（计算机软件与理论专业论文）基于密度单元覆盖的聚类数据流算法研究.pdf

摘要 随着计算机应用的普及，信息系统产生的数据量日益增大，如何有效的利用 巨量的原始数据分析现状和预测未来，已经成为人类面临的一大挑战近年来， 越来越多的应用促使了数据流的产生，它是连续的、有序的、快速变化的、海量 的数据，如网络连接数据、传感器数据和w e b 点击流数据，分析和挖掘这种类 型的数据已经成为一个热点。 聚类是挖掘数据流的一种重要工具。聚类就是把没有类别标记的样本按照某 种准则划分为若干类，使类内样本的相似性尽可能大，而类间样本的相似性尽可 能小，是一种无监督的学习方法。流聚类分析较传统的聚类分析具有更大的挑战 性，这是由数据流的特性决定的。数据流分析的基本要求有：有限的使用内存及 存储空间；对数据的访问最多一次；能够有较短的响应时间。 除了内存限制和单遍扫描限制，数据流环境对聚类还有如下要求：不预先设 定聚类个数，能处理具有任意形状的聚簇并且能够处理孤立点。目前已经提出了 许多数据流聚类算法，但是都尚未解决以上数据流环境下的要求。传统的基于密 度的聚类算法，如d b s c a n ，可以发现具有任意形状的聚类，但这些算法的高 复杂度以及多次扫描数据集的需求不适合对流数据进行聚类。 在数据流滑动窗口模型下，本文提出了基于密度单元覆盖的数据流聚类算法 d u c s t r e a m 。该算法能发现具有任意形状的数据流聚类，解决了由于数据流滑动 窗口模型下不能精确记录每个数据，历史数据对聚类结果的影响问题。d u c s t r e a m 使用核心密度单元和候选密度单元刻画数据分布形式，作为在线数据摘要信息； 根据每个单元中的最近数据到达时间修剪单元，保证了在线数据摘要信息是对当 前窗口中数据流数据的覆盖；最后根据查询要求得到结果。在实际和人工数据集 上的实验表明，d u c s t r e a m 算法具有良好的性能。 关键字：数据流，聚类，滑动窗口，密度单元； 第1 页 a b s t r a c t w i t ht h ew i d eu s a g eo fi n f o r m a t i o nt e c h n o l o g y , d a t ag e n e r a t e df r o md i f f e r e n t i n f o r m a t i o ns y s t e m sb e c o m em o r ea n dm o r e ：h o wt ou t i l i z et h eh l l g co r i g i n a ld a mt o a n a l y z ec u r r e n ts i t u a t i o na n dm a k ep r e d i c t i o ne f f e c t i v e l y , h a v ea l r e a d yb e c o m eag r e a t c h a l l e n g e r e c e n t l y , ag r o w i n gn u m b e ro fa p p l i c a t i o n sg e n e r a t es t x c a m so fd a t a , s u c h a sn e t w o r kf l o w s ，s e n s o rd a t aa n dw e bc l i c ks t r e a m s t h e ya r et e m p o r a l l yo r d e r e d ， f a s tc h a n g i n g ，m a s s i v e ，a n dp o t e n t i a l l yi n f i n i t e a n a l y z i n ga n dm i n i n gs u c hk i n d so f d a t ah a v eb e e nb e c o m i n gah o tt o p i c 、 c l u s t e r i n gi sa l li m p o r t a n tt a s ki nm i n i n ge v o l v i n gd a ms t r e a m s c l u s t e r i n g , a n u n s u p e r v i s e dc l a s s i f y i n gm e t h o d ，i st h ep r o c e s so fg r o u p i n gs i m i l a rm u l t i - d i m e n s i o n a l d a t av e c t o r si n t oan u m b e ro fc l u s t e r s c o m p a r e dw i t ht r a d i t i o n a lc l u s t e ra n a l y s i s ， c l u s t e ra n a l y s i so ns t r e a md a t am e e t sm u c hm o r ec h a l l e n g e sb e c a u s eo ft h ep r o p e r t i e s o fs t r e a md a t a f o rs t r e a md a t a , t h ef o l l o w i n gc o n d i t i o n ss h o u l db es a t i s f i e d ：f i r s t l y , l i m i t e dm e m o r ya n ds t o r a g es p a c e ；s e c o n d l y , a c _ x 圮s st od a t aa tm o s to n et i m e ；t h i r d l y , h a v el i t t l er e s p o n s et i m e b e s i d e st h el i m i t e dm e m o r ya n d o n e - p a s sc o n s t r a i n t s ，t h en a t u r eo fe v o l v i n g d a t a s t r e a m si m p l i e st h ef o l l o w i n gr e q u i r e m e n t sf o rs t r e a mc l u s t e r i n g ：n oa s s u m p t i o no n t h en u m b e ro fc l u s t e r s ，d i s c o v e r yo fd u s t e r sw i t ha r b i t r a r ys h a p ea n da b i l i t yt oh a n d l e o u t l i e r s w h i l eal o to fc l u s t e r i n ga l g o r i t h m sf o rd a t as t r e a m sh a v eb e e np r o p o s e d ， t h e y o f f e r1 1 0s o l u t i o nt ot h ec o m b i n a t i o no ft h e s er e q u i r e m e n t s t r a d i t i o n a l d e n s i t y - b a s e dc l u s t e r i n gm e t h o d s ，s u c ha sd b s c a n , c o u l d b ea d a p t a b l et ot h ed a t a s e t o fa r b i t r a r ys h a p e ，b u th a v eh i g hc o m p u t a t i o n a lc o m p l e x i t ya n ds c a nd a t a s e t ss e v e r a l t i m e s t h i sp a p e rp r o p o s e dan e wd a t as t r o a mc l u s t e r i n ga l g o r i t l n nu n d e rs l i d i n g w i n d o wm o d e l , c a l l e dd u c s t r c a m , w h i c hb a s e do nt h ed e n s i t yu n i tc o v e r d u c s t r e a mc a nd i s c o v e rd u s t e r sw i t ha r b i t r a r ys h a p e , a n dh a ss o l v e dt h e h i s t o r i c a ld a t ai n f l u e n c eo nc u r r e n tc l u s t e r sb e c a u s eu n d e rt h ed a t as t r e a ms l i d i n g w i n d o wm o d e lm e m o r yc a n n o tp r e c i s e l yr e c o r de a c hd a t a w eu s ec o r ed e n s i t y u n i ta n dt h ec a n d i d a t ed e n s i t yu n i ta so n l i n ed a t as y n o p s e st op o r t r a yt h ed a t a 第n 页 d i s t r i b u t e df o r m w ew i l lp r u n et h eu n i ta c c o r d i n gt ot h er e c e n td a t aa r r i v a lt i m e i ne a c hu n i t , t h a tg u a r a n t e e dt h eo n l i n ed a t as y n o p s e si st h es m a l l e s tc o v e 4 o f c u r r e n tw i n d o wd a t ai nt h ed a t as l z e a m f i n a l l yo b t a i nt h ef i n a lo u t p u ta c c o r d i n g t ot h er e q u e s t t h ee x p e r i m e n t a lr e s u l to v c rr e a l i s t i ca n dt h ea r t i f i c i a ld a t as e t d e m o n s t r a t e sg o o dp e r f o r m a n c eo ft h ed u c s t r e a ma l g o r i t h m k e y w o r d s ：d a t as t r e a m ；c l u s t e r i n g ；s l i d i n gw i n d o w ；d e n s i t yu n i t ； 第页 第一章引言 第一章引言 随着信息技术的快速发展和信息搜集能力的日益提高，产生了海量数据，这 些海量的数据或是以静态的形式存储在企业的物理存储器上，或是不被存储而瞬 时出现的动态数据，称之为“数据流”面对如此丰富的海量数据，传统的数据 处理方法和能力已不能满足实际需要，针对数据流挖掘的方法也应运面生。 数据挖掘就是从大量数据中发现有趣模式，这是一个跨学科领域，源于诸如 数据库系统、数据仓库、统计学、机器学习、数据可视化、信息检索和高性能计 算【1 1 。在关系数据库基础上，数据挖掘方法已经有了较为深入的研究，而基于数 据流的数据挖掘方法的研究，是一个较新的但是却也有着广泛应用前景的领域。 基于数据流的数据挖掘是指从实时产生、快速到达的数据流中发现隐含模式。 聚类是数据挖掘中的一个重要问题，也是一种重要的数据分析形式，将物理 或抽象的集合分组成为由类似对象组成的多个类的过程被称为聚类，聚类分析能 作为一个独立的工具来获得数据分布的情况观察每个簇的特点，集中对某些特 定的簇作进一步分析，此外，聚类分析还能作为其他算法( 如特征和分类) 的预 处理步骤。在数据流环境中，对聚类分析提出了更大的挑战，传统的聚类算法都 不能适应新的变化，在新的需求面前，对数据流聚类的研究正不断的开展，在传 统聚类方法的基础上，已经提出了部分数据流聚类算法如s t r e a m 2 1 、c l u s t r c a m 6 1 等，目前聚类数据流分析是一个较为活跃的研究方向。 本文的题目是基于密度单元覆盖的数据流聚类算法研究，着重解决在滑动窗 口模型下，处理高速、海量数据流中具有任意形状的聚簇问题。 1 1 研究背景 近年来，一种新型数据形式数据流得到了广泛的应用和研究，数据流是持续 快速到达的数据序列，数据量巨大，并且数据分布具有时变性【9 1 。日益增长的应 用促使了数据流的产生，如：电信呼叫记录、商业信用卡交易、网络管理和流量 控制、金融市场股票交易、传感器数据、网页日志和网页点击流等。这些信息呈 现形式较多的不是静态方式，而是动态连续流的形式 1 0 i 。这种应用的特点是：数 据量巨大，数据产生速度特别快。 数据流具有如下特征： 第1 页 第一章引言 ( 1 ) 数据量巨大，可以认为是无限的 ( 2 ) 数据分布不断变化，不是保持固定的数据分布不变。 ( 3 ) 数据持续到达，速度特别快，需要实时响应。 ( 4 ) 数据流是一种有序序列，在时间维上存在次序关系。 一系列连续且有序的点( 通常数量巨大) 组成的序列初，x i ，x a ，称为数 据流。数据流与传统的数据集不同，它们以不同的速率连续到达和离开计算机系 统。这些数据是按照时间有序的、快速变化的、大量的、无限的。基于数据流的 这些特性，数据流处理需要满足以下基本要求： ( 1 ) 单遍( s i n g l e p a s s ) ：线性扫描，不允许随机访问 ( 2 ) 实时( r e a l - t i m e ) ：每个数据的处理时间必须快速，实时响应 ( 3 ) 存储限制( b o u n d e ds t o r a g e ) ：由于数据流数据的海量特性，对数据流 的处理一般是不存储的。但是，在进行某些分析处理时，必须考虑历史数据的特 性，因此必须存储历史数据的一些概要信息。 由于众多应用领域的需求，近几年数据流处理问题，特别是数据流挖掘问题 已受到越来越多的研究。国外在数据流挖掘方面有两个比较有影响的研究小组： 一个是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 教授领导的小组。前者研究侧重在数据流管理、数据流的连续查询和数 据流的聚类方面【卅，提出不同于传统d b m s 的d s m s ( d a t as t r e a mm a n a g e m e n t s y s t e m ) 概念。后者的研究侧重于数据流分析，对于数据流的在线分析，从聚类、 分类、频繁模式项集挖掘以及可视化等角度作了大量研究工作 6 - 8 1 。 1 2 研究动机 在数据流领域，聚类是一个比较困难的问题。这是因为在数据流中数据到达 的速度快，数据量巨大，并且聚类中心也在随时间演化，即数据分布潜在的模型 也在不断变化例如，在网络管理中，用户的t c p 连接记录就形成了一个数据 流，但用户得连接模式却随时间不断地交化。特别是数据流环境中，要求对数据 单遍扫描，这种情况下，传统聚类方法都不再适应。 本文研究的重点是滑动窗口模型下的数据流聚类问题。在很多数据流应用领 第2 页 第一章引言 域中，如分析网络流量模式，电话记录，科学传感器数据，一般认为当前最近到 达的数据比历史数据更有代表性，更注重于对当前一段数据的查询，数据流的滑 动窗口模型能够很好地实现对最近到达数据的处理。 同传统数据处理方法相比，数据流的特点要求内存不能存储所有的数据，对 每个数据至多扫描一次，而且处理时间必须快速，实时响应。基于数据流环境的 限制，滑动窗口模型下的聚类需要处理以下问题： ( 1 ) 在线保存有效的近似数据摘要。由于无法存储所有数据和记录数据的 流入次序，所以如何处理窗口中的过时数据，保留有意义的历史数据，是滑动窗 口模型下数据流聚类的关键。 ( 2 ) 发现由于数据流中数据分布的时变性导致的具有任意形状聚簇。如在 网络管理中，连接的分布通常是无规则的，就需要能够得到任意形状的聚簇结果。 先前的数据流聚类算法，如c l u s t r e a m 由于采用距离作为度量，通常得到的是球 形聚簇。 ( 3 ) 数据流随时间的演化，表现为聚类中心的变化迁移，或者聚类个数的 增减。 ( 4 ) 能够满足用户在一定时间水平下的查询。 数据流是传统数据的一种特殊形式，因此基于数据流的数据挖掘是传统数据 挖掘在数据维上的扩展。但是，由于数据流本身的特性，基于传统数据集的数据 挖掘方法不再适用于数据流环境，能够适应数据流挖掘要求的方法需求迫切。 1 3 本文的贡献 基于以上因素，在滑动窗口模型下，本文对数据流聚类问题作了深入研究， 并提出了新的基于密度单元覆盖的聚类数据流算法d u c s t r e a m 。 本文主要贡献： ( 1 ) 研究了滑动窗口模型下，历史数据的保存问题。根据历史数据产生的 微聚类对当前窗口中数据聚类影响的大小，决定是否保留历史数据。在这种方式 下，更加符合数据流的特性，对数据流环境的挖掘有实际意义，也是本文的创新 点之一。 第3 页 第一章引言 ( 2 ) 提出了密度单元覆盖的概念。利用核心密度单元和候选密度单元刻画 了当前数据流窗口下数据的特征，保留了足够的在线信息。 ( 3 ) 提出了基于密度单元覆盖的聚类数据流算法d u c s t r e a m ，能够发现具 有任意形状的聚簇。该算法包括在线部分基于滑动窗口模型的微聚类保持，离线 聚类方法和聚类演化分析。在线部分通过核心密度单元和候选密度单元保存数据 流信息，利用单元中最近数据到达时间修剪单元，选择历史数据聚簇。离线部分 利用在线部分保存的摘要信息，获得具有任意形状的聚簇分析结果。 1 4 本文的内容组织 围绕前述研究内容，本文各章节安排如下： 第一章为本文的引言部分，介绍了本文的研究背景和动机，简单了解数据流 的相关概念和背景，并提出了论文的意义和贡献，以及本文的组织结构。 第二章为相关的工作介绍，主要给出了聚类问题的研究进展，以及相关数据 流聚类算法的分析和讨论。 第三章为双层数据流聚类框架描述，介绍了双层数据流聚类框架的优点。以 及本文中的框架简介。 第四章为本文的算法思想描述，主要介绍了滑动窗口模型和密度单元覆盖原 理，针对数据流聚类的问题，介绍了d u c s t r c a m 算法的主要过程。 第五章是实验结果和分析，选用c l u s t r e a m 算法作为对比，利用几个不同数 据集测试，最后比较算法的性能和敏感度分析。 第六章是总结和工作展望。对本文的工作做了总结，并且对下一步需要继续 研究的问题作了探讨 最后是本文的参考文献、致谢及附录。 第4 页 第二章聚类算法 第二章聚类算法 聚类( c l u s t e r i n g ) 是数据挖掘中的一种重要分析方法，将数据对象分组成为 多个类或簇，在同一个簇中的对象之间具有较高的相似度，而不同的簇中的对象 差别较大。相异度是根据描述对象的属性值来计算的。距离是通常采用的方式。 聚类分析源于许多领域，包括数据挖掘、统计学、生物学、以及机器学习。 在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并 且用购买模式来刻画不同的客户群的特征。在生物学上，聚类能用于推导植物和 动物的分类，对基因进行分类，获得对种群中固有结构的认识。聚类也能用于对 w e b 文档的分类，以发现信息。作为一个数据挖掘的功能，聚类分析能作为一个 独立的工具来获得数据分布的情况，观察每个簇的特点，集中对特定的某些簇作 进一步的分析。 聚类是一个富有挑战性的领域，它的潜在应用提出了各自特殊的要求。如下： 可伸缩性、处理不同类型属性的能力、发现任意形状聚类、用于决定输入参数的 领域知识最小化、处理噪声数据的能力、对于输入记录的顺序不敏感、高维性， 基于约束的聚类，可解释性和可用性。 2 1 数据流挖掘概述 基于数据流的数据挖掘是指从实时产生的、快速到达的数据流中发现隐含 的、利用简单查询得不到的隐含模式。已有的关于数据挖掘、机器学习、数据库 系统、统计方法等的研究为进一步的数据挖掘方法研究奠定了良好的基础。新的 数据流挖掘方法一定是在继承已有的理论方法研究基础上，结合新的数据特性而 得到的理论方法。 2 1 1 数据挖据 数据挖掘就是从大量的数据( 大型数据库和数据仓库) 中提取和挖掘知识的 过程，这些知识是人们感兴趣的、隐含的、事先未知的和潜在有用的信息。 数据挖掘按照功能可以分为两种：描述性挖掘和预测性挖掘。前者用来发现 数据库中数据的一般性规律和特征，如概念( 或类别) 的特征化和区分、关联分析、 聚类分析等。后者则先根据现有数据建立模型，然后对未知数据进行推断和预测， 第5 页 第二章聚类算法 如数据分类、数值预测( 又称回归) 等。 数据挖掘综合了很多学科技术，具有多种功能，当前主要功能如下： 分类：分类就是找出一个类别的概念描述，它代表了这类数据的整体信息， 即该类的内涵描述，并用这种描述来构造模型，一般用规则或决策树模式来表示。 聚类：就是把数据按照相似性归纳成若干类别，统一类别中的数据彼此相似， 不同类别中的数据相异。聚类分析可以建立宏观的概念，发现数据的分布模式， 以及可能的数据属性之间的相互关系。 关联规则和序列模式的发现：关联是某种事物发生时其他事物也会发生这样 一种联系一般用支持度和可信度两个阈值来度量关联规则的相关性，还不断引 入兴趣度、相关性等参数，使得所挖据的规则更符合要求。例如：每天买啤酒的 人也有可能购买香烟，比重有多大，可以通过关联的支持度和可信度来描述。与 关联不同，序列模式是一种纵向关系。 预测：就是利用历史数据找出变化规律，建立模型，并由此模型对未来数据 的种类及特征进行检测。预测关心的是精度和不确定性，通常用预测方法差来度 量。 偏差的检测：对分析对象少数的、极端的特例的描述，揭示内在的原因。流 入：在银行的1 0 0 万笔交易中有5 0 0 例的欺诈行为，银行为了稳健经营，既要发 现这5 0 0 例的内在因素，减小以后经营的风险。 2 1 2 数据流挖掘 和传统数据模型相比，数据流模型具有截然不同的特性，这对数据流模型下 的查询处理技术提出了新到的挑战。概括言之，主要有以下几个方面的挑战。 ( 1 ) 实时性( r e a lt i m e ) 实时、连续地输出查询结果是数据流算法的最基 本要求。对于数据流上到达的任一元组，要求数据流算法能很快处理完成。否则， 数据不断到达、延时不断积累，最终导致服务质量显著降低另外，在大多数应 用中，数据流速率会随着外部环境的变化而改变。例如，节假日的信用卡消费日 志要比工作日的日志大得多。 ( 2 ) 低空间复杂度( 1 0 ws p a c ec o m p l e x i t y ) 数据流从理论上是无限的。为 第6 页 第二章聚类算法 保证算法持续稳定运行，数据流算法的空间复杂度要非常小假设在当前时刻， 数据流长度为n ，数据流算法的空间复杂度一般要求在o ( p o l y ( 1 0 9 0 ) 之内。这样， 数据流算法的空间占用量的增长速度就远远小于数据流自身规模的增长速度。 ( 3 ) 准确性数据流模型下数据规模大、速率快，对于一些复杂问题不可能 一次遍历就得到准确答案。但很多实际应用也并不需要误差为零的查询结果。例 如，网络路由器通过实时监控各个口地址发送的数据包数量，可以检测是否有 d o s 攻击。对路由器来说，口包数目到底是5 0 1 7 5 还是5 0 0 0 0 1 0 0 0 ，差别并不 大数据流算法的一大特性就是它通常返回一个近似值，而非准确值。算法的精 确度往往和内存空间紧密相连，当被分配更多内存空间时，算法准确度也更高。 ( 4 ) 适应性( a d a p t i v i t y ) 在很多应用中，数据流变化很大。这个变化不 仅可以是流速变化，还可以表示数据分布的变化例如，在传感器网络中，各个 传感器节点都采集数据，发送到中心主机进行处理。传感器节点发送数据的速率 和外部条件紧密相关一一当特定事件发生时，有些节点会发送更多数据。对于数 据流算法而言，当外部条件变化时，能够根据数据流变化及时调整参数，进而提 高性能就非常重要。 在数据流挖掘中，研究较多的是聚类【硐、分类【1 1 , 1 2 、多维回归分析【埘、频 繁模式挖掘f 体r 丌、序列模式挖掘【1 8 。驯等，在数据流环境中，聚类算法一直得到很 大重视，能够在数据量巨大，而且流速特别快的数据中，通过设计聚类算法，得 到数据的特征分析，在网络流量分析，路由设计，网络入侵检测研究中都有十分 重要的作用。而本文的研究就是在复杂多变的数据流环境中，如何有效的聚类出 正确的结果，满足聚类结果评价分析的要求，并且不减少精确度，也就是本文的 研究起点。 2 2 传统聚类算法 在数据挖掘领域，聚类分析已经得到了广泛的研究根据不同的应用领域， 针对各种应用问题，提出了大量的聚类算法，涉及到了多种知识领域。同样的， 在新的数据流聚类算法研究时，传统聚类算法都是可以作为借鉴的参考，从思想 和方法上都对新的挖掘方法有指导作用。接下来我们给出传统聚类算法的分类和 主要思想，并且详细介绍了与本文也有关联的基于密度的聚类算法d b s c a n 。 第7 页 第二章聚类算法 2 2 1 聚类算法分类 ( 1 ) 划分方法 给定一个疗个对象或元组的数据库，一个划分方法构建数据的 1 个划分，每 个划分表示一个聚簇，并且k 嚣。也就是说，它将数据分为虫各组，同时满足 如下要求：( i ) 每个组至少包含一个对象；( i i ) 每个对象必须属于且只属于一个 组。划分方法说先创建一个初始划分，然后采用一种迭代的重定位技术，尝试通 过对象在划分间的移动来改进划分。 为了达到全局最优，基于划分的聚类会要求穷举所有可能的划分，大多数应 用采用了以下两个比较流行的启发式方法：( i ) 七一平均值算法，每个簇用该簇 中对象的平均值来表示，相对可伸缩和高效，仅能发现局部最优结果，仅当均值 定义下才能够使用，不适合发现非凸面形状的聚类，对孤立点和噪声数据敏感。 伍弘- 中心点算法，每个簇用接近聚类中心的一个对象来表示，此种算法消除了对 孤立点的敏感性，但同样需要提前制定七值。 ( 2 ) 层次方法 层次的方法对给定数据对象集合进行层次的分解，分为凝聚的和分裂的。层 次方法的缺陷在于，一旦一个步骤( 合并或分裂) 完成，它就不能被撤销。 具有代表性的层次聚类方法有：b i r c h l 2 1 1 ，利用层次方法的平衡迭代归约 和聚类；c u r e = ，利用代表点聚类；c h a m e l e o n 2 a ，利用动态模型的层次聚类。 ( 3 ) 基于密度的方法 绝大多数划分方法基于对象之间的距离进行聚类。这样的方法只能发现球形 聚簇，而在发现具有任意形状的簇上遇到了困难。基于密度方法的主要思想是： 只要临近区域的密度超过某个阈值，就继续聚类。这样的方法可以用来过滤噪声， 发现任意形状的聚簇。 具有代表性的基于密度的方法有：d b s c a n 2 4 1 ，基于高密度连接区域的密 度聚类；o p t i c s l 2 5 】，通过对象识别排序识别聚类结构；d e n c l u e l 2 日，基于密 度分布函数的聚类。 ( 4 ) 基于网格的方法 第8 页 第二章聚类算法 基于网格的方法把对象空间量化为有限数目的单元，形成了一个网格结构。 所有聚类操作都在这个网格结构( 即量化空间) 上进行，主要优点是处理速度特 别快，其处理时间独立于数据对象数目，但空间代价较高 具有代表性的基于网格的聚类算法：s t i n c 斗2 n ，统计信息网格， w a v e c l u s t e r l 2 日1 ，采用小波变换聚类；c l i q u e e m j ，聚类高维空间 ( 5 ) 基于模型的方法 基于模型的方法为每个聚簇假定了一个模型，寻找数据对给定模型的最佳拟 和。一个基于模型的算法可能通过构建反映数据点空间分布的密度函数来定位聚 类，它也基于标准的统计数字自动决定聚类的数目，考虑“噪声”数据或孤立点， 产生健壮的聚类算法。 具有代表性的基于模型的聚类算法：统计学方法c o b w e b 0 0 1 ，神经网络方 法，竞争学习和自组织特征映射。 虽然传统聚类方法已经得到了广泛的研究，也提出了多种适用于静态数据的 算法，但在数据流环境中，传统聚类方法不能解决下面问题： ( 1 ) 当数据随时间演化非常大时，聚类结果质量是不好的。 ( 2 ) 数据流聚类算法需要有效的在流的不同部分发现和得到聚类。 ( 3 )数据流环境要求的单遍扫描和内存限制问题。 简单的将流聚类视为单遍聚类从实用角度是没有意义的，例如，在过去几年 所有数据流数据上的单遍聚类结果被大量的过时数据所占据。由于聚类的结果是 一定数据的积累，所以即使在流环境中也不可能在每一个数据到来的时候就能测 得聚类的演化。 2 2 2 , d b s c a n 算法 基于密度的聚类算法是本文研究工作的一个基础，先在这里对我们后面借鉴 的d b s c a n l 2 4 1 算法作一个概述。 d b s c a n 算法是一个基于密度的聚类算法，该算法能够将具有足够高密度 的区域划分为簇，并可以在带有“噪声”的空间数据库中发现任意形状的聚类。 基于密度的聚类算法涉及的定义： 第9 页 第二章聚类算法 给定对象半径e 内的区域成为。一邻域。 如果一个对象c 一邻域至少包含最小数目m i n p t s 个对象，则称该对象为核 心对象。 给定一个对象集合d ，如果p 是在q 的e 一邻域内，而鼋是一个核心对象， 我们说对象p 从对象鼋出发是直接密度可达的。 如果存在一个对象链肌，p 2 ，p n ，p l = q ，办= p ，对p t e d ，1 i n ，a + l 是从a 关于和m i n p t s 密度可达的，那么对象p 和鼋是关于e 和m i n p t s 密度相 连的。 一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合。不包含 在任何簇中的对象被认为是“噪声”。 d b s c a n 通过检查数据库中的每个点的c 一邻域来寻找聚类。如果一个点p 的e 一邻域包含多于m i n p t s 个点，则创建一个以p 作为核心对象的新簇。然后， d b s c a n 反复的寻找从这些核心对象直接密度可达的对象，这个过程可能涉及 一些密度可达簇的合并当没有新的点可以被添加到任何簇时，该过程结束。 如果采用空间索引，d b s c a n 的计算复杂度是o ( n l o s , , ) ，这里n 是数据库 中对象的数目。 2 3 数据流聚类算法 随着数据流挖掘的不断深入，数据流聚类算法也成为研究的一个热点。近几 年来，陆续提出了几种关于数据流聚类的挖掘算法，对数据流聚类算法的研究还 在不断的探讨之中，在这里，我们详细介绍了几种具有代表性的数据流聚类方法， 从中分析各种方法的应用范围和不足之处。 2 3 1b i r c h 算法 b i r c h l 2 1 】算法试图利用有限的资源来生成最好的聚类结果，尽可能减少b o 请求。b i r c h 算法采用聚类特征树( c - v - t r e e ) 来表示聚类，c f 树是高度平衡树， 采用分层数据结构存储聚类特征。聚类特征c f 是聚类信息的三元组：c f = ( ， 工s 5 s ) ，这里是类中对象个数，上j 、船分别是这个对象的属性值之和与平 方和，用于计算属性均值和方差。c f 树的大小由两个参数确定：分支因子b 和 第1 0 页 第二章聚类算法 阈值l 分支因子定义了每个非叶节点孩子的最大数目，而阈值给出了叶节点中 聚类的最大直径。b i r c h 算法包括了两个阶段：第1 阶段扫描数据库，建立初 始存于内存的c f 树；第2 阶段采用某个聚类算法对c f 树的叶节点进行聚类以 进一步改进聚类质量。由于c f 树的每个节点只能包含有限数目的条目，节点并 不总是对应于自然聚类，而且由于b i r c h 算法用直径的概念控制聚类的边界， 如果聚类的边界不是球形的，b i r c h 算法不能很好地工作 2 3 2s t r e a m 算法 g u h a 等人为了解决数据流聚类问题，早期提出了聚类数据流的算法 s t r e a m 2 1 ，它是基于局部搜索的快速k 中心点单层数据流聚类算法，主要解决了 数据流环境下内存容量的限制。将数据流分为能适应内存大小的块，蜀 对每个块，首先确定是否仅有小于k 个点在重复出现，如果是，那么就用这些值 仅出现一次来表示块，但加上每个点在块中的个数作为权值( 如果原始点有权值， 那么新的权值是这个点在块中所有权值之和) 。使用l o c a j _ s e a r c h 来聚类块， 仅保留在块中得到的k 个加权中心点，每个中心点的权值是所有属于它所表示聚 类中点的个数。最后应用l 0 咄e a r c h 到从局，蕊所有得到的中心点上 得到最终的k 个聚类中心点。 s t r e a m 算法的核心是使用了工厂位置( f a c i l i t yl o c a t i o n ) 方法的 l o c a l s b 堰c h 子程序。在l o c a l s e a r c h 算法的执行过程中，中间步骤变 化聚类数目，最后达到精确的k 值。给定n 个数据点的集合和参数z ，这里z 为工厂耗费值，也可以理解为在一个点作为中心点需要增加的代价，对于k 个中 心点的集合c = c j , c z ，c k c q , 定义的划分为k 个聚类m ，肌，满足 魁中包含所有中距c i 最近的点，日标是选择一个k 值和集合c ，使函数f c 最 小：f c ( - v ，c ) - z l c | + 荟奢) 首先需要一个好的初始解决方案，具体方法是随机重排数据，将第一个点作 为中心点，然后后面的数据计算和它最近中心点的距离d ，以概率d z 在该点建 立一个中心点，接着取得可用的o ( g l o g k ) 个抽样候选点，可以和最优解达到高概 率的常数近似。从这个初始方案开始，通过局部改进来得到最终结果。在 第1 l 页 第二章聚类算法 l o c a l s e a r c h 算法中使用二叉查找法，对每一个新的方案，都用在中抽样 得到的可用点作为中心，如果f c 变小，那么来代替c 中的点如果所有的可用 候选点都不能代替现有中心点使f c 变小，而又没有达到期望的k 值，将需要改 变z 值，z 的值最初设置为所有点同一个随机点的距离之和的一半，然后在这个 范围内执行二叉查找，如果得到的中心点个数小于k ，那么可以减小工厂耗费值 z ；如果大于k ，需要增大工厂耗费值z ，那么直到得到合适的z 值和期望的足。 l o c a l s e r c h 可得到最优解的常数近似，时间复杂度为o ( n , , n + n l d o g l , ) , 其中 i n 是初始方案中的c 值一般情况下，虽然肼依赖于数据集，但通常是小的。 l o c a l _ s e a r c h 算法的实质是选择出能使s s q 最小的k 个点作为中心点，但由 于数据流中每一块聚类数目并不相同，所以用工厂位置方法灵活的控制七的个 数，以达到更高的精确度，它随机选取了数据集中能高概率保证结果个数的点作 为候选中心点，来替换已有的中心点。 在实际运行l o c a l s e a r c h 程序时，的确性能比k 均值要高。s t r e a m 作为 早期处理流聚类的算法，很好的解决了数据流要求内存限制的问题，并且对结果 从理论上证明了其性能保证。如果单独从满足数据流的自身特点出发，单层数据 流聚类算法可以说是显示出很强的优势。但是聚类是一个应用性很强的问题，在 现实的数据流应用中，数据量不仅浩瀚如海，而且数据通常变化很大。在满足聚 类质量的同时，还要满足用户从不同应用角度获取聚类结果的要求。而单层数据 流聚类算法恰恰忽略了这些方面，也就是它忽略了我们前面提出的数据流聚类需 要考虑的后两个问题。 2 3 3c l u s t r e a m 算法 尽管已经提出解决流聚类可伸缩性的方法，但是这些方法忽视了数据的演 化，不能解决以下两个问题1 ) 当数据随时间演化很大时，聚类质量是差的。2 ) 数据流聚类方法要求在流的不同部分能够发现和得到聚类。在不同时间窗口上挖 掘流能给用户提供对聚类演化行为更深层的认识，同时，对于所有时间水平上的 数据流，不可能都立即得到动态聚类。 c l u s t r c a m 6 1 是一种基于用户定义，在线聚类查询的演化数据流聚类算法。主 要思想是将聚类过程分为周期性存储详细摘要信息的在线组件( o n l i n e 第1 2 页 第二章聚类算法 c o m p o n e n t ) ，和仅使用这些摘要信息的离线组件c o m i n ec o m p o n e n t ) 。在快速数据 流中有效的选择、存储和使用统计信息是十分棘手的问题。因此，使用了同微聚 类( m i c r oc l u s t e r i n g ) 方法相关联的金字塔时间框架o y r 眦i d a lt i m ef r a m e ) 的概念。 在线部分使用微聚类计算和存储数据流上的摘要统计量，完成微聚类的增量在线 计算和保持。离线部分就是宏聚类( m a c r o c l u s t e r i n g ) ，使用存储的摘要统计量 来回答不同的用户问题。聚类演化数据流是基于历史和当前数据信息，时间框架 模型依赖予新鲜度在多粒度水平上存储微聚类的快照，直觉上更新的数据将比老 的数据提供更多信息。存储的信息能用于处理历史相关数据，用户定义的聚类查 询。 在c l u s t r e a m 中的一个微聚类表示为一个聚类特征。c l u s t r e a m 包括进去时间 域，扩展了在b i r c h 中提出的聚类特征的概念由于聚类特征的时间扩展，对 于一个d 维点集合，x 。，z ，以及时间戳瓦，瓦的微聚类定义成c 2 u + 3 ) 个元组( c f 2 。，c f l 。，c f 2 ，c f t ，n ) ，其中，前两个是d 维向量，后三个是 数量。c f 2 。是每维数值的平方和，即芝二i 砰类似的，每维的数值和保存在 c f l 中。从统计学的观点看，c f l 。和c f r 代表了数据的第二和第一序列距。 时间戳的平方和保存在c f 2 中，c f l f 是时间戳的和。最后，在微聚类中的数据 点的数目等于n 。 在线m i c r o c l u s t e r s 处理分为两个部分；1 统计数据选择。2 微聚类的更新。 在第一步中，总共保存口个微聚类，膨。，m 。，其中q 通常比自然聚类的 数目大很多，由可用内存的数量决定。在第二步中，每个新的数据点添加到一个 现存的聚类中，或者建立一个新的聚类。为了决定是否要建立一个新的聚类，需 要为每个聚类定义一个最大边界。如果新的数据点在最大边界之中，它就添加到 这个聚类中去，否则它就是建立新的聚类的第一个数据。当一个数据点添加到一 个现存聚类中时，因为微聚类的加法性质它被“吸收”。当一个数据点添加到一 个新的聚类中时，为了为新的聚类创建内存空间，最近最少使用的聚类必须被清 除或者两个现存聚类必须依据一定标准合并。 离线部分能完成用户指引的宏聚类或聚类演化分析。宏聚类允许用户在不同 第1 3 页 第二章聚类算法 的时间水平上探测流聚类。时间水平h 是流长度为h 的历史。给定用户定义的 时间水平h ，和期望得到的宏聚类个数k ，那么宏聚类将在h 上得到k 个聚类。 首先，在当前时间乞的快照中减去在时间t h 的快照。比当前时间水平老的聚类 没有包括进来。在时间水平中的微聚类被认为是加权点，被重新聚类得到高水平 的聚类结果。聚类过程同在s t r e a m 中使用的方法是类似的，但仅需要两个快 照( 开始和最后) 。 如果用户想看聚类怎样随时问变化，比如在过去一季度或一年。给定用户定 义的时间水平h ，两个时钟时间f 1 和f 2 ( f l w ) t h e n 标记该单元为空； 3 e n d i f 4 i f 一个候选密度单元g 满足权值大于m i n p t t h e n 5 i f 存在空闲核心密度单元空间t h e n 利用c i 创建新的核心密度单元，标 记e 为空； 6 e n d i f 7 e n d f o r 第2 9 页 第四章基于密度单元覆盖的聚类数据流算法 设当前时间为t ，对每个非空的密度单元，如果t t ，w 。表示该单元已经 不含任何当前窗口中数据，则删除该密度单元。如果有候选密度单元随着不断有 数据合并进入，当其8 区域内包含的数据点超过m i n p t ，即在该候选密度单元处 已经成了高密度区域，需要将其转变为核心密度单元。 定理4 1 核心密度单元和候选密度单元在任意时刻都是对当前滑动窗口下 数据的覆盖表示。 证明：初始阶段，核心密度单元是对初始数据集的覆盖表示，随着在线数据 流聚类过程，核心密度单元和候选密度单元都随着新数据的到来而更新，设当前 时间为l 如果有新数据进入，则该单元内的，将更新为当前进入时刻同时测 定如果有任何单元不满足t t w ，该单元将被删除置空。所以任何时刻，每个 单元的t 都在当前窗口之内，即都包含至少一个当前窗口中的数据。 数据流实际应用中，聚类的演化表现为聚类个数的增减