（计算机应用技术专业论文）基于术语簇和关联规则的文档聚类方法.pdf

摘要 摘要 聚类技术是数据挖掘领域具有重要价值的技术之一，随着网络在社会生活的不断深 入，加之数据库技术的迅速发展和普及，w e b 挖掘日益受到信息科学界的关注和重视， 总的来说，w 曲挖掘可分为三种类型：w 曲结构挖掘，w | e b 使用挖掘和w - e b 文本挖掘， 其中，文档聚类属于w e b 文本挖掘的研究内容，所谓文本挖掘，是指从文档集合中发 现隐含的某些未知模式或规则。 文档聚类不同于传统的文档分类，它不是基于预定的类表或类目体系，而是完全基 于文档本身，即先有文档后有类，类的内涵和外延以及整个类目体系完全由需要进行聚 类处理的文档集合确定。目前常用的文档聚类方法有层次方法和划分方法等，其中，层 次方法通过将文档组织成若干类并形成一个相应的树来进行聚类，其准确度较高，但运 行速度较慢，不适合大规模文档集合的聚类；划分方法将文档集合水平的划分为许多类， 各类间没有层次性，其运行速度较快，但须事先确定聚类数目，且对噪声和输入顺序较 敏感，尤其是当文档形式化表示的维数较高时，该方法的性能和聚类质量都明显下降。 对此，本文提出一种基于术语簇和关联规则的文档聚类方法，首先对文档集合进行 分词得到许多术语，对这些术语进行处理得到一个术语集合，再计算术语之间的平均互 信息并以此为依据使用聚丛法形成术语簇，用术语簇来表示文档，并计算术语簇和文档 之间的关联度得到一个关联矩阵，使用d h p ( d i r e c th a s h i n g a n dp r i m i n g ) 算法从关联矩阵 中挖掘出文档的初始聚类，对此进行聚类分析获得最终的文档聚类。此外，还使用了新 的术语权重和文档相似度计算方法，在实验数据的计算中使用了加权平均法。实验结果 表明，与传统的聚类方法相比，新聚类方法运行速度快，聚类效果和聚类质量都有显著 提高。 关键词矢量空间模型；关联规则；文档聚类；w e b 挖掘；术语簇 a b s t r a c t a b s t r a c t c l u s t e r i n gi so n eo ft h em o s tv a l u a b l et e c h n o l o g yi nd a t am i n i n gd o m a i n w i t hr a p i d d e v e l o p m e n to fn e t w o r ka n dd a t a b a s et e c h n o l o g y ，w e bm i n i n gh a sg e tm o r ea n dm o r e c o n c e r na n da t t e n t i o n sf r o mi n f o r m a t i o ns c i e n c ed o m a i n i ng e n e r a l ，w i t hd i f f e r e n c eo f c o n t e n t s ，w e bm i n i n gh a st h r e et y p e s ：w e bs t r u c t u r em i n i n g ，w e bu s a g em i n i n ga n dw e b c o n t e n tm i n i n g d o c u m e n tc l u s t e r i n gb e l o n g st ow e bc o n t e n tm i n i n ga n dc o n t e n tm i n i n gi st o f i n ds o m em o d e l so rr u l e sw h i c hi m p l i e di nd o c u m e n tc o l l e c t i o n d o c u m e n tc l u s t e r i n gi sd i f f e r e n tf r o mt r a d i t i o n a ld o c u m e n tc l a s s i f i c a t i o n ，i ti sn o t b a s e do nc l a s s t a b l eo rc l a s sa r c h i t e c t u r e ，b u td o c u m e n t st h e m s e l v e s ，n a m e l y , i tu s e s d o c u m e n t st og e tc l a s s e so fd o c u m e n t ，t h ec o n t e n ta n de x t e n s i o no fc l a s s e sa n dt h ew h o l e c l a s sa r c h i t e c t u r ea r ea l lc o m p l e t e l yd e t e r m i n e db yd o c u m e n tc o l l e c t i o nw h i c hn e e d st od o c l u s t e r i n gp r o c e s s n o wc o m m o nd o c u m e n tc l u s t e r i n gm e t h o d sh a v eh i e r a r c h i c a lm e t h o d ， p a r t i t i o n i n gm e t h o d ，e t c h i e r a r c h i c a lm e t h o do r g a n i z e sd o c u m e n t st os o m ec l a s s e sa n d f o r m sat r e ea c c o r d i n gt ot h e s ec 1 3 s s e st od oc l u s t e r i n gp r o c e s s ，t h ep r e c i s i o no fc l u s t c r i n gi s h i g h e r b u te x e c u t i v es p e e di s s l o w e r , a n di t i sn o tf i tf o rl a r g ed o c u m e n tc o l l e c t i o n ； p a r t i t i o n i n gm e t h o dp a r t i t i o n sd o c u m e n tc o l l e c t i o nt o s o m ec l a s s e sf l a t l y , t h e r ea r en o h i e r a r c h i c a lr e l a t i o n s h i p sb e t w e e nc l a s s e s ，t h ee x e c u t i v es p e e di s q u i c k l yb u tw es h o u l d d e t e r m i n et h en u m b e ro fc l u s t e r i n gi na d v a n c ea n di ti ss e n s i t i v et on o i s ed a t aa n ds e q u e n c e o fd o c u m e n t se s p e c i a l l yw h e nd i m e n s i o no fd o c u m e n tf o r m u l ar e p r e s e n t a t i o ni sh i g h ，t h e p e r f o r m a n c ea n dc l u s t e r i n gq u a l i t ya r ed e c l i n e do b v i o u s l y s ow ep r o p o s ean e wd o c u m e n tc l u s t e r i n ga p p r o a c hb a s e do nt e r mc l u s t e r i n ga n d a s s o c i a t i o nr u l e s i nt h i sa p p r o a c h ，f i r s t l yw eg e tl o t so ft e r m sf r o mp a r t i c i p l ep r o c e s st oa l l d o c u m e n t si nd o c u m e n tc o l l e c t i o na n dd os o m ep r e p r o c e s st ot h e s et e r m st of o r mat e r m c o l l e c t i o n ，t h e nc o m p u t ea m l ( a v e r a g em u t u a li n f o r m a t i o n ) b e t w e e nt e r m sa n du s ec l u m p m e t h o dt oc o n s t r u c tt e r mc l u s t e r i n ga c c o r d i n gt oa m ib e t w e e nt e r m s ，d o c u m e n tv s m ( v e c t o r s p a c em o d e l ) i sr e p r e s e n t e db yt e r mc l u s t e r i n g ，w ec o m p u t et h er e l e v a n c ed e g r e eb e t w e e n d o c u m e n t sa n dt e r mc l u s t e r i n gt og e tar e l e v a n c em a t r i x ，u s ed h p ( d i r e c th a s h i n ga n d ab s t r a c t p r u n i n g ) a l g o r i t h mt om i n ei n i t i a ld o c u m e n tc l u s t e r i n gf r o mr e l e v a n c em a t r i x ，f i n a l l yw ed o c l u s t e r i n ga n a l y s i st og e tf i n a ld o c u m e n tc l u s t e r i n g i na d d i t i o n ，w eu s en e ww e i g h tc o m p u t e f o r m u l ao ft e r m s ，n e ws i m i l a rc o m p u t ef o r m u l ao fd o c u m e n t si n c l u s t e r i n gp r o c e s sa n d w e i g h t - a v e r a g em e t h o dt og e tt h er e s u l t si ne x p e r i m e n t e x p e r i m e n tr e s u l t ss h o wt h a tt h e e x e c u t es p e e d ，p e r f o r m a n c ea n dc l u s t e r i n gq u a l i t yo fn e wa p p r o a c ha r eo b v i o u s l yi m p r o v e d t h a nt h o s eo ft r a d i t i o n a lm e t h o d si nt h ec l u s t e r i n gp r o c e s s k e y w o r d sv e c t o rs p a c em o d e l ；a s s o c i a t i o nr u l e s ；d o c u m e n tc l u s t e r i n g ；w e bm i n i n g ； t e r mc l u s t e r i n g 河北大学 学位论文独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写的研究成果，也不包含为获得河北大学或其他教育机构的学位或证书所 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示了致谢。 作者签名：2 亟盈整日期：丑年立月日 学位论文使用授权声明 本人完全了解河北大学有关保留、使用学位论文的规定，即：学校有权保留并向国 家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。学校可以公布 论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 本学位论文属于 l 、保密口，在年月同解密后适用本授权声明。 2 、不保密包 ( 请在以上相应方格内打“”) 作者签名： 导师签名： 日期：2 竺l 年上l 月上同 日期：4 年鱼一月二一日 第1 章引言 1 1 研究背景 第1 章引言 随着网络在人们社会生活的不断深入，加之数据库技术的迅速发展和普及，人们面 临着一个快速扩张的数据海洋，据粗略估算，早在2 0 世纪8 0 年代，全球的信息量每2 0 个月就翻一番，进入2 0 世纪9 0 年代后，全世界所拥有的数据库及其所存储的数据规模 其增长速度更是飞快，如何有效地利用这一丰富数据海洋的宝藏为人类服务，已经成为 广大信息技术研究人员所关注的焦点之一。 在这种情况下，w e b 挖掘作为数据挖掘中个全新的研究领域便随之诞生了，并日 益受到各国研究者们的重视，总的来说，w e b 挖掘可分成三种类型：1 w e b 结构挖掘； 2 w e b 使用挖掘；3 w e b 文本挖掘【，本文所述的的文档聚类方法就属于第3 种w e b 文 本挖掘的研究内容，所谓文本挖掘，就是指从包含大量文档的集合中发现隐含的某些未 知模式或者规则，若将文本挖掘的整个过程看作是一个i 0 系统，令文档集合d c 作为 输入，隐含的模式或者规则肘& r 作为输出，则进行文本挖掘即是要发现从输入d c 到 输出m & 尺的一个映射三：d cjm & r 。 1 2 国内外研究现状 所谓文档聚类，就是将一个文档集合中的所有文档分成若干类，其中每一类中的文 档之间具有较高的相似度，而不同类中文档之间的相似度很低或者是不相似的。文档聚 类不同于传统的文档分类，因为它不是基于预定的类表或者类目体系，而是完全基于文 档本身的，即先有文档后有类，类的内涵和外延以及整个类目体系完全由需要进行聚类 处理的文档集合确定。 目前常用的文档聚类方法有层次方法，划分方法，基于网格的方法以及基于模型的 方法等，其中，层次方法通过将文档组织成若干类并形成一个相应的树来进行聚类，其 准确度较高，但运行速度较慢，不适合大规模文档集合的聚类；划分方法是将文档集合 水平的划分为许多类，各类之间不具有层次性，都是处于同一层次的，其运行速度较快， 河北人学1 ：学硕十学位论文 但须事先确定聚类的数目，并且对噪声和输入顺序都是敏感的，尤其是当文档形式化表 示的维数较高时，该方法的性能和聚类质量都明显下降；基于网格的方法利用多维网格 数据结构，它将文档空间划分为一定数目的单元网格，以构成一个可进行聚类分析的网 格结构，该方法的聚类时间比较短，但聚类质量和准确性较差；基于模型的方法试着将 文档集合中的文档与某个事先建立的文档模型进行匹配，与其中某个文档模型相匹配的 文档就归到该类中，该类方法主要有统计方法和神经网络方法两种，但他们都不适合对 大规模文档集合进行聚类，其时空开销以及计算复杂度都比较大。 国外近些年来的研究大部分是对传统方法作一些改进或者将一些新的知识和理论 应用到传统的聚类方法中，其中有h 。r a l a m b o n d r a i n y1 2 1 、s h e h r o zs k h a n 3 1 等对 k m e a n s 的改进和扩展；j u n g s o o ny o o 4 1 、s a n j o yd a s g u p t a 5 1 、i v a nk o j a d i n o v i c 6 1 、c l a r k f o l s o n t 7 1 等运用不同知识对层次方法的改进；h e l e n ab r a ss i l v a t 8 】将图论知识、j o s ej a m a d o r l 9 1 将统计方法应用到聚类处理中等，有些学者还把不同的聚类方法结合起来进行 聚类处理，如a b g o k t e p e t l 0 1 等。此外，还有一些专家和学者提出一些新的聚类方法和 聚类思想，其中有k h a l e dm h a m m o u d ar l l j 等的词组索引图模型等。 国内在文档聚类方面的研究人员也比较多，其中有：姜亚莉等的基于相似度的软聚 类算法i t 2 1 ；郑小慎的基于频繁特征项集的文档聚类方法0 3 1 ；王升明等的基于改进的自 组织特征映射网络的文档聚类方法1 1 4 1 ；雷景生等的基于混合神经网络的文档聚类算法 1 1 5 1 ；王维林等的基于进化论思想的w e b 文档聚类方法1 1 6 j ；胡宁静等的基于模糊c 均值 算法文档聚类方法f 1 7 1 ；孙学刚等的基于主题的w e b 文档聚类方法in s ；刘远超等的改进 的基于最小最大原则的k m e a n s 文档聚类初始值选择算法| 1 9 1 等。其中把关联规则用 于到文档聚类处理的有宋擒豹1 2 0 l 和张蓉1 2 1 1 ，他们用术语所组成的主题来表示文档，其 相应的实验也取得了较好的效果。 第1 章引言 1 3 本文工作 相对来说，国内外的相关研究主要是对传统聚类方法做一些改进或者将新的知识和 理论应用到传统聚类方法中，其有着共同的基本聚类机理，而本文则是提出一种新的文 档聚类方法，它利用术语簇和关联规则进行聚类，与传统聚类方法有着较大的不同。 本文提出一种基于术语簇和关联规则的文档聚类方法，该方法首先对文档集合进行 分词得到许多术语，然后利用稀有词和停用词表以及中国分类主题词表等对这些术 语进行处理得到一个术语集合，再计算术语之间的平均互信息并以此为依据使用聚丛法 形成术语簇，用术语簇来表示文档，并计算术语簇和文档之间的关联度得到一个关联矩 阵，使用d h p ( d i r e c th a s h i n g a n dp r u n i n g ) 算法m 1 从关联矩阵中挖掘出文档的初始聚类， 对此进行聚类分析获得最终的文档聚类。此外，还使用了新的术语权重和文档相似度计 算方法，在实验数据的计算中使用了加权平均法。 其主要研究步骤如图1 1 所示： 圈1 1 本义的主要研究步骤 ( 1 ) 文档分词及预处理：主要是对文档集合进行分词，并对分词结果进行处理得 到一个术语集合，其中，要依据停用词表和稀有词表去除停用词和稀有词，使用中国 分类主题词表处理同义词和近义词等； ( 2 ) 构造术语簇：计算术语间的平均互信息，得到一个平均互信息矩阵，以此使 用聚丛法形成术语簇，并计算术语权重； ( 3 ) 文档形式化描述：使用术语簇来表示文档矢量空间模型并计算术语簇和文档 河北人学j i ：学硕+ 学何论文 之间的关联度，得到个关联矩阵； ( 4 ) 挖掘文档初始聚类：使用d h p 算法挖掘关联矩阵中的频繁项集，并以此为依 据得到文档的初始聚类结果； ( 5 ) 初始聚类结果分析评价：使用平均类间差异度和平均类内相似度来评价初始 聚类结果并进行相应处理得到最终文档聚类。 1 4 论文组织结构 本篇论文的具体组织结构如下所示： 第1 章：引言。简要介绍文档聚类的研究背景、国内外研究现状、本文的主要工作 及研究步骤等。 第2 章：传统聚类方法概述。主要介绍传统聚类方法，其中有以k m e a n s 和 k m e d o i d s 为代表的划分方法、以b i r c h2 3 】 2 4 和c u r e l 2 5 为代表的层次方法等。此 外，还简单介绍了其他聚类方法，如基于密度的方法等。 第3 章：基于术语簇和关联规则文档聚类方法的相关知识。主要介绍新聚类方法的 相关知识，其中包括与术语簇、文档形式化描述、关联规则挖掘以及聚类评价指标相关 的知识和技术。 第4 章：基于术语簇和关联规则的文档聚类方法。主要介绍新聚类方法的整个处理 过程，对从文档分词及预处理，途经术语平均互信息计算、构造术语簇、文档与术语簇 关联度计算、关联规则挖掘以及文档聚类评价等步骤，直至得出最终文档聚类的整个过 程进行描述。 第5 章：实验过程及结果分析。首先介绍为评测基于术语簇和关联规则的文档聚类 方法而建立的测试文档集合，然后根据相应的聚类评价指标，通过实验与k m e a n s 和 k m e d o i d s 的聚类质量和时间丌销进行比较，总结新聚类方法的优越性并对此进行分 析。 第6 章：总结与展望。对全文研究工作进行总结并对未来的后续研究工作进行展望。 第2 章传统聚类方法概述 第2 章传统聚类方法概述 聚类分析( c l u s t e r i n g a n a l y s i s ) 又称集群分析，是研究“物以类聚”的一种数据挖 掘方法，它是将一个数据集划分为若干组或类的过程，并使得同一组内的数据对象具有 较高的相似度，而不同组中的数据对象则是不相似的。通过聚类分析，可将性质相近的 个体归为一类，而性质差异较大的个体则归于不同的类。本章主要介绍传统聚类的各种 方法，如划分方法、层次方法等。 2 1 聚类概述 聚类分析起源于分类学，在古老的分类学中，人们主要依靠经验和专业知识来实现 分类，几乎很少利用数学工具来定量分类。随着科学技术的发展，人类对分类的要求也 越来越高，仅凭经验和专业知识很难确切地分类，人们便把各种数学工具逐渐引用到分 类学中，形成了数值分类学，随后多元分析技术引入到数值分类学中就形成了聚类分析。 将许多物理的或抽象的对象，根据它们之间的相似程度，分为若干组，其中相似的 对象构成一组，这一过程就称为聚类处理。一个聚类就是由彼此相似的一组对象所构成 的集合且不同聚类中的对象彼此不相似。聚类分析就是从给定的数据集中找出数据对象 之间所存在的有价值联系。 目前，聚类分析已被应用到众多领域，其中包括：模式识别、数据分析、图像处理 及市场分析与预测等。通过聚类，人们可发现数据对象整个分布模式及数据对象各属性 之间所存在的有价值联系。聚类分析的典型应用有：商业方面，聚类分析可帮助市场分 析人员发现顾客群中所存在的具有不同特征的组群，再利用消费模式来描述不同的顾客 组群，最后以此采取相应的市场开拓策略以取得商业上的成功；生物方面，聚类分析可 获取动植物之间所存在的层次结构，或者根据基因功能对其进行分类以获得对人群所固 有的结构有更深入的了解等；此外，聚类还可以从地球观测数据库中帮助识别具有相似 的土地使用情况的区域等；作为数据挖掘的重要研究内容，聚类还可分析出数据的分布、 各数据类的特征及确定所感兴趣的数据类以作进一步的分析研究等；还有，聚类分析也 可作为其他算法如分类和定性归纳算法的预处理步骤等。 聚类算法目前有许多种，其中包括划分方法、层次方法、基于密度的方法、基于网 5 河北- 人学一r 学硕十学位论文 格的方法以及基于模型的方法等。通常需要根据实际应用所涉及的数据类型、聚类目的 以及具体应用要求来选择合适的聚类算法。若将聚类分析作为描述性或探索性的工具， 则可使用若干聚类算法对同一数据集分别进行多次处理以观察可获得的有关数据描述。 2 2 划分方法 给定一个包含个数据对象的集合和划分个数k ，划分方法要将该集合划分为k 个子集( 或划分) ，其中每个子集代表一个聚类( 憝) 且这些子集还要满足以下要求： ( 1 ) 每个子集至少包含一个数据对象( 可根据实际应用需要对子集所包含的数据 对象的最少个数进行规定) ； ( 2 ) 每个数据对象仅属于某一子集( 可根据实际应用的需要对此进行调整) 。 划分方法首先根据划分个数k 创建一个初始划分，然后利用循环再定位技术，即通 过调整不同划分中的数据对象来改变划分内容，其最终所形成的聚类将达到某个客观划 分标准( 又称相似函数) 的最优化，并使得每个聚类中的数据对象都彼此相似，不同聚 类中的数据对象彼此不相似。 2 2 1 传统划分方法 目前最常用也最知名的划分方法是k m e a n s 和k m e d o i d s 以及它们的相关改进 算法，这两种算法都属于启发式聚类算法，它们在分析中小规模的数据集以发现圆形或 者球状聚类时效果很好，两者最大的不同之处在于k m e a n s 中的每个聚类用相应聚类 中数据对象的均值来表示，而k m e d o i d s 中每个聚类用相应聚类中离聚类中心最近的 数据对象来表示。 1 k m e a n s 算法 k m e a n s 使用随机方式选择k 个数据对象作为初始的聚类中心，然后算法开始迭 代执行，直到算法最后迭代时每个聚类中所包含的数据对象不再发生变化为止。 k m e a n s 算法描述 输入：划分个数k 以及包含个数据对象的数据集。 输出：满足某个客观划分标准( 通常使用方差最小标准) 的k 个划分( 或聚类) 。 处理流程： 6 第2 章传统聚类方法概述 ( 1 ) 从个数据对象中用某种随机方式选择k 个数据对象作为初始聚类中心； ( 2 ) 循环下述步骤( 3 ) 到( 4 ) ，直到每个聚类不再发生变化为止； ( 3 ) 根据每个聚类对象的均值( 即中心数据对象) ，计算每个数据对象与相应中心 数据对象的距离，并根据最小距离原则重新对数据对象进行划分； ( 4 ) 重新计算每个( 有变化) 聚类的均值( 即中心数据对象) 。 k m e a n s 算法的主要处理过程说明：首先从个数据对象中任意选择k 个对象作 为初始聚类中心，剩下的其他数据对象，则根据它们和这些聚类中心的相似度( 或距离) ， 分别将它们划分给与之最相似的聚类，然后再计算每个新聚类的聚类中心，不断重复这 一过程直到标准测度函数开始收敛为止，一般采用均方差作为标准测度函数，其具体定 义如下： k e = i p - - m t1 2 ( 2 1 ) t = lp e c | 其中，是数据集中所有数据对象与相应聚类中心的均方差之和；p 代表数据对象 f j d o 的一个点；为聚类c 的均值( p 和啊均是多维的) 。 k m e a n s 算法适用于聚类均值有意义的应用，它需事先指定划分个数k ，并对噪 声和异常数据较敏感，也不宜发现非凸形状或大小不同的聚类。此外，k m e a n s 还有 一些改进算法，它们主要是在初始k 个聚类中心的选择、差异度计算和聚类中心均值的 计算方法等方面有所不同，但基本的聚类思想和处理过程都基本相同。 2 k m e d o i d s 算法 由于异常数据对象的取值可6 月匕p - - ，4 k h 大，它将影响到对数据对象分布的估计，在此使用 m e d o i d s 作为参考点来代替k m e a n s 算法中各聚类的均值，便可继续依据各数据对 象与各参考点间的距离( 差异性) 之和最小化原则来应用划分方法，这就形成了 k m e d o i d s 算法。 k m e d o i d s 算法的基本策略是首先为每个聚类任意找一个中心数据对象，从而把 包含个数据对象的集合划分为k 个聚类，其他数据对象则根据他们与相应中心数据 对象的距离分别归属到各个聚类中。其中，若替换一个聚类的中心数据对象能够提高聚 类的整体质量，则用新数据对象作为该聚类的中心数据对象。 河北大学t 学硕十学佗论文 k m e d o i d s 算法描述 输入：划分个数足以及包含个数据对象的数据集。 输出：满足某个客观划分标准( 通常使用方差最小标准) 的k 个划分( 或聚类) 。 处理流程： ( 1 ) 从个数据对象中用某种随机方式选择k 个数据对象作为初始聚类中心； ( 2 ) 循环步骤( 3 ) 到( 5 ) ，直到每个聚类不再发生变化为止； ( 3 ) 依据每个聚类的中心数据对象及各数据对象与相应中心数据对象间的距离， 根据最小距离原则重新对数据对象进行划分； ( 4 ) 任意选择一个非中心对象棚，计算其与中心对象p ，交换的整个成本s ； ( 5 ) 若s 为负值则交换q 瓣。与0 ，以构成新聚类的k 个中心对象。 与k m e a n s 算法相比，k m e d o i d s 算法在处理异常数据和噪声数据方面更为鲁 棒，这主要是因为与聚类均值相比，一个聚类的中心数据对象较少受到异常数据或极端 数据的影响，两者的共同点是都须事先指定划分个数k 。 2 2 2 大型数据集的划分方法 传统划分方法在中小型数据集上所取得的效果较好，但在处理大型数据集时其效果 却并不理想，对此人们用一个基于采样的聚类方法c l a r a ( c l u s t e r i n gl a r g e a p p l i c a t i o n ) 来解决这个问题，以达到有效处理大型数据集的目的。 由于c l a r a 方法在聚类处理过程中使用了p a m ( p a r t i t i o n i n g a r o u n dm e d o i d s ) 算 法，在介绍c l a r a 方法之前，先介绍p a m 算法的基本知识，p a m 是一种最初提出的 k m e d o i d s 算法，它在初始选择k 个中心数据对象后，不断循环对每两个数据对象( 一 个非中心数据对象，一个中心数据对象) 进行分析，以选择最佳的中心数据对象，并根 据各聚类所包含的数据对象分析计算所达到的聚类质量。 c l a r a 方法的基本思想是在聚类处理过程中无需考虑整个数据集，而只取其中一 小部分数据作为样本集，然后利用p a m 算法从这个样本集中选出中，心数据对象。如果 样本数据是随机选择的，则样本集就可近似代表原来的数据集。从样本集所选出的中心 数据对象就很接近从整个数据集中所选出的中心数据对象。c l a r a 方法在处理过程中， 会分别取若干样本集，然后对每个样本集都应用p a m 算法，再将其中最好的聚类结果 r 第2 章传统聚类方法概述 输出。 c l a r a 方法在处理大规模数据集时其每次循环的计算复杂度为 o ( k s 2 + k ( n k ) ) ，其中，s 为样本集大小，k 为聚类个数，为数据对象总数。该方 法的有效性依赖于诸多要素，如所选择样本集的质量和大小及p a m 算法从给定数据集 中是否选择到最好的k 个中心数据对象等。若样本集中的中心数据对象不是整个数据集 最好的x 个中心数据对象，则c l a r a 方法就很难发现最好的聚类结果。 大型数据集的其他聚类方法还有c l a r a n s ( c l u s t e r i n gl a r g ea p p l i c a t i o nb a s e du p o n r a n d o m i z e ds e a r c h ) ，它将采样算法和p a m 算法结合起来进行聚类处理。与c l a r a 方法最大的不同之处在于c l a r a n s 方法在聚类处理的每一步都以某种随机方式进行 采样，其处理的样本集是动态变化的，而c l a r a 方法每一步处理的数据样本是固定的。 c l a r a n s 方法的整个处理过程可描述成一个图，图中的每个结点都代表潜在的解 决方案( 即一组聚类的中心数据对象) ，替换一个中，t l , 数据对象所得到的新聚类就称为 当前聚类的邻居，随机产生的聚类邻居数由用户所设置的参数来限制。若发现一个更好 的邻居时，c l a r a n s 方法移动到该邻居结点，否则当前结点就是一个局部最优，若发 现一个局部最优，c l a r a n s 方法就随机选择一个结点重新开始以寻找下一个局部最 优。 c l a r a n s 方法能够发现最“自然”的聚类个数，它比c l a r a 方法和p a m 算法 都有效，并可用于检测异常数据，但其计算复杂度较大。 2 3 层次方法 层次方法通过分解所给定的数据集来创建层次结构。根据层次分解的方式，可将层 次方法分为自下而上和自上而下两种类型。自下而上的层次方法从每个数据对象均为一 个单独组开始，逐步将这些组合并，直到这些组合并到层次顶端或满足预先设定的终止 条件为止；自上而下的层次方法从所有数据对象均属于一个组开始，每一个循环将其分 解为更小的组，直到每个数据对象构成一组或满足预先设定的终止条件为止。 。 层次方法最大的缺陷是每次分解或合并后，无法进行回溯，这一点使得在分解或合 并时无需考虑不同选择所造成的组合爆炸问题，但同时会造成该方法无法纠正自己的错 误决策，为此人们将循环再定位与层次方法结合起来处理这个问题，即首先利用自下而 9 河北人学j i ：学硕+ 学位论文 上的层次方法，然后再利用循环再定位技术对聚类结果进行调整，一些具有可扩展性的 聚类算法，如b i r c h 和c u r e ，就是基于这种思想设计的。 2 3 。1b i r c h 方法 b i r c h ( b a l a n c e di t e r a t i v er e d u c i n ga n dc l u s t e r i n gu s i n gh i e r a r c h i e s ) 方法是一种集 成的层次聚类方法，它是自下而上的，其中包含有两个重要概念：聚类特征( c l u s t e r i n g f e a t u r e ，简称c f ) 和聚类特征树( c l u s t e r i n gf e a t u r et r e e ，简称c ft r e e ) ，这两个概念 主要用于对聚类描述进行概要总结。 聚类特征是有关数据对象子集概要信息的一个三元组，令一个聚类包含个d 维数 据对象q ，则该聚类的c f 为：c f = ( n ，l s ，s s ) ，其中，表示该聚类所包含的数据对 象个数；历表示个数据点的向量和，即n 孑，鼹表示数据点的平方和，即兰i 2 ； c f 树是一个高度平衡树，它存有用于进行层次聚类的聚类特征，一个c f 树有两个重 要参数：分支系数和阈值，其中，分支系数用于指定每个非叶结点的最大子女数，而阈 值用于指定存放在叶结点的聚类最大直径，此外该树中的非叶子结点还存放有子女结点 的c f 值。 b i r c h 方法的处理过程主要包括两个阶段： 第阶段：b i r c h 方法扫描整个数据集以建立一个初始的基于内存的c f 树，该树 可看成是对数掘集的压缩，其中保留有数据集中关于聚类结构的相关信息； 第二阶段：b i r c h 方法应用一种聚类算法( 一般为划分方法) 对c f 树的叶结点进 行聚类。 有关实验表明，就数据集的大小和所取得的聚类质量而言，b i r c h 方法表现出线 性可扩展性，其计算复杂度为o ( n ) ，此外，b i r c h 方法在进行动态聚类时也很有效。 但由于c f 树中的每个结点仅能容纳有限的入口，使得一个c f 树结点并不总能对应一 个自然聚类，另一方面，由于b i r c h 方法是利用半径来控制聚类的，当聚类形状不是 圆形时，该方法的性能会变差。 第2 章传统聚类方法概述 2 3 2c u r e 方法 c u r e ( c l u s t e r i n gu s i n gr e p r e s e n t a t i v e s ) 方法将层次方法和划分方法结合起来，它 在克服偏向发现相似大小和圆形形状聚类不足的同时，在处理异常数据时也显得更加鲁 棒。它是自上而下进行分解和自下而上进行聚合的折中方案，它在用中心数据对象描述 聚类的同时，选用有代表性的空间点表示聚类，这些空间点首先通过选择分布较好的聚 类对象来产生，然后根据指定的速率( 收缩因子) 将它们“收缩”移向聚类中心，该方 法的每一步，都是对分别来自两个不同聚类两个最近代表点所涉及的两个聚类进行合 并。 c u r e 方法的主要处理步骤如下： ( 1 ) 对数据集进行随机采样获得集合s ，其中包含s 个对象； ( 2 ) 将采样集合s 划分成夕个划分，每个划分大小为【s p 】； ( 3 ) 将各划分部分聚类成【s ( p 9 ) 】个聚类，其中q j ； ( 4 ) 通过随机采样消除异常数据，即若一个聚类增长速度太慢，就除去它； ( 5 ) 对部分聚类进行再聚类，对落在每个新获得聚类中的代表点，根据收缩囚子 伐，“收缩”移向聚类中心。 ( 6 ) 对聚类中的数据标记相应的聚类号。 c u r e 方法对异常数据对象进行分析时，也能获得较高的聚类质量。此外，它还允 许聚类具有复杂的形状和不同的大小，且该方法只需对整个数据集进行一遍扫描，其计 算复杂度为o ( n ) 。 2 3 3 其他层次方法 r o c k 方法是一种聚合层次聚类算法，与c u r e 方法不同的是它可以处理符号属 性，它通过将两聚类间连接的累计与用户所指定的静态连接模型相比较，计算出两聚类 的相似性，聚类间的相似程度利用不同聚类中点所具有的共同邻居数来确定。r o c k 方 法首先根据所给数据集的相似矩阵和相似阈值，构造一个松散图，然后在松散图上应用 一个层次聚类算法来进行处理。 1 l - 洞北人学t 学硕十学何论文 c h e m a l e o n 方法1 2 6 1 是一种探索层次聚类动态模型的聚类算法，它是针对c u r e 和r o c k 这两个层次方法所存在的不足而提出的，其主要由于c u r e 方法忽略了两个 不同聚类间的连接累计信息，而r o c k 在强调聚类间连接信息时却忽略了两个聚类的相 近信息。c h e m a l e o n 方法首先利用一个图划分算法将数据集聚合成许多相对较小的 子聚类，然后再利用聚合层次聚类方法，通过不断合并子聚类来发现真正的聚类。在聚 类处理过程中，该算法不仅考虑聚类间的连结度，而且也考虑聚类间的近似度，特别是 聚类本身的内部特征。 2 4 其他聚类方法 除划分方法和层次方法外，还有众多其他聚类方法，本节简单介绍一下其中的三种 聚类方法：基于密度的方法、基于网格的方法及基于模型的方法。 2 4 1 基于密度的方法 基于密度方法的指导思想是，只要某区域中点的密度大于某个阀值，就把它加入与 之相近的聚类中。由于大多数划分方法是基于对象间距离进行聚类的，因此仅能发现圆 形或球状的聚类而较难发现具有任意形状的聚类，基于密度的聚类方法实际上就是解决 这个问题的，它不断增长所获聚类直到“邻近”的数据对象密度小于一定阈值为止。这 种方法可以用于消除数据中的噪声以及帮助发现任意形状的聚类，其典型方法有 d b s c a n 、o p t i c s 2 7 1 等。 2 4 2 基于网格的方法 基于网格的方法将整个数据对象空间划分为有限数目的单元以形成一个网格结构， 所有的聚类操作都在这一网格结构上进行。该方法的主要优点是处理时间仅与划分数据 对象空间的网格数相关，而与数据对象的个数无关，处理速度相对较快，其典型方法有 s t i n g 2 8 1 等。 筇2 章传统聚类方法概述 2 4 3 基于模型的方法 基于模型的方法其处理过程是首先为每个聚类假设一个模型，再去发现符合相应模 型的数据对象，该类方法可通过构造一个描述数据点空间分布的密度函数来确定具体的 聚类。它根据标准统计方法并考虑“噪声”或异常数据等因素，可自动确定聚类个数， 是一种较鲁棒的聚类方法。 在实际应用中，一些聚类算法将若干聚类方法的思想结合在一起，因此很难明确界 定一个聚类算法究竟属于哪一聚类方法类别。此外，一些应用也需要将多个聚类技术结 合起来方可实现应用目标。 河北火学一f j 学硕十学何论文 第3 章基于术语簇和关联规则文档聚类方法的相关知识 本文提出一种新的基于术语簇和关联规则的文档聚类方法，该聚类方法运用了信息 科学领域和数据挖掘领域的众多知识和技术，如术语簇、平均互信息、文档形式化描述、 关联规则，关联规则挖掘算法等，本章主要对此进行介绍。 3 1 术语簇 术语簇( t e r mc l u s t e r i n g ，简称t c ) 是根据术语之间的关联信息，采用统计或计算 的方法对术语进行群集以生成某种类集或群体，它主要应用于词表或类表的自动生成、 文档聚类、自动标引等研究领域。其中，术语之间的关联信息一般用术语在文档中的出 现频度、共现频度、位置以及相应权值等以及它们的组合来表示。 3 1 1 平均互信息 一般来说，术语与术语之间的搭配是有一定规律的，其表现为许多术语与另外其他 一些术语之间具有相对固定的搭配关系。任意给定两个术语，它们之间的相近关系可以 分为两种，即语义相似和语义相关1 2 9 1 ，其中的语义相似，即近义词和同义词一类的，对 于语义相关的两个术语，本文采用平均互信息( a v e r a g em u t u a li n f o r m a t i o n ，简称a m i ) 来描述它们之间的相关度，在此引入文档集合、术语集合、术语间平均互信息及术语簇 的定义： 定义1 ：文档集合d = ( 口，d 2 ，毋，q ) ，j 七疗。 ( 3 1 ) 其中，q 表示文档集合d 中的第k 个文档； 表示文档集合d 所包含的文档总数。 定义2 ：术语集合t = ( 乃，乃，z ，瓦，) ，f m 。 ( 3 2 ) 其中，r 表示术语集合丁中的第，个术语；m 为术语集合丁所包含的术语总数。 定义3 ：术语z 和术语r 之间的平均互信息为： 第3 章基丁术语簇和关联规则文档聚类方法的相关知识 a m ( r , ，i ) =