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

几种常用的异常数据挖掘方法在数据挖掘的过程中,数据库中可能包含一些数据对象,它们与数据的一般行为或模型不一致,这些数据对象被称为异常点,对异常点的查找过程称为异常数据挖掘,它是数据挖掘技术中的一种.异常数据挖掘又称孤立点分析、异常检测、例外挖掘、小事件检测、挖掘极小类、偏差检测等.孤立点可能是“脏数据”,也可能是与实际对应的有意义的事件.从知识发现的角度看,在某些应用里,那些很少发生的事件往往比经常发生的事件更有趣、也更有研究价值,例外的检测能为我们提供比较重要的信息,使我们发现一些真实而又出乎预料的知识.因此,异常数据的检测和分析是一项重要且有意义的研究工作。异常数据挖掘的简介•异常数据挖掘有着广泛的应用,如欺诈检测,用异常点检测来探测不寻常的信用卡使用或者电信服务;预测市场动向;在市场分析中分析客户的极低或极高消费异常行为;或者在医疗分析中发现对多种治疗方式的不寻常的反应等等.通过对这些数据进行研究,发现不正常的行为和模式,有着非常重要的意义.•对异常点数据的挖掘可以描述如下:给定一个n个数据点或对象的集合,以及预期的异常点的数目k,目标是:发现与剩余的数据相比是显著相异的、异常的或者不一致的头k个对象.聚类数据集序列数据集图1数据集中异常点示例异常点数据挖掘的任务可以分成两个子问题:(1)给出已知数据集的异常点数据的定义;(2)使用有效的方法挖掘异常点数据.对数据模式的不同定义,以及数据集的构成不同,会导致不同类型的异常点数据挖掘,实际应用中根据具体情况选择异常数据的挖掘方法.基于统计的方法利用统计学方法处理异常数据挖掘的问题已经有很长的历史了,并有一套完整的理论和方法.统计学的方法对给定的数据集合假设了一个分布或者概率模型(例如正态分布),然后根据模型采用不一致性检验来确定异常点数据.不一致性检验要求事先知道数据集模型参数(如正态分布),分布参数(如均值、标准差等)和预期的异常点数目.不一致性检验是如何进行的?•工作假设(workinghypothesis)即零假设:H。：O∈F,i=1,2,⋯n;•替代假设(alternativehypothesis)即对立假设:H：O∈F,i=1,2,⋯n;•不一致性检验验证Oi与分布F的数据相比是否显著地大(或者小).•假设某个统计量T被选择用于不一致性检验,对象Oi的该统计量的值为Vi,则构建分布T,估算显著性概率SP(Vi)=Prob(TVi).如果某个SP(Vi)足够的小,那么检验结果不是统计显著的,则Oi是不一致的,拒绝工作假设,反之,不能拒绝假设.对立假设是描述总体性质的另外一种想法,认为数据Oi来自另一个分布模型G.对立假设在决定检验能力(即当Oi真的是异常点时工作假设被拒绝的概率)上是非常重要的,它决定了检验的准确性等.i1i目前利用统计学研究异常点数据有了一些新的方法,如通过分析统计数据的散度情况,即数据变异指标,来对数据的总体特征有更进一步的了解,对数据的分布情况有所了解,进而通过数据变异指标来发现数据中的异常点数据.常用的数据变异指标有极差、四分位数间距、均差、标准差、变异系数等等,变异指标的值大表示变异大、散布广;值小表示离差小,较密集.用统计学的方法检测异常点数据的有效性如何呢?一个主要的缺点是绝大多数检验是针对单个属性的,而许多数据挖掘问题要求在多维空间中发现异常点数据.而且,统计学方法要求关于数据集合参数的知识,例如数据分布.但是在许多情况下,数据分布可能是未知的.当没有特定的分布检验时,统计学方法不能确保所有的异常点数据被发现,或者观察到的分布不能恰当地被任何标准的分布来模拟.0s基于距离的方法什么是基于距离的异常点检测?•如果数据集合S中独享至少有p部分与对象o的距离大于d,则对象o是一个带参数的p和d的基于距离的(DB)的异常点,即DB(p,d).换句话说,不依赖于统计检验,我们可以将基于距离的异常点看作是那些没有“足够多”邻居的对象,这里的对象是基于距给定对象的距离来定义的.与基于统计的方法相比,基于距离的异常点检测拓广了多个标准分布的不一致性检验的思想.基于距离的异常点检测避免了过多的计算.d目前比较成熟的基于距离的异常数据挖掘的算法有:•基于索引的算法(Index-based):给定一个数据集合,基于索引的算法采用多维索引结构R-树,k-d树等,来查找每个对象在半径d范围内的邻居.假设M为异常点数据的d–邻域内的最大对象数目.如果对象o的M+1个邻居被发现,则对象o就不是异常点.这个算法在最坏情况下的复杂度为O(kn),k为维数,n为数据集合中对象的数目.当k增加时,基于索引的算法具有良好的扩展性.•嵌套-循环算法(Nested-loop):嵌套-循环算法和基于索引的算法有相同的计算复杂度,但是它避免了索引结构的构建,试图最小化I/O的次数.它把内存的缓冲空间分为两半,把数据集合分为若干个逻辑块.通过精心选择逻辑块装入每个缓冲区域的顺序,I/O效率能够改善.2•基于单元的算法(cell-based):在该方法中,数据空间被划为边长等于d/(2k)的单元.每个单元有两个层围绕着它.第一层的厚度是一个单元,而第二层的厚度是[2k-1].该算法逐个单元地对异常点计数,而不是逐个对象地进行计数.对于一个给定的单元,它累计三个计数———单元中对象的数目(cell_count),单元和第一层中对象的数目(cell_+_1_cell_count),单元和两个层次中的对象的数目(cell_+_2_cell_count).该算法将对数据集的每一个元素进行异常点数据的检测改为对每一个单元进行异常点数据的检测,它提高了算法的效率.它的算法复杂度是O(ck+n),这里的c是依赖于单元数目的常数,k是维数.它是这样进行异常检测的:若cell_+_1_cell_countM,单元中的所有对象都不是异常;若cell_+_2_cell_count=M,单元中的所有对象都是异常;否则,单元中的数据某一些可能是异常.为了检测这些异常点,需要逐个对象加入处理.•基于距离的异常数据挖掘方法要求用户设置参数p和d,而寻找这些参数的合适设置可能涉及多次试探和错误.1/21/2基于偏差的方法•基于偏差的异常数据挖掘方法不采用统计检验或者基于距离的度量值来确定异常对象,它是模仿人类的思维方式,通过观察一个连续序列后,迅速地发现其中某些数据与其它数据明显的不同来确定异常点对象,即使不清楚数据的规则.基于偏差的异常点检测常用两种技术:序列异常技术和OLAP数据立方体技术.•序列异常技术模仿了人类从一系列推测类似的对象中识别异常对象的方式.它利用隐含的数据冗余.给定n个对象的集合S,它建立一个子集合的序列,{S1,S2,⋯.,Sm},这里2≤m≤n,由此,求出子集间的偏离程度,即“相异度”.该算法从集合中选择一个子集合的序列来分析.对于每个子集合,它确定其与序列中前一个子集合的相异度差异.光滑因子最大的子集就是异常数据集.•这里对几个相关概念进行解释:(1)异常集:它是偏离或异常点的集合,被定义为某类对象的最小子集,这些对象的去除会产生剩余集合的相异度的最大减少.(2)相异度函数:已知一个数据集,如果两个对象相似,相异函数返回值较小,反之,相异函数返回值较大;一个数据子集的计算依赖于前个子集的计算.(3)基数函数:数据集、数据子集中数据对象的个数.(4)光滑因子:从原始数据集中去除子集,相异度减小的程度,光滑因子最大的子集就是异常点数据集.特点基于偏差的异常数据挖掘方法的时间复杂度通常为O(n),n为对象个数.基于偏差的异常点检测方法计算性能优异,但由于事先并不知道数据的特性,对异常存在的假设太过理想化,因而相异函数的定义较为复杂,对现实复杂数据的效果不太理想.基于密度的方法•基于密度的异常数据挖掘是在基于密度的聚类算法基础之上提出来的.它采用局部异常因子来确定异常数据的存在与否.•它的主要思想是:计算出对象的局部异常因子,局部异常因子愈大,就认为它更可能异常;反之则可能性小.(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的k-距离邻域(Nk-distance):给定p的k-距离k-distance(p),p的k-距离邻域包含所有与p的距离不超过k-distance(p)的对象.(3)对象p相对于对象o的可达距离:给定自然数k,对象p相对于对象o的可达距离为reach-distk(p,o)=max{k-distance(o),d(p,o)}.(4)对象p的局部可达密度(LocalReachableDistance):对象p的局部可达密度为对象p与它的MinPts-邻域的平均可达距离的倒数.•对象p的局部异常因子表示p的异常程度,局部异常因子愈大,就认为它更可能异常;反之则可能性小.簇内靠近核心点的对象的算局部异常点因素LOF接近于1,那么不应该被认为是局部异常.而处于簇的边缘或是簇的外面的对象的LOF相对较大.为了更好地理解，先看一个2-D数据集的例子，如图4所示，该数据集是一个2维数据集，包含502个对象，在聚类C1中有400个对象，在聚类C2中有100个对象，此外还有2个特殊的对象O1和O2，该例中，可以看出C2形成的聚类要比C1稠密．高维数据的方法•以上几种异常数据挖掘算法一般都是在低维数据上进行的,对于高维数据的效果并不是很好,基于这个原因,Aggarwal和Yu提出一个高维数据异常检测的方法.它把高维数据集映射到低维子空间,根据子空间映射数据的稀疏程度来确定异常数据是否存在.•高维数据的异常点检测的主要思想是:首先它将数据空间的每一维分成φ个等深度区间.所谓等深度区间是指将数据映射到此一维空间上后,每一区间包含相等的f=1/φ的数据点.然后在数据集的k维子空间中的每一维上各取一个等深度区间,组成一个k维立方体,则立方体中的数据映射点数为一个随机数ξ.设n(D)为k维立方体D所包含点数,N为总的点数.•定义稀疏系数s(D)如式所示:•s(D)为负数时,说明立方体D中数据点低于期望值,s(D)越小,说明该立方体中数据越稀疏.•数据空间的任一模式可以用m1m2⋯mi来表示.mi指此数据在第i维子空间映射区间,可以取值1到φ,或者3(3表示可以为任意映射值).异常检测问题可以转化成为寻找映射在k(k作为参数输入)维子空间上的异常模式以及符合这些异常模式的数据.•高维数据中寻找异常模式是非常困难的.一个简单办法是对所有数据维进行组合,来搜索可能异常模式,但是效率极其低下.异常数据挖掘是数据挖掘的重要组成部分,由于其广泛的应用于科学研究、金融欺诈分析、电信计费、医疗保险、网络安全等各个领域,这些年来,在国外,吸引了数据挖掘研究人员的注意.本文根据现有研究理论,着重介绍了使用统计、距离、偏离技术、密度和高维持数据进行异常数据挖掘的方法并分析了其各自的特点.