最新版基于文本的聚类算法研究毕业设计.docx

最新版基于文本的聚类算法研究毕业设计.docx

《最新版基于文本的聚类算法研究毕业设计.docx》由会员分享，可在线阅读，更多相关《最新版基于文本的聚类算法研究毕业设计.docx（36页珍藏版）》请在冰点文库上搜索。

最新版基于文本的聚类算法研究毕业设计

摘要

聚类作为一种知识发现的重要方法，它广泛地与中文信息处理技术相结合，应用于网络信息处理中以满足用户快捷地从互联网获得自己需要的信息资源。

文本聚类是聚类问题在文本挖掘中的有效应用，它根据文本数据的不同特征，按照文本间的相似性，将其分为不同的文本簇。

其目的是要使同一类别的文本间的相似度尽可能大，而不同类别的文本间的相似度尽可能的小。

整个聚类过程无需指导，事先对数据结构未知，是一种典型的无监督分类。

本文首先介绍了文本聚类的相关的技术，包括文本聚类的过程，文本表示模型，相似度计算及常见聚类算法。

本文主要研究的聚类主要方法是k-均值和SOM算法，介绍了两种算法的基本思想和实现步骤，并分析两种算法的聚类效果。

同时介绍了两种算法的改进算法。

关键词：

文本聚类聚类方法K-MEANSOM

Abstract

Clusteringasanimportantknowledgediscoverymethod,whichextensivelywithChineseinformationprocessingtechnology,usedinnetworkinformationprocessingtomeettheuserstoquicklyaccessfromtheInternet,theinformationresourcestheyneed.Textclusteringisaclusteringproblemintheeffectiveapplicationoftextmining,whichaccordingtothedifferentcharacteristicsoftextdata,accordingtothesimilaritybetweenthetext,thetextwillbedividedintodifferentclusters.Theaimistomakethesameclassaslargeaspossiblethesimilaritybetweenthetext,anddifferenttypesoftextassmallaspossiblethesimilaritybetween.Theclusteringprocesswithoutguidance,priortothedatastructureisunknown,isatypicalunsupervisedclassification.

Thispaperstudiestheeffectofinfluencingfactorsthattextclustering,textrepresentationofthemodelsuchastheBooleanmodel,vectorspacemodel,probabilisticretrievalmodelandlanguagemodel.Alsostudiedtheanalysisofsuchtextclusteringalgorithm:

.Alsostudiedthetextclusteringalgorithmanalysisandmethodsofimprovement.

Keywords：

Textclusteringclusteringmethodk-meansom

毕业设计（论文）原创性声明和使用授权说明

原创性声明

本人郑重承诺：

所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。

尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得及其它教育机构的学位或学历而使用过的材料。

对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。

作者签名：

　　　　　日　期：

指导教师签名：

　　　　　日　　期：

使用授权说明

本人完全了解大学关于收集、保存、使用毕业设计（论文）的规定，即：

按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。

作者签名：

　　　　　日　期：

学位论文原创性声明

本人郑重声明：

所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。

除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。

对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。

本人完全意识到本声明的法律后果由本人承担。

作者签名：

日期：

年月日

学位论文版权使用授权书

本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。

本人授权　　　　大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。

涉密论文按学校规定处理。

作者签名：

日期：

年月日

导师签名：

日期：

年月日

指导教师评阅书

指导教师评价：

一、撰写（设计）过程

1、学生在论文（设计）过程中的治学态度、工作精神

□优□良□中□及格□不及格

2、学生掌握专业知识、技能的扎实程度

□优□良□中□及格□不及格

3、学生综合运用所学知识和专业技能分析和解决问题的能力

□优□良□中□及格□不及格

4、研究方法的科学性；技术线路的可行性；设计方案的合理性

□优□良□中□及格□不及格

5、完成毕业论文（设计）期间的出勤情况

□优□良□中□及格□不及格

二、论文（设计）质量

1、论文（设计）的整体结构是否符合撰写规范？

□优□良□中□及格□不及格

2、是否完成指定的论文（设计）任务（包括装订及附件）？

□优□良□中□及格□不及格

三、论文（设计）水平

1、论文（设计）的理论意义或对解决实际问题的指导意义

□优□良□中□及格□不及格

2、论文的观念是否有新意？

设计是否有创意？

□优□良□中□及格□不及格

3、论文（设计说明书）所体现的整体水平

□优□良□中□及格□不及格

建议成绩：

□优□良□中□及格□不及格

（在所选等级前的□内画“√”）

指导教师：

（签名）单位：

（盖章）

年月日

评阅教师评阅书

评阅教师评价：

一、论文（设计）质量

1、论文（设计）的整体结构是否符合撰写规范？

□优□良□中□及格□不及格

2、是否完成指定的论文（设计）任务（包括装订及附件）？

□优□良□中□及格□不及格

二、论文（设计）水平

1、论文（设计）的理论意义或对解决实际问题的指导意义

□优□良□中□及格□不及格

2、论文的观念是否有新意？

设计是否有创意？

□优□良□中□及格□不及格

3、论文（设计说明书）所体现的整体水平

□优□良□中□及格□不及格

建议成绩：

□优□良□中□及格□不及格

（在所选等级前的□内画“√”）

评阅教师：

（签名）单位：

（盖章）

年月日

教研室（或答辩小组）及教学系意见

教研室（或答辩小组）评价：

一、答辩过程

1、毕业论文（设计）的基本要点和见解的叙述情况

□优□良□中□及格□不及格

2、对答辩问题的反应、理解、表达情况

□优□良□中□及格□不及格

3、学生答辩过程中的精神状态

□优□良□中□及格□不及格

二、论文（设计）质量

1、论文（设计）的整体结构是否符合撰写规范？

□优□良□中□及格□不及格

2、是否完成指定的论文（设计）任务（包括装订及附件）？

□优□良□中□及格□不及格

三、论文（设计）水平

1、论文（设计）的理论意义或对解决实际问题的指导意义

□优□良□中□及格□不及格

2、论文的观念是否有新意？

设计是否有创意？

□优□良□中□及格□不及格

3、论文（设计说明书）所体现的整体水平

□优□良□中□及格□不及格

评定成绩：

□优□良□中□及格□不及格

（在所选等级前的□内画“√”）

教研室主任（或答辩小组组长）：

（签名）

年月日

教学系意见：

系主任：

（签名）

年月日

摘要IV

AbstractV

目录VI

第一章绪论1

1.1课题研究的背景1

1.2课题研究的意义2

第二章文本聚类效果影响因素3

2.1文本聚类过程3

2.2文本表示模型4

2.2.1布尔模型5

2.2.2向量空间模型5

2.3文本相似度计算6

2.4文本聚类算法8

2.5本章小结11

第三章k-均值聚类算法12

3.1K-均值聚类算法的思想12

3.1.1K-均值聚类算法的基本思想12

3.1.2K-均值聚类算法的算法流程12

3.1.3K-均值算法的优缺点分析13

3.1.4现有的对于K-均值聚类算法的改进15

3.1.5现有基于初始中心点改进的K-均值聚类算法16

3.2本章小结17

第四章SOM聚类算法18

4.1SOM聚类算法的网络特性与基本流程18

4.1.1SOM网络的特性18

4.1.2SOM网络聚类的基本流程19

4.1.3SOM网络聚类的优点及存在的问题19

4.2改进的SOM聚类方法20

4.2.1已有的学习策略改进20

4.2.2等离差理论在神经元获胜策略中的应用改进21

4.2.3初始化连接权值22

4.2.4已有的初始化连接权的方法22

4.2.5新的确定初始权值的方法23

4.3本章小结25

参考文献26

致谢28

第一章绪论

1.1课题研究的背景

随着Internet的迅猛发展，信息的爆炸式增加，信息超载问题变的越来越严重，信息的更新率也越来越高，用户在信息海洋里查找信息就像大海捞针一样。

搜索引擎服务应运而生，在一定程度上满足了用户查找信息的需要。

然而Internet的深入发展和搜索引擎日趋庞大，进一步凸现出海量信息和人们获取所需信息能力的矛盾。

那么，如何从中获取特定内容的信息和知识成为摆在人们面前的一道难题。

面对互联网时代庞杂无序的海量信息，智能高效地处理和深层次综合利用信息离不开文本挖掘技术，国际上多个国家都抓紧投入文本挖掘技术的研究，以期能对“堆积如山”的信息进行有效的过滤，开发和利用，提取发现具有指导意义的知识。

文本挖掘是指从大量文本数据中抽取出事先未知的，可理解的，最终可用的信息或知识的过程，它涉及Web，计算机语言，数据挖掘，信息检索等多个领域，较大程度地解决了信息杂乱的现象，方便用户准确地定位所需的信息和信息分流。

文本挖掘可以对大量文档集合的内容进行总结，结构分析，分类，聚类，关联分析，分布分析以及利用文档进行趋势预测等，目前已成为一项具有较大实用价值的关键技术，是组织和管理数据和知识的有力手段。

聚类作为一种只是发现的重要方法，是数据挖掘中一项重要的研究课题，它广泛地与中文信息处理技术相结合，应用于网络信息处理中以满足用户快捷地从互联网获得自己需要的信息资源，文本聚类则是聚类问题在文本挖掘中的有效应用，是文本挖掘的重要内容之一。

文本聚类是根据文本数据的不同特征，按照事物间的相似性，将其划分为不同数据类的过程。

其目的是使同一类别的文本间相似度尽可能大，而不同类别的文本间的相似度尽可能的小。

在这一过程中无需指导，是一种典型的无需督分类，从而打破了在许多实际应用中由于缺少形成模式类别过程的知识，或者模式类别的形成非常困难时的挖掘局限性。

随着人们对聚类问题更加深入地了解和重视，国内外大量学者不断投身到该项目研究，聚类主要工作集中在寻找针对大型数据库的聚类方法和世界的聚类分析方法上，使得各种成果不断涌现，各个领域的聚类分析算法层出不穷。

通过聚类分析可以发现隐藏在数据集中的簇，标识出有意义的模式或分布。

不同算法针对与不同规模的数据集而提出，而使用却不仅仅限于某些特定的环境。

1.2课题研究的意义

文本聚类分析在信息检索领域有相当长的研究历史，近年来在文本数据上的聚类分析研究和应用越来越受到关注。

关于文本数据上的聚类分析研究，较早的综合性介绍可以追溯到C.J.vanRijsbergen在IR领域的经典书籍《InformationRetrieval》中提到的利用文本聚类分析技术来提高信息检索系统的准确率，但近年来此类研究已不多见。

上个世纪90年代以来，文本的聚类分析技术研究更多地集中在对大规模的文档集合的浏览上在对用户提出的查询重新组织搜索引擎的查询结果的研究中利用聚类技术重新组织文档集合，用于文档集合的浏览，这是近年来文本聚类中一个广受关注的研究点，2004年SIGIR上MSRA推出的SearchResultClustering技术代表了此类应用研究目前最新的进展。

在此类研究中，主要利用K-Means或者后缀树聚类算法的变种来实现其需求。

文档聚类分析算法被用于自动产生文档集合的层次结构，比如用于产生类似Yahoo!

的网页分类目录结构。

近年来，文档聚类算法还在文档分析处理领域中一个新的应用方向话题检测与跟踪中得到了进一步研究与应用。

话题检测中利用文档聚类算法从大量的文档中自动地抽取话题，应用于个性化信息服务或者情报分析。

在这些应用的推动之下，文本数据上的聚类分析算法层出不穷，各说各的好处，在我们的工程实践中具体该采用哪种算法，如何设计文本聚类算法并对其进行评价都是难以解决的问题。

由于算法种类众多，文本聚类算法间缺乏一个进行横向比较与分析的机制，在工程实践中对算法的选择及参数的设定都是经验性的，这对进一步开展研究以及科学地设计算法、分析算法造成了困难。

因此，需要对文本聚类分析结果的质量进行评价，利用这种评价机制来指导算法设计、算法选择、算法效能分析、参数优化等。

有了文本聚类分析的科学评价机制，我们未来的工作就有据可依，可以更科学地选择算法，分析、设计算法。

第二章文本聚类效果影响因素

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中的所有逻辑表达式的文档被判定相关，不满足的被判定为不相关。

经典布尔模型只能用于信息检索中计算用户查询与文档的相关性，而无法利用该模型计算两个文档更深层面的相似度，无法在更多的文本处理应用中使用。

在经典布尔模型基础上，研究人员又提出了扩展布尔模型（ExtendedBooleanApproach），重新定义了And与Or操作符成为多元操作符，使相关性可以成为[0,1]之间的数。

2.2.2向量空间模型

Salton教授提出的向量空间模型简称VSM模型（VectorSpaceModel），是信息检索领域中经典的检索模型。

向量空间模型将文档表示成一个向量，向量的每一维表示一个特征，这个特征可以是一个字、一个词、一个n-gram或某个复杂的结构。

通过对文档的解析处理可以得到这些特征。

通常情况下用向量空间模型中的向量表示文档时，需要对文档进行切分（中文分词、英文通过词的分界符识别单词）、停用词处理、英文词的词形还原或者提取词干（Stemming），经过若干个处理步骤后，基本上就可以得到一系列词，将这些词作为文档的特征。

所有的这些词构成一个“空间”，每个词对应着空间中的一维。

每个文档可以用文档中的词来表示，这些词及其对应的权重构成一个向量。

文档对应特征空间中的一个向量，对应特征空间中的一个点。

表2.1说明VSM模型中文档与向量空间之间的映射关系。

表2.1VSM模型中文档与向量空间之间的映射关系

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基于划分的方法

基于划分的聚类算法（PartitioningMethod）是文本聚类应用中最为普遍的算法。

方法将数据集合分成若干个子集，它根据设定的划分数目k选出k个初始聚类中心，得到一个初始划分，然后采用迭代重定位技术，反复在k个簇之间重新计算每个簇的聚类中心，并重新分配每个簇中的对象，以改进划分的质量。

使得到的划分满足“簇内相似度高，簇间相似度小”的聚类原则。

典型的划分聚类方法有k-means算法[36]和k-medoids算法，两者的区别在于簇代表点的计算方法不同。

前者使用所有点的均值来代表簇，后者则采用类中某个数据对象来代表簇。

为了对大规模的数据集进行聚类，以及处理复杂形状的聚类，各类改进的划分算法逐渐增多。

基于划分方法的优点是运行速度快，但该方法必须事先确定k的取值。

算法容易局部收敛，且不同的初始聚类中心选取对聚类结果影响较大。

为此，应用最广泛的k-means算法有很多变种，他们可能在初始k个聚类中心的选择、相似度的计算和计算聚类中心等策略上有所不同，最终实现聚类结果改进的目标。

2.4.2基于层次的方法

基于层次的聚类算法（HierarchicalMethod）又叫“分级聚类算法”或“树聚类”，它通过分解给定的数据对象集来创建一个层次。

这种聚类方法有两种基本的技术途径：

一是先把每个对象看作一个簇，然后逐步对簇进行合并，直到所有对象合为一个簇，或满足一定条件为止；二是把所有对象看成一类，根据一些规则不断选择一个簇进行分解，直到满足一些预定的条件，如类的数目达到了预定值，或两个最近簇的距离达到阈值等。

前者称为自下而上的