文本自动分类系统的研究与实现

基于向量空间模型的文本自动分类系统的研究与实现ResearchandImplementationofTextCategorizationSystemBasedonVSM庞剑锋(Pangjianfeng)卜东波(Budongbo)白硕(Baishuo)（中国科学院计算技术研究所InstituteofComputingTechnology,CAS100080）E-mail:[e-mail]中图法分类号TP391摘要：随着网络信息的迅猛发展，信息处理已经成为人们获取有用信息不可缺少的工具，文本自动分类系统是信息处理的重要研究方向，它是指在给定的分类体系下，根据文本的内容自动判别文本类别的过程，本文对文本分类中所涉及的关键技术，包括向量空间模型、特征提取、机器学习方法，进行了研究和探讨，并且提出了基于向量空间模型的文本分类系统的结构，并给出了评估方法和实验结果。关键词：文本分类中文信息处理向量空间模型Abstract：Inrecentyears,informationprocessingturnsmoreandmoreimportantforustogetusefulinformation.TextCategorization,theautomatedassigningofnaturallanguagetextstopredefinedcategoriesbasedontheircontents,isataskofincreasingimportance.ThispapergivesaresearchtoseveralkeytechniquesaboutTextCategorization,includingVectorSpaceModel,FeatureExtraction,MachineLearning.ItalsodescribesatextcategorizationmodelbasedonVSM,andgivestheevaluationsandresults.Keywords：TextCategorizationChineseInformationProcessingVectorSpaceModel1引言九十年代以来，Internet以惊人的速度发展起来，它容纳了海量的各种类型的原始信息，包括文本信息、声音信息、图像信息等等。如何在浩若烟海而又纷繁芜杂的文本中掌握最有效的信息始终是信息处理的一大目标。基于人工智能技术的文本分类系统能依据文本的语义将大量的文本自动分门别类，从而更好地帮助人们把握文本信息。近年来，文本分类技术已经逐渐与搜索引擎、信息推送、信息过滤等信息处理技术相结合，有效地提高了信息服务的质量。本文主要探讨了文本分类系统的实现和关键技术，第一部分为引言，第二部分描述了文本分类解决的问题并对其性能评估方法进行了介绍，第三部分探讨了文本分类系统的关键技术，第四部分给出了我们实现的基于向量空间模型的文本分类系统的结构框架，第五部分是该系统的测试数据和实验结果，第六部分是对将来工作的设想，第七部分是结束语。2问题描述2.1系统任务简单地说，文本分类系统的任务是：在给定的分类体系下，根据文本的内容自动地确定文本关联的类别。从数学角度来看，文本分类是一个映射的过程，它将未标明类别的文本映射到已有的类别中，该映射可以是一一映射，也可以是一对多的映射，因为通常一篇文本可以同多个类别相关联。用数学公式表示如下：合为分类体系中的类别集为待分类的文本集合，其中，:BABAf文本分类的映射规则是系统根据已经掌握的每类若干样本的数据信息，总结出分类的规律性而建立的判别公式和判别规则。然后在遇到新文本时，根据总结出的判别规则，确定文本相关的类别。2.2评估方法因为文本分类从根本上说是一个映射过程，所以评估文本分类系统的标志是映射的准确程度和映射的速度。映射的速度取决于映射规则的复杂程度，而评估映射准确程度的参照物是通过专家思考判断后对文本的分类结果（这里假设人工分类完全正确并且排除个人思维差异的因素），与人工分类结果越相近，分类的准确程度就越高，这里隐含了评估文本分类系统的两个指标：准确率和查全率。准确率是所有判断的文本中与人工分类结果吻合的文本所占的比率。其数学公式表示如下：实际分类的文本数分类的正确文本数准确率)(precision查全率是人工分类结果应有的文本中分类系统吻合的文本所占的比率，其数学公式表示如下：应有文本数分类的正确文本数查全率)(recall准确率和查全率反映了分类质量的两个不同方面，两者必须综合考虑，不可偏废，因此，存在一种新的评估指标，F1测试值，其数学公式如下：查全率准确率查全率准确率测试值21F另外有微平均和宏平均两种计算准确率、查全率和F1值的方法。微平均：计算每一类的准确率、查全率和F1值。宏平均：计算全部类的准确率、查全率和F1值。所有文本分类系统的目标都是使文本分类过程更准确，更快速。3关键技术3.1文本的表示计算机并不具有人类的智能，人在阅读文章后，根据自身的理解能力可以产生对文章内容的模糊认识，而计算机并不能轻易地“读懂”文章，从根本上说，它只认识0和1，所以必须将文本转换为计算机可以识别的格式。根据“贝叶斯假设”，假定组成文本的字或词在确定文本类别的作用上相互独立，这样，可以就使用文本中出现的字或词的集合来代替文本，不言而喻，这将丢失大量关于文章内容的信息，但是这种假设可以使文本的表示和处理形式化，并且可以在文本分类中取得较好的效果。目前，在信息处理方向上，文本的表示主要采用向量空间模型(VSM)。向量空间模型的基本思想是以向量来表示文本：（W1,W2,W3……Wn），其中Wi为第i个特征项的权重，那么选取什么作为特征项呢，一般可以选择字、词或词组，根据实验结果，普遍认为选取词作为特征项要优于字和词组，因此，要将文本表示为向量空间中的一个向量，就首先要将文本分词，由这些词作为向量的维数来表示文本，最初的向量表示完全是0、1形式，即，如果文本中出现了该词，那么文本向量的该维为1，否则为0。这种方法无法体现这个词在文本中的作用程度，所以逐渐0、1被更精确的词频代替，词频分为绝对词频和相对词频，绝对词频，即使用词在文本中出现的频率表示文本，相对词频为归一化的词频，其计算方法主要运用TF-IDF公式，目前存在多种TF-IDF公式，我们在系统中采用了一种比较普遍的TF-IDF公式：dtttnNdttfnNdttfdtW2)01.0/log(),()01.0/log(),(),(其中，),(dtW为词t在文本d中的权重，而),(dttf为词t在文本d中的词频，N为训练文本的总数，tn为训练文本集中出现t的文本数，分母为归一化因子。另外还存在其他的TF-IDF公式，例如：dtttnNdttfnNdttfdtW22222)/(log)),(log1()/(log)),(log1(),(该公式中参数的含义与上式相同。文本经过分词程序分词后，首先去除停用词，合并数字和人名等词汇，然后统计词频，最终表示为上面描述的向量。3.2特征项的抽取构成文本的词汇，数量是相当大的，因此，表示文本的向量空间的维数也相当大，可以达到几万维，因此我们需要进行维数压缩的工作，这样做的目的主要有两个，第一，为了提高程序的效率，提高运行速度，第二，所有几万个词汇对文本分类的意义是不同的，一些通用的、各个类别都普遍存在的词汇对分类的贡献小，在某特定类中出现比重大而在其他类中出现比重小的词汇对文本分类的贡献大，为了提高分类精度，对于每一类，我们应去除那些表现力不强的词汇，筛选出针对该类的特征项集合，存在多种筛选特征项的算法，如下所列：1．根据词和类别的互信息量判断2．根据词熵判断3．根据KL距离判断在我们的系统中采用了词和类别的互信息量进行特征项抽取的判断标准，其算法过程如下所列：STEPONE:初始情况下，该特征项集合包含所有该类中出现的词。STEPTWO:对于每个词，计算词和类别的互信息量)()|(logWPCWPj其中，VsDiisDiijdWNVdWNCWP111),(),(1)|(，)|(jCWP为W在jC中出现的比重，D为该类的训练文本数，),(idWN为词W在id中的词频，V为总词数，VsDiisdWN11),(为该类所有词的词频和。而)(WP同上面的计算公式相同，只是计算词在所有训练文本中的比重，其中，D为全体训练文本数。STEPTHREE:对于该类中所有的词，依据上面计算的互信息量排序。STEPFOUR:抽取一定数量的词作为特征项，具体需要抽取多少维的特征项，目前无很好的解决方法，一般采用先定初始值，然后根据实验测试和统计结果确定最佳值，一般初始值定在几千左右。STEPFIVE:将每类中所有的训练文本，根据抽取的特征项，进行向量维数压缩，精简向量表示。其他抽取特征项的算法，除判断函数上有所差别，主要过程类似。3.3训练方法与分类算法训练方法和分类算法是分类系统的核心部分，目前存在多种基于向量空间模型的训练算法和分类算法，例如，支持向量机算法、神经网络方法，最大平均熵方法，最近K邻居方法和贝叶斯方法等等，本文以下具体介绍三种分类算法：1.简单向量距离分类法该方法的分类思路十分简单，根据算术平均为每类文本集生成一个代表该类的中心向量，然后在新文本来到时，确定新文本向量，计算该向量与每类中心向量间的距离（相似度），最后判定文本属于与文本距离最近的类，具体步骤如下：STEPONE:计算每类文本集的中心向量，计算方法为所有训练文本向量简单的算术平均STEPTWO:新文本到来后，分词，将文本表示为特征向量STEPTHREE:计算新文本特征向量和每类中心向量间的相似度，公式为：MkMkjkikMkjkikji))((),Sim(其中，id为新文本的特征向量，jd为第j类的中心向量，M为特征向量的维数，kW为向量的第K维。STEPFOUR:比较每类中心向量与新文本的相似度，将文本分到相似度最大的那个类别中。2.贝叶斯算法该算法的基本思路是计算文本属于类别的概率，文本属于类别的几率等于文本中每个词属于类别的几率的综合表达式，具体算法步骤如下：STEPONE:计算特征词属于每个类别的几率向量，)......,,(321n其中，VsDiisDiikjkkdWNVdWNCWPw111),(),(1)|(，计算公式与计算互信息量的公式相同STEPTWO:在新文本到达时，根据特征词分词，然后按下面的公式计算该文本id属于类jC的几率：||1),(1),(1)ˆ;|()ˆ|()ˆ;|()ˆ|()ˆ;|(CrdWNnkrkrdWNnkjkjijikikCWPCPCWPCPdCP其中，总训练文档数训练文档数jjCCP)ˆ|(，)ˆ|(rCP为相似含义，||C为类的总数，),(ikdWN为kW在id中的词频，n为特征词总数。STEPTHREE:比较新文本属于所有类的几率，将文本分到几率最大的那个类别中。3.KNN（K最近邻居）算法该算法的基本思路是：在给定新文本后，考虑在训练文本集中与该新文本距离最近（最相似）的K篇文本，根据这K篇文本所属的类别判定新文本所属的类别，具体的算法步骤如下：STEPONE:根据特征项集合重新描述训练文本向量STEPTWO:在新文本到达后，根据特征词分词新文本，确定新文本的向量表示STEPTHREE:在训练文本集中选出与新文本最相似的K个文本，计算公式为：MkMkjkikMkjkikji))((),Sim(其中，K值的确定目前没有很好的方法，一般采用先定一个初始值，然后根据实验测试的结果调整K值，一般初始值定为几百到几千之间。STEPFOUR:在新文本的K个邻居中，依次计算每类的权重，计算公式如下：KNNdjiijiCdydxSimCxp