（计算机应用技术专业论文）基于网格的数据流聚类方法研究.pdf

一：；， - 一 j c l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo f d e n g r e s e a r c ho fd a t as t r e a mc l u s t e r i n gm e t h o d s b a s e do ng r i d c a n d i d a t e ：y ux i a n g s u p e r v i s o r ：p r o f y i ng u i s h e n g a c a d e m i cd e g r e ea p p li e df o r ：d o c t o ro fe n g i n e e r i n g s p e ci a lt y ：c o m p u t e ra p p lie dt e c h n o l o g y d a t eo fs u b m i s s i o n ：a p r il ，2 0 1 0 d a t eo f0 r a le x a m i n a t i o n ：j u n e ，2 0 1 0 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y ，。 - ， - ， 哈尔滨工程大学 学位论文原创性声蹰 本人郑重声明：本论文的所有工作，是在导师的指导下，自 作者本人独立完成的。有关观点、方法、数据和文献i f i - il 用己在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体己经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均己在文中以明确方式 标黾弓。本人完全惹识到本声明的法律结果由本人承担。 作者( 签字) ：一一寸荔防 日期： 钞产年舌月，3 曰 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属亍哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文泛在授予学位后即可口在授予学位1 2 个月后 口 解密后) 自哈尔滨工程大学送交有关部门进行保存、 作者( 签享) ： 匀射 导师( 签享) 邑期：矽少年多月哆吕 扣年乡胃 孑， 0 基于网格的数据流聚类方法研究 摘要 近年来，数据采集技术以及数据挖掘技术不断发展，通常在短时间内就 可以采集到大量的数据，并加以分析处理。随着信息技术以及w e b 技术的飞 速发展，数据不再是存储于可多次随机访问的介质中的静态数据，而是称之 为数据流的动态流式数据。不同于静态数据，数据流具有实时性、连续性、 顺序性等特性，因而传统的聚类分析技术无法直接应用于数据流，需要新的 聚类分析技术来处理数据流。本文针对数据流聚类技术从多个方面进行了深 入细致地研究。 首先，分析了基于网格的聚类算法的优缺点，进而对传统的静态网格划 分方法以及动态网格划分方法进行了研究，针对网格聚类算法中数据空间的 划分方法进行改进，拟对新的数据空间动态划分策略展开研究，使其可增量 地更新网格单元的结构以及统计信息。在此基础上，设计出基于动态网格划 分的聚类算法，使得新算法不仅具有传统网格聚类算法的高效性，且在一定 程度上提高聚类的质量。 其次，在新的数据空间动态划分策略的基础上，着重针对数据流的增量 聚类进行研究。对现有的数据流聚类算法和增量聚类算法的特性以及存在的 问题进行分析，针对数据流对聚类算法的实时性等方面的要求以及现有聚类 算法对非球形聚类效果不好的缺点，设计一种基于数据流的不规则网格增量 聚类算法。使得与其它算法相比，新算法具备传统网格聚类算法处理速度快 的优点，同时不断动态增量地调整网格整体结构。并充分利用网格聚类算法 的特点，通过判断网格是否相连，保证对于不同形状聚类的聚类效果。在网 格聚类时，无需预先指定聚类数目，且对孤立点有较好的鲁棒性。通常包含 孤立点的网格单元不会满足稠密度阈值的要求，可以通过剪枝策略进行去除 以减少算法复杂性。由于动态划分的网格单元反映了当前数据流的分布特点， 新算法应在一定程度上提高聚类的精度。 再次，在分析高维数据聚类方法和维度约简方法以及这两种方法在数据 哈尔滨t 稃大学博十学位论文 流环境中应用的基础上，针对高维空间数据稀疏性、数据属性重要度倾斜等 问题，对粗糙集理论进行研究，拟设计一种基于粗糙集属性约简的数据流增 量聚类算法。新算法应针对聚类的无监督特性通过改进后的无决策属性的属 性约简方法计算数据点各属性的重要度，并调整属性集。在属性集中增加具 有较高重要度属性的同时，淘汰属性集中不再重要的属性。同时，新的约简 算法在保证聚类精度的前提下，可动态调整参与聚类的属性集合，提高算法 的效率。 最后，对现有的数据流子空间聚类算法进行研究，针对现有子空间聚类 算法中效率较低的问题，拟提出一种新的基于区域划分策略的数据流子空间 聚类算法，新算法拟采用自底向上的搜索策略，充分考虑数据点在每维上的 分布特性，对各维空间进行区域划分，根据区域交叠产生聚类子空间，进而 聚类。新算法应具有处理速度快、对孤立点不敏感等优点，可以有效地在高 维数据流中识别出子空间聚类。且可根据数据流的变化情况，对区域进行重 新划分，以有效地反映数据流的变化。 本文的工作围绕着数据流聚类展开，通过对数据挖掘技术、人工智能技 术、粗糙集理论等的研究，并通过仿真实验证明方法的有用性和有效性，为 未来的研究工作提供了良好的理论基础和思路。 关键词：数据流；网格；增量聚类；动态划分；约简 口 r 基于网格的数据流聚类方法研究 a b s t r a c t i nr e c e n ty e a r s ，t h et e c h n o l o g yo fd g ac o l l e c t i o na n dd a t am i n i n gd e v e l o p e d c o n t i n u o u s l y , t h e nw ec a ng e tm a s s i v ed a t at op r o c e s sa n da n a l y z ei nv e r ys h o r t t i m e w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g ya n dw e b t e c h n o l o g y , 一 data a r en ol o n g e rs t a t i cd a t as t o r e di nt h em e d i aw h i c hc a nb ev i s i t e ds e v e r a l t i m e s ，b u tt h ef l o w t y p ed a t ac a l l e dd a t as t r e a m o t h e rt h a ns t a t i cd a t a , d a t as t r e a m h a st h ec h a r a c t e r i s t i c so fr e a l t i m e p r o p e r t y , c o n t i n u i t yp r o p e r t y , s u c c e s s i o n p r o p e r t y , e t c t r a d i t i o n a lc l u s t e r i n ga n a l y s i st e c h n o l o g yc a nn o tp r o c e s sd a t a s t r e a md i r e c t l y , a n dn e wt e c h n o l o g yi sr e q u i r e dt op r o c e s sd a t as t r e a m t h i sp a p e r m a k e sd e e pa n dd e t a i l e ds t u d yo nt h ec l u s t e r i n gt e c h n o l o g yo fd a t as t r e a mf r o m s e v e r a ls e a l e s f i r s t ，w ea n a l y z et h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h ec l u s t e r i n g a l g o r i t h m sb a s e do n 鲥d ，t h e nf u r t h e rm a k et h es t u d yo nt r a d i t i o n a ls t a t i c 酣d p a r t i t i o nm e t h o d sa n dd y n a m i co n e s w ep r o p o s ean e wd y n a m i cp a r t i t i o ns t r a t e g y o fd a t as p a c ew h i c hi m p r o v e st h ep a r t i t i o nm e t h o d si nc l u s t e r i n ga l g o r i t h m sb a s e d o ng r i da n du p d a t e st h es t r u c t u r eo f 咖dc e l l sa n dt h es t a t i s t i c si n f o r m a t i o n o n t h eb a s i so ft h e s e ，w ep r o p o s et h ec l u s t e r i n ga l g o r i t h mb a s e do nd y n a m i c 鲥d p a r t i t i o nw h i c hh a sh i g he f f e c t i v e n e s sa st r a d i t i o n a lc l u s t e r i n ga l g o r i t h mb a s e do n g r i dd o e sa n di m p r o v et h ec l u s t e r i n gq u a l i t yi naw a y s e c o n d ，b a s e do nt h en e wp r o p o s e dd y n a m i cp a r t i t i o ns t r a t e g y , w et h e np u t f o c u so nt h es t u d yo fd a t as t r e a mi n c r e m e n t a l c l u s t e r i n g h a v es t u d i e dt h e c h a r a c t e r i s t i c so ft h ec u r r e n td a t as t r e a m c l u s t e r i n ga l g o r i t h m s ， c u r r e n t i n c r e m e n t a lc l u s t e r i n ga l g o r i t h ma n dt h ee x i s t i n gd i s a d v a n t a g e s ，w ep l a nt od e s i g n an e wa l g o r i t h mw h i c hi sa ni n c r e m e n t a la l g o r i t h mb a s e do ni r r e g u l a rg r i df o r c l u s t e r i n g d a t as t r e a mt o p r o c e s st h ed i s a d v a n t a g e s o fc u r r e n t c l u s t e r i n g a l g o r i t h m si n e f f e c t i v e n e s so fc l u s t e r i n gs p h e r i c a lc l u s t e r sa n dt om e e tt h e 哈尔滨丁稃大学博十学1 _ f 7 ：论文 r e q u i r e m e n t so fr e a l t i m ep r o p e r t y , e t c c o m p a r e d t oo t h e ra l g o r i t h m s ，t h e p r o p o s e da l g o r i t h ms h o u l dh a v et h ea d v a n t a g eo fh i g he f f i c i e n c y , m e a n w h i l e ，i t 甜j u s tt h e 鲥ds t r u c t u r ec o n t i n u o u s l ya n dd y n a m i c l y t h en e wp r o p o s e da l g o r i t h m j u d g e sw h e t h e rg r i dc e l l sa r ec o n n e c t e d ，a n dg u a r a n t e e st h ec l u s t e r i n gr e s u l t so f d i f f e r e n ts h a p eo fd u p e r s w h e nc l u s t e r i n g ，i tn e e d n tt op r o v i d et h en u m b e ro f c l u s t e r sa n di ts h o u l dn o tb es e n s i t i v et oo u t l i e r g e n e r a l l y , t h eg r i dc e l l sc o n t a i n s o u t l i e r sc a nn o te x c e e dt h et h r e s h o l do fd e n s i t ya n dc a nb er e m o v e db yp r u n i n g s t r a t e g yt or e d u c et h ec o m p l e x i t yo fa l g o r i t h mw h i c hw o n ti n f l u e n c et h ep r o c e s s o fc l u s t e r i n g t h ed y n a m i cp a r t i t i o ns t r a t e g yo fg r i dc e l l s r e f l e c t st h ec u r r e n t 基于网格的数据流聚类方法研究 c h a n g e so fd a t as t r e a mw h i c hc a nr e f l e c tt h es t a t u so fd a t as t r e a m t h i sd i s s e r t a t i o ni sm a i n l yc a r r i e do nd a t as t r e a mc l u s t e r i n g a n dt h ev a l i d i t y , e f f i c i e n c yo f e a c hn e wm e t h o di sd e m o n s t r a t e db ys i m u l a t ee x p e r i m e n t s w i t ht h e r e s e a r c ho nd a t am i n i n gt e c h n o l o g y , a r t i f i c i a li n t e l l i g e n c ea n dr o u g hs e tt h e o r y i n v o l v e d ，i tp r o v i d e sag o o dt h e o r e t i c a lb a s i sa n di d e af o rf u t u r er e s e a r c h k e yw o r d s ：d a t as t r e a m ；g r i d ；i n c r e m e n t a lc l u s t e r i n g ；d y n a m i cp a r t i t i o n ； r e d u c t i o n 基于网格的数据流聚类方法研究 目录 第1 章绪论1 1 1 论文的选题背景及意义1 1 2 国内外研究现状3 1 2 1 基于网格的聚类方法“3 1 2 2 增量聚类算法8 1 2 3 高维聚类算法1 0 1 2 4 子空间聚类方法1 2 1 3 论文的研究内容”16 1 4 论文的组织结构”1 7 1 5 本章小结1 9 第2 章数据流聚类相关理论2 1 2 1 数据空间划分方法”2 1 2 1 1 均匀网格划分”2 1 2 1 2 不均匀网格划分2 2 2 1 3 聚类方法中的网格划分2 4 2 2 数据流聚类技术”2 7 2 2 1 数据流的特征2 7 2 2 2 数据流聚类的要求2 7 2 2 3 数据流聚类算法”2 8 2 3 粗糙集基本理论”3 0 2 3 1 粗糙集的基本概念3 0 2 3 2 粗糙集模型的算法3 2 2 4 其他相关技术“3 3 2 4 1 特征转换技术3 3 2 4 2 特征选择技术”3 3 2 5 本章小结3 4 哈尔滨丁程大学博十学位论文 第3 章动态网格划分的聚类方法一“3 7 3 1 引言3 7 3 2 动态网格划分中的问题分析”3 7 3 2 1 问题分析及解决方法3 7 3 2 2 相关概念3 9 3 3 基于动态网格划分的聚类方法i g r i d 4 1 3 3 1i g r i d 算法的网格结构形成4 1 3 3 2i g r i d 算法的聚类过程”4 3 3 4 理论分析与实验分析”4 4 3 4 1 算法复杂性分析4 4 3 4 2 实验结果与分析4 4 3 5 本章小结”4 7 第4 章数据流的不规则网格增量聚类方法4 9 4 1 引言4 9 4 2 增量数据流聚类中的问题分析”4 9 4 2 1 问题分析及解决方法4 9 4 2 2 相关概念5 0 4 3 基于数据流的增量聚类算法i i g s t r e a m 5 2 4 3 1i i g s t r e a m 中的数据压缩表示5 2 4 3 2i i g s t r e a m 的在线微聚类过程一5 3 4 3 3i i g s t r e a m 的离线宏聚类过程5 4 4 4 理论分析与实验分析”5 4 4 4 1 算法复杂性分析5 5 4 4 2 实验结果与分析5 5 4 。5 本章小结”5 9 第5 章数据流的粗约简增量聚类方法6 1 5 1 引言”6 1 5 2 数据流聚类中的维度约简分析一6 2 i 基于网格的数据流聚类方法研究 5 2 1 问题分析及解决方法6 2 5 2 2 相关概念6 4 5 3 基于粗约简的数据流增量聚类算法“6 5 5 3 1r i c s t r e a m 的基本原理6 5 5 3 2r i c s t r e a m 中的维度约简过程6 6 5 3 3r i c s t r e a m 中的聚类过程”6 7 5 4 理论分析与实验分析6 8 5 4 1 算法复杂性分析6 8 5 4 2 实验结果与分析6 9 5 5 本章小结7 3 第6 章数据流的子空间聚类方法”7 5 6 1 引言7 5 6 2 数据流子空间聚类中的问题分析一7 9 6 2 1 问题分析及解决方法7 9 6 2 2 相关概念8 1 6 3 基于数据流的子空间聚类算法r g s c d 8 1 6 3 1r g s c d 中数据的区域划分”8l 6 3 2r g s c d 中的聚类描述”8 3 6 3 3r g s c d 子空间聚类过程”8 4 6 4 理论分析与实验分析8 6 6 4 1 算法复杂性分析8 7 6 4 2 实验结果与分析8 7 6 5 本章小结9 1 结论9 3 参考文献9 5 攻读博士学位期间发表的论文和取得的科研成果“1 0 7 蜀c 谢10 9 第1 章绪论 ， 第1 章绪论 1 1 论文的选题背景及意义 聚类分析是重要的数据挖掘技术之一，聚类分析既可以作为一个独立的 工具来获取数据的分布情况，也可以作为其它数据挖掘算法的预处理步骤。 作为统计学的一个分支，作为数据挖掘领域中的重要技术，聚类分析技术经 过多年的发展，随着新的聚类要求的出现，已再次成为研究热点。 聚类是一种无监督学习过程，数据中不提供类标记等信息。聚类是一个 过程，该过程将物理或是抽象的对象集合划分为由相似的对象所组成的多个 类。根据最大化相同聚类内部数据对象之间的相似程度，同时最小化不同聚 类中的数据对象之间的相似程度这项原则，可以令存在于不同聚类中的数据 对象差异较大，而存在于同一聚类中的数据对象差异较小。此外，聚类还可 以作为分类的预处理步骤以产生类标信息。经过多年研究，聚类分析技术已 广泛应用于生产或生活等诸多领域。在生物学领域，为了获取对不同种群结 构的认识，可以首先对植物和动物聚类，进而对聚类群体的基因信息分类， 最终获得不同种群结构的认识。在商业领域，通过聚类技术对客户的消费信 息进行分析，可以了解客户的消费模式，进而得到不同消费群体的偏好。聚 类可用于对互联网上的不同网页信息进行分组，在天体观测中根据天体信息 对相似的天体进行分组，还可以根据住房的各项信息将城市中的不同类型的 房屋进行分组，提供给不同阶层的购房者。 近年来，随着软、硬件技术以及w e b 技术的发展，数据采集技术变得越 来越智能化、自动化，通常在短时间内就可以产生大量需要处理的数据。这 些数据不再是静态、固定地存储于可多次、随机访问的介质中，而是以数据 流的形式出现。数据流是具有实时性、连续性、顺序性的动态流式数据，传 统的聚类分析技术无法直接应用于数据流，造成这一现象的原因主要在于： ( 1 ) 数据流中的数据是海量的，所以不可能在内存及硬盘上存储整个流数据 集。甚至问题不仅是在于有太多的数据，而在于需要记录的属性值的定义域 都相当大；同样，因为数据流巨大的数据量，传统的多遍扫描数据的挖掘方 哈尔滨t 程大学博十学位论文 法是不切实际的，对数据流的挖掘应该是一个单遍扫描的过程。( 2 ) 数据流 是快速变化的，所以不可能看到数据流中的每一个数据点，只能通过对部分 数据点进行分析来做出决策。此外，通常数据流是不断到来的，需要聚类算 法具有增量处理数据的能力。( 3 ) 数据流是时序的，所以对数据流中的数据 元素的访问一般是单次线性的，即数据元素只能按照其流入顺序依次读取一 次，随机访问是不现实的；多数应用要求快速响应且挖掘应该是一个连续的、 在线的过程，而不是间歇性地进行。 随着信息技术的发展，所获取到的数据流的特征也越来越丰富，即数据 流的维数越来越高，对高维数据流聚类的研究逐渐变得重要而富有意义。在 高维数据空间中，数据点之间的距离趋近于相等。随着维度的增长，对于满 足一定要求的数据分布，数据对象之间的最近和最远距离相对差异将趋近于 0 t 6 3 1 。高维数据流聚类是一个非常困难的问题，其原因是：( 1 ) 随着维度增 加，聚类算法的效率下降很快。( 2 ) 高维空间的最近邻特性和稀疏性使得在 高维空间中存在数据类的可能性变得微乎其微，因为在高维数据空间中任何 地方数据点的密度都很低，此外，许多维或者维的组合还可能存在着一些均 匀分布的噪声点。 对于高维数据流，并非所有的维度都与聚类相关，在不同的子空间中可 能存在不同的数据类，且这些数据类对应的子空间也可能不同。子空间聚类 算法按照其搜索方法的不同区分为两类，即自顶向下的方法以及自底向上的 方法。显而易见，一种朴素的方法就是搜索所有可能存在的子空间，而后通 过聚类校验方法来确定包含最佳聚类的子空间。但是，这种朴素方法是不现 实的，因为子空间子集的产生问题是难以控制的，需要更加复杂的启发式子 空间搜索方法，但搜索方法的选择会对算法的其它方面的特性有一定的影响。 鉴于这种情况，对数据流子空间聚类进行研究具有重要的意义。 近年来，数据采集技术的飞速发展以及聚类技术应用日益广泛使得待解 决的问题日趋复杂化，数据流聚类也面临着越来越大的挑战。这也促使着研 究者们不断去寻求和探索新的方法，以使得数据流聚类更加完善，更加符合 实际需求。 针对上述数据流聚类领域中存在的挑战，研究人员从各个不同角度引入 新的方法加以解决。通过对传统聚类算法进行改进或是提出新的聚类算法以 2 第1 章绪论 满足数据流的增量聚类要求；在保证不损失或损失少量精度的情况下，对高 维数据流进行维度约简以提高聚类效率；根据不同需求，对数据流在不同子 空间中聚类，从不同角度得到数据流的聚类信息。 开展数据流聚类技术的研究对于数据挖掘、粗糙集理论、聚类技术的发 展均具有重要的意义。虽然数据流聚类在近几年得到了快速的发展，但仍然 存在着聚类精度、聚类代价、聚类结果更新等方面的问题需要加以解决，在 此背景下，本文将进行如下方面的研究：针对传统网格聚类算法中网格划分 方法的不足，引入新的数据空间划分策略，并在此基础上设计增量聚类算法。 针对数据流对算法实时性的高要求以及数据流聚类中非球形聚类效果不好的 情况，设计可保证对于不同形状聚类效果的数据流聚类方法。针对高维数据 中的冗余维度以及“维灾”现象，在保证聚类精度前提下，开展可根据数据 流变化情况进行动态维度调整的数据流聚类方法的研究，以节省聚类时间， 减少计算量。进一步对数据流的子空间聚类算法进行研究。以发现存在于不 同子空间中的聚类，从不同层面发现聚类。 1 2 国内外研究现状 1 2 1 基于网格的聚类方法 数据挖掘中的聚类分析在各个方面针对不同的情况有不同的要求，主要 体现在几个方面【l 】： ( 1 ) 可伸缩性：目前，一些传统的聚类算法可以很好地处理规模不大的 数据集，然而，这是不够的，对一个包含百万或百万以上级的大数据集进行 聚类，则往往会产生比较大偏差。所以，聚类算法应该具有可伸缩性。 ( 2 ) 不同类型属性的处理能力：现有的多数聚类算法通常可以很好地处 理数值类型的数据，但是在现实应用中往往存在着二元类型、序数型等一些 其他类型的数据或者是它们所组成的混合型数据。因此，需要聚类算法具有 处理不同类型属性的能力。 ( 3 ) 对聚类形状的适应性：传统的聚类算法是基于一些传统的距离度量 方式来确定聚类，如欧几里德距离。但通常聚类的形状是无法预知的，可能 是任意的，这对传统的距离度量方式提出了新的挑战，因此聚类算法应具有 3 哈尔滨t 程大学博十学何论文 对不同聚类形状的适应性。 ( 4 ) 弱化参数的决定性：现有的一些聚类算法对参数的依赖性很强，如 在k - m e a n s 聚类算法中需要用户预先给出聚类数目这个参数。在现实的应用 当中，预先提供参数是比较困难的，这也在某种程度上限制了此类算法的应 用。因此，聚类算法应该尽可能的弱化参数的作用。 ( 5 ) 算法的抗噪性：现有的聚类算法对噪声数据的处理能力不同，有些 算法对噪声数据十分敏感，直接导致了在存在噪声数据情况下聚类质量低下。 因此，聚类算法应具有一定的抗噪性。 ( 6 ) 数据输入的无序性：传统的一些聚类算法，如k m e a l l s ，随着数据 的输入顺序不同，产生的聚类结果也不同，使得聚类结果对数据的输入顺序 产生了一定的依赖性，这种情况是聚类算法应该避免的。 ( 7 ) 处理高维数据：随着信息采集技术的发展，所获取的数据特征越多， 即所需处理的数据的维度也越高，而一些传统的聚类算法在高维空间中对数 据的处理能力较差，应加以改进。 ( 8 ) 基于约束的聚类：在某些情况下，需要在某些限制性条件下进行聚 类。因此，聚类算法应一方面满足这些限制条件的约束，另一方面保证聚类 的质量。 ( 9 ) 可解释性和可用性：聚类结果应具有良好的可解释性和可用性，即 聚类需要和特定的语义解释和应用相联系。 通常情况下，传统的基于内存的聚类算法中一般采用的是数据矩阵和相 异度矩阵两种数据结构： 第一种可以看成是以p 形式的关系表，称之为数据矩阵( d a t a m a t r i x ) ， 其中刀为数据对象的个数，p 为属性的个数。 五_ ， ： 嘞 ： 工哪 第二种可以看成是咒，z 维的矩阵形式，称之为相异度矩阵( d i s s i m i l a r i t y 4 ， p 妒 加；砌；知 ；h ；确 第1 章绪论 m a t r i x ) ，用来存储刀个数据对象两两之间的近似性。 o d ( 2 ，1 ) 0 d ( 3 ，1 ) d ( 3 ，2 ) 0 ；i； d ( n ，1 ) d ( n ，2 ) 0 其中，d ( i ，j ) 表示的是数据对象f 与数据对象之间的相异度。数据对象 之间越相似，其值越趋近于o 。相异度将被用来进行数据对象的聚类计算。 针对数据对象的不同属性，如区间标度属性，二元属性，标称型、序数型及 比例标度型属性，混合型属性，分别采取不同的相异度计算方法，具体方法 参见文献 1 。 目前，主要有如下几种聚类算法，这里主要对基于网格的聚类算法进行 介绍。 ( 1 ) 基于划分的聚类算法 基于划分的聚类算法通常需要预先指定聚类数目或聚类中心点，而后通 过反复地进行迭代运算，逐步降低目标函数的误差值，当目标函数收敛时， 得到最终的聚类结果。比较有代表性的基于划分的聚类算法有k - m e a n s 算法、 缸中心点算法、c l a r a n s 算法等。 ( 2 ) 基于层次的聚类算法 基于层次的聚类算法的操作过程不可回退，一个分裂或合并操作执行后， 无法恢复为原来的状态。此类算法按照其层次结构的形成过程分为两种，第 一种是白底向上的凝聚型层次聚类算法，另一种是自顶向下的分裂型层次聚 类算法。 ( 3 ) 基于密度的聚类算法 基于密度的聚类算法可以发现任意形状的聚类，此类算法将聚类看作是 数据空间中被低密度区域分割开的高密度数据对象区域。具有代表性的基于 密度的聚类算法有d b s c a n 、o p t i c s 、d e n c l u e 等。 ( 4 ) 基于模型的聚类算法 现有的基于模型的聚类方法主要有统计学方法和神经网络方法两种，此 哈尔滨丁程大学博十学位论文 类聚类算法一般基于某种概率分布的假设。有代表性的有c o b w e b 和神经 网络方法。 ( 5 ) 基于网格的聚类算法 基于网格的聚类方法处理时间很短，此类方法将数据空间划分为一定数 目的单元，单元的大小可以是相同的，也可以是不同的，由这些单元组成网 格结构，存储数据的统计信息。基于网格的聚类方法的处理对象是网格单元， 而不是数据对象本身，其处理时间仅与网格单元的数目有关，而与数据对象 的数目无关。s t i n g 、w a v e c l u s t e r 和c l i q u e 是具有代表性的基于网格的聚 类算法。 s t i n g 【2 】将数据空间分层次地划分为方形单元，聚类时充分利用存储于 这些方形单元中的统计信息。其中分布在不同层次的方形单元对应不同层次 的分辨率。与其它聚类方法相比，s t i n g 具有如下优点：( 1 ) 基于网格计算， 由于描述网格单元数据统计信息是存储在相应网格单元中，因此它与查询要 求无关；( 2 ) 网格结构有助于实现并行运算和增量更新；( 3 ) s t i n g 方法处 理速度快，其通过对数据库的一次扫描得到各个方形单元中存储的统计信息， 其聚类时间复杂度为d ( 盯) ，其中n 为数据对象的数目。在产生聚类后进行查 询的实际复杂度为d ( g ) ；其中g 为在最底层的所有网格数，通常比刀要小许 多。s t i n g 方法存在一些缺点：由于s t i n g 方法是利用多分辨率来进行聚 类的，如果最底层网格单元的划分粒度太细，会得到较高的聚类精度，但处 理开销会增加，导致聚类时间会较长；反之，如果底层网格单元的划分粒度 太粗，则会减少聚类时间，但粗粒度会降低聚类精度。除此之外，s t i n g 方 法并没有充分考虑不同层次之间相邻网格单元之间的相互关系，其聚类边界 往往是水平或垂直的。 w a v e c l u s t e 一3 】是一种基于小波转换方法处理数据对象的多分辨率聚类算 法，数据空间中的多维网格结构用于存储统计信息，在此基础上，利用小波 变换将原始特征空间映射到新的空间中，进而在新空间中发现聚类。 w a v e c l u s t e r 主要具有如下优点：( 1 ) 它采用无监督聚类。通过区分数据空间 中的密集区域与非密集区域，对信息进行取舍。在特征空间中，自然形成聚 类，密集区域吸引邻近数据点，非密集区域对数据点起抑制作用。( 2 ) 孤立 点通过小波变换可以被自动过滤掉。( 3 ) 多分辨率特性使得通过小波变换可 6 第1 章绪论 以根据不同的精度要求实现聚类。( 4 ) 基于小波变换的聚类方法速度很快， 算法的计算复杂度是d ( 一) ，其中数据对象的数目为以。易于实现并行化。 c l i q u e t 4 】算法融合了基于网格、基于密度两种思想，可以有效地处理高 维数据。通常数据空间中的多维数据点分布式不均匀的，c l i q u e 算法可以 发现其中最高维空间中所存在的聚类。c l i q u e 算法具有如下优点：c l i q u e 无需预先假定数据的分布特征，因此其聚类结果不受数据对象的输入顺序影 响。c l i q u e 具有良好的维度伸缩性。然而，c l i q u e 算法的简化，在一定 程度上会降低聚类精度。 经过研究，学者们又提出了一些新的基于网格划分，具有诸多优秀特性 的聚类算法。其中有代表性的有o p t i g r i d ，c l t r e e ，g c h l ，g d i l c ，s g c 垒奎【5 】 寸o o p t i g r i d 6 1 算法可以有效地聚类海量高维数据。o p t i c , r i d 在构建数据的最 优网格划分的基础上进行聚类，算法通过数据投影，计算各维的最优划分超 平面，进而确定最优的网格划分。o p t i g r i d 算法递归地执行，每一步将数据 集划分为一定数量的子集。而后对至少包含一个类的子集递归地进行处理。 算法通过使用一个由至少g 个切平面组成的多维网格来确定划分。 c l t r e e 7 】通过构造决策树来区分子空间中的密集部分与稀疏单元。决策 树是数据分类中普遍使用的方法，它根据某个纯度函数将数据空间划分成不 同类别数据的区域。由于聚类的无监督特性，无法事先确定类别标记，因而 无法直接使用该方法。 g d i l c s 】是z h a o 等人于2 0 0 1 年提出的基于网格密度等值线的聚类算法。 密度等值线图可以很好地描述数据样本的分布。算法的核心思想是用密度等 值线描述数据样本的分布。通过使用网格方法，计算每一个数据样本的密度， 发现相对的密集区域。g d i l c 是一种无监督算法，能够消除奇异值以及发现 各种形状的类，具有聚类准确度高和聚类速度快等特点。 s g c 9 是m a 等人于2 0 0 4 年提出的一种新的基于移位网格概念的基于密 度和网格的聚类算法。它不需要用户输入参数，是一种非参数类型的算法， 它将数据空间的每一维分成某些间隔以形成一个数据空间的网格结构。基于 滑动窗口概念，为获得一个被更多描述的密度剖面引入了整个网格结构的移 位概念，因此能够提高聚类结果的准确度。与传统算法相比，因为类数据是 哈尔滨t 程大学博十学位论文 基于网格单元的，算法效率较高。s g c 的计算时间与数据样本数无关，具有 极好地处理任意形状聚类的能力，且不需要用户输入参数，在处理大型数据 集时很少遇到内存不足的情况。 g c h l 1 0 】是p i l e v a 等人于2 0 0 5 年提出的一种用于大型、高维空间数据库 的网格聚类算法。g c h l 将并行轴划分策略与一种新的基于密度和网格的聚 类算法相结合，进而确定输入数据空间的高密度区域，即聚类。该算法可以 很好地工作在任意数据集的特征空间中，只对数据进行一次扫描，将大型数 据集划分为子部分，通过使用有限内存缓冲区对子部分逐个进行处理；g c h l 能够发现任意形状的类。此外，还可以发现奇异值，对噪声数据也不敏感。 g c h l 适合处理大型、高维数据集聚类的情况，通过将数据空间量化为一定 数目的网格单元进而形成网格结构，使得聚类操作在网格结构上进行，聚类 时间独立于数据对象数目和数据次序，聚类速度快。 1 2 2 增量聚类算法 随着信息技术的发展，在许多新的应用领域出现了新的数据类型和数据 形态，这些新型数据对传统聚类算法提出了诸多挑战，如一次线性扫描、在 线处理、增量式处理、设计新的距离函数、处理动态变化的数据等。多数传 统的聚类算法并不具备增量式地处理数据的能力，只有少数几个可以增量式 地处理数据，如b i r c h 、c u r e 、c o b w e b 等。 b i r c h 1 1 1 是一个可以增量处理数据的基于层次的聚类方法。它将数据集 划分为一系列子类的集合来减小聚类规模。引入了聚类特征( c f ) 以及聚类 特征树( c f 树) 两个概念，聚类特征项是用来保存聚类信息的三元组，聚类 特征树是一个包含两个参数的高度平衡的树结构。b i r c h 是增量的，不需要 扫描所有数据点或是已经存在的类就可以聚类，且b i r c h 只需对数据集进行 一次扫描。实验结果显示该算法具有较好的聚类质量，对数据对象数目具有 线性伸缩性。然而，在c f 树中，并非每个节点的存储容量