基于向量空间模型的文本自动分类系统的研究与实现

1、基于向量空间模型的文本自动分类系统的研究与实现庞剑锋,卜东波,白硕(中国科学院计算技术研究所,北京100080摘要:随着网络信息的迅猛发展,信息处理已经成为人们获取有用信息不可缺少的工具。文本自动分类系统是信息处理的重要研究方向,它是指在给定的分类体系下,根据文本的内容自动判别文本类别的过程。对文本分类中所涉及的关键技术,包括向量空间模型、特征提取、机器学习方法等进行了研究和探讨,并且提出了基于向量空间模型的文本分类系统的结构,并给出了评估方法和实验结果。关键词:文本分类;中文信息处理;向量空间模型R esearch and Implementation of Text C ategoriza

2、tionSystem B ased on VSMPANGJian2feng,BU D ong2bo,BAI Shuo(Institute o f Computing Technology,Chinese Academy o f Sciences,Beijing100080,ChinaAbstract:In recent years,in formation processing turns m ore and m ore im portant for us to get useful in formation.T ext categ oriza2 tion,the automated assi

3、gning of natural language texts to predefined categ ories based on their contents,is a task of increasing im por2 tance.This paper gives a research to several key techniques about text categ orization,including vector space m odel,feature extrac2 tion,machine learning.It als o describes a text categ

4、 orization m odel based on VS M,and gives the evaluations and results.K ey w ords:T ext categ orization;Chinese in formation processing;Vector space m odel1引言20世纪90年代以来,Internet以惊人的速度发展起来,它容纳了海量的各种类型的原始信息,包括文本信息、声音信息、图象信息等等。如何在浩若烟海而又纷繁芜杂的文本中掌握最有效的信息始终是信息处理的一大目标。基于人工智能技术的文本分类系统能依据文本的语义将大量的文本自动分门别类,从而

5、更好地帮助人们把握文本信息。近年来,文本分类技术已经逐渐与搜索引擎、信息推送、信息过滤等信息处理技术相结合,有效地提高了信息服务的质量。2问题描述211系统任务简单地说,文本分类系统的任务是:在给定的分类体系下,根据文本的内容自动地确定文本关联的类别。从数学角度来看,文本分类是一个映射的过程,它将未标明类别的文本映射到已有的类别中。该映射可以是一一映射,也可以是一对多的映射,因为通常一篇文本可以同多个类别相关联,用数学公式表示如下: f:AB其中,A为待分类的文本集合,B为分类体系中的类别集合。文本分类的映射规则是系统根据已经掌握的每类若干样本的数据信息,总结出分类的规律性而建立的判别公式和判

6、别规则;然后在遇到新文本时,根据总结出的判别规则,确定文本相关的类别。212评估方法因为文本分类从根本上说是一个映射过程,所以评估文本分类系统的标志是映射的准确程度和映射的速度。映射的速度取决于映射规则的复杂程度,而评估映射准确程度的参照物是通过专家思考判断后对文本的分类结果(这里假设人工分类完全正确并且排除个人思维差异的因素。与人工分类结果越相近,分类的准确程度就越高。这里隐含了评估文本分类系统的两个指标:准确率和查全率。准确率是所有判断的文本中与人工分类结果吻合的文本所占的比率,其数学公式表示如下:准确率(Precision=分类的正确文本数实际分类的文本数查全率是人工分类结果应有的文本中

7、分类系统吻合的文本所占的比率,其数学公式表示如下:查全率(Recall=分类的正确文本数应有文本数准确率和查全率反映了分类质量的两个不同方面,两者必须综合考虑,不可偏废。因此,存在一种新收稿日期:2000212221的评估指标F1测试值,其数学公式如下:F1测试值=准确率查全率2准确率+查全率另外,有微平均和宏平均两种计算准确率、查全率和F1值的方法。微平均:计算每一类的准确率、查全率和F1值。宏平均:计算全部类的准确率、查全率和F1值。所有文本分类系统的目标都是使文本分类过程更准确,更快速。3关键技术311文本的表示计算机并不具有人类的智能,人在阅读文章后,根据自身的理解能力可以产生对文章内

8、容的模糊认识;而计算机并不能轻易地“读懂”文章,从根本上说,它只认识0和1,所以必须将文本转换为计算机可以识别的格式。根据“贝叶斯假设”,假定组成文本的字或词在确定文本类别的作用上相互独立,这样,可以就使用文本中出现的字或词的集合来代替文本。不言而喻,这将丢失大量关于文章内容的信息,但是这种假设可以使文本的表示和处理形式化,并且可以在文本分类中取得较好的效果。目前,在信息处理方向上,文本的表示主要采用向量空间模型(VS M。向量空间模型的基本思想是以向量来表示文本:(W1,W2,W3,Wn,其中Wi为第i个特征项的权重。那么选取什么作为特征项呢?一般可以选择字、词或词组。根据实验结果,普遍认为

9、选取词作为特征项要优于字和词组,因此,要将文本表示为向量空间中的一个向量,就首先要将文本分词,由这些词作为向量的维数来表示文本。最初的向量表示完全是0,1形式,即:如果文本中出现了该词,那么文本向量的该维为1,否则为0。这种方法无法体现这个词在文本中的作用程度,所以0,1逐渐被更精确的词频代替,词频分为绝对词频和相对词频。绝对词频,即使用词在文本中出现的频率表示文本;相对词频为归一化的词频,其计算方法主要运用TF2I DF公式。目前存在多种TF2I DF公式,我们在系统中采用了一种比较普遍的TF2I DF公式:W(t,d=tf(t,d×log(N/n t+0101tdtf(t,d&#

10、215;log(N/n t+01012其中,W(t,d为词t在文本d中的权重,而tf(t,d为词t 在文本d中的词频,N为训练文本的总数,n t为训练文本集中出现t的文本数,分母为归一化因子。另外还存在其它的TF2I DF公式,例如:W(t,d=(1+log2tf(t,d×log2(N/n ttd1+log2tf(t,d×log2(N/n t2该式中参数的含义与上式相同。文本经过分词程序分词后,首先去除停用词,合并数字和人名等词汇;然后统计词频,最终表示为上面描述的向量。312特征项的抽取构成文本的词汇,数量是相当大的,所以,表示文本的向量空间的维数也相当大,可以达到几万维

11、。因此我们需要进行维数压缩的工作,这样做的目的主要有两个:第一,为了提高程序的效率,提高运行速度;第二,所有几万个词汇对文本分类的意义是不同的,一些通用的、各个类别都普遍存在的词汇对分类的贡献小;在某特定类中出现比重大而在其它类中出现比重小的词汇对文本分类的贡献大。为了提高分类精度,对于每一类,我们应去除那些表现力不强的词汇,筛选出针对该类的特征项集合,存在多种筛选特征项的算法,如下所列:(1根据词和类别的互信息量判断(2根据词熵判断(3根据K L距离判断在我们的系统中采用了词和类别的互信息量进行特征项抽取的判断标准,其算法过程如下:初始情况下,该特征项集合包含所有该类中出现的词。对于每个词,

12、计算词和类别的互信息量logP(W|C jP(W其中,P(W|Cj=1+|D|i=1N(W,d i|V|+|V|s=1|D|i=1N(W s,d iP(W|C j为W在C j中出现的比重,|D|为该类的训练文本数,N(W,d i为词W在d i中的词频,|V|为总词数,|V|s=1|D|i=1N(W s,d i为该类所有词的词频和。而P(W同上面的计算公式相同,只是计算词在所有训练文本中的比重,其中,|D|为全体训练文本数。对于该类中所有的词,依据上面计算的互信息量排序。抽取一定数量的词作为特征项。具体需要抽取多少维的特征项,目前无很好的解决方法,一般采用先定初始值,然后根据实验测试和统计结果确

13、定最佳值。一般初始值定在几千左右。将每类中所有的训练文本,根据抽取的特征项进行向量维数压缩,精简向量表示。其它抽取特征项的算法,除判断函数上有所差别外,主要过程类似。313训练方法与分类算法训练方法和分类算法是分类系统的核心部分,目前存在多种基于向量空间模型的训练算法和分类算法,例如,支持向量机算法、神经网络方法、最大平均熵方法、最近K邻居方法和贝叶斯方法等等。以下具体介绍三种分类算法:(1简单向量距离分类法该方法的分类思路十分简单,根据算术平均为每类文本集生成一个代表该类的中心向量;然后在新文本来到时,确定新文本向量,计算该向量与每类中心向量间的距离(相似度;最后判定文本属于与文本距离最近的

14、类。具体步骤如下:计算每类文本集的中心向量;计算方法为所有训练文本向量简单的算术平均。新文本到来后分词,将文本表示为特征向量。计算新文本特征向量和每类中心向量间的相似度,公式为:S im(d i,d j=Mk=1W ik×W jk (Mk=1W2ik(Mk=1W2jk其中,d i为新文本的特征向量,d j为第j类的中心向量,M为特征向量的维数,W k为向量的第K维。比较每类中心向量与新文本的相似度,将文本分到相似度最大的那个类别中。(2贝叶斯算法该算法的基本思路是计算文本属于类别的概率。文本属于类别的几率等于文本中每个词属于类别的几率的综合表达式,具体算法步骤如下:(1,2,3,n,

15、其中,W k=P(W k|C j=1+|D|i=1N(W k,d i|V|+|V|s=1|D|i=1N(W s,d i计算公式与计算互信息量的公式相同。在新文本到达时,根据特征词分词,然后按下面的公式计算该文本d i属于类C j的几率:P(C j|d i=P(C j|n k=1P(W k|C j;N(W k,d i|C|r=1P(C r|n k=1P(W k|C r;N(W k,d i其中,P(C j|=C j 训练文档数总训练文档数P(C r|为相似含义,|C|为类的总数,N(W k,d i为W k在d i中的词频,n为特征词总数。比较新文本属于所有类的几率,将文本分到几率最大的那个类别中。

16、(3K NN(K最近邻居算法该算法的基本思路是:在给定新文本后,考虑在训练文本集中与该新文本距离最近(最相似的K篇文本,根据这K篇文本所属的类别判定新文本所属的类别。具体的算法步骤如下:根据特征项集合重新描述训练文本向量。在新文本到达后,根据特征词分词新文本,确定新文本的向量表示。在训练文本集中选出与新文本最相似的K个文本,计算公式为:sim(d i,d j=Mk=1W ik×W jk (Mk=1W2ik(Mk=1W2jk其中,K值的确定目前没有很好的方法,一般采用先定一个初始值,然后根据实验测试的结果调整K值。一般初始值定为几百到几千之间。在新文本的K个邻居中,依次计算每类的权重,

17、计算公式如下:p(x,C j=diK NNSim(x,d iy(d i,C j其中,x为新文本的特征向量;Sim(x,d i为相似度计算公式,与上一步骤的计算公式相同;而y(d i,C j为类别属性函数,即:如果d i属于类C j,那么函数值为1,否则为0。比较类的权重,将文本分到权重最大的那个类别中。除此以外,支持向量机和神经网络算法在文本分类系统中应用得较为广泛。支持向量机的基本思想是使用简单的线形分类器划分样本空间。对于在当前特征空间中线形不可分的模式,则使用一个核函数把样本映射到一个高维空间中,使得样本能够线形可分。而神经网络算法采用感知算法进行分类。在这种模型中,分类知识被隐式地存储

18、在连接的权值上,使用迭代算法来确定权值向量。当网络输出判别正确时,权值向量保持不变,否则进行增加或降低的调整,因此也称为奖惩法。314阈值的确定上面的算法都是将新文本归于分类体系中的一个类,即与该文本关联最大的类。而事实上,分类体系中的类别不是完全互斥的,存在这样一些既属于其中一个类别,又同时属于其它类别的文本。对于这种文本,上述的分类算法无法确定文本所属的所有类别;因此,需要对每个类别确定阈值,当文本在该类的阈值之上时,就将文本归于该类中。但是,阈值的确定是十分困难的,理论上,没有很好地解决方法,一般采用预定初始值,然后给出测试文本,使用分类器进行分类,再根据分类的准确程度调整初始值。这样的

19、方法有两个缺点:首先,初始值的确定不容易,完全是根据经验或简单的测试而定;其次,调整的幅度无法确定,当初始值过高或过低需要增减时,增减的幅度无法很好地确定,只能反复测试,反复调整,这样就大大地增加了工作量。而且,一个分类系统的阈值由于测试文本的不同也无法完全应用于另一个分类系统中。我们在系统中考虑了一种确定阈值的方法,称为百分比阈值确定法,它的基本思想是:首先依据上述训练算法和分类算法构造分类器;然后对于要确定阈值的类,用分类器对该类中所有的训练文本进行分类,从而使每个文本都得到一个相关的值。以上述算法为例:简单向量距离分类法文本与本类中心向量间的相似度值贝叶斯算法文本归属于类的几率K NN算

20、法K个邻居中的类权重然后按递减顺序排列所有本类训练文本得到的值。假定本类有n 篇文本,那么这些文本的值为d 1,d 2,d n ,那么本类阈值y 确定为:y =d sn %其中,s 为初始值。根据训练文本的质量程度,可以确定为80或更高,这样就确定了本类的初始阈值。可以想象,S 越大,该分类器的查全率就越高,准确度就越低;相反地,S 越小,查全率就越低,准确率就越高。然后根据测试进行调整。相应地,调整阈值可以转化为调整s 值,如果对查全率满意而对准确率不满意,那么可以减少s 值,否则就增加s 值。4系统的结构框架我们实现的文本分类系统,研究并结合了上述的关键技术,其结构如图1所示。 图1系统的

21、结构框架,我们实现了上述的三种训练算法和分类算法,并对其效率和结果进行了一定的比较和测试。5测试数据和实验结果我们在一个具有2830篇中文文本的语料库上测试我们系统实现的分类算法,并对其效率和结果进行了比较分析。语料库中的文本都是新闻电讯稿,绝大部分采自新华社,还有200余篇采自中国新闻社和人民日报。所有的新闻稿都由领域专家事先进行分类,按照中图分类法分成政治、经济、军事等共38类。我们选择训练集和测试集的方法如下:将这些分好类的语料平均分成10份,选择其中1份作为开放测试集,剩余的9份作为训练集和封闭测试集。这样每1份都依次轮流作为开放测试集,运行分类算法,共执行10次分类操作,计算其平均值

22、,实验结果如表1所示。表1算法封闭测试查全率封闭测试准确率封闭测试F1值开放测试查全率开放测试准确率开放测试F1值简单向量距离87.08%87.08%87.08%80.23%80.23%80.23%贝叶斯82.39%83.78%83.08%76.17%77.26%76.71%K NN 89.11%91.42%90.25%83.29%85.12%84.20%另外,从算法的时间花费考虑,假设系统的训练文本集包括m 篇文本(向量,分别属于k 个类,而抽取的特征项为n 维,则这三种算法的时间花费见表2。表2算法训练算法分类过程简单向量距离O (mn O (kn 贝叶斯O (mn O (kn K NN无

23、O (km +nm 因此,从测试结果看来,K NN 算法在分类效果上是最佳的,同时在训练过程中投入的时间最少,但是在分类过程中花费的时间最多,不利于文本的实时处理;而贝叶斯算法和简单向量距离算法的时间花费近似,其分类效果也近似,简单距离算法的效果略好。6将来的工作今后,我们在文本分类方向上的研究工作主要围绕三个方面展开:在向量空间模型方面,结合计算语言学,使用概念空间代替词空间;目前的分类体系为平面体系,可以在层次分类体系中考虑文本分类系统;新算法的研究及旧算法的改进。7结束语本文探讨了文本分类系统的关键技术,比较和分析了三种训练和分类算法,并提出了文本分类系统的结构模型,同时给出了实验结果和

24、分析,将来还将继续在层次分类体系中进行文本分类系统的进一步研究。参考文献:1David D Lewis 1Feature Selection and Feature Extraction for T extCateg orizationA 1In Proceedings of S peech and Natural Lan 2guage W orkshop C .Defense Advanced Research Projects A 2gency ,M organ K au fmann ,1992,212221712Y iming Y ang 1An Evaluation of S tatistical Approaches to T extCateg orizationJ 1In Journal of In formation Retrieval ,1999,1(1/2:6728813David D Lewis ,M arc Ringuette 1A C om paris on of T ow LearningAlg orithms of T ext Categ orizationA1In Third Annual S ym posium on D ocument Analysis and In form