《机器学习》-- 第四章 决策树
正文共：8270 字 151 图 预计阅读时间：21 分钟
前文推送
- MIT线性代数相关资源汇总
- 《机器学习》--第一章
- 《机器学习》--第二章
- 《机器学习》--第三章（上）
- 《机器学习》--第三章（下）
本文目录：
- 4.1 决策树基本流程
- 4.2 划分选择
- 4.3 剪枝处理
- 4.4 连续值与缺失值处理
- 4.5 决策树算法对比
第四章 决策树
4.1 决策树基本流程
决策树(decision tree，亦称为判定树)是一类常见的机器学习方法。
以二分类任务为例，我们希望从给定训练数据集学得一个模型用以对新实例进行分类，这个把样本分类的任务，可看作对“当前样本属于正类吗?"这个问题的“决策”或“判定”过程，顾名思义，决策树是基于树结构来进行决策的，这恰是人类在面临决策问题时一种很自然的处理机制。
例如，我们要对“这是好瓜吗?"这样的问题进行决策时，通常会进行一系列的判断或“子决策"：我们先看“它是什么颜色?"，如果是“青绿色”，则我们再看“它的根蒂是什么形态?" ，如果是“蜷缩" ，我们再判断“它敲起来是什么声音?" ，最后，我们得出最终决策:这是个好瓜。决策过程如图4.1所示：
4.1 decision_tree_4.1
显然，决策过程的最终结论对应了我们所希望的判定结果，例如“是”或“不是”好瓜；决策过程中提出的每个判定问题都是对某个属性的“测试” ，例如“色泽=?" “根蒂=?" ；每个测试的结果或是导出最终结论，或是导出进一步的判定问题，其考虑范围是在上次决策结果的限定范围之内，例如若在“色泽=青绿”之后再判断“根蒂=?" ，则仅在考虑青绿色瓜的根蒂。
一般一颗决策树包含：一个根节点、若干个内部节点和若干个叶子节点，易知：
* 每个叶节点存放一个类别，对应于决策结果。
* 每个非叶节点表示一个特征/属性测试。
* 每个节点包含的样本集合通过属性测试被划分到子节点中，每个分支代表这个特征/属性在某个值域上的输出。
* 根节点包含样本全集。
* 从根节点到每个叶节点的路径对应了一个判定测试序列（决策序列）。
决策树学习的目的是为了产生一颗泛化能力强，即处理未见实例（样本）能力强的决策树（判定规则），其基本流程遵循简单且直观的“分而治之”（divide-and-conquer）策略，如图4.2所示
4.2 desicion_tree_algorithm
显然，决策树的生成是一个递归过程，在决策树基本算法中，有三种情形会导致递归返回:
- (1) 当前结点包含的样本全属于同一类别，无需划分；
- (2) 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；
- (3) 当前结点包含的样本集合为空，不能划分。
在第(2)种情形下，我们把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别；在第(3)种情形下，同样把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别。
注意这两种情形的处理实质不同：情形(2)是在利用当前结点的后验分布，而情形(3)则是把父结点的样本分布作为当前结点的先验分布。
一句话总结，对于决策树这种树形结构，可以认为是 if-then（如果…那么…） 规则的集合，是以实例为基础的归纳学习。基本思想是自顶向下，以信息增益（或信息增益比，基尼系数等）为度量构建一颗度量标准下降最快的树，每个内部节点代表一个属性的测试，直到叶子节点处只剩下同一类别的样本。
决策树的学习包括三个重要的步骤，特征选择，决策树的生成以及决策树的剪枝：
- 特征选择：特征选择方法有信息增益，信息增益比，基尼系数等。
- 生成过程：通过计算信息增益或其它指标，选择最佳特征。从根结点开始，递归地产生决策树，不断的选取局部最优的特征，将训练集分割成能够基本正确分类的子集。（如图4.1所示）
- 剪枝过程：有预剪枝和后剪枝两类方法。
4.2 划分选择
从 图4.2 的决策树算法过程可以看出：决策树学习的关键在于第8行，即如何选择最优划分属性，不同的划分属性得出不同的分支结构，从而影响整颗决策树的性能。一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的 “纯度”(purity) 越来越高。决策树最常用的量化纯度的指标有三种：信息熵，信息增益比，基尼系数，分别对应了ID3, C4.5, CART 三种决策树算法。
4.2.1 信息增益
ID3（Iterative Dichotomiser，迭代二分器）算法使用信息增益为准则来选择划分属性，“信息熵”(information entropy)是度量样本集合纯度（随机变量不确定度）的常用指标，假定当前样本集合
中第
类样本所占比例为
，则样本集合
的信息熵定义为：
的值越小（最小值为0，最大值为
），则样本集
的纯度越高。其中
表示样本类别数——最终分类数，如{好瓜，坏瓜}，则值为2。
信息论之父克劳德·香农，总结了信息熵的三条性质：
- 单调性，即发生概率越高的事件，其所携带的信息熵越低。极端案例就是“太阳从东方升起”，因为为确定事件，所以不携带任何信息量。从信息论的角度，认为这句话没有消除任何不确定性。
- 非负性，即信息熵不能为负。这个很好理解，因为负的信息，即你得知了某个信息后，却增加了不确定性是不合逻辑的。
- 累加性，即多随机事件同时发生存在的总不确定性的量度是可以表示为各事件不确定性的量度的和。写成公式就是事件
同时发生，两个事件相互独立，则
,那么信息熵为
香农从数学上，严格证明了满足上述三个条件的随机变量不确定性度量函数具有唯一形式：
其中
为常数，将其归一化之后即得到信息熵公式。 如果两个随机事件不独立，则满足
，其中
为互信息（mutual information），代表一个随机变量包含另一个随机变量的度量。
假定离散属性
有
个可能的取值
，通过
属性划分样本集
，则产生了
个分支结点，用
表示其中第
个分支结点，则该分支结点包含了
中所有在属性
上取值为
的样本，记为
。由式4.1我们即可计算该划分下的信息熵，并且易知：分支结点包含的样本数越多，表示该分支结点的影响力越大，则对分支结点根据样本数比例赋予权重
，即可计算出划分后相比原始数据集
获得的“信息增益”（information gain）
信息增益越大，表示使用该属性划分样本集
的效果越好，即使用该属性来进行划分所获得的纯度提升越大。因此 ID3 算法在递归过程中，每次选择最大信息增益的属性作为当前的划分属性，即在图4.2的算法流程的第8行中，选择属性
。
表4.1 西瓜数据集2.0
以表4.1中西瓜数据集2.0 为例，该数据集包含17个训练样例，显然,
，在决策树学习开始时，根结点包含
中的所有样例，其中正例占
，反例占
。于是，根据式(4.1)可计算出根结点的信息煽为
然后我们计算整个属性集
中 {色泽，根蒂，敲声，纹理，脐部，触感} 每个属性的信息增益，以属性”色泽“为例，它有3个可能的取值，即 {青绿，乌黑，浅白} ，使用该属性（色泽）对数据集
进行划分，即得到3个子集：
(色泽=青绿)，
(色泽=乌黑)，
(色泽=浅白) 。
子集
包含编号为 {1， 4， 6， 10， 13， 17} 的6个样例，其中正例占
，反例占
;
包含编号为 {2， 3， 7， 8， 9， 15} 的6个样例，其中正、反例分别占 p1=4/6，
;
包含编号为 {5， 11， 12， 14， 16}的5个样例，其中正、反例分别占
，
。根据 式(4.1) 可计算出用“色泽”划分之后所获得的3个分支结点的信息熵为
再根据 式4.2 即可得到属性“色泽”的信息增益
类似地，我们可以计算得到其他5个属性的信息增益和它们各自属性值分支结点的信息熵
显然，属性“纹理”的信息增益最大，因此我们选择其作为划分属性。图4.3 给出了基于纹理对根结点进行划分的结果，各分支结点所包含的样例子集显示在结点中。
fig4.3
然后，决策树学习算法将对每个分支结点进一步划分，即对应于图4.2中第11行到第15行的步骤。
以图4.3中第一个分支结点（纹理=清晰）为例，样例集为
，可用属性集 {色泽，根蒂，敲声，脐部，触感} 。
表4.1.1 纹理=清晰样本子集
基于该样例集计算各属性的信息增益和它们各自属性值分支结点的信息熵
这里的样本集的信息熵我们在之前已经计算过，即
“根蒂”、“脐部”、“触感” 3个属性均取得了最大的信息增益，可任选其中之一作为纹理=清晰结点下的划分属性，类似的，对其他每个分支结点继续进行上述操作，最终得到的决策树如图4.4所示
fig4.4
4.2.2 信息增益率
信息增益指标存在一个问题，就是偏向于取值数目较多的属性，即 V 值较大的属性，例如：对于表4.1 的西瓜数据集2.0的编号列，样本集
将会被划分为
个分支，每个分支只有一个样本，这样划分后每一个分支的信息熵为零，十分纯净，但是对分类毫无用处。
C4.5(Classifier 4.5) 算法使用“增益率”（gain ratio）来选择最优划分属性，来避免信息增益准则对可取值数目较多的属性的偏好导致的不利影响。
因为信息增益率对于可取值数目较少的属性有所偏好（与信息增益相反），因此 C4.5 算法首先计算出所有属性的信息增益，然后取其中高于平均水平的多个候选属性，计算这些候选属性的信息增益率，最后选择信息增益率最高的属性作为最优划分属性，增益率定义为：
其中，
称为属性
的固有值（intrinsic value），属性
的可能取值数目越多（V越大），则通常
的值越大。
可以发现固有值的定义与信息熵的定义是一样的！实际上，属性的固有值就是将该属性作为目标列计算的信息熵，但是因为我们的目标列不是该属性，因此我们称为特征熵。
对于西瓜数据集2.0 我们可以得到各个属性的固有值
4.2.3 基尼指数
CART（Classification and Regression Tree）决策树使用“基尼指数”（Gini index）来选择划分属性，基尼指数反映的是从样本集
中随机抽取两个样本，其类别标记不一致的概率，因此
越小越好，即数据集的纯度越高。数据集
的基尼指数：
进而，使用属性
划分后的基尼指数为：
于是，我们在候选属性集合 A 中，选择使得划分后基尼指数最小的属性作为最优划分属性即可，即
4.3 剪枝处理
从决策树的构造流程中我们可以直观地看出：不管怎么样的训练集，决策树总是能很好地将各个类别分离开来，这时就会遇到之前提到过的问题：过拟合，即太依赖于训练样本，以致于把训练集自身的一些特点当作所有数据都具有的一般性质。剪枝（pruning）则是决策树算法对付过拟合的主要手段，剪枝的策略有两种如下：
* 预剪枝（prepruning）：在构造的过程中先评估，再考虑是否分支。
* 后剪枝（postpruning）：在构造好一颗完整的决策树后，自底向上，评估非叶结点分支的必要性。
评估指的是性能评估（2.2节），即评估决策树的泛化性能。预剪枝表示在构造数的过程中，对一个结点考虑是否分支时，首先计算决策树不分支时在测试集上的性能，再计算分支之后的性能，若分支对性能没有提升，则选择不分支（即剪枝）。后剪枝则表示在构造好一颗完整的决策树后，从最下面的结点开始，考虑该结点分支对模型的泛化性能是否有提升，若无提升则剪枝，即将该结点标记为叶子结点，类别标记为其包含样本最多的类别。
本节假定采用留出法，即预留一部分数据为验证集以进行性能评估。对于表4.1的西瓜数据集2.0，随机划分为2部分，编号为{1,2,3,6,7,10,14,15,16,17}的样例组成训练集，编号为{4,5,8,9,11,12,13}的样例组成验证集。采用4.2.1节的信息增益准则进行划分属性选择，则可将训练集训练生成 如图4.5 所示的决策树。
fig4.5
4.3.1 预剪枝
基于信息增益准则，在计算了训练集（编号为{1,2,3,6,7,10,14,15,16,17}的样例）各特征的信息增益后，选择脐部作为划分属性。
fig4.6
在划分之前，所有样例集中在根结点，若不进行划分，则根据算法4.2 第6行，该结点将被标记为叶结点，其类别标记为训练样例数最多的类别，假设我们将这个叶结点标记为“好瓜”，用验证集{4, 5, 8, 9, 11, 12, 13} 对这个单结点决策树进行评估，则编号为{4, 5, 8}的样例被分类正确，另外4个样例分类错误，于是，验证集精度为 (3/7)*100% =42.9%。（因为训练集正负样本数相等，因此将划分前的根节点标记为“坏瓜”，也是可以的，相对应的验证集精度为57.1%）
在用属性“脐部”划分之后，图4.6中的结点②、③、④分别包含编号为{1, 2, 3, 14}、{6, 7, 15, 17} 、{10, 16}的训练样例，因此这3个结点分别被标记为叶结点“好瓜”、“好瓜”、“坏瓜”。此时，验证集中编号为{4, 5, 8, 11, 12}的样例被分类正确，验证集精度为 (5/7)*100% = 71.4% > 42.9%于是，用“脐部”进行划分得以确定。
然后，决策树算法应该对结点②进行划分，基于信息增益准则，将挑选出划分属性“色泽” ，然而，在使用“色泽”划分后，编号为{5}的验证集样本分类结果会由正确转为错误，使得验证集精度下降为57.1%，于是，预剪枝策略将禁止结点②被划分。 对结点③，最优划分属性为“根蒂”，划分后验证集精度仍为71.4%。这个划分不能提升验证集精度，于是，预剪枝策略禁止结点3被划分。 对结点④，其所含训练样例已属于同一类，不再进行划分。
于是，基于预剪枝策略所生成的决策树如图4.6所示，其验证集精度为71.4%，这是一棵仅有一层划分的决策树，亦称“决策树桩” (decision stump)。 对比图4.6和图4.5可看出，预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了训练时间开销和测试时间开销，但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高；预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。
4.3.2 后剪枝
后剪枝先从训练集生成一颗完整的决策树（如图4.5所示）。
后剪枝首先考察图4.5中的结点⑥。若将其领衔的分支剪除，则相当于把⑥替换为叶结点，替换后的叶结点包含编号为{7, 15}的训练样本，于是，该叶结点的类别标记为“好瓜”，此时决策树的验证集精度提高至57.1%。于是，后剪枝策略决定剪枝。 然后考察结点⑥，若将其领衔的子树替换为叶结点，则替换后的叶结点包含编号为{6, 7, 15}的训练样例，叶结点类别标记为“好瓜” ，此时决策树验证集精度仍为57.1%，于是，可以不进行剪枝。(实际上，根据奥卡姆剃刀准则，通常会进行剪枝) 对结点②，若将其领衔的子树替换为叶结点，则替换后的叶结点包含编号为{1, 2, 3, 14}的训练样例，叶结点标记为“好瓜”.此时决策树的验证集精度提高至71.4%，于是，后剪枝策略决定剪枝。 对结点③和①，若将其领衔的子树替换为叶结点，则所得决策树的验证集精度分别为71.4%与42.9%，均未得到提高。于是它们被保留。 最终，基于后剪枝策略所生成的决策树如图4.7所示，其验证集精度为71.4%。
fig4.7.png
对比图4.7和图4.6可看出，后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树，但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。
4.4 连续值与缺失值处理
下述方法为 C4.5决策树算法中采用。
4.4.1 连续值二值划分
对于连续值的属性，若每个取值作为一个分支则显得不可行，因此需要进行离散化处理，常用的方法为二分法（bi-partition），基本思想为：给定样本集
与连续属性
，二分法试图找到一个划分点 t 将样本集
在属性
上分为 ≤t 与＞t ，样本集即可分为子集
和
，其中
包含在属性
上取值不大于 t 的样本，而
则包含大于 t 的样本 。显然，当取值为
中任意值所产生的划分结果是相同的。
* 首先将α的所有取值按升序排列，所有相邻属性的均值作为候选划分点（n-1个，n为α所有的取值数目）。
* 计算每一个划分点划分集合D（即划分为两个分支）后的信息增益。
* 选择最大信息增益的划分点作为最优划分点。
可知 n-1 个候选划分点集合为
于是，我们可以像离散属性值一样来考虑这些划分点，选取最优的划分点进行样本集合的划分。对式4.2 进行稍加改造即可得到可应用于连续值属性的信息增益
其中，
是样本集
基于划分点 t 二分后的信息增益。于是，我们可选择使得
最大化的划分点。
现在西瓜数据集2.0上增加两个连续属性"密度"和"含糖率"，得到表4.3所示的西瓜数据集3.0。
表4.3 西瓜数据集3.0
对属性“密度”，在决策树学习开始时，根结点包含的17个训练样本在该属性上取值均不同，根据式(4.7)，该属性的候选划分点集合包含 16 个候选值:
由式(4.8)可算出属性“密度”的信息增益为0.262, 对应于划分点0.381。
对属性“含糖率” ，其候选划分点集合也包含 16 个候选值:
，类似的，根据式(4.8)可计算出其信息增益为0.349，应于划分点0.126。
最终生成如图4.8 所示决策树
fig4.8
需要注意的是，与离散不同之处在于，若当前结点划分属性为连续属性，该属性还可以作为其后代的划分属性。比如在图4.8中决策树的左树分支，对于"密度≤0.381?"分支，不会禁止子结点使用"密度≤0.294?" 。
4.4.2 缺失值处理
现实中常会遇到不完整的样本，即某些属性值缺失。有时若简单采取剔除，则会造成大量的信息浪费。如表4.4所示的西瓜数据集2.0a 。因此有必要考虑利用有缺失属性值的训练样例来进行学习。
表4.4 西瓜数据集2.0a
而在属性值缺失的情况下需要解决两个问题：（1）如何选择划分属性；（2）给定划分属性，若某样本在该属性上的值缺失，如何划分到具体的分支上。
给定训练集
和属性
，令
表示
在属性
上没有缺失值的样本子集。对于问题（1），显然可以根据
来判断属性
的优劣。假定属性有 V 个值
，令
表示在属性
上取值为
的样本子集，
表示
中属于第
类
的样本子集，则显然有
, 假定为样本集中的每一个样本
都赋予一个权重
，根结点中的权重初始化为 1 ，并定义：
可知，
表示无缺失样本所占的比例。
可知，
表示无缺失样本中
类所占的比例。
可知，
表示无缺失样本中在属性
上取值为
的样本所占的比例。
显然可以得到，
对于问题（1）：通过在样本集
中选取在属性α 上没有缺失值的样本子集
，计算在该样本子集上的信息增益，最终的信息增益等于该样本子集划分后信息增益乘以样本子集占样本集的比重
。即：
其中，
。
一句话总结就是，以属性非缺失的样本子集作为训练样本集，计算其信息增益，最后将信息增益以样本子集非缺失样本数对总样本数按比例进行折价。
对于问题（2）：若该样本
在属性α 上的值已知，则将
划入与其取值对应的子结点，且权值保持为
；则将若该样本在属性α 上的值缺失，则将该样本以不同的权重（按每个分支所含样本比例）划入到所有分支结点中。该样本在分支结点中的权重变为：
一句话总结就是，未缺失则权重不变，缺失则按比例（权重）划分到所有分支。
以西瓜数据集2.0a 为例，演示缺失数据集下的信息增益的计算方法。
在学习开始时，根结点包含样本集
中全部17个样例，各样例的权值均为1，以属性“色泽”为例，该属性上无缺失值的样本子集
包含编号为 {2,3,4,6,7,8,9,10,11,12,14,15,16,17} 的14个样例，即
基于式4.12 可以得到样本子集的信息熵
对于色泽，有三个不同的属性值，因此 V = {"乌黑","青绿","浅白"}, 于是可得按属性值划分后的信息熵
于是我们可以得到信息增益为
最后基于上述计算方式，继续计算其他特征以及属性划分下的信息增益，得到如图4.9所示的决策树。
fig4.9
4.5 决策树算法对比
本文项目地址：
https://github.com/firewang/lingweilingyu/blob/master/contents/Machine_Learning_Zhi-Hua_Zhou.md
参考网址：
- 周志华 著. 机器学习, 北京: 清华大学出版社, 2016年1月.