（计算机应用技术专业论文）组合聚类方法在文本聚类中的应用研究.pdf

硕士学位论文 m a s t e r st h e s i s 中文摘要 互联网时代，w e b 中的文本数量和访问这些文档的人数一直在海量增加，对 这些数量巨大的文本信息，人们要想找出一些相关主题的内容，仅靠人工的分类 方法已经不能符合实际需要了。借助计算机来帮助我们进行w e b 内容的整理再 进行后继的处理是目前一种常见的手段。文本聚类研究是数据挖掘非常热门的研 究课题之一。 目前研究文本聚类的算法有很多，主要集中在单次聚类及其相关参数的改进 上，本文研究的重点是组合聚类方法。 首先分析了文本聚类中比较流行的3 种聚类算法( s o m 聚类算法、k - m e a n s 聚类算法、f c m 聚类算法) ，对这3 种算法进行了详细的介绍并分析了各自的优 缺点。 然后，结合文本特征选择方法的特点分析，提出了两种组合聚类流程模型， 从理论上说明其有效性及特点，并详细介绍了与其对应的聚类算法：d s o m f s k - m e a n s 算法和d s o m f s f c m 算法，其中，在d s o m f s f c m 算法中，还使 用了优化函数对f c m 算法中的隶属度函数进行调整，降低了孤立点数据对聚类 效果的影响。 最后，为了验证组合聚类算法的有效性，我们把这两种组合算法与各自相对 应的单次聚类算法和没有结合特征选择的组合聚类算法进行对比，对实验结果进 行分析，证明了组合聚类算法的优越性。 关键词：数据挖掘；组合聚类；特征选择；d s o m f s k - m e a n s 算法； d s o m f s f c m 算法 硕士学位论文 m a s t e r st h e s i s a b s t r a c t w i t ht h ew i d e l yu s eo fi n t e m e t ，v a r i o u st y p e so ft e x tm e s s a g e sc o n t i n u et o g r o w t he x p l o s i v e l yi nt h en e t w o r k s ，t h e i rn u m b e ri si n c a l c u l a b l e ，i ti sd i f f i c u l tf o r p e o p l et oi d e n t i f yt h er e l a t e dt o p i c sf r o mt h ee n o r m o u st e x tm e s s a g e s ，u s i n gc o m p u t e r t oh e l pt ot h ec l a s s i f i c a t i o ni sag o o dm e t h o d ，s ot e x tc l u s t e r i n gh a sb e c o m eav e r yh o t r e s e a r c ht o p i ci nd a t am i n i n gr e s e a r c ha r e a s t h e r ea r eal o to fc l u s t e r i n ga l g o r i t h m sn o w ，w h i c hm a i n l yc o n c e n t r a t ei ns i n g l e l y c l u s t e r i n g a n dt h e i rr e l a t e dp a r a m e t e r s i m p r o v e m e n t s t h i s p a p e rf o c u s e s o n c o m b i n a t o r i a l c l u s t e r i n gm e t h o d s 。 f i r s to fa l l ，t h r e ek i n d so fp o p u l a rt e x tc l u s t e r i n ga l g o r i t h m s ( s o mc l u s t e r i n g a l g o r i t h m ，k - m e a n sc l u s t e r i n ga l g o r i t h m , f c mc l u s t e r i n ga l g o r i t h m ) h a v eb e e n i n t r o d u c e dd e t a i l l y , t h e i ra d v a n t a g e sa n dd i s a d v a n t a g e sa l s ob ea n a l y s i s e d t h e n ，c o m b i n e d 谢t l lt h em e t h o d so ft h ef e a t u r es e l e c t i o n ，t w oc l u s t e r i n gf l o w m o d e l sa r ep r o p o s e d ，t h e i re f f e c t i v e n e s sa n dc h a r a c t e r i s t i c sh a v eb e e ne x p l a i n e d t h e o r e t i c a l l y ，a n dt h e nt h ec o r r e s p o n d i n gc l u s t e r i n ga l g o r i t h m ( d s o m f s k - m e a n s a l g o r i t h ma n dd s o m - f s f c ma l g o r i t h m ) h a v eb e e nd e s c r i b e di nd e t a i l 。 f i n a l l y , i no r d e rt ov e r i f yt h ee f f e c t i v e n e s so fc o m b i n a t o r i a lc l u s t e r i n ga l g o r i t h m s ， w e c o m p a r et h e s et w oa l g o r i t h m st ot h e i rc o r r e s p o n d i n gs i n g l ec l u s t e r i n ga l g o r i t h m s o rt h e i rc o r r e s p o n d i n gc o m p o s i t ec l u s t e r i n ga l g o r i t h m sw i t h o u tf e a t u r es e l e c t i o n , t h e r e s u l t sa n a l y z eo ft h ee x p e r i m e n t sp r o v e dt h a tt h ec o m b i n a t o r i a lc l u s t e r i n ga l g o r i t h m s a r es u p e r i o rt ot h ec o r r e s p o n d i n gs i n g l ec l u s t e r i n ga l g o r i t h m s k e y w o r d s ：d a t a m i n i n g ； c o m b i n a t o r i a l c l u s t e r i n g ； f e a t u r e s e l e c t i o n ； d s o m - f s - k - m e a n sa l g o r i t h m ；d s o m f s f c ma l g o r i t h m 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工 作所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：方吾 日期：妒。和石月9 日 作者签名：万舌日期：妒。孵6 月9 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有 权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同 意华中师范大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分 内容。 作者签名：方春导师签名 兰! 竺生o 日o o 三掣o o ! 仁 作暑签名：方着 吼伽7 年6 月7 日 导师签名：刷艘乞 呐：r1 日 硕士学位论文 m a s t e r st h e s i s 1 1 课题背景 第一章绪论 近十几年来，随着信息技术的高速发展，人们利用信息技术的能力大幅度 提高，但各类信息每天都在i n t e r n e t 上爆炸式地增长，w e b 上信息的内容也越来 越复杂混乱，仅仅依靠人工整理和统计学方法已经远远不能满足现实需要了，即 使是使用检索，而目前的大部分搜索机制都是基于点击链接数的原理，会返回给 用户很多无关主题的东西。所以现在迫切要求智能地处理海量数据的技术，从海 量数据中找出有用的信息和规律，从而达到为生活或者商业决策服务的目的。数 据挖掘正式应这种需求而生。数据挖掘的目的就是从海量数据中寻找有用的模式 和信息的技术 1 】，它是目前研究领域非常活跃的研究课题。 比如，如何衡量一个网站的成功? 什么广告人气最高? 主要访客来自哪些 群体? 什么原因让他们前来? 这些都是数据挖掘研究范围里的问题。w e b 上的 信息多种多样，有图像，声音，视频动画，文本等，其中，文本数据占有最大比 例，文本聚类分析是数据挖掘的一个很重要的方面，是目前数据挖掘中的研究热 点。 文本聚类能被广泛应用到各个领域，例如，搜索引擎，商业管理，信息安 全，离群点检测，电子商务等领域 2 】。所以文本聚类分析作为挖掘技术的基础， 正吸引着无数学者的关注。 1 2 研究意义 对一个文本数据集，在文本聚类时，相似的文本被分为一簇，不同类的文本 被聚到不同的簇，这个过程是靠计算机根据文本间的相似度进行全自动处理的， 文本聚类操作时，聚类事先不需要知道文本的类别信息，属于无教师指导的学习 方式。聚类方法可以被用来对w e b 上的文档库进行摘要和导航等，对w e b 上 的文本内容进行预处理，方便对这些文档进行后续处理。 为了在提高查准率和查全率上有质的飞跃，我们需要研究出更好的聚类算法 来达到此目的，聚类算法的发展可以带了检索引擎等技术的准确率飞跃，高效率 硕士学位论文 m a s t e r st h e s i s 的聚类算法很有实际用处同时也是一个很大的挑战，具有重要现实意义。 1 3 国内外研究现状 目前，国外对英文文本聚类技术的研究已趋于成熟，研究成果已经被应用在 很多领域，取得了不少令人瞩目的研究成果。 ( 1 ) 在理论研究方面，m o n t e s 等人提出了基于概念图的文本挖掘 3 】；印度 理工学院的b h o o p e s hc h o u d h a r y 和p u s h p a k 提出了基于语义聚类的方法等 4 】。 ( 2 ) 在应用方面，也产生了一些可用的文本挖掘系统：如自动分类新闻稿 件的文本分类器。自动分类w e b 页的文本分类器，自动跟踪用户阅读兴趣的分类 分析器等等【5 】。 国内的文本挖掘技术起步比较晚，一方面是互联网是从1 9 9 4 年才开始进入 中国，另一方面是因为中国汉字的特殊和复杂性。尽管如此，国内学者在文本挖 掘方面还是取得一些好的成绩。比如。中国科学院做了中文分词系统，准确率高 达9 8 以上。北京科技大学的唐管等人也将文本挖掘技术应用在了远程教育系统 中，微软亚洲研究院等多家研究机构的学者都在积极投身于这方面研究。在应用 方面，国内的一些文本挖掘软件大部分都是在简单地统计词频，在分析功能问题 上效果不佳，总的来说，国内在文本挖掘方面还处于起步研究阶段，研究技术处 于相对落后水平。 文本聚类是文本挖掘和检索技术的重要基础，目前，国内的文本聚类研究很 多集中在对某一算法单个参数的改进上面。而文本聚类是个非常复杂的过程，包 含多方面的内容，涉及到多种技术，每一个环节的完善都可能带来聚类效果的大 大改进。 目前文本聚类方面，常用的聚类方法主要有基于划分的方法、凝聚的层次 聚类方法、基于密度的聚类方法及基于神经网络的方法 7 】。单词聚类算法一般都 或多或少有这方面或者那方面的缺陷，很多学者对聚类算法的研究也倾向于去改 进单词聚类算法某方面的参数，这样可以带来微观上的改进效果，但我们同时可 以从宏观上来对聚类算法进行组合，综合这些算法各自的优点，通过互补避免各 自的缺点，如果还能巧妙结合算法以外的其他技术，这样势必可以带来聚类效果 上的巨大改进，因此，本文考虑了将聚类方法变成两阶段或者多阶段进行，即如 何采用组合聚类的方法并结合相应特征选择来增强聚类的效果。 2 硕士学位论文 m a s t e r st h e s i s 因此，可以考虑将聚类方法变成两阶段或者多阶段进行。本文探讨了如何采 用组合聚类的方法并结合相应特征选择来增强聚类的效果。 1 4 本文研究内容 本研究的主要内容包括四个方面： 1 首先分析了文本聚类的相关技术，详细探讨了特征选择方法。 2 、研究当前流行的3 种流行聚类算法( s o m 聚类算法、k m e a n s 聚类算法、 f c m 聚类算法) 。 3 、提出了组合聚类流程模型一，从理论上说明其有效性及特点，并详细研 究了与其对应的聚类算法：d s o m f s k m e a n s 算法 4 、提出了组合聚类流程模型二，从理论上说明其有效性及特点，并详细研 究了与其对应的聚类算法：d s o m f s f c m 算法，还使用了优化函数对f c m 算 法中加以改进，更好地增强了聚类的效果。 1 5 论文组织结构 本文的组织结构如下 第一章绪论主要叙述了本课题的研究背景，国内外研究现状，研究意义及 本文的研究内容。 第二章文本聚类的相关技术主要介绍了聚类分析的应用，中文文本聚类 的一般过程，文本聚类与文本分类的区别，聚类算法的分类情况，文本的表示等， 重点介绍了向量空间模型( v s m ) ，并详细讨论了文本的特征选择方法和相似性 度量问题。 第三章组合聚类算法的分析与改进简单介绍了三种常见的聚类算法，在分 析了上述三种算法的基础上，结合特征选择技术提出了两种组合聚类算法的流程 模型，从理论上说明其有效性及特点，并详细研究了与其对应的两种聚类算法。 第四章实验证明对比分析第三章中的各种算法，用实验验证了第三章中 的两种改进的方法的有效性。 第五章总结与展望再次总结了本文的研究工作对存在的问题进行了总结 并提出了进一步研究方向。 3 硕士学位论文 m a s t e r st h e s i $ 第二章文本聚类的相关技术 2 1 聚类分析介绍 2 1 1 文本挖掘 我们现在生活在一个信息时代，每天要与电脑和网络上的海量数据打交道。 如何充分利用这些大量数据信息来为我们的生活服务，如何从中找出有用的规 律，已成为人类急需解决的问题。比如，该如何测量一个网站是否成功? 哪些内 容、广告是人气最旺的? 主要访客是哪些人? 什么原因吸引他们前来? 以上种种 皆属于数据挖掘分析的范畴，数据挖掘就是一种从海量数据中寻找规律和模式的 过程【8 】。 i n t e m e t 上的信息有文本、声音、图像，视频等，其中文本的比例在信息中 占主导地位，因此文本挖掘技术成为当前研究领域的热点，文本挖掘技术也已经 应用到了很多领域，比如：文本摘要，文本分类，检索引擎，文本过滤，电子商 务，信息安全等，所以文本挖掘是目前研究领域的热点。 2 1 2 文本聚类与文本分类 本分类是指按照预定义好的类别信息将文本分到各个类属中去，在操作进行 前，该分多少类，每个文档属于什么类别的都是已经定义好的，这个过程是有监 督的学习过程。 而事先无类别指导的文本分类我们称之为文本聚类，在操作前；我们不知道 要分多少类，也不知道哪个文档具体属于哪类，只是根据相似度衡量去让这些文 本自动聚合或者分散，相似的聚集到一块，不相同的相互区分开来，是无教师指 导的学习过程。 2 1 3 聚类方法的分类 目前已经有很多种聚类方法，但对它们很难提出明确的分类界限，一种聚类 方法可能同时具有几种类别的特征，但可以根据他们的聚类原理、组织方式进行 大概的区分。主要有如下几类聚类算法【2 】： ( 1 ) 基于划分的方法 4 硕士学位论文 m a s t e r st h e s i s ( 2 ) 基于层次的方法 ( 3 ) 基于密度的方法 ( 4 ) 基于模型的方法 ( 5 ) 基于网格的方法 2 2 中文文本聚类过程 图2 1 描述了一般中文文本聚类的过程，首先要收集用于聚类的文档集，再 进行中文文档的表示，如，分词，词频统计，去掉停用词，特征提取，再对项进 行向量化特征提取后的，特征向量调整，最后用聚类算法和工具进行聚类，最后 选用评定标准对聚类结果进行评估。 文档集正匠画哗 聚类结果+ 至三二卜 图2 1 中文文本聚类模型 以下是中文文本聚类过程的五个步骤： ( 1 ) 文本表示，包括分词，词频统计，去掉停用词，特征提取等过程； ( 2 ) 定义文本之间的相似度衡量； ( 3 ) 建立聚类模型； ( 4 ) 聚类算法描述，用软件工具根据算法实现聚类操作； ( 5 ) 对聚类结果进行验证分析。 2 3 文本的表示一向量空间模型 要让计算机能进行文本聚类处理，必须把文本转换为计算机可以处理的数据 格式。目前，向量空间模型( v e c t o rs p a c em o d e l 简称v s 【9 】是标示中文文本 效果最好的方法最简便的方法。 在向量空间模型( v s m ) 中，文本表示的基本单位为特征项，。向量空间中 硕士学位论丈 m a s t e r st h e s i s 一个向量代表一篇文档，有多少个特征项向量中就有多少维，特征项在每一个 文本中的权重用对应的每一维的值表示，这个值表示特征项能表示这篇文本内容 的能力。中文本集d 中的任一文档d i 表示为： d ，2 ，w 2 ，j ，i = 1 2 n w 面表示特征t j 在文档d i 中的权重，n 表示文档集所含文档总数【1 0 。这 样所有的文本向量就被映射到一个对应的特征空间，这就使文本的表示形式能被 计算机处理了。 2 4 维数消减 在中文文本聚类分析中，文档被分词技术处理后得到的单词或词组称为特征 项，所有不同的词汇构成文本的特征项集合，这样得到的特征项数目太多，每个 单词都作为特征空间坐标系的一维，每篇文本对应一个向量，这样会导致文本向 量空间变得非常高维而且稀疏，且提取的类别信息也不准确，不仅耗费时间且聚 类结果也很难令人满意【1 1 】。有效的维数削减对提高文本聚类的速度和效果是 非常重要的。特征选择就是在不牺牲聚类质量的前提下，进行特征集缩减以降低 特征向量空间的高维稀疏性来方便计算机进行聚类处理的技术。 根据某个特征评价函数，特征选择算法对各个特征项进行评分，然后根据 评分值经行筛选，一般是设定某个阀值，去掉小于或者大于这个阀值的特征项， 这样剩下的即作为最佳特征项子集，即作为能代表文档内容的特征子集【1 2 。 现在已经存在多种这种特征评价函数。按其选择过程是否需要类别指导而 主要被分为两大类：有监督的特征选择方法和无监督的特征选择方法。它们各有 优点和缺点，在不同场合下可根据需要进行合适的选择，恰当的特征选择方法对 改善聚类效果大有益处。 2 4 1 有监督特征选择 有监督的特征选择在选择前需要知道每个特征项的类别信息，不能直接应 用，但我们可以用它对一个中间聚类结果进行有监督特征选择来帮助另一个另一 个聚类过程。 常用的有监督特征选择方法有如下几种【13 1 4 。 ( 1 ) 信息增益( i n f o r m a t i o ng a i n ，i g ) ： 6 硕士学位论丈 m a s t e r st h e s i s 公式定义如下： 卿m ( ) 莩婀帆等+ p ( 而军p ( c f 慨等 公式( 2 1 ) 这种选择方法考虑了某个特征项不出现在某个类别中的情况。这样虽然对 聚类有贡献，但也会带来巨大干扰。 ( 2 ) 期望交叉熵( e x p e c t e dc r o s se n 仃o p y ) ： e c e ( 啥删) 即m g 等 怵2 2 ) 期望交叉熵与信息增益最大的区别就是没有考虑特征项未出现在文档中的 情况。 ( 3 )x 一统计量c h i z 统计衡量的是一个单词与一个类之间的相关程度，公式如下： z 2 ( f ) = - z p g ) z 2 ( f ，q ) 工2(f，c)：n(p(t,c)xp(t,c)-p(t,c)xp ( t , c ) ) 2 一。 p ( c ) ) p o ) p ( c ) p ( c ) 公式( 2 3 ) 该方法的最大特点是考虑了反相关的情况，比如：特征项t 和类c 相反， 考虑包含特征项t 的文档不属于c 的概率。 2 4 2 无监督特征选择 无监督特征选择因为事先不需要类别信息而可以直接应用到文本聚类中。 常用的无监督特征选择方法有如下两种【1 4 1 。 ( 1 ) 文档频率( d o c u m e n tf r e q u e n c y , d f ) ： d f 特征选择方法只考虑文档集中包含某一特征项的文档数目，这种方法实 现起来最简单。在统计了特征项的词频信息后，会根据设置的一个阀值来选择特 征项，d f 值比较小的特征项说明他对文本的表示能力不强，一般应该去掉；d f 值比较大的的特征项说明的它对文本内容的表示能力强，保留下来后对聚类结果 7 硕士学位论丈 m a s t e r st h e s i s 影响大些，在特征选择时，d f 值选择的阀值在开始时候应被设置的小一些，这 样可以防止文本特征项盲目丢失，应该这个过程是在无类别监督的条件下进行 的。 ( 2 ) 单词贡献度( t c ) 单词贡献度方法认为一个单词的重要性取决于它对整个文本数据集相似性 的贡献程度。公式定义如下： = 。，磊，他咖儿， 公式( 2 4 i ) f ，ip j分，硒，) 其中，f ( t ，d ) 表示特征词t 在文本d 中的权重。 2 5 特征项权值和相似度计算 2 5 1 特征项权值计算 目前比较流行的特征项的权重计算方法是基于词频统计的。该方法根据单词 项在文本中出现的次数来计算特征项权重。t f i d f 公式是现在普通受欢迎的权 重计算公式，该公式定义如下- 【1 5 】： w o = 矾l o g n n + 0 0 1 】 公式( 2 5 ) 其中，9 表示t j 在文档d i 中出现的次数即词频，n 表示出现t j 的文档数。 公式( 2 5 ) 认为在文档集中出现次数越少的特征词越重要，但忽略了有些噪声词， 可能只出现在几篇文章中，却得到了较大的权值。所以，有必要采取有效的特征 选择方法去掉噪声词。 2 5 2 相似性度量 衡量两个对象间的相近程度的相似性计算方法一般有两种：基于距离测量的 和基于相似系数的，下面分别来说明这两类方法。 ( 1 ) 基于距离的计算方法【2 】 基于距离的计算方法最典型的是欧几里得距离计算公式。该公式定义如下： 其中f = ( l ，t 2 ，) 和= ( x j in x ，2 ，b ) 为两个对象。 8 硕士学位论文 m a s t e r st h e s i s 则对象i ，j 之间的相似度d ( i ，j ) 用欧几里得距离计算公式可以表示为： d ( f ，歹) = lt 1 一x ，l1 2 + it 2 一x j 21 2 + + ix 荫一x 加1 2 公式( 2 6 ) 欧几里得距离计算公式有如下数学要求：设i ，j 表示两个对象。 a d ( i ，j ) 0 。 b d ( i ，i ) ：0 ：； c 1d ( i ，j ) = d ( j ，i ) 。 d d ( i ，j ) d ( i ，h ) + d ( h ，j ) ，h 表示其它某一对象。 ( 2 ) 基于相似系数的计算方法【1 8 文本间的相似系数是另一种常用的文本间的相似度表示方法，最常用的是余 弦系数公式表示法： 用余弦系数( c o s i n ec o e f f i c i e n t ) 方式定义s i m ( i ，j ) 时，使用公式如下： s 砌( f ，歹) ：下型些兰二 e 2 ：。w j , 2 其中，m 个特征项数，1 1 个文档数。 并且满足如下条件： 1 ) v i ，is i m ( i ，j ) i 1 ； 2 ) v f ，歹s i m ( i ，- ，) = s i m ( j ，n 。 2 6 本章小结 公式( 2 7 ) 本章介绍了文本聚类涉及的一些关键技术。对于中文文本，首先要进行分词 处理，然后进行词频统计。停用词处理可以去除意义虚泛的词，通过特征选择能 够选择出对聚类贡献较大的词，组成特征向量，用向量空间模型表示文本，一行 对应一个文本，根据t f i d f 公式计算单词的权重，用欧氏距离作为相似性度量。 本章主要介绍了由文本生成特征矩阵的步骤和涉及的关键技术。 9 硕士学位论文 m a s t e r st h e s i s 第三章组合聚类算法的分析与改进 3 1s o m 聚类算法 3 1 1d s o m 神经网络介绍 国外k o h o n e n 教授在上世纪8 0 年代初提出了自组织特征映射 ( s e l f - o r g a n i z i n gf e a t u r em a p ，s o m ) 网络【1 l 】，所以我们也把自组织特征映射称 为k o h o n e n 自组织特征映射网络。s o m 网络的拓扑结构有两层，输入层的每一 个单元与输出层的每一个单元都有权值连接关系，如图3 1 所示，输入层就象人 眼睛的视网膜可以接受外面的输入信息，输出层类似于人脑的大脑皮层，对输入 信息作出相应的反应。输入层各神经元通过权向量将外界信息汇集到输出层的各 个神经元，这个过程类似于人的大脑处理信息的过程，所以被称之为神经网络。 l 叩m1 a r c o m p e t i t i v el a y e r 图3 1s o m 神经网络结构图 s o m 神经网络的工作原理如下【1 5 】： s o m 神经网络输入层的每一个单元与输出层的每一个单元都有权值连接关 系。输入向量在输入层并没有被处理，输入层只是把输入矢量的各个分量经过连 接权传送到输出层。在s o m 算法训练过程中，获胜神经元周围会有一个以某一 长度为半径的圆形领域，这个领域内的所有点都按其距离获胜神经元的远近程度 来相应地调整权值，优胜领域半径随着训练次数的增加不断缩小直到为零。最后， 输入模式经过反复学习，权重向量空间与输入模式的概率分布趋于一致，这样输 l o 硕士学位论丈 m a s t e r st h e s i s 入模式的统计特征由相应的权重向量空间反映出来，这个过程由系统自动完成。 3 1 2d s o m 神经网络算法思想 d s o m 算法架如- f 1 3 ： ( 1 ) 设输入向量为 x = ( x l ，x 2 ，j 。，) 距离。 公式( 3 1 ) ( 2 ) 先随机选择一个向量五，计算它与输出层所有节点j 的权值向量w f 的 嘭= i = l ( # 一) 2 , i e 1 ，2 ，3 ，z ) ，_ ， 1 ，2 榭 公式( 3 2 ) ( 3 ) 竞争获胜结点_ ，宰为具有最小距离的节点： d 产= m i n d a j 1 , 2 。朋 ( 4 ) 获胜神经元及其邻域内节点自动调节权值。 嘞= 叩( f ) ( x ? 一) ，m n e j ( t ) ，f 1 ，2 刀 其中， o r i ( t ) 1 ， 7 7 ( f ) = 0 9 ( 1 一t 1 0 0 0 ) 为经验函数。 ( 6 ) 若输入样本未完，则t = t + l o + 1 ) = ( f ) + 口( x 一o ) ) 呢 + 1 ) = o ) ， 调整后的新向量进行重新归一化后转步骤( 1 ) ，其中， 不断减小，最后衰减到0 。 3 1 3 算法优缺点 公式( 3 3 ) 公式( 3 4 ) 公式( 3 5 ) 公式( 3 6 ) 学习率口a ( o ，1 】，其值 自组织映射( s e l f - o r g a n i z i n gm a p s ，s o 峋神经网络有如下优点【1 5 - ( 1 ) 适应性强，自主学习性高。 ( 2 ) 它事先不需要类别信息，是一种无监督学习方式。 硕士学位论文 m a s t e r st h e s i $ s o m 也有其缺点，如聚类效果不好，网络结构固定性，需要预先给出网格 单元数目等。 3 2k - 均值聚类算法分析 3 2 1k 均值聚类介绍 k - m e a n s 算法的原理是【1 6 1 7 ：对于一个有1 1 个对象的数据集，首先随机 给定目标聚类数k ，按照k 类对数据集进行初始划分，并为每个簇设定个簇中 心，并将数据点联系到与它们距离最近的中心，在重新计算k 个簇中心并重新调 整数据点到离它最近的簇中心，重复上面过程直到簇中心的位置不再变化为止， 循环结束。 k - m e a n s 算法使用如下函数作为距离优化函数，该函数定义为： ，= ：。球；。一叫2 其中，l i 一q 6 2 为数据点x ；力到簇中心q 的距离。 k m e a n s 算法利用函数求极值的方法进行迭代运算， 算法结束。 公式( 3 7 ) 直到准则函数以收敛， 3 2 2k - 均值聚类算法思想 下面是关于k - m e a n s 算法的框架描述【1 6 1 7 ： 1 ) 对数据集，令i ：l ，k 个初始聚类中心为乙( d ，歹= l ，2 ，3 ，七；其值在开始时 随机设定； 2 ) 计算每个对象与聚类中心的距离d ( t ，乃( f ) ) ，f = 1 ，2 ，3 ，- 七；，= 1 ，2 , 3 ，孟；如果 满足，d ( x f ，z j ( o ) = m i n d ( x , ，z ( j ) ) ) ，j = 1 ，2 ，3 ，一鸩，则呒： 3 ) 计算目标优化函数_ ，c ： 丘( f ) = 2 盛。” ( 叫 2 1 2 公式( 3 8 ) 硕士学位论文 m a s t e r st h e s i s 4 ) 当l l ( i ) 一j c ( i 一1 ) 1 o ，则 = 瀚刍矿 如果了f ，且d 箩= 0 ，则”? = l ，且对，f ，“雾= 0 2 ) 更新原型模式矩阵尸蹦，用如下公式： 公式( 3 1 1 ) ( “) ”以 p + 1 = 盟_ 一， 妙) 脚 j = 】 i = 1 ，2 ，r l公式( 3 1 2 ) 3 ) 若忙”一p i i 见t h e nj 获胜 i d ( 嘭，) 口，t h e n 建立一个新神经元 公式( 3 1 3 ) 公式( 3 1 4 ) 如果有多个神经元都满足阈值0 时，选择相似度最大的作为获胜神经元。如 果j 是获胜神经元，则修i e j 及其领域神经元的权值向量，且c l 【k 】= j ，k = k + i ， n s = n s + l 。如果没有神经元满足阈值则建立一个神经元，新建神经元的权值向量 n c = n c + l ，噬= 乓，c l k = n e ，k = k + i 。若k n ，则转向s t e p 3 ，否则，转 s t e p 5 。 i 吁= 嘭。1 + ，7 ( & 一嘭 i 彬k = 彬厶1 + o 5 ，7 ( 一彬r ) i ，( d ) 1 7 公式( 3 1 5 ) 硕士学位论文 m a s t e r st h e s i s 其中1 1 为学习率，值为刁2 。么m + 1 ) r oe ( 0 , 1 】。 q ( d ) 表示获胜神经元的领域，n j ( a ) 如公式( 3 1 6 ) 。 n j ( a ) = f ，d ( 哆。1 ，形厶1 ) 口，t h e nj 获胜 ld ( 嘭，乓) s 幺t h e n 建立一个新神经元 公式( 3 1 7 ) 公式( 3 1 8 ) 如果有多个神经元都满足阂值0 时，选择相似度最大的作为获胜神经元。如 果j 是获胜神经元，则修正j 及其领域神经元的权值向量，且c l 瞰 - - j ，k = k + i ， n s = n s + l 。如果没有神经元满足阈值则建立一个神经元，新建神经元的权值向量 硕士学位论文 m a s t e r st h e s i s n c = n c + i ，噬= 乓，c l 【k 】：n c ，k ：k + 1 。若k n ，则转向s t e p 3 ，否则，转 s t e p 5 。 f 哆= 哆q + 刁( & 一嘭) i 形置= 形纠+ o 5 刁( 最一彬x ) i ，( d ) 公式( 3 1 9 ) 其中1 1 为学习率，值为刁2 。么m + 1 ) 吼( o 1 1 。 够( j ) 表示获胜神经元的领域，以( d ) 如公式( 3 2 0 ) 。 n j ( d ) = f ，d ( w j k - , w 一肛1 ) d t 公式( 3 2 0 ) 其中t 为迭代次数。 s t e p 5 ：计算每个类簇的中心，每将类中心保存在矩阵c 【n c 】 m 】中。 当d s o m 网络训练结束后，n c 和c n c 】 m 】分别为模糊c 均值聚类的聚类 数及各类的聚类中心。 f c m 接着执行如下步骤：( 1 ) 初始化聚类中心v = v l ，v 2 ，v k ) ；此处的聚类 中心是根据d s o m 算法中得到的数组c 来得到初始聚类中心v 。 ( 2 ) 计算隶属度矩阵 2 封掣r 。l 幺，n = 肛成+ ( 1 一) 材主 公式( 3 2 1 ) 我们可以做如下修改，将隶 公式( 3 2 2 ) 【o ，1 】时，：0 时，：0 ；= 1 时，= 1 ；函数为凹函数， 在 o ，1 】区间内，隶属度比原来的值有了一定的减少，随着曲线的斜率的增加， 隶属度明减小，这样在聚类中就可以降低孤立点数据对那些隶属度小的数据对聚 类中心的影响【3 4 】。 ( 3 ) 更新聚类中心 2 l 硕士学位论文 m a s t e r st h e s i $ ( ) ”& u = 号- 一i = 1 ，2 ，c ( 4 ) 重复步骤( 2 ) ( 3 ) 直至( 3 2 1 ) 式收敛。 3 6 本章小结 公式( 3 2 3 ) 本章首先介绍了文本聚类中比较流行的3 种聚类算法( s o m 聚类算法、 k - m e a n s 聚类算法、f c m 聚类算法) ，对这3 种算法进行了详细的介绍，并分析 了各自的优缺点。然后，在分析了上述三种算法的基础上，结合文本特征选择方 法，提出了两种组合聚类流程模型，从理论上说明其有效性及特点，并详细介绍 了与这两种组合聚类流程模型对应的聚类算法：d s o m f s k m e a n s 算法和 d s o m - f s f c m 算法。在d s 0 m f s f c m 算法，还对f c m 算法中的隶属度函数 进行了优化调整，降低了孤立点在聚类过程中对聚类中心确定的影响程度。 第四章实验证明 为了更好地评估本文所提出的两个文本聚类流程模型及对应于各个模型的 文本聚类方法，实验( 1 ) 我们将d s o m f s k r e c a l l s 方法同，仅采用d s o m 与 k - m e a n s 组合而没有按照流程进行特征选择的方法一d s o m - k m e a n s ，d s o m ， k 均值三种聚类方法的聚类效果进行对比。实验( 2 ) 我们将d s o m f s f c m 方 法同，仅采用d s o m 与f c m 组合而没有按照流程进行特征选择的方法电为 d s o m f c m ，f c m 聚类方法和d s o m 三种方法的聚类效果进行对比。 4 1 实验环境 我们用e c l i p s e 32 + j d k l5 + w e k a3 55 在s n d o w s x p 系统下实现上述算法， w e k a 为当前比较流行的数据挖掘工具，类库里面已经集成了很多比较热门的算 法，使片j 起来非常方便，并且可以在j a v a 环境中任意扩展起功能，是一个很好 的数据挖掘工具。 系统配置如图4 l 所示： e a f = 3 t 一| 一h 1 ， ：，。o 叱出9 8 ，毒， o ”一 一 一d 口 一- u c - j 日t a - ”- - a ，。 z 目t t l 日t t 。ej l 1j t t 7l ul ：- l t 】。 t 目f k d - t t f 【一 ；b f k d f 。；b 1 ，# _ b l ”tl o q 。t o j 日一 l ”t ；f n ，t t m d f i o a c l “ f 一 t 口 l 自hc l m ：f t ( f d 。m 一：l i i l f 1 、y ， m c l fl 、”t d 1 e d a t d - f i t f h4 1 系统配置蚓 在测试阶段。我们从h t t p ：w w w 1 i bb u e d u 中的部分已经人工分类的文档 作为文档源进行聚类，用查全率r e 和查准率p r 来评价聚类效果。实验一所用的 文本集共有1 4 7 篇文章，分环境4 9 、交通3 3 、教育2 8 和经济3 7 。实验实验二 所用的文本集共有3 2 7 篇文章，分政治1 0 3 、交通7 1 、医药6 4 和计算机8 9 。 数招预备处理过程如下。首先对文档数据进行分词处理，得到结果如下图 4 2 所示。 图4 2 分词后的文竹 分词后根据停用训表去除对聚类贡献不重要的词，如结构助词，语气词等 停用词表如下图所示： 图4 3 停用词表 硕士学桩论工 然后统计每个特征词在每篇文档中出现的次数，结果如图4 3 所示 臼oz t 件戛一 t 曰曰曰国 # hi 口d 4 一十娃# “ 5t r r”m 图4 3 去掉停用词和统计词频后的文件 接着生成文档的特征向量，如果特征词i 出现在文档d 中，则对应矩阵的d 行i 列对应为l ，否则为0 。 00000 000 0000 0000000000 000000000 00000 0 o00000 oo00000000 000 0 0 0 o00 0000 0000 0000 00 00000000 000d 0 0 000 00000 0 000o00 000o000000000000o0 00000 0 000 000000 1000000 00 i0 00000 o000 i0 100000 00000000000000 100 0 0 o00000 o0 1o0 10 100000 1000000 000 0 0 0 1 1 1 1 i 1 10 0 0 00000 0 00000 000 0 00000 0000 00 000 o00 0000000000 0000 0 0 0 0 0 00000 0 000 o000000000000000o 000 00 00000 0 000 000 0000000000 0000 00 000 00000 0 000 o00 0000 0 00000 0000 0 0 0 0 0 00000 0 000 0000000 0 00000 0 000 0 0 0 o 0 00000 0 000 0000000 0 000000 o 00 0 0 000 00000 0 000 000 0000 0000000 0 00 0 0 000 00000 0 0000 o 00000 0 000000 0 o00 0 o00 00o o0 0000 000 0000 0 00000 0 000 0 0 o o o 国4 4 每个文什的特征词向量 。嚣嚣嚣学。哗攀嬲 全球4 o 环境2 资2 臭氧层4 生物2 一 多样性3 ， 减少3 i 酸雨2 一 森林2 土地2 o 万5 大气2 。 污染6 根据文本的特征向量和词频统计结果构建特征权值向量空间模型，如图4 5 所示。 日盔口曩田墨冒圈冒鹫鳐匿螽g 庭“删量 女# 4 】瞄q 川日 t i 岫* * 如 0 ，00 6