exercise-decision-trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "# ML-Fundamentals - Decision Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "## Table of Contents\n",
    "* [Introduction](#Introduction)\n",
    "* [Requirements](#Requirements) \n",
    "  * [Knowledge](#Knowledge) \n",
    "  * [Modules](#Python-Modules)\n",
    "* [Teaching Content](#Teaching-Content)\n",
    " * [Decision Trees](#Decision-Trees)\n",
    " * [Learning](#Learning)\n",
    " * [Information Gain as Splitting Criterion](#Information-Gain-as-Splitting-Criterion)\n",
    " * [Overfitting](#Overfitting)\n",
    "* [Exercises](#Exercises)\n",
    " * [Loading the Data](#Loading-the-Data)\n",
    " * [Preprocessing](#Preprocessing)\n",
    " * [Training and Visualization](#Training-and-Visualization)\n",
    " * [Prediction / Validation](#Prediction-/-Validation)\n",
    " * [Crossvalidation](#Crossvalidation)\n",
    " * [Gridsearch](#Gridsearch)\n",
    " * [Splitting Criterion Entropy / Information Gain](#Splitting-Criterion-Entropy-/-Information-Gain)\n",
    "* [Summary and Outlook](#Summary-and-Outlook)\n",
    "* [Literature](#Literature) \n",
    "* [Licenses](#Licenses)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "## Introduction\n",
    "\n",
    "In this exercise you will train and evaluate a decision tree. Opposed to the previous exercises with the topics _univariate linear regression_, _multivariate linear regression_, _logistic regression_ and _bias variance tradeoff_, you will not implement the algorithms from scratch using numpy. Instead you will use two python packages written on top of numpy, namely the _pandas_ and the _scikit-learn_ package, which are both widely used by the machine learning community. The steps can be broken down into:\n",
    "\n",
    "1. Load the data from a _csv file_ into a pandas DataFrame object\n",
    "2. Preprocess the data\n",
    "3. Train a decision tree and visualize it.\n",
    "4. Do hyperparameter optimization by dividing the dataset into a fixed training set and a fixed validation set.\n",
    "5. Do hyperparameter optimization by crossvalidation\n",
    "6. Do hyperparameter optimization by gridsearch\n",
    "\n",
    "Afterwards, show that you understand, what computations are done by the _scikit-learn_ package you have used by manually computing:\n",
    "\n",
    "7. The entropy for one node\n",
    "8. The information gain for one node\n",
    "\n",
    "**Note:**\n",
    "\n",
    "As this exercise heavily focuses on the usage of the high-level APIs _pandas_ and _scikit-learn_, reading their documentations (just the parts corresponding to the current task) is strongly recommended:\n",
    "\n",
    "- https://scikit-learn.org/stable/documentation.html#\n",
    "- https://pandas.pydata.org/pandas-docs/stable/search.html?q=&check_keywords=yes&area=default"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "## Requirements\n",
    "### Knowledge\n",
    "\n",
    "You should have a basic knowledge of:\n",
    "- Decision Trees\n",
    "- Entropy\n",
    "- Information gain\n",
    "- Crossvalidation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "### Python Modules\n",
    "\n",
    "By [deep.TEACHING](https://www.deep-teaching.org/) convention, all python modules needed to run the notebook are loaded centrally at the beginning. \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "from sklearn.preprocessing import Imputer # in newer versions: from sklearn.impute import SimpleImputer as Imputer\n",
    "from sklearn import tree\n",
    "from sklearn.externals.six import StringIO\n",
    "from sklearn.model_selection import cross_val_score\n",
    "from sklearn.model_selection import GridSearchCV\n",
    "from graphviz import Source"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Teaching Content\n",
    "\n",
    "### Decision Trees for Classification\n",
    "\n",
    "In a decision tree the data is split at each node according to a decision rule. This corresponds to nested _if-then-else_-rules. In the _if_-part of such a rule are decision is made based on a feature of the data record. \n",
    "\n",
    "We will use the scikit learn implementation. For this implementation the features must be binary or have (at least) ordinal characteristic. If a feature is e.g. nominal with many values, it must be converted to a set of binary (one-hot-coded) features.\n",
    "\n",
    "\n",
    "The splitting rules in the scikit learn implementation are binary and are based on a threshold, e.g.\n",
    "  - _if $x_6 <= 2.14$ then_ left subbranch, _else_ right subbranch.         \n",
    "  - binary features must be coded as 0/1, so the rule becomes: if $x_2 <= 0.5$ _then_ left subbranch, _else_ right subbranch. \n",
    "\n",
    "\n",
    "<!--The structure of the tree will be determined by data (see below) and a training procedure.-->\n",
    "\n",
    "In the leaves of the tree the (class) predictions are made. There are two possibilities for such an inference: \n",
    "   - hard assignment: Predict for the data records which end up on a leaf by the majority class of the training data that end up on that leaf.          \n",
    "   - soft assignment: Assign probabilities according to the distribution of the classes in respect to the training data which end up on that leaf.\n",
    "\n",
    "As an example of a decision tree we will learn the following tree from the titanic data set: \n",
    "\n",
    "<img src=\"https://gitlab.com/deep.TEACHING/educational-materials/raw/master/media/klaus/exercise-decision-trees-a-tree.png\" width=\"1024\" alt=\"internet connection needed\">\n",
    "\n",
    "A full explanation of the tree will be given later. Here just look at the decision rules (first line of the inner nodes) and at the last line of the leafs. In each leaf you see an array (values) with counts of the different targets for the train data: [number_died, number_survivors] .\n",
    "\n",
    "### Learning \n",
    "\n",
    "Finding a tree that splits the training data optimal is np-hard. Therefore often a _greedy_-strategy is used:\n",
    "\n",
    "To build up a decision tree the algorithm starts at the root of the tree. The feature and the threshold \n",
    "that splits the training data best (with respect to the classes) are chosen. In an iterative way the whole tree is build up by such splitting rules. \n",
    "\n",
    "There are different criteria for measuring the \"separation (split) quality\". The most important ones are:\n",
    "\n",
    "- Gini Impurity \n",
    "- Information Gain \n",
    "\n",
    "In this tutorial we concentrate on the information gain."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Information Gain as Splitting Criterion\n",
    "\n",
    "The entropy with respect to the target class variable $y$ of a training data set $\\mathcal D$ is defined as:\n",
    "\n",
    "$$\n",
    " H(y, \\mathcal D) = - \\sum_{y \\in \\mathcal Y} p(y|\\mathcal D) \\log_2 p(y|\\mathcal D)\n",
    "$$\n",
    "with the domain of the target values $\\mathcal Y = \\{t_1, t_2,... \\}$.\n",
    "\n",
    "\n",
    "The probabilities are estimated by \n",
    "$$\n",
    "  p(y=t_i, \\mathcal D) = |\\mathcal D^{(y=t_i)}| /|\\mathcal D| \n",
    "$$    \n",
    "\n",
    "\n",
    "with the number of training data $|\\mathcal D|$  and the number of training data $|\\mathcal D^{(y=t_i)}|$ with target label $t_i$: \n",
    "\n",
    "\n",
    "On a node a (binary) split on a feature $x_k$ is made by the split rule $x_k \\leq v$. \n",
    "As result there are two data sets $\\mathcal D_0$ and $\\mathcal D_1$ for the left resp. the right branch.\n",
    "\n",
    "The feature $x_k$ and the split value $v$ are chosen that they maximize the 'reduction of the entropy' measured by the information gain $I$:\n",
    "$$\n",
    "  I(y; x_k) = H(y, \\mathcal D) - H(y|x_k) = H(y, \\mathcal D) - \\sum_{j=0}^1 p_jH(y, \\mathcal D_j) =\n",
    "  H(y, \\mathcal D) + \\sum_{j=0}^1  \\sum_{y \\in \\mathcal Y} \\frac{|\\mathcal D_j|}{|\\mathcal D|} p(y|\\mathcal D_j) \\log_2 p(y|\\mathcal D_j)\n",
    "$$\n",
    "Note that $p_{j=0}$  is the estimated probability that a random data record of $\\mathcal D$ has feature value $x_k \\leq v$ which can be estimated by ${|\\mathcal D_0|}/{|\\mathcal D|}$ (analog for $j=1$).\n",
    "\n",
    "$p(y=t_i|\\mathcal D_0)$ can also be estimated by the fraction of the counts ${|\\mathcal D_0^{(y=t_i)}|}/{|\\mathcal D_0|}$. \n",
    "So the information gain can be computed just with counts:\n",
    "\n",
    "\n",
    "$$\n",
    "  I(y; x_k) = \n",
    "   \\sum_{y \\in \\mathcal Y} \\frac{|\\mathcal D^{(y=t_i)}|}{|\\mathcal D|}  \\log_2 \\frac{|\\mathcal D^{(y=t_i)}|}{|\\mathcal D|} + \\sum_{j=0}^1  \\sum_{y \\in \\mathcal Y} \\frac{|\\mathcal D_j^{(y=t_i)}|}{|\\mathcal D|}  \\log_2 \\frac{|\\mathcal D_j^{(y=t_i)}|}{|\\mathcal D_j|}\n",
    "$$\n",
    "\n",
    "\n",
    "<!--$|\\mathcal D_0|$ respectivly $|\\mathcal D_1|$ is the number of elements in the splitted data sets.-->\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Overfitting\n",
    "\n",
    "Deep decision trees generalize often poorly. The following remedies reduce overfitting: \n",
    "\n",
    "- Limitation of the maximal depth of the tree. \n",
    "- Pruning with an validation set either during training (pre-pruning) or after training (post-pruning).\n",
    "- Dimensionality reduction (reducing the number of features before training)\n",
    "\n",
    "\n",
    "Also often combining decision trees to an ensemble (decision forests) is used against overfitting.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercises"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Loading the Data\n",
    "\n",
    "First we read in the _titanic data set_ with _pandas_\n",
    "\n",
    "**Task:**\n",
    "\n",
    "1. Complete the code to load the dataset as [_pandas_](http://pandas.pydata.org/) [DataFrame](http://pandas.pydata.org/pandas-docs/stable/dsintro.html) object.\n",
    "2. Either download the [_titanic-train.csv_](https://gitlab.com/deep.TEACHING/educational-materials/raw/master/datasets/titanic-train.csv) or alternatively read the url directly into a pandas DataFrame."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Exercise: Load the csv file as pandas DataFrame\n",
    "url = 'https://gitlab.com/deep.TEACHING/educational-materials/raw/master/notebooks/data/titanic-train.csv'\n",
    "train_df = None"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `DataFrame` class implements (and overwrites) a lot of (standard) methods. Some of the are:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Not an exercise, just execute the cell\n",
    "\n",
    "print(train_df.ndim)\n",
    "print(train_df.shape)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Not an exercise, just execute the cell\n",
    "\n",
    "### To view the dataset as pretty table (when using jupyter) \n",
    "train_df"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Not an exercise, just execute the cell\n",
    "\n",
    "### To return the data as numpy array:\n",
    "train_df.values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Not an exercise, just execute the cell\n",
    "\n",
    "### To return just certain features (columns)\n",
    "train_df[['PassengerId', 'Survived', 'Sex']].values"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Data Preprocessing\n",
    "\n",
    "#### Feature Transformation\n",
    "\n",
    "Scikit's learn decision trees can handle only numeric data. So we must convert the nominal `Sex` feature. \n",
    "\n",
    "**Task:**\n",
    "\n",
    "Convert the nominal feature into a binary feature. Convert 'male' to 0 and 'female' to 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true,
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "### Exercise: Convert to binary feature\n",
    "train_df[\"Sex\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert train_df[\"Sex\"].values.sum() == 314"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Feature Selection\n",
    "\n",
    "`Survived` is the target, that we want to predict from the values of the other columns.   \n",
    "But not all of the other columns are helpful for classification. So we choose a feature set by hand and convert the features into a numpy array for scikit learn. \n",
    "\n",
    "**Tasks:**\n",
    "\n",
    "1. Query the values of the feature we have chosen as target feature (class) and save them as numpy array\n",
    "2. Query the values of the features we want to use for training (_\"Fare\", \"Pclass\", \"Sex\", \"Age\", \"SibSp\"_) and save them as numpy array."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "columns = [\"Fare\", \"Pclass\", \"Sex\", \"Age\", \"SibSp\"]\n",
    "y = None # Exercise: Extract target feature \"Survived\" as 1D array\n",
    "x = None # Exercise: Extract the features we want to use for training as 2D array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Missing Values\n",
    "\n",
    "There are missing values (`NaN`) for some examples in the _\"Age\"_ column. Use the scikit learn `Imputer` class to replace them by the mean of the columns."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"-----------First 5 with nan BEFORE----------\")\n",
    "nanMask = np.argwhere(np.isnan(x))\n",
    "print(x[nanMask[0:5,0]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "outputs": [],
   "source": [
    "# TODO as Exercise"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"-----------First 5 with nan AFTER----------\")\n",
    "print(x[nanMask[0:5,0]])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Training and Visualization"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we are ready to define and learn a decision tree by the criterion _'entropy'_ and we restrict the depth of the tree to 3.\n",
    "We use the [scikit learn decison tree module](http://scikit-learn.org/stable/modules/tree.html).\n",
    "\n",
    "**Task:**\n",
    "\n",
    "Define and train the model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "clf = None # Exercise: Define and train the classifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert clf.criterion == \"entropy\"\n",
    "assert clf.max_depth == 3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`clf` is an instance of a trained decision tree classifier.\n",
    "\n",
    "The decision tree can be visualized (after training). For this we must write an graphviz dot-File  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph = Source(tree.export_graphviz(clf, out_file=None\n",
    "   , feature_names=columns, class_names=['died', 'survived'] \n",
    "   , filled = True))\n",
    "graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "According to the decision tree the main criterion (root node) for survival is the sex of the passenger (_if your implementation is correct so far_). In the left subtree are the male passengers (sex = 0), in the right subtree the female (sex=1). \n",
    "\n",
    "In the leafs the class information is given by a `value` array. Here the second value is the number of survivors in the leaves.\n",
    "\n",
    "For example the leftmost leaf represents passengers that are male (sex=0) with fare<=26.2687 and age<=13.5. 13 of such boys survived and 2 of them died.\n",
    "\n",
    "The entropy $- \\sum p_i \\log_2 (p_i)$ is displayed also at each node (splitting criterion).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prediction / Validation\n",
    "\n",
    "To make predictions with scikit learn, we must convert the data in\n",
    "the same way as we did it with the training data. Then we could use the method:    \n",
    "\n",
    "    clf.predict(validation_data)\n",
    "    \n",
    "The depth of the decision tree is a hyperparameter. So the depth should be determined with the help of a \n",
    "validation set or by cross validation.\n",
    "\n",
    "**Task:**\n",
    "\n",
    "1. Manually split your training data in 75% for training and 25% for validation\n",
    "2. Repeat the training process several times for different tree depths (define a new model every time)\n",
    "3. Use `clf.predict(validation_data)` to predict your validation data\n",
    "3. Manually calculate the accuracy for the validation set each time\n",
    " - Accuracy is defined as $\\frac{\\text{number of correct predictions}}{\\text{number of all predictions}}$\n",
    "4. From your results: Which seems to be the best tree depths?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Exercise: Your code below to divide x and y\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Exercise: Your code below to train and predict trees with different depths\n",
    "\n",
    "for depth in range(1,20):\n",
    "    # Your code here\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Crossvalidation\n",
    "\n",
    "Now with a dataset with less than 900 data examples (we have 891), chances to unluckily divide training and validation split seem pretty high. Also \"wasting\" 25% for validation on such a small data set is also not the ideal solution.\n",
    "\n",
    "**Task:**\n",
    "\n",
    "Now do not manually divide your data and do not manually compute the accuracy. Instead use the function `sklearn.model_selection.cross_val_score` to search the best tree depth. Use 10-fold crossvalidation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Exercise: Your code below for crossvalidation\n",
    "\n",
    "for depth in range(1,20):\n",
    "    # Your code here\n",
    "    pass"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Gridsearch\n",
    "\n",
    "This already works pretty well to determine one hyperparameter. But imagine you had several hyperparameters. Since the computation (even with 10 fold crossvalidation) is very fast for decision trees, it is no problem at all to try out every possible combination of hyperparameters. For each hyperparameter you would have to implement another for-loop. Should be no problem. But for convenience, you should know scikit-learn also has a built-in function for that.\n",
    "\n",
    "**Task:**\n",
    "\n",
    "Use `sklearn.model_selection.GridSearchCV` to do a grid search for the best hyperparameters. In addition to `max_depth` parameter between _[1_, _20]_, add the `criterion` as another hyper parameter with the possible values _\"entropy\"_ and _\"gini\"_.\n",
    "\n",
    "Further useful functions after the grid search: `clf.best_score_` and `clf.best_params_`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### Exercise: Your code below for grid search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Splitting Criterion Entropy / Information Gain\n",
    "\n",
    "As you might have noticed, packages like _scikit learn_ can be very comfortable, since they do most of the work for you as long as you provide the data in the right format. Though a good advice is, that you should know what happens inside of such a black box."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task 1:**\n",
    "\n",
    "Recompute the root node entropy. On Pen & paper or with just some lines of code here using basic mathematical operations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Code below"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.testing.assert_almost_equal(entropy_before_split, 0.9607079018756469, decimal=5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task 2:**\n",
    "\n",
    "Compute the information gain of the first split node (root node). Use the shown entropy values and number of data records (samples). Again on Pen & paper or with just some lines of code here using basic mathematical operations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Code below"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.testing.assert_almost_equal(information_gain_split_root_node, 0.2176601066606142, decimal=5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Task 3:**\n",
    "\n",
    "Compute the information gain of the following split table:\n",
    "\n",
    "<table>\n",
    "    <thead>\n",
    "    <tr>\n",
    "        <th>\n",
    "        </th>\n",
    "        <th>\n",
    "            class 0\n",
    "        </th>\n",
    "        <th>\n",
    "            class 1\n",
    "        </th>\n",
    "    </tr>\n",
    "    </thead>\n",
    "    <tr>\n",
    "        <td>\n",
    "            feature $\\le$ v\n",
    "        </td>\n",
    "        <td>\n",
    "            2\n",
    "        </td>\n",
    "        <td>\n",
    "            13\n",
    "        </td>\n",
    "    </tr>\n",
    "    <tr>\n",
    "        <td>\n",
    "            feature $>$ v\n",
    "        </td>\n",
    "        <td>\n",
    "            359\n",
    "        </td>\n",
    "        <td>\n",
    "            41\n",
    "        </td>\n",
    "    </tr>\n",
    "</table>\n",
    " \n",
    "\n",
    "The numbers are the corresponding data records, e.g. there are 13 data records with target class 1 and feature $\\le$ v. \n",
    "\n",
    "Write a python function that computes the information gain.The data is given by a python array:\n",
    "\n",
    "Like always, you are free to write as many helper functions as you want."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "data = np.array([[2.,13.],[359., 41.]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def information_gain(data):\n",
    "    raise NotImplementedError()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "np.testing.assert_almost_equal(information_gain(data), 0.07765787804281093)\n",
    "print(\"Information Gain:\", information_gain(data))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "## Summary and Outlook\n",
    "\n",
    "Machine learning is not exclusively about neural networks - In this notebook you implemented a decision tree, which chains a set of if-then-else decision rules to make a prediction. You employed two popular APIs, scikit-learn and pandas. You also calculated entropy and information gain, measures that are widely applicable in a host of statistics tasks."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Literature\n",
    "\n",
    "<table>\n",
    "    <tr>\n",
    "        <td>\n",
    "            <a name=\"CRI\"></a>[CRI]\n",
    "        </td>\n",
    "        <td>\n",
    "            A. Criminisi, J. Shotton, and E. Konukoglu, Decision Forests for Classification, Regression, Density Estimation, Manifold Learning and Semi- Supervised Learning, no. MSR-TR-2011-114, 28 October 2011. - http://research.microsoft.com/pubs/155552/decisionForests_MSR_TR_2011_114.pdf\n",
    "        </td>\n",
    "    </tr>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "-"
    }
   },
   "source": [
    "## Licenses\n",
    "\n",
    "### Notebook License (CC-BY-SA 4.0)\n",
    "\n",
    "*The following license applies to the complete notebook, including code cells. It does however not apply to any referenced external media (e.g., images).*\n",
    "\n",
    "Exercise: Logistic Regression and Regularization <br/>\n",
    "by Christian Herta, Klaus Strohmenger<br/>\n",
    "is licensed under a [Creative Commons Attribution-ShareAlike 4.0 International License](http://creativecommons.org/licenses/by-sa/4.0/).<br/>\n",
    "Based on a work at https://gitlab.com/deep.TEACHING.\n",
    "\n",
    "\n",
    "### Code License (MIT)\n",
    "\n",
    "*The following license only applies to code cells of the notebook.*\n",
    "\n",
    "Copyright 2018 Christian Herta, Klaus Strohmenger\n",
    "\n",
    "Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the \"Software\"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:\n",
    "\n",
    "The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.\n",
    "\n",
    "THE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "deep_teaching_kernel",
   "language": "python",
   "name": "deep_teaching_kernel"
  },
  "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.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}