（通信与信息系统专业论文）基于改进kmeans算法的web文档聚类系统的研究与实现.pdf

复旦大学硕士论文基于改进k - m e a n s 算法的w e b 文档聚类系统的研究与实现 中文摘要 本文研究了一种基于改进k - m e a n s 算法的w e b 文档聚类系统，并开发出了 一套由网络爬虫、数据清理、中文分词、特征提取、权重计算和聚类分析等模块 组成的w e b 文档聚类系统。同时，针对k - m e a n s 算法的主要缺点和不足，本文 对k - m e a n s 算法中的关键环节如相似度计算公式，初始聚类中心的选择和新聚 类中心的计算方法进行了改进。并且使用f - m e a s u r e 评价方法对k - m e a n s 算法整 体改进后的聚类效果进行评价，通过实验性能对比说明了改进算法的优越性。 文章对数据挖掘、聚类分析和w e b 挖掘进行了概述和总结，介绍了整个系 统的架构。并对网络爬虫、中文分词、英文词干提取、特征提取，权重计算和聚 类分析等模块进行了深入的研究。最后，通过开发的由网络爬虫、数据清理、中 文分词、特征提取、权重计算和聚类分析等模块组成的w e b 文档聚类系统进行 了对比实验，验证了基于改进k - m e a n s 算法的w e b 文档聚类系统在准确性和稳 定性方面都有所提高。 关键词：数据挖掘，聚类，w e b 挖掘，k - m e a n s 聚类算法，向量空间模型 复旦大学硕士论文 基于改进k - m e a n s 算法的w e b 文档聚类系统的研究与实现 a b s t r a c t t h i sd i s s e r t a t i o nw i l ls t u d yt h er e a l i z a t i o no fw e bd o c u m e n t sc l u s t e r i n gs y s t e m ( w d c s ) b a s e do nt h ei m p r o v e dk - m e a n sa l g o r i t h m ，a n dd e s i g nan o v a lw d c s i n c l u d i n gs e v e r a lm o d u l e ss u c ha sw e bs p i d e r , c h i n e s es p l i t ，e n g l i s hs t e m m e r , f e a t h e r s e l e c t i o n ，w e i g h r i n gc a l c u l a t i o na n dc l u s t e r i n g o nt h eo t h e rh a n d , t h ed i s s e r t a t i o n w i l li m p r o v et h ep e r f o r m a n c eo fk - m e a n sa l g o r i t h mb ys e v e r a lm e t h o d ss u c ha s o p t i m i z i n gt h es i m i l a r i t yc a l c u l a t i o n ，u p g r a d i n gt h ei n i t i a lc l u s t e r i n gc e n t e r sa n d c h a n g i n gt h es e l e c t i o no ft h en e wc l u s t e r i n gc e n t e r s b yf m e a s u r ee v a l u a t i o nm e t h o d ， t h es i m u l a t e dr e s u l t sw i l lp r o v et h a tt h ep e r f o r m a n c eo ft h ek - m e a n sa l g o r i t h mc a nb e i m p r o v e d t h ed i s s e r t a t i o nw i l la l s os u m m a r i z et h em a i nf e a t h e ro fd a t am i n i n g ( d d ， c l u s t e r i n ga n a l y s i s ( c a n dw e bm i n i n g ( w d ，i n t r o d u c et h ef r a m e w o r ko ft h e w d c s i na d d i t i o n , t h ek e yt e c h n o l o g i e so fw e bs p i d e r , c h i n e s es p l i le n g l i s h s t e m m e r , f e a t h e rs e l c c t i o n ，w e i g h t i n gc a l c u l a t i o na n dc l u s t e r i n ga n a l y s i sw i l lb e c l a r i f i e di nt h i sd i s s e r t a t i o n f i n f l l y ，u s i n gt h es i m u l a t e dr e s u l t so fd e s i g n e dw d c s ， t h e i m p r o v e m e n t sf o r t h eo d l t e c t n e s sa n ds t a b i l i t yo ft h ei m p r o v e dk - m e a n s a l g o r i t h ma r ec o n f i r m e d k e yw o r d s ：d a t am i n i n g , c l u s t e r i n g , w e bm i n i n g ，k - m e a n sc l u s t e r i n g a l g o r i t h m ，v s m 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除了特别 加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的研究成 果。其他同志对本研究的启发和所做的页献均已在论文巾作了明确的声明并表示 了谢意。 作者签名 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印什，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影e 、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 复旦大学硕士论文基于e j o l t k 算法的w e b 文档聚类系统的研究与实现 1 1 论文的研究背景和意义 第一章绪论 i n t e m e t 和数字图书馆等领域的发展导致了信息的“爆炸”。随着以数据库、 数据仓库等数据仓储技术为基础的信息系统在各行各业的应用，海量数据不断产 生。随之而来的问题是如此多的数据让人难以消化，更无法从表面上看出他们所 蕴含的有用信息，更不用说有效地指导进一步的工作。如何从大量的数据中找到 真正有用的信息成为人们关注的焦点，数据挖掘技术也正是伴随着这种需求从研 究走向应用i l j 。 随着i n t e m e t w e b 技术的快速普及和迅猛发展，使各种信息可以以非常低的 成本在网络上获得。由于i n t e m e t w w w 在全球互连互通，可以从中取得的数据 量难以计算，而且i n t e m e t w w w 的发展趋势继续看好，特别是电子商务的蓬勃 发展为网络应用提供了强大支持。如何在w w w 这个全球最大的数据集合中发 现有用信息无疑将成为数据挖掘研究的热剧3 】。 信息中最主要的信息源就是文本数据，传统的文档和文本处理工具己经不能 满足用户的需求。于是在人工智能研究领域结合结构化数据库中的数据挖掘技 术，提出了一种有效的、可以充分利用这些文本数据的新的信息处理技术一文 本挖掘( t e x tm i n i n g ) 。文本挖掘是抽取有效、新颖、有用、可理解的、散布在文 本文件中的有价值知识，并利用这些知识更好地组织信息的过程。文本挖掘是信 息挖掘的一个研究分支，用于基于文本信息的知识发现。文本挖掘是利用智能算 法，如神经网络、基于案例的推理、可能性推理等，并结合文字处理技术，分析 大量的非结构化文本源，如文档、电子表格、客户电子邮件、问题查询、网页等， 抽取或标记关键字概念，文字问的关系，并按照内容对文档进行分类，获取有用 的知识和信息。它涉及多个学科领域，诸如数据库、信息位索、信息提取、机器 学习、自然语言处理、计算语言学、统计数据分析、线性几何、概率理论，甚至 还有图论等知识1 3 j 。 w e b 挖掘指使用数据挖掘技术在w w w 数据中发现潜在的、有用的模式或 信息。w e b 挖掘研究覆盖了多个研究领域，包括数据库技术、信息获取技术、统 计学、人工智能中的机器学习和神经网络等嘲。 3 复旦大学硕士论文基于改进k - m e a n s 算法的w e b 文档聚类系统的研究与实现 聚类是文本挖掘的主要内容之一。它是根据某种相似性准则将样本空间分成 多个子空间，使每个子空间内部样本点尽可能相似，不同子空间内样本点之间差 异尽可能大。其实质是寻找隐藏在数据中不同的数据模型，是一个无监督学习过 程，能够实现样本空间的盲分类。聚类广泛应用于统计、机器学习、模式识别， 数据分析等领域，并越来越受重视。聚类可以帮助人们更快的找到所需要的信息， 因此，聚类在现实生活中有着很重要的意义。现在，聚类分析己成为一个非常活 跃的研究课题1 5 j 。 1 2 相关内容的研究情况 在加拿大蒙特利尔市召开了第一届k d d ( k n o w l e d g ed i s c o v e rd a t a b a s e ，是 数据挖掘的另一种叫法- 数据库中的知识发现”的英文) 国际学术会谢，以 后每年召开一次。近年来，k d d 在研究和应用方面发展迅速，在电信、银行、 商业等领域得到了广泛的应用，s a s ，s p a s s 等诸多软件都提供了数据挖掘的功 制3 j 。 数据挖掘中的聚类分析是传统聚类方法( 特别是统计学中的聚类方法) 的继 承和发展。聚类分析作为数据挖掘中的一个重要研究热点，目前，聚类分析的研 究主要集中在两个方面：一方面是对聚类分析算法的研究，现在已经提出了很多 种算法，比如：k - m e a n s 、c i a r a n s 、b i r c h 、咖、c h a m e l e o n 、d b s a 气n 、 o p t i c s 、d e n c l u e 、s t i n g 算法等。特别是对文本、多媒体和w e b 信息等 复杂数据进行聚类的研究还是方兴未艾。另一方面是聚类分析的实际应用的研 究，聚类分析可以作为独立的数据挖掘工具来获得数据分布的知识，也可以作为 其它数据挖掘算法的预处理步骤。它在许多领域有着重要的应用，比如金融数据 分析，商业零售数据分析，电信和网络数据分析，生物医学和d n a 数据分析， 天文，陆地和海洋地理等科学探测数据分析等领域【5 】。 1 3 论文的研究内容和组织结构 本文主要做了下述工作： ( 1 ) 本文对文本挖掘中的文本表示方法、特征提取、权值计算进行了系统 的研究，并对网络爬虫、分词、聚类等过程进行了比较详细的阐述。 4 复旦大学硕士论文基于改进k - m e a n s 算法的w e b 文档聚类系统的研究与实现 ( 2 ) 开发了一整套由网络爬虫、数据清理、中文分词、特征提取、权值计 算和聚类分析等模块组成的系统。 ( 3 ) 对k - m e a m 算法进行了有特色的改进。区别于其它论文中只对算法的 某一方面进行改进，本文综合了大量参考资料，针对k - m e a n s 算法的主要缺点 和不足，对k - m e a n s 算法中的关键环节：相似度计算公式，初始聚类中心的选 择和新聚类中心的计算方法进行了改进。 ( 4 ) 使用f - m e a s u r e 评价方法对k - m e a n s 算法改进前后的系统进行评价， 通过f - m e a s u r e 值对比表、对比柱状图和f - m e a s u r e 分布情况说明了改进算法的 在准确性和稳定性方面都有所提高。 ( 5 ) 论文最后除对研究工作进行了总结外，还对今后的研究方向进行了展 望。 本文的组织结构如下： 第一章“绪论”，首先分析了论文研究的背景和意义，然后介绍了本文相 关内容的研究情况，最后介绍了论文的研究内容和组织结构。 第二章“数据挖掘与聚类分析”，是对数据挖掘，聚类分析和w e b 挖掘等 本文相关内容的综述。 第三章“w e b 文档聚类系统的总体架构”，首先给出了w e b 文档聚类系统 的总体架构图，然后分别介绍了网络爬虫、数据清理、中文分词、特征提取、权 值计算和聚类分析等模块。 第四章“k - m e a n s 算法和基于改进k - m e a n s 算法的聚类分析模块”，首先 介绍了原始的k - m e a n s 算法，然后对其进行了改进。 第五章“基于改进k - m e a n s 算法的w e b 文档聚类系统的实验及结果”，首 先介绍了聚类结果的评价方法，然后利用本文开发的系统对改进前后的k - m e a n s 算法的聚类质量进行了实验和比较，并给出了对比数据表和相应的柱状图。 第六章“结束语”，对本文的工作进行了总结，同时指出了还需进一步研 究的方向。 5 复旦大学硕士论文 基于改进k - m e a n s 算法的w e b 文档聚类系统的研究与实现 2 1 数据挖掘 第二章数据挖掘与聚类分析 2 1 1 数据挖掘的产生 i n t e m e t 和数字图书馆等领域的发展导致了信息的“爆炸”。随着以数据库、 数据仓库等数据仓储技术为基础的信息系统在各行各业的应用，海量数据不断产 生。随之而来的问题是如此多的数据让人难以消化，无法从表面上看出他们所蕴 涵的有用信息，更不用说有效地指导进一步的工作。如何从大量的数据中找到真 正有用的信息成为人们关注的焦点，数据挖掘技术也正是伴随着这种需求从研究 走向应用1 1 1 。 随着i n t e m e t w e b 技术的快速普及和迅猛发展，使各种信息可以以非常低的 成本在网络上获得。由于i n t e m e t w w w 在全球互连互通，可以从中取得的数据 量难以计算，而且i n t e m e t w w w 的发展趋势继续看好，特别是电子商务的蓬勃 发展为网络应用提供了强大支持。如何在w w w 这个全球最大的数据集合中发 现有用信息无疑将成为数据挖掘研究的热点1 3 】。 k d d 这一术语首先出现在1 9 8 9 年在美国底特律召开的第1 1 届国际人工智 能联合会议的专题讨论会上，1 9 9 1 ，1 9 9 3 和1 9 9 4 年又接着继续举行k d d 专 题讨论会。1 9 9 5 年在加拿大召开了第一届知识发现和数据挖掘国际学术会议， 以后每年召开一次。从1 9 9 7 年开始，k d d 已经拥有了专门的学术刊物 ( k n o w l e d g ed i s c o v e r ya n dd a t am i n i n g ) 。国外在这方面发表了众多的研究成果 和论文，并且开发了一大批数据挖掘软件，建立了大量的相关网站。对k d d 和 数据挖掘的研究已成为计算机领域的一个热门课题。我国近几年也逐渐跟上国际 步伐，许多计算机、数据库、人工智能、机器学习领域的专家学者投入到k d d 和数据挖掘的研究中，并已取得了一定的成果【3 】。 2 1 2 数据挖掘的定义 知识发现【2 】0 1 3 4 【1 0 l ； 复旦大学硕士论文基于改进k - m e a n s 算法的w e b 文档聚类系统的研究与实现 图3 1 l 最短路径求解示意图 为了从二分图中得到从初始状态s 到r 的条最短路径，系统只需要对节点 r 的所有节点按照距离排序，然后从中选出个项目依次按照上述方法找到原状 态节点s 即可得解i 埘。 3 3 2 3 未登录词的识别 未登录词f 1 0 】是指在核心字典中没有收录的词，由于这类词的存在大大的干 扰了正常情况下的分词结果。例如，在汉字串“克林顿对内塔尼亚胡说”中，“内 塔尼亚胡”是一个词典中没有收录的译名，实际切分的时候，“对”与“内”，“胡”与 “说”往往会粘在一起，最终导致错误的切分结果：“克林顿，对内搭尼亚胡说尸。 怎样正确的将未登录词识别出来是本小结的主题。在进入讨论正题前，让我们来 看看角色的概念。表3 - 1 为人名识别的角色表【堋。 角色1 1 0 】就是词语在一个语境中所盼演的一种身份。对于一个给定的初始划分 结果胙似o w l w 2 0 ，在角色范畴内，假定r = ( r o r l r 2 ) 为词语序列对应的角色 序列，我们取概率最大的角色序列作为词语序列最终的角色。我们将词语看成是 观测值，将角色看成是状态值，根据马尔科夫链可以得到【1 0 】： 尸 ) 一丌p “h 咖l ) ，( 3 - 2 ) 厶r 两边取负对数，得到 复旦大学硕士论文基于改进k - m e a n s 算法的w e b 文档聚类系统的研究与实现 一l o g p ( r ) 一( 一l o g p ( n h ) p ( l ) ) ，( 3 - 3 ) 口 通过后文描述的算法i 埘，系统得到一个最大概率角色序列，并在此基础上通过 某特定人名模板的匹配实现特定类型的未登录词识别。打个比方，如果通过后文 算法得到词语序列形得到的角色序列是c d e a e f , 那么c d e 所对应的词语就被 组合到一起，因为中文双名的名字组合就是c d e ( c ：中国人名的姓，d ：双名的 首字，e ：双名的末字) 【1 0 1 。 表3 - 1 人名识别的角色表 角色意义示例 a 人名的上文 又| 塞勤千i 诀胖 镝瘃 b 人名的下文 瓿华社f 记者威皮i 握 c 中国人名的姓 氆埠湃| t 生；医凰毽 d 双名的首字 弛当平 先生 e 双名的末字 张f 华f 翌先生 f单名 张馐 g 人名的前缀 鸯瓤、出季 h 人名的后缀王，总，刘老、肖氏 l 译名的首部 蓥帕 薷1 隅| 拙费 m 译名的中部 象| 蝗萤j 梅氆袭 n 译名的末部 豢帕隋f 瀚| 鼬蕴 o日本人名末部 、慕| 鼬一l 墼 x 连接词 礴f 钨麟 塑携| 遭南| 镜 z其它 厶基 遂纽缅怀踯价| 平 求解最大角色序列【1 0 】：如图3 - 1 2 所示，为了便于计算假设从取耻到的弧 长为( 一l o g p ( n i h ) - p ( m i ) ) ，那么问题将转化为求s 节点到终结点t 的最短 路径。假设d 叼们代表从s 到第i 个词语的第，种角色的最短路径，那么 d 【f 】【力。垣r a 功i n 】 d p 一1 】【纠+ ( 一l o g p ( r ui ) 。l o g p ( w ii ，；，m ，其中厅是单词耽l 存在的角色数。为此，本文采用动态规划算法来求解从s 节点到r 节点的最短路 复旦大学硕士论文基于改进k - m e a n s 算法的w e b 文档聚类系统的研究与实现 径。为了记录d 【f 】d 1 时的k ，系统引入路径记录矩阵b e s t p r e v m 】m ，其中m 是单 词个数，n 是一个单词最多的角色个数【堋。 图3 1 2 求最大序列示意图 【算法3 - 2 i 1 0 1 ：求取从s 到t 最短路径时，填充矩阵b e s t p r e v 曰 ：廿 。 回 s h o r t e s t p a t h 0 1 f o r i = o ；i w o r d s 0 n p o s ；i + + )艨一个单词的所有前驱为一1 a ) b e s t v r e v o i = 一1 ； 2 f o r ( m ri _ 1 ；i n w o r d s ；i + + ) a ) f o r ( i n t j = o ；j w o r d s i n p o s ；j + + )腩于每一个角色g i u 】 i t e m p = 啪洳o t e m p 相当于前文中的d 【i 】d 】 i i f o r 伽tk - - o ；k 1 ) e m e n t 一 n u u ，那么词语r e p i a c l 狲m n t 被替换成r e p l c ，其中m = 2 。 这个表达式部分也可以表示成如下形式： 峪一单词以s 结束( s 是一个字母或者是一个字符串) ； v 词干中含有一个元音字符； d 词干以两个相同的辅音字母结束； o - 词干以c v c 的形式结束，并且第二个c 不是职z 和y ( c 是一个辅音 字符，y 是一个元音字符1 ； c o n d i t i o n 可以是用a n d ，“口，和“n o t 对前面条件的组合。 p o n e rs t e m m e r 算法【1 4 】实际上是对英文后缀的一些列替换工作，具体介绍如 下： ( 1 ) s o e p1 a 替换单复数； 3 4 复旦大学硕士论文基于改进k - m e a n s 算法的w e b 文档聚类系统的研究与实现 & 范s s s i 壬洛 i s s 豁 s一 ( 2 ) s t e pl b 替换分词形式，如( - e d 。- i n g ) 细 e e l ) - ) e e f e 1 ) - f 删g 一 一 c a r e s s 。 p o m 石 一 c a r e s s c a t f e e d一 f e c d a g r e e d一 a g r e e p l a s t e r e d 一p l a s t e r b l e d一 b l e d m o t o r i n g - m o t o r s i n g一 s i n g 如果上述第二条或者第三条转换成功的话，那么继续进行下述转换； a t 一 a t e c o n f l a t ( e d ) c o n f l a t e b l 一 b l e t r o u b l ( e d ) 一 t r o u b l e i z - ) i z e s i z ( e d ) s i z e ( * d a n d n o tf 屹o f 岱d rj 功一 s i n g l el e t t e r = ja n d m 一) e h o p p ( i n g ) h o p t a n n ( e d ) t a n f a u ( i n g ) f a l l h i s s ( i n g ) h i s s f i l z z ( e d ) 一 f i z z f a i l ( i n g ) f a i l r a ( i n g ) f i l e ( 3 ) s t e p1 c 将前面词千中含有元音的最后一个y 改称i ( y 一 j h a p p yh a p p i skysky ( 4 ) s t e p2 对一些常见的词根进行处理 ( m 0 ) a t i o n a l a t e r e l a t i o n a l- r e l a t e 3 5 一一；l - 一妇= 复旦大学硕士论文基于改进k - m e a n s 算法的w e b 文档聚类系统的研究与实现 o ) e n c i - e n c e 细锄a n c i - a n c e 西堋i z e r i z e 锄a b l i - a b l e 西锄a i i i a l 伽如) e i v l 3 a 一 e n t 伽堋e l i e ( m - o ) o u s l i o u s ( m ) 0 ) i z a t i o n 一 i z e 伽如) a t i o n - a t e 棚a t o r - a t e 何锄a l i s m - a l 何锄d 4 e s s - i v e l 锄- o ) f u l n e s s f u l 0 ) o u s n e s s 一 o u s 细如) a i m a l 卸如) i v m i v e o ) b i l l t i b l e c o n d i t i o n a l ，c o n d i t i o n r a t i o n a l一) r a t i o n a l v a l e n c i v a l e n c e h e s i t a n c i h e s i t a n c e d i g i t i z e r d i g i t i z e r a d i c a u i r a d i c a l d i f 艳r e n t l id i f f e r e n t v i l e l i- v i l e a n a l o g o u s f i a n a l o g o u s v i e t n a m i z a t i o n v i e m a m i z e p r e d i c a t i o n 一 p r e d i c a t e o p e r a t o r o p e r a t e f e u d a l i s m f e u d a l d e c i s i v e n e s s d e c i s i v e h o p e f u l n e s s h o p e f u l c a l l o u s n e s s c a l l o u s f o n n a f i t i f o r m a l s e u s i t i v i t i s e n s i t i v e s e u s i b i l i t i一s e n s i b l e o ) s t e p3 做一些常见形容词和名词之间的后缀转换 似 o ) i c a t e 一 1 ( 7 伽, o ) m t v e 一 i 研 0 ) i c i t i - ) i c l 如, o ) i c a l 一 i c i 加 o ) f u l - 伽, o ) n e s s 一 t r i p l i c a t e f o r m a t i v e f o r m a l i z e e l e c t r i c i t i e l e c t r i c a l h o p e f u l g o o d n e s s t r i p l i c f o r m f o r m a l e l e c t r i c e l e c t r i c - h o p e 一g o o d 复旦大学硕士论文基于改进k - m e a n s 算法的 w e b 文档聚类系统的研究与实现 ( 6 ) s t e p4 作一些名词、形容词到动词的转换 细 1 ) a l 一 1 ) a n c e 一 西 1 ) e n c e 西 1 ) e r 一 ( m 1 ) i c 一 伽 1 ) a b l e - 西 1 ) i b l e 一 伽 1 ) a n t - ) 西 1 ) e m e n t 一 ( m 1 ) m e n t 一 i 而 d e n t 一 西 1a n d ( 峪o r + 2 3 ) i o n 一 ( m ) 1 ) d u 西 1 ) i s m 一 伽 1 ) a t e 一 1 ) 7 一 血 1 ) o u s 一 伽 1 ) i e 一 1 ) 1 z e 一 ( 7 ) s t e p5 继续做出一些小的修整 1 ) e r e v i v a l a l l o w a n c e i n f e r e n c e a i r l i n e r g y r o s c o p i c a d j u s t a b l e d e f e n s i b l e i r r i t a n t r e p l a c e m e n t a d j u s t m e n t d e p e n d e n t a d o p t i o n h o m o l o g o u c o n m a u n i s m a c t i v a t e = 1a n d n o t o ) e - 1 a n d da n d l ) 一 s i n g l e l e t t e r r e v i v a l l o w i n f e r a i r l i n 。 g y r o s c o p a d j u s t - d e f a n s i r r l t r e p l a e a d j u s t 一d e p e n d a d o p t a n g u l a r i t i h o m o l o g o u s h o m o l o g 一 m m u a e t i v a n g u l a r 一 h o m o l o g e f f e c t i v e e f f e c t b o w d l e r i z e i x r w d l e r p r o b a t e r a t e p r o b a t r a t e - ，a s c o n t r o l l - c o n t r o l r o l lr o l l 这个算法在许多信息检索系统中得到广泛的应用，其不仅不需要词典而且速 复旦大学硕士论文 基于改进k - m e a n s 算法的w e b 文档聚类系统的研究与实现 度较快，被公认为是一种非常好的算法。在此算法中系统用i f 来衡量一个词语 的长短。如果一个词语太短，那么一般不进行后缀替换工作。至此，整个算法已 经介绍完毕i 堋。 3 4 特征项的选择模块 特征项选择和提取是整个w e b 文档聚类系统的基础，它将系统从概念空间 映射到可运算空间，从而使整个系统实现成为可能。 3 4 1 向量空间模型( v s m ：v e c t o rs p a c em o d e l ) g s a l t o n 等人于6 0 年代末提出了向量空间模型v s m ( v e c t o rs p a c em o d e l ) 的概念，即使用向量表示文本或页面【1 1 。 向量空间模型的基本概念可以描述如下【1 】： ( 1 ) 文档：指一般的文本或文本的片段( 段落、旬群或句子) ，一般指一篇文 章。尽管文档可以是多媒体对象，但在我们的讨论中假设为文本对象，并且对文 本和文档不加以区别。 ( 2 ) 项( 特征项) ：文本的内容由一些特征项来表达，一般由文本所含有的基 本语言单位( 字、词、词组或短语等) 来表示，即文本可以表示为 d o c u m e n t - d ( t , ，f 2 ) ，其中表示各个项。换句话说，由这些项形成了一个向 量空间，每个项表示一个维度。 ( 3 ) 项的权重：在文本中，每个特征项都被赋予一个权重职以表示这个特 征项在该文本中的重要程度。权重一般都是以特征项的频率为基础进行计算的。 ( 4 ) 相似度度量：两个文本西和而之间的相关程度常常用它们的相似度 s i m 1 坳来度量。在向量空间模型下，我们可以借助向量之间的某种距离来表 示文本间的相似度。 ( 5 ) 向量空间模型( v s m ) ：给定一个自然语言文本，由于在文本中既可以重 复出现又应该有先后次序的关系，分析起来仍有一定的难度。为了简化分析， 可以暂不考虑在文本中的先后次序并要求互异( 即没有重复) 。在舍弃了各个特 征项之间的顺序信息之后，一个文本就表示成一个向量，也就是特征项空间中 的一个点；而一个文本集就可以表示成一个矩阵，也就是特征项空间中的一些 复旦大学硕士论文基于改进k - m e a n s 算法的w e b 文档聚类系统的研究与实现 点的集合。 3 4 2 特征项的选择 文本挖掘的特征属性是灵活的、多变的，这与数据挖掘使用固定的属性特征 是不同。抽象概念难于表示、难于形式化，文本特征往往是高维的。根据d u n j a m l a d e n i c 和m a r k og r o b e l n i k 在著名的搜索引擎y a h o o 上的实验结果表明，对 全体文档集进行特征表示时，其维数将高达6 9 ，2 8 0 2 5 5 ，6 0 2 维。而另一方面文档 的许多信息又是高冗余的，所以文本特征的提取( 缩减) 是相当重要的，这往往决 定了文本挖掘的效率【3 】。 对目标表示中词条t 的选取被称为特征提取。主要有两大类方法：独立评估 方法和综合评估方法，前者的基本思想是对特征集中的每个特征进行独立的评 估，让每个特征都获得一个权值，然后按权值大小排序，根据权值或预定的特征 数目选取最佳特征子集作为特征提取的结果。后者则是从高维的、彼此间不独立 的原始特征集中找出较少的描述这些特征的综合指标，且这些综合指标之间相互 独立，然后又用得到的综合指标对特征集进行特征选择【3 】。 向量空间模型( v s m ) 表达效果的优劣直接依赖于特征项的选取，以及权 重的计算，在此简单地介绍一下【3 】。 特征项的选择有以下三个原则1 3 】： ( 1 ) 应当选取那些包含语义信息较多的，对文本的表示能力较强的语言单 位作为特征项； ( 2 ) 这种选取的过程本身应当比较容易实现，其时间和空间开销都不应过 大。 ( 3 ) 文本在这些特征项上的分布应当有比较明显的统计规律性； 词特征：词特征对文本的表示能力比较好，词汇能够比较完整地表达语义信 息。然而，并不是所有词都适合作为特征项，研究表明，高频词和低频词对文本 的表示左右均小于中频词。因为高频词在所有文章中都有相近的较高频率；低频 词在文本中出现次数少，不适合采用统计方法来处理；而中频词和文本表达的主 题比较相关，表示能力最强。 字特征：字对文本的表示能力相对于词特征比较差，不能完整地独立地表达 复旦大学硕士论文基于改进k - m e a n s 算法的w e b 文档聚类系统的研究与实现 语义信息。使用字特征的特征抽取过程比较简单，而且由于常用的汉字数目很少， 因此抽取过程的时间和空间开销都不会太大。 对于文本中常常出现一些没有实在意义的虚词、助词等等，比如“的”，“地”， “得”，这些词出现次数很多，然而对于有无实在的意义。常用的方法是建立停 用词表，统计词频时过滤掉这些词，或者采用属性标注的方法，直接过滤掉所有 的虚词【l 】o 3 5 权重计算模块 通过特征提取的处理以后，用抽取的词作为向量的维数来表示文本，最初的 向量表示完全是0 、1 形式，即，如果文本中出现了该词，那么文本向量的该维 为1 ，否则为0 。这种方法无法体现这个词在文本中的作用程度，所以逐渐0 、1 被更精确的权重替代【1 】 向量d1 ( m ，w 2 ，) 表示文档d 的特征词条及相应权重。其中：m 为文档 集中词条的数目，m o 一1 ，掰) 表示词条缸在文档d 中的权重。特征权重w i 的计 算通常采用经典的t f m 一1 0 l 算法，并进行规格化处理【1 s l ： m 。 ( 3 _ 4 ) 其中：z f 表示该词条在文档d 中的频数，d f i 表示文档集中包含词条t i 的文档数，表示文档集中的文档数。 3 6 基于改进k - m e a n s 聚类分析模块的简介 经过前面的网络爬虫、数据清理、中文分词、特征提取、权值计算等模块的 处理，系统已将最初由网络爬虫下载下来的网页转化成了可进行运算聚类运算的 向量。 基于改进的k - m e a n s 聚类分析模块就是将可进行聚类运算的向量进行聚类 分析。具体内容我们在下一章详细介绍。 柏 复旦大学硕士论文基于改进k - m e a n s 算法的w e b 文档聚类系统的研究与实现 第四章k - m e a n s 算法和改进的k - m e a n s 聚类算法 4 1 原始的k - m e a n s 算法 k - m e a n s 算法首先由j m a c q u e e n 在1 9 6 7 年提出【6 】，这是一种应用非常广泛 的聚类算法，广泛应用在数据挖掘领域中。在k - m e a n s 算法中，每个类用该类 中对象的平均值来表示，故此得名k - m e a n s 算法。 k - m e a n s 算法的输入为聚类个数k ，以及包含弗个数据对象的数据库。输出 为满足评价函数最小的k 个聚类。 k - m e a n s 算法流程【6 1 如下： ( 1 )从再个数据对象任意选择k 个对象作为初始聚类中心； ( 2 )根据每个聚类对象的均值( 中心对象) ，计算每个对象与这些中心 对象的相似度；并根据最大相似度( 最小距离) 重新对相应对象进行划分； ( 3 )重新计算每个( 有变化) 聚类的均值( 中心对象) ； ( 4 )循环( 2 ) 到( 3 ) 直到每个聚类不再发生变化为止。 k - m e a n s 算法的工作过程说明如下。首先从栉个数据对象任意选择k 个对象 作为初始聚类中心。而对于所剩下其它对象，则根据它们与这些聚类中心的相似 度( 距离) ，分别将它们分配给与其最相似的( 聚类中心所代表的) 聚类。然后 再计算每个所获新聚类的聚类中心( 该聚类中所有对象的均值) 。不断重复这一 过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数。k 个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 k - m e a n s 算法的主要优点有： ( 1 ) 算法简单； ( 2 ) 处理速度快： ( 3 ) 可伸缩性好； ( 4 ) 效率高； ( 5 ) 适合于处理大数据集和大文档集； ( 6 ) 这个算法试图找出使评价函数值最小的k 个类。当结果类是密集的， 而类与类之间区别明显时，它的聚类效果较好； ( 7 ) 中止条件明确； 4 1 复旦大学硕士论文基于改进k - m e a n s 算法的w e b 文档聚类系统的研究与实现 ( 8 ) 适应动态数据。 然而，这种算法也存在一些主要的缺点和不足，比如： ( 1 ) 受初始聚类中心选择的影响较大。比如，对不同的k 值可能会导致不 同的聚类结果；如果初始聚类中心选择得不好，聚类结果可能会陷入局部最优解， 而得不到较好的聚类效果。 ( 2 ) 对“噪声”和孤立点很敏感，因为少量的该类数据能对平均值产生极 大的影响。 目前针对k - m e a n s 算法的一些主要的缺点和不足，已经提出了很多改进算 法。一般都是基于以下几个方面进行的： ( 1 ) 初始聚类中心的选择； ( 2 ) 相似度的计算； ( 3 ) 聚类平均值的计算。 本文采用k - m e a n s 聚类算法主要基于以下原因： ( 1 ) 文档聚类普遍采用的算法是k - m e a n s 算法 1 5 , 1 6 , 1 7 】。 ( 2 ) k - m e a n s 聚类算法适合于处理大文档集，对处理大数据集，该算法是 相对可伸缩的和高效的。并且算法简单，易实现，效率高。 ( 3 ) 虽然存在一些缺点和不足，但是已经提出了很多有针对性的改进算法。 在本章下面的三个小节中，本文针对k - m e a n s 聚类算法的主要缺点和不足， 对k - m e a n s 算法中的关键环节：相似度计算公式，初始聚类中心的选择和新聚 类中心的计算方法进行了改进。 首先，对k - m e a n s 聚类算法中，使用的变量和名词作以说明： 七：聚类的个数； 1 1 ：需要进行聚类的对象( 文档) 的总数； 小：文档集中词条的个数； t i ( f = 1 m ) ：提取出来特征词条 m ( f = 1 埘) ：词条t l 在文档d 中的权重； 对象= 文档( 本文的聚类对象就是w c b 文档) ； c l ( f = 1 一七) ：聚类划分出类别； s j ( f _ 1 七) ：七个聚类的类中心； 复旦大学硕士论文 基于改进k - m e a n s 算法的w e b 文档聚类系统的研究与实现 在之前介绍的k - m e a n s 算法流程中，我们可以看到有三点非常重要： 1 ，相似度的计算： 2 ，初始聚类中心的选择； 3 ，新聚类中心的计算。 在接下来的三个小节中，本文将针对以上三点进行改进。 4 2 相似性度量的改进 在进行相似性度量的改进之前，首先要对权重评价函数进行改进。因为相似 性的度量主要是对各个向量的权重值进行计算。 向量空间模型( v s m ) 是k - m e 锄s 算法中文档的表示模型，其中的词条权重评 价函数用t f * i d f 表示。然而实际上这种表示方法没有考虑对于该词条在文档中 出现的位置及不同位置对文档内容的决定程度不同这一情况，只体现了该词条是 否出现以及出现多少