决策树是如何选择特征和分裂点？

缘起

在解决回归和分类问题的时候，一般会使用Random Forest、GBDT、XGBoost、LightGBM等算法，这类算法因为性能好，被业界广泛采用。突然想到树类型的算法都需要明白一个基本问题，树是如何选择特征和分裂点的？其根本要追溯到决策树的种类，每种是如何划分特征和分裂点，以及如何剪枝的。

决策树分为三类：ID3、C4.5、CART。提出时间却是1984年提出CART，1986年提出的ID3，1993年提出的C4.5。在介绍决策树之前需要了解一些信息论的知识，信息、熵、条件熵、信息增益。决策树中的ID3和C4.5与信息论息息相关。

信息论基础

信息是杂乱无章数据的一种度量方式。在分类问题中，如果待分类的事物可以划分在多个分类中，那么某个分类 的信息定义为：

其中，
是某个分类的信息；

是选择该分类的概率。

熵是信息的期望，也就是计算所有分类包含信息的期望值：

其中，H(Y)表示分类数据集的熵。

条件熵是在特征X给定条件下，类别Y的条件概率分布的熵对特征X的数学期望。

其中， 表示在特征X下的条件熵； 表示特征下 具体特征值的条件熵； 表示x和y的联合概率分布。

在划分数据集之前之后信息发生的变化叫做信息增益，信息增益是熵的减少或者说是数据无序程度的减少。熵减去条件熵就是信息增益。

其中， 表示信息增益。

数据说明

ID3

算法思路

当H(D)的值越小，说明样本集合D的纯度就越高。

2）选择用样本的某一个特征A来划分样本集合D时，就可以得出特征A对样本D划分所带来的信息增益。特征A把D划分为n个子集，计算特征A对数据集D的条件熵 H(D|A):

3）计算信息增益 IG：

信息增益越大，说明用特征A来划分数据集D，信息混乱程度越小。我们需要对样本的所有特征计算信息增益情况，选择信息增益大的特征来作为决策树的一个结点，或者可以说那些信息增益大的特征往往离根结点越近。当一个特征已经作为划分的依据，在下面递归过程就不在参与了。经过根结点下面特征各个取值后样本又可以按照相应特征值进行划分，并且在当前的样本下利用剩下的特征再次计算信息增益来进一步选择划分的结点，ID3决策树就是这样建立起来的。

决策树生成过程

大概创建分支createBranch()伪代码的意思如下：

检测数据集中的每个子项是否属于同一分类：

if so return 类标签

else

寻找划分数据集的最好特征

划分数据集

创建分支节点

for每个划分的子集

调用函数createBranch并增加返回结果到分支节点中

retrun 分支节点

也就是说，遍历每一个特征，遍历每一个特征值，如果计算出来信息增益最大，那么该特征就是最佳特征；接下来每个特征和特征值递归调用，构建下面的子树，再次选取特征和特征值，直到划分的子项属于同一类别或者遍历完所有特征，返回出现次数最多的类别。

示例

选用原始论文中的一个示例：

假设有两个分类，一个是N，一个是P，Outlook表示天气情况，Temperature表示气温情况，Humidity表示湿度，Windy表示有风,这四个作为特征，每个特征下面的离散值作为特征值。那么数据的熵 ：

在Outlook的值sunny中P出现了2次，N出现了3次，因此 ，那么数据集在sunny下的熵表示为 同理：在overcast下 ；在rain下 。那么数据集D在Outlook特征的条件熵表示为：

那么outlook的信息增益表示为：

同理其他特征的信息增益结果为：

可以发现Outlook的信息增益最大，优先在这个特征上划分，在递归到其他特征上最终形成的决策树图如下：

C4.5

ID3算法中当一个特征的可取值数目较多时，而对应的特征值下面的的样本很少，这个时候它的信息增益是非常高的。ID3会认为这个特征很适合划分，但是较多取值的特征来进行划分带来的问题是它的泛化能力比较弱，不能够对新样本进行有效的预测。为了解决这个问题，C4.5决策树不直接使用信息增益来作为划分样本的主要依据，采用信息增益率来划分样本。

特征A对训练数据集合D的信息增益比 定义为特征A的信息增益IG(D,A)与训练数据集D关于特征A的取值熵 之比，即：

如果特征A有n个取值，则其中数据集D关于特征A的熵为：

上面的过程相当于对特征值多的特征做了一个归一化，校正信息增益容易偏向于取值较多的特征的问题。但是同样增益率对可取值数目较少的特征有所偏好，因此C4.5决策树先从候选划分属性中找出信息增益高于平均水平的特征，在从中选择增益率最高的。关于C4.5的剪枝问题，在CART树中一并介绍。

CART树

ID3和C4.5需要把连续特征离散化才能在回归数据中使用，（ID3需要人工处理，C4.5算法自带处理)；使用熵来度量信息的混乱程度还是复杂了些；最佳特征取值可以是多个，切分成复杂的多叉树。由于他们存在一些问题，下面还有一种决策树模型，CART树。虽然ID3和C4.5存在很多问题，但是我不认为CART树是为了解决这些问题的，因为CART论文是发表的最早的，这边只是为了介绍他们对比不同。

CART(Classification And Regression Trees,分类回归树)，采用二元切分的方法，如果数据切分特征值等于切分要求进入左子树，否则进入右子树。CART树即可以处理分类问题，又可以处理回归问题。分类问题采用基尼系数来选择最优特征和分裂点，回归问题采用平方误差的总值（总方差）来选择最优特征和分裂点。

CART数据集混乱程度衡量

CART分类树

基尼指数是1912年意大利统计与社会学家Corrado Gini提出的。基尼系数(Gini index、Gini Coefficient)用来衡量一个国家或地区居民收入差距的指标，值越大表示收入越悬殊。在CART分类树中，采用基尼系数衡量数据集的不纯度（混乱程度），基尼系数越小说明数据不纯度低，特征越显著。 那么分类数据集D的基尼系数可以表示为：

在特征A下，将数据划分成两类，一类是 ,一类是 ,那么在特征A下的基尼系数为：

CART回归树

计算回归数据真实目标值中所有数据的均值，每条数据真实目标值减去均值。使用差值的绝对值或者差值的平方来衡量回归数据的混乱程度。若果采用差值的平方来衡量，那么就是平方误差的总值（总方差）。

树的生成过程

函数createTree()的伪代码大致如下：

找到最佳的待切分特征：

如果该节点不能再分，将该节点存为叶节点

执行二元切分

在右子树调用createTree()方法

在左子树调用createTree()方法

那么如何找到最佳的待切分特征和特征值呢？

每个特征：

每个特征值：

将数据切分成两份

计算切分的误差

如果当前误差小于当前最小误差，那么将当前切分设定为最佳切分并更新最小误差

返回最佳切分的特征和特征值

如果是分类树，那么误差指的的基尼系数，如果是回归树，误差值的是总方差。

树的剪枝

树的剪枝分为预剪枝和后剪枝，一般为了寻求模型的最佳效果可以同时使用两种剪枝技术。

预剪枝过程相对简单，在生成树的过程中，如果某个特征和特征值切分的样本小于最小样本数或迭代误差下降值小于设置的最小下降值，就停止切分。预剪枝可以降低过拟合的风险并减少决策树的训练时间，但是也会带来欠拟合的问题。

下面重点讲后剪枝，训练集训练一个决策树。在验证集上，对于一颗子树 ,其损失函数为：

其中， 为正则化参数， 为验证集的预测误差， 是子树T叶节点的数量。 如果将T的子树减掉，那么损失函数为：

如果剪枝后损失函数变小，或者损失函数相等但是叶节点的数量变少，这两种情况都满足剪枝条件，具体后剪枝过程如下：

基于已有的树切分验证集数据：

如果存在任一子集是一棵树，则在该子集递归剪枝过程

计算将当前两个叶节点合并后的误差

计算不合并的误差

如果合并会降低误差的话，就将叶节点合并

决策树算法小结

在样本量比较小的情况下建议使用C4.5，大样本的情况下使用CART。C4.5需要对数据进行多次排序，处理成本耗时较高；CART树是一种大样本的统计方法，小样本处理下泛化误差较大。

目前这三种算法都是一棵树中的特征来决定最后的结果，后来发展成一组树来决定最后的结果。如果这些树是并行投票，就是每个树的投票权重相同，形成了bagging类的算法，最有代表性的是Random Forest；如果这些树是串行投票，每个树的投票权重不同，通过拟合残差的方式，形成了boosting类的算法，最有代表性的是GBDT、XGBoost、LightGBM。

参考文献：

1.Leo Breiman, Jerome H. Friedman, Richard A. Olshen, Charles J. Stone.(1984).

2.Classification And Regression Trees Quinlan1986_Article_InductionOfDecisionTrees

3.C4.5: by J. Ross Quinlan. Inc., 1993. Programs for Machine Learning Morgan Kaufmann Publishers

4.《机器学习实战》

5. https://www. cnblogs.com/pinard/p/60 53344.html

6.周志华西瓜书《机器学习》