孤立点挖掘算法研究.doc

孤立点挖掘算法研究杨永铭，王喆（兰州交通大学 电子与信息工程学院，甘肃 兰州 730070）摘 要：本文针对孤立点检测算法在现时中的应用展开研究。通过对当前的几种孤立点检测算法进行全面深入的分析与比较，归纳和总结了它们的特点。本文还对现有的高维和空间数据中孤立点检测算法进行了分析和研究，从而便于研究者以这些算法为基础，做进一步分析，提出新的改进算法。关 键 词：数据挖掘；孤立点；空间数据；数据流；异常检测中图分类号：TN92 文献标识码：A Research of Outlier Mining AlgorithmYang Yong Ming, Wang Zhe（Institute of Electronic and Information Engineering，Lanzhou jiao tong University，Gansu 730070，China）Abstract: This paper mainly study the outlier detection algorithm in the application of the present. Through a comprehensive in-depth analysis and comparison to several of the current outlier detection algorithm, their features were summarized. This paper also analyse and research the outlier detection algorithm in high dimensional data and spatial data. Based on these algorithm, reserchers can proceed a further analysis and pose a new improved algorithm. Keywords: data mining; outlier; spatial data; data stream; anomaly detection1 引言孤立点检测是数据挖掘中的一个重要方面。最早Hawkins1给出了孤立点（离群点或异常点）的本质性定义：孤立点如此不同与数据集中的其它数据，以至于使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。孤立点可能是由于度量或执行错误产生的，也有可能是由于固有数据变异产生的，或者其它原因。很多数据挖掘算法通过各种改进来尽量减少孤立点对挖掘结果的影响，或者在挖掘过程中排除孤立点。然而孤立点可能隐藏着重要的信息，也许比一般的数据更有价值。因此人们开始逐渐研究孤立点挖掘算法。孤立点检测的基本思想是给定一个包含n个数据对象的集合，及预期的孤立点的数目k，发现与剩余的数据相比是显著相异的、异常的或不一致的前k个对象。孤立点挖掘问题可分为两个子问题1：（1）在给定的数据集合中定义数据的不一致。（2）找到有效的方法来挖掘这样的孤立点。孤立点挖掘最早应用在统计学领域，在一定程度上，它与聚类分析有相似性。但是两者在概念和目的性方面还有偏差。实际生活中，孤立点挖掘有着广泛的应用，例如网络入侵检测，信用卡欺诈，金融审计，影像处理，恶劣天气预测等。2 孤立点挖掘算法 近些年来人们提出了大量的孤立点检测算法，大致可以归纳为以下几类：基于统计的方法，基于距离的方法，基于偏移的方法，基于聚类的方法，基于密度的方法。2.1基于统计的孤立点检测算法基于统计的方法是出现得最早的离群点检测方法。对给定的数据集合假设了一个分布或概率模型，然后根据模型采用不一致性检验来确立孤立点。基于统计的孤立点挖掘方法易于理解，实现起来也比较方便，但主要的缺点是绝大多数检测仅对数据分布满足某种概率分布的数值型单维数据集较为有效，然而许多数据挖掘问题要求在多维空间中发现孤立点。同时，统计学的方法要求关于数据集合参数的知识，但是，这参数有可能是未知的。当没有特定的检验时，该类方法不能确保所有的孤立点被发现。2.2基于距离的孤立点检测算法（distance-based）基于距离的方法最早是由Knorr和Ng2在1998年提出的。他们用DB（p,d）来表示数据集中的孤立点，采用不同的参数p与d，DB（p,d）可以表示所有的孤立点。与此定义相应的算法有三种，它们是基于索引（index-based）的算法3，嵌套循环（nested-loop）算法4,5，基于单元或划分（cell-based）的算法6等。它们的具体算法不在赘述。基于索引的方法依赖多维索引结构（R-trees，X-trees，KD-tress等）的性能。随着维数的增加，所有的索引结构的性能迅速下降，使得算法性能不佳。NL算法可以避免构建索引结构，减少了算法的I/O次数。以上两方法的算法时间复杂度为O(kn2)，当遇到大量数据集时它们还有待改进。基于单元的方法是把数据集划分为单元，逐个单元的检测，而非逐个对象的检测。它的时间复杂度为O(ck+n) ，其中ck取决于电源的个数和维数k。Knorr和Ng通过试验证明，当k的点q不超过n-1个，即 |qD| n-1，那么称p为孤立点。如果对数据对象根据它们的距离进行排序，那么前n个点就被看作孤立点。他们用聚类算法首先对数据集进行聚类，然后在类中发现孤立点。相对于DB（p,d）孤立点挖掘，孤立点挖掘方法人为干预的因素要小一些。但它也有自身缺陷，就是要计算数据集中所有点的，这显然影响到算法的效率。对低维空间的数据此方法优于索引算法和NL算法，但对于高维数据此算法性能不高。 Bay和Schwabacher5在沿用Rastogi和Ramaswamy对于异常定义的基础上，提出了一种基于随机抽样的检测方法，它通过随机抽样的方法，减少了寻找k近邻的范围，在试验数据上获得了几乎线性的计算复杂度。随着人们对基于距离的方法的不断研究，一些新的、较好的算法也不断的涌现。代表性的算法有：陆声链等8提出了一个判断孤立点的新定义，并设计了基于抽样的近似检测算法。使得算法性能有所提高；另外，徐雪松等9利用聚类算法与第 k个最近邻居的原理提出了基于距离的再聚类的离群点算法，它克服了一些基于距离算法的缺点，并取得了较好的试验结果。与基于统计的方法相比，它有以下几个优点：（1） 人们不必对数据集的相关信息（数据服从哪种统计分布模型，数据类型特点等）足够了解。实际上在给出了距离的度量，并对数据进行预处理后，则可找出数据集中的离群点。（2） 它在理论上可以处理任意维任意类型的数据，这就克服了基于统计方法仅能检测单个属性的缺点。 2.3基于偏移的孤立点检测算法基于偏移的检测算法是通过检查一组对象的主要特征来确定孤立点。与给出的描述“偏移”的对象被认为是孤立点。（1）序列异常技术：Aming和Argrawal10提出一种序列孤立点（sequential exception）的概念。这个算法复杂度与数据集大小呈线性关系，有优异的计算性能。但是并没有得到普遍的认同，这是因为序列异常在概念上有一定的缺陷，它对孤立点存在的假设太过理想化，对现实复杂数据效果不太好。（2）OLAP数据立方体技术：在大规模的多维数据中采用数据立方体来确定反常区域.如果一个立方体的单元值显著地不同于根据统计模型得到的值，该单元被认为是一个异常。此方法是发现驱动探索的一种形式。此方法由于搜索空间很大，人工探测非常困难。2.4基于聚类的孤立点检测算法聚类分析是数据挖掘的重要手段之一。目前有很多的聚类算法，如CLARANS，DBSCAN，STING，BIRCH，ROCK等。它们具有一定的异常处理的能力，但是它们的主要目标是产生聚类，即寻找性质相同或相近的记录并归为一个类，这不同孤立点检测的意义和目的。孤立点只是聚类分析的副产品而已。在实际应用中，可以先采用聚类算法对数据集进行聚类，然后再采用孤立点检测算法来发现离群点。但是把两个相互独立的算法结合进行计算势必会影响算法的整体效率，所以如何把两类算法有效地结合来产生较好的试验效果，成为人们研究的重点。2.5基于密度的孤立点检测算法基于密度的方法是在基于距离的方法上改进而来。基于密度的异常观点比基于距离的异常观点更贴近Hawkins的异常定义，因此能够检测出基于距离异常算法所不能识别的局部异常21。局部异常观点摈弃了以前所有的异常定义中非此即彼的绝对异常观念，更加符合现实生活中的应用。Breuning11提出了局部异常的概念及相应的异常检测方法（DBOM算法），即数据集中的每个对象的异常程度用局部异常因子LOF来衡量。也就是说是否是孤立点不仅仅取决于它与周围数据的距离大小，而且与临域内的密度情况有关。一个对象邻域内的密度可以用包含固定结点个数的邻域半径指定半径邻域中包含的结点数来描述。这样就不会像DB(p,d)异常点那样遗漏一部分孤立点。LOF算法中充分体现了“局部 ”的概念，每个点都给出了一个离群程度，离群程度最强的那几个点被标记为离群点。文献12从两个方面对LOF进行推广：一是由原来的一个邻域的变化为两个（计算密度邻域和比较密度邻域）；二是剪除非异常对象来减小计算代价；因此，使得算法的效率比传统的LOF算法有所提高。在现有的计算局部孤立因子 (LOF) 算法中，把具有很高LOF值的对象作为孤立点。计算LOF要耗费很大的计算量，针对此问题Malik Agyemang提出修改算法，即局部稀疏系数(LSC)算法13。这种方法主要是引入了局部稀疏系数（LSC）这一概念，根据每个对象的LSC值按从大到小的顺序排列整个数据集并把前 n 个对象作为孤立点。但是，此方法在实际应用中计算量亦是不小，效率还有待提高。另外，岳峰等14利用反向K近邻(RKNN)15的这个概念提出一个孤立点检测算法(ODRKNN)，在综合数据集和真实数据集上的实验结果表明，该算法能有效地检测出孤立点，且算法的效率高于典型的基于密度的孤立点检测算法 LOF 和 LSC 的效率。表1 几种孤立点检测算法检测方法 典型算法特点（优缺点）效率（时间复杂度）适用性基于统计的方法单样本多个离群检测算法(ESD)易于理解，只对单维数据集较为有效。需要知道数据集的先验知识。与数据集大小，及采用的概率分布模型有关。一般为 O（nlogn）不适合高维数据基于偏离的方法序列异常技术概念有缺陷，遗漏了不少孤立点时间复杂度与数据集大小成线性关系适用性不高OLAP数据立方体技术搜索空间大，人工探测困难不高可适用于多维数据中基于聚类的方法聚类与孤立点检测算法结合先聚类，后检测异常点。效率不高适用于大规模的数据集基于距离的方法索引算法I/O代价较高，性能与索引结构有关一般为O(kn2)适用于低维空间的数据集NL算法理论上可以处理任意维，减少了算法的I/O次数一般为O(kn2)适用于较低维，小规模的数据集单元算法在低维空间时优于NL算法O(ck+n)一般适用于较低维基于密度的方法LOF算法可以识别局部异常O(nlogn)不适用于高维空间LSC算法O(k n2) 表1总结了上述几种孤立点检测算法的主要特性。总的来说，以上这些面向统计数据的方法由于忽略了空间信息，因此若在空间数据集中直接应用，其结果可能导致发现的离群点没有现时意义，或产生错误的判断。3 高维空间孤立点检测算法3.1高维孤立点检测研究发现，高维数据的特性不同于低维数据，因此高维空间中的离群点发现方法区别与低维数据的孤立点发现。首先，高维空间的数据分布得比较稀疏，这使得高维空间中数据之间的距离尺度即区域密度不再具有直观的意义。其次，从一个数据点来看，其他点到它的距离落在一个范围很小的区间内，很难给出一个合适的近似度阈值，来确定哪些点是与它相似的，哪些点不是。 为解决这个问题，人们开始尝试将高维空间的数据投影到低维子空间中来发现数据异常点。他们不再平等地看待各个维，而是通过某些标准选择出一些维，在这些维中组成的自空间中寻找近邻。但随着维数的增加，对维数进行组合得到的子空间个数成指数级增长（数据集为n，可能的组合有2 n）。显然，我们不可能对每个子空间进行投影，再从中择优选择，因为这样的计算代价太大。Aggarwal等在文献16中提出了高维空间进行离群点挖掘的几点建议，同时还提出运用遗传算法的方法来优化问题的求解过程。如何有效的选择最优子空间就成为关键。要构造好的高维空间离群点检测算法，我们必须充分利用高维数据自身的特性 ，处理好数据集的主体聚类性与稀疏性之间的矛盾，以提高异常检测算法的效率。 3.2空间孤立点检测算法空间孤立点还没有一个统一的定义和模型。Shekhar等17认为，空间孤立点是指与邻居具有不连续性的空间点，或者是偏离观测值以致被认为与其它点不同。即具有与其空间邻居显著不同的空间属性值的空间对象。空间孤立点挖掘是空间数据挖掘领域的一个重要研究内容，此类知识的发现能为我们提供丰富的信息，在地理信息系统、交通控制、公共安全、卫生健康、环境检测等领域有广泛的应用。空间数据库中的数据挖掘不同于原有的面向统计数据库的数据挖掘，它需要区分空间维和非空间维。空间维是指空间属性，包括点、线、面等几何属性与拓扑属性。非空间维又叫属性空间维是指非空间属性，包括长度、归属、地名与各种非空间度量值等等。现有的空间离群点挖掘可分为定量测试和基于图形的两种方法。定量的方法是用测试来区分离群点和非离群点。代表性的算法有Scatterp lot18, 19和Moran Satterp lot20；基于图形的方法是在空间数据的可视化基础上，将空间离群点突出的显示出来以达到检测效果17。随着空间数据库挖掘的不断发展，Shekhar等提出了新的空间离群点的定义和查找方法21。此方法把空间属性和非空间属性区分来考虑，用空间属性来定义邻域函数，而用非空间属性来给出比较函数。基本思想是利用空间点邻域的平均属性与某一空间点的属性值进行比较，以判断空间点是否为孤立点。对于空间数据库的空间离群点挖掘方法整体而言还效率还较低，不能查找局部离群点。人们针对原有算法的不足，提出了一些改进算法。文献22采用定量分析的方法对空间属性里的属性关系进行度量，且引进了多属性相关矩阵的概念，并用动态的索引结构来搜索空间邻域，可较准确地发现离群数据。文献23在Shekhar对空间离群点定义的基础上，用空间属性来确定邻居关系，非空间属性定义距离函数，使用Mahalanobis距离检测孤立点。并给出了采用不同的邻域搜索方法，相应的算法复杂度。文献24提出了空间偏离因子（SOF）的概念，它较精确地反映了对象的非空间属性偏离它邻居的程度。与类似算法相比SOF算法也具有较好的效率。马荣华和何增友25从一个相反的角度来定义和挖掘空间离群点。认为空间离群点是在和其非空间属性邻域内的其它空间对象在空间位置上差异十分显著的空间对象。即用非空间属性来定义邻域关系，用空间属性来定义距离函数。他们还设计了SOD算法，并验证了此算法的有效性和优越性。4 其它的孤立点检测方法研究近年来，基于数据流数据的挖掘算法研究受到越来越多的重视。数据流离群点挖掘更因其挖掘对象具有动态性、不可复读性、数据量大等特点而成为离群知识发现研究的一个难点。人们研究指出主要有Time Series，Cash Register,Turnstile三种数据流模型，其一般性逐渐增大。文献26提出了针对第一种模型的数据流异常检测算法。此算法中用到的离群点定义只是针对于Time Series数据流模型的，所以它只能解决这类模型的孤立点检测问题。文献27提出了针对第二种数据流的检测算法，此算法在一定程度上还可以应用到Turnstile数据流模型。如何进一步地增强算法的有效性，提高算法的性能，以及如何把算法扩展到更为一般的数据流模型成为下一步研究的重点。5 结论与展望异常检测在现时生活中已经的到大量的应用，将来还会在更为广泛的领域发挥更为重要的作用。由于现有的一些检测算法自身的各种缺陷，所以在处理高维空间数据，时序数据，以及GIS数据时算法的有效性，执行效率还不令人满意。如何提高算法的可行性和可移植性与算法的时空效率是我们以后工作的重点。对大规模高维空间数据，动态性的大量数据，时间序列数据进行离群检测将是离群数据挖掘的进一步的研究方向。参考文献：1Hawkins D. Identification of OutliersM. London: Chapman and Hall, 19802E.Knorr, R.Ng. Alogrithms for Mining Distance-based Outliers in Large Datesets. In VLDB,1998.3 Han Jiawei, KamberM. DataM ining: Concepts and TechniquesM . Academic Press, 2001.4E.Knorr, R.Ng., V.Tucakov. Distance-based Outliers: Algorithms and Applications. In VlDB,2000.5S.Bay, M.Schwabacher. Mining Distance-based Outliers in Near Linear Time with Randomization and Simple Pruning Rule. In SIGKDD,2003.7S.Ramaswamy, R.Rastogi, K.Shim. Efficient Algorithms for Mining Outliners from Large Datasets. In SIGMOD,2000.6F.Angiulli, C.Pizzuti. Fast Outlier Detection in High DiMensional Spaces. In PKDD,2002.8陆声链, 林士敏. 基于距离的孤立点检测及其应用J. 计算机与数字工程, 2004,32(5).9 徐雪松, 刘凤玉. 一种基于距离的再聚类的离群数据发现算法J. 计算机应用, 2006,26(10).10 Arning A, Agrawal R, Raghavan P. A Linear Method for Deviation Detection in Large Databases C . Proc. of 1996 In.t Conf. Data Mining and Knowledge ( Special Issue on High Performance Data Mining) , 2000.11 Breunig M M, Kriegel H P, Ng R,et al. LOF: Identifying Density-Based Local Outliers C. Dallas ,Texas : Proc. of ACM SIGMOD Conf , 2000.12 Chiu A L, Fu A W. Enhancements on local outlier detection C. The (IEEE) 7th Int.Database Engineering and Applications symposium, (IDEAS) Hong Kong 2003.13 Malik Agyemang. Local Sparsity Coefficient-Based Mining of OutliersD. University of Windsor, 2002.14岳峰, 邱保志. 基于反向K近邻的孤立点检测算法J. 计算机工程与应用, 2007,43(7).15 Korn F, Muthukrishna S.Influence sets based on reverse nearest neighbors queriesC. Proceedings of ACM SIGMOD, 2000.16 Aggarwal C C,Yu P. Outlier Detection for High Dimensional Data. In Proc.of ACM SIGMOD,2001.17 Shekhar S, Lu C, Zhang P. Detecting Graph-based SpatialOutlier: Algorithms and Applications (A Summary o