lab10.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter, defaultdict\n",
    "from functools import partial\n",
    "import math, random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "def entropy(class_probabilities):\n",
    "    #entropia na podstawie listy prawdopodobienstw klas\n",
    "    return sum(-p * math.log(p,2) for p in class_probabilities if p)\n",
    "\n",
    "def class_probabilities(labels):\n",
    "    total_count = len(labels)\n",
    "    return [count / total_count for count in Counter(labels).values()]\n",
    "\n",
    "def data_entropy(labeled_data):\n",
    "    labels = [label for _,label in labeled_data]\n",
    "    probabilities = class_probabilities(labels)\n",
    "    return entropy(probabilities)\n",
    "\n",
    "def partition_entropy(subsets):\n",
    "    total_count = sum(len(subset) for subset in subsets)\n",
    "    return sum (data_entropy(subset) * len(subset) / total_count for subset in subsets)\n",
    "\n",
    "def group_by (items,key_fn):\n",
    "    groups = defaultdict(list)\n",
    "    for item in items:\n",
    "        key = key_fn(item)\n",
    "        groups[key].append(item)\n",
    "    return groups\n",
    "\n",
    "def partition_by(inputs,attribute):\n",
    "    return group_by(inputs,lambda x: x[0][attribute])\n",
    "\n",
    "def partition_entropy_by(inputs,attribute):\n",
    "    partitions = partition_by(inputs,attribute)\n",
    "    return partition_entropy(partitions.values())\n",
    "\n",
    "def classify(tree,input):\n",
    "    \"\"\"klasyfikacja danych wejsciowych\"\"\"\n",
    "    if tree in [True,False]:\n",
    "        return tree\n",
    "    \n",
    "    attribute,subtree_dict = tree\n",
    "    subtree_key = input.get(attribute)\n",
    "    if subtree_key not in subtree_dict:\n",
    "        subtree_key = None\n",
    "        \n",
    "    subtree = subtree_dict[subtree_key]\n",
    "    return classify(subtree,input)\n",
    "\n",
    "#reprezentacja drzewa na podstawie treningowych zbiorow danych\n",
    "def build_tree_id3(inputs, split_candidates=None):\n",
    "    if split_candidates is None:\n",
    "        split_candidates = inputs[0][0].keys()\n",
    "        \n",
    "    num_inputs = len(inputs)\n",
    "    num_trues = len([label for item,label in inputs if label])\n",
    "    num_falses = num_inputs - num_trues\n",
    "    \n",
    "    if num_trues == 0:\n",
    "        return False\n",
    "    if num_falses == 0:\n",
    "        return True\n",
    "    if not split_candidates:\n",
    "        return num_trues >= num_falses\n",
    "    \n",
    "    best_attribute = min(split_candidates,\n",
    "        key=partial(partition_entropy_by, inputs))\n",
    "\n",
    "    partitions = partition_by(inputs, best_attribute)\n",
    "    new_candidates = [a for a in split_candidates\n",
    "                      if a != best_attribute]\n",
    "\n",
    "    subtrees = { attribute : build_tree_id3(subset, new_candidates) for attribute, subset in partitions.items() }\n",
    "\n",
    "    subtrees[None] = num_trues > num_falses\n",
    "\n",
    "    return (best_attribute, subtrees)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "def forest_classify(trees, input):\n",
    "    votes = [classify(tree, input) for tree in trees]\n",
    "    vote_counts = Counter(votes)\n",
    "    return vote_counts.most_common(1)[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "level 0.6935361388961919\n",
      "lang 0.8601317128547441\n",
      "tweets 0.7884504573082896\n",
      "phd 0.8921589282623617\n",
      "\n",
      "lang 0.4\n",
      "tweets 0.0\n",
      "phd 0.9509775004326938\n",
      "\n",
      "building the tree\n",
      "('level', {'Senior': ('tweets', {'no': False, 'yes': True, None: False}), 'Mid': True, 'Junior': ('phd', {'no': True, 'yes': False, None: True}), None: True})\n",
      "Junior / Java / tweets / no phd True\n",
      "Junior / Java / tweets / phd False\n",
      "Intern True\n",
      "Senior False\n"
     ]
    }
   ],
   "source": [
    "if __name__ == \"__main__\":\n",
    "\n",
    "    #data from file\n",
    "    inputs = [\n",
    "        ({'level':'Senior','lang':'Java','tweets':'no','phd':'no'},   False),\n",
    "        ({'level':'Senior','lang':'Java','tweets':'no','phd':'yes'},  False),\n",
    "        ({'level':'Mid','lang':'Python','tweets':'no','phd':'no'},     True),\n",
    "        ({'level':'Junior','lang':'Python','tweets':'no','phd':'no'},  True),\n",
    "        ({'level':'Junior','lang':'R','tweets':'yes','phd':'no'},      True),\n",
    "        ({'level':'Junior','lang':'R','tweets':'yes','phd':'yes'},    False),\n",
    "        ({'level':'Mid','lang':'R','tweets':'yes','phd':'yes'},        True),\n",
    "        ({'level':'Senior','lang':'Python','tweets':'no','phd':'no'}, False),\n",
    "        ({'level':'Senior','lang':'R','tweets':'yes','phd':'no'},      True),\n",
    "        ({'level':'Junior','lang':'Python','tweets':'yes','phd':'no'}, True),\n",
    "        ({'level':'Senior','lang':'Python','tweets':'yes','phd':'yes'},True),\n",
    "        ({'level':'Mid','lang':'Python','tweets':'no','phd':'yes'},    True),\n",
    "        ({'level':'Mid','lang':'Java','tweets':'yes','phd':'no'},      True),\n",
    "        ({'level':'Junior','lang':'Python','tweets':'no','phd':'yes'},False)\n",
    "    ]\n",
    "    for key in ['level','lang','tweets','phd']:\n",
    "        print(key, partition_entropy_by(inputs, key))\n",
    "    print()\n",
    "    \n",
    "    senior_inputs = [(input, label)\n",
    "                     for input, label in inputs if input[\"level\"] == \"Senior\"]\n",
    "    \n",
    "    for key in ['lang', 'tweets', 'phd']:\n",
    "        print(key, partition_entropy_by(senior_inputs, key))\n",
    "    print()\n",
    "\n",
    "    print(\"building the tree\")\n",
    "    tree = build_tree_id3(inputs)\n",
    "    print(tree)\n",
    "\n",
    "    print(\"Junior / Java / tweets / no phd\", classify(tree,\n",
    "        { \"level\" : \"Junior\",\n",
    "          \"lang\" : \"Java\",\n",
    "          \"tweets\" : \"yes\",\n",
    "          \"phd\" : \"no\"} ))\n",
    "\n",
    "    print(\"Junior / Java / tweets / phd\", classify(tree,\n",
    "        { \"level\" : \"Junior\",\n",
    "                 \"lang\" : \"Java\",\n",
    "                 \"tweets\" : \"yes\",\n",
    "                 \"phd\" : \"yes\"} ))\n",
    "\n",
    "    print(\"Intern\", classify(tree, { \"level\" : \"Intern\" } ))\n",
    "    print(\"Senior\", classify(tree, { \"level\" : \"Senior\" } ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "level 0.6935361388961919\n",
      "lang 0.8601317128547441\n",
      "tweets 0.7884504573082896\n",
      "phd 0.8921589282623617\n",
      "building the tree\n",
      "('level', {'Junior': ('phd', {'no': ('lang', {'Python': ('tweets', {'yes': True, None: False}), 'R': True, None: True}), 'yes': ('lang', {'R': False, 'Java': True, None: False}), None: True}), 'Senior': ('lang', {'Java': False, 'Python': False, 'R': True, None: False}), 'Mid': True, None: True})\n"
     ]
    }
   ],
   "source": [
    "inputs20 = [\n",
    "        ({'level':'Junior','lang':'Python','tweets':'yes','phd':'no'},   False),\n",
    "        ({'level':'Senior','lang':'Java','tweets':'no','phd':'yes'},  False),\n",
    "        ({'level':'Mid','lang':'Python','tweets':'no','phd':'no'},     True),\n",
    "        ({'level':'Junior','lang':'R','tweets':'yes','phd':'no'},  True),\n",
    "        ({'level':'Junior','lang':'R','tweets':'yes','phd':'no'},      True),\n",
    "        ({'level':'Junior','lang':'R','tweets':'yes','phd':'yes'},    False),\n",
    "        ({'level':'Mid','lang':'R','tweets':'yes','phd':'yes'},        True),\n",
    "        ({'level':'Senior','lang':'Python','tweets':'no','phd':'no'}, False),\n",
    "        ({'level':'Senior','lang':'R','tweets':'yes','phd':'no'},      True),\n",
    "        ({'level':'Junior','lang':'Python','tweets':'yes','phd':'no'}, True),\n",
    "        ({'level':'Senior','lang':'Python','tweets':'yes','phd':'yes'},   False),\n",
    "        ({'level':'Senior','lang':'Java','tweets':'no','phd':'yes'},  False),\n",
    "        ({'level':'Mid','lang':'Python','tweets':'no','phd':'no'},     True),\n",
    "        ({'level':'Junior','lang':'Java','tweets':'no','phd':'yes'},  True),\n",
    "        ({'level':'Junior','lang':'R','tweets':'yes','phd':'no'},      True),\n",
    "        ({'level':'Junior','lang':'R','tweets':'yes','phd':'yes'},    False),\n",
    "        ({'level':'Mid','lang':'R','tweets':'yes','phd':'yes'},        True),\n",
    "        ({'level':'Senior','lang':'Python','tweets':'no','phd':'no'}, False),\n",
    "        ({'level':'Senior','lang':'R','tweets':'yes','phd':'no'},      True),\n",
    "        ({'level':'Mid','lang':'R','tweets':'yes','phd':'yes'}, True)\n",
    "]\n",
    "for key in ['level','lang','tweets','phd']:\n",
    "    print(key, partition_entropy_by(inputs, key))\n",
    "    \n",
    "print(\"building the tree\")\n",
    "tree = build_tree_id3(inputs20)\n",
    "print(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "level 0.6935361388961919\n",
      "lang 0.8601317128547441\n",
      "tweets 0.7884504573082896\n",
      "phd 0.8921589282623617\n",
      "building the tree\n",
      "('level', {'Junior': ('phd', {'yes': False, 'no': True, None: True}), 'Senior': ('tweets', {'no': ('lang', {'Python': ('phd', {'yes': False, 'no': True, None: False}), 'Java': False, 'R': False, None: False}), 'yes': True, None: False}), 'Mid': ('lang', {'Python': ('tweets', {'no': ('phd', {'no': True, None: True}), 'yes': False, None: True}), 'R': True, 'Java': True, None: True}), None: True})\n"
     ]
    }
   ],
   "source": [
    "inputs50 = [\n",
    "        ({'level':'Junior','lang':'R','tweets':'yes','phd':'yes'},   False),\n",
    "        ({'level':'Senior','lang':'Python','tweets':'no','phd':'yes'},  False),\n",
    "        ({'level':'Mid','lang':'Python','tweets':'no','phd':'no'},     True),\n",
    "        ({'level':'Junior','lang':'Python','tweets':'no','phd':'no'},  True),\n",
    "        ({'level':'Junior','lang':'Java','tweets':'yes','phd':'no'},      True),\n",
    "        ({'level':'Junior','lang':'R','tweets':'yes','phd':'yes'},    False),\n",
    "        ({'level':'Mid','lang':'R','tweets':'yes','phd':'yes'},        True),\n",
    "        ({'level':'Senior','lang':'Java','tweets':'no','phd':'no'}, False),\n",
    "        ({'level':'Mid','lang':'R','tweets':'yes','phd':'no'},      True),\n",
    "        ({'level':'Junior','lang':'Python','tweets':'yes','phd':'no'}, True),\n",
    "        ({'level':'Senior','lang':'R','tweets':'no','phd':'no'},   False),\n",
    "        ({'level':'Senior','lang':'Java','tweets':'no','phd':'yes'},  False),\n",
    "        ({'level':'Mid','lang':'Java','tweets':'no','phd':'no'},     True),\n",
    "        ({'level':'Senior','lang':'Python','tweets':'no','phd':'no'},  True),\n",
    "        ({'level':'Junior','lang':'R','tweets':'yes','phd':'no'},      True),\n",
    "        ({'level':'Junior','lang':'R','tweets':'yes','phd':'yes'},    False),\n",
    "        ({'level':'Mid','lang':'R','tweets':'yes','phd':'yes'},        True),\n",
    "        ({'level':'Mid','lang':'Python','tweets':'no','phd':'no'}, False),\n",
    "        ({'level':'Senior','lang':'R','tweets':'yes','phd':'no'},      True),\n",
    "        ({'level':'Junior','lang':'Python','tweets':'yes','phd':'no'}, True),\n",
    "        ({'level':'Senior','lang':'Java','tweets':'no','phd':'no'},   False),\n",
    "        ({'level':'Senior','lang':'Java','tweets':'no','phd':'yes'},  False),\n",
    "        ({'level':'Mid','lang':'Python','tweets':'no','phd':'no'},     True),\n",
    "        ({'level':'Junior','lang':'Java','tweets':'no','phd':'no'},  True),\n",
    "        ({'level':'Mid','lang':'R','tweets':'yes','phd':'no'},      True),\n",
    "        ({'level':'Junior','lang':'R','tweets':'yes','phd':'yes'},    False),\n",
    "        ({'level':'Mid','lang':'R','tweets':'yes','phd':'yes'},        True),\n",
    "        ({'level':'Senior','lang':'R','tweets':'no','phd':'no'}, False),\n",
    "        ({'level':'Senior','lang':'R','tweets':'yes','phd':'no'},      True),\n",
    "        ({'level':'Senior','lang':'Python','tweets':'yes','phd':'no'}, True),\n",
    "        ({'level':'Senior','lang':'Java','tweets':'no','phd':'no'},   False),\n",
    "        ({'level':'Senior','lang':'Java','tweets':'no','phd':'yes'},  False),\n",
    "        ({'level':'Mid','lang':'Python','tweets':'no','phd':'no'},     True),\n",
    "        ({'level':'Junior','lang':'Python','tweets':'no','phd':'no'},  True),\n",
    "        ({'level':'Junior','lang':'Java','tweets':'yes','phd':'no'},      True),\n",
    "        ({'level':'Junior','lang':'R','tweets':'yes','phd':'yes'},    False),\n",
    "        ({'level':'Mid','lang':'R','tweets':'yes','phd':'yes'},        True),\n",
    "        ({'level':'Senior','lang':'R','tweets':'no','phd':'no'}, False),\n",
    "        ({'level':'Senior','lang':'R','tweets':'yes','phd':'no'},      True),\n",
    "        ({'level':'Junior','lang':'Python','tweets':'yes','phd':'no'}, True),\n",
    "        ({'level':'Senior','lang':'Java','tweets':'no','phd':'no'},   False),\n",
    "        ({'level':'Senior','lang':'Python','tweets':'no','phd':'yes'},  False),\n",
    "        ({'level':'Mid','lang':'Python','tweets':'no','phd':'no'},     True),\n",
    "        ({'level':'Mid','lang':'Python','tweets':'no','phd':'no'},  True),\n",
    "        ({'level':'Junior','lang':'R','tweets':'yes','phd':'no'},      True),\n",
    "        ({'level':'Mid','lang':'Python','tweets':'yes','phd':'yes'},    False),\n",
    "        ({'level':'Mid','lang':'R','tweets':'yes','phd':'yes'},        True),\n",
    "        ({'level':'Senior','lang':'Python','tweets':'no','phd':'no'}, False),\n",
    "        ({'level':'Senior','lang':'R','tweets':'yes','phd':'no'},      True),\n",
    "        ({'level':'Senior','lang':'R','tweets':'yes','phd':'no'}, True)\n",
    "]\n",
    "\n",
    "for key in ['level','lang','tweets','phd']:\n",
    "    print(key, partition_entropy_by(inputs, key))\n",
    "    \n",
    "print(\"building the tree\")\n",
    "tree = build_tree_id3(inputs50)\n",
    "print(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}