异常检测算法综述异常检测算法综述异常探测简介异常探测简介什么是异常（什么是异常（outlieroutlier）？）？Hawkins(1980)Hawkins(1980)给出了异常的本质性的定义：给出了异常的本质性的定义：异常是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，异常是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。而是产生于完全不同的机制。聚类算法对异常的定义：聚类算法对异常的定义：异常是聚类嵌于其中的背景噪声。异常是聚类嵌于其中的背景噪声。异常探测算法对异常的定义：异常探测算法对异常的定义：异常是既不属于聚类也不属于背景噪声的点。他们的行为与正常的行为有很大不同。异常是既不属于聚类也不属于背景噪声的点。他们的行为与正常的行为有很大不同。异常探测方法的分类异常探测方法的分类基于统计（基于统计（statistical-based)statistical-based)的方法的方法基于距离基于距离((distance-based)distance-based)的方法的方法基于偏差基于偏差((deviation-based)deviation-based)的方法的方法基于密度基于密度((density-based)density-based)的方法的方法高维数据的异常探测高维数据的异常探测基于统计的方法基于统计的方法在许多情况下，用户并不知道这个数据分布。而且现实数据也往往不符合任何一种理想状态的数学分布；在许多情况下，用户并不知道这个数据分布。而且现实数据也往往不符合任何一种理想状态的数学分布；即使在低维（一维或二维）时的数据分布已知，在高维情况下，估计数据点的分布即使在低维（一维或二维）时的数据分布已知，在高维情况下，估计数据点的分布是极其困难的。是极其困难的。基于距离的方法基于距离的方法KnorrKnorr和和NgNg（（VLDB’199VLDB’19988）提出一种）提出一种基于距离的异常探测方法基于距离的异常探测方法基于距离的异常定义基于距离的异常定义数据集数据集SS中一个对象中一个对象OO称为称为DB(p,DDB(p,D)-)-outlieroutlier，，如果它满足下列性质：数据集如果它满足下列性质：数据集SS中至少中至少p*100%p*100%的对象与的对象与OO的距离大于的距离大于距离距离DD。。采用不同的参数采用不同的参数pp和和DD，，DB(p,DDB(p,D)-)-outlieroutlier可以表示所有的基于统计的异常。可以表示所有的基于统计的异常。基于距离的异常探测的算法基于距离的异常探测的算法基于索引（基于索引（index-basedindex-based））的算法的算法嵌套循环（嵌套循环（nested-loopnested-loop））算法算法基于单元（基于单元（cell-basedcell-based））的方法的方法基于索引的算法基于索引的算法嵌套循环算法嵌套循环算法NLNL将内存缓冲区空间划分成相等的两部分，数据集分成几个大小和每部分缓冲区相等的逻辑块，通过认真选择调入每一部分缓冲区的次序，使将内存缓冲区空间划分成相等的两部分，数据集分成几个大小和每部分缓冲区相等的逻辑块，通过认真选择调入每一部分缓冲区的次序，使I/OI/O次数最小次数最小算法复杂度是算法复杂度是OO（（kNkN22))kk————维数维数NN————数据点数数据点数特点：特点：不需要建立多维索引结构不需要建立多维索引结构较费时较费时基于单元的方法基于单元的方法基于距离的算法小结基于距离的算法小结由于索引建立的开销很大，简单索引算法没有竞争性由于索引建立的开销很大，简单索引算法没有竞争性当当k<=4k<=4时，基于单元的算法在时，基于单元的算法在NN越大时优越性越明显越大时优越性越明显当当k>=5k>=5之后，嵌套循环算法开始显现出优势之后，嵌套循环算法开始显现出优势基于距离的算法的改进基于距离的算法的改进基于距离的算法的改进基于距离的算法的改进RastogiRastogi和和RamaswamyRamaswamy（（SIGMOD’2000SIGMOD’2000））提出了一个提出了一个新的新的基于距离基于距离异常定义异常定义DDnnkk异常异常用用DDkk(p)(p)表示点表示点pp和它的第和它的第kk个最近邻的距离，个最近邻的距离，给定给定dd维空间中包含维空间中包含NN个点的数据集，参数个点的数据集，参数nn和和kk（（自然数），如果满足...
