第4章 决策树

4.1 基本流程

• 决策树也称判定树，是一类常见的机器学习方法。
• 决策树是基于树结构来进行决策的，这恰是人类在面临决策问题时一种很自然的处理机制。
• 决策的最终结论对应了我们所希望的判定结果，决策过程中提出的每个判定问题都是对某个属性的测试，每个测试结果考虑范围是在上次决策结果限定范围内。
• 叶结点对应于决策结果，其他每个结点对应于一个属性测试。
• 决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循分而治之的策略。
• 

4.2 划分选择

4.2.1 信息增益

“信息熵”是度量样本集合纯度常用的一种指标。

信息增益

一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。因此，可用信息增益来进行决策树的划分属性选择。

4.2.2 增益率

• 信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好带来的不利影响，著名的C4.5决策树算法不直接使用信息增益，而是使用增益率来选择最优划分属性。
• 增益率定义为：

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

4.2.3 基尼指数

CART决策树使用“基尼指数”来选择划分属性。数据集D的纯度可用基尼值来度量：

Gini(D)越小，数据集的纯度越高。
属性a的基尼指数定义为：

在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即：

4.3 剪枝处理

剪枝是决策树学习算法对付过拟合的手段。

留出法：预留一部分数据用作验证集以进行性能评估。

4.3.1 预剪枝

预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。

4.3.2 后剪枝

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

4.4 连续与缺失值

4.4.1 连续值处理

由于连续属性的可取数目不再有限，因此不能直接根据连续属性可取值来对结点进行划分。此时，连续属性离散化技术可派上用场。最简单的策略是采用二分法对连续属性进行处理，这正是C4.5决策树算法中采用的机制。

4.4.2 缺失值处理

离散值：众数填充、相关性最高填充。

连续值：中位数填充、相关性最高的列做线性回归进行估计。

4.5 多变量决策树

4.6 阅读材料