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

第1页共12页文本分类中的特征提取和分类算法综述摘要：文本分类是信息检索和过滤过程中的一项关键技术，其任务是对未知类别的文档进行自动处理，判别它们所属于的预定义类别集合中的类别。本文主要对文本分类中所涉及的特征选择和分类算法进行了论述，并通过实验的方法进行了深入的研究。采用kNN和NaiveBayes分类算法对已有的经典征选择方法的性能作了测试，并将分类结果进行对比，使用查全率、查准率、F1值等多项评估指标对实验结果进行综合性评价分析.最终，揭示特征选择方法的选择对分类速度及分类精度的影响。关键字：文本分类特征选择分类算法AReviewForFeatureSelectionAndClassificationAlgorithmInTextCategorizationAbstract:Textcategorizationisakeytechnologyintheprocessofinformationretrievalandfiltering,whosetaskistoprocessautomaticallytheunknowncategoriesofdocumentsanddistinguishthelabelstheybelongtointhesetofpredefinedcategories.Thispapermainlydiscussthefeatureselectionandclassificationalgorithmintextcategorization,andmakedeepresearchviaexperiment.kNNandNativeBayesclassificationalgorithmhavebeenappliedtotesttheperformanceofclassicalfeaturedetectionmethods,andtheclassificationresultsbasedonclassicalfeaturedetectionmethodshavebeenmadeacomparison.Theresultshavebeenmadeacomprehensiveevaluationanalysisbyassessmentindicators,suchasprecision,recall,F1.Intheend,theinfluencefeatureselectionmethodshavemadeonclassificationspeedandaccuracyhavebeenrevealed.Keywords:TextcategorizationFeatureselectionClassificationalgorithm第2页共12页)|(log)|()()|(log)|()()(log)()(111tCptCptptCptCptpCpCptIGimiiimiiimii前言互联网技术的高速发展引起了信息量的爆炸式增长，面对庞大的数据信息，如何在大规模的文本异构信息中准确、快速、全面地查找到个人所需的特定信息，已经成为了一项具有非常重要意义的研究课题[1]。文本分类的主要功能就是对相关的文档集合进行类别的标签与分配，其主要依据是在文本训练过程中将那些已经被提前分配合理的作为类别标签的训练文档集和。作为自动信息管理的核心技术，人工智能与信息检索技术是文本自动分类的两大技术基础，在组织和管理海量文本信息技术领域中文本分类是一种非常有效的技术手段[1]。所以，对文本自动分类技术的深入研究有着非常重要的理论意义与实用价值。目前通常采用向量空间模型来描述文本向量[2]。然而，面对高维的文本特征，如果不进行降维处理，则会造成“维度灾难”，从而大大影响分类效果。特征降维是文本分类过程中的一个重要环节。特征提取和特征抽取是特征降维技术的两大类，相对于特征抽取方法，特征提取方法因其快速、简单、便捷的优点，在文本分类领域中得到广泛的应用。选择合适的文本表示模型、特征降维方法和分类器算法对文本分类的速度和精度有着至关重要的影响。本文主要采用NewsGroups语料库中的20news-18828数据源，使用kNN和NativeBayes分类算法对验证几种已有的经典特征选择方法，并将其分类结果进行比较，揭示特征提取算法对分类性能的影响。1、几种经典的特征提取方法1.1文档频率（DF）文档频率是指在训练文档集中某词条出现过的文档总数[3]。文档频率特征提取方法的基本思想是：首先根据具体情况设定最小和最大的文档频率阈值，接着计算每个特征词的文档频率。如果该特征词的文档频率大于已设定的最大文档频率阈值或小于最小的文档频率阈值，则删除该特征词，否则保留。NntDFt)(（式1-1）其中，tn表示词条t在文档中出现的次数，N表示文本的总词汇数。DF是一种最简单的词约简技术，常用于大规模的语料特征选择中。但其缺点是如果某一稀有词条主要出现在某类训练集中，能够很好地反应该类别的特征，但因低于某个设定的阈值而直接滤除掉，因此就可能影响文本分类器的分类精度。1.2信息增益（IG）在文本分类系统中，信息增益算法通过统计某一个特征词t在文本类别中是否出现的文档频数来计算该特征项t对于文本类别ic的信息增益。该算法考虑了特征t在文档中出现前后的信息熵之差，公式定义为[3]：（式1-2）第3页共12页其中，m表示语料库中文档类别总数；)(iCp表示iC类文档在语料库中出现的概率；)(tp表示包含特征t的文档的概率；)(tp表示不包含特征t的文档的概率；)(tCpi表示包含特征t的文档属于类别iC的概率；)(tCpi表示包含特征t的文档不属于类别iC的概率。信息增益法的缺点是，它考虑了特征未发生的情况，尽管特征不出现的情况也可能对文本分类的判别有积极作用，但这种积极作用往往要远小于考虑这种情况时对文本分类带来的干扰。1.3互信息（MI）互信息衡量的是某个特征词和特征类别之间的统计相关性。因此，某个特征词t和某个文本类别ic互信息定义度量两个给定对象之间的相关性，在不良信息过滤问题中用以度量特征项对于文本主题的区分度。特征词t和类别ic的互信息公式定义如下[4]：（式1-3）其中，m为类别数；)(iCp表示类别iC的概率；),(iCtp表示包含特征t且属于类别iC的概率；)(tp表示特征t的概率；)(iCp表示属于类别iC的概率。互信息值较高的特征词通常在某个类别ic中出现的概率高，而在其他文本类别中出现的概率低，也就更有可能被选作为文本类别ic的特征。在m个类别的文本训练集上特征项t的互信息值公式定义如下[5]：),()(1miiictMIcpMI（式1-4）1.42统计（CHI）2统计用来衡量特征词条t和类别ic之间的统计相关性。假设特征t和类别ic之间是符合一阶自由度的2分布，则特征词t对于类别ic的2统计公式定义如下[6]：（式1-5）其中，A表示属于ic类且包含t的文档频数，B表示不属于ic类但是包含t的文档频数，C表示属于ic类但是不包含t的文档频数，D表示不属于ic类且不包含t的文档频数。对于多类问题，分别计算t对于每个类别的卡方统计值，再用下面两种公式计算特征t对于整个样本的卡方统计值，分别进行检验：（式1-6）（式1-7）其中，n为类别数，从原始特征空间中移除低于特定阈值的特征，保留高于该阈值的特征作为文档表示的特征。当特征词t与文本类别ic相互独立时，0),(2ict，此时特征t不含有任何与文本类别ic有关的鉴别信息。反之，),(2ict的值越大，t与ic的统计相关性越强。但是通过2统计的公式可看出，该方法对低文档频率的特征项不靠谱，因其提高了在指定文本类别中出现的频率较低但却大量存在于其他类别的特征项在该文本类别中的权值。),(max)(212maxintctt)()(),(log)(),(1iimiiicptpctpcpctMI)(*)(*)(*)()(*),(22DCBADBCACBADNcti),()()(212iniiavgCtCpt第4页共12页1.5TF-IDF词汇频率：，其中，N表示文本的总词汇数，wN表示词w在文本中出现的次数，TF的值越大，词w与文本的相关性就越强；逆文档频率：其中，wD表示包含词w的文档数，D表示语料库中的总文档数目，IDF值越大，该词与文档的相关性越低。（式1-8）针对TFIDF算法的归一化计算公式为：（式1-9）2、文本分类方法文本分类方法主要分为两大类：基于规则的分类方法和基于统计的分类方法。其中基于规则的分类方法包括：决策树、关联规则和粗糙集等；基于统计的分类方法包括：K-最近邻算法、朴素贝叶斯、支持向量机等算法。由于后者具有实现简单、分类性能良好的优点，故而在文本自动分类领域中应用广泛。2.1K-最近邻算法K-最近邻算法（kNN），是一种基于向量空间模型的类比学习方法。因其简单、稳定、有效的特点，被广泛应用于模式识别系统中。使用kNN算法分类时，首先将待分类文档通过特征权重计算表示成空间向量形式的特征集合；然后，根据相应的准则将特征向量与预先确定好类别的样本权重向量进行相关的计算，得到前K个相似度较高的文本；最后，判定该文档的文本类别属性。在计算文本相似度时，通常采用向量夹角余弦来度量。在空间模型中，通过计算两个文本向量之间夹角的余弦值来表示两个文档id和jd之间的文本相似度，计算公式如下：（式2-1）其中，ikw表示第i个文档的第k个属性值。当两个文本越相似时，),(jiddsim的值越大。通过上述计算公式，从预先确定好类别的文档集合中选取前K个与待分类文档最接近的样本。对于待分类样本的K个近邻样本，依次计算对每个类别的权重，计算公式如下：kNNdjiijicdydxsimcxp),(),(),(（式2-2）其中，x表示待分类文档的特征向量，),(jicdy则表示文本类别属性函数，若文档id属于类jc，则该函数值为1，否则为0.NNTFw)log(wDDIDF)(log),(),(ijijitNNdtTFdtTFIDFnijijiijdtTFIDFdtTFIDFW12),(),()(*)(*cos),(12121MkjkMkikjkMkikji第5页共12页在文本分类中，K-最近邻算法的主要过程是：在文本的训练阶段，将文本训练集文档分别表示成机器可识别操作的特征向量的形式；在文本分类阶段，主要进行文本的相似度计算和权重值排序。在分类中，K-最近邻算法的时间复杂度与文本训练集合的文档总数成正比，该算法的时间复杂度较高，更适用于文本训练集合规模较小的文本分类系统。2.2朴素贝叶斯算法朴素贝叶斯算法[7]可应用到大规模文本集合中，具有方法简单、速度快、分类准确率高等优点。理论上，由于朴素贝叶斯算法所基于的假设太过于严格，故而其分类效果要普遍优于其他分类算法，但是在实际应用中并不能完全符合理论中的假设条件，则算法的准确率会有一定程度的下降。在类别数目较多或者类别之间相关性较小的情况下，该模型的分类性能才能达到最佳。假设训练集中存在j个类别，类别集合表示为},...,{21jcccC，文本特征词集合表示为},...,,{21jtttT，各个文本特征对给定文本类别的影响是相互独立的。那么，类别ic的先验概率为：（式2-3）其中，iN表示属于ic类别的文本数目，N表示训练集的文本总数。设jt表示文本特征集合中的第j个特征词，)(ijctp表示特征词jt在所有属于类别ic的文档集中出现的概率。则未知类别文本d属于文本类别ic的条件概率)(icdp为：)()),...,,(()(121ijjiijictpctttpcdp（式2-4）根据贝叶斯定理，文本类别ic的后验概率)(dcpi为：（式2-5）（式2-6）其中，)(dp表示d文本中所有特征词在整个文本集合中出现的概率，为常数。因此，上式简化为：)()()(