决策树
martin
- 决策树
- 基本概念
- ID3
- C45
- CART
- 剪枝处理
- 前剪枝
- 后剪枝
基本概念
一般的，一颗决策树包含一个根节点、若干个内部节点和若干个叶节点，所以决策树相当于多叉树。叶节点对应于决策结果，其他每个结点则对应与一个属性测试，每个节点包含的样本集合根据属性测试的结果被分到子节点中。决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力的决策树，基本思想遵循“分而治之”的策略。
决策树的生成是一个递归过程。在决策树算法中有三种情形会导致递归返回：
- 当前节点包含的样本全部属于同一个类别，无需划分。
- 当前属性集为空，或是所有样本在所有属性集上取值相同，无法划分。此时，把当前节点标记为叶节点，并将其类别设定为该节点所含样本最多的类别。
- 当前节点包含的样本集合为空，不能划分。此时，同样把当前节点标记为叶节点，但将其类别设定为其父节点所含样本最多的类别。
注意：2和3不同，2是后验概率，3是把父节点的样本分布作为当前节点的先验概率。
下面给出一个决策树的例子：
决策树相当于对特征空间进行划分，如下：
也就是说，决策树的每条路径对应于特征空间的每个区域。对于决策树主要有以下几种：ID3，C4.5主要应用于分类任务；CART树，主要应用于预测任务，下面将逐个介绍。
ID3
对于之前给出的决策树的节点划分在ID3中有特定的方法，ID3中节点划分所衡量的指标是：信息增益。
信息熵：E(D)=−∑k=1ypklog2pk
特征a的信息增益：Gain(D,a)=E(D)−∑v=1v|Dv||D|E(Dv)
一般而言，信息增益越大，则意味着使用属性 α 来进行划分所获得的的“纯度提升”越大。因此，我们可用信息增益来进行决策树的划分属性选择。
给一个数据集，我们在这个数据集上来进行ID3决策树的生成：
| 编号 | 色泽 | 根蒂 | 敲声 | 纹理 | 脐部 | 触感 | 好瓜 |
|---|---|---|---|---|---|---|---|
| 1 | 青绿 | 蜷缩 | 浊响 | 清晰 | 凹陷 | 硬滑 | 是 |
| 2 | 乌黑 | 蜷缩 | 沉闷 | 清晰 | 凹陷 | 硬滑 | 是 |
| 3 | 乌黑 | 蜷缩 | 浊响 | 清晰 | 凹陷 | 硬滑 | 是 |
| 4 | 青绿 | 蜷缩 | 沉闷 | 清晰 | 凹陷 | 硬滑 | 是 |
| 5 | 浅白 | 蜷缩 | 浊响 | 清晰 | 凹陷 | 硬滑 | 是 |
| 6 | 青绿 | 稍蜷 | 浊响 | 清晰 | 稍凹 | 软粘 | 是 |
| 7 | 乌黑 | 稍蜷 | 浊响 | 稍糊 | 稍凹 | 软粘 | 是 |
| 8 | 乌黑 | 稍蜷 | 浊响 | 清晰 | 稍凹 | 硬滑 | 是 |
| 9 | 乌黑 | 稍蜷 | 沉闷 | 稍糊 | 稍凹 | 硬滑 | 否 |
| 10 | 青绿 | 硬挺 | 清脆 | 清晰 | 平坦 | 软粘 | 否 |
| 11 | 浅白 | 硬挺 | 清脆 | 模糊 | 平坦 | 硬滑 | 否 |
| 12 | 浅白 | 蜷缩 | 浊响 | 模糊 | 平坦 | 软粘 | 否 |
| 13 | 青绿 | 稍蜷 | 浊响 | 稍糊 | 凹陷 | 硬滑 | 否 |
| 14 | 浅白 | 稍蜷 | 沉闷 | 稍糊 | 凹陷 | 硬滑 | 否 |
| 15 | 乌黑 | 稍蜷 | 浊响 | 清晰 | 稍凹 | 软粘 | 否 |
| 16 | 浅白 | 蜷缩 | 浊响 | 模糊 | 平坦 | 硬滑 | 否 |
| 17 | 青绿 | 蜷缩 | 沉闷 | 稍糊 | 稍凹 | 硬滑 | 否 |
然后，我们要计算出当前属性集合 {色泽，根蒂，敲声，纹理，脐部，触感} 中每个属性的信息增益。
先计算根节点的信息熵：
E(D)=−∑k=12pklog2pk=−(817log2817+917log2917)=0.998
计算属性“ 色泽 ”的信息增益，它有3个可能取的值： {青绿，乌黑，浅白} ，分别记为：
D1(色泽=青绿) ，包含编号为 {1,4,6,10,13,17} 6个样例，于是 p1=36,p2=36 ，
D2(色泽=乌黑) ，包含编号为 {2,3,7,8,9,15} 6个样例，于是 p1=46,p2=26 ，
D3(色泽=浅白) ，包含编号为 {5,11,12,14,16} 5个样例，于是 p1=15,p2=45 ，
有了上面的信息就可以求该特征的每个属性的信息熵了：
E(D1)=−36log2(36)−36log2(36)=1.000
E(D2)=−46log2(46)−26log2(26)=0.918
E(D3)=−15log2(15)−45log2(45)=0.722
于是，可以计算出属性色泽的信息增益：
Gain(D,色泽)=E(D)−∑v=13|Dv||D|E(Dv)=0.998−(617×1.000+617×0.918+517×0.722)=0.109
类似的，我们可以计算出其他属性的信息增益：
Gain(D,根蒂)=0.143
Gain(D,敲声)=0.141
Gain(D,纹理)=0.381
Gain(D,脐部)=0.289
Gain(D,触感)=0.006
显然，属性纹理的信息增益最大，于是它被选为划分属性，给出基于纹理对根节点进行划分的结果：
然后，决策树学习算法将对每个分之节点做进一步划分。以上图第一个分支节点(纹理=清晰)为例，该节点包含的样例集合 D1 中有编号为 {1,2,3,4,5,6,8,10,15} 的9各样例，可用属性集合为 {色泽，根蒂，敲声，脐部，触感} ，少了一个纹理属性。基于 D1 计算出各个属性的信息增益：
先计算第一个分支节点的信息熵：
E(D1)=−∑k=12pklog2pk=−(79log279+29log229)=0.764
计算属性“ 色泽 ”的信息增益，它有3个可能取的值： {青绿，乌黑，浅白} ，分别记为：
D1(色泽=青绿) ，包含编号为 {1,4,6,10} 4个样例，于是 p1=34,p2=14 ，
D2(色泽=乌黑) ，包含编号为 {2,3,8,15} 4个样例，于是 p1=34,p2=14 ，
D3(色泽=浅白) ，包含编号为 {5} 1个样例，于是 p1=11,p2=01=0 ，
有了上面的信息就可以求该特征的每个属性的信息熵了：
E(D1)=−34log2(34)−14log2(14)=0.811
E(D2)=−34log2(34)−14log2(14)=0.811
E(D3)=−11log2(11)−0×log2(0)=0
于是，可以计算出属性色泽的信息增益：
Gain(D1,色泽)=E(D1)−∑v=13|Dv||D|E(Dv)=0.764−(49×0.811+49×0.811+0)=0.043
类似的，我们可以计算出其他属性的信息增益：
Gain(D1,根蒂)=0.458
Gain(D,敲声)=0.331
Gain(D,脐部)=0.458
Gain(D,触感)=0.458
根蒂，脐部，触感3个属性均取得了最大的信息熵增益，可任选其中之一作为划分属性，于是在第一个分支上划分后的决策树如下图：
重复上述操作即可得如下图的最终决策树结果：
C4.5
实际上，ID3的信息增益划分法对可取数值较多的属性有所偏好，为减少这种偏好可能带来的不利影响，C4.5算法不采用信息增益，取而代之的是信息增益率来选择最优划分特征属性。信息增益率定义为：
Gainraio(D,a)=Gain(D,a)IV(a)
其中，
IV(a)=−∑v=1v|Dv||D|log2|Dv||D|
IV(a)称为属性 a 的“固有值”。属性a的可能值数目越多(即V越大)，则IV(a)的值通常会越大。例如，对于上表的西瓜数据集，有：
IV(触感)=−1217log21217−517log2517=0.874(v=2)
IV(色泽)=−617log2617−617log2617−517log2517=1.580(v=3)
IV(编号)==4.088(v=17)
与ID3决策树一样，同是选择最大的值作为最优划分。
CART
CART决策树是一棵二叉树，内部节点特征取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。CART决策树使用“基尼系数”来选择划分属性。基尼系数的定义如下：
Gini(D)=∑k=1ypk(1−pk)=1−∑k=1kp2k
那么对于属性 a 其基尼系数即为：
Gini(D,a)=∑v=1v|Dv||D|Gini(Dv)
直观来说，Gini(D)反映了从数据集 D 中随机抽取两个样本，其类别标记不一致的概率。因此，Gini(D)越小，则数据集D的纯度越高。于是，对于属性集合 A 中，选择那个使得划分后基尼系数最小的属性作为最优划分属性。
| 编号 | 年龄 | 工作 | 房子 | 信贷 | 类别 |
|---|---|---|---|---|---|
| 1 | 青年 | 否 | 否 | 一般 | 否 |
| 2 | 青年 | 否 | 否 | 好 | 否 |
| 3 | 青年 | 是 | 否 | 好 | 是 |
| 4 | 青年 | 是 | 是 | 一般 | 是 |
| 5 | 青年 | 否 | 否 | 一般 | 否 |
| 6 | 中年 | 否 | 否 | 一般 | 否 |
| 7 | 中年 | 否 | 否 | 好 | 否 |
| 8 | 中年 | 是 | 是 | 好 | 是 |
| 9 | 中年 | 否 | 是 | 非常好 | 是 |
| 10 | 中年 | 否 | 是 | 非常好 | 是 |
| 11 | 老年 | 否 | 是 | 非常好 | 是 |
| 12 | 老年 | 否 | 是 | 好 | 是 |
| 13 | 老年 | 是 | 否 | 好 | 是 |
| 14 | 老年 | 是 | 否 | 非常好 | 是 |
| 15 | 老年 | 否 | 否 | 一般 | 否 |
求特征A1(年龄)的基尼系数：
Gini(D,青年)=515[1−(252+352)]+1015[1−(7102+3102)]=0.44
Gini(D,中年)=515[1−(352+252)]+1015[1−(6102+4102)]=0.48
Gini(D,老年)=515[1−(452+152)]+1015[1−(5102+5102)]=0.44
由于Gini(D,青年)和Gini(D,老年)相等且最小，所以都可以作为年龄的最优切分点。
接着求工作，房子的基尼系数：
Gini(D,有工作)=515[1−(552)]+1015[1−(4102+6102)]=0.32
Gini(D,没工作)=1015[1−(4102+6102)]+515[1−(552)]=0.32
Gini(D,有房子)=615[1−(662)]+915[1−(392+692)]=0.27
Gini(D,没房子)=915[1−(392+692)]+615[1−(662)]=0.27
所以对工作和房子分别取0.32和0.27。接着求信贷的基尼系数：
Gini(D,一般)=0.36
Gini(D,好)=0.47
Gini(D,非常好)=0.32
Gini(D,非常好)最小，所以信贷非常好作为最优切分点。
最后，在年龄(Gini(D,青年)=0.44)，工作(Gini(D,有工作)=0.32)，房子(Gini(D,有房子)=0.27)，信贷(Gini(D,非常好)=0.32)中，房子的基尼系数最小，所以选择房子作为最有特征，有房子作为其最优切分点。于是根节点生出两个子节点，一个是叶节点，对另一个节点继续使用以上方法在年龄，工作，信贷中选择 最优特征 及 最优划分点
剪枝处理
剪枝是决策树学习算法对付“过拟合”的主要手段。决策树剪枝的基本策略有“前剪枝”和“后剪枝”。前剪枝是指在决策树生成过程中，对每个节点在划分前先进行预估，若当前节点的划分不能够带来决策树泛化性能的提升，则停止划分并将当前节点标记为叶节点。后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上的对非叶子节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能的提升，则将该子树替换为叶节点。在进行泛化能力考察时，采用的方法是从原数据集中留出“验证集”的方式进行验证。
给出一个数据集，已经分割为“训练集”和“验证集”：
训练集：
| 编号 | 色泽 | 根蒂 | 敲声 | 纹理 | 脐部 | 触感 | 好瓜 |
|---|---|---|---|---|---|---|---|
| 1 | 青绿 | 蜷缩 | 浊响 | 清晰 | 凹陷 | 硬滑 | 是 |
| 2 | 乌黑 | 蜷缩 | 沉闷 | 清晰 | 凹陷 | 硬滑 | 是 |
| 3 | 乌黑 | 蜷缩 | 浊响 | 清晰 | 凹陷 | 硬滑 | 是 |
| 6 | 青绿 | 稍蜷 | 浊响 | 清晰 | 稍凹 | 软粘 | 是 |
| 7 | 乌黑 | 稍蜷 | 浊响 | 稍糊 | 稍凹 | 软粘 | 是 |
| 10 | 青绿 | 硬挺 | 清脆 | 清晰 | 平坦 | 软粘 | 否 |
| 14 | 浅白 | 稍蜷 | 沉闷 | 稍糊 | 凹陷 | 硬滑 | 否 |
| 15 | 乌黑 | 稍蜷 | 浊响 | 清晰 | 稍凹 | 软粘 | 否 |
| 16 | 浅白 | 蜷缩 | 浊响 | 模糊 | 平坦 | 硬滑 | 否 |
| 17 | 青绿 | 蜷缩 | 沉闷 | 稍糊 | 稍凹 | 硬滑 | 否 |
验证集：
| 编号 | 色泽 | 根蒂 | 敲声 | 纹理 | 脐部 | 触感 | 好瓜 |
|---|---|---|---|---|---|---|---|
| 4 | 青绿 | 蜷缩 | 沉闷 | 清晰 | 凹陷 | 硬滑 | 是 |
| 5 | 浅白 | 蜷缩 | 浊响 | 清晰 | 凹陷 | 硬滑 | 是 |
| 8 | 乌黑 | 稍蜷 | 浊响 | 清晰 | 稍凹 | 硬滑 | 是 |
| 9 | 乌黑 | 稍蜷 | 沉闷 | 稍糊 | 稍凹 | 硬滑 | 否 |
| 11 | 浅白 | 硬挺 | 清脆 | 模糊 | 平坦 | 硬滑 | 否 |
| 12 | 浅白 | 蜷缩 | 浊响 | 模糊 | 平坦 | 软粘 | 否 |
| 13 | 青绿 | 稍蜷 | 浊响 | 稍糊 | 凹陷 | 硬滑 | 否 |
前剪枝
基于上述给出的不完整的训练集根据信息增益所生成的未剪枝的决策树如下：
在进行划分时，对于要剪枝的节点需注意的是： 其标记为训练样本中最多的类别 。
第一步：
对根节点进行剪枝预估，对于根节点来说，所有训练集入选，则根据训练集中类别最多的进行标记，因为训练集中好瓜坏瓜的数量相同，可以任选一个，于是将1节点标记为好瓜。对根节点剪枝后为如图所示：
其意思为，不管你新来的数据的任何属性，只要来一个西瓜我就认为是好瓜，那么这样剪枝在验证集上只有对 {4,5,8} 分类正确，对其余的四个分类错误，故其精度为： 37×100%=42.9% 。
在用属性“脐部”划分后2，3，4节点分别包含训练集中数据为 {1,2,3,14} ， {6,7,15,17} ， {10,16} ，故根据标记最多的来标记这些节点的准则，2,3,4分别被标记为“好瓜”，“好瓜”，“坏瓜”。此时，该模型为如下所示：
上面的图是在对“脐部”进行划分后的决策树，其在验证集上分别对 {4,5,8,11,12} 分类正确，于是它的精度为： 57×100%=71.4%>42.9% ，于是确定“脐部”的划分。
第二步：
对节点2进行剪枝预估。如果对2节点的“色泽”进行剪枝，则剪枝完后的决策树如图：
其在验证集上的精度为： 57×100%=71.4% ，如果不对2节点进行剪枝决策树如图：
那么未剪枝的决策树在验证集上对 {4,8,11,12} 分类正确，精度为 47×100%=57.1%<71.4% ，所以未剪枝使得决策树泛化能力下降，所以进行剪枝处理。
第三步：
对节点3进行剪枝预估。如果对3节点的“根蒂”进行剪枝，则剪枝完后的决策树如图：
其在验证集上的精度为： 57×100%=71.4% ，如果不对3节点进行剪枝决策树如图：
对于5节点，其包含训练集数据 {6,7,14} ，故将其标记为好瓜。那么此未剪枝处理的决策树在验证集对 {4,5,8,11,12} 分类正确，所以精度为 57×100%=71.4% ，所以划分没有提高泛化能力，故剪枝。
第四步：
对节点4进行剪枝预估。因为4节点已经为一个叶子节点了，所以不再进行剪枝。
于是最终决策树模型为：
可以看出，前剪枝是的决策树的很多分支没有展开，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间的开销。但另一方面，在有些分支上虽然暂时不能提高泛化能力，但是在该节点的后续节点上面却能提高泛化能力，而没有得以展开，所以带来了欠拟合的风险。
后剪枝
后剪枝先从训练集生成一棵完整的决策树，如图，该树在验证集上的精度为 42.9% 。
后剪枝考虑的策略是对已经生成的决策树自底向上对节点进行考量。
第一步:
首先考虑6节点，将其替换为叶节点，所以该节点包含的训练集数据为 {7,15} ，所以任选其中之一标记，于是将该节点标记为“好瓜”。此时，生成的局决策树为下图：
那么该树在验证集上的精度为 57.1%>42.9% ，所以决定剪枝。
第二步：
考虑5节点，如果对其进行剪枝，其节点包含训练集数据 {6,7,15} ，故将其标记为“好瓜”，如图:
此决策树在验证集上的精度为 57.1%=57.1% ，所以决定不剪枝。
第三步：
对节点2进行预估。在该节点的训练数据集为 {1,2,3,14} ，故将其标记为“好瓜”，如图：
此时在验证集上精度提高到 71.4% ，故决定剪枝处理。
第四步：
对节点3,1节点进行预估。均未能在验证集上提高精度。所以对3,1节点不进行剪枝处理。第三步生成的决策树即为最终的决策树。
[1]《机器学习》周志华
[2]《统计学习方法》李航