Decision Trees.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 136,
   "metadata": {},
   "outputs": [],
   "source": [
    "import queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "training_data = [\n",
    "    ['Green', 3, 'Apple'],\n",
    "    ['Yellow', 3, 'Apple'],\n",
    "    ['Red', 1, 'Grape'],\n",
    "    ['Red', 1, 'Grape'],\n",
    "    ['Yellow', 3, 'Lemon'],\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "col_names=['color','diameter','label']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def unique_labels(data,col):  #function to return unique values for anycolumn\n",
    "    return set([row[col] for row in data])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Green', 'Red', 'Yellow'}"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "unique_labels(training_data,0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def class_counts(data,label_loc=-1): #count the values in the dataset #Presumes that the label is at the last column\n",
    "    d={}\n",
    "    for rows in data:\n",
    "        label=rows[-1]\n",
    "        if label not in d:\n",
    "            d[label]=1\n",
    "        else:\n",
    "            d[label]+=1\n",
    "            \n",
    "    return d"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'Apple': 2, 'Grape': 2, 'Lemon': 1}"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class_counts(training_data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def is_numeric(value):\n",
    "    if type(value)==float or type(value)==int:\n",
    "        return True\n",
    "    \n",
    "    return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, False)"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "is_numeric(90),is_numeric('abc')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Question():\n",
    "    \n",
    "    def __init__(self,column,value):\n",
    "        self.column=column\n",
    "        self.value=value\n",
    "        \n",
    "    def match(self,example):\n",
    "        exp_val=example[self.column]\n",
    "        \n",
    "        if is_numeric(exp_val):\n",
    "            return exp_val>=self.value\n",
    "        else:\n",
    "            return exp_val==self.value\n",
    "        \n",
    "    def __repr__(self):\n",
    "        if is_numeric(self.value):\n",
    "            condition='>='\n",
    "        else:\n",
    "            condition='=='\n",
    "        return f'Is {col_names[self.column]} {str(condition)} {str(self.value)} ?'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Is diameter >= 3 ?"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q=Question(1,3)\n",
    "q"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q.match(training_data[-1]) #last sample indeed has a value >=3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition(data,question):\n",
    "    true_clause=[]\n",
    "    false_clause=[]\n",
    "    for row in data:\n",
    "        if question.match(row):\n",
    "            true_clause.append(row)\n",
    "        else:\n",
    "            false_clause.append(row)\n",
    "            \n",
    "    return true_clause,false_clause"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([['Green', 3, 'Apple'], ['Yellow', 3, 'Apple'], ['Yellow', 3, 'Lemon']],\n",
       " [['Red', 1, 'Grape'], ['Red', 1, 'Grape']])"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "true_row,false_row=partition(training_data,q)\n",
    "true_row,false_row"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gini_impurity(rows):\n",
    "    initial_value=1\n",
    "    counts=class_counts(rows)\n",
    "    for label in counts:\n",
    "        lbl_count=counts[label]\n",
    "        prob_label=lbl_count/len(rows)\n",
    "        initial_value-=prob_label**2\n",
    "        \n",
    "    return initial_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.0"
      ]
     },
     "execution_count": 75,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gini_impurity(false_row)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {},
   "outputs": [],
   "source": [
    "def info_gain(left_split,right_split,orignal_gini):\n",
    "    d=len(left_split)+len(right_split)\n",
    "    \n",
    "    return orignal_gini-((len(left_split)/d)*gini_impurity(left_split)+(len(right_split)/d)*gini_impurity(right_split))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Is diameter >= 3 ?\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "0.37333333333333324"
      ]
     },
     "execution_count": 90,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "q=Question(1,3)\n",
    "print(q)\n",
    "true_row,false_row=partition(training_data,q)\n",
    "info_gain(true_row,false_row,gini_impurity(training_data))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {},
   "outputs": [],
   "source": [
    "def best_split(data):\n",
    "    n_features=len(data[0])-1  #last feature label is omitted\n",
    "    best_gain=0\n",
    "    best_question=None\n",
    "    \n",
    "    for f in range(0,n_features):\n",
    "        unique_vals=set([rows[f] for rows in data])\n",
    "        \n",
    "        for values in unique_vals:\n",
    "            question=Question(f,values)\n",
    "            \n",
    "            true_row,false_row=partition(data,question)\n",
    "            gain=info_gain(true_row,false_row,gini_impurity(data))\n",
    "            \n",
    "            if gain >=best_gain:\n",
    "                best_gain=gain\n",
    "                best_question=question\n",
    "                \n",
    "    return best_gain,best_question"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(0.37333333333333324, Is diameter >= 3 ?)"
      ]
     },
     "execution_count": 108,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "best_split(training_data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Leaf_Node():\n",
    "    \n",
    "    def __init__(self,rows):\n",
    "        self.predictions=class_counts(rows)  \n",
    "        self.prediction=max(self.predictions,key=lambda x:x[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Decision_Node():\n",
    "    \n",
    "    def __init__(self,left_split,right_split,question):\n",
    "        self.question=question\n",
    "        self.left_split=left_split\n",
    "        self.right_split=right_split\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 151,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_tree(dataset):\n",
    "    \n",
    "    \n",
    "    gain,question=best_split(dataset)\n",
    "    \n",
    "    if gain==0:\n",
    "        return Leaf_Node(dataset)\n",
    "    \n",
    "    true_data,false_data=partition(dataset,question)\n",
    "    \n",
    "    right_tree=build_tree(true_data)\n",
    "    false_tree=build_tree(false_data)\n",
    "    \n",
    "    \n",
    "    return Decision_Node(false_tree,right_tree,question)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "metadata": {},
   "outputs": [],
   "source": [
    "root_decision=build_tree(training_data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "metadata": {},
   "outputs": [],
   "source": [
    "def print_decision_tree(root):\n",
    "    q=queue.Queue()\n",
    "    q.put(root)\n",
    "    Level=0\n",
    "    while not (q.empty()):\n",
    "        node=q.get()\n",
    "        \n",
    "        if isinstance(node,Leaf_Node):\n",
    "            print('Predictions',str(node.predictions))\n",
    "        \n",
    "        else:\n",
    "            \n",
    "            print(str(Level)+' '+str(node.question))\n",
    "            Level+=1\n",
    "            q.put(node.left_split)\n",
    "            q.put(node.right_split)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 159,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 Is diameter >= 3 ?\n",
      "Predictions {'Grape': 2}\n",
      "1 Is color == Green ?\n",
      "Predictions {'Apple': 1, 'Lemon': 1}\n",
      "Predictions {'Apple': 1}\n"
     ]
    }
   ],
   "source": [
    "print_decision_tree(root_decision)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "metadata": {},
   "outputs": [],
   "source": [
    "global predictions\n",
    "predictions=[]\n",
    "def classify(data,root):\n",
    "    if isinstance(root,Leaf_Node):\n",
    "        predictions.append(root.prediction)\n",
    "        return\n",
    "        \n",
    "    if root.question.match(data):\n",
    "        classify(data,root.right_split)\n",
    "        \n",
    "    else:\n",
    "        classify(data,root.left_split)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "metadata": {},
   "outputs": [],
   "source": [
    "testing_data = [\n",
    "    ['Green', 3, 'Apple'],\n",
    "    ['Yellow', 4, 'Apple'],\n",
    "    ['Red', 2, 'Grape'],\n",
    "    ['Red', 1, 'Grape'],\n",
    "    ['Yellow', 3, 'Lemon'],\n",
    "]\n",
    "for row in testing_data:\n",
    "    classify(row,root_decision)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 165,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Apple', 'Apple', 'Grape', 'Grape', 'Apple']"
      ]
     },
     "execution_count": 165,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "predictions"
   ]
  },
  {
   "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.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}