决策树（decision tree）是一类常见的机器学习方法，顾名思义，决策树是基于树结构来进行决策的，这恰是人类在面临决策问题时一种很自然的处理机制。例如，我们想买西瓜的时候，如何判断一个好瓜是一项很实用的技能。我们可能会从颜色，根蒂或者敲声来进行判断，通常会通过一个优先级顺序来进行子决策，如图

西瓜问题的一颗决策树

一般的，一颗决策树包含一个根结点、若干个内部结点和若干个叶节点；叶节点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集。决策树的学习目的是为了产生一颗泛化能力强，即处理未见示例能力强的决策树。该算法遵循“分而治之”的策略。如图

决策树基本学习算法

显然，决策树的生成是一个递归过程。在决策树基本算法中，有三种情形会导致递归返回：（1）当前结点包含的样本全属于同一类别，无需划分；（2）当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；（3）当前结点包含的样本集合为空，不能划分。

在第（2）种的情形下，我们把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别；在第（3）种情形下，同样把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别。注意这两种情形的处理实质不同：情形（2）是在利用当前结点的后验分布，情形（3）则是把父结点的样本分布作为当前结点的先验分布。

划分结点

决策树学习最为关键的是确定如何选择最优划分属性。一般而言，决策树的分支结点所包含的样本尽可能属于同一类别，即结点的纯度越来越高。

1、信息增益

“信息熵”（information entropy）是度量样本集合纯度最常用的一种指标。

接下来需要计算信息增益，一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。决策树基本算法的第八行就是通过选择最大信息增益来进行划分属性的。计算方法如下：

信息增益计算方法

对于西瓜问题，它的属性有色泽、根蒂、敲声、脐部、触感，那首先选择哪个属性作为第一个节点分类呢？这就需要计算他们的信息增益，选择信息最高的那个，然后再往下重复这一过程。

2、增益率

信息增益最高的并不意味着它是最理想的划分属性，例如，有12个西瓜，我给这12个西瓜分别排上1到12的序号，这时，如果我是通过序号来计算信息增益的，可以得到最大的信息增益。这很容易解释：序号将产生12个分支，每个分支结点仅包含一个样本，这些分支结点的纯度已达最大。然而这样的决策树是不具备泛化能力的，无法对新样本进行有效预测。

实际上，信息增益准则对可取值数目较多的属性有所偏好，为了减少这种偏好带来的不利影响，著名C4.5决策树算法不直接使用信息增益，二是使用“增益率”来选择最优划分属性。增益率定义为：

IV(a)成为属性a的固有值，属性a可能取值数目越大，则IV(a)越大。但世上没有完美的事情，增益率对可取值数目较少的属性有所偏好，因此，C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

3、基尼指数

CART决策树使用“基尼指数”来选择划分属性。CART是Classfication and Regression Tree的简称，这是一种著名的决策树学习算法，分类和回归任务都可用。数据集D的纯度可用基尼值来度量：

基尼值计算方法

其中p_k是指当前样本集合中第k类样本所占的比例为p_k(k=1,2,.....,|y|).直观来说，Gini(D)反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此，Gini(D)越小，则数据集的纯度越高。

属性a的基尼指数定义为：

于是，在候选属性集合时，选择那个使得划分后基尼指数最小的属性作为最优划分属性。

剪枝处理

减枝是决策树学习算法中对付“过拟合”的主要手段。在决策树学习过程中，有时会造成决策树分支过多，这时有可能发生因训练样本学的太好了，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。这时可以通过主动去掉一些分支来降低过拟合风险。

决策树的剪枝策略有“预剪枝”和“后剪枝”。预剪枝是指在决策树的生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则将该子树替换为叶结点。后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化能力的提升，则将该子树替换为叶结点。

一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶子结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

连续和缺失值

1、连续值处理

前面我们主要讨论了基于离散属性来生成决策树。现实学习任务中常会遇到连续属性，有必要讨论如何在决策树学习中使用连续属性。

因为连续属性的可取数目不再有限，因此，连续属性离散化技术派上用场。最简单的策略是采用二分法对连续属性进行处理。

缺失值处理

现实任务中常会遇到不完整的样本，即样本的某些属性值缺失。如果简单地放弃不完整样本，仅使用无缺失值的样本进行学习，显然是对数据信息的极大浪费。有必要使用有缺失值的数据来进行模型训练。

这时我们需要解决的问题有两个：（1）如何在属性值缺失的情况下进行划分属性选择？

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