信息论中的一些基本知识-阿里云开发者社区

信息论中的一些基本知识

2013-12-27 1163

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 原文来自:http://www.cnblogs.com/zhangchaoyang 作者:Orisun信息论（Information Theory）是概率论与数理统计的一个分枝。

原文来自:http://www.cnblogs.com/zhangchaoyang 作者:Orisun

信息论（Information Theory）是概率论与数理统计的一个分枝。用于信息处理、信息熵、通信系统、数据传输、率失真理论、密码学、信噪比、数据压缩和相关课题。

基本概念

先说明一点：在信息论里面对数log默认都是指以2为底数。

自信息量

$I(x_i)=-log\ p(x_i)\qquad\cdots\cdots(1)$

联合自信息量

$I(x_i,y_j)=-log\ p(x_i,y_j)\qquad\cdots\cdots(2)$

条件自信息量

$I(x_i|y_j)=-log\ p(x_i|y_j)\qquad\cdots\cdots(3)$

信息熵

$H(X)=-\sum{p(x_i)log\ p(x_i)}\qquad\cdots\cdots(4)$

条件熵

$H(X|Y)=-\sum_i\sum_j{p(x_i,y_j)log\ p(x_i|y_j)}=\sum_i\sum_j{p(x_i,y_j)I(x_i|y_j)}\qquad\cdots\cdots(5)$

联合熵

$H(X,Y)=-\sum_i\sum_j{p(x_i,y_j)log\ p(x_i,y_j)}=\sum_i\sum_j{p(x_i,y_j)I(x_i,y_j)}\qquad\cdots\cdots(6)$

根据链式规则，有

$H(X,Y)=H(X)+H(Y|X)=H(Y)+H(X|Y)\qquad\cdots\cdots(a)$

可以得出

$H(X)-H(X|Y)=H(Y)-H(Y|X)\qquad\cdots\cdots(b)$

信息增益Information Gain

系统原先的熵是H(X)，在条件Y已知的情况下系统的熵（条件熵）为H(X|Y)，信息增益就是这两个熵的差值。

$IG=H(X)-H(X|Y)\qquad\cdots\cdots(7)$

熵表示系统的不确定度，所以信息增益越大表示条件Y对于确定系统的贡献越大。

信息增益在特征选择中的应用

由（7）式可以直接推出词条w的信息增益，（7）式中的X代表类别的集合，Y代表w存在和不存在两种情况

$IG(w)=H(C)-H(C|w)$

$=-\sum_i{p(c_i)log\ p(c_i)}+\sum_i{p(c_i,w)log\ p(c_i|w)}+\sum_i{p(c_i,\overline{w})log\ p(c_i|\overline{w})}$

$=-\sum_i{p(c_i)log\ p(c_i)}+p(w)\sum_i{p(c_i|w)log\ p(c_i|w)}+p(\overline{w})\sum_i{p(c_i|\overline{w})log\ p(c_i|\overline{w})}\qquad\cdots\cdots(8)$

p(c_i)是第i类文档出现的概率；p(w)是在整个训练集中包含w的文档占全部文档的比例；p(c_i|w)表示出现w的文档集合中属于类别i的文档所占的比例； $p(c_i|\overline{w})$ 表示没有出现w的文档集合中属于类别i的文档所占的比例。

信息增益在决策树中的应用

outlook	temperature	humidity	windy	play
sunny	hot	high	FALSE	no
sunny	hot	high	TRUE	no
overcast	hot	high	FALSE	yes
rainy	mild	high	FALSE	yes
rainy	cool	normal	FALSE	yes
rainy	cool	normal	TRUE	no
overcast	cool	normal	TRUE	yes
sunny	mild	high	FALSE	no
sunny	cool	normal	FALSE	yes
rainy	mild	normal	FALSE	yes
sunny	mild	normal	TRUE	yes
overcast	mild	high	TRUE	yes
overcast	hot	normal	FALSE	yes
rainy	mild	high	TRUE	no

（7）式中的X表示打球和不打球两种情况。

只看最后一列我们得到打球的概率是9/14，不打球的概率是5/14。因此在没有任何先验信息的情况下，系统的熵（不确定性）为

$H(X)=-\frac{9}{14}log\frac{9}{14}-\frac{5}{14}log\frac{5}{14}=0.94$

outlook			temperature			humidity			windy			play
	yes	no		yes	no		yes	no		yes	no	yes	no
sunny	2	3	hot	2	2	high	3	4	FALSE	6	2	9	5
overcast	4	0	mild	4	2	normal	6	1	TRUR	3	3
rainy	3	2	cool	3	1

如果选outlook作为决策树的根节点，（7）式中的Y为集合{sunny、overcast、rainy}，此时的条件熵为

$H(X|Y)=-p(sunny,yes)log\ p(yes|sunny)-p(sunny,no)log\ p(no|sunny)$

$-p(overcast,yes)log\ p(yse|overcast)-p(overcast,no)log\ p(no|overcast)$

$-p(rainy,yes)log\ p(yse|rainy)-p(rainy,no)log\ p(no|rainy)$

$=-p(sunny)[p(yes|sunny)log\ p(yes|sunny)+p(no|sunny)log\ p(no|sunny)]$

$-p(overcast)[p(yes|overcast)log\ p(yes|overcast)+p(no|overcast)log\ p(no|overcast)]$

$-p(rainy)[p(yes|rainy)log\ p(yes|rainy)+p(no|rainy)log\ p(no|rainy)]$

$=-\frac{5}{14}[\frac{2}{5}log\frac{2}{5}+\frac{3}{5}log\frac{3}{5}]-\frac{4}{14}[\frac{4}{4}log\frac{4}{4}+0log0]-\frac{5}{14}[\frac{3}{5}log\frac{3}{5}+\frac{2}{5}log\frac{2}{5}]=0.693$