{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Supervised Learning: Decision Trees"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"For methods like support vector machines to work well, it requires identifying an appropriate kernel function, which is not always straightforward or intuitive.\n",
"\n",
"An alternative to this is to perform statistical learning more directly, say, as a combination of the predictors (features). An **adaptive basis-function model** (ABM) is one example of this.\n",
"\n",
"$$f(x) = w_0 + \\sum_{j=1}^k w_j \\phi_j(\\mathbf{x})$$\n",
"\n",
"here, $\\phi_j$ is a *basis function*, which is typically parametric:\n",
"\n",
"$$\\phi_j(\\mathbf{x}) = \\phi_j(\\mathbf{x}|\\alpha_j)$$\n",
"\n",
"The parameter set for this model is thus $\\theta = \\{\\mathbf{w} = w_0,\\ldots,w_k; \\mathbf{\\alpha} = \\alpha_1, \\ldots, \\alpha_k\\}$. This model is *not* linear in the parameters.\n",
"\n",
"\n",
"**Decision trees** use an ABM to *recursively partition* the space of predictor variables into a piecewise-constant response surface. We can consider each component $j=1,\\ldots,k$ to be a region in the response surface, and $w_j$ the expected response in that region.\n",
"\n",
"$$f(x) = \\sum_{j=1}^k w_j I(\\mathbf{x} \\in R_j)$$\n",
"\n",
"Each paramter $\\alpha_j$ encodes both (1) a variable used for splitting and (2) the corresponding threshold value. Specifically, the basis functions define the regions, and the weights encode the response value in each region.\n",
"\n",
"This particular formulation implies a regression-type model, but we can generalize this to classification by storing the *distribution over classes* in each leaf, instead of the mean response."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"To get a sense of how decision trees work, consider the diabetes dataset that we have seen previously. In the plot below, the response variable (`target`, an index of disease progression) is color-coded as a function of two variables, metabolic rate (`bmi`) and a blood serum measurement (`ltg`)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"%matplotlib inline\n",
"import matplotlib.pyplot as plt\n",
"import numpy as np\n",
"import pandas as pd\n",
"import seaborn as sns\n",
"sns.set()\n",
"from sklearn.datasets import load_diabetes\n",
"\n",
"# Predictors: \"age\" \"sex\" \"bmi\" \"map\" \"tc\" \"ldl\" \"hdl\" \"tch\" \"ltg\" \"glu\"\n",
"diabetes = load_diabetes()\n",
"y = diabetes['target']\n",
"bmi, ltg = diabetes['data'][:,[2,8]].T\n",
"\n",
"plt.scatter(ltg, bmi, c=y, cmap=\"Blues\")\n",
"plt.colorbar()\n",
"plt.xlabel('ltg'); plt.ylabel('bmi');"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"One approach to building a predictive model is to subdivide the variable space into regions, by sequentially subdividing each variable. For example, if we split `ltg` at a threshold value of -0.01, it does a reasonable job of isolating the large values in one of the resulting subspaces."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"ltg_split = -0.01\n",
"plt.scatter(ltg, bmi, c=y, cmap=\"Blues\")\n",
"plt.vlines(ltg_split, *plt.gca().get_ylim(), linestyles='dashed')\n",
"plt.colorbar()\n",
"plt.xlabel('ltg'); plt.ylabel('bmi');"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"However, that region still contains a fair number of low (blue) values, so we can similarly bisect the region using a `bmi` value of -0.03 as a threshold value:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"bmi_split = -0.03\n",
"plt.scatter(ltg, bmi, c=y, cmap=\"Blues\")\n",
"plt.vlines(ltg_split, *plt.gca().get_ylim(), linestyles='dashed')\n",
"plt.hlines(bmi_split, ltg_split, plt.gca().get_xlim()[1], linestyles='dashed')\n",
"plt.colorbar()\n",
"plt.xlabel('ltg'); plt.ylabel('bmi');"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can use this partition to create a piecewise-constant function, which returns the average value of the observations in each region defined by the threshold values. We could then use this rudimentary function as a predictive model."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"np.mean(y[(bmi>bmi_split) & (ltg>ltg_split)])"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"np.mean(y[(bmi<=bmi_split) & (ltg>ltg_split)])"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"np.mean(y[ltg9.5)=0.17$, so we predict death ($y=0$). \n",
"- If, on the other hand, the passenger is younger than 9.5 years, we then check if the number of siblings and spouses on board was higher than 2.5; if \"yes\", then the probability of survival $p(y=1, x_1=M, x_2>9.5, x_3>2.5)=0.05$, so we predict death, otherwise we predict survival with $p(y=1, x_1=M, x_2>9.5 , x_3 \\lt 2.5)=0.89$. \n",
"\n",
"Hence, these probabilities are just the empirical fraction of positive examples that satisfy each conjunction of feature values, which defines a path from the root to a leaf.\n",
"\n",
"![titanic tree](http://upload.wikimedia.org/wikipedia/commons/f/f3/CART_tree_titanic_survivors.png)\n",
"\n",
"There is no way to feasibly evaluate all possible partitions. Instead, the strategy is to use a top-down, **greedy** approach that is optimal (according to a particular cost function) for the current split only. By \"greedy\", we mean that at each step it chooses the most advantageous binary partition, not taking into account the impact of the choice on the quality of subsequent partitions.\n",
"\n",
"$$(j^*, t^*) = \\text{argmin}_{j,t} C(\\{\\mathbf{x}_i,y_i: x_{ij} \\le t\\}) + C(\\{\\mathbf{x}_i,y_i: x_{ij} \\gt t\\})$$\n",
"\n",
"where $C$ is a cost function, $j$ and $t$ are a variable index and cutpoint, respectively. We will restrict consideration to **binary partitions**.\n",
"\n",
"## Classification Trees\n",
"\n",
"In addition to regression trees, we can also use decision trees on categorical outcomes, and these are called classification trees. The primary difference in implementation is that residual sums of squares is no longer an appropriate splitting criterion."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Entropy\n",
"\n",
"An alternative splitting criterion for decision tree learning algorithms is *information gain*. It measures how well a particular attribute distinguishes among different target classifications. Information gain is measured in terms of the expected reduction in the entropy or impurity of the data. The entropy of a set of probabilities is:\n",
"\n",
"$$H(p) = -\\sum_i p_i log_2(p_i)$$\n",
"\n",
"If we have a set of binary responses from some variable, all of which are positive/true/1, then knowing the values of the variable does not hold any predictive value for us, since all the outcomes are positive. Hence, the entropy is zero:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"\n",
"entropy = lambda p: -np.sum(p * np.log2(p)) if not 0 in p else 0"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"entropy([.4,.6])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"However, if the variable splits responses into equal numbers of positive and negative values, then entropy is maximized, and we wish to know about the feature:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"entropy([0.5, 0.5])"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"pvals = np.linspace(0, 1) \n",
"plt.plot(pvals, [entropy([p,1-p]) for p in pvals])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The entropy calculation tells us how much additional information we would obtain with knowledge of the variable.\n",
"\n",
"So, if we have a set of candidate covariates from which to choose as a node in a decision tree, we should choose the one that gives us the most information about the response variable (*i.e.* the one with the highest entropy).\n",
"\n",
"### Misclassification Rate\n",
"\n",
"Alternatively, we can use the misclassification rate:\n",
"\n",
"$$C(j,t) = \\frac{1}{n_{jt}} \\sum_{y_i: x_{ij} \\gt t} I(y_i \\ne \\hat{y})$$\n",
"\n",
"where $\\hat{y}$ is the most probable class label and $n_{ij}$ is the number of observations in the data subset obtained from splitting via $j,t$.\n",
"\n",
"### Gini index\n",
"\n",
"The Gini index is simply the expected error rate:\n",
"\n",
"$$C(j,t) = \\sum_{k=1}^K \\hat{\\pi}_{jt}[k] (1 - \\hat{\\pi}_{jt}[k]) = 1 - \\sum_{k=1}^K \\hat{\\pi}_{jt}[k]^2$$\n",
"\n",
"where $\\hat{\\pi}_{jt}[k]$ is the probability of an observation being correctly classified as class $k$ for the data subset obtained from splitting via $j,t$ (hence, $(1 - \\hat{\\pi}_{jt}[k])$ is the misclassification probability)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"gini = lambda p: 1. - (np.array(p)**2).sum()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"pvals = np.linspace(0, 1) \n",
"plt.plot(pvals, [entropy([p,1-p])/2. for p in pvals], label='Entropy')\n",
"plt.plot(pvals, [gini([p,1-p]) for p in pvals], label='Gini')\n",
"plt.legend()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## ID3\n",
"\n",
"A given cost function can be used to construct a decision tree via one of several algorithms. The Iterative Dichotomiser 3 (ID3) is one such algorithm, which uses entropy, and a related concept, *information gain*, to choose features and partitions at each classification step in the tree.\n",
"\n",
"Information gain is the difference between the current entropy of a system and the entropy measured after a feature is chosen. If $S$ is a set of examples and $X$ is a possible feature on which to partition the examples, then:\n",
"\n",
"$$G(S,X) = \\text{Entropy}(S) - \\sum_{x \\in X} \\frac{\\#(S_x)}{\\#(S)} \\text{Entropy}(S_x)$$\n",
"\n",
"where $\\#$ is the count function and $x$ is a particular value of $X$.\n",
"\n",
"Let's say $S$ is a set of survival events, $S = \\{s_1=survived, s_2=died, s_3=died, s_4=died\\}$ and a particular variable $X$ can have values $\\{x_1, x_2, x_3\\}$. To perform a sample calculation of information gain, we will say that:\n",
"\n",
"* $X(s_1) = x_2$\n",
"* $X(s_2) = x_2$\n",
"* $X(s_3) = x_3$\n",
"* $X(s_4) = x_1$"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"pd.DataFrame({'S': [1, 0, 0, 0], 'X': ['x2', 'x2', 'x3', 'x1']})"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The current entropy of this state is:\n",
"\n",
"$$\\begin{align}\n",
"\\text{Entropy}(S) &= -p^{(+)} \\log_2(p^{(+)}) - p^{(-)} \\log_2(p^{(-)}) \\\\\n",
"&= -0.25 \\log_2(0.25) - 0.75 \\log_2(0.75) \\\\\n",
"&= 0.5 + 0.311 = 0.811\n",
"\\end{align}$$\n",
"\n",
"Now, we need to compute the information after selecting variable $X$, which is the sum of three terms:\n",
"\n",
"$$\\begin{align}\n",
"\\frac{\\#(S_{x1})}{\\#(S)} \\text{Entropy}(S) &= 0.25 (-0 \\log_2(0) - 1 \\log_2(1)) = 0\\\\\n",
"\\frac{\\#(S_{x2})}{\\#(S)} \\text{Entropy}(S) &= 0.5 (-0.5 \\log_2(0.5) - 0.5 \\log_2(0.5) = 0.5\\\\\n",
"\\frac{\\#(S_{x3})}{\\#(S)} \\text{Entropy}(S) &= 0.25 (-0 \\log_2(0) - 1 \\log_2 1) = 0\\\\\n",
"\\end{align}$$\n",
"\n",
"Therefore, the information gain is:\n",
"\n",
"$$G(S,X) = 0.811 - (0 + 0.5 + 0) = 0.311$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This algorithm is implemented in the following function:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"\n",
"def info_gain(X, y, feature):\n",
" # Calculates the information gain based on entropy\n",
" \n",
" gain = 0\n",
" n = len(X)\n",
"\n",
" # List the values that feature can take\n",
" values = list(set(X[feature]))\n",
"\n",
" feature_counts = np.zeros(len(values))\n",
" E = np.zeros(len(values))\n",
" ivalue = 0\n",
" \n",
" # Find where those values appear in X[feature] and the corresponding class\n",
" for value in values:\n",
" \n",
" new_y = [y[i] for i,d in enumerate(X[feature].values) if d==value]\n",
" feature_counts[ivalue] += len(new_y)\n",
"\n",
" # Get the values in newClasses\n",
" class_values = list(set(new_y))\n",
"\n",
" class_counts = np.zeros(len(class_values))\n",
" iclass = 0\n",
" for v in class_values:\n",
" for c in new_y:\n",
" if c == v:\n",
" class_counts[iclass] += 1 \n",
" iclass += 1\n",
" \n",
" nc = float(np.sum(class_counts))\n",
" new_entropy = entropy([class_counts[c] / nc for c in range(len(class_values))])\n",
" E[ivalue] += new_entropy\n",
"\n",
" # Computes both the Gini gain and the entropy\n",
" gain += float(feature_counts[ivalue])/n * E[ivalue]\n",
" ivalue += 1\n",
" \n",
" return gain "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Consider a few variables from the titanic database:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"titanic = pd.read_excel(\"../data/titanic.xls\", \"titanic\")\n",
"titanic.head(3)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here, we have selected pasenger class (`pclass`), sex, port of embarcation (`embarked`), and a derived variable called `adult`. We can calculate the information gain for each of these."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"X = titanic.copy()\n",
"y = X.pop('survived')\n",
"X['adult'] = titanic.age<17\n",
"\n",
"info_gain(X, y, 'pclass')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"info_gain(X, y, 'sex')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"info_gain(X, y, 'embarked')"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"info_gain(X, y, 'adult')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Hence, the ID3 algorithm computes the information gain for each variable, selecting the one with the highest value (in this case, `adult`). In this way, it searches the \"tree space\" according to a greedy strategy.\n",
"\n",
"A tree can be constructed by recursively selecting the feature from the current dataset with the largest information gain, then removing it from the datset. Recursion stops when there are either no variables remaining, or there is only one class left in the subset (*e.g.* all `True` or all `False`).\n",
"\n",
"The ID3 algorithm is as follows:\n",
"\n",
"> * if all response data have the same class:\n",
"> \n",
"> - return leaf with data label\n",
"> \n",
"> * else if no features:\n",
"> \n",
"> - return leaf with most common label\n",
"> \n",
"> * else:\n",
"> \n",
"> - choose variable $X'$ that maximizes information gain to be a tree node\n",
"> - add branch from node for each value of $X'$\n",
"> - for each branch of node:\n",
"> \n",
"> * calculate $S_{x}$ by removing $X'$ from $S$\n",
"> * set $S=S_{x}$ and call algorithm again \n",
"\n",
"The greedy approach of maximizing information gain at each step tends to bias solutions towards smaller trees."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Decision Trees in `scikit-learn`\n",
"\n",
"Classification trees, either binary or multi-class, are implemented in `scikit-learn` in the `DecisionTreeClassifier` class. Where trees are binary, it expects the response variable to be coded as `[-1,1]` for negative and positive outcomes.\n",
"\n",
"Let's build a decision tree on the wine dataset."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"wine = pd.read_table(\"../data/wine.dat\", sep='\\s+')\n",
"\n",
"attributes = ['Alcohol',\n",
" 'Malic acid',\n",
" 'Ash',\n",
" 'Alcalinity of ash',\n",
" 'Magnesium',\n",
" 'Total phenols',\n",
" 'Flavanoids',\n",
" 'Nonflavanoid phenols',\n",
" 'Proanthocyanins',\n",
" 'Color intensity',\n",
" 'Hue',\n",
" 'OD280/OD315 of diluted wines',\n",
" 'Proline']\n",
"\n",
"grape = wine.pop('region')\n",
"y = grape\n",
"wine.columns = attributes\n",
"X = wine"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from sklearn import tree\n",
"from sklearn import model_selection\n",
"\n",
"X_train, X_test, y_train, y_test = model_selection.train_test_split(\n",
" X, y, test_size=0.4, random_state=0)\n",
"\n",
"clf = tree.DecisionTreeClassifier(criterion='entropy',\n",
" max_features=\"auto\",\n",
" min_samples_leaf=10)\n",
"clf.fit(X_train, y_train)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"If you have [GraphViz](http://www.graphviz.org) and `pydot` installed, you can draw the resulting tree:"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"import graphviz\n",
"gv_data = tree.export_graphviz(clf, out_file=None, \n",
" feature_names=attributes, \n",
" filled=True, rounded=True, \n",
" special_characters=True) \n",
"\n",
"graphviz.Source(gv_data)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"preds = clf.predict(X_test)\n",
"pd.crosstab(y_test, preds, rownames=['actual'], \n",
" colnames=['prediction'])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Pruning\n",
"\n",
"Despite the **inductive bias** associated with trees that tend to make them small, the ID3 algorithm continues choosing nodes and branches until either it runs out of variables, or all outputs are of the same class. This can clearly lead to overfit trees.\n",
"\n",
"To prevent overfitting, we can **stop growing** the tree if the information gain (or reduction in error, etc.) is not sufficient to justify the extra complexity of adding another node. However, this simple rule is not optimal, because an uninformative subtree can lead to informative ones later on. \n",
"\n",
"The standard approach is therefore to grow a full tree, and then to **prune** it. The easiest approach is to remove branches that give the least increase in the error (information gain). To determine how far back to prune, we can evaluate the cross-validated error on each candidate pruning, and then pick the tree whose CV error is within 1 standard error of the minimum.\n",
"\n",
"Analogous to the lasso or ridge regression, we can **penalize** the number of terminal nodes in a tree:\n",
"\n",
"$$\\sum_{m=1}^{|T|} \\sum_{x_i \\in R_m} (y_i - \\hat{y}_{R_j})^2 + \\alpha |T|$$\n",
"\n",
"where $|T|$ is the number of terminal nodes in tree T.\n",
"\n",
"### Pruned Decision Tree Algorithm\n",
"\n",
"1. Use recursive binary splitting to grow a large tree, such that each terminal node has fewer than some minimum number of observations.\n",
"2. Apply pruning to obtain a sequence of best subtrees, as a function of $\\alpha$.\n",
"3. Use k-fold cross-validation to choose $\\alpha$. Average results and pick $\\alpha$ to minimize the average error.\n",
"4. Return subtree from (2) that corresponds to chosen $\\alpha$.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Averaging Trees\n",
"\n",
"Decision trees have several advantages: \n",
"\n",
"* ease of interpretation\n",
"* easy of implementation\n",
"* handles continuous and discrete features (and mixed)\n",
"* invariant to monotone transformation of features\n",
"* variable selection automated (ignores redundant variables)\n",
"* robust\n",
"* scalable (can handle huge datasets)\n",
"\n",
"However, relative to other statistical learning methods, trees do not predict very accurately, due to the greedy nature of the tree construction algorithm. Also, trees tend to be **unstable**, as small changes to the inputs can have large effects on the structure of the tree; poor decisions near the root of the tree will propogate to the rest of the tree. Hence, trees are **high variance** (*i.e.* noisy) estimators.\n",
"\n",
"One way to reduce the variance of an estimate is to average together many estimates. In the case of decision trees, we can train $T$ different trees on random subsets of the data (with replacement) then average according to:\n",
"\n",
"$$\\hat{f}(\\mathbf{x}) = \\frac{1}{T} \\sum_{i=1}^T f_t(\\mathbf{x})$$\n",
"\n",
"where $f_t$ is the $t^{th}$ tree. This approach is called \"bootstrap aggregating\", or **bagging**.\n",
"\n",
"Note that, since we are averaging over trees, there is *no need to prune*. With bagging, we reduce variance by averaging, rather than by pruning."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from sklearn.ensemble import BaggingClassifier\n",
"\n",
"bc = BaggingClassifier(n_jobs=4, oob_score=True)\n",
"bc"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"bc.fit(X_train, y_train)\n",
"\n",
"preds = bc.predict(X_test)\n",
"pd.crosstab(y_test, preds, rownames=['actual'], \n",
" colnames=['prediction'])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Test error of a bagged model is measured by estimating **out-of-bag error**.\n",
"\n",
"On average, each bagged tree uses about 2/3 of observations, leaving the remaining third as \"out-of bag\". The response for the ith observation for each of the trees in which that observation was excluded (on average, B/3) is averaged. This essentially the same as performing leave-one-out (LOO) cross-validation."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"bc.oob_score_"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This approach is an **ensemble learning** method, because it takes a set of *weak* learners, and combines them to construct a *strong* learner that is more robust, with lower generalization error.\n",
"\n",
"An average of B trees, each with variance $\\sigma^2$, has variance $\\sigma^2/B$. If the variables are simply identically distributed, with positive pairwise correlation $\\rho$, then the variance of the average of the B trees is:\n",
"\n",
"$$\\rho \\sigma^2 + \\frac{1-\\rho}{B}\\sigma^2$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"As the number of trees becomes large, the second term goes to zero. Further reductions in variance are limited by the size of the **correlation** among the trees $\\rho$."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Random Forests\n",
"\n",
"**Random forests** improves upon bagging by creating a set of decision trees that are less correlated than bootstrapped trees. This is done by selecting from only a subset $m$ out of $M$ possible predictors at each split. Typically, we choose approximately the square root of the available number.\n",
"\n",
"This procedure is used to create a set of trees, most of which will be poor at predicting a given observation. However, classification is based on a *majority vote* of the constituent trees."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from sklearn.ensemble import RandomForestClassifier\n",
"\n",
"rf = RandomForestClassifier(n_jobs=4)\n",
"rf.fit(X_train, y_train)\n",
"\n",
"preds = rf.predict(X_test)\n",
"pd.crosstab(y_test, preds, rownames=['actual'], \n",
" colnames=['prediction'])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"With random forests, it is possible to quantify the **relative importance** of feature inputs for classification. In scikit-learn, the Gini index (recall, a measure of error reduction) is calculated for each internal node that splits on a particular feature of a given tree, which is multiplied by the number of samples that were routed to the node (this approximates the probability of reaching that node). For each variable, this quantity is averaged over the trees in the forest to yield a measure of importance."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"importances = rf.feature_importances_\n",
"indices = np.argsort(importances)[::-1]\n",
"\n",
"# Print the feature ranking\n",
"print(\"Feature ranking:\")\n",
"\n",
"for f in range(X.shape[1]):\n",
" print(\"%d. %s (%f)\" % (f + 1, X.columns[indices[f]], importances[indices[f]]))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"plt.figure()\n",
"plt.title(\"Feature importances\")\n",
"plt.bar(range(X.shape[1]), importances[indices],\n",
" color=\"r\", align=\"center\")\n",
"plt.xticks(range(X.shape[1]), X.columns[indices], rotation=90)\n",
"plt.xlim([-1, X.shape[1]]);"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"`RandomForestClassifier` uses the Gini impurity index by default; one may instead use the entropy information gain as a criterion."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"rf = RandomForestClassifier(n_jobs=4, criterion='entropy')\n",
"rf.fit(X_train, y_train)\n",
"importances = rf.feature_importances_\n",
"indices = np.argsort(importances)[::-1]\n",
"\n",
"# Print the feature ranking\n",
"print(\"Feature ranking:\")\n",
"\n",
"for f in range(X.shape[1]):\n",
" print(\"%d. %s (%f)\" % (f + 1, X.columns[indices[f]], importances[indices[f]]))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Example: Baseball pitch classification\n",
"\n",
"Today, over 6TB of data per game are collected by MLB Advanced Media. This consists of information from cameras, used to track primarily the players, and radar, used to track the ball. The TrackMan radar system follows ball by tracking the seams at a rate of 20,000 frame/second. This results in information on where the pitcher released the ball (extension), how hard he threw (velocity), what sort of spin he had (spin rate), how fast it appeared to the batter (perceived velocity), how hard the ball was hit (exit velocity), how it came off the bat (launch angle), and exactly where it went (batted ball direction). \n",
"\n",
"The dataset ‘pitches.csv’ contain [Statcast](https://en.wikipedia.org/wiki/Statcast) data corresponding to over 13,000 pitches from 5 different pitchers over 3 years. The data dictionary describing each column is given in `pitches.md`."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"pitches = pd.read_csv('../data/pitches.csv', index_col=0)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"pitches.head()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Recode a few character columns"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"pitch_lookup = {'CB': 0,\n",
" 'SL': 1,\n",
" 'SI': 2,\n",
" 'CH': 3,\n",
" 'CU': 4,\n",
" 'FB': 5}\n",
"\n",
"pitches_recoded = pitches.replace({'throws': {'R': 0, 'L': 1},\n",
" 'type': pitch_lookup})"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Extract predictor columns"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"prediction_cols = ['throws', 'height', 'initspeed', 'breakx',\n",
" 'breakz', 'initposx', 'initposz', 'extension', 'spinrate']"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"X = pitches_recoded[prediction_cols].copy()\n",
"y = pitches_recoded.type"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"X_train, X_test, y_train, y_test = model_selection.train_test_split(\n",
" X, y, test_size=0.4, random_state=0)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Fit model"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"baseball_clf = RandomForestClassifier()\n",
"baseball_clf.fit(X_train, y_train)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Generate predictions"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"preds = baseball_clf.predict(X_test)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"baseball_clf.score(X_test, y_test)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from sklearn.metrics import confusion_matrix\n",
"\n",
"confusion_matrix(y_test, preds)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"We can tune several hyperparameters using cross-validation."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from sklearn.model_selection import RandomizedSearchCV\n",
"\n",
"n_estimators = [50, 100, 150]\n",
"max_depth = [10, 20, 30, 40]\n",
"min_samples_split = [4, 6, 8]\n",
"min_samples_leaf = [1, 2, 4]\n",
"\n",
"# Create the random grid\n",
"parameter_grid = {'n_estimators': n_estimators,\n",
" 'max_depth': max_depth,\n",
" 'min_samples_split': min_samples_split,\n",
" 'min_samples_leaf': min_samples_leaf}"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"clf_baseball = RandomForestClassifier()\n",
"\n",
"rf_cf = RandomizedSearchCV(clf_baseball, parameter_grid, \n",
" n_iter=50, cv=5, n_jobs=2)\n",
"\n",
"rf_cf.fit(X_train, y_train)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"rf_cf.best_estimator_.get_params()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"preds = rf_cf.best_estimator_.predict(X_test)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from sklearn.metrics import confusion_matrix\n",
"\n",
"confusion_matrix(y_test, preds)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"pd.Series(rf_cf.best_estimator_.feature_importances_, index=prediction_cols).sort_values().plot.barh()"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Decision Tree Regression"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"While it may not be apparent how to use trees for regression analysis, it requires only a straightforward modification to the algorithm. A popular tree-based regression algorithm is the **classification and regression tree** (CART).\n",
"\n",
"The file `TNNASHVI.txt` in your data directory contains daily temperature readings for Nashville, courtesy of the [Average Daily Temperature Archive](http://academic.udayton.edu/kissock/http/Weather/). This data, as one would expect, oscillates annually. We can use a decision tree regression model to fit the data."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"daily_temps = pd.read_table(\"../data/TNNASHVI.txt\", sep='\\s+', \n",
" names=['month','day','year','temp'], na_values=-99)\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"daily_temps.temp[daily_temps.year>2010].plot(style='b.', figsize=(10,6))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In this context, none of the cost functions considered so far would be appropriate. Instead, it would be more suitable to use something like mean squared error (MSE) to guide the growth of the tree. With this, we can proceed to choose:\n",
"\n",
"1. a variable on which to split the dataset\n",
"2. a value of the variable at which to place a node (in the case of continuous features)\n",
"\n",
"Recall that the output of a tree is just a constant value for each leaf; here, we simply return the average of all the response values in the region. Thus, we choose a cut point that minimizes the MSE at each step."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Transmogrify data\n",
"y = daily_temps.temp[daily_temps.year>2010]\n",
"X = np.atleast_2d(np.arange(len(y))).T"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from sklearn.tree import DecisionTreeRegressor\n",
"clf = DecisionTreeRegressor(max_depth=7, min_samples_leaf=2)\n",
"clf.fit(X, y)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"X_fit = np.linspace(0, len(X), 1000).reshape((-1, 1))\n",
"y_fit_1 = clf.predict(X_fit)\n",
"\n",
"plt.plot(X.ravel(), y, '.k', alpha=0.3)\n",
"plt.plot(X_fit.ravel(), y_fit_1, color='red');"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"A single decision tree allows us to estimate the signal in a non-parametric way,\n",
"but clearly has some issues. In some regions, the model shows high bias and\n",
"under-fits the data\n",
"(seen in the long flat lines which don't follow the contours of the data),\n",
"while in other regions the model shows high variance and over-fits the data\n",
"(reflected in the narrow spikes which are influenced by noise in single points).\n",
"\n",
"One way to address this is to use an ensemble method, like random forests, so that the\n",
"effects of their over-fitting go away on average. \n",
"\n",
"Here we will use a random forest of 200 trees to reduce the tendency of each\n",
"tree to over-fitting the data."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from sklearn.ensemble import RandomForestRegressor\n",
"clf = RandomForestRegressor(n_estimators=200, max_depth=9, \n",
" min_samples_leaf=10)\n",
"clf.fit(X, y)\n",
"\n",
"y_fit_200 = clf.predict(X_fit)\n",
"\n",
"plt.plot(X.ravel(), y, '.k', alpha=0.3)\n",
"plt.plot(X_fit.ravel(), y_fit_200, color='red')\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Prediction intervals\n",
"\n",
"The predictions from random forests are not accompanied by estimates of uncertainty, as is the case with Bayesian regression models. However, it is possible to obtain probability intervals using a random forests approach. Since we are using an ensemble of trees, it is possible to track *all* predicted values for all leaf nodes in a random forest, rather than just the mean or modal value. This results in conditional distributions $P(y|X=x)$ for every x, from which percentiles can be calculated for desired endpoints in a prediction interval. This approach is called **quantile regression forests**.\n",
"\n",
"To implement quantile regression forests in scikit-learn, we need to allow each tree to grow so that each leaf node contains exactly one value. Then, each tree returns a single response variable, from which a conditional distribution can be approximated. Of course, fully expanding trees will result in overfitting, but these can also be cross-validated.\n",
"\n",
"scikit-learn does not automatically calculate prediction intervals, but the estimators from each constitutent tree in the `RandomForestRegressor` is avaialable, from which individual tree predictions can be made."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"def prediction_intervals(mod, X, alpha=0.05):\n",
" preds = [pred.predict(X) for pred in mod.estimators_]\n",
" lower = np.percentile(preds, 100*(alpha/2), axis=0)\n",
" upper = np.percentile(preds, 100*(1-alpha/2), axis=0)\n",
" return lower, upper, np.array(preds)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"X_train, X_test, y_train, y_test = model_selection.train_test_split(\n",
" X, y, test_size=0.4, random_state=0)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"clf = RandomForestRegressor(n_estimators=1000, min_samples_leaf=1)\n",
"clf.fit(X_train, y_train)\n",
"\n",
"y_fit_200 = clf.predict(X_fit)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"lower, upper, preds = prediction_intervals(clf, X_test, alpha=0.1)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"x_sorted = np.sort(X_test.ravel())\n",
"order = np.argsort(X_test.ravel())\n",
"plt.errorbar(x_sorted, y_test.values[order], \n",
" yerr=[(y_test.values-lower)[order], (upper-y_test.values)[order]])\n",
"plt.plot(X_test, y_test, '.r', alpha=0.3)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Exercise\n",
"\n",
"Selecting the optimal random forest regression model for the nashville daily temperature data via cross-validation in `scikit-learn`. Use the number of estimators and the maximim leaf nodes as tuning parameters."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Write your answer here"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"---\n",
"## References\n",
"\n",
"Meinshausen, N. [Quantile Regression Forests](http://www.jmlr.org/papers/volume7/meinshausen06a/meinshausen06a.pdf) Journal of Machine Learning Research 7 (2006) 983–999\n",
"\n",
"T. Hastie, R. Tibshirani and J. Friedman. (2009) [Elements of Statistical Learning: Data Mining, Inference, and Prediction](http://statweb.stanford.edu/~tibs/ElemStatLearn/), second edition. Springer.\n"
]
}
],
"metadata": {
"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.6.6"
},
"latex_envs": {
"bibliofile": "biblio.bib",
"cite_by": "apalike",
"current_citInitial": 1,
"eqLabelWithNumbers": true,
"eqNumInitial": 0
}
},
"nbformat": 4,
"nbformat_minor": 2
}