machine_learning_algorithms/decision_tree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithms from Scratch: Decision Tree\n",
    "## Detailing and Building a Decision Tree model from Scratch\n",
    "\n",
    "Those of you familiar with my earlier writings would recall that I once wrote an overview of the Random Forest algorithm. A solid foundation on Decision trees is a prerequisite to understanding the inner workings of Random Forest; The Random forest builds multiple Decision tree's and outputs the average over the predictions of each tree for regression problems, and in classification problems it outputs the relative majority of the predictions from each tree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To build on the above story, I will be focusing much more on the Decision tree learning algorithm as it is a fundamental algorithm in the Machine Learning space. Many models base their structure on the Decision tree model such as the Random Forest and Gradient Boosted tree's. Additionally, I will be doing a Python implementation of this algorithm from scratch to further expand our intuition on what is happening within our algorithm.\n",
    "\n",
    "Defining terms: \n",
    "* Parametric Models - Used to make inferences about population parameters, however these inferences are not valid if all assumptions are not met. \n",
    "* Non-Parametric Models - Do not assume that the data or population have any characteristic structure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Decision Tree\n",
    "\n",
    "Popular due to its intelligibility and simplicity, the Decision tree is one of the easiest algorithms to visualize and interpret which is handy when presenting results to a non-technical audience, as is often requi`red in industry. If we simply consider a tree in a flowchart-like state, from root to leaves where the path to a leaf from the root defines decision rules on the features, then we already have a good level of intuition required to understand Decision tree learning.\n",
    "Unlike the first two algorithms we covered in the Algorithms from Scratch series (Linear Regression and Logistic Regression), the Decision tree algorithm is a non-parametric algorithm meaning that it does not make an assumption about the data or population. This does have an affect on our model since we are introducing variance into the model during training, making the Decision tree much more prone to overfitting.\n",
    "\n",
    "In the field of Machine Learning there are two main Decision tree models. The one we use depends on the type of target variable we are attempting to predict: \n",
    "\n",
    "Classification tree: A tree model employed to predict a target variable that takes a discrete value. Thereby, the leaf node represents a class and the branches represent conjunctions of the features that lead to those class labels.\n",
    "Regression tree: A tree model employed to predict a target variable that takes a continuous value. Contrary to the classification tree, in the Regression tree, each leaf node contains a continuous value (i.e. a house price); The branches represent conjunctions of the features that lead to each continuous variable.\n",
    "Note: An umbrella term to refer to both procedures is Classification and Regression Tree (CART), first introduced by Breiman et al. in 1984. \n",
    "\n",
    "In Figure 1 we can see the structure that is followed by CART algorithms. Though this structure is set for both trees, there are some subtle differences between classification and regression trees such as the output from each tree - the classification tree returns mode class of the leaf node and the regression tree returns the mean."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another significant difference between the two algorithms is the criterion that we try to minimize when partitioning the feature space. Generally, we want to select the feature, j, and split-point, s, that best splits the feature space into 2 regions, but how this is done in a regression tree and classification tree differs as is shown in Figure 2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Chunking the Algorithm \n",
    "\n",
    "Note: We will be building a Decision tree classifier with gini impurity as the criterion for the split. \n",
    "\n",
    "1. Consider all possible splits of feature j and split point s\n",
    "2. Having found the best split, partition the data into 2 resulting regions\n",
    "3. Repeat 1 and 2 until stopping criterion is reached\n",
    "\n",
    "This demonstrates a phenomena known as recursion in computer science - A method of solving a problem where the solution depends on solutions to smaller instances of the same problem (Source: Wikipedia), and Binary splitting hence in some illustrations step 1–2 is referred to as recursive binary splitting."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Implementation\n",
    "\n",
    "For this implementation we will be leveraging the following frameworks: \n",
    "* NumPy (linear algebra and data manipulation)\n",
    "* Pandas (data manipulation)\n",
    "* Sci-kit Learn (machine learning)\n",
    "* Graphviz (graph visualization software) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 157,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np \n",
    "import pandas as pd \n",
    "import graphviz\n",
    "from sklearn.metrics import accuracy_score\n",
    "from sklearn.datasets import load_iris\n",
    "from sklearn.tree import DecisionTreeClassifier\n",
    "from sklearn.tree import export_graphviz\n",
    "from sklearn.model_selection import train_test_split\n",
    "\n",
    "pd.options.mode.chained_assignment = None  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The dataset we will use is the iris dataset from scikit learn."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(150, 6)\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>sepal length (cm)</th>\n",
       "      <th>sepal width (cm)</th>\n",
       "      <th>petal length (cm)</th>\n",
       "      <th>petal width (cm)</th>\n",
       "      <th>target</th>\n",
       "      <th>target_names</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>5.1</td>\n",
       "      <td>3.5</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "      <td>setosa</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>4.9</td>\n",
       "      <td>3.0</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "      <td>setosa</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>4.7</td>\n",
       "      <td>3.2</td>\n",
       "      <td>1.3</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "      <td>setosa</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>4.6</td>\n",
       "      <td>3.1</td>\n",
       "      <td>1.5</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "      <td>setosa</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>5.0</td>\n",
       "      <td>3.6</td>\n",
       "      <td>1.4</td>\n",
       "      <td>0.2</td>\n",
       "      <td>0</td>\n",
       "      <td>setosa</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   sepal length (cm)  sepal width (cm)  petal length (cm)  petal width (cm)  \\\n",
       "0                5.1               3.5                1.4               0.2   \n",
       "1                4.9               3.0                1.4               0.2   \n",
       "2                4.7               3.2                1.3               0.2   \n",
       "3                4.6               3.1                1.5               0.2   \n",
       "4                5.0               3.6                1.4               0.2   \n",
       "\n",
       "   target target_names  \n",
       "0       0       setosa  \n",
       "1       0       setosa  \n",
       "2       0       setosa  \n",
       "3       0       setosa  \n",
       "4       0       setosa  "
      ]
     },
     "execution_count": 158,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# loading the data set\n",
    "dataset = load_iris(as_frame=True)\n",
    "df= pd.DataFrame(data= dataset.data)\n",
    "\n",
    "# adding the target and target names to dataframe\n",
    "target_zip= dict(zip(set(dataset.target), dataset.target_names))\n",
    "df[\"target\"] = dataset.target\n",
    "df[\"target_names\"] = df[\"target\"].map(target_zip)\n",
    "\n",
    "print(df.shape)\n",
    "df.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Seperating to X and Y \n",
    "X = df.iloc[:, :4]\n",
    "y = df.iloc[:, -1]\n",
    "\n",
    "# splitting training and test\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, train_size=0.75, shuffle=True, random_state=24) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 160,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "DecisionTreeClassifier()"
      ]
     },
     "execution_count": 160,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dt = DecisionTreeClassifier()\n",
    "dt.fit(X_train, y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 161,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.38.0 (20140413.2041)\r\n",
       " -->\r\n",
       "<!-- Title: Tree Pages: 1 -->\r\n",
       "<svg width=\"626pt\" height=\"671pt\"\r\n",
       " viewBox=\"0.00 0.00 626.00 671.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 667)\">\r\n",
       "<title>Tree</title>\r\n",
       "<polygon fill=\"white\" stroke=\"none\" points=\"-4,4 -4,-667 622,-667 622,4 -4,4\"/>\r\n",
       "<!-- 0 -->\r\n",
       "<g id=\"node1\" class=\"node\"><title>0</title>\r\n",
       "<path fill=\"#f4fef8\" stroke=\"black\" d=\"M296,-663C296,-663 169,-663 169,-663 163,-663 157,-657 157,-651 157,-651 157,-592 157,-592 157,-586 163,-580 169,-580 169,-580 296,-580 296,-580 302,-580 308,-586 308,-592 308,-592 308,-651 308,-651 308,-657 302,-663 296,-663\"/>\r\n",
       "<text text-anchor=\"start\" x=\"165\" y=\"-647.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">petal width (cm) ≤ 0.8</text>\r\n",
       "<text text-anchor=\"start\" x=\"195\" y=\"-632.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.663</text>\r\n",
       "<text text-anchor=\"start\" x=\"185\" y=\"-617.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 112</text>\r\n",
       "<text text-anchor=\"start\" x=\"172\" y=\"-602.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [38, 42, 32]</text>\r\n",
       "<text text-anchor=\"start\" x=\"177\" y=\"-587.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = versicolor</text>\r\n",
       "</g>\r\n",
       "<!-- 1 -->\r\n",
       "<g id=\"node2\" class=\"node\"><title>1</title>\r\n",
       "<path fill=\"#e58139\" stroke=\"black\" d=\"M202,-536.5C202,-536.5 105,-536.5 105,-536.5 99,-536.5 93,-530.5 93,-524.5 93,-524.5 93,-480.5 93,-480.5 93,-474.5 99,-468.5 105,-468.5 105,-468.5 202,-468.5 202,-468.5 208,-468.5 214,-474.5 214,-480.5 214,-480.5 214,-524.5 214,-524.5 214,-530.5 208,-536.5 202,-536.5\"/>\r\n",
       "<text text-anchor=\"start\" x=\"124.5\" y=\"-521.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"start\" x=\"110\" y=\"-506.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 38</text>\r\n",
       "<text text-anchor=\"start\" x=\"101\" y=\"-491.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [38, 0, 0]</text>\r\n",
       "<text text-anchor=\"start\" x=\"107.5\" y=\"-476.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = setosa</text>\r\n",
       "</g>\r\n",
       "<!-- 0&#45;&gt;1 -->\r\n",
       "<g id=\"edge1\" class=\"edge\"><title>0&#45;&gt;1</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M205.091,-579.907C197.492,-568.652 189.231,-556.418 181.593,-545.106\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"184.391,-542.996 175.895,-536.667 178.59,-546.913 184.391,-542.996\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"171.136\" y=\"-557.51\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">True</text>\r\n",
       "</g>\r\n",
       "<!-- 2 -->\r\n",
       "<g id=\"node3\" class=\"node\"><title>2</title>\r\n",
       "<path fill=\"#d0f9e1\" stroke=\"black\" d=\"M379,-544C379,-544 244,-544 244,-544 238,-544 232,-538 232,-532 232,-532 232,-473 232,-473 232,-467 238,-461 244,-461 244,-461 379,-461 379,-461 385,-461 391,-467 391,-473 391,-473 391,-532 391,-532 391,-538 385,-544 379,-544\"/>\r\n",
       "<text text-anchor=\"start\" x=\"240\" y=\"-528.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">petal width (cm) ≤ 1.65</text>\r\n",
       "<text text-anchor=\"start\" x=\"274\" y=\"-513.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.491</text>\r\n",
       "<text text-anchor=\"start\" x=\"268\" y=\"-498.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 74</text>\r\n",
       "<text text-anchor=\"start\" x=\"255\" y=\"-483.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 42, 32]</text>\r\n",
       "<text text-anchor=\"start\" x=\"256\" y=\"-468.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = versicolor</text>\r\n",
       "</g>\r\n",
       "<!-- 0&#45;&gt;2 -->\r\n",
       "<g id=\"edge2\" class=\"edge\"><title>0&#45;&gt;2</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M259.909,-579.907C265.914,-571.014 272.331,-561.509 278.529,-552.331\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"281.444,-554.267 284.14,-544.021 275.643,-550.35 281.444,-554.267\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"288.898\" y=\"-564.864\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">False</text>\r\n",
       "</g>\r\n",
       "<!-- 3 -->\r\n",
       "<g id=\"node4\" class=\"node\"><title>3</title>\r\n",
       "<path fill=\"#47e78a\" stroke=\"black\" d=\"M291,-425C291,-425 150,-425 150,-425 144,-425 138,-419 138,-413 138,-413 138,-354 138,-354 138,-348 144,-342 150,-342 150,-342 291,-342 291,-342 297,-342 303,-348 303,-354 303,-354 303,-413 303,-413 303,-419 297,-425 291,-425\"/>\r\n",
       "<text text-anchor=\"start\" x=\"146\" y=\"-409.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">petal length (cm) ≤ 4.95</text>\r\n",
       "<text text-anchor=\"start\" x=\"183\" y=\"-394.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.127</text>\r\n",
       "<text text-anchor=\"start\" x=\"177\" y=\"-379.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 44</text>\r\n",
       "<text text-anchor=\"start\" x=\"168\" y=\"-364.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 41, 3]</text>\r\n",
       "<text text-anchor=\"start\" x=\"165\" y=\"-349.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = versicolor</text>\r\n",
       "</g>\r\n",
       "<!-- 2&#45;&gt;3 -->\r\n",
       "<g id=\"edge3\" class=\"edge\"><title>2&#45;&gt;3</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M279.928,-460.907C272.94,-451.923 265.467,-442.315 258.261,-433.05\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"260.918,-430.766 252.016,-425.021 255.393,-435.063 260.918,-430.766\"/>\r\n",
       "</g>\r\n",
       "<!-- 10 -->\r\n",
       "<g id=\"node11\" class=\"node\"><title>10</title>\r\n",
       "<path fill=\"#8540e6\" stroke=\"black\" d=\"M474,-425C474,-425 333,-425 333,-425 327,-425 321,-419 321,-413 321,-413 321,-354 321,-354 321,-348 327,-342 333,-342 333,-342 474,-342 474,-342 480,-342 486,-348 486,-354 486,-354 486,-413 486,-413 486,-419 480,-425 474,-425\"/>\r\n",
       "<text text-anchor=\"start\" x=\"329\" y=\"-409.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">petal length (cm) ≤ 4.85</text>\r\n",
       "<text text-anchor=\"start\" x=\"366\" y=\"-394.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.064</text>\r\n",
       "<text text-anchor=\"start\" x=\"360\" y=\"-379.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 30</text>\r\n",
       "<text text-anchor=\"start\" x=\"351\" y=\"-364.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 1, 29]</text>\r\n",
       "<text text-anchor=\"start\" x=\"353.5\" y=\"-349.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = virginica</text>\r\n",
       "</g>\r\n",
       "<!-- 2&#45;&gt;10 -->\r\n",
       "<g id=\"edge10\" class=\"edge\"><title>2&#45;&gt;10</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M343.419,-460.907C350.484,-451.923 358.039,-442.315 365.324,-433.05\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"368.208,-435.045 371.637,-425.021 362.705,-430.718 368.208,-435.045\"/>\r\n",
       "</g>\r\n",
       "<!-- 4 -->\r\n",
       "<g id=\"node5\" class=\"node\"><title>4</title>\r\n",
       "<path fill=\"#39e581\" stroke=\"black\" d=\"M115,-298.5C115,-298.5 12,-298.5 12,-298.5 6,-298.5 -7.10543e-015,-292.5 -7.10543e-015,-286.5 -7.10543e-015,-286.5 -7.10543e-015,-242.5 -7.10543e-015,-242.5 -7.10543e-015,-236.5 6,-230.5 12,-230.5 12,-230.5 115,-230.5 115,-230.5 121,-230.5 127,-236.5 127,-242.5 127,-242.5 127,-286.5 127,-286.5 127,-292.5 121,-298.5 115,-298.5\"/>\r\n",
       "<text text-anchor=\"start\" x=\"34.5\" y=\"-283.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"start\" x=\"20\" y=\"-268.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 40</text>\r\n",
       "<text text-anchor=\"start\" x=\"11\" y=\"-253.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 40, 0]</text>\r\n",
       "<text text-anchor=\"start\" x=\"8\" y=\"-238.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = versicolor</text>\r\n",
       "</g>\r\n",
       "<!-- 3&#45;&gt;4 -->\r\n",
       "<g id=\"edge4\" class=\"edge\"><title>3&#45;&gt;4</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M166.03,-341.907C149.89,-329.88 132.251,-316.735 116.224,-304.791\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"118.116,-301.836 108.006,-298.667 113.933,-307.449 118.116,-301.836\"/>\r\n",
       "</g>\r\n",
       "<!-- 5 -->\r\n",
       "<g id=\"node6\" class=\"node\"><title>5</title>\r\n",
       "<path fill=\"#ab7bee\" stroke=\"black\" d=\"M292,-306C292,-306 157,-306 157,-306 151,-306 145,-300 145,-294 145,-294 145,-235 145,-235 145,-229 151,-223 157,-223 157,-223 292,-223 292,-223 298,-223 304,-229 304,-235 304,-235 304,-294 304,-294 304,-300 298,-306 292,-306\"/>\r\n",
       "<text text-anchor=\"start\" x=\"153\" y=\"-290.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">petal width (cm) ≤ 1.55</text>\r\n",
       "<text text-anchor=\"start\" x=\"187\" y=\"-275.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.375</text>\r\n",
       "<text text-anchor=\"start\" x=\"185\" y=\"-260.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 4</text>\r\n",
       "<text text-anchor=\"start\" x=\"176\" y=\"-245.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 1, 3]</text>\r\n",
       "<text text-anchor=\"start\" x=\"174.5\" y=\"-230.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = virginica</text>\r\n",
       "</g>\r\n",
       "<!-- 3&#45;&gt;5 -->\r\n",
       "<g id=\"edge5\" class=\"edge\"><title>3&#45;&gt;5</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M221.888,-341.907C222.173,-333.558 222.477,-324.671 222.773,-316.02\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"226.271,-316.135 223.115,-306.021 219.275,-315.895 226.271,-316.135\"/>\r\n",
       "</g>\r\n",
       "<!-- 6 -->\r\n",
       "<g id=\"node7\" class=\"node\"><title>6</title>\r\n",
       "<path fill=\"#8139e5\" stroke=\"black\" d=\"M115.5,-179.5C115.5,-179.5 23.5,-179.5 23.5,-179.5 17.5,-179.5 11.5,-173.5 11.5,-167.5 11.5,-167.5 11.5,-123.5 11.5,-123.5 11.5,-117.5 17.5,-111.5 23.5,-111.5 23.5,-111.5 115.5,-111.5 115.5,-111.5 121.5,-111.5 127.5,-117.5 127.5,-123.5 127.5,-123.5 127.5,-167.5 127.5,-167.5 127.5,-173.5 121.5,-179.5 115.5,-179.5\"/>\r\n",
       "<text text-anchor=\"start\" x=\"40.5\" y=\"-164.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"start\" x=\"30\" y=\"-149.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 2</text>\r\n",
       "<text text-anchor=\"start\" x=\"21\" y=\"-134.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 0, 2]</text>\r\n",
       "<text text-anchor=\"start\" x=\"19.5\" y=\"-119.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = virginica</text>\r\n",
       "</g>\r\n",
       "<!-- 5&#45;&gt;6 -->\r\n",
       "<g id=\"edge6\" class=\"edge\"><title>5&#45;&gt;6</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M170.724,-222.907C154.79,-210.88 137.375,-197.735 121.552,-185.791\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"123.529,-182.898 113.439,-179.667 119.312,-188.485 123.529,-182.898\"/>\r\n",
       "</g>\r\n",
       "<!-- 7 -->\r\n",
       "<g id=\"node8\" class=\"node\"><title>7</title>\r\n",
       "<path fill=\"#ffffff\" stroke=\"black\" d=\"M299,-187C299,-187 158,-187 158,-187 152,-187 146,-181 146,-175 146,-175 146,-116 146,-116 146,-110 152,-104 158,-104 158,-104 299,-104 299,-104 305,-104 311,-110 311,-116 311,-116 311,-175 311,-175 311,-181 305,-187 299,-187\"/>\r\n",
       "<text text-anchor=\"start\" x=\"154\" y=\"-171.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">petal length (cm) ≤ 5.45</text>\r\n",
       "<text text-anchor=\"start\" x=\"199.5\" y=\"-156.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.5</text>\r\n",
       "<text text-anchor=\"start\" x=\"189\" y=\"-141.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 2</text>\r\n",
       "<text text-anchor=\"start\" x=\"180\" y=\"-126.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 1, 1]</text>\r\n",
       "<text text-anchor=\"start\" x=\"173\" y=\"-111.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = versicolor</text>\r\n",
       "</g>\r\n",
       "<!-- 5&#45;&gt;7 -->\r\n",
       "<g id=\"edge7\" class=\"edge\"><title>5&#45;&gt;7</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M225.888,-222.907C226.173,-214.558 226.477,-205.671 226.773,-197.02\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"230.271,-197.135 227.115,-187.021 223.275,-196.895 230.271,-197.135\"/>\r\n",
       "</g>\r\n",
       "<!-- 8 -->\r\n",
       "<g id=\"node9\" class=\"node\"><title>8</title>\r\n",
       "<path fill=\"#39e581\" stroke=\"black\" d=\"M210,-68C210,-68 107,-68 107,-68 101,-68 95,-62 95,-56 95,-56 95,-12 95,-12 95,-6 101,-0 107,-0 107,-0 210,-0 210,-0 216,-0 222,-6 222,-12 222,-12 222,-56 222,-56 222,-62 216,-68 210,-68\"/>\r\n",
       "<text text-anchor=\"start\" x=\"129.5\" y=\"-52.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"start\" x=\"119\" y=\"-37.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 1</text>\r\n",
       "<text text-anchor=\"start\" x=\"110\" y=\"-22.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 1, 0]</text>\r\n",
       "<text text-anchor=\"start\" x=\"103\" y=\"-7.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = versicolor</text>\r\n",
       "</g>\r\n",
       "<!-- 7&#45;&gt;8 -->\r\n",
       "<g id=\"edge8\" class=\"edge\"><title>7&#45;&gt;8</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M202.435,-103.726C196.837,-94.9703 190.913,-85.7032 185.289,-76.9051\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"188.123,-74.8399 179.787,-68.2996 182.225,-78.6103 188.123,-74.8399\"/>\r\n",
       "</g>\r\n",
       "<!-- 9 -->\r\n",
       "<g id=\"node10\" class=\"node\"><title>9</title>\r\n",
       "<path fill=\"#8139e5\" stroke=\"black\" d=\"M344.5,-68C344.5,-68 252.5,-68 252.5,-68 246.5,-68 240.5,-62 240.5,-56 240.5,-56 240.5,-12 240.5,-12 240.5,-6 246.5,-0 252.5,-0 252.5,-0 344.5,-0 344.5,-0 350.5,-0 356.5,-6 356.5,-12 356.5,-12 356.5,-56 356.5,-56 356.5,-62 350.5,-68 344.5,-68\"/>\r\n",
       "<text text-anchor=\"start\" x=\"269.5\" y=\"-52.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"start\" x=\"259\" y=\"-37.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 1</text>\r\n",
       "<text text-anchor=\"start\" x=\"250\" y=\"-22.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 0, 1]</text>\r\n",
       "<text text-anchor=\"start\" x=\"248.5\" y=\"-7.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = virginica</text>\r\n",
       "</g>\r\n",
       "<!-- 7&#45;&gt;9 -->\r\n",
       "<g id=\"edge9\" class=\"edge\"><title>7&#45;&gt;9</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M254.565,-103.726C260.163,-94.9703 266.087,-85.7032 271.711,-76.9051\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"274.775,-78.6103 277.213,-68.2996 268.877,-74.8399 274.775,-78.6103\"/>\r\n",
       "</g>\r\n",
       "<!-- 11 -->\r\n",
       "<g id=\"node12\" class=\"node\"><title>11</title>\r\n",
       "<path fill=\"#ab7bee\" stroke=\"black\" d=\"M467,-306C467,-306 336,-306 336,-306 330,-306 324,-300 324,-294 324,-294 324,-235 324,-235 324,-229 330,-223 336,-223 336,-223 467,-223 467,-223 473,-223 479,-229 479,-235 479,-235 479,-294 479,-294 479,-300 473,-306 467,-306\"/>\r\n",
       "<text text-anchor=\"start\" x=\"332\" y=\"-290.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">sepal width (cm) ≤ 3.1</text>\r\n",
       "<text text-anchor=\"start\" x=\"364\" y=\"-275.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.375</text>\r\n",
       "<text text-anchor=\"start\" x=\"362\" y=\"-260.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 4</text>\r\n",
       "<text text-anchor=\"start\" x=\"353\" y=\"-245.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 1, 3]</text>\r\n",
       "<text text-anchor=\"start\" x=\"351.5\" y=\"-230.8\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = virginica</text>\r\n",
       "</g>\r\n",
       "<!-- 10&#45;&gt;11 -->\r\n",
       "<g id=\"edge11\" class=\"edge\"><title>10&#45;&gt;11</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M402.806,-341.907C402.663,-333.558 402.511,-324.671 402.364,-316.02\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"405.863,-315.959 402.193,-306.021 398.864,-316.079 405.863,-315.959\"/>\r\n",
       "</g>\r\n",
       "<!-- 14 -->\r\n",
       "<g id=\"node15\" class=\"node\"><title>14</title>\r\n",
       "<path fill=\"#8139e5\" stroke=\"black\" d=\"M606,-298.5C606,-298.5 509,-298.5 509,-298.5 503,-298.5 497,-292.5 497,-286.5 497,-286.5 497,-242.5 497,-242.5 497,-236.5 503,-230.5 509,-230.5 509,-230.5 606,-230.5 606,-230.5 612,-230.5 618,-236.5 618,-242.5 618,-242.5 618,-286.5 618,-286.5 618,-292.5 612,-298.5 606,-298.5\"/>\r\n",
       "<text text-anchor=\"start\" x=\"528.5\" y=\"-283.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"start\" x=\"514\" y=\"-268.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 26</text>\r\n",
       "<text text-anchor=\"start\" x=\"505\" y=\"-253.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 0, 26]</text>\r\n",
       "<text text-anchor=\"start\" x=\"507.5\" y=\"-238.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = virginica</text>\r\n",
       "</g>\r\n",
       "<!-- 10&#45;&gt;14 -->\r\n",
       "<g id=\"edge14\" class=\"edge\"><title>10&#45;&gt;14</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M456.93,-341.907C472.761,-329.88 490.063,-316.735 505.784,-304.791\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"507.999,-307.503 513.844,-298.667 503.764,-301.93 507.999,-307.503\"/>\r\n",
       "</g>\r\n",
       "<!-- 12 -->\r\n",
       "<g id=\"node13\" class=\"node\"><title>12</title>\r\n",
       "<path fill=\"#8139e5\" stroke=\"black\" d=\"M442.5,-179.5C442.5,-179.5 350.5,-179.5 350.5,-179.5 344.5,-179.5 338.5,-173.5 338.5,-167.5 338.5,-167.5 338.5,-123.5 338.5,-123.5 338.5,-117.5 344.5,-111.5 350.5,-111.5 350.5,-111.5 442.5,-111.5 442.5,-111.5 448.5,-111.5 454.5,-117.5 454.5,-123.5 454.5,-123.5 454.5,-167.5 454.5,-167.5 454.5,-173.5 448.5,-179.5 442.5,-179.5\"/>\r\n",
       "<text text-anchor=\"start\" x=\"367.5\" y=\"-164.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"start\" x=\"357\" y=\"-149.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 3</text>\r\n",
       "<text text-anchor=\"start\" x=\"348\" y=\"-134.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 0, 3]</text>\r\n",
       "<text text-anchor=\"start\" x=\"346.5\" y=\"-119.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = virginica</text>\r\n",
       "</g>\r\n",
       "<!-- 11&#45;&gt;12 -->\r\n",
       "<g id=\"edge12\" class=\"edge\"><title>11&#45;&gt;12</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M399.765,-222.907C399.308,-212.204 398.813,-200.615 398.349,-189.776\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"401.841,-189.508 397.917,-179.667 394.848,-189.807 401.841,-189.508\"/>\r\n",
       "</g>\r\n",
       "<!-- 13 -->\r\n",
       "<g id=\"node14\" class=\"node\"><title>13</title>\r\n",
       "<path fill=\"#39e581\" stroke=\"black\" d=\"M588,-179.5C588,-179.5 485,-179.5 485,-179.5 479,-179.5 473,-173.5 473,-167.5 473,-167.5 473,-123.5 473,-123.5 473,-117.5 479,-111.5 485,-111.5 485,-111.5 588,-111.5 588,-111.5 594,-111.5 600,-117.5 600,-123.5 600,-123.5 600,-167.5 600,-167.5 600,-173.5 594,-179.5 588,-179.5\"/>\r\n",
       "<text text-anchor=\"start\" x=\"507.5\" y=\"-164.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">gini = 0.0</text>\r\n",
       "<text text-anchor=\"start\" x=\"497\" y=\"-149.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">samples = 1</text>\r\n",
       "<text text-anchor=\"start\" x=\"488\" y=\"-134.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">value = [0, 1, 0]</text>\r\n",
       "<text text-anchor=\"start\" x=\"481\" y=\"-119.3\" font-family=\"Helvetica,sans-Serif\" font-size=\"14.00\">class = versicolor</text>\r\n",
       "</g>\r\n",
       "<!-- 11&#45;&gt;13 -->\r\n",
       "<g id=\"edge13\" class=\"edge\"><title>11&#45;&gt;13</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M448.338,-222.907C461.961,-211.101 476.827,-198.217 490.404,-186.45\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"492.966,-188.861 498.23,-179.667 488.381,-183.571 492.966,-188.861\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.files.Source at 0x2163902d4c0>"
      ]
     },
     "execution_count": 161,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dot_data = export_graphviz(dt, out_file=None, \n",
    "                           feature_names=X.columns,  \n",
    "                           class_names=dataset.target_names,  \n",
    "                           filled=True, rounded=True,  \n",
    "                           special_characters=True)  \n",
    "graph = graphviz.Source(dot_data)  \n",
    "graph "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 162,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sklearn Implementation:\n",
      "ACCURACY: 0.9736842105263158\n"
     ]
    }
   ],
   "source": [
    "sklearn_y_preds = dt.predict(X_test)\n",
    "print(f\"Sklearn Implementation:\\nACCURACY: {accuracy_score(y_test, sklearn_y_preds)}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# My Implementation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are going to need to split our data into true and false index in response to the decision rule at a specific branch. If the condition of the decision rule is met, we say that branch is true (which we will denote as the `left`) and false (denoted as `right`).  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition(data, column, value): \n",
    "    \"\"\"\n",
    "    Partition the data into left (indicating True) and right (inidcating false).\n",
    "    \n",
    "    Inputs\n",
    "    data: The data to partition \n",
    "    \n",
    "    Outputs\n",
    "    left: index of values that meet condition\n",
    "    right: index of values that fail to meet the condition\n",
    "    \"\"\"\n",
    "    left = data[data[column] <= value].index\n",
    "    right = data[data[column] > value].index\n",
    "\n",
    "    return left, right"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To check if our function works correctly, we will perform a split on all of the data and pass it the best column and value manually to see if our data is seperated with respect to the graph above. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[petal length (cm) <= 2.45]\n",
      "left_idx: {'setosa': 38}\n",
      "right_idx: {'versicolor': 42, 'virginica': 32}\n"
     ]
    }
   ],
   "source": [
    "# performing a split on the root node\n",
    "left_idx, right_idx = partition(X_train, \"petal length (cm)\", 2.45)\n",
    "\n",
    "print(\"[petal length (cm) <= 2.45]\")\n",
    "\n",
    "# print results --> left_idx = 38 setosa | right index = 42 versicolor, 32 virginica \n",
    "print(f\"left_idx: {dict(zip(np.unique(y_train.loc[left_idx], return_counts=True)[0], np.unique(y_train.loc[left_idx], return_counts=True)[1]))}\\n\\\n",
    "right_idx: {dict(zip(np.unique(y_train.loc[right_idx], return_counts=True)[0], np.unique(y_train.loc[right_idx], return_counts=True)[1]))}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Perfect!\n",
    "\n",
    "Next, we need a criterion that we want to minimize. In this implementation we will be minimizing the gini impurity using a function called `gini_impurity`. Without getting to technical gini impurity simply measures how mixed our data is at a node; To help you conceptualize this think of gold. When gold is impure it referes to the mixture of other substances within it, however when it is pure we can say there are 0 impurities (this isn't exactly true as refined gold up to 99.99% pure so technically there are still some impurities). \n",
    "\n",
    "The ideal is to nodes that are pure meaning that the target labels are seperated into seperate nodes. - To go into the technical details of gini impurity see [here](https://en.wikipedia.org/wiki/Decision_tree_learning#Gini_impurity)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gini_impurity(label, label_idx):\n",
    "    \"\"\"\n",
    "    A measure of how often a randomly chosen element from the set would\n",
    "    be incorrectly labelled if it was randomly labelled according to the \n",
    "    distribution of labels in the subset (Soure: Wikipedia)\n",
    "    \n",
    "    Inputs\n",
    "    label: The class label available at current node\n",
    "    \n",
    "    Outputs\n",
    "    impurity: The gini impurity of the node \n",
    "    \"\"\"\n",
    "    # the unique labels and counts in the data\n",
    "    unique_label, unique_label_count = np.unique(label.loc[label_idx], return_counts=True)\n",
    "\n",
    "    impurity = 1.0\n",
    "    for i in range(len(unique_label)):\n",
    "        p_i = unique_label_count[i] / sum(unique_label_count)\n",
    "        impurity -= p_i ** 2 \n",
    "    return impurity "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you scroll back up to *Figure # - DECISION TREE GRAPH* you will see that the impurity at the root node is 0.663. Therefore, to determine whether our `gini_impurity` function is working correctly, we should see this number on output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "metadata": {},
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "invalid syntax (<ipython-input-166-819e5389a95b>, line 3)",
     "output_type": "error",
     "traceback": [
      "\u001b[1;36m  File \u001b[1;32m\"<ipython-input-166-819e5389a95b>\"\u001b[1;36m, line \u001b[1;32m3\u001b[0m\n\u001b[1;33m    impurity`\u001b[0m\n\u001b[1;37m            ^\u001b[0m\n\u001b[1;31mSyntaxError\u001b[0m\u001b[1;31m:\u001b[0m invalid syntax\n"
     ]
    }
   ],
   "source": [
    "# Gini impurity of the first node\n",
    "impurity = gini_impurity(y_train, y_train.index)\n",
    "impurity`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great! \n",
    "\n",
    "To split at a feature (and value) we need to a way of quantifying what would result in the best outcome if we were to split at that point. Information gain is a useful way to quantify what feature and feature value to split on at each node. For each node of the tree, the information value \"represents the expected amount of information that would be needed to specify whether a new instance should be classified yes or no, given that the example reached that node\". (Source: Wikipedia)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 167,
   "metadata": {},
   "outputs": [],
   "source": [
    "def information_gain(label, left_idx, right_idx, impurity): \n",
    "    \"\"\"\n",
    "    For each node of the tree, the information gain \"represents the\n",
    "    expected amount of information that would be needed to specify whether\n",
    "    a new instance should be classified yes or no, given that the example\n",
    "    reached that node. (Source: Wikipedia)\n",
    "    \n",
    "    Inputs\n",
    "    left: The values that met the conditions of the current node\n",
    "    right: The values that failed to meet the conditions of the current noode\n",
    "    gini_impurity: the uncertainty at the current node\n",
    "    \n",
    "    Outputs\n",
    "    info_gain: The information gain at the node\n",
    "    \"\"\"\n",
    "    \n",
    "    p = float(len(left_idx)) / (len(left_idx) + len(right_idx))\n",
    "    info_gain = impurity - p * gini_impurity(label, left_idx) - (1 - p) * gini_impurity(label, right_idx)\n",
    "    return info_gain\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The best first split is the one that provides the most information gain. This process is repeated for each impure node until the tree is complete. (Source: Wikipedia) \n",
    "\n",
    "Based on the above statement, we can now see why petal length (cm) with the value 2.45 was selected as the first split. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.33830322669608387"
      ]
     },
     "execution_count": 168,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# testing info gain of the first split at root node\n",
    "info_gain = information_gain(y_train, left_idx, right_idx, impurity)\n",
    "info_gain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.25446843371494937"
      ]
     },
     "execution_count": 169,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# testing a random feature and value to see the information gain\n",
    "left_idx, right_idx = partition(X_train, \"petal width (cm)\", 1.65)\n",
    "\n",
    "impurity = gini_impurity(y_train, y_train.index)\n",
    "\n",
    "info_gain = information_gain(y_train, left_idx, right_idx, impurity)\n",
    "info_gain"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above helper functions are now going to be brought into play. We had to manually select the feature and value before right? The next function will now automatically search the feature space and find the feature and feature value the best splits the data. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_best_split(df, label, idx):\n",
    "    \"\"\"\n",
    "    Splits the data on the best column and value \n",
    "    \n",
    "    Input\n",
    "    df: the training data\n",
    "    label: the target label \n",
    "    idx: the index of the data\n",
    "    \n",
    "    Output: \n",
    "    best_gain: the max information gain\n",
    "    best_col: the column that produced best information gain\n",
    "    best_val: the value of the column that produced best information gain\n",
    "    \n",
    "    \"\"\"\n",
    "    \n",
    "    best_gain = 0 \n",
    "    best_col = None\n",
    "    best_value = None\n",
    "    \n",
    "    df = df.loc[idx] # converting training data to pandas dataframe\n",
    "    label_idx = label.loc[idx].index # getting the index of the labels\n",
    "\n",
    "    impurity = gini_impurity(label, label_idx) # determining the impurity at the current node\n",
    "    \n",
    "    # go through the columns and store the unique values in each column (no point testing on the same value twice)\n",
    "    for col in df.columns: \n",
    "        unique_values = set(df[col])\n",
    "        # loop thorugh each value and partition the data into true (left_index) and false (right_index)\n",
    "        for value in unique_values: \n",
    "\n",
    "            left_idx, right_idx = partition(df, col, value)\n",
    "            # ignore if the index is empty (meaning there was no features that met the decision rule)\n",
    "            if len(left_idx) == 0 or len(right_idx) == 0: \n",
    "                continue \n",
    "            # determine the info gain at the node\n",
    "            info_gain = information_gain(label, left_idx, right_idx, impurity)\n",
    "            # if the info gain is higher then our current best gain then that becomes the best gain\n",
    "            if info_gain > best_gain:\n",
    "                best_gain, best_col, best_value = info_gain, col, value\n",
    "                \n",
    "    return best_gain, best_col, best_value\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.33830322669608387, 'petal length (cm)', 1.9)"
      ]
     },
     "execution_count": 171,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "find_best_split(X_train, y_train, y_train.index)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [],
   "source": [
    "# helper function to count values\n",
    "def count(label, idx):\n",
    "    \"\"\"\n",
    "    Function that couunts the unique values\n",
    "    \n",
    "    Input\n",
    "    label: target labels\n",
    "    idx: index of rows \n",
    "    \n",
    "    Output\n",
    "    dict_label_count: Dictionary of label and counts\n",
    "    \n",
    "    \"\"\"\n",
    "    unique_label, unique_label_counts = np.unique(label.loc[idx], return_counts=True)\n",
    "    dict_label_count = dict(zip(unique_label, unique_label_counts))\n",
    "    return dict_label_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'setosa': 38, 'versicolor': 42, 'virginica': 32}"
      ]
     },
     "execution_count": 173,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# check counts at first node to check it aligns with scitkit learn\n",
    "count(y_train, y_train.index)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {},
   "outputs": [],
   "source": [
    "# https://github.com/random-forests/tutorials/blob/master/decision_tree.ipynb\n",
    "class Leaf:\n",
    "    \"\"\"\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, label, idx):\n",
    "        self.predictions = count(label, idx)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {},
   "outputs": [],
   "source": [
    "# https://github.com/random-forests/tutorials/blob/master/decision_tree.ipynb\n",
    "class Decision_Node:\n",
    "    \"\"\"\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",
    "                 column,\n",
    "                 value,\n",
    "                 true_branch,\n",
    "                 false_branch):\n",
    "        self.column = column\n",
    "        self.value = value\n",
    "        self.true_branch = true_branch\n",
    "        self.false_branch = false_branch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Great, we have all the components we need for our algorithm to work. However, the above functions on only perform one split on our training data (the stump/root). For the algorithm to work we will need the splits to happen recursively until we meet a stopping criterion - in this case it's until each leaf node is pure. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_tree(df, label, idx): \n",
    "    \"\"\"\n",
    "    Recursively Builds the tree until is leaf is pure. \n",
    "    \n",
    "    Input \n",
    "    df: the training data\n",
    "    label: the target labels\n",
    "    idx: the indexes \n",
    "    \n",
    "    Output\n",
    "    best_col: the best column \n",
    "    best_value: the value of the column that minimizes impurity \n",
    "    true_branch: the true branch \n",
    "    false_branch: the false branch \n",
    "    \"\"\"\n",
    "    best_gain, best_col, best_value = find_best_split(df, label, idx)\n",
    "    \n",
    "    if best_gain == 0: \n",
    "        return Leaf(label, label.loc[idx].index)\n",
    "    \n",
    "    left_idx, right_idx = partition(df.loc[idx], best_col, best_value)\n",
    "    \n",
    "    true_branch = build_tree(df, label, left_idx)\n",
    "    \n",
    "    false_branch = build_tree(df, label, right_idx)\n",
    "    \n",
    "    return Decision_Node(best_col, best_value, true_branch, false_branch)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "metadata": {},
   "outputs": [],
   "source": [
    "# https://github.com/random-forests/tutorials/blob/master/decision_tree.ipynb\n",
    "def print_tree(node, spacing=\"\"):\n",
    "    \"\"\"\n",
    "    World's most elegant tree printing function.\n",
    "    \n",
    "    Input\n",
    "    node: the tree node\n",
    "    spacing: used to space creating tree like structure\n",
    "    \"\"\"\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 col and value at this node\n",
    "    print(spacing + f\"[{node.column} <= {node.value}]\")\n",
    "    \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": 178,
   "metadata": {},
   "outputs": [],
   "source": [
    "my_tree = build_tree(X_train, y_train, X_train.index)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 179,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[petal length (cm) <= 1.9]\n",
      "--> True:\n",
      "  Predict {'setosa': 38}\n",
      "--> False:\n",
      "  [petal width (cm) <= 1.6]\n",
      "  --> True:\n",
      "    [petal length (cm) <= 4.9]\n",
      "    --> True:\n",
      "      Predict {'versicolor': 40}\n",
      "    --> False:\n",
      "      [sepal length (cm) <= 6.0]\n",
      "      --> True:\n",
      "        [sepal width (cm) <= 2.2]\n",
      "        --> True:\n",
      "          Predict {'virginica': 1}\n",
      "        --> False:\n",
      "          Predict {'versicolor': 1}\n",
      "      --> False:\n",
      "        Predict {'virginica': 2}\n",
      "  --> False:\n",
      "    [petal length (cm) <= 4.8]\n",
      "    --> True:\n",
      "      [sepal width (cm) <= 3.0]\n",
      "      --> True:\n",
      "        Predict {'virginica': 3}\n",
      "      --> False:\n",
      "        Predict {'versicolor': 1}\n",
      "    --> False:\n",
      "      Predict {'virginica': 26}\n"
     ]
    }
   ],
   "source": [
    "print_tree(my_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Super! Now you've seen how to implement a Decision tree from scratch and we have used it to train our data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 197,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predict(test_data, tree):\n",
    "    \n",
    "    \"\"\"\n",
    "    Classify unseen examples\n",
    "    \n",
    "    Inputs\n",
    "    test_data: Unseen observation\n",
    "    tree: tree that has been trained on training data\n",
    "    \n",
    "    Output\n",
    "    The prediction of the observation.\n",
    "    \"\"\"\n",
    "    \n",
    "    # Check if we are at a leaf node\n",
    "    if isinstance(tree, Leaf): \n",
    "        return max(tree.predictions)\n",
    "    \n",
    "    # the current feature_name and value \n",
    "    feature_name, feature_value = tree.column, tree.value\n",
    "    \n",
    "    # pass the observation through the nodes recursively\n",
    "    if test_data[feature_name] <= feature_value: \n",
    "        return predict(test_data, tree.true_branch)\n",
    "    \n",
    "    else: \n",
    "        return predict(test_data, tree.false_branch)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 198,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(sepal length (cm)       5.3\n",
       " sepal width (cm)        3.7\n",
       " petal length (cm)       1.5\n",
       " petal width (cm)        0.2\n",
       " predictions          setosa\n",
       " Name: 48, dtype: object,\n",
       " 'setosa')"
      ]
     },
     "execution_count": 198,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# taking one instance to test function \n",
    "example, example_target = X_test.iloc[6], y_test.iloc[6]\n",
    "example, example_target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 199,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'setosa'"
      ]
     },
     "execution_count": 199,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# if working correctly should output setosa\n",
    "predict(example, my_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 200,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a new col of predictions\n",
    "X_test[\"predictions\"] = X_test.apply(predict, axis=1, args=(my_tree,))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 202,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "107    True\n",
       "114    True\n",
       "57     True\n",
       "59     True\n",
       "105    True\n",
       "11     True\n",
       "48     True\n",
       "72     True\n",
       "29     True\n",
       "148    True\n",
       "30     True\n",
       "19     True\n",
       "26     True\n",
       "111    True\n",
       "144    True\n",
       "14     True\n",
       "103    True\n",
       "31     True\n",
       "104    True\n",
       "120    True\n",
       "112    True\n",
       "140    True\n",
       "135    True\n",
       "51     True\n",
       "136    True\n",
       "1      True\n",
       "108    True\n",
       "137    True\n",
       "49     True\n",
       "109    True\n",
       "78     True\n",
       "17     True\n",
       "77     True\n",
       "92     True\n",
       "133    True\n",
       "113    True\n",
       "9      True\n",
       "84     True\n",
       "Name: predictions, dtype: bool"
      ]
     },
     "execution_count": 202,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sklearn_y_preds == X_test[\"predictions\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 201,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sklearn Implementation:\n",
      "ACCURACY: 0.9736842105263158\n",
      "\n",
      "My Implementation:\n",
      "ACCURACY: 0.9736842105263158\n"
     ]
    }
   ],
   "source": [
    "# sklearn accuracy vs my implementation accuracy\n",
    "print(f\"Sklearn Implementation:\\nACCURACY: {accuracy_score(y_test, sklearn_y_preds)}\\n\\n\\\n",
    "My Implementation:\\nACCURACY: {accuracy_score(y_test, X_test['predictions'])}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pros\n",
    "* Simple and easy to interpret \n",
    "* Able to handle both numerical and categorical data\n",
    "* Requires little data preparation \n",
    "* Performs well with large datasets\n",
    "* Built in feature selection\n",
    "\n",
    "### Cons \n",
    "* Instability of trees (Changing something in the data can change everything) \n",
    "* Lack of smoothness (Particular issue for regression problems) \n",
    "* Prone to overfitting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Wrap Up \n",
    "Establishing a good foundation of Decision trees will go a long way in understanding many other important Machine Learning algorithms. It is a very powerful algorithm that is often used as an ensemble model to win various Data Science competitions.\n",
    "\n",
    "Thank you for reading to the end of the article! If you'd like to keep in contact with me, I am most accessible on LinkedIn.\n",
    "###INSERT LINKED IN "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.8.3 64-bit (conda)",
   "language": "python",
   "name": "python38364bitcondab8eeb421859c4b2b97a8c102771f8a36"
  },
  "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}