（计算机软件与理论专业论文）数据流异常检测技术研究与应用.pdf

l “_ ：! 。1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名：日期：2 口o 年万月石日 论文使用授权 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：二蛀导师签名： 日期：2 口 l 摘要 摘要 异常检测技术由于其在网络安全、信用欺诈和金融分析等领域的广泛应用， 一直都是信息科学研究领域的关注重点，研究者们将统计学，数据挖掘，信息理 论等众多技术引入异常检测的研究，提出了许多有效的异常检测方法。但是随着 社会信息化程度和数据采集自动化程度的不断提高，许多数据如商品交易、视屏 点播等都以数据流的形式出现，因此数据流作为待分析的动态数据集合越来越多 地引起研究者和工业界的关注。相比传统的静态数据集，数据流具有海量，无限、 多变化( 概念漂移) 等特点，这些特性都对传统的异常检测方法提出了挑战，其 中概念漂移更是给数据流异常检测方法的有效实现带来了极大的困难。如何建立 一种基于数据流的异常检测方法，使得该方法既能体现概念漂移对异常检测模型 的影响又能快速有效的进行异常检测，将是一个重要的研究课题。 本文以数据流作为研究对象，把对数据流概念漂移的处理引入异常检测研究 领域，通过捕获和容忍数据流的分布变化，提出了一种适合数据流应用场景的异 常检测方法，具有较高的应用价值。 本文开篇对传统的异常检测技术和现有的数据流异常检测技术进行了分析， 简要介绍了典型的检测方法并给出了自己的见解。在此基础上，本文提出了一种 响应式数据流异常检测方法。该方法首先将有监督和无监督算法结合应用到数据 流异常检测中，在实现了未知异常数据对象检测的同时保证了检测的效率。针对 数据流中概念漂移的难题，引入了概念漂移检测和容忍策略来适应数据流分布的 变化。通过训练数据选择、训练数据更新和多分类器集成，提高了分类器对概念 漂移的容忍度；通过量化分析和比较数据流中不同时间数据对象集合的整体特征， 实现了概念漂移的检测，并以此为依据触发异常检测模型的更新。实验表明，本 文提出的响应式数据流异常检测方法不但能够有效地实现数据流的异常检测，也 能够捕获数据流的概念漂移并及时更新异常检测模型。最后本文尝试将该方法应 用于p 2 p 僵尸网络检测中，通过对僵尸病毒传播过程中的p 2 p 僵尸通信进行捕获， 辅助实现网络中僵尸主机的发现，为进一步发现整个僵尸网络提供依据。实验表 明，本文中提出的数据流异常检测方法能够有效的捕获p 2 p 僵尸病毒之间的通信。 关键词：异常检测，数据流，概念漂移，p 2 p 僵尸通信 a b s t r a c t a bs t r a c t b e c a u s eo fv 撕o u sa p p l i c a t i o n s ，s u c h 嬲n 出r ks e c u r i 劬c r e d i t 丘a u dd e t e c t i o n a n d 矗n a l l c ea 1 1 a l y s i s ，0 u t l i e rd e t e c t i o ni sa l w a y sc o n s i d e r e d 嬲a i li m p o f t a n tr e s e a r c h a r e ai nd o m a i no fi n f o 肌a t i o n s c i e n c e 7 r e c h n i q u e s 行o ms t a t i s t i c s ， d a t am i n i n 吕 i n f o n n a t i o n 廿l e o r ye t c h a v eb e e i la p p l i e di l lt h i sa r e aa i l dv 撕o u se 毹c t i v eo u t l i e r d e t e c t i o nt e 蛳q u e sh a v eb e e np r o p o s e d h o w e v w i t ht h ei n c r e a s i n ga p p l i c a t i o n so f i n f b m a t i o nt e 6 h n o l o g ya n dr 印i dd e v e l o p m e n to fd a t aa c q u i s i t i o na u t o m a t i o n ，1 0 to f d a t as e t sa p p e a ri nf 0 册o fd a t as t r e 锄，s u c ha sd a t ao fc o m m o d 埘e x c h 锄g e ，o n l i n e m e d i ac o m m 埘：1 i c a t i o n ，e t c t h u sd a t as 仃e 锄，c o n s i d e r e da sak i n do fd m l 啪i cd a t as e t ， h a sb e e nb r o u 曲ti n t 0f o c u s 撇o n ga c a d 锄e sa n di n d u s 仃y sa t t e n t i o n c o n t r a s t e dw i t h s t a t i cd a t a s e t ， d a t as t r e 锄 h a san a t u r eo fm a 星m i t u d e ， i n f i n i t 夕a n dv a 矗o u s n e s s ( c o n c 印t - d r i f t ) ，a 1 1o fw h i c | hb r i n gc h a u e n g e st ot h et r a d i t i o n a lw a yo fo u t l i e rd e t e c t i o n t e c h n i q u e s e s p e c i a l l yt h ec o n c e p t d n ro fd a t as t r e a m ，w h i c hm a k e so u t l i e r sd e t e c t i o n t a s km u c hm o r ed i 衔c u l t h o wt of i n da no u t l i e rd e t e c t i o na p p r o a c hb a s e do nd a t a s t r e 锄，w h i c hc a ne x p r e s st h ec h a n g e so fo u t l i e rd e t e “o nm o d ec a u s e db yc o n c 印t d r i r a sw e l la sf i n d i n go u t l i e r se f i c i e n t l ya n de 虢c t i v e l y ，w i l lb ea ni m p o r t a n tr e s e a r c h s u b j e c t w ef o c u so nd e t e c t i n go u t l i e r so v e rd a t as t r e a mi nt h i s p a p e r s 0 1 u t i o n so f c o n c 印t d r i rh a v e b e e nu s e di nt h er e s e a r c ba r e ao fo u t l i e rd e t e c t i o n 1 1 啪u 2 1 1c a p t u r i n g a i l dt o l e r a t i n gm ec h a l l g eo fd a t as t r e a m sd i s t r i b u t i o n ，a no u t l i e rd e t e c t i o na p p r o a c h ， w h i c hi s 印p r o p r i a t eo v e rd a t a s t r e a n l ，h a sb e e np u tf o n a r d t h ep r o p o s e dn e w 印p r o a c hi so f 黟e a tv a l u ei na p p l i c a t i o n s i nt h e t h e s i s ， 打a d i t i o n a lo u t l i e rd e t e c t i o n t e c h n i q u e sa n do u t l i e rd e t e c t i o n t e c h n i q u e so v e rd a t as t r e 锄h a v eb e e na 1 1 a l y z e di nt h e 丘r s tp l a c e b e fi n t r o d u “o n s a n dp e r s o n a lv i e w so fs o m et y p i c a ld e t e c t i o na p p r o a c h e sh a v eb e e n 百v e n b a s e do n a b o v ea n a l y s i s ， ar e a c t i v eo u t l i e rd e t e c t i o n a p p r o a c ho v e rd a t as t r e 锄 h a sb e e n i n t r o d u c e d f i r s t l y ；s u p e r 、，i s e da n du n s u p e r v i s e da l g o r i t h m sh a v eb e e nc o m b i n e dt o r e a l i z et h eb a s i co u t l i e rd e t e c t i o nm e 也o do v e rd a t a s t r e a m w h i c hc a nc a t c ht h e u n k n o w no u t l i e r sa j l dk e e pr e l a t i v e h i 曲e f ! f i c i e n c ya 8w e l l a c c o r d i n gt ot h ek e y l i a b s t r a c t a p p l i e dt oa d a p tt h ec h a i l g eo fd a t as 骶锄t 缸o u 曲仃a i l l i n gd a t as e l e c t i o n ，订a i n i n gd a t a a d a p t a t i o na n dm u l t i p l ec l a s s i f i e r se 1 1 s 锄b l e ，m er o b u s 缸1 e s so fc l a s s i f i e r sh a sb e e n i n l p r o v e d b yq u a n t i t a t i v e l ya n a l y z i n ga n dc o n l p a r ec h a r a c t e r so fd i 触d a t ac h o c k w h i c he x 仃a c t e df 沁md a t as 仃l ；a ma td i 行i e r e n tt i m e ，m ec o n c 印t - 矾rd e t e c t i o nh a sb e e i l i m p l e 玎 1 e n t e d a n db a s e do n 1 ed e t e c t i o nr e s u l t s ，a i l 印t a t i o no fo u t l i e rd e t e c t i o nm o d e c a nb ea c t i v a t e dp r o p e d y t h ee x p e r i m e n t ss h o w sm a t ，t l l ea p p r o a c ho fr e a c t i v eo u t l i e r d e t e c t i o no v e rd a t as 拄e a mp r o p o s e di nt ：h i st h e s i sc a i ln o t o n l ya d a p t 也ed e t e c t i o nm o d e i i lt i m eb yc a p t u r i n gc o n c 印t - d r i r ，b u ta l s o d i go u t 1 ep o t e i l t i a lo u t l i e r so v e rd a t a s 骶a me 毹以v e l y f i n a l l y ，m ep r o p o s e da p p r o 如hh a sb e e nt r i e dt 0 印p l yi l ln l ea r e ao f p 2 pb o t n e td e t e c t i o n 7 1 1 1 r o u 曲c a p t l l r i n gn l ep 2 pb o t st r a 伍ci nt h ep r o c e e d i n go fb o t s s p r e a d ，w ec a i lh e l pt of i n dt 1 1 ec o m p r o m i s e dh o s th i d i n gi nm en e t 、) l ，o r ka n dp r o v i d e e v i d e n c et o 矗】r t b e rd e t e c t i o no ft 】ew h 0 1 eb o t l l e t k e y w o r d s ：o u t l 衙d e t e c t i o n ，d a t as 雠锄，c o n c 印t - 越r ，p 2 p b o t s 仃a 衔c i i i 目录 目录 第一章绪论1 1 1 研究背景及意义1 1 2 研究现状：2 1 3 论文研究内容3 1 4 论文章节安排4 第二章相关理论与技术5 2 1 异常检测相关技术5 2 1 1 异常及异常检测技术的相关概念5 2 1 2 异常检测技术的分类7 2 2 数据流异常检测1 2 2 2 1 基于网格的数据流异常检测算法1 3 2 2 2 基于密度的数据流异常检测1 4 2 2 3 基于距离的数据流异常检测1 5 2 3 本章小结1 6 第三章响应式数据流异常检测方法1 7 3 1 检测方法设计原理及流程1 7 3 2 实验数据集2 0 3 3 数据聚类2 l 3 3 1 基于聚类的异常2 1 3 3 2 实验及结果分析。2 4 3 4 容忍概念漂移的分类器训练2 8 3 4 1 数据流概念漂移容忍2 8 3 4 2 神经网络分类器3 1 3 4 3 实验及结果分析3 3 3 5 概念漂移的检测：3 8 3 5 1 基于数据块分布特征的概念漂移检测3 8 3 5 2 实验及结果分析4 0 3 6 整体流程实验及结果分析4 4 i v ，l 目录 3 7 本章小结4 5 第四章数据流异常检测在僵尸网络检测中的应用4 6 4 1 僵尸网络背景介绍4 6 4 2p 2 p 僵尸网络检测技术4 8 4 3 基于数据流异常检测的僵尸通信捕获4 9 4 3 1p 2 p 僵尸病毒传播状态模型4 9 4 3 2p 2 p 僵尸病毒通信的捕获5 0 4 3 3 实验及结果分析5 2 4 4 本章小结5 3 第五章总结与展望5 4 5 1 总结5 4 5 2 展望5 5 致谢：5 7 参考文献5 8 攻硕士期间取得的研究成果。6 2 v i 第一章绪论 1 1 研究背景及意义 第一章绪论 异常数据通常被认为是数据集合中的一小部分数据，这一小部分数据与集合 中的大部分数据都有着本质的不刚1 1 ，不禁让人怀疑这些数据是由于完全不同的机 制而产生的，而怎样从数据集中发现这一小部分异常数据则是异常检测技术的主 要研究内容。早在1 9 世纪，研究者们就在统计领域展开了关于异常检测的研究【2 】， 迄今为止，研究者们在更多的领域中提出了新的异常检测方法，这些异常检测方 法相继引入了统计学、机器学习、信息理论和数据挖掘等理论和技术来解决不同 应用领域中的一些特定的问题。 近年来，随着计算机和互联网等技术的发展和应用领域中实际需求的驱动， 基于数据流的异常检测技术越来越受到学术界和工业界的重视。做为一种基础且 重要的数据挖掘手段，基于数据流的异常检测逐渐成为了一个研究的热点。在传 统数据集合中，异常分析检测技术已经在图像处理、模式识别、市场调研等领域 取得了实际的应用，而在数据流环境中，异常检测同样是一种重要的并具有强大 信息挖掘功能的数据分析技术。例如在网络安全领域，分析监控网络通信的异常 行为可以发现入侵、病毒等众多的互联网恶意行为和安全威胁。这使得我们可以 及时采取应对措施，保障互联网服务的效率和计算机用户的隐私和数据安全。 基于数据流的异常检测技术作为近几年来的研究热点，具有非常广泛的应用 前景，包括针对信用卡，保险等领域的信用欺诈检测，工业系统故障检测，航空 数据异常检测等。特别是在网络安全领域，随着近年来个人计算机和网络的普及， 日常生活信息化程度日益增加，人们对网络依赖性日益增强，恶意的网络行为给 互联网服务效率和个人电脑的安全带来极大的威胁。因此，计算机网络安全问题 引起了人们的极大关注，而僵尸网络( b o 仃1 e t ) 作为一种新的互联网安全威胁，已成 为安全领域研究者所共同关注的热点。基于承c 协议的第一代僵尸网络命令与控 制机制具有集中的控制点，使得这种基于客户端朋艮务器架构的僵尸网络容易被跟 踪、检测和反制，研究者们也针对m c 僵尸( i r cb o t ) 提出了比较有效的检测方法。 但随着技术的发展，p 2 p 技术被用以僵尸网络而发展成为了第二代p 2 p 僵尸网络。 基于p 2 p 技术的僵尸网络在健壮性、安全性和隐蔽性等方面都有很大的提高，这 给僵尸网络的发现和监测带来了挑战。如何将数据流异常检测技术应用到这一研 l l 电子科技大学硕士学位论文 究领域，构建对p 2 p 僵尸和p 2 p 僵尸网络的有效检测方法将是现在和未来很长一 段时间的研究重点。 本文旨在通过对异常检测技术研究，找到一种适合数据流应用场景的异常检 测方法，并尝试将其应用于p 2 p 僵尸病毒的检测当中，使得通过监控网络数据流， 能够有效的发现p 2 p 僵尸病毒在传播过程当中的特殊行为，并通过捕获这些行为 来辅助实现僵尸主机的发现，为进一步捕获整个僵尸网络提供依据。 1 2 研究现状 异常检测的研究自兴起以来，国际上一些著名的研究机构和学术单位都在这 个领域开展了大量的研究，提出了一系列新的异常检测方法，例如i b ma h n a d e n 、 g t e 和u cb e 出e l e y 等。除了对算法的理论研究，国外很多计算机公司也非常重 视异常检测技术的开发应用，i b m 和微软都成立了相应的研究中心进行这方面的 工作。由美国明尼苏达大学p i n 心1 i i l a r 教授和j a i d e 印s r i v a s t a v a 教授等开发的著 名入侵检测系统m i n d s 吲( m i n i l e s o t ai n l 肌s i o nd e t e c t i o ns y s t e m ) ，更是充分体现了 异常检测技术的有效性。与国外相比，国内开展关于异常检测的研究起步比较晚， 研究人员主要集中在高校，大多数研究项目是由政府资助进行的。 在算法理论研究方面，基于统计模型的异常检测方法是最早被研究者关注的 异常检测技术，该方法的主要思想通常是假设正常数据对象满足一种特定的分布 或者概率模型，如果存在数据对象不符合该分布或者模型则被认为是异常数据， 有许多异常检测方法均源自该思想【5 ，6 7 】。基于统计模型的异常检测方法要求事先知 道关于数据集合参数的知识，比如数据的分布等，但是在很多情况下数据的分布 是很难被准确描述或者估计的。为了改进基于统计模型异常检测方法的缺点，研 究人员引入了基于距离的异常检测方法 8 ，9 】，这类方法降低了基于统计模型方法对 数据分布知识的依赖性，并且对相对较高维的数据集有着较好的检测效果。但是 该方法也存在两个主要问题：一是基于距离的参数选择，二则是仅能够发现全局 的异常而会丢失局部的异常信息。因此研究者们提出了基于局部密度的异常检测 方法，其基本思想来自于基于密度的聚类方法，通过数据集中各个数据对象邻居 的密度大小来确定该数据对象的异常度大小【l o 】，然后根据异常度的大小确定t o p k 个异常数据。该类方法能够发现局部的异常数据对象，弥补了基于距离的异常检 测方法的缺点，但是其时间复杂度较大， 随着异常检测技术研究的不断发展， 2 对大规模数据的处理存在效率问题。 数据流作为待分析数据对象逐渐成为了 第一章绪论 研究者们关注的新热点。目前国际上对数据流研究较为深入机构有s t a i l f 0 r d 大学组 建的基于关系的数据流处理系统s n 也a m 【l l 】研究小组；b r o w n 大学构建的数据流 系统a l d r a 【1 2 】研究小组；另外还有c o m e l l 大学的c o u g p d 1 3 】项目组和w i s c o n s i n 大学的n i a g a r a c q 【1 4 】项目组等。而国内针对数据流处理的研究主要集中在中国科学 院计算所，如“冰河2 0 0 4 【1 5 】项目组。与传统的异常检测分析对象不同，数据流 作为实时的、连续的、有序的动态数据集合，一般来说具有快速性、连续性、多 变性和无限性等特点，这些特点使得传统处理静态数据集合的异常检测技术和算 法面临了极大地挑战。其中数据分布的变化的问题就由w _ i i d 】n e r 等人于1 9 9 6 年提 出【3 】，并定义为概念漂移，c h e nz h i y u a l l 等人也指出概念漂移问题是数据流分析中 的一个关键问题【1 6 】。许多的研究者致力于有关数据流挖掘的研究【1 7 ，1 8 1 。2 0 0 1 年， s 讹“1 9 】等人提出了一个集成分类器算法s e a ，并同时将它应用到了数据流的概念 漂移检测中；2 0 0 3 年，hw 抽g 【2 0 】等人对集成分类器中权值的变化和分类器选择的 问题进行了讨论；2 0 0 4 年，r u s l l i n g 【2 l 】等人集中讨论了一种基于聚类算法的集成 分类器裁剪的问题；a l b e r tb i f e t 【2 2 】于2 0 0 7 年设计了一种基于滑动窗口的概念漂移 检测算法，该方法依据窗口中所测数据变化速率进行在线重计算来实现；2 0 0 8 年， 孙岳 2 3 】等人提出了一种数据流挖掘算法m i d 4 ，利用多分类器综合技术和较少训练 样本实现数据流中的概念漂移检测，但由于依赖有序数据块建立分类器，因此其 性能受到数据块规模的约束。 综上所述，众多的研究者在异常检测技术及数据流概念漂移挖掘上都提出了 不少研究成果，但是如何将数据流上的概念漂移处理与异常数据对象捕获结合在 一起，实现有效的数据流异常检测方法，还少有研究者进行较为系统的研究。本 文就如何在实现数据流异常检测的同时解决概念漂移为检测结果带来影响，进行 了研究和初步的应用尝试。 1 3 论文研究内容 本论文的研究课题来自国家自然科学基金项目“基于隐私保护的分布式数据流 异常检测模型融合研究”和2 4 2 信息安全计划项目“木木木木妒。文中将有监督和无监 督算法相结合应用于数据流异常检测，提出了一种基于聚类和分类器训练相结合 的数据流异常检测方法。在该异常检测方法的基础上，针对数据流作为动态数据 集，其数据对象的特征分布可能发生变化的特性( 概念漂移) ，引入了容忍概念漂移 的分类器训练策略，并且提出了一种概念漂移的检测方法来触发异常检测模型的 3 电子科技大学硕士学位论文 更新。最终通过大量实验证明，该数据流异常检测方法在保证其有效性的同时， 对数据流的概念漂移具有更好的健壮性。本文还尝试将该方法应用于p 2 p 僵尸病 毒通信的检测上，通过对网络数据流中异常数据的发现，能够实现p 2 p 僵尸病毒 之间通信数据的检测。希望本文能够在提出一种有效的数据流异常检测方法的基 础上，为p 2 p 僵尸网络检测方面的研究工作提供一点思路。 本文主要的研究内容如下： ( 1 ) 将有监督和无监督算法相结合，提出一中有效的异常检测方法； ( 2 ) 针对数据流作为待分析数据集的特殊性，对异常检测方法进行改进从而实现一 种响应式的数据流异常检测方法； ( 3 ) 采用权威数据集和人工数据集对提出的数据流异常检测方法进行实验并对结 果进行分析； ( 4 ) 将文中提出的数据流的异常检测方法应用于p 2 p 僵尸病毒通信的检测，并实验 检测的效果。 本文的主要贡献在于： ( 1 ) 将基于聚类的异常检测方法与分类器训练相结合，提出了一种基于数据流的异 常检测方法； ( 2 ) 针对数据流中存在的概念漂移，提出了_ 种容忍概念漂移的分类器训练方法； ( 3 ) 针对数据流中存在的概念漂移提出了一种有效的概念漂移检测方法； ( 4 ) 将提出的响应式数据流异常检测方法应用于p 2 p 僵尸网络发现中，实现僵尸病 毒之间通信的检测。 1 。4 论文章节安排 本文总共分为五章，每一章的主要内容如下： 第二章，将对相关的理论和现有的技术做一个简要介绍，主要集中在已有的异 常检测技术及数据流异常检测技术； 第三章，对本文提出的响应式数据流异常检测方法总体流程进行一个简述，详 细描述该方法的各个部分并采用权威数据集进行实验，分析实验结果。 第四章，通过对典型p 2 p 僵尸病毒进行分析，并根据其传播特点，应用本文提 出的数据流异常检测技术，实现僵尸病毒传播过程中的异常行为检测。 第五章，总结及展望。 4 第二章相关理论与技术 第二章相关理论与技术 本文主要从异常检测技术研究入手，将数据流作为分析对象，提出了一种基 于数据流的异常检测方法，因此，在本章节当中，将就论文涉及到得相关理论与 相关的技术做一个简要介绍。本章中各个小节的安排如下：2 1 节介绍了一些基本 概念和异常检测技术的分类，并对各个类别中的典型异常检测技术做了简单介绍， 2 2 节介绍了典型的基于数据流的异常检测方法，2 3 节为本章总结。 2 1 异常检测相关技术 2 1 1 异常及异常检测技术的相关概念 异常通常指代的是一种模式，这种模式的数据并不满足我们事先定义的正常 数据的特征或者行为，而在整个数据集中找出符合这种模式的数据就称之为异常 检测。如图2 1 所示，在一个二维的数据集当中，正常数据分为两个区域m 和2 ， 大部分的数据都属于这两个区域。而另外一些距离m 和2 较远的零散数据点，比 如图中的q 和q ，以及距离较远的点集合q 中的点都可以被认为是异常数据点。 图2 1 二维数据集中的异常数据 简单的来说异常检测就是找出不符合正常数据模式的那些数据。那么最为直 接的方式就是定义什么是正常数据的特征或者行为，如果未知的数据对象不在这 些已定义的特征或行为的范围之内则被认为是异常数据。但是，某些因素使得异 5 电子科技大学硕士学位论文 常检测面临着挑战，比如： 给出一个完备的能够概括所有正常数据的定义是非常困难的。数据集中往往存 在着某些边缘领域，在这些领域中异常和正常数据的界限并不是非常的明显。 异常检测中需要用到的有效数据。异常检测需要大量的有标签的数据用于训 练，从而建立起正常对象的模型来达到有效检测异常的目的，而这些数据的搜 集往往也是个难题。 数据分布的变化。在某些情况下( 比如基于数据流的异常检测) ，需要处理的 数据对象( 正常或异常数据对象的特征或者行为) 是随着时间的变化而不断变 化的。在某一时刻训练得到的数据模型，可能很难准确的描述未来可能出现的 数据对象。 事实上，针对不同的应用领域，数据的性质、数据是否存在标签、异常数据 的类型等都不尽相同，因此需要采取不同的策略来实现异常的检测。迄今为止， 研究人员已经将统计学，机器学习，数据挖掘，信息理论等领域的技术引入异常 检测研究当中来解决一些特定应用领域的问题( 图2 2 ) 。接下来就会分类对现有 的异常检测技术做一个简单的介绍。 研究领域： 机器学习 统计学 数据挖掘 信息理论 儿 异常检测技术 么 数据特征异常类型 标签 数据输出 需要考虑的问题 彳f 应用领域： 入侵检测 信用欺诈检测 故障检测 医疗信息 图2 2 异常检测相关技术及应用领域 6 第二章相关理论与技术 2 1 。2 异常检测技术的分类 异常检测技术可以根据其实现所采用技术的不同来进行分类。这是一种较为 直观的分类方式，主要可以分为基于统计方法的异常检测技术，基于分类的异常 检测技术，基于最近邻居的异常检测技术和基于聚类的异常检测技术。 ( 一) 基于统计方法的异常检测技术 基于统计方法的异常检测技术通常基于一个前提条件： 前提条件：正常数据对象往往都以很高的概率出现在一个随机模型当中而异 常的数据黜以很低的概率符合这个随机模型。 采用统计方法的异常检测技术首先需要建立一个统计模型( 通常代表正常的 行为特征) ，然后通过统计模型来确定未知数据对象是正常数据还是异常数据。如 果未知的数据对象以很低的概率符合事先通过学习建立的模型，则被认为是异常 数据。在训练统计模型的时候，带参数或者无参数两种统计建模方法都是可行的。 带参数的训练方法需要假设数据集的分布规律( 如高斯分布) ，并且由已有的训练 数据集来估计参数的值【2 4 】；而无参数建模的方式则不需要假设数据的分布规律【2 5 】， 统计模型的结构完全取决于训练集中的数据。 基于统计的异常检测技术的优点在于：如果建立的统计模型与真实数据的实 际分布相符合，则异常检测的准确率是很高的，并且在估计数据概率分布的时候 能够以无监督的方式进行，而不需要有准确标签的数据集用于训练。但是该类异 常检测方法的缺点也很明显：必须假设数据集满足一种特定的分布，而在实际的 应用当中，特别是以高维数据或者数据流为处理对象时，该假设往往不能成立。 ( 二) 基于分类的异常检测技术 基于分类的异常检测技术通常需要训练数据集( 代类别标签的数据对象) 训 练得到分类器。该类的异常检测技术通常都分为两个相似的步骤，首先是通过学 习有类别标签的训练数据集得到分类器，然后通过分类器将未知的数据进行分类。 基于分类的异常检测技术必须满足如下的前提条件： 前提条件：能够有效区分正常数据对象和异常数据对象的分类器可以由a 知 的数据集调练得飘。 许多的分类算法都被应用到异常检测技术的研究领域当中，比如神经网络 2 6 】【2 7 1 、贝叶斯网络【2 8 】、支持向量机2 9 1 等等。根据用于训练的数据标签的不同，可 以将分类异常检测技术分为多类别异常检测和单类别异常检测两种。 ( 1 ) 多类别异常检测技术用于训练的数据集往往存在多个标签将正常数据分为了 7 电子科技大学硕士学位论文 多个类别。该类方法通过训练得到的多个分类器可将数据分成多个正常类别或 者不属于任何类别。如图2 3 中( a ) 所示，如果未知数据对象通过分类器后不属 于任何类别，则被认为是异常，反之为正常。 ( 2 ) 单类别异常检测技术中用于训练分类器的数据集往往只有一个类别标签。该类 方法通过学习得到的分类器将确定正常数据类别的一个边界，如果当未知数据 通过分类器后没有落在该边界范围之内，则被认为是异常数据，反之为正常， 如图2 3 中f b ) 所示。 ( a ) 多类别异常检测( b ) 单一类别异常检测 图2 3 基于分类的异常检测技术 基于分类的异常检测技术的时间复杂度往往取决于分类算法的时间复杂度， 一旦分类器学习完成，对未知数据的分类则是非常迅速的。但是基于分类的异常 检测技术必须要求有训练数据集来完成分类器的训练，而在某些应用当中，有类 别标签的数据集是很难获得的。 ( 三) 基于最近邻居的异常检测技术 分析最近邻居的方法也被应用到了异常检测技术的研究当中。采用这种技术 需要基于如下一个前提条件： 前提条件：正常数据对象的邻居密度较大丽异常数据的邻居密度购小得多( 甚 至司以看作是孤立点) o 基于最近邻的异常检测需要计算数据集中所有数据对象之间的相似度( 距 离) ，欧式距离是比较流行的计算方法。基于最近邻居的异常检测方法可以被大致 的分为两类：( a ) 根据每个数据对象与其k 个邻居的距离来确定异常的数据对象， ( b ) 根据每个数据对象邻居的密度大小来确定每个数据对象的异常度。而通过估计 邻居密度来确定异常数据对象的方法其应用非常广泛。这里简要介绍一种典型的 基于最近邻居的异常检测算法l o f ( l 0 c a lo u t l i c rf a c t o 订。 b r e u n i g 【3 0 】等人引入了一种“局部异常 的概念，提出了基于局部密度的异常 第二章相关理论与技术 检测算法l o f 。该方法在传统的基于最近邻的方法上做出了改进，在考虑每个数 据对象是否异常时，只考虑和它邻近的“局部邻居”的密度，算法对密度分布不 均匀的数据集有很好的检测效果。该算法首先给出了几个重要的定义【3 0 】： ( 1 ) 数据对象p 的k 距离：对于任意的正整数k ，数据点p 的k 距离k - d i s t a n c e 0 ) 定义为一个距离值d i s t a n c e 0 ，o ) ，其中。属于整个数据集d ，并且满足： ( i ) 至少有k 个数据点d d 满足d ( p ，d ) d ( p ，d ) ； ( i i ) 至多有k - 1 个数据点d d 满足d ( p ，d 。) 6 。 i ( ic 1 l + l c 2 i + l c ：1 ) l d l 木口 ( 2 3 ) ll c 6 i l c 6 + 。l ( 2 4 ) 从该定义可以看出，它是完全符合该类异常检测算法的前提假设的。公式( 2 3 ) 说明大多数的数据对象都应该属于整成数据对象，异常的数据对象只占小部分( 阈 值口通常设置大于o 5 ) 。如口值设定为o 9 则表示数据集中9 0 的数据对象都属于 大类，即为正常的数据对象。公式( 2 4 ) 则反映出了大类和小类所包含的数据对象 个数存在着明显的差异。比如我们取= 5 ，则任何大类所包含数据对象的个数都 至少是任意小类所包含的数据对象个数的5 倍。 电子科技大学硕士学位论文 根据上述定义的大类( l c ) 小类( s c ) 之后，就可以计算出数据集中每个数 据的异常度。如下计算公式： il q 卜m 觑( 如纪咒( f ，c ，) ) 据g ，g s ca n dc ，三cf o r j = 1 幻6 c b 己d 联力2 1i l 木( 咖纪刀c e q ) ) t 兰ea 1 1 ：q ：l c ( 2 。5 ) 从上述计算公式( 2 5 ) 可以看出每个数据对象的c b l o f 值都取决于所属类的 大小以及距离其最近的大类的距离( 如果该数据对象属于小类) 或者是类中心的 距离( 如果该数据对象属于大类) 。这样集合中每个数据对象的异常值就能够很好 的反映局部数据行为。 从上述介绍的三类基于聚类的异常检测方法可以看出，许多基于聚类的异常 检测技术也需要计算数据对象之间的距离，在这一点上与基于最近邻居的异常检 测技术很类似。但是基于聚类的异常检测算法关注的是对象与各个类之间的距离 关系，而基于最近邻居的异常检测算法是关注每个对象和其邻居之间的距离关系。 综上所述，基于聚类的异常检测技术采用的是一种无监督的算法模式，不需 要带标签的训练数据集来进行学习；而且基于聚类的异常检测技术对不同的数据 类型有着很好的健壮性，只需要通过改变简单改变聚类算法的输入数据就可以实 现。但是，采用聚类的异常检测算法也存在缺陷，多数异常的数据对象只是聚类 算法的副产品，这并不是最优化的异常检测方法；某些聚类算法必须要求数据对 象属于一个类别，这样就可能导致异常数据对象被归到一个大类，使得异常检测 的准确率下降；或者当异常数据对象被聚成一个明显的大类时，算法甚至可能完 全失效( 无法检测出异常) 。 2 2 数据流异常检测 随着硬件设备和通信技术的不断发展，数据的采集变得越来越趋向于自动化。 各个领域每天都在源源不断的产生大量数据，比如我们每天接触到的计算机互联 网数据。这些数据与传统的数据集合不太一样，它们不但数量庞大，无穷无尽， 而且数据和数据之间是存在时序关系的，并且会随着时间的推移而不断变化。这 样的数据形态我们就称之为数据流 由于数据流所具有的特性，传统的分析方法( 比如o “廿和传统数据挖掘算 法) 用于数据流的分析是不太现实的，其主要原因如下： ( 1 ) 海量数据：数据流作为数据集，其数据量是非常庞大的，不可能将其存储在内 1 2 第二章相关理论与技术 存或者硬盘上进行分析，因此我们只能通过能保存的部分数据信息进行分析， 做出决策； ( 2 ) 一次性扫描：数据流是具有时序性的，我们只能对数据流中的元素按照顺序访 问一次( 不存储到本地) ，随机访问是不现实的； ( 3 ) 概念漂移：数据流是随着时间的变化而快速变化的，过去某个时刻对于部分数 据分析得到的决策可能在这一时刻已经不正确了。 。 近年来，很多基于数据流的异常检测方法方法被提出来以解决上述的某些挑 战和难题，大多数方法都是将传统异常检测技术针对数据流的特性进行改进来实 现数据流异常检测的，这里就对一些典型的数据流异常检测方法做一个简要介绍。 2 2 1 基于网格的数据流异常检测算法 c u ih o n g 如n 【3 6 1 在基于p a r k 和l e e 【3 8 】提出的一种基于网格聚类方法的基础上， 提出了一种实时的数据流异常检测方法。基于网格聚类的数据流挖掘方法是把整 个数据空间( 数据的每个维度) 分割成为相互独立，大小一致的很多网格( c e l l ) 。 人为地设定一个支持度，当网格中所包含的数据元素个数( 支持度) 超过或者等 于了事先设定的支持度大小时，就从所有的维度中选出一维，并按照这一维度将 网格动态的分为两个完全独立的子网格。当子网格的支持度也达到或超过阈值时， 同样的分割操作也会在子网格上进行。文章【3 8 】中给出了三种网格的分割方法：一 分割法，主要基于数据对象每一维度的特征均值；万分割法，主要基于数据对象 每一维度的标准差；混合分割法，同时考虑均值和标准差的分割方法。对网格进 行分割时，采用一个两层的结构保存网格中的数据信息。比如将一个初始的网格g 分割成为g ，和9 2 ，则g 。和g ：就是g 的孩子网格。如果g 。需要进一步分割为岛和 的时候，晶和氍会代替昌成为g 的孩子结点。如图2 5 所示，假设每个网格的支 持度阈值设定为1 0 。 圆圆 图2 5 网格聚类中分割网格的例子 最终，每一个堆积密集数据对象的网格都会递归的被分割，最终变成一个个 小的且相互独立的网格，称为单位网格。而一组由相邻单位网格组成的网格集合 则最终被归为一个类( 如图2 6 所示) 。 1 3 电子科技大学硕士学位论文 图2 - 6 二维空间网格聚类示例 文掣3 6 】将该聚类方法应用到了数据流异常检测当中。网格聚类不需要计算数 据对象之间的距离，只需要按照事先确定的网格大小，直接把数据放入相应的网 格，因此可以实现实时的增量聚类。每次聚类完毕之后只需要保存每个类的特征