DecisionTree.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "training_data = [\n",
    "    ['Green', 3, 'Mango'],\n",
    "    ['Yellow', 3, 'Mango'],\n",
    "    ['Red', 1, 'Grape'],\n",
    "    ['Red', 1, 'Grape'],\n",
    "    ['Yellow', 3, 'Lemon']\n",
    "]\n",
    "\n",
    "header = [\"color\", \"diameter\", \"label\"]\n",
    "\n",
    "# Find the unique values for a column in a dataset\n",
    "def unique_vals(rows, col):\n",
    "    return set([row[col] for row in rows])\n",
    "\n",
    "# Counts the number of each type of example in a dataset\n",
    "def class_counts(rows):\n",
    "    counts = {}\n",
    "    for row in rows:\n",
    "        label = row[-1]\n",
    "        if label not in counts:\n",
    "            counts[label] = 0 \n",
    "        counts[label] += 1\n",
    "        return counts\n",
    "\n",
    "# Test whether a value is numeric or not\n",
    "def is_numeric(value):\n",
    "    return isinstance(value, int) or isinstance(value, float)\n",
    "\n",
    "class Question:\n",
    "    \"\"\"\n",
    "    This class records a column number e.g 0 for color and column value e.g Green.\n",
    "    The match method is used to compare the feature value in an example \n",
    "    to the feature value stored in the questions\n",
    "    \"\"\"\n",
    "    def __init__(self, column, value):\n",
    "        self.column = column\n",
    "        self.value = value\n",
    "        \n",
    "    def match(self, example):\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 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))\n",
    "    \n",
    "def partition(rows, question):\n",
    "    \"\"\"\n",
    "    Partions a dataset.\n",
    "    For each row in the dataset, check if it matches the question. If so, add it\n",
    "    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\n",
    "\n",
    "def gini(rows):\n",
    "    # Calculate the Gini Impurity for a list of rows\n",
    "    counts = class_counts(rows)\n",
    "    impurity = 1\n",
    "    for lbl in counts:\n",
    "        prob_of_lbl = counts[lbl] / float(len(rows))\n",
    "        impurity -= prob_of_lbl**2\n",
    "    return impurity\n",
    "\n",
    "def info_gain(left, right, current_uncertainty):\n",
    "    # The Uncertainty of the starting node, minus weighted impurity of 2 child nodes\n",
    "    p = float(len(left)) / (len(left) + len(right))\n",
    "    return current_uncertainty - p * gini(left) - (1 - p) * gini(right)\n",
    "\n",
    "def find_best_split(rows):\n",
    "    \"\"\"Find the best split to ask by iterating over every feature/value \n",
    "    and calculating the info gain\"\"\"\n",
    "    best_gain = 0\n",
    "    best_question = None\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",
    "        values = set([row[col] for row in rows]) # unique values in the column\n",
    "        for val in values: # for each value\n",
    "            question = Question(col, val)\n",
    "            # try splitting the dataset\n",
    "            true_rows, false_rows = partition(rows, question)\n",
    "            # skip the split if it doesnt divide the dataset\n",
    "            if len(true_rows) == 0 or len(false_rows) == 0:\n",
    "                continue\n",
    "            # calculate info gain from the split\n",
    "            gain = info_gain(true_rows, false_rows, current_uncertainty)\n",
    "            \n",
    "            # It's more prudent to use > instead of >= here but this is a toy dataset\n",
    "            # If it works then it's fine I guess\n",
    "            if gain >= best_gain:\n",
    "                best_gain, best_question = gain, question\n",
    "    return best_gain, best_question\n",
    "\n",
    "\n",
    "class Leaf:\n",
    "    \"\"\"This node classifies data\n",
    "    It holds a dictionary of class e.g Mango -> number of times \n",
    "    it appears in the rows from the training data that reach this leaf\"\"\"\n",
    "    def __init__(self, rows):\n",
    "        self.predictions = class_counts(rows)\n",
    "\n",
    "\n",
    "class Decision_Node:\n",
    "    \"\"\"A decision node asks a question.\n",
    "    It holds a reference to the question and to the two child nodes\"\"\"\n",
    "    def __init__(self, question, true_branch, false_branch):\n",
    "        self.question = question\n",
    "        self.true_branch = true_branch\n",
    "        self.false_branch = false_branch\n",
    "\n",
    "\n",
    "def build_tree(rows):\n",
    "    \"\"\"Builds the tree. Let's see if it works...\"\"\"\n",
    "    # Try partitioning the dataset on each of the unique attributes\n",
    "    # Calculate the info gain\n",
    "    # Return the question that produces the highest gain\n",
    "    gain, question = find_best_split(rows)\n",
    "    \n",
    "    # Base case(no further info gain)\n",
    "    # Since we can ask no further questions, we return a leaf\n",
    "    if gain == 0:\n",
    "        return Leaf(rows)\n",
    "    \n",
    "    # Reaching here means we've found a useful feature/value to partition on\n",
    "    true_rows, false_rows = partition(rows, question)\n",
    "    \n",
    "    # Recursively build the true branch\n",
    "    true_branch = build_tree(true_rows)\n",
    "    \n",
    "    # Recursively build the false branch\n",
    "    false_branch = build_tree(false_rows)\n",
    "    \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 depending on the answer\n",
    "    return Decision_Node(question, true_branch, false_branch)\n",
    "\n",
    "\n",
    "def print_tree(node, spacing=\"\"):\n",
    "    \"\"\"Lets see if we can visualize it manually\"\"\"\n",
    "    # Base case: we've reached a leaf\n",
    "    if isinstance(node, Leaf):\n",
    "        print (spacing + \"Predict\", node.predictions)\n",
    "        return\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 + \" \")\n",
    "    \n",
    "\n",
    "def classify(row, node):\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/false branch\n",
    "    # Compare the feature/value stored in the node to the example we're considering\n",
    "    if node.question.match(row):\n",
    "        return classify(row, node.true_branch)\n",
    "    else:\n",
    "        return classify(row, node.false_branch)\n",
    "\n",
    "\n",
    "def print_leaf(counts):\n",
    "    \"\"\"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\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Predict {'Mango': 1}\n",
      "Actual: Mango. Predicted: {'Mango': '100%'}\n",
      "Actual: Mango. Predicted: {'Mango': '100%'}\n",
      "Actual: Grape. Predicted: {'Mango': '100%'}\n",
      "Actual: Grape. Predicted: {'Mango': '100%'}\n",
      "Actual: Lemon. Predicted: {'Mango': '100%'}\n"
     ]
    }
   ],
   "source": [
    "if __name__ == '__main__':\n",
    "    my_tree = build_tree(training_data)\n",
    "    print_tree(my_tree)\n",
    "    \n",
    "    # Evaluate\n",
    "    testing_data = [\n",
    "        ['Green', 3, 'Mango'],\n",
    "        ['Yellow', 4, 'Mango'],\n",
    "        ['Red', 2, 'Grape'],\n",
    "        ['Red', 1, 'Grape'],\n",
    "        ['Yellow', 3, 'Lemon'],\n",
    "    ]\n",
    "    for row in testing_data:\n",
    "        print(\"Actual: %s. Predicted: %s\" % (row[-1], print_leaf(classify(row, my_tree))))\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# This hasnt perfomed that well so maybe we could add more rows to the dataset\n",
    "# There is also a bug in the __repr__ method or the print_tree method"
   ]
  }
 ],
 "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}