决策树(decision tree)

本文主要基于西瓜书第4章，以及个人对相关领域的理解写成。

决策树是基于一系列对属性的逻辑判断形成的树形结构，通过在当前属性集上对其中某个属性进行划分，可形成若干个子属性集，从而一步步缩小属性集考虑空间。

1. 基本流程

一颗决策树一般包含一个根节点、若干个内部结点和若干个叶结点。其中叶结点对应于决策结果，其他每个结点对应于一个属性测试，根节点包含样本全集，每个结点包含的样本集合根据属性测试的结果被依次划分到子结点中。从根节点到每个叶结点的路径对应了一个判定测试序列。决策树就是一个这样的结构，它根据已有的样本集合产生划分标准，目的是产生一棵能够处理未见示例的分类器。

决策树的算法流程遵循典型的“分而治之”的递归思想，其中又三种情形会造成递归终止：（1）当前结点包含的样本都属于同一类别，无需划分；（2）当前属性集为空，或是当前样本在所有属性上取值相同，无法划分。此时将当前结点所含样本最多的类别设为结点类别；（3）当前结点包含的样本集合为空，不能划分。此时将父节点所含样本最多的类别当做当前结点的类别；

2. 划分选择

决策树学习的关键是选择最优划分属性，以生成树的分支。选择最优属性时，应遵循决策树的分支所包含的样本尽可能属于同一类别的原则，通过划分使子结点的纯度(purity)越来越高。

2.1 信息熵

信息熵是用于定义样本集合纯度的一种指标。设当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k (k=1, 2, ..., |\mathcal{Y}|)$ ，则信息熵为

$\operatorname{Ent}(D)=-\sum_{k=1}^{|\mathcal{Y}|}p_k\log_{2}{p_k}$

$\operatorname{Ent}(D)$ 越小，则集合 $D$ 的纯度越高。

2.2 信息增益与增益率

有了样本集合纯度的定义，接下来我们可以定义使用某个属性对集合 $D$ 进行划分的“信息增益”(information gain)

$\operatorname{Gain}(D,a) = \operatorname{Ent}(D) - \sum_{v=1}^{V}\frac{|D^v|}{|D|}\operatorname{Ent}({D^v})$

其中 $D^v$ 表示在集合 $D$ 中属性a的取值为 $a^v$ 的样本形成的子集合，属性a在问题空间中有{ $a^1, a^2, ... , a^v$ }总共V个可能的取值。

信息增益表示已知一个随机变量的信息后使得另一个随机变量的不确定性减少的程度。在这里，该公式可以理解为在属性 $a$ 的取值已知后，集合 $D$ 类别的不确定性减小的程度。信息增益越大，意味着使用a进行划分所获得的“纯度提升”越大，因此信息增益可作为决策树的属性划分标准。

事实上，信息增益在决策树中，很容易对可取值数目较多的属性有所偏好（如编号），这有可能大大降低决策树的泛化能力。因此，可使用“增益率”来代替“信息增益”作为最优划分属性。

$\operatorname{Gain\_ratio}(D,a) = \frac{\operatorname{Gain}(D,a) }{IV(a)}$ ，其中 $IV(a)=- \sum_{v=1}^{V}\frac{|D^v|}{|D|}\log_2\frac{|D^v|}{|D|}$
$IV(a)$ 是属性a的“固有值”，属性a的可能取值越多，则IV(a)的值也就越大，这也可理解为是在当前条件下属性a的熵。增益率是在信息增益下利用固有值进行纠正，使得属性选择时对可取值数目较少的属性有所偏好。

在C4.5决策树算法中，属性划分标准同时考虑了信息增益和增益率：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的属性。

2.3 基尼指数

“基尼指数”(Gini index)也是一种属性划分标准，它在CART决策树中被使用。基尼指数基于基尼值定义

$Gini(D)=1-\sum_{k=1}^{|\mathcal{Y}|}p_k^2$

基尼值表示数据集 $D$ 中随机两个样本类别标记不一致的概率，跟熵一样可以衡量数据集 $D$ 的纯度。基尼值越小，则代表数据集 $D$ 的纯度越高。

基尼指数表示为基尼值的分布（或是加权和），表示选用属性a进行划分后子属性集的总“纯度”。基尼指数越小，则该属性作为划分属性更优。

$\operatorname{Gini\_index}(D,a) = \sum_{v=1}^{V}\frac{|D^v|}{|D|}\operatorname{Gini}(D^v)$

3. ID3、C4.5、CART决策树的发展历程

4. 决策树剪枝

剪枝是决策树算法对抗“过拟合”的主要手段。剪枝基本可分为“预剪枝”和“后剪枝”。

4.1 预剪枝

“预剪枝”是指在决策树生成过程中，对每个结点在划分前进行估计，看当前划分能否带来泛化性能的提高。评判泛化性能是否有提升，一般通过从训练集中划分出一部分样本作为验证集，检查验证集上的准确率来评判泛化性能。

预剪枝本质上是一个贪心算法，它仅考虑当前结点分裂是否能提升性能，而无法预测到本次分裂后进一步分裂带来的影响。因此，预剪枝具有欠拟合的风险。

4.2 后剪枝

后剪枝是从训练集生成一颗完整的决策树，然后自底向上对非叶结点进行考察，看将结点对应的子树替换为叶结点是否能带来决策树泛化性能提升。

后剪枝是在决策树完全生成后才进行的考察，因此后剪枝决策树的欠拟合风险很小，泛化性能往往也优于预剪枝决策树。但对应的训练开销要比预剪枝决策树大得多。

5. 属性连续值与属性缺失值处理

5.1 决策树对于属性连续值的处理

在C4.5决策树算法中，使用了二分法来处理决策树中的连续属性。在处理离散属性时，我们考虑离散属性的每一个可能的取值作为候选划分点对原数据集进行划分，再比较信息增益；对于连续属性而言，由于连续属性具有无限个可能的取值，因此我们仅考虑训练样本集中该连续属性有多少种不同的取值，再在这些取值中按照大小顺序排列成数列，选择数列值两两之间的平均值作为可能的分裂点进行考虑。

具体而言，假定给定样本集 $D$ 和连续属性 $a$ ， $a$ 在 $D$ 上有n个不同的取值，记为 $\{a^1, a^2, ... , a^n\}$ ，那么候选划分点集合为 $T_a = \{\frac{a^i+a^{i+1}}{2} | 1 \leq i \leq n-1 \}$ ，共n-1个，分别考虑这些候选划分点即可。需要注意的是，离散属性作为划分属性分裂后在子结点中仍需要进行考虑，只是考虑的范围缩小了而已。

5.2 决策树对于属性缺失值的处理

决策树对于缺失值的处理较为繁琐，但基本思想很简单，将在下文中简要介绍。在C4.5算法中也使用了这种方法处理缺失值。

当考虑使用属性a进行划分属性对决策树进行划分时，通常的方式是计算信息增益 $Gain(D, a)$ ，但因为样本集合 $D$ 中的样本在属性 $a$ 上并不都存在值，因此需要在计算时乘上一个系数 $\rho$ ， $\rho$ 表示无缺失值样本所占的比例；在将属性a划分为各个子分支时，需要乘于的系数也根据无缺失值样本的比例进行归一化；在使用划分后样本集合的类别比例计算熵时，仅考虑无缺失值样本中各类别所占的比例；一言蔽之，就是每一步计算时仅考虑无缺失值的样本即可，并对对应系数进行归一化。

6. 回归决策树

我们在第5节介绍了决策树对于连续属性的处理。连续属性值不像离散属性存在天然的划分点，需要使用属性可能取值的平均值作为候选划分点，并挨个进行考虑。本节要介绍的回归决策树则是针对连续的样本标签值进行考虑。

对于连续的标签值，使用信息增益和信息熵作为选择最优划分属性的标准不可行，在此一般使用均方误差(mean squared error, MSE)代替信息增益来选择最优划分属性。在选择一个属性作为划分属性后，评判依据该属性划分后子分支作为叶子结点的均方误差之和，选择使得均方误差之和最小的属性作为最优划分属性。