05 基于类别概念的特征选择方法 王琳

基于类别概念的特征选择方法王琳1，陈伟萍2，封化民3，方勇1，3,杨鼎才2(1.北京邮电大学电信工程学院，北京100876；2.燕山大学，秦皇岛066004；3.北京电子科技学院信息安全与保密重点实验室，北京100070)摘要：本文基于中文文本分类的定义及其向量空间模型，分析了向量空间模型正确分类的关键所在。通过对传统的特征选择方法及其存在的问题的分析，提出了基于类别概念的特征选择方法。通过支撑向量机对中等规模语料库的实验，验证了此方法的有效性。关键词：文本分类；向量空间模型；知网；类别概念。FeatureSelectionMethodBasedonCategoryConceptLinWang1,WeipingChen2,HuaminFeng3,YongFang1,3,DingcaiYang(1.SchoolofTelecommunicationEngineering,BeijingUniversityofPostandTelecommunications,Beijing100876China;2.SchoolofInformationEngineering,YanShanUniversity,Qinhuangdao066004China;3.KeyLaboratoryforSecurityandSecrecyofInformation,BeijingElectronicScienceandTechnologyInstitute,Beijing100070China)Abstract:BasedonthedefinitionoftextcategorizationandVSM(VectorSpaceModel),thispaperanalyzesthekeypointsofcorrectlycategorizingtexts.Afteranalyzingtheconventionalfeatureselectionmethods,anewfeatureselectionmethodwasproposed.ByusingSupportVectorMachine,experimentresultonamid-sizecorpusshowedtheeffectivenessofthemethod.keywords:TextCategorization;VSMmodel;HowNet;CategoryConcept.基金资助：国家自然科学基金资助项目（项目编号：60472082）作者简介：王琳（1981-）,女，山东，硕士研究生.emaiiainerhy引言网络技术的发展和Internet的开放性使它逐步成为一个全方位的资源宝库，但其复杂的结构使人们很难从中准确找到需要的信息。文本分类是信息检索中的重要课题。传统的文本分类是基于人工方式的，如过去Yahoo的做法就是将网页放在一个巨大的层次分类结构中，通过人工组装维护这些类别，达到帮助人们方便快速查找信息的目的。这种方式缺点很多，如周期长、费用高、效率低、需要大量专业人员以及分类结果的一致性低等。20世纪90年代以后，基于机器学习的文本自动分类方法越来越成为主流。通过学习的方式使分类器获得分类知识，直至具备判别新文本所属类别的能力。相比于人工方式它具有周期短，效率高，节省人力资源，分类结果一致性高等优点。但作为自然语言处理、人工智能、模式识别等多领域的交叉学科，它受到多方面的限制，分类准确率一直不能达到令人满意的效果。在Internet信息急剧膨胀的今天，为文本分类提供了广阔的发展空间，文本自动分类面临前所未有的机遇和挑战，如何提高分类准确率成为研究热点本文从文本分类的基本问题出发，分析了文本分类的基本模型、特征选择等内容。全文结构安排如下：第一节介绍文本分类定义及向量空间模型；第二节简要介绍了典型的传统特征选择方法；第三节是本文重点，提出了基于类别概念的特征选择方法；第四节描述了实验设计的系统框架结构；第五节给出了实验结果及其分析；最后第六节得出结论并对未来研究予以展望。1 文本分类及向量空间模型1.1 文本分类定义文本分类(TextCategorization)是指依据文本的内容，由计算机根据某种自动分类算法，把文本判分为预先定义好的类别。1.2 向量空间模型向量空间模型(VSM,VectorSpaceModel)是最常用的文本分类模型之一。它以特征项作为向量空间的坐标，将文本看作向量空间中的点。特征项可以是字、词、短语、句子等意义单位。一般取词作为特征项。即是说，集合所有的特征项确定一个特征空间，假定为n维空间V=T,T,T，每一篇文本D就可以用V的一个向量表示n12ninD=w,w,w，其中w表示T在D中的权重。其中，T为词或短语，对应ii1i2inikkik每个T，通常用w权重来表示T在文本中的出现情况，以区别其文本。kkVSM解决文本分类问题的前提有两个，一是所有特征项都正交，即T,T,T两12n两正交；二是向量D=w,w,w能够完全表征文本D。然而，自然语言中同ii1i2ini义、近义词以及词语歧义性的存在，使这两个前提往往难以满足，甚至相差甚远。这是影响VSM模型分类正确率的关键所在。2 传统特征选择方法介绍在中文文本分类中，特征项通常是这样提取的：先对语料分词，去除没有意义的特征项(如助词)，再选择一种算法，对剩余的每一个特征计算统计度量值，然后设定一个阈值，将小于阈值的特征项过滤掉，剩下的即认为是有效特征项。一般的统计度量值都取作词频的函数，比较有代表性的有文档频率(DF,DocumentFrequency)、信息增益QG,InformationGain)、互信息(MI,MutualInformation)4、CHIi、期望交叉熵2和文本证据权等。为便于描述，先对如下符号约定：f:T在第i篇文本中出现的次数；ikkf:T在所有文本中出现的次数；kkf,:T在第s类文本中出现的次数；skkn:T在第s类文本中出现的文本总数；kskn:出现T的文本总数；kkN：语料库文本总数。2.1 文档频率词条的文档频率是指训练语料中出现该词条的文档数。大量实验表明，出现频率越高的词条携带越多的分类信息。它是最基本的特征选择方法，很容易被用于大规模语料统计学习中。以词条T为例，它的归一化DF值为knDF(T)弋(1)kNDF简单实用，但它忽略了低频词的作用，高估了高频词的贡献。如果DF(T)不高，k但T集中出现于某一类，那么它就携带了丰富的类别信息，然而，有时DF选择方法可k能会将其过滤掉；反之，如果T普遍出现于很多类中，那么DF(T)会较大，而实际上,kk却对分类效果没有作用。因此，对DF选择方法应予以折衷考虑。2.2 信息增益信息增益在机器学习领域被广泛应用。对每个词条T，通过综合考虑每一类中出k现与不出现该词条的文档数来衡量该词条的信息增益。计算公式(2)所示IG(T)=-lP(C)logP(C)+P(T忆P(CIT)logP(CIT)+P(T)P(CIT)logP(CIT)ksskskskksksks=1i=1s=1(2)其中，P(C)表示任一篇文本属于第S类的概率；P(T)表示特征项T在文本集中skk出现的概率；P(正)表示除T外的特征项在文本集中出现的概率；P(CIT)表示任一kksk篇包含T的文本属于第s类的概率；P(CIT)表示任一篇不包含T的文本属于第s类的kskk概率。2.3 互信息互信息在统计语言模型中被广泛应用4。对特定的词条T和类别C，T和C之间ksks的互信息由(3)式计算AxNMI(T,C)=log(3)ks(A+C)x(A+B)词条T的互信息量度值为kMI(T)=mmaxMI(T,C)(4)kkss=1其中，A表示包含词条T且属于类别C的文档频数，B为包含词条T且不属于类ksk别C的文档频数，C为不包含词条T但属于类别C的文档频数，N表示语料库中文档sks总数，m表示分类体系中的类别数。3 基于类别概念的特征选择根据VSM分类对特征项的要求，我们提出了基于类别概念的特征选择方法。它以词语所表达的概念作为特征项，更准确地理解了文本的语义；并且不同于传统方法中完全基于词频统计确定全局意义上的特征项的方法，它在类别层次上分析确定对分类最有贡献的特征项。3.1 特征项的要求根据前文所述的VSM正确解决文本分类问题的前提，不难发现传统的特征选择方法的局限性。首先是没有一种根本的措施去降低特征项之间的相关性；其次每一种选择算法都有自己的偏好，比如DF认为出现特征项的文档频数越高，重要性越大；IG、MI等方法偏爱一些低频词，认为一部分低频词对类别区分有重要作用，不应将其去掉。总之，文本分类的向量空间模型对特征项有以下要求：(1) 特征项之间应该是正交的。这一点很难证明，我们通过削弱特征项的相关性来尽量满足正交的要求，具体做法见3.2。(2)要使文本向量D=w,w,w能在整个特征向量空间中更好地区分其类ii1i2in别，特征项应当是那些具有比较强的单类别指示意义的词语；并且，W应当能体现Tikk在整个文本集中地位的权重；即是说，特征项是类别意义上的，但权重应定位于全局意义上。这是为其他大多数文本分类算法所忽视的一点，本文的做法在3.3和3.4中有详细介绍。3.2 知网知网(英文名称为HowNet)是一个以汉语和英语的词语所代表的概念为描述对象,以揭示概念与概念之间以及概念所具有的属性之间的关系为基本内容的常识知识库。知识词典是知网的最基本的数据库。在这个文件中每一个词语的概念及其描述形成一个记录。每一种语言的每一个记录主要包含4项内容。其中每一项由两部分组成，中间以“=”分隔。每一个“=”的左侧是数据的域名，右侧是数据的值。它们排列如下：W_X=词语E_X=词语例子G_X=词语词性DEF=概念定义对文本分词后，我们得到的是一个词序列，传统文本分类中的特征空间就是这个词序列的一个子集。同义、近义词的存在使特征空间难以达到正交的要求，且维数高。为此，我们通过组织知网数据，对词语进行概念映射，即以词语所表达的概念作为特征项这不仅大大缩小了特征空间维数，而且降低了特征项之间的相关性。3.3 类别概念根据上述分析，可以选用类别概念作为特征项。定义如下：概念类别度概念T属于类别C的概念类别度记作a，a可由(5)式计算。aksnksnsksksks=P(CIT)-MaxP(CIT)skjks其中，P(CIT)表示出现特征项T，文本属于第S类的概率。根据Bayes后验概skk率公式，有P(CIT)=skP(C)：s任意一篇文本属于第s类的概率;P(Tk)Tk在文本集中出现的概率，P(Tk)k;YfjjP(TIC):T在第s类文本中出现的概率,kskP(TIC)二ksosjj另外，在实验中，我们对P(TIC)=kssjj作了一点改动，改为P(TIC)xP(C)P(T)_厂k90.5xfxfskskP(TIC)=牛余。这是因为，中文文本分类存在着向量空间维数过高的问题,ksfsjj过高的特征维数使Yf很大，而单个特征项的有限性使f比较小，这就导致f差别sjskskj较大的特征项的P(TIC)差距甚微，致使不能通过后验概率体现T的类别指示意义。ksk类别概念对-13a，那么T称作在a水平上属于C的类别概0ks0k0s念。那么，给定合理的阈值a，选出a水平上的类别概念，就可确定我们期望的特征00项。3.4特征加权为将文本表示成向量形式，选择特征项后，应该对特征项加权，即计算D=和,w,w。前文所述传统特征选择方法中计算特征统计度量值的算法都可ii1i2in以作为特征加权算法，另外还有TFIDF等特征加权方法。目的就是确定T在整个文本集k中的作用，以及它在D中的贡献，使,w,w能够合理地表征文本D。ii1i2ini从类别概念的定义可以看出，特征项出现的频率越高，它的贡献越大。这与DF的思想是一致的。4 系统框架结构系统框架结构如图1所示。图1分类模型结构图Fig1.StructureofCategorizationModel系统包括分词、概念映射、计算概念类别度、确定特征空间、文本向量表示、训练器和分类器等模块。其中，分词模块采用海量分词软件(海量分词研究版)7；概念映射模块通过重新组织知网数据，用SQL编程实现；训练器和分类器采用支撑向量机(SVM,SupportVectorMachine)算法。5 实验与结果分析我们采用复旦大学的中文文本分类语料库，其中共有艺术、计算机、经济、教育、环境、体育、医药、军事、政治和交通等10个类别。每类取200篇文本，160篇用于训练，40篇用于测试。测试方法为封闭测试。为便于比较,我们对相同的数据分别采用传统的DF方法和本文提出的方法做了实验。在DF方法中，特征选择的阈值取0.015，特征空间维数是2914；基于类别概念的特征选择中，a取0.6，特征空间维数是2305。实验结果分别见表1、表2和图2。表1：文本分类测试结果(传统DF方法)Tablel.TheTestResultofTextCategorization(DF)类别艺术计算机经济教育环境体育医药军事政治交通召回率0.90.9750.8250.8250.5750.90.80.80.8250.925准确率0.9730.8860.6230.9170.920.9470.970.80.6110.925F1值0.9350.9290.710.8680.7080.9230.8770.80.9250.925表2：文本分类测试结果(基于类别概念)Table2.TheTestResultofTextCategorization(BasedonCategoryConcept)类别艺术计算机经济教育环境体育医药军事政治交通召回率0.9750.9750.9250.90.7251.00.90.7550.9250.925准确率0.9750.9750.7551.01.00.9761.00.940.6380.974行值0.9750.9750.8230.9470.8410.9870.9470.8490.7550.949图2各类别F比较Fig2.ComparisonofF1in10Categories不难看出，基于类别概念的特征选择方法大大提高了文本分类正确率。认真分析实验数据，对同样的400篇测试文本，传统DF方法正确分类334篇，平均正确率为83.5%；而本文提出的方法正确分类361篇，平均正确率为90.25。从图2中可以看出，对每一个类别，基于类别概念的特征选择方法都优于传统DF选择方法。从图2中还可以直观看出，艺术、计算机、体育、交通的F很高，而经济、环境两类的F值较低。这是因为，属于经济、环境的类别概念在其他类别中的概念类别度也比较高，而艺术、计算机等类的类别概念在其他类中出现很少，因此能够得到较高的分类准确率。6 总结及未来研究本文针对文本自动分类中传统特征选择的缺陷，提出了基于类别概念的特征选择方法。我们通过实验，证明了本文提出的方法是有效的，无论在运算复杂度还是分类准确率上，都比传统的文本分类方法有很大提高，能够较好地筛选出携带分类信息的有效特征集，提高文本分类准确率。下一步工作中，我们将重点完善概念映射模块，结合上下文语境进行歧义分析，更准确地理解文本的语义概念。7致谢本研究得到国家自然科学基金项目编号：60472082及北京电子科技学院重点实验室基金项目项目编号：YZDJ0427的支持。参考文献：1 史忠植.知识发现M.北京：清华大学出版社，2002.2 YangYiming,PedersonJO.AComparativeStudyonFeatureSelectioninTextCategorizationA.Nashville:MaorganKaufmann,pages412-420.3 TomMitchell.MachineLearningM.McCrawHill,1996.and4 KennethWardChurchandPatricKHanks.Wordassociationnorms,mutualinformationlexicographyC.In:ProceedingsofACL27,Vancouver,Canada,1989.pages76-835 董振东，董强。知网简介，6 周茜，赵明生等。中文文本分类中的特征选择研究.北京：中文信息学报，2004.7http;/www,hylanda,com/