鹅厂优文·决策树及ID3算法学习

更多腾讯海量技术文章，请关注云加社区：https://cloud.tencent.com/developer

作者：袁明凯|腾讯IEG测试开发工程师

决策树的基础概念

决策树是一种用树形结构来辅助行为研究、决策分析以及机器学习的方式，是机器学习中的一种基本的分类方法。决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。决策树用于对条件到决策的过程进行建模。查看一个示例图：

示例给出了通过天气情况，晴天、雨天、多云、是否有风、以及湿度情况来决策判定是否适合游玩。由图可见，决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。当根据信息构建好决策树后，就可以依据决策树做出对给出的情况的决策结果判定了。决策树算法是一种监管学习，所谓监管学习就是给定一堆样本，每个样本都有一组属性和一个类别，这些类别是事先确定的，通过学习得到一个分类器，分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。

机器学习中，决策树是一个预测模型；它代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。由此可见，决策树最关键的点，就是选好决策的每个分支节点的决策条件的优先级，更好的保证更关键的决策条件在树的更上层，那么选择方法中，如果一个分割点（特征）可以将当前的所有节点分为两类，使得每一类都很“纯”即每一类的准确度都很高，也就是它们大多属于同一个目标结果，那么就是一个好分割点。这个分割的“纯度”的量化要有两种算法：基尼不纯度（Gini Impurity）和信息量（Entropy）。

GINI不纯度

基尼不纯度（Gini Impurity）是指，将来自集合中的某种结果随机应用在集合中，某一数据项的预期误差率，是决策树对于混杂程度预测的一种度量方式。

信息量

信息量（Entropy）可以指描述一件事情的难易程度，比如太阳从哪边升起，我只需要说东边；而世界杯哪支球队夺冠，我需要说可能是巴西、可能是德国、可能是西班牙、可能是……；下面三幅图，C是最容易描述的，信息量最小，而A是最不好描述的，信息量最大。换句话说，一件事情越“纯”，信息量越小。

信息量如何量化呢？其实就是描述这件事情需要使用多少bit位存储。抛出硬币的结果是正面还是反面，需要0或1存储，信息量为1bit。世界杯32支球队谁会夺冠，最多需要5bit存储。可以明显看出信息量是事件的所有可能性

以2为底的对数

。所以一条信息的不确定性越大，需要越多的空间存储，它的信息量就越大。发生概率为0或1的事件都是非常确定的事情，它们的信息量就为0。然而并不是所有事件结果的出现概率都像抛硬币那样是相同的。比如实际上世界杯32支球队的夺冠概率都是不同的，这种情况下该怎么算信息量呢？对之前的公式进行推导：

，设P为事件N中每个结果的概率，当每个结果出现概率相同时，公式如此。

而如果概率不同，记

为每个结果x1的概率，那么公式就变成了：香农熵公式：

，香农熵（Shannon Entropy）就是这样来量化计算信息大小，构建决策树就是要选择一个特征，将数据分割后信息量变得越小，越容易描述，越“纯”，就越好，因此也是此公式计算后值越小越好。还是以天气的案例，来做香农熵的计算，如果是原有信息量，不增加条件的话，

，如果增加了以天气情况分割的话，为：

晴天，有无去玩数据信息量：

雨天，有无去玩数据信息量：

多云，有无去玩数据信息量：

信息量再进行期望相加，得到分割后的信息量之和：

，通过对比发现天气分割后的信息量最小，且比原信息量小，所以这种分割是最好的。同样，沿着各自节点向下计算剩余特征的信息量，直到信息量为0或不再降低。

过度拟合

l 蓝线为Gini分布，红线为Entropy分布，经过实际验证在决策树算法中都能比较准确地进行分支；Entropy由于有Log运算，效率略微比Gini慢；

l 两者都只能以某个特征进行整体评估（比如户口），而不能具体到特征下某个特定类别上，比如多云的天气都适合出去玩，具备很高区分度，但不能被这两种算法挑出来，只能通过修改达到该目的并评估效果的差异。

l 就像前一条提到的，如果样本中多云天气100%适合出去玩，万一后面有一天多云天气风太大而不适合出去玩的话，就会出现决策失效。因此构造决策树很容易陷入过度拟合（Overfitting）的问题，如果不设置一定的限制条件，一定可以让训练数据集达到100%准确率，比如为每条数据都生成一个叶子节点。

案例，比如使用大小区分橘子和柚子，橘子大多比柚子小，所以理论上可以训练出体积在某个较小范围内的大多是橘子，而另一个范围是柚子，这样的决策树叶子节点。但如果不进行限制的话，决策树很可能会变成21cm3的是橘子、32cm3宽的是橘子、85cm3宽的是柚子，它针对训练集是100%准确的，但对训练集以外的数据就不能很好的进行决策了。

避免过度拟合一般有两种方式：约束决策树和剪枝。

约束决策树

约束决策树方法有很多种，需要根据情况或需求来选择或组合：

1. 设置每个叶子节点的最小样本数，这能避免某个特征类别只适用于极小量的样本；

2. 设置每个节点的最小样本数，与上类似，但它是从根节点就开始避免过度拟合；

3. 设置树的最大深度，避免无限往下划分；

4. 设置叶子节点的最大数量，避免出现无限多的划分类别；

5. 设置评估分割数据时的最大特征数量，避免每次都考虑所有特征为求“最佳”，而采取随机选取的方式避免过度拟合；

上面这些数据到底设置为多少合适呢，就需要使用实际的测试集来验证不同约束条件下的决策准确性来评估了。

剪枝

剪枝是先构造好决策树之后再进行调整，总体思路是：对每个节点或其子树进行裁剪，通过一些算法评估裁剪前后决策树模型对数据的预测能力是否有降低，如果没有降低则说明可以剪枝。

几个常用的剪枝评估方法：

l 错误率降低剪枝（Reduced Error Pruning，REP）

a) 使用某种顺序遍历节点

b) 删除以此节点为根节点的子树

c) 使此节点为叶子节点

d) 将训练集中该节点特征出现概率最大的那一类赋予此节点（即这个节点就代表这一类）

e) 计算整体误判率或准确率，如果比剪枝前更好，那么就剪掉

l 悲观剪枝（Pessimistic Error Pruning，PEP）

a) 评估单个节点（并非子树）是否裁剪

b) 使用该节点下所有叶子节点的误差之和评估

c) 当裁剪前后的误差率不超过某个标准值，则裁剪

l 代价复杂度剪枝（Cost Complexity Pruning，CCP）

a) 在CART算法中具体介绍

决策树算法的优劣

优势：简单易懂；可处理数值和类别两种类型的数据；只需要少量的训练集即可使用；使用白盒模型，可清晰观察每个步骤；对大数据量的处理性能较好；相比其他算法更贴近人类思维方式。

劣势：准确性不如其他算法，对连续性字段难预测，特别是时间顺序的数据，需要较多预处理工作；树的稳定性不足，训练集的小变化就可能引起整棵树的剧变，导致最终预测的变化；容易过拟合；决策树处理包含不同数值类别的特征数据时，容易倾向于选择取值更多的特征作为分割节点，对字段特例化严重的数据，例如游戏用户分析中的用户名，就更容易出现过拟合，并且类别越多，错误就会增加的更快。

ID3- Iterative Dichotomiser 3

ID3也就是第三代迭代式二分法，是一种基本的构建决策树的算法。ID3算法是一种贪心算法，用来构造决策树，每一步选择当前的最优决策，并不是整体可见的最优决策。ID3算法起源于概念学习系统（CLS），以信息熵的下降速度为选取测试属性的标准，即在每个节点选取还尚未被用来划分的具有最高信息增益的属性作为划分标准，然后继续这个过程，直到生成的决策树能完美分类训练样例。该算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。

信息熵

上文已介绍过信息量的概念，这里从另外一个角度来说明。熵是一个来源于物理学的概念，用于度量一个热力学系统的无序程度，一个系统越混乱，系统的熵值越大。在信息论中，熵用于度量事件的不确定性，不确定性越高则信息熵越大。如果事件发生前，事件的结果就已经确定，如一定发生，或者一定不发生，信息熵趋近于零。Shannon给出了度量信息熵的数学公式。对于随机变量X，其值域为，pi为xi发生的概率密度函数，则随机变量X的熵为：

，从信息熵的定义看，随机变量X的值域范围越广，概率分布越均匀，则随机变量对应的信息熵值越大。事件发生前，越难猜中结果，事件包含的信息熵越大。依然以天气数据为例：

对于Play这一列数据，14天中有9天适合游玩，5天不适合，假设9/14就是适合游玩的概率，则天气是否适合游玩的信息熵计算方法如下：

信息增益

数据通常包含多个特征值，例如天气数据包含湿度、风力、降雨等。如果将天气先按照某种属性进行分类，然后再计算其他列数据的信息熵，分类前的信息熵与分类后的信息熵的差值则为数据按某列属性进行分类后得到的信息增益。假设可以按某个属性划分成n类，每一类为Ti, |Ti|表示数量，划分后的信息熵计算方法如下：

，H（x）和H（p）表达相同的含义。信息增益的计算方法如下：

，还是以天气数据为例，计算是否适合游玩这一列数据按照温度划分后的的信息增益。温度分为hot、mild、cool三种，将天气是否时候游玩的数据按温度分成三部分：

划分后的信息量为：

则是否合适游玩的数据按照温度划分后的信息增益为：0.940-0.911=0.029bits。

ID3算法核心

ID3算法正是一种使用信息增益概念的贪心算法。算法步骤如下：

1） 在所有数据上依次计算每一个属性数据决策后带来的信息增益，选择信息增益最大的一个属性作为决策树的根节点，其实反向来说也就是选择信息熵最小的属性来做根节点。

2） 将数据第一步选择的属性进行分类，在每一个分类后的子集数据上创建依次计算剩余属性的信息增益，选择信息增益最大的属性作为根节点的叶子节点。

3） 重复执行第2）步，直到所有的子集只包含一个元素或者所有的属性都已经成为决策树的某个节点。

需要指出的是，ID3算法是一种贪心算法，每一步都选择当前子集上最大信息增益对应的属性作为节点。使用ID3该天气示例的最后建立的决策树结果如下：

ID3对所使用的样本数据是有一定要求的，第一无法处理连续性数据，需要离散型数据，除非连续数据被分解为模糊范畴的类别数据；第二需要足够的样本量，因为需要足够的数据来区分每种数据特征类别存在过度耦合，从而更好的消除特殊的情况数据影响；第三，使用信息增益作为节点的分裂标准，实际上并不合理，会倾向于选择取值较多的属性。

ID3的算法劣势

1、从信息增益的计算方法来看，信息增益无法直接处理连续取值的的属性数据，只能处理离散型的数据。

2、信息增益的计算方法需要对某列属性进行分类，如果属性是ID，按照ID分类后，所有的分类都只包含一个元素，即ID就是信息增益最大的属性，导致ID3算法失效。

3、如果预测数据中出现了训练样本中没有出现过的情况，ID3也是没有办法处理的。针对ID3算法的缺陷，后续发明了C4.5，CART，random forest等算法。