文本分类中特征提取及分类算法综述.doc

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

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

A Review For Feature Selection And Classification Algorithm In Text Categorization

Abstract:Text categorization is a key technology in the process of information retrieval and filtering,whose task is to process automatically the unknown categories of documents and distinguish the labels they belong to in the set of predefined categories. This paper mainly discuss the feature selection and classification algorithm in text categorization, and make deep research via experiment.
kNN and Native Bayes classification algorithm have been applied to test the performance of classical feature detection methods, and the classification results based on classical feature detection methods have been made a comparison. The results have been made a comprehensive evaluation analysis by assessment indicators, such as precision, recall, F1. In the end, the influence feature selection methods have made on classification speed and accuracy have been revealed.
Keywords:Text categorization Feature selection Classification algorithm

前言
互联网技术的高速发展引起了信息量的爆炸式增长，面对庞大的数据信息，如何在大规模的文本异构信息中准确、快速、全面地查找到个人所需的特定信息，已经成为了一项具有非常重要意义的研究课题[1]。
文本分类的主要功能就是对相关的文档集合进行类别的标签与分配，其主要依据是在文本训练过程中将那些已经被提前分配合理的作为类别标签的训练文档集和。作为自动信息管理的核心技术，人工智能与信息检索技术是文本自动分类的两大技术基础，在组织和管理海量文本信息技术领域中文本分类是一种非常有效的技术手段[1]。所以，对文本自动分类技术的深入研究有着非常重要的理论意义与实用价值。
目前通常采用向量空间模型来描述文本向量[2]。然而，面对高维的文本特征，如果不进行降维处理，则会造成“维度灾难”，从而大大影响分类效果。特征降维是文本分类过程中的一个重要环节。特征提取和特征抽取是特征降维技术的两大类，相对于特征抽取方法，特征提取方法因其快速、简单、便捷的优点，在文本分类领域中得到广泛的应用。
选择合适的文本表示模型、特征降维方法和分类器算法对文本分类的速度和精度有着至关重要的影响。本文主要采用NewsGroups语料库中的20news-18828数据源，使用kNN和Native Bayes分类算法对验证几种已有的经典特征选择方法，并将其分类结果进行比较，揭示特征提取算法对分类性能的影响。
1、 几种经典的特征提取方法
1.1 文档频率（DF）
文档频率是指在训练文档集中某词条出现过的文档总数[3]。文档频率特征提取方法的基本思想是：首先根据具体情况设定最小和最大的文档频率阈值，接着计算每个特征词的文档频率。如果该特征词的文档频率大于已设定的最大文档频率阈值或小于最小的文档频率阈值，则删除该特征词，否则保留。
（式1-1）
其中，表示词条在文档中出现的次数，表示文本的总词汇数。
是一种最简单的词约简技术，常用于大规模的语料特征选择中。但其缺点是如果某一稀有词条主要出现在某类训练集中，能够很好地反应该类别的特征，但因低于某个设定的阈值而直接滤除掉，因此就可能影响文本分类器的分类精度。
1.2 信息增益（IG）
在文本分类系统中，信息增益算法通过统计某一个特征词在文本类别中是否出现的文档频数来计算该特征项对于文本类别的信息增益。该算法考虑了特征在文档中出现前后的信息熵之差，公式定义为[3]：

（式1-2）

其中，表示语料库中文档类别总数；表示类文档在语料库中出现的概率；表示包含特征的文档的概率；表示不包含特征的文档的概率；表示包含特征的文档属于类别的概率；表示包含特征的文档不属于类别的概率。
信息增益法的缺点是，它考虑了特征未发生的情况，尽管特征不出现的情况也可能对文本分类的判别有积极作用，但这种积极作用往往要远小于考虑这种情况时对文本分类带来的干扰。
1.3 互信息（MI）
互信息衡量的是某个特征词和特征类别之间的统计相关性。因此，某个特征词和某个文本类别互信息定义度量两个给定对象之间的相关性，在不良信息过滤问题中用以度量特征项对于文本主题的区分度。特征词和类别的互信息公式定义如下[4]：

（式1-3）
其中，为类别数；表示类别的概率；表示包含特征且属于类别的概率；表示特征的概率；表示属于类别的概率。
互信息值较高的特征词通常在某个类别中出现的概率高，而在其他文本类别中出现的概率低，也就更有可能被选作为文本类别的特征。在个类别的文本训练集上特征项的互信息值公式定义如下[5]：
（式1-4）
1.4 统计（CHI）
统计用来衡量特征词条和类别之间的统计相关性。假设特征和类别之间是符合一阶自由度的分布，则特征词对于类别的统计公式定义如下[6]：

（式1-5）
其中，表示属于类且包含的文档频数，表示不属于类但是包含的文档频数，表示属于类但是不包含的文档频数，表示不属于类且不包含的文档频数。
对于多类问题，分别计算对于每个类别的卡方统计值，再用下面两种公式计算特征对于整个样本的卡方统计值，分别进行检验：
（式1-6）

（式1-7）
其中，为类别数，从原始特征空间中移除低于特定阈值的特征，保留高于该阈值的特征作为文档表示的特征。
当特征词与文本类别相互独立时，，此时特征不含有任何与文本类别有关的鉴别信息。反之，的值越大，与的统计相关性越强。但是通过统计的公式可看出，该方法对低文档频率的特征项不靠谱，因其提高了在指定文本类别中出现的频率较低但却大量存在于其他类别的特征项在该文本类别中的权值。
1.5 TF-IDF
词汇频率： ，其中，表示文本的总词汇数，表示词在文本中出现的次数，的值越大，词与文本的相关性就越强；
逆文档频率： 其中，表示包含词的文档数，表示语料库中的总文档数
目，值越大，该词与文档的相关性越低。
（式1-8）
针对TFIDF算法的归一化计算公式为：

（式1-9）

2、 文本分类方法
文本分类方法主要分为两大类：基于规则的分类方法和基于统计的分类方法。其中基于规则的分类方法包括：决策树、关联规则和粗糙集等；基于统计的分类方法包括：K-最近邻算法、朴素贝叶斯、支持向量机等算法。由于后者具有实现简单、分类性能良好的优点，故而在文本自动分类领域中应用广泛。
2.1 K-最近邻算法
K-最近邻算法（kNN），是一种基于向量空间模型的类比学习方法。因其简单、稳定、有效的特点，被广泛应用于模式识别系统中。
使用kNN算法分类时，首先将待分类文档通过特征权重计算表示成空间向量形式的特征集合；然后，根据相应的准则将特征向量与预先确定好类别的样本权重向量进行相关的计算，得到前K个相似度较高的文本；最后，判定该文档的文本类别属性。
在计算文本相似度时，通常采用向量夹角余弦来度量。在空间模型中，通过计算两个文本向量之间夹角的余弦值来表示两个文档和之间的文本相似度，计算公式如下：

（式2-1）

其中，表示第个文档的第个属性值。当两个文本越相似时，的值越大。
通过上述计算公式，从预先确定好类别的文档集合中选取前K个与待分类文档最接近的样本。
对于待分类样本的K个近邻样本，依次计算对每个类别的权重，计算公式如下：
（式2-2）

其中，表示待分类文档的特征向量，则表示文本类别属性函数，若文档属于类，则该函数值为1，否则为0.
在文本分类中，K-最近邻算法的主要过程是：在文本的训练阶段，将文本训练集文档分别表示成机器可识别操作的特征向量的形式；在文本分类阶段，主要进行文本的相似度计算和权重值排序。在分类中，K-最近邻算法的时间复杂度与文本训练集合的文档总数成正比，该算法的时间复杂度较高，更适用于文本训练集合规模较小的文本分类系统。
2.2 朴素贝叶斯算法
朴素贝叶斯算法[7]可应用到大规模文本集合中，具有方法简单、速度快、分类准确率高等优点。理论上，由于朴素贝叶斯算法所基于的假设太过于严格，故而其分类效果要普遍优于其他分类算法，但是在实际应用中并不能完全符合理论中的假设条件，则算法的准确率会有一定程度的下降。在类别数目较多或者类别之间相关性较小的情况下，该模型的分类性能才能达到最佳。
假设训练集中存在个类别，类别集合表示为，文本特征词集合表示为，各个文本特征对给定文本类别的影响是相互独立的。那么，类别的先验概率为：
（式2-3）
其中，表示属于类别的文本数目，表示训练集的文本总数。
设表示文本特征集合中的第个特征词，表示特征词在所有属于类别的文档集中出现的概率。则未知类别文本属于文本类别的条件概率为：
（式2-4）
根据贝叶斯定理，文本类别的后验概率为：
（式2-5）

（式2-6）
其中，表示文本中所有特征词在整个文本集合中出现的概率，为常数。因此，上式简化为：
（式2-7）
结合式2-4和2-7，可得
（式2-8）
利用式2-8计算出的每个类别对于文档的后验概率值，然后将文档判定到概率值最大的那个文本类别中去。
2.3 支持向量机（SVM）
支持向量机SVM算法是一种基于统计学理论的机器学习方法。该理论的基本思想是在准确性和机器容量之间，对于给定的具有有限数量训练文本集的学习任务进行折衷，以期望得到最佳的应用性能[8]。该算法依据结构风险最小化的原则，合理地选择特征集合以及文本类别的判定函数，以保证通过有限实验条件下所得到的性能良好的文本分类器在对实际的分类中效果仍然良好，最终得到一个分类性能优异并具有广泛应用性的学习机[9]。
SVM算法是依据线性且可分情况下的最优分类平面提出的，如图所示：

图1 最优分类超平面和支持向量
图1：SVM中的分类平面
如图1所示，样本集合能够被平面H完全区分开，同时使直线H1、H2间的距离最大。其中，H1、H2是指在样本集合中平行于H并且过离H最近的点的直线。支持向量机的基本思想是：首先将样本输入空间，通过某种非线性变换（通过定义适当的内积实现）转换到高维空间中去，并且在高维空间线性可分的情况下通过计算得到文本最优分类平面[10]。
通常，一个分类面只能对两个类别进行划分，而对于多类别的文本分类问题，就需要构造多个超平面，将每一类别和其它的类别区分开来。同时，稀疏、高维的数据对SVM算法基本没影响，因此能够更好地体现文本数据的类别特征，相对于其它分类算法，SVM算法的文本分类准确率较高。大量实验结果表明，支持向量机的文本分类效果明显优于其它的文本分类算法[11]。
3、分类系统实现与结果分析
3.1 文本分类系统的整体设计
本文使用Newsgroups18828数据源和java软件设计平台做分类分类实验，实现了文本训练与测试前的文本预处理等相关工作，通过利用java软件编程，生成了朴素贝叶斯分类器和KNN分类器。
在面对大规模的文本数据时，文本预处理后所得到的特征项数量巨大，给分类器的处理工作打来很大困难，因此需通过特征降维（即加入特征降维模块）来降低分类器的处理的复杂度。整个系统分为四个模块：文本预处理模块、特征降维模块、分类模块及测试评估模块，系统框架如图2所示。具体的处理流程如下：
（1） 将语料库中的文本进行预处理（去停顿词、虚词等处理）后，形成原始特征集和；
（2） 在文本预处理模块处理的结果的基础上，循环读取每个特征词条，获得其相关的词频以及文档频率等信息。然后统计特征提取方法所需要的参数，利用特征提取方法进行计算，选出预定数目的最能代表各个类别特征的最优特征集和，经过权重计算，区别每个特征词条所代表的文本类别信息大小并存储；
（3） 把文档表示为文本特征向量的表示形式，经过分类模块处理过程得到最终的文本分类结果；
（4） 最后通过测试评估模块，对文本分类结果进行分析与比较，验证采用不同的特征提取方法进行特征降维，对分类结果的影响。

训练文本集

文本预处理

构造分类器

测试文本集

特征提取

文本预处理

分类

建立特征模型

文本向量化表示
分类结果的分析
与评价

分类器

图2：文本分类实验系统框图
3.2 系统功能模块设计
3.2.1 文本预处理模块
文本预处理模块主要是利用分词词典对语篇内容进行词的划分，并去除标点符号、各类虚词、停顿词等，得到一个词的列表文件。详细的处理过程参照文档预处理类DataPreProcess.java。
具体步骤如下：
1） 英文词法分析，去除数字、连字符、标点符号、特殊字符，所有大写字母转换成小写，可以用正则表达式 String res[]=line.split(“[^a-zA-Z]”)；
2） 去停用词，过滤对分类无价值的词；
3） 词根还原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下包含单词tk的文件数+1）/(类c下单词总数+2)
先验概率P(c)=类c下文件总数/整个训练样本的文件总数
由于多项式模型分类准确率较高，故本文的朴素贝叶斯分类器采用多项式模型。
（2）KNN分类器
KNN算法描述：
1） 文本向量化表示，由特征词的TF*IDF值计算；
2） 在新文本到达后，根据特征词确定新文本的向量；
3） 在训练文本集中选出与新文本最相似的k个文本，相似度用向量夹角余弦度量，计算公式为：

一般采用先设定一个初始k值，然后根据实验测试结果调整k值，本文中取k=20。
4） 在新文本的 K 个邻居中，依次计算每类的权重，每类的权重等于K个邻居中属于该类的训练样本与测试样本的相似度之和；
5） 比较类的权重，将文本分到权重最大的那个类别中。
3.2.4 测试评估模块
（1）朴素贝叶斯算法实现
在java编程实现中，包含两大类：贝叶斯算法类（NaiveBayesianClassifier.java）与测试集与训练集创建类（CreateTrainAndTestSample.java）。其中，分类器主类如图3所示

图3：朴素贝叶斯分类器主类
Java代码注解：
1）计算概率用到了BigDecimal类实现任意精度计算；
2）用交叉验证法做十次分类实验，对准确率取平均值；
3）根据正确类目文件和分类结果文计算混淆矩阵并且输出；
4）Map<String,Double> cateWordsProb key为“类目_单词”, value为该类目下该单词的出现次数，避免重复计算。
朴素贝叶斯分类器分类结果（混淆矩阵）如图4所示：

图4：贝叶斯分类法分类结果的混淆矩阵表示
（2）KNN算法实现
在java编程实现中，包含两大类：文档向量计算类（ComputeWordsVector.java）和KNN算法实现类（KNNClassifier.java）。分别如图5和图6所示：

图5：文档向量计算类
Java代码注解：
1）计算IDF非常耗时，3万多个词的属性词典初步估计需要25个小时；
2）可以先尝试所有词的IDF都设成1的情况。

图6：KNN分类器主类
Java代码注解：
1）用TreeMap<String,TreeMap<String,Double>>保存测试集和训练集；
2）注意要以"类目_文件名"作为每个文件的key，才能避免同名不同内容的文件出现；
3）注意设置JM参数，否则会出现JAVA heap溢出错误；
4）本程序用向量夹角余弦计算相似度。
KNN算法的分类结果（混淆矩阵）如图7所示：

图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）两种分类算法的性能比较
在相同的硬件环境下，贝叶斯分类算法和KNN分类算法经比较，可知：在分类准确率方面，KNN算法更优；在分类速度方面，朴素贝叶斯算法更优。
4、结论
本文首先对文本分类的相关技术做了详细的介绍，然后针对文本分类系统中的特征提取过程和算法进行了进一步的研究与探讨。对特征降维模块中常用的特征提取方法，如文档频率（DF）、信息增益（IG）、互信息（MI）、分布、TF-IDF，进行了系统的理论概述；对常用的分类算法（如朴素贝叶斯算法、KNN算法和支持向量(SVM)）的原理进行了详细的描述。最后通过采用Newsgroups18828数据源以及java软件环境搭建文本自动分类的实验平台，证明了文档频率（DF）和TF-IDF特征提取方法的有效性，并对朴素贝叶斯分类算法和KNN分类算法的实验结果进行比较，得出结论：在分类准确率方面，KNN算法更优；在分类速度方面，朴素贝叶斯算法更优。
本文存在的不足之处是并未验证信息增益（IG）、互信息（MI）、分布等特征提取方法在文本分类中的有效性，对上述特征提取方法的对分类结果的影响也并未做出比较。因此，我的下一步任务就是验证上述特征提取方法在文本分类中的实效性，并对相应的分类结果作出比较，从而找出一种高效的文本特征提取方法。

参考文献
[1]Mark Graven,Dan Dipasquo,Daven Freitag Learning to Construct Knowledge Bases from the World Wide Web[J]Artificial Intelligence 2000,118(1-2):69-113
[2]刘赫.文本分类中若干问题研究[D].吉林：吉林大学.2009.6
[3]Sebastiani F.Machine Learning In Automated Text Categorization[C].ACM Computing Surveys,2002,34(1):1-47
[4]刘健，张维明.基于互信息的文本特征选择方法研究与改进[J].计算机工程与应用.2008,44(10):135-137
[5]范小丽，刘晓霞.文本分类中互信息特征选择方法的研究[J].计算机工程与应用.2010，46（34）:123-125
[6]邓彩凤.中文文本分类中互信息特征选择方法研究[D].重庆：西南大学.2011
[7]Y.H. Liand A.K. Jain Classification of text document[J]The computer Joural,141(8):537-546,1998
[8]台德艺，基于特征权重算法的文本分类研究[D].合肥：合肥工业大学，2007
[9]张小莉，基于信息增益的中文特征提取算法研究[D].重庆：重庆大学，2008
[10]蒋健，文本分类中特征提取和特征加权方法研究[D].重庆：重庆大学，2010
[11]T.Joachims,Text catagorization with support vector machines:learning with many relevant features in proceedings of ECML-98 10th European Conference on Machine Learning.137-142,1998
第12页共12页