08-decision-tree.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Decision Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Objective\n",
    "\n",
    "This notebook introduces decision tree models. **Decision tree** learning is one of the most widely used and practical methods for inductive inference. It's a method for approximating discreted-valued functions that is **robust** to **noisy data** and capable of **learning disjuctive** expressions.\n",
    "\n",
    "### Learning objective\n",
    "\n",
    "After finished this notebook, you should be able to explain **decision tree** learning models, as well as know to use them through the scikit-learn library."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Loading the libraries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "assert sys.version_info >= (3, 6)\n",
    "\n",
    "import numpy\n",
    "assert numpy.__version__ >=\"1.17.3\" \n",
    "import numpy as np\n",
    "\n",
    "import pandas\n",
    "assert pandas.__version__ >= \"0.25.1\"\n",
    "\n",
    "import pandas as pd\n",
    "\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "import seaborn\n",
    "assert seaborn.__version__ >= \"0.9.0\"\n",
    "import seaborn as sns\n",
    "\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Decision trees in scikit-learn\n",
    "\n",
    "In scikit-learn, decision trees are implemented through [tree.DecisionTreeClassifier](http://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html) for classification and [tree.DecisionTreeRegressor](http://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeRegressor.html) for regression."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sklearn\n",
    "assert sklearn.__version__ >='0.21.3'\n",
    "\n",
    "from sklearn import tree\n",
    "from sklearn.tree import DecisionTreeClassifier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1. Toy data set\n",
    "\n",
    "In order to better understand how a decision tree processes the feature space, let us first work on a simulated dataset. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.figure(figsize=(5, 5))\n",
    "\n",
    "x1 = np.random.multivariate_normal([2,2], [[0.1,0],[0,0.1]], 50)\n",
    "x2 = np.random.multivariate_normal([-2,-2], [[0.1,0],[0,0.1]], 50)\n",
    "x3 = np.random.multivariate_normal([-3,3], [[0.1,0.1],[0,0.1]], 50)\n",
    "X1 = np.concatenate((x1,x2,x3), axis=0)\n",
    "\n",
    "y1 = np.random.multivariate_normal([-2,2], [[0.1,0],[0,0.1]], 50)\n",
    "y2 = np.random.multivariate_normal([2,-2], [[0.1,0],[0,0.1]], 50)\n",
    "y3 = np.random.multivariate_normal([-3,-3], [[0.01,0],[0,0.01]], 50)\n",
    "X2 = np.concatenate((y1,y2,y3), axis=0)\n",
    "\n",
    "plt.plot(X1[:,0],X1[:,1], 'x', color='blue', label='class 1')\n",
    "plt.plot(X2[:,0], X2[:,1], 'x', color='orange', label='class 2')\n",
    "\n",
    "\n",
    "plt.legend(loc=(0.4, 0.8), fontsize=12)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Changing the **splitter** to **random**, meaning that the algorithm will consider the feature along which to split _randomly_, rather than picking the optimal one, and then select the best among several _random_ splitting point. Run the algorithm several times. What do you observer?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Training data\n",
    "X_demo = np.concatenate((X1, X2), axis=0)\n",
    "y_demo = np.concatenate((np.zeros(X1.shape[0]), np.ones(X2.shape[0])))\n",
    "\n",
    "clf = tree.DecisionTreeClassifier(splitter=\"random\", random_state=100).fit(X_demo, y_demo)\n",
    "\n",
    "# Create a mesh, i.e., a fine grid of values between the minimum and maximum\n",
    "# values of X1 and X2 in the training data\n",
    "plot_step = 0.02\n",
    "x_min, x_max = X_demo[:, 0].min() - 1, X_demo[:, 0].max() + 1\n",
    "y_min, y_max = X_demo[:, 1].min() - 1, X_demo[:, 1].max() + 1\n",
    "xx, yy = np.meshgrid(np.arange(x_min, x_max, plot_step), np.arange(y_min, y_max, plot_step))\n",
    "\n",
    "# Label each point of the mesh with the trained DecisionTreeClassifier\n",
    "Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])\n",
    "Z = Z.reshape(xx.shape)\n",
    "\n",
    "# Plot the contours corresponding to these labels \n",
    "# (i.e., the decision boundaries of the DecisionTreeClassifier)\n",
    "cs = plt.contourf(xx, yy, Z, cmap=plt.cm.Paired)\n",
    "\n",
    "# Plot the training data \n",
    "plt.plot(X1[:,0], X1[:,1], 'x', label='class 1')\n",
    "plt.plot(X2[:,0], X2[:,1], 'x', label='class 2')\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "?tree.DecisionTreeClassifier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The features are always randomly permuted at each split. To have a determinist behavior, we have to fix the value of `random_state` parameter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Toy data set 2: play tenning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Uncomment and execute the following code if you don't have installed the [```graphviz```](https://pypi.org/project/graphviz/) library."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ! conda install -y -c conda-forge graphviz xorg-libxrender xorg-libxpm\n",
    "# ! pip install graphviz"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tennis = pd.read_csv('data/playtennis.csv')\n",
    "tennis.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.preprocessing import LabelEncoder\n",
    "\n",
    "lb = LabelEncoder()\n",
    "\n",
    "for c in tennis.columns:\n",
    "    tennis[c + '_'] = lb.fit_transform(tennis[c])\n",
    "\n",
    "tennis.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = tennis.iloc[:,7:11] \n",
    "Y = tennis.iloc[:,11]\n",
    "\n",
    "tennis_tree = DecisionTreeClassifier(criterion='entropy')\n",
    "tennis_tree.fit(X, Y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.tree import export_graphviz\n",
    "from IPython.display import SVG\n",
    "import graphviz\n",
    "\n",
    "assert graphviz.__version__ >= '0.13.2'\n",
    "\n",
    "\n",
    "dot_model = export_graphviz(tennis_tree, \n",
    "                            class_names = tennis.columns[0:5], \n",
    "                            feature_names = tennis.columns[1:5], \n",
    "                            impurity = True,\n",
    "                            filled = True,\n",
    "                            rounded = True)\n",
    "\n",
    "graph = graphviz.Source(dot_model)\n",
    "SVG(graph.pipe(format='svg'))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2. Wisconsin Prognostic Breast Cancer dataset\n",
    "\n",
    "The data are available at https://archive.ics.uci.edu/ml/machine-learning-databases/breast-cancer-wisconsin/wpbc.data\n",
    "\n",
    "### Data description\n",
    "\n",
    "* The dataset contains 569 samples of **malign** and **benign** tumor cells\n",
    "* It has 35 columns, where the first one stores the **unique ID** number of the sample, the second one the diagnosis (M=malignant, B=benign), 3--32 ten real-valued features are computed for each cell nucleus\n",
    "\n",
    "    * radius (mean of distances from center to points on the perimeter)\n",
    "    * texture (standard deviation of gray-scale values)\n",
    "    * perimeter\n",
    "    * area\n",
    "    * smoothness (local variation in radius lengths)\n",
    "    * compactness ($\\frac{perimeter^2}{area} - 1.0$)\n",
    "    * concavity (severity of concave portions of the contour)\n",
    "    * concave points (number of concave portions of the contour)\n",
    "    * symmetry\n",
    "    * fractal dimension (coastline approximation - 1); 5 here 3--32 are divided into three parts first is Mean (3-13), Stranded Error(13-23) and Worst(23-32) and each contain 10 parameter (radius, texture,area, perimeter, smoothness,compactness,concavity,concave points,symmetry and fractal dimension).\n",
    "    \n",
    "The goal is to classify whether the breast cancer is **benign** or **malignant**. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Loading the data\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.datasets import load_breast_cancer\n",
    "cancer_ds = load_breast_cancer()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "X = cancer_ds.data\n",
    "y = cancer_ds.target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn import model_selection\n",
    "\n",
    "skf = model_selection.StratifiedKFold(n_splits=5)\n",
    "skf.get_n_splits(X, y)\n",
    "folds = [(tr,te) for (tr,te) in skf.split(X, y)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cross-validation procedures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Import the functions defined in the ```cross_validation.py``` file. Module enables us to reuse code across different jupyter notebooks."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from cross_validation import cross_validate_clf , cross_validate_clf_optimize"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.2 Breast cancer tumor classification data\n",
    "\n",
    "**Question:** Cross-validate 5 different decision trees (with default parameters) and print out their accuracy. Why do you get different values?\n",
    "_Hint:_ _Check the documentation_ (?tree.DecisionTreeClassifier)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn import metrics\n",
    "\n",
    "ypred_dt = [] # will hold the 5 arrays of predictions (1 per tree)\n",
    "\n",
    "for tree_index in range(5):\n",
    "    clf = tree.DecisionTreeClassifier() \n",
    "    pred_proba = cross_validate_clf(X, y, clf, folds)\n",
    "    ypred_dt.append(pred_proba)\n",
    "    \n",
    "    print(\"%.3f\" % metrics.accuracy_score(y, np.where(pred_proba > 0.5, 1, 0)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Setting a value for the ```random_state``` parameter allow us to get the same value."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question:** Compute the mean and standard deviation of the area under the ROC curve of these 5 trees. Plot the ROC curves of these 5 trees.\n",
    "Use the [metrics](http://scikit-learn.org/stable/modules/classes.html#module-sklearn.metrics) module of scikit-learn."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "fpr_dt = [] \n",
    "tpr_dt = [] \n",
    "auc_dt = []\n",
    "\n",
    "for tree_index in range(5):\n",
    "    # Compute the ROC curve of the current tree\n",
    "    fpr_dt_tmp, tpr_dt_tmp, thresholds =  metrics.roc_curve(y, ypred_dt[tree_index], pos_label=1)\n",
    "    # Compute the area under the ROC curve of the current tree\n",
    "    auc_dt_tmp = metrics.auc(fpr_dt_tmp, tpr_dt_tmp)\n",
    "    fpr_dt.append(fpr_dt_tmp)\n",
    "    tpr_dt.append(tpr_dt_tmp)\n",
    "    auc_dt.append(auc_dt_tmp)\n",
    "\n",
    "# Plot the first 4 ROC curves\n",
    "for tree_index in range(4):\n",
    "    plt.plot(fpr_dt[tree_index], tpr_dt[tree_index], '-')\n",
    "            \n",
    "# Plot the last ROC curve, with a label that gives the mean/std AUC\n",
    "plt.plot(fpr_dt[-1], tpr_dt[-1], '-', \n",
    "         label='DT (AUC = %0.2f +/- %0.2f)' % (np.mean(auc_dt), np.std(auc_dt)))\n",
    "\n",
    "# Plot the ROC curve\n",
    "plt.xlabel('False Positive Rate', fontsize=16)\n",
    "plt.ylabel('True Positive Rate', fontsize=16)\n",
    "plt.title('ROC curves', fontsize=16)\n",
    "plt.legend(loc=\"lower right\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.3 Visualizing the decision trees built for the breast cancer classification"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dot_model = export_graphviz(clf, class_names = ['malignant', 'benign'], \n",
    "                            feature_names = cancer_ds.feature_names, \n",
    "                            impurity = True,\n",
    "                            filled = True,\n",
    "                            rounded = True)\n",
    "\n",
    "graph = graphviz.Source(dot_model)\n",
    "\n",
    "SVG(graph.pipe(format='svg'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_feature_importances(model, n_features, feature_names):\n",
    "    plt.barh(range(n_features), model.feature_importances_, align='center')\n",
    "    plt.yticks(np.arange(n_features), feature_names)\n",
    "    plt.ylabel(\"Feature importance\")\n",
    "    plt.ylabel(\"Feature\")\n",
    "    plt.ylim(-1, n_features)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plot_feature_importances(clf, cancer_ds.data.shape[1], cancer_ds.feature_names)"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}