（计算机应用技术专业论文）高维孤立点检测算法研究.pdf

江苏大学硕士学位论文 摘要 孤立点检测是数据挖掘的一个重要方面，因其独特的知识发现功能而得到较 为深入的研究。孤立点检测算法已经在金融欺诈检测、网络入侵检测、生态系统 失调、天气预报等风险控制领域得到了广泛的应用。但随着应用范围的不断扩大， 传统的孤立点检测算法遇到了一些难以克服的障碍，算法效率不能适应大规模数 据处理，算法的参数难以选择造成检测结果不稳定，算法不能适应高维数据的特 性等。论文主要针对以上问题对孤立点检测技术进行了研究。 论文首先详细介绍了传统的孤立点检测算法，并对它们进行了比较和分析， 指出它们的不足之处，在此基础上提出基于平均密度的孤立点检测算法 ( a d o d ) ，以减少用户对参数选择的困难；其次，为了解决高维数据对孤立点 检测带来的困难，先提出基于有限比较的最大频繁项目集挖掘算法( h n 吼) ， 再利用l c m f i 算法对基于频繁模式的孤立点检测算法( f i n d f p o f ) 进行改进， 提出基于加权最大频繁模式的孤立点检测算法( f i n d w m f p o f ) ，该算法以最大 频繁模式代替频繁模式计算频繁孤立因子( f p o f ) ，降低了算法的运算规模， 具有良好的检测效果。 论文主要工作如下： 1 对现有的孤立点检测算法进行了分析，指出它们共同存在的不足：算法 对参数的选择缺乏自动化。 2 提出基于平均密度的孤立点检测算法( a d o d ) 。用平均密度的概念重 新定义孤立点度量，以一个新的视点来检测孤立点，并用实验验证a d o d 算法 有效性，不仅能在孤立点检测时减少用户对参数选择的困难，而且具有较好的检 测效果。 3 分析了高维数据的特点及其对传统孤立点检测方法的影响。比较和分析 了现有高维孤立点检测算法，指出它们在算法效率上存在的不足。 4 提出基于有限比较的最大频繁项目集挖掘算法( l c m f i ) ，给出了相关 定义和定理，并对算法的运行效率作了详细地分析和证明，l c m f i 算法挖掘2 - 最大频繁项目集的时间复杂度为o ( m 弗2 ) 。该算法的提出为改进f i n d f p o f 算法 提供了理论基础。 江苏大学硕士学位论文 5 提出基于加权最大频繁模式的孤立点检测算法( f i n d w m f p o f ) 。该算 法以最大频繁模式代替f i n d f p o f 算法中的频繁模式，有效降低了数据的处理规 模。实验结果表明，以l c m i f 算法挖掘最大频繁模式，可使f i n d w m f p o f 算法 对高维数据的孤立点检测具有更好的可扩展性，并能有效的检测高维数据的孤立 点。 关键词：平均密度高维数据最大频繁项目集孤立点检测加权最大频繁孤 立因子 江苏大学硕士学位论文 a b s t r a c t o u t l i e rd e t e c t i o ni sa ni m p o r t a n ta s p e c to fd a t am i n i n g ，w h i c hh a sg e tm o r e d e p t hr e s e a r c hb e c a u s eo fi t su n i q u ek n o w l e d g ed i s c o v e r yf u n c t i o n s t o d a y ，t h e r ea r e l o t so fe f f i c i e n to u t l i e rd e t e c t i o na l g o r i t h m sw h i c ha r ew i d e l yu s e di nf i n a n c i a lf r a u d d e t e c t i o n , n e t w o r ki n t r u s i o nd e t e c t i o n , e c o s y s t e m si m b a l a n c e ，w e a t h e rf o r e c a s ta n d o t h e rr i s kc o n t r o la r e a s b u t ，w i t ht h ec o n s t a n te x p a n s i o no ft h es c o p eo fa p p l i c a t i o n ， t r a d i t i o n a lo u t l i e rd e t e c t i o na l g o r i t h m sh a v ee n c o u n t e r e ds o m ei n s u r m o u n t a b l e o b s t a c l e s f o ri n s t a n c e ：t h ea l g o r i t h m se f f i c i e n ti su n a b l et om e e tl a r g e s c a l ed a t a s e t s ；t os e l e c tt h ea l g o r i t h m sp a r a m e t e r si sd i f f i c u l tw h i c hl e a dt oa nu n s t a b l er e s u l t ； t h ea l g o r i t h mc a nn o tm e e tt h eh i g h - d i m e n s i o n a ld a t ac h a r a c t e r i s t i c s ；a n d , s o0 1 1 t h e s e p a p e r sm a i n l y f o rt h ea b o v ep r o b l e m sd os o m er e s e a r c ho no u t l i e rd e t e c t i o n t e c h n o l o g y f i r s t , w ei n t r o d u c et h et r a d i t i o n a lo u t l i e rd e t e c t i o na l g o r i t h m sa n da n a l y s i st h e m b yc o m p r i s i n g o nb a s eo ft h ea b o v ea n a l y s i sw ep r o p o s e da l la l g o r i t h mb a s e do n a v e r a g ed e n s i t yf o ro u t l i e rd e t e c t i o n ( a d o d ) a d o di sd e s i g nt or e d u c et h eu s e r s d i f f i c u l t i e st os e l e c tt h ep a r a m e t e r s i no r d e rt os o l v et h ed i f f i c u l t i e sf r o mt h e h i 曲一d i m e n s i o n a ld a t ai no u t l i e rd e t e c t i n g ，w ep r o p o s eal i m i t e dc o m p a r i s o na l g o r i t h m f o rm i n i n gm a x i m a lf r e q u e n ti t e ms e t s ( l c 田i na d v a n c e t h e n ，w ei m p r o v et h e f i n d f p o fb yl c m f i ，a n dp r o p o s ea na l g o r i t h mb a s e do nw e i g h tm a x i m a lf r e q u e n t p a t t e r n f o ro u t l i e r d e t e c t i o n ( f i n d w m f p o f ) t h ei m p r o v e da l g o r i t h m i s t i m e - e f f i c i e n t , a n dh a sag o o dd e t e c t i o ne f f e c t t h em a i nw o r kc o v e r s ： 1 t h ee x i s t i n go u t l i e rd e t e c t i o na l g o r i t h m sa r ei n t r o d u c e da n da n a l y z e d t h e i r c o m l n o nd e f i c i e n c i e s ：t h ea l g o d t h m sa r et h el a c ko fa u t o m a t i o nf o rs e l e c t i n gt h e p a r a m e t e r s 2 p r o p o s ea d o da n dp r o v ei t se f f e c t i v e n e s sb ye x p e r i m e n t s a d o dc a n d e c r e a s et h ed i f f i c u l t i e sf o ru s e ft os e l e c tt h ep a r a m e t e r sa n dh a sa g o o dd e t e c t i o n e f f e c t 3 t h eh i g h - d i m e n s i o n a ld a t ac h a r a c t e r i s t i c sa n dt h e i re f f e c t st ot h et r a d i t i o n a l 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 ea n a l y z e d t h ep a p e ra n a l y s i sa n dc o m p a r et h ee x i s t i n g l l i g h d i m e n s i o n a lo u t l i e rd e t e c t i o na l g o r i t h m s w ea n a l y s i sa n dc o m p a r et h ee x i s t i n g r n 江苏大学硕士学位论文 h i g h - d i m e n s i o n a lo u t l i e rd e t e c t i o na l g o r i t h m sa l s o a n dp o i n to u tt h el a c ko f e f f i c i e n c yo ft h e m 4 w ep r o p o s el c m f ia n di n t r o d u c et h er e l e v a n td e f i n i t i o n s , n l e o r e m a n d p r o v i s i o n t h e s ep r o v i d eat h e o r e t i c a lb a s i sf o ri m p r o v i n gt h ef i n d f p o f 5 w ep r o p o s ef i n d w m f p o f f i n d w m f p o fi n s t e a dm a x i m a lf r e q u e n tp a t t e m t of r e q u e n tp a t t e mw h i c hr e d u c et h es c a l eo ft h ed a t as e t se f f e c t i v e l y u s i n gl c m i f t om i n i n gm a x i m a lf r e q u e n tp a t t e r nc a l lm a k ef i n d w m f f o f g e tb e t t e rs c a l a h i l i t yf o r d e t e c t i n gt h eh i g h - d i m e n s i o n a ld a t a so u t l i e r s k e y w o r c l s ：a v e r a g ed e n s i t y ，h i g h - d i m e n s i o n a ld a t a ，m a x i m a lf r e q u e n t i t e m s e t s ，o u t l i e rd e t e c t i o n , w m f p o f i v 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密 学位论文作者答名1 司为廖 沙1 年lz 月，分日 指导教师签名：豸姒七乏 一) 卿年，? 月侈日 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已注明引用的内容以外，本论 文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：司勿亏 日期：畛年f 月，彳日 江苏大学硕士学位论文 1 1 研究背景 第一章绪论 1 1 1 数据挖掘技术的产生与发展 数据挖掘“1 指的是从大量的数据中提取人们感兴趣的知识，这些知识是隐含 的、事先未知的、并且潜在有用的信息。数据挖掘是目前国际上数据库和信息决 策领域的最前沿研究方向之一，引起了学术界和工业界的广泛关注。一些国际上 高级别的工业研究实验室，例如瑕ma l m a d e n 和g t e ，众多的学术单位，例如 u cb e r k e l e y ，都在这个领域开展了各种各样的研究计划。研究的主要目标是发 展有关的方法论、理论和工具，以支持从大量数据中提取有用的和让人感兴趣的 知识和模式。 数据挖掘，也叫数据库中知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ， k d d ) 。k d d 一词首次出现在1 9 8 9 年8 月举行的第1 l 届国际联合人工智能学 术会议上。随着k d d 在学术界和工业界的影响越来越大，国际k d d 组委会于 1 9 9 5 年把专题讨论会更名为国际会议，在加拿大蒙特利尔市召开了第一届k d d 国际学术会议，以后每年召开一次。迄今为止，由美国人工智能协会主办的k d d 国际研讨会已经召开了1 2 次，规模由原来的专题讨论会发展到国际学术大会。 除了美国人工智能协会主办的k d d 年会外，还有许多的数据挖掘年会，包 括p a k d d ，p k d d ，s i a m - d a t am i n i n g ，等。p a k d d ( p a c i f i c - a s i ac o n f e r e n c e ； o nk n o w l e d g ed i s c o v e r ya n dd a t am i n i n g ) 是亚太知识发现和数据挖掘会议，从 1 9 9 7 年到现在已经召开了1 1 届。p k d d ( e u r o p e a ns y m p o s i u mo np r i n c i p l e so f d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y ) 是欧洲数据挖掘讨论会，现一般伴随 e c m l ( e u r o p e a n c o n f e r e n c eo nm a c h i n el e a r n i n g ) 欧洲机器学习讨论会召开，也 是从1 9 9 7 年开始，到目前已经召开了1 1 届。s i a m d a t am i n i n g ( s o c i e t yf o r i n d u s t r i a la n da p p l i e dm a t h e m a t i c s ) 是s i a m 组织召开的数据挖掘讨论会，2 0 0 1 年4 月召开第1 届讨论会，专注于科学数据的数据挖掘。此外，数据库、人工智 能、信息处理、知识工程等领域的国际学术刊物也纷纷开辟了k d d 专题或专刊。 江苏大学硕士学位论文 1 1 2 数据挖掘的分类与任务 按照挖掘结果的模式，数据挖掘任务可以分为两大类：描述性和预测性。描 述性数据挖掘对数据的一般特性进行描述。预测性数据挖掘通过对现有数据进行 分析推理，对未来的行为进行预测。具体来说可以分为关联分析、聚类分析、分 类、预测、时序模式、异常分析等。 ( 1 ) 关联分析( a s s o c i a t i o na i l a l v s i s ) 关联规则挖掘嘲是由a g r a w a ! 等人首先提出的。两个或两个以上变量的取值 之间存在某种规律性，就称为关联。数据关联是数据库中存在的一类重要的、可 被发现的知识。关联分为简单关联、时序关联和因果关联。关联分析的目的是找 出数据库中隐藏的关联网。一般用支持度和可信度两个阀值来度量关联规则的相 关性，还不断引入兴趣度、相关性等参数，使得所挖掘的规则更符合需求。 ( 2 ) 聚类分析( c l u s t e r i n g ) 聚类是把数据按照相似性归纳成若干类别，同一类中的数据彼此相似，不同 类中的数据相异。聚类分析可以建立宏观的概念，发现数据的分布模式，以及可 能的数据属性之间的相互关系。 ( 3 ) 分类( c l a s s i f i c a t i o n ) 分类就是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类 的内涵描述，并用这种描述来构造模型，一般用规则或决策树模式表示。分类是 利用训练数据集通过一定的算法而求得分类规则。分类可被用于规则描述和预 测。 ( 4 ) 预测( p r e d i c a t i o n ) 预测是利用历史数据找出变化规律，建立模型，并由此模型对未来数据的种 类及特征进行预测。预测关心的是精度和不确定性，通常使用预测方差来度量。 ( 5 ) 时序模式( t i m e - s e r i e sp a t t e r n ) 时序模式是指通过时间序列搜索出的重复发生概率较高的模式。与回归一 样，它也是用己知的数据预测未来的值，但这些数据的区别是变量所处时间的不 同。 ( 6 ) 异常分析( o u t l i e ra n a l v s i s ) 在异常中包括很多有用的知识，数据库中的数据存在很多异常情况，发现数 2 江苏大学硕士学位论文 据库中数据存在的异常情况是非常重要的。异常检测的基本方法就是寻找观察结 果与参照之问的有很大差别的对象。 1 2 孤立点检测技术发展及研究现状 孤立点检测，也称异常检测，是数据挖掘的一个新的热点。目前，孤立点检 测主要关注异常的应用驱动，已经广泛应用于金融欺诈检测、网络入侵检测、生 态系统、医疗卫生、天文物理等领域。 从2 0 世纪8 0 年代起，孤立点发现问题就在统计学领域里得到广泛研究，通 常用户用某个统计分布对数据点进行建模，再以假定的模型，根据点的分布来确 定是否异常。许多针对不同分布的异常测试方法发展起来，它们分别适用于不同 的情形：数据分布状况；数据分布参数是否已知；异常数据数量 异常 数据类型( 高于或低于一般抽样值) 。这些方法的最大缺陷是：在许多情况下，用 户并不知道这个数据的分布。而且现实数据也往往不符合任何一种理想状态的数 学分布。 j o h n s o n 等人提出了基于深度的算法d e e p l o c “，根据算法，每一个数据被 映射到一个k 维数据空问上的点，并且每个点被赋予一个特定定义的“深度”， 并根据不同的深度将数据划分成不同层次。基于统计学的结论，异常往往存在于 较“浅”的层次中。由于基于深度的算法要求计算k 维数据空间的凸闭包，时间 复杂度为。协。实际上，仅仅当k = l ，2 ，3 时，算法性能可以忍受。 a r g a w a l 和r a g a r a n 在1 9 9 6 年提出过“序列异常”的概念“1 。他们采用这样 个机制：扫描数据集并观测一系列相似数据，当发现一个数据点明显不同于前 面的序列，这样的点就被认为是异常数据。这个算法复杂度与数据集的大小呈线 性关系，有优异的计算性能。但是序列异常在对异常存在的假设太理想化，对现 实复杂数据效果不太好。 k n o r r 和n g 5 】在1 9 9 8 年提出了基于距离的孤立点发现算法。r a s t o g i 和r a m a - s w a m 改进了他们的孤立点度量，提出了 最近邻的定义嘲。 在聚类算法研究中，如c l a r a n s ，d b s c a n ，b i r c h 都具有一定的噪声处理能 力。但是聚类中的噪声和孤立点在概念上还是有些偏差的。噪声是定义在聚类基 础之上，即噪声是不隶属于任何聚类的数据；而孤立点的定义不依赖于是否存在 江苏大学硕士学位论文 聚类。而且这些算法出发点只是优化聚类查找，而不是孤立点发现。 b r e u n i g 和k r i e g e l 作了将基于密度的聚类算法o p t i c s 与孤立点发现合并到 一起的研究。这个算法的主要计算消耗在聚类的查找上，只需要很小的额外代价 就可以检测到孤立点。这些研究也奠定了基于密度的孤立点定义的产生。在此基 础上，b r e u n i g 和k r i e g e l 给出局部异常因子的概念l o f m 。p a p a d i m i t i r o u 等人提 出的l o c i 算法嘲。这些算法一方面具有d f d j 9 帕以上的时间复杂度；另一方面， 数据集的高维性常造成上述算法失效。 为了克服因“高维数据”带来的孤立点检测困难的问题，a g g 撇l 等人提 出了基于空间投影的孤立点检测算法e v o l u t i o n a r y o u t l i e r s e a r c h 。1 ，w e i 等人提出 了基于超图模型的孤立点检测算法h o t 。，但时间复杂度较高，在处理大数据 集时无法获得令人满意的响应速度。 h c 等人提出了基于频繁模式的孤立点检测算法f i n d f p o f “”，算法给出了新 的孤立点度量频繁模式孤立因子( f r e q u e n tp a t t e r no u t l i e rf a c t o r ，f p o f ) ，认 为频繁模式为通常模式，一个数据中包含的频繁模式越少，则其成为孤立点的可 能性越大。f i n d f p o f 具有高维数据孤立点检测能力，比e v o l u t i o n a r y o u t l i e r s e a r c h 和h o t 时间复杂度要低。 1 3 本文主要工作 本文在广泛阅读国内外数据挖掘、关联分析、孤立点分析等相关文献的基础 上，比较和分析了现有成熟的孤立点检测算法。先对孤立点的定义加以改进，提 出基于平均密度的孤立点检测算法( a na l g o r i t h mb a s e do na v e r a g ed e n s i t yf o r o u t l i e rd e t e c t i o n ，a d o d ) 。a d o d 算法从一个新的视点来发现孤立点，减轻了 用户选择参数的困难，并具有良好的检测效果。然后，针对高维数据的特点，改 进了基于频繁模式的孤立点检测算法f i n d f p o f ，提出了基于加权最大频繁模式 孤立点检测算法f i n d w m f p o f ，该算法引入最大频繁模式代替原算法的频繁模 式，极大降低了算法复杂度。 本文的主要研究内容包括： 1 对传统孤立点检测算法的研究 孤立点检测就是根据孤立点的行为特征，采用适当的检测算法，在数据集中 4 江苏大学硕士学位论文 找到这些孤立点数据并加以标识。因此孤立点检测的核心是孤立点检测算法。本 文对典型孤立点检测算法进行了分析和总结。针对现有孤立点算法的不足，本文 研究了具体算法中孤立点的定义，从一个新的视点来发现孤立点，以减轻孤立点 检测时用户对参数选择的困难，对孤立点检测的算法自动化作了一定的探索。 2 高维数据特性的研究 数据挖掘技术己经在许多领域得到了广泛的应用，在这些应用中，经常会碰 到一些对象，它们可能有几十、几百或成千上万个属性。可以将这些对象表示成 高维属性空间中的点或向量，这样就把客观世界中的对象集用高维数据的集合来 表示，对这种数据进行挖掘就是高维数据挖掘问题。由于高维数据的普遍性，对 高维数据的处理，成为近几年研究的一个热点。本文针对高维数据的特点，分析 了其对孤立点检测算法的影响。为寻求新的高维孤立点检测算法提供了借鉴和事 实依据。 3 对频繁项目集挖掘技术的研究 为了避开“维灾”对孤立点检测的影响，一些研究者们了引入关联规则挖掘 的方法发展了许多新的孤立点检测算法，取得了较好的效果。但这些算法的效率 大多依赖于经典的关联规则挖掘算法的效率。关联规则的挖掘算法主要是对频繁 项目集的发现算法。经典的频繁项目集挖掘算法易产生组合爆炸问题，或需要频 繁的构造复杂的数据结构，常常使得效率低下，难以适用。最大频繁项目集包含 了频繁项目集的所有信息，很多应用只需要发现最大频繁项目集。而对最大频繁 项目集的挖掘至今没有一个直截了当的方法。本文提出了新的最大频繁项目集挖 掘算法一基于有限比较的最大频繁项目集挖掘算法l c m f i 渔l i m i t e dc o m p a r - i s o na l g o r i t h mf o rm i n i n gm a x i m a lf r e q u e n ti t e m s e t g ) ，该算法避开了组合爆炸问 题和构造复杂数据结构的繁琐，并且易于并行实施，有良好的执行效果。 4 对高维数据孤立点发现的研究 孤立点检测的主要应用如信用卡检测、网络入侵检测等，经常遇到的是高维 数据( 通常在1 0 维以上) 。对这种高维数据进行孤立点检测时，会遇到两方面的 问题：算法效率的下降和基于距离和密度的孤立点意义的失效。本文比较、研究 了最新高维孤立点检测算法，对基于频繁模式的孤立点检测算法f i n d f p o f 作了 改进，提出了基于加权最大频繁模式孤立点检测算法f i n d w m f p o f ，该算法使 5 江苏大学硕士学位论文 用最大频繁模式代替原算法中的频繁模式，并利用本文提出的新的最大频繁项目 集挖掘算法l c m f i ，极大降低了的算法的运行规模，并具有较好的检测效果。 1 4 论文结构 论文共分七章，主要内容概要如下： 第一章介绍了本课题的研究背景，简单地介绍了数据挖掘技术及孤立点检测 技术的发展及研究现状。同时给出了本文的主要研究内容和论文结构。 第二章对孤立点进行了概述。介绍了几种典型的孤立点检测算法，并对他们 进行了比较分析。 第三章分析了现有孤立点检测算法在参数选择自动化上的不足，提出基于平 均密度的孤立点检测算法a d o d 。 第四章分析了高维数据的特点及高维对传统孤立点算法的影响。对现有高维 孤立点检测算法进行了概述、分析了其优缺点。 第五章研究最大频繁项目集挖掘算法。提出基于有限比较的最大频繁项目集 挖掘算法l c m f i 。 第六章用i c m f i 算法改进基于频繁模式的孤立点检测算法f i n d f p o f ，提出 基于加权最大频繁模式的孤立点检测算法弛d w 砌f p o f ，用最大频繁模式代替 频繁模式，给出新的孤立点度量因子w m f p o f 的定义。 第七章对全文进行总结，并提出进一步需要开展的工作。 6 江苏大学硕士学位论文 第二章孤立点检测算法分析 孤立点发现是数据挖掘的一个重要研究方面，被用来发现数据集中小的模式 ( 相对于聚类) ，即数据集中明显不同于其它数据的对象。到目前为止，孤立点还 没有一个正式的、为人们所普遍接受的定义。h a w k i n a “2 1 给出了孤立点的本质性 的定义：孤立点是一个观测值，它在数据集中是如此的与众不同，不禁让人怀疑 这些数据并非随机产生，而是产生于完全不同的机制。后来研究者们根据对异常 存在的不同假设，发展了很多孤立点检测算法，大体可以分为基于统计的算法、 基于距离的算法、基于密度的算法、基于偏离的算法以及基于聚类的算法等。 2 1 基于统计的方法 孤立点检测的问题最早在统计领域得到研究“”。对给定的数据集预先假定一 个分布或概率模型，然后根据模型采用不一致性检验来确定孤立点。统计方式发 现孤立点主要有两种方法：( 1 ) 块处理步骤：将所有的有疑问的数据对象当作孤 立点对象或正常数据对象。( 2 ) 连续步骤：将最不可能是孤立点的数据对象首先 进行检验，若此数据是孤立点，其它数据当然也是孤立点；将最可能是孤立点的 数据首先进行检验，若此数据不是孤立点，其它数据当然也不是孤立点。 不一致性检验一般包含两个假设：零假设凰和对立假设h - 。岛是一个命题， 认为数据有同一分布模型f ，即h o ：o i e ，i = 1 ，2 ，疗；如果没有统计学上的显 著证据来拒绝这个假设，那么就接受i 王0 。不一致性检验验证o i 与分布，的数据 相比是否显著的大或小。检验统计量的选取，取决于数据的先验知识。假设统计 量r 己选定，数据对象嘶的统计量为n ，t 的统计分布被建立，计算统计显著性 s p ( v i ) = p r o b ( t , 曲。如果s p ( 叼足够小，检验结果不是统计显著的，则拒绝零假设 i 0 ，反之，不能拒绝零假设。对立假设h 1 ，是描述总体性质的另外一种想法。 认为数据嘶来自另外的分布模型g 。既然0 f 可能在一个模型下是孤立点，在另 一个模型下是非常有效的值，那么结果非常依赖于模型的选择。由此说明对立假 设是非常重要的，它决定了检验的准确性，它有以下几种形式“。： 曲内在的对立分布( i n h e r e n t a l t e r n a t i v e d i s t r i b u t i o n ) ：在内在对立分布中，零 7 江苏大学硕士学位论文 假设被拒绝，所有的数据对象来自于另一个的分布g 的对立假设成立： h 1 ：o i e g ，i = 1 ，2 ，以。f 和g 可能是不同的分布，或者是参数不同的 同一分布。 b 、混合的对立分布( m i x t u r ea l t e r n a t i v ed i s t r i b u t i o n ) ：混合的对立分布是指不 一致的数据对象不是孤立点，但它受到了另外一种分布影响，这种情况 下的对立假设是：h i ：o i ( 1 一r + l g ，f _ 1 ，2 ，弹。 西滑动对立分布：滑动对立分布假设认为所有数据对象( 除较少分布外) 独立来自初始分布f ，剩余数据对象独立来自修改后的分布f ( 参数有 所变化) 。 基于统计学手段检测孤立点的主要缺点是大多数检验是针对单个属性的，而 许多数据挖掘问题要求在多维空间中发现孤立点。而且，统计学方法要求知道数 据集参数( 如数据的分布) 、分布参数( 如均值、标准差等) 。但在实际中，数据分 布往往是未知的。统计学方法也不能确保所有的孤立点被发现，或者观察到的分 布不能合适的被任何标准的分布来模拟和表示。并且用统计学方法进行孤立点检 测需要预先知道孤立点个数，而这在实际应用中往往是难以实现的。 2 2 基于距离的方法 为了解决统计学方法带来的一些限制，研究者们引入了基于距离的孤立点定 义。孤立点检测算法与其定义有密切的联系，因为算法是为发现相应的孤立点而 设计的。即便对于给定的距离度量函数，对孤立点也有不同的定义，以下是使用 较多的几个： a 1 在数据集s 中，0 是一个孤立点，仅当s 中至少有p 部分对象与0 的距 离大于d 。换句话说，如果0 在d 范围内有不多于m 个邻居，则0 是一 个带参数p 和d 的d b ( p ，回孤立点。这里m = n + ( 1 - 力， 为数据对象 的个数“。 协孤立点是数据集中与其第k 个最近邻居的距离最大的前伟个对象”。 c ) 孤立点是数据集中与其k 个最近邻居的平均距离最大的前一个对象“。 以上几个定义尽管不同，但其基础都是基于距离的，即对象间的度量是一致 的，区别在于对孤立点离群程度的度量不同。基于距离的孤立点检测方法与基于 8 江苏大学硕士学位论文 统计的方法相比有几个优点，首先，它不要求用户知道数据集服从哪种统计分布 模型。实际上，对于恰当定义的p 和d ，一个可以被给定的不一致性检验检测出 的孤立点同样可以利用d b ( p ，d ) 检测出；同时，它克服了基于统计的孤立点检 测通常仅能检测单个属性的缺点。 目前已经开发了若干个高效的基于距离的孤立点检测算法”，概述如下： ( 1 ) 基于索引( i n d e x b a s e d ) 的算法 基于索引的算法采用多维的索引结构，如月树、j 树等，来查找每个对象o 在半径d 范围内的邻居。设m 是一个孤立点的d 领域内的最大对象数目。因此， 一旦对象o 的第m + 1 个邻居被发现，o 就不是孤立点。该算法在最坏情况下的 复杂度为d ( 七n 2 ) ，这里k 为数据集维数，n 是数据集中对象的数目。当k 增 加时，基于索引的算法具有良好的扩展性。计算复杂度时没有考虑建立索引的时 间，而建立索引的任务本身是计算密集的。 ( 2 ) 循环一嵌套( n e s t e d 1 0 0 p ，n l ) 算法 循环一嵌套算法的思想是：将内存缓冲区分成大小相同的两块，称为第一块 和第二块，第一块用来保存从没在该块保存过的数据块，同时把数据集划分为若 干块。算法每次读个数据块( 第一次首先将第一个数据块读到内存缓冲区的第 一块) ，并且放到内存缓冲区的第二块中，然后计算这两块中的每对对象间的距 离。对第一块中的每个对象o ，用一个变量c o u n t 记录它的d 距离邻居，一旦它 的d 距离邻居数超过肘，则计数停止，开始处理下一个对象。如果计算完第二块 中的对象后，o 的c o u n t 值仍然不大于m ，则下一次将另一个数据块读到内存缓 冲区的第二块后，继续用o 去与新读入的对象计算距离，并累计其c o u n t 值。 该算法与基于索引的算法有相同的计算复杂度，但它不用建立索引结构，相 比于基于索引的算法中对每个对象逐个计算，输入输出效率有所改善。 ( 3 ) 基于单元( c e l l - b a s e d ) 的算法 基于单元的算法试图避免0 ( k 矛) 的计算复杂度，它的思想是：首先将数 据集划分为边长为l = d 压的单元，每个单元有两个层围绕着它，第一层的厚度 为一个单元，第二层的厚度为i2 i 一11 个单元。该算法逐个单元地检测孤立点， lj 而不是逐个对象检钡8 。对于一个给定的单元，它累计三个计数：单元中对象的数 目c e l l _ c o u n t 、单元和第一层中对象的数目1 1 l a y e r lc o u n t 以及单元和两个层 9 江苏大学硕士学位论文 中对象的数目c e l l + l a y e r l2c o u n t 。 基于单元的算法正是利用了以上单元及其邻居单元的性质，与前面的论述一 致，设 f 是一个孤立点在d 邻域的最大对象数，基于单元的方法通过以下的步 骤发现孤立点： a 1c c u ，单元中的对象都不是孤立点；+ l a y e r l c o u n tm b 、c e l l = ，单元中的所有对象都是孤立点；+ l a y e r l 2c o u n tm c 1 否则，该单元中可能包含着孤立点，这需要逐个对象进行处理，对单元 中的每个对象o ，与其第二层邻居单元中的每个对象比较，若0 的d 邻域 内的对象不超过m ，则0 就是一个孤立点。 基于单元的算法时间复杂度是o + 帕，这里的，“m ( i2 t mi + 1 广，m 是单 元个数，七是数据集维数或属性个数。随着k 的增加，单元的个数肼和单元中的 对象呈指数级增长，e m k n o r r 和r t - n g 通过实验证明，只有当k = 4 时，该 算法的运行时间优于n l 算法。 在上述算法中，输入参数d 与k 很难确定，并且对于不同参数d 、七结果有 很大不稳定性。这就需要用户反复输入d 和k 进行测试，以确定一个满意解。 2 3 基于密度的方法 2 3 1 局部异常定义 以上孤立点定义有一个共同的不足：都采用了一个全局的距离标准作为孤立 点检测的依据。而孤立点概念本身具有一定的“局部”性，即某孤立点是指这一 点与之邻近的聚类相对较远。b r e u n i g 和k r i e g e l 引入了局部异常因子的概念“7 1 ， 并认为一个孤立点不应该是对象的二进制性质( 非此即彼) ，而是某个度量。下面 给出局部异常的定义。 定义2 1 对象p 的缸距离 对任意的自然数k ，定义p 的b 距离( k - d i s t a n c e ( p ) ) ，为p 到它的第七个最近 邻o 之间的距离，这里的o 满足： a ) 至少存在k 个对象o i d - p ) ，使得d p ，o ) g ( p ，0 ) ，并且 b ) 至多存在缸1 个对象0 1 e d 一扫) ，使得d ( p ，o g d ( p , o ) 。 定义2 2 对象p 的缸距离邻域 江苏大学硕士学位论文 给定p 的缸距离k - d i s t a n c e 4 p ) 的缸邻域n m 。o ) ( 力包含所有除p 外与p 的 距离不超过如d i s t a 峨的对象，即， r e a c h - d i s t k ( p , d ) = m a x k - d i s t a n c e ( o ) ，d 慨 ，在后面的讨论中m i n p t s 表示k 卜，7 一 2 ， ( p 卜f 些 瓦- l q 。2 即对象p 的局部可达密度( l o c a lr e a c h a b l ed i s t a i 雠) 为对象p 与它的肘汛p 括 三( 加专掣r ( 2 s ) 对象p 的局部异常因子( 1 0 c a lo u t l i e rf a c t o r ，l o f ) 表示p 的异常程度，局 对低维数据，可以利用网格( g r i d ) 的方法来作k - n n 查询，整个计算时问 1 1 江苏大学硕士学位论文 为d o ) ； 对中维数据或中高维数据，必须采用索引结构如量树“”等，使得作k - n n 查 询的时间为o ( 1 0 9 n ) ，整个计算时间为o ( n l o g n ) 对特高维数据，索引结构不再有效，时间复杂度提高到o ( n 2 ) 。 第二步：利用物化的数据库m ，计算每个点的局部异常因子。在该步的计算 中，需要扫描数据库两次。第一遍扫描，计算每个点的局部可达密度，第二遍计 算出每个点的局部异常因子。因此这一步的时间复杂度为o ( m 。 基于密度的孤立点检测给出了对象是孤立点程度的定量度量，并且即使数据 具有不同的密度区域也能够很好的处理。与基于距离的方法一样，这些方法具有 2 ) 的时间复杂度，对于低维数据，使用专门的数据结构能将它降低到o ( n l o g n ) 。 但其参数的选择一般是困难的。 2 4 基于偏离的方法 基于偏离的孤立点检测不采用统计检验或基于距离的度量值来确定孤立点。 而是通过检查一组对象的主要特征来确定孤立点唧1 。如果一个对象的特征与给定 的描述过分“偏离”，则认为该对象是孤立点。基于偏离的孤立点检测方法主要 有序列异常技术和o l a p 数据立方体技术1 2 种。 ( 1 ) a r g a w a l 等提出的序列异常技术( s e q u e n t i a le x c e p t i o n t e c h n i q u e ) 模仿了 人类的思维方式，在观察一个连续的序列后，即使不清楚数据的规则，也能快速 发现其中一项数据与其他数据明显不同。给定雄个对象的集合s ，可以建立一个 子集合的序列， s l ，品 ，这是2 m 三d 2 ( 3 4 ) 假设若存在点a y ) 满足( 3 。4 ) 式，且a ( 五力p | 4 暑i ：阿：j ：巧 e s s ， | a 墨l = x - d ) 2 + y 2 = 乒2 一疵+ 号+ y 2 e 3 6 ， 则由公式计算阻p l i ，d 。p 2 l ，两者中至少有一个距离大于矗 这与集合p 的直径为d 矛盾! 同样( 3 3 ) 式中，为了与平均密度的定义一致，在计算对象密度毋时，仍 将有效直径延长至原来的倍。 以上二维空间的平均密度的概念同样适用于三维或多维空间e 3 3a d o d 算法描述 首先对数据集t 进行标准化后，计算 个对象两两之间的距离奶，形成距 离矩阵r ， 胄- 畦畦j 西 d 犁d 2 ，2 d 2 或j 吱，2 或， ( 3 7 ) 通过一次扫描r ，分别计