---

---

决策树是一种特殊的树形结构，一般由节点和有向边组成。其中，节点表示特征、属性或者一个类。而有向边包含有判断条件。如图所示，决策树从根节点开始延伸，经过不同的判断条件后，到达不同的子节点。而上层子节点又可以作为父节点被进一步划分为下层子节点。一般情况下，我们从根节点输入数据，经过多次判断后，这些数据就会被分为不同的类别。这就构成了一颗简单的分类决策树。结点有两种类型：内部结点和叶节点。内部节点表示一个特征或属性, 叶节点表示一个类。

决策树(Decision Tree)，又称为判定树，是一种以树结构(包括二叉树和多叉树)形式表达的预测分析模型。

一、决策树原理

1.1 决策树简介

决策树是一种常见的机器学习方法。比如西瓜书中的例子，我们判断一个西瓜好坏，可以先判断色泽，然后在判断根蒂，再判断敲声，然后就可以得出好瓜和坏瓜，以此构建的树称为决策树。如下：

决策树属于非参数学习算法、可以用于解决(多)分类问题，回归问题。 回归问题的结果，叶子结点的平均值是回归问题的解。

• 分类树–对离散变量做决策树
• 回归树–对连续变量做决策树

本文只讲用于分类的决策树。

1.2 基本概念

• 根节点：决策树具有数据结构里面的二叉树、树的全部属性；
• 非叶子节点 ：（决策点） 代表测试的条件，数据的属性的测试；
• 叶子节点 ：分类后获得分类标记；
• 分支： 测试的结果。

用决策树分类：从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点，此时每个子节点对应着该特征的一个取值，如此递归的对实例进行测试并分配，直到到达叶节点，最后将实例分到叶节点的类中。

• 决策树学习的目标：根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。
• 决策树学习的本质：从训练集中归纳出一组分类规则，或者说是由训练数据集估计条件概率模型。
• 决策树学习的损失函数：正则化的极大似然函数
• 决策树学习的测试：最小化损失函数
• 决策树学习的目标：在损失函数的意义下，选择最优决策树的问题。
• 决策树原理和问答猜测结果游戏相似，根据一系列数据，然后给出游戏的答案。

决策树的学习过程：

• 特征选择；
• 决策树生成: 递归结构, 对应于模型的局部最优；
• 决策树剪枝: 缩小树结构规模, 缓解过拟合, 对应于模型的全局选择。

二、数学知识

2.1 信息熵

“信息熵”information entropy是度量样本集合纯度最常用的一种指标，假定当前样本集合D中第k类样本所占比例为$p_k$（k=1,2,…,|y|）,则D的信息熵定义为：

End(D)的值越小，则D的纯度越高。在信息论中，常用$H$来表示信息熵。

举例说明：

比如说，明天会下雨吗？假设我们有历史上每天是否下雨的1000条记录，其中100天下雨，900天不下，那么我们这个系统的信息熵可以计算：

2.2 条件熵:

假设随机变量(X,Y), 其联合分布概率为$P(X=x_i,Y=y_i)=P_{ij},i=1,2,...,n;j=1,2,..,m$
则条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性, 其定义为X在给定条件下Y的条件概率分布的熵对X的数学期望：

2.3 信息增益

信息增益是指某个信息条件下，系统整体的熵减少了多少，也就是整体信息熵减去条件信息熵的结果。用属性a对样本集D进行划分所获得的“信息增益”information gain：

这里可能有些迷糊，下边构造决策树时，会有例题，跟着例题走，然后再回来看定义就比较清楚了。

三、ID3决策树

ID3决策树是原始的决策树，其依靠“信息增益“选择属性，称之为ID3决策树。当然，也有ID3、ID5决策树，下一章将讲解经典的C4.0决策树。

构造决策树主要由以下三部分：

• 特征选择；
• 决策树生成: 递归结构, 对应于模型的局部最优；
• 决策树剪枝: 缩小树结构规模, 缓解过拟合, 对应于模型的全局选择。

算法流程如下：

决策树的生成是一个递归过程，在决策树基本算法中，有三种情形会导致递归返回：

• （1）当前节点包含的样本全属于同一类别，无需划分；
• （2）当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别，利用了当前结点的后验分布；
• （3）当前结点包含的样本集合为空，不能划分，把当前结点标记为叶结点，但将其类别设定为其父节点所含样本最多的类别，这里是将父结点的样本分布作为当前结点的先验分布。

3.1 特征选择

上述算法中，对于属性 A = { a 1 , a 2 , . . . , a d } A=\{a_1,a_2,...,a_d\} A={a1​,a2​,...,ad​}的选择至关重要。希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”purity越来越高。其代表的是不同的类别在数据在总数据集中的熵的和，当样本集合越“纯”时，信息熵越小（信息熵的取值范围为0～log2(k)）。

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

“纯度”的大小用信息增益来描述，一般而言：信息增益越大，意味着使用属性a来进行划分所获得的“纯度”越大。

因此，可以使用信息增益来进行决策树的划分属性选择，选择属性：

以该准则（信息增益）来选择划分属性的决策树称之为ID3决策树。

举例说明：以西瓜数据集2.0为例

该数据集包含17个训练样本，用以学习一棵能预测没剖开的是不是好瓜的决策树。显然|Y|=2，在决策树开始时，根节点包含D中的所有的样例，其中正例占p1 = 8/17，反例占 p2 = 9/17。可以计算出根节点的信息熵为：

然后计算出当前属性的集合{色泽，根蒂，敲声，纹理，脐部，触感}中每个属性的信息增益。以”色泽“为例，有3个可能的取值：{青绿，乌黑，浅白}。使用该属性对D进行划分，则可以得到3个子集，分别记为：$D_1${色泽=青绿}，$D_2${色泽=乌黑}，$D_1${色泽=浅白}。

子集$D_1$包含编号为{1，4，6，10，13，17}的6个样本，其中正例占p1 = 3/6，反例占 p2 = 3/6；
子集$D_2$包含编号为{2，3，7，8，9，15}的6个样本，其中正例占p1 = 4/6，反例占 p2 = 1/6；
子集$D_1$包含编号为{5，11，12，14，16}的6个样本，其中正例占p1 = 1/5，反例占 p2 = 4/5；

则可以计算出用”色泽“划分之后所获得的三个分支节点的信息熵为：

则”色泽“的信息增益为：

类似的，计算出其他属性的信息增益：

可以看出：属性"纹理"的信息增益最大，于是将其被选为划分属性，如下图：

然后，决策树学习算法将对剩下的每个分支节点做进一步划分（”纹理“不再作为候选划分属性），以上图中的第一个分支节点（“纹理=清晰”）为例，该节点包含的样例集合$D_1$中有编号为{1，2，3，4，5，6，8，10，15}的9个样例，可以用属性集合为{色泽，根蒂，敲声，脐部，触感}。基于$D_1$计算出各属性的信息增益：

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

3.2 算法思路

输入的是m个样本，样本输出集合为D，每个样本有n个离散特征，特征集合即为A，输出为决策树T。

算法的过程为：

• 1)初始化信息增益的阈值$ϵ$；
• 2）判断样本是否为同一类输出$D_i$，如果是则返回单节点树$T$。标记类别为$D_i$；
• 3）判断特征是否为空，如果是则返回单节点树$T$，标记类别为样本中输出类别$D$实例数最多的类别；
• 4）计算$A$中的各个特征（一共n个）对输出D的信息增益，选择信息增益最大的特征$A_g$；
• 5）如果$A_g$的信息增益小于阈值$ϵ$，则返回单节点树$T$，标记类别为样本中输出类别$D$实例数最多的类别；
• 6）否则，按特征$Ag$的不同取值$A_{gi}$将对应的样本输出D分成不同的类别$Di$。每个类别产生一个子节点。对应特征值为$Agi$。返回增加了节点的数$T$；
• 7）对于所有的子节点，令$D=D_i,A=A-A_g$递归调用2-6步，得到子树$T_i$并返回。

3.3 算法不足

ID3算法虽然提出了新思路，但是还是有很多值得改进的地方。

• a）ID3没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
• b）ID3采用信息增益大的特征优先建立决策树的节点。很快就被人发现，在相同条件下，取值比较多的特征比取值少的特征信息增益大，此时分类精度会大打折扣。比如一个变量有2个值，各为1/2，另一个变量为3个值，各为1/3，其实他们都是完全不确定的变量，但是取3个值的比取2个值的信息增益大。如何校正这个问题呢？
• c） ID3算法对于缺失值的情况没有做考虑
• d） 没有考虑过拟合的问题

ID3 算法的作者昆兰基于上述不足，对ID3算法做了改进，这就是C4.5算法，也许你会问，为什么不叫ID4，ID5之类的名字呢?那是因为决策树太火爆，他的ID3一出来，别人二次创新，很快 就占了ID4， ID5，所以他另辟蹊径，取名C4.0算法，后来的进化版为C4.5算法。下面我们就来聊下C4.5算法

四、C4.5决策树算法

上一节我们讲到ID3算法有四个主要的不足，一是不能处理连续特征，第二个就是用信息增益作为标准容易偏向于取值较多的特征，最后两个是缺失值处理的问和过拟合问题。昆兰在C4.5算法中改进了上述4个问题。

4.1 处理连续特征

C4.5的思路是将连续的特征离散化。

比如m个样本的连续特征A有m个，从小到大排列为$a_1,a_2,...,a_m$,则C4.5取相邻两样本值的平均数，一共取得m-1个划分点，其中第i个划分点$T_i$表示为：$T_i=\frac{a_i+a_{(i+1)}}{2}$。对于这m-1个点，分别计算以该点作为二元分类点时的信息增益。选择信息增益最大的点作为该连续特征的二元离散分类点。比如取到的增益最大的点为$a_t$,则小于$a_t$的值为类别1，大于$a_t$的值为类别2，这样我们就做到了连续特征的离散化。要注意的是，与离散属性不同的是，如果当前节点为连续属性，则该属性后面还可以参与子节点的产生选择过程。

4.2 C4.5决策树特征选取

对于第二个问题，信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，C4.5决策树算法不直接使用信息增益，而是使用增益率（gain ratio）来选择最优划分属性。

增益率定义为：
$$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$$

其中：
$$IV(a)=-\sum _{v=1}^V\frac{|D^v|}{|D|}lo{g}_2\frac{|D^v|}{|D|}$$

称为属性a的“固有值”。属性a的可能取值数目越多（即V越大），则IV(a)的值通常越大。例如，对西瓜数据集2.0，有 IV(触感)=0.874（V=2）， IV(色泽)=10580（V=3），IV(编号)=4.088（V=17）。

增益率准则对可取值数目较少的属性有多偏好，因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

4.3 处理缺失值

对于第三个缺失值处理的问题，主要需要解决的是两个问题，一是在样本某些特征缺失的情况下选择划分的属性，二是选定了划分属性，对于在该属性上缺失特征的样本的处理。

对于第一个子问题，对于某一个有缺失特征值的特征A。C4.5的思路是将数据分成两部分，对每个样本设置一个权重（初始可以都为1），然后划分数据，一部分是有特征值A的数据D1，另一部分是没有特征A的数据D2。然后对于没有缺失特征A的数据集D1来和对应的A特征的各个特征值一起计算加权重后的信息增益比，最后乘上一个系数，这个系数是无特征A缺失的样本加权后所占加权总样本的比例。

对于第二个子问题，可以将缺失特征的样本同时划分入所有的子节点，不过将该样本的权重按各个子节点样本的数量比例来分配。比如缺失特征A的样本a之前权重为1，特征A有3个特征值A1,A2,A3。 3个特征值对应的无缺失A特征的样本个数为2,3,4.则a同时划分入A1，A2，A3。对应权重调节为2/9,3/9, 4/9。

4.4 过拟合问题

对于过拟合问题，C4.5引入了正则化系数进行初步的剪枝，下一节说明。

五、决策树C4.5算法的不足

C4.5虽然改进或者改善了ID3算法的几个主要的问题，仍然有优化的空间。

• 1）由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5的剪枝方法有优化的空间。思路主要是两种，一种是预剪枝，即在生成决策树的时候就决定是否剪枝。另一个是后剪枝，即先生成决策树，再通过交叉验证来剪枝。后面在下篇讲CART树的时候我们会专门讲决策树的减枝思路，主要采用的是后剪枝加上交叉验证选择最合适的决策树。
• 2）C4.5生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。
• 3）C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。
• 4）C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。如果能够加以模型简化可以减少运算强度但又不牺牲太多准确性的话，那就更好了。

这4个问题在CART树里面部分加以了改进。所以目前如果不考虑集成学习话，在普通的决策树算法里，CART算法算是比较优的算法了。scikit-learn的决策树使用的也是CART算法。