异常检测算法综述ppt课件.ppt

《异常检测算法综述ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、异常检测算法综述报告人杨风召异常探测简介异常探测是数据挖掘中一个重要方面，用来发现”小的模式”(相对于聚类)，即数据集中间显著不同于其它数据的对象。异常探测应用电信和信用卡欺骗贷款审批药物研究气象预报金融领域客户分类网络入侵检测等什么是异常（outlier）？Hawkins(1980)给出了异常的本质性的定义：异常是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。聚类算法对异常的定义：异常是聚类嵌于其中的背景噪声。异常探测算法对异常的定义：异常是既不属于聚类也不属于背景噪声的点。他们的行为与正常的

2、行为有很大不同。异常探测方法的分类基于统计（statistical-based)的方法基于距离(distance-based)的方法基于偏差(deviation-based)的方法基于密度(density-based)的方法高维数据的异常探测基于统计的方法假设给定的数据集服从一个随机分布（如正态分布等），用不一致性测试（discordancytest）识别异常。存在问题在许多情况下，用户并不知道这个数据分布。而且现实数据也往往不符合任何一种理想状态的数学分布；即使在低维（一维或二维）时的数据分布已知，在高维情况下，估计数据点的分布

3、是极其困难的。基于距离的方法Knorr和Ng（VLDB’1998）提出一种基于距离的异常探测方法基于距离的异常定义数据集S中一个对象O称为DB(p,D)-outlier，如果它满足下列性质：数据集S中至少p*100%的对象与O的距离大于距离D。采用不同的参数p和D，DB(p,D)-outlier可以表示所有的基于统计的异常。基于距离的异常探测的算法基于索引（index-based）的算法嵌套循环（nested-loop）算法基于单元（cell-based）的方法基于索引的算法寻找所有的DB(p,D)-outlier可以通过对最近邻

4、查询或以O为中心的范围查询的回答来实现基于多维索引结构R-Tree或kd-Tree算法复杂度是O（kN2)k——维数N——数据点数缺点：需要建立多维索引结构费时嵌套循环算法NL将内存缓冲区空间划分成相等的两部分，数据集分成几个大小和每部分缓冲区相等的逻辑块，通过认真选择调入每一部分缓冲区的次序，使I/O次数最小算法复杂度是O（kN2)k——维数N——数据点数特点：不需要建立多维索引结构较费时基于单元的方法单元划分数据空间被划分为边长为D/(2k1/2)的单元；每个单元有两个包围层第一层为1倍的单元厚第二层为int（2k1/2-1）

5、+1倍的单元厚确定异常若cell_+_1_layer_count>M，单元中的对象都不是异常；若cell_+_2_layer_count<=M，单元中的所有对象都是异常；否则，单元中的一些对象可能为异常，逐个对象进行处理。算法复杂度是O（ck+N)基于距离的算法小结由于索引建立的开销很大，简单索引算法没有竞争性当k<=4时，基于单元的算法在N越大时优越性越明显当k>=5之后，嵌套循环算法开始显现出优势基于距离的算法的改进Knorr和Ng（VLDB’1998）基于距离的异常探测方法的缺陷输入参数p与D很难确定，并且对于不同参数，结果

6、有很大不稳定性。这就需要用户反复输入p与D进行测试，以确定一个满意解；不能给定异常的程度；算法的复杂度较高。基于距离的算法的改进Rastogi和Ramaswamy（SIGMOD’2000）提出了一个新的基于距离异常定义Dnk异常用Dk(p)表示点p和它的第k个最近邻的距离，给定d维空间中包含N个点的数据集，参数n和k（自然数），如果满足Dk(p’)Dk(p)的点p’不超过n-1个，那么称p为Dnk异常。如果对数据点根据它们的Dk(p)距离进行排序，那么前n个点就被看作异常。改进的基于距离的算法循环嵌套算法(Nested-loop

7、Algorithm)对每个点p，计算它的第k个最近邻的距离Dk(p)，把具有极大Dk值前n个点作为异常。上面的算法每次处理一个点p，那么需要扫描一遍数据库，总共需要扫描N遍（N为数据点数）。基于索引的算法(Index-basedAlgorithm)用如R*-树的空间索引结构存储。基于划分的算法(partition-basedAlgorithm)如果某个点的Dk(p)较小的话，那么不可能是Dnk异常，可以先对数据集进行划分，然后估计每个划分的Dk(p)的上、下界，如果能判定某个划分不可能包含异常的话，那么就可以直接把它删除掉；然后再

8、从剩下的划分（侯选划分）来计算异常。现有的许多聚类算法可以用来划分数据集，如BIRCH。基于偏差的方法Argrawal和Ragaran（KDD’1995）提出一种“序列异常”(sequentialexception)的概念。算法介绍给定n个对象的集