几种常用的异常数据挖掘方法

《几种常用的异常数据挖掘方法》由会员分享，可在线阅读，更多相关《几种常用的异常数据挖掘方法（27页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,几种常用的异常数据挖掘方法,在数据挖掘的过程中,数据库中可能包含一些数据对象,它们与数据的一般行为或模型不一致,这些数据对象被称为,异常点,对异常点的查找过程称为,异常数据挖掘,它是数据挖掘技术中的一种,.,异常数据挖掘又称孤立点分析、异常检测、例外挖掘、小事件检测、挖掘极小类、偏差检测等,.,孤立点可能是“脏数据”,也可能是与实际对应的有意义的事件,.,从知识发现的角度看,在某些应用里,那些很少发生的事件往往比经常发生的事件更有趣、也更有研究价值,例外的检测能为我们提供比较重要的信息,使我们发现一些真实而

2、又出乎预料的知识,.,因此,异常数据的检测和分析是一项重要且有意义的研究工作。,异常数据挖掘的简介,异常数据挖掘有着广泛的应用,如,欺诈检测,用异常点检测来探测不寻常的信用卡使用或者电信服务,;,预测市场动向,;,在市场分析中分析客户的极低或极高消费异常行为,;,或者在医疗分析中发现对多种治疗方式的不寻常的反应等等,.,通过对这些数据进行研究,发现不正常的行为和模式,有着非常重要的意义,.,对异常点数据的挖掘可以描述如下,:,给定一个,n,个数据点或对象的集合,以及预期的异常点的数目,k,目标是,:,发现与剩余的数据相比是显著相异的、异常的或者不一致的头,k,个对象,.,聚类数据集,序列数据集

3、,图,1,数据集中异常点示例,异常点数据挖掘的任务可以分成两个子问题,:,(,1,),给出已知数据集的异常点数据的定义,;,(,2,),使用有效的方法挖掘异常点数据,.,对数据模式的不同定义,以及数据集的构成不同,会导致不同类型的异常点数据挖掘,实际应用中根据具体情况选择异常数据的挖掘方法,.,基于统计的方法,利用统计学方法处理异常数据挖掘的问题已经有很长的历史了,并有一套完整的理论和方法,.,统计学的方法对给定的数据集合假设了一个分布或者概率模型,(,例如正态分布,),然后根据模型采用,不一致性检验,来确定异常点数据,.,不一致性检验要求事先知道数据集模型参数,(,如正态分布,),分布参数,

4、(,如均值、标准差等,),和预期的异常点数目,.,不一致性检验是如何进行的,?,工作假设,(working hypothesis),即零假设,:,H,。：,O,F,i=,1,2,n;,替代假设,(alternative hypothesis),即对立假设,:,H,：,O,F,i=,1,2,n;,不一致性检验验证,Oi,与分布,F,的数据相比是否显著地大,(,或者小,).,假设某个统计量,T,被选择用于不一致性检验,对象,Oi,的该统计量的值为,V i,则构建分布,T,估算显著性概率,S P(V i)=,Prob,(T V i).,如果某个,S P(V i),足够的小,那么检验结果不是统计显著的

5、,则,Oi,是不一致的,拒绝工作假设,反之,不能拒绝假设,.,对立假设是描述总体性质的另外一种想法,认为数据,Oi,来自另一个分布模型,G.,对立假设在决定检验能力,(,即当,Oi,真的是异常点时工作假设被拒绝的概率,),上是非常重要的,它决定了检验的准确性等,.,i,1,i,目前利用统计学研究异常点数据有了一些新的方法,如通过分析统计数据的散度情况,即数据变异指标,来对数据的总体特征有更进一步的了解,对数据的分布情况有所了解,进而通过数据,变异指标,来发现数据中的异常点数据,.,常用的数据变异指标有极差、四分位数间距、均差、标准差、变异系数等等,变异指标的值大表示变异大、散布广,;,值小表示

6、离差小,较密集,.,用统计学的方法检测异常点数据的有效性如何呢,?,一个主要的缺点是绝大多数检验是针对单个属性的,而许多数据挖掘问题要求在多维空间中发现异常点数据,.,而且,统计学方法要求关于数据集合参数的知识,例如数据分布,.,但是在许多情况下,数据分布可能是未知的,.,当没有特定的分布检验时,统计学方法不能确保所有的异常点数据被发现,或者观察到的分布不能恰当地被任何标准的分布来模拟,.,0,s,基于距离的方法,什么是基于距离的异常点检测,?,如果数据集合,S,中独享至少有,p,部分与对象,o,的距离大于,d,则对象,o,是一个带参数的,p,和,d,的基于距离的,(DB),的异常点,即,DB

7、(p,d).,换句话说,不依赖于统计检验,我们可以将基于距离的异常点看作是那些没有“足够多”邻居的对象,这里的对象是基于距给定对象的距离来定义的,.,与基于统计的方法相比,基于距离的异常点检测拓广了多个标准分布的不一致性检验的思想,.,基于距离的异常点检测避免了过多的计算,.,d,目前比较成熟的基于距离的异常数据挖掘的算法有,:,基于索引的算法,(Index-based):,给定一个数据集合,基于索引的算法采用多维索引结构,R-,树,k-d,树等,来查找每个对象在半径,d,范围内的邻居,.,假设,M,为异常点数据的,d,邻,域,内的最大对象数目,.,如果对象,o,的,M+,1,个邻居被发现,则

8、对象,o,就不是异常点,.,这个算法在最坏情况下的复杂度为,O(,kn,),k,为维数,n,为数据集合中对象的数目,.,当,k,增加时,基于索引的算法具有良好的扩展性,.,嵌套,-,循环算法,(Nested-loop):,嵌套,-,循环算法和基于索引的算法有相同的计算复杂度,但是它避免了索引结构的构建,试图最小化,I/O,的次数,.,它把内存的缓冲空间分为两半,把数据集合分为若干个逻辑块,.,通过精心选择逻辑块装入每个缓冲区域的顺序,I/O,效率能够改善,.,2,基于单元的算法,(cell-based):,在该方法中,数据空间被划为边长等于,d/(,2,k ),的,单元,.,每个单元有两个层围

9、绕着它,.,第一层的厚度是一个单元,而第二层的厚度是,2,k -,1,.,该算法逐个单元地对异常点计数,而不是逐个对象地进行计数,.,对于一个给定的单元,它累计三个计数,单元中对象的数目,(,cell_count,),单元和第一层中对象的数目,(cell_+_1_cell_count),单元和两个层次中的对象的数目,(cell_+_2_cell_count).,该算法将对数据集的每一个元素进行异常点数据的检测改为对每一个单元进行异常点数据的检测,它提高了算法的效率,.,它的算法复杂度是,O(ck+n),这里的,c,是依赖于单元数目的常数,k,是维数,.,它是这样进行异常检测的,:,若,cell

10、_+_1_cell_count,M,单元中的所有对象都不是异常,;,若,cell_+_2_cell_count =,M,单元中的所有对象都是异常,;,否则,单元中的数据某一些可能是异常,.,为了检测这些异常点,需要逐个对象加入处理,.,基于距离的异常数据挖掘方法要求用户设置参数,p,和,d,而寻找这些参数的合适设置可能涉及多次试探和错误,.,1/2,1/2,基于偏差的方法,基于偏差的异常数据挖掘方法不采用统计检验或者基于距离的度量值来确定异常对象,它是模仿人类的思维方式,通过观察一个连续序列后,迅速地发现其中某些数据与其它数据明显的不同来确定异常点对象,即使不清楚数据的规则,.,基于偏差的异常

11、点检测常用两种技术,:,序列异常技术,和,OLAP,数据立方体技术,.,序列异常技术模仿了人类从一系列推测类似的对象中识别异常对象的方式,.,它利用隐含的数据冗余,.,给定,n,个对象的集合,S,它建立一个子集合的序列,S,1,S,2,.,S m ,这里,2,m,n,由此,求出子集间的偏离程度,即“相异度”,.,该算法从集合中选择一个子集合的序列来分析,.,对于每个子集合,它确定其与序列中前一个子集合的相异度差异,.,光滑因子最大的子集就是异常数据集,.,这里对几个相关概念进行解释,:,(,1,),异常集,:,它是偏离或异常点的集合,被定义为某类对象的最小子集,这些对象的去除会产生剩余集合的相

12、异度的最大减少,.,(,2,),相异度函数,:,已知一个数据集,如果两个对象相似,相异函数返回值较小,反之,相异函数返回值较大,;,一个数据子集的计算依赖于前个子集的计算,.,(,3,),基数函数,:,数据集、数据子集中数据对象的个数,.,(,4,),光滑因子,:,从原始数据集中去除子集,相异度减小的程度,光滑因子最大的子集就是异常点数据集,.,特点,基于偏差的异常数据挖掘方法的时间复杂度通常为,O(n),n,为对象个数,.,基于偏差的异常点检测方法计算性能优异,但由于事先并不知道数据的特性,对异常存在的假设太过理想化,因而相异函数的定义较为复杂,对现实复杂数据的效果不太理想,.,基于密度的方

13、法,基于密度的异常数据挖掘是在基于密度的聚类算法基础之上提出来的,.,它采用局部异常因子来确定异常数据的存在与否,.,它的主要思想是,:,计算出对象的局部异常因子,局部异常因子愈大,就认为它更可能异常,;,反之则可能性小,.,(,1,),对象,p,的,k-,距离,(k-,distance):,对任意的自然数,k,定义,p,的,k-,距离,(k-,distance,(p),为,p,和某个对象,o,之间的距离,这里的,o,满足,:,至少存在,k,个对象,o,D,p,使得,d(p,o),d(p,o),并且至多存在,k-,1,个对象,o,D,p,使得,d(p,o)d(p,o).,(,2,),对象,p,

14、的,k-,距离邻域,(,Nk,-,distance):,给定,p,的,k-,距离,k-,distance,(p),p,的,k-,距离邻域包含所有与,p,的距离不超过,k-,distance,(p),的对象,.,(,3,),对象,p,相对于对象,o,的可达距离,:,给定自然数,k,对象,p,相对于对象,o,的可达距离为,reach-dist k(p,o)=,max,k-,distan,ce(o),d(p,o).,(4),对象,p,的局部可达密度,(,Local Reachable Distance):,对象,p,的局部可达密度为对象,p,与它的,MinPt,s-,邻域的平均可达距离的倒数,.,对

15、象,p,的局部异常因子表示,p,的异常程度,局部异常因子愈大,就认为它更可能异常,;,反之则可能性小,.,簇内靠近核心点的对象的算局部异常点因素,LOF,接近于,1,那么不应该被认为是局部异常,.,而处于簇的边缘或是簇的外面的对象的,LOF,相对较大,.,为了更好地理解，先看一个,2-D,数据集的例子，如图,4,所示，该数据集是一个,2,维数据集，包含,502,个对象，在聚类,C1,中有,400,个对象，在聚类,C2,中有,100,个对象，此外还有,2,个特殊的对象,O1,和,O2,，该例中，可以看出,C2,形成的聚类要比,C1,稠密,对象,Ol,和,02,都应被看作是,C2,数据集中的异常点

16、，且聚类,C1,和聚类,c2,中的对象都是聚类中的数据，而不是异常点既然基于距离的异常点定义能够统一异常点的概念，那么能否找到合适,P,和,d,，使得其满足,DB(P,，,d),异常点的定义事实上，利用,DB(P,，,d),的定义，只能发现,01,是一个异常点，这是因为对,C1,中的每一个对象,q,，找不到一个合适的参数,P,和,d,来满足使弓最近的邻域中的对象间的距离大于,02,和,C2,间的距离，从而保证,02,是异常点的同时又能保证,c2,中的对象不是异常点从该例可看出,DB(P,，,d),在某些特定的情况下是准确和充分的，但聚类密度如果存在不同就会出现问题，为了解决这个问题，基于密度模型的局部异常点挖掘算法被提出，从而保证,01,和,02,在数据集中都是异常点,高维数据的方法,以上几种异常数据挖掘算法一般都是在低维数据上进行的,对于高维数据的效果并不是很好,基于这个原因,Aggarwal,和,Yu,提出一个高维数据异常检测的方法,.,它把高维数据集映射到低维子空间,根据子空间映射数据的稀疏程度来确定异常数据是否存在,.,高维数据的异常点检测的主要思想是,:,首先它将数据空间的每