14-Classification-I-Decision-Trees.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "hide_input": true,
    "slideshow": {
     "slide_type": "skip"
    },
    "tags": [
     "remove-cell"
    ]
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "%config InlineBackend.figure_format='retina'\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "from IPython.display import Image, display_html, display, Math, HTML;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Decision Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Today we start our study of __classification__ methods.\n",
    "\n",
    "Recall that in a classification problem, we have data tuples $(\\mathbf{x}, y)$ in which the $\\mathbf{x}$ are the features, and the $y$ values are __categorical__ data.  \n",
    "\n",
    "We typically call the $y$ values \"labels\" or \"classes.\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some examples of classification tasks:\n",
    "   * Predicting tumor cells as malignant or benign\n",
    "   * Classifying credit card transactions as legitimate or fraudulent\n",
    "   * Classifying secondary structures of a protein as alpha-helix, beta-sheet, or other\n",
    "   * Categorizing news stories as finance, weather, entertainment, sports, etc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first classification method we will consider is called the __decision tree.__\n",
    "\n",
    "It is a __very__ popular method, and has some nice properties as we will see."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Decision Trees in Action"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "source": [
    "```{note}\n",
    "This section and a number of following sections are based on slides by Tan, Steinbach, and Kumar (2004)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We will start by describing how a decision tree works.\n",
    "\n",
    "We are assuming a decision tree has been built to solve the following classification problem:\n",
    "\n",
    "<center>\n",
    "<font color = \"blue\">Given an individual's Tax Refund Status, Marital Status, and Taxable Income, predict whether they will repay a loan.</font>\n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": [
     "hide-input"
    ]
   },
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/L14-DT-Example-1.png\" alt=\"Figure\" width=\"800px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "We then step through the tree, making a decision at each node that takes us to another node in the tree.\n",
    "\n",
    "Each decision examines a single feature in the item being classified."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": [
     "hide-input"
    ]
   },
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/L14-DT-Example-2.png\" alt=\"Figure\" width=\"800px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": [
     "hide-input"
    ]
   },
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/L14-DT-Example-3.png\" alt=\"Figure\" width=\"800px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": [
     "hide-input"
    ]
   },
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/L14-DT-Example-4.png\" alt=\"Figure\" width=\"800px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "tags": [
     "hide-input"
    ]
   },
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/L14-DT-Example-5.png\" alt=\"Figure\" width=\"800px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/L14-DT-Example-6.png\" alt=\"Figure\" width=\"800px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We conclude that this record is classified as \"Not Repay\" is \"No\"."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Note also that decision trees can be used to predict numeric values, so they are used for regression as well.\n",
    "\n",
    "The general term \"Classification and Regression Tree\" (CART) is sometimes used -- although this term also refers to a specific decision tree learning algorithm."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Learning a Decision Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "hide_input": false,
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/L14-DT-Overview.png\" alt=\"Figure\" width=\"800px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We've discussed how to apply a decision tree to data (lower portion of this figure).\n",
    "\n",
    "But how does one train a decision tree?   What algorithm can we use?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "A number of algorithms have been proposed for building decision trees:\n",
    "\n",
    "* Hunt's algorithm (one of the earliest)\n",
    "* CART\n",
    "* ID3, C4.5\n",
    "* SLIQ, SPRINT\n",
    "* etc"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Hunt's Algorithm"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We build the tree node by node, starting from the root.\n",
    "\n",
    "As we build the tree, we divide the training data up."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "<div style = \"float: left; width: 55%;\">\n",
    "\n",
    "Let $D_t$ be the set of training records that reach node $t$.\n",
    "    \n",
    " * If $D_t$ contains records that all belong to a single class $y_t$, then $t$ is a leaf node labeled as $y_t$.\n",
    " * If $D_t$ is an empty set, then $t$ is a leaf node labeled by the default class $y_d$.\n",
    " * If $D_t$ contains records that belong to more than one class, use an attribute to split $D_t$ into smaller subsets, and assign that splitting-rule to node $t$.\n",
    "    \n",
    "Recursively apply the above procedure until a stopping criterion is met.\n",
    "</div>\n",
    "    \n",
    "<img src=\"figs/L14-DT-Data-Example.png\" alt=\"Figure\" width=\"40%\" float = \"right\">\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "So as Hunt's algorithm progresses, records are divided up and assigned to leaf nodes.   The most challenging step in Hunt's algorithm is deciding which leaf node to split next, and how to specify the split.\n",
    "\n",
    "In general, we use a greedy strategy.  We will split a set of records based on an attribute test that optimizes some criterion.\n",
    "\n",
    "We choose the set to split that provides the largest improvement in our criterion."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Once we have chosen the set to split, the remaining questions are:\n",
    "    \n",
    "* Determining how to split the record set\n",
    "    * How should we specify the attribute test condition?\n",
    "    * How should we determine the best split for a set based on a given attribute?\n",
    "* Determining when to stop splitting."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Specifying the Test Condition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "How we specify a test condition depends on the attribute type:\n",
    "* Nominal (Categorical)\n",
    "* Ordinal (eg, Small, Medium, Large)\n",
    "* Continuous"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "And depends on the number of ways to split - __multi-way__ or __binary__:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "For a __Nominal__ attribute:\n",
    "\n",
    "* In a __Multi-way split__ we can use as many partitions as there are distinct values of the attribute:\n",
    "    \n",
    "<center>\n",
    "    \n",
    "<img src=\"figs/L14-split-1.png\" alt=\"Figure\" width=\"300px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* In a __Binary split__ we divide the values into two groups.  In this case, we need to find an optimal partitioning of values into groups.\n",
    "\n",
    "<center>\n",
    "    \n",
    "<img src=\"figs/L14-split-2.png\" alt=\"Figure\" width=\"600px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "An __Ordinal__ attribute is similar to a Nominal attribute, except that since attributes have an ordering, we can specify the test in terms of a threshold.  This simplifies the search for a good paritition.\n",
    "\n",
    "\n",
    "<center>\n",
    "    \n",
    "<img src=\"figs/L14-split-3.png\" alt=\"Figure\" width=\"600px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "A __Continuous__ attribute can be handled two ways:\n",
    "    \n",
    "* It can be __discretized__ to form an ordinal categorical attribute\n",
    "\n",
    "<center>\n",
    "    \n",
    "<img src=\"figs/L14-split-4.png\" alt=\"Figure\" width=\"400px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "* Or it can be partitioned via a threshold to form for a binary split.\n",
    "\n",
    "<center>\n",
    "    \n",
    "<img src=\"figs/L14-split-5.png\" alt=\"Figure\" width=\"200px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Note that finding good partitions for nominal attributes can be expensive, possibly involving combinatorial searching of groupings.  \n",
    "\n",
    "However for ordinal or continuous attributes, sweeping through a range of threshold values can be more efficient."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Determining the Best Split"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Our algorithmic strategy is to split record sets so as to improve classification accuracy on the training data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "When is classification accuracy maximized?   When each leaf node contains records that all have the same label."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Consider this case:\n",
    "    \n",
    "At some node in the tree, before splitting that node's records, we have \n",
    "* 10 records from class 0, and\n",
    "* 10 records from class 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "There are three attributes we can split on.   Which split is best?\n",
    "\n",
    "<center>\n",
    "    \n",
    "<img src=\"figs/L14-split-6.png\" alt=\"Figure\" width=\"700px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "The \"Car Type\" attribute yields more homogeneous splits.\n",
    "\n",
    "Using the \"Student ID\" attribute yields perfect accuracy on the training data."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "... but what would it do on the test data?\n",
    "\n",
    "... using the \"Student ID\" attribute would lead to __overfitting__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We'll talk about how to avoid overfitting shortly.\n",
    "\n",
    "For now, let's just focus on maximizing the homogeneity of splits."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We need a measure of homogeneity:\n",
    "    \n",
    "<center>\n",
    "    \n",
    "<img src=\"figs/L14-split-7.png\" alt=\"Figure\" width=\"700px\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "A number of measures have been proposed:\n",
    "* GINI Index\n",
    "* Entropy\n",
    "* Misclassification Error\n",
    "\n",
    "We will review GINI, as it is a typical measure. \n",
    "\n",
    "It's used, for example, in CART, SLIQ, and SPRINT."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Computing GINI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The GINI coefficient measures the degree of \"balance\" in a distribution.\n",
    "\n",
    "As nodes are split in building the tree, we will be decreasing the GINI score."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For a given node $t$, we will use $p(j\\,|\\,t)$ to denote the frequency of class $j$ at node $t$.\n",
    "\n",
    "Then:\n",
    "\n",
    "$$ \\text{GINI}(t) = 1 - \\sum_j [p(j\\,|\\,t)]^2 $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<center>\n",
    "    \n",
    "<img src=\"figs/L14-GINI-1.png\" alt=\"Figure\" width=\"80%\">\n",
    "    \n",
    "</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Now, how do we compute the improvement in GINI when a node is split?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Remember that we would like to create large, homogeneous nodes.\n",
    "\n",
    "So we will weight each node's GINI score by the number of records it contains. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "So the improvement in GINI score when splitting a node $t$ with $n$ records will be computed as:\n",
    "    \n",
    "$$ \\text{GINI}_{\\text{new}} = \\sum_i \\frac{n_i}{n}\\; \\text{GINI}(i) $$\n",
    "\n",
    "where new node $i$ contains $n_i$ records;\n",
    "\n",
    "and the improvement in GINI score will be defined as\n",
    "\n",
    "$$  \\text{GINI}(t) - \\text{GINI}_{\\text{new}} $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "__GINI for Binary Partitions__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here is an example of computing the new GINI score for a partition:\n",
    "    \n",
    "<center>\n",
    "    \n",
    "<img src=\"figs/L14-GINI-2.png\" alt=\"Figure\" width=\"80%\">\n",
    "    \n",
    "</center>   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "__GINI for Nominal Attributes__\n",
    "\n",
    "* For each distinct value, gather counts for each class in the dataset\n",
    "* Use the count matrix to evaluate groupings\n",
    "\n",
    "<center>\n",
    "    \n",
    "<img src=\"figs/L14-GINI-3.png\" alt=\"Figure\" width=\"80%\">\n",
    "    \n",
    "</center>  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "__GINI for Continuous Attributes__\n",
    "\n",
    "To find the best threshold efficiently:\n",
    "* Sort the attribute on values\n",
    "* Linearly scan the values, \n",
    "    * each time updating a count matrix and\n",
    "    * computing the new GINI score\n",
    "* Choose the split position with the smallest GINI index\n",
    "\n",
    "<center>\n",
    "    \n",
    "<img src=\"figs/L14-GINI-4.png\" alt=\"Figure\" width=\"80%\">\n",
    "    \n",
    "</center>  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## When to Stop Splitting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "We now see how the decision tree is built, node by node, by splitting nodes in a way that steadily improves the overall GINI score."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "Clearly, we could keep on splitting nodes until every leaf node contains only unique training records.\n",
    "\n",
    "For example, each leaf node could contain just a single training record - a fully-grown tree.\n",
    "\n",
    "This would certainly be overfitting! \n",
    "\n",
    "We would have as many leaf nodes (parameters) as training data records.\n",
    "\n",
    "And we would not expect the decision tree to generalize well."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "source": [
    "There are two strategies that can be used to control the complexity of a decision tree:\n",
    "\n",
    "1. Early-stopping: stop the algorithm before the tree becomes fully-grown \n",
    "2. Post-pruning: grow decision tree fully, then prune nodes from leaves upward"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "__Early Stopping__\n",
    "\n",
    "Do not expand the current node, even though it still has multiple records.\n",
    "\n",
    "Default stopping conditions include:\n",
    "* Stop if all records belong to the same class\n",
    "* Stop if all the records have the same attributes\n",
    "\n",
    "More restrictive stopping conditions include:\n",
    "* Stop if number of records is less than a specified value\n",
    "* Stop if expanding the current node does not improve homogeneity (eg, GINI score)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Post-pruning__\n",
    "\n",
    "Assumes that we can assess generalization error \n",
    "* For example, using held-out data\n",
    "\n",
    "Then:\n",
    "* Grow decision tree to its entirety\n",
    "* Trim the nodes of the tree in bottom-up fashion\n",
    "* If generalization error improves after trimming, replace sub-tree by a leaf node\n",
    "* "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Advantages of Decision Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Decision Trees are a very popular technique.  \n",
    "\n",
    "They have a number of advantages:\n",
    "* They are relatively inexpensive to construct\n",
    "* They are extremely fast at classifying unknown data\n",
    "* Their accuracy can be quite good in many cases\n",
    "* And oftentimes they are __interpretable__\n",
    "\n",
    "__Interpretability__ ---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}