decision_tree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Decision Tree Classifier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag: ID3,C4.5,C5.0, CART, Gini Index, Impurity, Information Gain and Entropy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "#CART(Classification and regression tree) use Gini index\n",
    "#ID3 use entropy and information gain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'\\ndetermine the attribute that best classifies the training data; use this attribute at the root of the tree.\\nRepeat this process at for each branch.\\n'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Pick first node\n",
    "'''\n",
    "determine the attribute that best classifies the training data; use this attribute at the root of the tree.\n",
    "Repeat this process at for each branch.\n",
    "'''"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. Entropy: Measure of uncertainity in data\n",
    "2. Information Gain: difference in entry after data is splitted based on attribute a \n",
    "\n",
    "1.compute the entropy for data-set\n",
    "2.for every attribute/feature:\n",
    "       1.calculate entropy for all categorical values\n",
    "       2.take average information entropy for the current attribute\n",
    "       3.calculate gain for the current attribute\n",
    "3. pick the highest gain attribute.\n",
    "4. Repeat until we get the tree we desired.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 168,
   "metadata": {},
   "outputs": [],
   "source": [
    "# color, size, label\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": 139,
   "metadata": {},
   "outputs": [],
   "source": [
    "# color, size, label\n",
    "training_data = [\n",
    "    ['Green', 3, 'Apple'],\n",
    "    ['Yellow', 3, 'Apple'],\n",
    "    ['Red', 1, 'Grape'],\n",
    "    ['Red', 1, 'Grape'],\n",
    "    ['Yellow', 2, 'Grape'],\n",
    "    ['Red', 2, 'Apple'],\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_class_freq(rows):\n",
    "    #last column is the class\n",
    "    classes={} #dictionary\n",
    "    for row in rows:\n",
    "        c=row[-1]\n",
    "        if c not in classes:\n",
    "            classes[c]=1\n",
    "        else:\n",
    "            classes[c]+=1\n",
    "    return classes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Apple': 2, 'Grape': 2, 'Lemon': 1}"
      ]
     },
     "execution_count": 142,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "count_class_freq(training_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<img src='imgs/gini-index-formula.png' width=20%>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gini(rows):\n",
    "    classes=count_class_freq(rows)\n",
    "    impurity = 1\n",
    "    for c in classes:\n",
    "        prob_of_c = classes[c] / float(len(rows))\n",
    "        impurity -= prob_of_c**2\n",
    "    return impurity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.6399999999999999"
      ]
     },
     "execution_count": 144,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gini(training_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "CART:\n",
    "1. compute the gini index for data-set\n",
    "2. for every attribute/feature/column:\n",
    "       1.calculate gini index for all categorical values\n",
    "       2.take average information entropy for the current attribute \n",
    "       3.calculate the gini gain\n",
    "3. pick the best gini gain attribute.\n",
    "4. Repeat until we get the tree we desired.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Gini index and Entropy\n",
    "Decision tree algorithms use information gain to split a node. Gini index or entropy is the criterion for calculating information gain. \n",
    "Both gini and entropy are measures of impurity of a node. A node having multiple classes is impure whereas a node having only one class is pure.  Entropy in statistics is analogous to entropy in thermodynamics where it signifies disorder. If there are multiple classes in a node, there is disorder in that node. \n",
    " \n",
    "Information gain is the entropy of parent node minus sum of weighted entropies of child nodes. \n",
    " Weight of a child node is number of samples in the node/total samples of all child nodes. Similarly information gain is calculated with gini score. \n",
    " <img src='imgs/ginientropy.jpg'>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Entropy vs gini\n",
    "<img src='imgs/entropy_vs_gini.png' width=40%>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import log\n",
    "def entropy(rows):\n",
    "    classes=count_class_freq(rows)\n",
    "    impurity = 0\n",
    "    for c in classes:\n",
    "        prob_of_c = classes[c] / float(len(rows))\n",
    "        impurity -= prob_of_c*  log(prob_of_c, 2)\n",
    "    return impurity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.5219280948873621"
      ]
     },
     "execution_count": 146,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "entropy(training_data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {},
   "outputs": [],
   "source": [
    "#information gain for a split.\n",
    "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": 148,
   "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": 149,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 149,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_numeric(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 150,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_numeric('Red')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition(rows, q, col):\n",
    "    \n",
    "    true_rows, false_rows = [], []\n",
    "    for row in rows: \n",
    "        cv=row[col] \n",
    "        if is_numeric(cv):\n",
    "            if cv>=q:\n",
    "                true_rows.append(row)\n",
    "            else:\n",
    "                false_rows.append(row)\n",
    "        else:\n",
    "            if cv==q:\n",
    "                true_rows.append(row)\n",
    "            else:\n",
    "                false_rows.append(row)\n",
    "        \n",
    "    return true_rows, false_rows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true:  [['Red', 1, 'Grape'], ['Red', 1, 'Grape']]\n",
      "false:  [['Green', 3, 'Apple'], ['Yellow', 3, 'Apple'], ['Yellow', 3, 'Lemon']]\n"
     ]
    }
   ],
   "source": [
    "true_rows, false_rows = partition(training_data, 'Red', 0)\n",
    "print('true: ', true_rows)\n",
    "print('false: ', false_rows)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 153,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true:  [['Green', 3, 'Apple'], ['Yellow', 3, 'Apple'], ['Yellow', 3, 'Lemon']]\n",
      "false:  [['Red', 1, 'Grape'], ['Red', 1, 'Grape']]\n"
     ]
    }
   ],
   "source": [
    "true_rows, false_rows = partition(training_data, 3, 1)\n",
    "print('true: ', true_rows)\n",
    "print('false: ', false_rows)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 154,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.6399999999999999\n"
     ]
    }
   ],
   "source": [
    "cr=gini(training_data) #current\n",
    "print(cr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.1399999999999999"
      ]
     },
     "execution_count": 155,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "true_rows, false_rows = partition(training_data, 'Green', 0)\n",
    "info_gain(true_rows, false_rows, cr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.37333333333333324"
      ]
     },
     "execution_count": 156,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "true_rows, false_rows = partition(training_data, 'Red', 0)\n",
    "info_gain(true_rows, false_rows, cr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 182,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'Green', 'Red', 'Yellow'}\n",
      "Green  : IG= 0.1399999999999999\n",
      "Red  : IG= 0.37333333333333324\n",
      "Yellow  : IG= 0.17333333333333323\n"
     ]
    }
   ],
   "source": [
    "col=0\n",
    "values = set([row[col] for row in training_data])\n",
    "print(values)\n",
    "for value in values:\n",
    "    true_rows, false_rows = partition(training_data, value, col)\n",
    "    ig=info_gain(true_rows, false_rows, cr)\n",
    "    print(value,' : IG=',ig)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1, 3}\n",
      "1  : IG= 0.0\n",
      "3  : IG= 0.37333333333333324\n"
     ]
    }
   ],
   "source": [
    "col=1\n",
    "values = set([row[col] for row in training_data])\n",
    "print(values)\n",
    "for value in values:\n",
    "    true_rows, false_rows = partition(training_data, value, col)\n",
    "    ig=info_gain(true_rows, false_rows, cr)\n",
    "    print(value,' : IG=',ig)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 169,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.37333333333333324, 1, 3)"
      ]
     },
     "execution_count": 169,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def find_best_split(rows, igcol=None):\n",
    "    ncol=len(rows[0])-1\n",
    "    current_uncertainty = gini(rows)\n",
    "    best_gain=0\n",
    "    best_col=None\n",
    "    best_feature=None\n",
    "    for col in range(ncol):\n",
    "        if not igcol==None and col==igcol:  #ignore this column\n",
    "#             print('Ignoring column=',col, ' Total=',ncol)\n",
    "            continue\n",
    "        values = set([row[col] for row in rows])  # unique values in the column\n",
    "#         print('Values: ', values)\n",
    "        for val in values:  # for each value\n",
    "            # try splitting the dataset\n",
    "            true_rows, false_rows = partition(rows, val, col)\n",
    "            if len(true_rows) == 0 or len(false_rows) == 0:\n",
    "                continue\n",
    "            gain=info_gain(true_rows, false_rows, current_uncertainty)\n",
    "            if gain>=best_gain:\n",
    "                best_gain=gain\n",
    "                best_col=col\n",
    "                best_feature=val\n",
    "                \n",
    "    return best_gain, best_col, best_feature\n",
    "                \n",
    "find_best_split(training_data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 178,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "gain:  0.37333333333333324  best_col:  1  best_val= 3\n"
     ]
    }
   ],
   "source": [
    "gain, best_col, best_val=find_best_split(training_data)\n",
    "print('gain: ', gain, ' best_col: ',best_col,' best_val=',best_val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 171,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "gain:  0.37333333333333324  best_col:  1  best_val= 3\n"
     ]
    }
   ],
   "source": [
    "igcol=None\n",
    "gain, best_col, best_val=find_best_split(training_data, igcol)\n",
    "print('gain: ', gain, ' best_col: ',best_col,' best_val=',best_val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 172,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "true:  [['Green', 3, 'Apple'], ['Yellow', 3, 'Apple'], ['Yellow', 3, 'Lemon']]\n",
      "false:  [['Red', 1, 'Grape'], ['Red', 1, 'Grape']]\n"
     ]
    }
   ],
   "source": [
    "true_rows, false_rows = partition(training_data, best_val, best_col)\n",
    "print('true: ', true_rows)\n",
    "print('false: ', false_rows)\n",
    "igcol=best_col"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "gain:  0.11111111111111116  best_col:  0  best_val= Yellow\n"
     ]
    }
   ],
   "source": [
    "gain, best_col, best_val=find_best_split(true_rows, igcol)\n",
    "print('gain: ', gain, ' best_col: ',best_col,' best_val=',best_val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 174,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "gain:  0  best_col:  None  best_val= None\n"
     ]
    }
   ],
   "source": [
    "gain, best_col, best_val=find_best_split(false_rows, igcol)\n",
    "print('gain: ', gain, ' best_col: ',best_col,' best_val=',best_val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 175,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Leaf Node:  None\n",
      "leaf: None :None\n"
     ]
    }
   ],
   "source": [
    "if gain==0:\n",
    "    print('Leaf Node: ', best_val)\n",
    "    print( 'leaf: '+str(best_col)+' :'+str(best_val) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "def build_tree(rows, igcol=None):\n",
    "    gain, best_col, best_val=find_best_split(rows, igcol)\n",
    "    print('gain: ', gain, ' best_col: ',best_col,' best_val=',best_val)\n",
    "    if gain==0:\n",
    "        print('Leaf Node: ', best_val)\n",
    "        return 'leaf: '+str(best_col)+' :'+str(best_val)\n",
    "    true_rows, false_rows = partition(rows, best_val, best_col)\n",
    "    \n",
    "    true_branch=build_tree(true_rows, best_col)\n",
    "    false_branch=build_tree(false_rows, best_col)\n",
    "    return 'Decision: '+str(best_col)+' :'+str(best_val)+'\\nTrue:'+str(true_branch)+'\\nFalse: '+str(false_branch)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 177,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "gain:  0.37333333333333324  best_col:  1  best_val= 3\n",
      "gain:  0.11111111111111116  best_col:  0  best_val= Yellow\n",
      "gain:  0  best_col:  None  best_val= None\n",
      "Leaf Node:  None\n",
      "gain:  0  best_col:  None  best_val= None\n",
      "Leaf Node:  None\n",
      "gain:  0  best_col:  None  best_val= None\n",
      "Leaf Node:  None\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "'Decision: 1 :3\\nTrue:Decision: 0 :Yellow\\nTrue:leaf: None :None\\nFalse: leaf: None :None\\nFalse: leaf: None :None'"
      ]
     },
     "execution_count": 177,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "build_tree(training_data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def num_split(data, th): \n",
    "    lt=[]\n",
    "    rt=[]\n",
    "    for i,d in enumerate(data[:,0]):\n",
    "#         print(i,d,th)\n",
    "        d=int(d)\n",
    "        if d>th:\n",
    "            rt.append(data[i])\n",
    "        else:\n",
    "            lt.append(data[i])\n",
    "    return lt,rt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "dt=[\n",
    "    [10.0,'F'],\n",
    "    [0.0, 'F'],\n",
    "    [80.0, 'P'],\n",
    "    [100.0,'P'],\n",
    "    [35.0, 'F'],\n",
    "    [37.0, 'P'],\n",
    "    [34.0, 'F'],\n",
    "    [25.0, 'F']\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.46875\n"
     ]
    }
   ],
   "source": [
    "ct=gini(dt)\n",
    "print(ct)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "th=25\n",
    "lb=[]\n",
    "rb=[]\n",
    "for row in dt:\n",
    "#     print(row)\n",
    "    v=row[0]\n",
    "#     print(v)\n",
    "    if v<=th:\n",
    "        lb.append(row)\n",
    "    else:\n",
    "        rb.append(row)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "def split_data(dt, th):\n",
    "    lb=[]\n",
    "    rb=[]\n",
    "    for row in dt:\n",
    "    #     print(row)\n",
    "        v=row[0]\n",
    "    #     print(v)\n",
    "        if v<=th:\n",
    "            lb.append(row)\n",
    "        else:\n",
    "            rb.append(row)\n",
    "    return lb,rb"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[10.0, 'F'], [0.0, 'F'], [35.0, 'F'], [37.0, 'P'], [34.0, 'F'], [25.0, 'F']]\n",
      "[[80.0, 'P'], [100.0, 'P']]\n"
     ]
    }
   ],
   "source": [
    "lb,rb=split_data(dt, 50)\n",
    "print(lb)\n",
    "print(rb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "# ndt=np.array(dt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[10.0, 'F'], [0.0, 'F'], [25.0, 'F']]\n",
      "\n",
      "[[80.0, 'P'], [100.0, 'P'], [35.0, 'F'], [37.0, 'P'], [34.0, 'F']]\n"
     ]
    }
   ],
   "source": [
    "print(lb)\n",
    "print('')\n",
    "print(rb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0 0.48\n",
      "0.16875\n"
     ]
    }
   ],
   "source": [
    "lg=gini(lb)\n",
    "rg=gini(rb)\n",
    "print(lg,rg)\n",
    "td=len(lb)+len(rb)\n",
    "\n",
    "ig=ct- (len(lb)/td)*lg - (len(rb)/td)*rg\n",
    "print(ig)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "td=len(lb)+len(rb)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(len(lb)/td)*lg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_class_freq(rows):\n",
    "    #last column is the class\n",
    "    classes={} #dictionary\n",
    "    for row in rows:\n",
    "        c=row[-1]\n",
    "        if c not in classes:\n",
    "            classes[c]=1\n",
    "        else:\n",
    "            classes[c]+=1\n",
    "    return classes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gini(rows):\n",
    "    classes=count_class_freq(rows)\n",
    "    impurity = 1\n",
    "    for c in classes:\n",
    "        prob_of_c = classes[c] / float(len(rows))\n",
    "        impurity -= prob_of_c**2\n",
    "    return impurity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0: 3, 1: 2, 2: 2, 3: 3}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "count_class_freq(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.74\n"
     ]
    }
   ],
   "source": [
    "ct=gini(data)\n",
    "print(ct)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "#information gain for a split.\n",
    "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)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "dt=[\n",
    "    [10.0,1],\n",
    "    [30.0, 2],\n",
    "    [60.0, 3],\n",
    "    [50.0,2],\n",
    "    [20.0, 1],\n",
    "    [95.0, 3],\n",
    "    [85.0, 1]\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "dt=[\n",
    "    [30.0, 2],\n",
    "    [60.0, 3],\n",
    "    [50.0,2],\n",
    "    [95.0, 3],\n",
    "    [85.0, 1]\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "dt=[\n",
    "    [60.0, 3],\n",
    "    [95.0, 3],\n",
    "    [85.0, 1]\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "dt=[\n",
    "    [17,0],\n",
    "    [25, 0],\n",
    "    [38, 0],\n",
    "    [42,1],\n",
    "    [44, 1],\n",
    "    [47, 2],\n",
    "    [49, 2],\n",
    "    [50, 3],\n",
    "    [54, 3],\n",
    "    [53, 3]\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "data=np.array(dt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "ndt=np.array(dt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[array([17,  0]), array([25,  0])]\n",
      "\n",
      "[array([38,  0]), array([42,  1]), array([44,  1]), array([47,  2]), array([49,  2]), array([50,  3]), array([54,  3]), array([53,  3])]\n"
     ]
    }
   ],
   "source": [
    "lt,rt=num_split(data, 25)\n",
    "print(lt)\n",
    "print()\n",
    "print(rt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.16499999999999992"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lt,rt=num_split(data, 25)\n",
    "info_gain(lt,rt,ct)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[30.  2.]\n"
     ]
    }
   ],
   "source": [
    "print(rt[0])\n",
    "data=rt[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "lt,rt=num_split(data, 54)\n",
    "info_gain(lt,rt,ct)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}