经典算法：决策树（Decision Tree）

一、模型介绍

决策树是一类常见的机器学习方法。既可以作为分类算法，也可以作为回归算法。同时也非常适合集成学习。决策树是最简单的机器学习算法，它易于实现，可解释性强，完全符合人类的直观思维，有着广泛的应用。本文将对最基础的决策树算法原理进行介绍，后续再介绍关于决策树相关算法的变体。

二、模型原理

image.png

决策树算法采用树形结构，使用层层推理来实现最终的分类。一颗完整的决策树包括：

根节点：包含样本的全集。
内部节点：对应特征属性测试。
叶节点：代表决策结果。

预测时，在树的内部节点处用某一属性值进行判断，根据判断结果决定进入哪个分支节点，直到到达叶节点处，得到分类结果。

决策树的学习关键是如何选择最优划分属性？
通俗理解，我们希望随着划分过程不断进行，决策树的分支节点所包含的样本尽可能属于同一类别，即节点的‘纯度’越来越高。所以我们需要有一个可量化的指标来表示‘纯度’，以作为决策树选择最优划分属性的依据。
下面主要介绍三种常见的指标：信息增益（ID3）、信息增益率（C4.5)、基尼指数（CART）。

信息增益

‘信息熵’是度量样本集合纯度最常用的一种指标。熵度量了事物的不确定性，越不确定的事物，它的熵就越大。假定当前样本集合 D 中第 k 类样本所占的比例为 $p_k(k=1,2,……m)$ 则 D 的信息熵定义为： $Ent(D) = -\sum_{i=1}^{m}p_k\log_{2}{p_k}$ $Ent(D)$ 越小，则 D 的纯度越高。
假设离散属性 a 有 n 个可能的取值 $\{a^1,a^2,……,a^n\}$ , 若使用 a 来对样本集 D 进行划分，则会产生 V 个分支结点，其中第 n 个分支包含了 D 中所有在属性 a 上取值为 $a^n$ 的样本，记作 $D^n$ 。同时考虑到样本越多的分支节点的影响越大，于是可以计算出用 a 属性对样本集 D 进行划分所得的‘信息增益’ (information gain): $Gain(D,a) = Ent(D) - \sum_{i=1}^{n}\frac{|D^n|} {|D|} Ent(D^n)$
一般而言，信息增益越大，则意味这使用属性 a 来进行划分所获得的‘纯度提升’越大。 ID3 决策树学习算法就是以信息增益为准则来选择划分属性。

增益率

在信息增益中，如果以每个对像的 ID 为属性划分，这样的分支节纯度已经到达最大，但是，这样的决策树明显不具有泛化能力，无法对新样本进行有效预测。
实际上，信息增益在计算的时候会对取值数目较多的属性有所偏好，为了减少这种偏好可能带来的不利影响。C4.5 决策树算法不直接使用信息增益，而是使用‘增益率’ (gain ratio) 来选择最优划分属性。增益率定义为： $Gain_ratio(D,a) = \frac{Gain(D,a)}{IV(a)}$
其中 $IV(a) = - \sum_{i=1}^{n}\frac{|D^n|}{|D|}log_{2}{\frac{|D|^n}{|D|}}$
称为属性 a 的‘固有值’。属性 a 的可能取值数目越多(即 n 越大)，则 IV(a) 的值通常会越大。不过，增益率准则会对取值数目较少的属性有所偏好。因此，C4.5 算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率高的。

C4.5 算法的不足与思考

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

1、由于决策树算法非常容易过拟合，因此对于生成的决策树必须要进行剪枝。剪枝的算法有非常多，C4.5 的剪枝方法有优化的空间。思路主要是两种，一种是预剪枝，即在生成决策树的时候就决定是否剪枝。另一个是后剪枝，即先生成决策树，再通过交叉验证来剪枝。
2、C4.5 生成的是多叉树，即一个父节点可以有多个节点。很多时候，在计算机中二叉树模型会比多叉树运算效率高。如果采用二叉树，可以提高效率。
3、C4.5 只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。
4、C4.5 由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算。

基尼指数

CART 决策树使用‘基尼指数’来选择划分属性，数据集 D 的纯度可用基尼值来度量：
计算公式： $Gini(D) = \sum_{i=1}^{k}\sum_{i'\neq i} p_k p_{k'} = 1 - \sum_{i=1}^{k}p_k^2$
对于样本 D :
$Gini(D) = 1 - \sum_{i=1}^{k}(\frac{C_k}{D})^2$
对于特征 A 将 D 划分：
$Gini(D, A) = \frac{D_1}{D}Gini(D_1) + \frac{D_2}{D}Gini(D_2)$
直观来说，Gini(D) 反映了从数据集 D 中随机抽取两个样本，其类别标记不一致的概率。 所以，Gini(D) 越小，则数据集 D 的纯度越高。同时有，属性 a 的基尼指数定义为： $Gini\_index(D,a) = \sum_{i=1}^{k}\frac{|D^k|}{|D|}Gini(D^k)$
于是，我们在候选属性集合中，选择那个是的划分后基尼指数最小的那个属性作为最优划分属性。

CART 分类树算法对于连续特征和离散特征处理的改进

对于 CART 分类树连续值的处理问题，其思想和 C4.5 是相同的，都是将连续的特征离散化。唯一的区别在于在选择划分点时的度量方式不同，C4.5使用的是信息增益比，则CART分类树使用的是基尼系数。具体的思路如下：
比如 m 个样本的连续特征 A 有 m 个，从小到大排列为 𝑎1,𝑎2,...,𝑎𝑚 则 CART 算法取相邻两样本值的平均数，一共取得 m-1 个划分点，其中第 i 个划分点 𝑇𝑖 表示为：𝑇𝑖=(𝑎𝑖+𝑎𝑖+1)/2。对于这 m-1 个点，分别计算以该点作为二元分类点时的基尼系数。选择基尼系数最小的点作为该连续特征的二元离散分类点。比如取到的基尼系数最小的点为 𝑎𝑡，则小于 𝑎𝑡 的值为类别 1，大于 𝑎𝑡 的值为类别 2，这样我们就做到了连续特征的离散化。

要注意的是，与 ID3 或者 C4.5 处理离散属性不同的是，如果当前节点为离散属性，则该属性后面还可以参与子节点的产生选择过程。
对于 CART 分类树离散值的处理问题，采用的思路是不停的二分离散特征。
回忆下 ID3 或者 C4.5，如果某个特征 A 被选取建立决策树节点，如果它有A1, A2, A3 三种类别，我们会在决策树上一下建立一个三叉的节点。这样导致决策树是多叉树。但是 CART 分类树使用的方法不同，他采用的是不停的二分，还是这个例子，CART 分类树会考虑把 A 分成 {𝐴1} 和 {𝐴2,𝐴3}, {𝐴2} 和 {𝐴1,𝐴3}, {𝐴3}和 {𝐴1,𝐴2}三种情况，找到基尼系数最小的组合，比如 {𝐴2} 和 {𝐴1,𝐴3},然后建立二叉树节点，一个节点是 A2 对应的样本，另一个节点是 {A1,A3} 对应的节点。同时，由于这次没有把特征 A 的取值完全分开，后面我们还有机会在子节点继续选择到特征 A 来划分 A1 和 A3。这和 ID3 或者 C4.5 不同，在 ID3 或者 C4.5 的一棵子树中，离散特征只会参与一次节点的建立。

三、模型细节

剪枝处理

剪枝(pruning) 是决策树学习算法处理过拟合的主要手段。通过主动去掉一些分支来降低过拟合的风险。决策树剪枝的基本策略有：预剪枝(prepruning) 和后剪枝(postpruning)。

预剪枝：在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点不能带来决策树泛化性能提升，则停止划分并将当前节点标记为叶节点。
后剪枝：先从训练集生成一棵完整的决策树，然后自底向上的对非节点进行考察，若该节点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点。
预剪枝是的决策树的很多分支都没有展开，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间。但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却有可能导致性能显著提高，预剪枝禁止这些分支展开，也同时带来了欠拟合的风险。
后剪枝通常比预剪枝保留了更多的分支，一般情况下，后剪枝决策树的欠拟合风险更小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在完全生成决策树之后进行的，而且需要自底向上的对树种所有非叶节点进行一一考察，因此其训练时间开销要比预剪枝决策树大得多。

四、模型优缺点

优点：

决策树易于理解和解释，可以可视化分析，容易提取出规则。
不需要预处理，不需要提前归一化，处理缺失值。
既可以处理离散值也可以处理连续值。

缺点：

决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
寻找最优的决策树是一个难题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。

五、模型使用

sklearn 中的 Decision Tree（CART算法）：

from sklearn.tree import DecisionTreeClassifier
tree = DecisionTreeClassifier(max_depth=7）

决策树在 sklearn 中的使用也相对简单，具体参数可参考 sklearn 相关文档，这里不再赘述。