离群数据检测研究

赵向兵，白 伟

（1.山西大同大学数学与计算机科学学院，山西大同 037009； 2.太原广播电视大学，山西太原 030012）

离群数据检测研究

赵向兵1，白 伟2

（1.山西大同大学数学与计算机科学学院，山西大同 037009； 2.太原广播电视大学，山西太原 030012）

通过充分调研，对现有离群数据检测算法作了分析比较，总结出各算法的特点，并且探讨和展望了离群数据检测的几个热点问题，为离群数据检测算法的进一步研究打下基础。

离群数据；高维离群；数据流；分布离群

近年来，随着计算机硬件技术和数据库技术的飞速发展，许多行业建立了自己的数据库系统。随之而来出现了庞大的存储数据，这就需要有强有力的工具，检测隐藏在这些数据里难以被人们发现的重要信息。数据挖掘就是基于这种需求，引起人们广泛兴趣并迅速发展起来的一门学科。数据挖掘是从大量的、随机的、有噪声的、模糊的、不完整的数据中，检测出隐含于其中潜在的有用信息，从而为人们提供决策依据。离群数据检测作为数据挖掘的一种重要技术，在数据挖掘、机器学习和统计学领域等方面得到了广泛关注。其应用前景非常广阔，如：行用卡欺骗、金融领域、药物研究、气象预报、客户分类、电信诈骗、犯罪行为监测和网络入侵检测等。

到目前为止，离群数据没有被普遍采纳的定义，基于此Hawkins给出了揭示离群数据本质的定义：“离群点的表现与其它点如此不同，以至于怀疑它是由完全不同的机制产生的”[1]。早期的数据挖掘算法通常将离群数据作为噪声，去除掉离群数据来减少其对正常数据的干扰，但离群数据可能极有价值，因为一万个正常数据可能只包含一条有用信息，而一个离群数据可能正是此条有用信息。检测的目的在于找出隐含于海量数据中相对孤立而稀疏的异常数据模式，离群数据的检测可以看作两个子问题：1）在给定数据集中定义什么样的数据是离群数据；2）找出检测离群数据的有效方法[2]。引起离群点的因素主要是两个方面：1）数据来源不同。因为在数据采集过程中，数据本身的变化导致了数据异常。例如：自然气候变化、客户习惯改变等，这些有用的离群数据是我们重点关注的对象。2）数据采集时，数据异常是人为因素所致。如干扰信号、测量失误等。由于这些错误干扰数据的正确分析，进而影响其结果，是真正的噪声数据，所以有必要清除这些数据。

1 离群数据检测研究现状

近年来，随着离群数据检测的广泛应用及对其重要性认识的加深，数据挖掘研究领域已成为热点问题之一。离群数据检测方法大致分为以下几类：基于统计学方法、基于距离方法、基于密度方法、基于偏差方法[3]。下面分别综述各算法的特点。

1.1 基于统计的离群点挖掘算法

离群点挖掘最早出现于统计 （statistical-based）学领域，其主要思想是假设已知数据集的概率分布或概率模型（如泊松分布和正态分布）和数据参数（如均值和方差），利用数据集的规律及分布状况进行不一致性检测，把严重偏离分布曲线的数据确定为离群点。基于分布离群数据检测方法可以依托概率统计理论，这为离群数据检测提供有力支撑。利用概率统计理论生成统计模型，有利于解释离群数据，同时节省数据的存储空间。然而，此方法只适用于周期数据，单属性数据及数值型数据的挖掘。现实生活中，大多数为高维数据，基于统计离群点算法不能满足高维数据的挖掘。而基于统计的方法必须以已确定的数据分布为前提条件，所以不适用未知数据分布情况。该算法可移植性差，主要被应用于科研计算领域。

1.2 基于距离的离群点挖掘算法

1998年，Knorr和Ng提出基于距离 （distancebased）的方法，该方法不依赖统计检验，不需要知道数据的具体分布，而是把没有“足够多”邻居的对象看作是离群对象，根据给定对象的距离定义邻居。通常描述为DB（p，d），如果数据集S中至少有P部分与对象O的距离大于d，则对象O是一个带参数P和d的离群数据。该方法拓展了基于统计思想的算法，即使数据集不满足任何特定分布模型，它也能有效的发现离群点。但随着维数的增加，其算法复杂度也会大幅增加。且在高维数据集中，空间的稀疏性不能对离群数据给出一个合理的解释。此外，该方法需要用户设置参数p和d，确定这些参数需要多次试凑。基于距离的离群点检测算法虽然对以上算法有所改进，但它没有从根本上解决数据的稀疏程度，因为此算法的参数选择是就全局而言的，对于局部离群无能为力，挖掘出来的离群点也只能算是全局离群点。

基于距离的离群数据检测算法分为：基于索引、嵌套循环和单元算法。基于索引检测算法就是采用多维索引结构搜索每个对象O在半径d范围内的邻居。该算法有良好的扩展性，但我们在计算复杂度时只研究了搜索对象花费的时间，没有考虑建造索引任务的复杂度。嵌套循环算法和基于索引的算法具有同样的时间复杂度，但嵌套循环算法的研究是针对避免索引结构的构建，试图大幅减少I/ O的访问次数。将内存的缓冲空间分为两部分，同时将数据集合分成若干个逻辑块。逻辑块有选择性的装入每个缓冲区域，通过精心选择达到最佳的I/ O效率。为了降低此算法的复杂度，主要对存储于内存的数据集合作单元划分处理，该算法不是逐个对每对象而是对每个划分单元查找离群数据。

1.3 基于密度的方法

基于密度（density-based）的方法是在基于距离方法的基础上发展起来的，其思想是根据数据之间的距离和某一给定范围内的数据提出了“密度”概念，然后根据密度判定数据是否为离群点。所以它是一个局部概念。典型的算法有Breuing和Kriegel提出的LOF，计算每个点的局部离群因子识别离群数据，LOF是点P和其最近邻的局部可达密度比率的平均值。LOF（P）越大，越可能是离群数据。该算法的主要缺点是I/O代价比较高，对高维数据效率低。该方法对每个对象是否为离群对象的判定依据于两方面：（1）一定范围内数据对象的个数，（2）数据对象之间的距离。这两个数据的结合体现了数据的局部特性和密度含义，用不同密度区域中数据对象的离群度检测离群点，所以此方法比较准确，而且便于解释离群点具体意义，得到了广泛的发展空间。但时间复杂度达到了O（DNk），且此算法参数确定存在人为因素，参数的选择也比较困难。

1.4 基于偏差的离群点挖掘算法

基于偏差（density-based）的离群点检测是通过检测对象的主要特征来识别离群点，存在描述特征差异的数据对象认为是离群点。Arning等提出一种“序列异常”概念，从一系列类似对象中识别异常的方法进行模仿，利用相异度函数计算光滑因子的最大子集，集合中的对象即为离群数据。其主要思想是检验数据集的主要特征进而发现离群点。如果一个数据严重不同于前面的序列时，即可依据相异度函数计算光滑因子的最大子集，即为异常集，集合中的对象即为离群数据。虽然其方法理论上可以挖掘各种类型的数据，但是由于要事先知道不容易被人们发现的数据主要特征，所以很难选择数据的相异度函数，而且结果不尽如人意。该算法趋于理想化，在大多数情况下，不能运用于复杂的高维数据。

2 离群数据检测研究热点

现有的研究表明，目前离群数据检测的热点问题主要是对高维数据、数据流和分布式方面的研究。

2.1 高维大数据集离群点检测

随着计算机技术的发展，数据的采集量不断增大，且维数也不断增加，离群数据的检测面临着巨大的挑战。在高维数据集中，数据和数据之间非常稀疏，数据对象之间的距离及区域密度不再有直观的意义。许多算法在高维数据的离群点检测中不再有效，所以对高维数据离群点的检测是一个复杂且有巨大发展空间的研究课题。

现在，解决高维数据的离群数据检测方法有投影变换和属性提取。通过投影子空间进行查找，但子空间的组合数较大，必须在其中找到最优的组合，这就可以用遗传算法、微粒群等算法。另外，在降维时可以对冗余属性和不相关属性进行删除，得到最小属性集合，使其具有几乎全部属性的分布情况。2005年，Aggarwal等提出了一种新的高维离群数据检测算法，通过离群子空间度量——稀疏度系数，将高维数据投影到低维子空间中，利用遗传算法搜索离群数据，这样可以提高离群数据的效率。但该算法也有不足之处：（1）结果不很准确；（2）不能保证检测出所有的离群数据；（3）只能在有限维上寻找。在此基础上又提出了一种基于用户实例的高维数据检测算法，利用用户掌握的实例提取离群数据概念，然后用改进的遗传算法搜索离群子空间，该算法具有很高的准确性、可解释性和可伸缩性。张继福等[4]进行了一些细节方面处理。在离群子空间基础上引入了稠密度系数的概念，提高了实验结果的准确性和高效性。 金义富等[5]提出了基于关键维或区域的子空间及聚类算法，收到了良好的效果。Shekhar等学者提出二分算法，将属性分为空间属性和非空间属性，计算对象与其邻域的非空间属性值的比值或差值，消除数据的自相关性，简称为SLZ算法。该算法不能解决数据的空间异质性问题，而主要检测全局离群点。Cbawla等[6]同时考虑了数据的自相关性和异质性，引入波动参数β，用β和对象与其邻域欧拉距离的乘积表示空间局部离群度SLOM。但β需处于对称分布状况，所以在空间邻居较少或波动幅度较小的状况下不能准确反映波动情况，有误检和漏检的可能。薛安荣等[7]人提出了一种SLOF算法，该算法同时解决了空间自相关性约束问题和空间异质性约束问题，用空间领域偏离因子表示离群度，但该算法属性权值还由邻域专家决定。针对这一点，一种改进的基于加权属性的SLOF离群点挖掘算法[8]对该算法做了改进，进一步减少了人为因素。

总之，高维离群数据的检测还有很大的研究空间，且计算复杂，还需进一步改善。

2.2 数据流离群点检测

数据流是一种新型数据，应用于通信服务、金融服务和网络控制等领域。与传统数据相比，其具有连续性、无限性、实时性，按照到达的先后顺序控制。由于数据流的数据量很庞大，不可能扫描和存储整个数据流集合。所以对数据流研究离群检测时，关键是设计高效的单遍扫描检测算法。典型算法有：基于抽样方法、树模型、基于散列和指数直方图等方法。在一些现有算法中，通过较小权重的设置或丢弃旧数据来照应变化分布的情况，但存在缺陷，没有考虑到分布变化是怎样发生以及何时发生。所以采用参照和滑动两个数据窗口，利用两个窗口的数据集分布情况辨别数据流数据变化，并对变化数据进行量化和分析，收到比较好的效果。文献[9]提出一种动态网格划分检测算法，过滤掉稠密区域数据，减小考察数据规模，通过计算其离群度来确定离群数据。文献[10]利用组合优化解决数据流离群数据检测的问题。总之，数据流离群数据检测方法是比较前沿的研究领域，有待于进一步的研究。

2.3 分布式离群点检测

现阶段分布式系统在实际应用中得到了较大的发展，对各个节点之间传输数据的离群点检测，以上算法是不可行的，所以提出了分布式离群数据挖掘算法。

解决高维海量数据集的一种途径是基于网格分布式离群挖掘，网格作为一种能带来巨大处理、存储能力和其他IT资源的新型网络，网格计算可以通过共享网络将不同地点计算机相联，形成虚拟的超级计算机，可为研究和其它数据集中的应用提供强大的处理能力。建立在此基础之上的数据挖掘，不仅结合了网格计算思想及其技术优点，而且能高效分析处理广域分布的海量数据集，并给科学研究领域，经济社会生活带来巨大的价值。

全美有12所大学和研究机构参与了Globu的研发项目，作为美国argonne国家实验室的Globus，研究了网格计算的关键理论，如数据管理、资源管理、信息服务、及安全等，开发了能在各种平台上运行的网格计算软件（toolkit），组建大型网格试验平台，开发适合于大型网格系统运行的程序。Globus网格计算协议是以互联网协议中的通信、名字解析、路由为基础。

目前，尽管基于网格平台的分布式数据挖掘已成为研究热点之一，但是在国内外，对它的研究成果还较少。

3 结语

离群点检测技术的应用前景非常广泛，已引起了许多研究者的关注。该文章主要详细讨论离群点检测算法，比较各种检测算法的特点，最后总结了离群点检测算法的三个热点问题。

[1]Hawkins D.Identification of Outliers[M].London：Chapman and Hall，1980.

[2]Jiawei Han，Micheline Kanmber.数据挖掘：概念与技术（第二版）[M].范明，孟小峰译.北京：机械工业出版社，2008.

[3]吕晓玲，谢邦昌.数据挖掘：方法与应用[M].北京：中国人民大学出版社，2009.

[4]张继福，蒋义勇，胡立华.基于概念格的天体光谱离群数据识别方法[J].自动化学报，2008，34（9）：1060-1066.

[5]金义富，朱庆生，邢永康.一种基于关键域子空间的离群数据聚类算法[J].计算机研究与发展，2007，44（4），651-659.

[6]Chawla Sanjay，Sun Pei.SLOM：a newmeasure for localspatialoutliers[J].Knowledge and Information Systems，2006（9）：412-429.

[7]薛安荣，鞠时光，何伟华，等.局部离群点挖掘算法研究[J].计算机学报，2007，30（8）：1457-1458.

[8]赵向兵.一种改进的基于加权属性的SLOF离群点挖掘算法[J].山西大同大学学报：自然科学版，2011，27（3）：11-13.

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

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

Research on Outlier Detection

ZHAO Xiang-bing1，BAIWei2
（1.School ofMathe matic s and Computer Science，ShanxiDatong University，Datong Shanxi，037009； 2.Taiyuan R adio and T elevision U niversity，T aiyuan Shanxi，030012）

This paper analyzed and compared outlier detection algorithms through full investigation.The characteristics of each algorithm was summarized.Furthermore several hot issueswere discussed and prospected in order to prepare further research of outlier detection algorithms.

outlier data；high-dimension outlier；data stream；distribution outlier 〔责任编辑 高海〕

TP311

A

1674－0874（2012）02－0010－04

2011-02-28

赵向兵（1978-），男，山西大同人，助教，研究方向：数据挖掘。