基于双倍距离的孤立点检测算法研究

杨 臻，张明慧

（郑州师范学院 信息科学与技术学院，郑州 450044）

0 引言

随着信息技术和互联网的日益普及，人们在日常工作中积累了大量数据，如何更有效的利用这些数据，从数据中发现潜在的、更有价值的知识，是人们目前热炽期待解决的问题。数据挖掘技术为此提供了有力的技术支持，其中的孤立点检测技术更是以挖掘少数特例的独特作用而成为了广大研究者的兴趣焦点。孤立点检测技术就是利用一些方法挑选出那些与大部分数据特征不一致的不同寻常的数据，从而进一步研究这些数据意义的一门技术。在当今社会生活中，孤立点检测技术有着重要的现实意义和应用价值，被许多行业比如：冶金、电信、气象等用来挖掘数据背后的深层价值，为决策者决策提供有效的数据支撑。

1 概述现有算法

不同数据领域的孤立点有着不同的定义和相应有效的检测方法，为了检测出各种假设情况下存在的孤立点,广大研究者提出了多种方法。早期时候的典型算法有Rastogi和Ramaswamy提出的k-th Nearest Neighbor孤立点检测方法。Breunig和Kriegel[3]则对孤立点的认定提出了局部性这一不同的新颖的看法。Malik Agyemang进一步提出了LSC算法。近些年来，国内许多研究人员也相继从不同方面对前者的算法加以改进和提高，如文献[7]中提出了反向K-近邻的检测算法；文献[8]中提出了变异系数的检测算法等。

2 DTKA算法

本文提出了DTKA算法，具体定义如下：

定义1 对象p的2k-距离近邻数nn2k (p)

设数据集中的任意一个对象p，则对象p的nn2k (p)值指的是从起点p开始，到2k-距离范围内的所有对象数。即：

定义2 对象p的DTKA值DTKA(p)

设数据集中的任意一个对象p，则对象p的DTKA值就是2k-距离近邻数与k-距离近邻数的比值。即：

其中，|nnk(p)|为对象p的k-距离近邻数。

如果DTKA值很小说明对象的邻域是稀疏的，它的离散度较大，数据对象很可能是孤立点，相反，如果DTKA值很大说明对象的邻域是稠密的，它的离散度较小，对象则不可能是孤立点。

3 算法的流程

4 实现算法的主要函数

4.1 函数Getkdistance()

4.2 函数Getnn2k()

4.3 函数GetDTKA()

5 实验与分析

下面通过运行VC++实现的DTKA算法和LOF算法，在数据集上进行多个对比实验来从不同方面检验算法对孤立点的真实识别情况。需要实验的数据集由文本文件输入提供。

5.1 准确性对比分析

准确性实验采用的数据集是一个已知具有5000个对象的2维数据集，其中不仅包含大小不一、形状各异、密度各不相同的4个类，而且包含任意分布的若干孤立点。参数:k=6。DTKA算法和LOF算法经过运行以后，获得的运行结果如图1、图2所示，其中DTKA识别的孤立点情况如图1所示，LOF识别的孤立点情况如图2所示。

从图1和图2的对比结果来看，可以充分认定DTKA算法对孤立点的识别能力是准确的，可以正确检测出需要的孤立点。

图1 DTKA实验结果图

图2 LOF实验结果图

5.2 时间复杂度对比分析

算法性能高低的一个重要衡量指标是时间复杂度。时间复杂度的大小是由算法的关键部分来综合决定的。算法第1个主要的运算是在计算每个对象的k-距离过程，因此时间复杂度为o(kn)。第2个主要的运算是在计算每个对象的K-距离近邻数,因此时间复杂度是o(n2)。第3个主要的运算是在是根据排过序的DTKA值确定前n个孤立点对象过程,因此时间复杂度为o(nN)，n＜＜N。总之，经过上述分析得出本算法主要时间复杂度是o(kn2)，表明DTKA算法的执行时间与k存在一次函数关系，与n存在平方关系，其中k代表每个数据对象的最近邻数，n代表数据集中的数据对象数目。

从以上分析结果来看，DTKA算法的时间复杂度不比LOF算法高，可以认为是符合要求的，可行的。

5.3 执行时间对比分析

下面通过测试DTKA算法在随着数据对象数量增加的情况下的执行时间的变化规律，深入检验其执行效率。该实验采用的数据集是一个具有12000个记录的集合，数据对象增量变化的范围从2000到12000，每个对象的最近邻数为 K=100，则当数据规模分别获取不同值，并且每次加2000个数据对象，即N等于2000，4000，…，12000时，算法在随着数据对象数量增加的情况下执行时间的变化情况如图3所示。

图3 不同数据规模的执行时间

从图3中可以看出: DTKA算法运行时所花费的时间是受数据规模直接影响的，但是变化是渐进增加的，变化趋势近似抛物线规律，并且在相同数据规模情况下DTKA算法的运行时间少于LOF算法。

通过以上多方面的深入实验分析，可以认定DTKA算法能够高效准确地检测出数据集中的异常数据。

6 结束语

本文提出的数据挖掘技术方面的DTKA算法，改进了对于孤立点的判定方法，详细给出了算法的定义，介绍了算法的主要计算流程，实现算法的主要函数。最后进行了大量的实验，而且对实验结果做了深入系统的分析，并于典型算法LOF对比研究，实验结论充分表明DTKA算法能有效进行孤立点检测，并且在执行时间上少于LOF,解决了传统算法检测的缺陷。该算法的合理性、优越性在冶金、天气预报等数据挖掘技术研究领域有着广阔的应用前景和实际的研究价值。

[1] E.Knorr,R.Ng.A lgorithms for M ining Distance-based Outliers in Large Data Sets[C].Proceedings of the VLDB Conference,1998.392-403.

[2] MALIK A,EZEIFE CI. LSC-m ine: A lgorithm for M ining Local Outliers[A].Proceedings of the 15th Information Resource Management Association (IRMA) International Conference[C].2004.5-8.

[3] Breunig M.M.,K riegel H.–P. ,Ng R.T. ,and Sander J.OPTICS -OF:Identifying local outliers[C]1In Proceedings of 3rd European Conference on Principles of Data M ining and Know ledge Discovery ,Prague,1999.

[4] 薛安荣,鞠时光,何伟华等.局部离群点挖掘算法研究[J].计算机学报,2007,30(8):1455-1463.

[5] 卢启程,邹平.数据挖掘的研究与应用进展[J].昆明理工大学学报.2002,27(5):62-66.

[6] 康塔尼克:数据挖掘:概念、模型、方法和算法[M].北京:清华大学出版社,2003.

[7] 岳峰,聚类的边界点检测算法研究,[学位论文].郑州大学,2007.

[8] 薛丽香等.基于变异系数的边界点检测算法[J].模式识别与人工智能.2009.05.