（计算机科学与技术专业论文）数据流挖掘若干关键技术研究.pdf

国防科学技术大学研究生院博士学位论文 摘要 随着计算机硬件、网络通信和分布计算技术的飞速发展，产生了一种新型的 数据类型一数据流，它广泛存在于诸如互联网监控、金融分析、传感器网络、天 气或环境监测等领域中。传统的数据处理技术适合处理静态、稳定的数据集，难 以直接扩展至无限、快速、变化、持续的数据流场景中，因此，如何管理和分析 这些数据流，特别是，通过数据流挖掘及时检测网络异常等问题，成为新一代计 算理论和应用的研究难点。 本文在总结和分析国内外现有研究工作的基础上，围绕数据流挖掘的四个关 键技术：相似性搜索技术、频繁模式挖掘技术、数据流分类技术和数据流任意形 状聚类技术展开深入研究，主要工作包括： l 、在数据流相似性搜索方面，针对数据流上难以建立索引结构的特点，基于 动态时间扭曲距离函数( d t w ，d y n a m i ct i m ew a r p i n g ) ，通过对其下限函数的研 究，利用数学中的分段、填充元和行列约束度等概念，构造了一组适合不同场景 的数据流相似性度量函数及其配套的上下界精化函数，进而提出了相应的数据流 相似性搜索算法。理论分析和统计实验表明，本文构造的函数和搜索算法计算复 杂度低，相似性程度高，在数据流相似性搜索中有很好的应用前景。 2 、在数据流频繁模式挖掘方面，针对数据流的时效性和流中心的偏移性特点， 提出了界标窗口模型与时间衰减模型相结合的数据流频繁模式挖掘算法。该算法 通过动态构建全局模式树，利用时间指数衰减函数对模式树中各模式的支持数进 行统计，以此刻画界标窗口内模式的频繁程度；进而，为有效降低空间开销，设 计了剪枝阈值函数，用于对预期难以成长为频繁的模式及时从全局树中剪除。论 文对出现在算法中的重要参数和阈值进行了深入分析。一系列试验表明，与现有 同类算法m s w 相比，该算法挖掘精度高( 平均超过9 0 ) ，内存开销小，速度 上可以满足高速数据流的处理要求，且可以适应不同事务数量、不同事务平均长 度和不同最大潜在频繁模式平均长度的数据流频繁模式挖掘。 3 、在数据流分类方面，传统的后向传播算法难以满足数据流实时处理的要求。 基于核主成份分析算法，通过对其增量化求解方法的研究，构造了旨在降低分类 处理量的维数约减算法；进而结合b p 神经网络提出了相应的数据流分类算法。理 论分析和统计实验表明，本文构造的维数约减算法时空复杂度低、收敛性能稳定， 分类算法能够满足数据流实时处理要求，且分类精度较高。 4 、在数据流任意形状聚类方面，针对数据流的时效性和概念漂移特性，提出 了滑动窗口模型与时间衰减模型相结合的数据流任意形状聚类算法。该算法应用 时间衰减模型以指数级速度衰减历史元组密度，使当前滑动窗口外元组的密度近 第i 页 国防科学技术大学研究生院博士学位论文 似衰减至零；通过构建六元组聚类特征结构，在界标窗口内统计微簇的衰减密度， 以此刻画其在滑动窗口内的疏密程度。并运用剪枝策略，对当前窗口中稀疏微簇 和窗口外微簇及时进行剪枝，从而有效地降低了空间开销和维护代价。一系列试 验表明，与现有同类算法d e n s t r e a m 相比，该算法聚类速度快，内存开销小，且 可以适应不同长度、维数和自然簇个数的数据流任意形状聚类。 关键词：数据流；相似性搜索；频繁模式挖掘；分类；任意形状聚类；时间 衰减模型 国防科学技术大学研究生院博士学位论文 a b s t r a c t 缈劢t h er a p i dd e v e l o p m e n to fc o m p u t e rh a r d w a r e 。n e t w o r kc o m m u n i c a t i o na n d d i s t r i b u t e dc o m p u t i n gt e c h n i q u e ，d a t as t r e a m ，an e wk i n do fd a t at y p e ，h a sb e e nc o m i n g ， w h i c he x t e n s i v e l ye x i s t si nm a n yr e s e a r c ha r e a s ，s u c ha sn e t w o r km o n i t o r i n g ，f i n a n c i a l a n a l y s i s ，s e n s o rn e t w o r k s ，w e a t h e ro re n v i r o n m e n t a lm o n i t o r i n ga n ds oo n o nt h eo t h e r h a n d ，t h et r a d i t i o n a ld a t ap r o c e s s i n gt e c h n o l o g yi ss u i t a b l ef o rd e a l i n gw i t l ls t a t i ca n d s t a b l ed a t a s e t sb u tn o ty e te a s yt ob ee x t e n d e dt od a t as t r e a ms c e n e si nw h i c ht h ed a t a s t r e a mi s i n f i n i t e ，r a p i d ，v a r i o u s a n dc o n t i n u o u s s o ，a m o n gt h en e wk i n do f c o m p u t a t i o n ，i ti so n eo ft h en e wd i f f i c u l t i e si nt h e o r ya n da p p l i c a t i o nh o wt om a n a g e a n da n a l y z et h ed a t as t r e a m s ，e s p e c i a l l y ，t od e t e c ti nt i m et h en e t w o r ka n o m a l yt h r o u g h d a t as t r e a mm i n i n g b a s e do nt h ec o n c l u s i o na n da n a l y s i so ft h e e x i s t i n gr e s e a r c h e sa th o m ea n da b r o a d t h i sp a p e rd e e p l ya n dp r o f o u n d l yc a r r i e so u ts t u d i e sw h i c hf o c u so nt h ef o u rk e y t e c h n i q u e si nd a t as t r e a mm i n i n g ，t h a ti st os a y ，s i m i l a r i t ys e a r c h , m i n i n gf r e q u e n t p a t t e r n s ，c l a s s i f y i n ga n da r b i t r a r ys h a p ec l u s t e r i n go v e rd a t as t r e a m s 1 1 1 em a i n c o n t r i b u t i o n sa r ec o n c l u d e da sf o l l o w s ： 1 i nt h ea s p e c to ft h ed a t as t r e a ms i m i l a r i t ys e a r c h w er e s e a r c ht h en oi n d e x s t r u c t u r el o w e rb o u n df u n c t i o no fd y n a m i ct i m ew a r p i n g ( d t w ) u s i n gt h ec o n c e p t s o fs u b s e c t i o n ，f i l l - i n s ，a n dr o w & c o l u m nc o n s t r a i n si nm a t h e m a t i c s ，w ec o n s t r u c ta g r o u po fd a t as t r e a ms i m i l a r i t ym e a s u r ef u n c t i o n ss u i t a b l ef o rd i f f e r e n ts c e n e sa n dt h e c o r r e s p o n d i n gr e f i n i n gf u n c t i o n so ft h eu p p e ra n dl o w e rb o u n d s ，a n dt h e nw ep r o p o s e t h es i m i l a r i t ys e a r c ha l g o r i t h mo nd a t as t r e a m s t h et h e o r y a n a l y s i sa n ds t a t i s t i c a l e x p e r i m e n t sc o n f i r mt h a tb o t ht h ec o n s t r u c t e df u n c t i o n sa n dt h es e a r c ha l g o r i t h mh a v e l o wc o m p u t a t i o n a l c o m p l e x i t ya n dh i g ha p p r o x i m a t ed e g r e e ，w h i c hh a sag o o d a p p l i c a t i o np e r s p e c t i v ei nt h ed a t as t r e a ms i m i l a r i t ys e a r c h 2 i nt h ea s p e c to ft h ed a t as t r e a m f r e q u e n tp a t t e mm i n i n g ，c o n s i d e r i n gt h e t i m e l i n e s so fd a t as t r e a ma n dt h es h i f to ft h es t r e a mc e n t e r ，w ep r o p o s ea na l g o r i t h mo f d a t as t r e a mf r e q u e n t p a t t e r nm i n i n g ，n a m e dl w f p m ，c o m b i n i n g 、i t l lb o t ht h e l a n d m a r kw i n d o wa n dt h et i m ed e c a y i n gm o d e l b yd y r n a m i c a l l yc o n s t r u c t u r i n gt h e g l o b a lp a t t e r nt r e e ，t h em e t h o du s e st i m ee x p o n e n t i a ld e c a yf u n c t i o nt oa c c o u n tt h e s u p p o r to fe a c hp a a e m ，w i t h i nt h el a n d m a r kw i n d o w ，w h o s ef r e q u e n td e g r e ei s d e s c r i b e d m o r e o v e r ，t or e d u c et h es p a c ec o s te f f e c t i v e l y ，t h ec o n s t r u c t e dp r u n i n g t h r e s h o l df u n c t i o ni su s e dt oc u ti nt i m et h ep a t t e mt h a ti sn o ta b l et ot u r ni n t ot h e f r e q u e n tp a t t e r nf r o mt h eg l o b a lt r e e t i l i sp a p e rd e e p l ya n a l y z e st h ei m p o r t a n t p a r a m e t e r sa n dt h r e s h o l d s i nt h ea l g o r i t h m t h e e x p e r i m e n t a lr e s u l t ss h o wt h a t c o m p a r i n gw i t ht h ea l g o r i t h mm s w l w f p mh a sh i g h e rm i n i n gp r e c i s i o n ( o v e r9 0 i na v e r a g e ) a n dl o w e rs t o r a g ec o s t ，a n di tc a nr e a c ht h er e q u e s to fp r o c e s s i n gh i g h s p e e d 第i i i 页 国防科学技术大学研究生院博士学位论文 d a t as t r e a m si nt h ee x e c u t i o ns p e e d o u rm e t h o dc a nb ea p p l i e dt ot h es t r e a m sw i t h d i f f e r e n tn u m b e ro ft r a n s a c t i o n s ，a v e r a g et r a n s a c t i o ns i z e sa n dm a x i m a lp o t e n t i a l l y f r e q u e n tp a t t e r ns i z e s 3 i nt h ea s p e c to ft h ed a t as t r e a mc l a s s i f i c a t i o n ，t h et r a d i t i o n a lb a c kp r o p a g a t i o n ( b p ) c l a s s i f i c a t i o na l g o r i t h mi sd i m c u l tt om e e tt h en e e df o rr e a l - t i m er e s p o n s e b a s e d o nt h ek e r n e lp r i n c i p a lc o m p o n e n ta n a l y s i sa l g o r i t h m ，t h r o u g ht h es t u d yo fi n c r e m e n t a l s o l v i n gm e t h o d s ，w ec o n s t r u c tt w od i f f e r e n td i m e n s i o n a l i t y r e d u c t i o na l g o r i t h m st o d e c r e a s et h ea m o u n to fc a l c u l a t i o no fc l a s s i f i c a t i o n f u r t h e r m o r e ，c o m b i n e dw i t ht h eb p n e u r a ln e t w o r k ，t h ec o r r e s p o n d i n gd a t as t r e a mc l a s s i f i c a t i o na l g o r i t h mi sr a i s e d ，n a m e l y i k o c t h et h e o r ya n a l y s i sa n ds t a t i s t i c a le x p e r i m e n t si n d i c a t et h er e d u c t i o na l g o r i t h m s h a v el o ws p a c e & t i m ec o m p l e x i t ya n ds t a b l ec o n v e r g e n c ep e r f o r m a n c e ，a n di k o cc a n r e a l t i m ep r o c e s sd a t as t r e a m sa n dh a sh i g hc l a s s i f i c a t i o na c c u r a c y 4 i nt h ea s p e c to ft h ed a t as t r e a ma r b i t r a r ys h a p ec l u s t e r i n g ，c o n s i d e r i n gt h e t i m e l i n e s sa n dt h ec o n c e p ts h i f to fd a t as t r e a m ，w ep r o p o s ea r ta l g o r i t h mo fa r b i t r a r y s h a p ec l u s t e r i n gc a l l e ds w a s c ，c o m b i n i n gw i t hb o t ht h es l i d i n gw i n d o wa n dt h et i m e d e c a y i n gm o d e l t h i sa l g o r i t h ma p p l i e st h et i m ed e c a y i n gm o d e l t od e c a yt h ed e n s i t yo f t h eh i s t o r i cd a t u ma tt h es p e e do fe x p o n e n t i a lo r d e rs ot h a tt h ed e n s i t yo fd a t u mw i t h o u t t h ec u r r e n ts l i d i n gw i n d o wi sa l m o s tr e d u c e dt oz e r o b yc o n s t r u c t i n gac l u s t e r i n g f e a t u r es t r u c t u r ew i t hs i xe l e m e n t s ，w eg e tt h ed e c a yd e n s i t yo fm i c r o c l u s t e r sw i t h i nt h e l a n d m a r kw i n d o w w h i c hi su s e dt od e s c r i b et h ed e g r e eo fd e n s i t yo fm i c r o - c l u s t e r w i t h i nt h ec u r r e n ts l i d i n gw i n d o w n l ep r u n i n gs t r a t e g yi sd e s i g n e dt ot i m e l yc u td o w n t h es p a r s em i c r o c l u s t e ra n dt h eo b s o l e t em i c r o - c l u s t e rw i t h i na n dw i t h o u tt h ec u r r e n t w i n d o w , r e s p e c t i v e l y ，w h i c hc a nd e c r e a s et h es t o r a g ec o s t a n dm a i n t e n a n c ec o s t e x t e n s i v ee x p e r i m e n t a lr e s u l t si n d i c a t et h a t ，c o m p a r i n gw i t ht h ea l g o r i t h md e n s t r e a m ， s w a s ch a sh i g h e rc l u s t e r i n gs p e e da n dl o w e rm e m o r yc o s t ，a n di ti sf i tf o ra r b i t r a r y s h a p ec l u s t e r i n go v e rd a t as t r e a m sw i t hd i f f e r e n ts i z e s ，d i m e n s i o n sa n dn u m b e r so f n a t u r a lc l u s t e r s k e y w o r d s ：d a t as t r e a m ，s i m i l a r i t ys e a r c h ，m i n i n gf r e q u e n tp a t t e r n s ， c l a s s i f y i n g ，a r b i t r a r ys h a p ec l u s t e r i n g ，t i m ed e c a y i n gm o d e l 第i v 页 国防科学技术大学研究生院博士学位论文 表目录 表2 1 标记和定义1 4 表2 2 测试数据集3 1 表2 3 没有全局约束条件下，不同下限函数的近似程度比较3 2 表2 4 全局约束条件下，不同下限函数的近似程度比较3 2 表2 5 没有全局约束条件下，p o s t u r ed a t a 数据集中的过滤率。3 3 表2 6 没有全局约束条件下，p o w e rd a t a 数据集中的过滤率3 3 表2 7 没有全局约束条件下，s y n t h e t i cd a t a 数据集中的过滤率3 4 表2 8 全局约束条件下，p o s t u r ed a t a 数据集中的过滤率3 5 表2 9 全局约束条件下，p o w e rd a t a 数据集中的过滤率3 5 表2 1 0 全局约束条件下，s y n t h e t i cd a t a 数据集中的过滤率3 5 表4 1k d d c u p 9 9 数据集下，i k o c f i k o c k o c f i o c 比较7 5 表4 2 五种数据集下，i k o c f i k o c k o c f i o c 比较7 6 表4 3 基于各种核函数的i k o c 性能比较7 8 表4 4 基于各种核函数的f i k o c 性能比较7 8 第1 v 页 国防科学技术大学研究生院博士学位论文 图目录 图1 1 数据流处理模型。4 图2 1 扭曲矩阵，扭曲路径和对整1 5 图2 2 序列x 和y 的前向累积距离矩阵1 5 图2 3 序列x 和y 的后向累积距离矩阵。1 5 图2 4 累积距离矩阵和分段累积距离2 0 图2 5 分段累积距离矩阵中最优扭曲路径的计算元素个数和行、列约束度2 1 图2 6 分段累积距离矩阵中计算元素的填充区域2 l 图2 7 分段累积距离矩阵中填充元素的取值区域2 4 图2 8 全局约束下累积距离矩阵和分段累积距离矩阵2 5 图2 9 相互重合的累积距离矩阵2 7 图2 1 0o s s d s 算法伪代码3 0 图2 1 l 没有全局约束条件下，不同数据集中的过滤率一3 4 图2 1 2 全局约束条件下，不同数据集中的过滤率一3 6 图3 1g l o b a l t r e e 举例3 9 图3 2l w f p m 算法描述。4 6 图3 3 宽度为t c a r e 的数据流4 9 图3 4 挖掘纯度51 图3 5 内存开销比5l 图3 6 内存开销比5 2 图3 7 执行时间比5 2 图3 8 执行时间比5 3 图3 9 执行时间随事务数量事务平均长度最大潜在频繁模式平均长度变化一5 4 图3 1 0 纯度内存开销执行时间随衰减因子变化5 6 图3 1 l 纯度内存开销执行时间随阈值变化5 7 图4 1 多层前馈神经网络5 9 图4 2i k d r 算法描述6 5 图4 3i k d r 直观解释6 7 图4 4f i k d r 算法描述6 9 图4 5i k o c 流程图7 1 图4 6i k o c 算法描述7 2 图4 7 四组收敛性分析7 4 图4 8 执行时间分别随数据流长度维数类个数变化7 7 第v 页 国防科学技术大学研究生院博士学位论文 图5 1 聚类算法8 2 图5 2o n l i n e s w a s c 算法描述9 0 图5 3 内存开销节省率9 l 图5 4 执行时间比9 2 图5 5 执行时间分别随数据流长度维数簇个数变化9 3 图5 6 执行时间随滑动窗口长度变化9 4 第v i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的 研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教 育机构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示谢意 学位论文题目：熬堡速撞翅羞王羞链技盔盟究 学位论文作者签名：基盘垒 日期：年月 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留。使用学位论文的规定本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文 档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书x 学位论文题目：熬握速控握羞王羞链技苤煎究 学位论文作者签名：墨题日期： 年 月 日 国防科学技术大学研究生院博士学位论文 第一章绪论弟一旱三百记 当前，有关数据流管理与分析的研究已成为数据库领域的研究热点。近1 0 多 年来，随着通信技术的不断发展，数据采集手段多样且方便快捷，诸如各类监控 系统，包括传感器网络监控、安全态势的实时感知、天气或环境监测、网络服务 商对流量的监控等，每时每刻都在产生无穷、时序和快速到达的数据流f j 】。这些数 据的高效实时处理以及相关的在线监控、持续提供近似查询结果等现实需求，与 计算& 存储能力、网络带宽资源等方面的矛盾日益突出，对传统的面向静态数据集 的数据处理技术提出了诸多挑战【l ，2 】。如何管理和分析【2 。5 】这些数据流，成为新一代 计算理论和应用的研究难点之一。 数据流管理侧重数据流查询语言、负载控制、操作调度等管理系统相关问题 研究；数据流分析侧重数据流统计查询、挖掘等理论问题研究。本文正是围绕数 据流挖掘中若干具有深刻技术背景和广泛应用前景的热点问题展开研究。 本章一方面从研究背景出发，在总结和分析数据流相关研究工作的基础上， 重点介绍了数据流挖掘的四个关键技术：相似性搜索技术、频繁模式挖掘技术、 数据流分类技术以及数据流聚类技术；另一方面，概括介绍了本文的研究内容和 主要贡献，并给出论文的组织结构。 1 1 1 应用背景 1 1 研究背景 随着互联网基础建设的日益完善，网络技术的不断创新发展，网络应用己广 泛深入到各国的政治、经济、军事和生活中。从应用领域来看，在2 0 0 9 年3 月召 开的互联网诞生2 0 周年纪念活动上总结指出 6 1 ，互联网给人类生产、生活及娱乐 等诸多方面带来了l o 大积极变化，包括：“信息、创业、中立性、电子商务、组 织、文化、历史、游戏、幽默以及视频”。从应用规模上来看，据中国互联网络 信息中心( c 岍c ) 在2 0 0 9 年7 月发布的第2 4 次中国互联网络发展状况统计 报告中披露【7 】，截至2 0 0 9 年6 月3 0 日，中国网民数量己突破3 亿，达到3 3 8 亿，稳居全球第一，较2 0 0 8 年底增长1 3 4 ，普及率达到2 5 5 ；数据显示，截 至6 月，手机上网用户达到1 5 5 亿，占网民数量的4 6 ；特别地，网络购物的群 体数量也在金融危机中逆势增长，达到8 7 8 8 万。如此广泛的应用领域，加之规模 巨大的用户群体，在互联网上产生了一种无限、持续、快速、随时间变化的数据 类型，这种新的类型定义为数据流。 近年来，数据流管理和分析已成为数据库领域的研究热点，其中，数据流挖 第l 页 国防科学技术大学研究生院博士学位论文 掘技术，如相似性搜索、频繁模式挖掘、分类、聚类等，己在许多领域内得到成 功应用，典型的应用场景有： 互联网监控：伴随互联网的迅速普及，信息化的日渐深入，网络安全事件 发生的频率、种类和复杂性逐年增加，潜在威胁和攻击规模持续增长，网络安全 形势十分严峻。2 0 0 8 年底，c o n f i c k e r 蠕虫病毒开始利用w i n d o w s 操作系统漏洞感 染计算机系统，截至2 0 0 9 年6 月已有数百万台计算机系统被控制，由此形成的僵 尸网络构成了0 9 年最为严重的网络威胁之一1 8 j 。c n c e r t c c 发布的( ( 2 0 0 8 年上 半年中国互联网网络安全报告 9 1 指出，国内网络安全事件数量同比2 0 0 7 年上半 年有显著增加，其中，网页恶意代码增长近一倍；网页篡改和仿冒事件分别增长 2 3 7 和3 8 ；恶意代码肆意传播，仅2 0 0 8 年上半年就捕获了9 0 万个样本，同比 增长6 2 5 ，为木马和僵尸网络的大量产生和扩散提供了重要途径。国家反计算机 入侵和防病毒研究中心发布的我国信息网络安全状况和发展趋势指出【旧】，当 前网络安全面临的主要威胁在于：“1 ) 针对网络浏览器插件程序的攻击；2 ) 内 部攻击者的威胁；3 ) 网络间谍技术；4 ) 以重大事件或流行事件为诱饵的混合型 攻击；5 ) 无线网络、移动手机成为新的安全重灾区”。同时指出，未来网络安全 的发展趋势为： “1 ) 集团化、产业化，例如，形成“病毒木马编写者专业盗号 人员一销售渠道一专业玩家 产业链；2 ) “黑客 逐渐变成职业犯罪，如“网络 钓鱼等；3 ) 恶意软件的手段将更为高明；4 ) 网页挂马危害继续延续；5 ) 利用 应用软件漏洞的攻击将更为迅猛”。病毒制造者、传播者追求经济利益的强烈欲 望，对国际国内社会造成了极为严重的损失和不稳定因素，带给各国互联网安全 保障一系列挑战，包括：如何及时、全面地把握本国互联网安全态势? 如何正确 地做出安全风险评估和预警? 如何有效地采取危机控制措施，并模拟、预见控制 效果? 等。可见，需要一套有力的网络监控机制【l ，通过n e t f l o w 流量分析系统、 分布式蜜罐系统、i d s 入侵检测系统、分布式探针系统以及骨干网监测系统等各种 网络监控平台，实时监控网络上的流量、通讯和安全事件等信息，并对大规模网 络攻击或威胁行为( 如d d o s 、蠕虫、僵尸网络等) 、网络性能、网络流量等方面 进行分析和预测，从而帮助网络管理人员实时了解目标网络的态势( 例如：1 ) 网 络详细流量信息：分布及变化情况如何? 2 ) 网络安全事件在国内的蔓延情况( 地 理、拓扑位置) ，比如说：当前国内感染蠕虫最严重的省份? 未来可能蔓延至哪 些区域? 3 ) 境外对本国发起的网络攻击行为信息? 等) ，并及时发现其中存在的 安全隐患，进而为后续安全风险评估、主动防御提供决策支持，最终对网络实施 有效管控。 传感器网络i l2 j ：传感器网络可用于监控各种物理或环境状况( 如温度、气 压、湿度、声音或振动等) ，另外还可用于发现、追踪目标。最早起源于军事应 第2 页 国防科学技术大学研究生院博士学位论文 用( 包括侦查敌情、监控火力装备、判断攻击等) ，现已广泛应用于工业、农业、 环境、医疗、交通、保健等领域，包括：地理环境与生态监测、交通拥堵监测、 健康监护、生命信号检测、车辆运行追踪、视频监视等应用。这些分布广泛的传 感器网络时刻都在向监测中心发送大量的传感器数据，而监测中心必须及时地对 这些海量数据进行分析处理，以发现潜在的变化和目标。 在线日志分析：博客的普及程度逐年提高，正表现出强烈的社会化网络特 征，现己成为互联网应用的一大热门。根据( ( 2 0 0 8 2 0 0 9 博客市场及博客行为研究 报告显示【l3 1 ，截至2 0 0 9 年6 月，博客用户规模已达到了1 8 2 亿，博客空间也超 过了3 亿；报告表明，博客应用率持续增长，半年增长率为1 2 ；活跃程度也在 进一步提高，活跃用户规模达到了1 1 3 亿，占6 2 7 。如此庞大的用户群体留下 了大量的日志记录，这些记录反映了公众的自我情感和对“社会现象”的言论， 通过实时分析处理可以随时了解社会舆情以及公众感兴趣的话题。 1 1 2 数据流技术 数据库技术从诞生至今得到了迅猛发展，不仅已具备坚实的理论基础，而且 还产生了许多成熟的产品和成功的应用，对人们的生产、生活方式带来了巨大的 改变。尽管如此，随着数据形式的不断扩展和新技术的层出不穷，数据库技术仍 将面临巨大挑战，这其中就包括如何有效管理和分析数据流的问题。数据流具有 不同于静态数据集的四大特性【l 捌：( 1 ) 数据无限、快速到达，规模超出任何系统 的存储范围；( 2 ) 数据仅限单遍扫描，除非特意保存，否则不能被再次处理；( 3 ) 数据的统计特征随时间变化，需要持续更新查询结果；( 4 ) 仅要求提供满足一定 误差范围的近似查询结果。对比而言，针对静态数据集的传统处理技术通常将数 据持久存储在特定介质( 磁盘、磁带等) 中，方便多遍扫描，并通过建立相应的 索引机制来支持高效、精确的查询。显然，传统处理技术在处理数据流时，势必 会在存储开销、实时处理、持续更新查询结果等方面，难以满足实际应用需求。 1 1 2 1 数据流处理模型 有限的存储空间无法容纳整个数据流，所以必须在精度和存储空间之间采取折 衷，借助概要数据结构在有限内存中表达、处理数据流。同时，数据流的统计特 征会随时间不断发生改变，而“单遍扫描”的限制决定了必须设计出高效的单遍 扫描算法，一方面确保数据分析处理速度快于流速，另一方面确保以在线增量更 新方式实时维护概要数据结构，以便持续提供近似查询结果。综上分析，数据流 分析处理基本框架可用图1 1 表示【l j 。 不难看出，概要数据结构是数据流研究的基础。常见的概要数据结构【2 l 包括直 方图方法、抽样方法、小波方法和哈希方法等。直方图方法1 1 4 , 1 5 1 将数据流划分为 第3 页 国防科学技术大学研究生院博士学位论文 图1 1 数据流处理模型 、近似查询结果 一一一 多个连续的桶( b u c k e t ) ，每个桶都附有相应的统计特征值；该表示法直观、简洁， 能够很好地表示数据流轮廓；直方图方法可具体划分为等宽、压缩和v 优化直方 图等类型。抽样方法选取流上部分样本集合来表征整个数据流，并根据该集合获 得近似查询结果，具体可划分为水库【16 1 、精确【1 7 】和计数1 7 1 抽样等类型。小波变换 方法【1 8 珈1 通过将数据流变换成小规模的小波参数集合，以此来近似数据流。哈希 方法【2 1 ，2 2 】定义一组哈希函数，将数据流映射成一个小值域范围内的数据集合，通 过该集合能够研究原始数据流的某些特性；可以划分为b l o o mf i l t e r 方法、s k e t c h 方法和f m 方法等。 1 1 2 2 数据流管理原型 传统数据库管理系统( d b m s ) 旨在处理永久存储、静态稳定的数据，其设计 目标是【2 3 】：1 ) 维护数据的绝对正确性、完整性及一致性；2 ) 提高系统的吞吐量， 减少平均响应时间，降低系统的维护代价；3 ) 提供友好的用户接口。与d b m s 不 同，数据流管理系统( d s m s ) 旨在处理无穷多变、高速动态的数据，因此需要提 供内建近似查询功能；由于在决策、调度过程中必须考虑与数据相关联的不确定 性以及时空限制等各种因素，因此设计目标更加侧重于查询服务质量和自适应性。 d b m s 与d s m s 对比如下【1 , 2 , 1 1 , 2 4 , 2 5 】： ( 1 ) 数据模型。d b m s 中数据是静态稳定、规模有限的，全局统计特性( 如 规模、方差、概率分布等) 可获知。d s m s 中数据是动态变化、无限到达的，全局 统计特性无法获知。 ( 2 ) 处理模型。d b m s 采用“存储索引查询处理模型。d s m s 采取“即时 处理，概要存储”处理模型。 ( 3 ) 数据存储。d b m s 采用磁盘、磁带作为存储介质；d s m s 采用内存中规模 至多为o ( p o l y l o g ( n ) ) ( _ 为流的长度) 的概要数据结构来处理数据流。 第4 页 国防科学技术大学研究生院博士学位论文 ( 4 ) 访问模式。d b m s 可随机访问数据，并可通过增、删、改操作加以更新。 d s m s 只能顺序访问数据，而且只能通过增量方式加以更新。 ( 5 ) 结果查询。d b m s 可通过一次查询、多遍扫描返回精确查询结果。d s m s 只能通过不间断单遍扫描获取近似查询结果。 1 1 2 3 数据流窗口模型 用户通常关注于特定窗口内数据流的演变规律，常用窗口模型有三种【1 ，2 4 2 6 】： l 、界标窗口模型( l a n d m a r kw i n d o w ) 。预定起始时刻为乃删，那么当前时刻 如一，该模型的处理范围为时间段 瓦撕f 】之间的流数据。 2 、跳动窗口模型( j u m p i n gw i n d o w ) 。该模型中，每当到肼流数据时，窗 口的起始和结束时间戳均会向前滑动外位置。其中，根据用户需求设定，一般小 于窗口大小。 3 、滑动窗口模型( s l i d i n gw i n d o w ) 。该模型中，新到达一个时间单元或流数 据时，窗口的起始和结束时间戳均会向前滑动一个位置，但大小仍保持固定。窗 1 2 1 大小的度量方式通常分两种类型：一种基于时间，设定固定时间间隔为疋触馏， 那么当前时刻，该模型处理范围为 瓦删旷瓦触哟如删脚之间到达的流数据； 另一种基于元素个数，处理范围为最近到达的个流数据( 为滑动窗口的大小) 。 1 2 数据流相关研究工作 数据流相关研究可分为管理和分析两个方面。首先，介绍国内外数据流管理 系统的概况；其次，综述数据流分析技术的研究现状；最后，对数据流研究工作 进行总结。 1 2 1 数据流管理系统 随着数据流技术的飞速发展，国内外众多知名大学和研究机构相继开发了一 些具有成功应用的数据流管理系统( d s m s ) 。典型代表如斯坦福大学的通用流系 统s t r e a m l 2 7 , 2 5 】，布朗大学、布兰蒂斯大学和麻省理工大学的大型流监控系统 a u r o r a 2 9 - 3 1 】& b o r e a l i s l 3 2 1 和加州大学伯克利分校电信电话流系统t e l e g r a p h