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

邹凌君：流数据的聚类分类算法研究 摘要 近年来，随着信息处理应用的发展，许多应用中的数据是以流的形式产 生的，数据呈现出“连续数据流”的形式而不是传统的静态存储结构形式。 这些应用领域包括金融证券信息分析、网络传输监控、计算机网络安全、通 信数据管理、w e b 应用、生产制作、传感器网络等。这些应用产生的数据形 式称为数据流。与传统数据库不同，数据流具有如下特点：( 1 ) 数据总量的 无限性：( 2 ) 数据到达的快速性；( 3 ) 数据到达次序的无约束性；( 4 ) 除非可 以保存，每个元素均只能被处理一次。 数据流的上述特点对数据流上的挖掘提出了如下要求：首先，算法必须 能够进行实时在线挖掘，快速处理每一个元组，并实时输出挖掘处理结果。 其次，由于相对于无限规模的数据流而言，内存通常是有限的，这就要求算 法的空间复杂度要低，往往需要在数据量的对数范围内。再次，由于算法实 时在线挖掘以及对空间复杂度的限制，算法往往只能得到近似解，且需要具 有一定的精确度保证。最后，算法要具有较强的适应性，包括对数据流不断 进化的底层模型的适应性，处理离群点能力等。 学术界己经对数据流上的挖掘问题进行了很多研究工作，但仍存在许多 问题尚待研究和解决。 本文研究了数据流上的聚类问题和分类问题，做了以下一些工作： ( 1 ) 提出了基于相关系数的多数据流聚类算法。使用相关系数作为数 据流间距离的度量，将有相同变化趋势的数据流聚为一类。我们使用衰减系 数来使得新数据比旧数据在聚类结构中有更大的重要性，采用更新时间片段 的机制很好地反映了聚类结构的变化过程。我们采用动态后m e a n s ，不断的 试探性地调整聚类的个数，通过比较聚类质量，选取最优的类的个数，提高 聚类质量。 此外，我们基于相关系数的度量，提出了另一种满足用户需求的聚类算 法框架。算法分为前台和后台两个部分：在前台部分，我们提出了一种新颖 的保存汇总信息的机制；后台阶段，根据用户的聚类请求，读取相应长度的 信息进行聚类。满足了用户对不同长度的聚类需求。 ( 2 ) 提出了一种基于谱分量相似度的多数据流的聚类算法框架。使用 自回归模型对数据流序列作谱分析，把数据流表示为谱参数的和。通过将相 位设为零后，使用谱分量信息计算两条数据流之间的相关性。 ( 3 ) 提出了一种基于网格密度的数据流聚类算法g d c s 算法。算法采 用了在线离线双层框架，它在前台在线层快速实时地将到达的数据点放入 相应的单元格，在后台离线层不断地更新单元格的密度并将网格单元聚成 类。此外，算法适时检测和剔除孤立点以改进系统的时间空间有效性。实验 i i 扬州大学硕士学位论文 表明，算法具有更优的聚类效率和聚类质量，能发现任意形状的类，且能有 效识别实时数据流的变化行为。 ( 4 ) 基于改进的f i s h e r 判别分析方法，我们提出了一种新的数据流的 分类方法。改进的f i s h e r 判别准则能同时适用于类内散布矩阵奇异和非奇异 两种不同场合。提高了分类的速度，更好的满足了流数据处理的要求。使用 最新滑动窗口中的样本不断重复构建分类模型，能及时反应概念的漂移。 类。 关键词：数据流；相关系数；聚类；自回归模型；f i s h e r 判别分析；分 自5 凌君：流数据的聚类分类算法研究 a b s t r a c t r e c e n t l y ，w i t ht h ed e v e l o p m e n to fi n f o r m a t i o np r o c e s s i n g ，t h ed a t ai s m o d e l e da sc o n t i n u o u st r a n s i e n td a t as t r e a mr a t h e rt h a na sp e r s i s t e n tr e l a t i o n si n m a n ya p p l i c a t i o n a r e a s i n c l u d i n g f i n a n c i a l a p p l i c a t i o n s ， n e t w o r kt r a f f i c m o n i t o r i n g ，s e n s o rn e t w o r k s 。t h i sk i n do fd a t ai sk n o w na sd a t as t r e a m u n l i k e t h et r a d “i o n a ld a t ab a s e s ，d a t as t r e 锄 h a st h e f b l l o w i n gd i s t i n g u i s h e d c 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 印i da f r i v i n gr a t eo fd a t a ；( 3 ) u n c o n t r o l l 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 ef b r e a c ht u p l e ，e x c e p tb e i n gr e s e r v e d 。 t h o s 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 j r e m e n t so nd a t as t r e 锄s m i n i n g ：f i r s t ly ，a l g o r i t h m ss h o u l db ei na no n l i n ep r o c e s s ，a n db ea b l et of a s t h a n d l ee 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 d l y ，b e c a u s eo f t h el i m i t e dm e m o r yc o m p a r e dw i t hu 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 d h a v el o ws p a c e c 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 i l g eo f l o g a “t h m i cb 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 g a n dl o ws p a c ec 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 ta 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 tac e r t a i np r e c i s i o no ft h er e s u l t ss h o u l db eg u a r a n t e e d a tl a s t ，a l g o r i t h m s s 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 c a b i l i t y0 nd a t as t r e 锄sw i t he v o l v i n g u 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 s r e s e a r c h e sh a v em a d ee f f b n so nd e s i g h n i n ge f f i c i e n ta l g o r i t h m sf o rm i n i n g d a t as t r e a m s ，h o w e v e rt h e r ea r em a n yp r o b l e m sn e e dt ob er e s e a r c h e da i l d r e s o h ，e d i nt h i s p a p e r ， w e s t u d y t h e p r o b l e mo fc l u s t e r i n g d a t as t r e a m sa n d c l a s s i f y i n g d a t as t r e a m t h em a i nc o n t l i b u t i o n so ft h i sp a p e ri n c l u d et h e f o l l o w i n ga s p e c t s ： ( 1 ) w ep r o p o s eac l u s t e r i n gm e t h o df b rm u l t i p l ed a t as t r e a m sb a s e do n c o r r e l a t i o nc o e m c i e n t w eu s et h ec o r r e l a t i o nc o e f f i c i e n tt om e a s u r et h e s i m i l a r i t yb e t w e e nd a t as t r e a m s t h ea t t e n u a t i o c o e m c i e mw a si n t r o d u c e dt o i m p r o v et h ep e r f o m a n c eo fc l u s t e r i n g w eu s es l i d i n gw i n d o wt e c h n i q u et o r e f l e c tt h eb e h a v i o fo fc l u s t e f i n gs t m c t u r e ad y n a m i c 缸m e a n sa l g o r i t h mi s p r o p o s e dt oa d j u s tt h en u m b e ro fc l u s t e ra i l di m p r o v et h ec l u s t e r i n gq u a l i t y i na d d i t i o n ，b a s e do nc o r r e l a t i o nc o e m c i e n t ，w ep r o p o s eac o rf r a m e w o r k t os a t i s f yu s e r sc l u s t e r i n gd e m a n d s t h ef r a m e w o r kc o n s i s t so ft w op h a s e s ，i e ， t h ef b r e g r o u n dp h a s ea n dt h eb a c k g r o u n dp h a s e t h ef b r e g r o u n dp h a s ep r o v i d e s an o v e lm e c h a n i s mt om a i n t a i nt h es t a t i s t i c a li n f b r m a t i o no fn l ed a t as t r e a m o n 扬州大学硕士学位论文 t h eb a c k g r o u n dp h a s e ，t h ea p p r o x i m a t i o no fd e s i r e ds u b s t r e a m si sr e t r i e v e d a c c o r d i n gt oc l u s t e r i n gq u e r i e s ( 2 ) an e wa l g o r i t h mf o fc l u s t e r i n gm u l t i p l ed a t as t r e a m su s i n gan o v e l s i m i l a r i t ym e t r i ci sp r o p o s e d b a s e do ns p e c t r a lc o m p o n e n ts i m i l a r i t ya n a l y s i s ， t h ea l g o r i t h mc a ne f 南c t i v e l yc l u s t e rs t r e a m sw h i c hs h o ws i m i l a rb e h a v i o rw i t h s o m eu n k n o w nt i m ed e l a y a u t o - r e g r e s s i v em o d e l i n gt e c h n i q u ei se x p l o i t e dt o m e a s u r el a gc o r r e l a t i o nb e t w e e nd a t as t r e a m s ，w h i c hi su s e da st h ed i s t a n c e m e t r i c sf o rc l u s t e r i n g b a s e do nas l i d i n gw i n d o wm o d e l ，t h ea l g o “t h mc a l l c o n t i n u o u s l yr e p o nt h em o s tr e c e n tc l u s t e r i n gr e s u l t s ，a n dd y n a m i c a l l ya d j u s t t h en u m b e ro fc l u s t e r s ( 3 ) a n a l g o r i t h m n a m e dg d c sf o f c l u s t e r i n g s t r e a md a t a u s i n g a d e n s i t y b a s e da p p r o a c hi sp r o p o s e d t h ea l g o r i t h mu s e sa no n l i n ec o n l p o n e n t w h i c hm a p se a c hi n p u td a t ar e c o r di n t oag r i d ，a n da no f n i n ec o m p o n e n tw h i c h c o m p u t e st h ed e n s i t yo ft h eg r i da n dc l u s t e r st h eg r i d sb a s e do nt h e i rd e n s i t y f u n h e r m o r e ，at h e o r e t i c a l l ys o u n dt e c h n i q u ei sd e v e l o p e dt od e t e c ta n dr e m o v e s p o r a d i cg r i d sw h i c ho n l yc o n s i s to fo u t l i e r si no r d e rt od r a m a t i c a l l yi m p r o v e t h es p a c ea n dt i m ee m c i e n c yo ft h es y s t e m e x p e r i m e n t a lr e s u l t ss h o wt h a to u f a l g o r i t h mh a ss u p e r i o rq u a l i t ya n de f f i c i e n c y ，c a nf i n dc l u s t e r so fa r b i t r a r y s h a p e s ，a n dc a na c c u r a t e l yr e c o g n i z et h ee v o l v i n gb e h a v i o r so fr e a l t i m ed a t a s t r e 啪s ( 4 ) am o d i f i e df i s h e rd i s c r i m i n a t ea n a l y s i sm e t h o di sp r o p o s e dt os a t i s f y t h er e a l - t i m ed e m a n di nd a t as t r e 锄c l a s s i f y i n g t h i sm e t h o dn o to n l yh a sah i g h e 艏c i e n c yb u ta l s oo v e r c o m e st h es i n g u l a rp r o b l e mo fw i t h i n - c l a s ss c a t t e r m a t r i x t h ea l g o r i t h mt r a i n st h em o d e lw i t h i ns l i d i n gw i d o wa n dr e b u i l d st h e m o d e la tac o n s t a n tr a t e t h em o d e ll e a r n e dc a nc a p t u r et h eu p - t o - d a t at r e n d si n t h es t r e a m e x p e r i m e n tr e s u l t ss h o wt h a to u ra l g o r i m mc a ns p e e du pt h em i n i n g e m c i e n t l 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 ，c o r r e l a t i o nc o e f f j c i e n t ，a rm o d e l ，s p e c t r a l c o m p o n e n t ，c l a s s i f i c a t i o n ，f i s h e rd i s c r i m i n a t ea n a l y s i s 邹凌君：流数据的聚类分类算法研究 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取 得的研究成果。除文中已经标明引用的内容外，本论文不包含其他个人或 集体已经发表的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 学位论文作者签名：乡f 凌石 签字日期：矽。占年5 月巧日 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保 留并向国家有关部门或机构送交学位论文的复印件和电子文档，允许论文 被查阅和借阅。本人授权扬州大学可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编 学位论文。同时授权中国科学技术信息研究所将本学位论文收录到中国 学位论文全文数据库，并通过网络向社会公众提供信息服务。 学位论文作者签名： 芗 凌男导师躲f 孕谴 签字日期：如昭年，月巧日签字日期：沙硌年岁月必，日 ( 本页为学位论文末页。如论文为密件可不授权，但论文原创必须声明。) 邹凌君：流数据的聚类分类算法研究 1 绪论 1 1 研究背景 1 1 1 数据挖掘技术概述 数据挖掘( d a t am i n i n g ) ，也称数据库中的知识发现( k d d ：k n o w l e 曲e d i s c o v e r vi nd a t a b a s e ) ，是指从大型数据库或数据仓库中提取人们感兴趣的 知识，这些知识是隐含的、事先未知的潜在有用信息，提取的知识一般可表 示为概念( c o n c e p t s ) 、规则( r u l e s ) 、规律( r e g u l a r i t i e s ) 、模式( p a t t e r n s ) 等 形式。如今已可以用数据库管理系统来存储数据，还可用机器学习的方法来 分析数据和挖掘大量数据背后的知识，而这两者的结合就促成了数据挖掘技 术的产生。 数据挖掘是一门交叉性学科，涉及到机器学习、模式识别、归纳推理、 统计学、数据库、数据可视化、高性能计算等多个领域。数据挖掘技术旨在 发现大量数据中所隐藏的知识，以用来解决“数据丰富、知识贫乏”的问题。 近年来随着数据库和网络技术的广泛应用，加上使用先进的自动数据生成和 采集工具，人们所拥有的数据量急剧增加，为数据挖掘技术的应用创造了必 要条件。 数据挖掘大体上有两种功能，预测验证功能和描述功能。前者指用数据 库的若干己知属性预测或验证其他未知属性值：后者指找到描述数据的可理 解模式。图1 1 列出了数据挖掘的几类主要的功能。 图1 1 数据挖掘的功能 数据挖掘是一个完整的过程，该过程从大型数据库或数据仓库中挖掘先 扬州大学硕士学位论文 前未知的、有效的、可实用的信息，并使用这些信息做出决策或丰富知识。 数据挖掘由以下过程或步骤组成： 1 ) 数据准备。这一阶段又可以进一步分为四个子阶段：数据清理、数据 集成、数据选择和预分析、数据变换。数据清理就是消除噪声或不一致数据。 数据集成将多文件或多数据库运行环境中的数据进行合并处理，建立统一的 数据视图。数据选择就是从数据库中检索与分析和任务相关的数据。预分析 的目的是辨别出需要分析的数据集合，缩小处理范围，提高数据挖掘的质量。 数据变换就是把数据变换或统一成适合挖掘的形式，如通过汇总和聚集技 术。 2 ) 挖掘。这个阶段进行实际的挖掘操作，使用智能方法提取数据模式。 3 1 知识表述。使用可视化和知识表示技术，根据最终用户的决策目的对 提取的信息进行分析，把最有价值的信息区分出来，提供给决策者。 4 ) 评价。如果分析人员对结果不满意，可以重复上述三个过程，直至满 意为止。 1 1 2 数据流管理概述及应用需求 近年来，由于网络通讯技术、传感器网络技术的发展，一种新形式的数 据处理应用受到了相关领域研究者的关注。许多实时应用如金融管理，安全 管理，传感器网络中出现了一类新的数据，这类数据不同于传统的静态的存 储在数据库中的数据，不适合持久稳定关系建模。适合用瞬态数据流建模。 我们称这样的数据形态为数据流( d a t as t e a m i n g ，简称s t r e 锄i n g ) ，并用数据 流模型( d a t as t r e a m i n gm o d e l ) 来描述它。数据流是一种大量的连续到达， 时间有序，快速变化，潜在无限的数据川。随着通信技术和硬件设备的不断 发展，尤其是小型无线传感设备的广泛应用，数据采集变得越来越便捷和趋 于自动化。新兴的应用领域，诸如实时监控系统、气象卫星遥感、网络通信 量监测和电力供应网等等，每时每刻都在源源不断地产生大量的数据。例如， 电信部门的记录数据，远程传感器传回的各种监测数据，气象海洋数据，股 票市场的交易数据等等。传统的数据处理技术己不适合数据流的处理，由此 产生一系列新的研究问题。 这类数据的主要特点是数据不断到达，难以用一个确切的数字来统计数 据的总量，数据总量被将定为无限的。数据的到达次序是连续的，不受应用 所约束。数据量很大，相对来说存储介质就小的多，不能全部保存，除非刻 意保留，每个数据只能访问一次。 h e n l z i n g e r 等人于1 9 9 8 年在论文“c o m p u t i n go nd a t a s t r e a m ”中首次将数 邹凌君；流数据的聚类分类算法研究 据流作为一种数据处理模型提出来【2 】。从2 0 0 0 年开始，数据流作为一个热点 研究方向出现在数据挖掘与数据库领域的几大顶级会议中，如v l d b 、 s i g m o d 、s l g k d d 、i c d e 、i c d m 等会议每年都有多篇有关数据流处理的 文章。目前，数据流研究大致可分为两个方面：数据流管理系统( d a t as t r e a m m a n a g e m e ms y s t e m s ，d s m s ) 和流数据挖掘i ”。其中，建立数据流管理系统 方面的研究主要集中在数据流查询。已有多个研究机构进行了d s m s 的研究， 并构建出一些系统，如s t r e a m ，t e l e g r a p h c q ，a u r o r a 等。流数据挖掘方面的 研究主要包括多数据流挖掘和单数据流挖掘。目前学者们已提出了大量流数 据挖掘算法，并开发出流数据挖掘系统。如u i u c 的m a i d s ( m i n i n g a l a r m i n g i n c i d e n t sf r o md a t as t r e 8 m s l 就是一个集查询、聚类、分类、频繁项挖掘，以 及处理结果可视化五大功能为一体的流数据挖掘系统。 数据流的几种典型应用领域如下： ( 1 ) 金融应用领域：金融证券交易中产生大量的流式数据，如美国四个 交易所( n y s e ，a m s e ，n a s d a q 和s m a l l c a p ) 的统计信息显示所有上市股票 的日常交易数据和报价数据以每月1 0 g b 的速度增长。股民更关注的是对股 票价格变化趋势的分析，多支股票的相关性分析，预测外部的事件对股票价 格的影响等。如世界各地各种政治，经济，文化新闻和突发事件不断涌现， 直接或间接影响着股票价格。股票交易所，证券公司需要不断实时获取各种 股票的价格以及各种新闻信息，并在此基础上进行大量复杂的实时分析挖 掘。因而，我们要采用数据挖掘的技术和方法从流数据中提取有用的信息。 ( 2 ) 传感器网络：传感器网络可以使人们在任何时间、地点和环境条件 下获取大量详实而可靠的信息。因而，传感器网络被广泛的应用在国防军事、 地理监视、高速公里拥塞检测、移动物体跟踪、制造业的流程监管等应用中。 在一个传感器网络中分布着众多的传感器节点。传感器节点间通过发射无限 信号进行通讯，并最终将数据传送到中心主机中进行处理，用户可以持续分 析传感器节点采集的数据，发现异常模式，及时给出报警信号。例如，我们 可以在一个仓库内通过多个传感器监控实时地温度情况，当平均温度超过一 定范围则采取一定的措施。 ( 3 1 计算机网络：计算机网络实时交互着大量的及时通讯信息、电子邮 件、在线视频等数据。这些数据被封装为各种i p 数据包通过局域网( 广域 网) 从源地址传送到目的地址。作为网络连接节点的路由器、交换机等设备 需要极快的传送这些数据包，例如c i s c o 公司w s c 6 5 0 3 交换机最高背板 带宽高达7 2 0 g b p s 。因特网服务提供商( 例如中国网通) 需要从交换机设备 中获取这些实时i p 数据包，并进行分析挖掘，从而实现对计算机网络的监 控和维护。 f 4 ) 事务日志分析；事务日志有很多，如因特网访问记录、电话记录、 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 ，并还将以每年1 1 以上的速度递增。这些不断增长的页 面搜索请求为网络搜索公司带来了巨大的网络流量的同时，给公司网站的事 物日志留下大量的搜集记录。如何对这些搜索记录进行实时分析处理，以带 来更好的用户体验和更为强大的搜索功能，是每个网络搜索公司不断追求的 目标。 1 1 3 数据流的特点 上述各种应用场景的共同特点是海量数据实时快速到达。学术界把具有 这种特征的新兴数据库称为数据流。数据流相对于传统数据库已成为一种新 兴且日益主流的数据存在方式。人们迫切需要从这些包含有大量数据的数据 流中提取有价值的信息和知识。因而，数据流的分析和挖掘日益成为一个热 点问题。建立数据模型是数据管理和分析的基础，数据流是由有序的对象组 成的序列。数据流不同于传统的存储关系模型。有如下几个特点： 1 数据流中的元素在线式到达。 2 频繁的变化和快速的反应。 3 数据元素到达的顺序无法控制和预知。 4 数据的潜在总量难以预知，也许是无穷无尽的，而存储空间是有限的， 难以将数据全部存储起来。 5 一旦数据流中的某个元素经过处理，要么被丢弃，要么被存储。因此， 除非这个数据被直接存储在内存中，否则不容易被检索。 根据数据流的特点，处理数据流时应考虑以下问题： 1 同时处理大量数据是不可能的，处理无限数据更是不可能，应考虑将 无限的数据集映射到有限数据集的方式进行处理。即用有限来表示 无限。 2 可以增量的维护。在有限的主存中维持一定数量的数据单元，根据一 定的更新机制，进行实时地更新和维护。 数据流的数据量以惊人速度持续不断增长对数据挖掘技术提出了新的 挑战。海量数据高速到达使得传统数据挖掘技术对数据集中所有数据反复进 行操作的做法不再可行。数据流挖掘对挖掘算法提出了一系列新要求。总的 来说，数据流挖掘算法必须以增量方式跟踪数据流的变化，同时不能占用过 邹凌君：流数据的聚类分类算法研究 多的计算和内存资源。下面概括了数据流挖掘与传统数据挖掘主要的不同之 处。这些差别归根结底是由数据流无限增长的数据量和数据快速到达特性所 造成的。 1 由于数据量无限增长，对数据流的扫描次数仅限于单遍，即除非刻意 保存，每个数据只可以被处理一次。而在传统数据挖掘中，数据集 通常保存在数据文件中，可对数据集进行多遍扫描。 2 数据流的快速流动性要求算法对数据的分析处理速度不能低于数据 流动速度，因而算法对新数据的处理时间是严格受限的。而在传统 数据挖掘中，数据静态保存在数据库中，对算法的处理时间并无此 限制。 3 相对于数据流的无限数据量，系统中的内存容量是微不足道的，因而 对数据流挖掘算法来说，空间复杂度是严格受限的。而传统数据挖 掘可反复将数据库中的数据装载到内存中，对算法的空间复杂度并 没有严格限制。 4 数据流数据量的无限性使得数据流挖掘往往无法保留原始数据，仅能 在内存中维护原始数据的一系列概要信息，并基于这些概要信息生 成最终结果。数据流挖掘结果往往是有一定允许误差的近似结果。 而在传统数据挖掘中，数据量相对较小，且无处理时间扫描遍数等 限制，因而可获得相对准确的挖掘结果。 5 数据流动态环境下，数据底层分布模型会受现实应用中各种因素的干 扰，如网络黑客入侵，传感器网络外部环境的改变等而随着时间不 断改变，即数据流通常是不断进化的。因而，数据流挖掘中的概念 模型通常为多个。而传统数据挖掘通常是对数据库中静态数据进行 挖掘，这些数据往往符合同一分布模型，所以传统数据挖掘中的概 念模型通常是一个。 1 1 4 数据流管理系统与传统数据库管理系统的对比 传统的数据库管理系统皆在处理持久、稳定的数据，强调维护数据的完 整性、一致性，其性能目标是以较低的代价获得较高的系统吞吐量，其设计 目标是维护数据的绝对正确性、提供友好的用户接口等。这种数据库管理系 统对于传统的事务性应用是有效的、成功的，然而它不适合于处理无限数据 的、快速的、实时的应用，关键在于传统的数据库管理系统通常不考虑与事 务相关联的时间和空间限制，其调度与处理决策不考虑数据的各种时间特 性，其系统的设计指标并不强调实时性和查询服务质量的自适应性，而实时 6 扬州大学硕士学位论文 性和自适应性恰恰是数据流应用所必须的。 表1 。1d b m s 与d s m s 的对比 数据库管理系统( d b m d )数据流管理系统( d s m s ) 一次查询长时间连续查询 随即访问 顺序存取 极大的磁盘存储有限的主存空间 仅表示当前的事件状态 历史到达顺序是关键性特征 被动的储藏主动存储 相对低的更新速率可能是多路g b 级到达速率 不具有实时服务功能实时服务是必要功能 假定精确数据数据可能是陈旧或不精确的 访问计划由查询处理器，物理数据库 不可预知，变化的数据抵达方式和特征 设计确定 与传统d b m s 一切为了保证结果的绝对正确性相反，d s m s 更看重自 适应性。允许向用户提供近似查询结果。d b m s 与d s m s 的对比如表1 1 。 d s m s 与传统d b m s 相比，新颖性主要表现在三个方面1 4 j ； ( 1 ) 语义( s e m a n t i c s ) ：流按时间顺序输入，查询结果以流形式输出。 ( 2 ) 状态( s t a t e ) ：不能存储无终止的流，某些操作需要历史记录。 ( 3 ) 性能( p e r f o r m a n c e ) ：自适应性( a d a p t i v i t y ) ，速率可变性( v a r i a b i l i t y ) ， 不精确性( i m p r e c i s i o n ) ，等等。 1 1 5 数据流模式 且前，在数据流研究领域中存在多种数据流模型。不同的数据流模型具 有不同的适用范围，需要设计不同的处理算法。可以分别按照数据流中数据 描述现象的方式和算法处理数据流时所采用的时序范围对这些模型进行划 分。 假设描述信号一( 定义为函数爿： 1 加斗r ) 的数据流，由连续的数据项 口l ，组成。按下标递增的顺序依次到达数据项q 可能包含多维属性，根 据q 等于川i 】与的关系不同，文献【5 】给出了三种数据流模式，分别是： 邹凌君：流数据的聚类分类算法研究 ( 1 ) 时间序列模式( t i m es e r i e s m o d e l ) 。每个数据项q 等于4 【f 】按照f 增 加的顺序出现，相当于时间序列数据，例如每隔5 分钟观测i p 的流量，每分 钟观测n a s d a q 等等。下文称此类数据流为时间序列数据流。 ( 2 ) 现金记帐模式( c a s hr e 百s t e rm o d e l ) 。每个数据项q 表示4 刀的增加， 即q = ( _ ，) ，0 ，其含义为4 【刀= 4 一。 月+ ，其中4 表示观测到流中第j 个 项时信号的状态，如同现金记帐一样，多个q 表示一段时间上一【刀的增量。 这是一种更为普遍的数据流模式。 ( 3 ) 十字转门模式( t u r n s t i l em o d e l ) 。每个数据项q 表示对爿【门的更新，即 q = ( ，u ) ，其含义为4 【刀= 4 一。【刀+ u ，( q 可能为正也可能为负) ，这种模式 得名自繁忙的地下铁路站上限制旅客进入和离开站台的十字转门，适合于描 述数据流动态的入队和出队状态，单位时间内流入和流出的数据量不必相 同，是研究数据流最为通用的动态模式。 在这3 种模型中，t u m s t i i e 是最具一般性的数据流模型，其适用范围最 广，也最难处理。流数据分类与聚类通常使用的是时序模型，它们将数据流 中的每个数据项看作一个独立的对象。若将爿【刀记为信号，出现的次数，则 流数据频繁模式挖掘通常使用的是c a s hr e g i s t e r 模型，只允许数据的插入。 也有算法研究了同时存在数据插入和删除时的流数据频繁模式挖掘问题。此 时，算法应用的是数据流的t u m s t i l e 模型。 1 1 6 数据流计算模型 数据流可看作是一个不断增长的d 维元组集合 石，z ，对任意 砸1 ) z = ( 爿z ) ，各元组的时标为五巧。对数据流的数据挖掘通常基于 某种特定的时间区间( 称为窗口) 进行，常用的窗口模型有三种： 1 界标窗口模型( l a n d m a r kw i n d o wm o d e l ) 。在该窗口模型下，被用来 挖掘的数据集为从数据流开始到当前到达的所有元组的集合，即 写，z ( f 扬州大学项士学位论文 为当前元组的时标) ，且窗口大小随数据流进行不断增加。 2 滑动窗口模型( s l i d i n gw i n d o wm o d e l ) 。在该窗口模型下，被用来挖 掘的数据集为从当前时标开始，最近到达的个元组的集合( 这里的为 滑动窗口的大小) ，即 五一。五 ( f 为当前元组的时标) 。窗口位置在时间轴 上随着数据流进行不断滑动。 3 衰减窗口模型( d 锄p e dw i n d o w m o d e l ) 。在该窗口模型下，被用来挖 掘的数据集为从数据流开始到当前到达的所有元组的集合，但各元组被赋予 不同的权重。较早到达的元组具有较小权重，较晚到达的元组具有较大权重。 各元组的权重根据某种衰减函数( 例如指数衰减厂( r ) = 2 “) 其中2 0 ) 随时 间f 不断衰减。 4 倾斜时间框架( t i t l e dt i m ef r a m e ) 滑动窗口和衰减函数都只能在单一时间维的窗口上得到计算结果。然 而，很多应用要求在不同的时间粒度层上进行分析和挖掘。比如。用户通常 对细粒度层上的当前变化感兴趣，而在粗粒度层上对长期变化感兴趣【l 】。 为此，我们可以构建不同层次的时间粒度窗口。最近的数据在最细的粒 度层上记录和运算，较久远的数据在较粗的粒度上记录和运算h l 。这样，我 们不仅可以满足需求，而且不会占用太多的存储空间。更重要的是，我们可 以构建适合应用需要和当前存储条件的粒度层。这样的时间维模型被称为 “倾斜时间框架”。 h a n 和k 锄b e r 在文献【6 】中介绍了三种倾斜时间框架模型：自然倾斜时间 框架模型( n a t u r a l ) 、对数尺度倾斜时间框架模型( 1 0 9 a r i t h m i cs c a l e ) 和渐进对数 时间框架模型( p r o g r e s s i v el o g a r i t h m i c ) a 如下图所示： lii il lii i llijlilii f r a m e s n a p s h o t s ( b y c i o c k ，o w t i m e l ( a ) an a t u r a lt i l t e dt i m e 觎m em o d e l 0 6 96 76 5 16 66 25 8 26 86 05 2 6 4 t3 2 ti 6 t8 f 4 t2 t t 35 64 02 4 flliiiijlill iif i1z 7 。，p 44 81 6 n 0 w 56 43 2 ( b ) al o g a r i t h m i ct i l t e dt i m ef r a r n em o d e l ( c ) ap r o g r e s s i v ei o g a r i t h m i c t i l t e dt i m ef a m et a b l e 图1 2 倾斜时间框架的三种模型 邹凌君：流数据的聚类分类算法研究 9 在实际应用中，这几种窗口模型的选取往往根据用户的需求而定。无论 具体采用哪一种或几种窗口模型，数据流挖掘都具有相同的挖掘框架，如图 1 3 所示： 图1 3 数据流处理模型 传统的数据挖掘技术往往需要存储整个的数据集，需要对数据进行随机 访问或者多次的访问，而且，处理每个数据项的时间比较长。因为它不强调 数据处理的时间和空间限制，其系统的性能指标是吞吐量和平均响应时间。 数据流独特的特点，使得传统的数据挖掘技术不能直接移植到数据流上。且 传统的数据库系统旨在处理永久、稳定的数据，强调维护数据的完整性、一 致性。其性能目标是高的系统吞吐量和低的代价，设计目标是维护数据的绝 对】下确性、保证系统的低代价、提供友好的用户接口。这种数据库系统对传 统的商务和事务型应用是有效的、成功的，然而它不适合无限、快速、实时 的应用。对数据流而言，存储所有的数据是不实际的，随机访问的代价也是 相当高的，对每个数据项的简单计算要考虑到时间和空间的限制。这些都是 挖掘数据流所要面临的一些主要的问题。 1 2 基本技术 在许多数据流应用中，计算资源和通信资源是极为有限的，为了及时地 完成某些复杂的数据流处理，例如决策支持、查询优化等，用户需要接受近 似的解答。因此，设计单遍扫描算法( o n e p a s sa l g o r i t h m ) ，实时地给出近似 查询结果是数据流模型下数据处理的目标之一。近似算法的关键在于设计一 个远小于数据集规模的结构，从而可以在内存中处理数据。这种名为概要数 据结构( s y n o p s i sd a t as t r u c t u r e ) 的规模至多应该是数据流规模的次线性函数。 允许得到近似结果的查询操作可以在概要上执行，而不必直接访问无限的流 数据f 。 数据流挖掘算法从数据流中不断接收新到达的元组。当处理一个新元组 时，挖掘算法通过增量计算更新概要数据结构。当接收到挖掘请求时( 也可 l o