1. 基本概念
决策树模型为非参数监督模型，该模型为根据一系列的if-else逻辑组合而成。树可以看作是一个分段函数，并且树的层数越深，就会更贴合数据(fitted)。
显然决策树的生成时一个递归过程，且在以下三种情形下会导致递归返回：
- 当前结点包含的样本全属于同一类别：例如敲声清脆的瓜都是好瓜，则敲声音清脆下无需继续划分。
- 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分：例如色泽黑色的瓜全都是敲声浊响根蒂蜷缩。
- 当前节点包含的样本集合为空，不能划分
分类和回归任务，决策树模型一般均可以执行。
1.1 分类树
DecisionTreeClassifier可以用作训练决策树分类模型。
from sklearn.datasets import load_iris
from sklearn import tree
X, y = load_iris(return_X_y=True)
clf = tree.DecisionTreeClassifier()
clf = clf.fit(X, y)
tree.plot_tree(clf)
Out[310]:
[Text(167.4, 199.32, 'X[2] <= 2.45\ngini = 0.667\nsamples = 150\nvalue = [50, 50, 50]'),
Text(141.64615384615385, 163.07999999999998, 'gini = 0.0\nsamples = 50\nvalue = [50, 0, 0]'),
Text(193.15384615384616, 163.07999999999998, 'X[3] <= 1.75\ngini = 0.5\nsamples = 100\nvalue = [0, 50, 50]'),
Text(103.01538461538462, 126.83999999999999, 'X[2] <= 4.95\ngini = 0.168\nsamples = 54\nvalue = [0, 49, 5]'),
Text(51.50769230769231, 90.6, 'X[3] <= 1.65\ngini = 0.041\nsamples = 48\nvalue = [0, 47, 1]'),
Text(25.753846153846155, 54.359999999999985, 'gini = 0.0\nsamples = 47\nvalue = [0, 47, 0]'),
Text(77.26153846153846, 54.359999999999985, 'gini = 0.0\nsamples = 1\nvalue = [0, 0, 1]'),
Text(154.52307692307693, 90.6, 'X[3] <= 1.55\ngini = 0.444\nsamples = 6\nvalue = [0, 2, 4]'),
Text(128.76923076923077, 54.359999999999985, 'gini = 0.0\nsamples = 3\nvalue = [0, 0, 3]'),
Text(180.27692307692308, 54.359999999999985, 'X[2] <= 5.45\ngini = 0.444\nsamples = 3\nvalue = [0, 2, 1]'),
Text(154.52307692307693, 18.119999999999976, 'gini = 0.0\nsamples = 2\nvalue = [0, 2, 0]'),
Text(206.03076923076924, 18.119999999999976, 'gini = 0.0\nsamples = 1\nvalue = [0, 0, 1]'),
Text(283.2923076923077, 126.83999999999999, 'X[2] <= 4.85\ngini = 0.043\nsamples = 46\nvalue = [0, 1, 45]'),
Text(257.53846153846155, 90.6, 'X[1] <= 3.1\ngini = 0.444\nsamples = 3\nvalue = [0, 1, 2]'),
Text(231.7846153846154, 54.359999999999985, 'gini = 0.0\nsamples = 2\nvalue = [0, 0, 2]'),
Text(283.2923076923077, 54.359999999999985, 'gini = 0.0\nsamples = 1\nvalue = [0, 1, 0]'),
Text(309.04615384615386, 90.6, 'gini = 0.0\nsamples = 43\nvalue = [0, 0, 43]')]
1.2 回归树
DecisionTreeRegressor可以用于构建回归树。回归树为该叶节点的预测值为该组的值。
# Import the necessary modules and libraries
import numpy as np
from sklearn.tree import DecisionTreeRegressor
import matplotlib.pyplot as plt
# Create a random dataset
rng = np.random.RandomState(1)
X = np.sort(5 * rng.rand(80, 1), axis=0)
y = np.sin(X).ravel()
y[::5] += 3 * (0.5 - rng.rand(16))
# Fit regression model
regr_1 = DecisionTreeRegressor(max_depth=2)
regr_2 = DecisionTreeRegressor(max_depth=5)
regr_1.fit(X, y)
regr_2.fit(X, y)
# Predict
X_test = np.arange(0.0, 5.0, 0.01)[:, np.newaxis]
y_1 = regr_1.predict(X_test)
y_2 = regr_2.predict(X_test)
2 划分选择
决策树模型的关键为划分选择，即应该使用哪个属性进行划分，以及该属性为连续值时该从哪个值划分。以下介绍常用于划分的几个指标。
2.1 信息增益 (information gain)
信息熵(information entropy)是度量样本集合纯度常用的一个指标。越小，则纯度越高。
对数为什么选择2作为底数，是信息学约定俗称的一个习惯，笔者这里推断可能原因是与2进制有关。
信息增益(information gain)则为在一个节点，划分后对划分前所带来的增益。一般而言，越大则使用属性
进行划分带来的纯度提升越大。
即我们选择信息增益大的属性a来进行划分，数学上的表示为
使用信息增益作为划分指标，也就是经典的ID3(Iterative Dichotomise 3rd) 模型 [Quinlan, 1979, 1986]。
初次接触很难理解，以下为一个构建决策树的实例。
2.1.1 例子
首先我们需要计算出根节点的信息熵，即使用“好瓜”这个字段来计算。
然后我们要计算出当前数据集内，每个属性的信息增益。以色泽为例，.若使用该属性对 D 进行划分，则可得到3个子集，分别记为：D1 (色泽=青绿)，D2 (色泽=乌黑)，D3 (色泽=浅白)：
使用同样方法计算其他属性的信息增益：
由于纹理的信息增益最高，所以选择他为划分属性。
然后每个节点再继续对比信息增益，然后向下划分。例如选择纹理=“清晰”为例，基于计算各属性的信息增益：
"根蒂"、 "脐部"、 "触感" 3 个属性均取得了最大的信息增益，可任选其中之一作为划分属性。最终我们获得了以下决策树：
2.2 增益率(gain ratio)
另一个经典的C4.5算法[Quinlan, 1993]则使用了增益率作为划分指标。引入增益率的原因为，ID3中的信息增益遇到多分类特征时，会偏大，便偏向于对多分类特征。
属性a可取值的数目越多，便会越高，则对
的惩罚就会越大。
2.3 基尼系数(Gini index)
CART决策树[Breiman et al., 1984]使用基尼系数来选择划分属性。
于是，我们在候选属性集合A中，选择那个使得划分后基尼指数小的属性作为最优划分属性，即
3. 剪枝
剪枝(purning)是决策树对付“过拟合”的主要手段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得“太好”了。剪枝，顾名思义就是将一个节点之后分叉剪掉，让该节点变为一个叶节点。
3.1 预剪枝
对每个结点划分前先进行估计，若当前结点的划分不能带来决策树的泛化性能的提升，则停止划分，并标记为叶结点。
3.2 后剪枝
先从训练集生成一棵完整的决策树，然后自底向上对非叶子结点进行考察，若该结点对应的子树用叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。
后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要白底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。
4. 连续值与缺失值
4.1 连续值
将连续值拆分，最简单的方法为二分法(bi-partition)。
给定拥有个样本量的样本集
和连续属性
，将
的值从大到小排列，记为
。基于划分点
可将D分为子集
和
，
为小于
的样本，
为大于等于
的样本。
于是我们选择一个可以最大化的划分点。
4.1.1 例子：
data = pd.DataFrame({'is_house_owner': list('TFFTTFFFFT'),
'marriage': list('SMSMDDSMSD'),
'income': [125, 100, 100, 110, 60, 95, 85, 75, 90, 220],
'is_unable_payloan': list('FFFFFTTFTF')})
data
Out[197]:
is_house_owner marriage income is_unable_payloan
0 T S 125 F
1 F M 100 F
2 F S 100 F
3 T M 110 F
4 T D 60 F
5 F D 95 T
6 F S 85 T
7 F M 75 F
8 F S 90 T
9 T D 220 F
我们需要将收入(作为分类的特征)。
from numpy import log2
import numpy as np
import pandas as pd
def Sum_Every_Part_Log2(a):
return -(a/a.sum()[0]*log2(a/a.sum()[0])).sum()[0]
def Cal_Entropy(ridge, data, y_name, x_name):
df = data[[y_name, x_name]]
return Sum_Every_Part_Log2(df[df[x_name] >= ridge].groupby(y_name).count()) + Sum_Every_Part_Log2(df[df[x_name] < ridge].groupby(y_name).count())
Entropy_Result = pd.DataFrame({'ridge': data['income'].sort_values().append(pd.Series([max(data['income'])]))})
Entropy_Result['Entropy'] = Entropy_Result['ridge'].apply(lambda x: Cal_Entropy(x, data, 'is_unable_payloan', 'income'))
Entropy_Result
Out[203]:
ridge Entropy
4 60 0.881291
7 75 0.918296
6 85 0.954434
8 90 1.781416
5 95 1.650022
1 100 0.970951
2 100 0.970951
3 110 0.985228
0 125 0.954434
9 220 0.918296
0 220 0.918296
可以看到在95的时候，信息熵最大，故选择95作为划分点划分为>=95和<95两部分。
4.2 缺失值
缺失值的处理方法为，在计算时，乘特征a的数据缺失率。
例如：
5. 例子
使用CART对titanic dataset的用户生存率进行预测。
import graphviz
import numpy as np
import pandas as pd
from sklearn import tree
from sklearn.feature_extraction import DictVectorizer
from sklearn.model_selection import cross_val_score
from sklearn.tree import DecisionTreeClassifier
x = titan[['pclass', 'age', 'sex', 'fare']]
y = titan['survived']
x_train, x_test, y_train, y_test = train_test_split(x, y, random_state = 99)
transfer = DictVectorizer(sparse=False)
x_train = transfer.fit_transform(x_train.to_dict(orient="records"))
x_test = transfer.fit_transform(x_test.to_dict(orient="records"))
score = []
for i in range(1, 21):
estimator = DecisionTreeClassifier(criterion="entropy", max_depth = i)
estimator.fit(x_train, y_train)
precision.append(estimator.score(x_test, y_test))
score
Out[183]:
[0.7477477477477478,
0.7477477477477478,
0.7972972972972973,
0.7972972972972973,
0.8063063063063063,
0.7882882882882883,
0.7882882882882883,
0.7927927927927928,
0.7882882882882883,
0.7882882882882883,
0.7702702702702703,
0.7522522522522522,
0.7837837837837838,
0.7612612612612613,
0.7567567567567568,
0.7387387387387387,
0.7432432432432432,
0.7432432432432432,
0.7477477477477478,
0.7477477477477478]
可以看到树的深度在5时，测试集的精度最好，故我们选择五层的CART模型作为最终模型。
使用测试集来确定一个新的参数，有可能会引起模型的泛化问题，避免这一问题可以多预留一个另外的测试集。
estimator = DecisionTreeClassifier(criterion="gini", max_depth = 5)
estimator.fit(x_train, y_train)
dot_tree = tree.export_graphviz(estimator, out_file=None)
graph = graphviz.Source(dot_tree)
graph.view('titanic')
reference
周志华，机器学习
Quinlan, J. R. (1986). "Induction of decision trees." Machine Learning
scikit learn官方文档
