【Python机器学习】信息熵和在决策树中的运用（附源码）

之前在【Python机器学习】系列五决策树非线性回归与分类（深度详细附源码）一期中， 我们提到了用熵来度量信息的不确定性和信息增益。今天我们来详细解读一下什么是信息熵及其相关概念，以及如何进行信息增益的计算和它在decision tree中的运用。

信息熵与热力学熵

学过化学或热力学的同学可能了解热力学熵。 熵的概念由德国物理学家克劳修斯提出，其定义为：在一个可逆性程序里，被用在恒温的热的总数。宏观上，热力学熵主要用于研究热机，微观上，玻尔兹曼将其赋以统计学意义用以描述系统的混乱程度。而信息熵也称为香农熵， 香农于1948年将热力学中的熵的概念引入到信息论中，来度量信息中的信息量。与信息量相关的是信息的不确定性，如果一条信息中不确定性越大， 我们就希望获得更多的信息去消除不确定性并了解信息所想要表达的真正意思。因此对信息量的量化也可以理解为对一则信息不确定性的量化。

在吴军老师的《数学之美》一书中有这样的例子： 假如你totally错过了2010年的世界杯， 如果有人问你此届世界杯的冠军是谁，在没有任何提示下，你需要从32支队伍中猜出谁夺得了大力神杯。每猜一次需要花费1bit信息量，而提问者会回答：是或否。 如果你对32个球队一无所知（比如以为皇马也来参加了世界杯。。）并假定32支队伍夺冠几率相同，你可能会采取二分法来逐渐缩小范围。这样你总共需要花费5 bit 信息量，因为log 32 = 5。 而假如你对足球有一定的了解，会知道每个球队夺冠的概率是不一样的。那么根据香农熵的公式，准确信息量将应该是

条件熵(conditional entropy)

因为相关信息的存在也可以消除不确定性， 比如在自然语言模型中，相比于一元语言模型，二元语言模型除了参考词语本身的概率之外还要借助上下文的信息，因此结果更为准确。 假如说我们想要知道随机变量X的信息熵，同时我们已知在随机变量Y出现时X出现的概率（条件概率）和X，Y同时出现的概率（联合概率）这些信息， 那么我们计算在Y的条件下X的熵为：

这个熵不同于H(X)， 被称为条件熵。 在X和Y不相互独立的时候，因为我们得到了Y的信息，我们确定X所需要的信息熵就下降了。 因此 H(X)>=H(X|Y)。

互信息(mutual information)

互信息是用来量化两个变量X，Y相关性的量。它的定义为：

互信息的意义为：由于事件X发生与事件Y发生相关联而提供的信息量。 I(X|Y）同时也是H(X)与条件熵H(X|Y)之间的差。

相对熵（Kullback-Leibeler Divergence）

相对熵又称KL散度，用来衡量两个取值为正数的函数的相关性。他的定义为：

相对熵具有如下性质：

1. 相对熵始终大于等于0，两个完全相同的函数相对熵为0

2. 相对熵不对称， 即KL(A||B)不等于KL(B||A)

2. 相对熵越大，函数差异越大

3. 相对熵可以度量两个随机分布之间的距离

相对熵常用来做文本相似度分析，以及在多指标系统中用来进行指标权重分配。

我们可以比较互信息和相对熵的概念，发现互信息是在求KL(P(x,y)||P(x)P(y))。当X 与Y相互独立时，P(x,y)=P(x)P(y)。所以当X与Y相互独立时互信息为0。从上面的韦恩图中也可以看出。

信息增益(Information Gain)

信息增益表示在条件a下，信息不确定性减少的量。与互信息不同的是，互信息衡量的是两个变量之间的相关性，而信息增益衡量的是系统分类后增加的信息量，a指的是分类方式。

算法

介绍完基本概念后，我们可以了解在决策树中常用的算法。算法主要有三种： ID3, C4.5以及CART。再此主要介绍ID3和C4.5.

ID3

ID3 是基于以信息熵和信息增益为衡量标准来选取属性进行分类的方式。其基本思路如下：

在决策树中，结点可以分为：根结点，内部结点，叶结点。在选取根结点和内部结点时，我们选择信息增益最大的属性。比如我们拥有一个training set数据集S其类别集合为｛0，1｝，参与分类的属性集合为{A,B,C,D}，那我们分别计算IG(S, A), IG(S,B), IG(S,C), IG(S,D)。按照上面的公式：IG(S,A)=H(S)-H(S|A) ，求得最大IG最大的属性，即可作为本次划分的结点。划分直至终结条件满足后，决策树构建完成。

终结条件主要分两种：

1 划分出的类为同类

2 所有属性已被考虑，不再有属性可供再分

在Machine Learning in Action 一书中有ID3的详细代码（python）

C4.5

C4.5是在ID3基础上的扩展，不同的是，C4.5用的是信息增益率来进行属性选择。信息增益率定义如下：

其中 Gain(S,A)=IG(S,A)，就是信息增益

SplitInfo(S,A)指的是按照属性A对S的信息分裂值，用以将信息增益规范化，因此避免了ID3中指标偏向分支多的属性的倾向。C4.5算法框架如下：

参考文献： 《数学之美》－吴军［著］ Machine Learning in Action --Peter Harrington http://blog.csdn.net/google19890102/article/details/28611225 http://shiyanjun.cn/archives/417.html http://isilic.iteye.com/blog/1844097