决策树

4.1 基本流程

决策树基于树结构来进行决策的。决策树的基本形式如下：

Pic14.png

有关于节点：

根节点：最上面的节点，没有进只有出，只有一个。
中间节点：既有进也有出。进去只有一条，出去可以有很多条。
叶节点：有进无出。
子节点与父节点：相邻的节点，更靠近根节点的是父节点，另一个是子节点。

4.2 划分选择

决策树学习的关键是如何选择最优划分属性。随着划分的进行，我们希望决策树的分支节点包含的样本尽可能属于同一类别，即节点的纯度越来越高。

4.2.1 ID3算法：信息增益

信息熵：度量样本集合纯度最常用的一种指标。

假定当前样本集合D中第类k样本所占的比例为p_k，则D的信息熵定义为：

$Ent(D)=-\sum_{k=1}^{|y|}{p_k\log_2p_k}$

约定：当p=0时，p\log_2p=0。Ent(D)的最大值是\log_2|y|，最小值是0。

Pic15.png

$Gain(D,a)=Ent(D)-\sum_{v=1}^{V}{\frac{|D^v|}{|D|}Ent(D^v)}$

信息增益越大，意味着使用属性a划分获得的纯度提升越大，因此可以用信息增益来进行决策树的划分属性选择。

以下面这个表的数据进行举例：

Pic16.png

表中共17个样例，包含8个正例和9个反例，其中共6划分个属性。这是个二分类任务，显然|y|=2。整个过程如下：

首先计算根节点的信息熵：

$Ent(D)=-\sum_{k=1}^{2}{p_k\log_2p_k}=(\frac{8}{17}\log_2\frac{8}{17}+\frac{9}{17}\log_2\frac{9}{17})=0.998$
依次计算每个属性的信息增益：
- “色泽”属性有三个属性值，以此属性对D进行划分可得3个子集，分别记为D^{1(色泽=青绿),D}2(色泽=乌黑),D^{3(色泽=浅白)。其中，子集D}1有6个样例，包括3个正例和3个反例；子集D^{2有6个样例，包括4个正例和2个反例；子集D}3有5个样例，包括1个正例和4个反例。分别计算划分后的3个分支节点的信息熵为：
$Ent(D^1)=(\frac{3}{6}\log_2\frac{3}{6}+\frac{3}{6}\log_2\frac{3}{6})=1.000\\ Ent(D^2)=(\frac{4}{6}\log_2\frac{4}{6}+\frac{2}{6}\log_2\frac{2}{6})=0.918\\ Ent(D^3)=(\frac{1}{5}\log_2\frac{1}{5}+\frac{4}{5}\log_2\frac{4}{5})=0.722$
- 计算属性“色泽”的信息增益：
  
  $Gain(D,色泽)=Ent(D)-\sum_{v=1}^{3}{\frac{|D^v|}{|D|}Ent(D^v)}\\=0.998-(\frac{6}{17}\times1.000+\frac{6}{17}\times0.918+\frac{5}{17}\times0.722)\\=0.109$
- 计算其余5个属性的信息增益：
  
  $Gain(D,根蒂)=0.143\\Gain(D,敲声)=0.141\\Gain(D,纹理)=0.381\\Gain(D,脐部)=0.289\\Gain(D,触感)=0.006$
- 选择信息增益最大的属性作为划分属性：
  
  这6个属性里面，选择“纹理”作为划分属性：
  
  Pic17.png
得到上面的第一层中间节点后，继续进行划分：
- 在“纹理”为“清晰”的节点中，共包含9个样例。其中7个正例，2个反例。计算此时的信息熵：
  
  $Ent(D^1)=-\sum_{k=1}^{2}{p_k\log_2p_k}=(\frac{2}{9}\log_2\frac{2}{9}+\frac{7}{9}\log_2\frac{7}{9})=0.764$
- 计算属性“根蒂”的各个子集的信息熵：
  
  根蒂包含三个属性，可形成3个子集，分别为D^{{11}(根蒂=蜷缩),D}{12}(根蒂=稍缩),D^{13}(根蒂=硬挺)，其信息熵分别为：
  
  $Ent(D^{11})=(\frac{5}{5}\log_2\frac{5}{5}+\frac{0}{5}\log_2\frac{0}{5})=0.000\\ Ent(D^{12})=(\frac{2}{3}\log_2\frac{2}{3}+\frac{1}{3}\log_2\frac{1}{3})=0.918\\ Ent(D^{13})=(\frac{1}{1}\log_2\frac{1}{1}+\frac{0}{1}\log_2\frac{0}{1})=0.000$
- 计算属性“根蒂”的信息增益：
  
  $Gain(D^1,根蒂)=0.764-(\frac{5}{9}\times0.000+\frac{3}{9}\times0.918+\frac{1}{9}\times0.722)=0.458$
- 以同样的方法对其余的4个属性计算信息增益：
  
  $Gain(D^1,色泽)=0.043\\Gain(D^1,敲声)=0.331\\Gain(D^1,脐部)=0.458\\Gain(D^1,触感)=0.458\\$
  
  可见，“根蒂”、“脐部”和“触感”3个属性的信息增益最大且相同，因此，可任选其一作为划分属性。由于“根蒂”中的属性值“蜷缩”和“硬挺”均只对应一个标签，而“稍缩”里面既有好瓜也有坏瓜，因此“蜷缩”和“硬挺”下面不再进行划分，均属于叶节点。而“稍缩”还要继续进行划分。
- 按同样的方法继续对“纹理”下面的“稍糊”和“模糊”属性进行划分，得到下面的决策树：
  
  Pic18.png

4.2.2 C4.5算法：增益率

信息增益准则对可取值数目较多的属性有所偏好，为减少此种偏好带来的不利影响，C4.5决策树算法使用增益率选择最优的划分属性。

增益率的定义为：

$Gain\_radio(D,a)=\frac{Gain(D,a)}{IV(a)}\\其中\\IV(a)=-\sum_{v=1}^{V}{\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}}$

称为属性a的固有值。属性a的可能取值数目越多，即V越大，则IV(a)的值会越大。

信息率准则对可取值数目较少的属性有所偏好，为减少此种偏好带来的不利影响，C4.5决策树算法先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的属性作为划分属性。

4.2.3 CART算法：基尼指数

CART算法使用基尼指数来选择划分属性。数据集D的纯度用基尼指数度量：

$Gini(D)=\sum_{k=1}^{|y|}\sum_{k^`≠k}{p_kp_k^`}\\=1-\sum_{k=1}^{|y|}p_k^2$

基尼指数反映了从数据集中随机抽取两个样本，其类别标记不一致的概率。因此，基尼指数越小，数据集的纯度越高。

属性a的基尼指数定义为：

$Gini\_index(D,a)=\sum_{v=1}^{V}{\frac{|D^v|}{|D|}}Gini(D^v)$

我们在候选属性集合A中，选择基尼指数最小的属性作为划分属性。

4.3 剪枝

决策树为了尽可能分类正确训练样例，会不断的划分节点，导致分支过多，造成严重的过拟合。剪枝是决策树算法解决过拟合的主要手段。

剪枝的基本策略有预剪枝和后剪枝。

采用留出法作为验证决策树的泛化能力。对前面的西瓜数据集进行划分，一部分用于训练集，另一部分作为验证集，如下图，双横线上面是训练集，下面是验证集：

Pic19.png

采用ID3算法，用此训练集产生如下的决策树：

Pic20.png

4.3.1 预剪枝

预剪枝：在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来泛化能力的提升，则停止划分并将当前结点作为叶结点。

在划分前，若将所有“脐部”属性的样本均标记为好瓜，则在验证集进行验证时，第4、5、8样例分类正确而第9、11、12、13样例分类错误，此时验证集精度为\frac{3}{7}\times100%=42.9%。

基于ID3算法，按照“脐部”的属性值划分后，根据“凹陷”、“稍凹”和“平坦”在训练集中样例的正例数量，将“凹陷”、“稍凹”和“平坦”分别标记为“好瓜”、“好瓜”和“坏瓜”的叶结点。此时在验证集进行验证时，第4、5、8、11、12样例分类正确而第9、13样例分类错误，此时验证集精度为\frac{5}{7}\times100%=71.4%。划分前后，验证集精度明显上升（42.9%<71.4%），因此“脐部”进行划分是可以的。

基于ID3算法，继续对节点②进行划分，选择的信息增益最大的属性是“色泽”。根据上图的决策树，使用“色泽”划分后，将“浅白”划分为坏瓜，因此在验证集上，会将第5样例分类错误，这样原来5个分类正确的样例数，现在变成了4个，此时验证集精度为\frac{4}{7}\times100%=57.1%。精度变小，于是禁止节点②进行划分。

基于ID3算法，继续对节点③进行划分，选择的信息增益最大的属性是“根蒂”。划分后，验证集中，样例8仍是验证正确，样例9仍是验证错误，因此验证集精度不变，仍是71.4%，于是禁止对节点③进行划分。

对于节点④，所含样本均是同一类，已经是叶结点，不再进行划分。

剪枝后的决策树如下：

Pic21.png

可见，预剪枝使得很多分支未展开，显著降低了过拟合的风险，也降低了训练时间和验证时间开销。但有些分支当前划分虽然不能提升泛化性能甚至导致泛化性能下降，但在其基础上进行的后续划分却可能导致性能提升，因此预剪枝为决策树可能带来欠拟合的风险。

4.3.2 后剪枝

后剪枝：先从训练集生成一棵完整的树，然后自底向上对非叶节点进行考察，若将该结点对应的字树替换为叶结点能带来决策树泛化性能的提升，则将该结点替换为叶结点。

对于上上图中的决策树，用验证集测试，会得到分类正确的样例4、11、12，其余分类错误，这样验证集精度为42.69%。

首先对结点6，将其分支检剪除，即把其替换为叶结点，此时验证集精度提升为57.1%。

然后对结点5，把其替换为叶结点，此时验证集精度仍为57.1%不变，因此可以不进行剪枝。

对结点2，把其替换为叶结点，此时验证集精度为71.4%，因此可以进行剪枝。

同理对结点3和1，把其替换为叶结点，此时验证集精度分别为71.4%和42.9%，不进行剪枝。

通常，后剪枝决策树的欠拟合风险小，泛化性能往往优于预剪枝决策树，但后剪枝训练时间开销比未剪枝决策树和预剪枝决策树要大很多。

4.4 连续与缺失值

4.4.1 连续值处理

对于连续属性，可取数目不再有限，此时需要使用连续属性离散化技术。最简单的策略是采用二分法。

对于样本数据集D和连续属性a，假设a在D上出现了n个不同的取值，将这些值从小到大进行排序，记为{a^1,a2,\dots,a^n}。划分点T_a表示为：

$T_a=\{\frac{a^i+a^{i+1}}{2}|1≤i≤n-1\}$

也就是说，把区间[a^i,a{i+1})的中位点作为候选划分点。可将划分点设为该属性在训练集中出现的不大于中位点的点，例如中位点是0.5185，可将0.518作为划分点。此时：

$Gain(D,a)=max_{t∈T_a}Gain(D,a,t)=max_{t∈T_a}Ent(D)-\sum_{\lambda∈\{-,+\}}{\frac{|D^\lambda|}{|D|}Ent(D^\lambda_t)}$

作为示例，在原有的西瓜数据集上增加“密度”和“含糖量”两个属性：

Pic22.png

对于属性“密度”，将这17个属性值从小到大进行排序，得到{0.243, 0.245, 0.343, 0.36, 0.403, 0.437, 0.481, 0.556, 0.593, 0.608, 0.634, 0.639, 0.657, 0.666, 0.697, 0.719, 0.774}，然后相邻的两个值取平均值作为划分点，得到16个划分点：{0.244 0.294 0.3515 0.3815 0.42 0.459 0.5185 0.5745 0.6005 0.621 0.6365 0.648 0.6615 0.6815 0.708 0.7465}。然后计算属性“密度”的信息增益为0.262，对应的划分点为0.381。

同理对属性“含糖率”，得到信息增益为0.349，对应划分点为0.126。

结合前面的离散数据的6个信息增益，总体上，还是以信息增益最大的“纹理”作为根结点，此后结点划分过程递归进行，得到如下决策树：

Pic23.png

需要注意的是，不同于离散属性，连续属性可以作为其后代结点的划分属性。

4.4.2 缺失值处理

有的样本数据集缺失属性值数据，如果直接去掉有缺失值的样本，那么会造成极大的浪费。含有缺失值的样例集的处理方法如下：

Pic24.png

以属性“色泽”为例，该属性无缺失值的样本集包括\vec{D}={2,3,4,6,7,8,9,10,11,12,14,15,16,17},计算其信息熵为：

$Ent(\vec{D})=-\sum_{k=1}^{2}\vec{p}_k\log_2\vec{p}_k\\=-(\frac{6}{14}\log_2\frac{6}{14}+\frac{8}{14}\log_2\frac{8}{14})=0.985$

“色泽”属性包含3个属性值“青绿”、“乌黑”及“浅白”，分别计算其信息熵为：

$Ent(\vec{D}^1)=-(\frac{2}{4}\log_2\frac{2}{4}+\frac{2}{4}\log_2\frac{2}{4})=1.000\\Ent(\vec{D}^2)=-(\frac{4}{6}\log_2\frac{4}{6}+\frac{2}{6}\log_2\frac{2}{6})=0.918\\Ent(\vec{D}^3)=-(\frac{0}{4}\log_2\frac{0}{4}+\frac{4}{4}\log_2\frac{4}{4})=0.000$

因此样本集\vec{D}上的属性“色泽”的信息增益为：

$Gain(\vec{D},色泽)=Ent(\vec{D})-\sum_{v=1}^{3}\vec{r}_vEnt(\vec{D}^v)\\=0.985-(\frac{4}{14}\times1.000+\frac{6}{14}\times0.918+\frac{4}{14}\times0.000)=0.306$

再求出样本集D上“色泽”属性的信息增益：

$Gain({D},色泽)=\rho\times Gain(\vec{D},色泽)=\frac{14}{17}\times0.306=0.252$

同样地，计算出所有属性在D上的信息增益：

$Gain(D,色泽)=0.252;Gain(D,根蒂)=0.171;Gain(D,敲声)=0.145;\\Gain(D,纹理)=0.424;Gain(D,脐部)=0.289;Gain(D,触感)=0.006;$

因此，以“纹理”作为根结点进行划分，按照3个属性值划分成3个子节点，分别包含7个、5个和3个样例。注意，由于第8个样例在“纹理”上缺乏属性值，因此将它们同时加入三个子节点里面，但其权重分别为7/15、5/15、3/15。第10个样例同理。

最终得到的决策树如下：

Pic25.png

4.5 多变量决策树

决策树所形成的分类边界有一个明显的特点，即轴平行，它的分类边界由若干个与坐标轴平行的分段组成。

例如，如下的西瓜数据集：

Pic26.png

对应的决策树及分类边界如下：

Pic27.png

这样的分类边界使得学习结果有很好的可解释性，但在学习任务的真实分类边界比较复杂时，必须使用很多段划分才能得到较好的近似，时间开销很大。如果能使用斜的边界，决策树模型将大为简化，例如下面的红色曲线：

Pic28.png

多变量决策树：可以实现斜着划分甚至更复杂划分的决策树。

在此类决策树中，非叶结点不再是单个属性，而是多个属性的线性组合，每个非叶结点都是\sum_{i=1}^{d}w_ia_i=t的线性组合。例如同样是对于上面的数据集，学得下面的多变量决策树，分类边界是：

Pic29.png

4.6 $scikit-learn$ 决策树

import graphviz
import pandas as pd
from sklearn import tree
from sklearn.datasets import load_wine
from sklearn.model_selection import train_test_split

wine = load_wine()
wine.data.shape  # 样本数据，(178, 13)
wine.feature_names  # 属性名，共13个属性
wine.target_names  # 三分类

pd.concat([pd.DataFrame(wine.data), pd.DataFrame(wine.target)], axis=1)  # 查看整个表的数据

Xtrain, Xtest, Ytrain, Ytest = train_test_split(wine.data,wine.target,test_size=0.3)  # 分出训练集及验证集

wine_tree = tree.DecisionTreeClassifier(criterion="entropy"
                                       ,random_state=10
                                       ,splitter="best"
                                       )
wine_tree = wine_tree.fit(Xtrain, Ytrain)
score = wine_tree.score(Xtest, Ytest)  # 验证分类准确率
score  # 0.926

# 画出决策树
dot_data = tree.export_graphviz(wine_tree
                                ,feature_names=wine.feature_names
                                ,class_names=wine.target_names
                                ,filled=True
                                ,rounded=True
)
graph = graphviz.Source(dot_data)
graph

[*zip(wine.feature_names, wine_tree.feature_importances_)]  # 查看各个属性的重要程度
'''
[('alcohol', 0.3105469459665367),
 ('malic_acid', 0.04914102355800148),
 ('ash', 0.021703756013797745),
 ('alcalinity_of_ash', 0.0),
 ('magnesium', 0.039325800285971386),
 ('total_phenols', 0.0),
 ('flavanoids', 0.36843622950210064),
 ('nonflavanoid_phenols', 0.014236961139536255),
 ('proanthocyanins', 0.0),
 ('color_intensity', 0.049683554827815106),
 ('hue', 0.025088839146435126),
 ('od280/od315_of_diluted_wines', 0.06244719458516666),
 ('proline', 0.059389694974638946)]
 可见，有3个属性未派上用场
 '''

graph.render('tree.png', view=True)

tree.png

决策树

决策树