decision-trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Classification and Regression Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* * *\n",
    "![Alt text](./images/dt.png \"Decision Tree\")\n",
    "* * *\n",
    "Decision Tree visualization by Tony Chu and Stephanie Yee."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "\n",
    "Classification and regression trees (CART) are a non-parametric [decision tree learning](https://en.wikipedia.org/wiki/Decision_tree_learning) technique that produces either classification or regression trees, depending on whether the dependent variable is categorical or numeric, respectively.  CART is both a generic term to describe tree algorithms and also a specific name for Breiman's original algorithm for constructing classification and regression trees.\n",
    "\n",
    "- **Decision Tree:** A tree-shaped graph or model of decisions used to determine a course of action or show a statistical probability.\n",
    "- **Classification Tree:** A decision tree that performs classification (predicts a categorical response).\n",
    "- **Regression Tree:** A decision tree that performs regression (predicts a numeric response).\n",
    "- **Split Point:** A split point occurs at each node of the tree where a decision is made (e.g. x > 7 vs. x &leq; 7).\n",
    "- **Terminal Node:** A terminal node is a node which has no descendants (child nodes).  Also called a \"leaf node.\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Properties of Trees\n",
    "\n",
    "- Can handle huge datasets.\n",
    "- Can handle *mixed* predictors implicitly -- numeric and categorical.\n",
    "- Easily ignore redundant variables.\n",
    "- Handle missing data elegantly through *surrogate splits*.\n",
    "- Small trees are easy to interpret.\n",
    "- Large trees are hard to interpret.\n",
    "- Prediction performance is often poor (high variance)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tree Algorithms\n",
    "\n",
    "There are a handful of different tree algorithms in addition to Breiman's original CART algorithm.  Namely, [ID3](https://en.wikipedia.org/wiki/ID3_algorithm), [C4.5](https://en.wikipedia.org/wiki/C4.5_algorithm) and [C5.0](https://en.wikipedia.org/wiki/C4.5_algorithm#Improvements_in_C5.0.2FSee5_algorithm), all created by [Ross Quinlan](https://en.wikipedia.org/wiki/Ross_Quinlan).  C5.0 is an improvement over C4.5, however, the C4.5 algorithm is still quite popular since the multi-threaded version of C5.0 is proprietary (although the single threaded is released as GPL). \n",
    "\n",
    "## CART vs C4.5\n",
    "\n",
    "Here are some of the differences between CART and C4.5:\n",
    "\n",
    "- Tests in CART are always binary, but C4.5 allows two or more outcomes.\n",
    "- CART uses the Gini diversity index to rank tests, whereas C4.5 uses information-based criteria.\n",
    "- CART prunes trees using a cost-complexity model whose parameters are estimated by\n",
    "cross-validation; C4.5 uses a single-pass algorithm derived from binomial confidence\n",
    "limits.\n",
    "- With respect to missing data, CART looks for surrogate tests that approximate the outcomes when the tested attribute has an unknown value, but C4.5 apportions the case probabilistically among the outcomes. \n",
    "\n",
    "\n",
    "Decision trees are formed by a collection of rules based on variables in the modeling data set:\n",
    "\n",
    "1. Rules based on variables' values are selected to get the best split to differentiate observations based on the dependent variable.\n",
    "2. Once a rule is selected and splits a node into two, the same process is applied to each \"child\" node (i.e. it is a recursive procedure).\n",
    "3. Splitting stops when CART detects no further gain can be made, or some pre-set stopping rules are met. (Alternatively, the data are split as much as possible and then the tree is later pruned.)\n",
    "\n",
    "Each branch of the tree ends in a terminal node. Each observation falls into one and exactly one terminal node, and each terminal node is uniquely defined by a set of rules."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Splitting Criterion & Best Split\n",
    "\n",
    "The original CART algorithm uses the Gini Impurity, whereas ID3, C4.5 and C5.0 use Entropy or Information Gain (related to Entropy).\n",
    "\n",
    "### Gini Impurity\n",
    "\n",
    "Used by the CART algorithm, [Gini Impurity](https://en.wikipedia.org/wiki/Decision_tree_learning#Gini_impurity) is a measure of how often a randomly chosen element from the set would be incorrectly labeled if it was randomly labeled according to the distribution of labels in the subset. Gini impurity can be computed by summing the probability $f_i$ of each item being chosen times the probability $1 − f_i$ of a mistake in categorizing that item. It reaches its minimum (zero) when all cases in the node fall into a single target category.\n",
    "\n",
    "To compute Gini impurity for a set of m items, suppose $i ∈ {1, 2, ..., m}$, and let $f_i$ be the fraction of items labeled with value $i$ in the set.\n",
    "\n",
    "$$ I_{G}(f)=\\sum _{i=1}^{m}f_{i}(1-f_{i})=\\sum _{i=1}^{m}(f_{i}-{f_{i}}^{2})=\\sum _{i=1}^{m}f_{i}-\\sum _{i=1}^{m}{f_{i}}^{2}=1-\\sum _{i=1}^{m}{f_{i}}^{2}=\\sum _{i\\neq k}f_{i}f_{k}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Entropy\n",
    "\n",
    "[Entropy](https://en.wikipedia.org/wiki/ID3_algorithm#Entropy), $H(S)$, is a measure of the amount of uncertainty in the (data) set $S$ (i.e. entropy characterizes the (data) set $S$).\n",
    "\n",
    "$$ H(S)=-\\sum _{{x\\in X}}p(x)\\log _{{2}}p(x) $$\n",
    "\n",
    "Where,\n",
    "- $S$ is the current (data) set for which entropy is being calculated (changes every iteration of the ID3 algorithm)\n",
    "- $X$ is set of classes in $S$\n",
    "- $p(x)$ is the ratio of the number of elements in class $x$ to the number of elements in set $S$\n",
    "\n",
    "When $H(S)=0$, the set $S$ is perfectly classified (i.e. all elements in $S$ are of the same class).\n",
    "\n",
    "In ID3, entropy is calculated for each remaining attribute. The attribute with the smallest entropy is used to split the set $S$ on this iteration. The higher the entropy, the higher the potential to improve the classification here."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Information gain\n",
    "\n",
    "Information gain $IG(A)$ is the measure of the difference in entropy from before to after the set $S$ is split on an attribute $A$: in other words, how much uncertainty in $S$ was reduced after splitting set $S$ on attribute $A$.\n",
    "\n",
    "$$ IG(A,S)=H(S)-\\sum _{{t\\in T}}p(t)H(t)$$\n",
    "\n",
    "Where,\n",
    "- $H(S)$ is the entropy of set $S$\n",
    "- $T$ is the set of subsets created from splitting set $S$ by attribute $A$ such that $S=\\bigcup _{{t\\in T}}t$\n",
    "- $p(t)$ is the ratio of the number of elements in $t$ to the number of elements in set $S$\n",
    "- $H(t)$ is the entropy of subset $t$\n",
    "\n",
    "In ID3, information gain can be calculated (instead of entropy) for each remaining attribute. The attribute with the *largest* information gain is used to split the set $S$ on this iteration."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Decision Boundary\n",
    "\n",
    "This is an example of a decision boundary in two dimensions of a (binary) classification tree.  The black circle is the Bayes Optimal decision boundary and the blue square-ish boundary is learned by the classification tree.\n",
    "\n",
    "![Alt text](./images/boundary_dt.png \"Decision Tree Boundary\")\n",
    "Source: Elements of Statistical Learning"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Missing Data\n",
    "\n",
    "CART is an algorithm that deals effectively with missing values through *surrogate splits*.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Visualizing Decision Trees\n",
    "\n",
    "![Alt text](./images/r2d3_visual_ml.png \"R2D3 Visual ML\")\n",
    "\n",
    "[Tony Chu](https://twitter.com/tonyhschu) and [Stephanie Yee](https://twitter.com/stephaniejyee) designed an award-winning visualization of how decision trees work called \"A Visual Introduction to Machine Learning.\"  Their interactive D3 visualization is available [here](http://www.r2d3.us/visual-intro-to-machine-learning-part-1/)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# CART Software in R\n",
    "\n",
    "Since it's more common in machine learning to use trees in an ensemble, we'll skip the code tutorial for CART in R. For reference, trees can be grown using the [rpart](https://cran.r-project.org/web/packages/rpart/index.html) package, among others."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "R",
   "language": "R",
   "name": "ir"
  },
  "language_info": {
   "codemirror_mode": "r",
   "file_extension": ".r",
   "mimetype": "text/x-r-source",
   "name": "R",
   "pygments_lexer": "r",
   "version": "3.3.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}