3.6
决策树

3.6.1 决策树的概念

决策树（Decision Tree）是一种典型的分而治之的机器学习算法，基于样本数据，递归选择合适特征条件作为分支节点，不断提高子分支的“纯度”，结果直观，可解释性好 ^[26] 。决策树是一棵有向树，有一个根节点（没有输入边），其他节点都有一条输入边，有输出边的节点称为内部节点或测试节点，所有其他节点称为叶节点 ^[27] 。决策树算法的原理可用图3-30来进行简要示意，图3-30a所示为由 x ₁ 、 x ₂ 两个特征变量构成的决策树，根据切割点 t ₁ 、 t ₂ 、 t ₃ 、 t ₄ ，有5种结果 R ₁ ， R ₂ ，…， R ₅ （可以是连续量，也可能是类别量），例如，当 x ₁ ≤ t ₁ 且 x ₂ ≤ t ₂ 时，模型的结果为 R ₁ ，决策树本质上是在特征空间上进行不断切分，形成合适的子空间，每个子空间上的结果是一样的，如图3-30b所示。决策树分为分类树和回归树两大类，前者用于分类标签值，后者用于预测连续值。

3.6.2 决策树构建过程

简单来说，决策树的决策过程就是从根节点开始，测试待分类项中对应的特征属性，并按照其值选择输出分支，直到叶子节点，将叶子节点的存放的类别作为决策结果。构建步骤如下。

1）遍历每个特征的每一种分割方式，找到最好的分割点；

2）将数据划分为不同的子节点，如N1，N2，…;计算划分之后所有子节点的“纯度”信息；

3）对第2步产生的分割，选择出最优的特征以及最优的划分方式；得出最终的子节点：N1，N2，…;

4）对子节点N1，N2，…，N m 分别继续执行2~3步，直到每个最终的子节点都满足“纯度”要求。

1.分割属性选择

决策树算法是一种“贪婪”算法策略，只考虑在当前数据特征情况下的最好分割方式，不进行回溯操作。决策树是通过“纯度”来选择分割特征属性点。在训练数据集上，分别对各个特征属性进行划分操作，对所有划分操作的“纯度”进行比较，选择“纯度”越高的特征属性作为当前需要分割的数据集进行分割操作，持续迭代，直到满足停止条件。

常用的“纯度”度量指标有基尼（Gini）系数、熵（Entropy）、错误率（Error），更多的指标可以参阅参考文献［26］。

2.停止条件

决策树构建的过程是一个递归的过程，所以必须给定停止条件，一般设定的停止条件如下。

1）大于设置的决策树的最大深度；

2）小于设置的内部节点再划分所需最小样本数；

3）小于设置的叶节点最少样本数；

4）大于设置的最大叶节点数；

5）小于设置的不纯度阈值。

3.效果评估

与一般的分类算法一样，效果评估多采用混淆矩阵、召回率、精确度等指标。

决策树也可以采用叶子节点的纯度值总和计算损失函数值来评估算法效果，值越小，效果越好。

4.后剪枝

决策树过度拟合一般是由于节点太多导致的，剪枝优化提高决策树的泛化能力非常重要，也是最常用的一种优化方式（另外一种优化方式是用随机森林算法）。剪枝可以分为预剪枝和后剪枝。预剪枝指的是在构建决策树的过程中提前停止；后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树变为叶结点能带来泛化性能提升，则将该子树替换为叶结点。因为决策树是一个贪婪算法，预剪枝策略一般无法得到比较好的结果，因此采用的往往是后剪枝策略。

常见的后剪枝方法包括错误率降低剪枝（Reduced Error Pruning，REP）、悲观剪枝（Pessimistic Error Pruning，PEP）、代价复杂度剪枝（Cost Complexity Pruning，CCP）、最小误差剪枝（Minimum Error Pruning，MEP）、CVP（Critical Value Pruning）、OPP（Optimal Pruning）等方法，这些剪枝方法各有利弊，关注不同的优化角度 ^[28] 。

决策树剪枝系数由损失函数得来：

3.6.3 常用决策树算法

本小节主要介绍ID3、CHAID（Chi-square Automatic Interaction Detection，卡方自动交互检测）、C4.5、C5.0、CART（Classification And Regression Tree，分类回归树）等算法。

1.ID3算法

ID3算法的特点是每次迭代选择信息增益最大的特征属性作为分割属性：

优点：决策树构建速度快，实现简单。

缺点：

1）计算依赖于特征数目较多的特征，而属性值最多的属性并不一定最好；

2）ID3算法不是递增算法；

3）ID3算法是单变量决策树，对于特征属性之间的关系不会考虑；

4）抗噪性差；

5）只适合小规模数据集，需要将数据放到内存中。

R的rpart包中rpart()函数可以实现ID3算法。下面例子使用了iris默认数据集，使用rpart.plot()绘制决策树结果图，如图3-31所示。

2.CHAID算法

CHAID根据统计检验来确定自变量和分割点的选择，通过卡方检验计算相关性进行模型分类。party包中的ctree()函数可以实现，这种方法因为设定了阈值所以不需要剪枝，所以如何决定阈值比较关键。如下述代码和图3-32所示。

3.C4.5算法

C4.5算法是在ID3算法的基础上提出的一种决策树构造算法 ^[29] ，使用信息增益率来取代ID3算法中的信息增益，并且在树的构造过程中会进行剪枝操作优化，除此之外C4.5算法会自动完成对连续变量的离散化处理，在分割时自动选择信息增益率（Gain_ratio）最大的特征。

优点：产生的规则易于理解、准确率较高、实现简单。

缺点：

1）对数据集需要进行多次顺序扫描和排序，所以效率较低；

2）同样只适合小规模数据集，需要将数据放到内存中。

RWeka包中J48()函数可以实现C4.5算法，如下述代码和图3-33所示。

4.C5.0算法

C5.0是加入自适应增强（Adaboost）算法对C4.5算法加以改进的算法 ^[30] ，使用的是c50包，C5.0算法的优点之一就是它可以自动进行剪枝操作。如下述代码和图3-34所示。

5.CART算法

CART算法使用基尼（Gini）系数作为纯度的量化指标来构建决策树，也称作分类回归树。

R语言rpart包中rpart()函数也可以实现CART方法，如下述代码和图3-35所示。

对于简单的iris数据集，无论是用信息增益还是Gini来选择分裂属性，得到的决策树都是一样的。

6.算法对比

前述几种算法的对比见表3-7。