一种基于PCA的组合特征提取文本分类方法

计算机应用研究ApplicationResearchofComputers收稿日期：2012-12-12基金项目：江苏省2010年度青蓝工程骨干教师资助项目（项目编号：苏教2010-16）；作者简介：李建林(1974-)，男，湖南洪江市人，副教授、高级工程师，计算机与软件学院副院长，国家示范性(骨干)院校项目重点建设专业(软件技术)项目组副组长，加拿大里贾纳大学高级访问学者，中国计算机学会会员(E200016559M)，主要研究方向：数据挖掘、软件技术、教学管理，E-mail:[e-mail]。一种基于PCA的组合特征提取文本分类方法*李建林1,2(1.南京信息职业技术学院计算机与软件学院,南京210023;2.里贾纳大学计算机科学系,里贾纳S4S0A2,加拿大)摘要：为了获得更好的文本分类准确率和更快的执行效率，研究了多种WEB文本的特征提取方法,通过对互信息(MI)、文档频率(DF)、信息增益(IG)和χ2统计（CHI）算法的研究,利用其各自的优势互补，提出一种基于主成分分析(PCA)的多重组合特征提取算法(PCA-CFEA)；首先通过PCA算法的正交变换快速的将文本特征空间降维，再通过多重组合特征提取算法在降维后的特征空间中快速的提取出更具代表性的特征项，过滤掉一些代表性较弱的特征项，最后使用SVM分类器对文本进行分类；实验结果表明PCA-CFEA算法能有效的提高文本分类的正确率和执行效率。关键词：基于PCA的组合特征提取算法(PCA-CFEA)；主成分分析；特征提取；文本分类；中国分类号：TP391文献标识码：A文章编号：AcombinationoffeatureextractionintextclassificationalgorithmbasedonPCALIJian-lin1,2(1.NanjingCollegeofInformationTechnologyDepartmentofComputer&Software,Nanjing210023,China;2.UniversityofReginaDepartmentofComputerScience,ReginaS4S0A2,Canada)Abstract:Inordertoobtainabettertextclassificationaccuracyandfasterexecutionefficiency,studyavarietyofWEBtextfeatureextractionmethod,basedonthemutualinformation(MI),documentfrequency(DF),informationgain(IG)andx2Statistics(CHI)algorithm,throughusingoftheircomplementaryadvantages,proposedacombinationsoffeatureextractionalgorithmbasedonprincipalcomponentanalysis(PCA-CFEA).First,bytheorthogonaltransformationofthePCAalgorithmtofasterdimensionalityreductionofthetextfeaturespace;Thenthroughthemultiplecombinationfeatureextractionalgorithminthelowerdimensionoffeaturespacefastextractmorerepresentativeofthefeature,filteroutsomerepresentativeweakfeatureitems;Finally,usingtheSVMclassifiertoclassifythetext.TheexperimentalresultsshowthatPCA-CFEAalgorithmcaneffectivelyimprovetextclassificationaccuracyandrunningefficiency.Keywords:CombinedfeatureextractionalgorithmbasedonPCA(PCA-CFEA);Principalcomponentanalysis;Featureextraction;Textclassification;0引言Internet上蕴含着海量的各种类型的原始资源信息，随着Internet技术和应用的快速发展,越来越多的人使用网络来查找对自己有用的信息；如何在大量的信息源中获得有价值的模式与知识是当前WEB数据挖掘的主要目标[1]。Web文本分类是Web数据挖掘的一个重要研究课题,其主要思想是根据Web文本内容,利用从已知类别的网页集中学习到的知识,自动对一个待识别网页予以一个类别标识。文本分类时,通常用向量空间模型（SVM）表示文本,即以一组词条作为属性的向量构成的特征向量空间。文本的原始特征向量空间包含全部的词条属性,具有高维性、稀疏性的特点。但并不是所有属性对分类决策都有贡献,冗余的属性不但对决策的结果无任何贡献,反而会降低决策的执行效率。计算机应用研究提高属性集的充分、必要性以及降低属性间的相关性是提高文本向量空间中模式的可分性以及分类效率的重点[2]，这就需要在不降低系统性能的前提下,对高维文本特征属性空间进行有效的降维处理,提取出最佳分类特征属性集合。目前,文本特征提取主要是在特征文档矩阵的基础上采用某种特征评估函数对每个特征词进行评估,通过设定阈值保留一定数量的特征来完成的，现有的特征选择函数主要有文档频率(DF)、互信息(MI)、信息增益(IG)和χ2统计（CHI）等。但这些特征提取方法都是在假设特征项之间是独立的前提下进行的,并且每种方法关注的重点不同，文档频率(DF)强调高频词汇对文本分类的影响,虽然文献[3]采用本体关联度改进了TF-IDF的特征词提取方法，但实验结果的优劣却与领域本体的选择有关，如本体概念的细分程度、覆盖程度，本体构建的成熟程度，关联度计算公式中的参数选取以及阈值的设定都会对本体关联词集合的构建造成影响，进而影响到文本分类的准确率；互信息(MI)的特征选择倾向于罕见词对文本分类的影响[2]，文献[4]通过引入扰动因子,改进了MI方法,使其在维数约简与分类性能上均取得了较好的效果，但对于低维数据的处理却不尽如人意；而χ2统计（CHI）是假设词条与类别之间符合χ2分布,χ2统计量的值越高,词条和文本类别之间的相关性越强,对文本类别的贡献越大[5]，这些应用前提假设势必会造成部分分类信息的丢失,影响后面文本分类的结果。针对上面各种方法的局限性,本文提出了一种基于主成分分析(PCA)的组合特征提取方法(PCA-CFEA)，利用PCA方法充分考虑到特征项之间的相关性,将原始的特征文档矩阵转换为较低维的正交特征矩阵,此矩阵由原始特征文档矩阵的主成分组成,他们保留了原始特征矩阵最多的特征信息,而且保证了新特征之间是互不相关的,不会因为约去某个特征而丢失有用的信息,所以能获得文本的最佳描述特征。然后在PCA降维的基础上再分别利用改进的文档频率(DF)、互信息(MI)、信息增益(IG)和χ2统计（CHI）方法组合特征提取，克服使用单一特征提取方法的缺陷，最终获得更优的分类特征,实验结果表明采用本文基于PCA的组合特征提取方法提取词语特征对提高文本分类的正确率和执行效率都有效。1文本分类关键技术1.1主成分分析(PCA)主成分分析法(PCA)是一种很经典的多元数据分析工具,它能把原来的多个变量转化为少数几个综合指标,是一种很好的数据降维处理技术。假设有N个数据样本,每个样本用n个观测变量错误!未找到引用源。来表示,则可以得到一个样本数据矩阵:错误!未找到引用源。(1)设综合指标为错误!未找到引用源。,他们是观测变量错误!未找到引用源。的线性组合,即:错误!未找到引用源。m≤n其中,系数aij由下列原则决定:①任意两个综合指标之间不相关;②错误!未找到引用源。为错误!未找到引用源。线性组合中方差最大的,错误!未找到引用源。依次递减。错误!未找到引用源。分别称为错误!未找到引用源。第1,第2,…第m个主成分。他们可以看作是一组新特征,他们保留了原始特征集合中尽可能多的特征信息量；根据数学理论,系数a就是错误!未找到引用源。的协方差矩阵的m个特征值对应的特征向量。1.2互信息(MI)词条与类别的互信息(MI)所用的评估函数为:错误!未找到引用源。(2)其中:W为特征词;Ci为类别;P(W)为在整个文档集中W出现的概率;P(W|Ci)为在类别Ci出现的前提下W出现的概率。它有两种常用的计算形式:错误!未找到引用源。(3)错误!未找到引用源。(4)通过设定阈值，将低于阈值的特征从原始特征空间中移除以降低特征空间的维数,保留高于阈值的特征。一般来说,MImax(W)要优于MIavg(W)，本文选取互信息量最大的名词作为特征词,因为这样的词在某个类中的出现概率大,而在其他类中出现的概率小，这是因为互信息量越大,名词和类别之间同时出现的概率也越大[4]。1.3文档频率(TF-IDF)单词权重计算最为有效的实现方法应该是TF*IDF,它是Salton在1988年提出的。它的计算如下公式所示:错误!未找到引用源。(5)计算机应用研究其中错误!未找到引用源。是特征项错误!未找到引用源。在文本错误!未找到引用源。的权重取值,错误!未找到引用源。是特征项错误!未找到引用源。在文本错误!未找到引用源。中出现的频率(即TF),用于计算该词描述文档内容的能力；错误!未找到引用源。(即IDF)是特征项错误!未找到引用源。在文本集d中出现文本频率数的反比，称为反文档频率，用于计算该词区分文档的能力；TF*IDF的指导思想是建立在这样一条基本假设之上:在一个文本中出现很多次的单词,在另一个同类文本中出现次数也会很多,反之亦然[6,7]。所以如果特征空间坐标系取TF词频作为测度,就可以体现同类文本的特点。另外还要考虑单词区别不同类别的能力,TF*IDF法认为一个单词出现的文本频率越小,它区别不同类别的能力就越大,所以引入了反文本频度IDF的概念,以TF和IDF的乘积作为特征空间坐标系的取值测度[8,9]。TF-IDF方法结合TF和IDF，从词语在一篇文本中的频率和在文本集中的分布状况两个方面来衡量该词语在文本表示中的重要程度。其中TF（TermFrequency）是对一个词语局部重要性的度量，用该词语在某一文本中出现的频率表示，频率越大，则该词语对于这篇文本的表示贡献越大；IDF（InverseDocumentFrequency)为反文本频率，表示词语t在整个文本集中的分布情况，文本集中含有词语t的文本数量越少，则词语t表示文本时越重要[10]。本文对TF-IDF公式进行了适当加权处理[3],在计算词频的时候考虑文档长度因素,在计算特征频率的时候用特征频率再除以文本总的特征词数,即用错误!未找到引用源。代替TF,其中L代表文档所包含的词数。在TF-IDF公式中的反文档频率即IDF部分,为了弥补IDF没有考虑特征词在类间分布的缺陷。把各个类间的平均偏差平方错误!未找到引用源。加入TF-IDF公式中,计算公式为:错误!未找到引用源。(6)其中,错误!未找到引用源。代表词条在类中出现的频率,错误!未找到引用源。代表词条在各个类的平均词频,最后TF-IDF被修改为[3]:错误!未找到引用源。(7)1.4χ2统计(CHI)除了使用TF-IDF方法进行特征提取外,CHI方法也是目前人们认为比较好的一个特征词选取方法,计算公式为:错误!未找到引用源。(8)其中P1为特征t与文档c类同时出现的次数，P2为特征t与c类文档均不出现的次数，P3为特征t出现而c类文档不出现的次数,P4为c类文档出现而特征t不出现的次数，N为文档总数。当P1→0且P2→N时,CHI统计提高了在指定类中出现频率低而普