离群点检测算法研究

（晋中学院信息技术与工程学院晋中030619）

离群点检测算法研究

李俊丽芦彩林

（晋中学院信息技术与工程学院晋中030619）

离群检测作为数据挖掘中一项重要内容，已经应用于许多领域，因此引起广泛关注。介绍了传统的离群点检测算法的分类，针对传统算法无法适用于新兴数据模型的问题，首先详细讨论了高维数据的离群点检测算法，并提出了离群组合技术的方法以解决与高维数据相关联的问题，其次描述了不确定数据和数据流离群检测算法，最后对离群检测算法的性能评价进行了讨论，并指出了进一步的研究方向。

高维数据；离群检测；不确定数据；数据流

Class NumberTP311

1 引言

传统离群检测算法大致可以分为四类：基于分布的、基于距离的、基于密度的和基于聚类的。随着科学技术的发展，数据的收集更快也更容易，从而导致更复杂的数据形式出现了。

高维数据的特征完全不同于传统数据，传统离群检测算法都不能很有效地应用于高维数据。在高维数据中，数据变得稀疏，数据集中的对象几乎是等距离彼此分开，数据在高维空间中的表现相对于低维空间有很大的差异。而且由于数据集变得更多样化，在高维数据中许多属性通常是不相关的，这些不相关的属性能够混淆离群算法。

除了高维数据，还出现了不确定性数据、流数据等新兴数据模型，同时也出现了一些新的离群检测算法，因此关于新型数据领域的离群检测算法的研究更有意义。

2 高维数据离群检测算法

高维数据离群检测是近年来数据挖掘的一个较为活跃的研究领域。目前，高维数据离群检测算法己在文本挖掘、生物信息学、信息安全等领域得到广泛应用。根据高维数据离群检测所采用的基本思想可以分为基于降维的、基于子空间的和离群联合技术。

2.1 降维

高维数据降维技术主要通过从数据集中提取重要特征来实现，其中主要包括特征变换和特征选择两种。

特征变换通常用于高维数据集，这种方式通过创建属性的线性组合发现潜在的结构。文献［1］利用Hilbert空间填充曲线将数据集线性化，文献［2］利用小波变换从原始数据集中消除聚类，从而达到发现离群点的目的。文献［3］使用主成分分析方法获得能代表数据的δ维属性的d个最正交向量（属性），投影变化后再进行挖掘。文献［4］采用分形的思想得到非整数值的分数维数，为进一步降维提供参考。

特征选择也是一种常用的减少数据集维数的技术，它试图发现一个数据集最相关的属性。这种方法不用变换，而是从维度中启发式地选取一部分维，删除不相关或冗余的属性（维），目标是找出最小属性集，使得数据类的概率分布尽可能接近使用所有属性得到的原分布。这种方法避免了挖掘结果难以解释的问题，并且由于属性数目的减少，使得模式更易于理解。基于启发式方法的技术包括逐步向前选择、逐步向后删除、向前选择和向后删除的结合和决策树归纳［5］等。

2.2 子空间离群检测方法

子空间离群检测方法不是在全维空间中寻找离群点，而是在相关的子空间中。要确定哪些子空间是相关的也开发了很多技术，下面介绍一些重要的算法。

文献［6］提出了一个动态子空间搜索系统，称为HOS-Miner。该算法使用固定的阈值来识别异常值，对于给定的数据点，能有效确定其离群子空间。HOS-Miner存在的问题是在不同维度的子空间中离群点得分无法比较。文献［7］提出OutRank（outlier ranking）方法，通过引入新的离群点得分函数评估子空间聚类分析确定的其余部分数据对象的偏差。OutRank存在的问题是离群值作为基于密度的聚类所产生的副产物可导致一大组的离群值。文献［8］提出轴平行子空间，文献［9］提出在多个子空间中同时评估每个对象的偏差，文献［10］提出一个处理局部属性相关的多维空间，文献［11］提出只适合基于密度离检测的高对比度子空间等。

尽管基于子空间的离群检测技术很多，但还是局限在特定数据类型或特定背景环境下。下面介绍以离群组合技术这样一种方式以减少算法的复杂性和使计算成本更低。

2.3 离群组合技术

在一般情况下，组合技术有潜力解决与高维数据相关联的问题，组合分析方法通常是用于降低模型的具体的数据集或数据局部的依赖性，这极大地增加了数据挖掘过程的鲁棒性，组合技术常用于聚类和分类中。但在某些情况下，组合分析技术已经隐含在许多离群分析算法中。

文献［12］可以被认为是顺序组合的例子，顺序组合是一个给定的算法或算法集被顺序地应用于分析基本数据的修改或算法的具体选择，从而使算法将来的应用能被前面的应用影响。最终结果是一个加权的组合或离群值的最后一个应用程序的最终结果分析算法。在独立组合中，不同算法或相同算法的不同实例被应用于完整数据或部分数据中。关于数据和算法的选择应用是从这些不同的算法执行得到的独立结果。不同的算法执行的结果组合在一起，以获得更健壮的离群值。例如，文献［13］从底层数据得到的示例子空间以确定每一个独立执行得到的离群值。文献［14］尝试将构建在相同的数据集上不同模型的离群得分结合起来，这在许多经典离群分析算法中已经做了很多，这种模式的主要挑战是，不同模型的离群得分彼此之间通常不能直接进行比较。数据为中心的组合对数据的不同部分和不同功能进行分析，数据是抽样的随机子空间，在这些预测子空间确定离群值，最后确定的离群值为来自不同的子空间离群值的组合。

这些方法很显然并不全面，但它们代表了组合算法中重要的一部分，组合分析已有效用于高维离群检测，其中经常使用数据的多个子空间以发现离群值。这些情况表明，正确使用组合分析技术对算法的改进有明显提高。

3 离群点检测研究热点

3.1 不确定数据离群检测

近年来，由于越来越多地使用传感器、无线射频识别（RFID）、GPS和类似的设备进行数据收集，不确定数据变得很常见。不确定性的原因包括测量的局限性，包括噪声、电源电压不一致和传输延迟或数据丢失。为了管理、查询或挖掘这样的数据，需要考虑数据的不确定性。传统的离群检测算法在确定性数据中已经应用很广，但在新兴的不确定数据领域却是一项新的研究课题。发现不确定数据中的离群对象是很困难的，因此，很多研究者开始开发新的数据处理和挖掘技术来探寻不确定数据中的离群点，不确定数据中的离群检测同样也会遭遇到随着维度增大而难以标识离群点的难题。

针对不确定数据离群检测，Aggarwal等首次提出了基于子空间的不确定性数据挖掘技术［15］，该算法假设在低密度异常子空间出现离群值，并在指定对象的子空间计算每个点的密度，然后判断是否为离群点。文献［16］从一个全面的模型考虑不确定对象和它们的实例，一个不确定的对象包含一些固有的属性和一组由概率密度分布建模的实例。通过假设具有相似属性的不确定对象往往有相似的实例来学习对每个不确定对象使用具有相似属性的对象实例。因此，通过和正常实例进行比较可以检测到异常实例，进一步可以检测到大多数实例是离群值的离群对象。技术上使用贝叶斯推理算法来解决这个问题，并开发了一个近似算法和一个过滤算法来加快计算速度。文献［17］实现了一个使用基于密度抽样方法的不确定对象的离群检测方法，虽然密度抽样法是一个很好理解和相对简单的离群检测技术，但其应用在不确定数据上会产生很高的计算工作量。该算法使用一个廉价的GPU（图形处理器）大大降低了运行时间。文献［18］提出基于距离的top-k不确定数据对象离群检测方法，基于距离的离群检测最基本的方法是利用嵌套循环，这种方法的代价是非常大的，因为两个不确定的对象之间的距离函数花费很大。而该方法中，一个不确定对象通过高斯分布的概率密度函数建模，数据的离群点检测算法只需要考虑一小部分数据，因此数据集对象能快速确定候选对象的top-k离群点。

随着更复杂的不确定数据模型的出现，未来需要对不确定数据做进一步研究以便于找到快速、高效的离群检测算法。

3.2 数据流离群点检测

最近，数据流挖掘的研究得到越来越多的关注。数据流是信息技术快速发展出现的一类新的数据模型，数据量大、不可预测、连续快速和短暂易逝是此类数据的特点。很多传统数据挖掘技术无法推广到数据流挖掘上，因此，数据流离群检测是数据挖掘的一个新兴课题，是一个非常具有挑战性的问题。这是因为数据流不能被多次扫描，而且新概念也在不断发展。

为了解决数据流的异常检测问题，Yang等提出一个新的快速的离群检测算法［19］。该方法基于动态网格分区数据空间，过滤处于密集区域的大量主体数据，大大降低了算法应考虑对象的大小。在稀疏区域的候选离群点，采用近似方法计算其离群度，具有高离群度的数据作为离群点输出。周晓云等给出一种快速数据流离群点检测算法［20］，该算法通过动态发现和维护频繁模式来计算离群度，能够有效地处理高维类别属性数据流，并可进一步扩展到数值属性和混合属性数据流。Elahi等人提出一个基于聚类的方法［21］，把流分成块并使用k均值算法使用固定数量的簇聚类每个块。通过使用前一个数据流块的平均值与当前数据流块的平均值以决定数据流对象中更好的离群值。Cao等提出了一种新的基于反向最近邻居的数据流异常检测算法SODRNN［22］，在该算法中插入或删除的更新只需要扫描一次当前窗口，从而提高了效率。

数据流异常检测的主要目的是在合理时间准确找到数据流异常值。现有的离群点检测算法不适用于动态数据流，并不能找到有效的异常数据。由于实时检测和动态调整的要求以及现有的数据流离群检测算法的不适用性，下一步的研究要能够实时发现数据中的异常数据流并动态调整检测结果，使算法具有更好的可扩展性。

3.3 离群检测方法性能评价

离群检测目前正专注于新方法的研究和改进，但同时也忽略了一个问题，那就是由不同的方法所提供的离群得分的性能评价。现有的离群检测方法经常采用精确度进行评价，即包含k个离群点的数据集中前k个结果的真正正确率，这是评价结果的一个很单纯的方式。

评价的另一种常用方法是ROC曲线（receiver operating characteristic curve）和AUC曲线（ROC曲线下的面积），这种方法基本上失去了离群得分信息。

但是离群检测需要接受的“基本事实”可能是不完整的，而且现实世界的数据可能包括合理的离群只是还不知道或者被认为是没有意义的，当比较或者组合不同子空间的结果后，有意义的离群得分比离群排名包含更多的信息。因此，离群检测方法评价要更注重以下几个方面：

1）已知的（或估计的）异常值权重更高。

2）允许非二进制的基本事实。

3）通过组合（不同的）得分向量提高离群检测，这个方向的研究从长远看将标准化离群得分。

4 结语

离群检测在现代生活中已经得到广泛应用，离群检测许多应用领域的数据具有很高的维度，而维度灾难一直是处理高维数据时面临的一个关键问题。为了解决这个问题，本文从高维数据离群检测所采用的基本思想出发，将它们分为基于降维的、基于子空间的和离群联合技术。但由于现有的一些检测算法自身的各种缺陷，所以还需要进一步的研究和改进。文中还就目前离群检测研究的热点——不确定数据和数据流的离群检测以及离群检测性能评价进行了讨论，并指出了下一步研究的方向。

［1］Angiulli F，Basta S，Pizzuti C.Distance-based detection and prediction of outliers［J］.Knowledge&Data Engineering IEEE Transactions on，2006，18（2）：145-160.

［2］Yu D，Sheikholeslami G，Zhang A.FindOut：Finding Outliers in Very Large Datasets［J］.Knowledge&Information Systems，2002，4（4）：387-412.

［3］Dutta H，Giannella C，Borne K D，et al.Distributed Top-K Outlier Detection from Astronomy Catalogs using the DEMAC System［C］//Proceedings of the Seventh SIAM International Conference on Data Mining，April 26-28，2007，Minneapolis，Minnesota，USA.2007.

［4］孙金花，胡健，李向阳.基于分形理论的离群点检测［J］.计算机工程，2011，37（3）：33-35. SUN Jinhua，HU Jian，LI Xiangyang.Outlier Detection Based on Fractal Theory［J］.Computer Engineering，2011，37（3）：33-35.

［5］Jiawei Han，Micheline kamber，Jian pei.数据挖掘：概念与技术，第3版［M］.北京：机械工业出版社，2012. Jiawei Han，Micheline kamber，Jian pei.Data Mining Concepts and Techniques（Third Edition）［M］.Beijing：China Machine Press，2012.

［6］Zhang J，Lou M，Ling T W，et al.HOS-Miner：A System for Detecting Outlying Subspaces of High-dimensional Data［C］//Thirtieth International Conference on Very Large Data Bases.VLDB Endowment，2004：1265-1268.

［7］E.Müller，I.Assent，U.Steinhausen，and T.Seidl.Out-Rank：ranking outliers in high dimensional data［C］//Proceedings of the 24th International Conference on Data Engineering（ICDE）Workshop on Ranking in Databases（DBRank），Cancun，Mexico，2008：600-603.

［8］Kriegel H P，Ger P，Schubert E，et al.Outlier Detection in Axis-Parallel Subspaces of High Dimensional Data［C］// Advances in Knowledge Discovery and Data Mining，Pacific-Asia Conference，PAKDD 2009，Bangkok，Thailand，April 27-30，2009，Proceedings，2009：831-838.

［9］Müller E，Schiffer M，Seidl T.Adaptive outlierness for subspace outlier ranking［C］//International Conference on Information and Knowledge Management，2010：1629-1632.

［10］Nguyen H V，Gopalkrishnan V，Assent I.An Unbiased Distance-BasedOutlierDetectionApproachfor High-Dimensional Data［C］//Database Systems for Advanced Applications.Springer Berlin Heidelberg，2011：138-152.

［11］Keller F，Muller E，Bohm K.HiCS：High Contrast Subspaces for Density-Based Outlier Ranking［J］.IEEE，2012，41（4）：1037-1048.

［12］Yoav Freund，Robert E Schapire.A Decision-Theoretic Generalization of On-Line Learning and An Application to Boosting［C］//European Conference on Computational Learning Theory，Springer Berlin Heidelberg，1995：119-139.

［13］Lazarevic A，Kumar V.Feature bagging for outlier detection.［C］//In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2005：157-166.

［14］Papadimitriou S，Kitagawa H，Gibbons P B，et al.LOCI：Fast Outlier Detection Using the Local Correlation Integral［J］.Proc Icde，2003：315-326.

［15］Aggarwal C C，Yu P S.Outlier Detection with Uncertain Data.［C］//Proceedings of the SIAM International Conference on Data Mining，SDM 2008，April 24-26，2008，Atlanta，Georgia，USA，2008：483-493.

［16］Jiang B，Pei J.Outlier detection on uncertain data：Objects，instances，and inferences［J］.IEEE，2011，6791（4）：422-433.

［17］Matsumoto T，Hung E.Accelerating Outlier Detection with Uncertain Data Using Graphics Processors［C］//Pacific-Asia Conference on Advances in knowledge Discovery and Data Mining，Springer Berlin Heidelberg，2012：169-180.

［18］Shaikh S A，Kitagawa H.Top-k Outlier Detection from Uncertain Data［J］.International Journal of Automation &Computing，2014，11（2）：128-142.

［19］杨宜东，孙志挥，朱玉全，等.基于动态网格的数据流离群点快速检测算法［J］.软件学报，2006，17（8）：1796-1803.

YANG Yidong，SUN Zhihui，ZHU Yuquan，et al.A Fast Outlier Detection Algorithm for Data Streams Based on Dynamic Grids［J］.Journal of Software，2006，17（8）：1796-1803.

［20］周晓云，孙志挥，张柏礼，等.高维类别属性数据流离群点快速检测算法［J］.软件学报，2007，18（4）：933-942.

ZHOU Xiaoyun，SUN Zhihui，ZHANG Baili，et al.A Fast Outlier Detection Algorithm for High Dimensional Categorical Data Streams［J］.Journal of Software，2007，18（4）：933-942.

［21］Elahi M，Li K，Nisar W，et al.Efficient Clustering-Based Outlier Detection Algorithm for Dynamic Data Stream.［C］//International Conference on Fuzzy Systems and Knowledge Discovery，Fskd 2008，18-20 October 2008，Jinan，Shandong，China，Proceedings，Volume.2008：298-304.

［22］Cao L，Liu X，Zhou T，et al.A Data Stream Outlier Delection Algorithm Based On Reverse K Nearest Neighbors［C］//International Symposium on Computational Intelligence and Design.IEEE，2010：236-239.

Research on Algorithms for Outlier Detection

LI JunliLU Cailin
（School of Information Technology and Engineering，Jinzhong College，Jinzhong030619）

Outlier detection as an important item of data mining has been used in many areas thus caused wide public concern. This paper introduces traditional classification of outlier detection algorithm，aiming at the problem that traditional algorithm is not suitable for new data models，the paper firstly discusses the outlier detection methods of high-dimensional data detailed，and points out outlier ensembles for solving the problems associated with high-dimensional data.Secondly，outlier detection algorithms of uncertain data and data streams are described，and finally the evaluation of the outlier detection methods are discussed，and the direction for further research is pointed out.

high-dimensional data，outlier detection，uncertain data，data streams

TP311

10.3969/j.issn.1672-9722.2017.06.007

2016年12月18日，

2017年1月23日

国家青年科学基金项目（编号：61602335）资助。

李俊丽，女，博士研究生，讲师，研究方向：数据挖掘。芦彩林，男，硕士，副教授，研究方向：计算机网络。