【机器学习】【决策树】用样本集详解并计算：信息+香农熵+条件熵+信息增益+信息增益比+决策树的最优根节点+经验熵+经验条件熵

香农熵

首先信息、香农熵、条件熵、信息增益都是信息论里面的概念。

本文章的讲解和代码实现（除了条件熵和信息增益）都基于两个随机变量的样本空空间，样本空间X={x1, x2}的概率分布如下所示：

p(x1) = p1, 0< p1 <1
p(x2) = p2, 0< p2 <1
p1 + p2 = 1

1.信息

1.1信息函数

信息是用来消除随机不确定性的东西，信息的公式如下所示

I(x) = -log(p(x), 2) ，
其中p(x)就是随机变量x发生时的概率，x ∈ {x1，x2}

可知I(x1)就是随机变量x1的信息，I(x2)就是随机变量x2的信息。

1.2信息函数的Python是实现

# -*- coding: utf-8 -*-
"""
@author: 蔚蓝的天空tom
Talk is cheap, show me the code
aim:画出样本空间X={x1, x2}中随机变量变量x1的信息函数Info(x1)曲线图，因变量为p
Info(x1) = -log2(p)
已知p(x1)=p, p(x2)=1-p, 0<= p <= 1
"""

import numpy as np
import math
import matplotlib.pyplot as plt

def log_ele(x, n):
    '''
    表达式x的logn函数 log(x, n)
    :param x:表达式
    :param n:log的底
    '''
    if 0 >= x:
        return 0
    else:
        return math.log(x, n)

def log_func(X, n):
    '''
    logn函数的向量化
    :param X:向量X
    :param n:log的底
    '''
    func = np.frompyfunc(log_ele, 2, 1)
    return func(X, n)

#画以概率p为因变量的随机变量的信息曲线
def plot_information():
    '''
    样本空间:X={x1, x2}
    概率密度:p(x1) = p, p(x2) = 1 - p, 0.0<= p <=1.0
    '''
    p = np.arange(0.0, 1.01, 0.01)
    '''
    [ 0.    0.01  0.02  0.03  0.04  0.05  0.06  0.07  0.08  0.09  0.1   0.11
      0.12  0.13  0.14  0.15  0.16  0.17  0.18  0.19  0.2   0.21  0.22  0.23
      0.24  0.25  0.26  0.27  0.28  0.29  0.3   0.31  0.32  0.33  0.34  0.35
      0.36  0.37  0.38  0.39  0.4   0.41  0.42  0.43  0.44  0.45  0.46  0.47
      0.48  0.49  0.5   0.51  0.52  0.53  0.54  0.55  0.56  0.57  0.58  0.59
      0.6   0.61  0.62  0.63  0.64  0.65  0.66  0.67  0.68  0.69  0.7   0.71
      0.72  0.73  0.74  0.75  0.76  0.77  0.78  0.79  0.8   0.81  0.82  0.83
      0.84  0.85  0.86  0.87  0.88  0.89  0.9   0.91  0.92  0.93  0.94  0.95
      0.96  0.97  0.98  0.99  1.  ]
    '''
    info_x1 = -1 * log_func(p, 2)   #x1的信息
    
    #plot x1's information and x2's information in the coordinate system
    x = p
    y = info_x1
    plt.figure(1)
    plt.grid(True)
    plt.title('random variable x1\'s information')
    plt.xlabel('p')
    plt.ylabel('random variable x1\'s information')
    plt.ylim(min(y.min(), y.min()), max(y.max(), y.max())+1)
    plt.xlim(x.min() - 0.1, x.max() + 0.1)
    plt.plot(x, y, c='red',label='Info(x1)=-log2(p)')
    plt.legend(loc = 'upper right')
    plt.show()
if __name__=='__main__':
    plot_information()

1.3信息函数的曲线图（变量概率p为因变量）

从图上可以知道样本空间中的随机变量x1的信息是随着x1的发生概率p的增大而减小下。可知随机变量的概率越大，此信息变量的信息会越小，此随机变量的不确定性就越小。

2.香农熵(Shannon Entropy)

2.1香农熵公式

从概率论的角度看，香农熵是样本空间内所有随机变量的信息的期望，香农熵的公式如下所示：

H(X)=p(x1)I(x1) + p(x2)I(x2)，
其中X是样本空间{x1, x2}，p(x1)是x1发生时的概率，p(x2)是x2发生时的概率，I(x1)是x1的信息，I(x2)是x2的信息

2.2香农熵的意义

1）香农熵只依赖样本空间X的分布

2）香农熵和样本空间X内的所有的样本取值没有任何关系

3）香农熵用来度量随机变量的不确定性

4）熵越大，概率说明X的不确定性越大

5）熵越小，概率说明X的不确定性越小

6）熵，就是不确定性的度量！

应用：在机器学习分类中用到香农熵，熵越到说明这个类别的不确定性越大，反之越小。

下面以本章中的样本空间为例，画出香农熵以概率p为因变量的变化曲线，其中p(x1)=p, p(x2) = 1 - p，0<= p <= 1。

2.3香农熵的python实现

# -*- coding: utf-8 -*-
"""
@author: 蔚蓝的天空tom
Talk is cheap, show me the code
Aim:画出样本空间X={x1, x2}的香农熵函数图H(X) = -p*log2(p) - (1-p)*log2(1-p)，因变量为p
已知p(x1)=p, p(x2)=1-p, 0<= p <= 1
"""

import numpy as np
import math
import matplotlib.pyplot as plt

def log_ele(x, n):
    '''
    表达式x的logn函数 log(x, n)
    :param x:表达式
    :param n:log的底
    '''
    if 0 >= x:
        return 0
    else:
        return math.log(x, n)

def log_func(X, n):
    '''
    logn函数的向量化
    :param X:向量X
    :param n:log的底
    '''
    func = np.frompyfunc(log_ele, 2, 1)
    return func(X, n)

def plot_shannon_entropy():
    '''
    画以概率p为因变量的香农熵曲线H(X) = -p*log2(p) - (1-p)*log2(1-p)
    样本空间:X={x1, x2}
    概率密度:p(x1) = p, p(x2) = 1 - p, 0.0<= p <=1.0
    '''
    p = np.arange(0.0, 1.01, 0.01)
    '''
    [ 0.    0.01  0.02  0.03  0.04  0.05  0.06  0.07  0.08  0.09  0.1   0.11
      0.12  0.13  0.14  0.15  0.16  0.17  0.18  0.19  0.2   0.21  0.22  0.23
      0.24  0.25  0.26  0.27  0.28  0.29  0.3   0.31  0.32  0.33  0.34  0.35
      0.36  0.37  0.38  0.39  0.4   0.41  0.42  0.43  0.44  0.45  0.46  0.47
      0.48  0.49  0.5   0.51  0.52  0.53  0.54  0.55  0.56  0.57  0.58  0.59
      0.6   0.61  0.62  0.63  0.64  0.65  0.66  0.67  0.68  0.69  0.7   0.71
      0.72  0.73  0.74  0.75  0.76  0.77  0.78  0.79  0.8   0.81  0.82  0.83
      0.84  0.85  0.86  0.87  0.88  0.89  0.9   0.91  0.92  0.93  0.94  0.95
      0.96  0.97  0.98  0.99  1.  ]
    '''
    I1 = -1 * log_func(p, 2)   #x1的信息
    I2 = -1 * log_func(1-p, 2) #x2的信息
    shannon_entropy = p*I1 + (1-p)*I2 #样本空间X的香农熵
    
    #画图香农熵函数，H(X) = -p*log2(p) - (1-p)*log2(1-p)
    x, y= p,shannon_entropy
    plt.figure(1, figsize=(8,6))
    plt.grid(True)
    plt.title('shannon entropy of {x1, x2}, p(x1)=p is dependent variable')
    plt.xlabel('p')
    plt.ylabel('H(X) = -p*log2(p) - (1-p)*log2(1-p)')
    plt.ylim(y.min(), y.max() + 0.2)
    plt.plot(x, y, c='red', label='shannon_entropy(X) = -p*log2(p) - (1-p)*log2(1-p)')

    plt.legend(loc='upper left')
    plt.show()

if __name__=='__main__':
    plot_shannon_entropy()

2.4香农熵的曲线图（以随机变量x1的概率p为因变量）

从图上可以知道：

1）当p=0或者p=1时，样本空间X的香农熵取值最小为0，则此时概率地说此时的样本空间不确定性最小；

2）当p=0.5时，样本空间X的香农熵取值最大，则此时可以概率地说此时的样本空间不确定性最大。

3）在0<p<=0.5范围内，随着随机变量x1的概率值p增加，样本空间X的香农熵增大，则可以说样本空间的不确定性也在增大

4）在0.5=<p<=1范围内，随着随机变量x1的概率值p增加，样本空间X的香农熵减小，则可以说样本空间的不确定性也减小

3.条件熵

详见：【机器学习】用样本集详解条件熵H(Y|X)的计算过程

此处只拿出部分内容，介绍条件熵的计算步骤：

3.1.样本数据集

样本集简介：

样本集有8个example样本

每个样本有3个特征(身高，房子，性格)，1个分类结果refuse或者agree

身高取值范围={high, low}

房子取值范围={no, yes}

性格取值范围={good, bad}

分类标签=相亲结果={refuse,agree}

 3.2分类样本空间 Y=相亲结果

3.3样本空间 X=身高

3.3.1条件样本空间 X=身高

3.3.2计算条件熵H(Y=相亲结果| X=身高)

有了上面的统计后，我们可以计算条件熵了。

我们想要求出当已知身高的条件下的分类样本空间Y的条件熵。

而条件熵是一个变量Y熵对X(条件)的期望：

[plain] view plain copy

1. H(Y={refuse,agree}|X=身高)  
2.   
3. = p(身高=high) * H(Y|身高=high) + p(身高=low) * H(Y|身高=low)  
4.   
5. =(3/8) * {-2/3log(2/3)  -1/3log(1/3)}  +  (5/8)* {-3/5log(3/5) -2/5log(2/5)}  

Python计算如下：

4.信息增益

以3.条件熵中用到的相亲样本集为例，继续讲解信息增益。

4.1样本集的香农熵

n_samples = 8

n_refuse = 5

n_agree = 3

p(y=refuse) = n_refuse/n_samples = 5/8

p(y=agree) = n_agree/n_samples = 3/8

H(Samples) 

= -p(y=refuse)*log2(p(y=refuse))  - p(y=agree)*log2(y=agree)

=-(5/8)*log2(5/8)  -(3/8)*log2(3/8)

Python计算结果如下：

-(5/8)*math.log2(5/8)  -(3/8)*math.log2(3/8)
Out[63]: 0.954434002924965

4.2条件样本空间 X=身高={high, low}时的条件熵

condition_entropy(Y={refuse, agree} | X=身高={high, low})

= p(身高=high) * H(Y|身高=high) + p(身高=low) * H(Y|身高=low)

=(3/8) * {-2/3log(2/3)  -1/3log(1/3)}  +  (5/8)* {-3/5log(3/5) -2/5log(2/5)} 

python计算结果如下：

(3/8) * (-2/3*math.log2(2/3)  -1/3*math.log2(1/3))  +  (5/8) * (-3/5*math.log2(3/5) -2/5*math.log2(2/5))
Out[60]: 0.9512050593046015

4.3信息增益

条件空间样本X=身高={high, low}时，信息增益计算公式如下所示：

Gain(X=身高={high, low})

=shannon_entropy(samples) - condition_entropy(Y={refuse, agree} | X=身高={high, low})

=H(Y={refuse, agree}) - H(Y={refuse, agree}|X=身高={high, low})

=0.954434002924965 - 0.9512050593046015

=0.0032289436203635224

按照信息增益的计算公式，可以计算出：

Gain(X=身高={high, low})   = 0.954434002924965 - 0.9512050593046015 = 0.0032289436203635224

Gain(X=房子={yes, no})      = 0.954434002924965 - 0.896240625180289   = 0.058193377744676034
Gain(X=性格={good, bad}) = 0.954434002924965 - 0.6068441215341679 =0.34758988139079716

在实际使用中，将信息增益数值最大的特征作为决策树的根节点，可以使得基于此训练样本集得出的决策树最简洁有效。

根据上面的计算可知，将选取“性格”作为决策树的根节点，“房子”作为决策树的第二层节点，“身高”作为决策树的第三层节点。

5.经验熵

根据给定的已知样本集，计算样本集的香农熵，就是经验熵。

比如

投硬币游戏，得到如下样本集：

正面：6次

反面：8次

则根据本次的样本集，得到样本集的香农熵就是经验熵：

经验熵

=-p(正面)*log(p正面) -p(负面)*log(p负面)

=-6/14*log2(6/14) -8/14*log2(8/14)

python计算得到：

-6/14*math.log2(6/14) -8/14*math.log2(8/14)
Out[67]: 0.9852281360342516

6.经验条件熵

以5.经验熵为基础计算出来的条件熵，就是经验条件熵。

计算步骤详见3.条件熵

7.信息增益比

以4.信息增益中用到的相亲样本集为例，继续讲解信息增益比，以计算特征为身高的信息增益比过程为例：

Gain(X=身高={high, low}) = 0.003289436203635224

我们知道特征身高的样本空间以及概率密度分布如下所示：

Entropy(X=身高) = -3/8*math.log2(3/8) - 5/8*math.log2(5/8) = 0.954434002924965

GainRatio(X=身高) = Gain(X=身高={high, low})  / Entropy(X=身高) = 0.003446478429681251

如果以特征的信息增益比作为选择决策树根节点的选择标准，则此算法就是C4.5算法

ID3算法只有树的生成，所以该算法生成的树容易产生过拟合。

C4.5算法对ID3算法进行了改进，C4.5在生成的过程中，用信息增益比来选择特征作为每个子树的根节点

C4.5算法的pyton实现软件系统请见：https://blog.csdn.net/u012421852/article/details/79808223

enjoy it~

(end)

相关阅读

天天特价极致爆款入驻条件说明，商家和商品要求分别是什

随着天天特价极致爆款的诞生，熟知该活动的商家是越来越多了，大部分的人都想争夺这个资源位，目前都是为了提高淘宝店铺销量，为了帮大家

淘宝特卖怎么加入?加入淘宝特卖的前提条件是什么?

今天小编要跟各位展开讨论的话题是淘宝特卖怎么加入?加入淘宝特卖的前提条件是什么?关于这两个问题其实小编在之前的问题中也有涉

shell中if条件判断

if [  ];then...esle...fi或者if [  ];then...elif [  ];then...else...fi条件判断：1、字符串判断str1 = str2 （当两个串相等时

直通车精准匹配和广泛匹配设置条件是什么？

现在seo实验室宝店，不做付费好像就无法做起来，单纯制作淘宝客推广或者淘宝免费推广，好像已经不够用了，直通车推广已经成为趋势，中小卖

天猫入驻需要什么条件?要做什么准备？

现在的网络投资越来越火爆，很多的企业和商家都开始在天猫上进行经营，天猫一般是企业商家入驻的，对于里面的一些入驻条件、费用一类的