毕业论文网
此文是一篇检测算法论文范文,为你的毕业论文写作提供有价值的参考。
高维数据集之中基于距离的离群快速检测算法
摘 要：针对现有的挖掘算法并不适用于大规模的高维数据集的问题,给出了一种针对高维数据集的RBRP算法,能够快速检测出数据集中基于距离的异常,该算法将对数线性作为数据点个数的函数,线性作为维数的函数.实验结果表明,RBRP算法始终优于ORCA算法,且是一种针对高维数据集的最优的基于距离的异常检测算法,并且RBRP算法的优势往往超过ORCA算法一个数量级.
关键词：数据挖掘；算法；离群；高维数据集；近似K-近邻；聚类
中图分类号：TP311.13；TP301.6文献标志码：ADOI：10.3969/j.issn.1674-9146.2017.11.067
数据挖掘的一个普遍问题是如何在数据集中自动搜寻离群或异常点.离群点是一些在给定的数据模型中出现可能性极小的点.由于离群和异常点比较少见,因此,它们可以用来表示数据的不正确、收集错误或恶意内容.通过与相邻数据点的距离来定义离群值,已被证明是一种有效的非参数的离群检测方法,然而现有的挖掘算法并不适用于大规模的高维数据集,笔者对其进行了改进.
1离群快速检测算法的研究背景与目的
目前存在一些异常检测的方法,其中一类是基于模型的异常检测方法.该类算法首先假设数据是遵循参数分布的.然而这种方法即使是在适度的高维空间其检测效果也不理想,而且也很难找到合适的模型.为了克服这些局限性,研究者们已经开始着手研究非参数方法,这些方法使用与某点最近邻居点的距离来衡量异常点.基于距离的异常检测已经被证明是一种有效的非参数检测方法,但是,这个过程也是非常耗时的.嵌套循环（NestedLoop,NL）算法[1]通常需要o（N2）的时间,其中N是数据点的数量.
为了克服这个问题,在过去几年中,研究者们已经提出了若干解决方案,其中包括使用空间索引结构（KD-trees,R-trees或X-trees）的快速近邻计算方法以及利用聚类来分割特征空间的方法.但遗憾的是这些方法不能很好地解决多维数据的问题.因此,简单的NL算法仍然是公认的有效解决高维数据集的基础方案.
NL算法的主要思想是：对于数据集D中的每个数据点,当算法扫描该数据集时追踪其k个最近邻的邻居.当一个数据点与第k个最近邻的邻居的距离小于C时,该数据点不再作为一个离群点,此时算法从下一个数据段开始检测.由于数据集中记录了更多的数据点,因此算法能发现更多的额外离群,这种简便方法提高了离群检测的效率.
最先进的基于距离的异常检测最优算法——ORCA算法使用NL算法对数据集进行预处理.ORCA算法通过使用基于磁盘的重排（Shuffling）算法在线性时间内将数据集D随机化.这种随机机制允许NL算法快速处理大量非异常点,该方法的提出者给出了ORCA算法作用在几个真实和合成数据集上的次平方时间性能（通常远低于二次曲线,但不完全是对数线性）.
为了进一步提高基于距离的异常检测算法在大型高维数据集中的效率,笔者做了如下研究,对算法作出了改进.首先,研究在何种条件下ORCA算法不能提供近线性时间性能.其次,给出了基于距离的异常检测快速挖掘的递归分级和重投影（RecursiveBinningandRe-Projection,RBRP）算法,该算法有利于快速搜寻出邻居节点.最后,证明了RBRP算法的收敛性.该算法可以有效地处理高维数据集中的数百万个数据点,并优于ORCA算法,并且性能优势一般超过了一个数量级.事实证明,该算法解决的数据点数目是非线性的,而作为一个功能的数目方面是线性的[2-7].
2异常检测算法
2.1ORCA算法的缺点
为了简单说明,笔者假设要在数据集中找到距离其最近邻居的距离最大前n个的离群点.下面来看看处理一个非异常数据点（例如x）时需要进行的距离计算的次数.上述问题可以看成一组独立的伯努利实验,其中一个实验不断地借鉴实例,直到有一个实例满足条件（一个数据点在截止阈值内）.用∏（x）表示随机选取的数据点落在截止阈值内的概率,y是一个随机变量,表示直到取得一个成功时进行的试验次数.
为了收敛于一个近线性时间,E（Y）必须是一个常数,这是ORCA算法收敛于接近线性时间的核心前提.但是正如接下来能够看到的情况,这种结论并不是始终成立的.简单阐述一个例子,假设在面积大小为N的区域内有N个均匀分布的数据点,设法回答下列问题：如果要在这个区域内随机挑选一个点X,要使得∏（x）是一个常数,此时截止阈值c的预期值应是多少？直观地说,应该使∏（x）为常数、半径为c、中心为x、面积为πc2的圆收敛于o（N）,换言之,c应收敛于o（N）.但是不仅对于均匀分布的数据集,而且对于任意的数据集都很难期望截断阈值c快速收敛到如此大的值.总的来说,只有当截止距离很快地收敛到∏（x）这样大常数时,ORCA算法才表现出接近线性的收敛行为,也只有当数据集有大量而不是少数几个点时这种情况才会发生.而当数据集由几个分布混合而成并不包含那么多的点时,ORCA算法的复杂性就接近于二次方.
2.2RBRP算法
正如在第一部分中指出,为了找到基于距离的离群使用了NL算法,该算法需要在截止阀值c内找到k个数据点,这k个数据点被称为近似邻居节点.快速异常检测的关键是准确发现一个数据点的k近似近邻.这个目标不同于大多数试图高效地找到k个最近邻居的方法,这个方法开销更大.为了弥补ORCA算法和其他现有方法的缺陷,笔者提出了RBRP算法,这是一种在高维数据集中快速挖掘基于距离的异常值的算法.RBRP算法可分为两个阶段,以下分别予以介绍.
2.2.1RBRP算法的第1阶段
该阶段的目标是将数据集分为块,空间中接近的点很可能被分配到相同的块中.生成这种数据块的一种候选方法是使用k均值（k-means）算法等来对数据进行聚类,以发现大量的小簇,每个小簇可以被看成是一个数据块.但是这一过程需要人为指定簇的数目,并不能保证所有数据点以平等的频率被组合,因此这类方法并不适用.另一种获选方法是使用聚类算法,如BIRCH算法,这在某种意义上类似于Ramaswamy,Rastogi和Shim在文献[8]中提出的方法,不过这种做法并不适用于大规模高维数据.RBRP算法对数据集的分区过程见第69页图1.这是一个被称为分裂层次聚类的递归过程,在递归的每个阶段,算法迭代地将数据分成k个分区.这个迭代分割类似于k-means算法中的分割步骤.首先,从k个随机中心开始,将每个点分配到最近的中心以创建k个分区.然后,分别为这k个分区找到k个中心,并以迭代方式继续进行固定次数的迭代.一旦完成了每个分区的迭代,分区的大小如果大于用户定义的阈（Binsize）,又会继续迭代,这种分区策略使得空间中很接近的点很可能被划分到同一个分区.由于在下一阶段中将依次扫描某个数据点的每个分区以找到该点的近似最近邻,因此,在顺序扫描过程中为了便于快速收敛到近似的近邻,算法按照数据点在分区主成分中的投影顺序重新组织分区中的每个数据点,每个分区的主要成分为最大方差的轴.这种分区内的重组使得通过对分区顺序扫描能够快速收敛到近似最近邻.这是因为当对数据点按照其在主要成分上的投影进行排序时,通常希望找到数据点在其领域内的近似最近邻.
复杂性分析：经过计算可知,RBRP算法的第1阶段预期的平均时间复杂度为o（NlogN×d）,其中d是数据的维度.
2.2.2RBRP算法的第2阶段
在该阶段,笔者使用扩展的NL算法来检测已经整理成分区的数据集中的离群点.对于每个数据点,算法在分区的下一个连续位置开始寻找近似的近邻.一旦到达分区的末端则绕到分区的开始处,然后继续对分区的其余区间进行搜索.如果整个区间已被搜查或者在这个分区内没有发现k个近似最接近邻,则切换到下一个最接近区间继续寻找近似最接近邻.重复迭代以上搜索过程,直到k个近似最接近邻被发现.
复杂性分析：最坏的情况下第2阶段的时间复杂度为o（N2）.然而,笔者期望在同一个分区中找到一个正常点的近似最近邻,为找到离群点,算法需要扫描所有的区间.但这种情况几乎不可能发生,因为理想的离群点的数目n要比数据集的大小N少得多.因此,笔者预期的RBRP算法的第2阶段的时间复杂度为o（Nd）.由于第1阶段的时间复杂度为o（NlogN×d）,所以预期的RBRP的时间复杂度接近o（NlogN×d）.在此笔者还要指出,在实验部分RBRP算法和ORCA算法发现是一套完全相同的集群.RBRP算法和ORCA算法之间主要差异是：当处理正常数据点时,RBRP算法在检测k近似近邻时花费的时间比ORCA算法花费的时间少得多；而对于离群点,RBRP算法和ORCA算法都需要扫描整个数据集.
3实验环境和实验结果
3.1实验环境与数据集
在基于linux的系统上评估该算法的性能,该系统配备2.4GHzIntelPentium4处理器和1GB的主内存.为了捕获CPU和输入/输出（I/O）的处理时间,报告墙上挂钟的时间.实验中包含的所有的算法均用C语言来实现,并使用了几个真实的和合成的数据集来对算法的性能进行分析,这些数据集涵盖了一系列问题,具有不同的特性,以上数据集的简要介绍见表1.
第70页图2为不同数据集的数据点数与执行时间关系曲线,显示了当数据点数变化时,各种算法在6种数据集挖掘离群点时的总执行时间,而且这个总的执行时间中包含了RBRP算法的两个阶段.图2-a～图2-f都包含了4条曲线,其中2条曲线表示在线性时间算法和NlogN时间算法下挖掘数据集的预期执行时间,另外2条曲线表示RBRP算法和ORCA算法的实际运行时间.该实验在参数k设置为2的条件下,挖掘前30个离群点.
3.2实验结果
对于以上所有考虑的数据集,RBRP算法的性能都优于ORCA算法.在Covertype,Mixed30D和Uniform30D数据集上,RBRP算法性能优于ORCA算法一个数量级.此外,随着数据集大小的增加RBRP算法表现出更好的可扩展性.这些结论可以归因于：RBRP算法产生大小为o（NlogN）预处理开销的同时可以在近乎恒定的时间内找到异常点.对于有大量数据点的数据集,截止阀值能够快速增加,且ORCA算法能够提供相当好的性能,这种现象可以从Ipums数据集上的实验结果看出来.但是,当数据集包含的离群点数目较少时,截止阈值不会快速增长,使得ORCA算法的性能接近二次方,该情况从针对其余数据集的实验结果中看出.RBRP算法的性能不受截止阀值缓慢衰减的影响,其搜索空间得到了改善,从而在所有情况下的性能都得到了提高.此外,由图2可知,RBRP算法确实收敛于o（NlogN）.可以看出,在IPUMS和KDDCup1999数据集上,RBRP算法的性能似乎比o（NlogN）略好.
RBRP算法和ORCA算法都在所有考虑的数据集上表现出线性的可伸缩性,而且,随着k的增加,RBRP算法比ORCA算法具有更好的可扩展性.这主要归因于RBRP算法所使用的近似近邻的局部搜索.随着k的增加,对于每个正常的点,期望看到需要搜索的分区的数量也不断增加.与ORCA算法不同,RBRP算法不会受到大多数数据集上出现的截止阀值的缓慢衰减的影响.这一现象在除了IPUMS数据集之外的所有数据集上都表现很明显.在IPUMS数据集上,截止阀值相对较快地收敛于一个较大的值.因此,ORCA算法和RBRP算法在这个数据集上具有可比较的伸缩性.
4结论
笔者介绍了RBRP算法,这是一种针对高维数据集的基于距离的异常快速检测算法.RBRP算法通过采用允许快速确定近似最近邻的有效预处理步骤来提高最先进算法的效率.RBRP算法能够在包含N个数据点的d维数据集上的收敛于o（NlogN×d）.并验证了该算法在几个真实和合成数据集上的收敛性.RBRP算法始终优于ORCA算法以及是一种最优的基于距离的异常检测算法,并且RBRP算法的优势往往超过ORCA算法一个数量级.
参考文献：
[1]KNORREM,NGRT.Findingintensionalknowledgeofdistance-basedoutliers[C]//ACM.Proceedingsofthe25thInternationalConferenceonVeryLargeDataBases(VLDB).SanFrancisco:MorganKaufmannPublishersInc,1999:211-222.
[2]HANJiawei,KAMBERMicheline,PEIJia.数据挖掘概念与技术[M].范明,孟小峰,译.北京:机械工业出版社,2007.
[3]朱利,邱媛媛,于帅,等.一种基于快速k-近邻的MST离群检测方法[J/OL].计算机学报,2017:1-15[2017-08-28].http://kns.cnki.net/kcms/detail/11.1826.TP.20170828.2334.008.html.
[4]邓廷权,刘金艳,王宁.高维数据离群点检测的局部线性嵌入方法[J/OL].计算机工程与应用,2017:1-9[2017-03-04].http://kns.cnki.net/kcms/detail/11.2127.TP.20170304.1727.006.html.
[5]ANGIULLIF,PIZZUTIC.Fastoutlierdetectioninhighdimensionalspaces[C]//ACM.Proceedingsofthe6thEuro-peanConferenceonPrinciplesofDataMiningandKnowl-edgeDiscovery.London:Springer-Verlag,2002:15-26.
[6]BAYSD,SCHWABACHERM.Miningdistance-basedoutliersinnearlineartimewithrandomizationandasimplepruningrule[C]//ACM.ProceedingsoftheninthACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining.NewYork:ACMPublications,2003:29-38.
[7]BOLTONRJ,HANDDJ.Statisticalfrauddetection:are-view[J].StatisticalScience,2002,17(3):235-249.
[8]RAMASWAMYS,RASTOGIR,SHIMK.Efficientalgo-rithmorminingoutlierromlargedatasets[C]//ACM.Proceedingsofthe2000ACMSIGMODinternationalcon-ferenceonManagementofdata.NewYork:ACMPublica-tions,2000:427-438.
（责任编辑邸开宇）
检测算法论文范文结:
适合不知如何写检测算法方面的相关专业大学硕士和本科毕业论文以及关于检测算法论文开题报告范文和相关职称论文写作参考文献资料下载。
2、论文查重检测
4、论文抄袭率检测
5、论文检测
6、论文字数检测