（计算机软件与理论专业论文）面向数据流的局部异常孤立点动态挖掘算法研究及应用.pdf

1 l l a b s t r a c t m o s to ft h ed a t am i n i n ga l g o r i t h m s m a i nr e s e a r c hq u e s t i o n sa r et of i n dt h e ”l a r g ep a t t e r n s ”o u t l i e rd e t e c t i o na l g o r i t h m sa r e u s e dt of i n d ”s m a l lp a t t e r n s ”i nt h e d a t as e t t h eo u t l i e ri sa no b s e r v a t i o nt h a td e v i a t e ss om u c hf r o mo t h e ro b s e r v a t i o n s a st oa r o u s es u s p i c i o nt h a ti tw a sg e n e r a t e db yad i f f e r e n tm e c h a n i s m t h et a s ko f o u t l i e rd e t e c t i o nc o u l db ed e s c r i b e da sf o l l o w s ：g i v e nad a t as e tw h i c hc o n t a i n sn d a t ap o i n t s ，a n dt h ee x p e c t e dn u m b e ro fo u t l i e r s ，n ，f i n d i n gt h et o p - nd a t ap o i n t s w h i c ha r em o s ti n c o n s i s t e n t ，a n o m a l o u so rs i g n i f i c a n t l yd i s s i m i l a rw i t ht h er e s tp o i n t s o u t l i e rd e t e c t i o ni sa ni m p o r t a n tb r a n c ho fd a t am i n i n ga n dh a sb e e na p p l i e dt oa l a r g en u m b e ro ff i e l d s e s p e c i a l l yi nt h en e t w o r ki n t r u s i o nd e t e c t i o n ，t h ei n t r u s i o n b e h a v i o r sa r ed i f f e r e n tt ot h en o r m a lb e h a v i o r s ，s ow em a k er e s e a r c ho ft h eo u t l i e r d e t e c t i o na l g o r i t h ma n da p p l yi tt ot h en e t w o r ki n t r u s i o nd e t e c t i o n t h el o fa l g o r i t h mc o u l df i n dt h eo u t l i e r sb a s e do nd i f f e r e n td e n s i t y a s s i g n i n gt o e a c hd a t ar e c o r dad e g r e eo fb e i n go u t l i e r , i ti sm o r ec l o s et ot h ed e f i n i t i o no fo u t l i e r s r e c e n t l yan e wc l a s so fd a t a - i n t e n s i v ea p p l i c a t i o n sc a l l e dd a t as t r e a m sh a sb e c o m e w i d e l yr e c o g n i z e di nw h i c ht h er e l a t i o no fd a t ai sm o d e l e dn o ta sp e r s i s t e n ta n dt h e d a t ae l e m e n t sa r r i v ec o n t i n u o u s l ya n dr a p i d l yi nl a r g e s c a l e t h er e c o r d so fn e t w o r k c o n n e c t i o na r r i v i n gc o n t i n u o u s l yb e l o n gt os t r e a m i n gd a t a b u tt h et i m ec o m p l e x i t yo f t h eo r i g i n a ls t a t i cl o fa l g o r i t h mi sh i g ha n di tc o u l dn o ta d a p tt ot h ec h a n g e so fd a t a s t r e a m s ，t h eo r i g i n a ll o fa l g o r i t h mi sn o ts u i t a b l ef o rr e a l t i m ed a t as t r e a mm i n i n g w eh a v er e s e a r c h e do nt h ew a yt oi d e n t i f ya n dd e t e c ta n o m a l i e si nt h ed a t as t r e a m e n v i r o n m e n ta c c u r a t e l ya n dad y n a m i c a ll o c a lo u t l i e rd e t e c t i o na l g o r i t h m ：n i n c l o f i sp r o p o s e dw h i c hc o u l da d j u s tt h en - t h r e s h o l da d a p t i v e l y n - i n c l o fi sb a s e do nt h e l o c a lo u t l i e rd e t e c t i o na l g o r i t h m d u et ot h ep r o b l e mt h a tt h en u m b e ro ft h eo u t l i e r si n d a t as t r e a m si su n e v e n ，t h ea d j u s t m e n tf u n c t i o no fn - t h r e s h o l di sp r o p o s e d w eh a v e a l s oa n a l y z e dt h es i t u a t i o nw h e nt h ed a t ap o i n ti si n s e r t e d ，d e l e t e da n dm o d i f i e d t h e d e s c r i p t i o no f t h en - i n c l o fa l g o r i t h mi sg i v e na n dt h ec o m p l e x i t yo ft h ea l g o r i t h mi s a n a l y z e dt o o t h ea n o m a l yd e t e c t i o ns y s t e mo u t l i e r d i d sh a sb e e nd e s i g n e dw h i c hu s e st h e n - i n c l o f a l g o r i t h ma st h ed e t e c t i o ne n g i n eb a s e d o nb o t hh o s ta n dn e t w o r k p r o p e r t i e s t h ee x p e r i m e n to fo u t l i e rd e t e c t i o np e r f o r m e do nt h ek d dc u p 9 9d a t a s t r e a mp r o v e st h ev a l i d i t yo ft h en - i n c l o fa l g o r i t h m ：i tc o u l dn o to n l yi n c r e a s et h e d e t e c t i o nr a t es i g n i f i c a n t l yb u ta l s or e d u c e dt h ef a l s ea l a r mr a t ea tt h es a m et i m e c o m p a r e dt ot h eo r i g i n a la l g o r i t h m t h ef e a s i b i l i t yo ft h eo u t l i e r d i d s ：e f f e c t i v e n e s s ， a d a p t a b i l i t ya n dr e a l t i m ep e r f o r m a n c ei sa l s op r o v e di nt h ee x p e r i m e n t k e yw o r d s ：o u t l i e r ；n - t h r e s h o l d ；d a t as t r e a m s ；d a t am i n i n g ；i d s ， l-：劓，l11 目录 第一章引言一1 1 1 选题的背景和意义”l 1 2 国内外相关研究进展2 1 3 研究的主要内容和创新点一3 第二章基于数据挖掘的入侵检测系统概述5 2 1 引一言一5 2 2 入侵检测的分类5 2 3 数据挖掘的原理和过程6 2 4 数据挖掘在网络入侵检测中的应用6 第三章孤立点发现算法分析和比较”9 3 1 基于统计的方法”9 3 2 基于聚类的方法9 3 3 基于距离的孤立点检测算法9 3 4 基于密度的孤立点检测算法1 0 3 5 基于偏离的孤立点检测算法”：1 2 3 6 高维孤立点检测算法1 2 3 7 本章小结13 第四章面向数据流的局部异常孤立点动态挖掘算法研究1 5 4 1 引。言15 4 2 面向数据流的数据挖掘方法概述1 5 4 3 局部异常孤立点动态增量算法”1 6 ： ： ： 4 3 1 数据点的插入i7 4 3 2 数据点的删除”19 4 4 面向数据流的n 阈值自动调整的孤立点动念挖掘算法2 0 4 4 1n 阈值自动调整函数2 0 4 4 2n i n c l o f 算法实现_ 2 2 4 4 3n - i n c l o f 算法时间复杂度分析2 4 4 5 本章小结2 5 第五章基于n - i n c l o f 算法的网络入侵实时异常检测系统2 6 5 1o u t l i e r d i d s 系统结构2 6 5 2o u tlie r d i d s 系统详细设计2 6 5 2 1 数据采集2 6 5 2 2 数据预处理一2 7 5 2 3 实时异常检测引擎2 8 5 2 4 实验结果及分析3 2 5 3 本章小结3 5 第六章全文总结和展望 参考文献 3 7 攻读学位期间的研究成果4 0 致谢一4 1 学位论文独创性声明、学位论文知识产权权属声明4 2 第一章引言 1 1 选题的背景和意义 第一章引言 随着信息化的进程和互联网的普及，越来越多的组织成为各种网络威胁的受害 者。根据c e r t c c n l 的研究调查，近年来，网络攻击行为每年以指数级的速度增长。 因此，使政治、军事和经济等关键领域的信息系统能够发现和抵御这些攻击行为变 得越来越重要。 网络入侵手段正在呈现多元化、复杂化、智能化、且行为特征不断变化和更新。 单纯依赖传统的静态防御技术已难以胜任网络安全的需求。网络入侵检测( n e t w o r k i n t r u s i o nd e t e c t i o n ) 是近年来发展起来的继“防火墙”、“访问控制”、“数据加密”等 传统静态安全保护措施一种主动防护机制，通过从系统内部和网络中收集、分析是 否有针对计算机客户端和网络各层资源的恶意行为问题，并对这些非法行为进行阻 止或提醒用户进行处理，是一种集检测、记录、报警、响应于一体的动态安全技术。 和防火墙不同，网络入侵检测系统不仅能检测来自外部的入侵行为，同时也可以监 督来自内部的攻击和误操作行为。网络入侵检测系统作为网络防火墙的有力补充， 已经成为网络管理的关键组成部分。 目前应用最广的入侵检测系统是基于特征签名的方法，这种方法只能检测特征 签名库中已知的攻击，因此，特征签名库必须对新的入侵行为的特征进行手工更新。 这些局限性使基于数据挖掘的入侵检测系统的研究越来越受到重视。采用数据挖掘 技术的网络入侵检测系统可以充分发挥数据挖掘处理海量数据的优势，能够从数据 挖掘中发现人们未知的知识和规律，提高检测的效率和准确性。 数据挖掘中的大多数算法主要是发现“大模式，即发现数据的主要特征，然而 数据集中常常包含与一般数据存在较大偏差一些数据对象，这些数据对象被称为孤 立点。在网络活动中，正常行为远多于入侵行为，即入侵行为与正常行为是不一致 的，是一种“小模式 ，而孤立点发现算法可以挖掘这些“小模式 的异常，更符合 入侵行为的本质，因此将孤立点算法应用于网络入侵异常检测是非常有意义的。基于 数据挖掘的误用入侵检测主要通过数据挖掘分类算法对己标注好的i ) l l 练集进行学 习，因此，训练集的质量将直接影响入侵检测系统的检测效果，但在实际应用中， 要收集纯净的训练集往往不太容易，训练集的标注亦需要很大的人力和物力。由于 只能通过学习得到的规则库来识别入侵行为，误用入侵检测不能发现规则库晕没有 的新的未知的入侵行为，然而现在的入侵行为是正在以惊人的速度不断变化和更新 的。我们采用无监督的孤立点发现算法来进行网络入侵异常检测，不需要任何训练 集来学习和生成规则库，而是直接通过挖掘孤立点来发现异常，可以发现新的未知 的入侵行为。针对目前新的入侵行为正在同益增多和不断变化特征的特点，采用孤 青岛人学硕十学位论文 立点算法进行异常检测具有很重要的价值。 近年来，一种新的数据应用正受到广泛关注，在这些应用中数据不再保存持久 不变的关系，而是规模宏大，连续，快速，随时问变化的数据流。这些应用包括： 金融应用、网络监控、网络安全、通信数据管理、互联网应用、工业生产、传感器 网络等。随着数据流技术研究的发展，研究如何在数据流环境下如何能够准确识别 和发现孤立点正受到广泛的关注。因此，我们采用动态孤立点算法来识别网络连接 数据流中的入侵行为，具有很好的理论和实践意义。 1 2 国内外相关研究进展 1 9 8 0 年4 月，j a m e sp a n d e r s o n 乜在为美国空军做的一份题为“计算机安全威胁 的监察 的技术报告中提出必须建立为专职系统安全人员提供安全信息的系统审计 机制，被认为是网络入侵检测的最早论述。1 9 8 6 ，s r i 的d o r o t h ye d e n n i n g 。”深入 探讨了入侵检测技术，探索了行为分析的基本机制，首次将入侵检测的概念作为一 种计算机系统安全措施提出，并且建立了一个独立于系统、程序应用环境和系统脆 弱性的通用入侵检测模型。与传统的加密和访问控制相比i d s 是全新的计算机安全 措施。1 9 8 8 年，t e r e s al u n t 在d e n n i n g 提出的网络入侵检测模型上进一步改进，并 创建了i d e s ( i n t r u s i o nd e t e c t i o ne x p e r ts y s t e m ) h 1 ，提出了与系统无关的实时检测 思想。 1 9 9 8 年，w e n k el e e 等人瞄1 给出了将数据挖掘技术应用于入侵检测系统的综述， 并设计了使用数据挖掘技术进行入侵检测的框架哺1 ，系统的精度和可伸缩性得到了 提高，其工作主要足将关联规则挖掘和频繁情节模式挖掘应用到入侵检测方法中， 并通过规则学习器来表述入侵检测；之后，针对入侵检测数据量大以及训练集难以 获得的情况，e s k i n 等人口3 将数据挖掘中的聚类挖掘方法应用到异常入侵检测研究 中。应用于入侵检测中的数据挖掘方法主要集中在关联规则、频繁模式、分类、聚 类挖掘上，并且当前唯一的由l e e 课题组构建的入侵检测系统属于误用检测范畴。 目前关于孤立点发现算法在网络入侵异常检测中的应用研究正在被越来越多的人所 重视，美国m i n n e s o t a 大学的a l e k s a n d a rl a z a r e v i c 等人坤刚对数据挖掘技术在入侵检 测系统中的应用做了综述并将几种静态孤立点枪测算法应用于d a r p a 9 8 数据集和 真实网络环境数据的离线异常检测，经过对比分析得出局部异常孤立点l o f 算法们 性能最佳的结论。 近年来，数据流的挖掘和分析已成为国内外研究热点，特别是传感器网络技术 的快速发展，数据流挖掘和传感器数据挖掘已成为国内外各大数据挖掘相关会议的 重要主题。数据流环境下的异常检测正在开始被人们所重视，数据流异常检测的最 大挑战在于如何快速捕获数据流的实时变化并及时响应，从而得到近似的检测结果。 2 i，j11j1 j-l 1 一 第一章引言 i b m 和微软公司都成立了专门的研究中心进行数据流异常检测系统的丌发应用。 2 0 1 0 年2 月初，i b m 公司与美国空军签订了试验性合同，获准为后者建立一个能够 安全地支持国防和情报网络安全系统，目的是更好地保证军方的网络安全。i b m 方 面表示，i b m 将对数千个数据流进行实时分析，以便检测和防御恶意攻击和系统故 障。 在网络入侵检测系统研究中，国外主要有c o l u m b i a 大学的l e e 和n e wm e x i c o 大学的f o r r e s t 等研究小组，国内在这方面最近几年丌展了较多的研究，主要包括中 国科学院国家信息安全重点实验室、中国科学院高能物理研究所、清华大学、东北 大学国家软件工程研究中心等单位和机构。 随着网络技术的高速发展，入侵检测技术正在逐渐标准化，这改善了目前该技 术封闭、专用、彼此不兼容、数据无法共享、无法协同等方面的缺陷，为网络入侵 检测的解决提供了一个比较完备、安全的方案。进一步，现在多种方法和技术不断 应用于智能入侵检测技术、以提高检测的准确性1 。由于现实中产生的持续到达的 网络连接数据属于流数据，把数据流环境下的数据挖掘方法应用于实时的网络入侵 误用和异常检测正成为研究的热点。 1 3 研究的主要内容和创新点 本文以数据挖掘技术为工具，主要研究孤立点发现算法在网络入侵异常检测中 的应用。课题的研究目标是：利用动念孤立点挖掘算法自适应、高效的发现网络数 据流中的入侵行为，以此为基础构建实时网络入侵异常检测系统。研究工作主要包 括：研究分析现有孤立点发现算法，分析算法优缺点，探讨孤立点发现在入侵检测 系统中的应用；针对数据流孤立点分布不稳定的特点，在现有算法基础上提出孤立 点数目1 1 阈值自动调整的动念孤立点挖掘算法：n i n c l o f 设计了以n i n c l o f 算法 为核心检测引擎基于网络和主机混合属性的异常检测系统o u t l i e r d i d s ，该系统包括 数据采集和预处理、数据流异常检测和报警模块，实现了对入侵行为的有效、自适 应、实时的检测。论文的组织结构如一f ： 第一章，阐明了课题的研究背景及其重要意义，国内外研究动态以及本文的内 容和思路。 第二章，分别介绍了网络入侵检测和数据挖掘的基本概念、技术，以及数据挖 掘在网络入侵检测系统中的应用。 第三章，介绍了基于距离、基于密度、基于统计、基于偏离、基于聚类、以及 高维孤立点发现的主要算法，对各种方法进行了比较分析并讨论应用于入侵检测的 可行性和优缺点。 第四章，讨论了基于密度的局部异常孤立点l o f 挖掘算法的动态增量算法，并 3 青岛人学硕十学位论文 针对数据流中的孤立点的分布不稳定的特点，提出了面向数据流的根据孤立点数目 的变化而自动调整n 阈值的局部异常孤立点动态挖掘算法：n i n c l o f 。此外，通过 分析，n 阈值调整的方法同样适用于动念的基于距离的d ：算法。 第五章，设计了以n i n c l o f 为检测引擎核心算法的基于网络和主机混合属性的 无监督实时入侵异常检测系统o u t l i e r d i d s ，并在对网络连接数据流的异常检测实验 中证明了n i n c l o f 算法的有效性：和原增量算法相比不仅大幅提高了检测率还降低 了误报率；同时验证了o u t l i e r d i d s 系统的可行性，满足了网络入侵检测的有效性、 自适应性和实时性的要求。 第六章，总结全文，分析研究中存在的问题，并对今后的研究工作进行展望。 4 第二章基丁数据挖掘的入侵检测系统概述 第二章基于数据挖掘的入侵检测系统概述 2 1 引言 入侵检测系统i d s 是近年来发展起来的一种动念的龄控、预防或抵御系统入侵 行为的安全机制。主要通过监控网络，系统的状态，行为以及系统的使用情况，来 检测系统用户的越权使用以及系统外部的入侵者利用系统的安全缺陷对系统进行入 侵的企图。它是防火墙的合理补充，帮助系统对付网络攻击，扩展了系统管理员的 安全管理能力( 包括安全审计、监视、进攻识别和响应) ，提高了信息安全基础结构 的完整性。入侵检测系统被认为是防火墙之后的第二道闸门，在不影响网络性能的 情况下能对网络进行检测，从而提高对内部攻击、外部攻击和误操作的实时保护。 总的来说，i d s 的作用和功能包括：监控、分析用户和系统的活动；审计系统 的配置和弱点；评估关键系统和数据文件的完整性；识别攻击的活动模式；对异常 活动进行统计分析；对操作系统进行审计跟踪管理：识别违反政策的用户活动。 入侵检测系统存在的问题包括：精确性的缺乏；检测新攻击能力的缺乏；特征 提取能的缺乏；无法适用数据量增大的趋势；不便于分布式分析和协同工作。 数据挖掘在i d s 中的应用减少了手工分析和编码入侵模式的需要；提高了检测 的精确性；适应数据量增大的趋势；便于分布式分析和协同工作。 2 2 入侵检测系统的分类 i d s 根据数据来源的不同可以分为：基于主机的h i d s ( h o s t b a s e di d s ) ，基于 网络的n i d s ( n e t w o r k b a s e di d s ) 以及基于主机和网络混合型d i d s 。基于主机的 h i d s 通过分析该主机的审计记录和系统同志中的数据、文件属性、进出主机的网络 数据流等其他辅助信息来发现入侵行为；基于网络的n i d s 捕获整个共享网段的原 始网络数据包，通过实施监视和分析这些原始数据包来发现异常，检测网络上发生 的入侵行为。网络数据包狭耿的方式包括：一种是在以太网上进行监听来获耿数据， 将网卡设置为混杂模式。另一种是连接到路由器或交换机的监听端口或者镜像端口 来获取数据；基于主机的入侵检测h i d s 能够对主机上的用户或进程进行细粒度的 检测，能够很好的保护主机的安全。基于网络的入侵检测n i d s 则能够对网络的整 体念势做出反应。这两种优点都是用户所需要的，因此计算机安全界对两者的融合 进行了大量的研究，并称这种融合系统为混合式入侵检测系统d i d s 。本质上都是由 多个检测模块执行分布式协同检测，一个管理中心进集中式分析管理，这也是目f j 主流入侵检测系统的基本实现思想。将基于主机的入侵检测技术和基于网络的入侵 检测技术进行结合是入侵检测系统发展的一个重要方向。 i d s 根据检测的机制不同可分为两种检测模型：误用检测模型和异常检测模型。 5 青岛人学硕十学位论文 其中，误用检测首先对入侵行为进行特征化描述，然后通过搜索和所存储的已知入 侵情况匹配的程序或用户行为模式来区分入侵行为，这些所存储的识别标记通常由 专家提供，其优点是可以有针对性的建立高效的入侵检测系统，其缺点是无法识别 新的未知的入侵行为；异常入侵检测技术将入侵活动作为异常活动的子集，通过构 造j 下常网络行为模型( 特征) 来区分异常行为，该技术的优点是不需要事先已知的 漏洞和攻击方法的知识，具有较强的适应性，由于异常检测可以发现新的未知的入 侵行为，现在正成为网络入侵检测研究的热点。异常检测具有高误报率的缺点，这 主要是因为有些不常见的系统行为比如系统故障( 合法的) 也被认为是异常。 i d s 根据系统结构可划分为集中式i d s 和分布式i d s 。集中式i d s 是由一台入 侵检测服务器对分散的采集模块发送来的信息进行集中分析和处理。集中式i d s 比 较适合中小型的网络，随着网络规模的扩大，服务器和采集模块之间的数据传输量 会随之增加，将导致网络性能的下降。相对于集中式i d s ，分布式i d s 各个数据收 集和分析模块分布在网络中的不同节点上，系统的可扩展性和安全性得到提高。 2 3 数据挖掘的原理和过程 数据挖掘( d a t am i n i n g ，d m ) ，也称数据库中的知识发现( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ，k d d ) ，就是从大量的、不完全的、有噪声的、随机的数据中，提取隐 含在其中的、人们事先不知道的、但又是潜在的有用的信息和知识的非平凡过程引。 数据挖掘的产生和发展一直是由分析和理解数据的实际需求推动的。数据挖掘从工 业、农业、医疗卫生、和商业的需求中获得动力，从数据库、人工智能、数理统计、 机器学习、可视化、并行计算等领域的长期研究和发展中汲取营养n 3 | 。 数据挖掘的过程可卡h 略分为：问题定义、数据准备和预处理、数据挖掘，以及 结果的解释和评估。 ( 1 ) 问题定义是指数据挖掘者要熟悉领域背景知识，清楚用户要求，确定挖掘 目标。 ( 2 ) 数据准备和预处理包括：选取相应的源数据，并根据具体的挖掘目标和任 务抽取相应的数掘；对抽取的数据进行再加工，包括数据清洗、数据变换、数据归 约等功能。 ( 3 ) 数据挖掘是指通过建立挖掘模型，实施相应的挖掘算法来找出所需要的知 识模式。 ( 4 ) 结果的解释和评估包括：根据某种兴趣度度量，识别表示知识的真正有价 值的模式；使用可视化和知识表示技术，向用户提供简洁的易于理解的有价值的知 识和信息。 2 4 数据挖掘在网络入侵检测中的应用 6 第二章基于数据挖掘的入侵检测系统概述 目前应用最广的入侵检测系统是基于特征签名的方法，这种方法只能检测到特 征签名库中已知的攻击，因此特征签名库必须对新的入侵行为的特征进行手工更新。 这些局限性使基于数据挖掘的入侵检测系统的研究越来越受到重视。 基于数据挖掘的入侵检测模型的构建过程与知识发现过程相似，同样要经过数 据准备、模型构建和解释评估三大阶段。网络入侵检测系统中常用的数据挖掘方法 主要有关联分析、序列模式方法、分类分析、聚类分析、以及孤立点挖掘。 关联分析的目的在于生成部分数据的概要。举例来说，寻找数据子集间的关联 关系或者一些数据与其他数据之问的派生关系。本领域最常见的技术是关联规则。 关联规则的计算依赖于发现相关数据中频繁出现的数据项，利用这些频繁项可以获 取规则。常用的算法有a p r i o r i 和a p r i o r i t i d 算法。 序列模式是为了发现不同数据记录之间的纵向关系，这与关联分析挖掘数据记 录中不同数据项之间的横向关联性有所不同。给定一个由不同序列组成的集合，其 中，每个序列由不同的元素按顺序有序排列，每个元素( 交易) 由不同项目组成，同 时给定一个用户指定的最小支持度阈值，序列模式挖掘就是找出所有的频繁子序列， 即该子序列在序列集中的出现频率不低于用户指定的最小支持度阈值。序列模式挖 掘方法主要有a p r i o r i a l l 和a p r i o r i s o m e 算法。 分类的任务就是确定对象属于哪个预定义的目标类，通过学习得到一个目标函 数f ，把每个属性集x 映射到一个预先定义的类标号y 。分类方法是一种根据输入 数据集建立分类模型的系统方法。数据挖掘分类常用的方法主要有决策树、神经网 络、粗糙集、支持向量机等。这些技术都是使用学习算法确定分类模型。 聚类分析方法，将物理或抽象对象的集合分组成为有类似的对象组成的多个类 的过程称为聚类。聚类分析的原则是：聚类结果要使得各类内部数据问的相似度最 大，而各类间的相似度最小。聚类分析和分类分析的明显不同之处在于，分类模型 所使用的数据是己知类别标签的，属于有监督的学习方法；而聚类分析和处理的数 据均是无类别标签的，属于无监督学习方法。通过聚类可以识别稀疏或密集的数据 区域，从而发现数据的整个分布情况，以及数据属性间存在的有意义的、有价值的 相关联系。聚类分析算法可以分为以下几大类：划分法、层次发、基于密度的方法、 基于网格的方法和基于模型的方法等。 孤立点发现方法，任何事物都要一分为二来看，一个人的噪声( n o i s e ) 可能是另 一个人的信号。孤立点是实际生活中反常行为的写照，从距离观点看，孤立点就是 那砦离群点，是那些远离密度较高部分的点。在下一章中，本文将对孤立点发现算 法进行详细的讨论。 数据挖掘的在入侵检测中的应用研究可分为误用检测和异常检测两个方向。 ( 1 ) 目前数据挖掘在误用检测中应用主要集中在分类方法的研究上。数据集中 7 青岛人学硕十学位论文 的每个对象都被标识为“j 下常”或者“入侵”类别，然后作为训练集通过选用的分 类算法进行训练。这种方法可以通过自动学习标注好的新的入侵行为的训练集以达 到更新规则库的目的。与基于特征签名的入侵检测系统不同的是，采用分类算法的 误用检测系统可以自动生成规则，并月比人工标注特征签名要更加精确和有效率。 误用检测的最大优点是其对已知攻击行为的高检测率。但其显著的缺点是不能发现 未知的新的入侵行为。 ( 2 ) 由于异常检测可以发现新的未知的入侵行为，因此是数据挖掘在入侵检测 应用中的一个主要研究方向。目前数据挖掘在异常检测中的研究主要集中在聚类分 析和孤立点发现方法的研究上。前者首先通过聚类算法构造f 常网络行为模型( 特 征) ，然后把与这些f 常行为模式偏离较大的行为认为是异常3 。采用孤立点的方法 比如基于密度的孤立点检测方法直接从异常本质出发来发现异常，给每个对象都赋 予一个异常因子柬表示其异常程度，然后把异常因子大的那些行为认为是入侵行为， 相比聚类技术更适合网络入侵的异常检测。 近年来，随着网络技术的高速发展，入侵检测技术逐渐标准化，这改善了目前 该技术封闭、专用、彼此不兼容、数据无法共享、无法协同等方面的缺陷，为网络 入侵检测的解决提供了一个比较完备、安全的方案。进一步，现在多种方法和技术 不断应用于智能入侵检测技术、以提高检测的准确性；由于现实中产生的持续到达 的网络连接数据属于数据流，把面向数据流的数据挖掘方法应用于实时的网络入侵 误用检测和异常检测j 下成为研究的热点。 8 j1； 第三章孤立点发现算法分析和比较 第三章孤立点发现算法分析和比较 数据挖掘的大多数算法主要研究问题是发现“大模式”，孤立点发现算法是用来 发现数据集中“小的模式”。在数据集合中，一个孤立点是一个明显不同的点，即与 数据其余部分不连续。h a w k i n s n 引在文献中将孤立点定义为“一个偏离其他的观测值 以至于被怀疑为从不同的机制产生的观测值”。孤立点发现的任务可以描述如下：给 定一个由n 个数据点或对象构成的集合，及预期的孤立点数量n ，发现与剩余的数 据相比是最不一致的、异常的或显著相异的前n 个对象n2 1 。一个人的噪声可能是另 一个人的信号，在很多情况下，挖掘这些孤立点是很有意义的。孤立点发现已成为 数据挖掘中的一个重要研究方向，已经应用子电信、信贷信用、医药研究、天气预 测、财务、市场营销、客户分段、网络入侵检测等大量领域。 3 1 基于统计的孤立点检测方法n 引 早期的孤立点检测大多利用统计的方法，统计意义上的孤立点定义为与给定的 分布或统计模型的显著性差异超过某个阈值的数据。基于统计的孤立点发现算法可 以分为两类：基于分布的方法和基于深度的方法，基于分布的方法首先为数据集指 定一个标准分布( 正态分布，泊松分布等) ，异常基于该可能分布而定义，然后用不 一致性测试方法发现孤立点。基于深度的算法中，每个数据对象表示k 维空间中的 一个点，并且有着一个深度，孤立点有可能存在于那些深度较低的数据中。 统计方法的主要缺点在于所使用的算法大多数是针对单变量的，虽然也有部分 测试是多变量的；另一个限制是需要事先假定数掘服从某种分柿，但在许多情况下， 用户并不知道所要发现的数据集服从什么分布，而且现实数据也往往不符合任何一 种理想状态的数学分布，即使在低维( 一维或二维) 时的数据分布已知，在高维情 况下，估计数据点的分布也是极其困难的。 3 2 基于聚类的孤立点检测方法 从聚类的观点看，孤立点是不在簇中的数据，通常被称为噪声。大多数聚类算 法( 比如c l a r a n s ，d b s c a n ，b i r c h ，s t i n g ，w a v e c l u s t e r ，d e n c l u e ，c l i q u e ) 都具有一定的噪声处理能力，虽然聚类中的噪声和孤立点在概念上有重叠之处，但 还不是完全一样的。噪声是定义建立在聚类基础之上的，即噪声是不属于任何聚类 的数据，而孤立点的定义是不依赖于聚类的。而且这些聚类算法的出发点是排除噪 声干扰，使聚类效果达到最好，而不是为了发现孤立点。 3 3 基于距离的孤立点检测算法 k n o r r 和n g ( v l d b 1 9 9 8 ) 7 1 提出了一种基于距离的孤立点检测算法d b ( p ，d ) 。 定义1 ：基于距离的孤立点 o 青岛人学硕+ 学位论文 如果数据集合s 中对象至少有p 部分与对像o 的距离大于d ，则对象o 是一个 带参数p 和d 的基于距离的( d b ) 孤立点，即d b ( p ，d ) 。换句话说，与统计的方法不同， 我们可以将基于距离的孤立点看作是在给定的距离旱，那些没有“足够多”邻居的 数据对象。d b ( p ，d ) 算法可以分为：基于索引的算法；基于嵌套循环的算法；基于单 元的算法n 刖。基于距离的孤立点发现算法比基于统计的方法避免了过多的计算，且 事先不需要知道数据集服从什么分稚。d b ( p ，d ) 算法的缺陷是输入参数p 和d 很难确 定，对于不同的参数，结果有很大的不稳定性；将孤立点看作是二元属性，不能给 出每个数据对象的孤立的程度。 针对d b ( p ，d ) 算法的缺陷，r a m a s w a m y 提出了基于距离的第k 个最近邻( k t h n e a r e s tn e i g h b o r ) 孤立点挖掘方法硝算法口们。 定义2 ：给定有n 个点的输入数据集合，参数k 及n ，若存在不多于n 1 个其他点 p ，使得d k ( p ) d 。( p ) ，则点p 是d 。的孤立点，其中，d 。( p ) 表示点p 到它的第k 个 最近邻之问的距离。换句话说，若根据距离d k ( p ) ，对数据点降序排序，在这个排序 中项部n 个点就被认为是孤立点。 d ! 可以分为以下几种算法： 批处理嵌套循环，计算孤立点的嵌套循环算法对每个数据对象p 简单计算出它 的第k 个最近邻的距离d 。( p ) ，然后选取前n 个d k ( p ) 值最大的点作为孤立点。每次 只处理一个点，需扫描数据库n 次，其中n 是数据集中数据对象的个数，故算法对 距离计算的复杂度为o ( n 2 ) 。 基于索引的链接，通过高维空问索引结构，比如通过对r 木树心们的剪枝来降低 计算数据对象的d k ( p ) 的时问复杂度。 基于划分的方法瞳是先对数据集进行划分，然后估计每个划分的d 。( p ) 的上下 界，如果判定某个划分不可能包含孤立点，就可以把这个划分里的数据对象忽略掉， 这样就不需要计算全部数据对象的d k ( p ) 。 当基于距离的第k 个最近邻d ：孤立点挖掘算法的k = l 时，这种方法称为最近邻 ( n e a r e a tn e i g h b g r ，简记n n ) 孤立点挖掘算法。 3 4 基于密度的局部异常孤立点检测算法 在不同密度数据集的情况下，基于距离的孤立点算法往往会遗漏一部分孤立点 数据。b r e u n i n g 和k r i e g e l n0 1 提出数据对象是否异常不仅仅取决于它与周围数据的距 离大小，而且还跟周围邻居的稀疏程度即密度有关，给出了基于密度的孤立点发现 算法，准确地找出了这部分孤立点。与以往大多数方法把孤立点当作非此即彼的二 元属性不同，他们给每个数据对象赋予了一个局部异常因子l o f ( l o c a lo u t l i e rf a c t o r ) 1 0 第三章孤立点发现算法分析和比较 来表示其异常程度，然后选取前n 个局部异常因子最大的对象为孤立点。 定义3 ：数据点p 的k 距离 对任意的自然数k ，定义数据点p 的k 距离( k d i s t a n c e ( p ) ) ，为p 和某个对象o 之 间的距离，这里的o 满足：至少存在k 个对象o d p ，使得d ( p ，0 ) g ( p ，o ) ，并且至 多存在k 1 个对象0 d p ，使得d ( p ，0 ) k d i a t a n c e ( 。1 d ) ( p j ) ，j r e a c h d i s t ( 。l d ) ( p i ，p j ) = d ( p i ，p j ) 。根据推论4 1 ，k - d i a t a n c e ( p j ) ) f 会增大，因此，如果d ( p i ， p j ) k d i s t a n c e ( 。l d ) ( p j ) ，r e a c h d i s t ( n e w ) ( p i ，p j ) = r e a c h - d i s t ( 。l d ) ( p i ，p j ) 。 定理4 3 ：以下点的l r d 值需要更新：k 近邻域发生变化的点以及与这些点互为k 近 邻的点。因此，每次更新r e a c h d i s t ( p i ，p j ) 之后，除了更新p j 的l r d 值外，我们需要更 新l r d ( p i ) ，如果p j k n n ( p i ) 。 。证明：根据公式4 ( 2 ) ，p i 的k 距离发生变化，其1 r d 发牛变化；根据定理4 2 ， p j 的k 一距离变化，有且只有p j 的k 一近邻p i 相对于p j 的可达距离r e a c h d i s t ( p i ，p j ) 发生 变化。根据公式4 - ( 2 ) ，只有p j k n n ( p i ) 时，r e a c h d i s t ( p i ，p j ) 彳。能参与l r d ( p i ) 的计算。 定理4 4 ：1 r d 值更新的点p m 的l o f