决策树中信息、熵、信息增益、基尼指数的概念及其python实现

冷不防 2022-05-25 02:41 316阅读 0赞

from：http://www.cnblogs.com/fantasy01/p/4581803.html?utm\_source=tuicool

关于对信息、熵、信息增益是信息论里的概念，是对数据处理的量化，这几个概念主要是在决策树里用到的概念，因为在利用特征来分类的时候会对特征选取顺序的选择，这几个概念比较抽象，我也花了好长时间去理解(自己认为的理解),废话不多说，接下来开始对这几个概念解释，防止自己忘记的同时，望对其他人有个借鉴的作用，如有错误还请指出。

### 1、信息 ###

这个是熵和信息增益的基础概念，我觉得对于这个概念的理解更应该把他认为是一用名称，就比如‘鸡‘(加引号意思是说这个是名称)是用来修饰鸡(没加引号是说存在的动物即鸡)，‘狗’是用来修饰狗的，但是假如在鸡还未被命名为'鸡'的时候，鸡被命名为‘狗’，狗未被命名为‘狗’的时候，狗被命名为'鸡'，那么现在我们看到狗就会称其为‘鸡’，见到鸡的话会称其为‘鸡’，同理，信息应该是对一个抽象事物的命名，无论用不用‘信息’来命名这种抽象事物，或者用其他名称来命名这种抽象事物，这种抽象事物是客观存在的。

引用香农的话，信息是用来消除随机不确定性的东西，当然这句话虽然经典，但是还是很难去搞明白这种东西到底是个什么样，可能在不同的地方来说，指的东西又不一样，从数学的角度来说可能更加清楚一些，数学本来就是建造在悬崖之上的一种理论，一种抽象的理论，利用抽象来解释抽象可能更加恰当，同时也是在机器学习决策树中用的定义，如果带分类的事物集合可以划分为多个类别当中，则某个类（xi）的信息定义如下:

![3d00e0dc9206182c8d5ea27481b4ceb1.png][]

I(x)用来表示随机变量的信息，p(xi)指是当xi发生时的概率，这里说一下随机变量的概念，随机变量时概率论中的概念，是从样本空间到实数集的一个映射，样本空间是指所有随机事件发生的结果的并集，比如当你抛硬币的时候，会发生两个结果，正面或反面，而随机事件在这里可以是，硬币是正面；硬币是反面；两个随机事件，而\{正面，反面\}这个集合便是样本空间，但是在数学中不会说用‘正面’、‘反面’这样的词语来作为数学运算的介质，而是用0表示反面，用1表示正面，而“正面->1”,"反面->0"这样的映射便为随机变量，即类似一个数学函数。

### 2、熵 ###

既然信息已经说完，熵说起来就不会那么的抽象，更多的可能是概率论的定义，熵是约翰.冯.诺依曼建议使用的命名（当然是英文），最初原因是因为大家都不知道它是什么意思，在信息论和概率论中熵是对随机变量不确定性的度量,与上边联系起来，熵便是信息的期望值，可以记作：

![f6cbcaaf8277afc5d6f2bb68cb483a8a.png][]

n为：类别的个数。

熵只依赖X的分布，和X的取值没有关系，熵是用来度量不确定性，当熵越大，概率说X=xi的不确定性越大，反之越小，在机器学期中分类中说，熵越大即这个类别的不确定性更大，反之越小，当随机变量的取值为两个时，熵随概率的变化曲线如下图：

![cfa90ff4cb5601ab0bfed4be2dddab7d.png][]

当p=0或p=1时，H(p)=0,随机变量完全没有不确定性，当p=0.5时，H(p)=1,此时随机变量的不确定性最大

条件熵

条件熵是用来解释信息增益而引入的概念，概率定义：随机变量X在给定条件下随机变量Y的条件熵，对定义描述为：X给定条件下Y的条件干率分布的熵对X的数学期望，在机器学习中为选定某个特征后的熵，公式如下：

![b3fa6681e59edfdb668618299b1d0c6d.png][]

这里可能会有疑惑，这个公式是对条件概率熵求期望，但是上边说是选定某个特征的熵，没错，是选定某个特征的熵，因为一个特征可以将待分类的事物集合分为多类，即一个特征对应着多个类别，因此在此的多个分类即为X的取值。

### 3、信息增益 ###

信息增益在决策树算法中是用来选择特征的指标，信息增益越大，则这个特征的选择性越好，在概率中定义为：待分类的集合的熵和选定某个特征的条件熵之差（这里只的是经验熵或经验条件熵，由于真正的熵并不知道，是根据样本计算出来的），公式如下：

![a69a345a5d95352b1d5d0395a9bef832.png][]

注意：这里不要理解偏差，因为上边说了熵是类别的，但是在这里又说是集合的熵，没区别，因为在计算熵的时候是根据各个类别对应的值求期望来等到熵

4、信息增益算法（举例，摘自统计学习算法）

训练数据集合D，|D|为样本容量，即样本的个数（D中元素个数），设有K个类Ck来表示，|Ck|为Ci的样本个数，|Ck|之和为|D|，k=1，2.....，根据特征A将D划分为n个子集D1，D2.....Dn，|Di|为Di的样本个数，|Di|之和为|D|,i=1,2,....,记Di中属于Ck的样本集合为Dik,即交集，|Dik|为Dik的样本个数，算法如下：

输入：D，A

输出：信息增益g(D,A)

(1)D的经验熵H(D)

![1a58ed7ba3034c6b24fab1246c9fe80c.png][]

此处的概率计算是根据古典概率计算，由于训练数据集总个数为|D|，某个分类的个数为|Ck|，在某个分类的概率，或说随机变量取某值的概率为：|Ck|/|D|

(2)选定A的经验条件熵H(D|A)

![d874a304f2469801aa22c31cdaecba70.png][]

此处的概率计算同上，由于|Di|是选定特征的某个分类的样本个数，则|Di|/|D|,可以说为在选定特征某个分类的概率，后边的求和可以理解为在选定特征的某个类别下的条件概率的熵，即训练集为Di，交集Dik可以理解在Di条件下某个分类的样本个数，即k为某个分类，就是缩小训练集为Di的熵

(3)信息增益

![13ef284d301b313f0ecd0cb470329ba3.png][]

### 4、基尼指数 ###

1、是一种不等性度量；  
2、通常用来度量收入不平衡，可以用来度量任何不均匀分布；  
3、是介于0~1之间的数，0-完全相等，1-完全不相等；  
4、**总体内包含的类别越杂乱，GINI指数就越大（跟熵的概念很相似）**

**基尼不纯度指标**

在CART算法中, 基尼不纯度表示一个随机选中的样本在子集中被分错的可能性。基尼不纯度为这个样本被选中的概率乘以它被分错的概率。当一个节点中所有样本都是一个类时，基尼不纯度为零。  
假设y的可能取值为\{1, 2, ..., m\},令fi是样本被赋予i的概率，则**基尼指数**可以通过如下计算：

![70][]

使用基尼系数作为特征划分规则时：

![70 1][]

上述使用jini指数作为特征分类标准时，以特定的一个属性作为一部分，另外的全部属性作为另外一部分，来计算jini指数。

《统计学习》中CART树的gini指数计算：  
计算的表格数据，是一个分类问题：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70][]

计算最佳的特征值和属性值

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70 1][]

### 5、 python实现信息增益和基尼系数 的计算 ###

**1.输入数据集**

#!/usr/bin/env python
    # -*- coding: utf-8 -*-
    """
    __title__ = ''
    __author__ = 'mike_jun'
    __mtime__ = '2019-7-12'
    #目的：
    """
    import numpy as np
    import pandas as pd
    import matplotlib.pyplot as plt
    import io
    
    # 计算两个特征的基尼指数
    data_str = output = io.StringIO('''编号,色泽,根蒂,敲声,纹理,脐部,触感,密度,含糖率,好瓜
    1,青绿,蜷缩,浊响,清晰,凹陷,硬滑,0.697,0.46,是  
    2,乌黑,蜷缩,沉闷,清晰,凹陷,硬滑,0.774,0.376,是  
    3,乌黑,蜷缩,浊响,清晰,凹陷,硬滑,0.634,0.264,是  
    4,青绿,蜷缩,沉闷,清晰,凹陷,硬滑,0.608,0.318,是  
    5,浅白,蜷缩,浊响,清晰,凹陷,硬滑,0.556,0.215,是  
    6,青绿,稍蜷,浊响,清晰,稍凹,软粘,0.403,0.237,是  
    7,乌黑,稍蜷,浊响,稍糊,稍凹,软粘,0.481,0.149,是  
    8,乌黑,稍蜷,浊响,清晰,稍凹,硬滑,0.437,0.211,是  
    9,乌黑,稍蜷,沉闷,稍糊,稍凹,硬滑,0.666,0.091,否  
    10,青绿,硬挺,清脆,清晰,平坦,软粘,0.243,0.267,否  
    11,浅白,硬挺,清脆,模糊,平坦,硬滑,0.245,0.057,否  
    12,浅白,蜷缩,浊响,模糊,平坦,软粘,0.343,0.099,否  
    13,青绿,稍蜷,浊响,稍糊,凹陷,硬滑,0.639,0.161,否  
    14,浅白,稍蜷,沉闷,稍糊,凹陷,硬滑,0.657,0.198,否  
    15,乌黑,稍蜷,浊响,清晰,稍凹,软粘,0.36,0.37,否  
    16,浅白,蜷缩,浊响,模糊,平坦,硬滑,0.593,0.042,否  
    17,青绿,蜷缩,沉闷,稍糊,稍凹,硬滑,0.719,0.103,否  ''')
    
    data = pd.read_csv(data_str)
    data.set_index('编号', inplace=True)
    print(data)

**2.计算系统信息熵**

def entropy(data):
        length = data.size
        ent = 0
        for i in data.value_counts():
            print(i)
            prob = i / length
            ent += - prob * (np.log2(prob))
        return ent
    print('--------')
    print(entropy(data['好瓜'])) # 0.9975025463691153

**3.计算信息增益**

def gain(data, input_column, output_colum):
        """
        :param data: 输入DataFrame 的数据
        :param input_column: 特征的名称
        :param output_colum: 好瓜or 坏
        :return:
        """
        ret = 0
        lens = data[output_colum].size
        all_attribute = data[input_column].value_counts()  # 保存特征全部属性的取值个数
        for name in data[input_column].unique(): # 特征的不同属性名
            print(name)
            temp = 0
            for i in range(len(data[output_colum].unique())):  # 好瓜 or 坏瓜
                attribute_num = data[input_column].where(data[output_colum] == data[output_colum].unique()[i]).value_counts()
                # print(attribute_num[name]) # 当刚好 好瓜 中没有 硬挺这一属性值的时候,使用异常处理机制
                try:
                    prob = int(attribute_num[name]) / int(all_attribute[name])
                except:
                    prob = 0
    
                if prob == 0:
                    temp += 0
                else:
                    temp += - prob * np.log2(prob)
                # 还需要乘以 该属性出现的概率
            temp *= all_attribute[name] / lens
            ret += temp
        return ret
    print(gain(data, '根蒂', '好瓜'))
    entD = entropy(data['好瓜'])
    for name in data.columns[:-3]:
        print('打印出全部的特征的信息增益')
        ret = gain(data, name, '好瓜')
        print(name)
        gain_ = entD - ret
        print(gain_)
    print(entD)

**4.计算基尼系数**

# 计算基尼系数， 基尼系数越小，越应该选择该特征作为分裂结点
    def gini_index(data, input_column, output_colum):
        ret = 0
        lens = data[output_colum].size
        all_attribute = data[input_column].value_counts()  # 保存全部属性的取值个数
        for name in data[input_column].unique(): # 特征的不同属性
            print(name)
            temp = 0
            for i in range(len(data[output_colum].unique())):  # 输出值的取值个数
                # 当 为好瓜时，
                attribute_num = data[input_column].where(data[output_colum] == data[output_colum].unique()[i]).value_counts()
                # print(attribute_num[name]) # 当刚好 好瓜中没有 硬挺这一属性值的时候,使用异常处理机制
                try:
                    prob = int(attribute_num[name]) / int(all_attribute[name])
                except:
                    prob = 0
    
                if prob == 0:
                    temp += 0
                else:
                    temp += np.square(prob)
                # 还需要乘以 该属性出现的概率
            temp = all_attribute[name] / lens * (1-temp)
            ret += temp
        return ret
    
    print('打印出全部的特征的基尼系数')
    for name in data.columns[:-3]:
        ret = gain(data, name, '好瓜')
        print(name)
        print(ret)

--------------------

### 项目推荐： ###

**[2000多G的计算机各行业电子资源分享（持续更新）][2000_G]**

**[2020年微信小程序全栈项目之喵喵交友【附课件和源码】][2020]**

**[Spring Boot开发小而美的个人博客【附课件和源码】][Spring Boot]**

**[Java微服务实战296集大型视频-谷粒商城【附代码和课件】][Java_296_-]**

**[Java开发微服务畅购商城实战【全357集大项目】-附代码和课件][Java_357_-]**

**[最全最详细数据结构与算法视频-【附课件和源码】][-]**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70_pic_center]

[3d00e0dc9206182c8d5ea27481b4ceb1.png]: /images/20220525/b721e8cbf1de4387ba4cf931b1aaad33.png
[f6cbcaaf8277afc5d6f2bb68cb483a8a.png]: /images/20220525/1dd2905115744396a000901a2626e9ae.png
[cfa90ff4cb5601ab0bfed4be2dddab7d.png]: /images/20220525/02dd63884bff402599e58326ffab7b43.png
[b3fa6681e59edfdb668618299b1d0c6d.png]: /images/20220525/15d14d6ea82f48fdb42d94e20cf4f74c.png
[a69a345a5d95352b1d5d0395a9bef832.png]: /images/20220525/0e3b4dc15895467eb42d836504b6c376.png
[1a58ed7ba3034c6b24fab1246c9fe80c.png]: /images/20220525/6fa85a780506481cacc6a0e869838bf0.png
[d874a304f2469801aa22c31cdaecba70.png]: /images/20220525/ab0c90fb1a77408c894d5785e3df18ca.png
[13ef284d301b313f0ecd0cb470329ba3.png]: /images/20220525/c21a55d2c1ad4703b8f15eac5d8a93db.png
[70]: /images/20220525/c4180240a5f24cc99c8424a482d38071.png
[70 1]: /images/20220525/e7599690d9a5469e9890a90b18f54956.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70]: /images/20220525/cd2a6fbd3fbe4ae7860fd6bda5dd4127.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70 1]: /images/20220525/eed2c0d157f741ca8bad24dfb33e92bf.png
[2000_G]: https://mp.weixin.qq.com/s/sP4JgGWkCzpgwKr9sAV2_Q
[2020]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487704&idx=1&sn=5f4b2127c4d49fd07ae072a0721424a2&chksm=e8036fc2df74e6d489c4aa9b06f917ef7cee6027f13e150fca53cf79d5d188d4ccc1af49e098&scene=21#wechat_redirect
[Spring Boot]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487798&idx=2&sn=ac0293b996521b872a9dba5fbb3e65e6&chksm=e8036e2cdf74e73aba104a9a994a5b2e31483e8dcbe0f1d9936f6d5173b887e1560f59d2819c&scene=21#wechat_redirect
[Java_296_-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487674&idx=1&sn=7aff0bdf2bb727303f3d3618995aef21&chksm=e8036fa0df74e6b6d872c7e6ece179c524ed463a4a6b74c96875475c9a3d5ddb903427dd993b&scene=21#wechat_redirect
[Java_357_-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247486376&idx=1&sn=d1fef270c463ea8ac663f6fbfedd70a0&chksm=e80374b2df74fda4d3bafba878a106a19e18c5fcda266008f4f37975847a21bc612ffcd5ff39&scene=21#wechat_redirect
[-]: https://mp.weixin.qq.com/s?__biz=MzIyNTI3NDQ4NQ==&mid=2247487750&idx=1&sn=747bccbb5f5ea6b58915198de40da777&chksm=e8036e1cdf74e70ae97a5e8e265b49d7236d904d291203309159d07ba1724033062c0e370843&scene=21#wechat_redirect
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70_pic_center]: /images/20220525/78cde96b953b470884e1fcc8d1bfa249.png