结合中文分词的贝叶斯文本分类/showarticle.aspx?id=247来源:[] 作者:[] 日期:[2009-7-27]魏晓宁1,2,朱巧明1,梁惺彦2(1.苏州大学,江苏苏州215021;2.南通大学,江苏南通226007)摘要:文本分类是组织大规模文档数据的基础和核心。
朴素贝叶斯文本分类方法是种简单且有效的文本分类算法,但是属性间强独立性的假设在现实中并不成立,借鉴概率论中的多项式模型,结合中文分词过程,引入特征词条权重,给出了改进Bayes方法。
并由实验验证和应用本方法,文本分类的效率得到了提高。
1. Using Bayesian in Text Classification withParticiple-methodWEI Xiao-ning1,2,ZHU Qiao-ming1,LIANG Xing-yan2(1.Suzhou University,Suzhou 215006,China;2.Nantong University,Nantong 226007,China)Abstract:Text classification is the base and core of processing large amount of documentdata.Native Bayes text classifier is a simple and effective text classification method.Text classification is the key technology in organizing and processing large amount of document data.The practical Bayes algorithm is an useful technique which has an assumption of strong independence of different properties.Based on the polynomial model,a way in feature abstraction consideringword-weight and participle-method is introduced. At last the experiments show that efficiency of text classification is improved.1.0引言文档分类是组织大规模文档数据的基础和核心,利用计算机进行自动文档分类是自然语言处理和人工智能领域中一项具有重要应用价值的课题。
现有的分类方法主要是基于统计理论和机器学习方法的,比较著名的文档分类方法有Bayes、KNN、LLSF、Nnet、Boosting及SVM等。
贝叶斯分类器是基于贝叶斯学习方法的分类器,其原理虽然较简单,但是其在实际应用中很成功。
贝叶斯模型中的朴素贝叶斯算法有一个很重要的假设,就是属性间的条件独立[1][2],而现实中属性之间这种独立性很难存在。
因此,本文提出了一种改进型的基于朴素贝叶斯网络的分类方法,针对于文本特征,结合信息增益于文本分类过程,实验表明文本分类的准确率在一定程度上有所提高。
1中文分词与特征提取中文文本分类与西方语种文本分类的主要区别在于文本特征生成模块。
对于西文语种,如果以词为特征,则文本无需复杂的分词算法,因为词之间有空格分隔,只需要对不同单词进行词干提取。
对于中文文本,由于词的形成依赖于语气语义,利用简单分词提取特征在效率和效果上都存在较大的缺陷。
常用的汉语分词算法有:第一种基于词典(Dictionary-Based)的机械匹配算法,如正向匹配、逆向匹配、最小匹配算法等,[3]这类算法的优点是易与实现。
但由于词典是在分词之前准备的,其规模和内容受到了限制;虽然可以通过加入构词规则的方法识别出一些可构造新词,但是基于词典的这一类算法无法解决文本中大量出现的未登陆词的问题,故分词的效果有其不可避免的缺陷。
第二种基于统计的分词方法,如N-Gram算法,HMM算法,最大熵算法,基于EM的算法等等。
利用统计方法可以从已有的大量实例中进行归纳总结,分析语言内在的关联信息,从而建立适用的统计模型。
对统计的方法来说,训练语料库的规模直接影响分词的效果:训练集规模小,则模型的可信度低,分词效果差;训练集规模大,则会导致数据稀疏的问题,高维数据的处理会使得分词的效率大大降低。
第三种较为理想的分词算法是将统计的方法与词典的方法进行结合。
本文基于此方法实现分词,并为后期处理提供特征。
其基本过程包括:(1)利用已有特征库建立词典;(2)利用词典匹配对语料进行提取词串X1={x1,x2,…x i};(3)以词典提取得到的词串X1对语料进行分隔,得到Y={y1,y2,…};(4)统计Y中的重复串X2;(5)以得到的重复串更新特征库X=X1+X2,(X1:词典中提取的词串;X2:语料分隔后的重复串)由此,我们得到后期文本分类的特征,即对第i个文本样本S i,其对应特征向量为:x!ti=(x1i,x2i,……,x mi),同时可得各特征在该文本中出现的频率。
其优点体现在:(1)利用词典匹配可以提高分词的效率;(2)可以消除部分助词和停用词对后期处理的影响,充分发掘文档所提供的信息;(3)有助于为产生的结果提供易用的标签。
2信息增益与特征选择构成文本的词汇数量是相当大的,因此,表示文本的向量空间也会很大,考虑进行降维是必要的。
事实上,一些通用的类别都普遍存在的词汇对分类的贡献较小;在某一类中出现概率大而在其它类中出现概率小的词汇对文本分类的贡献大。
为了提高分类精度,考虑到分类预期是实现二分,本文引入信息增益,筛选出针对该类的特征项集合。
信息增益[4][5]用于度量给定的属性对于训练样本的区分能力。
在文本分类过程中,通过计算信息增益可以得到那些在正例样本中出现频率高而在反例样本中出现频率低的特征,以及那些在反例样本中出现频率高而在正例样本中出现频率低的特征。
其定义如下:IG(x)表示词条x为整个分类所提供的信息量。
式中,P(x)表示词条x在文本S中出现的概率,P(x")表示词条x不在文本S中出现的概率,P(c i|x)表示包含词条x的文本(正例样本)属于c i类的概率,P(c i|x")表示不包含词条x的文本(反例样本)属于c i类的概率。
在实际情况中,P(c i|x)、P(ci|x")的概率是不稳定的。
为了大致估计出P(c i|x)、P(c i|x")的值,只能假设特征向量中的各个特征项x#ti=(x1i,x2i,……,x mi)之间是相互独立的,即某一特征单词在邮件中出现的事件独立于另一个特征单词在邮件中出现的事件。
该假设条件正好吻合朴素贝叶斯分类的前提假设条件。
在分类过程中,我们从训练集中选择信息增益值最高的前若干个词作为模型的特征。
3贝叶斯分类器设计在文本分类中,贝叶斯分类器实际上就是根据给定的数据样本和相关参数信息求取后验概率。
就朴素贝叶斯方法而言,以k类训练样本集为例,记C={c1,c2,…c k},则每个类C i的先验概率P(C i)可由该类样本数除以训练样本总数n得到。
对于新样本d,设其归属于C i的条件概率为P(d|ci),则其后验概率P(c i|d)可由贝叶斯公式计得:P(c i|d)=P(d|c i)*P(c i)/P(d);由于P(d)对于所有类均为常数,上式变换为P(c i|d)=P(d|c i)*P(c i)。
在本文中,考虑利用朴素贝叶斯方法实现二分分类,采用两种类型的测度,构成二维文本空间,将文本映射为二维空间中的一个点,将分类算法看作是在一个二维空间中寻找一条分割直线,根据文本点到这条分割直线的距离来判断文本为何种类型。
给定二值文本向量d=(W1,W2,W3,…,W D),W i=0或1,如果第i个特征出现在文本中,W i=1,否则W i=0。
令Pki=P(Wk=1/Ci),P(·)表示求事件发生的概率,Pki表示第k个特征出现在文本中,属于类型Ci的概率。
朴素贝叶斯分类的判别函数可表示为:Mol只与所采用的训练样本集有关,不随文本d的变化而变化,D为常数。
X表示根据特征估算出来的文本d属于类型c1的偏测度;Y表示根据特征估算出来的文本d属于类型c2的偏测度,则公式1.1可改写成:(fd)=X-Y+Mol （1.5）公式1.5表示将两类朴素贝叶斯分类看作是在由X、Y构成的二维空间中寻找一条分割直线(fd)=0,这样,可利用公式1.3、1.4,将文本表示为二维空间中的一个点(x,y),该点到分割直线(fd)=0的距离Dist可表示为:Dist=sin45°(X-Y+Mol) （1.6）当Dist≥0时,表示文本d属于类型C1;当Dist<0时,表示文本d属于类型C2。
4实验方案及结果分析根据上述的方法实现分类,建立分类模型如下:本文实验以邮件作为分类对象,采用的训练和测试样本来自于本研究小组收集的实际中文邮件,总邮件数3800封。
640封构成属于类型C1(垃圾邮件)的文本集,3160封构成属于类型C2(合法邮件)的文本集。
两类数据集中的文本数目比例设为1:6,将属于类型C1和属于类型C2的文本集均分为四份,设:C1(A、B、C、D)和C2(A、B、C、D),取两种类型对应位置上其中的三份作为训练集,另外一份作为测试集,按四栏进行交叉验证,以四次实验的平均值作为最终的性能指标,这样避免了实验的随机性和偶然性。
在处理前去除附件,剥离html标示,解析出邮件的标题以及邮件正文。
采用本文提出的统计与词典相结合的方法对邮件标题和正文分词;特定好训练集后,采用信息增益的方法来获取特征词。
利用信息增益公式将所有词条的增益值计算出,并按降序将其排列,选取排在前面的词条做实验测试。
选取词条个数多少的确定,可经多次实验比较来设置这个IG的截断阈值。
特征集的规模最终通过分类算法的性能随特征数目的变化曲线来确定。
4.1特征数目对分类性能的影响在评价二分分类性能上,利用常用的准确率、召回率进行分析:准确率(Precision):P=(正确分为某类的文本数)(/测试集中分为该类文本总数);召回率(Recall):R=(正确分为某类的文本数)/(测试集中属于该类文本总数);F1测试值:F1=(准确率*召回率*2)(/准确率+召回率)本文首先以前500个特征项作为特征集,对测试集中的邮件进行测试,然后再将特征项增加100个,重复这样的测试,直到特征项增至2400个为止。
通过20次分类测试,取信息增益值最高的前若干个词作为模型的特征。