p73 - p97

第四章 决策树

4.1 基本流程

一棵决策树包含一个根节点，若干个内部节点和若干个叶节点；
叶节点对应决策结果，其他每个节点对应于一个属性测试

决策树学习基本算法伪码 p74 图4.2
在算法中，选择最优划分属性成为了关键。

4.2 划分选择

我们希望决策树的分支节点所包含的样本尽可能属于同一类别。
即：结点的纯度（purity）越来越高。

4.2.1 信息增益

信息熵度量法：Ent(D): 见p75
Ent越小，D的纯度越高

对于一个属性a的每个取值av，我们可以计算出Dv的信息熵。
又要考虑到Dv样本容量不同，容量越大越有影响力，因此需要赋予权重
综述：
计算用属性a对样本进行划分的信息增益
具体计算方法：p75

信息增益越大，纯度提升越大。因此可用信息增益来进行决策树的划分属性选择。
即ID3决策树学习算法

以西瓜数据集举例的详细计算过程：p76-77

4.2.2 增益率

如果把id也作为一个属性：增益非常大。但显然不合理，不具备泛化能力。

可以看出，信息增益准则对取值较多的属性有所偏好。
C4.5决策树算法，不直接使用增益，而使用增益率。

但C4.5是对取值数目较少的属性有所偏好的。

4.2.3 基尼指数

CART决策树 使用 Gini index来选择属性。
D的纯度通过基尼值来度量。

公式：p79

选择基尼指数最小的属性作为最优划分属性。

4.3 剪枝处理

目的：对付过拟合
基本策略：预剪，后剪
预剪：对每个节点划分前进行估计，若能带来泛化能力提升才划分。
后剪：生成以后自底向上看每个节点，若该节点作为叶子节点能提升泛化能力，就。

若使用留出法：

4.3.1 预剪枝

例子中最终只划分了一层：这样的决策树称为决策树桩

可以看出，这样虽然能预防过拟合，但可能会有欠拟合的风险

4.3.2 后剪枝

通常，后剪枝会比预剪枝保留更多分支。欠拟合风险较小。
但训练时间开销会大。

4.4 连续与缺失值

4.4.1 连续值处理

如何处理连续属性？

最简单的方法：二分法（C4.5使用了）
若一个属性取了n个值，那我们就取n-1个分割点，一个个地计算信息增益，选择最佳分割点。
需注意的是，与离散点不同，若一个属性用过了，在子节点还可以继续用这个属性。

4.4.2 缺失值处理

某些属性值不知道，但丢掉这些数据又可惜：

问题1：如何进行划分属性选择：

对于训练集D和属性a，显然我们可以仅根据D在a上没有缺失值的数据来确定划分属性。

调整了信息增益的计算式。

问题2：属性缺失的样本在通过缺失属性划分时怎么办？

初始要给每个样本权重
样本在碰到倒霉属性时要都进
但要调整权重。

4.5 多变量决策树

把样本放到坐标系中去考虑：
决策树形成的分类边界有一个明显的特点：轴平行，即他的分类边界和若干个与坐标轴平行的分段组成。

即在坐标系中边界是直来直去的。图见p90

如果能用斜的边界来搞定，那么模型会得到简化：引出多变量决策树（MDT）

MDT中每个节点不再针对某个属性，而是属性的线性组合。
换言之，每个节点是一个线性分类器。见图p91
如 -0.8密度 - 0.44含糖率 <= -0.3? 是则..否则..

4.6 阅读材料

休息一会儿

ID3算法：澳大利亚，罗斯昆兰，解决国际象棋残局2步内是否会被将死。引入了信息增益准则。
C4.0：ID3算法的后继算法，因为ID4,ID5被抢注了..
C4.5（后续改进）,C5.0（商业化版本）