【文本分类】 特征抽取之信息增益

 

全文装载：http://www.blogjava.net/zhenandaci/archive/2009/03/24/261701.html

作者：Jasper (from BlogJava)

 

在前面的《文本分类概述》文章中，我们讲到了基于统计学习的方法进行分类的关键在于对训练集语料的特征选择的好坏。那么训练集中哪些词可以作为特征，哪些词则不能呢？我们必须对训练集中所有词语量化其重要程度。信息增益 (IG, Information Gain ) 就是一种很有效的特征量化方法(特征选择方法)。

 

在信息增益中，重要性的衡量标准就是看特征能够为分类系统带来多少信息，带来的信息越多，该特征越重要。

 

(1) 信息量是如何度量的 —— 信息熵 Entropy

因此先回忆一下信息论中有关信熵 的定义。说有这么一个变量X，它可能的取值有n多种，分别是x₁ ，x₂ ，……，x_n ，每一种取到的概率分别是P₁ ，P₂ ，……，P_n ，那么X的熵就定义为：

                                       

                       想要对这个公式又较深的理解，请参见《Google黑板报--数学之美》第四章

 

这个公式可以反映一个变量X出现某种值的可能性越多，它携带的信息量就越大。这个道理很好理解，比如X代表一个问题，这个问题可能有10种答案，那么自然我们需要较多的信息量才能准确的知道答案。而如果问题只有一种答案，我们所需要知道的信息量自然也就少很多了。

 

( 2) 在分类领域中，信息熵和信息增益的使用

对分类系统来说，类别C是变量，它可能的取值是C₁ ，C₂ ，……，C_n ，而每一个类别出现的概率是P(C₁ )，P(C₂ )，……，P(C_n )，因此n就是类别的总数。此时整个分类系统的熵就可以表示为：

                                      

上面的公式中  P(Ci)表示Ci类中包含文档数量占整个分类体系中全部文档数量的比重

 

那么信息增益是针对一个个的特征而言的，就是看一个特征t。整个系统中某些文本有t和整个系统中都没t 的时候信息量各是多少，两者的差值就是这个特征t给系统带来的信息量，即信息增益 。

 

系统有t的时候信息量很好计算，就是上面的式子，它表示的是包含所有特征时系统的信息量。

 

问题是假如把系统中的t全部去掉以后，信息量如何计算？我们换个角度想问题，把系统要做的事情想象成这样：说教室里有很多座位，学生们每次上课进来的时候可以随便坐， 因而变化是很大的（无数种可能的座次情况）；但是现在有一个座位，看黑板很清楚，听老师讲也很清楚，于是校长的小舅子的姐姐的女儿托关系，把这个座位定下来了，每次只能给她坐，别人不行。那么在这种情况下，对于其他同学来说，教室里有没有这个位置都是一样的。

 

对应到分类系统中，就是说下面两个命题是等价的。(1) 所有的文本中都没有出现特征t；(2) 系统虽然包含特征t，但是t的值已经固定了。这里所说的t的值指的就是t存在和t不存在两种值。

 

因此我们计算分类系统不包含特征t的信息量，就使用上面第(2)中情况来代替，就是计算当一个特征t值确定后，系统的信息量是多少。这个信息量其实也有专门的名称，就叫做“条件熵 ”，条件嘛，自然就是指“t已经固定“这个条件。

 

但是问题接踵而至，例如一个特征X，它可能的取值有n多种（x₁ ，x₂ ，……，x_n ）， 当计算条件熵而需要把它固定的时候，要把它固定在哪一个值上呢？答案是每一种可能都要固定一下，计算n个值，然后取均值才是条件熵。而取均值也不是简单的 加一加然后除以n，而是要用每个值出现的概率来算平均（简单理解，就是一个值出现的可能性比较大，固定在它上面时算出来的信息量占的比重就要多一些）。条件熵公式如下：

 

那么具体到我们在分类系统中讨论特征t固定后的条件熵为：

上面公式中前半部分P(t)表示整个分类系统中包含特征t的文档数量占全部文档数量的比重，P(Ci|t)表示包含了特征 t 的Ci 类中的文档数量占整个系统中包含了特征 t 的文档数量的比重。 而后版本分的 非t 表示不包含 t 的文档比重。

 

那么特征t的信息增益公式为：    IG(T)=H(C) - H(C|T)

 

(3) 实验证明分类系统的特征信息熵

 

我使用了复旦大学分类语料库的20个大类9787语料作为训练集合，计算训练集合中所有不同词语的信息增益。下图是其中五个词语在分类系统中的文档分布：

实验结果： GI(原文)=0.5294024092788958

                GI(参考文献)=0.2888259720738895

                GI(计算机)=0.1612834659409792

                GI(##0.0)=0.0002919484403363093

                GI(广东人)=0.0013525481719112165

 

       我们发现，当词语t分布在很少的几个类中时(比如"##0.0"和"广东人")，说明t在类别中的情况比较少，也就是说t属于Cx的不确定性比较小，那么该 t 所包含的信息量也就比较小。因此当 t 值固定之后，对整个文本集合的信息量影响也就不大，因此H(C|t) = H(C) (基本相等)。那么词语 t 的信息增益也就非常小了。

       而"原文"，“参考文献”，“计算机”分布的类别比较多，信息增益也就大了。

 

       从这个实验我们可以看出，在训练语料中分布类别比较广泛的词语，信息增益都比较高。我们可以认为这些词语对整个训练语料有比较重要的意义。但是信息增益只能获得整个训练语料的特征词，其值不能区分不同类别间的特征词的权重。因此对于特征词权重的计算。我们还需要采取很多其他方法，其中最常用的就是TF*IDF了。

评论

1 楼 fuhao_987 2011-07-10  

请问你是对训练集合中所有词都计算了信息熵吗？？那有多少个词啊~~还有你算的时候速度怎么样啊~~