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

国防科学技术大学研究生院博士学位论文 摘要 数据流的本质特征为变化性及不可预测性。作为数据流一种重要的数据分析 方法，数据流突发检测能够及时检测数据流中特定元素的数量异常变化，因此得 到了学术界和工业界的广泛关注。应用领域有：光子爆发检测、股票波动检测、 网络流量异常波动检测等。 数据流突发检测是一个新兴的研究领域，存在许多值得研究且尚未解决的问 题：( 1 ) 数据流元素及其频数的高效存储。突发检测关心频数变化较大的元素， 因此须保存所有相异元素及其频数，而海量数据流中相异元素数目庞大且总数不 断变化，每个元素频数的差异也很大。如何高效地存储这些元素及其频数，降低 存储开销的同时支持高效的查询处理，是一个基础、关键、值得研究的问题；( 2 ) 在某些应用场合，数据流整体的数据量波动剧烈，导致单个元素频数随之变化剧 烈。在建立突发模型时，要考虑如何减小数据流整体数据量的波动对单个元素流 量的影响；( 3 ) 突发检测作为典型的数据流监测应用，并不是孤立的。现有的多 个监测应用如t o p k ，频繁项挖掘，变化检测、离群点检测等都是相对独立串行工 作。如何在单遍处理的前提下，利用有限的存储和计算资源，实时并行地完成多 个监测任务，是一个很有意义的工作。 本文紧紧围绕着数据流突发检测这个中心，针对上述若干挑战性问题，从数 据流处理角度出发，对突发检测处理流程中几个关键问题进行了研究。本文的主 要贡献为： l 、针对总数动态变化的海量相异数据流元素存储问题，提出了一种自适应的、 灵活的、可动态扩展的布卢姆过滤器e x b f 。e x b f 由一个或多个称为桶的子布卢 姆过滤器组成，并由目录和桶的两级结构组成可扩展哈希数据结构，以管理和维 护这些桶。与用汐、印职、s c b f 等已有数种容量可扩展的布卢姆过滤器相比，e x b f 的优势为：( 1 ) 元素更新和查询时间复杂度为d ( 1 ) ，不随桶数目的增多而线性增 加；( 2 ) 扩展方式灵活，扩展时仅重新分布一个桶的元素，数据迁移量为总数据 量的1 2 n ，其中n 为桶的数目；( 3 ) 在元素数目较少时能够动态缩减桶的数目和 目录的大小；( 4 ) 能够保证假阳性率限制在任意事先确定的范围内。 2 、针对数据流元素及其频数的高效存储问题，提出了一个基于改良的计数型 布卢姆过滤器b c b f + h s e t 保存所有元素频数的基本方法。该方法使用相对静态和 固定的结构，能提高约2 5 的存储效率，且能应对少数元素频数的剧烈变动。针 对数据流中所有元素及其频数重尾分布的特点，提出了一个基于分层计数型布卢 姆过滤器h c b f 的方法，该方法在选取合适分层参数的情况下，能提高约3 0 的 存储效率。 第i 页 国防科学技术大学研究生院博士学位论文 3 、在突发模型的建立方面，针对数据流整体数据量波动比较剧烈的情况下进 行准确突发检测的问题，提出了流量无关的突发检测方法f f b d ，该方法使用单个 元素数量与总体元素数量的比值作为单个元素滑动窗口内的聚合函数值，并使用 前后两个滑动窗口内的聚合函数值的比值来判断突发。与典型的聚合塔突发检测 方法相比，f f b d 方法使用多约2 的存储空间，高约5 的计算复杂度，但能有 效地规避整体数据流的显著变化对单个元素突发检测带来的影响，有着更好的检 测效果。 4 、在数据流多监测任务协同处理方面，基于数据流滑动窗口模型，提出了一 个基于网格划分的多监测任务协同处理方法g d - m m t p m , 将监测离群点、监测变 化和监测突发等三个监测任务统一起来，使用单遍处理的方式进行统一处理。该 方法能同时检测出离群点、变化和突发，且只需维护网格的简单信息，与其它方 法相比，能够显著地减少时间复杂度和空间复杂度。 综上所述，本文的工作针对数据流中进行突发检测的问题，围绕着该问题的 几个挑战进行突破研究，提出了数个算法、方法及模型。由于突发检测在数据流 挖掘中的重大理论意义及广阔应用前景，本文对于促进突发检测问题的理论研究 和实用化具有一定的理论意义和应用价值。 主题词：数据流，数据流挖掘，突发检测，布卢姆过滤器，数据流监测，高效存 储 第i i 页 国防科学技术大学研究生院博士学位论文 a bs t r a c t d a t as t r e a mh a st w oe s s e n t i a lc h a r a c t e r i s t i c s ：m u t a b l ea n du n p r e d i c t a b l e a sa b a s i ca n di m p o r t a n tm e t h o do fd a t aa n a l y s i s ，b u r s td e t e c t i o no nd a t as t r e a mc a nd e t e c t t h ea b n o r m a lc h a n g e so fs o m es p e c i f i ce l e m e n t sf r e q u e n c yi nt i m e c o n s e q u e n t l y ，i t h a sa t t r a c t e de x t e n s i v ea t t e n t i o n sf r o mt h er e s e a r c ha n di n d u s t r yc o m m u n i t i e s t h i s t e c h n o l o g yh a sb e e na d o p t e di nm a n ya p p l i c a t i o n s ，i n c l u d i n gt h ep h o t o nb u r s td e t e c t i o n ， s t o c kf l u c t u a t i o n sd e t e c t i o n ，n e t w o r kt r a f f i cf l u c t u a t i o n sd e t e c t i o na n ds oo n b u r s t d e t e c t i o no nd a t as t r e a mi san e wr e s e a r c hf i e l da n d h a si n t r o d u c e dal o to fc h a l l e n g e s a n du n s o l v e dp r o b l e m s ( 1 ) h o wt os t o r et h ee l e m e n t sa n di t sf r e q u e n c ye f f i c i e n t l y b u r s td e t e c t i o nf o c u s e so nt h ee l e m e n t sc h a n g i n gg r e a t e r ，t h u sa l le l e m e n t sa n di t s f r e q u e n c ym u s tb er e c o r d e d t h en u m b e ro ft h e s ee l e m e n t si sv e r yl a r g ea n dk e e p s c o n t i n u o u s l yc h a n g i n g t h ed i f f e r e n c eo fe a c he l e m e n ti sa l s on o t a b l e h o wt os t o r et h e e l e m e n t sa n di t sf r e q u e n c ye f f i c i e n t l yw h i l es u p p o r t i n ge f f e c t i v eq u e r y i n gi sd e f i n i t e l ya c h a l l e n g i n gw o r k ( 2 ) h o wt oa b a t et h ei n f l u e n c ew h i c ht h et o t a lf l o wi n c u r st os i n g l e e l e m e n ti nb u r s td e t e c t i o n i ns o m ea p p l i c a t i o ns c e n a r i o s ，t h et o t a lf l o wo fd a t as t r e a m f l u c t u a t e sa c u t e l ya n dc a u s e st h ea c u t ef l u c t u a t i o no ft h es i n g l ee l e m e n t sf r e q u e n c y f i n d i n ga na p p r o a c ht oa b a t et h ei n f l u e n c ew h i c ht h et o t a l f l o wi n c u r st os i n g l ee l e m e n t i nb u r s td e t e c t i o ni sw o r t hp a y i n gm o r ea t t e n t i o nt o ( 3 ) h o wt oa c c o m p l i s hm a n y m o n i t o r i n gt a s k si np a r a l l e la n dr e a l t i m ew i t hl i m i t e ds p a c er e s o u r c e sw i t h i no n ep a s s b u r s td e t e c t i o ni sat y p i c a la p p l i c a t i o no fd a t as t r e a mm o n i t o r i n g a tt h es a m et i m e ， t h e r ea l s oh a v es o m eo t h e rm o n i t o r i n ga p p l i c a t i o n si nt h em o n i t o r i n gs y s t e m ，s u c ha s t o p kq u e r y i n g ，f r e q u e n tm i n i n g ，c h a n g ed e t e c t i o n ，o u t l i n ed e t e c t i o na n ds of o r t h h o w t o a c c o m p l i s hm a n ym o n i t o r i n gt a s k s i n p a r a l l e l a n dr e a l - t i m e 、析t hl i m i t e ds p a c e r e s o u r c e sb yo n ep a s si sac h a l l e n g i n gw o r k t l l i sd i s s e r t a t i o np u t se m p h a s i so nt h ea b o v ec h a l l e n g e so fb u r s td e t e c t i o n ，a n d a d d r e s s e ss e v e r a lk e yp r o b l e m so nb u r s td e t e c t i o np r o c e s s i n g t h em a i nc o n t r i b u t i o n so f m i sa r ed i s s e r t a t i o nc o n c l u d e da sf o l l o w s ： 1 w ep r o p o s eas e l f - a d a p t i n g ，f l e x i b l ea n ds c a l a b l eb l o o mf i l t e rc a l l e de x b ft o a d d r e s st h ed y n a m i ce x t e n d i b l ep r o b l e mo fs t o r i n ge l e m e n t so fd a t as t r e a m e x b fi s c o n s t r u c t e db a s e do nt h ee x t e n d i b l eh a s h i n g c o m p a r i n gt oe x i s t i n gt r a d i t i o n a l e x t e n d i b l eb l o o mf i l t e r ss u c ha sp b f s p b fa n ds c b f , e x b fh o l d sf o u rn o t a b l e a d v a n t a g e s ：( 1 ) t h et i m ec o m p l e x i t yo fe l e m e n tu p d a t i n ga n dq u e r y i n gi sd ( 1 ) a n dd o e s n o tr i s e 谢t ht h ec o u n to fb u c k e t s ；( 2 ) e x t e n d i n gm e t h o di sf l e x i b l e e x b fd o e sn o tn e e d t or e - d i s t r i b u t ea l le l e m e n t sw h i l ee x t e n d i n gd a t as t r u c t u r e t h es i z eo fd a t am i g r a t i o n a n dt h ei m p a c t i o no no r i g i n a ld a t as t r u c t u r ea r eb o t hs m a l l ；( 3 ) n l es i z eo fe x b fc a nb e r e d u c e dd y n a m i c a l l yw i t ht h ee l e m e n tn u m b e rb e i n gr e d u c e d ；( 4 ) t h ef a l s ep o s i t i v er a t e c a nb ec o n t r o l l e dt oa na c c e p t a b l et h r e s h o l d 第i i i 页 国防科学技术大学研究生院博士学位论文 2 w ec o m eu pw i t han o v e ls o l u t i o nb a s e do ni m p r o v e dc o u n t i n gb l o o mf i l t e r 。 n a m e da sb c b f + h s e t 、t oa d d r e s st h es p a c e e f f i c i e n tp r o b l e mo fs t o r i n ge l e m e n t sa n d i t sf r e q u e n c yi nd a t as t r e a m t h i ss o l u t i o nm a k eu s eo ft h er e l a t i v es t a b l ed a t as t r u c t u r e ， s oi tc a ns a v ea b o u t2 5 s p a c ea n da b a t et h ea c u t ef l u c t u a t i o na c u t e l yo fl i t t l ee l e m e n t s o nt h ec o n d i t i o no fh e a v y - t a i l e dd i s t r i b u t i o no fa l lt h ee l e m e n t sf r e q u e n c i e s ，w ep r o p o s e an o v e lh i e r a r c h i c a lc o u n t i n gb l o o mf i l t e r s ( h c b f ) d a t as t r u c t u r e t h i sm e t h o dc a n r e d u c ea b o u t3 0 s p a c ec o s tw i t ha p p r o p r i a t ep a r a m e t e r s 3 w eb r i n gf o r w a r daf l o wf r e eb u r s td e t e c t i o nm e t h o dc a l l e df f b dt oa d d r e s s t h ea c c u r a t eb u r s td e t e c t i o np r o b l e md u r i n gt h et o t a lf l o wo fd a t as t r e a mf l u c t u a t e s a c u t e l y t h i sm e t h o di n t r o d u c e st h er a t i oo fo n ee l e m e n t sf r e q u e n c ya n dt o t a le l e m e n t s f r e q u e n c ya st h ea g g r e g a t i o nf u n c t i o nv a l u et oc h e c kb u r s t c o m p a r i n gt ot h et r a d i t i o n a l a g g r e g a t i o np y r a m i d ，f f b dp r o v i d et h ec a p a b i l i t yo fa v o i d i n gt h ei n f l u e n c eb yt o t a l f l o wa tt h ec o s to f2 m o r es p a c ea n d5 m o r ec o m p u t a t i o n a lc o m p l e x i t y 4 、a l s op u tf o r w a r dag r i dd i v i d i n gb a s e dm u l t i p l em o n i t o r i n gt a s k p r o c e s s i n gm e t h o dc a l l e dg d m m t p m t h i sm e t h o df i n d st h er e l a t i o n s h i pb e t w e e n o u t l i e r ，c h a n g ea n db u r s ti nd a t as t r e a m ，a n dc a np r o c e s so u t l i e rd e t e c t i o n ，c h a n g e d e t e c t i o na n db u r s td e t e c t i o n s y n c h r o n o u s l y d i f f e r e n tf r o mo t h e rm e t h o d s g d - m m t p mo n l yn e e dm a i n t a i nt h es i m p l eg r i dl n f o r m a t i o n t h u si tc a nr e d u c et i m e c o m p l e x i t ya n ds p a c ec o m p l e x i t ys i g n i f i c a n t l y i ns u m m a r y ，t h i sd i s s e r t a t i o na d d r e s s e st h ep r o b l e mo fb u r s td e t e c t i o ni nd a t a s t r e a m ，a n dp r o p o s e ss e v e r a ls p e c i f i ca l g o r i t h m s ，m e t h o d sa n dm o d e l s t h i si sa p r o m o t i o no fd a t ap r o c e s s i n go nb o t ht h e o r e t i c a ls t u d ya n dp r a c t i c a la p p l i c a t i o n s k e yw o r d s ：d a t as t r e a m ，d a t as t r e a m s t r e a mm o n i t o r i n g ，e f f i c i e n ts t o r i n g m i n i n g ，b u r s td e t e c t i o n ，b l o o mf i l t e r ，d a t a 第i v 页 国防科学技术大学研究生院博士学位论文 表 目录 表2 1 本章常用符号列表及其含义1 6 表3 1 计数型布卢姆过滤器的比较3 8 表3 2 改良计数型布卢姆过滤器符号列表及其含义3 9 表3 3 分层计数型布卢姆过滤器符号列表及其含义4 5 表5 1 检测到各类事件的数目8 7 第1 v 页 国防科学技术大学研究生院博士学位论文 图目录 图1 1 互联网关键词突发一俯卧撑3 图1 2 数据流处理模型。5 图1 3 文本流及其突发示意图一8 图1 4 论文结构图1 4 图2 1 标准布卢姆过滤器。1 6 图2 2 划分式布卢姆过滤器j 19 图2 3e h 数据结构2 1 图2 4 插入元素示例图2 2 图2 5 桶的分裂示例图2 4 图2 6 目录的扩展示例图2 5 图2 7e x b f 和b f 取不同值时的存储开销2 9 图2 8b f 位数组不同长度下存储1 0 ，0 0 0 个和1 0 0 ，0 0 0 个元素时的假阳性率3 0 图2 9e x b f 与s p b f , s c b f 存储可伸缩性对比一3 0 图2 1 0e x b f 与s p b f , s c b f 处理1 0 0 ，0 0 0 个元素时的存储开销对比3 1 图2 1 1e x b f 与s p b f , s c b f 处理1 0 0 ，0 0 0 个元素，不同桶的时间开销对比3 1 图2 1 2e x b f 与s p b f , s c b f 处理1 0 0 ，0 0 0 个元素，不同桶的假阳性率对比3 1 图3 1 网络数据流元素频数分布图3 4 图3 2s b f 整体结构图3 6 图3 3d c f 结构示意图3 7 图3 。4b c 8 n 尼眙，数据结构示意图3 9 图3 5 某一时刻滑动窗口中各元素的频数状况4 3 图3 6 各元素计数器的应取长度4 3 图3 7h c b f 数据结构示意图4 4 图3 8d c f 与h c b f 存储开销对比示意图4 8 图3 9 数据集1 不同c 的空间复杂度。5 0 图3 1 0 数据集2 不同c 的空间复杂度5 0 图3 1 l 数据集1 d c f , c b f 和b c b f + h s e t 空间复杂度5 0 图3 1 2 数据集2 d c f , c b f 和b c b f + h s e t 空间复杂度5 l 图3 1 3d c f , c b f 和b c b f + h s e t 时间复杂度对比5 l 图3 1 4b c b f + h s e f 与c b f 的错误率对比5 2 图3 1 5 数据集1 d c f , c b f 和h c b f 空间复杂度5 2 图3 1 6 数据集2 d c f , c b f 和h c b f 空间复杂度5 2 第v 页 国防科学技术大学研究生院博士学位论文 图3 17d c f , c b f 和h c b f 时问复杂度对比5 3 图3 1 8d c f 和h c b f 错误率对比5 3 图4 1 一个偏移小波树的例子5 6 图4 2 一个窗口大小为8 的聚合塔实例5 6 图4 3 聚合塔的阴影和叠加示意图5 6 图4 4 聚合塔与偏移小波树关系示意图5 7 图4 5 经典聚合塔和比值聚合塔中内容的比较5 8 图4 6 由比值聚合塔计算倾斜塔6 0 图4 7 比值聚合塔的更新6 0 图4 8 近年来中国信息化的进程6 3 图4 9 文本流突发检测流程图6 3 图4 1 0 在线处理算法实例6 6 图4 1 1 批处理算法实例6 7 图4 1 22 0 0 5 年八个典型关键词每日数量及文本总量。6 8 图4 1 3 基于r a p 和彳尸在不同阈值下检测到的突发数目。6 8 图4 1 4a p 和r a p 处理时间对比6 9 图4 15 么p 和r a p 存储开销对比6 9 图4 1 6 不同阈值和窗口大小检测到的突发数目6 9 图5 1 树形网格划分示意图7 2 图5 2p x p 网格均匀划分方法7 2 图5 3 基于合并的非均匀划分7 3 图5 4 网格单元相邻的定义7 4 图5 5 网络监控示意图7 5 图5 6 多监测任务协同处理方法执行流程7 7 图5 7 网格划分定义示意图7 8 图5 8 解决方案框架示意图7 9 图5 9b i r t h 和d e a t h 变化示意图8 3 图5 10e x p a n d 和s h r i n k 变化示意图8 3 图5 1 1u n i o n 和勋胁变化示意图8 3 图5 1 2 黝沙变化示意图8 4 图5 1 3 离群点示意图8 4 图5 1 4 突发示意图8 4 图5 1 5 弱离群点和强离群点。8 6 图5 1 6 弱突发和强突发8 6 第v i 页 国防科学技术大学研究生院博士学位论文 图5 17g d m m t p m 、g b c a 与c l u s t r e a m 处理时间对比8 8 图5 1 8g d 一膨坛伊从g b c a 与c l u s t r e a m 内存使用对比8 8 图5 1 9g d m m t p m 各种事件类型的检测精度8 9 图5 2 0g d - m m t p m 各种事件类型的检测召回度8 9 第v i i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得的研 究成果尽我所知，除了文中特另4 加以标注和致谢的地方外，论文中不包含其他人已 经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它教育机构的学 位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意 学位论文题目：熬量速塞发撞测羞王差缝技苤叠究 学位论文作者签名：刍皂垄垦日期：知。髟年。月7 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定本人授权国 防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允 许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索， 可以呆用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密学位论文在解密后适用本授权书) 学位论文题目：熬量速塞塞捡型羞王差缝撞盔亟究 学位论文作者签名：盘查垦 日期：刎年。月7 日 作者指导教师签名：啦日期：? 哟年f 口膏 日 国防科学技术大学研究生院博士学位论文 第一章绪论弟一早珀t 匕 随着计算机技术的迅猛发展和网络应用的日益广泛，数据流技术受到了科研 人员和工程技术人员持续关注。由于数据流技术契合越来越多应用场景的特点， 其在金融电讯、科学计算、网络安全、传感器网络等众多领域有着越来越广泛的 应用。 数据流指的是一组持续彳、= 断到达的、带有时间标签的元素序列。由于数据流 难以预测，因此数据流的本质特征是其变化性。作为数据流一种基础且重要的处 理方法，数据流突发检测能够及时检测到数据流中特定元素数量的异常变化，因 此得到了学术界和工业界的广泛关注。在数据流挖掘领域，数据流突发指的是数 据流中某时间段内特定元素的数量发生异常，具体实例有：光子爆发、股票波动、 网络流量异常波动等等。 基于数据流的处理技术已经成为当前的一个研究热点，数据流突发检测是一 个新兴的、有着广泛应用背景、深刻技术背景的研究方向。本文围绕如何存高速、 海量的数据流上进行有效的突发检测这一热点问题展开研究。 本章的行文安排如下：1 1 节首先介绍数据流突发检测的研究背景，给出数个 突发检测的实例，并引出数据流突发检测；1 2 节介绍数据流突发检测的相关研究 工作，包括通用的数据流模型、数个已有的数据流处理应用以及突发检测的相关 研究工作；1 3 节给出本文工作的简单介绍，包括主要研究内容及主要创新点：1 4 节给出论文的总体结构。 1 1 1 突发检测需求背景 1 1 研究背景 自上世纪以来，在金融市场、天文监测、网络监控、电讯管理、传感器网络、 互联网分析等众多领域中出现了一种新的数据产生方式和应用模式。该类数据和 应用的共同特点是数据持续不断地产生、在时间维度上有先后顺序、其数值不断 地变化、数据规模一般都十分庞大且增长迅速。这种新的应用模式被称为数据流 模型【1 3 】。 近年来，数据流的分析处理和挖掘日益成为数据处理分析领域的热点和焦点 问题，基于数据流的挖掘技术【4 - 9 】( 分类、聚类、频繁项挖掘、关联规则等) 、数 据流查询技术( t o p k 查询1 1 1 、s k y l i n e 查询【1 2 - 2 0 1 、极值查询1 2 1 2 5 1 、阈值查询陷2 5 】 等) 已得到广泛而充分的研究。数据流是一个新兴且交叉性极强的学术领域，融 合了数据库、数据挖掘、海量信息处理、概率论等多种已有技术及方法，因此， 第l 页 国防科学技术大学研究生院博士学位论文 数据流的分析处理和挖掘也非常具有挑战性。 数据流的本质特征是其变化性及不可预测性。作为数据流一种基础且重要的 数据分析方法【8 】，数据流突发检测已在许多实际领域有着广泛的应用，以下数个实 例是数据流应用场景中的突发现象： 实例一：天文现象监控。在美国，天文学家在一个足球场大小的“天文望 远镜”上布满光敏感的探测器，使用这种探测器来持续监测宇宙中高能光 子的数量【2 酬。如果光子数量在某段时间内达到某个阈值，那么认为这是伽 玛射线爆发。伽玛射线爆发是发现黑洞和其他天文现象的基础，因此必须 及时检测到，然后才能调动更多的资源来观察这个事件，得到更加翔实和 准确的结果，以便进行进一步的分析。 实例二：金融信息分析。股票价格的异常波动无论从宏观层面还是从微观 层面来说都是对股票市场本身的巨大伤害。从宏观层面来说，异常波动将 加大整个金融体系的系统风险，并使作为资源配置指标的股价信号产生失 真。从微观层面来说，异常波动将使众多大众股民对市场失去信心。而通 常说来，股票的异常波动通常由人为事件引起，因此必须及时检测到这种 事件。在股票交易中，股票的交易量是一个非常重要的参数。如果某支或 者某几支股票的交易量突然增加或者减少，其中一定存在特殊事件发生， 这个事件通常会指导价格的走势，因此是非常值得关注的。 实例三：网络监控。d d o s 攻击检测p 7 】中，由于传统的基于规则的d d o s 攻击检测方法和基于聚类的数据挖掘方法难以把攻击流与正常的“f l a s h c r o w d ”区分开来，因此效果都不显著。研究表明【2 引，现有d d o s 攻击多 为高分布式和高源i p 地址伪装，即通过随机函数产生i p 地址，因此在一 次d d o s 攻击中，只有0 6 1 4 的i p 地址是以前出现过的。而在一次正 常的“f l a s hc r o w d ”中，大约有8 2 9 的i p 曾经发送过请求。也就是说， 可以对网络流量和i p 地址进行监测与统计，当网络流量急剧增加时：如 果所观察到新i p 地址的增加是显著的，那么就可以判定发生了d d o s 攻 击；如果网络中出现的i p 地址以很大概率在一定时期内重复出现，则判 定这是一次正常的“f l a s hc r o w d ”( 当然“f l a s hc r o w d 是另一种性质的 突发，即流量负载突然增大) 。s i m 2 9 】( s o u r c ei pa d d r e s sm o n i t o r i n g ) 机 制就基于这种特性来检测d d o s 攻击。 实例四：在线事务口志分析。中国网民数量的爆炸性增长为国内w e b 网 站的出现和成长提供了大量的机会，网站管理员可以通过监测和分析网站 的访问日志，得到其所需要的各种信息：一、记录访问用户的人员组成情 况及个人偏好等信息，有的放矢地为用户投放恰当的广告，推荐恰当的产 第2 页 国防科学技术大学研究生院博士学位论文 品等；二、通过对特定公开电子媒体( 博客、论坛等) 的监测，了解民众 对舆情的关注情况；三、对某些重点关注的网站( 例如奥运新闻报道服务 器) 的服务器访问流量进行监测，在访问流量突然异常增多的时候进行流 量控制进行保护，以应付可能出现的网络攻击【3 0 ，3 1 1 。通过对网页点击流日 志的分析，可以对网页服务器的服务质量进行优化，并可防范恶意点击现 象【3 2 3 4 】： 总结以上数个数据流实际应用场景的共性可以发现：其应用特征都是数据流 中特定元素在特定时间段内数据量突然增多或者减少，也就是前文所说的数据流 突发现象。在后文的具体章节中，仍将以这些实例为背景，详细阐述本文的具体 工作内容。 1 1 2 突发检测的提出 数据流是一种和数据库概念并列的数据表示、存储和处理方式，在其基础上 可以进行多种类型的分析处理和挖掘操作。作为数据流一种基础且重要的数据分 析方法，z h u 等【2 6 】最早提出了突发检测问题。数据流突发指的是数据流中某时间 段内特定元素的数量发生异常，它属于一种特殊形式的数据流异常变化。一般来 说，突发检测的处理流程为： l 、同时对数据流中的多个元素进行监测； 2 、得到每个元素在滑动窗口内的聚集函数值( 例如s u m 、c o u n t 等) ； 3 、对单个元素而言，如果该聚集值显著偏离其它时间段滑动窗口的聚集值， 那么进行报警，认为这是一次突发； s c a l ei sb a s e do nt h ea v e r a g et r a f f i co f 锵卧撂f r o mc h i n ai n 掣尝叫a 三竺罗悃 0l lli ii n2 22 i 瞎j u a n 2 * 3 l fi；il 挂野拇s 野幻雅f 0 辑鹕缸m 舒 一 l 图1 1 互联网关键词突发一俯卧撑 第3 页 国防科学技术大学研究生院博士学位论文 图1 1 给出了一个互联网关键词突发的实例【3 川。在该实例中，持续监测互联网 中各关键词每天的搜索和访问频率，如果某天的搜索和访问频率显著地偏离了前 面一天，那么就认为该关键词在某天出现了突发现象。图中关注一个词汇：俯卧 撑。从7 月1 日开始到7 月3 口结束，该关键词的数量与前一天相比，有显著的 上升。因此认定，从7 月1 日到7 月3 日，“俯卧撑出现了突发现象。 从突发检测的实例可以看出，突发检测的目标有三个：1 、找出数据流中突发 的元素( 在该实例中为“俯卧撑 ) ；2 、得到突发的类型，是突发增加还是突发 减少( 在该实例中为突发增加) ；3 、找出突发的时间段，包括起始时间和持续时 间( 在该实例中为7 月1 日始，持续三天) 。 1 2 相关工作分析 前面一节介绍了本文的研究背景，并给出了数据流突发检测的应用背景以及 和突发检测的基本概念。在本节中，将详细介绍数据流及其突发检测的相关研究 工作及进展，并在本节末尾总结相关研究工作。 1 2 1 数据流模型 数据流可看作是一个连续不断增长的元素序列x 。, x 2 x 。，各元素都带有 时间标签。由于数据流是无限的，因此对数据流的分析处理和挖掘操作通常基于 某个特定的时间区间( 这里称之为窗v i ) 进行，常用的窗口模型有三种【播3 9 】： l 、界标窗口模型( l a n d m a r kw i n d o w m o d e l ) 。在该窗口模型下，处理的数据 集为从数据流开始到当前到达的所有元素的集合，且窗口大小随数据流进 行不断增加。 2 、跳动窗口模型( j u m p i n gw i n d o wm o d e l ) 。在该窗口模型下，每当，个元素 到达时，窗口才向前滑动，个位置，其中，小于窗1 3 内数据元素个数。 3 、滑动窗口模型( s l i d i n gw i n d o wm o d e l ) 。在该窗口模型下，被用来挖掘的 数据集为从当前时标开始，最近到达的个元素的集合( 这里的为滑动 窗口的大小) ，窗口位置在时间轴上随着数据流进行不断滑动。 另外，窗口大小的度量有两种选择：一种基于时间进行度量，另一种基于元 素个数进行度量。在实际应用中，窗口模型的选取往往根据用户的需求而定。在 本文中关注的是新数据，且新数据的权重一致，因此选用滑动窗口模型。 数据流处理模型如图1 2 所示：该模型在内存中维护一个远小于原始数据规模 的数据结构，称为“概要数据结构”，用以反映原始数据的特性。新数据到达时， 不断更新概要数据结构的内容；而在任何时刻，用户都可以通过概要数据结构得 到满足精度要求的查询结果。研究者可以根据数据处理功能的实际需要，设计出 第4 页 国防科学技术大学研究生院博士学位论文 满足自己需求的概要数据结构。一般而言，直方图、抽样、小波、哈希等都是构 造概要数据结构的常用方法。 s i i 图1 2 数据流处理模型 度约束 结果流 和传统数据模型相比，数据流模型具有截然不同的特性，这对数据流模型下 的分析处理技术提出了新挑划2 挪】。概括言之，主要有以下几个方面的挑战： 实时性。连续地、实时地输出查询结果是数据流算法最基本的要求。对于 数据流上到达的任一元素，要求数据流算法能很快处理完成。否则，数据 不断到达、延时不断积累，最终导致服务质量显著降低。 低空间复杂度。数据流的规模在理论上是无限的，为保证算法持续稳定运 行，数据流算法的空间复杂度要非常小，其空间占用量的增长速度要远