Code-Example-019-Decision_tree_without_libs.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "hE80unDWAOhR"
   },
   "source": [
    "# Decision Tree Example implementation without using libraries \n",
    "\n",
    "Here we develop an example dataset and write functions for implementing decision tree using CART algorithm (Classification and Regression Trees)  based on Gini's impurity\n",
    "\n",
    "*Based on implementation of Josh Gordon\n",
    "https://github.com/random-forests/tutorials/blob/master/decision_tree.py \n",
    "\n",
    "> Indented block\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "id": "NO5IM8x78SGo"
   },
   "outputs": [],
   "source": [
    "from __future__ import print_function"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "id": "lYlaRfL58ksY"
   },
   "outputs": [],
   "source": [
    "training_data = [\n",
    "                 [210, 160, 'Smoker','Cancer'],\n",
    "                 [200, 180, 'Smoker','Cardiovascular' ],\n",
    "                 [210, 190, 'Smoker','Cardiovascular'],\n",
    "                 [210, 150, 'Smoker','Cancer'],\n",
    "                 [110, 140, 'nonesmoker', 'Normal'],\n",
    "                 [110, 120, 'nonesmoker', 'Normal'],\n",
    "                 [140, 120, 'nonesmoker', 'Normal']\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "id": "BKq5A5iy9P-Q"
   },
   "outputs": [],
   "source": [
    "features = ['Chol', 'SPB', 'SmokerOrNot']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "id": "_pm-VFoM9YKf"
   },
   "outputs": [],
   "source": [
    "testing_data = [\n",
    "                 [190, 160, 'Smoker', 'Cancer'],\n",
    "                 [185, 180, 'Smoker', 'Cardiovascular'],\n",
    "                 [180, 175, 'Smoker', 'Cardiovascular'],\n",
    "                 [120, 150, 'nonesmoker', 'Normal'],\n",
    "                 [100, 110, 'nonesmoker', 'Normal'],\n",
    "                 [130, 110, 'nonesmoker', 'Normal']\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "id": "X7O6eQz190tY"
   },
   "outputs": [],
   "source": [
    "def unique_values(rows, col):\n",
    "  return set([row[col] for row in rows])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "d8ygExIa-FWe",
    "outputId": "34c6ae46-57e1-48a9-a258-30088c970c38"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{110, 140, 200, 210}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "unique_values(training_data, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "it3qhLIb-KpP",
    "outputId": "da632d4d-af1f-4c30-dd08-d0739f182d63"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{120, 140, 150, 160, 180, 190}"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "unique_values(training_data, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "L6Rs1LE7FjvX",
    "outputId": "597edc03-9c25-49ed-cb57-2fbdb1532edd"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Smoker', 'nonesmoker'}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "unique_values(training_data, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "id": "cc_d_sii-oVX"
   },
   "outputs": [],
   "source": [
    "def class_counts(rows):\n",
    "  counts = {}\n",
    "\n",
    "  for row in rows:\n",
    "    # our label is the last column\n",
    "    label = row[-1]\n",
    "    if label not in counts:\n",
    "      counts[label] = 0\n",
    "    counts[label] +=1\n",
    "  \n",
    "  return counts  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "hW2cdZvbBH3I",
    "outputId": "5d8173c8-0567-4864-df49-29c3ae3f3319"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Cancer': 2, 'Cardiovascular': 2, 'Normal': 3}"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class_counts(training_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "F38FC8qOANUS"
   },
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "id": "zWjMa1RyCOxA"
   },
   "outputs": [],
   "source": [
    "class Question:\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",
    "    \n",
    "    if (type(self.value) == int) or (type(self.value) == float):\n",
    "      return val >= self.value\n",
    "    else:\n",
    "      return val == self.value\n",
    "  \n",
    "  def __repr__(self):\n",
    "\n",
    "    condition = \"==\"\n",
    "\n",
    "    if type(self.value) == int or float:\n",
    "      condition = \">=\"\n",
    "    return \"Is %s %s %s?\" % (features[self.column], condition, str(self.value))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "R1_50n6ZCRke",
    "outputId": "af14eca4-8030-4d90-996d-4ec6e06de6ac"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Is Chol >= 3?"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Question(0, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "id": "ZCbaskPcDY6r"
   },
   "outputs": [],
   "source": [
    "def gini(rows):\n",
    "  \"\"\"Gini Impurity for a list of data rows 1-p^2\"\"\"\n",
    "  counts = class_counts(rows)\n",
    "  impurity =1 \n",
    "\n",
    "  for label in counts:\n",
    "    prob_of_label = counts[label] / float(len(rows))\n",
    "    impurity -= prob_of_label**2\n",
    "  return impurity\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "lapdCSV7LtYy",
    "outputId": "b1e75d37-4d48-4136-f366-d58ca5e7e611"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "no_mixiing = [['Sick'], ['Sick']]\n",
    "\n",
    "gini(no_mixiing)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "gcHGekeZMNvm",
    "outputId": "de5520ed-723b-49c4-fba2-faef677025f3"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.5"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mixiing = [['Sick'], ['Normal']]\n",
    "gini(mixiing)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "q2G2YI7MMTTd",
    "outputId": "3c120d9e-3ec5-4c53-b033-c53919aaaa38"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.7999999999999998"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "more_mixiing = [['normal'], ['flu'], ['Cardiovascular'], ['Cancer'], ['COVID-19']]\n",
    "gini(more_mixiing)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "id": "RPphJ27WMrM6"
   },
   "outputs": [],
   "source": [
    "def info_gain(left, right, current_uncertainty):\n",
    "  p = float(len(left)/(len(left) + len(right)))\n",
    "  return current_uncertainty - p* gini(left) - (1-p)*gini(right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "AuhVYJhaNVVt",
    "outputId": "84199b14-255e-49cf-bbc6-9ba6156ef02c"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.653061224489796"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "current_uncertainty = gini(training_data)\n",
    "current_uncertainty"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "id": "P5dBV_3CRZfr"
   },
   "outputs": [],
   "source": [
    "def partition(rows, question):\n",
    "    \"\"\"Partitions a dataset.\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\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "id": "eq4P8yScPK5z"
   },
   "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 train 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": 21,
   "metadata": {
    "id": "rJKOho6CNdPc"
   },
   "outputs": [],
   "source": [
    "class Leaf:\n",
    "    \"\"\"A Leaf node classifies data.\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)\n",
    "\n",
    "\n",
    "class Decision_Node:\n",
    "    \"\"\"A Decision Node asks a question.\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\n",
    "\n",
    "\n",
    "def build_tree(rows):\n",
    "    \"\"\"Builds the tree.\n",
    "    Rules of recursion: 1) Believe that it works. 2) Start by checking\n",
    "    for the base case (no further information gain). 3) Prepare for\n",
    "    giant stack traces.\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",
    "\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",
    "\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\n",
    "    # dependingo on the answer.\n",
    "    return Decision_Node(question, true_branch, false_branch)\n",
    "\n",
    "\n",
    "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 + \"  \")\n",
    "\n",
    "\n",
    "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):\n",
    "        return classify(row, node.true_branch)\n",
    "    else:\n",
    "        return classify(row, node.false_branch)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "id": "p9Wh8TYaRD3Y"
   },
   "outputs": [],
   "source": [
    "#######\n",
    "# Demo:\n",
    "# The tree predicts the 1st row of our\n",
    "# training data is an apple with confidence 1.\n",
    "# my_tree = build_tree(training_data)\n",
    "# classify(training_data[0], my_tree)\n",
    "#######\n",
    "\n",
    "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": 23,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "SyUbV-5dRGux",
    "outputId": "bf1f59e7-1006-401d-b8fd-a1e879648867"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is SmokerOrNot >= Smoker?\n",
      "--> True:\n",
      "  Is SPB >= 180?\n",
      "  --> True:\n",
      "    Predict {'Cardiovascular': 2}\n",
      "  --> False:\n",
      "    Predict {'Cancer': 2}\n",
      "--> False:\n",
      "  Predict {'Normal': 3}\n"
     ]
    }
   ],
   "source": [
    "my_tree = build_tree(training_data)\n",
    "\n",
    "print_tree(my_tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/"
    },
    "id": "2aXD6ywDRNIa",
    "outputId": "9afd7f17-8222-4e12-9271-7cdf4716aeff"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Actual: Cancer. Predicted: {'Cancer': '100%'}\n",
      "Actual: Cardiovascular. Predicted: {'Cardiovascular': '100%'}\n",
      "Actual: Cardiovascular. Predicted: {'Cancer': '100%'}\n",
      "Actual: Normal. Predicted: {'Normal': '100%'}\n",
      "Actual: Normal. Predicted: {'Normal': '100%'}\n",
      "Actual: Normal. Predicted: {'Normal': '100%'}\n"
     ]
    }
   ],
   "source": [
    "testing_data = [\n",
    "                 [190, 160, 'Smoker', 'Cancer'],\n",
    "                 [185, 180, 'Smoker', 'Cardiovascular'],\n",
    "                 [180, 175, 'Smoker', 'Cardiovascular'],\n",
    "                 [120, 150, 'nonesmoker', 'Normal'],\n",
    "                 [100, 110, 'nonesmoker', 'Normal'],\n",
    "                 [130, 110, 'nonesmoker', 'Normal']\n",
    "]\n",
    "\n",
    "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": null,
   "metadata": {
    "id": "EsEdqYaeRn8J"
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "Decision-Tree-without-libs.ipynb",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}