第四章决策树 | BeZer0 Space

一、基本流程

决策树（decision tree） 是一种常见的机器学习方法。一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点；叶节点对应于决策结果，其他每个结点则对应于一个属性测试；每个节点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列。决策树学习的目的是为了产生一棵泛化能力强的决策树，算法如下：

由此可见，决策树的生成是一个递归过程。

二、划分选择

从算法中可以看出，决策树学习的关键是划分最优属性。一般来说，随着划分过程不断进行，要使决策树的分支结点所包含的样本尽可能属于同一类别，即结点的纯度（purity） 越来越高。

1. 信息增益

信息熵（information entropy） 是度量样本集合纯度最常用的一种指标。假定当前样本集合中第类样本所占比例为，则的信息熵定义为：

的值越小，则的纯度越高。

假定离散属性有个可能的取值，若使用来对样本集进行划分，则会产生个分支结点，其中第个分支结点包含了中所有在属性上取值为的样本，记为。利用上式可以计算出的信息熵，再考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重，即样本数越多的分支结点的影响越大，于是可计算出用属性对样本集进行划分所获得的信息增益（information gain）：

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

2. 增益率

信息增益准则对可取值树木较多的属性有所偏好，为减少这种偏好可能带来的不利影响，可以使用增益率（gain ratio）：

其中称为的固有值（intrinsic value）。属性的可能取值数目越多，则的值通常会越大。需要注意的是，增益率准则对可取值数目较少的属性有所偏好，因此算法使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

3. 基尼指数

基尼值可以度量数据集纯度：

反映了从数据集中随机抽取两个样本，其类别标记不一致的概率，因此基尼值越小则数据集纯度越高。基尼指数（Gini index） 定义：

因此在侯选属性集合中，选择使基尼指数最小的属性作为最优划分属性。

三、剪枝处理

剪枝（pruning） 是决策树学习算法中解决过拟合的主要手段。

决策树剪枝的基本策略有预剪枝（prepruning）和后剪枝（post-pruning）。预剪枝指在决策树生成过程中，对每个结点在划分前进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

四、连续与缺失值

1. 连续值处理

要想使用连续属性来生成决策树，就需要对连续值进行处理。最简单的策略是采用二分法（bi-partition）。

假定有一个连续属性，它具有多个不同的取值，将这些值从小到大排序，使得其在某个划分点可以对样本集进行划分，此时就等于相邻两被划分元素取值的均值：

为选取最优的划分点，可对式 4.2 进行改造：

其中是样本集基于划分点二分后的信息增益，因此可选择使其最大化的划分点。

2. 缺失值处理

如何在属性值缺失的情况下进行划分属性选择？

给定训练集和属性，令表示中在属性上没有缺失值的样本子集。假定属性有个可取值，令表示中在属性上取值为的样本子集，表示中属于第类的样本子集，则显然有，。假定为每个样本赋予一个权重，并定义：

直观来看，堆属性，表示无缺失值样本所占的比例，表示无缺失值样本中第类所占的比例，表示无缺失值样本中在属性上取值的样本所占的比例。显然，。基于上述定义，可对式 4.2 进行改造：

其中，由式 4.1 ，有：

给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

若样本在划分属性上的取值已知，则将划入与其取值对应的子结点，且样本权值在子结点中保持为。若样本在划分属性上的取值未知，则将同时划入所有子结点，且样本权值在与属性值对应的子结点中调整为。直观的看，这就是让同一个样本以不同的概率划入到不同的子结点中去。

五、多变量决策树

若把每个属性视为坐标空间中的一个坐标轴，则个属性描述的样本就对应了维空间中的一个数据点，对样本分类则意味着在这个空间中寻找不同类样本之间的分类边界。决策树所形成分类边界的特点是轴平行（axis-parallel），即它的分类边界由若干个与坐标轴平行的分段组成。

因此，这样的分类边界使得学习结果有较好的可解释性，因为每一段划分都直接对应了某个属性取值。但是当学习任务的真实分类边界比较复杂时，必须使用很多段划分才能获得较好的近似。

此时决策树非常复杂，由于要进行大量的属性测试，因此预测时间开销很大。若能使用斜的划分边界，如上图红色线断所示，决策树模型将被简化。多变量决策树（multivariate decision tree）可以实现这个目标。在此类决策树中，非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试，即每个叶结点是一个形如的线性分类器，其中是属性的权重，和可在该结点所含的样本集和属性集上学得。于是，与传统的单决策树（univariate decision tree）不同，在多变量决策树的学习过程中，不是为每个非叶结点寻找一个最优划分属性，而是建立一个合适的线性分类器。