Ex5-Solution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercise 5: Decision Trees\n",
    "\n",
    "# In-Class Basics\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "import scipy.stats as stats # We will use stats.entropy to calculate the entropy of a distribution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To implement decision trees, we will need recursive functions. Here is a simple example to calculate the factorial of an integer (n!). Make sure you understand how this works before moving on."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def factorial(n):\n",
    "    \n",
    "    if n==1:\n",
    "        return 1\n",
    "    else:\n",
    "        return n*factorial(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "120"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factorial(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Load and prepare the data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "((15000, 16), (15000,))\n",
      "(array([ True,  True,  True,  True,  True,  True,  True,  True,  True,\n",
      "        True,  True,  True, False, False, False, False]), 0)\n"
     ]
    }
   ],
   "source": [
    "f = np.load(\"Ex5_data.npz\") # Make sure to also download this file from github\n",
    "X = f[\"arr_0\"]\n",
    "y = f[\"arr_1\"]\n",
    "\n",
    "# We have a total of 15k examples with 16 features per example. \n",
    "# All features are binary - so either True (1) or False (0).\n",
    "# Additionally we have a vector of class labels y. \n",
    "# For each example the class is either 0 or 1.\n",
    "# The features contain enough information to (partially) infer the class.\n",
    "print(X.shape,y.shape)\n",
    "print(X[0],y[0])\n",
    "\n",
    "# Split into training (10k examples) and testing (5k examples) data\n",
    "X_train = X[:10000]\n",
    "X_test = X[10000:]\n",
    "\n",
    "y_train = y[:10000]\n",
    "y_test = y[10000:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's define a very simple format for specifying decistion trees: \n",
    "# nested python lists\n",
    "# Each node is specified by 3 quantities:\n",
    "# - what feature to split on (an integer specifying the column of the data matrix)\n",
    "# - what to do if the feature == True \n",
    "#     This can be either another list (tree) specifying a further subdivision or an integer specifying the class\n",
    "# - what to do if the feature == False \n",
    "#     (again, either a list or an integer)\n",
    "\n",
    "# Simple example:\n",
    "tree_1 = [5, 0, 1] \n",
    "# This should be interpreted as:\n",
    "# if x[5] == True choose class 0,\n",
    "# else choose class 1\n",
    "\n",
    "# Slightly more complicated\n",
    "tree_2 = [5,1, [3,0,1]] \n",
    "# This should be interpreted as:\n",
    "# if x[5] == True choose class 1\n",
    "# else\n",
    "#   if x[3] == True choose class 0 \n",
    "#   else choose class 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Recursive function to apply a decision tree to a given exampke x\n",
    "\n",
    "def apply_decision_tree(x, tree):\n",
    "        \n",
    "    # As specified above, a tree can either be a list or a number\n",
    "    # If it is a list, we have to go deeper, \n",
    "    # if it is a number, we return it.\n",
    "        \n",
    "    # Test if the object is a list\n",
    "    if tree.__class__ == list:\n",
    "        \n",
    "        # If it is a list then we interprete it as:\n",
    "        # [feature to test, tree to follow if True, tree to follow if False]\n",
    "        \n",
    "        # Test if the feature is true\n",
    "        if x[tree[0]]:\n",
    "            # go deeper on the feature==True path\n",
    "            return apply_decision_tree(x,tree[1])\n",
    "        else:\n",
    "            # go deeper on the feature==False path\n",
    "            return apply_decision_tree(x,tree[2])\n",
    "        \n",
    "    else:\n",
    "        # If the 'tree' is just a number, we have reached a leave node. \n",
    "        # Just return the number\n",
    "        return tree\n",
    "        \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Homework Problems\n",
    "\n",
    " * Write a function `calc_gain(X,y,feature)` that takes a matrix of training events `X`, correpsponding labels `y` and a feature index `feature` and return the entropy gain (as defined in the lecture) in y when splitting according to feature. You can find a skeleton version of the function below.\n",
    " * Write a function `build_decision_tree(X,y,features)` that takes a matrix of training events `X`, correpsponding labels `y` and a list of `features` and returns a decision tree using the format specified above. You can find a skeleton version of the function below.\n",
    " * Use `build_decision_tree` to calculate a decision tree for the X_test sample. Apply it to all examples in `X_test` to obtain a vector of predictions `y_pred`. Compare it to `y_test` and calculate the accuracy (the fraction of examples where the prediction and true label are identical). The code for doing this is already available below and simply needs to be run once `build_decision_tree` and `calc_gain` are finished."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calc_gain(X,y,feature):\n",
    "\n",
    "    # \n",
    "    sel = (X[:,feature]==True)\n",
    "    \n",
    "    # First calculate the entropy for y as well as \n",
    "    # for the subsets of y that pass and fail the selection, respectively\n",
    "    \n",
    "    # -> Your code goes here\n",
    "    \n",
    "    # Then calculate the fraction of examples that pass and fail the selection and use it to \n",
    "    # calculate the average entropy after the selection\n",
    "    \n",
    "    # -> Your code goes here\n",
    "    \n",
    "    # Finally, return the difference in entropy of y and the average entropy you calculated above\n",
    "    \n",
    "    # -> Your code goes here\n",
    "    \n",
    "    entropy_all = stats.entropy(y,base=2)\n",
    "    entropy_pass = stats.entropy(y[sel],base=2)\n",
    "    entropy_fail = stats.entropy(y[~sel],base=2)\n",
    "\n",
    "    fraction_pass = 1. * sum(sel) / len(sel)\n",
    "    fraction_fail = 1.  - fraction_pass\n",
    "\n",
    "    if fraction_pass == 1. or fraction_fail == 1.:\n",
    "        return 0.\n",
    "    else:\n",
    "        entropy_avg = fraction_pass * entropy_pass + fraction_fail * entropy_fail\n",
    "\n",
    "        if entropy_avg > 0:\n",
    "            return entropy_all - entropy_avg\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def build_decision_tree(X,y, features):\n",
    "\n",
    "    \n",
    "    # Check if all the examples in y are from the same class. \n",
    "    # In that case, return this class.\n",
    "\n",
    "    if y.mean() == 1:\n",
    "        return 1\n",
    "\n",
    "    if y.mean() == 0:\n",
    "        return 0\n",
    "\n",
    "    # Check if we have any features left to try. \n",
    "    # If not, return the class that has the larger fraction of examples in y \n",
    "    # (at this point in the selection chain)\n",
    "    \n",
    "    if len(features)==0:\n",
    "        return int(round(y.mean()))\n",
    "\n",
    "    # Find the feature that yields the largest information gain\n",
    "    # Use the calc_gain function we defined above and test all available features\n",
    "    \n",
    "    \n",
    "    \n",
    "    best_feature = features[0]\n",
    "    best_gain = calc_gain(X,y,best_feature)\n",
    "\n",
    "    if len(features)>1:\n",
    "        for i in features[1:]:\n",
    "            gain = calc_gain(X,y,i)\n",
    "            if gain > best_gain:\n",
    "                best_gain = gain\n",
    "                beast_feature = i\n",
    "\n",
    "    # Build new matrices of examples (X_pass and y_pass) for the \n",
    "    # examples where the selected feature is True as well as \n",
    "    # X_fail and y_fail for those where the feature is False\n",
    "    # Also build a copy of the list of features without the one we select on         \n",
    "    new_features = [i for i in features if not i==best_feature]\n",
    "    \n",
    "    sel = X[:,best_feature] == True\n",
    "\n",
    "    X_pass = X[sel]\n",
    "    y_pass = y[sel]\n",
    "\n",
    "    X_fail = X[~sel]\n",
    "    y_fail = y[~sel]\n",
    "\n",
    "    # Check if one of the new subcategories is empty. \n",
    "    # If it is, we set the output class for this subcategory\n",
    "    # to the predominant class (at the current point in the selection)\n",
    "    # Otherwise, call build_decision_tree on it. \n",
    "    \n",
    "    if sum(sel):\n",
    "        do_pass = build_decision_tree(X_pass,y_pass,new_features)\n",
    "    else:\n",
    "        do_pass = int(round(y.mean()))\n",
    "\n",
    "    if sum(~sel):\n",
    "        do_fail = build_decision_tree(X_fail,y_fail,new_features)\n",
    "    else:\n",
    "        do_fail = int(round(y.mean()))\n",
    "\n",
    "    # Build and return a list with three entries: \n",
    "    # [best_feature, \n",
    "    #  decision (either class or further build_decision_tree call for pass),\n",
    "    #  decision (either class or further build_decision_tree call for fail)]\n",
    "        \n",
    "    tree = [best_feature, do_pass, do_fail]\n",
    "\n",
    "    return tree\n",
    "    \n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8754"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# The code below can be used to build the tree and calculate the accuracy \n",
    "# once calc_gain and build_precision_tree are properly implemented\n",
    "\n",
    "tree = build_decision_tree(X_train,y_train,range(X_train.shape[1]))\n",
    "\n",
    "# Calculate predictions on the test data\n",
    "y_pred = np.array([apply_decision_tree(X_test[i],tree) for i in range(X_test.shape[0])])\n",
    "\n",
    "# Calculate accuracy\n",
    "1.*sum(y_pred == y_test) / y_pred.shape[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}