（计算数学专业论文）演化数据流的异常检测研究.pdfVIP

摘要 随着计算机与网络通信技术的飞速发展和应用领域的不断扩大， 在传感器网络管理、金融风险分析、互联网流量管理和网络入侵检测 等诸多领域里，处理的数据不再是有限存储的数据集合，而是短时间 内大量到达，随时间动态变化的演化数据流。传统的数据库技术无法 使用有限空间来快速处理这种海量、高速的数据流从而获取实时的有 用信息。如何对这些场景中大量的数据流实时准确地进行异常检测以 达到相关的应用需求己成为当前数据流挖掘的研究热点。 由于演化数据流具有快速到达只能一次遍历的特征，数据流异常 检测的最大挑战在于如何快速捕获数据流的实时变化并及时响应，从 而得到近似的检测结果。本文综述了目前国内外关于数据流异常检测 的研究成果；在分析现有研究成果的基础上，针对数据流的不同应用 场景，分别提出了解决方法。针对中低维的集中式数据流，采用l o f 算法和s r 树索引结构结合的方法设计了s ri n c l o f 算法，特别针对 高维的集中式数据流场景，提出了基于张量分解的异常检测算法；对 于分布式数据流场景，构建了一个分布式的数据流异常检测模型，设 计了结合核密度和微簇树数据结构的异常检测算法。通过不同类型数 据集的实验验证了本文算法的异常检测性能相比其他同类算法都有 较大的提高。本文的研究内容包括以下几个方面： 针对基于密度的l o f 算法所存在的不足进行改进，提出一种结 合s r 索引树的异常检测优化算法s ri n c l o f 算法，能够解决集中式 的低中维数据流异常检测问题。该算法通过s r 索引树来快速查找每 个数据点的k n n 集和k r n n 集，采用局部异常因子l o f 刻画异常 程度，不但能够快速地增量更新，有效地解决了数据流的快速演化和 一次遍历等问题，而且复杂度较低，支持实时要求非常高的数据流异 常检测。 针对高维的集中式数据流异常检测问题，分析了基于张量分解的 高维索引技术，提出了基于张量分解的异常检测算法。该算法以张量 的视角来模拟演化数据流，对此进行张量分解，基于张量分析来近似 数据流的分布，并且通过自适应采样能得到关于数据流的最佳近似矩 阵，易于实施。 针对分布式数据流场景，提出基于核密度的分布式异常检测技 术，提出了两种新的异常点定义，分别对应于基于距离和基于密度的 异常分布。针对此问题提出两种有效的算法，第一个算法基于核密度 估计技术来快速近似的获取数据流的分布，同时采取指数衰减技术解 决数据流的时间演化；第二个算法结合微簇( m i c r o c l u s t e r ) 技术处理数 据的划分问题。 综上所述，本文针对演化数据流的不同应用场景，分别提出了不 同的解决方案，通过理论分析和模拟数据集的实验表明，本文提出的 算法具有较高的精度和反馈率，并且时间复杂度和空间复杂度较低， 更加适用于演化数据流场景。 关键字：演化数据流，异常检测，s r 树，局部异常因子，张量分解， 核密度估计 i l a b s t r a c t a l o n gw i t ht h ec o m p u t e ra n dn e t w o r kc o m m u n i c a t i o nt e c h n o l o g y 螂i dd e v e l o p m e n ta n dt h ee x p a n s i o no fa p p l i c a t i o n s ，d a t ap r o c e s s e d i sn o l o n g e rd a t ac o l l e c t i o nw i t hl i m i t e ds t o r a g e ，b u tt h ee v o l v i n g d a t as t r e a m s c h a r a c t e r i z e db ys h o r ta r r i v a lt i m ea n dd y n a m i cc h a n g eo v e rt i m e ，i nt h e f i e l d so fs e n s o rn e t w o r km a n a g e m e n t ，f i n a n c i a lr i s ka n a l y s i s ，i n t e m e t t r a f f i cm a n a g e m e n ta n dn e t w o r ki n t r u s i o n d e t e c t i o ne t c t r a d i t i o n a l d a t a b a s et e c h n i q u e sc a nn o tu s el i m i t e ds p a c e t od e a lw i t hm a s sa n d h i g h s p e e df l o wd a t a ，a n do b t a i nu s e f u li n f o r m a t i o ni n r e a l t i m e h o wt o m a k ea c c u r a t e l yo u t l i e rd e t e c t i o ni nr e a l - t i m et od a t ai nt h e s es c e n e sa n d a c h i e v et h er e l e v a n ta p p l i c a t i o nr e q u i r e m e n t sh a sb e c o m eah o tr e s e a r c h t o p i ci nd a t as t r e a m sm i n i n g d u et oe v o l v i n gd a t as t r e a m sq u i c k l ya r r i v ea n dc a nb et r a v e r s e d o n l vo n c e ，o n eo ft h eb i g g e s tc h a l l e n g e sf a c i n gt h eo u t l i e rd e t e c t i o ni n d a t as 仃e 舢i sh o wt oc a p t u r et h er e a lt i m ec h a n g e so f d a t as t r e a mf a s t l y , t i m e l yr e s p o n s ea n dg e ta p p r o x i m a t et e s t i n gr e s u l t s ac o m p r e h e n s i v e s u r v e yo nt h e o u t l i e rd e t e c t i o ni nd a t as t r e a m s l sg i v e n i no r d e rt o e f f e c t i v e l vi m p r o v et h es p e e da n da c c u r a c yo fd e t e c t i o n ，l o fa l g o r i t h m a n ds rt r e ea r eu n i t e d a na l g o r i t h mb a s e do nt h ed e c o m p o s i t i o no f t e n s o ri sp r o p o s e dt od e a lw i t hh i g hd i m e n s i o n a ld a t as t r e a m s b a s e do n a n a l y s i s o fe x i s t i n gr e s e a r c hr e s u l t s ，t h i sp a p e rm o d e l sa d i s t r i b u t e d o u t l i e r d e t e c t i o ni nd a t as t r e a m s t w on o v e l f o r m a ld e f i n i t i o n so f a b n o r m a lp o i n t sa r eg i v e n a no u t l i e rd e t e c t i o na l g o r i t h m c o m b i n e dw i t h d a t as t m c t u r eo fm i c r oc l u s t e ri sd e s ig n e d t h ec o n t r i b u t i o n s i nt h i sp a p e r i n c l u d et h ef o l l o w i n ga s p e c t s s ri n c l o fa l g o r i t h mi sp r o p o s e dt oe f f e c t i v e l yi m p r o v e t h es p e e d a n da c c u r a c yo fc e n t r a l i z e d a n dn o r m a ld i m e n s i o n a ld a t a s 仃e a h 峪 d e t e c t i o n t h ea l g o r i t h mq u i c k l ys e a r c h e st h ea p p r o x i m a t en e i g h b o rs e t i i i o fe v e r yd a t au s i n gt h es t m c n l r eb l o c ko fs rt r e ei n d e xa n dd e p i c t s o u t l i e rl e v e lb yl o c a lo u t l i e rf a c t o r t h ea l g o r i t h mc a l le f f e c t i v e l ys o l v e t h et h ep r o b l e m so fr a p i df l o wo fd a t as t r e a m sa n dt r a v e r s a lo n c e ，h a s l o w e rc o m p l e x i t y , a n ds u p p o r t n o r m a ld i m e n s i o n a ld a t as t r e a m s d e t e c t i o n f o rm u l t i d i m e n s i o nd a t as t r e a m s ，h i g h d i m e n s i o n a li n d e x t e c h n i q u e sa b o u tt h ed e c o m p o s i t i o n o ft e n s o ra r ea n a l y s z e da n da l lo u t l i e r d e t e c t i o na l g o r i t h mi sp r o p o s e d t h ea l g o r i t h m v i e w se v o l v i n gs t r e a m sa s at e n s o r , d e c o m p o s i t et h et e n s o r , a n da p p r o x i m a t ef l o wd i s t r i b u t i o no f d a t aa n dg e tm eb e s ta p p r o x i m a t i o na b o u td a t as t r e a mm a t r i xt h r o u g ht h e s e l f - a d a p t i v es a m p l i n g o u t l i e rd e t e c t i o nt e c h n o l o g yi sb a s e do nak e r n e ld e n s i t y t h r o u g h m ea b n 0 1 瑚ld i s t r i b u t i o na b o u td i s t a n c ea n dd e n s i t y , t w on o v e lf o r m a l d e f i n i t i o n so fa b n o r m a lp o i n t sa r eg i v e n u s i n gt h ek e m e ld e n s i t y e s t i m a t et e c h n i q u e sa l la l g o r i t h mi si n t r o d u c e dt oq u i c k l yg e ta p p r o x i m a t e f l o wd i s t r i b u t i o no fd a t a t h ee x p o n e n t i a ld e c a yt e c h n o l o g yi st a k e nt o s 0 1 v et h et i n l ee v o l u t i o no ff l o wd a t ai n t h i sa l g o r i t h m a no u t l i e r d e t e c t i o na l g o r i t h mc o m b i n e dw i t hd a t a s t r u c t u r eo fm i c r oc l u s t e ri s d e s i g n e dt op r o c e s sd a t ap a r t i t i o np r o b l e m s t os u mu p ，a i m i n ga tt h ec h a r a c t e r i s t i c so fe v o l v i n gd a t as t r e a m s ， t h i sp a p e rp r o p o s e sd i f f e r e n ts o l u t i o n s t h e t h e o r e t i c a la n a l y s i sa n d e x p e r i m e n t ss h o wt h a ta l g o r i t h m sp r o p o s e dh a v eh i g h e rp r e c i s i o na n d r e s p o n s er a t e ，l o w e rt i m ec o m p l e x i t ya n ds p a c ec o m p l e x i t y , a n d a r em o r e a p p l i c a b l et oe v o l v i n gd a t as t r e a m s - k e yw o rds ：e v o l v i n gd a t as t r e a m s ，o u t l i e rd e t e c t i o n ，s rt r e e ，l o c a l o u t l i e rf a c t o r ，t e n s o rd e c o m p o s i t i o n ，k e r n e ld e n s i t y e s t i m a t e 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不合任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：捅孕陟 加哆年 石月纱 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 研究生在校攻读学位期间论文工作的知识产权单位属湖南师范大学。 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密日。 ( 请在以上相应方框内打“”) 作者签名：胡雪杉日期：p 的年占月矿日 导师签名：高君吨乌 日期：) 1 ，哆年占月9 日 演化数据流的异常检测研究 1 1 引言 1 绪论 近年来，由于实际应用需求的推动，数据库技术在许多领域中得 到了广泛的应用。但是白上个世纪末以来，随着计算机技术在诸如网 络路由、传感器网络、股票分析等领域应用的普及和深入，产生了一 种新型的数据，使得传统数据库技术面临很大的挑战。这类数据持续 到达，且速度快、规模宏大，传统的数据库技术由于时间空间复杂度 高，对这类数据进行分析和管理显得非常困难，学术界将具有这类特 征的数据序列形象地称为数据流。有关数据流异常检测与挖掘的研究 是目前国际数据库研究领域的一个热点。对这类典型的数据流进行处 理时，大多数传统的异常检测方法需要一次性将所有数据载入内存， 耗费大量计算时间，无法满足海量数据流环境下的实时知识提取需 要，因此数据流异常检测方法研究是当今数据流分析领域富有挑战性 的前沿课题。本文以大规模演化数据流为研究对象，采用数据挖掘、 机器学习和人工智能等技术和分布式计算相结合的方法，探索数据流 环境下新的异常检测技术，为高效、合理利用大规模数据流提供理论 和技术基础，针对数据流异常分析的若干数据流场景进行深入研究并 分别提出了新的解决方案。 1 2 课题研究背景及意义 数据流的应用非常广泛，从环境和天文监测、计算机网络监控、 金融股票交易到网页搜索日志分析等无所不在。该类应用中，海量数 据以实时方式快速到达。下面列举几个常见的数据流应用场景。 ( 1 ) 传感器网络( s e n s o rn e t w o r k ) 【1 1 目前已经广泛分布于各种 地理环境中，如热带雨林、江河流域以及高速公路等，用于地理信息 硕十学位论文 监测、生命信号检测、车辆运动跟踪和交通拥塞检测等。在传感器网 络中，大量传感器每时每刻不断感应出大规模的监测数据流，并通过 无线网络传输到基站。基站中的数据分析服务器必须及时地对这些监 测数据流进行分析和处理。 ( 2 ) 互联网应用【2 】。计算机互联网实时交互着大量的及时通讯 消息、电子邮件、在线视频等数据。这些数据被封装为各种i p 数据包 通过局域网或广域网从源地址传送到目标地址。作为网络连接节点的 路由器、交换机等设备需要极快地传输这些i p 数据包，例如c i s c o 公 司n w s c 6 5 0 3 交换机最高背板带宽高j 达7 2 0 g b p s t 3 1 。因特网服务提供 商例如中国网通需要从交换机设备中获取这些实时i p 数据包并进行 分析挖掘，从而实现对计算机网络的实时监控和维护。 ( 3 ) 金融股市【4 】。股票和基金等金融交易报价数据瞬息万变且 规模庞大，全世界每天交易着成千上万种价格瞬息万变的股票和基 金。这些金融数据的在线分析涉及到趋势识别、相关性分析与价格预 测等诸多方面，快速获取这些金融信息就意味着更好的财富机会和更 小的金融风险。与此同时，世界各地各种政治、经济、文化新闻和突 发事件不断涌现。它们也直接或间接影响着这些股票和基金的价格。 仅据美国n y s e 、a m s e 、n a s d a q 和s m l l c 印四个股票交易所的不 完全统计信息，上市股票的日常交易数据和报价数据以每天1 0 g b 的 速率增长。 ( 4 ) 网页搜索 5 1 。目前网页搜索引擎已形成了一种新兴产业。 例如百度公司每天都需要对8 亿多中文网页完成上亿次搜索，g o o g l e 公司每天需要对全球6 0 多亿网页完成2 亿次搜索。2 0 0 6 年度中国搜索 引擎市场报告显示2 0 0 6 年中国网页搜索用户数匕l 2 0 0 5 年增长2 2 6 ， 并还将以每年1 1 以上的速度递增。 上述各种应用场景的共同特点是海量数据实时快速到达。学术界 把具有海量、快速、连续、随时间到达的数据序列称为数据涮6 1 。数 演化数据流的异常检测研究 据流模型与传统数据模型的主要区别如下： 1 ) 部分或者所有待操作的输入数据无法通过读取磁盘或者内存，进 行任意的存取。获得的只是一个或多个连续到达的数据点。 2 ) 与等待处理的数据流的大小相比，可以使用的内存空间非常有限。 3 ) 到达数据流的数据量和数据值通常显示出不规则的情况，例如一 定时间内网络中传输的数据包的数量经常有突变( b u r s t ) 的行为，同 样的情况也发生在网站访问量以及电子邮件的数量变化中。 4 ) 数据流模型下数据规模大、速率快，因此对于一些复杂问题，往 往实际应用并不要求返回精确的查询结果，通常只需要返回一个近似 值。 目前数据流相对于传统数据库例如基于磁盘的数据库己成为一 种新兴且日益主流的数据存在方式。人们迫切需要从这些包含有大量 数据的数据流中提取有价值的信息和知识。因而，数据流的分析和挖 掘日益成为一个热点问题。作为一种基础且重要的数据挖掘手段，数 据流环境下的异常分析得到了学术界和工业界的广泛关注。在传统数 据库中，数据流异常分析已经在图像处理、模式识别、空间数据分析、 市场调研等领域取得了实际应用。在数据流环境中，异常分析同样是 一种重要的并具有强大信息提取功能的数据分析技术，例如：在线分 析金融数据流的异常行为，可实现金融欺诈检测，消费者分布状况统 计以及为金融走势预测提供支持。金融数据的变化，往往代表着消费 者分布状况的改变，新消费模式的形成以及金融走势出现新变化。 本课题基于国家8 6 3 项目“基于本体的图像检索系统。该系统旨 在更好地实现动漫资源的存储、管理以及检索服务，从而为动画公司 以及动画的制作人员提供一个基础平台，实现动漫产业基地的资源共 享，增加不同基地人员协同工作能力。在卡通动画素材库的建设中， 数据库的出现解决文件管理数据的不足，同样，为了解决管理图像数 据、x m l 数据和文本数据，人们很容易地会想到使用数据库。传统 硕士学位论文 的关系数据模型建立在严格的关系代数的基础上，因此，目前平坦化 的数据类型不适于表达复杂的信息，文本、x m l 、图像这些非格式 化的数据是关系模型无法处理的；简单化的关系也会破坏这些信息实 体的复杂联系。这些非格式化的数据由于具有丰富的语义性，因此超 过了关系模型的表示能力。如何将原有的关系数据库产品加以扩充， 使之在一定程度上能支持多种媒体的应用，是数据库发展的一个重要 方向。卡通动画素材资源库集多种媒体于一体，该素材数据库中的数 据量巨大且各种数据媒体之间格式的差异也极大，目的是将分散于各 处的x m l 文件、图片、概念、索引文件、动画等各种资源统一管理， 因此信息量非常大，覆盖面广，能面向所有的动画制作人员，使媒体 资料能得到充分共享，从而扩展了创作空间。 本课题对卡通动画素材库的研究主要集中于如何改进检索效果。 在动画素材数据库的存储方面，由于各种异常数据的加入，不但加重 数据库存储负担，导致时空信息冗余巨大，并且检索质量低下，查询 效率不高或者无效查询增加，甚至系统瘫痪。因此异常检测模块是其 中重要的一个模块。 针对这些问题，本文深入研究了集中式和分布式数据流环境中的 异常检测算法，针对集中式的中低维数据流采用基于s r 索引树和局 部异常因子的异常检测算法，针对集中式高维数据流，采用结合张量 分解的方法以解决常规算法的维数灾难问题，而对于分布式的数据流 异常检测通过基于核密度和微簇树相结合的方法可以有效得到解决。 1 3 研究框架与创新点 本课题的研究内容分为以下几个方面： 1 ) 基于s r 索引树的快速异常检测算法 针对集中式的中低维数据流，采用基于s r 索引树和i n c l o f 算 法结合的快速异常检测算法，通过s r 树能够迅速得到每个数据点的 演化数据流的异常检测研究 k n n 集和k r n n 集，利用局部异常因子l o f 快速估算数据的异常程 度，采用i n c l o f 算法能够避免数据流演化过程中重复计算非异常点 的异常因子，检测效率得到快速提高，从而快速获得实时的异常点集。 2 ) 检测高维演化数据流的异常处理 在集中式高维数据流的实际应用中，例如金融股票交易、天气及 环境监测以及电话通讯等应用中，成百上千的远程站点连续不断地产 生高速数据流。这些数据流往往都是高维的，传统异常检测算法在通 讯量开销，处理能力，内存开销方面难以满足高维数据流实时在线挖 掘的需求，导致“维数灾难”。本文以张量的视角来看待高维数据流， 对此进行张量分解，针对张量的某一显著维进行了张量分解后，会得 到一个矩阵，这样数据的维度便从高维降到了低维，并且数据特征几 乎不会发生改变。在该矩阵中提取数据流的基本代数特征，即奇异值 特征，然后将奇异值特征映射到投影空间，每一个向量就对应了数据 流中的一个点，根据向量范数即点之间的欧氏距离进行基于距离的孤 立点检测，可得到异常点，该算法基于张量分析来近似数据流的分布， 并且通过自适应采样能得到关于数据流的最佳近似矩阵，易于实施。 3 ) 基于分布式数据流环境的异常检测系统 在分布式数据流聚类环境中，往往会出现一些新到达的数据点无 法被现有任何簇所吸收的情况。我们将这类数据点称为“异常点”。之 所以对异常点加引号，是因为它们只是不属于当前任何簇，并不一定 是真正的异常点。在分布式数据流中产生“异常点”主要有如下两类情 况：( 1 ) 由于数据流的动态特性，数据流中的数据分布往往随时间 不断发生变化。从而导致一些新数据点无法被现有的簇所吸收。这些 无法被现有簇所吸收的新数据点往往可能代表着一类新出现的簇。 ( 2 ) 在分布式数据流应用中，受各种因素的干扰如传感器受外部电 磁干扰，往往会随机出现一些噪声，这些噪声同样表现出无法被现有 簇所吸收的特点。在传统异常检测中，数据集中的簇与异常点是非常 硕士学位论文 不确定且不随时间变化的。目前大多数异常检测算法无法识别异常点 的具体属性，统一作为噪声处理。然而在分布式数据流环境下“异常 点”却有可能成长成为新的簇，例如第一种情况中的“异常点”往往代 表一个新簇的出现。第二种情况中的“异常点”才是在数据流环境下真 正需要消除其影响的对象。本文提出的分布式数据流异常检测系统能 快速而准确地检测并处理这两类不同的“异常点”。 4 _ ) 在线捕捉数据流的演化 由于分布式数据流的动态性，它必须通过有效而鲁棒的分析技术 来克服其自身固有的动态性。通常的做法是假定待处理的数据流符合 某种特定的分布，采用基于模型的异常检测算法，而分布式数据流中 的数据往往具有交叠性，有噪声、受损或不完整性，显然用这种方法 经常得不到正确的异常集。为了在线捕获分布式数据流的演化，本文 采用了一个具有指数衰减的核密度估计策略，该策略的基本思想是让 逐步减少旧数据的权重直至丢弃历史数据，权重越大，旧数据相对于 新数据重要性越大。这种方法能够广泛应用于时间序列分析和预测。 即通过权重来调节原始数据和当前数据的影响程度，以适应不同的应 用环境。 5 ) 高效的m i c r o c l u s t e r 树存储方法 数据流上的簇表示法主要应具有两方面特性：( 1 ) 空间节省。 传统基于聚类算法的数据异常检测，尤其是基于层次和密度的算法， 往往需保留簇中各个数据点甚至是保留簇中所有数据点来进行簇的 描述。然而，这类簇表示法在数据流环境下已不再适用。随着新数据 点的不断到达，保留簇中所有数据点会带来无限增长的存储开销。因 此任何基于聚类的数据流异常检测算法都无法将所有数据点保留下 来实现对数据簇的描述。此外，由于数据流的实时性，我们只能利用 内存资源处理这些原始数据点，且难以实时地将原始数据点存入其它 存储设备。因而数据流上的簇表示法必须是空间节省的。( 2 ) 时间 演化数据流的异常检测研究 特征。传统数据聚类往往是对数据库中的静态数据进行聚类，簇的时 间特征要求并不明显。然而在数据流动态环境下，新簇随时间不断产 生，旧簇随时间不断消亡。此外，数据流上的聚类分析请求也往往具 有时间属性，即用户往往只关心一段时间窗口的簇。因而，数据流聚 类算法中的簇表示法应具有时间特征。本文采用的m i c r o c l u s t e r 树存 储方法可以同时满足上述两种要求，能很好地解决分布式演化数据流 的连续异常检测问题。 6 ) 快速增量处理新到达数据点的能力 这个需求也是由数据流中海量数据高速到达所造成的。在分布式 数据流异常分析过程中，这往往不是一个容易达到的需求。这是因为， 对新数据点的处理往往取决与该数据点与已往数据点的相似程度关 系。这种相似度的度量通常基于某种评价函数。该评价函数需具有如 下两个特性：( 1 ) 对新数据点与己往数据点的相似度评判，不应要 求保留以前的数据点。( 2 ) 评价函数应当具有较小的计算复杂度， 适合于大数据量的实时在线处理。第一个特性再次提出了对数据簇表 示的空间节省要求，此外，还要求该评价函数有利用当前簇结构进行 相似度评判的能力。第二个特性对评价函数的计算复杂度方面提出要 求，通常计算复杂度至多应与当前簇结构个数呈线性。本文通过核密 度估计函数作为评价函数，能够快速地增量处理新到达数据的相似 度。 1 4 论文组织结构 论文分为六章，各章的内容安排如下： 第一章为绪论，主要介绍论文的研究背景，阐述了数据流挖掘方 面的应用需求，讨论数据流挖掘方面的典型方法，最后对论文的研究 内容及创新点进行概述。 第二章分别从集中式和分布式两个方面讨论了数据流异常检测 硕士学位论文 领域相关的研究现状，介绍该领域相关的概念与现有的数据流异常检 测系统。 第三章针对集中式中低维数据流的异常检测，结合s r 树索引和 l o f 算法提出一种新的检测算法：s ri n c l o f 算法，该算法利用s r 树 快速索引演化数据流上滑动窗口中的数据点，能够实时得到每个数据 点的k n n 集和k r n n 集，通过局部异常因子l o f 快速估算相关数据点 的异常程度，从而获得实时的异常点集。该算法能实时捕获数据流的 快速变化，并高效处理这种变化，得到该数据流的异常点集。 第四章针对集中式高维演化数据流中的异常点提出了一种新算 法w s t a ( w i n d o w ss t r e a m i n gt e n s o r sa n a l y s i s ) ，该算法引入张量分 解的思想，将滑动窗口中的高维数据流作为整个数据流的子张量，在 滑动窗口中通过自适应抽样生成概要数据结构，用张量分解压缩数 据，在数据稳定压缩以后检测质量不会显著降低，然后通过基于欧式 空间距离的异常检测算法即可得出检测到的异常点。 第五章针对分布式环境中数据流异常分析问题，采用核密度估计 技术来快速近似的获取数据流的分布，并能在精度可控的情况下极大 的减少节点间的通信开销，设计了一种新的概要结构m i c r o c l u s t e r 树 来保持滑动窗口中簇的统计信息，数据的划分问题也能得到很好的处 理；同时采取指数衰减技术解决数据流的时间演化，实验证明文中提 出的算法在时间复杂度和空间复杂度方面都取得了比较理想的结果。 第六章对本文的工作进行总结，并展望下一步的研究工作。在实 际研究过程中，充分重视将各种研究方法有机地结合起来，达到相互 弥补、相互印证的目的。 演化数据流的异常检测研究 2 数据流异常检测相关技术和问题 2 1 国内外研究现状 近年来，k d d 在研究和应用方面发展迅速，尤其是在商业和银 行领域的应用比研究的发展速度还要快。作为一门处理数据的新兴技 术，异常检测有许多的新特征。首先，数据挖掘面对的是海量的数据， 这也是异常检测产生的原因；其次，异常数据是不完全的、有噪声的、 随机的，有复杂的数据结构，维数大；最后，异常检测是许多学科的 交叉，运用了统计学，计算机，数学等学科的技术。 目前，国外异常检测的发展趋势其研究方面主要有：针对传统数 据的异常检测在统计学方面的研究进一步发展，如近年来注重对 b a y e s ( 贝叶斯、) 方法以及b o o s t i n g 方法的研究和提高；针对异常检测 的k d d 商业软件工具不断产生和完善，注重建立解决问题的整体系 统，而不是孤立的过程。用户主要集中在大型银行、保险公司、电信 公司和销售业。国外很多计算机公司非常重视异常检测系统的开发应 用，i b m 和微软都成立了相应的研究中心进行这方面的工作，此外， 一些公司的相关软件也开始在国内销售，如p l a t i n u m 、b o 以及i b m 。 现有的算法研究可归为以下五类：基于分布的、基于聚类的、基 于距离、基于密度的和基于索引的。 1 ) 基于分布的方法【7 】是预先假定数据服从某种概率分布模型( 如正 态分布) ，显著偏离模型的数据即为异常点。然而，在高维数据空 间中，很难获取其数据的概率分布模型。为了克服这些局限性， 研究人员转向各种非参数的方法。 2 ) 基于聚类分析 8 】的方法。这是无监督异常检测技术中最具有代表 性的方法。聚类，又称无指导的学习，是数据挖掘中重要的一类 方法，可以不依赖预先定义的类和带类标号的训练实例来完成数 硕士学位论文 据集的划分。p o r t n o y 首先提出了基于聚类分析的异常检测技术， 之后又有不少研究者提出各种相似算法，但是该方法的基本流程 都是先对数据集进行聚类，然后标识数量稀少的类为异常类。这 种方法存在的不足在于：( 1 ) 有些聚类算法如k - m e a n s 1 1 】可能会 落入局部最优的陷阱，导致结果不精确；( 2 ) 由于某些入侵行为 的数量可能非常稀少，以致于被邻近的大类所吸收，而并没有形 成单独的一个类，这样就有可能被混入正常类而漏报。因此基于 聚类的方法在检测率方面并不总是令人满意。其余的大部分聚类 算法，例如c l a r a n s 12 1 、d b s c a n 1 3 1 、b i r c h 1 4 1 、w a v e c l u s t e r t l5 1 、 c l i q u e 1 6 】等，在某种程度上它们的主要目的也是寻找聚类，针 对聚类进行优化，而把异常点检测作为其算法的“副产品 3 ) e m k n o r r 和r t n g 首次提出基于距离的方法【9 】，该方法试图克 服基于分布方法的局限，通过计算数据点之间的距离来寻找异常。 该算法认为如果一个数据点与其它大多数的数据点充分的远，则 该点更像异常点。由于该类算法基于单一全局的判别参数，而在 数据集中存在不同密度的数据分布时，该方法就束手无策。于是 研究人员提出了更为鲁棒的基于密度的算法。 4 _ ) 基于密度的方法【1 0 】最先由m b r e u n i g 等人提出。它为每个点定义 一个局部异常因子( l o f ) ，此因子通过它附近邻居的局部密度来计 算，通常，具有相对高l o f 值的点即为异常点。该方法吸引了很 多研究人员。近年来，这类算法主要关心如何定义密度或提高算 法的效率等，最为有名的算法有：l o c i 算法【1 7 1 。 5 ) 在分布数据流环境中，b a b c o c k 和o l s t o n 提出了分布的t o p k 查询 算法【1 8 】，a m i tm a n j h i 等人考虑在分布数据流中查找频繁项集【1 9 】， s u b r a m a n i a m 等人更侧重于分布式传感器数据流的异常检测【2 0 1 ， c o r m o d e 等人研究了分布式数据流上的连续聚判2 l 】问题。 目前国际上比较著名的数据流研究小组有：s t a n f o r d 大学正在构 演化数据流的异常检测研究 建的基于关系的通用数据流处理系统s t r e a m 2 2 1 ；b r o w n 大学建立 的基于工作流的、用户通过直观连线方式操作数据流的系统 a u r o r a 2 3 1 ，该系统使用一种结构化的查询语言( g s q l ) 表达查询条件。 在查询过程中，除需要描述哪些元组( t u p l e ) 要被处理以外，不用对诸 如选择( s e l e c t i o n ) 矛i 投影( p r o j e c t i o n ) 等操作进行特别声明；加州大学 b e r k e l e y 分校构建的持续查询处理系统t e l e g r a p h c q ，主要着重研 究共享子查询求值以及多查询的自适应调度，能够解决内存管理和近 似查询处理方面的问题。该系统使用c q l 语言定义查询，生成查询 计划等，灵活地调度运算符更好地分配系统资源，使资源朝着最优化 查询准确率的方向分配。此外，该系统可以在系统性能和查询准确性 之间进行权衡，最终给出适合当前数据流速度以及查询负载的策略； 另外还有c o m e l l 大学的c o u g a r 项卧2 5 1 ，w i s c o n s i n 大学n i a g a r a c q 项引2 6 1 ，一个连续查询( c o n t i n u o u sq u e r y ) 处理系统，它支持自适应的， 以及面向监测的查询处理。 国内研究数据流处理系统主要是中科院计算所软件室的“冰河 2 0 0 4 ”【2 7 】项目组。“冰河2 0 0 4 ”正在构建一个基于关系的通用数据流处 理平台，并在这个平台上构建宏观网络安全监测系统、金融监察系统 两个应用。 2 2 有关定义 定义2 1 ：数据流( d a t as t r e a m ) 。按照固定的次序持续到达，且其中 的数据元素只能被读取一次或有限次。若令t 表示任一时间戳( t i m e s t a m p ) ，五表示在t 时刻到达的数据元素，则数据流可以表示为无限集 合 ，巾，x t 小 。 定义2 - 2 ：多维数据流模式。假设a = 4 ，4 ，a x ) 是一个有界、全部有 序域的集合，s = 4 4 xa r 是一个k 维数值空间，其中4 ，4 ，以 表示s 的k 个维。k 维数据流x - - ( x 。，x ：，x 。) ，表示s 上的数据流t 时 硕士学位论文 刻的一个点集，其中x i - - ( x ”工，x 岛) 表示一个数据点，x 西为数据 点x ；的第，维的值；e ，表示x ，的值，可以是正数也可以是负数。 从数据挖掘的角度分析，数据流具有以下特性： 有序性、连续性、实时( 或随时) 性，数据有序地、- 连续地到达 并实时地变化： 无限性，大数据量，甚至是无限的数据量，存储所有数据的代 价是极大的，i 单遍性，由于内存的限制，只能对数据流进行单遍扫描： 概要性，处理数据流中的数据时，要求构造概要数据结构： 低层次性和多维性，数据流的原始细节数据的概念层次较低且 具有多维( 或高维) 的特点； 近似性，数据流查询以及挖掘处理得到的结果是近似的； 即时性，用户要求得到即时的处理结果。 数据流查询中，往往对最近产生的数据更感兴趣，而不是历史数 据。在进行检测时，并不计算整个历史数据流，而是计算最近流中进 来的数据。例如股票市场，只有上个星期的数据能够得出查询结果， 而上个星期以前的数据都将被丢弃。这种查询采用滑动窗e l 2 8 】的技 术。 定义2 3 ：滑动窗口( s l i d i n gw i n d o w ) 。在一个数据流上维护目前为 止最近的n 个数据元素的总计以及其他统计变量，我们把这种只考 虑最近n 个元素的模型称为滑动窗口模型。 滑动窗口的大小基于数据流元素个数，窗口的两个端点，分别确 定了这个窗口在数据流上的起始位置和终止位置。滑动窗口的两个端 点都随时间而移动，并且通常窗口大小保持为一个常数c o ，我们称这 个窗e l 为滑动窗 ( s l i d i n gw i n d o w ) 。窗口更新间隔，确定了滑动窗口 随数据元素到达而移动的频率。如果每到达一个新的数据元素，窗口 跟着向前滑动一个位置，这是最一般意义下的滑动窗口；如果每当j 演化数据流的异常检测研究 ( j 小于窗口内数据元素个数) 个数据元素到达时，窗口才向前滑动 i 个位置，这样的滑动窗口被称为跳动窗e l ( j u m p i n gw i n d o w ) ；如果 每当n ( n 等于窗口内数据元素个数) 个数据元素到达时，滑动窗口才向 前滑动n 个位置，这样的窗口被称为滚动窗口( t u m b l i n gw i n d o w ) 。 后两种滑动窗口是一般意义下的滑动窗口在时间维度下的简化形式。 本文研究的滑动窗口是基于后者的。 滑动窗口模型非常适合于数据流计算。第一个原因是滑动窗口 提供了一种语义：因为主存无法保存整个数据流，所以很多查询可以 用最近到达的数据元素上的查询结果近似整个数据流上的查询结果。 这种近似语义是直观的，同时也是确定的，即不会带来随机误差；第 二个原因是很多用户查询语义本身要求在滑动窗口上计算查询结果， 因为真实世界中的大部分用户查询最关心的往往是最近到达的数据， 数据流中的元素的重要性随时间递减，而滑动窗口正好体现了用户的 这种查询语义。正因为如此，滑动窗口模型在数据流计算中占据重要 位置，目前正在研究中的很多数据流算法都是基于滑动窗口模型的。 数据流中很多问题的解决都要使用滑动窗口，如按位统计【2 8 1 、抽样【2 8 】、 计算方差【2 8 】等。 定义2 - 4 ：概要数据结构。将海量的数据流缩减为可以控制的概要数 据结构【2 9 1 ，并同时尽可能的保持数据的特征。这是在对海量数据进行 分析和挖掘的基础。几乎所有高性能的数据流分析都依赖于一定的数 据摘要技术。目前成熟的概要数据结构主要有：小波【4 9 1 、直方图【4 9 】、 哈希技术【3 2 】、分形 3 5 1 、抽样【2 3 】等。 2 3 数据流异常检测中的关键技术 在演化数据流中进行异常检测有