数据挖掘算法02 - C4.5

迷南。 2022-01-27 12:27 161阅读 0赞

## C4.5 ##

> 决策树学习通常包括三个步骤

*  特征选择。选取最优特征来划分特征空间，用信息增益或者信息增益比来选择
 *  决策树的生成。ID3、C4.5、CART
 *  剪枝

> 什么是信息熵？

*  随机变量

*  概率

P(x) 表示 x 出现的概率

*  信息量

H(x)=−log(P(x))

信息量是信息论中的一个度量，简单来说就是，当我们观察到某个随机变量的具体值时，接收到了多少信息。

而我们接收到的信息量跟发生事件的概率有关。**事情发生的概率越大，产生的信息量越小；事情发生的概率越小，产生的信息量越大**。

*  纯净度

你可以把决策树的构造过程理解成为寻找纯净划分的过程。数学上，我们可以用**纯度**来表示，纯度换一种方式来解释就是让目标变量的**分歧**最小。

*  熵（混乱度 | 纯净度）

某个随机变量的信息量之期望。

![f9da465b8601bb84b97022afd88cbac0.png][]

从集合和分组的角度来说，如果一个集合里的元素**趋向于落在同一分组里**，那么告诉你某个元素属于哪个分组的信息量就越小，整个集合的**熵也越小**，换句话说，整个集合就**越“纯净”**。

相反，如果一个集合里的元素**趋向于分散在不同分组里**，那么告诉你某个元素属于哪个分组的信息量就越大，整个集合的**熵也越大**，换句话说，整个集合就**越“混乱”**。

一个集合中所包含的分组越多、元素在这些分组里分布得越均匀，熵值也越大。而熵值表示了纯净的程度，或者从相反的角度来说，是混乱的程度。

从**混乱**的程度去理解信息熵，它能帮我们反映出来这个信息的**不确定度**。当不确定性越大时，它所包含的信息量也就越大，信息熵也就越高。

信息熵越大，纯度越低。当集合中的所有样本均匀混合时，信息熵最大，纯度最低。

我们在构造决策树的时候，会基于纯度来构建。而经典的 “不纯度”的指标有三种，分别是信息增益（ID3 算法）、信息增益率（C4.5 算法）以及基尼指数（Cart 算法）。

*  多个小集合的整体的熵

好了，你已经知道单个集合的熵是如何计算的了。那么，如果将一个集合划分成多个更小的集合之后，又该如何根据这些小集合，来计算整体的熵呢？之前我们提到了信息量和熵具有加和的性质，所以对于包含多个集合的更大集合，它的信息量期望值是可以通过每个小集合的信息量期望值来推算的。具体来说，我们可以使用如下公式：

![cd8f5873383759df7782b37f125bb1d3.png][]

其中，T 表示一种划分，Pv 表示划分后其中某个小集合，Entropy(Pv)表示某个小集合的熵， 而 |Pv|/|P| 表示某个小集合出现的概率。所以这个公式其实就表示，**对于多个小集合而言，其整体的熵等于各个小集合之熵的加权平均**。而每个小集合的权重是其在整体中出现的概率。

> 什么是信息增益？（区分能力）

如果我们将划分前后的整体熵做个对比，你会发现划分后的整体熵要小于划分之前的整体熵。这是因为每次划分，都可能将不同分组的元素区分开来，**降低划分后每个小集合的混乱程度**，也就是降低它们的熵。我们将划分后整体熵的下降，称为**信息增益**（Information Gain）。如果划分后整体熵下降的越多，信息增益就越大。我列出公式便于你的理解。

![7268dcacc996164ba51a499db45de679.png][]

其中 T 表示当前选择的特征，Entropy§ 表示选择特征 T 之前的熵，Entropy(Pv)表示特征 T 取值为 v 分组的熵。减号后面的部分表示选择 T 做决策之后，各种取值加权平均后整体的熵。Gain(P,T) 表示两个熵值之差，越大表示信息增益越多，应该选择这维特征 T。

我们把这个概念放到咱们的小游戏里就是，如果一个测试问题能够将来自不同分组的人物尽量的分开，也就是该划分对应的**信息增益越高，那么我们就认为其区分能力越高，提供的信息含量也越多**。

信息增益和信息熵是紧密相关的。如果说信息熵衡量了某个状态下，每个分组的纯净程度或者说混乱程度，那么信息增益就是比较了不同状态下，信息熵的差异程度。

信息增益指的就是**划分可以带来纯度的提高**，信息熵的下降。它的计算公式，是父亲节点的信息熵减去所有子节点的信息熵。在计算的过程中，我们会计算每个子节点的归一化信息熵，即按照每个子节点在父节点中出现的概率，来计算这些子节点的信息熵。

> 如何通过信息熵挑选合适的问题？

为了实现一个更简短的问卷，你也许很自然地就想到，每次选择问题的时候，我们可以选择信息增益最高的问题，这样熵值下降得就最快。这的确是个很好的方法。我们来试一试。

![9db1ccd4fd4aa2cd03d74f02811abb1c.png][]

从这个图可以看出来，对于每种人物的判断，我们至多需要问 3 个问题，没有必要问全 5 个问题。比如，对于人物 J 和 C，我们只需要问 2 个问题。假设读者属于 10 种武侠人物的概率是均等的，那么我们就可以利用之前介绍的知识，来计算读者需要回答的问题数量之期望值。每种人物出现的概率是 0.1，8 种人物需要问 3 个问题，2 种人物需要问 2 个问题，那么回答问题数的期望值是 0.8 \* 3 + 0.2 \* 2 = 2.8（题）。

好了，现在我们总结一下，如何才能进行高效的问卷调查。最核心的思想是，根据当前的概率分布，挑选在当前阶段区分能力更强的那些问题。具体的步骤有三个。

*  第一步，根据分组中的人物类型，为每个集合计算信息熵，并通过全部集合的熵之加权平均，获得整个数据集的熵。注意，一开始集合只有一个，并且包含了所有的武侠人物。
 *  第二步，根据信息增益，计算每个问卷题的区分能力。挑选区分能力最强的题目，并对每个集合进行更细的划分。
 *  第三步，有了新的划分之后，回到第一步，重复第一和第二步，直到没有更多的问卷题，或者所有的人物类型都已经被区分开来。这一步也体现了递归的思想。

其实，上述这个过程就体现了训练**决策树**（Decision Tree）的基本思想。决策树学习属于归纳推理算法之一，适用于分类问题。在前面介绍朴素贝叶斯的时候，我说过，分类算法主要包括了建立模型和分类新数据两个阶段。决定问卷题出现顺序的这个过程，其实就是建立决策树模型的过程。

> ID3

ID3 就是要将**信息增益最大**的节点作为父节点，这样可以得到纯度高的决策树。

随着机器学习的快速发展，人们也提出了不少优化版的决策树。采用信息增益来构建决策树的算法被称为**ID3**（Iterative Dichotomiser 3，迭代二叉树 3 代）。但是这个算法有一个**缺点**，它一般会**优先考虑具有较多取值的特征**，因为取值多的特征会有相对较大的信息增益。这是为什么呢？

> C4.5 算法

你仔细观察一下信息熵的定义，就能发现背后的原因。更多的取值会把数据样本划分为更多更小的分组，这样熵就会大幅降低，信息增益就会大幅上升。但是这样构建出来的树，很容易导致机器学习中的**过拟合现象**，不利于决策树对新数据的预测。为了克服这个问题，人们又提出了一个改进版，**C4.5 算法**。

这个算法使用**信息增益率**（Information Gain Ratio）来替代信息增益，作为选择特征的标准，并降低决策树过拟合的程度。信息增益率通过引入一个被称作**分裂信息**（Split Information）的项来惩罚取值较多的特征，我把相应的公式给你列出来了。

![1d2d93ed55bfe09f256a9b72ca6c88a2.png][]

其中，训练数据集 P 通过属性 T 的属性值，划分为 n 个子数据集，|Pi| 表示第 i 个子数据集中样本的数量，|P| 表示划分之前数据集中样本总数量。 这个公式看上去和熵很类似，其实并不相同。

熵计算的时候考虑的是，集合内数据是否属于**同一个类**，因此即使集合数量很多，但是集合内的数据如果都是来自相同的分类（或分组），那么熵还是会很低。而这里的分裂信息是不同的，它只考虑子集的数量。如果某个特征取值很多，那么相对应的子集数量就越多，最终分裂信息的值就会越大。正是因为如此，人们可以使用分裂信息来惩罚取值很多的特征。具体的计算公式如下：

![01f28b759dae3e5fa7139535984eb6c4.png][]

其中 Gain(P,T)是数据集 P 使用特征 T 之后的信息增益，GainRatio(P,T) 是数据集 P 使用特征 T 之后的信息增益率。

> 如何判断要不要去打篮球？

![327eafa4a33e3e76ca86ac59195c0307.png][]

![a6d66a655c5d82ea81299a7351694a3f.jpg][]

所以 ID3 有一个缺陷就是，**有些属性可能对分类任务没有太大作用，但是他们仍然可能会被选为最优属性**。这种缺陷不是每次都会发生，只是存在一定的概率。在大部分情况下，ID3 都能生成不错的决策树分类。针对可能发生的缺陷，后人提出了新的算法进行改进。

> 在 ID3 算法上进行改进的 C4.5 算法

*  采用信息增益率

因为 ID3 在计算的时候，倾向于选择取值多的属性。为了避免这个问题，C4.5 采用信息增益率的方式来选择属性。信息增益率 = 信息增益 / 属性熵，具体的计算公式这里省略。

当属性有很多值的时候，相当于被划分成了许多份，虽然信息增益变大了，但是对于 C4.5 来说，属性熵也会变大，所以整体的信息增益率并不大。

*  采用悲观剪枝

ID3 构造决策树的时候，容易产生过拟合的情况。在 C4.5 中，会在决策树构造之后采用悲观剪枝（PEP），这样可以提升决策树的泛化能力。

悲观剪枝是后剪枝技术中的一种，通过递归估算每个内部节点的分类错误率，比较剪枝前后这个节点的分类错误率来决定是否对其进行剪枝。这种剪枝方法不再需要一个单独的测试数据集。

*  离散化处理连续属性

C4.5 可以处理连续属性的情况，对连续的属性进行离散化的处理。比如打篮球存在的“湿度”属性，不按照“高、中”划分，而是按照湿度值进行计算，那么湿度取什么值都有可能。该怎么选择这个阈值呢，**C4.5 选择具有最高信息增益的划分所对应的阈值**。

*  处理缺失值

针对数据集不完整的情况，C4.5 也可以进行处理。

> ID3 & C4.5

现在我们总结下 ID3 和 C4.5 算法。首先 ID3 算法的优点是方法简单，缺点是对噪声敏感。训练数据如果有少量错误，可能会产生决策树分类错误。C4.5 在 ID3 的基础上，用信息增益率代替了信息增益，解决了噪声敏感的问题，并且可以对构造树进行剪枝、处理连续数值以及数值缺失等情况，但是由于 C4.5 需要对数据集进行多次扫描，算法效率相对较低。

> 总结

![d02e69930c8cf00c93578536933ad07a.png][]

[f9da465b8601bb84b97022afd88cbac0.png]: /images/20220127/31ddb990e1e047a58a73afb4d43b9109.png
[cd8f5873383759df7782b37f125bb1d3.png]: /images/20220127/910abf438dae489e9e26fd67f2729969.png
[7268dcacc996164ba51a499db45de679.png]: /images/20220127/b1f5c7a616014c1e96bec91f4a7fddf4.png
[9db1ccd4fd4aa2cd03d74f02811abb1c.png]: /images/20220127/8bc3c254eea146fbb5bd6645763a673b.png
[1d2d93ed55bfe09f256a9b72ca6c88a2.png]: /images/20220127/9873ed7bd7a64c69ad5e97213c93a280.png
[01f28b759dae3e5fa7139535984eb6c4.png]: /images/20220127/cc934349a20f4226bc98193b7150df49.png
[327eafa4a33e3e76ca86ac59195c0307.png]: /images/20220127/04818f9f35bd4a76899ccc0f8b63c9c5.png
[a6d66a655c5d82ea81299a7351694a3f.jpg]: /images/20220127/cda91b97ed2a4f3ab26b13e98a5a5e05.png
[d02e69930c8cf00c93578536933ad07a.png]: /images/20220127/a9518159ca644297a1dded0aaba3dd19.png