（计算机软件与理论专业论文）一种改进的数据流突变检测算法的研究.pdf

哈尔滨工程大学硕士学位论文 摘要 数据流突变检测是数据流研究领域中的一个重要分支，受到越来越多的 科研学者的高度重视。数据流突变检测的应用非常广泛，可以应用在金融、 灾害预警、网络流量监控等重要领域。目前存在的数据流突变检测算法多数 集中在检测单调聚集函数的突变，且都是利用固定滑动窗口来检测数据流的 突变，而用于突变检测的数据结构不能适应数据流实时更新的特点，缺乏灵 活性和适用性。为提高大规模、连续数据流的突变检测效率，需要研究新的 实时性和伸缩性强的数据结构和精确度高的数据流突变检测算法。 本文在分析和研究国内外数据流突变检测技术的基础上，对现有数据流 突变检测算法进行改进，优化数据流的输入，提高数据流突变检测的效率。 针对现有的数据流突变检测算法存在的不足，本文给出一种改进的数据流突 变检测算法。该算法与现有的算法相比具有如下优势：第一，对输入的数据 流进行优化，能够将负数据流、以及正负交错数据流都转变成非负的数据流， 从而放宽输入数据流的限制条件j 并且可以处理非单调聚集函数的突变；第 二，构建了一个弹性的数据结构，能够高效的检测潜在突变的数据流；第三， 该算法能够用较少的时间检测潜在突变的数据流，从而提高数据流突变检测 的效率，降低了数据流突变检测的时间复杂度。 为验证本文给出的数据流突变检测算法的可行性和有效性，利用网络真 实访问量和人造数据集进行仿真实验，实验结果表明与同类突变检测算法相 比，所给出算法在正负交错数据流突变检测中具有较小的检测时间开销和较 高的检测精度。 关键词：滑动窗口；突变检测；阈值；数据流突变 哈尔滨工程大学硕士学位论文 目宣暑暑葺暑置葺暑暑置| 皇_ i _ 宣置；i 置i 宣i 宣_ 嗣宣宣i 宣暑宣i 皇昌_ 冒i _ _ _ _ _ _ _ 置 a b s t r a c t t h eb u r s td e t e c t i o ni nd a t as t r e a m si sa ni m p o r t a n tb r a n c ho fr e s e a r c hi nt h e f i e l do fd a t as t e a m sa n dh a sb e e na t t r a c t i n gm o r ea n dm o r es c h o l a r s a t t e n t i o n t h eb u r s td e t e c t i o ni nd a t a s t r e a m r s h a sw i d ev a r i e t yo fr e a lw o r l da p p l i c a t i o n s f o ri n s t a n c e ，i tc a r lb ea p p l i e dt of i n a n c i a l ，m o n i t o r i n gn e t w o r kt r a f f i ca n do t h e r c r i t i c a li m p o r t a n ta r e a s e x i s t i n gb u r s td e t e c t i o nm e t h o d sm o s t l yb ef o c u s e do n b u r s to fm o n o t o n o u sa c c u m u l a t i o nf u n c t i o n ，w h i c ho n l yb cf o c u s e do nf i x e d s l i d i n gw i n d o w s m o r e o v e r , t h ed a t as t r u c t u r e so fb u r s td e t e c t i o na l g o r i t h m sc a n n o tb ea d a p t e dt or e a l - t i m ec h a n g e a b l ec h a r a c t e r i s t i c so fd a t as t r e a m s h e n c e ，a r e a l t i m ed a t as t r u c t u r ew i t hs t r o n gf l e x i b i l i t yi sn e e d e d ，a tt h es a m et i m e ，a h i g h p r e c i s i o na l g o r i t h mt od e t e c tb u r s ti nc o n t i n u o u sa n dh u g ea m o u n to fd a t a s t r e a m si sn e c e s s a r y i nt h i st h e s i s b a s e do nt h ea n a l y s i so fb u r s td e t e c t i o nt e c h n i q u e s ，t h eb u r s t d e t e c t i o na l g o r i t h ma n do p t i m i z i n gt h ei n p u to fd a t as t r e a m sa r ei m p r o v e d o u r m a j o rc o n t r i b u t i o n sa sf o l l o w s ：1 a ni m p r o v e da l g o r i t h mo fb u r s td e t e c t i o no v e r d a t as t r e a m si sp r o p o s e d c o m p a r e dt ot h ee x i s t i n ga l g o r i t h m ，t h ea l g o r i t h m p r e s e n t e di nt h i st h e s i sh a st h ef o l l o w i n ga d v a n t a g e s ：t h ef i r s t ，t h ea l g o r i t h r no f o p t i m i z i n gt h ed a t as t r e a m so nt h eb a s i so f s h i f t e da g g r e g a t i o nt r e ei sp r e s e n t e d s ot h ea l g o r i t h mc a nn o tb eo n l yr e l a x e dt h ec o n s t r a i n tc o n d i t i o n so ft h ei n p u ti n d a t as t r e a m s ，b u ta l s oc a nb ec h a n g e dn e g a t i v ed a t as t r e a m so rt h ep o s i t i v ea n d n e g a t i v ed a t as t r e a m si n t on o n n e g a t i v ed a t as t r e a m s ，w h i c hc a n b eh a n d l e dt h e b u r s to fn o n - m o n o t o n o u sa g g r e g a t i o nf u n c t i o n t h es e c o n d ，t h ed a t as t r u c t u r ei s c o n s t r u c t e d ，i ti sas u i t a b l ee l a s t i cd a t as t r u c t u r et h a tc a nb ed e t e c t e dt h eb u r s ti n d a t as t r e a m se f f i c i e n t l y t h el a s t , t h ea l g o r i t h mc o s t sl e s st i m et od e t e c tb u r s ti n d a t as t r e a m s ，t h e ni m p r o v e st h ee f f i c i e n c yo fb u r s td e t e c t i o n , a n dr e d u c e st h et i m e c o m p l e x i t y t h e o r e t i c a l a n a l y s i s a n d e x p e r i m e n t a l r e s u l t ss h o wt h a tt h e i m p r o v e d 哈尔滨工程大学硕士学位论文 a l g o r i t h mp r o p o s e di nt h i st h e s i si ss u i t a b l ef o rb u r s td e t e c t i o no v e rd a t as t r e a n m i tc a nb ec o n c l u d e dt h a tt h ea l g o r i t h mp r o p o s e di nt h i s p a p e rc a nb ea c h i e v e d h i g h e rp r e c i s i o nw i t hl e s st i m ec o m p l e x i t yc o m p a r e dw i t he x i s t i n gr e s e a r c h a l g o r i t h m s k e y w o r d s ：s l i d i n gw i n d o w ；d a t as t r e a m s ；b u r s td e t e c t i o n ；t h r e s h o l d ；b u r s ti nd a t a s t r e a m s 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ： 日期：年月 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ： e l 期： 年丹- 一e l 黑警涉嘲 1 年；月l 一 _ 哈尔滨工程大学硕士学位论文 第1 章绪论 1 1 课题研究的目的和意义 随着数据库技术突飞猛进的发展，很多领域都出现了海量的、高速的、 实时的大规模数据，数据流作为一种新兴的数据形式应运而生。由于数据流 与人们的日常生活息息相关并且具有广泛的应用前景，受到广大数据库和实 时系统科研学者的广泛关注。数据流早期出现在银行、股票交易市场等国家 的金融机构。例如在股票交易市场中对股价波动的追踪、都离不开对数据流 技术的分析、研究和探索。尤其是近年来随着互联网的快速发展，大量的流 类型的数据涌现出来，数据流也被广泛的应用在网络流量的监控、电信中信 息流量的监测、灾害监测系统的预警等。与此同时数据流也被应用到了生态 环境的指标监测、地质的勘探与测量、天气预报、宇宙观测等。随着数据流 的进一步发展，数据流技术逐渐成为现代数据库技术研究的主要方向之一。 由于数据流本身具有实时的、连续的、有序的特点，所以对数据流技术的研 究也面临着很多新的挑战“，。 数据流突变检测技术作为数据流技术的一个重要方向，受到了越来越多 的数据库研究人员的关注。数据流突变检测技术具有广泛的应用领域。例如 股票交易中的股票价格的突变，对股票市场和炒股者来说都是一个不小的风 险。在生态环境的监测中，生态指标的突变，是影响生态环境标准的重要因 子。在网络流量管理中，对每个连接所用的带宽进行实时的监控，检测一段 时间内网络的流量是否超出了给定带宽的阈值，从而探索出网络拥塞的原因 “。数据流突变检测技术的研究目前还存在许多难以解决的问题，其面临的任 务也是十分艰巨，需要研究人员进一步深入的研究和探索。 目前数据流突变检测算法存在很多不足。第一，算法多数是集中在检测 简单的单调聚集函数的数据流突变，对于非单调聚集函数和复杂聚集函数的 突变还没有一个合适的算法。第= ，数据流突变检测算法采用的数据结构也 哈尔滨工程大学硕士学位论文 存在着一定的局限性，对输入的数据流都有一定限制条件，缺乏一个很好的 适应各种数据流实时变化的数据结构。第三，多数算法都是检测固定滑动窗 中数据流的突变，对于不同滑动窗口的实时变化的数据流突变检测还缺乏有 效的手段，。第四，目前的很多算法受到环境等外界因素的影响，算法的执行 效率会大大降低- 。第五，现有韵突变检测方法往往需要用户或者领域专家对 大量的参数凭经验预先进行设置，这些参数设置的是否合适将直接影响检测 结果- 。 因此针对以上几点不足，为了检测实时变化的数据流的突变，提高突变 检测的效率，需要构建一个实时性和伸缩性强的数据结构来优化数据流的输 入，同时需要一个适应性强的数据流突变检测算法对输入的数据流进行高效 检测。在构建的数据结构基础上给出的改进的数据流突变检测算法具有如下 的优点： ( 1 ) 对输入的数据流放宽限制条件，输入的数据流既可以是正的数据流， 也可以是负的数据流，也可以是正负交错的数据流。 ( 2 ) 不仅可以检测简单魄单调聚集函数值的突变，也可以检测复杂的非 单调聚集函数值的突变。 ( 3 ) 构建的突变检测的数据结构能够很好的平衡构建其结构的时间开 销和检测潜在突变的时间开销，具有高效的实时性和伸缩性。 ( 4 ) 算法能够提高突变检测的效率，具有广泛的应用性。 1 2 数据流突变检测的研究现状 1 2 1 数据流突变检测的国内研究现状 国内关于数据流突变检测技术主要集中在基于滑动窗口上的聚集函数值 r i 的突变检测的研究上。包括单个滑动窗口的简单聚集函数的突变检测和复杂 聚集函数以及非聚集函数的突变检测。最近复旦大学秦首科博士对数据流的 突变检测技术有了深入的研究并提出了数据流异常检测技术，这是对数据流 突变检测技术的扩充和创新。其中有基于直方图的数据流突变检测技术、基 2 哈尔滨工程大学硕士学位论文 一ii i i 一i i - 于单调搜索空间的数据流突变检测算法和基于分段分形模型的数据流突变检 测算法。 基于直方图的数据流突变检测技术更加全面的概括了数据流上的突变信 息，并且排除了颠簸数据的干扰，能够在较小的时间和空间开销下精确的完 成检测任务盯- 。此外还能为数据流的突变检测提供更加准确的聚集查询支持， 更加适用于数据流上的突变检测。此外，该算法严密的理论分析和证明为基 于的突变检测技术提供了理论上的误差界限，保证最终的数据流突变检测结 果具有较高的准确率。与现有算法相比，基于直方图的数据流突变检测技术 在突变检测的准确率以及效率芳面有突出的优势h 一。基于单调搜索空间的数据 流突变检测算法具有较高的精确度和较低的时间和空间复杂度，更加适用于 数据流上的突变检测。基于分段分形技术的数据流突变检测算法己被证明能 够为异常检测提供准确的结果，具有很高的执行效率。此外基于分形技术的 数据流突变检测算法，在数据流突变检测中引入了自然界中的分形概念哺，并 提出分形分析技术，建立分段分形模型，降低数据流突变检测的时间复杂度 和空间复杂度，并保证一定误差界限的条件下，被用于重构原始数据流 王永利、徐宏炳等人针对传统数据流异常检测中存在的数据量大、实时 性差、对异常数据在线修复的精度偏低等缺点提出数据流上异常数据的在线 检测与修正。该算法成功的将遗忘因子引入到异常数据的检测中，并对 k a h n a n 滤波预测算法进行改进，不仅能够检测历史时刻的异常数据而且还能 够检测未来时刻的异常数据。通过连续异常数据量的不同，采用插值小波来 实现对在线异常数据的实时修补，从而提高了数据流上异常数据的修正精度 和检测异常数据的速度n ”。 宋国杰、唐世渭等人提出的数据流中异常模式的提取与趋势监测算法具 有高效性和可行性。该算法通过将t p s s 概念应用到滑动窗口中，从而为异常 模式的提取与趋势预测提供支持。同时还建立了关联度指标的计算方法将外 界的干扰因素有效去除后，保留符合要求的模式，并在此基础上采用回归分 析方法进行异常模式趋势预测“u 。 蒋盛益、姜灵敏针对传统数据流异常检测算法中存在的时间复杂度高、 数据集规模大以及算法适应性差等缺点提出了一种高效异常检测方法。该算 法通过对第二阶段数据对象的异常因子与所有异常因子的均值和方差进行比 3 哈尔滨工程大学硕士学位论文 较，并将基于最小差异的聚类算法应用到异常检测算法中，从而提高了算法 的时效性和准确性u ”。 1 2 2 数据流突变检测的国外研究现状 国外的各研究机构都对数据流突变检测技术有了广泛的探索和研究。国 外与数据流突变检测相关领域的代表性研究包括： 2 0 0 0 年c s h a h a b i ，x t i a a 和w z 蛳究了数据库中趋势和异常的检测， 该算法降低了时间和空间的复杂度“”。2 0 0 1 年，j o h a n n e sg e h r k e 、f l i pk o m 和d i v e s hs f i v a s t a v a 使用了很小的空间来模拟计算界标模型和滑动窗口中的 相关数据流的聚集值，并探索出了单调收敛数据流聚集的重要属性。界标模 型和滑动窗口模型由于要不断地处理新来的数据，更接近于真实应用。因而 该算法的提出为连续数据流的进一步研究做出了巨大的贡献“”。2 0 0 3 年， y z h u 和s h a s h a 在数据流上提出了一种高效的聚集函数值突变的检测算法，该 算法建立一种平移小波树的数据结构，通过检测s w t 的少数几层就能够判断 是否有数据流突变检测发生“劓。2 0 0 3 年，y z h u 和s h a s h a 提出了一个快速检测 金融交易的时间序列数据流的突变方法。该方法能够快速的找到在时间序列 上密切相关的数据流和不容易发生突变的数据流，提高了突变检测的速率， 降低了时间及空间的复杂度n ，。 2 0 0 4 年，m i e h a i lv l a e h o s 和c h r i sm e e l c 通过傅立叶变换压缩了时间流，节 省空间的开销，但是在时间上却有很大的开销n “。2 0 0 5 年，a b u l u t 和a k s i n g h 提出一种更为高效的聚集函数值突变的检测算法。该算法使用一种新颖的索 引机制( 分层的最小边界矩形) ，能够在数据流上进行更加快速的突变检测“。 2 0 0 5 年，a o y i n gz h o u 、s h o u k eq i n 和w e i n i a gq i a n 提出自适应的突变检测算 法，能够保证用户能够以很高的准确率以及较小的时间开销和空间开销检测 数据流上的突变“”。2 0 0 5 年，s i m o ns h e u 、c h a n gy e n gc h e n g 和a l a nc h a n g 研究基于决策树的快速模式的数据流的突变检测。该算法通过优化需要检测 的数据流，使检测的数据流的数量保持最小，从而使检测数据流的速度提高 了4 到5 倍啪。2 0 0 6 年，x i n z l m 和提出了数据流弹性突变检测 算法，该算法提高了数据流突变g 检d 测e n 的n i 速s 度s h a ，s h 降a 低了搜索的时间复杂度悖“。 4 哈尔滨工程大学硕士学位论文 i i i i i i i - 2 0 0 6 年，t m g t i n gc h e 嘲y iw a n g 提出基于两层小波树的数据结构来检测持续 的数据流突变，该算法能够芘g 讨r 节省存储空间，并且提高了算法的效率川。 1 3 论文的主要研究内容及结构 数据流已经与人们的日常生活息息相关，而数据流技术更是逐渐发展成 为现代数据库技术研究的主要方向之一。数据流是具有一定的速度的，连续 到达的数据集序列。由于本身具有实时性、连续性、突变性等特点，因此对 于数据流相关技术的研究也是广大学者一直关注的课题。随着数据流技术的 快速发展，数据流的突变检测技术的应用也日益广泛并具有实际的研究价值。 为了检测实时的、连续变化的数据流的突变，提高数据流突变检测的效率， 需要建立一个数据流的优化算法对输入的数据流进行优化：需要构建一个实 时性和伸缩性强的数据结构能够根据输入数据流的不同特征自动调节结构的 密度；需要建立一个突变检测算法对输入的数据流进行高效的检测。本文正 是基于以上几点对数据流突变检测技术进行了深入的研究，并以建立数据流 突变检测的模型对输入数据流进行优化构建实时性和伸缩性强的数 据结构给出数据流突变检测的算法为主线组织和安排论文结构。论文的 主要内容安排如下： 第l 章论述了本课题研究的目的和意义，对数据流突变检测的相关理论知 识、理论模型和技术方法进行深入的研究，并总结数据流突变检铡技术的国 内外研究现状。 第2 章从数据流出发，介绍了数据流的概念、数据流模型以及在此模型上 数据流突变的概念，为后面建立数据流突变检测模型奠定了理论的基础。 第3 章分析研究了本课题的相关技术，论述了数据流突变检测的数学基 础、数据流突变检测的数据结构以及突变检测的原理。从而为构建数据流突 变检测的模型和数据流突变检测的算法打下了基础。 第4 章通过对现有的数据流突变检测算法的研究，首先建立了数据流突变 检测模型，在此基础上给出一种改进的数据流突变检测的算法。然后详细的 阐述了算法的三个阶段包括数据流的优化，构建突变检测的数据结构以及基 于嵌入型迁移聚集树的数据流突变检测。 s 哈尔滨工程大学硕士学位论文 第5 章对改进的数据流突变检测算法进行仿真实验，并应用突变检测的数 学基础对实验结果进行理论分析。实验结果和理论分析表明了本文给出的基 于嵌入二维数组的迁移聚集树的数据流突变检测算法具有正确性和可行性。 6 哈尔簇巍大学硕士学位论文 第2 章数据流与突变概述 数据流的基本概念和数据流的模型是研究数据流突变检测技术的基础， 本章将分别介绍数据流的概念、数据流的特点、数据流的类型、数据流模型 以及数据流的突变概念，为后面的研究工作奠定基础i 2 1 数据流 随着数据库技术的迅猛发展，和人们日常生活息息相关的很多领域都出 现了大量的、实时的、高速的、动态的数据，于是一种新的数据形式擞 据流应运而生。数据流的出现已经成为了数据库的一个新的研究方向，它的 应用也非常广泛。如金融市场基金的波动、电信部门通话信号的强弱、生态 环境指标的监测、交通信号的监控、网络流量的实时监测等旧- 。数据流作为 数据的一种动态的形式，可以形象的描述数据的流动性，并体现了数据的无 限性、实时性、连续性等特点。 2 1 1 数据流的基本概念 数据流是大量的、连续的、，实时的、有序的数据项组成的序列。若令t 表示任意一个时刻，x 。为t 时刻的数据项，那么数据流可以表示为 x i , x 2 ，x 3 ，函，x m 住”。随着不同时刻的数据项的到来，数据流可以看作是 由一系列数据项的插入与删除所组成的数据项的序列。数据流的长度即为所 包含的所有数据项的个数。一般来说，数据流的长度随着不同的时间实时更 新，在某一时刻既存在新的数据项的到来，又存在历史数据项的消失。所以 数据流是一个没有界限的数据序列，其速度和数据项到达的次序都是无法控 制的。由于数据流的规模无限、数据项的取值无限以及数据项不同的分布特 征，因此对数据流的深入研究也受到了广大数据库研究者的高度重视。 7 哈尔滨工程大学硕士学位论文 2 1 2 数据流的特点 数据流由于其本身的流动性屯与传统的数据有着本质的区别和特性。数 据流的特点如下： ( 1 ) 数据流具有流动性、实时性。数据流中的数据是一种流动形式出现 的，并且随着时间的推移不断的变化。可能会有新的数据项的到来，也可能 会有历史数据项的流逝。 ( 2 ) 数据流具有连续性、有序性。数据流中的数据项是连续的、不间断 的出现的，并且随着时间的不同，到来的数据项具有一定的先后次序暗1 。 ( 3 ) 数据流具有大量性、无限性。数据流中的数据是海量的，甚至是无 穷的。因此要存储这些数据需要耗费大量的空间，所以对数据流的压缩和存 储也成为了研究人员的一个研究的热点。 ( 4 ) 数据流具有单遍性。由于时间和空间的限制，对数据流中的数据项 只能扫描一次。这就给数据流牛数据的处理带来了一定的困扰，尤其是对那 些无法保存的历史数据的关注和研究。 ( 5 ) 数据流还具有一定的突变性。数据流中的数据在某一时刻由于受到 外界等环境因素的干扰发生了突变，与原始的数据有较大的异常。发生突变 的数据流可能会给某一问题的研究带来误差或者是错误，这无非会给研究人 员带来更大的难题。 2 1 3 数据流的类型 随着研究人员对数据流的深入研究，对数据流的类型也大致分为三种类 型，即基于时间序列的数据流、基于收银机类型的数据流和基于转盘类型的 数据流k 一。 1 基于时间序列的数据流 该数据流中的数据项随着时间的不同是以一定顺序出现。例如数据流中 数据项的下标是升序排列的，即每一个新到的数据项的下标都比它的前一个 数据项的下标大。本文可以更具体的描述基于时间序列的数据流为 8 哈尔滨工程大学硕士学位论文 一i i_t i 一_ _ x i x l 并2 冯，, x t ，x 伽，其中x l 为时间声l 时刻的数据项，x 2 为时间声2 时刻 的数据项，依次类推为t 时刻到来的数据项。 2 基于收银机类型的数据流 该类型的数据流规定数据流中的数据项可以不用排序，即数据项的下标 可以不用按照一定的顺序排列，并且允许数据项的重复出现。但它要求每一 个数据项的值必须是非负的，即限制了输入数据流的条件，这一规定在检测 数据流单调聚集函数值的突变上有广泛的应用。此外这种类型的数据流限制 了数据项只能添加，不能减少：卸不能实现数据项的删除操作，。 3 基于转盘类型的数据流 这种类型的数据流对数据项的下标没有任何要求，即可以排序也可以不 用排序，同时对数据流中的数据项的值也没有了限制的条件。既可以是非负 数据项，也可以是正的数据项。可以对数据进行增加、删除操作。 上述三种类型的数据流都广泛的应用在现实的生活领域。其中应用最多 的是基于时间序列的数据流，本文采用了基于时间序列的数据流作为研究的 对象。 2 2 数据流模型 数据流作为一种动态的数据：充分的体现了它的实时性。正如前面介绍 的，目前数据流多是基于时间序列的类型。众多学者研究的对象都是在某一 时间范围内的数据流。例如y z h u 和s h a s h a 提出的基于迁移小波树的数据流 突变检测的研究；复旦大学秦首科博士研究的基于直方图的数据流突变检测 技术的研究等。所以按照时间的范围将数据流的模型分为三种：滑动窗口模 型、快照模型、界标模型的。 2 2 1 滑动窗口模型 滑动窗口的概念首先由加拿大d a t a p 拥的设计者提出的滑动窗口广泛 的应用在数据流监控中，是数据流上应用比较多的一种特殊数据抽样方法。 9 哈尔滨工程大学硕士学位论文 滑动窗口有基于数据元组数量和基于时间两种定义方式。而根据窗口更新粒 度的不同，又可分其为连续更新滑动窗口和周期更新滑动窗口两种类型忉- 。 数据流上的滑动窗口是指在数据流上设定的一个区间，该区间只包括数据流 最近最新的部分数据，随着数据不断的到达，窗口向前移动，表示新数据到 来，新数据替换了旧数据。相关的定义：数据流x 是一个按照时间递增顺序 排列的无穷时间序列，x = ( x i ，t 0 ，( x 2 ，t 2 ) ，( x 3 ，t 3 ) 9 0 - o ，( x i ，t i ) ，其中x l ，) 【2 , x 3 是数据 域v 中的值，而t l ，t 2 ，t 3 是时间戳，( x i , t 1 ) 代表t l 时刻的数据值为x i ，即每一个 数据值x i 都与一个时间戳t i 相联系。x h ，t i 】表示从时刻t i 到t i 时刻的子序列。设 滑动窗口的大小为w ，当前的时刻为t ，那么滑动窗口中的每个数据项的域空 间是v = x x t i w + i9 0 0 0 ，t i ，滑动窗口中的每个数据项v i 用( 砭，t i ) 表示。其中v i 是对应t i 时间戳的数据项，v i 是对应t i w 时间戳的数据项m 。滑动窗口随着时 间向前移动的过程可以用许多的数据项v i 的插入和v j 的删除来表示。 2 2 2 快照模型 快照模型是将处理数据流中数据的范围限制在两个预定义的时刻之间。 快照模型又可以分为连续快照模型和序列快照模型。 连续快照模型应用在数据流中的具体含义是：仅记录和保留数据流中的 当前的数据项，对于前一时刻的数据项或是历史数据项都不保留，即插入一 个新的数据项，就删除历史的旧数据项廿”。连续的时间快照模型是记录一段 时间范围内数据流中的数据项，以用来描述整个时间段内数据流的特性和状 态。 序列快照模型有矢量快照模型和栅格快照模型。它应用在数据流的含 义为：将系列时间片段的数据流中的数据项保存起来，各个时间片段分别对 应不同时刻的数据流的状态，以此来反映数据流中数据项的变化过程。同时 也可以根据需要对指定时间片段内的数据流进行研究。 无论是连续快照模型还是序列快照模型由于它们对将来的数据项允许重 复，所以会存储大量的重复的、冗余的数据项，会浪费很大的空间。 l o 哈尔滨工程大学硕士学位论文 序列快照模型有矢量快照模型和栅格快照模型m 。它应用在数据流的含 义为：将系列时间片段的数据流中的数据项保存起来，各个时间片段分别对 应不同时刻的数据流的状态，以此来反映数据流中数据项的变化过程。同时 也可以根据需要对指定时间片段内的数据流进行研究。 无论是连续快照模型还是序列快照模型由于它们对将来的数据项允许重 复，所以会存储大量的重复的、冗余的数据项，会浪费很大的空间。 2 2 3 界标模型 界标模型处理数据的范围从某一个已知的初始时刻到当前时刻为止。记 录下初始的时刻为t l ，当前的时刻为t l l ，则基于界标模型的数据流可以描述 为x x h , x t z , x t 3 ，x t d 。通常将数据流的起始点作为数据处理的初始时间点。 算法对数据流的数据只存在插入操作旧。 这三种模型在数据流技术的应用都很广泛。由于滑动窗口模型和界标模 型都要处理数据流中新到的数据项，所以受到研究人员的高度的重视和广泛 的关注。 2 3 数据流的突变 数据流中的数据在某一时刻由于受到外界等环境因素的干扰，很容易发 生与理想值存在很大的偏差，此时数据流就发生了突变。数据流的突变可以 分为简单的单调聚集函数的突变和复杂聚集函数的突变。 1 简单单调聚集函数突变 简单的单调聚集函数包括s u m 、r a i n 、m a x 、c o u n t 等单调的一阶聚集函数。 由于此类聚集函数具有一定的单调性，所以基于单调聚集函数的数据流突变 检测技术相对来说比较简单，而且也具有一定的应用价值。 简单单调聚集函数的数据流的突变定义为：给定设初始的一系列滑动窗 1 2 1 ，且每个滑动窗1 2 1 都包括时间序列的数据流。给定的聚集函数f ( w ) ，给定 的阈值f ( w ) 。当在某一个滑动窗口内发生t f ( w ) f 【w ) ，就会发生报警，即数 据流在窗口为w 或是w 的子序列发生了突变。因此可以确定报警域为 l l 哈尔滨工程大学硕士学位论文 窗口的聚集函数值，然后和给定的阈值进行比较后再确定报警域。但是这些 函数的统计特性要比单调聚集函数强，因此具有很好的研究意义。对于复杂 的聚集函数的数据流突变检测，可以采用一系列优化的方法将复杂的聚集函 数转化为单调的聚集函数再对数据流进行突变检测。 2 4 本章小结 本章综述了数据流与突变的相关研究工作。首先介绍数据流的基本概念、 数据流特点和数据流类型。其次阐述数据流模型包括滑动窗口模型、快照模 型以及界标模型这三种模型都可以应用到数据流的突变检测技术中。但目前 比较常用的数据流模型是滑动窗口模型。最后阐述数据流的突变包括简单单 调聚集函数的突变和复杂聚集函数的突变，为后面提出的数据流突变检测算 法奠定了基础。 1 2 啥尔滨工程大学硕士学位论文 第3 章数据流突变检测技术的研究 本章在对数据流模型与突变概述深入分析研究的基础上，分别阐述了数 据流突变检测的数学基础、数据流突变检测的数据结构和数据流突变检测的 原理。通过对数据流突变检测的数据结构、突变原理以及突变检测的数学基 础的分析与研究，为后面数据流突变检测的模型的建立以及数据流突变检测 算法的研究提供理论依据。 3 1 数据流突变检测的数学基础 由于本文的实验分析需要以概率论基础知识为数学理论依据，所以先介 绍一下实验中要用到的突变检测的数学理论。 随机变量及其分布函数是概率论和数理统计中的知识。随机变量的分布 函数主要有o 1 分布，二项分布，泊松分布，指数分布，正态分布等。其中泊 松分布和指数分布能够根据人们的需要有选择的产生综合数据，从而被人们 广泛的应用在模拟许多真实数据的广泛应用。 3 1 1 指数分布 一类数据是很相似而且无规则的，在一个时间单元内的不规则的数据遵 循着指数分布。随机变量x 的密度函数为： r 1 瓜到去p 7 工 0 ( 3 - 1 )厂( 工) 一 万d( 3 1 ) i - 0 工0 式中：工 o 为常数，则称随机变量服从参数为五的指数分布。 若随机变量x 服从参数为允的指数分布，则x 的分布函数为： 1 3 哈尔滨工程大学硕士学位论文 3 1 2 正态分布 l0 x 0 f ( 工) 2 1 1 一g 工工 o ( 3 - 2 ) 设随机变量x 的概率密度为： 1 j - i l 1 2 = 丧p 百 ( 3 3 ) 二7 o 则称随机变量x 服从参数为( ，口2 ) 的正态分布。记作x 似，1 7 2 ) 的正 态分布。当= o ，仃= l 时，称其为标准正态分布，记作n ( o ，1 ) 。 3 1 3 中心极限定理 设随机变量五，x ：，墨，是独立同分布的随机变量序列，e x 鬈= ， d x r = 仃2 ( 0 o - 2 + ) ，k = l ，2 , 3 ，则对任意的工r ，有如下公式： l = 以- e ( y x 。) 七一i七l l 五一掣 = 生l ，：一 ( 3 - 4 ) o 纷仃 分布函数c ( x ) 满足： t 一心 x ( 3 - 5 ) 这表明无论随机变量列x 。，x 2 ，x 3 一服从什么样的分布，只要满足定理 的条件，它总是以标准正态分布n ( 0 ，1 ) 为极限分布。因此，在实际应用中， 只要力足够大，便可把疗个矗立商分布的随机变量的和作为正态随机变量来 处理。无论是哪种分布，最后都会在一定的范围内综合带有不同分布参数的 1 4 哈尔滨工程大学硕士学位论文 数据作为训练的样本进行分析和验证，从而找到最终想要的数据结构。 3 2 数据流突变检测的数据结构 数据流突变检测的数据主要有小波、直方图、哈希表、迁移二叉树、聚 集金字塔以及迁移聚集树。 1 小波数据结构 小波数据结构被广泛的应用到数据库领域，它可以把数据从高维降到低 维，可以生成直方图等旧- 。小波数据结构也可以被应用到数据流突变检测技 术中，可以估算某一个滑动窗口中数据流的聚集函数和m 。但由于本身结构 的特点对于检测任一个子序列滑动窗口中的数据流突变还具有一定局限性。 h e a r 小波数据结构如图3 1 所示： 删广1 础 二二二二二二 二二二二二 。 删 二二二 二二 二二二 二二二 触 = 二 二 二 二 二 二 蒯 二 二 亡亡! 皿 籼匝田卫工工叩丑 田田 图3 1 小波数据结构图 图3 1 中，h e a r 小波是通过对相邻数据求其标准均值和差值而得到的一 系列数据。h e a r 小波的变换可以看作是对数据流中的数据求解其均值和差值 的过程。最初的时间序列组成孑小波树的第0 级，即l e v e l 0 级。小波树的第 0 级的每相邻的两个数据项的均值和差值构成了第l 级小波树系数的数据。 第1 级小波树的每相邻两个数据项的均值和方差构成了第2 级小波树系数的 数据。依此类推，第i 级小波树每相邻的两个数据项的均值和方差构成了第 i + l 级小波树系数的数据，重复此步骤直到最顶级只由一个均值和方差为止。 小波树的系数可以被看作是不同时间间隔的时间序列的聚集啡。 在小波树的l e v e l i 级共有n 2 个连续的窗口，且每个窗口的大小为2 。在 同一级的所有窗口的大小都为2 。把小波树的数据结构应用于数据流的突变 检测还存在着一些问题。因为除了最顶级的窗口包含所有的数据项外，其它 1 5 哈尔滨工程大学硕士学位论文 级的窗口都不重叠，所以一个具有任意起始点和任意大小的滑动窗口都不被 小波结构的任一个窗口所包含。由于存在这样的不足，所以要检测小波树的 任意子序列时间窗口的数据流突变成为一个难以解决的问题。 2 直方图 直方图是一个直观、简单的表示大数据集的数据结构，在数据库领域的 应用也日益广泛。它将大的数据集划分为若干个连续的桶，每个桶都用一个 数字代表，从而将大数据集划分成为若干个小数据集旧。直方图也可以分为 多种，例如v - 优化直方图、等直方图、压缩直方图等l 町1 。在数据流突变检测 中，常利用v 优化直方图来计算某一数据项的查询和给定滑动窗口中的聚集 函数的查询。但是由于数据流实时性和高效性等特点，新的数据到来难免会 使直方图中的数据误差越来越大，从而导致数据流突变检测的精度下降旧。 3 迁移二叉树 迁移二叉树能够应用在弹性突变的高维聚集查询和突变检测中。它的数 据结构是在小波结构基础上加以改进的。每一级都增加一个额外的窗口，记 录着时间序列上重叠部分的信息，它能被显示或隐示的存储。所以迁移二叉 树的结构是小波结构的2 倍。图3 2 是迁移二叉树的结构旧一。 ，1 二二二二 删 二二= 三二二r 删 三三三三三三三宁 掀吒三三王5 三己王母 蛐哩五e 五呈五星五里五了 墨工 工口_ 工工口工 口工口1 工口工卫 图3 2 迁移二叉树结构图 l e v e l o 位于迁移二叉树的最底部，通过计算第o 级每两个相邻的数据项 的聚集和产生了l e v e l l 级的序列窗口。为了给迁移二叉树的高级提供输入， 所以需要在每一级建立一个下抽样的过程。下抽样的过程就是计算每一级时 间序列中的每隔一个数据项的两个非连续的数据项的聚集和。每一级的下抽 样过程都维护了上一级连续的非重叠的窗口信息m 。重复此步骤直到生成一 个单独的包含所有数据项的窗口。在迁移二叉树中以任意一个位置起始和结 1 6 哈尔滨工程大学硕士学位论文 |i i i im l 束的子序列，总能被迁移二又树中的一个窗口所包含。 4 聚集金子塔 聚集金字塔是一个类似于金字塔的数据结构，因此称为聚集金字塔。它 是在初始时间序列的数据流的基础上建立起来的数据结构。l e v e l o 级有n 个 数据单元，l e v e l l 级有n 1 个数据单元，l e v e l 2 级有n - 2 个数据单元，依次类 推，第i 级有n i 个数据单元。它是一个等边的三角形，并且以沿着4 5 度的 斜边所在的数据单元有相同的起始时间和沿着1 3 5 度斜边所在的数据单元有 相同的终止时间”。l e v e l l 级中的第1 个数据单元是由l e v e l o 中的第1 个和第 2 个数据单元聚集生成的，l e v d l 级中的第2 个数据单元是由l e v e l o 级中的第 2 个和第3 个数据单元聚集生成的，依次类推，l e v e l i 级中的1 个数据单元是 由l e v e l o 中的i + 1 个数据单元聚集生成的。在第i 级上先后有两个单元c l 和 c 2 。c l 的映射窗口与c 2 映射窗口的交叉部分即是单元e 的映射窗口。因此， 在迁移聚集树中，i 级的1 个单元覆盖了从初始l e v e l o 级中的i + 1 个单元到i 1 级中的两个单元。把该单元覆盖的所有单元定义为该单元的映射窗口，所以 迁移聚集树中的每个单元都是由它的映射窗口聚集生成的。聚集金字塔的 结构如图3 3 所示。 图3 3 聚集金字塔结构图 图3 3 是一个长度为1 0 的聚集金字塔，在聚集金字塔中，共有l o 级分 别从l e v e l o 到l e v e l 9 。初始时间序列数据流为1 e v e l o ，共有1 0 个滑动窗口。 每一级的单元都是由l e v e l o 级中的若干单元聚集生成，直到最顶