文本分类算法毕业论文

文本分类算法毕业论文学院：计算机科学与技术学院专业：电子信息科学与技术论文题目：基于半监督的文本分类算法摘要随着Internet的出现，大量的文字信息开始以计算机可读的形式存在，以传统的手工方式对这些信息进行组织整理既费时费力且效果不理想。文本分类作为处理和组织大量文本数据的关键技术，可以利用机器来对文本进行分析整理，使用户从繁琐的文档处理工作中解放出来，并能极大地提高了信息的利用率。文本分类是指分析文本内容并按一定的策略把文本归入一个或多个合适的类别的应用技术。而作为信息过滤、信息检索、搜索引擎、文本数据库、数字化图书馆等领域的技术基础，文本分类技术有着广泛的应用前景。本文首先介绍了文本分类的背景，文本分类所用的半监督算法及文本分类的几个关键技术。然后鉴于高分类精度需要大规模己标记训练集而已标记文档缺乏，利用未标识文档进行学习的半监督学习算法己成为文本分类的研究重点这一情况，着重研究了半监督分类算法。最后本文设计了一个文本分类原型系统，为保证分类的准确性，采用了不同的标准数据集进行测试，并评价了其分类的性能。通过以上实验表明，当有足够的己标识文档时，本算法与其它算法性能相当，但当已标识文档很少时，本算法优于现有的其它算法。关键词:文本分类；半监督学习；聚类；EM；KNNABSTRACTWiththeemergenceofInternet,alargenumberoftextmessagesbegantoexistintheformofcomputer-readable,tothetraditionalmanualwayfororganizationstocollatetheinformationistime-consumingeffortandtheresultisnotsatisfactory.Asthekeytechnologyinorganizingandprocessinglargemountofdocumentdata,Textclassificationcanusethemachinetocollatethetextanalysis,allowingusersfromthetediousworkofdocumentprocessingliberatedandcangreatlyimprovetheutilizationofinformation.Textclassificationisasupervisedleaningtaskofassigningnaturallanguagetextdocumentstooneormorepredefinedcategoriesorclassesaccordingtotheircontents.Moreover,textclassificationhasthebroadappliedfutureasthetechnicalbasisofinformationfiltering,informationretrieval,searchengine,textdatabase,anddigitallibraryandsoon..Thisthesisfirstlyintroducesthebackgroundofthetextclassification,textclassificationusingsemi-supervisedalgorithmandafewkeytechnologiesabouttextclassification.Secondlyconsideringthecontradictionofdeadlyneedforlargelabeledtrain-settoobtainhighclassificationaccuracyandthescarcityoflabeleddocuments，thisthesisemphasizesonimprovementofSemi-supervisedclassificationalgorithms，Finallywedesignadocumentclassificationsystem.Inordertoensuretheaccuracyofclassification,usingadatasetdifferentstandardsfortextingandevaluationoftheperformanceoftheirclassification.Theexperimentsaboveshowedthesuperiorperformanceofourmethodoverexistingmethodswhenlabeleddatasizeisextremelysmall.Whenthereissufficientlabeleddata，ourmethodiscomparabletootherexistingalgorithms.Keywords:textclassification;semi-supervisedleaning;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-BasedMethods） 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.2EM算法 304.2.3KNN算法 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致谢 611引言1.1课题背景随着信息技术的发展，互联网数据及资源呈现海量特征，而且，越来越多的信息以电子文本的形式存在。统计表明，目前网页的数量呈指数型增长，平均每年增加一倍。截至2006年，全球每年制造、复制出的数字信息量共计1610亿GB，这大约是有史以来出版的图书信息总量的300万倍。为了有效地管理和利用这些分布式的海量信息，基于内容的信息检索和数据挖掘逐渐成为备受关注的领域。其中，文本分类(TextClassification)技术是信息检索和文本挖掘的重要基础。文本分类在自然语言处理、信息组织与管理、内容信息过滤等领域都有着广泛的应用。因为文本分类可以极大地增强人们对海量信息的处理能力，早在上世纪中叶，有关文本分类的研究就已经开展起来。早在1957年，美国IBM公司的H．P．Luhn在自动分类领域最先进行了开创性的研究，提出了词频统计思想用于自动分类。1960年，M．E．Maron在JournalofACM上发表了有关自动分类的第一篇文章《OnRelevanceProbabilisticIndexingandInformationRetrieva1》，提出了自动关键词分类技术，正式宣告了自动分类技术的诞生。[1]从20世纪60年代起步至80年代末，文本分类主要是以专家人工构建的知识工程技术为支撑，具有代表性的是卡内基集团为路透社开发的新闻自动分类系统(ConstrueSystem)。基于知识工程的分类系统具有较好的分类效果，但无法移植，需要大量领域专家的参与。从20世纪9O年代开始，随着机器学习技术的不断进步和发展，为自动文本分类器的出现奠定了基础[3]。基于机器学习的文本分类方法，更注重分类器的模型自动挖掘和生成及动态优化能力，在分类效果和灵活性上都比之前基于知识工程和专家系统的文本分类模式有较大的提高与进步。从预先经人工正确分类的训练文本集合中学习类别的特征信息，根据算法生成分类器。这种分类方法适应性强，方便移植，不需要行业专家的介入。从此以后，文本分类器处理海量信息的能力逐步受到IT业和广大用户的赏识，开始发挥越来越大的社会与经济效益。例如，虽然各种搜索引擎部分地解决了Web上的资源发现问题，但由于搜索引擎存在着信息相关度差、精确度不高等原因，效果远不能使人满意；同时，搜索引擎的目的在于发现Web上的资源，就Web上的知识发现而言，即使检索精确度再高也无法胜任。为此，我们需要开发比搜索引擎信息检索技术更高层次的新技术。Web文本挖掘技术包括Web网页文本内容的挖掘及结构挖掘。Web文本挖掘技术可以同搜索引擎、信息推送、信息过滤等信息处理技术相结合，有效地提高了信息服务的质量。[1][3]不可否认，上世纪90年代以来，文本分类技术取得了很大的进步，取得了值得称道的喜人成绩。随着时代的进步，互联网中分布传播的海量电子化文本数量呈几何级数增长，文本之间的关系也越来越复杂；同时，人们对分类效果评估指标（如查全率和查准率）的要求也越来越高，传统的机器学习技术已经呈现“老态”。在机器学习领域，分类属于监督学习。绝大数的有监督的机器学习方法依赖于标注的训练样本集，忽略了未标注样本的作用，利用大规模的标注过的训练数据固然可以提高学习算法结果的准确度，但是标记必须由人手工完成，这是一项费时费力的工作，己经不能适应Internet网上信息的增长速度。同时，网上存在大量容易获得的未标识数据资源，半监督学习算法就是利用这些未标注样本，在传统的机器学习方法中结合未标注样本进行学习的算法。无疑它将在一定程度上提高学习算法的性能。1.2本文的内容组织本文首先介绍半监督和文本分类的一些相关知识，然后提出了一种基于EM和KNN的半监督文本分类算法，给出了算法的思想和步骤，并对其性能进行了测试分析。最后，给出了系统的实验和分析结果。全文共分五章，具体安排如下：第一章是引言，介绍本文研究背景；第二章是半监督学习，介绍关于半监督的一些相关知识；第三章是文本分类，介绍文本分类的一些基本知识及文本分类的关键技术；第四章是基于EM和KNN的半监督文本分类算法，提出了一种基于EM和Knn的半监督文本分类算法，并分析了算法运行的效率；第五章是实验与分析，首先用C语言实现本文算法的过程，然后通过标准数据集的实验验证和分析了本文算法的有效性。总结部分对本文的工作进行了总结，并指出了进一步需要开展的工作。2半监督学习2.1半监督学习的概念及意义半监督学习是相对于监督学习和无监督学习提出来的，其介于监督学习和无监督学习之间。监督学习通过具有标记的训练示例进行学习，以尽可能正确地对训练集之外的示例标记进行预测。无监督学习通过对没有标记的训练示例进行学习，以发现训练示例中隐藏的结构性知识。所谓的“标记”是指示例所对应的输出，在分类问题中标记就是示例的类别，通常想要获得有标记的训练示例是很困难的，或者是费时耗力的，因为要标记它们需要使用人类的经验进行人工的干预。然而，未标记的数据能够很容易就被收集到，但却没有方法使用它们。半监督学习通过使用大量的未标记的数据，用以辅助标记的数据，建立更好的分类器。半监督学习除了提供给学习算法未标记的数据，还要提供给学习算法一些监督信息。[2][11]半监督学习的基本设置是给定一个来自某未知分布的有标记示例集以及一个未标记示例集，期望学得函数可以准确地对示例预测其标记。这里均为维向量，为示例的标记，||和||分别为和的大小，即它们所包含的示例数。半监督学习是模式识别和机器学习中的重要研究领域。近几年随着机器学习理论在数据分析和数据挖掘的实际问题，例如网页检索和文本分类，基于生物特征的身份识别，图像检索和视频检索，医学数据处理等问题中的广泛应用，半监督学习在理论和实际应用研究中都获得了长足的发展。半监督学习研究主要关注当训练数据的部分信息缺失的情况下，如何获得具有良好性能和推广能力的学习机器，这里的信息缺失涵盖数据的类别标签缺失或者存在噪声，数据的部分特征维缺失等多种情况。半监督学习的理论研究对于我们深入理解机器学习中的许多重要理论问题，例如数据的流形与数据的类别信息的关系，缺失数据的合理处理，标注数据的有效利用，监督学习和非监督学习之间的联系，主动学习算法的设计等都有非常重要的指导意义。[11]2.2半监督学习的研究进展半监督学习(Semi-supervisedLearning)是模式识别和机器学习中的重要研究领域。近几年随着机器学习理论在数据分析和数据挖掘的实际问题，例如网页检索和文本分类，基于生物特征的身份识别，图像检索和视频检索，医学数据处理等问题中的广泛应用，半监督学习在理论和实际应用研究中都获得了长足的发展。自20世纪八九十年代以来国际机器学习界研究者在半监督学习研究领域展开了广泛深入的探讨和研究。其涵盖的范围非常广泛，例如半监督回归问题；利用标签和特征维都缺失的数据集进行学习；标签有噪声时的数据处理；利用少量正样本和大量未标注数据进行学习以及对于大量未标注数据中已知只存在少量正样本的情况下对于正样本进行检测；对各种监督学习算法进行修改，探讨如何融入非监督数据信息或者对于非监督学习算法进行修改，探讨监督数据信息的引入；利用有限混合模型对于数据的概率分布进行建模或者利用其他模型对于数据标签关于特征维的条件概率进行建模，利用EM算法学习模型参数的半监督学习的研究；引入合适的数学方法进行半监督学习，例如基于核矩阵的谱的分析，高斯随机场的利用，利用图论中的方法来对于样本集进行聚类分析；半监督数据的流形分析等。研究者同时开展了将半监督学习和传统模式识别和机器学习中的一些问题相结合的研究，例如基于半监督学习的特征提取，半监督学习和集分类器的设计等。国际研究者同时开展了与半监督学习有着密切关联的一些相关研究，具有代表性的是利用半监督数据和数据的不同特征维子集在数据的不同视图上同时训练具有良好性能的学习机器。[2]半监督学习研究正在继续从广度和深度上不断进行扩展，但是依然存在很多问题。一方面半监督学习的前提：聚类假设的数学分析依然不是十分完善，另一方面不同的监督和非监督算法的半监督修改版本依然存在相当多的问题，有的因计算量太大受到问题规模的限制，有的是因为缺乏理论依据只是技术上的设计，有的是因为模型参数过多非常容易陷入局部极值等等。另外半监督学习中如何更加有效利用标注数据的标签信息和未标注数据的分布或者流形信息依然没有得到很好的解决。半监督学习实际应用的研究随着许多实际领域需要分析和利用半监督数据集广泛开展起来。第一个问题涉及到聚类假设的合理性。主要探讨的问题是在欧氏空间聚集程度比较高的地方，也就是比较大的地方，变化一定很平缓的假设的合理性。数据的标签信息可以调整样本之间的相似性度量，那么在特定的核空间讨论和的关系或者说在核空间讨论聚类假设会更加合理。显然是与问题相关的，在实验中，可以设计均匀的地方变化比较大或者存在梯度的人工仿真数据集合，这时如果利用聚类假设进行半监督学习应当在特定的核空间才能进行。分析如何利用监督数据信息设计合适的核空间以进行半监督学习，讨论和的关系对于半监督学习机理中的聚类假设的分析有着很重要的理论研究意义。第二个问题是如何将监督信息中的等约束和不等约束（Side-information）[8]引入更多的半监督学习算法。半监督学习的本质是在给出半监督学习模型以及优化目标后，对模型参数求解，其中监督信息就是这些约束。目前，已经有一些基于这些约束的算法，例如相关成分分析（RelevantComponentAnalysis）[9]，这些方法在实际的分类问题中，获得了很好的性能。那么，如果有效利用各种类型的监督信息设计不同类型的半监督学习模型依然是开放性的问题。2.3半监督学习的方法根据半监督学习算法的工作方式，可以大致将现有的很多半监督学习算法分为三大类。第一类算法以生成式模型为分类器；第二类算法是基于图正则化框架的半监督学习算法；第三类算法是协同训练算法。而主要的半监督算法有：EM算法、S3VMs、自训练、协同训练、基于图的方法等。由于在后文中会对EM算法有详细介绍，故在此将不作介绍。2.3.1协同训练(Co-training)Co-Training方法[3]通过把特征集分为两个独立部分并分别在各个特征空间下用己标记数据训练分类器，再用分类器来分类未标记数据，挑出最确定的正例和反例加到标记例子中，两个分类器针对增大的标记例子集合重新训练，该过程重复执行。以网页为例，网页本身存在两种特征，一种特征是出现在网页上的单词，另一种特征是指向网页链接上的单词。联合训练通过NB（NaiveBayes）分类器训练两种不同特征生成的单词，由此建立两个内嵌的分类器A和B，利用已标记文档，A用网页特征的单词训练，B用链接特征的单词训练。然后，对于未标记文档，A和B分别以最大后验概率选出评分最高的文档，标记类别并一起加入己标记训练集，再如此逐次标记所有未标记文档，由此得到扩大后的训练集。然后利用此训练集集合某种分类器再进行分类。重复执行。实验结果表明，利用联合训练得到的训练集进行文本分类，平均分类错误率比EM-NB方法要低，性能比较稳定。文献[5]分析了联合训练算法优于EM-NB的三个主要原因:原因之一是前者利用了网页文档的两种结构信息进行联合训练;原因之二是它将两个用NB分类算法建立的分类器作为内嵌的分类器训练数据，从而降低了NB假设条件的影响;另一原因则是前者采用了增量训练未标记文档的方法，即在训练分类器时，每次对未标记文档只选出分值最高的部分文档标记其类别，加入已标记文档训练集中。而EM技术则是在每次迭代中，对每篇未标记文档都标记一个临时类别，直到迭代收敛。但联合训练算法不适用于自身没有多重特征的文档(比如纯文本文件)，而且很多类型的文档不易切分特征。多种资源数据也不易统一切分特征属性，在某些领域(如自然语言)，联合训练算法也存在许多局限[6][7]。2.3.2自训练自训练是半监督学习的常用技术，在自训练中，分类器首先用少量有标记的数据训练。然后分类器用于对未标记的数据进行分类。典型地，最先确定的未标记数据点，连同其预测的标记，都被添加到训练集。然后分类器重新训练并且重复上述过程。分类器采用其自身的预测以训练自己，这个过程也称为自教，或自举。这种方法来源于人类在没有直接老师的情况下，对自己以前的经历进行自学习，半监督学习中的自训练即是自动地对未标记的数据进行标记，自训练是一个迭代地对自身进行预测并且迭代地训练分类器的过程。在这个信息爆炸的时代，自训练技术具有天然的优势：训练过程的完全自动化，手工标记样本引入的人为误差可以避免，训练样本按需产生，训练过程简单高效。生成式模型以及EM方法可看成是“软”自训练的特例。可以想象一个分类错误可以加强其自身。如果预测的可信任度降低到某个门槛值，一些算法试图避免这一点通过“忘掉”未标记的数据点。[11]自训练已经被应用于几个自然语言处理的工作。Yarowsky使用自训练用于词义消歧。Riloff等人使用自训练辨别主观名词。自训练还用于语法分析和机器翻译。自训练是一种封装算法，一般来说很难进行分析。2.3.3半监督支持向量机（S3VMs）半监督支持向量机（Semi-SupervisedSVMs）本来被称为直推式支持向量机（TSVM），之所以现在称为半监督支持向量机是因为它们也适用于归纳，而不仅仅是直推。其思想很简单，即在低密度区找到一条决策边界。但是，其背后的优化问题是困难的。[11]TSVM通过把边界置于低密度区域建立了和判别式决策边界之间的联系。TSVM是一种使用未标记数据的标准的支持向量机的扩展。标准的支持向量机只使用有标记的数据，目标是在再生核希耳伯特空（ReproducingKernelHilbertSpace）找到最大边缘的线性边界。在TSVM中未标记的数据也被使用，目标是找到未标记数据的一个标记，以便一个线性边界在原始数据和未标记数据之间有最大边缘。由于判别式方法直接利用类条件概率，在参数估计迭代过程中可能会偏离，而直推式支持向量机通过引导决策边界远离稠密区的方法建立决策边界与间的联系，因而成为一种克服这一问题的较好选择。尽管找到精确的TSVM解是NP完全问题，但一些近似的方法已经提出并有积极的效果[23]。由于成功地把无标记样本中所隐含的分布信息引入了支持向量机的学习过程中，TSVM算法比单纯使用有标记样本训练得到的分类器在性能上有了显著提高。但该算法在执行前必须人为指定待训练的无标记样本中的正标记样本数，而值一般是很难准确地估计的，在TSVM算法中采用了一种简单的方法，即根据有标记样本中的正标记样本所占比例来估计无标记样本中的正标记样本比例，进而估计出值。可以看出，这种估计是有问题的，尤其是有标记样本较少的情况下，一旦估计不正确，将会导致较差的结果。对这个问题，陈毅松等提出了一种改进算法渐进直推式支持向量机（ProgressiveTransductiveSupportVectorMachine,PTSVM）[24]，该算法通过成对标记和标记重置的办法改进了TSVM的性能，但只适合于无标记样本较少的情况，样本较多时，这种频繁的标记与标记重置将导致算法的复杂性迅速增加，并且远超过一般的TSVM算法。现实应用的大多数情况是无标记样本远多于标记样本,因而需要开发适应于这种情况的相应算法。钟清流等提出了一种渐近式半监督学习算法[25],它采用的特定取样规则和核参数可以确保减少误标记数量并控制决策面的动态调节进程，通过删除非支持向量来提高训练速度。实验表明,这种算法能够适应不同的样本分布情况,并取得较好的效果,是一种值得关注的新尝试。2.3.4基于图的方法（Graph-BasedMethods）这曾经是半监督学习研究最活跃的领域。基于图的半监督方法定义了一个图，这个图的各个节点表示有标记的和未标记的数据，图的边则反映了数据间的相似度，这些方法通常假定标记在图上的平滑性。图方法是非参量的、判别的、直推式的。基于图的方法建立在流行假设上。图的正规化：许多基于图的方法可被视作估算一个在图上的函数，需要同时满足两个条件：其应该接近于给定的在已标记的节点的标记；其应在整个图上是平滑的。这是个正规化的框架，第一阶段是一个损失函数，第二阶段是一个正规化因子。当前有许多种基于图的方法，它们都是相似的。重要的是怎麽构造一个好的图，然而对于如何构造图的研究还不够成熟。大多数图方法通过利用图的拉普拉斯算子来涉及到图。用表示一个图，其边权重为。边的权重我指示出数据间的相似度。图的权重矩阵表示为：由定义的对角阵称为的度矩阵。现在有多种方法来定义图的拉普拉斯算子，较为著名的有：规范化图的拉普拉斯算子，未规范化图的拉普拉斯算子，分别表示为：通常预测由未标记节点的标记组成。因此，这种算法本质上时直推式的，也就是说，其只返回在未标记数据点上决策函数的值，而不是决策函数本身的值。图的信息传播也能有助于改进一个给定的考虑未标记的数据的分类。通常图是由计算机目标的相似性而构成的，例如在欧几里得数据点上使用核函数。但有时源数据已经具有图的形式。2.4本章小结本章对于半监督的概念、研究意义、研究进展以及半监督学习方法进行了分析和讨论，重点讨论了半监督学习常用的几种方法，并且重点放在半监督分类上。3文本分类3.1文本分类的概念及意义Internet信息量的迅猛增加，增加了人们获取有效信息的难度，而且信息产生的速度远远超过人们收集信息、利用信息的速度，使得人们无法快速地查找到最新的信息，从而造成了时间、资金和精力的巨大浪费。面对网上海量的信息，传统的做法是对网上信息进行人工分类，并加以组织和整理，从而为人们提供一种相对有效的信息获取手段。但是，这种人工分类的做法存在着许多弊端，不仅耗费大量的人力、物力和财力，而且存在着分类性能不佳的问题。因此，如何有效的组织和管理数据，方便人们的检索?如何区分有用的信息和无用信息?如何从海量的数据中高效地获取有用知识?如何满足用户的个性化需求?所有这些都成了人们亟待解决的问题。文本分类是指按照预先定义的分类体系，根据文本内容自动地将文本集合的每个文本归入某个类别，系统的输入是需要进行分类处理的大量文本，而系统的输出是与文本关联的类别。简单地说，文本分类就是对文档标以合适的类标签。从数学的角度来看，文本分类是一个映射过程，它将未标明类别的文本映射到现有类别中，该映射可以是一一映射，也可以是一对多映射，因为通常一篇文本可以与多个类别相关联。文本分类的映射规则是，系统根据已知类别中若干样本的数据信息总结出分类的规律性，建立类别判别公式和判别规则。当遇到新文本时，根据总结出的类别判别规则确定文本所属的类别。在理论研究方面，对单类别分类的研究要远远多于对多类别分类的研究。主要是由于单类别分类算法可以非常容易地转化成多类别分类算法，不过这种方法有一个假设条件，即各个类之间是独立的，没有相互依存关系或其它影响，当然在实际应用中，绝大多数情况是可以满足此假设条件的。因此，在文本分类的研究中，大部分实验都是基于单类别分类问题的探讨。3.2文本分类的国内外研究情况国外自动分类研究始于1950年代末，H.P.Luhn在这一领域进行了开创性的研究，他首先将词频统计的思想用于文本分类中。1960年Maron在JournalofASM上发表了有关自动分类的第一篇论文“Onrelevanceprobabiliticindexingandinformarionretriral"。1962年博科(H.Borko)等人提出了利用因子分析法进行文献的自动分类。其后许多学者在这一领域进行了卓有成效的研究。国外的自动分类研究大体上可以分为三个阶段:第一阶段（1958年-1964年)主要进行自动分类的可行性研究;第二阶段(1965年-1974年)，自动分类的实验研究;第三阶段(1975年-至今)，自动分类的实用化阶段。[26]国外当前流行的文本分类方法有Rocchio法及其变异方法、k近邻法（KNN)、决策树、朴素贝叶斯、贝叶斯网络、支持向量机(SVM)等方法。这些方法在英文以及欧洲语种文本自动分类上有广泛的研究，而且很多研究表明KNN和SVM是英文文本分类的最好方法。国外很多研究人员对英文文本分类领域的各个问题都有相当深入的研究，对几种流行的方法进行了大量的对比研究。SusanDumais等学者对这5种方法进行了专门的比较研究。国内自动分类研究起步较晚，始于20世纪80年代初期。1981年侯汉清对计算机在文献分类工作中的应用作了探讨[27]，并介绍了国外在计算机管理分类表、计算机分类检索、计算机自动分类、计算机编制分类表等方面的概况。我国自动分类的研究大体上正在经历从可行性探讨--辅助分类--自动分类系统的发展阶段。关于中文文本分类的研究相对较少，国内外的研究基本上是在英文文本分类研究的基础上采取相应策略，结合中文文本的特定知识，然后应用于中文之上，继而形成中文文本自动分类研究体系。国内外的很多学者在基于知识和统计的两种方法上对中文文本分类进行了大量的研究工作，主要有基于词典的自动分类系统和基于专家系统的分类系统。如上海交通大学、中国科学院、清华大学、北京大学、北京信息工程学院、复旦大学、东北大学、山西大学以及新加坡、香港和台湾的一些大学都有相应的研究成果，也研制出了不少的实验系统。3.3文本分类的关键技术一般的自动文本分类有以下几个阶段[10]，具体如图3-1所示。生成训练语料库的文本特征全集；文本特征提取，形成特征子集；采用某种数学模型和分类方法进行分类器构造；利用训练语料库中的文本对分类器进行训练，得到分类器的相关参数。训练文本采集及处理训练文本采集及处理特征提取/文本表示特征空间降维构造分类器分类和输出新文本预处理训练过程分类过程图3-1文本分类过程[26]由图3-1所示及上述的文本分类的几个阶段，可以看出文本分类过程所需要的几个关键技术，现下面开始介绍文本分类的关键技术。3.3.1文本特征生成在当前的计算机技术的研究水平下，机器还不可能识别自然文本，从根本上说，它只认识0和1，所以必须将文本转换为计算机可以识别的形式。而要想让计算机“读懂”文本，必须能够找到用于文本表示的数学模型。随着信息检索技术的发展，逐渐发展起来的主要有三个文本检索模型，分别是:布尔模型[10](BooleanModel，BM)、向量空间模型[12][13](VectorSpaceModel，VSM)和概率模型(ProbabilisticModel，PM)，这些模型从不同角度使用不同的方法处理特征加权、类别学习和相似度计算等问题，而最经典、最实用的是向量空间模型，本文的研究是建立在向量空间模型之上的。向量空间模型是由Salton在20世纪60年代末提出的，它最早应用于信息检索领域，例如著名的SMART(SystemfortheManipulationandRetrievalofText)系统就成功的应用了向量空间模型技术，后来又在文本分类领域得到了广泛的应用。向量空间模型的基于两个基本假设，一是文档所属的类别仅与某些特定的词或词组在该文档中出现的频数有关，而与词或词组在文档中出现的位置或顺序无关;二是假设文档的各特征词之间是相互独立的。这样，只需要提取出一份文档中蕴涵的各个特征词的词频信息就可以对其进行正确的分类。向量空间是由一组线性无关的基本向量组成，向量维数与向量空间维数一致，并可以通过向量空间进行描述。下面介绍文档向量空间的一些基本概念:文本:泛指一般的文献或文献中的片段(段落、句子或句子组)，一般指一篇文章(假设文档中不包含除文字以外的其他多媒体信息)。特征项:文本的内容特征常常用它所含有的基本语言单位(字、词、词组或短语)来表示，一般中文中使用词语作为文本的特征项。特征项的权重:对于含有个特征项的文本，常用一定的权重表示特征项在文本中的重要程度。即把文本表示为，特征词表示为，特征词的权重表示为。这样自然语言形式的文本文档就可以在向量空间中完全由特征向量来表示。对两个文本试和之间的内容相关程度的度量被称为相似度，可以用如下公式计算：（3-1）tkttktitj图3-2文本的向量空间模型及文本间的相似度其中，为特征向量的维数，表示第个文本的第个特征项的权重值。向量空间模型的主要优点在于:(l)标引词加权改进了检索效果;(2)其部分匹配策略允许检出与查询条件相接近的文献;(3)利用余弦公式，根据待测文献与训练文献之间的相似度对其进行排序。与其他的检索模型相比，向量空间模型简单、便捷，而且分类性能也非常好，已成为当今最流行的检索模型。3.3.2特征选择与降维实现文本自动分类的基本困难之一是特征项空间的维数过高。数量过大的特征项一方面导致分类算法的代价过高，另一方面导致无法准确地提取文档的类别信息，造成分类效果不佳。因此，需要在不牺牲分类质量的前提下尽可能地降低特征项空间的维数。特征选择的任务就是要将信息量小，“不重要”的词汇从特征项空间中删除，从而减少特征项的个数，它是文本自动分类系统中的一个关键步骤。常用的文本特征选择方法有:文档频率()、信息增益()、互信息()、统计量()，文本证据权，优势率，统计()等。这些方法都是基于阈值的统计方法，它们的基本思想都是对每一个特征计算某种统计度量值，然后设定一个闽值，把度量值小于阈值的那些特征过滤掉，剩下的即认为是有效特征。1、文档频率文档频率(DocumentFrequency)，就是文档集合中出现某个特征项的文档数目。在特征项选择中，计算每个特征项在训练集合中出现的频率，根据预先设定的阂值排除那些文档频率特别低和特别高的特征项。文档频率的计算复杂度较低，随训练集的增加而线性增加，能够适用于大规模语料，因此是特征降维的常用方法。其基本原则是:很少出现的特征对分类价值极小，对整个分类系统的效果影响也很小，因此，将这些特征去掉有助于降低特征空间维数，并且当这些不常出现的特征为噪音时，还会有助于提高分类正确率。但在信息检索领域，文档频率较低的特征项被认为是信息含量较高，与文本分类中的原则是相反的。2、信息增益信息增益(InformationGain)，是一种在机器学习领域应用较为广泛的特征选择方法。它从信息论角度出发，用各个特征取值情况来划分学习样本空间，根据所获取信息增益的多寡，来选择相应的特征。其计算公式如下:（3-2）其中，表示文本中出现单词时，文本属于的概率；同样表示文中不出现单词时文本属于的概率;表示类文本在语料中现的概率;表示在整个文本训练集中出现的概率。互信息互信息方法(MutualInformation)，可以度量特征项和类别的共现关系，特征项对于类别的互信息越大，说明特征中包含的与类别有关的鉴别信息就越多。因此，互信息衡量的是词与类之间的相关程度。文本分类中，一个特征词只有一个信息增益和文档频率，但拥有的互信息数目却是与训练语料中类别的数目相同的，对应于每个类，该特征词都会有一个互信息值。一个词可以对应几个互信息值，一般来说，因为我们的目的是选出对分类比较有用的词，所以通常根据每个词最大的互信息值来排序，然后从高到低选择特征词或者设定一个阈值排除那些互信息值比较低的词。假设文档集合分为类，记为，，…，，特征项对于文档类别的互信息(，)的计算公式如下:（3-3）其中(，)为特征项出现在类中的概率，(，)为特征项在所有文档中的出现概率。4、统计使用衡量特征项的重要程度时，只考虑到了正相关对特征项重要程度的影响。如果特征项和类别反相关，就说明含有特征项的文档不属于的概率要大一些，这对于判断一篇文档是否不属于类别也是很有指导意义的。为克服这个缺陷，使用以下公式计算特征项和类别的相关性:（3-4）其中:为和同时出现的次数;为出现而没有出现的次数。为出现而没有出现的次数;为和同时没有出现的次数。为训练集中的文档数。和类似，如果和不相关，则(，)值为0，因为在这种情况下，个训练文本的数目应该在这四种文本中均匀分布，即===。而另一个极端，词与类别非常相关，体现在这四个数量上，就是词出现的文本属于类别，而词不出现的文本不属于类别。这样的话，==/2，而==。在衡量词和类别之间的相关关系上，互信息和统计量之间有一定的相似之处。这两个向量间的不同之处在于互信息是一个非规格化的值，其取值范围很大，特别是对于那些边缘概率分布很小的情况。而统计量则是一个规格化的量。对于词，我们可以采用两种方法来求取其在训练集上的统计量值：（3-5）或是：（3-6）同相同，如果有个类，每个就会有个值，取它们的平均，就能得到特征选取所需的一个线性序列。平均值大的特征优先被选取。算法的计算复杂度也为。特征权方法基于术语在邻近相关文档中出现的频率来测试术语的强度。和是任意不同但相关的文档，术语的权值可由下式计算出:（3-7）但是实际中发现某些值很低的特征反而是信息量比较高的，不能从特征空间中删去，因此这种方法在某些情况下不可靠。以上介绍了五种常用的特征选择方法，它们具有的共同优势是计算量相对较小，而且结果特征集的解释性强，就是原来特征词集的子集，但是它们一些方面还需改进，比如分类器的特征集包含很多冗余的信息，同义词、多义词都能造成这种情况;一个词单独可能对分类器的作用不大，选择时被删去，但和其它一些词结合却是很好的辨别因素等等。3.3.3权重计算特征项选择出来后，要对每个项赋予权重，应使文本中越重要的项的权重越大。目前最普遍的赋权重的方法是运用统计方法，即用文本的统计信息，主要是词频，来计算特征项的权重。下面对常用的加权函数进行详细介绍。布尔权重布尔权重是最简单的一种加权方法，如果特征词出现次数为0，则其权重为0，如果特征词出现词数大于0，则其权重为1。公式如下:（3-8）其中表示特征词在文档中的权重，表示特征词在文档中出现次数。词频权重该方法将特征词的频次作为权重。公式如下：（3-9）-权重该方法基于以下两点原因:一是特征词在文档中出现词数越多越重要，权重和成正比;二是文档集中含有特征词的文档数越大越不重要，权重和成反比。公式如下:（3-10）该式表明，若特征词在所有文档中均出现，即=，则=0，也就是说，虽然特征词出现次数多，但它的分布比较均匀，说明它没有区分类别的能力。考虑到文档长度的影响，对上面公式进行归一化:（3-11）为了降低的作用将式(3-11)调整为：（3-12）3.3.4文本分类技术1、文本分类模式CCjCkCjCjCk图3-3样本的多峰分布图3-4样本的边界重叠文本分类器包括两个要素，一个是文本存在的特征空间，另一个是在该特征空间中所采取的分类方法。分类器的构造模式有两种，一种是单分类器模式，一种是多分类模式[15][16]，分别叙述如下:（1）单分类器模式所谓单分类模式，是指文本的全集及类别的全集共享一个特征空间，所有的文本及类别在这个特征空间中的不同区域内分布，并在这个特征空间中执行一种分类方法。在单分类器模式下的输出为待分类文本所属的具体的类别[12]。由于各个类别的样本同时存在于一个特征空间中，因而各个类别的样本之间存在着多峰分布和边界重叠的问题(见图3-3，3-4)。具体地说，就是同类样本之间的距离可能会大于不同样本之间的距离，各类样本存在着混杂分布的情况;同类样本的分布不够紧凑，大多数的样本处于类别的边界，类与类之间存在着边界重叠的情况。这样一来，在单分类器模式下，对处于这两种情况下的样本，很难给予正确的分类。比如，图3-4中位于和类交界处的样本，就无法区分他们究竟属于类还是属于类。而对于图3-3所示的情况，在采用KNN法或SVM法的时候，很难给予正确的分类，而采用Rocchio法则需要很好地选择类向量。（2）、多分类器模式CCjCj图3-5多分类器模式下类样本的多峰分布所谓多分类器模式，是指各类的文本独享一个特征子空间，每个类的文本只在自己的特征子空间中分布，类与类的特征子空间之间相互独立，各个特征子空间中可以执行不同的分类方法。多分类器模式下，每个类别的分类器的输出为待分类文本是否属于该类别。这种模式下，不会存在各类的样本混杂分布的情况，同类样本之间的多峰分布表现为该类样本在自己的特征子空间中的不同区域内分布(图3-5)。对于样本的边界重叠问题，也就是对存在着兼类现象的文本，在多分类器模式下，会对此类文本赋予多个类别。多分类器模式事实上是通过特征空间的划分取代单分类器模式下的区域划分，以此来解决样本的多峰分布及边界重叠问题，而空间的划分也导致了其上执行的分类方法的隔离。但采用多分类器的假设前提是认为各类文本之间是相互独立的，事实上，这一点很难做到，因为自然语言的丰富多样性使得各类文本之间存在着用语“斜交”的情况，也就是说，这种独立性的假设前提是不存在的，因而各个类别的特征子空间之间的相互独立也是很难做到的。这也是为什么现有的文本分类系统大多采用单分类器的原因，不过采用多分类器模式可以比采用单分类器模式使用更少的向量维数而达到较好的分类效果。2、常用的文本分类算法文本转化为向量形式并经特征提取以后，便可以进行文本分类了，也称特征匹配。机器学习领域常用的分类算法有:Rocchio算法、Knn算法、朴素贝叶斯分类、决策树、支持向量机等分类法。下面介绍几种常用的分类方法:（1）、Rocchio算法[17]Rocchio算法是情报检索领域最经典的算法。该算法中，首先为每一个类建立一个原型向量，然后通过计算文档向量与每一个原型向量的距离来给分类。Rocchio公式为：（3-13）其中指类的中心向量，是指文档向量的权重，是所有训练样本的数目，是训练集中属于类的正例样本的个数，为反例样本的个数。、、分别用来控制中心向量、正例集和反例集所占的权重。通常，为了强调正例文本的重要性，正例的权值取得较大，而反例的权值取得比较小。（2）、朴素贝叶斯分类(NaiveBayes)[18]NaiveByaes(以下简称NB)分类方法是一种简单而又非常有效的分类方法。NB方法的一个前提假设是:在给定的文档类语境下，文档属性是相互独立的。假设为一任意文档，它属于文档类中的某一类。根据NB分类法有:（3-14）(3-15)对文档进行分类，就是按(3-15)式计算所有文档类在给定情况下的概率。概率值最大的那个类就是所在的类，即:(3-16)由(3-14)、(3-15)和(3-16)可知，对于给定分类背景和测试文档，用NB方法分类的关键就是计算和。计算和的过程就是建立分类模型的过程。NB方法假设一个单词在一个分类文档中的发生概率与该文档中的其它单词无关，从而使得计算复杂度简单，具有较高的效率。但是该假设对于绝大多数真实的文本都不成立，从而分类精度有所降低。（3）、决策树(DecisionTree)[19]决策树提供了一种展示类似在什么条件下会得到什么值这类规则的方法，比如，在贷款申请中，要对申请的风险大小做出判断，图3-6是为了解决这个问题而建立的一棵决策树，从中可以看到决策树的基本组成部分:决策节点、分支和叶子。决策树中最上面的节点称为根节点，是整个决策树的开始。本例中根节点是“收入>￥40，000”，对此问题的不同回答产生了“是”和“否”收入>收入>¥40，000工作时间>5年高负债低风险高风险低风险高风险否否否是是是图3-6一棵简单的决策树决策树的每个节点子节点的个数与决策树所用的算法有关。如CART算法得到的决策树每个节点有两个分支，这种树称为二叉树。允许节点含有多于两个子节点的树称为多叉树。每个分支要么是一个新的决策节点，要么是树的结尾，称为叶子。在沿着决策树从上到下遍历的过程中，在每个节点都会遇到一个问题，对每个节点上问题的不同回答导致不同的分支，最后会达到一个叶子节点。这个过程是利用决策树进行分类的过程，利用几个变量(每个变量对应一个问题)来判断所属的类别(最后每个叶子会对应一个类别)。（4）、支持向量机SVM[20]SVM是一种建立在统计学习理论基础上的机器学习方法，有较好的推广性能和较高的分类准确率。该算法基于结构风险最小化原理，将数据集合压缩到支持向量集合(通常为前者的3％～5％)，学习得到分类决策函数。SVM的主要思想是在向量空间中寻找一个决策面，使它能最好地将数据点分割为两部分。Margin=Margin=H1HH2图3-7支持向量机的决策面在线性可分空间中，决策面常被称为超平面。如图3-7所示，圆圈为一类数据点，实心圆为另一类数据点，H即为分割它们的超平面。离超平面最近的数据点就被称为支持向量，也就是图中在H1和H2上的数据点。H1和H2间的距离称为分隔间隔(Margin)，SVM就是要达到既使这个间隔最大，也能精确地分类的目的。支持向量与超平面之间的距离为，则支持向量间距为，寻找超平面的问题可化为求解以下二次规划问题：最小化泛函数约束条件为：利用Lagrange优化方法得到最优分类面：，，为任意支持向量从上式可以看出，=0的样本对于分类不起任何作用，只有>0的样本起作用，从而决定分类结果，这样的样本即为支持向量。相应的分类器为：在线性可分情况下，支持向量机的内积核函数：SVM本质上是解决两类分类问题，所以SVM解决个类的分类问题需要转化为两类分类问题，其方法可以是：构造个分类器，第个分类器的训练数据是第类的数据作为正例，其他类的数据作为反例，为每个类构造一个分类器，第个分类器在第类和其他－1类之间构造一个超平面，在多个两类分类器中具有最大输出的类别即是测试文本所属的类别。3.3.5文本分类技术性能评价1、影响分类效果的主要因素根据实验和经验，影响文本分类算法和系统质量评价的因素是多方面的，除分类算法的因素外，还与测试方法、分类标准、分类层次和语料库是否标准等有关。(1)、测试方法的影响:开放性测试与封闭性测试的分类准确度的差距非常明显，但是随着训练文本集的增大，这一差距在缩小。封闭性测试是指训练语料的学习获取分类知识，开放性测试是对测试语料进行分类实验。与封闭性实验相比，开放性测试的结果更具有实际意义，一般而言，封闭式实验结果比开放式测试效果好，但是，当训练语料库的规模达到相当大的程度，封闭性测试结果与开放性测试结果应趋于吻合，如当语料数量从2000篇增加到5000篇左右时，差距仅缩小一个百分点。(2)、训练语料的影响:在相同的分类标准下，各人对分类规则的理解差异，较大程度影响分类系统的准确度，以相同的分类标准与分类层次(1层)等测试环境，以来源于复旦大学的训练语料作为学习样板，测试来源于人民日报和sina网的语料，发现分类的精度下降很多。一个合理的解释是各人对分类规则的理解差异导致人工标注的不同。(3)、类别特点的影响:分类标准的制定，在相当程度上影响文本分类的准确度，特别是存在类别交叉情况时更突出。有的学科，分类类别定义范围比较明确，如体育、电脑技术等，此类分类精度比较高;而部分学科，存在着交叉现象，分类精度较低，如政治、经济等。主要原因是分类标准对于交叉学科的范围定义含糊，训练集受人工干预较大，没有特别明显的概念特征，对于测试文档，很难提取出有效的分类特征向量。(4)、类别总量是影响分类系统准确度的一个重要因素，类别总量越多，分类精度越低，产生分类交叉的可能性也就越大，如果人工分类过于详细，系统在自动分类中，对于一些交叉的类别分类精度会降低。(5)、训练文本类别的分布情况的影响:如果训练文本类别的分布过度不均匀，则将会使分类结果偏向于文本数较多的一类。从而导致分类精度的降低。2、评价标准传统的信息检索着眼于发现资源，所用的指标主要有准确率(Precision)和召回率(Recall)等。文本分类是为了揭示分类器的分类性能，因此除了上述两项指标外，还采用了收益率(Gain)、分类正确率(ClassifiCation)、准确率与召回率的几何平均数、信息估计值等来衡量分类器的性能。一般用准确率、召回率、F值和微平均来衡量系统的性能，其中，是实际属于类的测试文档数;是分类器预测为类的文档数;是正确分类的文档数。对于简单的两类分类器，评价系统性能的指标分别定义如下:（1）正确率:识别正确的样本数/识别样本总数（2）召回率()/查全率:分类器正确判为该类的样本数/该类的样本总数，即：漏识率，（3）准确率（）:正确判为该类的样本数/判为该类的样本总数，即:误识率，（4）错误率:识别错误的样本数/识别样本总数（5）漏识率:该类样本中没有被判为该类的样本数/该类样本总数（6）误识率:不属于该类的样本数/判为该类的样本总数（7）F值:将准确率与召回率两者结合为一个指标，两者相对比重可用参数来刻画，计算公式如下:（3-17）式中，，当=0时，；当=时，；当=1时（即F1），Precision与Recall在系统中有着同样的重要性;当<l时，强调Precision的作用:当>l时，强调Recall的作用。对于多类别分类，一般采用平均的方法:微平均(micro-average)和宏平均(macro-average)。微平均统一计算全部类的召回率、准确率和F1(即中=1)值，宏平均计算每一类的召回率、准确率和F1值后取算术平均值。用、和表示微平均中的微观召回率、微观准确率和微观F值，则分类系统的微平均计算公式如下:（3-18）（3-19）（3-20）用、和表示宏平均中的宏观召回率、宏观准确率和宏观F值，则分类系统的宏平均计算公式如下:（3-21）（3-22）（3-23）一般来说，微平均易受到大类结果的影响，而宏平均是对全部类别取均值，相对易受小类分类结果的影响。影响文本分类的因素影响文本分类的因素主要有以下几种:（1）使用不同的特征生成方法。（2）使用不同的特征提取方法。（3）使用不同数量的特征。（4）是否采用了特征平滑技术。（5）使用不同的权重计算函数。（6）使用不同的分类方法。所谓特征平滑技术是指对文本中没有出现的特征的处理，比如，对那些没在文本中出现的特征词赋予一个较低权重值，避免文本向量过于稀疏。3.4本章小结本章主要是对文本分类相关知识的学习。除了对文本分类概念、意义及国内外发展情况作了简要介绍外，重点介绍了文本分类的一些关键技术，如文本特征生成、特征选择与降维、文本分类性能评价等。4基于EM和KNN的半监督文本分类4.1引言本文针对的是KNN这种常用的文本分类算法。KNN算法是一种基于实例的文本分类算法，对于一个测试文档，需要计算它与训练样本集中每个文本的文本相似度，依文本相似度找出K个最相似的训练文本，然后在此基础上分别计算测试文本与K个文本的权重，最后将测试文本分到权重最大的那个类中。在上述经典KNN算法中，对于一个测试文档，需要计算它与训练样本集中每个文本的相似度，计算复杂度非常高。针对这一问题，本章提出了一种在聚类基础上的半监督文本分类算法，算法首先对训练集进行聚类，计算每类的中心点，之后将每类的中心点和为聚类文本组合成新的训练集，最后用经典KNN算法对新的训练集进行训练。通过实验我们发现，上述算法在很大程度上减少了其计算复杂度，从而提高了分类器的性能。4.2相关工作4.2.1聚类分析聚类是人类一项最基本的认识活动。通过适当的聚类，事物才便于研究，事物的内部规律才可能为人类所掌握。所谓聚类就是按照事物的某些属性，把事物聚集成类，使类间的相似性尽量小，类内相似性尽量大。聚类是一个无监督的学习过程，分类是有监督的学习过程，两者的根本区别在于:分类时需要事先知道分类所依据的属性值，而聚类是要找到这个分类属性值。文本聚类和文本分类相比，最主要区别就是分类学习的样本或数据有类别标记，而要聚类的样本没有标记，需要由聚类学习算法自动确定。分类方法是典型的有监督学习方法，它需要预先定义一个训练集，即对文本集合进行人工分类，作为构造分类函数或分类模式的基础。但定义训练文本集是一个枯燥而又费时的工作，并且随着时间的推移，这些文本集合随时都在添加新内容，主题也可能发生变化，从而需要重新定义主题类别和训练集。而采用无监督学习方法时，就不需要人工预先确定训练文本类别，省去了枯燥而又费时的工作。相似性度量聚类分析是基于这样一个认识:每一类别对象之间较为相似，而类间对象之间应该具有较大差异。对应不同性质的数据，人们给出了不同的相似性度量标准。主要有以下两类函数:（1）、相似函数:两个样本点愈相似，则相似系数值愈接1;样本点愈不相似，则相似系数值愈接近0。这样就可以使用相似系数值来刻画样本点性质的相似性。如果一个函数:满足以下条件，我们就称之为相似系数函数：（4-1）（4-2）（4-3）越接近1，两个特征变量间的关系越密切。经常采用的相似系数有以下两种:a、夹角余弦：（4-4）这是受相似性启发而来，夹角余弦函数忽略各个向量的绝对长度，着重从形状方面考虑它们之间的关系。当两个向量的方向相近时，夹角余弦值较大，反之则小。特例是当两个向量平行时，夹角余弦值为1;而正交时值为0。b、相关系数（4-5）相关系数是对向量做标准化后的夹角余弦，表示两个向量的线性相关程度。（2）、距离函数:设用个特征项来描述样本，那么我们就可以把每个样本点看作维空间中的一个点，进而使用某种距离来表示样本点之间的相似性，距离越近的样本点性质越相似，距离越远的样本点差异越大。假设有个对象，描述第个对象的个属性值分别对应于区间变量值，，……，，描述第个对象的个属性值分别对应于区间变量值，，……，。那么对象和之间的相似度一般以它们之间的距离来表示。其计算公式如下:（4-6）其中，，，为正整数。当=1时，表示曼哈顿距离。当=2时，表示欧几里德距离，它是比较常用的距离计算公式。不论采用上述那一种距离计算方法，区间变量计量单位越小，度量值越大，对距离计算影响也就越大，从而使得差异度值也越大。为了避免计量单位对差异度计算的这种影响，可以对变量进行标准化处理。主要的聚类算法可以划分为如下几类：（1）划分的方法(Partioningmethod):它是一种基于原型的聚类方法，其基本思路是:首先从数据集中随机地选择几个对象作为聚类的原型，然后将其他对象分别分配到由原型所代表的最相似、也就是距离最近的类中。对于划分聚类方法，一般需要一种迭代控制策略，对原型不断进行调整，从而使得整个聚类得到优化，例如使得各对象到其原型的平均距离最小。实际上，绝大多数应用采用了以下两个比较流行的启发式方法:（i）k-平均算法:在此算法中，每个簇用该簇中对象的平均值来表示;（ii）k-中心点算法:在此算法中，每个簇用接近聚类中心的一个对象表示。此类方法比较适用于聚类的形状为凸形，大小和密度相似，聚类的数目可以合理估计的情况。此外这两种方法都要求用户指定聚类数目k。（2）基于层次的方法(heirarchicalmethod):该方法对给定的数据对象集合进行层次分解。根据层次的分解如何形成，层次聚类方法可以分为凝聚的和分裂的。（i）凝聚的方法，也称自底向上方法。一开始将每个对象作为单独的一个组，然后相继合并相近的对象或组，直到所有的组合并为一个(层次的最上层)，或者达到一个终止条件。（ii）分裂的方法，也称为自顶向下方法，一开始将所有对象置于一个簇中。在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件。层次聚类方法的缺陷在于，一旦一个步骤(合并或者分裂)完成，它就不能被撤销，即不能更正错误的决定。（3）基于密度的方法(density-basedmethod):绝大多数划分方法基于对象之间的距离进行聚类。这类方法只能发现球状簇，而在发现任意形状的簇上遇到了困难。随之提出了基于密度的另一类聚类方法。以局部数据特征作为聚类的判断标准，主要思想是:只要临近区域的密度(对象或数据点的数目)超过了某个阀值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法可以用来过滤“噪音”孤立点数据，发现任意形状的簇。（4）基于网格的方法(grid-basedmehotd):基于网格的方法把对象空间量化为有限数目的单元，形成了一个网络结构。所有的聚类操作都在这个网络结构(即量化的空间)上进行。这种方法的主要优点是处理速度快，其处理时间独立于数据对象的数目，只与量化空间中每一维的单元数目有关。（5）基于模型的方法(model-basedmethod):基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳拟合。如一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚类。就某一个聚类算法而言，往往融合了多种聚类方法的思想，并不能简单地将其归为上述某一类方法。4.2.2EM算法EM算法[21]是由Dempster提出，是一种被广泛使用的半监督学习算法，这是一种在不完全资料情况下计算极大似然函数估计和后验概率分布的迭代算法，亦用于计算边缘分布。名为EM算法是为了强调迭代算法的两个步骤，即Expectationstep和Maximizationstep：（1）E-step：在给定观测资料和前一次迭代所得的参数估计情况下计算完全资料对应的条件期望，利用当前网络结构和参数对未标记样本数据做软分类；（2）M-step：用极大似然函数估计确定参数的值，用于下一步的迭代。把所有已标记样本和已软分类的样本作为训练样本集，计算出新的最大可能的参数分布，并用来替换原有的。EM算法要求在E-step和M-step之间不断迭代，直到所估计的参数达到局部最优。EM算法的具体步骤操作将在4.3.3章节讲述。目前，许多EM算法的扩展版本关注的是如何修改EM算法使得能够尽量收敛到合理的局部极值，例如确定性退火EM算法（DeterministicAnnealingEMalgorithm简写为DAEM)[28]，分裂融合EM算法（SplitandMergeEM简写为SMEM）[29]，或者使得EM算法在理论上能够收敛到全局最优值，例如利用可逆的可跳转的MarkovMonteCarlo[30]链基于随机采样的机制搜索全局最优，另一方面，是关于如何对于模型复杂度加入约束以使EM算法能够自动选择有限混合模型的成分的数量同时收敛到合理的局部极值，例如基于最小信息长度（MinimumMessageLength简写为MML）[31]准则的一个算法，和基于竞争机制的EM算法。4.2.3KNN算法K近邻算法[22]是一种稳定而有效的基于实例的文本分类方法。采用KNN方法进行文档分类的过程如下：对于某一给定的测试文档d，在训练文档集中，通过相似度找到与之最相似的K个训练文档。在此基础上，给每一个文档类打分，分值为K个训练文档中属于该类的文档与测试文档之间的相似度之和。也就是说，如果在这K个文档中，有多个文档同属于一个类，则该类的分值为这些文档与测试文档之间的相似度之和。对这K个文档所属类的分值统计完毕后，即按分值进行排序，只有分值超过阈值的类才予以考虑。具体步骤如下：（1）假定K=最近邻数；（2）计算测试文档d与所有训练文本的相似度；（3）从中选出K个与文本d最相似的训练文本为测试文本d的最近邻；（4）收集这些已选出的最近邻的类别；（5）根据K个最近邻，给每一个类别打分；其中，，为阈值。（6）分值最大的类别即为测试文本的类别。4.3基于EM和KNN的半监督文本分类算法本节将重点介绍本文所研究的基于半监督的文本分类算法，对算法思想、算法步骤、算法的具体操作及算法的效率都做了详细的介绍。4.3.1问题描述前面已经介绍了，文本分类需要大量的数据集进行训练。然而在众多训练集中，得到有标记的数据是非常困难的，且费时费力；但未标记的数据却很容易就能得到。故现在文本分类大部分都是应用的半监督算法，以标记数据为主，未标记数据为辅来不断完善分类器。然而就是因为带标记数据比较难得到，数据非常少，从而可能造成前期训练分类器时出现错误，如图4-1示：图4-1图4-1分类示图其中，实心为已标记数据，空心为未标记数据，三角形和圆形代表两类。虚线代表可能造成的错误分类，实线为正确的分类。如图4-1，在分类中由于标记数据非常少，很可能造成如“虚线”一般的错误分类。本文所研究的基于半监督的分类算法就是为解决此类问题，尽可能减少错误的分类，从而提高分类器的性能。4.3.2算法思想本章所研究的算法思想是：先根据标记数据进行聚类，计算每类的中心点，用新的中心点和未聚类文本组成新的训练集，然后用新的训练集进行分类。基本思想如图4-2所示，图中两个多边形代表聚类结果，其它的与图4-1相同。算法的具体步骤及实现将在4.3.5小节详细介绍。图4-2聚类图4-2聚类-分类图根据以上所述，本文所研究的基于半监督的文本分类算法就是先对数据集进行聚类之后，然后在应用半监督分类算法进行分类。如此可以很大的提高分类器的性能。4.3.3基于EM算法的聚类分析本章所研究的基于EM算法的聚类数据集是基于高斯混合模型的。故本节将分别介绍高斯混合模型和聚类EM算法。[32][33]（1）高斯混合模型假设有一系列观测值由某混合分布产生，该分布又是由个成分构成，每一个成分都代表一个不同的类别(cluster)。假设观测样本，每个向量都是维的。表示是第类的密