《机器学习》笔记-决策树（4）
作者：刘才权
编辑：黄俊嘉
写在最前面
如今机器学习和深度学习如此火热，相信很多像我一样的普通程序猿或者还在大学校园中的同学，一定也想参与其中。不管是出于好奇，还是自身充电，跟上潮流，我觉得都值得试一试。对于自己，经历了一段时间的系统学习（参考《机器学习/深度学习入门资料汇总》），现在计划重新阅读《机器学习》[周志华]和《深度学习》[Goodfellow et al]这两本书，并在阅读的过程中进行记录和总结。这两本是机器学习和深度学习的入门经典。笔记中除了会对书中核心及重点内容进行记录，同时，也会增加自己的理解，包括过程中的疑问，并尽量的和实际的工程应用和现实场景进行结合，使得知识不只是停留在理论层面，而是能够更好的指导实践。记录笔记，一方面，是对自己先前学习过程的总结和补充。 另一方面，相信这个系列学习过程的记录，也能为像我一样入门机器学习和深度学习同学作为学习参考。
章节目录
- 基本流程
- 划分选择
- 减枝处理
- 连续与缺失值
- 多变量决策树
1
基本流程
一般的，一颗决策树包含一个根节点，若干个内部节点和若干个叶子节点；叶子节点对应决策结果，其他每个节点对应一个属性测试；每个节点包含的样本集合根据属性测试的结果被划分到子节点中；根节点包含样本全集，从根节点到每个叶子节点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一颗泛化能力强，即处理未见示例能力强的决策树，基本形式如下图所示（判别习惯是否为好瓜的决策树）：
2
划分选择
决策树学习的关键，是如何选择最优划分属性。一般而言，随着划分过程的不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即节点的“纯度”越来越高。
信息增益
2.1
“信息熵”（information entropy）是度量样本集合纯度最常用的一种指标。假定当前集合D中第k类样本所占的比例为pk（k=1,2,...,|y|），则D的信息熵定义为，
Ent(D)的值越小，则D的纯度越高。假定离散属性a有V个可能的取值，
若使用a来对样本集合D进行划分，则会产生V个分支节点，其中第v个分支点包含了D中所有在属性a上取值为a(v)的样本，记为D(v)。根据信息熵可计算出属性a对样本集D进行划分所获得的“信息增益”（information gain），
一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。因此，我们可用信息增益来进行决策树的划分属性选择。著名的ID3决策树学习算法就是以信息增益为准则来选择划分属性的。
增益率
2.2
信息增益准则对可取值数目较多的属性有所偏好，为了减少这种偏好可能带来的不利影响，著名的C4.5决策树算法不直接使用信息增益，而使用“增益率”（gain ratio）来选择最优划分属性。增益率定义为，
其中，
基尼指数
2.3
CART决策树使用“基尼指数”（Gini index）来选择划分属性，
直观说，Gini(D)反应了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此，Gini(D)越小，则数据集D的纯度越高。
3
剪枝处理
剪枝（pruning）是决策树学习算法对付”过拟合“的主要手段。
决策树剪枝的基本策略有”预剪枝“（prepruning）和”后剪枝“（post-pruning）。预剪枝是指在决策树生成过程中，对每个节点在划分前进行估计，若当前的划分不能带来决策树泛化性能提升，则停止划分并将当前节点标记为叶节点；后剪枝是先从训练集生成一颗完整的决策树，然后自底向上的对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点。
剪枝处理降低了”过拟合“风险，但也带来了”欠拟合“的风险。
一般情形下，后剪枝决策树欠拟合风险较小，泛化性能往往优于预剪枝决策树。但后剪枝训练开销比未剪枝决策树和预剪枝决策树都要大很多。
4
连续与缺失值
到目前为止我们讨论了基于离散属性来生成决策树。现实学习任务中常会遇到连续属性。此时 ，连续属性离散化技术可派上用场。最简单的策略是采用二分法（bi-partition）。
现实任务中常会遇到不完整样本，即样本的某些属性值缺失。我们需要解决两个问题：
- 如何在属性值缺失的情况下进行划分属性选择？
- 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
5
多变量决策树
若我们把每个属性视为坐标空间的一个坐标轴，则d个属性描述的样本就对应了d维空间的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同样本之间的分类边界。决策树所形成的分类边界有一个明显的特点：轴平行（axis-parallel），即它的分类边界由若干个与坐标轴平行的分段组成。
显然，分类边界的每一段都与坐标轴平行的。这样的分类边界使得学习结果又较好的可解释性，因为每一段划分都直接对应了某个属性取值。但在学习任务的真实分类边界比较复杂时，必须使用很多段划分才能取得较好的近似，此时的决策树会相当复杂，由于要进行大量的属性测试，预测时间开销会很大。
若能使用斜的划分边界，则决策树模型将大为简化。“多变量决策树”（multivariate decision tree）就是能实现这样的“斜划分”甚至更负责划分的决策树。如下图所示，
