毕业设计（论文）-基于半监督的文本分类算法.doc

文本分类算法毕业论文学 院： 专 业： 电子信息科学与技术 论文题目： 基于半监督的文本分类算法 摘 要随着Internet的出现，大量的文字信息开始以计算机可读的形式存在，以传统的手工方式对这些信息进行组织整理既费时费力且效果不理想。文本分类作为处理和组织大量文本数据的关键技术，可以利用机器来对文本进行分析整理，使用户从繁琐的文档处理工作中解放出来，并能极大地提高了信息的利用率。文本分类是指分析文本内容并按一定的策略把文本归入一个或多个合适的类别的应用技术。而作为信息过滤、信息检索、搜索引擎、文本数据库、数字化图书馆等领域的技术基础，文本分类技术有着广泛的应用前景。本文首先介绍了文本分类的背景，文本分类所用的半监督算法及文本分类的几个关键技术。然后鉴于高分类精度需要大规模己标记训练集而已标记文档缺乏，利用未标识文档进行学习的半监督学习算法己成为文本分类的研究重点这一情况，着重研究了半监督分类算法。最后本文设计了一个文本分类原型系统，为保证分类的准确性，采用了不同的标准数据集进行测试，并评价了其分类的性能。通过以上实验表明，当有足够的己标识文档时，本算法与其它算法性能相当，但当已标识文档很少时，本算法优于现有的其它算法。关键词:文本分类；半监督学习；聚类；EM；KNNABSTRACTWith the emergence of Internet, a large number of text messages began to exist in the form of computer-readable, to the traditional manual way for organizations to collate the information is time-consuming effort and the result is not satisfactory. As the key technology in organizing and processing large mount of document data, Text classification can use the machine to collate the text analysis, allowing users from the tedious work of document processing liberated and can greatly improve the utilization of information. Text classification is a supervised leaning task of assigning natural language text documents to one or more predefined categories or classes according to their contents. Moreover, text classification has the broad applied future as the technical basis of information filtering, information retrieval, search engine, text database, and digital library and so on.This thesis firstly introduces the background of the text classification, text classification using semi-supervised algorithm and a few key technologies about text classification. Secondly considering the contradiction of deadly need for large labeled train-set to obtain high classification accuracy and the scarcity of labeled documents，this thesis emphasizes on improvement of Semi-supervised classification algorithms， Finally we design a document classification system. In order to ensure the accuracy of classification, using a data set different standards for texting and evaluation of the performance of their classification. The experiments above showed the superior performance of our method over existing methods when labeled data size is extremely small. When there is sufficient labeled data，our method is comparable to other existing algorithms. Keywords: text classification; semi-supervised leaning; clustering; EM; KNN目 录1 引言11.1课题背景11.2本文的内容组织22 半监督学习32.1半监督学习的概念及意义32.2半监督学习的研究进展42.3半监督学习的方法52.3.1协同训练(Co-training)52.3.2自训练62.3.3半监督支持向量机（S3VMs）72.3.4基于图的方法（Graph-Based Methods）82.4本章小结93 文本分类103.1文本分类的概念及意义103.2文本分类的国内外研究情况103.3文本分类的关键技术113.3.1文本特征生成123.3.2特征选择与降维143.3.3权重计算163.3.4文本分类技术173.3.5文本分类技术性能评价223.4本章小结254 基于EM和KNN的半监督文本分类274.1引言274.2相关工作274.2.1聚类分析274.2.2 EM算法304.2.3 KNN算法314.3基于EM和KNN的半监督文本分类算法314.3.1问题描述324.3.2算法思想324.3.3基于EM算法的聚类分析334.3.4基于Knn算法的分类354.3.5算法步骤364.4算法效率分析374.5本章小结385 实验与分析395.1实现EM-KNN算法395.1.1实验平台395.1.2算法实现及流程图395.2实验结果与分析435.3小结43总结44参考文献45翻译部分48英文原文48中文译文54致 谢61中国矿业大学2009届本科毕业设计（论文） 第65页1 引言1.1课题背景随着信息技术的发展，互联网数据及资源呈现海量特征，而且，越来越多的信息以电子文本的形式存在。统计表明，目前网页的数量呈指数型增长，平均每年增加一倍。截至2006年，全球每年制造、复制出的数字信息量共计1610亿GB，这大约是有史以来出版的图书信息总量的300万倍。为了有效地管理和利用这些分布式的海量信息，基于内容的信息检索和数据挖掘逐渐成为备受关注的领域。其中，文本分类(TextClassification)技术是信息检索和文本挖掘的重要基础。文本分类在自然语言处理、信息组织与管理、内容信息过滤等领域都有着广泛的应用。因为文本分类可以极大地增强人们对海量信息的处理能力，早在上世纪中叶，有关文本分类的研究就已经开展起来。早在1957年，美国IBM公司的HPLuhn在自动分类领域最先进行了开创性的研究，提出了词频统计思想用于自动分类。1960年，MEMaron在Journal of ACM上发表了有关自动分类的第一篇文章On Relevance Probabilistic Indexing and Information Retrieva1，提出了自动关键词分类技术，正式宣告了自动分类技术的诞生。1从20世纪60年代起步至80年代末，文本分类主要是以专家人工构建的知识工程技术为支撑，具有代表性的是卡内基集团为路透社开发的新闻自动分类系统(Construe System)。基于知识工程的分类系统具有较好的分类效果，但无法移植，需要大量领域专家的参与。从20世纪9O年代开始，随着机器学习技术的不断进步和发展，为自动文本分类器的出现奠定了基础3。基于机器学习的文本分类方法，更注重分类器的模型自动挖掘和生成及动态优化能力，在分类效果和灵活性上都比之前基于知识工程和专家系统的文本分类模式有较大的提高与进步。从预先经人工正确分类的训练文本集合中学习类别的特征信息，根据算法生成分类器。这种分类方法适应性强，方便移植，不需要行业专家的介入。从此以后，文本分类器处理海量信息的能力逐步受到IT业和广大用户的赏识，开始发挥越来越大的社会与经济效益。例如，虽然各种搜索引擎部分地解决了Web上的资源发现问题，但由于搜索引擎存在着信息相关度差、精确度不高等原因，效果远不能使人满意；同时，搜索引擎的目的在于发现Web上的资源，就Web上的知识发现而言，即使检索精确度再高也无法胜任。为此，我们需要开发比搜索引擎信息检索技术更高层次的新技术。Web文本挖掘技术包括Web网页文本内容的挖掘及结构挖掘。Web文本挖掘技术可以同搜索引擎、信息推送、信息过滤等信息处理技术相结合，有效地提高了信息服务的质量。13不可否认，上世纪90年代以来，文本分类技术取得了很大的进步，取得了值得称道的喜人成绩。随着时代的进步，互联网中分布传播的海量电子化文本数量呈几何级数增长，文本之间的关系也越来越复杂；同时，人们对分类效果评估指标（如查全率和查准率）的要求也越来越高，传统的机器学习技术已经呈现“老态”。在机器学习领域，分类属于监督学习。绝大数的有监督的机器学习方法依赖于标注的训练样本集，忽略了未标注样本的作用，利用大规模的标注过的训练数据固然可以提高学习算法结果的准确度，但是标记必须由人手工完成，这是一项费时费力的工作，己经不能适应Internet网上信息的增长速度。同时，网上存在大量容易获得的未标识数据资源，半监督学习算法就是利用这些未标注样本，在传统的机器学习方法中结合未标注样本进行学习的算法。无疑它将在一定程度上提高学习算法的性能。1.2本文的内容组织本文首先介绍半监督和文本分类的一些相关知识，然后提出了一种基于EM和KNN的半监督文本分类算法，给出了算法的思想和步骤，并对其性能进行了测试分析。最后，给出了系统的实验和分析结果。全文共分五章，具体安排如下：第一章是引言，介绍本文研究背景；第二章是半监督学习，介绍关于半监督的一些相关知识；第三章是文本分类，介绍文本分类的一些基本知识及文本分类的关键技术；第四章是基于EM和KNN的半监督文本分类算法，提出了一种基于EM和Knn的半监督文本分类算法，并分析了算法运行的效率；第五章是实验与分析，首先用C语言实现本文算法的过程，然后通过标准数据集的实验验证和分析了本文算法的有效性。总结部分对本文的工作进行了总结，并指出了进一步需要开展的工作。2 半监督学习2.1半监督学习的概念及意义半监督学习是相对于监督学习和无监督学习提出来的，其介于监督学习和无监督学习之间。监督学习通过具有标记的训练示例进行学习，以尽可能正确地对训练集之外的示例标记进行预测。无监督学习通过对没有标记的训练示例进行学习，以发现训练示例中隐藏的结构性知识。所谓的“标记”是指示例所对应的输出，在分类问题中标记就是示例的类别，通常想要获得有标记的训练示例是很困难的，或者是费时耗力的，因为要标记它们需要使用人类的经验进行人工的干预。然而，未标记的数据能够很容易就被收集到，但却没有方法使用它们。半监督学习通过使用大量的未标记的数据，用以辅助标记的数据，建立更好的分类器。半监督学习除了提供给学习算法未标记的数据，还要提供给学习算法一些监督信息。211半监督学习的基本设置是给定一个来自某未知分布的有标记示例集以及一个未标记示例集，期望学得函数可以准确地对示例 预测其标记。这里均为维向量，为示例的标记，|和|分别为和的大小，即它们所包含的示例数。半监督学习是模式识别和机器学习中的重要研究领域。近几年随着机器学习理论在数据分析和数据挖掘的实际问题，例如网页检索和文本分类，基于生物特征的身份识别，图像检索和视频检索，医学数据处理等问题中的广泛应用，半监督学习在理论和实际应用研究中都获得了长足的发展。半监督学习研究主要关注当训练数据的部分信息缺失的情况下，如何获得具有良好性能和推广能力的学习机器，这里的信息缺失涵盖数据的类别标签缺失或者存在噪声，数据的部分特征维缺失等多种情况。半监督学习的理论研究对于我们深入理解机器学习中的许多重要理论问题，例如数据的流形与数据的类别信息的关系，缺失数据的合理处理，标注数据的有效利用，监督学习和非监督学习之间的联系，主动学习算法的设计等都有非常重要的指导意义。112.2半监督学习的研究进展半监督学习(Semi-supervised Learning)是模式识别和机器学习中的重要研究领域。近几年随着机器学习理论在数据分析和数据挖掘的实际问题，例如网页检索和文本分类，基于生物特征的身份识别，图像检索和视频检索，医学数据处理等问题中的广泛应用，半监督学习在理论和实际应用研究中都获得了长足的发展。自20世纪八九十年代以来国际机器学习界研究者在半监督学习研究领域展开了广泛深入的探讨和研究。其涵盖的范围非常广泛，例如半监督回归问题；利用标签和特征维都缺失的数据集进行学习；标签有噪声时的数据处理；利用少量正样本和大量未标注数据进行学习以及对于大量未标注数据中已知只存在少量正样本的情况下对于正样本进行检测；对各种监督学习算法进行修改，探讨如何融入非监督数据信息或者对于非监督学习算法进行修改，探讨监督数据信息的引入；利用有限混合模型对于数据的概率分布进行建模或者利用其他模型对于数据标签关于特征维的条件概率进行建模，利用EM算法学习模型参数的半监督学习的研究；引入合适的数学方法进行半监督学习，例如基于核矩阵的谱的分析，高斯随机场的利用，利用图论中的方法来对于样本集进行聚类分析；半监督数据的流形分析等。研究者同时开展了将半监督学习和传统模式识别和机器学习中的一些问题相结合的研究，例如基于半监督学习的特征提取，半监督学习和集分类器的设计等。国际研究者同时开展了与半监督学习有着密切关联的一些相关研究，具有代表性的是利用半监督数据和数据的不同特征维子集在数据的不同视图上同时训练具有良好性能的学习机器。2半监督学习研究正在继续从广度和深度上不断进行扩展，但是依然存在很多问题。一方面半监督学习的前提：聚类假设的数学分析依然不是十分完善，另一方面不同的监督和非监督算法的半监督修改版本依然存在相当多的问题，有的因计算量太大受到问题规模的限制，有的是因为缺乏理论依据只是技术上的设计，有的是因为模型参数过多非常容易陷入局部极值等等。另外半监督学习中如何更加有效利用标注数据的标签信息和未标注数据的分布或者流形信息依然没有得到很好的解决。半监督学习实际应用的研究随着许多实际领域需要分析和利用半监督数据集广泛开展起来。第一个问题涉及到聚类假设的合理性。主要探讨的问题是在欧氏空间聚集程度比较高的地方，也就是比较大的地方，变化一定很平缓的假设的合理性。数据的标签信息可以调整样本之间的相似性度量，那么在特定的核空间讨论和的关系或者说在核空间讨论聚类假设会更加合理。显然是与问题相关的，在实验中，可以设计均匀的地方变化比较大或者存在梯度的人工仿真数据集合，这时如果利用聚类假设进行半监督学习应当在特定的核空间才能进行。分析如何利用监督数据信息设计合适的核空间以进行半监督学习，讨论和的关系对于半监督学习机理中的聚类假设的分析有着很重要的理论研究意义。第二个问题是如何将监督信息中的等约束和不等约束（Side-information）8引入更多的半监督学习算法。半监督学习的本质是在给出半监督学习模型以及优化目标后，对模型参数求解，其中监督信息就是这些约束。目前，已经有一些基于这些约束的算法，例如相关成分分析（Relevant ComponentAnalysis）9，这些方法在实际的分类问题中，获得了很好的性能。那么，如果有效利用各种类型的监督信息设计不同类型的半监督学习模型依然是开放性的问题。2.3半监督学习的方法根据半监督学习算法的工作方式，可以大致将现有的很多半监督学习算法分为三大类。第一类算法以生成式模型为分类器；第二类算法是基于图正则化框架的半监督学习算法；第三类算法是协同训练算法。而主要的半监督算法有：EM算法、S3VMs、自训练、协同训练、基于图的方法等。由于在后文中会对EM算法有详细介绍，故在此将不作介绍。2.3.1协同训练(Co-training)Co-Training方法3通过把特征集分为两个独立部分并分别在各个特征空间下用己标记数据训练分类器，再用分类器来分类未标记数据，挑出最确定的正例和反例加到标记例子中，两个分类器针对增大的标记例子集合重新训练，该过程重复执行。以网页为例，网页本身存在两种特征，一种特征是出现在网页上的单词，另一种特征是指向网页链接上的单词。联合训练通过NB（Naive Bayes）分类器训练两种不同特征生成的单词，由此建立两个内嵌的分类器A和B，利用已标记文档，A用网页特征的单词训练，B用链接特征的单词训练。然后，对于未标记文档，A和B分别以最大后验概率选出评分最高的文档，标记类别并一起加入己标记训练集，再如此逐次标记所有未标记文档，由此得到扩大后的训练集。然后利用此训练集集合某种分类器再进行分类。重复执行。实验结果表明，利用联合训练得到的训练集进行文本分类，平均分类错误率比EM-NB方法要低，性能比较稳定。文献5分析了联合训练算法优于EM-NB的三个主要原因:原因之一是前者利用了网页文档的两种结构信息进行联合训练;原因之二是它将两个用NB分类算法建立的分类器作为内嵌的分类器训练数据，从而降低了NB假设条件的影响;另一原因则是前者采用了增量训练未标记文档的方法，即在训练分类器时，每次对未标记文档只选出分值最高的部分文档标记其类别，加入已标记文档训练集中。而EM技术则是在每次迭代中，对每篇未标记文档都标记一个临时类别，直到迭代收敛。但联合训练算法不适用于自身没有多重特征的文档(比如纯文本文件)，而且很多类型的文档不易切分特征。多种资源数据也不易统一切分特征属性，在某些领域(如自然语言)，联合训练算法也存在许多局限67。2.3.2自训练自训练是半监督学习的常用技术，在自训练中，分类器首先用少量有标记的数据训练。然后分类器用于对未标记的数据进行分类。典型地，最先确定的未标记数据点，连同其预测的标记，都被添加到训练集。然后分类器重新训练并且重复上述过程。分类器采用其自身的预测以训练自己，这个过程也称为自教，或自举。这种方法来源于人类在没有直接老师的情况下，对自己以前的经历进行自学习，半监督学习中的自训练即是自动地对未标记的数据进行标记，自训练是一个迭代地对自身进行预测并且迭代地训练分类器的过程。在这个信息爆炸的时代，自训练技术具有天然的优势：训练过程的完全自动化，手工标记样本引入的人为误差可以避免，训练样本按需产生，训练过程简单高效。生成式模型以及EM方法可看成是“软”自训练的特例。可以想象一个分类错误可以加强其自身。如果预测的可信任度降低到某个门槛值，一些算法试图避免这一点通过“忘掉”未标记的数据点。11自训练已经被应用于几个自然语言处理的工作。Yarowsky使用自训练用于词义消歧。Riloff等人使用自训练辨别主观名词。自训练还用于语法分析和机器翻译。自训练是一种封装算法，一般来说很难进行分析。2.3.3半监督支持向量机（S3VMs）半监督支持向量机（Semi-Supervised SVMs）本来被称为直推式支持向量机（TSVM），之所以现在称为半监督支持向量机是因为它们也适用于归纳，而不仅仅是直推。其思想很简单，即在低密度区找到一条决策边界。但是，其背后的优化问题是困难的。11TSVM通过把边界置于低密度区域建立了和判别式决策边界之间的联系。TSVM是一种使用未标记数据的标准的支持向量机的扩展。标准的支持向量机只使用有标记的数据，目标是在再生核希耳伯特空（Reproducing Kernel Hilbert Space）找到最大边缘的线性边界。在TSVM中未标记的数据也被使用，目标是找到未标记数据的一个标记，以便一个线性边界在原始数据和未标记数据之间有最大边缘。由于判别式方法直接利用类条件概率，在参数估计迭代过程中可能会偏离，而直推式支持向量机通过引导决策边界远离稠密区的方法建立决策边界与间的联系，因而成为一种克服这一问题的较好选择。尽管找到精确的TSVM解是NP完全问题，但一些近似的方法已经提出并有积极的效果23。由于成功地把无标记样本中所隐含的分布信息引入了支持向量机的学习过程中，TSVM算法比单纯使用有标记样本训练得到的分类器在性能上有了显著提高。但该算法在执行前必须人为指定待训练的无标记样本中的正标记样本数，而值一般是很难准确地估计的，在TSVM算法中采用了一种简单的方法，即根据有标记样本中的正标记样本所占比例来估计无标记样本中的正标记样本比例，进而估计出值。可以看出，这种估计是有问题的，尤其是有标记样本较少的情况下，一旦估计不正确，将会导致较差的结果。对这个问题，陈毅松等提出了一种改进算法渐进直推式支持向量机（Progressive Transductive Support Vector Machine, PTSVM）24，该算法通过成对标记和标记重置的办法改进了TSVM的性能，但只适合于无标记样本较少的情况，样本较多时，这种频繁的标记与标记重置将导致算法的复杂性迅速增加，并且远超过一般的TSVM算法。现实应用的大多数情况是无标记样本远多于标记样本, 因而需要开发适应于这种情况的相应算法。钟清流等提出了一种渐近式半监督学习算法25, 它采用的特定取样规则和核参数可以确保减少误标记数量并控制决策面的动态调节进程，通过删除非支持向量来提高训练速度。实验表明, 这种算法能够适应不同的样本分布情况, 并取得较好的效果, 是一种值得关注的新尝试。2.3.4基于图的方法（Graph-Based Methods）这曾经是半监督学习研究最活跃的领域。基于图的半监督方法定义了一个图，这个图的各个节点表示有标记的和未标记的数据，图的边则反映了数据间的相似度，这些方法通常假定标记在图上的平滑性。图方法是非参量的、判别的、直推式的。基于图的方法建立在流行假设上。图的正规化：许多基于图的方法可被视作估算一个在图上的函数，需要同时满足两个条件：（1） 其应该接近于给定的在已标记的节点的标记；（2） 其应在整个图上是平滑的。这是个正规化的框架，第一阶段是一个损失函数，第二阶段是一个正规化因子。当前有许多种基于图的方法，它们都是相似的。重要的是怎麽构造一个好的图，然而对于如何构造图的研究还不够成熟。大多数图方法通过利用图的拉普拉斯算子来涉及到图。用表示一个图，其边权重为。边的权重我指示出数据间的相似度。图的权重矩阵表示为：由定义的对角阵称为的度矩阵。现在有多种方法来定义图的拉普拉斯算子，较为著名的有：规范化图的拉普拉斯算子，未规范化图的拉普拉斯算子，分别表示为：通常预测由未标记节点的标记组成。因此，这种算法本质上时直推式的，也就是说，其只返回在未标记数据点上决策函数的值，而不是决策函数本身的值。图的信息传播也能有助于改进一个给定的考虑未标记的数据的分类。通常图是由计算机目标的相似性而构成的，例如在欧几里得数据点上使用核函数。但有时源数据已经具有图的形式。2.4本章小结本章对于半监督的概念、研究意义、研究进展以及半监督学习方法进行了分析和讨论，重点讨论了半监督学习常用的几种方法，并且重点放在半监督分类上。3 文本分类3.1文本分类的概念及意义Internet信息量的迅猛增加，增加了人们获取有效信息的难度，而且信息产生的速度远远超过人们收集信息、利用信息的速度，使得人们无法快速地查找到最新的信息，从而造成了时间、资金和精力的巨大浪费。面对网上海量的信息，传统的做法是对网上信息进行人工分类，并加以组织和整理，从而为人们提供一种相对有效的信息获取手段。但是，这种人工分类的做法存在着许多弊端，不仅耗费大量的人力、物力和财力，而且存在着分类性能不佳的问题。因此，如何有效的组织和管理数据，方便人们的检索?如何区分有用的信息和无用信息?如何从海量的数据中高效地获取有用知识?如何满足用户的个性化需求?所有这些都成了人们亟待解决的问题。文本分类是指按照预先定义的分类体系，根据文本内容自动地将文本集合的每个文本归入某个类别，系统的输入是需要进行分类处理的大量文本，而系统的输出是与文本关联的类别。简单地说，文本分类就是对文档标以合适的类标签。从数学的角度来看，文本分类是一个映射过程，它将未标明类别的文本映射到现有类别中，该映射可以是一一映射，也可以是一对多映射，因为通常一篇文本可以与多个类别相关联。文本分类的映射规则是，系统根据已知类别中若干样本的数据信息总结出分类的规律性，建立类别判别公式和判别规则。当遇到新文本时，根据总结出的类别判别规则确定文本所属的类别。在理论研究方面，对单类别分类的研究要远远多于对多类别分类的研究。主要是由于单类别分类算法可以非常容易地转化成多类别分类算法，不过这种方法有一个假设条件，即各个类之间是独立的，没有相互依存关系或其它影响，当然在实际应用中，绝大多数情况是可以满足此假设条件的。因此，在文本分类的研究中，大部分实验都是基于单类别分类问题的探讨。3.2文本分类的国内外研究情况国外自动分类研究始于1950年代末，H.P.Luhn在这一领域进行了开创性的研究，他首先将词频统计的思想用于文本分类中。1960年Maron在Journal of ASM上发表了有关自动分类的第一篇论文“On relevance probabilitic indexing and informarion retriral。 1962年博科(H.Borko)等人提出了利用因子分析法进行文献的自动分类。其后许多学者在这一领域进行了卓有成效的研究。国外的自动分类研究大体上可以分为三个阶段:第一阶段（1958年-1964年)主要进行自动分类的可行性研究;第二阶段(1965年-1974年)，自动分类的实验研究;第三阶段(1975年-至今)，自动分类的实用化阶段。26国外当前流行的文本分类方法有Rocchio法及其变异方法、k近邻法（KNN)、决策树、朴素贝叶斯、贝叶斯网络、支持向量机(SVM)等方法。这些方法在英文以及欧洲语种文本自动分类上有广泛的研究，而且很多研究表明KNN和SVM是英文文本分类的最好方法。国外很多研究人员对英文文本分类领域的各个问题都有相当深入的研究，对几种流行的方法进行了大量的对比研究。Susan Dumais等学者对这5种方法进行了专门的比较研究。国内自动分类研究起步较晚，始于20世纪80年代初期。1981年侯汉清对计算机在文献分类工作中的应用作了探讨27，并介绍了国外在计算机管理分类表、计算机分类检索、计算机自动分类、计算机编制分类表等方面的概况。我国自动分类的研究大体上正在经历从可行性探讨-辅助分类-自动分类系统的发展阶段。关于中文文本分类的研究相对较少，国内外的研究基本上是在英文文本分类研究的基础上采取相应策略，结合中文文本的特定知识，然后应用于中文之上，继而形成中文文本自动分类研究体系。国内外的很多学者在基于知识和统计的两种方法上对中文文本分类进行了大量的研究工作，主要有基于词典的自动分类系统和基于专家系统的分类系统。如上海交通大学、中国科学院、清华大学、北京大学、北京信息工程学院、复旦大学、东北大学、山西大学以及新加坡、香港和台湾的一些大学都有相应的研究成果，也研制出了不少的实验系统。3.3文本分类的关键技术一般的自动文本分类有以下几个阶段10，具体如图3-1所示。(1) 生成训练语料库的文本特征全集；(2) 文本特征提取，形成特征子集；(3) 采用某种数学模型和分类方法进行分类器构造；(4) 利用训练语料库中的文本对分类器进行训练，得到分类器的相关参数。训练文本采集及处理特征提取/文本表示特征空间降维构造分类器分类和输出新文本预处理训练过程分类过程图3-1 文本分类过程26 由图3-1所示及上述的文本分类的几个阶段，可以看出文本分类过程所需要的几个关键技术，现下面开始介绍文本分类的关键技术。3.3.1文本特征生成在当前的计算机技术的研究水平下，机器还不可能识别自然文本，从根本上说，它只认识0和1，所以必须将文本转换为计算机可以识别的形式。而要想让计算机“读懂”文本，必须能够找到用于文本表示的数学模型。随着信息检索技术的发展，逐渐发展起来的主要有三个文本检索模型，分别是:布尔模型10 (Boolean Model，BM)、向量空间模型1213(Vector Space Model，VSM)和概率模型 (Probabilistic Model，PM)，这些模型从不同角度使用不同的方法处理特征加权、类别学习和相似度计算等问题，而最经典、最实用的是向量空间模型，本文的研究是建立在向量空间模型之上的。向量空间模型是由Salton在20世纪60年代末提出的，它最早应用于信息检索领域，例如著名的SMART(System for the Manipulation and Retrieval of Text)系统就成功的应用了向量空间模型技术，后来又在文本分类领域得到了广泛的应用。向量空间模型的基于两个基本假设，一是文档所属的类别仅与某些特定的词或词组在该文档中出现的频数有关，而与词或词组在文档中出现的位置或顺序无关;二是假设文档的各特征词之间是相互独立的。这样，只需要提取出一份文档中蕴涵的各个特征词的词频信息就可以对其进行正确的分类。向量空间是由一组线性无关的基本向量组成，向量维数与向量空间维数一致，并可以通过向量空间进行描述。下面介绍文档向量空间的一些基本概念:文本:泛指一般的文献或文献中的片段(段落、句子或句子组)，一般指一篇文章(假设文档中不包含除文字以外的其他多媒体信息)。特征项:文本的内容特征常常用它所含有的基本语言单位(字、词、词组或短语)来表示，一般中文中使用词语作为文本的特征项。特征项的权重:对于含有个特征项的文本，常用一定的权重表示特征项在文本中的重要程度。即把文本表示为，特征词表示为，特征词的权重表示为。这样自然语言形式的文本文档就可以在向量空间中完全由特征向量来表示。对两个文本试和之间的内容相关程度的度量被称为相似度，可以用如下公式计算： （3-1） tktitj图 3-2 文本的向量空间模型及文本间的相似度 其中，为特征向量的维数，表示第个文本的第个特征项的权重值。向量空间模型的主要优点在于:(l)标引词加权改进了检索效果;(2)其部分匹配策略允许检出与查询条件相接近的文献;(3)利用余弦公式，根据待测文献与训练文献之间的相似度对其进行排序。与其他的检索模型相比，向量空间模型简单、便捷，而且分类性能也非常好，已成为当今最流行的检索模型。3.3.2特征选择与降维实现文本自动分类的基本困难之一是特征项空间的维数过高。数量过大的特征项一方面导致分类算法的代价过高，另一方面导致无法准确地提取文档的类别信息，造成分类效果不佳。因此，需要在不牺牲分类质量的前提下尽可能地降低特征项空间的维数。特征选择的任务就是要将信息量小，“不重要”的词汇从特征项空间中删除，从而减少特征项的个数，它是文本自动分类系统中的一个关键步骤。常用的文本特征选择方法有:文档频率()、信息增益()、互信息()、统计量()，文本证据权，优势率，统计()等。这些方法都是基于阈值的统计方法，它们的基本思想都是对每一个特征计算某种统计度量值，然后设定一个闽值，把度量值小于阈值的那些特征过滤掉，剩下的即认为是有效特征。1、文档频率文档频率(Document Frequency)，就是文档集合中出现某个特征项的文档数目。在特征项选择中，计算每个特征项在训练集合中出现的频率，根据预先设定的阂值排除那些文档频率特别低和特别高的特征项。文档频率的计算复杂度较低，随训练集的增加而线性增加，能够适用于大规模语料，因此是特征降维的常用方法。其基本原则是:很少出现的特征对分类价值极小，对整个分类系统的效果影响也很小，因此，将这些特征去掉有助于降低特征空间维数，并且当这些不常出现的特征为噪音时，还会有助于提高分类正确率。但在信息检索领域，文档频率较低的特征项被认为是信息含量较高，与文本分类中的原则是相反的。2、信息增益信息增益(Information Gain)，是一种在机器学习领域应用较为广泛的特征选择方法。它从信息论角度出发，用各个特征取值情况来划分学习样本空间，根据所获取信息增益的多寡，来选择相应的特征。其计算公式如下: （3-2）其中，表示文本中出现单词时，文本属于的概率；同样表示文中不出现单词时文本属于的概率; 表示类文本在语料中现的概率; 表示在整个文本训练集中出现的概率。3、 互信息互信息方法(Mutual Information)，可以度量特征项和类别的共现关系，特征项对于类别的互信息越大，说明特征中包含的与类别有关的鉴别信息就越多。因此，互信息衡量的是词与类之间的相关程度。文本分类中，一个特征词只有一个信息增益和文档频率，但拥有的互信息数目却是与训练语料中类别的数目相同的，对应于每个类，该特征词都会有一个互信息值。一个词可以对应几个互信息值，一般来说，因为我们的目的是选出对分类比较有用的词，所以通常根据每个词最大的互信息值来排序，然后从高到低选择特征词或者设定一个阈值排除那些互信息值比较低的词。假设文档集合分为类，记为，特征项对于文档类别的互信息 (，)的计算公式如下: （3-3）其中 (，)为特征项出现在类中的概率， (，)为特征项在所有文档中的出现概率。4、统计使用衡量特征项的重要程度时，只考虑到了正相关对特征项重要程度的影响。如果特征项和类别反相关，就说明含有特征项的文档不属于的概率要大一些，这对于判断一篇文档是否不属于类别也是很有指导意义的。为克服这个缺陷，使用以下公式计算特征项和类别的相关性: （3-4）其中: 为和同时出现的次数; 为出现而没有出现的次数。为出现而没有出现的次数; 为和同时没有出现的次数。为训练集中的文档数。和类似，如果和不相关，则 (，)值为0，因为在这种情况下，个训练文本的数目应该在这四种文本中均匀分布，即=。而另一个极端，词与类别非常相关，体现在这四个数量上，就是词出现的文本属于类别，而词不出现的文本不属于类别。这样的话，=/2，而=。在衡量词和类别之间的相关关系上，互信息和统计量之间有一定的相似之处。这两个向量间的不同之处在于互信息是一个非规格化的值，其取值范围很大，特别是对于那些边缘概率分布很小的情况。而统计量则是一个规格化的量。对于词，我们可以采用两种方法来求取其在训练集上的统计量值： （3-5）或是： （3-6） 同相同，如果有个类，每个就会有个值，取它们的平均，就能得到特征选取所需的一个线性序列。平均值大的特征优先被选取。算法的计算复杂度也为。5、 特征权方法基于术语在邻近相关文档中出现的频率来测试术语的强度。和是任意不同但相关的文档，术语的权值可由下式计算出: （3-7）但是实际中发现某些值很低的特征反而是信息量比较高的，不能从特征空间中删去，因此这种方法在某些情况下不可靠。以上介绍了五种常用的特征选择方法，它们具有的共同优势是计算量相对较小，而且结果特征集的解释性强，就是原来特征词集的子集，但是它们一些方面还需改进，比如分类器的特征集包含很多冗余的信息，同义词、多义词都能造成这种情况;一个词单独可能对分类器的作用不大，选择时被删去，但和其它一些词结合却是很好的辨别因素等等。 3.3.3权重计算特征项选择出来后，要对每个项赋予权重，应使文本中越重要的项的权重越大。目前最普遍的赋权重的方法是运用统计方法，即用文本的统计信息，主要是词频，来计算特征项的权重。下面对常用的加权函数进行详细介绍。1、 布尔权重布尔权重是最简单的一种加权方法，如果特征词出现次数为0，则其权重为0，如果特征词出现词数大于0，则其权重为1。公式如下: （3-8）其中表示特征词在文档中的权重，表示特征词在文档中出现次数。2、 词频权重该方法将特征词的频次作为权重。公式如下： （3-9）3、 -权重该方法基于以下两点原因:一是特征词在文档中出现词数越多越重要，权重和成正比;二是文档集中含有特征词的文档数越大越不重要，权重和成反比。公式如下: （3-10）该式表明，若特征词在所有文档中均出现，即=，则=0，也就是说，虽然特征词出现次数多，但它的分布比较均匀，说明它没有区分类别的能力。考虑到文档长度的影响，对上面公式进行归一化: （3-11）为了降低的作用将式(3-11)调整为： （3-12）3.3.4文本分类技术1、文本分类模式CjCkCjCjCk图3-3 样本的多峰分布 图3-4 样本的边界重叠文本分类器包括两个要素，一个是文本存在的特征空间，另一个是在该特征空间中所采取的分类方法。分类器的构造模式有两种，一种是单分类器模式，一种是多分类模式1516，分别叙述如下:（1）单分类器模式所谓单分类模式，是指文本的全集及类别的全集共享一个特征空间，所有的文本及类别在这个特征空间中的不同区域内分布，并在这个特征空间中执行一种分类方法。在单分类器模式下的输出为待分类文本所属的具体的类别