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

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);然后选择最大的那个属性作为此轮迭代的根节点属性,接着依次类推我们就能构造出整个决策树。

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20171213G0D7VZ00?refer=cp_1026

扫码关注云+社区