3.1、摘要

在这一篇文章中，将讨论一种被广泛使用的分类算法——决策树（decision tree）。决策树的优势在于构造过程不需要任何领域知识或参数设置，因此在实际应用中，对于探测式的知识发现，决策树更加适用。

3.2、决策树引导

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

女儿：多大年纪了？

母亲：26。

女儿：长的帅不帅？

母亲：挺帅的。

女儿：收入高不？

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

女儿：是公务员不？

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

女儿：那好，我去见见。

这个女孩的决策过程就是典型的分类树决策。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么这个可以用下图表示女孩的决策逻辑（声明：此决策树纯属为了写文章而YY的产物，没有任何根据，也不代表任何女孩的择偶倾向，请各位女同胞莫质问我^_^）：

机器学习之决策树

上图完整表达了这个女孩决定是否见一个约会对象的策略，其中绿色节点表示判断条件，橙色节点表示决策结果，箭头表示在一个判断条件在不同情况下的决策路径，图中红色箭头表示了上面例子中女孩的决策过程。

这幅图基本可以算是一颗决策树，说它“基本可以算”是因为图中的判定条件没有量化，如收入高中低等等，还不能算是严格意义上的决策树，如果将所有条件量化，则就变成真正的决策树了。

有了上面直观的认识，我们可以正式定义决策树了：

决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

可以看到，决策树的决策过程非常直观，容易被人理解。目前决策树已经成功运用于医学、制造产业、天文学、分支生物学以及商业等诸多领域。知道了决策树的定义以及其应用方法，下面介绍决策树的构造算法。

3.3、决策树的构造

不同于贝叶斯算法，决策树的构造过程不依赖领域知识，它使用属性选择度量来选择将元组最好地划分成不同的类的属性。所谓决策树的构造就是进行属性选择度量确定各个特征属性之间的拓扑结构。

构造决策树的关键步骤是分裂属性。所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支，其目标是让各个分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别。分裂属性分为三种不同的情况：

1、属性是离散值且不要求生成二叉决策树。此时用属性的每一个划分作为一个分支。

2、属性是离散值且要求生成二叉决策树。此时使用属性划分的一个子集进行测试，按照“属于此子集”和“不属于此子集”分成两个分支。

3、属性是连续值。此时确定一个值作为分裂点split_point，按照>split_point和<=split_point生成两个分支。

构造决策树的关键性内容是进行属性选择度量，属性选择度量是一种选择分裂准则，是将给定的类标记的训练集合的数据划分D“最好”地分成个体类的启发式方法，它决定了拓扑结构及分裂点split_point的选择。

属性选择度量算法有很多，一般使用自顶向下递归分治法，并采用不回溯的贪心策略。这里介绍ID3和C4.5两种常用算法。

3.3.1、ID3算法

从信息论知识中我们直到，期望信息越小，信息增益越大，从而纯度越高。所以ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。下面先定义几个要用到的概念。

设D为用类别对训练元组进行的划分，则D的熵（entropy）表示为：

机器学习之决策树

其中pi表示第i个类别在整个训练元组中出现的概率，可以用属于此类别元素的数量除以训练元组元素总数量作为估计。熵的实际意义表示是D中元组的类标号所需要的平均信息量。

现在我们假设将训练元组D按属性A进行划分，则A对D划分的期望信息为：

机器学习之决策树

而信息增益即为两者的差值：

机器学习之决策树

ID3算法就是在每次需要分裂时，计算每个属性的增益率，然后选择增益率最大的属性进行分裂。下面我们继续用SNS社区中不真实账号检测的例子说明如何使用ID3算法构造决策树。为了简单起见，我们假设训练集合包含10个元素：

机器学习之决策树

其中s、m和l分别表示小、中和大。

设L、F、H和R表示日志密度、好友密度、是否使用真实头像和账号是否真实，下面计算各属性的信息增益。

机器学习之决策树

因此日志密度的信息增益是0.276。

用同样方法得到H和F的信息增益分别为0.033和0.553。

因为F具有最大的信息增益，所以第一次分裂选择F为分裂属性，分裂后的结果如下图表示：

机器学习之决策树

在上图的基础上，再递归使用这个方法计算子节点的分裂属性，最终就可以得到整个决策树。

上面为了简便，将特征属性离散化了，其实日志密度和好友密度都是连续的属性。对于特征属性为连续值，可以如此使用ID3算法：

先将D中元素按照特征属性排序，则每两个相邻元素的中间点可以看做潜在分裂点，从第一个潜在分裂点开始，分裂D并计算两个集合的期望信息，具有最小期望信息的点称为这个属性的最佳分裂点，其信息期望作为此属性的信息期望。

3.3.2、C4.5算法

ID3算法存在一个问题，就是偏向于多值属性，例如，如果存在唯一标识属性ID，则ID3会选择它作为分裂属性，这样虽然使得划分充分纯净，但这种划分对分类几乎毫无用处。ID3的后继算法C4.5使用增益率（gain ratio）的信息增益扩充，试图克服这个偏倚。

C4.5算法首先定义了“分裂信息”，其定义可以表示成：

机器学习之决策树

其中各符号意义与ID3算法相同，然后，增益率被定义为：

机器学习之决策树

C4.5选择具有最大增益率的属性作为分裂属性，其具体应用与ID3类似，不再赘述。

3.3.3 CART算法

-------占位-------

决策树是表示基于特征对实例进行分类的树形结构

从给定的训练数据集中，依据特征选择的准则，递归的选择最优划分特征，并根据此特征将训练数据进行分割，使得各子数据集有一个最好的分类的过程。

决策树算法3要素：

- 特征选择
- 决策树生成
- 决策树剪枝

部分理解：

关于决策树生成

决策树的生成过程就是使用满足划分准则的特征不断的将数据集划分为纯度更高，不确定性更小的子集的过程。

对于当前数据集D的每一次的划分，都希望根据某特征划分之后的各个子集的纯度更高，不确定性更小。

而如何度量划分数据集前后的数据集的纯度以及不确定性呢？

答案：特征选择准则，比如：信息增益，信息增益率，基尼指数

特征选择准则：

目的：使用某特征对数据集划分之后，各数据子集的纯度要比划分前的数据集D的纯度高（不确定性要比划分前数据集D的不确定性低。）

注意：

1. 划分后的纯度为各数据子集的纯度的加和（子集占比*子集的经验熵）。

2. 度量划分前后的纯度变化用子集的纯度之和与划分前的数据集D的纯度进行对比。

特征选择的准则就是度量样本集合不确定性以及纯度的方法。本质相同，定义不同而已。

特征选择的准则主要有以下三种：信息增益，信息增益率，基尼指数

首先介绍一下熵的概念以及理解：

熵：度量随机变量的不确定性。（纯度）

定义：假设随机变量X的可能取值有x_1，x₂， ... , x_n

对于每一个可能的取值x_i，其概率 P(X=x_i) = p_i, ( i = 1,2, ... , n)

因此随机变量X的熵：

对于样本集合D来说，随机变量X是样本的类别，即，假设样本有k个类别，每个类别的概率是机器学习之决策树，其中|C_k|表示类别k的样本个数，|D|表示样本总数

则对于样本集合D来说熵（经验熵）为：

机器学习之决策树

信息增益（ ID3算法）

定义：以某特征划分数据集前后的熵的差值

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

划分前样本集合D的熵是一定的，entroy(前)，

使用某个特征A划分数据集D，计算划分后的数据子集的熵 entroy(后)

信息增益 = entroy(前) - entroy(后)

书中公式:

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

信息增益的理解：

对于待划分的数据集D，其 entroy(前)是一定的，但是划分之后的熵 entroy(后)是不定的，entroy(后)越小说明使用此特征划分得到的子集的不确定性越小（也就是纯度越高），因此 entroy(前) - entroy(后)差异越大，说明使用当前特征划分数据集D的话，其纯度上升的更快。而我们在构建最优的决策树的时候总希望能更快速到达纯度更高的集合，这一点可以参考优化算法中的梯度下降算法，每一步沿着负梯度方法最小化损失函数的原因就是负梯度方向是函数值减小最快的方向。同理：在决策树构建的过程中我们总是希望集合往最快到达纯度更高的子集合方向发展，因此我们总是选择使得信息增益最大的特征来划分当前数据集D。

缺点：信息增益偏向取值较多的特征

原因：当特征的取值较多时，根据此特征划分更容易得到纯度更高的子集，因此划分之后的熵更低，由于划分前的熵是一定的，因此信息增益更大，因此信息增益比较偏向取值较多的特征。

解决方法 : 信息增益比（ C4.5算法）

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

书中公式：

注意：其中的H_A(D)，对于样本集合D，将当前特征A作为随机变量（取值是特征A的各个特征值），求得的经验熵。

（之前是把集合类别作为随机变量，现在把某个特征作为随机变量，按照此特征的特征取值对集合D进行划分，计算熵H_A(D)）

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

惩罚参数：数据集D以特征A作为随机变量的熵的倒数，即：将特征A取值相同的样本划分到同一个子集中（之前所说数据集的熵是依据类别进行划分的）

缺点：信息增益比偏向取值较少的特征

原因： 当特征取值较少时H_A(D)的值较小，因此其倒数较大，因而信息增益比较大。因而偏向取值较少的特征。

使用信息增益比：基于以上缺点，并不是直接选择信息增益率最大的特征，而是现在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。

基尼指数（ CART算法 ---分类树）

定义：基尼指数（基尼不纯度）：表示在样本集合中一个随机选中的样本被分错的概率。

注意： Gini指数越小表示集合中被选中的样本被分错的概率越小，也就是说集合的纯度越高，反之，集合越不纯。

即 基尼指数（基尼不纯度）= 样本被选中的概率 * 样本被分错的概率

书中公式：

机器学习之决策树

说明:

1. p_k表示选中的样本属于k类别的概率，则这个样本被分错的概率是(1-p_k)

2. 样本集合中有K个类别，一个随机选中的样本可以属于这k个类别中的任意一个，因而对类别就加和

3. 当为二分类是，Gini(P) = 2p(1-p)

样本集合D的Gini指数： 假设集合中有K个类别，则：

机器学习之决策树

基于特征A划分样本集合D之后的基尼指数：

需要说明的是CART是个二叉树，也就是当使用某个特征划分样本集合只有两个集合：1. 等于给定的特征值的样本集合D₁ ， 2 不等于给定的特征值的样本集合D₂

实际上是对拥有多个取值的特征的二值处理。

举个例子：

假设现在有特征 “学历”，此特征有三个特征取值： “本科”，“硕士”， “博士”，

当使用“学历”这个特征对样本集合D进行划分时，划分值分别有三个，因而有三种划分的可能集合，划分后的子集如下：

1. 划分点： “本科”，划分后的子集合： {本科}，{硕士，博士}
2. 划分点： “硕士”，划分后的子集合： {硕士}，{本科，博士}
3. 划分点： “硕士”，划分后的子集合： {博士}，{本科，硕士}

对于上述的每一种划分，都可以计算出基于 划分特征= 某个特征值 将样本集合D划分为两个子集的纯度：

机器学习之决策树

因而对于一个具有多个取值（超过2个）的特征，需要计算以每一个取值作为划分点，对样本D划分之后子集的纯度Gini(D,A_i)，(其中A_i 表示特征A的可能取值)

然后从所有的可能划分的Gini(D,A_i)中找出Gini指数最小的划分，这个划分的划分点，便是使用特征A对样本集合D进行划分的最佳划分点。

3.4、关于决策树的几点补充说明

3.4.1、如果属性用完了怎么办

在决策树构造过程中可能会出现这种情况：所有属性都作为分裂属性用光了，但有的子集还不是纯净集，即集合内的元素不属于同一类别。在这种情况下，由于没有更多信息可以使用了，一般对这些子集进行“多数表决”，即使用此子集中出现次数最多的类别作为此节点类别，然后将此节点作为叶子节点。

3.4.2 过度拟合怎么办？？？

优化方案1：修剪枝叶

决策树过渡拟合往往是因为太过“茂盛”，也就是节点过多，所以需要裁剪（Prune Tree）枝叶。裁剪枝叶的策略对决策树正确率的影响很大。主要有两种裁剪策略。

前置裁剪 在构建决策树的过程时，提前停止。那么，会将切分节点的条件设置的很苛刻，导致决策树很短小。结果就是决策树无法达到最优。实践证明这中策略无法得到较好的结果。

后置裁剪 决策树构建好后，然后才开始裁剪。采用两种方法：1）用单一叶节点代替整个子树，叶节点的分类采用子树中最主要的分类；2）将一个字数完全替代另外一颗子树。后置裁剪有个问题就是计算效率，有些节点计算后就被裁剪了，导致有点浪费。

优化方案2：K-Fold Cross Validation

首先计算出整体的决策树T，叶节点个数记作N，设i属于[1,N]。对每个i，使用K-Fold Validataion方法计算决策树，并裁剪到i个节点，计算错误率，最后求出平均错误率。这样可以用具有最小错误率对应的i作为最终决策树的大小，对原始决策树进行裁剪，得到最优决策树。

优化方案3：Random Forest

Random Forest是用训练数据随机的计算出许多决策树，形成了一个森林。然后用这个森林对未知数据进行预测，选取投票最多的分类。实践证明，此算法的错误率得到了经一步的降低。这种方法背后的原理可以用“三个臭皮匠定一个诸葛亮”这句谚语来概括。一颗树预测正确的概率可能不高，但是集体预测正确的概率却很高。

准确率估计

决策树T构建好后，需要估计预测准确率。直观说明，比如N条测试数据，X预测正确的记录数，那么可以估计acc = X/N为T的准确率。但是，这样不是很科学。因为我们是通过样本估计的准确率，很有可能存在偏差。所以，比较科学的方法是估计一个准确率的区间，这里就要用到统计学中的置信区间（Confidence Interval）。

设T的准确率p是一个客观存在的值，X的概率分布为X ~ B(N,p)，即X遵循概率为p，次数为N的二项分布（Binomial Distribution），期望E(X) = N*p，方差Var(X) = N*p*(1-p)。由于当N很大时，二项分布可以近似有正太分布（Normal Distribution）计算，一般N会很大，所以X ~ N(np,n*p*(1-p))。可以算出，acc = X/N的期望E(acc) = E(X/N) = E(X)/N = p，方差Var(acc) = Var(X/N) = Var(X) / N² = p*(1-p) / N，所以acc ~ N(p,p*(1-p)/N)。这样，就可以通过正太分布的置信区间的计算方式计算执行区间了。

正太分布的置信区间求解如下：

1）将acc标准化，即