27 | 决策树：信息增益、增益比率和基尼指数的运用

Feb 15, 2019

27 | 决策树：信息增益、增益比率和基尼指数的运用-极客时间



下载APP





关闭

讲堂部落提薪训练营云原生训练营架构实战营企业版极客商城兑换中心 App下载浏览器插件

渠道合作

推荐作者

27 | 决策树：信息增益、增益比率和基尼指数的运用

2019-02-15 黄申来自北京

《程序员的数学基础课》

课程介绍



讲述：黄申

时长11:05大小10.13M



你好，我是黄申。
上一节，我通过问卷调查的案例，给你解释了信息熵和信息增益的概念。被测者们每次回答一道问题，就会被细分到不同的集合，每个细分的集合纯净度就会提高，而熵就会下降。在测试结束的时候，如果所有被测者都被分配到了相应的武侠人物名下，那么每个人物分组都是最纯净的，熵值都为 0。于是，测试问卷的过程就转化为“如何将熵从 3.32 下降到 0”的过程。
由于每道问题的区分能力不同，而我们对问题的选择会影响熵下降的幅度。这个幅度就是信息增益。如果问卷题的顺序选择得好，我们可以更快速地完成对用户性格的判定。这一节我们就继续这个话题，看看如何获得一个更简短的问卷设计，把这个核心思想推广到更为普遍的决策树分类算法中。
如何通过信息熵挑选合适的问题？为了实现一个更简短的问卷，你也许很自然地就想到，每次选择问题的时候，我们可以选择信息增益最高的问题，这样熵值下降得就最快。这的确是个很好的方法。我们来试一试。
我们现在开始选择第一个问题。首先，依次计算“性别”“智商”“情商”“侠义”和“个性”对人物进行划分后的信息增益。我们得到如下结果：
显然，第一步我们会选择“侠义”，之后用户就会被细分为 3 组。
针对第一组，我们继续选择在当前这组中，区分力最强、也是信息增益最高的问题。根据计算的结果我们应该选择有关“性别”的问题，然后进一步地细分。后续的步骤依次类推，直到所有人物都被分开，对于第二组和第三组我们也进行同样地操作。整个过程稍微有点复杂，为了帮你理解，我把它画成了一个图。
从这个图可以看出来，对于每种人物的判断，我们至多需要问 3 个问题，没有必要问全 5 个问题。比如，对于人物 J 和 C，我们只需要问 2 个问题。假设读者属于 10 种武侠人物的概率是均等的，那么我们就可以利用之前介绍的知识，来计算读者需要回答的问题数量之期望值。每种人物出现的概率是 0.1，8 种人物需要问 3 个问题，2 种人物需要问 2 个问题，那么回答问题数的期望值是 0.8 * 3 + 0.2 * 2 = 2.8（题）。
如果我们每次不选熵值最高的问题，而选择熵值最低的问题呢？
我计算了一下，最差的情况下，我们要问完全部 5 个问题，才能确定被测者所对应的武侠人物。而且问 4 个问题的情况也不少，回答问题数的期望值会在 4 到 5 之间，明显要多于基于最高熵来选择题目的方法。当然，如果测试的目标和问题很多，基于熵的问题选择其运算量就会比较大，我们就可以通过编程来自动化整个过程，最终达到优化问卷设计的目的。
好了，现在我们总结一下，如何才能进行高效的问卷调查。最核心的思想是，根据当前的概率分布，挑选在当前阶段区分能力更强的那些问题。具体的步骤有三个。
第一步，根据分组中的人物类型，为每个集合计算信息熵，并通过全部集合的熵值加权平均，获得整个数据集的熵。注意，一开始集合只有一个，并且包含了所有的武侠人物。
第二步，根据信息增益，计算每个问卷题的区分能力。挑选区分能力最强的题目，并对每个集合进行更细的划分。
第三步，有了新的划分之后，回到第一步，重复第一和第二步，直到没有更多的问卷题，或者所有的人物类型都已经被区分开来。这一步也体现了递归的思想。
其实，上述这个过程就体现了训练决策树（Decision Tree）的基本思想。决策树学习属于归纳推理算法之一，适用于分类问题。在前面介绍朴素贝叶斯的时候，我说过，分类算法主要包括了建立模型和分类新数据两个阶段。决定问卷题出现顺序的这个过程，其实就是建立决策树模型的过程。
你可以看到，整个构建出来的图就是一个树状结构，这也是“决策树”这个名字的由来。而根据用户对每个问题的答案，从决策树的根节点走到叶子节点，最后来判断其属于何种人物类型，这个过程就是分类新数据的过程。
让我们把问卷案例泛化一下，将武侠人物的类型变为机器学习中的训练样本，将问卷中的题目变为机器学习中的特征，那么问卷调查的步骤就可以泛化为决策树构建树的步骤。
第一步，根据集合中的样本分类，为每个集合计算信息熵，并通过全部集合的熵值加权平均，获得整个数据集的熵。注意，一开始集合只有一个，并且包含了所有的样本。
第二步，根据信息增益，计算每个特征的区分能力。挑选区分能力最强的特征，并对每个集合进行更细的划分。
第三步，有了新的划分之后，回到第一步，重复第一步和第二步，直到没有更多的特征，或者所有的样本都已经被分好类。
有一点需要注意的是，问卷案例中的每类武侠人物都只有一个样本，而在泛化的机器学习问题中，每个类型对应了多个样本。也就是说，我们可以有很多个郭靖，而且每个人的属性并不完全一致，但是它们的分类都是“郭靖”。正是因为这个原因，决策树通常都只能把整体的熵降低到一个比较低的值，而无法完全降到 0。这也意味着，训练得到的决策树模型，常常无法完全准确地划分训练样本，只能求到一个近似的解。
几种决策树算法的异同随着机器学习的快速发展，人们也提出了不少优化版的决策树。采用信息增益来构建决策树的算法被称为ID3（Iterative Dichotomiser 3，迭代二叉树 3 代）。但是这个算法有一个缺点，它一般会优先考虑具有较多取值的特征，因为取值多的特征会有相对较大的信息增益。这是为什么呢？
你仔细观察一下信息熵的定义，就能发现背后的原因。更多的取值会把数据样本划分为更多更小的分组，这样熵就会大幅降低，信息增益就会大幅上升。但是这样构建出来的树，很容易导致机器学习中的过拟合现象，不利于决策树对新数据的预测。为了克服这个问题，人们又提出了一个改进版，C4.5 算法。
这个算法使用信息增益率（Information Gain Ratio）来替代信息增益，作为选择特征的标准，并降低决策树过拟合的程度。信息增益率通过引入一个被称作分裂信息（Split Information）的项来惩罚取值较多的特征，我把相应的公式给你列出来了。
其中，训练数据集 P 通过属性 T 的属性值，划分为 n 个子数据集，∣Pi∣ 表示第 i 个子数据集中样本的数量，∣P∣ 表示划分之前数据集中样本总数量。 这个公式看上去和熵很类似，其实并不相同。
熵计算的时候考虑的是，集合内数据是否属于同一个类，因此即使集合数量很多，但是集合内的数据如果都是来自相同的分类（或分组），那么熵还是会很低。而这里的分裂信息是不同的，它只考虑子集的数量。如果某个特征取值很多，那么相对应的子集数量就越多，最终分裂信息的值就会越大。正是因为如此，人们可以使用分裂信息来惩罚取值很多的特征。具体的计算公式如下：
其中 Gain(P,T) 是数据集 P 使用特征 T 之后的信息增益，GainRatio(P,T) 是数据集 P 使用特征 T 之后的信息增益率。
另一种常见的决策树是 CART 算法（Classification and Regression Trees，分类与回归树）。这种算法和 ID3、C4.5 相比，主要有两处不同：
在分类时，CART 不再采用信息增益或信息增益率，而是采用基尼指数（Gini）来选择最好的特征并进行数据的划分；
在 ID3 和 C4.5 决策树中，算法根据特征的属性值划分数据，可能会划分出多个组。而 CART 算法采用了二叉树，每次把数据切成两份，分别进入左子树、右子树。
当然，CART 算法和 ID3、C4.5 也有类似的地方。首先，CART 中每一次迭代都会降低基尼指数，这类似于 ID3、C4.5 降低信息熵的过程。另外，基尼指数描述的也是纯度，与信息熵的含义相似。我们可以用下面这个公式来计算每个集合的纯度。
其中，n 为集合 P 中所包含的不同分组（或分类）数量。如果集合 P 中所包含的不同分组越多，那么这个集合的基尼指数越高，纯度越低。
然后，我们需要计算整个数据集的基尼指数。
其中，m 为全集使用特征 T 划分后，所形成的子集数量。Pj​ 为第 j 个集合。
无论是何种决策树算法，来自信息论的几个重要概念：信息熵、信息增益、信息增益率、基尼指数都起到了重要的作用。如果你能很好的学习并运用这些概念，那么决策树这种类型的算法就不难理解了。
总结通过这两节的介绍，我想你对信息熵、信息增益、基尼指数等信息论的概念，以及基于这些概念的决策树分类算法应该有了一定了解。决策树算法的优势在于，容易理解和实现。此外，对于通过样本训练所得的树结构，其每个结点都是基于某个数据特征的判定，对于我们的阅读和解释来说都是很方便的。
当然，决策树也有不足。之前我已经提到，这类算法受训练样本的影响很大，比较容易过拟合。在预测阶段，如果新的数据和原来的训练样本差异较大，那么分类效果就会比较差。为此人们也提出了一些优化方案，比如剪枝和随机森林。如果感兴趣，你可以自己去研究一下。
思考题刚刚我提到了，如果每次都选择使得信息增益最小的问题，那么构建出来的答题路径就相对冗长。你可以自己动手计算一下用户要回答问题数的期望。
欢迎留言和我分享，也欢迎你在留言区写下今天的学习笔记。如果你有朋友对决策树感兴趣，你可以点击“请朋友读”，把今天的内容分享给他，说不定就帮他解决一个问题。

分享给需要的人，Ta购买本课程，你将得20元

生成海报并分享

赞 6

提建议

26 | 信息熵：如何通过几个问题，测出你对应的武侠人物？

28 | 熵、信息增益和卡方：如何寻找关键特征？

 写留言

精选留言(22)

Peng
2019-03-05
开始看不懂了，我再多看几遍试试。
作者回复: 可以逐个理解，每次理解一点都是进步👍
共 2 条评论
10
Paul Shan
2019-09-10
信息增益，新分类的引入导致熵的减少。信息增益率，计算熵的时候还考虑了多个子项的数目。在计算分组后集合的熵，采用加权平均之后，还要除以，集合分组不同数目引入的熵。 Gini指数是一种新的计算混乱度的方法，熵是基于对数加权的，Gini指数是基于平方的相反数求和再加一。Gini指数求导以后是线性的，随着概率减少变化度比熵更敏感（熵的导数是对数），也就更惩罚小概率事件。
展开
7
张九州
2019-09-08
计算整个数据集基尼指数，pj是什么如何计算？
作者回复: pj表示第j组元素出现的概率，这里用在某个划分的组之中，第j组元素的数量除以这个划分的元素数量来计算
3
lifes a Struggle
2019-08-07
知道了，老师的案例中个体都是一个单独的分类，所有在原始集合中可以采用-n*(Pi*log(2,Pi))的形式进行信息熵的计算。如果存在分类的数据不均匀，通过各个分类的信息熵求和即可。
作者回复: 是的👍
3
罗耀龙@坐忘
2020-04-19
茶艺师学编程 1、思考题：按照最少信息增益来划分，用户回答题目的期望是多少？ 0.2*2+0.1*3+0.4*4+0.1*5+0.2*6=4 （换成人话，就是10个人，有两人要回答两题，有一人要回答三题，有四人要回答四题，有一人要回答五题，有两人要回答六题，他们的期望就是四题） 2、关于ID3和C4.5算法：两者都是罗斯•昆兰（Ross Quinlan）的作品，ID3决策树诞生于1986年，在7年后（1993年）罗斯就推出了它的改进版C4.5算法，后者被称为数据挖掘十大算法之一。
展开
2
总统老唐
2019-12-25
既然每次都是分解成左右两个子树，为什么CART算法公式中的m不直接写成2
作者回复: 这里主要是通用性，对于CART算法确实可以将m简写为2，对于其他使用基尼指数的算法仍然保持m
2
qinggeouye
2019-03-10
某个特征 T 取值越多，数据集 P 划分时分组越多，划分后的「信息熵」越小，「信息增益」越大。「分裂信息」是为了解决某个特征 T 取值过多，造成机器学习过拟合，而引入的一种惩罚项，惩罚取值多的特征。老师，「基尼指数」没怎么看明白，第一个式子中「n 为集合 P 中所包含的不同分组或分类的数量」该怎么理解？求和符号后面的 pi 是什么含义？谢谢～
展开
作者回复: 因为决策树是一种分类算法，我们有训练样本告诉我们每个数据样本属于何种分类，所以这里的分类、分组都是根据训练样本中的分类标签。
共 2 条评论
2
Thinking
2019-02-15
建议老师每堂课后能配多几个具有代表性的，针对性的练习题辅助理解概念和公式。
作者回复: 好的，后面我会考虑多从公式的角度出发
2
灰太狼
2020-03-28
老师，基尼系数公式里的pi是指分组i在集合P中的概率吗？
作者回复: 是的👍
共 4 条评论
1
💢 星星💢
2019-11-11
老师随机森林有没有好的文章推荐，另外老师有没有公众号，或者其他方式可以白嫖看您的文章呢，当然也期待老师出新的专栏，虽然这个专栏对于我来说已经是新的挑战。但是非常喜欢读老师的文章。
作者回复: 你好，感谢支持，我暂时还没有时间在其他地方发表博文。如果有好的想法写作，当然首选极客时间专栏啦😆。正在和编辑筹划下一个专栏，期待与大家再次交流
1
Joe
2019-02-21
老师，请问有没有相关代码实现的方式，能否给出参考链接。
作者回复: 你是指计算信息熵、信息增益和基尼指数？可以使用现成的机器学习包计算，如果希望自己计算也不难，遵循专栏中的公式就可以了。后面我有时间整理一下代码。
共 2 条评论
1
013923
2022-09-05 来自上海
学完一章，谢谢老师！
建强
2020-06-21
根据信息增益划分的原理，简单写了一个python程序计算了一下问题期望数，程序输出结果如下：选择信息增益小的问题对人物分类，问题数的期望值=3.7 选择信息增益大的问题对人物分类，问题数的期望值=2.8 程序代码如下： import pandas as pd # 初始化10个武侠人物的属性 p = { '性别':['男','男','男','男','男','女','女','女','女','女'] ,'智商':['高','高','高','高','中','高','高','高','高','中'] ,'情商':['高','高','中','中','高','高','中','中','中','中'] ,'侠义':['高','中','低','中','高','低','高','高','低','中'] ,'个性':['开朗','拘谨','开朗','拘谨','开朗','开朗','开朗','拘谨','开朗','开朗']} name = ['A','B','C','D','E','F','G','H','I','J'] knight = pd.DataFrame(data=p,index=name) # 定义问题类型及增益大小 problem_type = {'性别':1,'智商':0.72,'情商':0.97,'侠义':1.58,'个性':0.88} # 计算测试问题的期望值 def get_exp_problems(knight, problem_type): #BEGIN result = {} sub_knight = [(knight,0)] temp_sub_knight = [] for pt in problem_type: #用某一个问题类型对每一组侠客进行划分 for sub in sub_knight: temp_sub = sub[0].groupby(by = [pt]) #该问题没有将该组侠客进行划分，放入中间结果，继续下一组划分 if len(temp_sub) <= 1: temp_sub_knight.append((sub[0],sub[1])) continue # 对划分后的结果进行处理 for label, member in temp_sub: list_member = list(member.index) if len(list_member) == 1: result[list_member[0]] = sub[1] + 1 else: temp_sub_knight.append((member, sub[1]+1)) sub_knight.clear() sub_knight.extend(temp_sub_knight) temp_sub_knight.clear() # 计算问题数的期望值 exp = 0 for k in result: exp += result[k]/len(name) return exp #END def main(): problem = dict(sorted(problem_type.items(), key=lambda x: x[1], reverse=False)) print('选择信息增益小的问题对人物分类，问题数的期望值={}'.format(round(get_exp_problems(knight, problem),2))) problem = dict(sorted(problem_type.items(), key=lambda x: x[1], reverse=True)) print('选择信息增益大的问题对人物分类，问题数的期望值={}'.format(round(get_exp_problems(knight, problem),2))) if __name__ == '__main__': main()
展开
作者回复: 很好的实现
骑行的掌柜J
2020-06-09
思考题：“如果每次都选择使得信息增益最小的问题” 我算出来结果是期望值是3.9。。。跟楼上两个哥们的不一样。。。（因为A、C、D、F、H都要问四轮；B、E、J都要三轮；G、I 要问五轮）不过都是在4的附近
哈达syn$
2020-05-18
王天一喜欢用足球举例子，黄申喜欢武侠小说呀
作者回复: 哈哈，正好写这篇的时候金庸老爷子过世，也算纪念一下
拉普达
2020-03-29
期望是3.8次
作者回复: 列出所有可能的路径，大致在这个范围
J.Smile
2020-02-27
要点总结： CART算法和 ID3、C4.5 相比，主要有两处不同：在分类时，CART 不再采用信息增益或信息增益率，而是采用基尼指数（Gini）来选择最好的特征并进行数据的划分；在 ID3 和 C4.5 决策树中，算法根据特征的属性值划分数据，可能会划分出多个组。而 CART 算法采用了二叉树，每次把数据切成两份，分别进入左子树、右子树。
展开
lifes a Struggle
2019-08-07
老师，请问一下，当原始集合中的数据，本身是分布不均匀的，这个时候该如何计算它的信息熵呢？如：集合｛A,A,A,B,B,C｝
abson
2019-08-07
老师，有个疑问，像前几篇文章讲隐马尔科夫、信息熵和本节讲的决策树，数据是怎么来的，用什么方法去统计才能拿到相对偏差较少的数据
作者回复: 你是指在实际项目中如何获得数据吗？这个要看具体的应用场景和需求，通常的规则是尽量覆盖不同的情况。比如不同时间段、不同用户分组、不同地域等等
动摇的小指南针
2019-05-17
基尼系数中，基于特征T划分出来的子集m中，m的每个子集又有n个不同的分组。请问这个n是根据什么来进行划分的呢
作者回复: 由于是标注数据，所以这个n是根据原有分类的标签来看的

