第4章 决策树

决策树（判定树）是一种学习方法，也可以是学得的结果，顾名思义，基于树结构进行决策，最终结论（叶结点）是我们希望的判定结果。一般的，决策树有一个根结点，若干内部结点和若干叶结点，叶结点对应结果，内部结点对应属性划分。根结点包含所有样本，每个结点包含的样本集合根据属性测试结果划分到叶结点，从根结点到一个叶结点的路径就是一个判定测试序列，定义简单明了。

显然，决策树生成是一个递归过程，有3种条件可以终止递归，也就是标记为叶结点：
（1）当前结点包含的所有样本是同一类别，无需再划分；
（2）当前结点属性集为空，或者所有样本在所有属性上分类一样，无法再划分，其类别为包含样本中最多的类别，利用的是后验分布；
（3）当前结点包含的样本集合为空，不能划分，其类别为父结点包含样本最多的类别，利用的是先验分布。

如何选择最优划分属性是关键的问题，我们希望在划分过程中，分支结点包含的样本尽可能的属于同一类别，也就是结点的纯度尽可能高。有几种常用选择指标：信息增益、增益率以及基尼指数，当然还有许多其他准则，不过只能对决策树的尺寸有较大影响，对泛化能力影响有限。

信息增益准则，一般而言，信息增益越大，意味着使用属性α进行划分获得的纯度提升越大，用属性α对样本集D进行划分获得信息增益的公式为

决策树可能会有过拟合问题，即在划分过程中造成分支过多，导致泛化能力降低。剪枝是解决这类问题的主要手段，分为预剪枝和后剪枝。所谓预剪枝是在结点划分前先做评估，如果当前结点的划分不能带来泛化性能提升，则停止划分，将当前结点标记为叶结点；后剪枝则是先生成一棵决策树，在自底向上对非叶结点考察，如果将该结点的子树替换成叶结点能带来泛化性能提升，则替换成叶结点。预剪枝的优点是降低了过拟合的风险，显著减少了训练时间和测试时间的开销，但另一方面，由于禁止了很多分支的展开，可能会产生欠拟合的风险。后剪枝的优点是保留了更多的分支，因此欠拟合的风险较小，但因为要自底向上考察结点，训练时间开销可能要大很多。

现实任务中会有连续属性，不像离散属性是有限的，因此需要连续属性离散化技术来找到划分点，最简单的策略是二分法。和离散属性不同的是，如果当前结点划分属性是连续属性，其后代结点还可以使用该属性进行划分。现实任务中还会遇到不完整的样本，即样本的某些属性缺失，因此需要考虑缺失值处理的问题。对于如何在属性值缺失情况下进行划分属性选择，可以根据无缺失值样本所占比例、在某一类所占比例、在某属性上取某个值的的样本中的比例等信息拓展信息增益的计算方法来解决；对于给定划分属性，如果样本在该属性缺失值，如何进行样本划分的问题，可以让同一个样本以不同的概率划入到不同的子节点去来解决。

决策树形成的分类边界有轴平行的特点，即分类边界由若干与坐标轴平行的分段组成，该特点的优点是可解释性强，缺点是如果分类边界较复杂时，段划分会很多，预测时间开销会很大。多变量决策树是能实现斜划分或更复杂划分的决策树，关键在于非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试。也就是说，单变量决策树在学习过程中是为非叶结点寻找一个最优划分属性，而多变量决策树则是想建立一个合适的线性分类器。比如先贪心寻找每个属性最优权值，在局部优化基础上再对分类边界进行随机扰动来尝试找更好的边界；或者直接引入线性分类器学习的最小二乘法；甚至还可以在叶结点嵌入神经网络。

有一些决策树学习算法可以进行增量学习，原理是通过调整分支路径上的划分属性次序来对树进行部分重构，可以有效降低接收到新样本后的训练时间成本，但可能多步增量学习后，会与基于全量样本训练得到的模型有较大差别，孰好孰坏要看实际模型效果。