一种改进的贝叶斯文本分类方法

1、第25卷第2期收稿日期:2006212215基金项目:重庆市自然科学基金资助项目(CSTC 2006BB 2021作者简介:张玉芳(1965,女,上海人,重庆大学副教授,硕导。一种改进的贝叶斯文本分类方法张玉芳,陈剑敏,熊忠阳(重庆大学计算机学院,重庆400030摘要:朴素贝叶斯分类(naive Bayes 有一个“独立性假设”:给定一个实例的类标签,实例中的每个属性的出现都独立于实例中其他属性的出现,而在实际应用中这种条件并不易满足,另外由于文本的特殊性,相关的特征项可能会产生新的语义信息。因此在训练文本时,对特征选择后产生的特征集用一种可行的方法考察它们之间的相关性,然后对相关程度高的特征

2、进行合并处理。实验数据表明,这个改进的方法能提高朴素贝叶斯的算法精确度。关键词:文本分类;独立性假设;相关性中图分类号:T P 392文献标识码:A 文章编号:100126600(2007022*文本分类的目标是在分析文本内容的基础上给文本分配一个或者多个比较合适的类别,文本分类的过程是对训练集中文档的内容进行分析,构造一个分类器,用这些分类器对新文档分类,对文本分类的研究大大缩小信息检索的范围,增强检索对象与检索要求的相关性1。目前较为著名的文本分类方法有B ayes 方法、k 2NN 方法、神经网络方法、决策树方法、支持向量机算法等,其中朴素贝叶斯方法是目前公认的一种简单有效的分类方法,它

3、是一种基于概率的分类方法。1朴素贝叶斯分类目前大多数分类方法是基于向量空间模型的2,在该模型中,每个文档可看作词的序列,文档中的词称为特征,在经过切分词、去除停用词、截取词干等预处理后得到一个特征集合,还需要进行特征选择,找出能最好地代表一个文档或者类别的特征来参与分类计算,这样文档表示为由特征组成的特征矢量。1.1朴素贝叶斯分类器及独立假设贝叶斯文本分类模型是一种典型的基于统计方法的分类模型3,它利用先验信息和样本数据信息来确定事件的后验概率。令论域U =(w 1,w 2,w 3,w n ,C 是离散随机变量的有限集,其中w 1,w 2,w 3,w n 为特征项集,类变量C 的取值范围为(c

4、 1,c 2,c 3,c l ,一个文档d i 表示为特征向量(w 1,w 2,w 3,w n ,则d i 属于类c j 的概率可表示为:p (c j w 1,w 2,w 3,w n =p (w 1,w 2,w 3,w n c j p (c j p (w 1,w 2,w 3,w n 。(1根据概率的链规则:p (w 1,w 2,w 3,w n c j =7n i =1p (w i w 1,w 2,w i -1,c j ,(2朴素贝叶斯分类模型中的属性独立假设假定所有的属性都是相互条件独立,即有:p (w i w 1,w 2,w i -1,c j =p (w i c j ,(3结合公式(2、(3

5、,公式(1则变为:p (c j w 1,w 2,w 3,w n =7n i =1p (w i c j p (c j p (w 1,w 2,w 3,w n 。(4根据贝叶斯最大后验准则,给定某一待分类文本d i =(w 1,w 2,w 3,w n ,贝叶斯分类器选择使后验概率p (c j w 1,w 2,w 3,w n 最大的类作为该文本的类标签。朴素贝叶斯的独立性假设提高了分类的效率,但在实际应用中这种独立性假设是不太可能满足的,因此改进朴素贝叶斯文本分类器,使之在独立性假设不能满足的情况下具有较高的分类精度和分类效率,是值得研究的领域。Kononenko 的sem i 2naive 分类器4

6、将属性集分割成若干个不相交的属性组,假设在不同组中的属性之间是相互独立的,而同一属性组内的各属性相互关联,但这样大大增加学习的开销,对于特征项众多的文本分类并不现实。1.2TAN 树扩展朴素贝叶斯分类方法TAN (tree augm en t naive B ayes 是由F riedm an 等人提出的一种树状结构模型5,6,它将贝叶斯网络的部分表示依赖关系的能力与朴素贝叶斯方法的简易性结合。在TAN 结构中,类变量C 是根,没有父结点,特征项要不以类结点作为其父结点,要不以一个其他的特征项作为其父结点,这时这个其他的特征项只能以类结点作为父结点。因此p (w i w 1,w 2,w i -

7、1,c j =p (w i c j (特征项w i 只有类结点作为父结点或者p (w i w 1,w 2,w i -1,c j =p (w i w p ,c j (特征项w i 以一个其他特征项w p 作为父结点,即特征项w i 对分类的影响依赖于特征项w p ,此时w p 只能以类变量作为父结点,w p w 1,w 2,w i -1,TAN 分类模型具有较好的综合性能,体现了学习效率与分类精度之间的一种适当的折衷。2本文的改进方法相对于朴素贝叶斯,sem i 2naive 分类器和TAN 方法在一定程度上克服了基于属性独立性假设的限制,但实现相对复杂并且学习的效率相对朴素贝叶斯方法大幅度下降

8、,对于特征项众多的文本分类而言计算量是相当巨大的,并且在文本分类中,相关联的特征项除了存在一定的依赖关系外,他们一起出现还可能产生新的语义信息,因此对分类的性能有一定的影响,所以对相关的特征项进行归一的计算对最终的分类可能会取到很好的效果。要对相关的特征项进行合并,首先要从特征项集中找出相关程度较高的特征项,对文本分类而言,特征项之间的联系可能是错综复杂的,要衡量多个特征之间的相关程度是不容易实现的。本文从简易性的思想出发认为:一个特征项最多与一个其他的特征项关联。先得出相关程度较高的两两特征项,然后对这些特征项进行适当的处理来提升贝叶斯方法的性能。为描述两个特征项之间的相关程度,要给出一种数

9、学方法来度量。准确度量高维的特征相关度是困难的,这样做不仅问题复杂,而且得出相关的可能性并不可靠。本文用一种简单可行的方法度量两个特征项之间的相关程度。互信息7是一种广泛用于建立词关联统计模型的标准,互信息量反映了两个随机事件的统计关联程度,这里借用这个概念来表示两个特征项间的关联程度,在类别c j 中两个特征w i ,w p 之间的互信息计算公式为:I (w i ,w p c j =log p (w i ,w p c j p (w p c j p (w i c j ,(5其近似计算公式为:I (w i ,w p c j =log A N (A +L (A +K 。(6再考虑两个特征在该类别的

10、训练文本集的各个文档中一起出现的词频数,可以采用下面的公式来计算两个特征项在类别c j 之间的相关性:D (w i ,w p c j H Nlog A N (A +L (A +K ,(7其中N 为类别c j 中的文档总数,H 为两个特征项在类别c j 中一起出现的词频总数,A 为类别c j 中一起出现的文档数量,K 为类别c j 中w i 出现w p 不出现的文档数,L 为类别c j 中w p 出现且w i 不出现的文档数。若w i 、702第2期张玉芳等:一种改进的贝叶斯文本分类方法w p不相关,p(w i,w p c j=p(w p c jp(w i c j,即A N(A+L(A+K N2

11、,此时D(w i,w p c j0。但在实际应用中,如果对所有D(w i,w p c j0的特征项都要考虑的话,计算量是十分惊人的,另外若所有D(w i,w p c j都是从实际训练文本集得到,有可能D(w i,w p c j0并不代表两者一定相关,这样反而使精度下降。为了解决这个问题,可以采用一个统计上的阈值,当D(w i,w p c jc时,两个特征项才相关。考察特征项相关性的算法描述如下:B egin对所有的类别c j do;计算所有的特征项(w i,w p在类别c j中的相关性D(w i,w p c j;生成包含所有特征项对(w i,w p的集合S;Fo r(w i,w pSIf m

12、ax(D(w i,w p c jc then在类别c j加入合并的特征项w ip;在S中删除含有w i或者w p的特征项对;E lse ex itEnd fo rEnd。在得到相关性大的两两特征项后,本文采用以下的方法处理取得了较好的效果:在类别c j中如果w i,w p相关,则加入一个新的特征项w ip进行计算,相应地修改w i、w p的词频数。例如有一个文档d i,w i的词频数为a,w p的词频为b,ab,则计算p(c j d i时,w i的词频数为a-b,w p的词频为0,特征项w ip的词频为b。经过上述处理后,再采用朴素B ayes方法对文本分类,比较新文本属于所有类的几率,将文本

13、分到几率最大的那个类别中。3实验及结果分析在实验中采用了宏观平均F1值和微观平均F1值来评估分类的性能8。实验利用在CNL P下载的一个小型语料库作为测试数据。按照21的原则,把语料库分为训练文档和测试文档两个部分。当衡量特征项相关程度的限值c取不同值时,会影响文本分类的效果(图1,并且c值越小,考察特征的相关性时得出相关的特征项越多,算法的效率越低,从附图中可以看出c=0.3时性能最好,考虑到效率问题,实验采用了效果较好的c=0.4。表1实验结果Tab.1The result of exper i m en t 01图1参数c与精确度的关系F ig.1T he relati on of be

14、tw een Param eter c andthe p recisi on4结论本文介绍了一种改进的B ayes文本分类方法,它通过统计方法评估出特征项在类之间的相关性,然后802广西师范大学学报:自然科学版第25卷将相关性高的特征项合并,根据实验结果(表1可以看出,改进后的方法在分类精度上略优于naive B ayes 方法,由于特征选取后全部特征项都参与了计算,所以训练的时间很长。下一步将重点考虑如何只选取部分特征来考察相关性,在保证精确度的同时提高算法效率。参考文献:1Fabrizi o Sebastiani .M ach ine learning in autom ated text

15、 catego rizati on J .A C M Computing Curveys ,2002,34(1:11212,32233.2王灏,黄厚宽,田盛丰.文本分类实现技术J .广西师范大学学报:自然科学版,2003,21(S 1:1732179.3M cCALLUM A ,N IGAM K .A comparison of event models fo r N aive Bayes text retrival J .Info r m ati on P rocessingand M anagem ent ,1998,24(5:5132523.4KONON EN KO I .Sem i 2

16、N aive Bayesian classifiers C P roceedings of European Conference on A rtificial Intelli 2gence .Berlin :Sp ringer 2V erlag ,1991:2062219.5FR IEDM AN N ,GE IGER D ,GOLD SZ M I D T M .Bayesian netw o rk classifiers J .M ach ine L earning ,1997,29(23:1312163.6石洪波,王志海,黄厚宽.一种基于TAN 的文本分类方法J .广西师范大学学报:自然科

17、学版,2003,21(1:81285.7鲁晨光.广义信息论研究M .合肥:中国科技大学出版社,1993.8YAN G Y i 2m ing .A n evaluati on of statistical app roach to text catego rizati on J .Info r m ati on R etrieval ,1999,1(12:69290.I m p roved N aive B ayes T ex t C lassificati on A lgo rithmZHANG Y u -fang ,CHEN J i an -m i n ,X I ONG Zhong -yan

18、g(Computer A cadem ic ,Chongqing U niversity ,Chongqing 400030,Ch ina Abstract :T here is an “independence hypo thesis ”in B ayesian classifier m ethod :exam p les of the em er 2gence of each attribu te are indep enden t from the exam p les of o ther attribu tes appear ,the p ractical app li 2cati on of such conditi on s are no t easily satisfied becau se the special versi on of the related characters m ay have new m ean ing in a special tex t .T herefo re ,w h ile train ing the