27 决策树：信息增益、增益比率和基尼指数的运用
你好，我是黄申。
上一节，我通过问卷调查的案例，给你解释了信息熵和信息增益的概念。被测者们每次回答一道问题，就会被细分到不同的集合，每个细分的集合纯净度就会提高，而熵就会下降。在测试结束的时候，如果所有被测者都被分配到了相应的武侠人物名下，那么每个人物分组都是最纯净的，熵值都为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$划分后，所形成的子集数量。$P_{j}$为第$j$个集合。
无论是何种决策树算法，来自信息论的几个重要概念：信息熵、信息增益、信息增益率、基尼指数都起到了重要的作用。如果你能很好的学习并运用这些概念，那么决策树这种类型的算法就不难理解了。
总结
通过这两节的介绍，我想你对信息熵、信息增益、基尼指数等信息论的概念，以及基于这些概念的决策树分类算法应该有了一定了解。决策树算法的优势在于，容易理解和实现。此外，对于通过样本训练所得的树结构，其每个结点都是基于某个数据特征的判定，对于我们的阅读和解释来说都是很方便的。
当然，决策树也有不足。之前我已经提到，这类算法受训练样本的影响很大，比较容易过拟合。在预测阶段，如果新的数据和原来的训练样本差异较大，那么分类效果就会比较差。为此人们也提出了一些优化方案，比如剪枝和随机森林。如果感兴趣，你可以自己去研究一下。
思考题
刚刚我提到了，如果每次都选择使得信息增益最小的问题，那么构建出来的答题路径就相对冗长。你可以自己动手计算一下用户要回答问题数的期望。
欢迎留言和我分享，也欢迎你在留言区写下今天的学习笔记。如果你有朋友对决策树感兴趣，你可以点击“请朋友读”，把今天的内容分享给他，说不定就帮他解决一个问题。
- Peng 👍（13） 💬（2）
开始看不懂了，我再多看几遍试试。
2019-03-05 - lifes a Struggle 👍（5） 💬（1）
知道了，老师的案例中个体都是一个单独的分类，所有在原始集合中可以采用-n*(Pi*log(2,Pi))的形式进行信息熵的计算。如果存在分类的数据不均匀，通过各个分类的信息熵求和即可。
2019-08-07 - 总统老唐 👍（3） 💬（1）
既然每次都是分解成左右两个子树，为什么CART算法公式中的m不直接写成2
2019-12-25 - 张九州 👍（3） 💬（1）
计算整个数据集基尼指数，pj是什么 如何计算？
2019-09-08 - 建强 👍（2） 💬（1）
根据信息增益划分的原理，简单写了一个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()
2020-06-21 - qinggeouye 👍（2） 💬（2）
某个特征 T 取值越多，数据集 P 划分时分组越多，划分后的「信息熵」越小，「信息增益」越大。「分裂信息」是为了解决某个特征 T 取值过多，造成机器学习过拟合，而引入的一种惩罚项，惩罚取值多的特征。 老师，「基尼指数」没怎么看明白，第一个式子中「n 为集合 P 中所包含的不同分组或分类的数量」该怎么理解？求和符号后面的 pi 是什么含义？谢谢～
2019-03-10 - Thinking 👍（2） 💬（1）
建议老师每堂课后能配多几个具有代表性的，针对性的练习题辅助理解概念和公式。
2019-02-15 - 灰太狼 👍（1） 💬（4）
老师，基尼系数公式里的pi是指分组i在集合P中的概率吗？
2020-03-28 - 💢 星星💢 👍（1） 💬（1）
老师随机森林有没有好的文章推荐，另外老师有没有公众号，或者其他方式可以白嫖看您的文章呢，当然也期待老师出新的专栏，虽然这个专栏对于我来说已经是新的挑战。但是非常喜欢读老师的文章。
2019-11-11 - Joe 👍（1） 💬（2）
老师，请问有没有相关代码实现的方式，能否给出参考链接。
2019-02-21 - 哈达syn$ 👍（0） 💬（0）
王天一喜欢用足球举例子，黄申喜欢武侠小说呀
2020-05-18 - 拉普达 👍（0） 💬（1）
期望是3.8次
2020-03-29 - abson 👍（0） 💬（1）
老师，有个疑问，像前几篇文章讲隐马尔科夫、信息熵和本节讲的决策树，数据是怎么来的，用什么方法去统计才能拿到相对偏差较少的数据
2019-08-07 - 动摇的小指南针 👍（0） 💬（1）
基尼系数中，基于特征T划分出来的子集m中，m的每个子集又有n个不同的分组。请问这个n是根据什么来进行划分的呢
2019-05-17 - Bora.Don 👍（0） 💬（1）
老师，你好，既然CART算法是二叉树，那么在计算基尼指数的时候，n和m是不是就是定值：2？ CART算法又是如何保证是二叉树的呢？CART算法没看懂
2019-03-18