谈谈熵、信息熵和决策树的那些事儿

熵

19世纪，工程师在关注蒸汽机效率这个问题的时候，水要达到多热，要加入什么样的沸腾的物质才能让蒸汽机效率更高等等，为解答这些问题，热力学诞生了，并引入了热量、温度、能量等概念。并出现了热力学定律，这个时候的热力学定律是为了解释热量是如何流动。

随着科学家了解深入，以及为了更好的理解宇宙进化及时间流逝，热力学第二定律出现了熵这个概念，熵的概念是由德国物理学家克劳修斯于1865年所提出。熵最初是被用在热力学方面的，由热力学第二定律可以推出熵增的结论，然后熵是用来对一个系统可以达到的状态数的一个度量，能达到的状态数越多熵越大。

信息熵

信息熵也基本是很类似的，是香农1948年的一篇论文《A Mathematical Theory of Communication》提出了信息熵的概念，并且以后信息论也被作为一门单独的学科。

信息熵是用来衡量一个随机变量出现的期望值，一个变量的信息熵越大，那么他出现的各种情况也就越多，也就是包含的内容多，我们要描述他就需要付出更多的表达才可以，也就是需要更多的信息才能确定这个变量。在吴军的那篇《汉语信息熵和语言模型的复杂度》文章里说，只考虑字频的话英文是4.46比特/字符的信息熵，汉字是9.6比特/字符，直观上很容易理解，英文字母只有26个，所以描述一个字母所需要的信息表示不多，而中文字却很多，就需要更多的信息量才能表示。

用点通俗的来讲，信息熵衡量了一个系统的复杂度，比如当我们想要比较两门课哪个更复杂的时候，信息熵就可以为我们作定量的比较，信息熵大的就说明那门课的信息量大，更加复杂。

决策树

、

那么信息熵可以做什么呢，首先信息熵作为衡量一个系统复杂度的表示，在压缩时就相当于一个压缩极限的下限，不同的内容，如果他的信息熵越小，说明信息量越小，也就是压缩后所占的体积能够更小，信息熵在人工智能方面也有很多的应用，其中最有名的就是最大熵原理，保留尽可能大的不确定性而作出最佳的尽量无偏差的决定。

接着谈我们正在做着并且火着的大数据吧。数据挖掘中有一类很重要的应用是分类器是决策树，决策树最重要的点是一层层剥离根、页节点，而最简单的方法就是通过信息熵。

为了使决策树最优，哪一个属性将在树的根节点被测试？分类能力最好的属性被选作树的根结点的测试。采用不同测试属性及其先后顺序将会生成不同的决策树。信息熵在决策树中的计算过程起了非常大的作用，它能够帮助我们从众多潜在的决策树中找到最有效的那一个。

定义一个统计属性，称为“信息增益”（information gain），用来衡量给定的属性区分训练样例的能力。度量信息增益的标准为“熵”（entropy）。信息量就是不确定性的多少，熵越大，信息的不确定性越大。

自信息量：log(1/P)

H(x)=−∑x∈XP(x)log2P(x) //P(x)表示x发生的概率。

信息增益：Gain(S,A)≡Entropy(S)−∑v∈Values(A) Sv /S Entropy(Sv)

Values(A)是属性A所有可能值得集合，Sv是S中属性A的值为v的子集。该等式的第一项就是原集合S的熵，第二项是用A分类后S的熵的期望值。第二项描述的期望熵就是每个子集的熵的加权和，权值为属于Sv的样例占原始样例S的比例Sv /S。

对于测试数据集而言，假定数据集S有14个样例，9个正例，5个负例，三类属性（A1，A2，A3）：

则：Entropy(S)=-(9/14)log2(9/14)-(5/14)log2(5/14)=0.940。

每个属性的Entropy(S)=属性下集合的Entropy(S)的概率乘积。

而每个属性信息增益则是：数据集Entropy(S)-每个属性的Entropy(S)；然后选择最大的那个属性作为此轮迭代的根节点属性，接着依次类推我们就能构造出整个决策树。