决策树——机器学习

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

决策树学习的目的是为了产生一棵泛化能力强，即处理未见样本能力强的决策树，其基本流程遵循简单的”分而治之“策略。

决策树的生成是一个递归过程。对于一个节点所包含的样本集，选取一个属性进行划分，不同的属性值对应于该节点的不同子分支；当子分支中所包含的样本集或属性集为空或所有样本类别相同时，则递归返回。具体的算法细节此处不表。

显然，决策树生成算法的关键是为每个节点选择最优划分属性。

划分选择

一般而言，随着决策树划分过程的不断进行，期望分支节点所包含的样本尽可能属于同一类别，即节点的“纯度”越来越高。

我们用 信息增益 来衡量节点划分后获得的“纯度”提升量，信息增益即为节点使用该属性划分之前的信息熵减去划分之后的信息熵，对于每个属性的划分都计算一边信息增益，选取信息增益最大的那个属性作为节点的划分属性。

按照以上信息增益最大的准则，该准则对属性的可取值数目较多的属性有所偏好，C4.5决策树算法采用 增益率 来最为最优属性的划分准则。不过增益率对属性取值较少的有所偏好，所以C4.5算法首先从划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

此外，CART决策树采用 基尼系数 来选择划分属性，基尼系数反应了从数据集中随机抽取两个样本，其类别标记不一致的概率，每次划分采用使得基尼系数最小的属性。

剪枝处理

剪枝 用来处理决策树学习算法中的“过拟合”问题。决策树剪枝的基本策略有“预剪枝”和“后剪枝”两种。

预剪枝 是在决策树生成过程中，对每个结点在划分前进行估计，若当前节点的划分不能带来决策树 泛化性能 的提升，则停止划分并将当前节点标记为叶节点，其中泛化性能使用测试集的准确率来衡量。

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

预剪枝的本质是 贪心算法 ，这种算法可能不会达成最优状态，因为有些节点的划分虽然不能在当前提升泛化性能，但是在其基础上进行的后续划分可能会带来泛化性能的显著提高，所以预剪枝具有 欠拟合 的风险。一般情形下，后剪枝的欠拟合风险较小、并且泛化性能往往由于预剪枝，但后剪枝的缺点是计算与时间开销显然更大。

连续值与缺失值处理

现实学习任务中常会遇到连续值属性，其可取值数目不再有限，因此，需要对连续属性进行离散化，一种策略是对连续属性进行 二分法 处理。

二分法的策略是，针对连续属性，选择相邻属性值的平均值作为划分点，将样本分为两类，对基于每一个划分点的分类计算该属性的信息增益，该属性的信息增益则为所有划分点中的最大的信息增益。

同时，我们还要处理属性值缺失的情况，如果仅仅对属性值缺失的样本作丢弃处理，会丢失许多信息、造成很大浪费。为了解决该问题，为每个训练样本引入了一个 权重 属性，在对某一属性进行划分时，若样本缺少该属性值，则将该样本划入所有分支中，并且将该样本的权值乘以该分支属性值的样本占比。直观来看，就是将一个样本以不同的概率划分到不同的子节点中去。