简介

孤立点是数据集中不符合一般模型的那些对象，即和其它的数据有着不同的性质。它可能是度量或执行错误所导致的，也可能是固有数据变异性的结果。对此，Ｈａｗｋｉｎｓ［１］给出了其本质性定义：孤立点是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。
一般的，孤立点挖掘问题可以被看作两个子问题［１］：（１）在给定的数据集合中定义什么样的数据可以被认为不一致的；（２）找到一个有效的方法来挖掘这样的孤立点。

分类及应用

孤立点探测是数据挖掘中一个重要方面，用来发现＂小的模式＂（相对于聚类），即数据集中间显著不同于其它数据的对象。孤立点探测算法大致可以分为基于统计（ｓｔａｔｉｓｔｉｃａｌ－ｂａｓｅｄ）的方法，基于距离（ｄｉｓｔａｎｃｅ－ｂａｓｅｄ）的方法，基于偏差（ｄｅｖｉａｔｉｏｎ－ｂａｓｅｄ）的方法，基于密度（ｄｅｎｓｉｔｙ－ｂａｓｅｄ）的方法，以及高维数据的孤立点探测。孤立点挖掘有着广泛的应用：在信用卡欺诈探测中发现的孤立点可能预示着欺诈行为，而及时发现这种信用卡欺诈行为对商业银行而言相当重要，可以避免不必要的经济损失；在市场分析中，可用于确定极低或极高收入的客户的消费行为；在医疗分析中，可用于对多种治疗方式的不寻常的反应等；在网络安全方面；孤立点挖掘应用于网络入侵检测；在数据质量分析中，可以用孤立点挖掘算法检测错误数据；此外还可以应用到气象预报、个人隐私保护等方面。

传统的孤立点挖掘算法

基于统计的方法

基于统计的方法假设给定的数据集服从一个随机分布（如正态分布等），用不一致性测试（）识别孤立点。但是这种方法存在一个问题：在许多情况下，用户并不知道这个数据分布，而且现实数据也往往不符合任何一种理想状态的数学分布；即使在低维（一维或二维）时的数据分布已知，在高维情况下，估计数据点的分布也是极其困难的。

基于距离的方法

Ｋｎｏｒｒ和Ｎｇ［２］提出一种基于距离的孤立点探测方法：数据集Ｓ中至少ｐ＊１００％的对象与Ｏ的距离大于距离Ｄ。采用不同的参数ｐ和Ｄ，ＤＢ（Ｐ，Ｄ）－ｏｕｔｌｉｅｒ可以表示所有的基于统计的孤立点。在基于距离的孤立点定义下，分别有基于索引（ｉｎｄｅｘ－ｂａｓｅｄ）的算法，嵌套循环（ｎｅｓｔｅｄ－ｌｏｏｐ）算法和基于单元（ｃｅｌｌ－ｂａｓｅｄ）的算法。基于索引的算法可以通过对最近邻查询或以Ｏ为中心的范围查询的回答来实现寻找所有ＤＢ（Ｐ，Ｄ）－ｏｕｔｌｉｅｒ。基于多维索引结构Ｒ－Ｔｒｅｅ或ｋｄ－Ｔｒｅｅ算法复杂度是Ｏ（ＫＮ２），但它的缺点是：需要建立多维索引结构，费时；嵌套循环算法将内存缓冲区空间划分成相等的两部分，数据集分成几个大小和每部分缓冲区相等的逻辑块，通过认真选择调入每一部分缓冲区的次序，使Ｉ／Ｏ次数最小算法复杂度是Ｏ（ＫＮ２），它具有：不需要建立多维索引结构，但选择划分区域也较费时的特点。基于单元（ｃｅｌｌ－ｂａｓｅｄ）的方法：数据空间被划分为边长为Ｄ／２ｋ１／２的单元；每个单元有两个包围层；第一层为１倍的单元厚，第二层为ｉｎｔ（２ｋ１／２－１）＋１倍的单元厚。对于该种基于距离的方法小结：由于索引建立的开销很大，简单索引算法没有竞争性；当ｋ＜＝４时，基于单元的算法在Ｎ越大时优越性越明显；当ｋ＞＝５之后，嵌套循环算法开始显现出优势。

基于距离的算法的改进

Ｋｎｏｒｒ和Ｎｇ基于距离的孤立探测方法的缺陷在于：输入参数ｐ与Ｄ很难确定，并且对于不同参数，结果有很大不稳定性。这就需要用户反复输入ｐ与Ｄ进行测试，以确定一个满意解；不能给定孤立的程度，且算法的复杂度较高。Ｒａｓｔｏｇｉ和Ｒａ－ｍａｓｗａｍｙ［３］提出了一个新的基于距离孤立点定义，用Ｄｋ（ｐ）表示点ｐ和它的第ｋ个最近邻的距离，给定ｄ维空间中包含Ｎ个点的数据集，参数ｎ和ｋ（自然数），如果满足Ｄｋ（ｐ）＞Ｄｋ（ｐ＇）的点ｐ＇不超过ｎ－１个，那么称ｐ为Ｄｎｋ孤立点。如果对数据点根据它们的Ｄｋ（ｐ）距离进行排序，那么前ｎ个点就被看作孤立点。循环嵌套算法（Ｎｅｓｔｅｄ－ｌｏｏｐＡｌｇｏｒｉｔｈｍ）作为改进后的基于距离的算法，每次处理一个点ｐ，需要扫描一遍数据库，总共需要扫描Ｎ遍（Ｎ为数据点数）。基于索引的算法（Ｉｎｄｅｘ－ｂａｓｅｄＡｌ－ｇｏｒｉｔｈｍ）用类似Ｒ＊－树的空间索引结构存储，可以减少扫描数据库的次数。改进后的基于划分的算法，如果某个点的Ｄｋ（ｐ）较小的话，那么不可能是Ｄｎｋ孤立点，可以先对数据集进行划分，然后估计每个划分的Ｄｋ（ｐ）的上、下界，如果能判定某个划分不可能包含孤立的话，那么就可以直接把它删除掉；然后再从剩下的划分（侯选划分）来计算孤立点；现有的许多聚类算法可以用来划分数据集，如ＢＩＲＣＨ算法。

基于偏差的方法

Ａｒｇｒａｗａｌ和Ｒａｇａｒａｎ提出了＂序列孤立＂（ｓｅｑｕｅｎｔｉａｌｅｘｃｅｐ－ｔｉｏｎ）的概念中，对于给定ｎ个对象的集合Ｓ，建立一个子集序列｛Ｓ１，Ｓ２，…，Ｓｍ｝，对每个子集，确定该子集与前序子集的差异度的差。为减少输入数据的顺序对结果的影响，可以用不同的次序多次重复上述过程，找出其中光滑因子最大的子集。这个算法复杂度与数据集大小呈线性关系，有优异的计算性能。但是序列孤立在对孤立存在的假设太过理想化，对现实复杂数据效果不太好。

基于密度的方法

基于距离的方法对全局各个聚类的数据提出了统一的P和D的参数，但是如果各个聚类本身的密度存在不同,则基于距离的方法则出出现问题，因此提出了基于密度模型的局部异常点挖掘算法，通过局部异常点因子LOF的计算来确定异常点, 只要一个对象的LOF远大于1, 它可能就是一个异常点。簇内靠近核心点的对象的LOF接近于1,处于簇的边缘或是簇的外面的对象的LOF相对较大，这样便能检测到局部异常点，更贴近于实际的数据集的特性。这种传统的局部异常点的挖掘算法的主要问题在于局部范围的参数Minpts值存在选择上的困难，可以运用多粒度偏差因子代替Minpts来评价，这样便能得到比较好的解决方案。

基于聚类的方法

基于聚类的方法的基本思想是将孤立点挖掘的过程转换成聚类的过程。首先将数据集利用已经成熟的模型进行聚类分析，是数据集形成簇，而那些不在簇中的样本点即被视为异常点进行再处理。除了上述所述的4中基本的聚类方法外，还包括基于网格的的方法等。
基于统计的孤立挖掘应用主要局限于科研计算，这主要是因为必须事先知道数据的分布特征这就限制了它的应用范围。序列孤立挖掘算法提出的序列孤立的概念并没有得到普遍的认同。这是因为序列孤立在概念上仍然有一定缺陷，遗漏了不少的孤立数据。基于距离的算法跟基于统计的算法相比，不需要用户拥有任何领域知识。与＂序列孤立＂相比，在概念上更加直观。更重要的是，距离孤立更接近Ｈａｗｋｉｎｓ的孤立本质定义。

总结

基于密度的孤立观点比基于距离的孤立观点更贴近Ｈａｗｋｉｎｓ的孤立定义，因此能够检测出基于距离孤立算法所不能识别的一类孤立数据－局部孤立。局部孤立点观点摈弃了以前所有的孤立点定义中非此即彼的绝对孤立观念，更加符合现实生活中的应用。实际数据往往具有较大的噪声，因此孤立模式经常只存在于低维子空间中，而在高维空间中难以确定；且以前算法在维数较高时，性能急剧下降。因此Ａｇｇａｒｗａｌ和Ｙｕ提出的高维数据孤立挖掘的方法，采用遗传优化算法，获得良好的计算性能。近几年来，孤立点挖掘算法取得了许多进展：将基于距离和基于密度的算法并行化，能显著提高算法的性能；将高维空间中的点映射到低维空间，进而发现孤立点是高维数据孤立点挖掘的常用措施；而孤立点挖掘算法在气象数据分析，基因数据分析，个人隐私保护等方面的应用，也显示出孤立点挖掘算法具有独特的应用价值。当数据维数较高时，传统孤立点挖掘算法性能急剧下降，高维数据的孤立点的挖掘仍然是研究的难点。