基于文本的聚类算法研究毕业论文.doc

基于文本的聚类算法研究摘 要聚类作为一种知识发现的重要方法，它广泛地与中文信息处理技术相结合，应用于网络信息处理中以满足用户快捷地从互联网获得自己需要的信息资源。文本聚类是聚类问题在文本挖掘中的有效应用，它根据文本数据的不同特征，按照文本间的相似性，将其分为不同的文本簇。其目的是要使同一类别的文本间的相似度尽可能大，而不同类别的文本间的相似度尽可能的小。整个聚类过程无需指导，事先对数据结构未知，是一种典型的无监督分类。本文首先介绍了文本聚类的相关的技术，包括文本聚类的过程，文本表示模型，相似度计算及常见聚类算法。本文主要研究的聚类主要方法是k-均值和SOM算法，介绍了两种算法的基本思想和实现步骤，并分析两种算法的聚类效果。同时介绍了两种算法的改进算法。关键词：文本聚类 聚类方法 K-MEAN SOM IIAbstractClustering as an important knowledge discovery method, which extensively with Chinese information processing technology, used in network information processing to meet the users to quickly access from the Internet, the information resources they need. Text clustering is a clustering problem in the effective application of text mining, which according to the different characteristics of text data, according to the similarity between the text, the text will be divided into different clusters. The aim is to make the same class as large as possible the similarity between the text, and different types of text as small as possible the similarity between. The clustering process without guidance, prior to the data structure is unknown, is a typical unsupervised classification. This paper studies the effect of influencing factors that text clustering, text representation of the model such as the Boolean model, vector space model, probabilistic retrieval model and language model. Also studied the analysis of such text clustering algorithm: hierarchical clustering, agglomerative hierarchical clustering algorithm, hierarchical clustering algorithm to split and so on. Also studied the text clustering algorithm analysis and methods of improvement.Key words：Text clustering clustering method k-mean som毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作 者 签 名： 日 期： 指导教师签名： 日期： 使用授权说明本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名： 日 期： 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期： 年 月 日导师签名： 日期： 年 月 日指导教师评阅书指导教师评价：一、撰写（设计）过程1、学生在论文（设计）过程中的治学态度、工作精神 优 良 中 及格 不及格2、学生掌握专业知识、技能的扎实程度 优 良 中 及格 不及格3、学生综合运用所学知识和专业技能分析和解决问题的能力 优 良 中 及格 不及格4、研究方法的科学性；技术线路的可行性；设计方案的合理性 优 良 中 及格 不及格5、完成毕业论文（设计）期间的出勤情况 优 良 中 及格 不及格二、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格建议成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）指导教师： （签名） 单位： （盖章）年 月 日评阅教师评阅书评阅教师评价：一、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格二、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格建议成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）评阅教师： （签名） 单位： （盖章）年 月 日基于文本的聚类算法研究教研室（或答辩小组）及教学系意见教研室（或答辩小组）评价：一、答辩过程1、毕业论文（设计）的基本要点和见解的叙述情况 优 良 中 及格 不及格2、对答辩问题的反应、理解、表达情况 优 良 中 及格 不及格3、学生答辩过程中的精神状态 优 良 中 及格 不及格二、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格评定成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）教研室主任（或答辩小组组长）： （签名）年 月 日教学系意见：系主任： （签名）年 月 日目 录摘 要IVAbstractV目 录VI第一章 绪 论11.1 课题研究的背景11.2课题研究的意义2第二章 文本聚类效果影响因素32.1文本聚类过程32.2文本表示模型42.2.1布尔模型52.2.2向量空间模型52.3 文本相似度计算62.4文本聚类算法82.5本章小结11第三章 k-均值聚类算法123.1 K-均值聚类算法的思想123.1.1 K-均值聚类算法的基本思想123.1.2 K-均值聚类算法的算法流程123.1.3 K-均值算法的优缺点分析133.1.4现有的对于K-均值聚类算法的改进153.1.5现有基于初始中心点改进的K-均值聚类算法163.2 本章小结17第四章 SOM聚类算法184.1 SOM聚类算法的网络特性与基本流程184.1.1 SOM网络的特性184.1.2 SOM网络聚类的基本流程194.1.3 SOM网络聚类的优点及存在的问题194.2改进的SOM聚类方法204.2.1已有的学习策略改进204.2.2等离差理论在神经元获胜策略中的应用改进214.2.3初始化连接权值224.2.4已有的初始化连接权的方法224.2.5新的确定初始权值的方法234.3本章小结25参 考 文 献26致 谢28基于文本的聚类算法研究第一章 绪 论1.1 课题研究的背景随着Internet的迅猛发展，信息的爆炸式增加，信息超载问题变的越来越严重，信息的更新率也越来越高，用户在信息海洋里查找信息就像大海捞针一样。搜索引擎服务应运而生，在一定程度上满足了用户查找信息的需要。然而Internet的深入发展和搜索引擎日趋庞大，进一步凸现出海量信息和人们获取所需信息能力的矛盾。那么，如何从中获取特定内容的信息和知识成为摆在人们面前的一道难题。面对互联网时代庞杂无序的海量信息，智能高效地处理和深层次综合利用信息离不开文本挖掘技术，国际上多个国家都抓紧投入文本挖掘技术的研究，以期能对“堆积如山”的信息进行有效的过滤，开发和利用，提取发现具有指导意义的知识。文本挖掘是指从大量文本数据中抽取出事先未知的，可理解的，最终可用的信息或知识的过程，它涉及Web，计算机语言，数据挖掘，信息检索等多个领域，较大程度地解决了信息杂乱的现象，方便用户准确地定位所需的信息和信息分流。文本挖掘可以对大量文档集合的内容进行总结，结构分析，分类，聚类，关联分析，分布分析以及利用文档进行趋势预测等，目前已成为一项具有较大实用价值的关键技术，是组织和管理数据和知识的有力手段。聚类作为一种只是发现的重要方法，是数据挖掘中一项重要的研究课题，它广泛地与中文信息处理技术相结合，应用于网络信息处理中以满足用户快捷地从互联网获得自己需要的信息资源，文本聚类则是聚类问题在文本挖掘中的有效应用，是文本挖掘的重要内容之一。文本聚类是根据文本数据的不同特征，按照事物间的相似性，将其划分为不同数据类的过程。其目的是使同一类别的文本间相似度尽可能大，而不同类别的文本间的相似度尽可能的小。在这一过程中无需指导，是一种典型的无需督分类，从而打破了在许多实际应用中由于缺少形成模式类别过程的知识，或者模式类别的形成非常困难时的挖掘局限性。随着人们对聚类问题更加深入地了解和重视，国内外大量学者不断投身到该项目研究，聚类主要工作集中在寻找针对大型数据库的聚类方法和世界的聚类分析方法上，使得各种成果不断涌现，各个领域的聚类分析算法层出不穷。通过聚类分析可以发现隐藏在数据集中的簇，标识出有意义的模式或分布。不同算法针对与不同规模的数据集而提出，而使用却不仅仅限于某些特定的环境。1.2课题研究的意义文本聚类分析在信息检索领域有相当长的研究历史，近年来在文本数据上的聚类分析研究和应用越来越受到关注。关于文本数据上的聚类分析研究，较早的综合性介绍可以追溯到C.J.van Rijsbergen在IR领域的经典书籍InformationRetrieval中提到的利用文本聚类分析技术来提高信息检索系统的准确率，但近年来此类研究已不多见。上个世纪90年代以来，文本的聚类分析技术研究更多地集中在对大规模的文档集合的浏览上在对用户提出的查询重新组织搜索引擎的查询结果的研究中利用聚类技术重新组织文档集合，用于文档集合的浏览，这是近年来文本聚类中一个广受关注的研究点，2004年SIGIR上MSRA推出的Search Result Clustering技术代表了此类应用研究目前最新的进展。在此类研究中，主要利用K-Means或者后缀树聚类算法的变种来实现其需求。文档聚类分析算法被用于自动产生文档集合的层次结构，比如用于产生类似Yahoo!的网页分类目录结构。近年来，文档聚类算法还在文档分析处理领域中一个新的应用方向话题检测与跟踪中得到了进一步研究与应用。话题检测中利用文档聚类算法从大量的文档中自动地抽取话题，应用于个性化信息服务或者情报分析。在这些应用的推动之下，文本数据上的聚类分析算法层出不穷，各说各的好处，在我们的工程实践中具体该采用哪种算法，如何设计文本聚类算法并对其进行评价都是难以解决的问题。由于算法种类众多，文本聚类算法间缺乏一个进行横向比较与分析的机制，在工程实践中对算法的选择及参数的设定都是经验性的，这对进一步开展研究以及科学地设计算法、分析算法造成了困难。因此，需要对文本聚类分析结果的质量进行评价，利用这种评价机制来指导算法设计、算法选择、算法效能分析、参数优化等。有了文本聚类分析的科学评价机制，我们未来的工作就有据可依，可以更科学地选择算法，分析、设计算法。- 27 -第二章 文本聚类效果影响因素2.1文本聚类过程影响文本聚类分析效果的因素是多方面的，文本聚类分析全过程中的每个步骤都有可能对聚类结果造成影响。下面通过简要描述聚类分析过程来说明对结果可能造成影响的各种因素,如图2-1所示:图2-1 聚类流程聚类分析过程分成三个步骤，通过这三个步骤可以找到影响聚类分析效果四个方面的因素。聚类流程三个步骤的实际处理内容为：(1)文本聚类分析首先将文本表示成机器可计算的形式。不论是抽取文本特征形成一个向量还是抽取文本特征形成一个特殊的结构，对文本的这种机器表示过程简称为文本表示。文本表示过程显然需要领域知识参与，文本中哪些因素可以构成特征，特征中哪些在聚类中可用以及如何使用是文本聚类第一步骤文本表示考察的内容；(2)文本聚类分析的第二个步骤是算法。不同的算法有不同的特性，对相同的数据输入，不同的算法会产生出不同的聚类结果。聚类分析算法可以从不同的角度进行比较，比如是否产生层次聚类结构、是否需要参数、是否能够产生模糊聚类、能否识别出不规则形状的簇等等。目前在文献中出现的聚类分析算法数目众多，但在文本数据上效果孰优孰劣仍没有得到有效的研究。这个步骤中算法的时空效率、聚类结果质量是研发中选择算法的主要标准。该步骤还有一个关键因素就是对象距离(或者相似度)如何定义；(3)第三个步骤是算法中参数的选择。不同的算法对参数的敏感性不同，但是基本上参数的好坏对结果的影响都比较显著。从这三个步骤可以看出影响文本聚类分析效果的因素包括四个方面：文本表示模型、距离度量方法、算法模型和参数优化。参数的设定主观性比较强，如何设定才是一个好的参数缺乏有效的方法，利用本文中实现的聚类算法包和聚类评价方法可以通过指标的变化曲线图寻找算法的最佳参数。2.2文本表示模型在实际的文本聚类分析研究，将实际文本内容变成机器内部表示结构的方法多种多样，可以用词、字、短语、n-Gram、显著性短语等形成向量、树等结构。在经典的研究中通常利用特征(Term，包括字、词、词组等)的词频信息建立文本向量，通过文本向量与文本向量之间的相似度来进行聚类分析。文本表示包括两个问题：表示与计算。表示特指特征的提取，计算指权重的定义和语义相似度的定义。特征提取包括特征的定义和筛选，特征定义和筛选考虑以什么作为文本的特征，并不是所有的词和字都要求或者可以成为特征。特征的权重定义及特征结构上的相似度度量可以选取不同的模型，如向量空间模型、概率模型、语言模型等。文本表示是文本聚类的第一步，该步骤的变化很多，对最终聚类效果的影响也不尽相同。文本表示本质上是对原始文本进行转换，使之在机器上可形式化描述、可计算。特征定义与筛选可以采用不同的特征选择方法，可利用N-Gram、PAT树提取特征、可利用LSI降维转化特征、也可利用语义词典WordNet或者HowNet定义更复杂的特征结构。关于特征定义与筛选可以参考自然语言处理领域中的相关研究，这里不详细介绍。本节接下来主要介绍信息检索和文本分析处理中经常用到的几个检索模型，这几个检索模型根据不同的理论假设推导、定义了不同的特征权重计算方法与语义相似度计算方法，是文本表示模型的重要组成部分。2.2.1布尔模型布尔模型是基于集合论与布尔代数之上的一种简单模型，主要应用于信息检索中。在布尔模型中，一个文档表示成文档中出现的特征的集合，也可以表示成为特征空间上的一个向量，向量中每个分量权重为0或者1，这种布尔模型称为经典布尔模型。经典布尔模型中查询与文档的相关性只能是0或者1，满足查询query中的所有逻辑表达式的文档被判定相关，不满足的被判定为不相关。经典布尔模型只能用于信息检索中计算用户查询与文档的相关性，而无法利用该模型计算两个文档更深层面的相似度，无法在更多的文本处理应用中使用。在经典布尔模型基础上，研究人员又提出了扩展布尔模型(Extended Boolean Approach)，重新定义了And与Or操作符成为多元操作符，使相关性可以成为0,1之间的数。2.2.2向量空间模型 Salton教授提出的向量空间模型简称VSM模型(Vector Space Model)，是信息检索领域中经典的检索模型。向量空间模型将文档表示成一个向量，向量的每一维表示一个特征，这个特征可以是一个字、一个词、一个n-gram或某个复杂的结构。通过对文档的解析处理可以得到这些特征。通常情况下用向量空间模型中的向量表示文档时，需要对文档进行切分(中文分词、英文通过词的分界符识别单词)、停用词处理、英文词的词形还原或者提取词干(Stemming)，经过若干个处理步骤后，基本上就可以得到一系列词，将这些词作为文档的特征。所有的这些词构成一个“空间”，每个词对应着空间中的一维。每个文档可以用文档中的词来表示，这些词及其对应的权重构成一个向量。文档对应特征空间中的一个向量，对应特征空间中的一个点。表2.1 说明VSM模型中文档与向量空间之间的映射关系。表2.1 VSM模型中文档与向量空间之间的映射关系2.3 文本相似度计算文本相似度计算是自然语言处理、Web智能检索、文本分类和文本聚类研究中的一个基本问题。一个文本聚类分析过程的质量取决于对度量标准的选择。因此，在研究聚类算法之前，先要讨论其度量标准。文本相似度是用来衡量文本之间相似程度大小的一个统计量。文本相似度一般定义为界于0和1之间的一个值。如果两文本之间相似度为1，则说明这两个文本对象完全相同；反之，则说明两文本没有相似之处。2.3.1样本间相似度在向量空间模型中，文本相似性的度量方法很多，主要有内积法、Dice系数法、余弦法和距离度量法等。1.内积法通常在文本向量中，最常使用的相似度计算公式就是两个文本向量之间的“内积”运算，其定义为：2.Dice系数法3.余弦法上述各公式中，Sim(di,dj)表示文本di和dj之间的相似程度，分Wki,Wkj分别表示文本di和dj的第k个特征项的权重，n为文本特征项数。Sim值越大表示两个文本越相似，Sim越小则表示两个文本区别越大。4.距离度量法在文本相似度计算中，我们也可以用两个文本之间的距离来度量文本之间的相似程度。常使用的距离公式如下：公式中，Dis(di,dj)表示文本向量di和dj在向量空间的距离，Wki,Wkj分别表示文本的第k个特征项的权重，参数p决定了选择的是哪种距离计算。(1) 当p=1时(2) 当p=2时这就是欧式距离，也就是向量空间中的直线距离。2.3.2簇间相似度在聚类分析中，我们还需要衡量类与类之间的相似度，实现类与类之间的合并或拆分。为了衡量文本集合之间的相似度，常见的方法有：最小距离、最大距离、平均距离、质心法、离差平方和等。2.4文本聚类算法聚类分析作为一个活跃的研究领域，已经出现了很多聚类算法，总体上聚类算法可分为基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法等。每种算法都有各自的优缺点，都有其适用的领域，并不是每一类算法都适合于文本聚类，我们必须根据文本数据的特点对聚类算法进行分析选择。2.4.1基于划分的方法基于划分的聚类算法（Partitioning Method）是文本聚类应用中最为普遍的算法。方法将数据集合分成若干个子集，它根据设定的划分数目k选出k个初始聚类中心，得到一个初始划分，然后采用迭代重定位技术，反复在k个簇之间重新计算每个簇的聚类中心，并重新分配每个簇中的对象，以改进划分的质量。使得到的划分满足“簇内相似度高，簇间相似度小”的聚类原则。典型的划分聚类方法有k-means算法36和k-medoids算法，两者的区别在于簇代表点的计算方法不同。前者使用所有点的均值来代表簇，后者则采用类中某个数据对象来代表簇。为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，各类改进的划分算法逐渐增多。基于划分方法的优点是运行速度快，但该方法必须事先确定k的取值。算法容易局部收敛，且不同的初始聚类中心选取对聚类结果影响较大。为此，应用最广泛的k-means算法有很多变种，他们可能在初始k个聚类中心的选择、相似度的计算和计算聚类中心等策略上有所不同，最终实现聚类结果改进的目标。2.4.2基于层次的方法基于层次的聚类算法（Hierarchical Method）又叫“分级聚类算法”或“树聚类”，它通过分解给定的数据对象集来创建一个层次。这种聚类方法有两种基本的技术途径：一是先把每个对象看作一个簇，然后逐步对簇进行合并，直到所有对象合为一个簇，或满足一定条件为止；二是把所有对象看成一类，根据一些规则不断选择一个簇进行分解，直到满足一些预定的条件，如类的数目达到了预定值，或两个最近簇的距离达到阈值等。前者称为自下而上的凝聚式聚类，后者称为自上而下的分裂式聚类。在文本聚类中，最常见的是凝聚的层次聚类算法。使用该算法可以得到较好的聚类结果，而且该方法无需用户输入参数；但是层次聚类算法的时间复杂度比较高，达到了O(n2)，对于大规模的文本集合，有其不适用性。此外，在层次聚类算法中，一旦两个簇在凝聚和分裂后，这个过程将不能被撤销，簇之间也不能交换对象。如果某一步没有很好的选择要凝聚或者分裂的簇，将会导致低质量的聚类结果。2.4.3基于密度的方法绝大多数划分算法都是基于对象之间的距离进行聚类，这类方法只能发现圆形或球状的簇，较难发现任意形状的簇。为此，提出了基于密度的聚类算法（Density-Based Clustering Method），其主要思想是：只要邻近区域的对象或数据点的数目超过某个阈值，就继续聚类。即对给定类中的每个数据点，在一个给定范围的区域中至少包含某个数目的点，这样就能很好的过滤掉“噪声”数据，发现任意形状的簇。其基本出发点是，寻找低密度区域分离的高密度区域。具有代表性的方法是DBSCAN（Density Based Spatial Clustering of Applications withNoise），它是将密度足够大的那部分记录组成类，可以在带有“噪声”的空间数据库中发现任意形状的聚类，但它需要用户主观来选择参数，从而影响了最终的聚类结果。基于密度的聚类算法在当前的文献中较少被用于文本聚类中。这是由于文本间的相似度不稳定，同属一簇的文本，有些文本间的相似度较高，所以密度高；有些相似度较低，所以密度低。如果根据全局的密度参数进行判断，显然是不适合的。并且密度单元的计算复杂度大，需要建立空间索引来降低计算量，且对数据维数的伸缩性较差。2.4.4基于网格的方法基于网格的算法（Grid-Based Clustering Method）把对象空间量化为有限数目的单元，形成了一个网络结构。所用的聚类操作都在整个网络结构即量化的空间上进行。这种方法的一个突出的优点就是处理速度很快，其处理时间独立于数据对象的数目，只与量化空间中的每一维的单元数目有关。此外，它还可以处理高维数据。代表算法有统计信息网格法STING算法、聚类高维空间法CLIQUE算法、基于小波变换的聚类法WAVE-CLUSTER算法。STING（Statistical Information Grid），利用了存储在网格中的统计信息，它不但能并行处理且能增量更新，因而效率很高，缺点是簇的质量和精确性欠佳。WaveCluster（Clustering Using Wavelet Transformation）是一种多分辨率的聚类算法。其主要优点是能有效地处理大规模数据集；能发现任意形状的簇；能成功地处理孤立点；对于输入的顺序不敏感；不要求指定任何参数；且效率和聚类质量都比较高。CLIQUE（Clustering in Quest）是一种将基于密度的方法与基于网格的方法相结合的算法，能有效处理大型数据库的高维数据。它对输入顺序不敏感，无需假设任何规范的数据分布。另外，它还具有良好的可伸缩性。但由于方法大大简化，聚类结果的精确可能降低。2.4.5基于模型的方法基于模型的算法（Model-Based Clustering Method）试图优化给定的数据和某些数学模型之间的适应性。这样的算法经常是基于这样的假设，数据是根据潜在的概率分布生成的。它通过为每个聚类假设一个模型来发现符合相应模型的数据对象。根据标准统计方法并综合考虑“噪声”或异常数据，该方法可以自动确定聚类个数，从而得到鲁棒性较好的聚类方法。基于模型的算法主要有两类，分别为统计学方法和神经网络方法。大多数的概念聚类采用的是统计的方法，即在决定一个类时，用可能性的描述语句，典型的代表就是COBWEB，它是一个通用且简单的聚类方法。基于神经网络的聚类方法是将每一个类看作一个标本，它是这个类型的“典型”，但不需要和某个具体的对象或例子相对应。根据新对象和这个标本之间的距离，就可以将这个对象进行分类了。如基于SOM的文档聚类方法在数字图书馆等领域得到了较好的应用。聚类分析算法众多，应用于文档的聚类分析算法也种类繁多，如何评价文档聚类分析的效果，目前还没有一个确定的说法。在实际的应用中一般都是实现几种算法，然后用人工判断的方法去选择合适的算法以及算法相对应的参数。这么多的算法虽然带来了更多的选择，但同时也带来了应用上的困难，因此有必要在一个统一的尺度上来衡量一些算法并对他们做出评价。2.5本章小结本章主要介绍了影响文本聚类结果的三方面主要因素：文本表示模型、相似度计算方法及聚类算法。文本聚类过程中每个步骤都有可能影响最终的聚类效果，各方面因素变化情形众多，在实际研究和工程应用中，聚类评价工作困难重重。为了更好地评价聚类结果，我们在下一章将详细介绍已有的文本聚类评价方法，比较各自的优缺点。第三章 k-均值聚类算法3.1 K-均值聚类算法的思想3.1.1 K-均值聚类算法的基本思想一九六七年，麦克奎因B. Mac Queen提出了K-均值聚类算法，用来处理数据聚类的问题，该种算法由于其算法简便，又很早提出，因此在科学和工业领域的应用中影响力极为广泛。该算法首先随机选取k个数据点作为n个簇的初始簇中心，集合中每个数据点被划分到与其距离最近的簇中心所在的类簇之中，形成了k个聚类的初始分布。对分配完的每一个类簇计算新的簇中心，然后继续进行数据分配过程，这样迭代若干次后，若簇中心不再发生变化，则说明数据对象全部分配到自己所在的类簇中，聚类准则函数收敛，否则继续进行迭代过程，直至收敛。这里的聚类准则函数一般采用聚类误差平方和准则函数。本算法的一个特点就是在每一次的迭代过程中都要对全体数据点的分配进行调整，然后重新计算簇中心，进入下一次的迭代过程，若在某一次迭代过程中，所有数据点的位置没有变化，相应的簇中心也没有变化，此时标志着聚类准则函数已经收敛，算法结束。3.1.2 K-均值聚类算法的算法流程原始的K-均值聚类算法:输入:数据集x=x1，x2，xn，聚类数目k;输出: k个类簇cj，j=1，2，kstepl令I=1，随机选取k个数据点作为k个类簇的初始簇中心，mj(I) j=1，2，k;step2计算每一个数据点与这k个簇中心的距离d(xi，mj，(i), i=1，2，n，j=1，2，k，,如果满足d(xi，mj(I)=mind(xi， mj(I)，j=1，2，k则xi cj.steP3计算k个新的聚类中心step4判断:若mj(i+1) mj(I)，j=1，2，k，则I=i+1，返回step2:否则，算法结束。K-均值聚类算法在执行过程中还可以加入聚类准则函数来终止迭代过程，一般采用聚类误差平方和准则函数，即在上面算法流程中的step4中计算聚类误差平方和J，然后加入判断，若两次的J值没有明显变化，则说明J值已经收敛，结束算法，否则转入step2继续执行。具体流程如下:Stepl初始化l随机指定k个聚类中心(ml，m2，mk);Step2分配xi对每一个样本xi，找到离它最近的聚类中心，并将其分配到该类: Step3修正簇中心重新计算各簇中心Step4计算偏差 Step5收敛判断如果J值收敛，则return(m1， m2，mk)，算法终止;否则，转Step2。从上面的算法思想及流程中可以看出，k个类簇的初始簇中心点的选取对聚类的最终结果至关重要，算法中，每一次迭代都把数据点划分到与其距离最近的簇中心所在的类簇中去，然后重新计算簇中心，进而反复迭代，直到每一个数据点都不再重新划分为止。3.1.3 K-均值算法的优缺点分析K-均值算法是一种基于划分的聚类算法，它通过不断的迭代过程来进行聚类，当算法收敛到一个结束条件时就终止迭代过程，输出聚类结果。由于其算法思想简便，又容易实现，因此K-均值算法己成为一种目前最常用的聚类算法之一。然而K-means过分依赖于初始中心点的选取，且容易受噪音点的影响。为解决这一问题，出现了各种基于全局最优化思想的K-均值聚类方法，比如模拟退火算法、遗传算法等。然而这些技术并没有得到广泛认可，在许多实际应用中还是反复利用K-均值聚类算法来解决问题。K-均值聚类算法采用迭代式的过程对样本点进行分配来寻求最终的聚类结果，其终止条件是所有样本的位置不再变化，其迭代过程可以概括如下:(l)分配样本点，即对每个样本点，将其分配到与其距离最近的簇中心所在的类簇中;(2)重新计算簇中心，对于每一个重新分配后的类簇，重新计算其簇中心。和大多数的聚类算法一样，K-均值聚类算法也有其自身的局限，主要局限如下:(1)K-均值聚类算法中的聚类数目即K值需要由用户预先给出。从K-均值聚类算法的算法流程中可以看出，K值作为一个需要预先确定的参数，在已知的前提下才能执行K-均值聚类算法，而在实际应用中，需要聚类的数据究竟要分成多少个类别，往往不是被用户所知的。当聚类数目不被人所知的情况下，人们往往需要结合其它算法来获取聚类数目，即K值。往往获取K值的代价要比K-均值聚类算法的代价大得多，因此K值的不确定性是K-均值聚类算法的一个很大的不足之处。(2)K-均值聚类算法严重依赖于初始簇中心点的选取。K-均值聚类算法随机的选取K个初始簇中心点，并针对这K个簇中心点进行迭代运算，即重新分配数据点和重新计算簇中心的运算，直到所有的数据点位置不再变化或聚类误差准则函数不再变化。这样就导致了K-均值聚类算法对初始簇中心点的严重依赖性。初始簇中心点选取不当很容易造成聚类结果陷入局部最优解甚至或导致错误的聚