决策树算法整理

决策树（decision tree）是一种常见的分类和回归算法，也是性能较好的提升树算法（boosting tree）的基本分类器。

在分类问题中，决策树模型是以树的结构，基于特征来对样本进行分类决策的，其内部结点表示一个特征，叶结点表示一个类别。它可以看作是if-then 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。

决策树的损失函数为正则化的极大似然函数，学习策略是以损失函数为目标函数的最小化。其学习过程通常分为三个步骤：特征选择、决策树的生成和决策树的修剪。

决策树学习的算法通常是递归地选择最优特征，不断对数据集进行分割，构建决策树。主要的算法有ID3、C4.5和CART算法。

本文从四个方面整理和决策树模型有关的知识：

1、熵、信息增益和基尼指数

2、ID3算法和C4.5算法

3、决策树剪枝

4、CART算法之回归树与分类树

 

一、熵、信息增益和基尼指数

在决策树模型中，信息增益、信息增益比和基尼指数是特征选择的指标，分别用于ID3、C4.5和CART算法的特征选择问题。下面从熵的概念开始，一步步理解这三个重要的概念。

1、熵与条件熵

（1）熵的概念

熵（entropy）这个概念来自于信息论，是对随机变量不确定性的度量。考虑一个取有限个值的离散随机变量X，其概率分布为p(X=x_i) =p_i。首先怎么度量看到X取某个具体值x_i的信息呢？信息依赖于概率分布p(X)，低概率事件有更高的信息量，于是信息定义为：h(X)=-logp(X)（一般以2为底）。那么熵可以看做是随机变量X的平均信息量：

熵只依赖于X的概率分布，而与X的取值无关，故X的熵也记作H(p)。熵越大，随机变量的不确定性就越大，信息量也越大。特别的，当p_i=0时，定义p_i×logp_i =0。

（2）条件熵的概念

设有随机变量（X,Y），其联合概率分布为：

那么条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性，定义为在X给定的条件下，Y的条件概率分布的熵对X的数学期望：

在现实中，我们只能通过统计数据来估计熵和条件熵中的概率，进而得到熵和条件熵的估计值，相应的估计值称为经验熵和经验条件熵。

 2、信息增益

有了经验熵和经验条件熵的定义，那么信息增益（information gain）就定义为二者之差，表示在训练集中得知特征X的信息而使得类Y的不确定性减少的程度，也称为特征与类之间的互信息。信息增益的定义为：特征A对训练集D的信息增益g(D, A)，是集合D的经验熵H(D)和特征A给定条件下D的经验条件熵H(D|A)之差，即

在特征A给定的条件下对数据集D进行分类时，信息增益表示由于特征A而使得对数据集D的分类的不确定性减少的程度。不同的特征往往具有不同的信息增益，而信息增益大的特征具有更强的分类能力。在实际运用时，逐一计算每个特征对数据集D的信息增益，然后选择信息增益最大的特征进行分类。ID3算法便是根据信息增益准则来选择特征的。

3、信息增益的计算方法

设训练集为D，|D|表示其样本容量。设有K个类C_k ，|C_k|为类C_k的样本个数。设特征A有n个不同的取值a_i ，将D划分为n个子集D_i ，|D_i|为该子集的样本个数。子集D_i中属于类 C_k  的样本集合为 D_ik ，|D_ik|为D_ik的样本个数。那么信息增益的计算方法为：

（1）计算数据集D的经验熵H(D)：

（2）计算特征A对数据集D的经验条件熵H(D|A)：

（3）计算信息增益：

g(D,A) = H(D) - H(D|A)

4、信息增益比

信息增益准则偏向取值较多的特征，当特征的取值较多时，该特征的信息增益往往比较大。极端的情况就是以编号作为特征，每个特征值都对应一个样本，此时信息增益是最大的，但是不具备泛化能力。

因此使用信息增益比来校正这一问题，信息增益比 = 信息增益 * 惩罚参数，惩罚参数大时，特征的属性值较少。C4.5算法就是根据信息增益比来选择特征的。

以训练数据集D的经验熵H(D)的倒数作为惩罚参数，则信息增益比g_R(D,A)为：

而信息增益比准则又倾向于取值较少的特征，因此C4.5并不是直接选择信息增益比最大的特征，而是在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益比最高的特征。   

5、基尼指数

（1）基尼指数（Gini index）的定义

基尼指数表示在样本集合中一个随机选中的样本被分错的概率，基尼指数越大，则表示集合中被选中的样本被分错的概率越大。基尼指数 = 样本被选中的概率 × 样本被分错的概率。

在分类问题中，假设样本集合D中有K个类，样本点属于第k类的概率为p_k，则该概率分布的基尼指数就是：

特殊的，在二分类问题中，基尼指数为：Gini(p) = 2p(1-p)。

而给定样本集合D，|C_k|为第k类样本子集C_k的样本数，样本点属于第k类的概率p_k=(|C_k| / |D|)，所以基尼指数为：

（2）CART中的基尼指数

CART是个二叉树，也就是使用某个特征将样本划分为两个集合：1. 等于给定的特征值的样本集合D₁ ； 2. 不等于给定的特征值的样本集合D_2。实际上是对拥有多个取值的特征的二值处理。

在CART算法中，样本集合D根据特征A是否取某一可能的值a被分割为D₁和D₂两个部分，即：

那么在特征A的条件下，集合D的基尼指数定义为：

基尼指数Gini(D)表示集合D的不确定性，而基尼指数Gini(D,A)表示经过A=a分割后集合D的不确定性。基尼指数越大，样本集合的不确定性越大。

因此运用基尼指数进行特征选择时，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。

 

二、ID3算法和C4.5算法

1、ID3算法的核心是在决策树各结点上应用信息增益准则选择特征，递归地构建决策树。

2、决策树的ID3生成算法：

（1）从根节点开始，计算所有特征的信息增益，选择信息增益最大的特征作为结点的特征，由该特征的不同属性值建立子结点；

（2）对子节点递归地调用以上方法，构建决策树；

（3）直到所有特征的信息增益非常小或者没有特征可以选择为止。

3、递归返回的条件：

（1）数据集中所有实例都属于同一类了；

（2）当前的特征集为空集；

（3）特征的信息增益小于阈值。

4、由于ID3算法只有树的生成，没有树的剪枝，所以容易产生过拟合。

5、C4.5算法的分类决策过程与ID3算法类似，不同在于用信息增益比来选择特征。

 

三、决策树的剪枝

1、为什么要剪枝

决策树的剪枝是指将生成的树进行简化的过程，把已生成的树裁掉一些子树或叶结点，并将其根结点或父节点作为新的叶结点。

对决策树进行剪枝是为了解决过拟合问题。因为决策树生成算法递归产生决策树，在学习时过多考虑如何提高对训练数据的正确分类，从而构建出了过于复杂的决策树，因此要考虑决策树的复杂度，对模型进行简化。

2、怎样剪枝

（1）决策树的整体损失函数

决策树的剪枝往往通过极小化决策树整体的损失函数来实现。设树T的叶结点个数为|T|，t是树T的叶结点，该叶结点有N_t个样本点，其中k类样本点的个数为N_tk，H_t(T)是叶结点t上的经验熵，α≥0是惩罚参数，则决策树的整体损失函数为：

其中经验熵H_t(T)为：

令损失函数中的第一项为C(T)：

于是损失函数整理为：

C(T)表示模型与训练数据的拟合程度，|T|表示模型的复杂度，参数α权衡二者的重要性。较大的α使得模型倾向于选择简单的树，α=0意味着只考虑模型对训练数据的拟合程度，不考虑模型复杂度。

可见决策树生成学习的是局部模型，而决策树剪枝学习的是整体模型。

（2）如何判断是否需要剪枝

剪枝算法就是让考虑了模型复杂度的损失函数极小化，等价于用正则化的极大似然估计进行模型选择。

在剪枝操作中，设一组叶结点回缩到父结点之前与之后的整体树分别为T_B和T_A，其对应的损失函数值分别为C_α(T_B)和C_α(T_A)，如果C_α(T_B) ≥ C_α(T_A)，则进行剪枝，将父结点变成新的叶结点。递归地进行操作，直至得到损失函数最小的子树。

 

四、CART算法

CART(classification and regression tree)模型，叫做分类与回归树，既可以用于分类也可以用于回归。它假设决策树是二叉树，每个内部结点特征的取值只取“是”和“否”，左分支取值为“是”，右分支取值为“否”。这样的决策树递归地二分每个特征，在给定输入随机变量X的条件下输出随机变量Y的条件概率分布。

CART算法也是由特征选择、决策树生成和决策树剪枝三个步骤组成。

对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。

1、回归树的生成

假设X与Y分别为输入和输出变量，并且Y是连续变量，训练数据集为D={(x₁,y₁), (x₂,y₂), ..., (x_n,y_n)}。已将输入空间划分为M个单元R₁,R₂,...,RM，并且在每个单元R_m上有一个固定的输出值c_m。

I(•)表示指示函数。则回归树模型表示为：

用平方误差来表示回归树在单元R_m上对训练数据的预测误差，用平方误差最小的准则来求解每个单元上的最优输出，那么由最小二乘法可知，单元R_m上的输出的c_m的最优值是R_m上所有输入实例x_i对应的输出y_i的均值，即：

于是具体步骤如下：

第一步：选择第j个变量x^(j)和它取的值s，作为切分变量和切分点，将输入空间分为两个区域：

第二步：求解下式得到最优切分变量j和最优切分点s：

第三步：用选定的最优对（j, s）划分区域并决定输出值：

第四步：对每个区域重复上述划分过程，直到满足停止条件。于是将输入空间划分为了M个区域R₁, R₂, ..., R_M，生成决策树：

 2、分类树的生成

分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。

具体步骤如下：

第一步：样本集合D根据每一个特征A，对其可能的取值a，根据A=a是否成立，被分割为D1和D2两个部分，

然后计算在特征A条件下，集合D的基尼指数：

第二步：对所有可能的特征A及它们所有可能的切分点a，选择基尼指数最小的特征及其切分点作为最优特征与最优切分点。依最优特征和最优切分点，从现结点生成两个子结点，并分配训练数据集。

第三步：对两个子结点递归地调用第一步和第二步，直至满足停止条件，生成决策树。停止条件包括：特征集合为空，样本集的基尼指数小于预定阈值，结点的样本个数小于预定阈值。

 

CART的剪枝：略。

 

 五、其他

在《机器学习之十一问支持向量机(SVM)》中，提到了支持向量机无法处理缺失值的问题，而决策树可以。本来打算整理一下这个问题，结果发现真正要理解和说清楚，得手动计算缺失值的处理过程，篇幅太长。这个问题已经有博客整理得比较清楚了，就多看看博客喽。

 

 

 

参考资料：

1、李航：《统计学习方法》

2、周志华：《机器学习》

3、决策树--信息增益，信息增益比，Geni指数的理解：https://www.cnblogs.com/muzixi/p/6566803.html