（计算机系统结构专业论文）基于网格的mst数据流聚类算法研究.pdf

哈尔滨t 稃人学硕十学位论文 摘要 聚类分析是数据挖掘领域中一个非常重要的研究方向。近年来，随着信 息技术的高速发展出现了一种应用同益广泛的动态流数据一数据流。数据流 不同于传统的存储在磁盘上的静态数据，它是高速的、连续的、动态的、快 速变化的、海量的数据集合，由此对它的访问只能是顺序的、一次或有限次 的。数据流的这些特性既给数据流的挖掘带来了极大的困难，也给数据流的 聚类算法提出了更高的要求。在当前的数据挖掘领域中，数据流已经成为一 个研究热点，同时数据流聚类分析也成为聚类研究的一个重要方向。 本文首先介绍了数据流挖掘的相关理论与技术，结合流数据与传统的静 态数据的不同分析了数据流的特点。同时对传统聚类算法与数据流聚类算法 进行了研究和对比，分析了算法的优势与不足，阐述了数据流聚类算法的特 点及其与传统聚类算法的不同。然后介绍了用于聚类算法的网格划分方法及 其在聚类分析中的作用，并对基于网格的聚类算法进行了研究与分析。在此 基础上给出了一种新的数据流聚类算法g t s c l u 算法，该算法是基于网格 的最小生成树( m s t ) 数据流聚类算法，算法分为在线处理与离线聚类两部 分，并运用了网格与最小生成树技术。在线部分通过均匀网格划分数据空间 以获取数据流的信息，离线部分将网格空问拆分为不均匀的网格结构，并利 用最小生成树技术对在线获得的信息进行聚类。g t s c l u 算法可以有效排除 噪声数据发现任意形状的聚类，有效提高了聚类效率和质量。 实验结果表明，g t s c i u 算法能够发现任意形状的聚类，对数据的输入 顺序不敏感，而且网格拆分技术的采用使其能够有效分离出噪声数据具有很 高的聚类精度和处理效率，适合处理大规模的数据流。 关键词：聚类分析；数据流；网格；最小生成树 哈尔滨一f ：稃人学硕十学位论文 a b s t r a c t c l u s t e r i n ga n a l y s i si sa ni m p o r t a n tr e s e a r c ht o p i ci nt h ef i e l do fd a t am i n i n g w i t hf a s td 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 yt h e s ey e a r s ，t h e r ee x i s t sm o r e w i d e l yu s e dd y n a m i cf l o wd a t a d a t as t r e a m b e i n gd i f f e r e n tf r o mt r a d i t i o n a l s t a t i cd a t as t o r e di nd i s c ，d a t as t r e a mi sah i f g hs p e e da n dm a s s i v es e tw h i c hi s c o n t i n u o u s ，d y n a m i ca n df a s tc h a n g i n gt h u st h ev i s i tt oi tc a no n l yb eo r d i n a l ，o n e t i m eo rs e v e r a ll i m i t e dt i m e s t h e s ec h a r a c t e r i s t i c so fd a t as t r e a mb r i n gg r e a t d i f f i c u l t yt od a t am i n i n ga n dm u c hh i g h e rr e q u i r e m e n t so fc l u s t e r i n ga l g o r i t h mf o r d a t as t r e a m i nt h ef i e l do fd a t am i n i n g , d a t as t r e a mh a sb e e nar e s e a r c hf o c u s r e c e n t l y ；m e a n w h i l e ，d a t as t r e a mc l u s t e r i n ga n a l y s i sh a sb e c o m ea ni m p o r t a n t t o p i ci nc l u s t e r i n gr e s e a r c h t h i st h e s i sf i r s ti n t r o d u c e st h et h e o r i e sa n dt e c h n i q u e so fd a t as t r e a mm i n i n g , a n dg i v e sa i la n a l y s i so fc h a r a c t e r i s t i c so fd a t as t r e a mo nt h ec o m b i n a t i o no f s t r e a m i n gd a t aa n dt r a d i t i o n a ld a t a m o r e o v e r , c o m p a r i s o na n dr e s e a r c ha r em a d e b e t w e e ne x i s t i n gt r a d i t i o n a l c l u s t e r i n ga l g o r i t h m a n dd a t as t r e a mc l u s t e r i n g a l g o r i t h ma n dg e ta d v a n t a g ea n dd e f i c i e n c yb e t w e e nt h e m t h e ni tp r e s e n t st h e 鲥dd i v i d i n gm e t h o du s e di nc l u s t e r i n ga l g o r i t h ma n d i t se f f e c ti nc l u s t e r i n g a n z l y s i s a sw e l la st h er e s e a r c ha n da n a l y s i so f 鲥d - b a s e dc l u s t e r i n ga l g o r i t h m o nt h i sb a s i s ，an e wk i n do fc l u s t e r i n ga l g o r i t h mf o rd a t as t r e a m - - g t s c l g a l g o r i t h mi sp r o p o s e d i ti st h em i n i m u ms p a n n i n gt r e e d a t as t r e a mc h l s t e r i n g a l g o r i t h mb a s e do ng r i d ，w h i c hi s d i v i d e di n t oo n l i n ep r o c e s s i n ga n do f f l i n e c l u s t e r i n g ，c o m b i n i n gw i t hg r i d a n dm i n i m u ms p a n n i n gt r e et e c h n i q u e s t h e o n l i n ep a r ta c q u i r e sd a t as t r e a mi n f o r m a t i o nb ym e a n so fe v e ng r i dd i v i d i n gd a t a s p a c ew h i l eo f f i i n ep 5 nc a r r i e so u tc l u s t e r i n ga n a l y s i so nt h ei n f o r ：r a t i o no b t a i n e d o n l i n et h r o u g hd i v i d i n gt h eg r i ds p a c ei n t ou n e v e ng r i da n dt h em i n i m u m s p a n n i n gt r e et e c h n i q u e t h u s ，g t s c i ua l g o r i t h mc a nn o to n l yf i n dc l u s t e r sw i t h a r b i t r a r ys h a p ea n da m o u n t 。b u t a l s od e a lw i t hn o i s ed a t ae f f e c t i v e l y ，t h e 哈尔滨t 程大学硕十学位论文 e f f i c i e n c ya n dq u a l i t yo fc l u s t e r i n gi si m p r o v e d t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tg t s c i ua l g o r i t h mi s c a p a b l e o f d i s c o v e r i n ga r b i t r a r ys h a p eo fc l u s t e ra n di si n s e n s i t i v et ot h es e q u e n c eo fd a t a f u r t h e r m o r e ，t h ea p p l i c a t i o no fg r i dd i v i d i n gt e c h n i q u ec a nm a k et h ea l g o r i t h m h a v eh i 【g he f f i c i e n c ya n da c c u r a c yo fc l u s t e r i n g ，a n di tc a nd i s t i n g u i s hn o i s ed a t a e f f e c t i v e l y t h ea l g o r i t h mi ss u i t e dt ol a r g e s c a l ed a t as t r e a mp r o c e s s i n g k e y w o r d s ：c l u s t e r i n ga n a l y s i s ；d a t as t r e a m ；g r i d ；m i n i m u ms p a n n i n gt r e e 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。， 作者( 签字) ：王移黻马 日期： 知叼年罗月日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后口解 密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 i， 作者( 签- - 7 - - ) ：壬霉f 鸺导师( 签字) f 勺榔 r 期：伽1 年7 月i c f l 2 ( 年7 月u r i , t 7 、vi 哈尔滨下程人学硕十学位论文 1 1 引言 第1 章绪论 近年来，随着微传感器技术和计算机网络技术的广泛应用，在网络监控、 股票交易分析、气象与环境监测、传感器网络、w e b 应用等领域产生了一类 新的数据对象一数据流，它的出现受到了越来越多人的关注。人们遇到大量 的、源源不断的数据( 如传感器数据) ，这些数据不是静态不变的数据集合， 而是动态的、连续的、变化的、潜在无限的数据集合，它只能被按顺序访问， 且仅能被扫描一次或有限的几次，该类数据集合称为数据流“，。这些数据的共 同点就是数据规模巨大，且数据快速持续到达，数据通常只能被读取一次。 数据流与一般数据的区别在于它的到达是快速的、无界的、时变的和不可预 测的，从而不可能将原始数据流中的数据完全存储。数据流作为一种新兴且 日益主流的数据形式吸引了众多研究人员的注意，探究如何快速高效的从包 含大量数据的数据流中提取有价值信息的有效途径己成为众多应用领域的客 观需求，因而对数据流的分析和挖掘在近几年快速兴起且已发展成一个全新 的研究领域。数据流聚类作为数据流挖掘的关键技术之一，受到了越来越广 泛关注和研究。 聚类( c l u s t e r i n g ) 是数据挖掘中的重要组成部分，所谓聚类就是将数据对 象分组成为多个类或簇( c l u s t e r ) ，在同一个簇中的对象之间具有较高的相似 度，而不同簇中的对象差别较大。相似度是根据描述对象的属性来计算的。 距离是经常采用的度量方式。从机器学习的角度看，聚类属于无指导学习， 与分类不同，聚类的目标是在没有任何先验知识的前提下，根据数据的相似 性将数据聚合成不同的簇( 或类) ，使得相同簇中的元素尽可能相似，不同簇 中的元素差别尽可能大，因此又被称为非监督分类( u n s u p e r v i s e d c l a s s i f i c a t i o n ) 。聚类分析具有广泛的应用价值，如市场分割、模式识别、生 物学研究、空间数据分析、w e b 文档分类。除此之外，聚类分析还可以作为 哈尔滨。门挈大学硕十学位论文 i i 独立的数据挖掘工具，用于分析数据发布或作为其它数据挖掘算法的预处理 步骤。聚类受到越来越关注的原因主要包括： ( 1 ) 在很多实际应用中，由于缺少形成模式类过程的知识，或者由于实 际工作中的困难，收集并标识大型样本集是很费时费力的工作，所以实践中 往往只能用没有类别标签的样本集进行工作。另一方面，存在很多应用，待 分类模式的性质会随着时间发生缓慢的变化。如果这种性质的变化能在无监 督的情况下捕捉到，分类器的性能就会大幅度提升。 ( 2 ) 在一个广义的数据挖掘过程中，聚类分析往往是被作为最初的步骤， 用于对数据分布和聚合特性的初步了解，以在此基础上进行其它数据挖掘操 作。 聚类分析也已经广泛地应用到诸多领域中，包括模式识别、数据分析、 图像处理以及市场研究。通过聚类，人们能够识别密集与稀疏的区域，从而 可以发现全局的分布模式以及数据属性之间有趣的相互关系。在商务上，聚 类能帮助市场分析人员从客户基本信息库中发现不同的客户群，并且用购买 模式来刻画不同的客户群的特征。例如：网络监控日志、电子商务记录、电 话通信记录、银行交易信息、传感器数据等等。在生物学上，聚类能用于推 导植物和动物的分类，对基因进行分类，获得对种群中固有结构的认识。 数据流的广泛应用吸引了众多学者对数据流聚类算法的深入研究。由于 数据流本身的特点使得传统的算法不能直接应用于数据流住，。因为数据量很大 而且是持续的，与数据流的规模相比内存或缓存等存储空间是极其有限的， 只能对数据进行一次顺序扫描，因此需要一种动态的增量式的聚类算法来处 理数据流。并且，数据流到来的速度很快，多数应用要求在数据到来的同时 进行分析决策，这对聚类算法的处理时间提出了更高的要求。 1 2 国内外研究现状 尽管聚类问题在数据库、数据挖掘和统计等领域得到了广泛研究，然而 数据流的分析仍给聚类算法提出了前所未有的挑战。由于完整的存储过去数 据的方法在数据流聚类中不可行，这就需要能够只使用新数据就能够追踪聚 类变化的算法，从而要求聚类算法必须是增量式的、对聚类表示要简洁、对 哈尔滨i ：稃人学硕十学何论文 新数据的处理要快速以及对噪音和异常数据要稳健，因为数据流可看成是随 时间不断变化的无限过程，其隐含的聚类可能随时间动念的变化并会导致聚 类质量的降低。 数据流聚类分析作为数据流挖掘的一个重要研究方向，在面临着巨大挑 战的同时也引起了国内外研究者们的广泛关注。目前出现了不少相关的研究 成果，以下是对国内外所从事的与数据流聚类相关研究工作的介绍。 国外在数据流挖掘方面有两个比较有影响的研究小组是s t a n f o r d 大学的 r m o t w a n i 教授领导的研究小组和u i u c 的c a g g a r w a l 和j h a n 教授领导的 研究小组。r m o t w a n i 教授研究组的研究重点在数据流管理、数据流的连续 查询和数据流的聚类等方面u ，提出了不同于传统d b m s 的d s m s ( d a t a s t r e a mm a n a g e m e n ts y s t e m ) 概念，他们的研究得到了美国国家自然科学基金 的资助。c a g g a r w a l 教授研究组的研究重点在数据流分析方面，对数据流进 行在线分析，从聚类、分类、频繁项集挖掘以及可视化等角度做了大量研究工 作阳，提出了倾斜时问窗口( t i l t e d t i m ew i n d o w ) 策略，采用不同时间粒度 保存数据流的信息，他们的研究得到了美国军方和国家自然科学基金的资助。 在数据流聚类方面，近年来有学者提出了应用于大规模数据集的一趟聚 类算法，如s q u e e z e r 算法睁川和b i r c h 算法，它们可以应用于某些数据流 问题。也有学者提出了针对流数据的聚类算法，典型的有s t r e a m 算法、 c l u s t r e a m 算法和h p s t r e a m 算法。2 0 0 0 年，s g u h a 等人提出了基于分而治 之思想的l o c a l s e a r c h 算法，对数据流聚类理论进行了探讨。2 0 0 2 年， 0 c a l l a g h a n 基于l o c a i s e a r c h 算法思想并结合实践的基础上提出了 s t r e a m 算法。s t r e a m 算法使用质心和权重( 类中数据个数) 表示聚类， 比传统数据的聚类算法有更好的性能，但它采用了批处理方式且每次处理的 数据点个数受内存大小的限制导致不能给出任意时刻数据流的聚类结果。 c a g g a r w a l ，j h a n 等人于2 0 0 3 年在文献 6 中提出了流数据聚类算法 c l u s t r e a m 。c l u s t r e a m 算法开创性地将聚类过程分为联机与脱机两部分，首 次提出把数据流看成一个随时间不断变化的过程而不是一个整体进行聚类分 析。该算法有很好的可扩展性，可产生高质量的聚类结果，尤其在数据流随 时间变化较大时比其它算法产生更高质量的聚类。2 0 0 4 年，c a g g a r w a l ，j h a n 等人又提出了h p s t r e a m 算法，它使用投影( p r o j e c t ) 的方法对高维数据流进 3 哈尔滨i ：程人学硕十学位论文 l|l 行处理，并利用衰减簇结构保存历史数据，使历史数据与当前数据得到了较 好的集成。 随着应用需求的不断提高，聚类算法对数据的处理效率以及聚类质量的 要求不断提高，网格技术在聚类算法中的应用越来越广泛。c u q u e 聚类算 法是网格聚类中的一个典型算法，它是由r a k e s ha g r a w a l 等人在1 9 9 8 年提 出的。该算法对数据的每个属性进行等分，将整个数据空间划分为网格结构， 根据每个单元中数据点的数量找出其中的稠密单元，然后对稠密单元进行连 接就可形成聚类。它可以处理大量的高维数据，并能自动地识别嵌入在数据 子空间中的类。此外，基于网格的聚类算法还有s t i n g 算法、w a v e c l u s t e r 算法及它们的一些改进算法等。 目前国内对数据流聚类算法的研究还处于初期阶段，在借鉴国外研究的 基础上进行了一些探索并获得了一定的成果。2 0 0 6 年，f e n gc a o 等人在文 献 1 2 中提出了针对动态进化数据流的d e n s t r e a m 算法。它相对c l u s t r e a m 算法有很大的改进，继承了i n c r e m e n t a ld b s c a n 基于密度的优点，能够支 持对有噪声的动态进化的数据流进行任意形状的聚类。同年，中山大学的朱 蔚恒等在文献 1 3 中提出的基于密度与空间的a c l u s t r e a m 聚类算法，该算 法通过引入有严格空间的意义聚类块，在对数据流进行初步聚类的同时尽量 保留数据的空间特性，有效克服了c l u s t r e a m 算法不能支持任意形状聚类的 缺陷。2 0 0 8 年，单世民等人提出了g d c a p 算法一，该算法是一种基于网格 和密度的簇边缘精度增强聚类算法，虽然它是一种面向静态数据的聚类算法， 但它对网格聚类方法进行改进咀提高聚类质量的思想值得在数据流聚类方法 中予以借鉴。该算法可以将网格化方法聚类处理之后的簇边缘聚类不准现象 的消除，在低时间复杂度的前提下提高了聚类质量，且其聚类结果优于 c u q u e 算法的。此外，复旦大学的周傲英等人在数据流分析方面取得一定 的成果n “”，哈工大的李建中等人在数据流历史数据的存储也聚集查询方面取 得了一些成果”。 尽管现在已经涌现了很多数据流聚类挖掘簟法，但是由于数据流的特点， 当前的算法都或多或少的存在着各种问题，比如：动态适应性低、不能处理 混合属性的数据，这也是很多传统聚类算法所存在的问题。 4 哈尔滨t 稃大学硕十学位论文 1 3 研究内容及论文结构 本文根据动态流数据与静态数据的差异分析了数据流聚类与传统数据聚 类的不同，进而分析了数据流聚类算法所应具备的特点。在对现有的传统聚 类算法与数据流聚类算法进行研究和分析的基础上，给出了基于网格的最小 生成树数据流聚类算法一g t s c l u 算法，该算法引入了c l u s t r e a m 算法包含联 机和脱机两部分的思想，分为在线处理和离线聚类两部分，并利用不均匀网 格和最小生成树技术，能够有效分离噪声数据发现任意形状的聚类，提高了 聚类效率和质量。 本文的内容结构如下： 第1 章对本文研究领域进行了简要介绍，阐述了国内外的研究现状，并 介绍了本文所研究的主要内容。 第2 章介绍了数据流聚类算法与传统聚类算法的不同以及聚类算法中的 网格划分方法，对现有的传统聚类算法与数据流聚类算法进行了分析，阐述 了现有的基于网格的聚类算法及其改进算法的优点和不足。 第3 章给出了基于网格的m s t 数据流聚类算法g t s c l u 算法，详细介 绍了网格和最小生成树技术的相关概念以及算法的实现过程。 第4 章实验应用仿真数据集和真实数据集对g t s c i u 算法的性能进行了 验证，并对实验结果进行了分析比较。 最后一部分是全文的总结，对本文的研究工作进行了总体的概括，并对 未来的研究工作进行了展望。 5 哈尔滨t 柙大学硕十学佗论文 第2 章聚类分析及网格划分方法 在数据挖掘中，聚类尤其是数据流聚类技术是一个同趋活跃并富有挑战 性的研究领域。数据流的特点使得传统的聚类方法往往只能在静态数据的处 理上发挥作用。由此，引起了人们对传统数据聚类方法的进一步研究改进和 探索，以求得到适合数据流特性的有效聚类算法。本章首先介绍了数据流与 数据流挖掘的相关概念，根据数据流与传统数据的不同分析了数据流的特点 与数据流聚类算法的特点。然后对现有的聚类算法和网格划分方法及几种基 于网格划分的聚类算法进行了阐述，分析了它们的优点与不足，并根据相关 算法的特点引出了本文工作的切入点。 2 1 数据流挖掘 近年来，随着计算机技术和网络通信技术的蓬勃发展以及众多应用领域 的需求，数据流处理问题，特别是基于数据流的挖掘问题已被越来越多的研究 人员所关注。数据流挖掘就是在数据流上发现、提取隐含在其中且事先未知 而又潜在有用的信息和知识的过程。 2 2 1 数据流的概念 在应用中人们遇到大量的、源源不断的数据( 如传感器数据) ，这些数据 不是静态不变的数据集合，而是动态的、连续的、有序的、无限的数据集合， 它只能被按顺序访问，且仅能被扫描一次或有限的几次，这种数据集合称为 数据流n ”。数据流与一般的数据的区别在于它的到达是快速的、无界的、时 变的和不可预测的，从而不可能将原始数据流中的数据完全存储。 数据流的形式化定义为：数据流是由一系列按照时间顺序连续到达的数 据对象局五构成的数据集，其中每个数据对象置是一个包括d 维的多维 数据记录，用d 维向量的形式来表示：x i = ，x ：，氍，砌) ，其中 6 哈尔滨i ：程大学硕十学何论文 表示第f 个数据对象的第j 维的值，1 = 1 ，2 ，d 。 总体上，数据流与传统数据的区别主要在以下几方面： ( 1 ) 数据流中的数据是随着时间变化流入的，而传统数据库中的数据是 静态地存储在磁盘或其它存储介质中。 ( 2 ) 数据流中的数据是按时间顺序流过的，对数据只能依次进行顺序地 访问，且对数据的访问只能是一次或有限次，而磁盘或其它存储介质中的数 据可以随机访问、多次访问。 ( 3 ) 数据流中的数据是潜在无限的，而数据库中的数据是有限的。 ( 4 ) 由于在有限的存储空间内无法存储无限数据流的全部数据，因此数 据流中大部分的数据在处理后被丢弃了，对数据流的挖掘多数只能得到近似 结果，而传统数据库上的挖掘则可以得到精确的挖掘结果。 ( 5 ) 系统只能保存数据流全部数据的一个有限子集或概要数据，并随着 数据流上新数据的到来进行更新，这种更新的频度取决于数据流中数据到来 的速度。一般来说，数据流的更新频率要远远高于传统数据库中数据更新的 频率。 数据流的应用领域越来越广泛，在网络监控、入侵检测、情报分析、金 融服务、股票交易、电子商务、电信、卫星遥感( 气象、环境资源监控等) 、 w e b 页面访问和科学研究等众多领域中，数据以流的形式出现。由于数据流 的特殊性，短时间内有大量数据连续到达，这些数据具有随时问动态变化的 趋势，且往往又是高维的，如何对这些流数据使用有限存储空间进行快速处 理以获取有用信息，为数据挖掘及其应用研究带来了新的机遇和挑战，也具 有非常重要的意义。 2 2 2 数据流挖掘的特点 数据流中蕴含了大量的有用信息，因此从数据流中挖掘出未知的、有价 值的模式或规律将对网络安全、企业决策等产生重大影响。数据流自身的特 点决定了已有的数据挖掘模型不适合处理数据流，传统挖掘算法存在很多问 题，种种局限促使挖掘数据流只能用数据流挖掘模型。 数据流的特点决定了对数据流的处理必须遵循以下原则“飞 7 哈尔滨j r 程人学硕+ 学位论文 ( 1 ) 分析数据流时，每个数据项最多被检查一次。 ( 2 ) 尽管数据流的新数据项在连续不断地产生，但用来分析数据的内存 容量必须限定。 ( 3 ) 新产生的数据项必须尽快地处理，以得到数据流的最新分析结果。 2 2 3 数据流挖掘算法的特点 由于数据流的特点和传统数据挖掘算法存在的问题，将传统数据挖掘算 法直接用在数据流挖掘上是不可行的。数据流挖掘算法主要有以下特点( z o - 2 l 】 ( 1 ) 数据流中的数据是海量的，所以不可能在内存及硬盘上存储整个流 数据集。甚至问题不在于有太多的数据，而在于需要记录的属性值的定义域 都相当大。 ( 2 ) 同样因为数据量巨大，传统的多遍扫描数据的挖掘方法是不切实际 的，所以对数据流的挖掘应该是一个单遍扫描的过程。 ( 3 ) 数据流是快速变化的，所以无法看到数据流中的每一个数据元素， 人们只能通过分析部分数据元素来做出决策。 ( 4 ) 数据流是时序的，所以对流中数据元素的访问只能是单次线性的， 即数据元素只能按其流入顺序依次读取一次，随机访问是不现实的。 ( 5 ) 大多数应用要求很快的响应时间，并且挖掘应该是一个连续、在线 的过程，而不是偶然进行一次。 2 2 聚类分析 聚类分析是数据挖掘中一种非常重要的技术和方法，是数据挖掘的主要 任务之一。聚类是把一组个体按照相似性划分成若干个类别，且不同类中的 数据相异。聚类分析就是使用聚类算法来发现有意义的类，主要依据是把相 似的样本划分为_ 类，而把差异大的样本区分丌来，这样所生成的簇是组 数据对象的集合，这些对象与同一簇中的对象彼此相似，而与其它簇中的对 象彼此相异。聚类分析可以建立宏观的概念，发现数据的分布模式以及可能 的数据属性之i s j 的相互关系。聚类的数学描述如下： 8 哈尔滨+ 厂程大学硕十学位论文 设样本集为e ，类c 定义为e 的一个非空子集，即c c e 且c f ，则聚 类就是满足下列两个条件的类g ，c 2 ，g 的集合： ( 1 ) g uc 2 u u q 钮； ( 2 ) c f nc 叩( 对任意狰生f ) 。 定义2 1 ( 簇) 簇是一个数据对象的集合，在同一簇中对象具有相似性， 不同簇中对象之间是相异的。 定义2 2 ( 聚类分析( c l u s t e r i n ga n a l y s i s ) ) 聚类分析是把一个给定的数 据集合分成不同簇的的过程。聚类的目标是将数据聚集成类，使得类间的相 似性最小，而类内的相似性尽可能大。 2 2 1 聚类算法的性能评价 聚类分析源于统计学、机器学习、数据挖掘等多个研究领域，并广泛应 用于模式识别、图像处理、信息检索、生物学、医学、考古学、地质学、地 理学、市场学等多个学科。它既可以作为一个独立的算法分析数据中存在的 结构，也可被用作其它算法的预处理步骤。聚类的潜在应用对聚类分析提出 了各种不同的要求恤，。一般可从以下方面评价聚类算法的性能： ( 1 ) 可伸缩性。这里的可伸缩性是指算法要能够处理大数据量的数据库 对象，比如处理上百万条记录的数据库。这就要求算法的时间复杂度不能太 高，否则在大数据集合样本上进行聚类可能导致低效和较大偏差。 ( 2 ) 处理不同类型属性的能力。许多聚类方法只能对数值型的数据进行 聚类，但现实中的数据对象已远远超出关系型数据的范畴，比如空间数据、 多媒体数据、遗传学数据、时间序列数据、文本数据、i n t e m e t 的数据以及数 据流，这些数据对象的属性类型往往是由多种数据类型综合而成的。 ( 3 ) 用于决定输入参数的领域知识最少。许多聚类方法在聚类分析中要 求用户输入一定的参数，例如希望产生类的数目，而且聚类结果对于输入参 数十分敏感。参数通常很难确定，特别是对于包含高维对象的数据集来说， 更是如此。 ( 4 ) 发现任意形状的聚类。许多聚类方法基于欧氏距离来决定聚类，基 于这样的距离度量的算法趋向于发现球状簇，但一个簇很可能是任意形状的， 9 哈尔滨i ：程大学硕十学何论文 所以提出能发现任意形状簇的算法是很重要的。 ( 5 ) 对于输入数据的顺序不敏感。有些聚类方法对于输入数据的顺序是 敏感的。例如，同一个数据集合，当以不同的顺序提交给同一个方法时，可 能生成差别很大的聚类结果。 ( 6 ) 处理噪声数据的能力。绝大多数的现实世界中的数据库都包含了孤 立点、未知数据或错误的数据。有些聚类方法对于这样的数据较为敏感，可 能导致低质量的聚类结果。 ( 7 ) 高维性。一个数据库或数据仓库可能包含若干维或属性。许多聚类 方法擅长处理低维的数据，可能只涉及两到三维。在高维空间中对数据聚类 是非常有挑战性的，特别是在数据分布非常稀疏时。同时高维数还给聚类分 析带来两个问题：首先，不相关的属性削弱了数据汇聚的趋势；其次，高维 可能使得在低维中很有效的区分数据的标准在高维空间中失效。 ( 8 ) 基于约束的聚类。现实世界中的应用可能需要在各种约束条件下进 行聚类。要找到既满足特定的约束又具有良好聚类特性的数据分组是一项具 有挑战性的任务。 ( 9 ) 可解释性和可用性。用户希望聚类结果是可解释的、可理解的、可 用的。也就是说，聚类可能需要和特定的语义解释和应用相联系。 2 2 2 聚类分析的步骤 一个聚类算法应包括以下几个关键步骤：数据预处理、相似度定义以及 将数据分组和输出。 数据预处理包括将数据标准化、特征选择、特征提取、去除噪音等，数 据预处理并不是必要的，但是通常它能有效提高聚类结果的质量。在有些算 法中，特征选择可能与将数据分组交替进行。数据相似度定义决定了数据对 象之间的相似度计算方法。数据分绢是聚类算法的核心部分，将数据分组的 策略可以分为以下几类： ( 1 ) 以优化某个目标函数为目标产生对数据的分组。 ( 2 ) 按照簇的定义将数据分组。 ( 3 ) 基于数据对象或簇之间的相似度，建立一个层次分组。 1 0 哈尔滨一吲掣人学硕十学位论文 聚类算法的输出就是输出分组所得到的簇。簇可以由一个或多个代表点表示， 也可以由簇内所有数据表示。 2 3 传统聚类算法 目前存在的传统聚类算法可以分为划分聚类方法、层次聚类方法、基于 密度的聚类方法、基于网格的聚类方法和基于模型的聚类方法。算法的选择 取决于数据的类型、聚类的目的和应用。 1 划分的方法( p a r t i t i o n i n gm e t h o d ) 给定一个厅个对象或元组的数据库，一个划分方法构建数据的k 个划分， 每个划分表示一个簇，并且七行。也就是说，它将数据划分为k 个组，同时 满足如下的要求：( i ) 每个组至少包含一个对象；( i i ) 每个对象必须属于且 只属于一个组。其中在某些模糊划分技术中，第二个要求可以放宽。 给定要构建的划分的数目k ，划分方法首先创建一个初始划分。然后采 用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。一个好 的划分的一般准则是：在同一个类中的对象之间尽可能“接近”或相关，而不 同类中的对象之间尽可能“远离”或不同。根据这一原则，在实际的算法中 基于欧几旱德距离的聚类方法经常采用“平方距离和”，即s s q ( s u mo fs q u a r e d i s t a n c e ) 作为定量评估聚类结果质量的一个依据。设对于一个数据对象集 合进行聚类的结果是得到k 个簇g ，则这k 个簇的s s q 的数学定义如下： 七 2 s s q = | p m ， ( 2 - 1 ) l - l p 6 q 其中p 是集合中的数据对象，m ，是c f 的平均值( 或中心点) 。 为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分。实际 上，绝大多数应用采用了以下两个比较流行的启发式方法：( i ) k m e a n s ( k 一 平均算法) i z 4 l 这是由m a c q u e e n 在1 9 6 7 年提出的最早的累类算法，在该算 法中，每个簇用该簇中对象的平均值来表示。( i i ) k - m e d o i d s ( k 一中心点算 法) 懈，在该算法中，每个簇用接近聚类中心的一个对象来表示。 k m e a n s 算法是解决聚类问题的一种经典方法。它的主要优点是算法简 1 1 哈尔滨f ：稃大学硕十学何论文 单、快速。然而这种方法对不同的k 值可能会导致不同的聚类结果。其次， 该方法不能发现非凸面的簇，或大小差别很大的簇。而且对“噪声”和孤立 点很敏感，因为少量的该类数据能对平均值产生极大的影响。k - m e d o i d s 算 法可以看作是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 算法的执行代价比k - m e a n s 算法高。此外这两种 方法都要求用户指定结果簇的数目k 。 2 层次的方法( h i e r a r c h i c a im e t h o d ) 层次的方法对给定的数据对象集合进行层次的分解。根据层次的分解如 何形成，层次的方法可以分为凝聚和分裂两种。凝聚的方法也称为自底向上 的方法，一开始将每个对象作为单独的一个组，然后相继合并相近的对象或 组，直到所有的组合并为一个簇( 层次的最上层) ，或达到一个终止条件。分 裂的方法也称为自顶向下的方法，一开始将所有的对象置于一个簇中，然后 在迭代的每一步中一个簇被分裂为更小的簇，直到最终每个对象在单独的一 个簇中，或达到一个终止条件。 层次聚类方法虽然简单，但经常会遇到合并点或分裂点选择的困难，因 为一旦一组对象被合并或分裂，下一步的处理将在新生成的类上进行，并且 已做的处理不能被撤销，类之间也不能交换对象。如果在某一步中没有选择 好合并点或分裂点，就可能导致低质量的聚类结果。同时这种聚类方法不具 有很好的可伸缩性。因此人们提出众多改进的层次聚类算法以改进层次聚类 方法的性能。有两种方法可以改进层次聚类的结果：( i ) 在每层划分中，仔细 分析对象间的“联接 ，例如c u r e 和c h a m e l e o n 中的做法，( i i ) 综合层次聚 类和迭代的重定位方法。首先用自底向上的层次算法，然后用迭代的重定位 来改进结果，例如b i r c h 中使用的方法。 3 基于密度的方法( d e n sit y b a s e dm e t h o d ) 大多数划分方法基于对象之间的距离进行聚类，这样的方法只能发现球 状的簇，而在发现任意形状的簇上遇到了困难，为了克服上述弊端，人们提 出了基于密度的另一类聚类方法，其主要思想是：只要临近区域的密度( 对象 或数据点的数目) 超出某个阈值就继续聚类。也就是说，对给定类中的每个数 据点，在其所在区域的某个限定范围内必须同时包含一定数目的数据点。该 1 2 哈尔滨r 稃大学硕十学何论文 昌；i ；i ；i ；i ；i ；暑；宣；i i ；i ；i ；i t mttt_mm 窨 方法可以用来过虑噪声和孤立点数据，发现任意形状的簇，但算法的计算复 杂度高，一般为d 仍，对密度分布不均的数据集往往得不到满意的聚类结果。 同时，多数方法对参数都很敏感，参数设置的细微不同可能导致差别很大的 聚类结果。d b s c a n 是一个有代表性的基于密度的方法，它根据一个密度阈 值来控制簇的增长。o p t i c s 是另一个基于密度的方法，它为自动的和交互 的聚类分析提供一个聚类顺序。 4 基于网格的方法( g ri d - b a s e dm e t h o d ) 基于网格的方法把对象空间量化为有限数目的单元，由此形成一个网格 结构，所有的聚类操作都在这个网格结构上进行。这种方法的主要优点是它 的处理速度很快，同时可以识别任意形状的簇。其处理时间独立于数据对象 的数目，只与量化空间中每一维的单元数目有关。在处理数据对象时将同一 网格单元内的所有数据视为相同簇中的对象，避免了以距离作为度量标准的 算法只能识别球状簇的不足。但这种算法效率的提高是以聚类结果的精确性 为代价的。 s t i n g ”础是基于网格方法的一个典型例子。c u q u e 和w a v e c l u s t e r 这两 种算法既是基于网格的又是基于密度的。 5 基于模型的方法( m o d e i - b a s e dm t h o d ) 基于模型的方法为每个簇假定了一个模型，寻找数据对给定模型的最佳 拟合。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来 定位聚类。它也基于标准的统计数字自动决定聚类的数目，考虑噪声数据或 孤立点，从而产生健壮的聚类方法。这样的方法经常是基于的假设为：数据 是根据潜在的概率分布生成的。主要方法有两类：统计学方法和神经网络方 泫。如p i z z u t i c l a r a 等提出的p a u t o c l a s s 忙和s o f m 、a r t 网络等。 以上聚类算法在执行效率、聚类质量、聚类形状和过滤噪声数据等方面 各有自身的优点和局限性，因此人们在具体应用领域中须根据具体需求选择 合适的聚类算法。 1 3 哈尔滨i ：程大学硕十学位论文 2 4 数据流聚类算法 2 4 1 数据流聚类的含义 数据流聚类是传统聚类方法在数据流环境下的延伸，就是针对数据流的 聚类分析，它是相对于数据库操作模式下的传统聚类而言的，其特殊之处就 是其处理的数据是数据流中的数据。数据流聚类具有广泛的应用前景，例如， 它可以用于对网络使用情况进行监控，从而掌握网络用户的使用方式并对异 常的网络使用行为进行判别；它还可以应用在诸如电信记录的管理与分析， 商业交易管理与分析及金融信息监控与分析等众多的应用场景之中。 2 4 2 数据流聚类算法的要求 聚类分析已经被广泛研究了许多年，已经有许多有效的方法用于聚类静 态数据集。在数据库模式下，传统方法可以采用多次读取数据，并对数据进 行随机存取等操作实现对所存储数据的聚类。然而由于数据流本身的特性， 传统的聚类方法不能直接运用到数据流聚类上，人们需要的是适合于数据流 模型的、仅使用有界内存和有界处理时间的单遍扫描数据的高效聚类方法。 因而与传统的聚类算法相比，数据流聚类算法应当满足以下要求侧： ( 1 ) 线性扫描或一遍扫描。对于数据流中超大规模的海量数据而言，线 性扫描是唯一有效的读取数据方法，而随机读取或多次线性扫描数据需要相 当昂贵的计算代价。并且在多数数据流环境中数据以非常快的速度变化，并 不需要将其存储，这些数据必须在其产生时就被处理，实现线性扫描的增量