2.11　决策树

在机器学习中，决策树（Decision Tree）是一个预测模型，它代表的是对象属性与对象值之间的一种映射关系。本节主要介绍决策树的基本原理、生成过程、算法描述、算法优缺点、决策树中的熵及信息增益等。

2.11.1　决策树的基本原理

决策树是一种分而治之的决策过程。一个困难的预测问题，通过树的分支节点，被划分成两个或多个较为简单的子集，从结构上划分为不同的子问题。依照规则对数据集进行递归分割（Recursive Partitioning）。随着树的深度不断增加，分支节点的子集越来越小，所需要提的问题数也逐渐简化。当分支节点的深度或者问题的简单程度满足一定的停止规则（Stopping Rule）时，该分支节点会停止分裂，此为自上而下的停止阈值（Cutoff Threshold）法；有些决策树也使用自下而上的剪枝（Pruning）法。

2.11.2　决策树的生成过程

决策树的生成过程如下。

（1）特征选择：从训练数据众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有很多不同量化的评估标准，从而衍生出不同的决策树算法。

（2）决策树生成：根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分时，决策树停止生长。

（3）剪枝：决策树容易过拟合，一般需要剪枝，缩小树结构规模以缓解过拟合。剪枝技术有预剪枝和后剪枝两种。

2.11.3　决策树学习基本算法步骤

决策树学习基本算法步骤如下。

2.11.4　决策树算法的优缺点

决策树算法的优点如下。

（1）易理解，机理解释起来较简单。

（2）可以用于小数据集。

（3）时间复杂度较小，为用于训练决策树的数据点的对数。

（4）相比于其他算法，决策树算法在智能分析一种类型变量时可处理数字和数据的类别。

（5）可以处理多输出的问题。

（6）对缺失值不敏感。

（7）可以处理不相关特征数据。

（8）效率高，决策树只需要一次构建，就可以反复使用，每一次预测的最大计算次数不超过决策树的深度。

决策树算法的缺点如下。

（1）对连续性的字段比较难预测。

（2）容易出现过拟合。

（3）当类别太多时，错误可能会增加得比较快。

（4）在处理特征关联性比较强的数据时表现得不太好。

（5）对于各类别样本数量不一致的数据，在决策树当中，信息增益的结果偏向于那些具有更多数值的特征。

2.11.5　决策树和熵的联系

熵在决策树中起到了绝对作用，贯穿决策树的中心。决策树最重要的就是最优属性选择，这个最优属性选择的标准就得依靠熵。

2.11.6　熵的概念及定义

熵用于度量随机变量的不确定性。

假设随机变量X的可能取值有，对于每一个可能的取值xi，其概率为。随机变量的熵为：

对于样本集合，假设样本有k个类别，每个类别的概率为，其中，|Ck|是类别为k的样本个数，|D|为样本总数。样本集合D的熵为：

2.11.7　理解信息增益

信息增益指以某特征划分数据集前后的熵的差值。

熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。

假设划分前样本集合D的熵为H（D）。使用某个特征A划分数据集D，计算划分后的数据子集的熵为H（D|A）。

则信息增益为：

注：在决策树构建的过程中，我们总是希望集合往最快到达纯度更高的子集合方向发展，因此我们总是选择使得信息增益最大的特征来划分当前数据集D。

计算所有特征划分数据集D，得到多个特征划分数据集D的信息增益，从这些信息增益中选择最大的，因而当前节点的划分特征便是使信息增益最大的划分所使用的特征。

另外这里提一下信息增益比相关知识：

信息增益比=惩罚参数×信息增益

信息增益比的本质是在信息增益的基础之上乘上一个惩罚参数。当特征个数较多时，惩罚参数较小；当特征个数较少时，惩罚参数较大。

惩罚参数是数据集D以特征A作为随机变量的熵的倒数。

2.11.8　决策树中熵、条件熵和信息增益的联系

首先来看熵、条件熵及信息增益三者的基本概念。

（1）熵：表示一个随机变量的复杂性或者不确定性。

（2）条件熵：表示在知道某一条件后，某一随机变量的复杂性或不确定性。

（3）信息增益：表示在知道某一条件后，某一随机变量的不确定性的减少量。

假如我想买一件衣服，一直犹豫着要不要买，我决定买这件事的不确定性（熵）为2.8。

我在网上看了这件衣服的评价后，决定买衣服这件事的不确定性（条件熵）是1.2。

我在线下实体店试穿衣服后，决定买衣服这件事的不确定性（条件熵）是0.9。

看了网上的评价后，此时的信息增益为2.8减1.2，等于1.6。

线下试穿了衣服，此时的信息增益为2.8减0.9，等于1.9。

显然在线下试穿衣服之后对于决定买这件衣服的不确定性下降更多，也就是试穿衣服之后买这件衣服的可能性更大了。所以看网上评价和线下试穿两个属性，首先应该选择线下试穿来构建内部节点。

2.11.9　决策树算法中剪枝的作用及策略

剪枝处理是决策树算法用来解决过拟合问题的一种办法。

在决策树算法中，为了尽可能正确地分类训练样本，节点划分过程不断重复，有时候会导致决策树分支过多，以至于将训练样本集自身特点当作泛化特点，从而导致过拟合。因此可以采用剪枝处理来去掉一些分支来降低过拟合的风险。

剪枝的基本策略有预剪枝（Pre-Pruning）和后剪枝（Post-Pruning）。

（1）预剪枝：在决策树生成过程中，在每个节点划分前先估计其划分后的泛化性能提升与否，如果不能提升，则停止划分，将当前节点标记为叶结点。

（2）后剪枝：生成决策树以后，再自下而上对非叶结点进行考察，若将此节点标记为叶结点可以带来泛化性能提升，则修改之。