（图片来源网络）

1. 章节主要内容

决策树是机器学习的一类常见算法，其核心思想是通过构建一个树状模型来对新样本进行预测。树的叶结点是预测结果，而所有非叶结点皆是一个个决策过程。

要相对深入的了解决策树机器学习算法，我们将按照以下的分标题顺序由浅入深的进行介绍。

1）决策树算法的基本流程

一般的，一颗决策树包含一个根结点、若干内部结点和若干个叶结点；叶结点对应于决策结果，其它每个内部结点（包括根结点）则对应一个属性测试。决策树根据内部结点的属性测试结果将该结点所包含的样本集按照属性测试的结果被划分到不同的子结点中。

这是一种简单且直观的“分而治之”（divide-and-conquer）策略，决策树学习的目的是为了产生一颗泛化能力强的决策树。

套用俗语，决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：

女儿：多大年纪了？

母亲：26。

女儿：长的帅不帅？

母亲：挺帅的。

女儿：收入高不？

母亲：不算很高，中等情况。

女儿：是公务员不？

母亲：是，在税务局上班呢。

女儿：那好，我去见见。

这个女孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么这个可以用下图表示女孩的决策逻辑：

上边的训练过程就是我所理解的决策树构建过程，其实它就是一个将数据按属性分堆的过程。虽然名字叫的挺高大上的，但是背后的逻辑却十分简单。

既然决策树那么简单，我想有人应该会疑问“为什么还有那么多的人在一直研究和使用决策树”了。其实，这也不难理解吧，既然决策树的背后逻辑十分简单（其实大多数算法的思想都很简单，大家不要被复杂的公式吓到），那么它较难的地方就不在于这个背后逻辑了，它难的一定是在别的地方。

也许细心的人已经发现了我所举的例子中有些问题是没有解答的，比如我们是根据什么策略来决定属性测试的顺序的（年龄 > 长相 > 收入 > 公务员）；这些选定属性的取值是如何决定的（什么叫帅、什么叫丑，标准是什么）；这个构建的决策树是否足够泛化，能涵盖新样本数据的可能情况等

这些问题才是决策树tricky的地方所在，不过没关系，大家不要着急，这些内容我们将在下边一一进行解答。

2）属性的划分选择

随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”（purity）越来越高。

要使得结点纯度越来越高，我们得要选择合适的指标来对纯度进行评估，并且我们也得要在这些指标上对属性的划分进行选择。目前决策树主流使用的属性划分指标为以下三个：

［1］信息增益

“信息熵”（information entropy）是度量样本集合纯度最常用的一种指标。其代表的是不同的类别在数据在总数据集中的熵的和，当样本集合越“纯”时，信息熵越小（信息熵的取值范围为0～log2(k)）。

既然信息熵代表的是样本集合的纯度，那么我们一个合理的属性划分逻辑可以是这样的：当用一个属性对样本进行划分后，分开的不同样本集合的信息墒之和纯度最高，那么这个属性就是目前最好的划分选择。

原始信息熵与新的划分后的信息墒之差就是这次属性划分的“信息增益”（information gain），所以我们的属性划分选择就是在每个结点找到最高信息增益的属性。

［2］增益率（gain ratio）

信息增益是个优秀的属性划分指标，可实际上，信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，选择增益率来选择最优划分属性。

增益率是让信息增益除以选择的划分属性的“固有值”（intrinsic value）。一般来说属性a的可能取值数目越多，则固有值越大，所以信息增益除以固有值后，抵消了信息增益对取值数目多的属性的偏好。

需注意的是，信息增益除以固有值后获得的增益率反而是偏爱取值数目较少的属性的，所以一个合理利用增益率来对属性划分的方法是：先从候选划分属性中选出信息增益高于平均水平的属性，再从中选择增益率最高的。

［3］基尼指数

基尼值的公式如下：

Gini(D) = 1 - pk的平方

从上式可以看出，基尼值反映了从数据集D中随机抽取两个样本，其类别标记不一致的概率。因此，基尼值越小，则数据集D的纯度越高。

那么同信息增益的选择策略一样：当用一个属性对样本进行划分后，原始基尼值与新划分后的不同样本集合的基尼值之和的差值就是“基尼指数”（Gini index），所以我们的属性划分选择就是在每个结点找到划分后最高基尼指数的属性。

3）剪枝处理

剪枝（pruning）是决策树学习算法对付“过拟合”的主要手段。为了尽可能正确分类训练样本，会不断的进行结点划分，有时会造成决策树分支过多，这时就可能因为训练过程学得太好了，将训练集自身的一些特点当作普遍化特征进行学习而会导致过拟合。

因此，可通过主动去掉一些分支来降低过拟合的风险。目前决策树剪枝的基本策略有以下两种：

［1］预剪枝

在决策树生成过程中，对每个结点在划分前后进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。

［2］后剪枝

在训练出一颗完整的决策树之后，自底向上的对非叶结点进行考察，若将该结点对应的子树替换成叶结点能提升泛化性能，则将该子树替换为叶结点。

［3］剪枝过程

使用第二章中提到的性能评估方法来比较泛化性能的改变；

从样本预留出一部分数据用作“验证集”以进行性能评估。

4）连续与缺失值

在前边提到的决策树处理逻辑中的属性使用的都是离散值，那么当遇到属性是连续或缺失时，我们应该知道该如何处理。

［1］连续值处理

遇到连续值属性的一个合适的处理逻辑是：将连续值转换为离散值不就得了。我们需要做的是将训练样本中该属性的所有取值进行排序，并对这排好序的取值队列进行分区划分，每一个分区即为该属性的一个离散点取值。

不失一般性，我们就取二分法（即分为两个分区，可以根据需要分为N个）来进行描述。以身高划分为例，训练集中身高数据取值（cm）排序如下：

｛160，163，168，170，171，174，177，179，180，183｝

因为是二分法，我们只需要找到一个划分点即可。每个划分点可放在两个取值之间，也可放在一个取值之上，这里我们取两个取值之间的中位数。那么上边例子中可选的划分点为：

｛161.5，165.5，169，170.5，172.5，175.5，178，179.5，181.5｝

根据不同的划分，我们可以分别计算一下信息增益的大小，然后选出一个最好的划分来。

需注意的是，和离散值不同，连续值的划分是可以在子结点上继续划分的。即你将身高划分为“小于175”和“大于等于175”两部分，对于“小于175”的子结点，你仍然可以继续划分为“小于160”和“大于160”两部分。

［2］缺失值处理

属性缺失时，我们需要处理两个问题：

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

不将缺失值的样本代入选择判断的公式计算（信息增益、增益率、基尼指数）之中，只在计算完后乘以一个有值的样本比例即可。

比如训练集有10个样本，在属性 a 上，有两个样本缺失值，那么计算该属性划分的信息增益时，我们可以忽略这两个缺失值的样本来计算信息增益，然后在计算结果上乘以8/10即可。

第二，若一个样本在划分属性上的值为空，它应该被分在哪个子结点中

若样本 x 在划分属性 a 上取值未知，则将 x 划入所有子结点，但是对划入不同子结点中的 x 赋予不同的权值（不同子结点上的不同权值一般体现为该子结点所包含的数据占父结点数据集合的比例）。

5）多变量决策树

在学习任务的真实分类边界比较复杂时，必须使用很多段划分才能获得较好的近似，此时的决策树会相当复杂，由于要进行大量的属性测试，预测时间开销会很大。

若能使用斜的划分边界，则决策树模型将大为简化，这就是多变量决策树（multivariate decision tree）。在此类决策树中，非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试；换言之，每个非叶结点时一个形如线性回归的线性分类器了。下图是一个在连续属性密度和含糖率上的选瓜多变量决策树样例：

2. 基础知识

1）信息熵

2）信息增益

3）增益率

4）基尼指数

3. 总结

1）决策树采用的是一种简单且直观的“分而治之”（divide-and-conquer）策略

2）决策树根据数据集的总体纯度来衡量不同属性划分的优劣

3）当属性选择过于频繁会导致模型过拟合，这时候就需要使用剪枝算法来进行处理

4）剪枝算法的判断标准是剪枝前后模型的性能指标是否提高

5）当遇到连续值的属性时，可以通过将其拆解成两块的方式将数据转换为离散值

6）当遇到缺失值属性时，可以通过在属性选择算法中加入缺失值数据的影响来适应

7）在处理真实分类边界比较复杂的学习任务时，我们可以使用属性的线性组合来对数据进行划分