（计算机软件与理论专业论文）数据流聚类分析算法.pdf

中文摘要 近年来，许多应用中的数据是以流的形式产生的，例如网络流，传感器数 据，以及网页点击流等。分析和挖掘这类数据日益成为一个热点问题。作为一种 基础的数据挖掘手段，聚类分析在数据流环境下得到了学术界和工业界的广泛关 注。与传统数据库不同，数据流具有如下特点：( i ) 数据总量的无限性； ( 2 ) 数据到达的快速性； ( 3 ) 数据到达次序的无约束性；( 4 ) 除非可以保存，每个 元素均只能被处理一次。 数据流的上述特点对数据流上的聚类挖掘提出了如下要求：首先，算法必须 能够进行实时在线挖掘，快速处理每一个元组，并实时输出挖掘处理结果。其 次，相对于无限规模的数据流内存通常是有限的，算法的空间复杂度要低，往往 需要在数据量的对数范围内。再次，由于算法实时在线挖掘以及对空间复杂度的 限制，算法往往只能得到近似解，且需要具有一定的精确度保证。最后，算法要 具有较强的适应性，包括对数据流不断进化的底层模型的适应性，处理离群点的 能力，以及挖掘任意形状簇的能力等。 学术界已经对数据流上的聚类分析问题进行了不少研究工作，但仍存在许多 问题尚待研究和解决。本文研究了滑动窗口内的数据流聚类分析问题，数据流中 具有任意形状簇的挖掘问题，利用图形处理器加速数据流聚类问题以及分布式数 据流的数据聚类问题， 旨在为现有的数据流系统提供更为多样的聚类分析功能。 本文的主要贡献有如下四个方面： 1 本文提出了一种新算法c l u w i n 来解决滑动窗口内数据流聚类分析问题。我 们设计了一种新的概要结构一聚类特征指数直方图一来保持滑动窗口中簇 的统计信息。c l u w i n 算法仅需要维护d ( l o g ( e f 譬 ) ) 个时间聚类特征结构， 就能够估算长度为的滑动窗口中所有记录的聚类结果，且窗口最大相对 误差不超过e 。此外，它还被扩展用于解决n - n 窗口( 滑动窗口扩展模型) 数据聚类问题。 2 本文提出了一种新算法d e n s t r e a m 用于挖掘进化数据流中具有任意形状的 簇。我们引入一种“密”微簇称为核心微簇( c o r e - m i c r o - d u s t e r ) 用于描 述数据流中任意形状的簇，并提出潜在核心微簇( p o t e n t i a lc o r e - m i c r o - c l u s t e r ) 和离群微簇( o u t l i e rm i c r o - c l u s t e r ) 结构分别用于维护并区分数据 流中潜在的簇和离群点。d e n s t r e a m 基于这些概念包含了一种新颖的淘汰策 略，该策略可利用次线性空间的内存维护并保证各微簇权值的精度。 3 本文利用性能强大、目趋廉价且在数据流领域尚未引起足够重视的图形处 理器( g p u ) 处理数据流聚类挖掘问题。我们提出一类基于g p u 的快速聚 类方法，包括基于女m e a l l s 的基本聚类方法，基于g p u 的数据流聚类以及 数据流簇进化分析方法。这些方法的共同特点就是充分利用g p u 强大的处 理能力和流水线特性。与以往具有独立框架的数据流聚类算法不同，基 于g p u 的聚类算法具有同一框架和多种聚类分析功能，为数据流聚类分析 提供了统一平台。 4 本文提出了一个分布式聚类处理框架c l u d i s t r e a m 。该框架可高效地实时处 理分布式数据流中海量数据，有噪声、有损或不完整数据记录，以及有交 叠的数据集。在c l u d i s t r e 锄基于期望最大化( e x p e c t a t i o nm a x i m i z a t i o n ) 的算法中，每个数据记录可以以不同的隶属度属于不同的簇。这种软聚 类方式能较好地反映簇的交叠性对有噪声、损坏的或不完整的数据记 录，算法可通过最大化数据簇的似然度来学习数据流的底层分布。此 外，c l u d i s t r e a m 算法中测试后聚类的策略可有效地减少算法的平均处理代 价，这对分布式数据流的在线实时聚类挖掘非常有效。 总之，本文研究了数据流聚类分析的四个基本问题并分别提出了新的解决方 案。滑动窗口是处理数据流的基本模型之一，如何在滑动窗口内对数据流进行聚 类分析是一个基本问题；具有任意形状簇相对于球形簇是更为一般的数据簇模 型，如何挖掘任意形状的簇也是一个基本问题；如何提高数据流聚类算法的处理 速度是一个基本问题，这是由数据流聚类算法实时在线挖掘的特点所决定的；分 布式数据流的数据聚类问题，其基础性在于现实应用中数据流往往是在分布式环 境中产生的。本文算法是对现有数据流上的聚类分析技术的有益补充和改进。理 论分析和实验结果表明本文算法能够高效地解决相应问题，与现有数据流聚类方 法相比，本文算法在存储空间开销、挖掘处理速度以及结果准确性上具有优势。 关键词：数据流，聚类分析，进化，窗口，图形处理器 分类号：t p 3 0 1 a b s t r a c t r e c e n t l y , v a r i o u sa p p l i c a t i o n sg e n e r a t eal a r g en u m b e ro fs t r e a m i n gd a t a ，s u c h a sn e t w o r kf l o w ，s e u s o rd a t a ，a n dw e bp a g ec l i c k s m i n i n ga n da n a l y z i n gs u c h k i n do fd a t ah a sb e e nb e c o m i n gah o tt o p i c a sab a s i cm e t h o do fd a t am i n i n g ， c l u s t e r i n gi nd a t as t r e a ms e t t i n g sh a sb e e nw i l d l yc o n c e r n e df r o ma c a d e m i aa n d i n d u s t r y d i f f e r e n tf r o mt r a d i t i o n a ld a t ab a s e s d a t as t r e a m sh a v et h ef o l l o w i n g d i s t i n g u i s h e dc h a r a c t e r i s t i c s ：( 1 ) u n b o u n d e dv o l u m eo fd a t a ；( 2 ) r a p i da r r i v i n gr a t e o fd a t a ；( 3 ) u n c o n t r o u a b i l i t yo ft u p l e s a r r i v i n go r d e r ；( 4 ) b e i n gp r o c e s s e do n l yo n c e f o re a c ht u p l e ，e x c e p tb e i n gr e s e r v e d a b o v ec h a r a c t e r i s t i c sp r o p o s et h ef o l l o w i n gr e q u i r e m e n t so nc l u s t e r i n go v e rd a t a s t r e a m s ：f i r s t l y , a l g o r i t h m ss h o u l db eo n l i n em i n i n g ，b ea b l et of a s tp r o c e s se a c ht u - p l e ，a n do u t p u tt h em i n i n gr e s u l to nt i m e ；s e c o n d l y , b e c a u s eo ft h el i m i t e dm e m o r y c o m p a r e dt ou n l i m i t e dd a t as t r e a m s ，a l g o r i t h m ss h o u l dh a v el o ws p a c ec o m p l e x i t y , t h es p a c ec o m p l e x i t ys h o u l db ei nt h er a n g eo fl o gb o u n do fd a t av o l u m e t h i r d l y , b yt h ec o n s t r a i n to fo n l i n em i n i n ga n d l o ws p a c e c o m p l e x i t y , a l g o r i t h m sc a no n l yg e t a p p r o x i m a t er e s u l t s ，h o w e v e r ，t h a tr e s u l t ss h o u l db eg u a r a n t e e do np r e c i s i o n a t l a s t ，a l g o r i t h m ss h o u l db ea d a p t i v e ，i n c l u d i n gt h ea p p l i e a b i l i t yo nd a t as t r e a m sw i t h e v o l v i n gu n d e r l y i n gm o d e l ，t h ea b i l i t i e so nh a n d l i n go u t l i e r sa n da r b i t r a r y - s h a p e d c l u s t e r s a1 0 to fm e t h o d so ns t r e a mc l u s t e r i n gh a v eb e e np r o p o s e d h o w e v e rt h e r ea r e m a n yp r o b l e m sn e e dt ob er e s e a r c h e da n dr e s o l v e d i nt h i sp a p e r ，w es t u d yt h e t h e p r o b l e mo fc l u s t e r i n gd a t as t r e a m so v e rs l i d i n gw i n d o w s ，t h ep r o b l e mo fd i s c o v e r y a r b i t r a r y - s h a p e dc l u s t e r si nd a t as t r e a m s ，t h ep r o b l e mo fc l u s t e r i n gd a t as t r e a m sv i a g r a p h i cp r o c e s s o r sa n dt h ec l u s t e r i n gp r o b l e mi nd i s t r i b u t e dd a t as t r e a ms e t t i n g s ， i no r d e rt op r o v i d et h ee x i s t i n gd a t as t r e a ms y s t e r n sm o r ef i m c t i o 璐o nc l u s t e r i n g a n a l y s i s t h em a l nc o n t r i b u t i o n so ft h i st h e s i si n c l u d et h ef o l l o w i n ga s p e c t s ： 1 w ep r o p o s ean o v e lm e t h o d ，c l u w i n ，t oc l u s t e rd a t as t r e a m so v e rs l i d i n gw i n - d o w s ，a n dan e ws y n o p s i sn a m e de x p o n e n t i a lh i s t o g r a mo fc l u s t e rf e a t u r e s m t om a i n t a i nt h es t a t i s t i ci n f o r m a t i o no fc l u s t e r si ns l i d i n gw i n d o w s c l u w i n a l g o r i t h mc a l lp r o v i d et h ec l u s t e r i n gr e s u l t si ns l i d i n gw i n d o w s ( w i n d o ws i z e = n ) w i t hr e l a t i v ee r r o rn om o r et h a n eb ym a i n t a i n i n gd ( l o g ( 4 - 芒1 ) ) t i m e c 1 u s t e r i n gf e a t u r es y n o p s e s i na d d i t i o n ，i th a sb e e ne x t e n d e dt od e a lw i t h c l u s t e r i n gp r o b l e m so v e rt h en - o f - ns l i d i n gw i n d o w ( a ne x t e n d e dm o d e lo f s l i d i n gw i n d o w ) ， 2 w ep r o p o s ean e wa p p r o a c h ，d e n s t r e a m ，t od i s c o v e rc l u s t e r sw i t ha r b i t r a r y s h a p e si ne v o l v i n gd a t as t r e a m s ，a n di n t r o d u c ead e n s em i c r o - c l u s t e r ( c a l l e d c o r e - m i c r o - c l u s t e r ) t od e s c r i b et h ea r b i t r a r y - s h a p e dc l u s t e r si nd a t as t r e a m s i na d d i t i o n ，w ep r o p o s ep o t e n t i a lc o r e - m i c r o - c l u s t e ra n do u t h e rm i c r o - c l u s t e r s y n o p s e st om a i n t a i na n dd i s t i n g u i s ht h ep o t e n t i a lc l u s t e r sa n do u t l i e r si n d a t as t r e a m s b a s e do nt h e s ec o n c e p t s ，d e n s t r e a mi n c l u d e san o v e lp r u n i n g s t r a t e g y , w h i c hc a nm a i n t a i na n d e n s u r et h ep r e c i s i o no ft h ew e i g h to fm i c r o - c l u s t e r sb ym e m o r ys p a c ew i t hl o gc o m p l e x i t y 3 w eu t i l i z et h ep o w e r f u l 。c h e a p e ra n dc h e a p e ra n dn o te n o t i g hc o n s i d e r e d g r a p h i cp r o c e s s i n gu n i t s ( g p u s ) t oc l u s t e rd a t as t r e a m s w ep r o p o s eag r o u p o ff a s tc l u s t e r i n gm e t h o d sv i ag p u s ，i n c l u d i n gt h eb a s i ck - m e a n sm e t h o d ， t h es t r e a mc l u s t e r i n ga l g o r i t h m ，a n dt h ee v o l v i n ga n a l y s i sm e t h o do v e rd a t a s t r e a m s t h ec o m m o nc h a r a c t e r i s t i c so ft h e s em e t h o d 8a r em a k i n gu s eo ft h e s t r o n gc o m p u t a t i o n a la n dp i p e l i n ep o w e ro fg p u s d i f f e r e n tf r o mp e r v i o u s c l u s t e r i n gm e t h o ( i sw i t hi n d i v i d u a lf r a m e w o r k o u rm e t h o d 8s h a r et h es a n l e f r a m e w o r kw i t hm u l t i - f u n c t i o n ，w h i c hp r o v i d e sau n i f o r mp l a t f o r mf o rs t r e a m c l u s t e r i n g 4 w ep r o p o s ean e wf r a m e w o r k ，c l u d i s t r e a m ，f o rc l u s t e r i n gd i s t r i b u t e dd a t a s t r e a m s ，w h i c hc a ne f f e c t i v e l yh a n d l eah u g ev o l u m eo fd a t ai nr e a l - t i m e ，t h e n o i s y , c o r r u p t e do ri n c o m p l e t ed a t ar e c o r d s ，t h eo v e r l a p p i n gp r o p e r t i e so fd a t a s e ti nd i s t r i b u t e dd a t as t r e a m s i nc l u d i s t r e a m ，t h ee m b a s e d ( e x p e c t a t i o n m a x i m i z a t i o n ) a l g o r i t h m s ，e a c hd a t ar e c o r di sa s s i g n e dt oac l u s t e rw i t hc e r - t a i nd e g r e eo fm e m b e r s h i p t h i ss o f tc l u s t e r i n gr e f l e c t sm o r en a t u r a l l yt h e o v e r l a p p i n gp r o p e r t yo ft h ec l u s t e r s i nt h ep r e s e n c eo fn o i s y , c o r r u p t e do r i n c o m p l e t ed a t ar e c o r d s ，o u ra l g o r i t h m sl e a r nt h ep a r a m e t e r sg o v e r n i n gt h e d i s t r i b u t i o no fu n d e r l y i n gd a t as t r e a m sb ym a x i m i z i n gt h el i k e l i h o o do ft h e d a t ac l u s t e r s m o r e o v e r ，at e s t - a n d - c l u s t e rs t r a t e g yi sp r o p o s e dt or e d u c et h e a v e r a g ep r o c e s s i n gc o s t ，w h i c hi se s p e c i a l l ye f f e c t i v ef o ro n l i n ec l u s t e r i n go v e r l a r g ed a t as t r e a m s a ui na 1 1 w es t u d yf o u rp r i n c i p a lp r o b l e m so fc l u s t e r i n gd a t as t r e a m sa n d p r o p o s en o v e ls o l u t i o n 8f o rt h e mi nt h i st h e s i s s i n c es l i d i n gw i n d o wi s ab a s i c m o d e lf o rp r o c e s s i n gd a t as t r e a m s ，h o wt oc l u s t e rd a t as t r e a m so v e rs l i d i n gw i n - d o w sb e c o m e sab a s i cp r o b l e m ；a r b i t r a r y - s h a p e dc l u s t e r sm o d e li sm o r eg e n e r a l t h a ns p h e r i c a ld u s t e r sm o d e l ，t h e r e f o r ed i s c o v e r ya r b i t r a r y - s h a p e dc l u s t e r si nd a t a s t r e a m si sab a s i cp r o b l e m ；t h ec h a r a c t e r i s t i co fo n l i n em i n i n gm a k e sh o wt oi m p r o v e t h ep r o c e s s i n gs p e e do fa l g o r i t h mab a s i ci s s u ei nc l u s t e r i n gd a t as t r e a m s ；c l u s t e r - i n gd i s t r i b u t e dd a t as t r e a m si sab a s i cp r o b l e m ，b e c a u s ei nr e a ll i f ea p p l i c a t i o n s ， t h ed a t as t r e a m sa r eo f t e ng e n e r a t e di nad i s t r i b u t e de n v i r o n m e n t o u rm e t h o d s a r eg r e a tc o m p l e m e n t a r i t ya n di m p r o v e m e n tt oe x i s t i n gs t r e a mc l u s t e r i n gm e t h o d s t h e o r e t i ca n a l y s i sa n de x p e r i m e n t a lr e s u l t ss h o wt h a to u rm e t h o d sc a ns o l v et h e i r c o r r e s p o n d i n gp r o b l e m se f f i c i e n t l ya n do u t p e r f o r mp r e v i o u sc l u s t e r i n gm e t h o d si n s p a c ec o m p l e x i t y , p r o c e s s i n gr a t ea n dr e s u l tq u a l i t y 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 ，e v o l v i n g ，w i n d o w ，g r a p h i cp r o c e s s i n gu n i t v 图目录 1 1 数据流挖掘框架结构图 2 1 概率分布的小尾巴性质1 4 3 1 数据流中簇的进化2 3 3 2 微簇的形成2 4 3 3e h c f 的维护过程：e = 0 5 2 7 3 4e h c f 树3 0 3 5 迟后合并3 1 3 6 e h c f 与金字塔时间框架的比较3 2 3 7 聚类质量比较( 网络入侵检测数据集，窗口大小= 1 0 ，0 0 0 ) 4 0 3 8 聚类质量比较( 网络入侵检测数据集，窗口大小= 4 0 ，0 0 0 ) 4 0 3 9 聚类质量比较( 慈善捐赠数据集，窗口大小= 4 0 0 0 ) 4 0 3 1 0 聚类质量比较( 慈善捐赠数据集，窗口大小= 1 2 ，0 0 0 ) 。4 0 3 1 l 内存消耗随窗口大小变化( 网络入侵检测数据集) 4 1 3 1 2 内存消耗随窗口大小变化( 慈善捐赠数据集) 4 1 3 1 3 内存消耗随e 变化( 网络入侵数据集)4 1 3 1 4 执行时间随数据流长度变化( 网络入侵检测数据集) 4 2 3 1 5 执行时间随数据流长度变化( 慈善捐赠数据集) 4 2 3 1 6 执行时间随簇个数k 变化。4 2 3 1 7 执行时间随维度d 变化4 2 3 1 8e h c f 率对聚类质量的影响4 3 3 1 9 误差参数f 对聚类质量的影响4 3 3 2 0 跟踪簇4 4 4 1 通过核心微簇c - m i c r o - c l u s t e r s 表示簇 4 2 a d 与m d 的比较 4 3 交叠的问题 x 4 8 5 4 5 6 图目录 4 4 人工数据集 4 5 对数据集d s l ，d s 2 ，d s 3 的聚类 4 6 对进化数据流e d s 的聚类， 4 7 对含噪声数据流的聚类 4 8 聚类质量( e d s 数据集，h = 2 ，流速= 2 0 0 0 ) 4 9 聚类质量( e d s 数据集，h = 1 0 ，流速= 1 0 0 0 ) ， 4 1 0 聚类质量( 网络入侵检测数据集，h = i ，流速= 1 0 0 0 ) 4 1 l 聚类质量( 网络入侵检测数据集，h = 5 ，流速= 1 0 0 0 ) ， 4 1 2 聚类质量( 含l 噪声e d s 数据集，h = 2 ，流速= 2 0 0 0 ) 4 1 3 聚类质量( 含5 噪声e d s 数据集，h = 1 0 ，流速= 1 0 0 0 ) 4 1 4 执行时间随数据流长度变化( 网络入侵检测数据集) 4 1 5 执行时间随数据流长度变化( 慈善捐赠数据集) 4 1 6 执行时间随簇个数k 变化 4 1 7 执行时间随维度d 变化 4 1 8 内存消耗 4 1 9 聚类质量随衰减因子a 变化 4 2 0 聚类质量随离群点阈值口变化 5 1 图形处理流水线简图6 8 5 2 以对象为中心和以中心点为中心的计算7 3 5 3 标号过程。7 3 5 4 各聚类算法中的相对代价，7 7 5 5 基于g p u 和基于c p u 的聚类比较8 0 5 6 产生中心点代价与数据取回代价8 l 5 7 g p u _ l 的数据取回代价与单次循环代价8 l 5 8 聚类代价随簇个数k 变化8 1 5 9 聚类代价随维度d 变化8 1 5 1 0 基于g p u 和基于c p u 数据流界标窗口的聚类比较8 2 5 1 1 滑动窗口聚类效率比较8 3 5 1 2 基于g p u 和基于c p u 簇迸化在线聚类性能，8 3 6 1 分布式数据流体系结构8 8 6 2 合并标准厶。与 4 一。的比较，9 5 6 3 通讯代价( i t a 数据集) 9 9 6 4 通讯代价( 人工数据集) 9 9 6 5 人工数据集的直方图1 0 0 6 6 聚类结果图形化显示1 0 0 耵黝n缸；眈眈；田斛以 图目录 6 7 一段时间窗口内的聚类质量( 1 7 r a 数据集)，1 0 1 6 8 一段时间窗口内的聚类质量( 人工数据集) 1 0 1 6 9 界标窗口内的聚类质量( i t a 数据集) 1 0 2 6 1 0 界标窗口内的聚类质量( 人工数据集) ，1 0 2 6 1 l 协调站点的聚类质量( i t a 数据集) 1 0 2 6 1 2 协调站点的聚类质量( 人工数据集) 1 0 2 6 1 3 处理时间随更新次数变化( i i a 数据集) 1 0 3 6 1 4 处理时间随更新次数变化( 人工数据集)1 0 3 6 1 5 处理时间随产生新分布的概率局变化( 人工数据集) 1 0 4 6 1 6 处理时间随簇个数k 变化1 0 4 6 1 7 处理时间随维度d 变化，1 0 4 6 1 8 内存随更新次数变化1 0 5 6 1 9 内存随簇个数k 变化1 0 5 6 2 0 聚类质量随e 变化1 0 5 6 2 1 处理时间随e 变化，1 0 5 6 2 2 聚类质量随6 变化1 0 6 6 2 3 处理时间随d 变化1 0 6 6 2 4 处理时间随最大测试次数c r 变化( i t a 数据集) 1 0 6 6 2 5 处理时间随最大测试次数c m d 。变化( 人工数据集) 1 0 6 表目录 5 1 算法名称缩写，7 9 第一章 引言 1 1 数据流挖掘概述 1 1 1 研究背景 现代计算机网络和传感器网络技术的快速发展引发了一类具有广阔发展前景 的新数据库一数据流一应用，从环境和天文监测、计算机网络监控、金融股票交 易到网页搜索日志分析等。该类应用中，海量数据以实时方式快速到达。下面列 举了几个数据流常见的应用场景。 1 传感器网络( s e n s o rn e t w o r k ) 目前已经广泛分布于各种地理环境中，如热 带雨林、江河流域以及高速公路等，用于地理信息监测、生命信号检测、车 辆运动跟踪和交通拥塞检测等。在传感器网络中，大量传感器每时每刻不 断感应出大量监测数据，并通过无线网络传输到集站。集站中的数据分析 服务器必须及时地对这些监测数据进行分析和处理。 2 计算机网络实时交互着大量的及时通讯消息、电子邮件、在线视频等数 据。这些数据被封装为各种i p 数据包通过局域网( 或广域网) 从源地址 传送到目标地址。作为网络连接节点的路由器、交换机等设备需要极快 地传输这些i p 数据包，例如c i s c o 公司的w s c 6 5 0 3 交换机最高背板带宽高 达7 2 0 g b p s 。因特网服务提供商( 例如中国网通) 需要从交换机设备中获取 这些实时i p 数据包并进行分析挖掘，从而实现对计算机网络的监控和维护。 3 金融股市交易着成千上万种价格瞬息万变的股票和基金。与此同时，世界各 地各种政治、经济、文化新闻和突发事件不断涌现它们直接或间接影响 着这些股票和基金的价格。仅据美 n y s e 、a m s e 、n a s d a q 并i s m a u c a p 1 1 引言 四个股票交易所的不完全统计信息，上市股票的日常交易数据和报价数据以 每月1 0 g b 的速率增长。股票交易所、证券公司需要不断实时获取各种股票 和基金的价格以及各种新闻信息，并在此基础上进行大量的复杂实时分析挖 掘，如股票关联关系的发现、股价趋势分析、走势预测等。更快地获取更 多信息就意味着更好的财富机会和更小的金融风险。 4 网页搜索目前已形成了一种新兴产业。例如百度公司每天都需要对8 亿多中 文网页完成上亿次搜索，g o o g l e 公司每天需要对全球6 0 多亿网页完成2 亿次 搜索。( 2 0 0 5 年度中国搜索引擎市场报告显示2 0 0 6 年中国网页搜索用户 数比2 0 0 5 年增长2 2 6 7 0 ，并还将以每年1 1 以上的速度递增。这些不断增长 的页面搜索请求为网络搜索公司带来了巨大网络流量的同时，给公司网站的 事务日志留下大量的搜集记录。如何对这些搜索记录进行实时分析处理， 以带来更好的用户体验和更为强大的搜索功能，是每个网络搜索公司不断追 求的目标。 可以看到，上述各种应用场景的共同特点是海量数据实时快速到达学术界 把具有这种特征的新兴数据库称为数据流。数据流相对于传统数据库( 例如基于 磁盘的数据库) 已成为一种新兴且日益主流的数据存在方式人们迫切需要从这 些包含有大量数据的数据流中提取有价值的信息和知识。因而，数据流的分析和 挖掘日益成为个热点问题。 作为一种基础且重要的数据挖掘手段【6 9 1 ，数据流环境下的聚类分析得到了学 术界和工业界的广泛关注。聚类挖掘就是把数据集合中的数据对象归为若干组不 同的类( 簇) ，并使得组内对象的相似度尽可能的高而组间对象的相似度尽可能 的低f 6 9 】。在传统数据库中，数据聚类已经在图像处理、模式识别、空间数据分 析、市场调研等领域取得了实际应用【7 0 】。在数据流环境中，数据聚类同样是一 种重要的并具强大信息提取功能的数据约减技术，例如： 1 在线聚类传感器网络中的传感数据，可实现地理环境、交通拥塞等的实时 监控和模式挖掘。例如，交通拥塞往往对应于交通监测数据中某新簇的出 现，或具有相似地理信息簇所包含记录数量的大幅增加。 2 对因特网数据、事务日志进行在线聚类，可用于监测网络入侵、网络点击欺 诈、网络异常等现象例如，网络入侵往往对应着包含一个或多个具有相 似源或目的地址i p 包簇的快速形成。 3 在线聚类金融数据，可实现金融欺诈检测，消费者分布状况统计以及为金融 走势预测提供支持。例如，金融数据簇的变化，往往代表着消费者分布状 况的改变，新消费模式的形成以及金融走势出现新变化。 2 1 引言 4 对天文数据进行在线聚类，可及时发现新的天文现象。例如，天文观测数 据新簇的出现，往往对应着宇宙高速粒子流、超新星爆发或新星际云团的形 成等。 1 1 2 数据流挖掘与传统数据挖掘的不同 数据挖掘是信息技术自然演化的结果 6 1 1 。从最初的统计数据分析阶段到机 器学习阶段，再到大规模数据集挖掘，数据挖掘技术已历经了三个阶段的发展。 随着更快的传感器和计算机网络硬件的出现，数据挖掘研究迎来了其发展史上的 第四阶段一数据流挖掘阶段在线发掘数据流的数据模型将更有利于人们做出更 好的决策和及时发现新出现的有趣现象。 数据流的数据量以惊人速度持续不断增长对数据挖掘技术提出了新的挑战。 海量数据高速到达使得传统数据挖掘技术对数据集中所有数据反复进行操作的做 法不再可行。数据流挖掘对挖掘算法提出了一系列新要求。总的来说，数据流 挖掘算法必须以增量方式跟踪数据流的变化，同时不能占用过多的计算和内存资 源 1 3 ，17 1 。下面概括了数据流挖掘与传统数据挖掘主要的不同之处。这些差别 归根结底是由数据流无限增长的数据量和数据快速到达特性所造成的。 1 由于数据量无限增长，对数据流的扫描次数仅限于单遍，即除非刻意保存， 每个数据只可以被处理一次。而在传统数据挖掘中，数据集通常保存在数 据文件中，可对数据集进行多遍扫描 2 数据流的快速流动性要求算法对数据的分析处理速度不能低于数据流动的速 度，因而算法对新数据的处理时间是严格受限的。而在传统数据挖掘中， 数据静态保存在数据库中，对算法的处理时间并无此限制。 3 相对于数据流的无限数据量，系统中的内存容量是微不足道的，因而对数据 流挖掘算法来说，空间复杂度是严格受限的。算法的空间复杂度通常被要 求在o ( p o l y ( 1 0 9 ) ) 范围内。而传统数据挖掘可反复将数据库中的数据装载 到内存中，对算法的空间复杂度并没有严格限制。 4 数据流数据量的无限性使得数据流挖掘往往无法保留原始数据，仅能在内存 中维护原始数据的一系列概要信息，并基于这些概要信息生成最终结果。 数据流挖掘结果往往是有一定允许误差的近似结果。而在传统数据挖掘 中，数据量相对较小，且无处理时间、扫描遍数等限制，因而可获得相对准 确的挖掘结果。 5 数据流动态环境下，数据底层分布模型会受现实应用中各种因素的干扰( 如 网络黑客入侵，传感器网络外部环境的改变等) 而随着时间不断改变，即数 3 1 引言 图1 1 ：数据流挖掘框架结构图 据流通常是不断进化的。因而，数据流挖掘中的概念模型通常为多个。而 传统数据挖掘通常是对数据库中静态数据进行挖掘，这些数据往往符合同一 分布模型，所以传统数据挖掘中的概念模型通常是一个。 1 1 3 数据流计算模型 数据流可看作是一个不断增长的d 维元组t 集合 高冠) ，对任意 ( 1 ) 趸= ( z k 彰) ，各元组的时标为丑互且对任意f m ，正 0 ) 随时间t 不断衰减。 在实际应用中这三种窗口模型的选取往往根据用户的需求而定无论具体采 用哪一种( 或几种) 窗口模型，数据流挖掘都具有相同的挖掘框架，如图1 1 所 示。 在该框架中，数据流挖掘算法需在内存中维护一个概要数据结构( s y n o p s i s d a t as t r u c t u r e ) 【5 0 。数据流挖掘算法从数据流中不断接收新到达的元组m 。当 4 1 引言 处理一个新元组时，挖掘算法通过增量计算更新概要数据结构。当接收到挖掘请 求时( 也可能是连续挖掘请求) ，挖掘算