Decision Tree/Decision Tree ( Multiclass simple).ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Toy dataset.\n",
    "# Format: each row is an example.\n",
    "# The last column is the label.\n",
    "# The first two columns are features.\n",
    "# Feel free to play with it by adding more features & examples.\n",
    "# Interesting note: I've written this so the 2nd and 5th examples\n",
    "# have the same features, but different labels - so we can see how the\n",
    "# tree handles this case.\n",
    "training_data = [\n",
    "    ['Green', 3, 'Apple'],\n",
    "    ['Yellow', 3, 'Apple'],\n",
    "    ['Red', 1, 'Grape'],\n",
    "    ['Red', 1, 'Grape'],\n",
    "    ['Yellow', 3, 'Lemon'],\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Column labels.\n",
    "# These are used only to print the tree.\n",
    "header = [\"color\", \"diameter\", \"label\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def unique_vals(rows, col):\n",
    "    \"\"\"Find the unique values for a column in a dataset.\"\"\"\n",
    "    return set([row[col] for row in rows])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Green', 'Red', 'Yellow'}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#######\n",
    "# Demo:a\n",
    "unique_vals(training_data, 0)\n",
    "# unique_vals(training_data, 1)\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def class_counts(rows):\n",
    "    \"\"\"Counts the number of each type of example in a dataset.\"\"\"\n",
    "    counts = {}  # a dictionary of label -> count.\n",
    "    for row in rows:\n",
    "        # in our dataset format, the label is always the last column\n",
    "        label = row[-1]\n",
    "        if label not in counts:\n",
    "            counts[label] = 0\n",
    "        counts[label] += 1\n",
    "    return counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Apple': 2, 'Grape': 2, 'Lemon': 1}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "class_counts(training_data)\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_numeric(value):\n",
    "    \"\"\"Test if a value is numeric.\"\"\"\n",
    "    return isinstance(value, int) or isinstance(value, float)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "is_numeric(7)\n",
    "# is_numeric(\"Red\")\n",
    "#######\n",
    "#isinstance([12,3,],list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Question:\n",
    "    \"\"\"A Question is used to partition a dataset.\n",
    "\n",
    "    This class just records a 'column number' (e.g., 0 for Color) and a\n",
    "    'column value' (e.g., Green). The 'match' method is used to compare\n",
    "    the feature value in an example to the feature value stored in the\n",
    "    question. See the demo below.\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, column, value):\n",
    "        self.column = column\n",
    "        self.value = value\n",
    "\n",
    "    def match(self, example): # row passing\n",
    "        # Compare the feature value in an example to the\n",
    "        # feature value in this question.\n",
    "        val = example[self.column]\n",
    "        if is_numeric(val):\n",
    "            return val >= self.value\n",
    "        else:\n",
    "            return val == self.value\n",
    "\n",
    "    def __repr__(self):\n",
    "        # This is just a helper method to print\n",
    "        # the question in a readable format.\n",
    "        condition = \"==\"\n",
    "        if is_numeric(self.value):\n",
    "            condition = \">=\"\n",
    "        return \"Is %s %s %s?\" % (\n",
    "            header[self.column], condition, str(self.value))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Is color == Green?"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# How about one for a categorical attribute\n",
    "q = Question(0, 'Green')\n",
    "q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Let's pick an example from the training set...\n",
    "example = training_data[0]\n",
    "# ... and see if it matches the question\n",
    "q.match(example) # this will be true, since the first example is Green.\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition(rows, question): # question is object of Question class\n",
    "    \"\"\"Partitions a dataset.\n",
    "\n",
    "    For each row in the dataset, check if it matches the question. If\n",
    "    so, add it to 'true rows', otherwise, add it to 'false rows'.\n",
    "    \"\"\"\n",
    "    true_rows, false_rows = [], []\n",
    "    for row in rows:\n",
    "        if question.match(row):\n",
    "            true_rows.append(row)\n",
    "        else:\n",
    "            false_rows.append(row)\n",
    "    return true_rows, false_rows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "# Let's partition the training data based on whether rows are Red.\n",
    "true_rows, false_rows = partition(training_data, Question(0, 'Red')) # 0 indicating from which column this value belongs\n",
    "# This will contain all the 'Red' rows.\n",
    "true_rows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['Green', 3, 'Apple'],\n",
       " ['Yellow', 3, 'Apple'],\n",
       " ['Red', 1, 'Grape'],\n",
       " ['Red', 1, 'Grape'],\n",
       " ['Yellow', 3, 'Lemon']]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# This will contain everything else.\n",
    "false_rows\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gini(rows):\n",
    "    \"\"\"Calculate the Gini Impurity for a list of rows.\n",
    "\n",
    "    There are a few different ways to do this, I thought this one was\n",
    "    the most concise. See:\n",
    "    https://en.wikipedia.org/wiki/Decision_tree_learning#Gini_impurity\n",
    "    \"\"\"\n",
    "    counts = class_counts(rows)\n",
    "    impurity = 1 # all data value are not equal \n",
    "    for lbl in counts:\n",
    "        prob_of_lbl = counts[lbl] / float(len(rows)) # each label probability\n",
    "        impurity = impurity - prob_of_lbl**2\n",
    "    return impurity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0\n",
      "0.6399999999999999\n"
     ]
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "# Let's look at some example to understand how Gini Impurity works.\n",
    "#\n",
    "# First, we'll look at a dataset with no mixing.\n",
    "no_mixing = [['Apple'],\n",
    "              ['Apple']]\n",
    "# this will return 0\n",
    "#gini(no_mixing)\n",
    "print(gini(no_mixing)) # this indicates that the data you passed is contain same type of data which means data is classified\n",
    "print(gini(training_data))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Now, we'll look at dataset with a 50:50 apples:oranges ratio\n",
    "some_mixing = [['Apple'],\n",
    "               ['Orange']]\n",
    "# this will return 0.5 - meaning, there's a 50% chance of misclassifying\n",
    "# a random example we draw from the dataset.\n",
    "gini(some_mixing)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.7999999999999998"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Now, we'll look at a dataset with many different labels\n",
    "lots_of_mixing = [['Apple'],\n",
    "                  ['Orange'],\n",
    "                  ['Grape'],\n",
    "                  ['Grapefruit'],\n",
    "                  ['Blueberry']]\n",
    "# This will return 0.8\n",
    "gini(lots_of_mixing)\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "def info_gain(left, right, current_uncertainty):\n",
    "    \"\"\"Information Gain.\n",
    "    \n",
    "    The uncertainty of the starting node, minus the weighted impurity of\n",
    "    two child nodes.\n",
    "    \"\"\"\n",
    "    p = float(len(left)) / (len(left) + len(right))\n",
    "    return current_uncertainty - p * gini(left) - (1 - p) * gini(right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.6399999999999999"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "# Calculate the uncertainy of our training data.\n",
    "current_uncertainty = gini(training_data)\n",
    "current_uncertainty # it means 0.639 fluctuations are there in dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.1399999999999999"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# How much information do we gain by partioning on 'Green'?\n",
    "true_rows, false_rows = partition(training_data, Question(0, 'Green'))\n",
    "info_gain(true_rows, false_rows, current_uncertainty)  # information gain should be maximum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.37333333333333324"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# What about if we partioned on 'Red' instead?\n",
    "true_rows, false_rows = partition(training_data, Question(0,'Red'))\n",
    "info_gain(true_rows, false_rows, current_uncertainty)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.37333333333333324"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "true_rows, false_rows = partition(training_data, Question(1,3))\n",
    "info_gain(true_rows, false_rows, current_uncertainty)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.17333333333333323"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "true_rows, false_rows = partition(training_data, Question(0,'Yellow'))\n",
    "info_gain(true_rows, false_rows, current_uncertainty)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['Red', 1, 'Grape'], ['Red', 1, 'Grape']]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# It looks like we learned more using 'Red' (0.37), than 'Green' (0.14).\n",
    "# Why? Look at the different splits that result, and see which one\n",
    "# looks more 'unmixed' to you.\n",
    "true_rows, false_rows = partition(training_data, Question(0,'Red'))\n",
    "\n",
    "# Here, the true_rows contain only 'Grapes'.\n",
    "true_rows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['Green', 3, 'Apple'], ['Yellow', 3, 'Apple'], ['Yellow', 3, 'Lemon']]"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# And the false rows contain two types of fruit. Not too bad.\n",
    "false_rows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['Green', 3, 'Apple']]"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# On the other hand, partitioning by Green doesn't help so much.\n",
    "true_rows, false_rows = partition(training_data, Question(0,'Green'))\n",
    "\n",
    "# We've isolated one apple in the true rows.\n",
    "true_rows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['Yellow', 3, 'Apple'],\n",
       " ['Red', 1, 'Grape'],\n",
       " ['Red', 1, 'Grape'],\n",
       " ['Yellow', 3, 'Lemon']]"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# But, the false-rows are badly mixed up.\n",
    "false_rows\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_best_split(rows):\n",
    "    \"\"\"Find the best question to ask by iterating over every feature / value\n",
    "    and calculating the information gain.\"\"\"\n",
    "    best_gain = 0  # keep track of the best information gain\n",
    "    best_question = None  # keep tra in of the feature / value that produced it\n",
    "    current_uncertainty = gini(rows)\n",
    "    n_features = len(rows[0]) - 1  # number of columns\n",
    "\n",
    "    for col in range(n_features):  # for each feature\n",
    "\n",
    "        values = set([row[col] for row in rows])  # unique values in the column\n",
    "\n",
    "        for val in values:  # for each value\n",
    "\n",
    "            question = Question(col, val)\n",
    "\n",
    "            # try splitting the dataset\n",
    "            true_rows, false_rows = partition(rows, question)\n",
    "\n",
    "            # Skip this split if it doesn't divide the\n",
    "            # dataset.\n",
    "            if len(true_rows) == 0 or len(false_rows) == 0:\n",
    "                continue\n",
    "\n",
    "            # Calculate the information gain from this split\n",
    "            gain = info_gain(true_rows, false_rows, current_uncertainty)\n",
    "\n",
    "            # You actually can use '>' instead of '>=' here\n",
    "            # but I wanted the tree to look a certain way for our\n",
    "            # toy dataset.\n",
    "            if gain >= best_gain:\n",
    "                best_gain, best_question = gain, question\n",
    "\n",
    "    return best_gain, best_question"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.37333333333333324\n",
      "Is diameter >= 3?\n"
     ]
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "# Find the best question to ask first for our toy dataset.\n",
    "best_gain, best_question = find_best_split(training_data)\n",
    "best_question\n",
    "# FYI: is color == Red is just as good. See the note in the code above\n",
    "# where I used '>='.\n",
    "#######\n",
    "print(best_gain)\n",
    "print(best_question)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Leaf:\n",
    "    \"\"\"A Leaf node classifies data.\n",
    "\n",
    "    This holds a dictionary of class (e.g., \"Apple\") -> number of times\n",
    "    it appears in the rows from the training data that reach this leaf.\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self, rows):\n",
    "        self.predictions = class_counts(rows)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Decision_Node:\n",
    "    \"\"\"A Decision Node asks a question.\n",
    "\n",
    "    This holds a reference to the question, and to the two child nodes.\n",
    "    \"\"\"\n",
    "\n",
    "    def __init__(self,\n",
    "                 question,\n",
    "                 true_branch,\n",
    "                 false_branch):\n",
    "        self.question = question\n",
    "        self.true_branch = true_branch\n",
    "        self.false_branch = false_branch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_tree(rows):\n",
    "    \"\"\"Builds the tree.\n",
    "\n",
    "    Rules of recursion: \n",
    "    1) Believe that it works. \n",
    "    2) Start by checking for the base case (no further information gain). \n",
    "    3) Prepare for giant stack traces.\n",
    "    \n",
    "    \"\"\"\n",
    "\n",
    "    # Try partitioing the dataset on each of the unique attribute,\n",
    "    # calculate the information gain,\n",
    "    # and return the question that produces the highest gain.\n",
    "    gain, question = find_best_split(rows)\n",
    "    #print(gain,question)\n",
    "    # Base case: no further info gain\n",
    "    # Since we can ask no further questions,\n",
    "    # we'll return a leaf.\n",
    "    if gain == 0:\n",
    "        return Leaf(rows)\n",
    "\n",
    "    # If we reach here, we have found a useful feature / value\n",
    "    # to partition on.\n",
    "    true_rows, false_rows = partition(rows, question)\n",
    "    #print(true_rows,false_rows)\n",
    "    # Recursively build the true branch.\n",
    "    true_branch = build_tree(true_rows)\n",
    "    #print(true_branch)\n",
    "    #print('****************')\n",
    "    # Recursively build the false branch.\n",
    "    false_branch = build_tree(false_rows)\n",
    "    ##print(false_branch)\n",
    "    #print('----------------')\n",
    "    # Return a Question node.\n",
    "    # This records the best feature / value to ask at this point,\n",
    "    # as well as the branches to follow\n",
    "    # dependingo on the answer.\n",
    "    return Decision_Node(question, true_branch, false_branch)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<__main__.Decision_Node at 0x2445e309a58>"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "build_tree(training_data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_tree(node, spacing=\" \"):\n",
    "    \"\"\"World's most elegant tree printing function.\"\"\"\n",
    "\n",
    "    # Base case: we've reached a leaf\n",
    "    if isinstance(node, Leaf):\n",
    "        print (spacing + \"Predict\", node.predictions)\n",
    "        return\n",
    "\n",
    "    # Print the question at this node\n",
    "    print (spacing + str(node.question))\n",
    "\n",
    "    # Call this function recursively on the true branch\n",
    "    print (spacing + '--> True:')\n",
    "    print_tree(node.true_branch, spacing + \"  \")\n",
    "\n",
    "    # Call this function recursively on the false branch\n",
    "    print (spacing + '--> False:')\n",
    "    print_tree(node.false_branch, spacing + \"  \")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "my_tree = build_tree(training_data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " Is diameter >= 3?\n",
      " --> True:\n",
      "   Is color == Yellow?\n",
      "   --> True:\n",
      "     Predict {'Apple': 1, 'Lemon': 1}\n",
      "   --> False:\n",
      "     Predict {'Apple': 1}\n",
      " --> False:\n",
      "   Predict {'Grape': 2}\n"
     ]
    }
   ],
   "source": [
    "print_tree(my_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "def classify(row, node):\n",
    "    \"\"\"See the 'rules of recursion' above.\"\"\"\n",
    "\n",
    "    # Base case: we've reached a leaf\n",
    "    if isinstance(node, Leaf):\n",
    "        return node.predictions\n",
    "\n",
    "    # Decide whether to follow the true-branch or the false-branch.\n",
    "    # Compare the feature / value stored in the node,\n",
    "    # to the example we're considering.\n",
    "    if node.question.match(row):  # check each - each rows\n",
    "        return classify(row, node.true_branch)\n",
    "    else:\n",
    "        return classify(row, node.false_branch)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Apple': 1}"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "# The tree predicts the 1st row of our\n",
    "# training data is an apple with confidence 1.\n",
    "classify(training_data[0], my_tree)\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_leaf(counts):\n",
    "    \"\"\"A nicer way to print the predictions at a leaf.\"\"\"\n",
    "    total = sum(counts.values()) * 1.0\n",
    "    probs = {}\n",
    "    for lbl in counts.keys():\n",
    "        probs[lbl] = str(int(counts[lbl] / total * 100)) + \"%\"\n",
    "    return probs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Apple': '100%'}"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "# Printing that a bit nicer\n",
    "print_leaf(classify(training_data[0], my_tree))\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Apple': '50%', 'Lemon': '50%'}"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#######\n",
    "# Demo:\n",
    "# On the second example, the confidence is lower\n",
    "print_leaf(classify(training_data[1], my_tree))\n",
    "#######"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Evaluate\n",
    "testing_data = [\n",
    "    ['Green', 3, 'Apple'],\n",
    "    ['Yellow', 4, 'Apple'],\n",
    "    ['Red', 2, 'Grape'],\n",
    "    ['Red', 1, 'Grape'],\n",
    "    ['Yellow', 3, 'Lemon'],\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Actual: Apple. Predicted: {'Apple': '100%'}\n",
      "Actual: Apple. Predicted: {'Apple': '50%', 'Lemon': '50%'}\n",
      "Actual: Grape. Predicted: {'Grape': '100%'}\n",
      "Actual: Grape. Predicted: {'Grape': '100%'}\n",
      "Actual: Lemon. Predicted: {'Apple': '50%', 'Lemon': '50%'}\n"
     ]
    }
   ],
   "source": [
    "for row in testing_data:\n",
    "    print (\"Actual: %s. Predicted: %s\" %\n",
    "           (row[-1], print_leaf(classify(row, my_tree))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "def entropy(rows):\n",
    "    #initialise entropy\n",
    "    entropy=0\n",
    "    from math import log\n",
    "    #calculating log(x) in base 2\n",
    "    log2=lambda x:log(x)/log(2)\n",
    "    count=class_counts(rows)\n",
    "    #storing and traversing the dictionary\n",
    "    for label in count:\n",
    "        #probablity of each unique label\n",
    "        p=count[label]/float(len(rows))\n",
    "        #calculating entropy\n",
    "        entropy-=p*log2(p)\n",
    "    return entropy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.5219280948873621"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "entropy(training_data)"
   ]
  }
 ],
 "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
}