By

Contents
  1. 1. 定义
  2. 2. 划分选择
    1. 2.1. 信息增熵
    2. 2.2. 增益率
    3. 2.3. 基尼系数
  3. 3. 剪枝处理
    1. 3.1. 预剪枝
    2. 3.2. 后剪枝
  4. 4. 连续与缺失值
    1. 4.1. 连续值处理
    2. 4.2. 缺失值处理
  5. 5. 多变量决策树
  6. 6. 课外阅读材料

定义

一般的一棵决策树包含一个根节点、若干个内部节点和叶节点；叶节点对应于决策结果，其他每个节点则对应于一个属性测试；每个节点包含的样本集合根据测试的结果被划分到子节点中根节点包含样本全集。从根节点到每个叶节点的路径对应了一个判定测试序列。

决策树学习的目的是为了产生一颗繁华能力强，即处理未见示例能力强的决策树，其基本流程遵循简单的“分而治之”策略，如下图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
输入：训练集$D = {(x_1,y_1),(x_2, y_2),...,(x_m, y_m)}$
      属性集$A = {a_1,a_2,...,a_d}$
过程：函数TreeGeneration(D, A)
1. 生成节点 node
2. if D 中样本全属于统一类别 C then //情形1
3.     将node标记为C类叶节点; return
4. end if
5. if $A = \emptyset $ OR D 中样本在 A 上取值相同 then  //情形2
6.     将node标记为叶节点，其类别标记为D中样本数最多的类；return
7. end if
8. 从 A 中选出最优划分属性$a_*$;
9. for $a_{*} $ 的每一个值 $a_{*} ^v$ do
10.    为node生成一个分支；令$D_v$表示D在$a_*$上取值为$a_{*} ^v$的样本子集；
11.    if $D_v$ 为空 then     //情形3
12.        将分支标记为叶节点，其类别标记为D中样本最多的类；return
13.    else
14.        以$TreeGenerate(D_v, A\{a_*})$ 为分支节点
15.    end if
16. end for
输出：以node为根节点的一颗树

显然决策树生成过程是一个递归的过程。在算法中有三种情形会导致递归返回：

  1. 当前节点包含的样本全属于同一类别，无需划分
  2. 当前属性集为空，或是所有样本在所有属性集上取值相同，无法划分
  3. 当前节点包含的样本集合为空，不能划分

2情形：把当前节点标记为叶节点，并将其类别设定为该节点所含样本最多的类别
3情形：同样把当前节点标记为叶节点，但将其类别设定为其父节点所含样本最多的类别。

这两种情形处理实质不同，2是利用当前节点的后验分布，而3则是把父节点的样本分布当做当前节点的先验分布。

划分选择

决策树的关键是选择最优划分属性。随着划分的不断进行，我们希望决策树的分支节点包含的额样本尽可能属于同一类别，即节点的“纯度”越来越高。

信息增熵

“信息熵”是度量样本集合纯度最常用的一种指标。假定当前样本集合D中第k类样本所占比例为$p_k(k=1,2,3, \ldots, \mathcal{Y})$，则D的信息熵定义为：
$$Ent(D) = -\sum_{k=1}^{|\mathcal{Y}|} p_k\log_2 p_k$$
Ent(D)值越小，则D纯度越高。Ent(D)取值范围为$0 \sim \log_2|\mathcal{Y}|$

假定离散属性a有V个可能的取值${a_1, a_2,\ldots, a_V}$,若使用a来对样本集D进行划分，会产生V个分支节点，其中第v个分支节点包含算了D中所有属性在a上取值为$a^v$的样本，记为$D^v$,可以根据上式计算$D^v$的信息熵，再考虑不同的分子节点包含的样本数不同，给分支节点富裕权重$|D^v|/|D|$,即样本数越多分支节点影响越大。可以计算用属性a对样本D进行划分获得的“信息增熵”：
$$Gain(D,a) = Ent(D) - \sum_{v=1}^V \frac{|D^v|}{|D|} Ent(D^v)$$
一般而言，信息增熵越大，意味着属性a进行划分所获得的“纯度提升越大”。著名的ID3决策树就是以信息上增益为准则划分属性。

增益率

事实上，信息增益准则对可取值数目较多的属性有偏好，为了减少这种偏好可能带来的不利影响C4.5决策树算法不直接采用信息增益，而是使用“增益率”来划分属性，增益率定义为：
$$ Gain_ration(D,a) = \frac{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)的值会越大。

需要注意的是，增益率准则对可取值数目较少的属性有所偏好，因此C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

基尼系数

CART决策树使用“基尼系数”来选择划分属性。

CART是Classification and Regression Tree的简称，这是一种著名的决策树学习算法，分类和回归任务都可用。

数据集D的纯度可以用基尼值来衡量：
$$Gini(D) = \sum_{k=1}^{|\mathcal{Y}|} \sum_{k’ \neq k} p_k p_{k’} = 1- \sum_{k=1}^{|\mathcal{Y}|} p_k^2$$
直观地说，Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率，因此Gini越小则数据D的纯度越高。
属性a的基尼指数定义为：
$$Gini_index(D,a) = \sum_{v=1}^V \frac{|D^v|}{|D|}Gini(D^v)$$
于是我们在候选属性集A中，选择哪个使得划分后基尼指数最小的属性作为最优划分属性，即$a_* = argmin_{a\in A} (Gini_index(D,q))$

剪枝处理

剪枝处理决策树学习算法中对付“过拟合”的主要手段。
剪枝的基本策略有“预剪枝”和“后剪枝”。

  • 预剪枝是指在决策树生成过程中对每个节点在划分前先惊喜估计，若当前划分的节点不能带来决策树泛化性能的提升，则停止划分并将当前节点标记为叶节点。
  • 后剪枝是先从训练集生成一颗完整的决策树，然后自底向上的对非叶节点进行考察，若将该节点对应的子树替换成叶节点能带来泛化性能的提升，则将该子树替换成叶节点。

如何判决泛化性能的提升?
可以采用第二章提出的性能评估方法。
例如采用留出法，可以预留一部分数据用作“验证集”来进行性能的评估。

预剪枝

预剪枝主要对划分前后的泛化性能进行评估。
预剪枝使得决策树很多分支都没有“展开”，这不仅降低了过拟合的风险还限制减少了决策树的训练时间开销和测试时间开销。
但另一方面，有些分支的当前划分虽然不能提升泛化性能，甚至可能导致泛化性能暂时下降，但在其基础上进行的后继划分却有可能导致性能显著提高。
预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。

后剪枝

后剪枝通常比预剪枝保留了更多的分支。
一般情况下后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝。
但是后剪枝是在决策树完全生成之后进行的并且要自底向上对所有非叶结点进行考察，因此时间开销比未剪枝和预剪枝觉得数都要大得多。

连续与缺失值

连续值处理

连续值离散化
最简单策略是采用二分法（C4.5决策树）。
先将属性值进行排序，然后对于相邻的两个属性以中值作为候选划分点，然后像离散值一样考察这些划分点，以最优的的划分点作为样本集合的划分点。

缺失值处理

需要解决两个问题；

  1. 如何在属性值缺失的情况下进行划分属性选择？
  2. 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

针对问题2，首先令个样本权重初始化为1.
若样本x在划分属性a上的取值一致，则将x划分入与其取值对应的子节点，且样本权值在子节点中保持。若样本x在划分属相a上取值未知，则将x同时划入所有子节点，且样本权值进行调整。直观上看就是让同一个样本以不同概率划分到不同的子节点中去。

多变量决策树

我们把每个属性看做坐标空间中的一个坐标轴，则d个属性描述的样本就对应了d维空间中的一个数据点，对样本的分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。决策树所形成的分类边界有一个明显的特点：
轴平行，即它的分类边界由若干个与坐标轴平行的分段组成。

这样的分类边界使得学习结果具有较好的可解释性，因为每一段划分都直接对应了某个属性取值。但在学习任务的真实分类边界比较复杂的时候，必须使用很多段的划分才能获得较好的近似。此时决策树会相当复杂，由于要进行大量的属性测试，预测开销会很大。
若能使用斜的边界，则决策树模型将大为简化。如下图:

“多变量决策树”就是能实现这样的“斜划分”甚至更复杂划分的决策树。
以实现斜划分的决策树为例，在此类决策树中，非叶结点不再是进针对某个属性，而是对属性组合进行测试。换言之，每个节点是一个形如$\sum_{i=1}^{d} w_i a_i = t$的线性分类器，其中$w_i$是属性$a_i$的权重，$w_i$和t可以在该节点所含的样本集合属性集上学的。
于是，与传统的“单变量决策树”不同，在多变量决策树的学习过程中，不是为每个非叶节点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。

课外阅读材料

  1. C4.5Rule是一个将C4.5决策树转换为符号规则的算法。
  2. 除了信息增益、增益率、基尼指数外，人们还设计了很多其他准则用于决策树的划分。然而有实验表明，这些准则虽然对决策树的尺寸有较大影响但是对泛化性能的影响很有限。
  3. 剪枝方法对决策树泛化性能影响相当显著，在数据带有噪声的时候通过剪枝甚至能提升25%
  4. 多变量决策树算法有OC1等。主要几个方面：
    • 在局部优化的基础上再对分类边界进行随机扰动以试图找到更好边界。
    • 引入线性分类器学习的最小二乘法。
    • 在决策树叶节点上嵌入神经网络，结合这两者的优势如“感知机树”，在每个叶节点上训练一个感知机。
  5. 有一些决策树算法可以进行“增量学习”，主要机制是通过调整分支路径上的划分属性次序来对树进行部分重构。代表算法ID4.增量算法可以有效将第每次接受到新样本后的时间开销，但多步增量学习后的模型与基于全部数据训练获得的模型有较大差别。
Contents
  1. 1. 定义
  2. 2. 划分选择
    1. 2.1. 信息增熵
    2. 2.2. 增益率
    3. 2.3. 基尼系数
  3. 3. 剪枝处理
    1. 3.1. 预剪枝
    2. 3.2. 后剪枝
  4. 4. 连续与缺失值
    1. 4.1. 连续值处理
    2. 4.2. 缺失值处理
  5. 5. 多变量决策树
  6. 6. 课外阅读材料