会员服务

决策树信息论基础

COOL

决策树信息论基础

信息熵

信息是我们一直在谈论的东西，但信息这个概念本身依然比较抽象。但信息可不可以被量化，怎样量化？答案当然是有的，那就是“信息熵”。早在1948年，香农(Shannon)在他著名的《通信的数学原理》论文中指出：“信息是用来消除随机不确定性的东西”，并提出了“信息熵”的概念（据说是冯诺依曼建议他借用了热力学中熵的概念），来解决信息的度量问题.

熵度量了事物的不确定性，被用来衡量一个随机变量出现的期望值。熵越大，一个变量的不确定性就越大（也就是可取的值很多），把它搞清楚所需要的信息量也就越大，熵是整个系统的平均消息量。

概率和信息量

首先我们可以简单地认为，一个事件发生的概率越小，“信息量”就越大。例如：“太阳从西边落下”，几乎是一件确定的事，包含的信息量很小。当一件事确定会发生的话，则这件事的信息量为0，反之信息量则很大。
基于这种假设，我们可以认为，“信息量”的大小和概率负相关。

其次我们假设两个独立事件同时发生的概率：

p ( x , y ) = p ( x ) ∗ p ( y ) p(x,y) = p(x) * p(y)

两个事件分别发生的概率之积，但是同时发生的信息量则是两者信息量之和。从这个角度出发，我们可以认为：

− l o g ( p ( x , y ) ) = − l o g ( p ( x ) ) − l o g ( p ( y ) ) -log(p(x,y))=-log(p(x))-log(p(y))

现在我们考虑随机事件X，假设存在这样的情况：

X 0 1
P 1-p p
信息量 -log(1-p) -log( p )

那么我们如果要求“信息量”的期望的话：

E ( i n f o ) = − p l o g ( p ) − ( 1 − p ) l o g ( 1 − p ) = − ∑ i = 1 n p 1 l o g p i E(info) = -plog(p)-(1-p)log(1-p)=-\sum_{i=1}^{n}p_1logp_i

这样一来我们就导出了信息熵的定义：

H ( X ) = − ∑ i = 1 n p ( x i ) l o g p ( x i ) H(X)=-\sum_{i=1}^{n}p(x_i)logp(x_i)

联合熵

联合熵的概念很好理解，结合联合概率密度分布，有：

H ( X , Y ) = − ∑ j = 1 m ∑ i = 1 n p ( x i , y i ) l o g p ( x i , y i ) H(X,Y)=-\sum_{j=1}^{m}\sum_{i=1}^{n}p(x_i,y_i)logp(x_i,y_i)

条件熵

首先我们定义：在X给定条件下，Y的平均不确定性。
设有随机变量（X,Y），其联合概率分布为：

p ( X = x i , Y = y j ) = p i j p(X=x_i,Y=y_j)=p_{ij}

对应条件概率公式:

P ( X ∣ Y ) = P ( X Y ) P ( Y ) P(X|Y)=\frac{P(XY)}{P(Y)}

有链规则：

H ( Y ∣ X ) = H ( X ∣ Y ) − H ( X ) H(Y|X)=H(X|Y)-H(X)

我们可以得到条件熵的定义:

H ( X , Y ) − H ( X ) = − ∑ x , y p ( x , y ) l o g p ( x , y ) + ∑ x p ( x ) l o g p ( x ) = − ∑ x , y p ( x , y ) l o g p ( x , y ) + ∑ x ( ∑ y p ( x , y ) ) l o g p ( x ) = − ∑ x , y p ( x , y ) l o g p ( x , y ) + ∑ x , y p ( x , y ) l o g p ( x ) = − ∑ x , y p ( x , y ) l o g p ( x , y ) p ( x ) = − ∑ x , y p ( x , y ) l o g p ( y ∣ x ) \begin{aligned} H(X,Y)-H(X) &=-\sum_{x,y}p(x,y)logp(x,y)+\sum_xp(x)logp(x) \\ &=-\sum_{x,y}p(x,y)logp(x,y)+\sum_x(\sum_yp(x,y))logp(x) \\ &=-\sum_{x,y}p(x,y)logp(x,y)+\sum_{x,y}p(x,y)logp(x)\\ &=-\sum_{x,y}p(x,y)log\frac{p(x,y)}{p(x)} \\ &=-\sum_{x,y}p(x,y)logp(y|x) \end{aligned}

根据定义我们可以得到:

H ( X , Y ) − H ( X ) = − ∑ x , y p ( x , y ) l o g p ( y ∣ x ) = − ∑ x ∑ y p ( x , y ) l o g p ( y ∣ x ) = − ∑ x ∑ y p ( x ) p ( y ∣ x ) l o g p ( y ∣ x ) = ∑ x p ( x ) ( − ∑ y p ( y ∣ x ) l o g p ( y ∣ x ) ) = ∑ x p ( x ) H ( Y ∣ X = x ) \begin{aligned} H(X,Y)-H(X) &=-\sum_{x,y}p(x,y)logp(y|x)\\ &=-\sum_x\sum_yp(x,y)logp(y|x)\\ &=-\sum_x\sum_yp(x)p(y|x)logp(y|x)\\ &=\sum_xp(x)(-\sum_yp(y|x)logp(y|x))\\ &=\sum_xp(x)H(Y|X=x) \end{aligned}

例子

还是天气情况与去不去打高尔夫之间的关系。

Day Outlook Temperature Humidity Windy Play Golf?
1 Sunny 85 85 False No
2 Sunny 80 90 True No
3 Overcast 83 78 False Yes
4 Rainy 70 96 False Yes
5 Rainy 68 80 False Yes
6 Rainy 65 70 True No
7 Overcast 64 65 True Yes
8 Sunny 72 95 False No
9 Sunny 69 70 False Yes
10 Rainy 75 80 False Yes
11 Rainy 75 70 True Yes
12 Overcast 72 90 True Yes
13 Overcast 81 75 False Yes
14 Rainy 71 80 True No

设随机变量Y={Yes,No},代表去不去打高尔夫球，我们可以统计出,去的概率为9/14,那么Y的熵，根据熵的公式来算，可以得到

H ( Y ) = − 9 1 4 l o g 2 9 1 4 − 5 1 4 l o g 2 5 1 4 = 0 . 9 4 H(Y)=-\frac{9}{14}log_2\frac{9}{14}-\frac{5}{14}log_2\frac{5}{14}=0.94

我们还有一个变量Windy，代表是否有风,当有风时，统计出以下高亮所示：

Day Outlook Temperature Humidity Windy Play Golf?
1 Sunny 85 85 False No
2 Sunny 80 90 True No
3 Overcast 83 78 False Yes
4 Rainy 70 96 False Yes
5 Rainy 68 80 False Yes
6 Rainy 65 70 True No
7 Overcast 64 65 True Yes
8 Sunny 72 95 False No
9 Sunny 69 70 False Yes
10 Rainy 75 80 False Yes
11 Rainy 75 70 True Yes
12 Overcast 72 90 True Yes
13 Overcast 81 75 False Yes
14 Rainy 71 80 True No

可以得出，已知有风的条件下，满足条件的只有六个数据了，在这六个数据中，去打高尔夫的天数为3，占1/2，不去的天数为3，占1/2.
那么此时：

H ( Y ∣ X = T r u e ) = − 1 2 l o g 2 1 2 − 1 2 l o g 2 1 2 = 1 H(Y|X=True)=-\frac{1}{2}log_2\frac{1}{2}-\frac{1}{2}log_2\frac{1}{2}=1

同理:

H ( Y ∣ X = F a l s e ) = − 1 4 l o g 2 1 4 − 3 4 l o g 2 3 4 = 0 . 8 1 H(Y|X=False)=-\frac{1}{4}log_2\frac{1}{4}-\frac{3}{4}log_2\frac{3}{4}=0.81

p ( X = T r u e ) = 3 7 p(X=True)=\frac{3}{7}

因此条件熵为:

H ( Y ∣ X = W i n d y ) = p ( X = T r u e ) ∗ H ( Y ∣ X = T r u e ) + p ( X = F a l s e ) ∗ H ( Y ∣ X = F a l s e ) = 0 . 8 9 1 4 H(Y|X=Windy)=p(X=True)*H(Y|X=True)+p(X=False)*H(Y|X=False)=0.8914

信息增益

信息熵H(X)度量了X的不确定性，条件熵H(X|Y)度量了我们在知道Y以后X剩下的不确定性。那么H(X)-H(X|Y)呢,从上面的描述大家可以看出，它度量了X在知道Y以后不确定性减少的程度。这个度量我们在信息论中称为信息增益，记为I(X,Y).

I ( X , Y ) = H ( X ) + H ( Y ) − H ( X , Y ) I(X,Y)=H(X)+H(Y)-H(X,Y)

I ( X , Y ) = ∑ x , y p ( x , y ) l o g p ( x , y ) p ( x ) p ( y ) I(X,Y)=\sum_{x,y}p(x,y)log\frac{p(x,y)}{p(x)p(y)}

可以看出，如果X,Y完全独立，则信息增益I(X,Y)为0，不独立，则大于0.
互信息的物理意义：
从另外一个维度定义条件熵

H ( Y ∣ X ) = H ( X , Y ) − H ( X ) H(Y|X)=H(X,Y)-H(X)

H ( Y ∣ X ) = H ( Y ) − I ( X , Y ) H(Y|X)=H(Y)-I(X,Y)

对偶式得到关于联合熵的定义

I ( X , Y ) = H ( X ) + H ( Y ) − H ( X , Y ) I(X,Y)=H(X)+H(Y)-H(X,Y)

信息增益率

它是信息增益和特征熵的比值，即

I R ( Y , X ) = I ( Y , X ) H X ( Y ) I_R(Y,X)=\frac{I(Y,X)}{H_X(Y)}

其中Y是样本特征输出的集合，X为样本特征。其中特征熵的表达式如下:

H X ( Y ) = − ∑ i = 1 n p ( x i ) l o g p ( x i ) H_X(Y)=-\sum_{i=1}^np(x_i)logp(x_i)

其中n为特征X的类别数，特征数越多对应的特征对应的特征熵越大，它所作为分母，可以校正信息增益容易偏向取值较多的特征的问题。

参考资料

决策树（一）：信息熵

决策树-ID3、C4.5

展开全文
相关主题
决策树
Top
微信扫码咨询专知VIP会员
Top