搜索
基于特征选择的质心向量构建方法谢华，王健，林鸿飞，杨志豪(大连理工大学计算机科学与技术学院，辽宁大连116024)摘要：基于质心的文本分类方法对模型较敏感，分类性能较差。为此，提出一种基于特征选择的类别质心向量构建方法FSCC。计算特征与类别之间的特征选择值，利用质心特征权重计算公式得到类别的质心向量，并采用非归一化的余弦相似度计算文档与质心间的距离，实现文本分类。实验结果表明，与基于质心的方法和支持向量机方法相比，FSCC方法的分类效果更好。关键词：特征选择；特征权重；余弦相似度；质心；文本分类CentroidVectorConstructionMethodBasedonFeatureSelectionXIEHua,WANGJian,LINHong-fei,YANGZhi-hao(SchoolofComputerScienceandTechnology,DalianUniversityofTechnology,Dalian116024,China)【Abstract】Textcategorizationmethodbasedoncentroidshowspoorperformance.ThispaperproposesacentroidvectorconstructionmethodbasedonfeatureselectionnamedFSCC.Bycomputingfeatureselectionvaluebetweenfeaturesandcategories,thecentroidvectorarecalculateedbytheformulaofcentroidfeatureweight.Finally,anon-normalizedcosinesimilaritymeasureisemployedtocalculatethesimilarityscorebetweenatextvectorandacentroid.ExperimentalresultshowthatFSCCsignificantlyoutperformstraditionalcentroid-basedmethodsandstate-of-the-artSupportVectorMachine(SVM).【Keywords】featureselection;featureweight;cosinesimilarity;centroid;textclassificationDOI:10.3969/j.issn.1000-3428.2012.01.062计算机工程ComputerEngineering第38卷第1期Vol.38No.12012年1月January2012·人工智能及识别技术·文章编号：1000—3428(2012)01—0195—02文献标识码：A中图分类号：TP3911概述文本分类就是将文本集中的每个文本分配到预先定义好的类别集中的某一个类别中。目前有多种分类方法，如朴素贝叶斯、K最近邻、基于质心的方法[1-3]、支持向量机(SupportVectorMachine,SVM)[4]等。其中，基于质心的方法具有简单性。但由于它对模型的敏感性，因此分类效果往往会低于其他方法，如SVM。因此，针对基于质心方法效果较差的问题，提出了许多改进方法[1-3]，它们大多是利用词项在文本集中的分布信息来构建类别的质心。为提高分类结果的精度，本文提出了一种构建类别质心向量的新方法FSCC。2基于质心的分类方法基于质心的分类方法一般包含文本的表示、质心的构建和分类等步骤。文本的表示是将文本集中的文档表示成向量空间模型的形式。质心的构建是为每个类别构建一个原型向量，即质心，作为属于该类别的所有文档的代表向量，构建类别质心的经典方法有AAC(ArithmeticalAverageCentroid)和CGC(CumuliGeometricCentroid)[1]。之后，对于每篇待分类文档，计算其文档向量与各个类别对应的质心向量的距离，与该文档距离最近的质心对应的类别即为该文档所属的类别。3基于特征选择的质心构建基于特征选择的质心构建步骤如下：(1)计算文档中的词权重。本文采用的文档特征权重计算公式是：,,lntdtdtNtfidftfn⎛⎞=×⎜⎟⎝⎠(1)其中，tft,d表示特征t在文档d中出现的次数；nt表示特征t在文档集中出现的文档数；N表示文档集中包含的文档个数。在质心构建阶段，先利用特征选择的方法得到特征与类别之间的特征选择值，然后根据特征选择值计算质心向量中特征词的权重，并由此构建出类别的质心。本文先对特征词去停用词，再采用信息增益作为特征选择法。特征t的信息增益值为不考虑任何特征的熵与考虑该特征后的熵的差值，计算公式如下：()()()()()()()()()()()111|lb|lb||lb|niiinniiiiiiIGtHCHCTPCPCPtPCtPCtPtPCtPCt====−=−+∑+∑∑(2)其中，P(Ci)表示类别Ci出现的概率；P(t)表示特征t出现的概率；P(Ci|t)表示出现特征t时类别Ci出现的概率。该方法是从信息论的角度来筛选有效特征，在采用信息增益筛选有效特征的K最近邻分类实验中取得了很好的效果[5]。(2)计算这些特征的权重，其原则是：质心特征的权重应与它对该类别的类别区分度大小呈正比，即类别区分度越大的特征，其在类别质心中的权重也应该越大[6]。由此，特征的权重值应与该特征的信息增益值FSij呈正比函数关系。本文设计了一种新的特征权重计算方法，公式如下：基金项目：国家自然科学基金资助项目(60673039,60973068)；国家“863”计划基金资助项目(2006AA01Z151)；高等学校博士学科点专项科研基金资助项目(20090041110002)作者简介：谢华(1984－)，男，硕士研究生，主研方向：文本分类；王健，副教授；林鸿飞，教授、博士、博士生导师；杨志豪，副教授、博士收稿日期：2011-05-30E-mail：wangjian@dlut.edu.cn196计算机工程2012年1月5日ijFSijwb=(3)其中，wij表示特征ti在类别cj的质心中的特征权重；FSij是计算得到的特征ti与类别cj之间的特征选择值。底数大于1的指数函数对正数值具有迅速攀升性，因此，可以在适当放大重要特征权重值的同时不太影响那些非重要特征，进而强化了类别中那些具有代表性的特征，从而构建出对该类别更具区分性的质心向量。因此，b大于1且为常量。通过式(3)，即可构建每个类别的质心向量。类别cj对应的质心如下：()12,,,jjjjΓ=CentroidL(4)(3)得到类别对应的质心后，对于每篇待分类文档，只需计算其文档向量与各个类别对应的质心向量的距离。本文采用非归一化的余弦相似度来计算两者的相似度。公式如下：()'argmaxjjC=⋅dCentroid(5)4实验结果与分析4.1实验语料及对比实验本文在20-newsgroup、Reuters-21578和BC2_IAS3种不同类型的语料上将FSCC与AAC和CFC等基于质心的方法及SVM方法进行了对比实验。对于SVMTools(SVM-Light、LibSVM)，采用线性核函数，对于多类别分类问题，采用One-Vs-Rest的方法。对SVM分类方法，通过调整阈值使其得到最好的分类效果。对于语料20-newsgroup和Reuters-21578，均采用微平均(micro-F1)和宏平均(macro-F1)作为评测指标。对于BC2-IAS语料，采用F1、precision和recall作为评测指标。4.2结果分析首先在20-newsgroup和Reuters-21578语料上比较4种分类方法的分类效果，结果如表1所示。从中可见，对于20-newsgroup语料，无论采用何种分类方法，得到的Micro-F1和Macro-F1结果都相差不大。这是由于20-newsgroup是balancedandsufficient类型的数据集，不存在大类和小类的情况，因此得到的Micro-F1的Macro-F1相差不大。在BC2-IAS语料上4种方法的分类效果如表2所示。表120-newsgroup和Reuters-21578上的分类性能比较20-newsgroupReuters-21578分类方法Micro-F1Macro-F1Micro-F1Macro-F1FSCC0.93020.92960.99300.9906AAC0.83350.83260.89250.7529CFC0.92720.92690.99530.9890SVMLight0.84720.85390.94670.8947表2BC2_IAS上的分类性能比较分类方法F1值精确率召回率FSCC0.99410.98831.0000AAC0.79410.72440.8787CFC0.99410.98831.0000SVMLight0.75940.69270.8402综合表1和表2的结果可以看出，FSCC方法的分类效果在3种语料上均好于其他方法。其次，比较了不同方法的分类结果在不同区间上的分布。图1给出了在Reuters-21578语料上F1值的分布情况。可以看到，FSCC方法得到的F1值在0.9和1.0这2个值上的类别数远多于其他方法(如AAC和SVM)。这也是FSCC方法的最终结果远好于其他方法的原因。图1Reuters-21578语料上4种方法的F1值比较表3给出了在20-newsgroup语料上进行质心向量归一化和非归一化对实验结果的影响。从中可以看出，对FSCC进行归一化之后，分类效果大幅下降。原因在于，对质心向量进行归一化后，使得质心中类别词的区分度下降甚至消失，从而导致分类结果变差。对AAC和CGC进行归一化前后的分类结果相差不大。这主要是因为，20-newsgroup是一个balancedandsufficient类型的数据集，而且归一化前后AAC和CGC得到的类别中每个特征词的权重变化不大，因此，对分类结果的影响不大。表3归一化前后对20-newsgroup语料分类结果的影响分类方法Micro-F1Macro-F1NormalizedFSCC0.83650.8373DenormalizedFSCC0.93020.9296NormalizedAAC0.83350.8326DenormalizedAAC0.83070.8312NormalizedCGC0.83350.8326DenormalizedCGC0.83050.8311AAC和CGC是根据特征词在类别中各文档的权重来计算其在类别质心中的权重，并假设当一个文件和某一特定类的相似性最大时，该文件被分配到该特定类，而当模型出现偏差时该假设是不成立的，因此，其分类效果不够理想[1]。参数b的作用是调整特征词在类别中的权重。图2显示了b的变化对20-newsgroup语料分类结果的影响。从中可看出，b=1.0时效果最差，原因是此时所有词的权重都为1，特征没有类别区分性。be－1.7时相比b=e－1.8，分类结果有显著的提升。当be－1.7并且逐渐增大时，分类的效果反而逐渐下降。当b为0~1以及b很大时，都间接降低了特征的区分度，效果反而不好。因此，当b=e－1.7时，分类效果最好。图2参数b对20-newsgroup语料分类结果的影响(下转第210页)210计算机工程2012年1月5日5实验结果与分析为评价本文所提出的基于GPU的图像校正和处理方法，本节通过实验，比较本文方法与Touchlib的触点校正方法的处理速度。在WindowsXP系统实现了本文的图像校正和处理方法，并部署了Touchlib的运行环境，系统的硬件配置为Core2DuoT93002.50GHz和2GB内存，显卡采用nVidiaQuadroNVS140M。实验中2种方法的校正网格数均为8×6；均使用柔化、背景剔除、效果缩放和阈值控制4个滤镜进行图像处理；输入均为4个触点操控的相机