机器学习第六章决策树(decision tree)

资料参考来源：

清华大学出版社-周志华《机器学习》第四章决策树

基本概念

决策树（decision tree）是一种常见的机器学习方法，它基于树形结构来对样本进行决策，恰似人类面临决策问题时大脑的相当自然的一种处理机制。

举个例子，当我们要判断一个西瓜是否是好瓜的时候，我们就要对“这是好瓜吗？”这个问题进行一系列的判断或“子决策”，像是先看它的颜色，然后看它的纹路，在试试它的触感…等等等等，这个决策过程我们可以用图形表示：

决策过程的最终结论将会对应我们的判断结果，而决策过程中的每一次判定都是对某个属性的“测试”，如“色泽=？”“根蒂=？”；每个测试的结果要么导出最终结果，要么导出下一个判定问题，并且，每一次判定都会在上一次决策所划分好的范围内进行判定，例如，在“色泽=青绿”之后判定“根蒂=？”就是在判断青绿色的瓜的根蒂。

基本流程

一般来说，一棵决策树包含一个根节点，若干个内部节点和若干个叶节点。

叶节点对应于决策结果，其它每个节点则对应于一个属性测试
每个节点包含的样本集合根据属性测试的结果被划分到子节点中
根节点包含样本全集
从根节点到每个叶节点的路径对应了一个判定测试序列

决策树学习的目的是为了产生一棵泛化能力强，即能够处理未知示例能力强的决策树。决策树的基本流程遵循简单且直观的“分而治之”（divide-and-conquer）策略：

在决策树的基本算法中，有三种情况会导致递归返回：

当前节点包含的样本全部属于同一类别，无需返回
当前属性集为空，或是所有样本在所有属性上取值相同，无法划分
当前节点包含的样本集合为空，不能划分

第（2）种情况出现时，我们把当前节点标记为叶节点，并将其类别设定为该节点所含样本最多的类别。例如，假设我们在西瓜例子中将西瓜所有的属性都测试了一遍，但有3个西瓜的这些属性取值完全相同（色泽相同，根蒂相同，纹路相同……），在无法得到更多属性的情况下我们无法对其进行判断分类，那么这个时候，就取三个瓜中最多的那个类别作为叶节点：像是有2个好瓜1个坏瓜，那么我们就设定当前节点的导出结果为“好瓜”。
第（3）种情况出现时，我们同样将当前节点标记为叶节点，但将其类别设定为其父节点所含样本最多的类别。（这与第（2）种情形的处理方式很相似，不同的是，情形（2）利用的是当前节点的后验分布，情形（3）利用的是父节点的样本分布作为当前节点的先验分布）

选择最优划分方式

决策树的关键就在于如何选择划分方式。一般而言，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别（举西瓜例，即尽可能让好瓜都和好瓜分一起，坏瓜都和坏瓜分一起），即节点的纯度（purity）越来越高。

信息增益

信息熵

定义公式

信息熵(information entropy)是度量样本集合纯度最常用的一种指标。假定当前样本集合D中第k类样本所占的比例为 $p_k(k=1,2...,\mid Y\mid)$ ， $(其中\mid Y\mid表示测试的最终结果数，\\ 以西瓜例子为例，就是“好瓜”和“坏瓜”，因此\mid Y\mid=2)$ 则D的信息熵定义为：

$Ent(D)=-\sum^{\mid Y\mid}_{k=1}p_klog_2p_k$

注意：

计算信息熵时约定：若 $p=0,则plog_2p=0$
Ent(D)的最小值为0，最大值为 $log_2\mid Y\mid$

Ent(D)的值越小，则D的纯度越高。

来源与推导

此处资料参考：[维基百科：熵 (信息论)](https://zh.wikipedia.org/wiki/%E7%86%B5_(%E4%BF%A1%E6%81%AF%E8%AE%BA)

熵的概念起源于物理学，用于度量一个热力学系统的无序度（混乱度）。而在信息世界，熵越高则表明能传输的信息越低（不确定性高），熵越低则表明传输的信息越多（不确定性低）。

要度量信息熵，我们先来看这样一个例子：

如果我们有一枚硬币，它出现正面和反面的机会均等，那么，它的结果不外乎两个：0（反面）或1（正面），这个时候，“抛一枚硬币观察正反面”这个事件的熵就是一比特（bit），因为结果只有两个并且互相独立。若进行n次独立试验，那么它的熵则为n，因为这个事件的熵可以用长度为n的比特流来表示。

依据Boltzmann’s H-theorem，香农把随机变量X的熵值H定义如下，其值域为 $\{x_1,...x_n\}$ ：

$H(x)=E[l[X]]=E[-ln(P(X))]$

其中l[X]表示随机变量X的信息量，公式为：

$l[X]=-ln(p(X))$

这里p(X)为随机变量X的概率密度函数，对数部分除了取 $ln$ ，也可以取 $log_2,log_{10}$ ，这三个都是比较常见的取法，分别代表了信息熵的三个单位“nat”(对应对数底e)，“bit”（对应对数底2），“Hart”（对应对数底10）

并且信息量具有可加性，两个随机变量的概率密度函数相乘即为两个随机变量的信息量相加：

$设随机变量X，Y，则\\ p(X)p(Y)=l(X)+l(Y)$

因此，要计算一个系统中有限样本的信息熵时，可以采用公式：

$H(X)=\sum_iP(X_i)l(X_i)=-\sum_iP(x_i)log_bP(x_i)$

信息增益

假定离散属性a有V个可能的取值 $\{a^1,a^2...a^V\}$ ，若使用a来对样本集合D进行划分，则会产生V个分支节点。其中，第v个分支节点包含了D中所有在属性a上取值为 $a^v$ 的样本，我们这里将其记为 $D^v$ 。然后我们便可以根据信息熵的计算公式计算 $D^v$ 的信息熵，再考虑到不同的分支节点所包含的样本数不同，给分支节点赋予权重 $\frac{\mid D^v\mid}{\mid D\mid}$ （即让样本数越多的分支节点能够造成的影响越大）。于是，我们就可以计算出用属性a对样本集D进行划分所得的信息增益(information gain):

$Gain(D,a)=Ent(D)-\sum^V_{v=1}\frac{\mid D^V\mid}{\mid D\mid}Ent(D^v)$

一般而言，信息增益越大，则意味着用属性a来进行划分所获得的“纯度提升”就越大。

因此我们可以用信息增益来对决策树的划分属性进行选择，我们选择属性的公式就是：

$a_*=arg~max_{a∈A}Gain(D,a)$

即选择能够使信息增益达到最大的属性。

我们可以以西瓜数据集2.0为例：

这个数据集包含17个训练样本，并且 $\mid Y\mid=2$ 。再决策学习开始时，我们先根据根节点所包含的D中的所有样例（其中正例（好瓜）占 $p_1=\frac{8}{17}$ ，反例（坏瓜）占 $p_2=\frac{9}{17}$ ）计算根节点的信息熵：

然后，我们再计算当前属性集合中每个属性的信息熵。我们以属性“色泽”为例，它分为3个可能的取值 $\{青绿，乌黑，浅白\}$ ，然后根据这个属性，我们对样本进行三个划分： $D^1(色泽=青绿)，D^2（色泽=乌黑），D^3(色泽=浅白)$

子集 $D^1$ 包含编号 $\{1,4,6,10,13,17\}$ ，其中正例占 $p_1=\frac{3}{6}$ ，反例占 $\frac{3}{6}$ ，子集 $D^2$ 和 $D^3$ 以此类推，由此我们可以得到3个分支点的信息熵分别为：

然后我们就可以得到“色泽”的信息增益为：

类似的，我们得到其它信息熵的增益分别为：

我们可以观察得到，纹理的信息增益是最大的，因此，我们选择纹理作为下一步的划分属性。

下面是根据“纹理”对根节点进行划分的结果：

然后，决策树学习算法将对每个分支点进行下一步的划分，我们以分支节点（“纹理”=清晰）为例，基于该节点的样本集合 $D^1$ 计算出各属性的信息增益：

我们可以看到，“根蒂”、“脐部”、“触感”3个属性都取得了最大的信息增益，因此，我们可以任选其中之一作为划分属性。类似的，我们对每个节点进行上述操作，最后可以得到决策树：

增益率

实际上，信息增益准则对可取值数目较多的属性有所偏好（即属性取值较多容易使信息增益偏大）。为了减少这种偏好可能带来的不利影响，著名的C4.5决策树算法[Quinlan,1993]引入了增益率(gain ratio)。增益率定义为：

其中

$IV(a)$ 称为属性a的固有值（intrinsic value）。属性a的可能取值数目越多（V越大）， $IV(a)$ 的值通常也会越大。

但是，需要注意的是，增益率准则又会对可取值数目较少的属性有所偏好，因此，C4.5算法采用了一个启发式：

$先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。$

基尼系数

CART决策树使用基尼系数(Gini index)来选择划分属性。数据集D的纯度可以用基尼值来度量：

直观来说，Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此，Gini(D)越小，则数据集D的纯度越高。

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

于是，我们在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即

$a_*=arg~min_{a∈A}Gini_index(D,a)$

剪枝

基本概念

剪枝(pruning)是决策树算法对付“过拟合”的主要手段。

剪枝的基本策略有两个，一个是预剪枝(prepruning)，一个是后剪枝(postpruning)。

预剪枝是指在决策树生成过程中，在每个节点划分前先对这个节点做一个估计，判断这个节点的划分是否能够带来决策树泛化性能的提升，然后根据结果判断是否要划分节点。

后剪枝则是先从训练集生成一棵完整的树，然后自下而上地对非叶节点进行考察，判断若将该节点替换为叶节点能否带来决策树泛化性能的提升。

判断泛化性能留出法

那么在学习剪枝之前，我们就还需要先知道如何判断决策树的泛化性能。这里我们介绍一个方法，留出法：即预留一部分数据作为“验证集”以进行性能评估。

例如对于我们之前所举的西瓜例子，我们用留出法可以将它化为下面两个部分（上部分为训练集，下部分为验证集）：

假定我们采用信息增益准则来划分属性，然后生成了下面这样的一棵决策树（为了便于讨论，我们对图中的部分加了编号）：

这是一棵基于上表生成的未剪枝决策树。

预剪枝

流程

基于信息增益准则，我们优先选取“脐部”来对训练集进行划分，划分完成后，它会产生3个分支，如图：

为了判断我们是否有必要进行这个划分，我们就需要来对它划分前后的泛化性能进行估计：

首先我们假设我们没有进行划分，然后将该节点标记为叶节点，这个叶节点的类别为父节点中训练样本数最多的类别（在本例中即为根节点中样本最多的类别，若两者相同则随机取其一，这里我们假设是“好瓜”）
接着我们用验证集来对这个单节点决策树进行评估（在本例中，我们得到，编号{4，5，8}的样本分类正确，另外4个样本分类错误，因此验证集精度为 $\frac{3}{7}*100\%=42.9\%$ ）
然后我们再用选定的属性对节点进行划分，并将划分出来的节点按照其包含最多的类别划分为叶节点（这里就是用“脐部属性”对训练样本进行划分，得到图中节点编号2，3，4分别包含训练样本{1，2，3，4}，{6，7，15，17}，{10，16}，并且这三个节点还被分别标记为叶节点“好瓜”，“好瓜”，“坏瓜”）
代入验证集，检查划分后的验证精度。（在例子中得到验证集中编号为{4,5,8,11,12}的样本被分类正确，验证集精度为 $\frac{5}{7}*100\%=71.4\%>42.9\%$ ）
得出结果，判断是否划分（决定用脐部对节点进行划分）

重复这个过程，我们再对图中编号为2的节点进行划分，先基于信息增益准则挑出属性“色泽”。然而，在使用“色泽”划分后，编号为 $\{5\}$ 的验证集样本分类结果会由正确转为错误，导致验证集精度下降为57.1%，于是，我们不对图中编号为2的节点进行划分。

对图中编号为4的节点，由于其所含样例已属于同一类，不再进行划分。

于是，我们可以生成如图所示的决策树：

（没错，和上面那幅就是一样的）

该决策树的验证精度为 $71.4\%$ ，这种仅有一层划分的决策树我们成为决策树桩(decision stump)

利弊分析

对比仅根据信息准则划分和加入了预剪枝划分的决策树示意图，我们可以看出，预剪枝让决策树的很多分支没有展开。这不仅降低了过拟合的风险，而且还能显著减少决策树的训练时间开销和测试时间开销。

但另一方面，有些分支的当前划分或许不能提升甚至降低泛化性能，但在其基础上进行的后续划分却也有可能提高泛化性能。预剪枝基于贪心本质将这些分支禁止展开，会给决策树带来欠拟合的风险。

为了解决这个问题，我们就需要引入后剪枝。

后剪枝

基本流程

后剪枝先从训练集中生成一棵完整的决策树，例如下面基于训练集表根据信息增益准则生成的决策树表，并且，我们还可以知道，该决策树的验证集精度为 $42.9\%$ 。

对这个已经生成的决策树应用后剪枝，我们会先考察图中的节点6：

首先我们将其替换为叶节点，然后根据给节点中的集合所包含的训练样本决定该叶节点的类别（本例中替换后的叶节点包含编号{7,15}，因此类别为“好瓜”）
计算替换叶节点后的验证精度（本例中为 $57.1\%$ ），与未替换前（ $42.9\%$ ）做对比，决定是否剪枝。（本例中我们发现精度提高，于是进行剪枝）

然后我们再用同样的流程考察节点5，我们发现，替换前与替换后的精度都是57.1%，于是我们决定不剪枝。（这是书中例子的做法，但事实上，根据奥卡姆剃刀准则（“如无必要，勿增实体”），剪枝后的模型会更好，书中例子这样做仅是为了绘图方便，因而采取不剪枝的保守做法）

接着，我们再考察节点2，发现剪枝后精度提升到71.4%，遂进行剪枝。

对节点3和节点1，计算求得的精度分别为71.4%和42.9%，均未提高，于是将其保留。

最后，我们得到剪枝后的决策树：

该决策树的验证精度为71.4%。

利弊分析

将该图与预剪枝后的决策树示意图进行对比（然而实际上我们若应用奥卡姆剃刀准则，两幅图应该是一样的），后剪枝决策树通常比预剪枝保留了更多的分支。并且，一般情况下，后剪枝决策树欠拟合的风险很小，泛化性能也往往优于预剪枝的决策树。然而，后剪枝过程是在完全生成决策树之后才进行的，并且还要自底向上地对树中的所有非节点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大的多。

连续与缺失值

连续值处理

到目前为止，我们经讨论了基于离散属性来生成的决策树，但事实上，我们经常会遇到属性值为连续的情况。

一般应对这种情况，我们都会选择将其离散化，（关于这个，我在朴素贝叶斯算法一章中介绍过）。最简单地离散化策略便是采用二分法(bi-oartition)来对连续属性进行处理，这也是C4.5决策树算法中采用的机制。

二分法

给定样本集D和连续属性a，假定a在D上出现了n个不同的取值，将这些值从小到大进行排序，记为 $\{a^1,...,a^n\}$ 。基于划分点t可将D分为子集 $D^-_t$ 和 $D^+_t$ ，其中 $D^-_t$ 包含那些在属性a上取值不大于t的样本，而 $D^+_t$ 则包含那些在属性a上取值大于t的样本。

显然，对相邻的属性取值 $a^i$ 与 $a^{i+1}$ 来说，t在区间 $[a^i,a^{i+1})$ 中取任意值所产生的划分结果相同。因此对连续属性a，我们可以只考察包含n-1个元素的候选划分点（注意划分点在两个候选值中间，因此是n-1个）集合：

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

即把区间 $[a^i,a^{i+1})$ 的中位点 $\frac{a^i+a^{i+1}}{2}$ 作为候选划分点。然后我们就可以像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集合的划分。（也可以将划分点设为该属性在训练集中出现的不大于中位点的最大值，从而使得最终决策树使用的划分点都在训练集中出现过），例如：

其中Gain(D,a,t)是样本集D基于划分点t二分后的信息增益。于是，我们就可以选择使Gain(D,a,t)最大化的划分点。

为了表示清楚，我们来举一个详细的例子，这一次，我们给我们之前的西瓜例子加上两个连续属性：“密度”和“含糖率”：

下面我们用这个数据集来生成一棵决策树：

首先我们对属性“密度”的16个（n-1个）候选划分点计算出它的信息增益为0.262，对应于划分点0.381。（计算过程如下，先截取所有的候选划分点 $\{0.244,0.294,0.351,...,0.746\}$ ，然后应用信息增益公式，从左至右依次求得划分后的信息增益，挑出使得信息增益最大的划分点对节点进行划分）
对属性“含糖率”也同样是先算出所有的候选划分点，然后计算每个点的信息增益，得到最大信息增益为0.349，从而求得划分点0.126。

于是我们得到上述各属性的信息增益为：

于是我们将“纹理”作为根节点的划分属性，此后递归执行划分过程，最终生成决策树：

需要注意的是，如果当前节点划分属性为连续属性，那么这个属性还可以作为其后代节点的划分属性（也就是说，假设我们用“密度”给节点进行了一次划分，划分得到的新节点也还是可以用“密度”进行划分）

缺失值处理

基本流程

现实中我们常常会遇到不完整的样本，尤其是在属性数目多的情况下，大量的样本往往会出现缺失值。

这种情况往往会给我们的分析造成很大的麻烦。下面我们来举个例子：

要对付这些缺失值，我们要解决两个问题：

如何在属性值缺失的情况下进行划分属性的选择？
给定划分属性，若样本在该属性上缺失，如何对样本进行划分？

给定训练集D和a，令 $\tilde{D}$ 表示D中在属性a上没有缺失值的样本子集。对问题（1），我们可以根据 $\tilde{D}$ 来判断属性a的优劣。假定属性a有V个可取值 $\{a^1...a^V\}$ ，令 $\tilde{D}^v$ 表示集合 $\tilde{D}$ 中在属性a上取值为 $a^v$ 的样本子集， $\tilde{D}_k$ 表示集合 $\tilde{D}$ 中属于第k类 $(k=1,2,...\mid Y\mid)$ 的样本子集，则我们可以得到：

$\tilde{D}=\bigcup^{\mid Y\mid}_{k=1}\tilde{D}_k\\ \tilde{D}=\bigcup^V_{v=1}\tilde{D}^v$

假定我们为每个样本 $x$ 赋予一个权重 $w_x$ ，并定义：

（在决策树学习开始阶段，根节点中各样本的权重初始化为1）

直观地看，对于属性a，值ρ表示无确实值样本所占的比例， $\tilde{p}_k$ 表示无缺失值样本中第k类所占的比例， $\tilde{r}_v$ 则表示无缺失值样本中在属性a上取值 $a^v$ 的样本所占的比例。显然，

$\sum^{\mid Y\mid}_{k=1}\tilde{p}_k=1\\ \sum^{V}_{v=1}\tilde{r}_v=1$

基于上述定义，我们于是便可以将信息增益的计算式推广为：

其中由信息熵的计算式，有

接着，对问题（2），

若样本x在划分属性a上的取值已知，则将x划入与其取值对应的子节点，且样本权值在子节点中保持为 $w_x$ ，
若样本x在划分属性a上的取值未知，则将x同时划入所有的子节点，且样本权值在与属性值 $a^v$ 对应的子节点中调整为 $\tilde{r}_v·w_x$ ；直观地看，这就是让一个样本以不同的概率划入到不同的子节点中去。

例子

C4.5算法就是用了上述解决方案。现在，让我们以前面那个有缺失的西瓜数据集作为例子来生成一棵决策树：

1.首先我们知道，在学习开始时，根节点包含样本集D中全部17个样本，各样本的权值均为1。

2.计算属性无缺失样本子集 $\tilde{D}$ 的信息熵（以“色泽”属性为例，该属性上无缺失值的样例子集 $\tilde{D}$ 包含编号为 $\{2,3,4,6,7,8,9,10,11,12,14,15,16,17\}$ 的14个样例。显然， $\tilde{D}$ 的信息熵就为：

3.计算该属性无缺失样本子集 $\tilde{D}$ 中所有取值的信息熵（令 $\tilde{D}^1,\tilde{D}^2,\tilde{D}^3$ 分别表示在属性“色泽上”取值为“青绿”“乌黑”以及“浅白”的样本子集，有：

）

4.计算该属性无缺失样本子集 $\tilde{D}$ 上的信息增益（因此，样本子集 $\tilde{D}$ 上属性“色泽”的信息增益为：

）

5.计算样本集D上该属性的信息增益(于是，样本集D上属性“色泽”的信息增益为：

)

6.以2~5步骤类推，求出所有属性的信息增益(类似地，我们可以计算出所有属性在D上的信息增益：

）

观察各属性的信息增益，我们可以很容易地发现“纹理”在所有属性中取得了最大的信息增益，于是我们将其用于对根节点进行划分。划分结果是编号 $\{1,2,3,4,5,6,15\}$ 的样本进入“纹理=清晰”分支，编号 $\{7,9,13,14,17\}$ 的样本进入“纹理=稍糊”分支，编号 $\{11,12,16\}$ 的样本进入“纹理=模糊”分支，且样本在各子节点中的权重保持为1.需要注意的是，编号为 $\{8\}$ 的样本在属性“纹理”上出现了缺失，因此它将被同时划入三个分支，但权重在三个子节点中分别调整为 $\frac{7}{15},\frac{5}{15},\frac{3}{15}$ （即三个分支分别包含的关于该属性无缺失值的样本占该节点对应属性所有无缺失样本的比例），编号为 $\{10\}$ 的样本有类似划分结果。

上述划分过程递归进行，最终生成决策树：

多变量决策树

引子

若我们把每个属性视为空间中的一个坐标轴，则d各属性描述的样本就对应了d维空间中的一个数据点，对样本分类则意味着在这个空间中找不同类样本之间的分类边界。

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

以去掉离散值的西瓜数据集为例：

我们将它作为训练集可以得到如下所示的决策树：

这颗决策树的对应分类边界就会是：

显然，分类边界的每一段都是和坐标轴平行的。这样的分类边界使得学习结果有较好的可解释性，因为每一段划分都直接对应了某个属性取值。但是，在学习任务的真实分类边界比较复杂时，必须使用多段划分才能获得较好的近似：

此时的决策树将会相当复杂，由于需要进行大量的属性测试，预测时间的开销也会相当大。

多变量决策树

因此，若能使用斜的划分边界，就像上面那幅图中的红色线段一样，决策树的模型就能够大幅度简化。

多变量决策树(multivariate decision tree ,也称“斜决策树”,oblique decision tree)就是能实现这样的“斜划分”甚至于更复杂划分的决策树。

以实现斜划分的多变量决策树为例，在此类决策树中，非叶节点不再是仅对应某个属性而是对属性的线性组合进行测试；换句话说，每个非叶节点就是一个形如 $\sum^d_{i=1}w_ia_i=t$ 的线性分类器。

其中， $w_i$ 是属性 $a_i$ 的权重， $w_i$ 和t可在该节点所含的样本集和属性集上学得。于是，与传统的单变量决策树(univariate decision tree)不同，在多变量决策树的学习过程中，不是为每一个非叶节点寻找一个最优划分属性，而是试图找到一个合适的线性分类器。例如，对于我们上图所举例的仅包含“密度”和“含糖量”属性的西瓜数据集，我们可以生成这样一棵决策树：

它的分类边界如图：

ZyBlog

机器学习第六章决策树(decision tree)

基本概念

基本流程

选择最优划分方式