基本流程

决策树（decision）是一类常见的机器学习方法，其时基于树结构来进行决策的，这恰是人类在面临决策问题时一种很自然的处理机制。

一般的，一颗决策树包含一个根结点、若干个内部结点和若干个叶结点。叶结点对应于决策结果，其他每个结点则对应于一个属性测试；决策树学习的目的是为了产生一颗泛化能力强，即处理未见实例能力强的决策树，其基本流程遵循简单且直观的“分而治之”（divide-and-conquer）策略。


显然，决策树的生成是一个递归过程。在决策树基本算法中，有三种情形会导致递归返回：

1. 当前结点包含的样本全属于同一类别，无需划分；
2. 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；把当前结点标记为叶结点，类别设定为该结点所含样本最多的类别。
3. 当前结点包含的样本集合为空，不能划分。把当前结点标记为叶结点，类别设定为其父结点所含样本最多的类别。

划分选择

决策树学习的关键是第8行，即如何选择最优划分属性。一般而言，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”（purity）越来越高。本文介绍以下三种指标、：信息增益、增益率，基尼指数。分别对应三种决策树算法：ID3决策树学习算法、C4.5决策树算法、CART决策树。

信息增益

“信息熵”（information entropy）是度量样本集合纯度最常用的一种指标，其定义为：

Ent（D）的值越小，则D的纯度越高。假定离散属性a有V个可能的取值，则用属性a对样本集D进行划分所获得的“信息增益”（information gain）是：

一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大，因此可用信息增益来进行决策树的划分属性选择。著名的ID3决策树学习算法就是以信息增益为准则来选择划分属性。

增益率

实际上，信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的C4.5决策树算法不直接使用信息增益，而是使用“增益率”（gain ratio）来选择最优划分属性。采用与式（4.2）相同的符号表示

IV(a)称为属性a的“固有值”（intrinsic value），属性a的可能取值数目越多，则IV(a)的值通常会越大。增益率准则对可取值数目较少的属性有所偏好，因此C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式；先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

基尼指数

CART决策树使用“基尼指数”（Gini index）来选择划分属性。采用与式（4.1）相同的符号，数据集D的纯度可用基尼值来度量：

直观来说，Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此Gini(D)越小，则数据集D的纯度越高。采用与式（4.2）相同的符号表示，属性a的基尼指数定义为：

所以，在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性。

总结

除信息增益、增益率、基尼指数之外，人们还设计了许多其他的准则用于决策树划分选择，然而这些准则虽然对决策树的尺寸有较大影响，但对泛化性能的影响有限，它们仅在2%的情况下会有所不同，而下一节介绍的剪枝策略和程度对决策树泛化性能的影响相当显著。

剪枝处理

剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段。
决策树剪枝的基本策略有“预剪枝”（prepruning）和“后剪枝”（post-pruning）。

预剪枝

预剪枝是指在决策树生成过程中，对每个节点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；
预剪枝使得决策树的很多分支都没有“展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降，但在其基础上进行的后续划分却又可能导致性能显著提高；预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。

后剪枝

后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。性能评估可使用“留出法”，即预留一部分验证集以进行性能评估。
后剪枝决策树通常比预剪枝决策树保留了更多的分支，一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树，但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

连续与缺失值

连续值处理

到目前仅讨论了基于离散属性来生成决策树，现实任务中常会遇到连续属性，那如何在决策树学习中使用连续属性？由于连续属性的可取值数不再有限，因此，不能直接根据连续属性的可能取值来对结点进行划分。此时可使用连续属性离散化技术，最简单的策略是采用二分法对连续属性进行处理，C4.5决策树算法中采用此种机制。即把连续属性的取值区间的两两之间的中位点作为候选划分点，然后就可以像离散属性值一样来考察，选取最优的划分点进行样本集合的划分。需注意的是，与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。

缺失值处理

现实任务中常会遇到不完整样本，即样本的某些属性值缺失。如果简单地放弃不完整样本，仅使用无缺失值的样本来进行学习，显然是对数据信息极大地浪费，因此有必要考虑利用有缺失属性值的训练样例来进行学习。
在针对缺失值这个问题，我们需要解决两个问题：

1. 如何在属性值缺失的情况下进行划分属性的选择？
2. 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

对于问题一，给定数据集D和属性a，令D~表示D中在属性a上没有缺失值的样本子集，因此我们可根据D~来判断属性a的优劣。将信息增益的计算式推广为如下：

对于问题二，若样本x在划分属性a上的取值已知，则将x划入与其取值对应的子结点，且样本权值在子结点中保持为Wx。若样本x在划分属性a上的取值未知，则将x同时划入所有子结点，且样本权值在与属性值a对应的子结点中调整为r~*w;直观地看，就是让同一个样本以不同的概率划入到不同的子结点中。C4.5算法就使用了该解决方案。

多变量决策树

若我们把每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本就对应了d维空间中的一个数据点，对样本分类则意味着这个坐标空间中寻找不同类样本直接的分类边界，决策树所形成的分类边界有一个明显特点就是轴平行（axis-parallel），即它的分类边界由若干个与坐标轴平行的分段组成。
如图所示，此时的决策树会相当复杂，由于要进行大量的属性测试，预测时间开销会很大。

若能使用斜的划分边界，如图4.12中红色线段所示，则决策树模型将大为简化。

“多变量决策树”（multivariate decision tree）就是能实现这样的斜划分或者更复杂划分的决策树。以实现斜划分的多变量决策树为例，在此类决策树中，非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试，换言之，每个非叶结点是一个线性分类器，其中权重和偏移项均可在样本集合和属性集上学得。因此，与传统的“单变量决策树”（univariate decision tree）不同，在多变量决策树的学习过程中，不是为每个非叶结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。