文本分类中的特征提取和分类算法综述

文本分类中的特征提取和分类算法综述摘要：文本分类是信息检索和过滤过程中的一项关键技术，其任务是对未知类别的文档进行自动处理，判别它们所属于的预定义类别集合中的类别。本文主要对文本分类中所涉及的特征选择和分类算法进行了论述，并通过实验的方法进行了深入的研究。采用kNN和NaiveBayes分类算法对已有的经典征选择方法的性能作了测试，并将分类结果进行对比，使用查全率、查准率、F1值等多项评估指标对实验结果进行综合性评价分析.最终，揭示特征选择方法的选择对分类速度及分类精度的影响。关键字：文本分类特征选择分类算法AReviewForFeatureSelectionAndClassificationAlgorithmInTextCategorizationAbstract：Textcategorizationisakeytechnologyintheprocessofinformationretrievalandfiltering,whosetaskistoprocessautomaticallytheunknowncategoriesofdocumentsanddistinguishthelabelstheybelongtointhesetofpredefinedcategories.Thispapermainlydiscussthefeatureselectionandclassificationalgorithmintextcategorization,andmakedeepresearchviaexperiment.kNNandNativeBayesclassificationalgorithmhavebeeappliedtotesttheperformanceofclassicalfeaturedetectionmethods,andtheclassificationresultsbasedonclassicalfeaturedetectionmethodshavebeenmadeacomparison.Theresultshavebeenmadeacomprehensiveevaluationanalysisbyassessmentindicators,suchasprecision,recall,F1.Intheend,theinfluencefeatureselectionmethodshavemadeonclassificationspeedandaccuracyhavebeenrevealed.Keywords:TextcategorizationFeatureselectionClassificationalgorithm

前言互联网技术的高速发展引起了信息量的爆炸式增长，面对庞大的数据信息，如何在大规模的文本异构信息中准确、快速、全面地查找到个人所需的特定信息，已经成为了一项具有非常重要意义的研究课题［1］。文本分类的主要功能就是对相关的文档集合进行类别的标签与分配，其主要依据是在文本训练过程中将那些已经被提前分配合理的作为类别标签的训练文档集和。作为自动信息管理的核心技术，人工智能与信息检索技术是文本自动分类的两大技术基础，在组织和管理海量文本信息技术领域中文本分类是一种非常有效的技术手段［1］。所以，对文本自动分类技术的深入研究有着非常重要的理论意义与实用价值。目前通常采用向量空间模型来描述文本向量⑵。然而，面对高维的文本特征，如果不进行降维处理，则会造成“维度灾难”，从而大大影响分类效果。特征降维是文本分类过程中的一个重要环节。特征提取和特征抽取是特征降维技术的两大类，相对于特征抽取方法，特征提取方法因其快速、简单、便捷的优点，在文本分类领域中得到广泛的应用。选择合适的文本表示模型、特征降维方法和分类器算法对文本分类的速度和精度有着至关重要的影响。本文主要采用NewsGroups语料库中的20news-18828数据源，使用kNN和NativeBayes分类算法对验证几种已有的经典特征选择方法，并将其分类结果进行比较，揭示特征提取算法对分类性能的影响。1、几种经典的特征提取方法1.1文档频率(DF)文档频率是指在训练文档集中某词条出现过的文档总数［3］。文档频率特征提取方法的基本思想是：首先根据具体情况设定最小和最大的文档频率阈值，接着计算每个特征词的文档频率。如果该特征词的文档频率大于已设定的最大文档频率阈值或小于最小的文档频率阈值，则删除该特征词，否则保留。一一，、nDF()=节(式1-1)其中，n^表示词条t在文档中出现的次数，N表示文本的总词汇数。DF是一种最简单的词约简技术，常用于大规模的语料特征选择中。但其缺点是如果某一稀有词条主要出现在某类训练集中，能够很好地反应该类别的特征，但因低于某个设定的阈值而直接滤除掉，因此就可能影响文本分类器的分类精度。1.2信息增益(IG)在文本分类系统中信息增益算法通过统计某一个特征词t在文本类别中是否出现的文档频数来该算法考虑了特征t在文档中出现前后的信息熵之差-p(C11)logp(C11)计算该特征项W于文本类别c-的信息增益。公式定义O=iLmp(C)logP(C)+该算法考虑了特征t在文档中出现前后的信息熵之差-p(C11)logp(C11)+p(t)S-p(C11+p(t)S-p(C11)logp(C11)(式1-2)其中，m表示语料库中文档类别总数；P(C)表示C类文档在语料库中出现的概率；p(t)表示包含特征t的文档的概率；p(t)表示不包含特征t的文档的概率；p(C.|t)表示包含特征t的文档属于类别C.的概率；P(C)f)表示包含特征t的文档不属于类别C的概率。信息增益法的缺点是，它考虑了特征未发生的情况，尽管特征不出现的情况也可能对文本分类的判别有积极作用，但这种积极作用往往要远小于考虑这种情况时对文本分类带来的干扰。1.3互信息(MI)互信息衡量的是某个特征词和特征类别之间的统计相关性。因此，某个特征词t和某个文本类别匕互信息定义度量两个给定对象之间的相关性，在不良信息过滤问题中用以度量特征项对于文本主题的区觥t°C特征回^和类别珞散互信息公式定义如下［4］:"()"(「(式1-3)TOC\o"1-5"\h\z其中，m为类别数；p(^)表示类别C的概率；p(t,C)表示包含特征t且属于类别C的概率；p(t)表示特征t的概率；pC表示属于类'别C的概率。' '互信息值较高的特征词通常在某个类别匕中出现的概率高，而在其他文本类别中出现的概率低，也就更有可能被选作为文本类别c的特征。在m个类别的文本训练集上特征项t的互信息值公式定义如下［5］： ZMI=p(ci)^mMI(t,c「 (式1-4)i=11.4X2统计(CHI)X2统计用来衡量特征词条t和类别C之间的统计相关性。假设特征t和类别C之间是符合一阶自由度的X2分布，则特征词的对于类cB的X2统计公式定义如下⑹： 'X2(t，以-(♦+C)*(B+D)*(A+B)*(C+D)(式1-5)其中，A表示属于C类且包含t的文档频数，B表示不属于C类但是包含t的文档频数，C表示属于C类但是不包含t的文档频数，D表示不属于C类且不包含t的文档频数。对于多类问题，分别计算t对于每个类别的卡方统计值，再用下面两种公式计算特征t对于整个样本的卡方统计值，分别进行检验：x2(t)=maxwx2(t,c) (式1-6)xHt)=£p(C)x2(t,C)a^vg i ii=1(式1-7)其中，n为类别数，从原始特征空间中移除低于特定阈值的特征，保留高于该阈值的特征作为文档表示的特征。当特征词t与文本类别,相互独立时，X2(t,C「=0，此时特征t不含有任何与文本类别七有关的鉴别信息。反之，X2(t,ci)的值越大，t与c的统计相关性越强。但是通过X2统计的公式可看出，

该方法对低文档频率的特征项不靠谱，因其提高了在指定文本类别中出现的频率较低但却大量存在于其他类别的特征项在该文本类别中的权值。N1.5TF-IDF词汇频率：IDF=log其中)N表示文本的总词汇数，N^表示词w在文本中出现的次数，TFN表示包含词W的文档数，N表示包含词W的文档数，D表示语料库中的总文档数逆文档频竟：,d)=TF(t,d)其0中’目，IDF值越大'，该词与文档的相关性越低ATFIDF（t,d）针对（式1-TFIDF（t,d）针对:/TFIDF（t,d）2V ij*i=1（式1-9）2、文本分类方法文本分类方法主要分为两大类：基于规则的分类方法和基于统计的分类方法。其中基于规则的分类方法包括：决策树、关联规则和粗糙集等；基于统计的分类方法包括：K-最近邻算法、朴素贝叶斯、支持向量机等算法。由于后者具有实现简单、分类性能良好的优点，故而在文本自动分类领域中应用广泛。2.1K-最近邻算法K-最近邻算法(kNN)，是一种基于向量空间模型的类比学习方法。因其简单、稳定、有效的特点，被广泛应用于模式识别系统中。在计算文本相似度时，通常采用冤毒夹角余弦来度量。在空间模型中，通过计算两个文本向量使用kNN在计算文本相似度时，通常采用冤毒夹角余弦来度量。在空间模型中，通过计算两个文本向量之间夹角%j的余弦值)本表示两个文档滴和d；・之间的文本相似度，计算公式如下：" ，(XW2)*(XW2)\ ik jk（式2-1）TOC\o"1-5"\h\z'k=1 k=1（式2-1）其中，w^表示第i个文档的第k个属性值。当两个文本越相似时，sim(dj,dj)的值越大。通过上述计算公式，从预先确定好类别的文档集合中选取前K个与待分类文档最接近的样本。对于待分类样本的K个近邻样本，依次计算对每个类别的权重，计算公式如下：_ —> —>p(X,c)=zsim(x,d)y(d,c) (式2-2)\o"CurrentDocument"j iij—*djekNN

—►其中，顶表示待分类文档的特征向量，y(d,c.)则表示文本类别属性函数，若文档d属于类c，Ij I J则该函数值为1，否则为0.在文本分类中，K-最近邻算法的主要过程是：在文本的训练阶段，将文本训练集文档分别表示成机器可识别操作的特征向量的形式；在文本分类阶段，主要进行文本的相似度计算和权重值排序。在分类中，K-最近邻算法的时间复杂度与文本训练集合的文档总数成正比，该算法的时间复杂度较高，更适用于文本训练集合规模较小的文本分类系统。2.2朴素贝叶斯算法朴素贝叶斯算法［7］可应用到大规模文本集合中，具有方法简单、速度快、分类准确率高等优点。理论上，由于朴素贝叶斯算法所基于的假设太过于严格，故而其分类效果要普遍优于其他分类算法，但是在实际应用中并不能完全符合理论中的假设条件，则算法的准确率会有一定程度的下降。在类别数目较多或者类别之间相关性较小的情况下，该模型的分类性能才能达到最佳。假设训练集中存在j个类别，类别集合表示为 C={c,c,...c}，文本特征词集合表示为TOC\o"1-5"\h\z1 2jT={t,t，…,t}，各个文本特征对给定文本类别的影响是相互独立的。那么，类别c的先验概率为：1 2j ip(c)=普，i=1,2,3,...,j (式2-3)其中，N表示属于［类别的文本数目，N表示训练集的文本总数。设八表示文本特征集合中的第j个特征词，p(t］ci)表示特征词t.在所有属于类别七的文档集中出现的概率。则未知类别文本d属于文本类别c的条件概率p(d|cJ为： '(式2-4)(式2-5)p(dlc)=p((t,t,...,t)1c)=rip(tlc)(式2-4)(式2-5)1 12j‘ i=1 j'根据贝叶斯定理，文本类别七的后验概率p(c\d)为：p(c|d)=四"'1 p(d)p(d)=寸p(c「p(d|c) (式2-6)i=1其中，p(d)表示d文本中所有特征词在整个文本集合中出现的概率，为常数。因此，上式简化为：p(cild)=p(d|ci)p(c.) (式2-7)结合式2-4和2-7，可得p(cJd)=p(c，)rip(［匕) (式2-8)利用式2-8计算出的每个类别对于文档d的后验概率值，然后将文档d判定到概率值最大的那个文本类别中去。2.3支持向量机(SVM)支持向量机SVM算法是一种基于统计学理论的机器学习方法。该理论的基本思想是在准确性和机器容量之间，对于给定的具有有限数量训练文本集的学习任务进行折衷，以期望得到最佳的应用性能⑻。该算法依据结构风险最小化的原则，合理地选择特征集合以及文本类别的判定函数，以保证通过有限实验条件下所得到的性能良好的文本分类器在对实际的分类中效果仍然良好，最终得到一个分类性能优异并具有广泛应用性的学习机［9］。SVM算法是依据线性且可分情况下的最优分类平面提出的，如图所示：图1：SVM中的分类平面如图1所示，样本集合能够被平面H完全区分开，同时使直线H1、H2间的距离最大。其中，H1、H2是指在样本集合中平行于H并且过离H最近的点的直线。支持向量机的基本思想是：首先将样本输入空间，通过某种非线性变换（通过定义适当的积实现）转换到高维空间中去，并且在高维空间线性可分的情况下通过计算得到文本最优分类平面［10］。通常，一个分类面只能对两个类别进行划分，而对于多类别的文本分类问题，就需要构造多个超平面，将每一类别和其它的类别区分开来。同时，稀疏、高维的数据对SVM算法基本没影响，因此能够更好地体现文本数据的类别特征，相对于其它分类算法，SVM算法的文本分类准确率较高。大量实验结果表明，支持向量机的文本分类效果明显优于其它的文本分类算法［11］。3、分类系统实现与结果分析3.1文本分类系统的整体设计本文使用Newsgroups18828数据源和java软件设计平台做分类分类实验，实现了文本训练与测试前的文本预处理等相关工作，通过利用java软件编程，生成了朴素贝叶斯分类器和KNN分类器。在面对大规模的文本数据时，文本预处理后所得到的特征项数量巨大，给分类器的处理工作打来很大困难，因此需通过特征降维（即加入特征降维模块）来降低分类器的处理的复杂度。整个系统分为四个模块：文本预处理模块、特征降维模块、分类模块及测试评估模块，系统框架如图2所示。具体的处理流程如下：（1） 将语料库中的文本进行预处理（去停顿词、虚词等处理）后，形成原始特征集和；（2） 在文本预处理模块处理的结果的基础上，循环读取每个特征词条，获得其相关的词频以及文档频率等信息。然后统计特征提取方法所需要的参数，利用特征提取方法进行计算，选出预定数目的最能代表各个类别特征的最优特征集和，经过权重计算，区别每个特征词条所代表的文本类别信息大小并存储；

把文档表示为文本特征向量的表示形式，经过分类模块处理过程得到最终的文本分类结果；最后通过测试评估模块，对文本分类结果进行分析与比较，验证采用不同的特征提取方法进行特征降维，对分类结果的影响。图2：文本分类实验系统框图3.2系统功能模块设计3.2.1文本预处理模块文本预处理模块主要是利用分词词典对语篇容进行词的划分，并去除标点符号、各类虚词、停顿词等，得到一个词的列表文件。详细的处理过程参照文档预处理类DataPreProcess.java。具体步骤如下：英文词法分析，去除数字、连字符、标点符号、特殊字符，所有大写字母转换成小写，可以用正则表达式Stringres[]=line.split("「a-zA-Z]")；去停用词，过滤对分类无价值的词；词根还原stemming,基于Porter算法3.2-2特征降维模块文本预处理将语料库中出现的绝大部分词条作为文档的特征项，形成特征向量空间，致使原始特征空间的维数非常大，势必会增加机器学习的时间和空间的复杂度。因此，需通过特征降维实现对原始特征集的空间降维处理，以便提高文本分类系统的工作效率。该模块将原始特征集合中的特征词条按照特征提取方法进行计算评价，最后选出前N个（预定数目）个权重值最大的特征词构成特征集合。在提取特征词时，首先统计所有文档中出现不重复的单词的数目，通过两种策略选取特征词。策略一：可保留所有词作为特征词；策略二：选取出现次数大于等于4次的词作为特征词。统计结果如下：出现次数大于等于1次的词有87554个出现次数大于等于2次的词有49352个出现次数大于等于3次的词有36456个出现次数大于等于4次的词有30095个保留所有词作为特征词共计87554个选取出现次数大于等于4次的词作为特征词共计30095个3.2.3文本分类模块（1） 朴素贝叶斯分类器朴素贝叶斯分类器有两种模型：1） 多项式模型（以单词为粒度）类条件概率P（tk|c）=（类c下单词tk在各个文档中出现过的次数之和+1）/（类c下单词总数+训练样本中不重复特征词总数）先验概率P（c）=类c下的单词总数/整个训练样本的单词总数2） 伯努利模型（以文件为粒度）类条件概率P（tk|c）=（类c下包含单词4的文件数+1）/（类c下单词总数+2）先验概率P（c）=类c下文件总数/整个训练样本的文件总数由于多项式模型分类准确率较高，故本文的朴素贝叶斯分类器采用多项式模型。（2） KNN分类器KNN算法描述：1） 文本向量化表示，由特征词的TF*IDF值计算；2） 在新文本到达后，根据特征词确定新文本的向量；3） 在训练文本集中选出与新文'本最相似的k个文本相似度用向量夹角余弦度量计算公式为：二W*Wsim（d,d）=cosa一 卜i =- ：（XW2）*（XW2）ik jk'k=1 k=1一般采用先设定一个初始k值，然后根据实验测试结果调整k值，本文中取k=20。在新文本的K个邻居中，依次计算每类的权重，每类的权重等于K个邻居中属于该类的训练样本与测试样本的相似度之和；比较类的权重，将文本分到权重最大的那个类别中。3.2.4测试评估模块朴素贝叶斯算法实现在java编程实现中，包含两大类：贝叶斯算法类(NaiveBayesianClassifier.java)与测试集与训练集创建类(CreateTrainAndTestSample.java)。其中，分类器主类如图3所示NaiveBayesianClassifier.javaE)--KSj.NuibycciuJZla.EEi£iArC?no.itlt.String[]):vmid■:omput4Acaiji-acyCStrirag,Striiig):doutlecompi.Lt^Cat.ePrpb,Vector:-SIriFl^p任 Iloulild^doabl,MaptriIlcrnbl己>：l:Blglkairn^lMcomputerDonfusiorJila.trix(Map<5triile,3tring>,MapStriHg,3trirLg».void日doFroceEs(StringString.,String): d日getCateWordsNwi(5triragj:MapString.Hcnjble&getCateWcirdsFrijb(Stringl:Map:Stririg,.Doablez日geHlapFrcirTiEeE-^iltFileEtring.):Map^tring,Striris?图3：朴素贝叶斯分类器主类Java代码注解：计算概率用到了BigDecimal类实现任意精度计算；用交叉验证法做十次分类实验，对准确率取平均值；根据正确类目文件和分类结果文计算混淆矩阵并且输出；Map<String,Double>cateWordsProbkey为"类目_单词”,value为该类目下该单词的出现次数，避免重复计算。朴素贝叶斯分类器分类结果(混淆矩阵)如图4所示：D1 2 3 4r6 7 3 91D11 12ID1ijI：16 17JB19n61 n0 h j (i n0 o hn1 e o h 盟 1 a 0 o 时竣1 D 85 0 0 3 9 0 0 0 0 D D £ Z 1 3 D 1 £ 0 0.8^^(93877551D 1S3 2 3 19 0 0 0 3 1 9 E0 0 3 D (1 0 0 0.09(5(86868686860c U HU 1 f U « U H U i! U U H d 1 U k H 土地；:岳理1约州J-D3i?5?[；(l000D93223D(]f0 0.G14^^33333333^1TOC\o"1-5"\h\zE (1 g 0 H j 芯 11 0 0 H (1 A E 0 1 j (1 R E 。 f?fU3033A53口0H0DA023U1E0 ^.巧？1药8571曜8571? D £ 2 0 3 D 0 f 0 0 D 1 (1 0 J 3 J- 9 6 0 0.0u k u u j u u k u u u u u u u j k k u u.uD E 0 0 3 D 0 E 0 0 D Q 0 J a 1 1 f 0 0.0111n£qH3n(Iq016(I£0Hjn(1q1.011D90eaDI000D9990eaDI001.012D§1a32s0o0D196&29DDD003-673^939775518213Utaflduaau0UUk(5flduAau0』5蛎59典59595财UD900a2a0a@DD1092aD30aeJ3B77551KMM1?15n£q0jnaqo0liHce0K13qo土吓眄眄将判616D90eaDI000D2900a872000J5fi^39560^3956117DD003Ds0o0DD0003DOil0o1.618Utaflduaau0UUk«2152tuo.e19590aDa0aDD912181A40193.3®158735873M57TltduuurduufJ-Ndiut!Ody^iciiCLdbi.fierii6thExpii:0.8仙叫肖欢4出19卜图4:贝叶斯分类法分类结果的混淆矩阵表示(2)KNN算法实现在java编程实现中，包含两大类：文档向量计算类(ComputeWordsVector.java)和KNN算法实现类(KNNClassifier.java)。分别如图5和图6所示：-JComiuteVcircEVecto]'.java-ComputeYorcsVe:torrrainCStrin^ri:void3computelllF(String,SortedilapC-String,Double.>.):Sor11idJilaptring.,I)oulile>9computelFMultilDFGtrire,duuble,int.,SortedNap:Strang,Du^ble);,2ortedMap<String,DciubleQ:vold§c-：njTLllililords(Etririg,Eor+.e-I1!!ipCEtri .3〕 :Sortc-iMop-^StriDnull旦〉■pririlVordM：浊(S>n-tmdM迎<String：.,DoubLe>J:void图5:文档向量计算类Java代码注解：计算IDF非常耗时，3万多个词的属性词典初步估计需要25个小时；可以先尝试所有词的IDF都设成1的情况。-JjKNBClaEEifier.java|§••粉KBBlClaEsifier0政ByYalueComparator-■.conputsSlm(MapCString,Duiiljle},Map(String,Double.).):doulile—-jjllol'rE'Csee(String,String.,String.]:doubleDJ][CDnijiuteCate(String,Map<5tring,Houble>,Map<Etring,TreeFJap<String,Doable>>,Filetfriter.):Siring图6:KNN分类器主类Java代码注解：1） 用TreeMap<String,TreeMap<String,Double>>保存测试集和训练集；2） 注意要以"类目_文件名"作为每个文件的key，才能避免同名不同容的文件出现；3） 注意设置JM参数，否则会出现JAVAheap溢出错误；4） 本程序用向量夹角余弦计算相似度。KNN算法的分类结果（混淆矩阵）如图7所示：□1 23 4561二9ID1112i：16n】二19a62a:1:a:a:a:a:a:q::110.756097560975609611时D35gDaDaDa2£DaD1D1D-7ma58B235£g^llZD7Bl17:1-D1D-41D-1aD-Du7O^3^?E；Z6OSfi9566:]:11IS11aB01a：l052：l1：la：l10.609073394:495^11264D1■672■DaDi111■DaD■D.afl722S915i5626.5065D591Lis1-DaD-:11-DaD-D.T15510GDq：DSlfi326G:1jLLi21aD11211DaDa10r0r0r011r0r1r0r0r0r0.7777777777777773aDL-LDL-L:L-LDL-LDL-LLuD9:aDL:aDL:::DL:aDL:aDLL・[i10001z00:00.5971■la■|0■Ia■|0D.日我 日11DiDDiDDaD-ajaJa1a口泠心549皿迎的S12Da131is1DaDa7D210：la：i00.613953IBB：]7209313:i00000002001说■|a■Ia■|10.926067-^1614DaD-1aD-DaDiDi91aJija0.957354736842105215B1DaDaDaD11aD2D391a：i•JD.0165137611：1601000i0i10201110ra■a0-601301601001301517DiD-1a1-DaDi11D日9jD.3913:a:a:a:a:a:a:a:a:a:alB013i100i00000001z000390-7037037037037037TheflEcarocvforEMMClassifierinbthExpis:0.62099162910^9582图7:KNN分类器的分类结果表示3.3实验结果分析（1） 贝叶斯分类结果与分析由不同的特征提取策略，可得贝叶斯分类器结果如下：方法一：取所有词作为特征词，共87554个。做10次交叉验证实验，平均准确率78.19%，用时23min，第6次实验准确率超过80%；方法二：取出现次数大于等于4次的词作为特征词，共计30095个。做10次交叉验证实验，平均准确率77.91%，用时22min，第6次实验准确率超过80%。结论：朴素贝叶斯算法不必去除出现次数很低的词，因为出现次数很低的词的IDF比较大，去除后分类准确率下降，而计算时间并没有显著减少。（2） KNN分类结果与分析由于KNN分类算法的复杂度较高，若选取所有词作为特征词进行分类实验，则所需时间较长，为了适当提高分类效率，考虑提取出现次数不小于4次的词作为特征词，分类结果如下：取出现次数大于等于4次的词共计30095个作为特征词：10次交叉验证实验平均准确率78.19%，用时1h55min，其中有3次实验准确率超过80%。（3） 两种分类算法的性能比较在相同的硬件