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

1、几种常用的异常数据挖掘方法,在数据挖掘的过程中,数据库中可能包含一些数据对象,它们与数据的一般行为或模型不一致,这些数据对象被称为异常点,对异常点的查找过程称为异常数据挖掘,它是数据挖掘技术中的一种. 异常数据挖掘又称孤立点分析、异常检测、例外挖掘、小事件检测、挖掘极小类、偏差检测等.孤立点可能是“脏数据”,也可能是与实际对应的有意义的事件. 从知识发现的角度看,在某些应用里,那些很少发生的事件往往比经常发生的事件更有趣、也更有研究价值,例外的检测能为我们提供比较重要的信息,使我们发现一些真实而又出乎预料的知识. 因此,异常数据的检测和分析是一项重要且有意义的研究工作。,异常数据挖掘的简介,异

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

3、方法挖掘异常点数据. 对数据模式的不同定义,以及数据集的构成不同,会导致不同类型的异常点数据挖掘, 实际应用中根据具体情况选择异常数据的挖掘方法.,基于统计的方法,利用统计学方法处理异常数据挖掘的问题已经有很长的历史了,并有一套完整的理论和方法.统计学的方法对给定的数据集合假设了一个分布或者概率模型(例如正态分布) , 然后根据模型采用不一致性检验来确定异常点数据. 不一致性检验要求事先知道数据集模型参数(如正态分布) ,分布参数(如均值、标准差等) 和预期的异常点数目.,不一致性检验是如何进行的?,工作假设(working hypothesis) 即零假设: H。： O F, i = 1 ,

4、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 )足够的小, 那么检验结果不是统计显著的, 则Oi是不一致的,拒绝工作假设,反之,不能拒绝假设.对立假设是描述总体性质的另外一种想法, 认为数据Oi 来自另一个分布模型G. 对立假设在决定检验能力(即当Oi

5、 真的是异常点时工作假设被拒绝的概率) 上是非常重要的, 它决定了检验的准确性等.,i,1,i,目前利用统计学研究异常点数据有了一些新的方法,如通过分析统计数据的散度情况,即数据变异指标,来对数据的总体特征有更进一步的了解,对数据的分布情况有所了解,进而通过数据变异指标来发现数据中的异常点数据. 常用的数据变异指标有极差、四分位数间距、均差、标准差、变异系数等等, 变异指标的值大表示变异大、散布广;值小表示离差小,较密集.,用统计学的方法检测异常点数据的有效性如何呢?,一个主要的缺点是绝大多数检验是针对单个属性的,而许多数据挖掘问题要求在多维空间中发现异常点数据. 而且,统计学方法要求关于数据

6、集合参数的知识,例如数据分布. 但是在许多情况下,数据分布可能是未知的. 当没有特定的分布检验时,统计学方法不能确保所有的异常点数据被发现,或者观察到的分布不能恰当地被任何标准的分布来模拟.,基于距离的方法,什么是基于距离的异常点检测? 如果数据集合S 中独享至少有p 部分与对象o 的距离大于d ,则对象o是一个带参数的p 和d 的基于距离的( DB ) 的异常点, 即DB ( p , d) . 换句话说, 不依赖于统计检验,我们可以将基于距离的异常点看作是那些没有“足够多”邻居的对象, 这里的对象是基于距给定对象的距离来定义的. 与基于统计的方法相比,基于距离的异常点检测拓广了多个标准分布的

7、不一致性检验的思想. 基于距离的异常点检测避免了过多的计算.,目前比较成熟的基于距离的异常数据挖掘的算法有:,基于索引的算法( Index - based) : 给定一个数据集合,基于索引的算法采用多维索引结构R- 树, k - d树等,来查找每个对象在半径d范围内的邻居. 假设M 为异常点数据的d 邻域内的最大对象数目. 如果对象o 的M + 1 个邻居被发现,则对象o 就不是异常点. 这个算法在最坏情况下的复杂度为O( kn ) , k 为维数, n 为数据集合中对象的数目. 当k 增加时,基于索引的算法具有良好的扩展性. 嵌套- 循环算法(Nested - loop) :嵌套- 循环算法

8、和基于索引的算法有相同的计算复杂度,但是它避免了索引结构的构建,试图最小化I/ O的次数. 它把内存的缓冲空间分为两半,把数据集合分为若干个逻辑块. 通过精心选择逻辑块装入每个缓冲区域的顺序, I/ O 效率能够改善.,2,基于单元的算法(cell - based) :在该方法中,数据空间被划为边长等于d/ (2k ) 的单元. 每个单元有两个层围绕着它. 第一层的厚度是一个单元,而第二层的厚度是2k - 1 . 该算法逐个单元地对异常点计数, 而不是逐个对象地进行计数. 对于一个给定的单元, 它累计三个计数单元中对象的数目(cell_count) ,单元和第一层中对象的数目(cell_ +

9、_1_cell_count) ,单元和两个层次中的对象的数目(cell_ +_2_cell_count) . 该算法将对数据集的每一个元素进行异常点数据的检测改为对每一个单元进行异常点数据的检测,它提高了算法的效率. 它的算法复杂度是O( ck + n) ,这里的c 是依赖于单元数目的常数, k 是维数. 它是这样进行异常检测的: 若cell_ + _1_cell_count M ,单元中的所有对象都不是异常;若cell_ + _2_cell_count = M ,单元中的所有对象都是异常;否则,单元中的数据某一些可能是异常. 为了检测这些异常点,需要逐个对象加入处理. 基于距离的异常数据挖掘

10、方法要求用户设置参数p 和d , 而寻找这些参数的合适设置可能涉及多次试探和错误.,1/2,1/2,基于偏差的方法,基于偏差的异常数据挖掘方法不采用统计检验或者基于距离的度量值来确定异常对象, 它是模仿人类的思维方式,通过观察一个连续序列后,迅速地发现其中某些数据与其它数据明显的不同来确定异常点对象,即使不清楚数据的规则. 基于偏差的异常点检测常用两种技术:序列异常技术和OLAP 数据立方体技术. 序列异常技术模仿了人类从一系列推测类似的对象中识别异常对象的方式. 它利用隐含的数据冗余. 给定n 个对象的集合S ,它建立一个子集合的序列, S1 , S2 , . , S m ,这里2 m n

11、, 由此,求出子集间的偏离程度, 即“相异度”. 该算法从集合中选择一个子集合的序列来分析. 对于每个子集合,它确定其与序列中前一个子集合的相异度差异. 光滑因子最大的子集就是异常数据集. 这里对几个相关概念进行解释:,(1) 异常集:它是偏离或异常点的集合, 被定义为某类对象的最小子集, 这些对象的去除会产生剩余集合的相异度的最大减少. (2) 相异度函数:已知一个数据集, 如果两个对象相似,相异函数返回值较小, 反之, 相异函数返回值较大;一个数据子集的计算依赖于前个子集的计算. (3) 基数函数:数据集、数据子集中数据对象的个数. (4) 光滑因子:从原始数据集中去除子集, 相异度减小的

12、程度, 光滑因子最大的子集就是异常点数据集.,特点,基于偏差的异常数据挖掘方法的时间复杂度通常为O( n) , n为对象个数. 基于偏差的异常点检测方法计算性能优异, 但由于事先并不知道数据的特性,对异常存在的假设太过理想化,因而相异函数的定义较为复杂, 对现实复杂数据的效果不太理想.,基于密度的方法,基于密度的异常数据挖掘是在基于密度的聚类算法基础之上提出来的. 它采用局部异常因子来确定异常数据的存在与否. 它的主要思想是:计算出对象的局部异常因子,局部异常因子愈大, 就认为它更可能异常; 反之则可能性小.,(1) 对象p的k - 距离( k - distance) :对任意的自然数k ,定

13、义p 的k - 距离( k - distance ( p) ) ,为p 和某个对象o 之间的距离,这里的o 满足:至少存在k 个对象o D p , 使得d ( p , o) d ( p , o) ,并且至多存在k - 1 个对象oD p ,使得d ( p , o) d ( p , o) . (2) 对象p 的k - 距离邻域( Nk - distance) :给定p 的k - 距离k - distance ( p) , p 的k - 距离邻域包含所有与p 的距离不超过k - distance ( p)的对象. (3) 对象p 相对于对象o 的可达距离:给定自然数k ,对象p 相对于对象o 的可

14、达距离为 reach - dist k ( p , o) = max k - distance( o) , d( p , o) . (4) 对象p的局部可达密度(Local Reachable Distance) :对象p 的局部可达密度为对象p 与它的MinPt s - 邻域的平均可达距离的倒数. 对象p 的局部异常因子表示p 的异常程度,局部异常因子愈大,就认为它更可能异常;反之则可能性小. 簇内靠近核心点的对象的算局部异常点因素LOF 接近于1 ,那么不应该被认为是局部异常. 而处于簇的边缘或是簇的外面的对象的LOF 相对较大 .,为了更好地理解，先看一个2-D数据集的例子，如图4所示，

15、该数据集是一个2维数据集，包含502个对象，在聚类C1中有400个对象，在聚类C2中有100个对象，此外还有2个特殊的对象O1和O2，该例中，可以看出C2形成的聚类要比C1稠密,对象Ol和02都应被看作是C2数据集中的异常点，且聚类C1和聚类c2中的对象都是聚类中的数据，而不是异常点既然基于距离的异常点定义能够统一异常点的概念，那么能否找到合适P和d，使得其满足DB(P，d)异常点的定义事实上，利用DB(P，d)的定义，只能发现01是一个异常点，这是因为对C1中的每一个对象q，找不到一个合适的参数P和d来满足使弓最近的邻域中的对象间的距离大于02和C2间的距离，从而保证02是异常点的同时又能保

16、证c2中的对象不是异常点从该例可看出DB(P，d)在某些特定的情况下是准确和充分的，但聚类密度如果存在不同就会出现问题，为了解决这个问题，基于密度模型的局部异常点挖掘算法被提出，从而保证01和02在数据集中都是异常点,高维数据的方法,以上几种异常数据挖掘算法一般都是在低维数据上进行的,对于高维数据的效果并不是很好,基于这个原因,Aggarwal 和Yu提出一个高维数据异常检测的方法. 它把高维数据集映射到低维子空间,根据子空间映射数据的稀疏程度来确定异常数据是否存在. 高维数据的异常点检测的主要思想是:首先它将数据空间的每一维分成个等深度区间. 所谓等深度区间是指将数据映射到此一维空间上后,每一区间包含相等的f = 1/的数据点. 然后在数据集的k 维子空间中的每一维上各取一个等深度区间,组成一个k 维立方体,则立方体中的数据映射点数为一个随机数. 设n( D) 为k 维立方体D 所包含点数, N 为总的点数.,定义稀疏系数s ( D) 如式所示: s ( D) 为负数时, 说明立方体D 中数据点低于期望值, s ( D ) 越小,说明该立方体中数据越稀疏.,数据空间的任一模式可以用m1 m2 mi 来表示. mi 指此数据在第i 维子空间映射区间,可以取值1 到,或者3 ( 3 表示可以为任意映射值) .异常检测问题可以