决策树
目录
决策树简介 #
决策树就像一个树状的决策模型。它通常将解释变量递归地切分成子集来学习，如下图所示。决策树的节点用方块表示，用来测试解释变量。
这些节点通过边缘连接来指定输出。比如用某个节点来测试解释变量是否超出了阈值，如果没有超过，就指向左边的节点，如果超过了，就指向右边节点。就这样重复这一过程，到达终止条件即停止。在分类问题中，叶子节点就代表着类别；在回归问题中，所有响应变量的值取平均值来作为响应变量的估计值。
from IPython.display import Image
Image(filename = 'icons/em_tree.jpg')
训练决策树 #
我们开始先用ID３(Iterative Dichotomiser 3)算法来构建决策树。
假如现在我们需要把一些猫和狗进行分类。但是你不可以通过肉眼观察，而是通过一些它们的行为特征来分类。这些变量也就是所说的解释变量，比如是否喜欢打闹，脾气是否暴躁，三类食物中那类是最喜欢的。
为了对其分类，决策树需要把解释变量作为树节点来测试。这些节点的下一节点在于它们这次的测试结果是什么。直到最到抵达叶子节点，也就测试出是猫是狗。
Image(filename='icons/train_table_dog_cat.jpg')
观察这些数据可以看到，猫比狗更容易发脾气。大多数狗爱打闹，而猫不爱打闹。狗更喜欢狗粮和培根，而猫喜欢猫粮和培根。解释变量是否喜欢打闹和脾气是否暴躁可以很简单得转换成二元特征值，而喜欢的食物有三个值，我们将用独热编码(One-hot)来表示([1,0,0]，[0,1,0]，[0,0,1])。
到此，我们可以手动得去构建一个分类规则，比如说喜欢打闹并且喜欢吃培根那就是只狗，以此类推。但是手动构建这些规则比较麻烦，我们可以通过构建决策树来制定规则。
问题选择 #
在决策树中，我们通常先得对解释变量进行测试，然后通过测试得到的值去预测出响应变量。但是哪些解释变量放在前面会产生更好的输出，以形成好的model？我们的思路是通过测试得到的子集中包含所有的猫或者所有的狗，这样比得到的子集中既有猫又有狗要好很多。我们还需要避免创建那种测试，把单独的一只猫或一条狗分离出去。换句话说，也就是通过测试要最大程度的降低我们的不确定性。这里就涉及到一个用来度量信息不确定性的概念：熵(entropy)。
熵的单位是\(bit\)，它量化了一个变量的不确定性。它的方程表示如下，其中\(n\)代表会有多少个输出，\(P(x_i)\)代表第\(i\)个输出的概率。\(b\)一般取\(２\)，\(e\)一般取\(10\)。由于\(P\)会小于\(1\)，那么取得对数为负数，所以前面加个负号让其变为正。\(H(X) = -\sum_{i=1}^nP(x_i)log_bP(x_i)\) 比如，投硬币正面朝上的概率是\(0.5\),正面朝下的概率是\(0.5\),那么这个硬币投一次所得到的熵就等于：\(H(X) = -(0.5log_20.5+0.5log_20.5) = 1.0\) 也就是对于投硬币这件事，产生的所有可能值包含的信息期望值为\(1bit\)。如果我们投两个硬币的话，也可以轻松得到这件事产生的所有可能值包含的信息期望值为\(２bit\)。假如，我们对硬币做一些手脚，使得投掷后正面朝上的概率为\(0.8\)，正面朝下的概率为\(0.2\)，那么它的熵为：\(\)H(X) = -(0.8log_20.8+0.2log_20.2) = 0.7219280948873623 \(\)可以看到，它的值比\(1\)小，虽然硬币投出仍然会产生两种结果，但是它的不确定性小了。
接下来我们来计算动物分类的熵。如果这些训练数据中猫和狗的数量相等，那么计算出来的熵就是\(1\)，我们将得不到任何信息，这就像我们刚刚投硬币的例子。但是我们可以看到这份数据中猫的数量有\(8\)只，狗有\(6\)只，那么它决策的熵就是:\(\)H(X) = -(\frac{6}{14}log_2\frac{6}{14}log_2+\frac{8}{14}log\frac{8}{14}) = 0.985228136.342516 \(\)由于猫的数量相对要多，所以事件的不确定性要少一些。接下来我们就在这些解释变量中用这种方法找出不确定性最小的。我们可以测试是否喜欢打闹这个解释变量，将它们分成两组，喜欢和不喜欢，结果如下图所示：
Image(filename='icons/fetch_or_nofetch.jpg')
决策树经常会用类流程图来展示它的决策过程。在图中可以看到，上面的节点是根节点，包含了所有将要测试的解释变量。在根节点中还没有开始测试，只根据是否爱打闹得到的熵为\(0.985\)。前面我们说将解释变量是否爱打闹转换为二元变量，左边的子节点为\(０\)，右边的为\(１\)。由于在左边有\(７\)只猫和\(２\)只狗，所以得到的熵为\(H(X) = -(\frac{2}{9}log_2\frac{2}{9}+\frac{7}{9}log_2\frac{7}{9}) = 0.7642045065086203\) 右边的子集有\(１\)只猫和\(４\)只狗，所以得到的熵为：\(H(X) = -(\frac{1}{5}log_2\frac{1}{5}+\frac{4}{5}log_2\frac{4}{5}) = 0.721928094887362\) 现在我们换成脾气是否暴躁这种解释变量来测试，那么将得到下面这幅图。脾气温顺的在左边节点，脾气暴躁的在右边节点。
Image(filename='icons/grumpy_or_nogrumpy.jpg')
我们还可以按照这种思路测试剩下的解释变量，比如最喜欢的食物是猫食：
Image(filename='icons/cat_food.jpg')
信息增益 #
对解释变量最喜欢的食物是猫食的测试结果为，右节点中喜欢猫食的只有猫，没有狗，熵为０；而左节点中有２只猫６只狗，熵为0.811\(bit\)。那么至此，到底哪一个变量最大程度得降低了分类的不确定性呢？子集的熵的均值看起来是个合理的度量指标。在刚刚测试过程中，发现猫食的子集熵均值最小。直观上看确实是这样的，因为它可以识别出将近一半的样本。但是这么做的话其实只是得到局部最优。比方说测试出的一个子集中有２只狗没有猫，另一个子集中有４只狗８只猫。得到它们的熵一个是\(０\)，一个是\(0.9182958340544896\)，取平数为 0.459，但是会发现其中一个子集的熵将近\(1bit\)，这就好比说我们其实并没有消除多少信息的不确定性。因此，接下来我们将用信息增益(information gain)(如今改名为相对熵)来合理度量熵的降幅。信息增益的表达式如下，表示的是父节点的熵\(H(T)\)与其子节点熵的加权平均值的差。其中\(T\)表示目前的实例，\(a\)表示需要测试的解释变量。\({x\epsilon vals(a)}\)表示实例\(x\)属性是解释变量\(a\)的值。\({x\epsilon T\mid x_a=v}\)表示解释变量\(a\)的值等于\(v\)的数量。\(H({x\epsilon T\mid x_a=v})\)表示解释变量\(a\)的值为\(ｖ\)的实例子集的熵。\(IG(T,a)=H(T)-\sum_{v\epsilon vals(a)} \frac{\lvert {x\epsilon T \mid x_a=v} \rvert }{\lvert T \rvert }H({x\epsilon T\mid x_a=v})\) 下表是总体信息增益的计算结果，可以看到，猫粮测试是最佳选择，因为其信息增益最大。
Image(filename='icons/info_gain_all.jpg')
现在我们根据上表把其它的节点加进去，其中一个子节点只有猫，另一个节点中有\(2\)只猫\(６\)只狗。可以得到一下结果：
Image(filename='icons/info_gain_leftsub.jpg')
所有的测试都会产生熵为\(０\)的情况，但是可以看到脾气是否暴躁和是否爱打闹所得到的信息增益要大。ID3算法会任意选择一个节点作为测试，下面来看看脾气是否暴躁这个解释变量，可以看出，它的右节点有\(４\)只猫，左节点有\(２\)只猫和\(２\)只狗。
Image(filename='icons/info_gain_grumpy.jpg')
现在我们对剩下的解释变量计算信息增益，包括脾气是否暴躁，最喜欢狗粮，最喜欢培根，这些解释变量都会产生一个叶节点中包含\(１\)只猫和\(１\)只狗，另一个叶节点中包含剩下的动物，计算的信息增益结果如下图：
Image(filename='icons/info_gain_anothers.jpg')
现在我们随便挑选一个解释变量(脾气是否暴躁)来看，发现其左节点包含了\(１\)只猫和\(１\)只狗，另一个节点中包含了\(２\)只猫和\(１\)只狗。其他两个解释变量(最喜欢培根；最喜欢狗粮)产生了同样的结果——一个节点中包含了\(１\)只猫和\(１\)只狗，另一个节点中包含了\(２\)只猫。之后，我们对最喜欢狗粮这个变量进行测试，结果如下：
Image(filename='icons/info_gain_dog_food.jpg')
下面根据上面的测试数据来进行一些分类：
Image(filename='icons/info_gain_classified.jpg')
我们看到，第一类动物，喜欢打闹，脾气不暴躁，喜欢培根，通过上面计算的流程规则，我们把这种动物归类为狗。以此类推。
好了，以上我们用ID3算法实现了一个决策树，当然还有其他的方法，C4.5就是ID3的改进版，可以用来处理连续的解释变量并考虑特征之丢失的情况。C4.5算法可以对树进行修剪(prune),以减小决策树的规模。在scikit-learn中决策树用的是CART算法，它也支持树的修剪。
基尼不纯度 #
前面我们通过求最大的信息增益来构建决策树，这里还有一种常用的方法，基尼不纯度(Gini impurity)。用来度量一个集合中每种类型的比例，公式如下：\(Ginit=1-\sum_{i-1}^{j}P(i\lvert t)^2\) 其中，j是类型的数量，t是节点样本的子集，\(P(i\lvert t)\)是从节点子集中选择一个类型\(i\)的概率。
当所有元素都是一个类型的时候，基尼不纯度就为\(0\)，因为在这些中选择元素是那个类型的概率为\(1\)。和熵一样，当所有元素的概率一样时，基尼不纯度最大，可以这么表示：\(Gini_max=1-\frac{1}{n}\)在scikit-learn中，基尼不纯度和信息增益都会支持，哪个好就用哪个。
scikit-learn中的决策树 #
接下来我们用程序构建一个决策树。数据来源是网络上一份互联网广告的数据，包含有3279张图片，其中459张是广告，2820张是正常的。我们的目的就是将广告和正常的内容进行分类，以隐藏那些广告。决策树学习算法可以从比例并不协调的数据集中生成一个不平衡的决策树（biased tree）。在决定是否值得通过过抽样（over-sampling）和欠抽样（under-sampling）的方法平衡训练集之前，我们将用不相关的数据集对模型进行评估。本例的解释变量就是图片的尺寸，网址链接里的单词，以及图片标签周围的单词。响应变量就是图片的类型。解释变量已经被转换成特征向量了。前三个特征值表示宽度，高度，图像纵横比（aspect ratio）。剩下的特征是文本变量的二元频率值。下面，我们用网格搜索来确定决策树模型最大最优评价效果（F1 score）的超参数，然后把决策树用在测试集进行效果评估。
import pandas as pd
from sklearn.tree import DecisionTreeClassifier
from sklearn.cross_validation import train_test_split
from sklearn.metrics import classification_report
from sklearn.pipeline import Pipeline
from sklearn.grid_search import GridSearchCV
df = pd.read_csv('/home/sunnyin/ML-Data/ad-dataset/ad.data', header=None)
explanatory_variable_columns = set(df.columns.values)
response_variable_column = df[len(df.columns.values)-1]
explanatory_variable_columns.remove(len(df.columns.values)-1)
y = [1 if e == 'ad.' else 0 for e in response_variable_column]
# X = df[list(explanatory_variable_columns)]
X = df.loc[:, list(explanatory_variable_columns)]
print y[:10]
print X[:10]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
0 1 2 3 4 5 6 7 8 9 ... 1548 \
0 125 125 1.0 1 0 0 0 0 0 0 ... 0
1 57 468 8.2105 1 0 0 0 0 0 0 ... 0
2 33 230 6.9696 1 0 0 0 0 0 0 ... 0
3 60 468 7.8 1 0 0 0 0 0 0 ... 0
4 60 468 7.8 1 0 0 0 0 0 0 ... 0
5 60 468 7.8 1 0 0 0 0 0 0 ... 0
6 59 460 7.7966 1 0 0 0 0 0 0 ... 0
7 60 234 3.9 1 0 0 0 0 0 0 ... 0
8 60 468 7.8 1 0 0 0 0 0 0 ... 0
9 60 468 7.8 1 0 0 0 0 0 0 ... 0
1549 1550 1551 1552 1553 1554 1555 1556 1557
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0
3 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 0 0
9 0 0 0 0 0 0 0 0 0
[10 rows x 1558 columns]
数据不全，而那些不全的数据用了空白加问号表示( ?),所以我们为了计算方便要将这些数据替换为-1。之后会用交叉验证的方式来对数据进行切割。
X.replace(to_replace=' *\?', value=-1, regex=True, inplace=True)
X_train, X_test, y_train, y_test = train_test_split(X, y)
#创建一个管道和DecisionTreeClassifier，并用entropy来计算
pipeline = Pipeline([('clf',DecisionTreeClassifier(criterion='entropy'))])
#接下来创建网格搜索的参数们
parameters = {'clf__max_depth':(150,155,160),'clf__min_samples_split':(1,2,3),'clf__min_samples_leaf':(1,2,3)}
#通过网格搜索的方法来找出综合评价指数f1最大的参数以及一些结论
grid_search = GridSearchCV(pipeline,parameters,n_jobs=-1,verbose=1,scoring='f1')
grid_search.fit(X_train, y_train)
print 'Best score: %0.3f' % grid_search.best_score_
print 'Best parameters set: '
best_parameters = grid_search.best_estimator_.get_params()
for param_name in sorted(parameters.keys()):
print "\t%s: %r" % (param_name,best_parameters[param_name])
predictions = grid_search.predict(X_test)
print(classification_report(y_test, predictions))
Fitting 3 folds for each of 27 candidates, totalling 81 fits
[Parallel(n_jobs=-1)]: Done 42 tasks | elapsed: 6.9s
[Parallel(n_jobs=-1)]: Done 81 out of 81 | elapsed: 12.7s finished
Best score: 0.892
Best parameters set:
clf__max_depth: 155
clf__min_samples_leaf: 2
clf__min_samples_split: 2
precision recall f1-score support
0 0.97 1.00 0.98 697
1 0.98 0.80 0.88 123
avg / total 0.97 0.97 0.97 820
从结果中可以看出，有\(89%\)的广告图片被发现了，并且有\(98%\)真的是广告片。接下来我们可以继续改进模型。
集成决策树 #
最常用的就是随机森林(random forest)。在随机森林中，通常是把每个决策树的预测结果的均值或者众数作为最终的结果。在scikit-learn中，是用均值作为最终的结果。相对于单棵决策树，随机森林能够很好的避免过拟合现象，因为一棵决策树很难看到数据的全貌，也很难在训练时记住所有的噪声。
下面我们来用随机森林测试一下刚才的数据：
from sklearn.ensemble import RandomForestClassifier
pipeline = Pipeline([('clf', RandomForestClassifier(criterion='entropy'))])
parameters = {
'clf__n_estimators': (5, 10, 20, 50),
'clf__max_depth': (50, 150, 250),
'clf__min_samples_split': (1, 2, 3),
'clf__min_samples_leaf': (1, 2, 3)
}
grid_search = GridSearchCV(pipeline,parameters,n_jobs=-1,verbose=1,scoring='f1')
grid_search.fit(X_train,y_train)
print('best score: %0.3f' % grid_search.best_score_)
print('Best parameters set:')
best_parameters = grid_search.best_estimator_.get_params()
for param_name in sorted(parameters.keys()):
print "\t%s: %r" % (param_name,best_parameters[param_name])
predictions = grid_search.predict(X_test)
print(classification_report(y_test, predictions))
Fitting 3 folds for each of 108 candidates, totalling 324 fits
[Parallel(n_jobs=-1)]: Done 42 tasks | elapsed: 7.0s
[Parallel(n_jobs=-1)]: Done 192 tasks | elapsed: 31.6s
[Parallel(n_jobs=-1)]: Done 324 out of 324 | elapsed: 52.9s finished
best score: 0.930
Best parameters set:
clf__max_depth: 50
clf__min_samples_leaf: 1
clf__min_samples_split: 1
clf__n_estimators: 50
precision recall f1-score support
0 0.97 1.00 0.99 697
1 0.98 0.85 0.91 123
avg / total 0.97 0.97 0.97 820
啊哈，在这份数据集当中，虽然效果不是太明显，但是各项指标还都是有些提升的，比如召回率提升到了\(85%\)。
总结 #
我们在开始通过一个简单的例子解释了决策树的构建，详细讲解了熵、信息增益以及基尼不纯度的概念。之后通过scikit-learn对算法进行了实现。总体来讲，决策树的模型还是不错的，但是由于它很容易发生过拟合现象，所以最好用随机森林来进行分类。随机森林算法被人们大量的使用，并且在kaggle中也大方光彩，在后面的文章中，我还会针对随机森林继续讲解。