notebooks/01_classification/00_decision_tree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Decision tree step by step"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-20T10:15:19.729009Z",
     "start_time": "2019-03-20T10:15:14.393640Z"
    },
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "%load_ext autoreload\n",
    "%autoreload 2\n",
    "import os\n",
    "%matplotlib notebook\n",
    "# %matplotlib inline\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "sns.set()\n",
    "plt.style.use('seaborn-whitegrid')\n",
    "import sklearn\n",
    "from sklearn.model_selection import train_test_split\n",
    "from sklearn import metrics"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-19T23:03:08.148467Z",
     "start_time": "2019-03-19T23:03:08.109967Z"
    }
   },
   "outputs": [],
   "source": [
    "##### GOOGLE COLAB ######\n",
    "# ! pip install ipywidgets\n",
    "# ! jupyter nbextension enable --py widgetsnbextension\n",
    "if not os.path.exists('./decision_trees_utils.py'):\n",
    "    ! wget https://raw.githubusercontent.com/davidggphy/2019_03_Curso_IFT/master/notebooks/01_classification/decision_trees_utils.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-20T10:15:27.248187Z",
     "start_time": "2019-03-20T10:15:27.215843Z"
    }
   },
   "outputs": [],
   "source": [
    "from decision_trees_utils import print_tree_sklearn\n",
    "from decision_trees_utils import plot_interacting_tree_boundaries\n",
    "from decision_trees_utils import plot_tree_boundaries\n",
    "from decision_trees_utils import tree_sklearn_to_nodes\n",
    "from decision_trees_utils import tree_dic_to_nodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creating and preprocessing the data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-20T10:31:53.264436Z",
     "start_time": "2019-03-20T10:31:53.225536Z"
    }
   },
   "outputs": [],
   "source": [
    "dic_data_A = {'n': 30 ,'mean': (0,2), 'cov' :((1,0),(0,2)), 'y' : 0 }  # RED\n",
    "dic_data_B = {'n': 25 ,'mean': (1,0), 'cov' :((3,0),(0,1)), 'y' : 1 }  # BLUE\n",
    "dic_data = {'A': dic_data_A, 'B' : dic_data_B }\n",
    "\n",
    "# We sample the points with numpy.random\n",
    "np.random.seed(0)\n",
    "samples = {key : np.random.multivariate_normal(dic['mean'], np.array(dic['cov']), dic['n']) \n",
    "           for key,dic in dic_data.items()}\n",
    "     \n",
    "X = np.concatenate(tuple(samples[key] for key in dic_data.keys() ),axis=0)\n",
    "Y = np.concatenate(tuple(dic['y']* np.ones(dic['n'], dtype='int') \n",
    "                         for key,dic in dic_data.items() ), axis=0)\n",
    "\n",
    "\n",
    "# Train Test Split. 80% / 20%.\n",
    "X_train,X_test,Y_train, Y_test = train_test_split(X,Y,test_size = 0.2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-20T10:31:53.792371Z",
     "start_time": "2019-03-20T10:31:53.750309Z"
    }
   },
   "outputs": [],
   "source": [
    "# We transform into coordinates in the plane to make plotting easier.\n",
    "colors = [\n",
    "    \"#%02x%02x%02x\" % (int(r), int(g), int(b)) for r, g ,b  in 150*np.eye(3)[[0,2,1]][np.array(Y_train,dtype='int')]\n",
    "]\n",
    "colors_test = [\n",
    "    \"#%02x%02x%02x\" % (int(r), int(g), int(b)) for r, g ,b  in 150*np.eye(3)[[0,2,1]][np.array(Y_test,dtype='int')]\n",
    "]\n",
    "x0_range = (X[:,0].min()-1,X[:,0].max()+1)\n",
    "x1_range = (X[:,1].min()-1,X[:,1].max()+1)\n",
    "x0 = X_train[:,0] \n",
    "x1 = X_train[:,1] \n",
    "x0_test = X_test[:,0] \n",
    "x1_test = X_test[:,1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-20T10:31:54.927957Z",
     "start_time": "2019-03-20T10:31:54.738913Z"
    }
   },
   "outputs": [],
   "source": [
    "fig = plt.figure(figsize=(5,5))\n",
    "ax = fig.add_subplot(111)\n",
    "ax.set_xlim(x0_range)\n",
    "ax.set_ylim(x1_range)\n",
    "# TRAIN\n",
    "ax.scatter(x0, x1, s = 17, \n",
    "          alpha=1, c=colors )\n",
    "# TEST\n",
    "ax.scatter(x0_test, x1_test, s = 17, \n",
    "          alpha=0.3, c=colors_test )\n",
    "\n",
    "ax.figure.canvas.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Logistic Regression with sklearn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-20T10:31:56.073816Z",
     "start_time": "2019-03-20T10:31:56.019061Z"
    }
   },
   "outputs": [],
   "source": [
    "from sklearn.linear_model import LogisticRegression\n",
    "clf_log = LogisticRegression(solver='lbfgs', multi_class='multinomial').fit(X_train,Y_train)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can extract the coefficients of the linear regression to plot the decision boundary"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-20T10:31:57.348836Z",
     "start_time": "2019-03-20T10:31:57.312183Z"
    }
   },
   "outputs": [],
   "source": [
    "# Coefficients of the linear regression's bondary. Bias and slopes\n",
    "bias = clf_log.intercept_[0]\n",
    "alpha0, alpha1 = tuple(clf_log.coef_[0])\n",
    "x_line = x0_range\n",
    "y_line = tuple(-(bias+alpha0*x)/alpha1 for x in x_line)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-20T10:31:58.133801Z",
     "start_time": "2019-03-20T10:31:57.960125Z"
    },
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "fig = plt.figure(figsize=(5, 5))\n",
    "ax = fig.add_subplot(111)\n",
    "ax.set_xlim(x0_range)\n",
    "ax.set_ylim(x1_range)\n",
    "# TRAIN\n",
    "ax.scatter(x0, x1, s=17, alpha=1, c=colors)\n",
    "# TEST\n",
    "ax.scatter(x0_test, x1_test, s=17, alpha=0.3, c=colors_test)\n",
    "# LINE\n",
    "ax.plot(x_line, y_line, c='black')\n",
    "# PLOT ALL\n",
    "ax.figure.canvas.draw()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Classification Decision Tree with Sklearn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-20T10:31:59.065334Z",
     "start_time": "2019-03-20T10:31:59.031710Z"
    }
   },
   "outputs": [],
   "source": [
    "clf_tree = tree.DecisionTreeClassifier(criterion='gini')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-20T10:31:59.522439Z",
     "start_time": "2019-03-20T10:31:59.481953Z"
    }
   },
   "outputs": [],
   "source": [
    "clf_tree = clf_tree.fit(X_train,Y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-20T10:35:21.994721Z",
     "start_time": "2019-03-20T10:35:21.955925Z"
    }
   },
   "outputs": [],
   "source": [
    "from sklearn import tree\n",
    "clf_gini = tree.DecisionTreeClassifier(criterion='gini',min_samples_leaf=10).fit(X_train, Y_train)\n",
    "clf_ent = tree.DecisionTreeClassifier(criterion='entropy').fit(X_train, Y_train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-20T10:35:23.240603Z",
     "start_time": "2019-03-20T10:35:22.395263Z"
    }
   },
   "outputs": [],
   "source": [
    "print_tree_sklearn(clf_gini)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-20T10:35:32.799393Z",
     "start_time": "2019-03-20T10:35:32.610324Z"
    },
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "fig = plt.figure(figsize=(5, 5))\n",
    "ax = fig.add_subplot(111)\n",
    "# AXES LIMITS\n",
    "ax.set_xlim(x0_range)\n",
    "ax.set_ylim(x1_range)\n",
    "# TRAIN\n",
    "ax.scatter(x0, x1, s = 17, alpha=1, c=colors )\n",
    "# TEST\n",
    "ax.scatter(x0_test, x1_test, s = 17, alpha=0.3, c=colors_test )\n",
    "# DECISSION TREE BOUNDARIES\n",
    "plot_tree_boundaries(ax,clf_gini)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-20T10:32:06.811124Z",
     "start_time": "2019-03-20T10:32:06.646328Z"
    }
   },
   "outputs": [],
   "source": [
    "fig = plt.figure(figsize=(5, 5))\n",
    "ax = fig.add_subplot(111)\n",
    "# AXES LIMITS\n",
    "ax.set_xlim(x0_range)\n",
    "ax.set_ylim(x1_range)\n",
    "# TRAIN\n",
    "ax.scatter(x0, x1, s=17, alpha=1, c=colors)\n",
    "# TEST\n",
    "ax.scatter(x0_test, x1_test, s=17, alpha=0.3, c=colors_test)\n",
    "# DECISSION TREE BOUNDARIES\n",
    "plot_tree_boundaries(ax, clf_ent)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Different criteria change the decision boundaries.\n",
    "\n",
    "We can see how the algorithm works exploring how the boundaries are created step by step."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-20T10:32:10.648313Z",
     "start_time": "2019-03-20T10:32:10.424665Z"
    }
   },
   "outputs": [],
   "source": [
    "fig = plt.figure(figsize=(5, 5))\n",
    "ax = fig.add_subplot(111)\n",
    "# AXES LIMITS\n",
    "ax.set_xlim(x0_range)\n",
    "ax.set_ylim(x1_range)\n",
    "# TRAIN\n",
    "ax.scatter(x0, x1, s=17, alpha=1, c=colors)\n",
    "# TEST\n",
    "ax.scatter(x0_test, x1_test, s=17, alpha=0.3, c=colors_test)\n",
    "# DECISSION TREE BOUNDARIES\n",
    "plot_interacting_tree_boundaries(ax, clf_gini)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Some lessons"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Properties:**\n",
    "- The decision tree behaves as a nested set of if else conditions.\n",
    "- Interpretable (at least the first nodes)\n",
    "    -  We can know why we got a prediction\n",
    "    -  Contrast with common sense and domain knowledge\n",
    "- Decision trees will overfit\n",
    "- But will generalize using next parameters:\n",
    "    -  min_samples_leaf\n",
    "    -  min_samples_split \n",
    "    -  max_depth \n",
    "    -  max_leaf_nodes\n",
    "- Compared to a plain logistic regression, decision trees are slower (no vectorization), but really fast (we can do hyperparameter optimization)\n",
    "- We have many hyperparameters (size of data, depth of tree, etc)\n",
    "- No standarization / normalization (Using original units we will be able to understand the tree better)\n",
    "- Remember that decision boundaries are always orthogonal to the axis, PCA can be useful\n",
    "- Feature selection for free (not used if it not important clf.feature_importances_)\n",
    "- Ordinal categorical variables are treated nicely (They have an intrinsic order, and grouped with neighbours)\n",
    "- Low stability (Small changes in data, can cause a big change in the model)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Decision tree from scratch (dict)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-20T11:19:45.257459Z",
     "start_time": "2019-03-20T11:19:45.196061Z"
    }
   },
   "outputs": [],
   "source": [
    "def entropy(n_classes):\n",
    "    \"\"\"\n",
    "    Calculate the entropy of a discrete distribution. \n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    n_classes : np.array, rank=1\n",
    "        Array with the number of elements in each class.\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "    ent : float\n",
    "        Entropy of the distribution.\n",
    "    \"\"\"\n",
    "    # We have to avoid having a left/right part with no elements\n",
    "    # The number does not matter, since it will be multiplied by prob_right/left = 0.\n",
    "    if np.sum(n_classes) == 0:\n",
    "        return 9999999.\n",
    "    probs = n_classes / np.sum(n_classes)\n",
    "    # Regularize null probabilities\n",
    "    probs = probs[probs > 0.]\n",
    "    # Calculate entropy\n",
    "    ent = -np.sum(probs * np.log2(probs))\n",
    "    return ent\n",
    "\n",
    "\n",
    "def get_best_split(X, Y, class_values=[0, 1], criterion='entropy'):\n",
    "    \"\"\"\n",
    "    Calculate the best split. \n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    X : np.array, rank=2 (#items,#features)\n",
    "        Array with the inputs.\n",
    "    Y : np.array, rank=1 (#items)\n",
    "        Array with the output class of each input.\n",
    "    class_values : list of int/float or np.array\n",
    "        List with the outputs associated with each class.\n",
    "    criterion : str, default='entropy'\n",
    "        Criterion to follow to choose the best split.\n",
    "        'entropy' = Minimize the entropy - p * log2(p)\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "    best_split : tuple (int, float)\n",
    "        Best split, the feature index (in X) and its threshold.\n",
    "        best_split = (feature, threshold)\n",
    "    \"\"\"\n",
    "\n",
    "    best_split = None\n",
    "    best_criterion = 9999999.\n",
    "    # Transform class_values to have one row and as many columns as classes\n",
    "    class_values = np.array(class_values).reshape((1, -1))\n",
    "    # Have to loop over all the features and all the possible splits in each feature\n",
    "    for feature, values_feature in enumerate(X.T):\n",
    "        # Sort the values of that feature\n",
    "        values_sorted = np.sort(values_feature)\n",
    "        # Notice that the number of possible splits is one less than the number of points\n",
    "        for index, value in enumerate(values_sorted[:-1]):\n",
    "            # LEFT PART, <= value\n",
    "            '''\n",
    "            Explanation of the line below\n",
    "            =============================\n",
    "            Goal: Count the number of items in each class on the left part.\n",
    "            1) What is the left part? Values of the feature <= given value\n",
    "                condition = X[:,feature] <= value\n",
    "            2) Take the Y values of those elements.\n",
    "               Note: We reshape it to have only one column, we need that for broadcasting.\n",
    "                Y[condition].reshape((-1,1)) \n",
    "            3) Compare the Y's given above with the value associated to each class\n",
    "               Each column is the comparison with each class. # colums = # classes \n",
    "                condition_class = Y[condition].reshape((-1,1)) == class_values\n",
    "            4) Sum over all the elements in a row to obtain the number of elements in each class\n",
    "                np.sum(condition_class,axis=0)\n",
    "            '''\n",
    "            n_classes_left = np.sum(\n",
    "                                    Y[X[:, feature] <= value].reshape((-1, 1)) == class_values,\n",
    "                                    axis=0)\n",
    "            # Apply the criterion\n",
    "            if criterion == 'entropy':\n",
    "                criterion_left = entropy(n_classes_left)\n",
    "            # Calculate the probability of the left portion: prob_left = n_points_left/n_points\n",
    "            prob_left = np.sum(n_classes_left) / Y.size\n",
    "\n",
    "            # RIGTH PART, > value\n",
    "            n_classes_right = np.sum(\n",
    "                                     Y[X[:, feature] > value].reshape((-1, 1)) == class_values,\n",
    "                                     axis=0)\n",
    "            if criterion == 'entropy':\n",
    "                criterion_right = entropy(n_classes_right)\n",
    "            prob_right = np.sum(n_classes_right) / Y.size\n",
    "\n",
    "            # Calculate the mean value of the quantity of the criterion\n",
    "            criterion_split = prob_left * criterion_left + prob_right * criterion_right\n",
    "            # Keep track of the best split, update it if neccesary\n",
    "            if criterion_split < best_criterion:\n",
    "                best_split = (feature, (value + values_sorted[index + 1]) / 2)\n",
    "                best_criterion = criterion_split\n",
    "    return best_split\n",
    "\n",
    "\n",
    "def train_decision_tree(X,Y,class_values=[0, 1],\n",
    "                        criterion='entropy',\n",
    "                        min_samples_leaf=1):\n",
    "    \"\"\"\n",
    "    Train decision tree and save the structure in a nested dict.\n",
    "\n",
    "    Parameters\n",
    "    ----------\n",
    "    X : np.array, rank=2 (#items,#features)\n",
    "        Array with the inputs.\n",
    "    Y : np.array, rank=1 (#items)\n",
    "        Array with the output class of each input.\n",
    "    class_values : list of int/float or np.array\n",
    "        List with the outputs associated with each class.\n",
    "    criterion : str, default='entropy'\n",
    "        Criterion to follow to choose the best split.\n",
    "        'entropy' = Minimize the entropy - p * log2(p)\n",
    "    min_samples_leaf : int, default=1\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "    tree_dict : dict\n",
    "        Nested dictionary with the structure of the decision tree.\n",
    "        Each node consists of a dictionary:\n",
    "           node_dict = {'feature': int, 'threshold': float, 'left': dict, 'right': dict}\n",
    "        'feature' is the feature index as it appears in X.\n",
    "        'threshold' is the vlaue of the threshold for that split.\n",
    "        'left' is the left child. values < threshold\n",
    "        'right' is the right child. values > threshold\n",
    "        If a node has no child/children, then 'left' and/or 'right' = None\n",
    "    \"\"\"\n",
    "    # Given the dataset, we evaluate the best split (feature,threshold)\n",
    "    feature, threshold = get_best_split(\n",
    "        X, Y, class_values=class_values, criterion=criterion)\n",
    "    # Separate the dataset into left and right parts.\n",
    "    X_left = X[X[:, feature] <= threshold]\n",
    "    Y_left = Y[X[:, feature] <= threshold]\n",
    "    # If there is more than one class in the region and the number of items is > min_samples_leaf\n",
    "    # we iterate the splitting.\n",
    "    if (np.unique(Y_left).size > 1) and (Y_left.size > min_samples_leaf):\n",
    "        left_node = train_decision_tree(\n",
    "            X_left,\n",
    "            Y_left,\n",
    "            class_values=class_values,\n",
    "            min_samples_leaf=min_samples_leaf)\n",
    "    else:\n",
    "        left_node = None\n",
    "    X_right = X[X[:, feature] > threshold]\n",
    "    Y_right = Y[X[:, feature] > threshold]\n",
    "    if (np.unique(Y_right).size > 1) and (Y_right.size > min_samples_leaf):\n",
    "        right_node = train_decision_tree(\n",
    "            X_right,\n",
    "            Y_right,\n",
    "            class_values=class_values,\n",
    "            min_samples_leaf=min_samples_leaf)\n",
    "    else:\n",
    "        right_node = None\n",
    "    return {\n",
    "        'feature': feature,\n",
    "        'threshold': threshold,\n",
    "        'left': left_node,\n",
    "        'right': right_node\n",
    "    }"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The structure of the decision tree has been saved in a nested dictionary. This is, each note is a dictionary with the following `keys : values` pairs:\n",
    "\n",
    "- `feature : int`. The feature in which we perform the split.\n",
    "- `threshold : float`. The value of the feature that acts as a threshold in the split.\n",
    "- `left : dic`. Dictionary with the left node (value <= threshold). None if it has not left child.\n",
    "- `right : dic`. Dictionary with the right node (value > threshold). None if it has not right child.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-20T11:19:46.784374Z",
     "start_time": "2019-03-20T11:19:46.700748Z"
    }
   },
   "outputs": [],
   "source": [
    "dic_tree = train_decision_tree(X_train,Y_train)\n",
    "dic_tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To make it more readable, and to can use the `plot_tree_boundaries` method, the nested dictionary can be transformed into a list of named tuples, called Nodes. In this case the left/right inputs in each Node are the indices in the list of the left/right children."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-20T11:17:30.094897Z",
     "start_time": "2019-03-20T11:17:30.014458Z"
    }
   },
   "outputs": [],
   "source": [
    "dic_tree = train_decision_tree(X_train,Y_train)\n",
    "tree_dic_to_nodes(dic_tree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To finish the comparison, we can compare our implementation with the sklearn one. \n",
    "\n",
    "Notice that the decision boundaries does not have to match exactly, since when applying the heuristic, there can be several splits with the same value of the criterion variable (entropy, gini). This is, there can be several global minima and, in our case, we have establish that we select the first one found (which consist in the one with the lowest feature index and lowest value of the threshold).\n",
    "\n",
    "As a consequence of that, one expect to see more splits in the `X0` axis in our algorithm, i.e., more vertical boundaries."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-20T11:19:50.961876Z",
     "start_time": "2019-03-20T11:19:50.688579Z"
    }
   },
   "outputs": [],
   "source": [
    "fig = plt.figure(figsize=(8, 4))\n",
    "# FIRST SUBPLOT\n",
    "ax=plt.subplot(1, 2, 1)\n",
    "# AXES LIMITS\n",
    "ax.set_xlim(x0_range)\n",
    "ax.set_ylim(x1_range)\n",
    "ax.set_title('Our implementation')\n",
    "# TRAIN\n",
    "ax.scatter(x0, x1, s = 17, alpha=1, c=colors )\n",
    "# TEST\n",
    "ax.scatter(x0_test, x1_test, s = 17, alpha=0.3, c=colors_test )\n",
    "# DECISSION TREE BOUNDARIES\n",
    "plot_tree_boundaries(ax,dic_tree,is_nodes=False,is_sklearn_clf=False)\n",
    "# SECOND SUBPLOT\n",
    "ax2=plt.subplot(122, frameon=False)\n",
    "# AXES LIMITS\n",
    "ax2.set_xlim(x0_range)\n",
    "ax2.set_ylim(x1_range)\n",
    "ax2.set_title('Sklearn (entropy)')\n",
    "# TRAIN\n",
    "ax2.scatter(x0, x1, s = 17, \n",
    "          alpha=1, c=colors )\n",
    "# TEST\n",
    "ax2.scatter(x0_test, x1_test, s = 17, \n",
    "          alpha=0.3, c=colors_test )\n",
    "# DECISSION TREE BOUNDARIES\n",
    "plot_tree_boundaries(ax2,clf_ent)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-13T01:48:52.186237Z",
     "start_time": "2019-03-13T01:48:52.182809Z"
    }
   },
   "source": [
    "## Exercise: \n",
    "\n",
    "Implement the Decission Tree Classifier using the gini index instead of the entropy and compare with the sklearn solution.\n",
    "\n",
    "This is, create the `gini` index function and introduce it into \n",
    "`get_best_split`\n",
    "and \n",
    "`train_decision_tree`\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def gini(n_classes): \n",
    "    ### TODO\n",
    "    return gin"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise: \n",
    "\n",
    "Modify the `get_best_split` function to have an option that allows to select the best split, among all of them that minimize the criterion, in a random way."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise: \n",
    "\n",
    "Implement a `max_depth` option in our `train_decision_tree` function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-21T18:44:44.230141Z",
     "start_time": "2019-03-21T18:44:44.226109Z"
    }
   },
   "source": [
    "## (*) Exercise:\n",
    "\n",
    "Relaxing the greedy-ness. As you know, the Decision Tree algorithm is a greedy one, this is, in order to build the best tree it selects the optimal split at each step, but there can be the case in which the global optimal solution is built upon non optimal steps. A way of relaxing that is through beam search. \n",
    "\n",
    "Using beam search, at each step we save the best `B` solutions, where `B`is the beam width. Where now, to define best, we need a global criterion (depending on the current step and the previous ones). \n",
    "\n",
    "Can you define a global criterion?\n",
    "\n",
    "Can you implement the beam search to build the tree according to that criterion?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercise: \n",
    "\n",
    "Implement a predict function using our decision tree structure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "heading_collapsed": true
   },
   "source": [
    "## Another implementation\n",
    "https://machinelearningmastery.com/implement-decision-tree-algorithm-scratch-python/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-19T14:29:31.527744Z",
     "start_time": "2019-03-19T14:29:31.463062Z"
    },
    "hidden": true
   },
   "outputs": [],
   "source": [
    "# Split a dataset based on an attribute and an attribute value\n",
    "def test_split(index, value, dataset):\n",
    "    left, right = list(), list()\n",
    "    for row in dataset:\n",
    "        if row[index] < value:\n",
    "            left.append(row)\n",
    "        else:\n",
    "            right.append(row)\n",
    "    return left, right\n",
    "\n",
    "# Calculate the Gini index for a split dataset\n",
    "\n",
    "\n",
    "def gini_index(groups, classes):\n",
    "    # count all samples at split point\n",
    "    n_instances = float(sum([len(group) for group in groups]))\n",
    "    # sum weighted Gini index for each group\n",
    "    gini = 0.0\n",
    "    for group in groups:\n",
    "        size = float(len(group))\n",
    "        # avoid divide by zero\n",
    "        if size == 0:\n",
    "            continue\n",
    "        score = 0.0\n",
    "        # score the group based on the score for each class\n",
    "        for class_val in classes:\n",
    "            p = [row[-1] for row in group].count(class_val) / size\n",
    "            score += p * p\n",
    "        # weight the group score by its relative size\n",
    "        gini += (1.0 - score) * (size / n_instances)\n",
    "    return gini\n",
    "\n",
    "# Select the best split point for a dataset\n",
    "\n",
    "\n",
    "def get_split(dataset):\n",
    "    class_values = list(set(row[-1] for row in dataset))\n",
    "    b_index, b_value, b_score, b_groups = 999, 999, 999, None\n",
    "    for index in range(len(dataset[0])-1):\n",
    "        for row in dataset:\n",
    "            groups = test_split(index, row[index], dataset)\n",
    "            gini = gini_index(groups, class_values)\n",
    "            if gini < b_score:\n",
    "                b_index, b_value, b_score, b_groups = index, row[index], gini, groups\n",
    "    return {'index': b_index, 'value': b_value, 'groups': b_groups}\n",
    "\n",
    "# Create a terminal node value\n",
    "\n",
    "\n",
    "def to_terminal(group):\n",
    "    outcomes = [row[-1] for row in group]\n",
    "    return max(set(outcomes), key=outcomes.count)\n",
    "\n",
    "# Create child splits for a node or make terminal\n",
    "\n",
    "\n",
    "def split(node, max_depth, min_size, depth):\n",
    "    left, right = node['groups']\n",
    "    del(node['groups'])\n",
    "    # check for a no split\n",
    "    if not left or not right:\n",
    "        node['left'] = node['right'] = to_terminal(left + right)\n",
    "        return\n",
    "    # check for max depth\n",
    "    if depth >= max_depth:\n",
    "        node['left'], node['right'] = to_terminal(left), to_terminal(right)\n",
    "        return\n",
    "    # process left child\n",
    "    if len(left) <= min_size:\n",
    "        node['left'] = to_terminal(left)\n",
    "    else:\n",
    "        node['left'] = get_split(left)\n",
    "        split(node['left'], max_depth, min_size, depth+1)\n",
    "    # process right child\n",
    "    if len(right) <= min_size:\n",
    "        node['right'] = to_terminal(right)\n",
    "    else:\n",
    "        node['right'] = get_split(right)\n",
    "        split(node['right'], max_depth, min_size, depth+1)\n",
    "\n",
    "# Build a decision tree\n",
    "\n",
    "\n",
    "def build_tree(train, max_depth, min_size):\n",
    "    root = get_split(train)\n",
    "    split(root, max_depth, min_size, 1)\n",
    "    return root\n",
    "\n",
    "# Print a decision tree\n",
    "\n",
    "\n",
    "def print_tree(node, depth=0):\n",
    "    if isinstance(node, dict):\n",
    "        print('%s[X%d < %.3f]' %\n",
    "              ((depth*' ', (node['index']+1), node['value'])))\n",
    "        print_tree(node['left'], depth+1)\n",
    "        print_tree(node['right'], depth+1)\n",
    "    else:\n",
    "        print('%s[%s]' % ((depth*' ', node)))\n",
    "\n",
    "\n",
    "dataset = np.hstack([X_train, Y_train.reshape((-1, 1))])\n",
    "tree = build_tree(dataset, 15, 5)\n",
    "print_tree(tree)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-19T14:29:39.249159Z",
     "start_time": "2019-03-19T14:29:39.213097Z"
    },
    "hidden": true
   },
   "outputs": [],
   "source": [
    "tree"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "ExecuteTime": {
     "end_time": "2019-03-13T01:36:35.548460Z",
     "start_time": "2019-03-13T01:36:34.555600Z"
    },
    "hidden": true
   },
   "outputs": [],
   "source": [
    "print_cart(clf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "hidden": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "jupytext": {
   "text_representation": {
    "extension": ".py",
    "format_name": "percent",
    "format_version": "1.2",
    "jupytext_version": "1.0.1"
   }
  },
  "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.6"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}