基于距离的异常点挖掘算法研究

1、基于距离的异常点挖掘算法研究董沛然，王莉（北京邮电大学 电子工程学院，北京 100876）510152025303540摘要：异常点挖掘是一种从数据中分析并发现潜在的反常对象的数据挖掘技术，它在实际生产生活中越来越受到人们的关注，并逐渐成为计算机领域的一个研究热点。本文系统地研究了基于距离的异常点挖掘算法，针对循环嵌套算法和单元格算法这两种最常用的基于距离的异常点挖掘算法，对比分析了它们的算法思想和时间复杂度，并通过海量数据进行算法仿真，总结出其各自的优缺点及适用场合，为实际应用中异常点挖掘算法的选择提供了参考依据。关键词：计算机软件与理论；数据挖掘；异常点检测中图分类号：tp311resea

2、rch in distance-based outliers detection algorithmdong peiran, wang li(school of electronic engineering, beijing university of posts and telecommunications, beijing100876)abstract: outliers detection is a data mining technology to analyze and find potential abnormalphenomena from the data. this tech

3、nology has attracted increasing attention and it has nowbecome a focus for research in computer field. this paper systematically discusses algorithm ofoutliers detection based on distance, comparing and analyzing the main idea of the algorithm andtime complexity of the two most common outliers detec

4、tion algorithm based ondistancenested-loop algorithm and cell-based algorithm. the paper also summarizesrespectively the various occasions where these two most common outliers detection algorithm canbe used through algorithm simulation of mass data, providing references for the selection ofoutliers

5、detection algorithm in practical applications.key words: computer software and theory; data mining; outliers detection0 引言在现代工业生产和经济活动中，人们越来越关注数据集合中的异常数据。异常数据是与一般行为或模型不一致的数据，它们是数据集合中与众不同的数据，这些数据并非随机偏差，而是产生于完全不同的机制。异常的成因主要来自于以下几个方面1：（1）数据来源于不同的类；（2）自然变异，即许多数据集可以用一个统计分布建模，如用正态(高斯)分布建模，其中数据对象的概率随到分布中心距

6、离的增加而急剧减少，也就是说，大部分数据对象靠近中心，数据对象显著地不同于这个中心的似然性很小；（3）数据测量和收集的失误。 异常点挖掘就是发现与其它大部分对象不同的对象，属于数据挖掘中的一个分支。在欺诈检测、市场分析、医疗诊断等领域，异常点挖掘是一项很有意义的研究。因为数据集合中数据的多样性和多维性，所以异常点挖掘问题通常比较困难2。常见的异常点挖掘算法包括基于统计模型的方法、基于密度模型的方法、基于偏离模型的方法和基于距离模型的方法3。本文主要讨论基于距离模型的异常点挖掘算法，并在数据集规模增大和数据分布状况改变的情况下，对比分析单元格算法和传统算法的优劣。作者简介：董沛然（1986-），

7、男，北京邮电大学电路与系统专业工学硕士，主要研究方向为数据挖掘、异构通信网络的融合等通信联系人：王莉，女，北京邮电大学电子工程学院讲师，计算机和通信领域专家. e-mail: liwang-1-1 基于距离的异常点挖掘问题模型直观上，一个异常点是指在一个数据集合中这样的数据点：远离它的数据点较多，至少45要占 p ´100%，而接近它的数据点较少，至多占(1-p) ´100%。这里，称为临界邻居比例4。因此，从本质上讲，所谓异常点是指相对孤立的数据，即在其邻域内数据点较少的数据点。图 1 给出了二维数据集中异常点的示例（其中 a、b 两点为异常点）。图 1二维数据集中的异常

8、点50遵循这个直观描述，下面给出基于距离的异常点的精确定义：设存在一维点的集合a，a = o1 , o2 , o3 ,.,on ，oi = (xi1 , xi 2 ,.,xim ),i = 1,2,.,n ，其中 oi 为 a 中的数据点， xim 为 oi 的第 个分量。定义 a 中任意两点 o p 、 oq 间的距离为：mi =1556065其中 为任意正整数。若 =1，则：mi =1此时的距离称为绝对距离。若 =2，则：mi =1此时的距离称为欧氏距离。于是引入下面的定义：定义 1 对于 a 中的任一点 o p ，给定一个比较小的正数 d>0，若效用点集中的任一点 oq满足条件：

9、d k (op , oq ) <d，则称 oq 为 o p 的 d-邻近点，称所有 d-邻近点的集合为点 o p 的d-邻域5。定义 2 对于 a 中的任一点 o p ，选取一个经验临界值 m（视具体情况而定），设点 o p-2-d k (o p , oq ) = (å x pi - xqi )1 / kkd1 (o p , oq ) = å x pi - xqid 2 (o p , oq ) = (å x pi - xqi )1 / 2k的 d-邻域中的点的个数为 n p 若 n p <m，则称该点 o p 为 a 中的异常点5。这里 d 称为临界距

10、离，m 称为临界邻居数目。定义 2 是基于距离的异常点的数量化定义。7075802 循环嵌套算法在传统的循环嵌套算法中，需要计算集合 a 中各数据点之间的距离，再计算每个点 d-邻域内点的个数，才能判断这个点是否为异常点。具体流程包括以下四个步骤：步骤一 数据准备数据准备阶段的任务是数据的中心化和标准化。由于 a 中不同维度 x*i 和 x* j 表示的是数据对象的不同属性，它们往往会使用不同的度量单位，其数值也可能相差十分悬殊。在这种情况下，变化量大的维度可能会淹没变化量小的维度，从而使得后者应有的作用的不到反映6。为了确保个维度在分析中的地位相同，需要对数据进行中心化和标准化变换。中心化变

11、换的目的是使各种维度的量值都有相同的基点，通常在原始值上减去相应维度的平均值：记第 j 个维度的平均值为：x j =1 nn i=1那么对第 j 个维度的 n 个数据点所实施的中心化变换为：xij¢ = xij - x j ，在所有维度上都实施上述变换，则每个维度的均值都为 0，即各个维度的取值都有相同85的基点。标准化变换的目的是确保个维度的变化范围相等。当用不同的方法衡量变化范围时，就有不同的标准化变换方法7。常用的有：（1）最大最小归一法将 a 中每个点的每个分量都除以相应维度上取值的绝对值的最大值。90xij¢ =xijmax xij， i=1,2,n；j=1,2,

12、pi归一化后数据的取值介于-1 到 1 之间。该方法对于具有类均匀分布的数据归一化效果较好。（2）总和标准化将 a 中每个点的每个分量都除以相应维度上的取值之和。95xij¢ =xijni =1ij， i=1,2,n这种标准化方法所得的新数据集满足：ni=1ij= 1 ，（3）均值标准差标准化-3-å xij ，å xå x¢xij¢ =xij - m js j， i=1,2,n，100其中 m j ，s j 分别为第 j 列全部数据的均值和标准差。采用这种方法所得标准化后的数据满足：m ¢j =1 nn i =1n i=1

13、1均值标准差标准化方法特别适用于符合正态分布的数据，处理后的绝大多数数据值将位于-1 到 1 之间。105（4）极差标准化第 j 个维度的极差为：1£i£n 1£i£n第 j 个维度的 n 个数据所实施的极差标准化为：xij =xij - x jr j， i=1,2,n110115经过这种标准化所得的新数据集在各分量上的极大值为 1，极小值为 0，其余的数值均在 0 与 1 之间。经过标准化变换后，个变量的基点相同，变化范围也相同了。步骤二 计算各点之间的距离计算 a 中每两点之间的距离：mi=1步骤三 计算每个点 d-邻域内点的个数对于一个比较小的正数

14、 d，个数 n i 。步骤四 判断每个点是否为异常点oia ，i=1,2,n，统计 oi 的 d-邻域之内数据点的120125给定经验临界值 m，若 n i <m，则可以判定点 oi 为集合 a 中的异常点。3 单元格算法传统的异常点挖掘算法需要计算每两个数据点间距离，时间复杂度很高。为了解决这个问题，出现了异常点挖掘的单元格算法。单元格算法的基本思想是，在集合 a 中，有些点分布很集中，这些点不必计算它们之间的距离就能判定为非异常点；而另外一些数据点分布得比较孤立，在判断这些点是否异常时才需要计算它们与周围点的距离。异常点挖掘单元格算法相比于传统算法的优势在于，对于那些非常集中的点，由

15、于其分布密度很高，因此可以判断它们都不是异常点，不用计算这些点之间的距离，减小了时间复杂度8。二维数据集空间的算法流程如下：130步骤一把二维空间划分为边长为 l =d2 2的一些单元格（d 为邻域半径）（见图 2）。对-4-å1 nxij¢ = 0 ， s ¢j = ( å (xij¢ - m ¢j ) 2 ) 2 = 1r j = max ( xij ) - min( xij ) ， j=1,2,pd k (op , oq ) = (å x pi - xqi )1 / kk于某个单元格（图中白色方格），定义其第一层邻居为

16、这个单元格周围的八个单元格（图中灰色方格），其第二层邻居为从第一层邻居向外的两圈单元格（图中黄色方格）。那么，一个单元内的所有点到其第一层邻居内的点最远距离为 d，第二层邻居外的点到这个单元所有点的距离不小于 d。135下文中用 c 表示某个单元格或这个单元格中点的数目，用 c.neighbor1 表示单元格 c的第一层邻居内点的数目，用 c.neighbor2 表示单元格 c 的第二层邻居内点的数目。图 2二维数据集空间的单元格划分步骤二遍历每个非空单元格，依次试探性地判断其内部的点是否为异常点。140对于某单元格 c：若 c>m，则 c 内无异常点，并且 c 的第一层邻居内也无异常点

17、；若 c+c.neighbor1>m，则 c 中无异常点；若 c+c.neighbor1+c.neighbor2<m，则 c 中的所有点均为异常点。步骤三对于步骤二中未能判断出其内部是否为异常点的单元格 ，依次判断其内部每个点145'''骤二的多次筛选可知， 和 .neighbor2 的数目都比较小，所以需要计算的点间距离实际上很少，不会增加很多时间复杂度。150对于 k 维数据空间，只需调整二层邻居单元格的变长为d2 k，其它处理方法与二维相同9。4 仿真分析下面分别考察在数据集的规模增大和数据分布状况改变时，单元格算法和传统算法在时间复杂度上的变化。15

18、5用 matlab 实现循环嵌套算法和单元格算法，输入不同的数据集，运用循环嵌套算法和单元格算法分别进行异常点挖掘，观察两种算法的运行时间。-5-是否为异常点。在这一步，对于 内的每个点 o ，都需要判断它周围 d-邻域内有多少个点。不过，由于 o 到 和 的第一层邻居内各点的距离都小于 d，而到 的第二层邻居以外各点的距离都大于 d，因此这里只需要计算 o 到 的第二层邻居内各点的距离。而且，由算法步4.1数据集规模对两种算法性能的影响数据集规模包含两个方面：数据集中数据点的个数（行数）和属性个数（列数）。下面分别讨论：160属性个数不变，数据点的个数增多测试数据：取均值为 50，标准差为

19、10 的正态分布数据集，属性个数固定为 2。仿真结果如表 5.1：表 1数据点个数增加情况下的算法运行时间165算法运行时间随着点数增大而变化的情况如图 3 所示：图 3数据点个数的增加对算法运行时间的影响可以看出，单元格算法的时间复杂度低于循环嵌套算法，并且随点数增大的趋势也低于循环嵌套算法。170（2）数据点的个数不变，属性个数增多：测试数据：取均值为 500，标准差为 10 的正态分布数据集，固定数据点的个数为 800。测试结果如表 5.2 所示：表 2数据点个数增加情况下的算法运行时间-6-数据点个数10002000300040005000600070008000900010000循环

20、嵌套算法运行时间(秒)0.351.312.868.788.1111.6715.7321.3026.3032.57单元格算法运行时间(秒)0.070.230.470.771.651.722.742.934.324.97数据集维数12345循环嵌套算法运行时间(秒)0.140.240.150.120.19单元格算法运行时间(秒)0.030.150.320.370.43175算法运行时间随着属性个数增大而变化的情况如图 4 所示：图 4数据集维数的增加对算法运行时间的影响可以看出，单元格算法的运行时间随着维数增大而增大的趋势比较快，这是因为维数越大，划分出的单元格就越多，算法时间也越长。1804.2

21、数据集分布对两种算法性能的影响下面研究数据分布不同时，两种算法的比较。用 matlab 生成两份一维，含有 5000 个数据点的数据集，第一个数据集服从均值为 50、标准差为 20 的正态分布；第二份数据集服从均值为 50、标准差为 3 的正态分布。对两个数据集分别执行两种挖掘算法，其运行时间见表 3：185表 3不同数据集分布下算法的运行时间可见标准差的不同对循环嵌套算法运行时间几乎没有影响，而对单元格算法影响很大。这是因为当标准差很小时，数据较为集中，这时有更多的数据点排除了异常点的可能而不用计算它与周边点的距离，因而算法效率较高。因此，在实际应用中，对于分布比较集中的数据集，应首选单元格

22、算法；而对于分布较190为分散的数据集，应首选循环嵌套算法。总结本文介绍了基于距离模型的两种异常点挖掘算法原理，并通过 matlab 仿真对比了两种算法的时间复杂度，指出循环嵌套算法适用于数据集维数较大，且分布的标准差较大的场合，而单元格算法适用于数据集对象数目较多，且分布的标准差较小的场合。本文的分析为-7-数据集数据集一数据集二循环嵌套算法运行时间（秒）8.118.13单元格算法运行时间（秒）3.162.09195200205210实际应用中异常点挖掘算法的选择提供了参考。参考文献 (references)1 杨宇. 多指标综合评价中赋权方法评析j. 统计与决策，2006，217(7)：17 一 19.2 breiman l，friedman j h，olshen r a. classification and regression