（计算机软件与理论专业论文）基于数据流的聚类分析研究及应用.pdf

山东师范大学硕士学位论文 摘要 数据挖掘，又称数据库中的知识发现，是指从大型数据库或数据仓库中提 取隐含的、事先未知的、潜在有用的信息或模式。它融合了数据库、人工智能、 机器学习和统计学等多个领域的理论和技术，是数据库研究中的一个很有应用 价值的新领域。而聚类分析是数据挖掘中很重要的分析手段。聚类，是按照给 定的相似度定义将数据集合划分为若干个聚类簇，使得同簇的数据之间相似度 较高而不同簇的数据之间相似度较低的过程。 近年来，由于计算机及应用技术的高速发展，人们获取数据的能力得到极大 的提高，数据流( d a t as t r e a m s ) 作为一类重要的数据来源，受到越来越多的关 注，基于数据流模型的管理系统及其算法己成为重要的应用前沿课题。 数据流是一组顺序的、大量的、快速的、连续到达的数据序列。一般情况 下，数据流可以被视为一个随时间延续而无限增长的动态数据集合，对流中数 据的访问代价通常比较高，因此仅一次地访问数据成为数据流算法所追求的目 标。数据流的特性对传统聚类方法提出了许多新的挑战，如：仅一次地扫描数 据流并产生高质量的聚类结果，任意时间段内的窗口分析，等等。近些年来， 数据流聚类算法逐渐开始向分层的算法框架发展。分层聚类算法通常将算法结 构分为“在线层 和“离线层”两个部分：在线算法负责对流数据进行快速但 较为粗糙的处理，通过保存概要数据信息而避免后续过程对数据的回溯访问； 离线算法利用在线层保留下来的概要信息进行更高层次的精确分析，并最终得 到聚类结果。当前，数据流聚类算法尚且面临着以下一些较难解决的问题：分 割数据流造成全局信息缺损从而影响聚类效果、时间复杂度较高、难以实现有 效的基于密度聚类从而发现数据空间中不规则分布的高密度区域，等等。 本文针对数据流聚类算法进行了深入的研究，基于双层数据流聚类算法框 架提出了若干方法用以解决或改善上述问题，主要包括以下几部分内容： 1 ) 数据流表达是在线层算法研究中的一个重要问题，直接影响到算法的处 理方式及算法效率。传统的模型如：界标模型，滑动窗口模型和快照模型都属 于基于数据压缩的表达方式，它们针对数据本身的数值进行计算处理，得到远 远小于原始数据空间的映射空间，此模式不能很好的反映空间分布。本文提出 的微簇结构能够通过记录数据的分布获取更多的信息，同时可以进一步降低算 山东师范大学硕士学位论文 法的存储需求。通过保存数据本身使其在以后的处理中可以动态调整所属划分， 从而更好地反映出空问分布的变化。 2 ) 在线算法向离线算法输出中间数据。本文初始完全划分和算法后来非完 全划分相结合的策略，因为局部空间中的高密度区域通常也对应着全局空间中 的密集区域的原则，于是把局部空间中的高密度区域进行输出，而将其他的稀 疏数据留在内存中与后续数据一起处理。故初始的完全划分的簇最后密度高的 话就输出，而密度低的就分割与后续数据一起处理。这种划分策略能够提高在 线层的输出质量，进而得到更好的聚类结果。 3 ) 提出一种改进的双层流数据聚类算法s c l u s t r e a m ，聚类结果能够较真实 的反映出数据的空间分布。在对数据流进行初步聚类的同时，尽量保留数据的 分布特征，对流数据的动态特性表现出更强的适应性。实验结果表明，算法能 够保持较低的时间开销并得到质量较高的聚类结果。 4 ) 本文提出了一种新算法d e n c l u s t r e a m 用于挖掘数据流中具有任意形状 的簇我们把密度函数以权值的形式引入数据结构中，并利用核心微簇描述数据 流中任意形状的簇，并提出候选核心微簇和孤立微簇结构分别用于维护并区分 数据流中潜在的核心簇和孤立点。在线层输出的结果在离线层用“多维球簇” 进行保存，节省了外存空间。 另外，本文初步探讨了聚类分析算法的应用，分析目前聚类分析算法应用 的现状，展望应用前景，为以后研究做基础。 关键词：数据流聚类分析双层框架密度函数 山东师范大学硕士学位论文 a b s t r a c t d a t am i n i n g ，a l s or e f e h e dt oa sk n o w l e d g ed i s c 0 v e r yf 如md a t a b a s e ，i st o a b s t r a c tt h ep o t e n t i a l ，u n k n o w na n du s e f u li n f o 册a t i o no rp a t t e mf f o mt h e1 a r g e d a t a b a s eo rd a t aw a r e h o u s e i ti n t e g r a t e st h et h e o “e sa n dt e c h n o l o g i e so fd a t a b a s e ， a r t i f i c i a l i n t e l l i g e n c e ，m a c h i n el e a m i n ga n ds t a t i s t i c se t c a n di ti sav e r yp r o m i s i n g s t u d yf i e l di nt h er e s e a r c ho fd a t a b a s ew i t ht h eh i g hv a l u a b l ea p p l i c a t i o n c l u s t e r i n g a n a l y s i s i so n eo ft h em o s ti m p o n a n tt e c h n o l o g i e si nd a t am i n i n g c l u s t e r i n g a l g o r i t h m sp a n i t i o nad a t as e ti n t os e v e r a ld i s j o i n tg r o u p ss u c ht h a tp o i n t si n t h e s a m eg r o u pa r es i m i l a rt oe a c ho t h e ra c c o r d i n gt os o m es i m i l a r i t ym e t f i c i nr e c e n ty e a r s ，b e c a u s eo fc o m p u t e fa n da p p l yat e c h n i c a lh i g l ls p e e d d e v e l o p m e n t ，p e o p l eo b t a i nt h e 乏i b i l i t y0 fd a t at og e ta t r e m e n d o u se x a l t a t i o n ，d a t a s t r e a m si sat y p eo fi m p o n a n td a t as o u r c e ，a n di ss u b j e c t e dt om o r ea n dm o r e c o n c e m ，m a n a g e m e n ts y s t e ma n d i t sa l g o r i t h mb a s e do nd a t as t r e 锄sm o d e lh a v e b e c o m ea ni m p o n a n ta p p l i e dt o p i c ad a t as t r e a mi sa no r d e r e ds e q u e n c eo fh i g l l - s p e e dp o i n t sw h i c ha r ec o m i n g c o n t i n u o u s l y u s u a 儿yad a t as t r e a mc a nb er e g a r d e da sad y n a m i cd a t as e t ，t h es c a l e o fw h i c hi n c r e a s e si n f j n i t e l yw i t ht h el a p s eo ft i m e a sar e s u l t ，i ti st o oe x p e n s i v et 0 a c c e s sap o i n ti ns t r e a mf a n d o m l y ，a n dt h u sf e q u i r i n gas i n 班es c a no v e rt h es t r e a m h a sb e c o m ea no b j e c to ft h ec l u s t e f i n ga l g o f i t h m s c l u s t e r i n go ns t r e a m i n gd a t a b r i n g sf o r w a r dc h a l l e n g e s f o rt r a d i t i o n a l a l g o r i t h m si n t h ef o l l o w i n ga s p e c t s ： o b t a i n i n gl l i g l lq u a l i t yc l u s t e r sb yo n l yo n e - p a s so v e rt h ed a t a ；t i m e w i n d o wa n a l y s i s o v e ra na r b i t r a r yp e f i o do ft h es t r e a me t c i nr e c e n ty e a r s ，s t r e a ma l g o r i t h m sh a v e d e v e l o p e di n t oat w o p h a s es t r u c t u r e u s u a l l y ad u a lf r a m e w o r ki n c l u d e st w op a r 乏s ： t h e 伽一l i n ec o m p o n e n ta n dt h eo 搏l i n ec o m p o n e n t t h ef 6 珊e ri sr e s p o n s i b l ef o rt h e f a s tb u tr o u 曲p r o c e s s i n go fs t r e a i i l i n gd a t aa n ds a v i n gt h es u m m a r yi n f o 姗a t i o nt o m e e tt h eo n e - p a s sr e s t d c t i o nw h i l et h el a t t e rt a k e sa d v a n t a g eo ft h ei n f o r i l l a t i o nt o c o n d u c th i 曲- l e v e la n a l y s i s a tp r e s e n t ，s t r e a ma l g o r i t h m sa r es t i l lf a c i n gs o m e p r o b l e m s ，f o re x a m p l e ：b a dq u a l i l yo fc l u s t e r sd u et ot h el o s so f 垂o b a li n f o r i n a t i o n c a u s e db yd i v i d i n gt h es t r e a m ；h i g ht i m ec o m p l e x i t ye t c t h i sp a p e rh a sm a d eap r o f o u n dr e a c h 咖t h ec l u s t e r i n ga l g o r i t h m so nd a t a s t r e a m ，a i l dp u tf o r w a r ds o m em e t h o d sb a s e do nt h ed u a l t i e rf r 锄e w o r kt os o l v et h e p i d b l e m sa b o v e ，i n c l u d j n g ： 1 ) t h ee x p r e s s i o no ft h ed a t ai sa ni m p o f a n tp r o b l e mi nt h eo n - l i n ea l g o r i t h m ， i tw i l li n n u e n c et h em e t h o dw i t hw h i c ht h ea l g o r i t h mh a n d l et h ed a t aa n dt h e 山东师范大学硕士学位论文 e f f i c i e n c y i _ n d m a r km o d e l ，s l i d i n gw i n d o wm o d e la n dt h es n a p s h o tm o d e la r ea n e x p r e s s i o n sb a s e do nt h ed a t ac o m p r e s s i n g ，t h e ym a p p i n gt h ed a t ai n t oam u c h s m a l l e rs p a c ea c c o r d i n gt ot h ev a l u eo ft h ed a t a t h em i c r o - c l u s t e rc a no b t a i nm o r e i n f b n n a t i o na b o u tt h ed a t ab yr e c o r d i n gt h ed i s t r i b u t i o no ft h ep o i n t s ，s oa st og e ta l o w e rr e q u i r e m e n to ft h es t o r a g e t h i sp a p e rp r o m p t sat y p eo ft h em i c r o c l u s t e f ， w h i c hs t o r e st h ep o i n t si ni t t h e r e f o r e ，t h ep r o i n t sc a nb em o v e di nt h ea f t e rp r o c e s s t or e f l e c tt h ec h a n g eo ft h ed a t ad i s t r i b u t i o nb e t t e r 2 ) t h eo n - l i n ea l g o r i t h mo u t p u t st h em i d - d a t a ，w h i c ht h eo f - l i n ea l g o r i t h mg e t s a st h ei n p u t t h i sp a p e rp r o m p t sa nm i xs t f a t e g yt h a tb e g i n i n gu s ec o m p l e t e p a r t i t i o n s t r a t e g ya n da f t e n a r d su s ea ni n c o m p l e t e p a n i t i o ns t r a t e g y 1 h i si sb a s e do nt h e l e m m at h a tt h ed e n s ea r e a si nt h e1 0 c a ls p a c ea l w a y sc o r r e s p o n dt od e n s ea r e a si n t h e 酉o b a ls p a c e a n dt h eo t h e rp o i n t sr e m a i n i n gi nt h em e m o r ya r ew a i t i n gf o rt h e f h t u r et r e a t m e n tt o g e t h e rw i t hl a t e rp o i n t s t h ep a s tb e g i n n i n gs t a r t so fc o m p l e t e d i v i d et h el i n eo fc l u s t e rw h i c he n dt h ed e n s i t yi fi sh i g ho u t p u t ，b u tt h ep a n i t i o ni t s d e n s i t yi sl o ww i l lt oh a l l d l ew i t hf o l l o w u pd a t at o g e t h e r t l l l ss t m t e g yc a ni m p r o v e t h eq u a l i t yo ft h em i d - d a t af r o mt h eo n l i n et i e r ，a n dt h u s ，t h ea l g o r i t h mc a l lg e t b e t t e rd u s t e r i n gr e s u l t s 3 ) ai m p r 0 v ed u a l t i e rc 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 s ，s c l u s t f e a m ，i s p r o p o s e di n t h i sp a p e li tc a nr e n e c tt h ed i s t r i b u t i o ni nr e a ld a t as p a c eb e t t e lt h e a l g o r i t h mm a i n t a i nt h eg l o b a li n f o 册a t i o nm o r ce f 琵c t i v e l yw h e nf i r s t l yd u s t e r i n g d a t as t r e 锄s t h i sm a k e st h es c l u s t r e a mh a v eas t r o n g e ra d a p t a b i l i t yt ot h e d y n a m i c c h a r a c t e r i s t i c0 ft h es t r e a m t h ee m p i r i c a le v i d e n c es h o w st h a tt h i sm e t h o d c a no b t a i nh i 曲一q u a l i t y 4 ) t 1 l i sp a p e rp u t sf o n v a r dan e wa l g o r i t h m ，d e n c l u s t r e a m ，w h i c hc 柏b eu s e d t od a t am i n i n gt h ea r b i t r a r ys h a p ec l u s t e rf o rd a t as t r e a m w el e dt h ed e n s i t y f i l n c t i o ni n t ot h ed a t as t n l c t u r ea st h ew e i g l l t ，a n du s ed e n s em i c r o c l u s t e rt o d 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 e p r o p o s e c a n d i d a t ec o r e m i c r o c l u s t e ra n di s o l a t e dm i c r o - c l u s t e rs y n o p s e st om a i n t a i na n d d i s t i n g l l i s ht h ep o t e n t i a lm i c r 0c l u s t e r sa n di s o l a t i o np o i n ti nd a t as t r e a m s t h er e s u l t o n - l i n eo u t p u t t e di ss a v e da sh i g l ld i m e n s i o n a lb a 儿c l u s t e ra to u t - l i n e ，a n dc o n s e e t h es a v es p a c e h 1 a d d i t i o n ， t h i s p a p e f d i s c u s st h e印p l i c a t i o na b o u tc l u s t e ra 1 9 0 r i t h m p r o v i s i o n a u y ；a n da n a l y z ea p p l yc u r r e n ts i t u a t i o no fc l u s t e ra l g o r i t h mp r e s e n t l y i t 山东师范大学硕士学位论文 l o o k sf b 删a r da p p l i c a t i o np r o s p e c tf o r t h es t u d yi nf u t u r e k e y ：d a t as t r e a m c l u s t e r i n g d u a l t i e rf r a m e w o r k d e n s i t yf u n c t i o n v 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含为获得( 注：如没有其他需要特别声明的，本 栏可空) 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 侮儋商 学位论文版权使用授权书 导师签字： 本学位论文作者完全了解堂撞有关保留、使用学位论文的规定，有权保留并向国家 有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权堂撞可以 将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复 制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 蘑谚侵 签字日期：2 0 0 芬年月 o 日 导师签 签字日期：2 0 0 髫年期弘日 山东师范大学硕士学位论文 1 1 论文研究的背景 第一章绪论 近年来，由于计算机及应用技术的高速发展，人们获取数据的能力得到极大 的提高，数据流( d a t as t r e 鲫s ) 作为一类重要的数据来源，受到越来越多的关 注，基于数据流模型的管理系统及其算法已成为重要的应用前沿课题u 31 。大 型超市交易记录数据、股票交易所的股票价格、股票交易信息数据、网络检测 数据、电信部门的通话记录数据、信用卡交易流、传感器传回的数据等均可以 看作基于数据流模型的数据集。它们具有数据量大、连续的、有序的、到达速 率不确定等特点，若对这类数据按传统的数据库应用模式处理这些数据，即完 整、详细地收集这些数据，预处理后将其储存在数据库中，再交由计算机仔细处理 已成为不可能完成的任务。由有限的数据到有限的数据处理能力，计算机工作者 们面临着新的挑战。因此迫切需要提出高效、可行的基于数据流模型的算法， 使得在给定的有限的运行空间上，能够通过对数据流进行一次或较少次数的线 性扫描，对其进行管理以及进一步的知识发现。 针对如何分析管理这种大量快速的数据问题，人们提出了一类新型应用作 为解决方案。在数据流挖掘方面，如何在数据流中进行有效聚类，是一个吸引了 研究者很大注意力的问题。数据流聚类分析是数据流挖掘的一个重要工具，研 究如何对数据流进行有效的聚类对从大量数据中提取有用信息具有很大的意 义，对有效节省存储空间具有很深的理论意义和现实价值，对商务决策者进行 决策及网络的实时检测等都具有很大的现实意义。 1 2 聚类 聚类就是将数据对象分组成为多个类或簇，在同一个簇中的对象之间具有 较高的相似度，而不用簇中的对象差别较大。或者说所谓聚类就是：将物理或 抽象对象的集合分组成为由类似的对象组成的多个类的过程。 作为统计学的一个分支，聚类分析已经被广泛地研究了很多年，主要集中 山东师范大学硕士学位论文 在基于距离的聚类分析，如k m e a n s 、k m e d o i d s 等。另外一类是概念聚类 ( c o n c e p t u a lc l u s t e r i n g ) ，一组对象只有当他们可以被一个概念描述时才形 成一个簇。它不同于基于几何距离来度量相似度的传统聚类。概念聚类由两个 部分组成：( 1 ) 发现合适的簇；( 2 ) 形成对每个簇的描述。 聚类的应用相当广泛，在商务上，聚类能帮助市场分析人员从客户基本库 中发现不同的客户群，并且用购买模式来刻画不同的客户群的特征。在生物学 上，聚类能用于推导植物和动物的分类，对基因进行分类，获得对种群中固有 结构的认识。聚类在地球观测数据库中相似地区的确定，汽车保险单持有者的 分组，及根据房子的类型，价值和地理位置对一个城市中房屋的分组也可以发 挥作用。聚类也能用于对w e b 上的分档进行分类，以发现信息。作为一个数据 挖据的功能，聚类分析能作为一个独立的工具来获得数据分布的情况，观察每 个簇的特点，集中对特定的某些簇做进一步的分析。此外，聚类分析可以作为 其他算法( 如特征和分类等) 的预处理步骤，这些算法再在生成的簇上进行处 理。 目前，已经有大量的聚类算法。算法的选择取决于数据的类型，聚类的目 的和应用。大体上来看，主要的聚类算法可以划分成以下几类： ( 1 ) 划分方法( p a r t i t i o n i n gm e t h o d ) ：给定一个n 个对象或元组的数据 库，一个划分方法构造数据的k 个划分，每一个划分代表一个聚簇，并且k n 。 它将数据划分为k 个组，同时满足如下的要求：1 ) 每个组至少包含一个对象； 2 ) 每个对象必须属于且只属于一个组。为了达到全局最优，基于划分的聚类会 要求穷举所有可能的划分。 ( 2 ) 层次的方法( h i e r a r c h i c a lm e t h o d ) ：层次的方法对给定数据对象 集合进行层次的分解。根据层次的分解如何形成，层次的方法可以分为凝聚的 ( a g g l o m e r a t i v eo rm e r g i n g ) 和分裂的( d i v i s i v eo rs p l i t t i n g ) 两种类型。 凝聚的方法，也称为自底向上的方法，一开始将每个对象作为单独的一个组， 然后相继地合并相近的对象或组，直到所有的组合并为一个，或者达到一个终 止条件。分裂的方法，也成为自顶向下的方法，开始时将所有的对象置于一个 簇中。在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单 独的一个簇中，或者达到一个终止条件。 层次方法的缺陷在于，一旦一个步骤完成，就不能够被撤销。有两种方法 山东师范大学硕士学位论文 可以改进层次聚类的结果：( i ) 在每层划分中，仔细分析对象间的“联接”， 例如c u r e 和c h a m e l e o n 中的做法；( ii ) 综合层次凝聚和迭代的重定位方法， 首先用自底向上的层次算法，然后用迭代的重定位来改进结果。 层次法适合于具有树枝状结构的数据集合。 ( 3 ) 基于密度的方法( d e n s i t y _ b a s e dm e t h o d ) ：由于基于对象之间的距 离进行聚类的划分方法只能发现球状的簇，而提出了基于密度的聚类方法，它 能够发现任意形状的簇。其主要思想是：只要邻近区域的密度( 对象或数据点 的数目) 超过某个阈值，就继续聚类。也就是说，对给定类中的每个数据点， 在一个给定范围的区域中必须至少包含某个数目的点。这样的方法可以用来过 滤“噪声”孤立点数据，发现任意形状的簇。d b s c a n ( d e n s i t y - b a s e ds p a t i a l c 1 u s t e r i n go fa p p l i c a t i o n sw i t hn o i s e ) n 日是一个有代表性的基于密度的方 法，它根据一个密度阈值来控制簇的增长。 ( 4 ) 基于网格的方法( g r i d _ b a s e dm e t h o d ) ：基于网格的方法把对象空 间量化为有限数目的单元，形成了一个网络结构。所有的聚类操作都在这个网 格结构上进行。这种方法的主要优点是它的处理速度很快，其处理时间独立于 数据对象的数目，只与量化空间中每一维的单元数目有关。s t i n g 算法是这类 方法中的典型。 ( 5 ) 基于模型的方法( m o d e l - b a s e dm e t h o d ) ：基于模型的方法为每个簇 假定了一个模型，寻找数据对给定模型的最佳拟合。一个基于模型的算法可能 通过构建反映数据点空间分布的密度函数来定位聚类。它也基于标准的统计数 字自动决定聚类的数目，考虑“噪声”数据或孤立点，从而产生健壮的聚类方 法。统计学方法和神经网络方法都属于基于模型的方法。 对于任何一种聚类算法，其聚类结果的合理性和有效性都有待于评价，如 何评价这些结果主要依赖于不同的应用领域对聚类不同的考察标准。数据挖掘 对聚类的典型要求如下： 1 ) 可伸缩性：可伸缩性考察聚类算法对于目标对象集合的规模以及目标集 合潜在的模式数量的适应性。 一 2 ) 处理不同类型属性的能力：除了聚类数值型的数据外，应用当中可能要 求聚类其它类型的数据，如：二元类型，分类标称类型，序数型，或者不同数 据类型的混合。 山东师范大学硕士学位论文 3 ) 发现任意形状的聚类：许多聚类算法基于欧几里德距离或者曼哈坦距离 度量来决定聚类。基于这种距离度量的算法趋向于发现具有相近尺度和密度的 球状簇。但是一个簇可能是任意形状的，提出能发现任意形状簇的算法是很重 要的。 4 ) 用于决定输入参数的领域知识最小化：许多算法要求用户输入参数，而 聚类结果对于输入参数十分敏感，另一方面参数通常很难确定，要求用户输入 参数不仅加重了用户的负担，也使得聚类的质量难以控制。 5 ) 处理噪声数据的能力：绝大多数现实世界中的数据库都包含了孤立点， 空缺，未知数据或者错误的数据。一些聚类算法对于这样的数据敏感，可能导 致低质量的聚类结果。 6 ) 对于输入记录的顺序不敏感：一些聚类算法对输入数据的顺序是敏感 的。对于同一个数据集合当以不同的顺序输入时，产生的结果有很大差别。开 发对数据输入顺序不敏感的算法具有很大意义。 7 ) 高维性：一个数据库或者数据仓库可能包含若干维或者属性。许多聚类 算法只擅长处理低维数据。在高维空问中聚类数据对象是一个挑战，特别是数 据有可能非常稀疏和偏斜。 8 ) 基于约束的聚类：现实世界的应用可能需要在各种约束条件下进行聚 类 9 ) 可解释性和可用性：知识发现过程中，聚类结果总是需要表现为一定的 知识，这就要求聚类结果可解释，易理解。 1 3 基于数据流的聚类分析 信息时代的到来引发了信息大爆炸，各种行业需要处理的数据量与日俱增， 对数据挖掘技术提出了新的挑战。随着近些年来数据分析应用领域的不断发展， 数据流已经逐渐成为了一种常见的实用数据模式。同时，针对数据流的数据挖 掘技术也应运而生且发展迅速，开辟出了一个独立的，全新的研究领域。与传 统的数据库应用相比，应用于数据流的算法有几个明显的特点：首先，由于数据 流的速度很快，对算法的响应要求很高，所以数据流算法经常采用用精度换时间 的方法，尽量在对数据的一次访问中获得较优的解。其次，由于数据流量大，不 山东师范大学硕士学位论文 能象传统的方法把所有数据存储在内存或其他介质中，而是先概化。一般来说， 数据流算法是不可回溯的。再次，一些数据库应用中常用的操作在数据流中都是 不可行的。如，排序、统计最大值等b l o c k i n g 操作。聚类分析是数据挖掘的一 个重要分支，针对数据流的聚类分析已经成为了当今知识发现与数据挖掘领域 中的一个重要的研究热点。 对于数据流聚类的难点在于：数据量大，具有时间性、顺序性、实时性， 因此对流数据的随机访问几乎是不可能实现的，因此数据流聚类通常都要求“一 次性扫描数据”。数据流聚类算法首先对每个新到达的数据进行访问处理，之 后数据或被存储，或者直接被丢弃。数据流聚类算法通常会维护一个“概要数 据结构”，用来保存数据的摘要信息，当需要输出聚类结果时，以概要数据结 构中保存的信息作为目标对象集合，生成所需要的结果。 数据流本身所具有的特性决定传统的聚类分析不能直接用于数据流聚类。 与传统的聚类分析相比，数据流聚类具有以下特点： ( 1 ) 一遍扫描：在满足聚类分析的要求下，尽可能少的扫描数据，最好是 一遍扫描。 ( 2 ) 有限的存储空间：由于数据流具有无限连续性，不可能存储如此海量 的数据。所以必须对数据流进行必要的概化或有选择的舍弃。 ( 3 ) 实时性：对每一个记录的处理时间要尽可能的少，要跟上流的速度。 目前对数据流的研究还刚刚起步，数据流的聚类分析还处于初始阶段。 1 4 研究现状 目前，基于数据流的算法研究已经成为重要的研究课题。对数据流的研究主 要集中在以下几个方面：对数据流工作模型的建模、对数据流查询的响应、如何 管理数据流、如何对数据流进行挖掘等。在数据流挖掘方面，如何在数据流中进 行有效聚类，是一个吸引了研究者很大注意力的问题h 。7 1 。早期的数据流聚类研 究将数据流聚类问题作为“大数据库”聚类问题的一个特例，如2 0 0 0 年，g u h a 提出针对数据流聚类的l o c a l s e a r c h 侧算法。算法的基本思想是基于分治的思 想，使用一个迭代过程对数据流进行k m e a n s 聚类。o ，c a l1 a g h a n 发展了 l o c a l s e a r c h 的思想。他于2 0 0 2 年提出了s t r e 硼算法，并将其移植到数据流环境。 山东师范大学硕士学位论文 s t r e a m 算法采用批处理方式、分级聚类的方法。首先对最初的m 个输入数据进行 聚类得到o ( k ) 个l 级带权质心，然后将上述过程重复m 0 ( k ) 次，得到m 个l 级带权 质心，再对这m 个1 级带权质心进行聚类得到0 ( k ) 个2 级带权质心；同理，每当得 到m 个i 级带权质心时，就对这些质心进行一次聚类得到0 ( k ) 个i + 1 级带权质心： 重复这一过程直到得到最终的0 ( k ) 个质心。对于每个第i + 1 级带权质心而言，其 权值是与它对应的i 级质心的权值之和。 上述使用的算法框架就是转化问题域，分而治之的思想。，这类算法必须 指定k ，聚类的数目不能随便变动，对非凸形状等复杂形状的聚类也无能为力， 并且只保留了中心点的信息，造成很多有用信息的丢失。算法只能提供对当前 数据流的一种描述，而不能反映数据流的变化情况。这类早期的算法在框架结 构上属于单层算法结构。单层算法结构努力将数据流的动态特性转化为传统的 静态模式，从而能够应用成熟的传统方法解决问题。在这一阶段，算法研究的 重点是改进传统算法的性能，使之能够适应数据流的动态特性。然而，单纯的 改进传统算法效率使得早期的数据流聚类研究很快遇到了局限性的问题，现有 的算法框架很难满足日益增长的数据流算法的需求。 2 0 0 3 年，b a r b a r d 总结了数据流聚类算法的要求h 1 ，并对一些可能适用于 数据流的聚类算法做了一次总结。他认为在数据流中聚类要满足3 个要求：( 1 ) 压缩的表达：( 2 ) 快速、增长地处理新的数据点：( 3 ) 快速、清晰地判断独异点。 2 0 0 3 年a g g a r w a l 提出了一个解决数据流聚类问题的框架c l u s t r e a m 晦3 ，针对数 据流聚类问题提出了一个双层算法框架，算法分为在线层和离线层两个部分。 在线层算法负责对流数据进行快速而简单的处理，生成概要数据结构；离线层 算法利用这些概要数据信息进行更加复杂的分析，生成最终较为精确的聚类结 果。在z w r a n g 等人的算法中，在线层使用了不完全划分策略，使之能够更好 地适应数据流的动态特性【6 】。以上几种数据流聚类方法都使用k m e a n s 聚类思 想，对凸形状聚类效果较好，但它们都利用了欧氏空间距离的一些特性，对于非 凸形状聚类效果不理想，同时无法对高维数据进行聚类。 1 5 本人主要工作及内容组织 本文针对双层流数据聚类算法框架进行了深入的研究，并对当前聚类分析 山东师范大学硕士学位论文 得应用做了初步的研究，主要包括以下内容： 1 ) 深入地研究了在线层算法对数据的表达方式。重新定义数据结构“微簇” 来解决在线层算法中数据仅能根据临时分布状态确定所属聚类，从而导致算法 精度受损的问题。利用数据结构“多维球簇”，能够有效地解决流数据基于密度 聚类的问题。 2 ) 提出一种改进的方法的双层流数据聚类算法，在较低的时间丌销下能够 得到质量较高的聚类结果。算法较好的保持了全局信息的完整性。算法同时支 持数据流上的时间窗口分析。 3 ) 提出一种基于密度的数据流聚类算法，能够有效地解决数据空间中存在 不规则分布密集区域的聚类问题，实验结果表明该算法能够有效地标识空间中 的不规则形状簇。 钔聚类分析在数据流挖掘中具有很重要的地位，对当前数据流挖掘中聚类 分析的应用做初步研究，并对将来的研究方向做初步探讨。 本文各个章节的内容组织如下：第二章讨论双层数据流聚类算法的框架结 构；2 1 节概述双层流数据聚类的算法框架；2 2 节描述双层数据流聚类算法中 在线算法的数据表达方式，即，数据流处理模式。第三章提出一个改进的双层 数据流聚类算法；3 1 节介绍算法的问题提出；3 2 节阐述算法框架及过程；详 细地描述了在线层算法的设计要点，数据的紧缩处理以及对算法性能的讨论； 3 3 描述了离线算法的设计要点3 4 节对算法的实验结果进行了分析。第四章提 出一个基于密度的数据流聚类算法框架；4 1 节介绍算法的背景知识；4 2 节详 细介绍了算法中用到的概念。4 3 节详细描述在线层算法的设计，及描述离线层 算法的设计，包括用多维球数据结构保存数据：4 4 节对算法的实验结果进行 分析。第五章描述了聚类算法的应用5 1 节简单介绍聚类算法应用背景及应用 范围；5 2 节介绍入侵及入侵检测的概念；5 3 节描述聚类算法在入侵检测中的 应用。 山东师范大学硕士学位论文 2 1 概述 第二章：双层数据流聚类分析框架 单层数据流聚类算法由于在算法设计中自然地加入了单一访问的限制，使 得它在不同时间范围中进行聚类时非常困难，它不能提供我们所说的适应性。 例如s t r e a m 算法，在计算中需要同步保持所有可能的时间范围中的中间聚 类结果。这样的计算负担随着数据流的行进而不断增加，并且很快成为数据流 在线应用的瓶颈。进一步说，在很多情况中，一个分析师可能需要调用前面时 刻的聚类结果，将它和当前的聚类结果相比较。这对于单层数据流聚类算法来 说开销是惊人的，面对快速的数据流，它将被远远地抛在后面。 另外，单层数据流聚类算法对于数据点到达的顺序特别敏感。如果数据流 随着时间变化很大，那么使用这类算法将非常冒险。例如，在这类算法中为了 保持一定数量的簇中心，通常要改变或合并这些簇中心。一旦两个簇中心合并， 当在更大的范围的数据流中进行聚类分析时需要将其分开时，我们将会束手无 策。 综上这些单层数据流聚类算法的局限性，我们自然而然的需要突破这个框 架，设计一个更加行之有效的算法框架。于是，双层数据流聚类框架应运而生。 双层聚类算法将处理工作分为两个层面：在线层算法负责对数据进行粗糙 但快速的处理，并负责保存中间结果；离线层算法在中间结果的基础上进行精 确而复杂的分析，并得到最终结果。新的数据点到达时，在线层算法即对其进 行相应处理，处理算法通常相对简单并且高效，能够满足时间效率上的要求， 可以更好地适应较快的流速。在线算法同时生成概要数据信息，以中间结果的 方式保存在算法中，作为离线算法的输入。对于离线算法，可以采用相对较为 复杂的方法处理中间结果，此时目标集合已成为静态集合，因此通常情况下不 必考虑数据流速的影响。双层算法框架将处理工作分配在整个流数据过程中， 能够得到更高的算法效率。 j h a n 提出的双层结构算法a u s t r e a m i 引，利用微簇这种数据结构来保留 数据的局部摘要信息。微簇的概念是簇特征向量( c l u s t e rf e a t u r ev e c t o r ) 的时间 山东师范大学硕士学位论文 性扩展。微簇定义如下： 假设有这样一个集合，它由多维数据点，其时间戳为五砭组成。每个 数据点瓦为d 维，表示为i = ( 霉) 。一个微簇定义为一个( 2 d + 3 ) 元组i 凹z ，c f r