已阅读5页,还剩66页未读, 继续免费阅读
(计算机应用技术专业论文)基于聚类的数据流异常检测算法的研究.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
掌 寸 - d a j 0 - 哩 f i 膏 0 f 0 哈尔滨工程大学 学位论文原创性声明 本人郑重声明:本论文的所有工作,是在导师的指导下,由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出,并与参考文献相对应。除文中己注明引用的内容外, 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体,均己在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) :毋夯磋l 日期:z o o 年1 月,日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定,即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索,可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文,可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可鹾授予学位1 2 个月后口解 密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) :名糸堤 日期:趵历年,月f 日 导师( 签字) :危磁 幽f 。年弓月夕日 勺 岱 。0 哈尔滨下程大学硕十学何论文 摘要 在海量的、动态变化的网络数据流中如何检测出异常,是网络安全领域 主要关心的问题,同时也是检测网络攻击的主要手段,现在越来越受到学者 的关注。 在网络数据流方面一般认为正常的行为占大多数,而异常的行为属于个 别行为。基于此假设,选择k m e a n s 算法对数据流进行聚类分析,最终不属 于任何子簇的数据点最有可能是异常点。k - m e a n s 算法的执行过程是首先确 定k 个初始聚类中心点,将新到来的数据对象点根据距离阀值与距离最近的 子簇合并,最终完成具有k 个子簇的聚类结果。 本文针对k - m e a n s 算法存在的缺点和不足,例如,对输入数据对象点输 入顺序敏感、容易陷入局部最优而非全局最优等问题。从两个方面对原有算 法进行改进:首先根据有效性函数最小性原理,确定接近于真实聚类数的k 值,然后通过执行聚类中心选择算法,选取处于高密度区域的若干点,将点 集周围数据点数量作为权值赋予该点,对选取的若干点集合构建最小堆,然 后进行堆排序,权值作为堆节点的值,一次扫描确定密度最高的k 个数据点 作为初始聚类中心。改进后的k m e a n s 算法可以使准则函数收敛的更快,由 于使用堆排序而非距离迭代计算选取聚类中心,时间复杂度相对较低,从而 使算法在执行的时间效率上得到提高,又由于初始聚类中心点选择的接近于 真实聚类中心,在聚类过程中不容易将大簇分割,从而使聚类结果更准确。 最后选取u c i 数据库中的数据集和k d d 9 9 数据集,对改进后算法和原 算法进行聚类分析。实验结果表明,改进后的算法提高了聚类结果的准确性, 同时算法的执行效率也有一定程度的提高。 关键词:数据流;异常检测;k - m e a n s 算法;聚类中心;子簇 哈尔滨丁程大学硕十学位论文 a b s t r a c t h o wt od e t e c ta b n o r m a li nt h em a s s i v ea n dd y n a m i cc h a n g e so fi n t e r n e td a t a s t r e a mi sam a j o rp r o b l e mi nt h ef i l e do fn e t w o r ka n di sa l s ot h ep r i m a r ym e a n so f td e t e c t i n gn e t w o r ka t t a c k s ,n o wm o r ea n dm o r es c h o l a r sa r e c o n c e r n e da b o u tt h a t i nt h ea s p e c t so ft h en e t w o r kd a t as t r e a m ,g e n e r a l l yb e l i e v et h a tt h em a j o r i t y a r en o r m a lb e h a v i o r s ,w h i l et h ei n d i v i d u a lb e h a v i o r sa r ea b n o r m a lb e h a v i o r s b a s e do nt h i sa s s u m p t i o n ,c h o o s et h ek - m e a n sc l u s t e r i n ga l g o r i t h mt om a k ed a t a f l o wa n a l y s i s ,t h ee n dd o e sn o tb e l o n gt oa n ys u b c l u s t e ro fd a t ap o i n t sa r em o s t l i k e l yt ob eo u t l i e r s k - m e a n sa l g o r i t h mi m p l e m e n t a t i o np r o c e s si s t h a tf i r s t d e t e r m i n et h ei n i t i a lc l u s t e rc e n t e ro fk ,t h en e wd a t ao b j e c tp o i n t sb a s e do n d i s t a n c et h r e s h o l dm e r g e rt ot h en e a r e s ts u b - - c l u s t e r , f i n a l yg e tt h eks u b - c l u s t e r s o fc l u s t e r i n gr e s u l t s i nt h i sp a p e rf o rt h es h o r t c o m i n g sa n dd e f i c i e n c i e so fk - m e a n sa l g o r i t h m ,f o r i n s t a n c e ,s e n s i t i v et ot h es e q u e n c eo ft h ei n p u td a t ao b j e c tp o i n t ,e a s yt of a l li n t o l o c a lo p t i m u mr a t h e rt h a nt h eg l o b a lo p t i m u ma n do t h e ri s s u e s f r o mt w oa s p e c t s t oi m p r o v et h eo r i g i n a la l g o r i t h m :f i r s t ,a c c o r d i n gt ot h ep r i n c i p l eo fm i n i m u mo f t h ee f f e c t i v e n e s sf u n c t i o n ,d e t e r m i n et h ec l u s t e r i n gr e s u l t so fkc l o s et ot h et r u c v a l u e ,t h e nt h r o u g ht h ei m p l e m e n t a t i o no ft h ec l u s t e rc e n t e rs e l e c t i o na l g o r i t h m , s e l e c tm a n yp o i n t si nh i g h - d e n s i t yr e g i o n ,t h en u m b e ro fd a t ap o i n t sa r o u n dt h e p o i n ts e ta st h ew e i g h tg i v e nt ot h ep o i n t ,b u i l dm i nh e a po nt h es e l e c t e dh e a p , _ a n dt h e np r o c e e dt oh e a ps o r t ,t h ew e i g h tv a l u ea st h ev a l u eo ft h eh e a pn o d e s , k o n es c a nt od e t e r m i n et h ek h i g h e s td e n s i t yo fd a t ap o i n t sa st h ei n i t i a lc l u s t e r “ c e n t e r t h ei m p r o v e dk - m e a n sa l g o r i t h mm a k et h e c r i t e r i o nf u n c t i o nf a s t e rt o c o n v e r g e n c e ,b e c a u s ei n s t e a do fu s i n gt h eh e a ps o r ts e l e c tt h ec l u s t e rc e n t e rf r o m t h ei t e r a t i v ec a l c u l a t i o n ,t i m ec o m p l e x i t yi sr e l a t i v e l yl o w ,a n dt h u st h et i m ei nt h e 哈尔滨t 程大学硕十学位论文 k i m p l e m e n t a t i o no ft h ea l g o r i t h me f f i c i e n c y i s i m p r o v e d ,a l s o ,b e c a u s et h e s e l e c t i o no ft h ei n i t i a lc l u s t e rc e n t e r si sc l o s et ot h et r u ec l u s t e rc e n t e r s ,i nt h e 、 c l u s t e r i n gp r o c e s si sn o te a s yt os p l i tl a r g ec l u s t e r s ,s ot h a tg e tt h em o r ea c c u r a t e c l u s t e r i n gr e s u l t s f i n a l l ys e l e c tt h ed a t as e t si nt h eu c id a t a b a s ea n dk d d 9 9 ,m a k ea n a l y s i s o nt h ei m p r o v e da l g o r i t h ma n dt h eo r i g i n a la l g o r i t h m e x p e r i m e n t a lr e s u l t ss h o w thatt h ei m p r o v e da l g o r i t h mi nt h ei m p l e m e n t a t i o no ft i m ee f f i c i e n c ya n d t k a c c u r a c yo fc l u s t e r i n gr e s u l t sh a v eb e e ni m p r o v e db o t h ,r e d u c et h ef a l s ep o s i t i v e r a t eo fc l u s t e r i n gr e s u l t s k e y w o r d s :d a t as t r e a m ;a n o m a l yd e t e c t i o n ;k - m e a n sa l g o r i t h m ;c l u s t e rc e n t e r ; s u bc l u s t e r k 飞 t h q 哈尔滨t 程大学硕十学位论文 目录 第1 章绪论1 1 1 论文研究的背景”1 1 2 国内外研究现状2 1 3 课题研究内容4 1 4 本文组织结构”4 第2 章数据流及相关技术概述一6 2 1 数据流6 2 1 1 数据流基本概念7 2 1 2 传统数据与数据流的比较7 2 1 3 数据流的特点9 2 1 4 数据流的类型“1 0 2 2 数据流模型1 1 2 2 1 滑动窗口模型1 1 2 2 2 快照模型1 2 2 2 3 界标模型“1 3 2 3 本章小结1 4 第3 章数据流异常检测技术概述“1 5 3 1 数据流异常检测1 5 3 1 1 数据流异常检测中的关键技术1 6 3 1 2 数据流异常检测常用方法1 8 3 2 聚类分析在数据流异常检测领域的应用2 1 3 2 1 聚类分析概念”2 1 3 2 2 基于聚类的数据流异常检测实现2 2 3 2 3 常用的聚类分析方法”2 2 t - 鼍 - h 龟 哈尔滨t 程大学硕十学位论文 3 3 本章小结2 5 第4 章一种改进的基于聚类的k - m e a n s 算法2 6 4 1 问题的提出”2 6 4 2 问题的分析2 7 4 2 1 基于聚类的k m e a n s 算法2 7 4 2 2k m e a n s 算法存在的缺点和不足研究3 1 4 3 一种改进的k m e a n s 算法3 3 4 3 1k 值的选取3 4 4 3 2 初始聚类中心点的确定3 7 4 3 - 3 改进的k m e a n s 算法描述4 0 4 4 基于聚类的数据流异常检测模型”4 2 4 5 本章小结4 3 第5 章实验与分析4 5 5 1 实验运行环境及数据集4 5 5 2 实验结果分析4 6 5 3 本章小结5 6 结论“5 7 参考文献5 8 攻读硕士学位期间发表的论文和取得的科研成果6 3 致谢”6 4 k 、 哈尔滨t 程大学硕+ 学位论文 第1 章绪论 1 1 论文研究的背景 随着计算机与网络技术的发展,在越来越多的实际应用中需要处理大量、 连续、快速、随时间变化的数据,即流数据。流数据的特点是数据持续到达, 且速度快、规模大。其研究核心是设计高效的单遍数据集扫描算法,在一个 远小于数据规模的内存空间里不断更新一个代表数据集的结构概要数据结 构,使得在任何时候都能够根据这个结构迅速获得查询结果【卜2 1 。基于数据流 计算的研究与应用是目前国际数据库研究领域的一个热点。数据流上的异常 检测技术由于在金融风险分析、网络流量监测、趋势分析、网络通信、传感 器网络等领域广阔的应用前景也受到学术界和工业界越来越多的关注l 引。 数据流异常检测技术是在传统异常检测的基础上,结合数据流相关技术, 完成对数据流的异常检测。它能够对系统中产生的数据流进行有效的分析, 并快速获取分析结果,满足实时处理的需求。较常用的数据流异常检测方法 有基于阈值的方法,基于统计的方法,基于小波的方法,基于随机过程模型 的方法,基于机器学习的以及数据挖掘、人工神经网络的方法等。这些数据 流异常检测算法,需要先选取一定长度的数据作为一个滑动窗口建立数据概 要结构,构建数据概要结构主要有直方图、小波、抽样等方法。在新数据达 到时,要利用概要更新方法维护这个数据概要结构,然后,再结合相应的算 法进行异常检测【训。 目前,数据流异常检测技术的应用研究主要集中在传感器网络、电信网 络监测、股票分析等领域。如在传感器网络中,异常检测技术可以利用对单 个或多个数据流聚集的检测,对异常情况做出分析和补偿。在电信领域,如 果在一个特定的时间段内数据包丢失的数量超过阈值则报警。在金融领域, 股票交易量过大或短时间范围内股票价格波动较大都会引起关注。实际上 哈尔滨t 稃大学硕十学位论文 i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i - t 在工业控制和其它领域也涉及到很多实时的数据流,研究其在天文领域和电 力系统检测中的应用也具有重要的实际意义。在天文观测领域,可以用于通 过对y 射线异常的观测,为未来天体事件做出预测。数据流异常检测技术也 可以用于解决电能质量问题中的电压凹陷检测,来保电力系统设备的安全运 行。随着数据就异常检测的应用领域越来越广泛,对数据流异常检测技术 的研究变得越来越重要【5 l 。 1 2 国内外研究现状 国内外关于数据流异常检测的方法有很多种,近几年随着数据流技术的 发展,数据流技术和异常检测技术不断的融合和渗透,学者们提出了好多新 的方法和对以前传统数据流异常检测方法改进的方法。并形成了在线的异常 检测。其中较常用的方法有:基于统计的检测方法,基于马尔可夫等随机过 程模型的方法,基于神经网络的方法,基于阂值的方法,基于数据挖掘聚类 的方法,基于机器学习的方法,基于预测模式的方法,基于人工智能的方法 h 6 - 7 1 j o 异常检测的思想最早由d e n n i n g 提出,即通过监视系统审计记录上系统 使用的异常情况,可以检测出违反安全的事件。但d e n n i n g 的思想没有考虑 数据对象到达的顺序问题,为了克服d e n n i n g 模型这个缺点,1 9 9 0 年h e n r y 提出了预测模型。预测模型使用动态规则集合来检测入侵,这些规则根据所 观察事件的序列关系和局部特性归纳产生序列模式【剐。h e n r y 预测模型有效 的解决了d e n n i n g 对事件到达顺序判断不准确的问题。 在1 9 9 6 年以前,绝大多数异常检测技术都是利用用户的行为来建立特征 轮廓,当基于用户行为的活动轮廓与正常轮廓发生偏离时认为可能有入侵发 生。基于聚类的数据流异常检测就是其中的代表,该类方法根据不断到达的 网络数据对象点进行聚类分析,将新到达的数据对象点按照聚类中心最小距 离原则进行聚类,合并到已有的子簇中,然后迭代计算新的聚类中心点,直 到数据对象点输入完毕,从而发现孤立的点,根据程序局部住假设,孤立点 , 2 哈尔滨t 程大学硕十学位论文 最有可能就是异常的数据对象点【9 1 。而1 9 9 6 年f o r e s t 等人又引入了一个简 单的异常检测方法,该方法基于监视由特权程序使用的系统调用。他们的假 设行为是系统的损害主要是由执行了系统调用的运行着的特权程序所引起 的。所以他们把注意力放在监视特权进程上。 在1 9 9 6 年以后,更多的基于系统调用的统计异常检测技术被提出,主要 有序列时延嵌入法( s 1 1 d e ) 。该方法认为,局部区域的不匹配数目最有可能 表征发生了数据流异常行为,而且经实验证明这种行为足可以证明我们的假 设,正确率在7 0 以上。此外还有基于有限状态机的方法如隐式马尔可夫模 型h m m 方法等。1 9 9 9 年w a r r e n d e r 对这些方法做了详细的实验比较,结论 是简单的建模方法比如s t i d e 便可得到令人满意的效果,因此得到结论,数 据流的预处理分析和选取要比特定方法的选取更重要,而且实验也恰恰证明 了这一点【1 m 1 1 1 。 在基于聚类的数据流异常检测方面,近年来,有学者提出了应用于大规 模数据集的一趟聚类算法,如s q u e e z e r 算法和b i r c h 算法,它们可以应用于 某些数据流问题【1 2 l 。也有学者提出了针对流数据的聚类算法,典型的有 s t r e a m 算法、c l u s t r e a m 算法和h p s t r e a m 算法。s g u h a 等人对数据流聚类理 论进行了探讨,然后在实践的基础上提出了基于k - m e a n s 的s t r e a m 算法,使 用质心和子簇表示聚类。s t r e a m 算法采用批处理方式,每次处理的数据点个 数受内存大小的限制【1 3 l 。c a g g a r w a l ,j h a n 等人提出了流数据聚类算法 c l u s t r e a m ,首次提出把数据流看成一个随时间变化的过程,而不是一个整体 进行聚类分析,该算法有很好的可扩展性,可产生高质量的聚类结果,尤其 是在数据流随时间变化较大时比其它算法产生更高质量的聚类。接下来, c a g g a r w a l ,j h a n 等人又提出了h p s t r e a m 算法,它使用投( p r o j e c t ) 的方法 对高维数据流进行处理,经过实验证明,在各个方面都比c l u s t r e a m 有了进 一步提高1 1 4 j 。 本文所描述的主要是基于聚类的数据流异常检测方法,此方法是基于程 序局部性原理假设,认为数据流中正常行为属于大部分行为,把偏离大多数 3 哈尔滨t 程大学硕十学位论文 行为的孤立点、独立点认为是最有可能是异常行为。采用的方法主要是经典 的数据挖掘聚类算法k - m e a n s ,并针对原方法的缺点和不足进行了改进【1 5 】。 1 3 课题研究内容 数据流已经与人们的日常生活息息相关,而数据流技术更是逐渐发展成 为现代数据库技术研究的主要方向之一。本文首先对数据流的基本概念进行 阐述,分析数据流的特点及组成,以及数据流所具有的类型,接下来介绍几 种分析数据流时所用到的常用的数据流模型。随着数据流技术的快速发展, 数据流的异常检测技术的应用也日益广泛,并具有实际的研究价值。面对庞 大的网络数据流,好多学者提出了各种解决办法和方法对数据流进行分析和 研究,发现网络的异常行为,其中最有代表性的就是基于聚类的数据流异常 检测方法。在基于聚类的数据流异常检测方法中我们选取的是k m e a n s 算法 进行研究,针对k m e a n s 算法本身所具有的对初始聚类中心敏感,容易达到 局部最优解而非全局最优解的问题,还有k 值确定难等问题进行深入的研究。 提出算法的改进思路,对原算法进行优化,使算法在运行效率上得到提高, 同时在改进算法进行聚类时,降低聚类结果在异常检测过程中的误报率。并 通过仿真模拟实验证明了这一点。 1 4 本文组织结构 本文总共有5 章,组织结构如下: 第1 章介绍了本课题的研究的目的、意义以及到目前为止一些国内外关 于数据流异常检测技术的研究现状,最后介绍了本文研究的主要内容和文章 的组织结构。 第2 章首先介绍了数据流的基本概念、特点和类型,然后介绍了三种常 用的数据流模型。 第3 章主要针对数据流异常检测技术进行了深入研究,介绍了数据流异 常检测常用的方法。然后详细介绍了广泛应用于数据流异常检测领域的聚类 4 哈尔滨1 :稃大学硕十学位论文 分析方法,并分析了聚类在数据流异常检测领域的实现方式。最后介绍了几 种常用的聚类分析算法。 第4 章首先提出问题,分析已有聚类算法在聚类过程中存在的缺点和不 足。然后提出基于聚类的数据流异常检测模型,结合已有的聚类算法k - m e a n s 算法提出改进思路,并将改进后的与原算法进行比较分析。 第5 章对改进后的k m e a n s 算法和原k m e a n s 应用国际标准数据库u c i 中的数据集进行仿真实验,并对实验结果进行分析和比较,从而证明改进后 算法的有效性和可行性。 最后对全文进行总结,总结文中工作,指出不足。 5 哈尔滨丁程大学硕士学位论文 2 1 数据流 第2 章数据流及相关技术概述 随着数据库技术的迅猛发展,和人们日常生活息息相关的很多领域都出 现了大量的、实时的、高速的、动态的数据,于是一种新的数据形式数据流 应运而生。数据流的出现已经成为了数据库的一个新的研究方向,它的应用 也非常广泛。如金融市场基金的波动、电信部门通话信号的强弱、生态环境 指标的监测、交通信号的监控、网络流量的实时监测。数据流作为数据的一 种动态的形式,可以形象的描述数据的流动性,并体现了数据的无限性、实 时性、连续性等特点【1 6 】。 数据流是一个有序的以一定速度连续到达的数据元素的序列,它通常有 潜在无限的体积,数据的可能取值是无限的。数据流处理系统无法保存整个 数据流,并且数据流的实时处理要求使系统无法使用代价较大的磁盘读取, 即数据流处理系统的输入数据并不存在于可随机访问的磁盘或主存中。输入 数据以一种瞬态的、持续的流形式到达1 1 7 l 。数据流中的数据项在被读取一次 之后,就被丢弃,以后不可能再读到。 目前应用中的数据流种类有很多,比如:网络中用户点击的数据流、电 信行业中的电话记录数据流、实时监控中的数据流、股票证券交易中的数据 流、商场销售货物数据流、天气预报、环境检测数据流等等。这些数据流都 与传统数据有着不同的数据特点。这些数据流都有共同的特点就是快速增长、 随时间动态变化且潜在无限。有时数据流的增长会以指数级递增,如此大量 的动态数据与以往的静态数据不同,处理时首先要考虑的就是计算机无法提 供足够的内存来存储这些数据,而通常各领域产生的数据流都是需要被实时 处理,那么,如何及时且有效地处理数据流,同时从中挖掘有用的知识,对 各个应用领域有着重要的意义【1 8 j 。 6 哈尔滨t 程大学硕十学位论文 2 1 1 数据流基本概念 数据流是大量的、连续的、实时的、有序的数据项组成的序列。若令t 表示任意一个时刻,x 。为t 时刻的数据项,那么数据流可以表示为 x l ,x 2 ,x 3 ,x 小,x t + n 。随着不同时刻的数据项的到来,数据流可以看作是由 一系列数据项的插入与删除所组成的数据项的序列。数据流的长度即为所包 含的所有数据项的个数。一般来说,数据流的长度随着不同的时间实时更新, 在某一时刻既存在新的数据项的到来,又存在历史数据项的消失。所以数据 流是一个没有界限的数据序列,其速度和数据项到达的次序都是无法控制的。 由于数据流的规模无限、数据项的取值无限以及数据项不同的分布特征,因 此对数据流的深入研究也受到了广大数据库研究者的高度重视。 2 1 2 传统数据与数据流的比较 过去人们使用的传统数据库一般是存储静态的数据记录,同时这些记录 之间存在着一定的关系,如关系数据库,数据库中存储结构化的数据。这些 数据有着确定的大小空间、对应的数据操作、详细描述定义的数据结构,可 长期、持久的存储于数据库中,用户、管理者、数据分析人员可以随时从数 据库中提取数据用于分析、使用等。不过传统数据库中的计算一般都有比较 高的时间复杂度和空间复杂度,相应的查询处理功能都是静态的、最终都能 够生成确定的查询结果【1 9 】。传统数据库中的数据一般都没有时间的概念,即 与时间无关。当然一些特殊的应用也可以在数据中加入相应的时间戳。这种 数据库在过去可以满足个人或商业、企业信息存储的需求。 人们在处理传统数据时,能够详细和完整地收集数据,然后将这些数据 全部存储在传统的数据库中,根据功能需要,由计算机来对这些数据处理。 传统的关系型数据库管理系统强调维护数据的完整性和一致性,其追求的目 标是系统的吞吐量和平均响应时间,而不是系统提供的查询服务的质量和自 适应性,也不注重系统对数据处理的时间和空间限制。 静态的数据挖掘主要以数据为中心,所有的数据都存储在一个庞大的、 7 哈尔滨t 程大学硕十学位论文 相对稳定的存储媒介中,一大部分的数据都是始终不变的,变化的只是不同 用户提出的不同的查询请求【2 0 】。 但是科技的发展,信息数量的膨胀,新兴领域中不断产生的数据流使得 传统的数据库结构已经不再满足人们的需求,当前以及今后的许多应用中, 都要求系统能对不断快速动态变化的数据流提供在线的分析支持。通信数据 管理、网络监控器、数据传感器、以及一些个性化的生产应用,这些大量的 数据流是一个无限的集合,而过去的静态数据是一个有限的数据集合。对于 数据的查询也是不断的连续的查询,这些特性都提示人们要研究新的方法来 处理数据流。 动态数据挖掘是以查询为中心,数据集的数量巨大,同时具有高度的流 动性。相对稳定不变的是用户提交的查询需求,大量事前定义的用户查询被 存储到挖掘系统中等待数据集的到来。一旦有数据集到来,将促使查询开始 执行。例如,数据比较密集的生产系统所产生的日志数据,就具有这种海量 且流动的特点。这样的系统还包括:证券交易系统、互联网管理系统、金融 交易系统、电信系统等等。这些应用都是面对在线的、持续流动的高速数据, 系统所处理的对象形态完全不同于传统的静态数据,并且由于存储空间有限, 这些数据往往不可能被全部保存到存储器中,而用户又要求同时必须不间断 无延迟地实时处理这些数据流,以获得实时的结果,由此产生了一些新的基 础性研究问题。 由于数据流的动态变化的特殊性,较短时间内就会有大量的数据连续到 达,这就要求系统能够快速的给出响应。数据流的这些特性能够满足人们如 今处理数据的需要,不过数据流中的数据一般都具有多个数据项,是多维数 据,在处理时需要考虑到时间和空间的限制,进行多层次化和多维化处理, 一般采用一次扫描算法利用精度换时间,尽量在对数据流的一次访问中获得 有用的信息,从而得到较优的解【2 1 1 。 数据流不同于传统的基于关系集合的静态数据,与传统的数据相比数据 流连续到达,频繁变化,数据量的大小是不确定的,也可能是无限的。 8 哈尔滨丁程大学硕十学位论文 基于以上数据流和传统的数据库中的数据特点,比较两者总结后有以下 的不同。 ( 1 ) 传统数据库中的数据是存储在磁盘、外部存储器或内存中以供用户 随时使用处理,数据流中的数据是无限、连续、变化的序列不能全部被存储。 ( 2 ) 传统数据库中的数据可以被随机访问,数据流中的数据按时间序列 到达,无法提供随机访问功能。 ( 3 ) 数据流中的数据是大量无限的,而传统数据库中的数据是有限的。 ( 4 ) 传统数据库上的查询结果确定,而数据流上的查询由于数据的不断 变化和存储空间有限,其上的查询一般得到的是近似的结果。 ( 5 ) 内存中存储的数据流中的数据要不断的实时的被更新,而传统的数 据库中的数据一般只是根据使用者的使用情况更新,其更新频度低于数据流 中的数据更新。 ( 6 ) 数据流中的数据处理一般都是一遍扫描,而传统的数据挖掘是对静 态数据库进行多次扫描才完成的。 数据流处理以前一直都有没有得到足够的重视,目前还不存在像数据库 管理系统一样较成熟的和通用的数据流处理平台。但随着网络技术的发展和 广泛应用,人们对于数据流处理的需要,使得近年来数据流的研究在国际、 国内逐步得到重视,不久的将来具有工业标准的通用数据流处理平台也将会 应运而生【2 2 】。 2 1 3 数据流的特点 数据流由于其本身的流动性,与传统的数据有着本质的区别和特性。数 据流的特点如下: ( 1 ) 数据流具有流动性、实时性。数据流中的数据是一种流动形式出现 的,并且随着时间的推移不断的变化。可能会有新的数据项的到来,也可能 会有历史数据项的流逝。 ( 2 ) 数据流具有连续性、有序性。数据流中的数据项是连续的、不间断 9 哈尔滨工程大学硕十学位论文 的出现的,并且随着时间的不同,到来的数据项具有一定的先后次序。 ( 3 ) 数据流具有大量性、无限性。数据流中的数据是海量的,甚至是无 穷的。因此要存储这些数据需要耗费大量的空间,所以对数据流的压缩和存 储也成为了研究人员的一个研究的热点。 ( 4 ) 数据流具有单遍性。由于时间和空间的限制,对数据流中的数据项 只能扫描一次。这就给数据流中数据的处理带来了一定的困扰,尤其是对那 些无法保存的历史数据的关注和研究。 ( 5 ) 数据流还具有一定的突变性。数据流中的数据在某一时刻由于受到 外界等环境因素的干扰发生了突变,与原始的数据有较大的异常。发生突变 的数据流可能会给某一问题的研究带来误差或者是错误,这无非会给研究人 员带来更大的难题【2 3 1 。 2 1 4 数据流的类型 随着研究人员对数据流的深入研究,对数据流的类型也大致分为三种类 型,即基于时间序列的数据流、基于收银机类型的数据流和基于转盘类型的 数据流。 1 基于时间序列的数据流 该数据流中的数据项随着时间的不同是以一定顺序出现。例如数据流中 数据项的下标是升序排列的,即每一个新到的数据项的下标都比它的前一个 数据项的下标大。本文可以更具体的描述基于时间序列的数据流为 x = 【x l ,x 2 ,x 3 ,x t ,x t + n 】,其中x 1 为时间t = l 时刻的数据项,x 2 为时间t = 2 时 刻的数据项,依次类推x 。为t 时刻到来的数据项。 2 基于收银机类型的数据流 该类型的数据流规定数据流中的数据项可以不用排序,即数据项的下标 可以不用按照一定的顺序排列,并且允许数据项的重复出现。但它要求每一 个数据项的值必须是非负的,即限制了输入数据流的条件,这一规定在检测 数据流单调聚集函数值的突变上有广泛的应用。此外这种类型的数据流限制 1 0 哈尔滨下程大学硕十学位论文 了数据项只能添加,不能减少,即不能实现数据项的删除操作。 3 基于转盘类型的数据流 这种类型的数据流对数据项的下标没有任何要求,即可以排序也可以不 用排序,同时对数据流中的数据项的值也没有了限制的条件。既可以是非负 数据项,也可以是正的数据项。可以对数据进行增加、删除操作【2 4 】。 上述三种类型的数据流都广泛的应用在现实的生活领域。其中应用最多 的是基于时间序列的数据流,本文采用了基于时间序列的数据流作为研究的 对象。 2 2 数据流模型 数据流作为一种动态的数据,充分的体现了它的实时性。正如前面介绍 的,目前数据流多是基于时间序列的类型。众多学者研究的对象都是在某一 时间范围内的数据流。例如y z h u 和s h a s h a 提出的基于迁移小波树的数据流 突变检测的研究:复旦大学秦首科博士研究的基于直方图的数据流突变检测 技术的研究等。所以按照时间的范围将数据流的模型分为三种:滑动窗口模 型、快照模型、界标模型的【2 5 1 。 2 2 1 滑动窗口模型 滑动窗口的概念首先由加拿大d a t a p a c 网的设计者提出的滑动窗口广泛的 应用在数据流监控中,是数据流上应用比较多的一种特殊数据抽样方法。滑动 窗口有基于数据元组数量和基于时间两种定义方式。而根据窗口更新粒度的不 同,又可分其为连续更新滑动窗口和周期更新滑动窗口两种类型。数据流上的 滑动窗口是指在数据流上设定的一个区间,该区间只包括数据流最近最新的部 分数据,随着数据不断的到达,窗口向前移动,表示新数据到来,新数据替换 了旧数据。相关的定义:数据流x 是一个按照时间递增顺序排列的无穷时间序 列,x = ( x l ,t 1 ) ,( x 2 ,t 2 ) ,( x 3 ,t 3 ) ,( x i ,t i ) ) ,其i :和x 1 ,x 2 ,x 3 是数据域v 中的 值,而t 1 ,t 2 ,t 3 是时间戳,( x 1 ,t 1 ) 代表t 1 时刻的数据值为x 1 ,即每一个数据值x i 哈尔滨t 程大学硕十学何论文 都与一个时间戳t i 相联系。x t l , t i l 表示从时刻t i 到t i 时刻的子序列。设滑动窗口的 大小为w ,当前的时刻为t i ,那么滑动窗口中的每个数据项的域空间是 v = x x t i w + i ,t i ,滑动窗口中的每个数据项v i 用( x i , t i ) 表示。其中v i 是对 应丑时间戳的数据项,v i 是对应t i w 时间戳的数据项。滑动窗1 3 随着时间向前 移动的过程可以用许多的数据项v i 的插入和v i 的删除来表示【2 删。总之,滑动 窗口模型开始和结束边界都是向前滑动的,而且窗口内部的数据对象数量始终 保持不变,随着新数据的到达,将窗口中的旧数据丢弃,如图2 1 所示。 2 2 2 快照模型 图2 1 滑动窗口模型 快照模型是将处理数据流中数据窗口的范围限制在两个预定义的时刻之 间,且窗1 3 的大小保持固定不变,如图2 2 所示。 哆_ 卜卜卜卜卜h 图2 2 快照模型 快照模型又可以分为连续快照模型和序列快照模型。 连续快照模型应用在数据流中的具体含义是:仅记录和保留数据流中的 当前的数据项,对于前一时刻的数据项或是历史数据项都不保留,即插入一 1 2 哈尔滨t 程大学硕+ 学位论文 个新的数据项,就删除历史的旧数据项。连续的时间快照模型是记录一段时 间范围内数据流中的数据项,以用来描述整个时间段内数据流的特性和状态。 序列快照模型有矢量快照模型和栅格快照模型。它应用在数据流的含义 为:将系列时间片段的数据流中的数据项保存起来,各个时间片段分别对应 不同时刻的数据流的状态,以此来反映数据流中数据项的变化过程。同时也 可以根据需要对指定时间片段内的数据流进行研究。 无论是连续快照模型还是序列快照模型由于它们对将来的数据项允许重 复,所以会存储大量的重复的、冗余的数据项,会浪费很大的空间。 2 2 3 界标模型 界标模型处理数据的范围从某一个已知的初始时刻到当前时刻为止。记 录下初始的时刻为t l ,当前的时刻为t n ,则基于界标模型的数据流可以描述 为x x t l ,x t 2 ,x t 3 ,x t n 。通常将数据流的起始点作为数据处理的初始时间点。 算法对数据流的数据只存在插入操作,界标模型如图2 3 所示。 图2 3 界标模型 这三种模型在数据流技术的应用都很广泛。由于滑动窗口模型和界标模型都 要处理数据流中新到的数据项,所以受到研究人员的高度的重视和广泛的关注。 t - 哈尔滨下程大学硕七学位论文 2 3 本章小结 本章对数据流和相关的概念进行了介绍。首先介绍了数据流的基本概念, 并对传统的数据和数据流数据进行了比较。然后介绍了数据流的特点和几种 不同类型的数据流。最后介绍了三种最为常用的数据流模型。 1 4 哈尔滨t 程大学硕士学位论文 第3 章数据流异常检测技术概述 本章主要介绍数据流异常检测的关键技术以及进行数据流异常检测常用 的方法,然后对广泛应用于数据流异常检测方面的聚类分析方法进行详细介 绍,并介绍几种常用的聚类分析算法。其中第4 章将要介绍的k m e a n s 算法 就是聚类分析算法中具有代表性的一种,由于它的简单性和易用性被广泛的 应用于数据流异常检测领域。 3 1 数据流异常检测 定义3 1 数据流( d a t as t r e a m ) :按照固定的次序持续到达,且其中的 数据元素只能被读取一次或有限次。若令t 表示任一时间戳( t i m es t a m p ) , x t 表示在t 时刻到达的数据元素,则数据流可以表示为无限集合 x l ,z 2 一x t ) 【2 8 1 。 定义3 2 多维数据流模式:假设a = 4 ,a :a k ) 是一个有界、全部 有序域的集合,s = 4 4 4 】是一个k 维数值空间,其中4 ,a :a k 以表示s 的k 个维。k 维数据流x = ( 石。,x :x 。) ,表示s 上的数据流t 时刻 的一个点集,其中鼍= ( 石n ,t :e ;) 表示一个数据点,嘞为数据点x i 的第j 维的值;e i 表示z ;的值,可以是正数也可以是负数。 从数据挖掘的角度分析,数据流具有以下特性: 有序性、连续性、实时( 或随时) 性,数据有序地、连续地到达并实 时地变化; 无限性,大数据量,甚至是无限的数据量,存储所有数据的代价是极 大的; 单遍性,由于内存的限制,只能对数据流进行单遍扫描; 概要性,处理数据流中的数据时,要求构造概要数据结构; 低层次性和多维性,数据流的原始细节数据的概念层次较低且具有多 哈尔滨丁程大学硕十学位论文
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 高一政治必修一“原始社会的解体和阶级社会的演进”教学设计
- 高中信息技术选修算法与程序设计双重循环教学设计
- 初中数学九年级下册反比例函数图象与性质复习教学设计
- 八年级物理 熔化与凝固 教学设计
- 初中物理八年级上册 1.1 声音是什么 教学设计
- 小学五年级班队活动教学设计《做自己的舵手-从被管教到自觉的成长》
- 初中八年级信息技术《改变图像大小和方向》教学设计
- 学期教学工作总结
- CN119538297A 一种基于客户端分组的联邦学习隐私保护方法 (安徽工业大学)
- CN119537506A 一种异步式服务化信息检索和索引管理方法及系统 (中国石油天然气股份有限公司)
- 东营港东营港区环抱港池内航道维护性疏浚工程环境影响报告书
- 熔化焊接与热切割培训课件
- 12J9-1 室外工程图集
- ReFi动态养老财务模型目标基准点及养老财务相关知识测试题附答案
- GB/T 29911-2025汽车租赁服务规范
- 河大版小学信息技术课件教学
- 贝壳租房合同协议
- T-CALC 007-2025 重症监护病房成人患者人文关怀规范
- 《农村既有居住建筑抗震鉴定与加固技术标准》
- ABBdcs组态课件CONDUCTORVMS操作
- DB43T 833-2016 前(后)置微耕机
评论
0/150
提交评论