（管理科学与工程专业论文）基于异常挖掘的网络入侵检测系统研究.pdf

西安建筑科技大学硕士论文 基于异常挖掘的网络入侵检测系统研究 专业：管理科学与工程 姓名：彭绪友 指导教师：黄光球教授 捅要 在信息化大浪潮席卷全球的今天，互联网获得迅速发展。网络信息已经应用在国 家和社会各个部门，人们在进行资源共享同时，也感受到信息安全问题日益突出。如 何保证网络信息安全已成为互联网发展中十分重要的课题。从最初访问控制机制到结 合包过滤及应用层网关的防火墙技术等这些被动的、静态的安全防御体系已经无法满 足当前安全状况的需要。在这种情况下，促使了入侵检测系统的诞生，它以主动方式， 通过检查网络和系统内部数据异常情况来发现可能入侵行为，并进行报警或主动切断 入侵通道，弥补其它静态防御系统的不足。 论文首先介绍异常挖掘理论，将其作为一种新的入侵检测技术引入到入侵检测系 统中。文中对异常挖掘技术进行分析与研究，结合异常挖掘技术特点和入侵检测系统 的检测目标，提出基于异常挖掘网络入侵检测系统，该系统通过运用异常挖掘技术挖 掘异常数据的高效性，及时挖掘出新的未知入侵行为，用以更新入侵规则库，并采用 高效率模式匹配算法进行实时入侵检测，从而使系统能够高效准确地检测到己知或新 的未知的入侵行为，并具备自动构建和更新入侵规则库的智能化功能。随后，论文详 细分析和综述入侵检测系统发展现状及存在问题，构建基于异常挖掘网络入侵检测系 统模型，并根据功能需求，对模型进行模块划分，阐述各子模块需要实现的功能。文 中还对算法进行了例证分析，并对数据预处理过程作了深入研究。最后，论文运用形 式化语言对入侵检测系统各子模块进行结构化分析与描述，为系统进一步实现奠定基 础。论文主要创新，首次将基于密度异常挖掘方法应用于入侵检测系统中，提出并构 建系统原始模型，并对系统进行形式语言描述。 论文提出并构建的基于异常挖掘网络入侵检测系统与既有检测系统相比，具有自 动创建并及时自动更新入侵规则库的智能化功能，在实时检测速度及检测准确性方面 也有较大改进，因此能够高效准确地检测已知和新的未知的网络入侵行为，提高了网 络安全性能并减少管理人员的工作量。 关键词：异常异常挖掘模式匹配入侵检测 论文类型：应用研究 西安建筑科技大学硕士论文 s t u d y o nn e t w o r ki n t r u s i o nd e t e c t i o ns y s t e m b a s e do no u t l i e r sm i n i n g s p e c i a l t y ：m a n a g e m e n ts c i e n c ea n de n g i n e e r i n g n a m e ：p e n gx u y o u i n s t r u c t o r ：p r o f h u a n gg u a n g q i u a b s t r a c t t o d a y , t h et i d eo f i n f o r m a t i o n i z a t i o ni ss w e e p i n ga c r o s st h eg l o b ea n di n t e m e th a sb e e n g e t t i n gf a s td e v e l o p m e n t t h en e t w o r ki n f o r m a t i o nh a sb e e n a p p l i e dt oe v e r yd e p a r t m e n to f c o u n t r i e sa n ds o c i e t y w h i l ep e o p l es h a r et h en e t w o r ki n f o r m a t i o nt o g e t h e r , t h e yf e e lt h a t t h eq u e s t i o no fi n f o r m a t i o ns a f e t yi sb e c o m i n gm o r ea n dm o r es e r i o u s i th a sb e e nav e r y i m p o r t a n tf o ru st og u a r a n t e et h es e c u r i t yo fn e t w o r ki n f o r m a t i o n t h ep a s s i v ea n ds t a t i c s e c u r i t y d e f e n s es y s t e mf r o mt h ei n i t i a la c c e s sc o n t r o lm e c h a n i s mt op a c k e t st i l t e ra n dt h e f i r e w a ut e c h n i q u e so fa p p l i c a t i o nl a y e rg a t e w a yh a sb e e na l r e a d yu n a b l et om e e tt h e d e m a n d so f p r e s e n ts e c u r i t ys t a t e i nt h i se a s e ，t h eb i r t ho f t h ei n t r u s i o nd e t e c t i o ns y s t e mh a s b e e ni m p e l l e d i tt a k e si n i t i a t i v ea p p r o a c h e st od e t e c tt h ep o s s i b l ei n t r u s i o nb e h a v i o r s t h r o u g hc h e c k i n gt h ea b n o r m a l s t a t eo fn e t w o r ka n ds y s t e mi n t e r i o rd a t a ，a n d g i v e s w a r n i n g so rc u t so f f t h ei n t r u s i o nw a y s t h e r e f o r ei tr e m e d i e st h ed e f i c i e n c i e so f o t h e rs t a t i c d e f e n s es y s t e m s t h et h e s i si n t r o d u c e sf i r s t l yt h et h e o r yo fo u t l i e r sm i n i n gw h i c hi sa p p l i e dt ot h e i n t r u s i o nd e t e c t i o ns y s t e ma sak i n do fn e wi n t r u s i o nd e t e c t i o nt e c h n i q u e i nt h i st h e s i s ，t h e o u t l i e r sm i n i n gt e c h n i q u ei sa n a l y z e da n dr e s e a r c h e d c o m b i n i n gt h ec h a r a c t e r i s t i c so ft h e o u t l i e r sm i n i n gt e c h n i q u ew i t ht h ea i mo fi n t r u s i o nd e t e c t i o ns y s t e m ，t h ea u t h o rp r o p o s e s t h en e t w o r ki n t r u s i o n d e t e c t i o ns y s t e mb a s e do no u t l i e r s 埘j i l i n g t h r o u g ha p p l y i n gt h e e f f i c i e n c yo fo u t l i e r sm i n i n gt e c h n i q u et om i n et h eo u t l i e r sd a t a ，t h es y s t e mf i n d st i m e l y t h o s en e wa n du n k n o w ni n t r u s i o nb e h a v i o r s ，t h u sm n e w st h ei n t r u s i o nr u l e sd a t a b a s e a tt h e s a m et i m ei tc a r r i e so nr e a l t i m ei n t r u s i o nd e t e c t i o nb yu s i n ge f f i c i e n tp a t t e r nm a t c h i n g a l g o d t h m ，w h i c hm a k e st h es y s t e md e t e c te f f i c i e n t l ya n da c c u r a t e l yt h o s ek n o w no rn e w a n du n k n o w ni n t r u s i o nb e h a v i o r s ，a n dp o s s e s st h ei n t e l l i g e n tf u n c t i o no fc o n s t r u c t i n ga n d r e n e w i n ga u t o m a t i c a l l yi n t r u s i o nr u l e sd a t a b a s e l a t e r , t h et h e s i sa n a l y z e sd e t a i l e d l ya n d s u m m a r i e st h ec u r r e n td e v e l o p i n gs i t u a t i o na n de x i s t i n gp r o b l e m so fi n t r u s i o nd e t e c t i o n 西安建筑科技大学硕士论文 s y s t e m ，c o n s t r u c t sam o d e lo fn e t w o r ki n t r u s i o nd e t e c t i o ns y s t e mb a s e do no u t l i e r sm i n i n g ， a n dd i v i d e sm o d u l et ot h em o d e la c c o r d i n gt o 也ef u n c t i o nd e m a n d s a tt h es a m et i m ei t e x p a t i a t e so nt h ef u n c t i o nw h a te v e r ys u b m o d u l er e a l i z e s t h et h e s i sa l s om a k e sa n e x e m p l i f i c a t i o nt ot h ea l g o r i t h ma n dat h o r o u g hr e s e a r c ht ot h ep r o c e s so fd a t ap r e t r e a t m e n t f i n a l l y , u s i n gt h ef o r m a l i z e dl a n g u a g e ，t h et h e s i sa n a l y z e sa n dd e s c r i b e ss t r u c t u r a l l ye v e r y s u b m o d u l eo fi n t r u s i o nd e t e c t i o ns y s t e mw h i c he s t a b l i s h e st h ef o u n d a t i o nt or e a l i z ef n r t h e l - t h e s y s t e m i nt h et h e s i s ，m a i ni n n o v a t i o n s i n c l u d et h a ti t a p p l i e s t h em e t h o do f d e n s 畸一b a s e do u t l i e r sm i n i n gt oi n t r u s i o nd e t e c t i o ns y s t e mf o rt h ef i r s tt i m e ，p r o p o s e sa n d c o n s t r u c t st h eo r i g i n a lm o d e lo fs y s t e m ，a n da p p l i e sf o r m a l i z e dl a n g u a g et od e s c r i b et h e s y s t e m c o m p a r e dw i t h o t h e ri n t r u s i o nd e t e c t i o ns y s t e m ，t l 】9n e t w o r ki n t r u s i o n d e t e c t i o n s y s t e mb a s e do no u f l i e r sm i n i n gp o s s e s s e st h ei n t e l l i g e n tf u n c t i o no fc o n s t r u c t i n ga n d r e n e w i n ga u t o m a t i c a l l yi n t r u s i o nr u l e sd a t a b a s e ，a tt h es a l et i m et h er e a l - t i m ed e t e c t i o n v e l o c i t ya n da c c u r a c ya r eg r e a t l ye n h a n c e d t h u si tc a nd e t e c te f f i c i e n t l ya n da c c u r a t e l y t h o s ek n o w na n dn e w - a n k n o w nn e t w o r ki n t r u s i o nb e h a v i o r , i m p r o v et h en e t w o r ks e c u r i t y p e r f o r m a n c ea n dr e d u c et h ew o r k l o a do f a d r n i n i s t r a t o r s k e y w o r d s ：o u t l i e r s ，o u t t i e r sm i n i n g ，p a t t e r nm a t c h ，i n t r u s i o nd e t e c t i o n t h e s i st y p e ：a p p l i c a t i o ns t u d y 声明 本人郑重声明我所呈交的论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含本人或其他人在其它单位已申请学位或为其它用途使用过的成果。 与我一同工作的同志对本研究所做的所有贡献均已在论文中作了明确 地说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者答名。彭缓芡 聃：知f 午 关于论文使用授权的说明 本人完全了解西安建筑科技大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校 可以公布论文的全部或部分内容，可以采用影印、缩印或者其它复制 手段保存论文。 ( 保密的论文在论文解密后应遵守此规定) 论文作者签名：嘲锔欠导师签名：老 期：功心q - 2 7 西安建筑科技大学硕士论文 1 1 选题背景 1 绪论 在信凰比大浪潮席卷全球的今天，互联网获得迅速的发展。全球国际互联网用户总数已超 过2 亿，世界独立域名网站总数也已超过1 6 0 0 万个。网络信息已经匣用在国家和社会的各个部 门：军事、金融、工业和贸易等。人们在进行资源共享的同时，也感受至b 信息安全问题日益突 出。如何保证网络信息安全已成为互联网发展中十分重要的课题。从最初自q 访问控制机制到结 合包过滤及应用层网关的防火墙技术，部未能有效的解决问题。主要问题在于： 设计；f 口实现个整体匕绝对安全的系统几乎是不可能的。操作系统和应用软件正变得越来 越复杂，软件设计者在设计时无法预测程序运行时的系统状态，更无法精确地预测出在不同系 统状态下会发生什么结果。所以，系统往往存在着设计和配置管理上的漏洞。m i l l e 9 1 蛤出了一 份有关当今流行的操作系统和应用程序的硼究报告，指出软件中不可能没有缺陷。 信息加密技术方法、访问控制机制和保护模型本身存在一定问题“。从信息安全三要素即 保密性( c 。l 】：丘d 锄d 出b 、完整陛删和可用。 生( a v a i l a b i l i t y ) 来看，个安全的计算机信息系 统不仅应该保护它的信息和资源不被未授权者访问和篡改，同时还必须保证信息和系统资源能 持续可用。由于当前加密技术方法本身存在一定问题，因此很难保证信息能1 0 0 地不被泄漏； 而些用户列懒j 性能的苛亥啦皂求，也导致访问控制机制e 存在一定安全隐患。 组成计算机网络的某些关键技术本身存在安全问题。例如组成计算机网络的关键技术 t c p i p 仂设本身就有许多不完善地方。 因此，绝对安全的网络系统是不存在的，即使再安全的系统，都可能有各种各样的漏洞存 在，黑客正是利用这些漏洞来对网络系统进厅攻击。在8 0 年代末，针对网络系统的攻击j 亨式还 仅限于窃取口令和利用已知的系统漏洞；到了今天，网络攻击已发展为野蛮攻击脚f 缸瞄、 网络窃听 、源代码分析、i p 伪装口s p 0 d 0 、拒绝服务攻击、网络扫描脚i n 曲、 分布式攻击s b jb i 删a t t a c k ) 、利用已知漏洞及协议缺陷的攻击、以及针对特定应用服务f 如 f t p ，t e l r m i ，w w w ，的攻击。尽管进行复杂攻击还需要相当的计算机专业知识，但是 由于攻击技术的发展和在网络上无限制传播，即使是不具备专业计算机知识，也可以从网络上 下载到些使用简便的攻击程序进行危害幽艮大的攻击。 针对众多入侵行为，为了加固我们的网络，人1 f 阿院制定并应用各种安全策略和工具。传 统防御策略是：采用诸如防火墙、加密、身份认证以及访问控制、操作系统加固等静态安全防 御策略。这种防御措施在一定程度e 起到了良好的作用。然而，随着入侵技术不断发展、攻击 手段与方法的复杂化和多样化，这种被动的、静态的安全防御体系已经无法满足当前安全状况 西安建筑科技大学硕士论文 的需要。 在这种情况下，促使了入e 捌系统o n 廿商o n d e t e c t i o n s y s t e n l ，d s ) 的诞生，它以主动方 式，i 恿过检查网络和系统内部数据的异常情况来发现可能入侵行为，并进行报警或主动切断入 侵通道。入侵检测系统不仅可以防止来自于外部的攻击，还可以发现内乱人员的非法行为，弥 补了其它静态防御系统的不足。 然而，入侵检测系统目前仍然存在很多问题：虚警率偏高、事件响应与恢复机甫怀完善、 缺乏国际统一标准等，尤其是具有自适应能力、能自我学习的入侵检h 4 系绱丕不完善。因此， 本文分析了异常挖掘技术在入侵检测系统中的适用性，将其应用于八侵检测系统中，对入侵行 为提取特征、建立 侵规则序，实现了入侵检测模式库的自动更新，通过对审计数据的处理并 与x 侵规则进行匹配，检淝l 入侵，提高了入侵检灏4 的准确性，以及降低了虚警率，形成智能化 的入侵检测系统。 蓬无疑问，在网络犯罪日益猖獗的今天，保障计算机系统、网络系统及整个信息系统基础 设施的安全已成为亥唰潮的任务，如何争取在信息战中的主动权，保护国家信息安全，是科 研人员必须研究的重大讶 趿。所以致力于入侵检测方法研究t 作无疑具有重要p l 研意义和社会 意义。本论文工作旨在对当前入侵检测中的些问题进行探索性研究，提出一些建设性的且对 后续研究工作具自借鉴意义的方法和技术。 12 国内外研究现状及发展动态 国内外对i d s 研究大约有二十多年，从无到有，成为个非常活跃的研究 觅域。相对来说， 国夕阿究人员在这方面所做工作较多。1 9 8 0 年j a m e sa n d c r n 冈首先提出入侵检测概念，他对 侵检测系统的定义是潜在的、有预谋的、未经授权自访问信息、操作信息、致使信息不可靠 或无法使用的企图。1 9 8 6 年，d n i n g 囹和n e u m a m 提出种实时入侵检澳蟆型( r e a l - t i r i l e l r l r l 】s i o nd e t 枷o l lm o d e l ) 队奠入信封佥澳抟家系统( 髓s ) 。入侵检测专家系统主要j 彭立统计方法 来植朔9 攻击以及发驰佣户异常行为。1 9 8 7 年，d e n n i n g 提出了叶j 蘑用入侵* 佥澳蝴翘甄a ) m ) ， 他的这篇论文被认为是入侵检m 4 领域的里程碑。1 9 8 8 年，l u 玎柙等 、对b e r i n g 提出的入侵检 测模型进行了改进，提出了与系统平台无关的实时检测思想。1 9 9 0 年， i c 刚划5 j 等人提出基 于网络的入侵检测系统( n s 均，通过主动监视网络信息流量来检测攻击。1 9 9 1 年，n a d i 一和 d i d s 喂出了收集处理多主机的审计信息来检测对主机的协同攻击。1 9 9 4 年，m kc r o s b i e 和 g e 掣盘剥8 提出用a l 蚰r l o m 咖sa g e n t 来提高入侵检测系绕肚能。1 9 9 4 年b i s w a n a t h 、 m 蚓e 。d 等系统总结了入侵检测系统的工作并分析评述各种i d s 原型。1 9 9 6 年 g r i d s ( g r a p h - b a s e di n 廿u s i o nd e t e c t i o ns y s t e m 严刈的设计和实现解决当代绝大多数入侵检4 系统 伸缩眭不足的问题，使得对大规模自动或协同攻击的检测更为便利，这些攻击有时甚至可能跨 过多个管理领域。 过多个管理领域。 西安建筑科技大学硕士论文 国内入侵检测研究工作开展较晚，科研界研究工作主要集中在中科院、北邮、北京大学、 武汉大学等国家信息安全重点实验室，目前扶发表文献来看主要以研究靴t l u 2 , 1 3 1 、提出系统 框架【1 4 , 1 5 , 1 6 , 1 7 , 1 8 , 1 9 , 2 0 , 2 1 等居多，并且儿总体上讲，研究人员在入侵检测研究方法的选择上并没有超 出国际| 上己经提出的方怯范畴。 近年主要创新包括：f o n e s t 2 2 1 等将免疫原理运用到分布式入侵检测领域。1 9 9 8 年r o s s a l d ( z s c , l q 和a b i d a k h a t t a k t 2 3 1 将信息检索技术引进到入侵检测，各种新方法都处于研究阶段。现 在的趋势是将其他领域及相关学科知识综合应用于入侵检测系统中，e 匕立口，p u r d u eu n i v e r s i t y 的s a i x t e 印k t m a a r 和g e l l e s p a f f o r d 设计的着色p e t r i 网( c p - n e q 3 ，采用状态转移分析技术 i 来优化_ 误用检测系统的方法。i d i o t p 4 1 系统就是该方珐具体实现。另种比菠新的检i 贝| i 方法是 基因算法，典型代表是由f r e n c h 蛳g u n i v e r s i t yl u d o v i c m 6 0 f s u p e l e e 开发的g a s s a t a 系纠蠲。 1 3 论文主要研究内容 本论文工作重点为网络异常行为检测方法的研究及其形式化语言实现。针对当前异常检测 系统所面l 临的三个挑战性问题：入侵检测实时陛、刚鼎吴报率、检测新类型攻击的能力。本论 文做了如下些工作： ( 1 ) 综述了常用异常挖掘方法，并对基于密度的异常挖掘算法做了进步分析研究和例证分 析。 ( 2 ) 分析总结了目前入侵检测系研究现状与发展动态，针对当前 侵检澳0 系统存在的主要问 题，提出了种基于异常挖掘的网络入侵检i 贝瞟统m 删d s 。 ( 3 ) 构建了基于异常挖掘的网络入侵检测系统总体模型结构，并根据功能需求进行模块划 分。给出了各模燃结构并阐述了各模块的主要功能。 ( 4 ) 对o m n i d s 系统的数据初步预处理工作做了较深入的分析。 ( 斓形式化语对o m n i d s 系统中各功能馍块做了详细的描述。 本文对基于异常挖掘方法的网络入侵检测技术进行了探索l 生研究。第二章首先对常用的异 常挖掘方法进行了综述，然后对基于密度的异常挖掘算法进行了进步的分析研究。第三章分 析了目前入侵检测系统研究现状，针对存在的三大问题提出了种基于异常挖掘的网络入侵检 测系统。第四章给出了o m n i d s 系统的体系结构并对数据预处理工作做了分析。第五章对整 个系统做了详细的形式化语言描述。最后对本文的工作进行了总结与展望。 西安建筑科技大学硕士论文 异常挖掘方法分析与研究 有关异常的定义说法很多。例如，m w k 呶l g s o ) 给出了异常的本磺性定义阳：异常就是在数 据采集中与众不同的数揖使人附为犁鞘据并j 嗣期偏差，而是产生于完全不同0 。聚类 算法对异常的定义为：异常就是聚类嵌于其中的背景噪声。异常挖掘算法对异常的定义为：异常 是既不属于聚类也不属于背景噪声的点，他们的行为与正常行为有很大不同。本文认为，异常就 是指那些不符合数据叫测的数据对象。它可能是窆星蓟渤行 昔误所导致的，例如，个人的 徽- 9 9 9 9 9 可能翮哥耘艄3 录年龄的映省设置昕产生的；它也可自凝固有数据变异性的结果， 例如，个公司首席执行官的工资自然远远超过公司其他雇员的工资，成为个异常。 许多数据挖掘算法试图使异常的影响最小化，或眷徘除它们。但是由于个 、的噪声可能 是另个 、的信号，因此，这样做可能会导致重要隐藏信息的丢失。也就是说，异常本身可能 是非常重要的，例如，在欺诈探测中，异常可能飘揪诈行为。可见，对异常进行专门挖掘 是数据挖掘中个重要方面。由此，异常挖掘的概念便匣i 云而生。 所谓异常挖掘就是用数据挖掘方法来发现“小模式”( 相对于聚类) 即数据集中明显不同于 其他数据的数据对象的挖掘过程。它可以描述如下：给定个n 个数据点或对象集合，及预期 的异常数目k ，发现与剩余数据相比是显著相异的、异常的或不致的头k 个对象。异常挖掘 问题可以秘舶如下谚将问题： ( 1 ) 在给定数据集合中定义什么样的数据可以被认为是异常； ( 2 ) 找到个有效方法来挖掘这样的异常。 异常挖掘有融楚基本j 丑翟：( 1 沛b 过程。或者所有波阿壤对象都谈况为异常，或者都被视为 致数据而被接受。( 2 ) 连续过程。该过程的个例子是内部出局过程。它的主要思想是：首先 检验最不可能是异常的对象。如果它是异常，那么所有更极端的值都被认为是异常；否则，检 验下爪极端对缘，依此类推。这们过程往往比批过任更晴效。 异常挖掘有着广泛应用。例如，进行异常挖掘，在电信业中可以探测不寻常的信用卡使用 或电信服务；在市场分析中可以用于确定极低或极高收入客户的消费行为：在医疗业中可以用 于发现对多种治疗方式的不寻常反应。此外，异常挖掘方法还可应用于贷款审批、气象预报、 网络入侵等领域。本论文重点研究异常拄浦移路# 在网络 侵检测领域中的应用。 2 2 异常挖掘基本算法 基于计算机的异常挖掘方法很多，综合起来有：基于统计方法口1 , 3 0 7 、基于距离方法【3 瑚、 4 西安建筑科技大学硕士论文 基于偏离方法田弼、基于密度方法嘲以及高维数据异常挖掘方托皆。 2 2 1 基于统计方法 基于统计方法对给定数据繁f 阪设了个分布或概璋副奠型( 例如一个正态分布) ，然后根据模 型采用不致检验来确定异常。 不致检验的基本思想是：个统计学的不致 蜷查有两个假设：个工作假设和个 替代假设。个工作假设h 是个命题：n 个对象的整个数据集合来自个初始分布模型f ， 即h ：盯，f ，f = 1 , 2 ，九。如果没有统计上的显著证据支持拒绝这个假设，它就被保留。 不致检验验证个对象盯，关于分布f 是否显著地大或小。依据可用的关于数据的知识，不同 的统计量被提出来用作不致瞄凇测。假设某个统计量7 1 被选择用于不致性检测，对象盯。的 该统计量自雅沩v 。，则构建分布r ，估算显著性概率s l ( v 。) = p r o b ( t v ，) 。如果某个s p ( v ，) 足够小，那么叽是不致的，工作假设被拒绝。替代假设厅被哥毛喟，它声明盯，来自另个分 布模型g 。既然盯，可1 i 涟个模型下是异常，而在另个模型下是非异常，可见结果非常依赖 于分布模型f 的选择。替代分布在决定检测能力( 即当仃真的是异常时工作假设被拒绝的概率) 上是非常重要的。常见替代分布有：固有替p 盼布、混合替代分布以及滑动替代分布。 基于统计方法的主要缺点是：绝大多数检凝0 都是针对单个屙陆的，而许多数据挖掘问题都 要求在多维空间中发现异常。而且，使用该方法要求关于数据集合参数的知识，如分布模型、 分布参数和预期的异常数目。并且在大多数情况下，数据分布可能是未知的。所以，当没有特 定的检验时，该撕自崩的拔卿所有异常，或者观测到的分布不能晗当地被缶刚衬髟子布来 模拟。 2 _ 2 2 基于距离方法 如果数据集合s 中至少有p 部分与对象盯的距离大于d ，贝慨像口是个带参数p 和d 的 基于距离的( d b ) 异常，记为d i ， d ) 。换句话说，基于距离的异常就是那些没有“足够多” 邻居的对象。这里邻居是基于给定对象的距离来定义的。 目前已经开发了若干个高效的挖掘基于距离异常的算法，概述如下： 1 基于索引的算法。给定个数据集合，基于索引的算法采用多维索引结构( 如r 树或 l “树) ，来险彦淘啥对象盯在半径d 范围内的西罾。设m 为一个异常数据d 逝邻中的最大对 象数。因此，旦对象盯的m + 1 卟邻居被发现，那么o - 就不是异常数据。这个算法的复杂度 是o ( 尼+ n 2 ) ，其中k 是维数，n 是数据集合中对象的数目。当k 增加时，这种算法具有良好 的扩展性。但是，复杂尉占算只考虑了搜索时间，即使构造索引任务本身计算量也是相当大的。 2 嵌套1 廊不算法。该算法避免了索引结构的构建，试图最小化i o 的次数。它把内存的 缓冲空间分成两半，把数据集分成若干逻辑块。通过精心选择逻辑块装) 、每个缓冲区域的顺序， 5 西安建筑科技大学硕士论文 来改善i ，o 的效率。 3 基于单元的方法。该算法把数据空问划分：d 2 后的单元。每个单元两个包 围层，第层的厚度是一个单元，第二层的厚度是2 以一1 。该算法逐个单元地计数异常，而 不是逐个对象地计数异常。对于个给定的单元，它累计三个计数：单元中对象的数目、单元 和第层中对象的数目以及单元和两个层中对象的数目。 ( 1 ) 当单元和第_ 层中对象的数目大于m 时，单元中的对象都不是异常； ( 2 ) 当单元和两个层中对象的数目小于等于m 时，单元中的对象都是异常；否则，单元中 的一些对象可能为异常，应对对象逐个进行处理。 该算法的复杂度为d ( c + h ) ，其中c 为单元数目，k 为维数。 可见，基于索引的算法由于建立索引的开销大而基本匕没有竞争性；当k 4 时，基于单元 的j 章法在n 越大时伊凇f 生越明显；当k 5 时，嵌套1 静雠于瞵湿示出优势。基于距离的 算法拓宽了多个标准分布不致检验的思想，避免了过多的计算。但该方法要求用户设置参数 p 和d ，寻找这些参数的合适设置可能涉及多次的试探和错误。 2 2 3 基于偏离方法 基于偏离的方法不采用统计检验或基于距离的度量值来确定异常对象，而是通过捡查组 对象的主要特征来确定异常。偏离特征描述的对象被认为是异常数据。该方法中的“偏离”典 型地用于指异常。 基于偏离的异常挖掘有两种技术： i 序列异常技爿9 1 。它模仿了 类从一系歹恻以的对象中识别异常对象的方式。该技术 冁割嘱想是给定n 们掾的集台s ，建立何之策序列强，是，s 。) ，这里的2 卅疗， 并有：s 。cs ，s 。对每个子集，确定该子集与前序子集的相异度差；光滑因子最大的子 集就黾异常集；光滑因子用来评价从原始鲫蝶中去除闩i 集后，相异度阐氐了多少；为减 少输入数据顺i 序对结果的影响，可以用不同的次序多次重复b 描勘曼找出其中光滑因子最大 的子集。这们鞑复杂度与数撰集歹孙呈线性关系，有僻的计算陛能。但哥移情常舀：对异 常存在的假设太过理想化，对现实中复杂的数据效果不太好。 2 o l a p 数据立方体技术。该技耗髟殳现驱动探索的种形式，预先计算指示数据异常的 值被用来酗群耕算的所有层次上指导用户进黜分析。如果含立方体的单元值显著地不 同于根据统计模型得到的期望值，那么该单元被认为是一个异常并i 硼可视化方法来表示，例 如背景颜色反映每个单元的异常程度。用户可以选择对那些标示为异常的单屙封行钻取。一个 单元的度量直可能反映了发生在立方体更低层次上的异常，这些异常在当前的层次e 是不可见 的。 西安建筑科技大学硕士论文 2 2 4 基于密度方法 基于密度的异常挖掘方法根据数据对象的邻居数量来判断数据是否为异常。邻居数超过预 先设定的阈值的数据不是异常数据，相反，当邻居数低于预先设定阈值时，该数据贝| 舸能是 异常数据。该算法重点是计算数据对象的局部异常因子，并根据局部异常因子值判断数据是否 为异常。具体的挖掘方法如下： 1 计算对象p 的k - e g n ( k _ m s m n c e ( p ) ) 。计算对象p 的k - 罡e 离是为了检测哪些数据是p 的邻居。对于任意自然数k 皿即是m i n p t s ，对象p 的最少邻居物，定义p 的枷巨离为p 和数据 集d 内的某个对缘0 之间的距离d ( p ，0 ) ，这里的0 满足： ( 1 ) j 至少。存在k 1 、对象o 。，0 。d p ) 满足a , p ，o 。) d ( p ，o ) ； ( 2 ) j i 型 存在k 一1 1 、对象d ，o d p ) 满足d 0 ，0 1f 4 p ，o ) 。 2 查找对象p 的k - 距离邻域m 。( p ) a 给定p 的k 距离，p 的k - 距离邻域包含所 有与p 的距离不l 跫过p 的k - 距离的对象q 。其数学表达示为： m 一如t 。( p ) ( p ) = q d p ) i d ( p ，q ) k d i s t a n c e ( p ) ) ( 2 1 ) 对象q 的集合被称为对象p 的k - 距离邻域。 3 计算对象p 相对于对象。的可达距离口如d i s t i ( n d ) ) 。给定自然数k ，对象p 相对 于对缘。的可达距离： r e a c h d i s t , ( p ，o ) = m a x 忙一d i s t a n c e ( o ) ，d ( p ，d ) ) ( 2 2 ) 4 计算对象p 的局部可达密度q r d 。( p ) ) 。对象p 的局部可达密度为对象p 与它的 m i n p 睁邻域的平均可达距离的倒数。其数学表达式为： m 一船( p ) = i 蕊去五：而) i n ( p ) l 5 计算对象p 的局部异常因子。 ( 1 ) 其数学表达式为： l r d 黼t s 三妇，= 等黜 ( 2 ) 局部异常的性质：对象p 的局部异常因子表示p 的异常程度，局部异常因子愈大，就认 西安建筑科技大学硕士论文 m i l l i l l 为它更可能为异常；反之则可能性愈小。簇内靠近核心点的对象的l o f 接近于1 ，那么不应该 被认为是局部异常。而处于簇的边缘或是簇的外面的对象的l o f 相对较大。 ( 3 ) 局部异常因子的计算：第步先产生所有点的m i n p t s 部域( 同时得到m i n p t s - 距离) ， 并计算到其中每个点的距离。对低维数据，可以利用( d ) 来做k - n n 查询，整个计算时间为 o ( n ) ；对中维或高维数据，必须采用索引结构如x - 树等，使得做k 二n n 查询的时间为o o o g o ， 整个计算时间为o ( n l o g n ) ；对特高维数据，索引结构不再有效，时间复杂度提高到o ( 确。第二 步计算每个点的局部异常因子。计算出异常因子后，可以根据异常因子值的大d , c e d 断数据是否 为异常。 基于密度的异常观点比基于距离的异常观点更贴近h a w l d n s 的异常的本质陛定义，因此能 够挖掘出基于距离异常算法所不能识别的类异常数据_ 局部异常。局部异常观点摈弃了以 前所有的异常定义中非此即彼的绝对异常观念，更加符合现实生活中的应用。 a g g m w a l 和( s i g m o i 0 0 1 ) 提出了个高维数据异常挖掘奇诘删。该僦高维数据 集映射到低维子空间，根据子空间映射数据的稀疏程度来确定异常数据是否存在。 高维数据的异常挖掘算法基本思想是：将数据空间每维分成中个等深度区间。所谓等深 度区间是指将数据映射到一维空间后，每一区间包含相等的仁1 中的数据点。在数据集的k 维 予空间中的每维匕各取个等深度区间，组成个k 维立方体，则立方体中的数据映射点数 为个髓机数，。设n e d ) 为k 维立方体d 所包含的点数，n 为总的点数。定义稀疏系数s o ) 为： s ( d ) ：害! 竺三丝：!但 + f ( 1 一f 2 ) s o ) 为负数时，说明立方体d 中数据尉氐于期望值；s ) 越小，说明此立方体中的数据越 稀疏。数据空间自勺任_ 撇可以用肌。，m ：，m ，来表示。聊， 卧嶙掘在第i 维予空间映射区 间的映射值，可以取值1 到m ，或者+ ( + 表示可以为任意映射值) 。异常挖掘问题可以转化成为 寻找映射在k ( k 作为参数输入) 维子空问上的异常模式以及符舒吝些异常模式的数据。如4 维空间( 设o = 1 0 ) 中的个映射在2 维子空间上的模式为+ 3 + 9 。 在高维数据中寻找异常模式是非常困难的。一个简单办法是对所有数据维进行组合，来搜 索可能的异常模式，但是其效率很低。a g g a r w a l 和y u 运用遗传算法的方法来优化这个问题的 求解过程。该方法以随机选择的p 个合法模式作为候选解开始，反复经历选择、交叉、变异等 几们立程，直至得到较满意的解。 1 选择。对于候选解，即合法模式，计算其稀疏系数，并以此依据排序。稀疏系数越小， 说明该虞式异常程度大，被选择的概率也大，直至雌出新的p 制匡越解。 r 西安建筑科技大学硕士论文 2 交叉。舅e 用了叶忧化的交叉算j 去。 3 变异。设q 为值匙的位置的集合，变异只发生在非q 类位置。有两种变异! 类型：( 1 ) 将变异位置置为4 ，然后在q 中间选择个位置，随机置为1 到。中间的一个值即可；( 2 ) 将变 异位埴韵1 到中中间的个值。 2 3 基于密度方法的改进 异常数据往往占整个数据集的比例相当小，从而导致基于密度的异常挖掘算法存在如下一 些不足：( 1 ) 局部可达距离的计，矧 常大；( 2 ) 局部异常因子的计算量也非常大。这样大大降低 了算法的性能。种基于密度方怯的改进算法则不用计算局部可达距离，并尽卑易4 出那些不包 含异常数据的数据对象，m 而在很大程度e 减少比较次数和计算量，提高了该算法盼眭能。 1 算法改进： 首先，给出两个定义： 定义1 对象p 的局部稀疏度比，记为i s r , ( p ) ，是对象p 的k - 距离邻域与邻域内所有对象 与p 的距离的和之比： 概( p ) 2 忑面in k ( 巧p ) 面 局部r 6 疏度比表示个测象自螂居数的多少。比值高，表明数据对象的邻居数多，该对象 成为异常的可能性较小。 定义2 对象p 的局部稀疏度系数，记为工s t ( p ) ，是对象p 的所有邻居的局部稀疏度比 与对象口的局部稀疏度比的比值的和求平均值： g - l s r ( o ) l s c 。( p ) - 黼 局部稀疏度系数能够表明个数据对象的周围邻居的离散程度。局部稀疏度系数高表明该 对象的邻居比饺分散，因此，该对象很有可能就是异常数据。 改进算法如下： ( 1 ) 计算对缘p 的k - 距离： 计算对象p 的k _ 足e 离与基于密度茼去相同：计算行有喇缘与对象p 的距离；查找第个k _ 最小距离；查找k - 最小距离中的最大距离。 ( 2 ) 查找对象p 的k _ 距离邻域： 查找对象p 的k 堆目驽邻域与基于密度方法相同。 西安建筑科技大学硕士论文 ( 3 ) 计算局部稀疏度比： 瓜珞( p )