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

基于向量空间模型的文本自动分类系统的研究与实现Research and Implementation of Text Categorization System Based on VSM庞剑锋(Pang jianfeng) 卜东波(Bu dongbo) 白硕(Bai shuo)（中国科学院计算技术研究所 Institute of Computing Technology, CAS 100080）E-mail: 中图法分类号TP391摘 要：随着网络信息的迅猛发展，信息处理已经成为人们获取有用信息不可缺少的工具，文本自动分类系统是信息处理的重要研究方向，它是指在给定的分类体系下，根据文本的内容自动判别文本类别的过程，本文对文本分类中所涉及的关键技术，包括向量空间模型、特征提取、机器学习方法，进行了研究和探讨，并且提出了基于向量空间模型的文本分类系统的结构，并给出了评估方法和实验结果。关键词：文本分类 中文信息处理 向量空间模型Abstract：In recent years , information processing turns more and more important for us to get useful information . Text Categorization, the automated assigning of natural language texts to predefined categories based on their contents, is a task of increasing importance. This paper gives a research to several key techniques about Text Categorization , including Vector Space Model , Feature Extraction , Machine Learning . It also describes a text categorization model based on VSM, and gives the evaluations and results .Key words：Text Categorization Chinese Information Processing Vector Space Model1 引言九十年代以来，Internet 以惊人的速度发展起来，它容纳了海量的各种类型的原始信息，包括文本信息、声音信息、图像信息等等。如何在浩若烟海而又纷繁芜杂的文本中掌握最有效的信息始终是信息处理的一大目标。基于人工智能技术的文本分类系统能依据文本的语义将大量的文本自动分门别类，从而更好地帮助人们把握文本信息。近年来，文本分类技术已经逐渐与搜索引擎、信息推送、信息过滤等信息处理技术相结合，有效地提高了信息服务的质量。本文主要探讨了文本分类系统的实现和关键技术，第一部分为引言，第二部分描述了文本分类解决的问题并对其性能评估方法进行了介绍，第三部分探讨了文本分类系统的关键技术，第四部分给出了我们实现的基于向量空间模型的文本分类系统的结构框架，第五部分是该系统的测试数据和实验结果，第六部分是对将来工作的设想，第七部分是结束语。2问题描述2.1 系统任务简单地说，文本分类系统的任务是：在给定的分类体系下，根据文本的内容自动地确定文本关联的类别。从数学角度来看，文本分类是一个映射的过程，它将未标明类别的文本映射到已有的类别中，该映射可以是一一映射，也可以是一对多的映射，因为通常一篇文本可以同多个类别相关联。用数学公式表示如下：文本分类的映射规则是系统根据已经掌握的每类若干样本的数据信息，总结出分类的规律性而建立的判别公式和判别规则。然后在遇到新文本时，根据总结出的判别规则，确定文本相关的类别。2.2 评估方法因为文本分类从根本上说是一个映射过程，所以评估文本分类系统的标志是映射的准确程度和映射的速度。映射的速度取决于映射规则的复杂程度，而评估映射准确程度的参照物是通过专家思考判断后对文本的分类结果（这里假设人工分类完全正确并且排除个人思维差异的因素），与人工分类结果越相近，分类的准确程度就越高，这里隐含了评估文本分类系统的两个指标：准确率和查全率。准确率是所有判断的文本中与人工分类结果吻合的文本所占的比率。其数学公式表示如下：查全率是人工分类结果应有的文本中分类系统吻合的文本所占的比率，其数学公式表示如下：准确率和查全率反映了分类质量的两个不同方面，两者必须综合考虑，不可偏废，因此，存在一种新的评估指标，F1 测试值，其数学公式如下：另外有微平均和宏平均两种计算准确率、查全率和 F1 值的方法。微平均：计算每一类的准确率、查全率和 F1 值。宏平均：计算全部类的准确率、查全率和 F1 值。所有文本分类系统的目标都是使文本分类过程更准确，更快速。3 关键技术3.1 文本的表示计算机并不具有人类的智能，人在阅读文章后，根据自身的理解能力可以产生对文章内容的模糊认识，而计算机并不能轻易地“读懂”文章，从根本上说，它只认识 0 和 1，所以必须将文本转换为计算机可以识别的格式。根据“贝叶斯假设”，假定组成文本的字或词在确定文本类别的作用上相互独立，这样，可以就使用文本中出现的字或词的集合来代替文本，不言而喻，这将丢失大量关于文章内容的信息，但是这种假设可以使文本的表示和处理形式化，并且可以在文本分类中取得较好的效果。目前，在信息处理方向上，文本的表示主要采用向量空间模型 (VSM)。向量空间模型的基本思想是以向量来表示文本：（W1,W2,W3Wn），其中 Wi 为第 i 个特征项的权重，那么选取什么作为特征项呢，一般可以选择字、词或词组，根据实验结果，普遍认为选取词作为特征项要优于字和词组，因此，要将文本表示为向量空间中的一个向量，就首先要将文本分词，由这些词作为向量的维数来表示文本，最初的向量表示完全是 0、1 形式，即，如果文本中出现了该词，那么文本向量的该维为 1，否则为 0。这种方法无法体现这个词在文本中的作用程度，所以逐渐 0、1 被更精确的词频代替，词频分为绝对词频和相对词频，绝对词频，即使用词在文本中出现的频率表示文本，相对词频为归一化的词频，其计算方法主要运用 TF-IDF 公式，目前存在多种 TF-IDF 公式，我们在系统中采用了一种比较普遍的 TF-IDF 公式：其中， 为词 t 在文本 中的权重，而 为词 t 在文本 中的词频，N 为训练文本的总数， 为训练文本集中出现 t 的文本数，分母为归一化因子。另外还存在其他的 TF-IDF 公式，例如：该公式中参数的含义与上式相同。文本经过分词程序分词后，首先去除停用词，合并数字和人名等词汇，然后统计词频，最终表示为上面描述的向量。3.2 特征项的抽取构成文本的词汇，数量是相当大的，因此，表示文本的向量空间的维数也相当大，可以达到几万维，因此我们需要进行维数压缩的工作，这样做的目的主要有两个，第一，为了提高程序的效率，提高运行速度，第二，所有几万个词汇对文本分类的意义是不同的，一些通用的、各个类别都普遍存在的词汇对分类的贡献小，在某特定类中出现比重大而在其他类中出现比重小的词汇对文本分类的贡献大，为了提高分类精度，对于每一类，我们应去除那些表现力不强的词汇，筛选出针对该类的特征项集合，存在多种筛选特征项的算法，如下所列：1 根据词和类别的互信息量判断2 根据词熵判断3 根据KL距离判断在我们的系统中采用了词和类别的互信息量进行特征项抽取的判断标准，其算法过程如下所列：STEP ONE:初始情况下，该特征项集合包含所有该类中出现的词。STEP TWO:对于每个词，计算词和类别的互信息量 其中， 为 W 在 中出现的比重， 为该类的训练文本数， 为词 在 中的词频， 为总词数， 为该类所有词的词频和。而 同上面的计算公式相同，只是计算词在所有训练文本中的比重，其中， 为全体训练文本数。STEP THREE:对于该类中所有的词，依据上面计算的互信息量排序。STEP FOUR:抽取一定数量的词作为特征项，具体需要抽取多少维的特征项，目前无很好的解决方法，一般采用先定初始值，然后根据实验测试和统计结果确定最佳值，一般初始值定在几千左右。STEP FIVE:将每类中所有的训练文本，根据抽取的特征项，进行向量维数压缩，精简向量表示。其他抽取特征项的算法，除判断函数上有所差别，主要过程类似。3.3 训练方法与分类算法训练方法和分类算法是分类系统的核心部分，目前存在多种基于向量空间模型的训练算法和分类算法，例如，支持向量机算法、神经网络方法，最大平均熵方法，最近 K 邻居方法和贝叶斯方法等等，本文以下具体介绍三种分类算法：1. 简单向量距离分类法该方法的分类思路十分简单，根据算术平均为每类文本集生成一个代表该类的中心向量，然后在新文本来到时，确定新文本向量，计算该向量与每类中心向量间的距离（相似度），最后判定文本属于与文本距离最近的类，具体步骤如下：STEP ONE:计算每类文本集的中心向量，计算方法为所有训练文本向量简单的算术平均STEP TWO:新文本到来后，分词，将文本表示为特征向量STEP THREE:计算新文本特征向量和每类中心向量间的相似度，公式为：其中， 为新文本的特征向量， 为第 j 类的中心向量，M 为特征向量的维数， 为向量的第 K 维。STEP FOUR:比较每类中心向量与新文本的相似度，将文本分到相似度最大的那个类别中。2. 贝叶斯算法该算法的基本思路是计算文本属于类别的概率，文本属于类别的几率等于文本中每个词属于类别的几率的综合表达式，具体算法步骤如下：STEP ONE:计算特征词属于每个类别的几率向量，其中，计算公式与计算互信息量的公式相同STEP TWO:在新文本到达时，根据特征词分词，然后按下面的公式计算该文本 属于类 的几率： 其中， 为相似含义， 为类的总数， 为 在 中的词频，n 为特征词总数。STEP THREE:比较新文本属于所有类的几率，将文本分到几率最大的那个类别中。3. KNN（K 最近邻居）算法该算法的基本思路是：在给定新文本后，考虑在训练文本集中与该新文本距离最近（最相似）的 K 篇文本，根据这 K 篇文本所属的类别判定新文本所属的类别，具体的算法步骤如下：STEP ONE:根据特征项集合重新描述训练文本向量STEP TWO:在新文本到达后，根据特征词分词新文本，确定新文本的向量表示STEP THREE:在训练文本集中选出与新文本最相似的 K 个文本，计算公式为：其中，K 值的确定目前没有很好的方法，一般采用先定一个初始值，然后根据实验测试的结果调整 K 值，一般初始值定为几百到几千之间。STEP FOUR:在新文本的 K 个邻居中，依次计算每类的权重，计算公式如下：其中， 为新文本的特征向量， 为相似度计算公式，与上一步骤的计算公式相同，而 为类别属性函数，即，如果 属于类 ，那么函数值为 1，否则为 0。STEP FIVE:比较类的权重，将文本分到权重最大的那个类别中。除此以外，支持向量机和神经网络算法在文本分类系统中应用得也较为广泛，支持向量机的基本思想是使用简单的线形分类器划分样本空间。对于在当前特征空间中线形不可分的模式，则使用一个核函数把样本映射到一个高维空间中，使得样本能够线形可分。而神经网络算法采用感知算法进行分类。在这种模型中，分类知识被隐式地存储在连接的权值上，使用迭代算法来确定权值向量。当网络输出判别正确时，权值向量保持不变，否则进行增加或降低的调整，因此也称为奖惩法。3.4 阈值的确定上面的算法都是将新文本归于分类体系中的一个类，即与该文本关联最大的类，而事实上，分类体系中的类别不是完全互斥的，存在这样一些既属于其中一个类别，又同时属于其他类别的文本，对于这种文本，上述的分类算法无法确定文本所属的所有类别。因此，需要对每个类别确定阈值，当文本在该类的阈值之上时，就将文本归于该类中。但是，阈值的确定是十分困难的，理论上，没有很好的解决方法，一般采用预定初始值，然后给出测试文本，使用分类器进行分类，再根据分类的准确程度调整初始值，这样的方法有两个缺点，首先，初始值的确定不容易，完全是根据经验或简单的测试而定，其次，调整的幅度无法确定，当初始值过高或过低需要增减时，增减的幅度无法很好的确定，只能反复测试，反复调整，这样就大大地增加了工作量。而且，一个分类系统的阈值由于测试文本的不同也无法完全应用于另一个分类系统中。我们在系统中考虑了一种确定阈值的方法，称为百分比阈值确定法，它的基本思想是：首先依据上述训练算法和分类算法构造分类器，然后对于要确定阈值的类，用分类器分类该类中所有的训练文本，从而每个文本都得到一个相关的值，以上述算法为例：简单向量距离分类法：文本与本类中心向量间的相似度值贝叶斯算法：文本归属于类的几率KNN 算法：K 个邻居中的类权重然后按递减顺序排列所有本类训练文本得到的值，假定本类有 n 篇文本，那么这些文本的值为 ，那么本类阈值 y 确定如下：其中，s 为初始值，根据训练文本的质量程度，可以确定为 80 或更高，这样就确定了本类的初始阈值，可以想象，S 越大，该分类器的查全率就越高，准确度就越低，相反地，S 越小，查全率就越低，准确率就越高，然后根据测试进行调整。相应地，调整阈值可以转化为调整 s 值，如果对查全率满意而对准确率不满意，那么可以减少 s 值，否则就增加 s 值。4 系统的结构框架我们实现的文本分类系统，研究并结合了上述的关键技术，其结构如下图所示：新文本预处理训练文本预处理特征项抽取训练文本再处理构造分类器训练过程分类过程分类和输出在构造分类器模块中，我们实现了上述的三种训练算法和分类算法，并对其效率和结果进行了一定的比较和测试。5 测试数据和实验结果我们在一个具有2830篇中文文本的语料库上测试我们系统实现的分类算法，并对其效率和结果进行比较分析。语料库中的文本都是新闻电讯稿，绝大部分采自新华社，还有200余篇采自中国新闻社和人民日报。所有的新闻稿都由领域专家事先进行分类，按照中图分类法分成政治、经济、军事等共38类。我们选择训练集和测试集的方法如下：将这些分好类的语料平均分成十份，选择其中一份作为开放测试集，剩余的九份作为训练集和封闭测试集。这样每一份都依次轮流作为开放测试集，运行分类算法，共执行10次分类操作，计算其平均值，实验结果如下表所示：算法封闭测试查全率封闭测试准确率封闭测试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%KNN89.11%91.42%90.25%83.29%85.12%84.20%另外，从算法的时间花费考虑，假设系统的训练文本集包括 m 篇文本（向量），分别属于 k 个类，而抽取的特征项为 n 维，则这三种算法的时间花费分别为：算法训练算法分类过程简单向量距离O (mn) O (kn)贝叶斯O (mn) O (kn)KNN无O (km+nm)因此，从测试结果看来，KNN 算法在分类效果上是最佳的，同时在训练过程中投入的时间最少，但是在分类过程中花费的时间最多，不利于文本的实时处理；而贝叶斯算法和简单向量距离算法的时间花费近似，其分类效果也近似，简单距离算法的效果略好。6 将来的工作今后，我们在文本分类方向上的研究工作主要围绕三个方面展开：1. 在向量空间模型方面，结合计算语言学，使用概念空间代替词空间；2. 目前的分类体系为平面体系，可以在层次分类体系中考虑文本分类系统；3. 新算法的研究及旧算法的改进7 结束语本文探讨了文本分类系统的关键技术，比较和分析了三种训练和分类算法，并提出了文本分类系统的结构模型，同时给出了实验结果和分析，将来还将继续在层次分类体系中进行文本分类系统的进一步研究。参考文献1. David D. Lewis: Feature selection and feature extraction for text categorization, In Proceedings of Speech and Natural Language Workshop, pp 212-217. Defense Advanced Research Projects Agency, Morgan Kaufmann, February 19922. Yiming Yang: An evaluation of statistical approaches to text categorization, In Journal of Information Retrieval, 1999, Vol 1, No. 1/2, pp 67-883. David D. Lewis and Marc Ringuette: A comparison of tow learning algorithms of text categorization , In Third Annual Symposium on Document Analysis and Information Retrieval, pp 81-93, Las Vegas, NV, April 11-13 1994. ISRI; Univ. of Nevada, Las Vegas4. Andrew McCallum and Kamal Nigam: A comparison