维普资讯 http://www.cqvip.com Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ Ｃｏｎｓｕｌｔｉｎｇ Ｈｅｒａｌｄ 业 Ｑ： 学术论坛 数据挖掘中孤立点检测方法的探讨 董健康李霞 （甘肃学院计算机科学学院 ７３００７０） 摘要：孤立点检测在信息科学研究领域日益受到重视，本文系统地综述了数据库研究领域中孤立点检测的研究现状，对已有各种孤立点 检测方法进行了阐述和比较，展望了孤立点检测未来的研究方向及其面临的挑战。 关键词：数据挖掘 孤立点 检测方法 中图分类号：ＴＰ３ 文献标识码：Ａ 文章编号：０６７３ ０５３４（２００７）０５（ａ）～０１３７ ０ｌ１前言 异常数据在聚类挖掘中常常表现为孤立 点，孤立点就是既不属于聚类也不属于背景噪 立点看作是那些没有“足够多”邻居的对 象，这里的邻居是基于距离给定对象的距离来 定义的。与基于统计的方法相比，基于距离 本。对一个有ｎ个样本的已知数据集，一个可 能的相异度函数是样本集的总的方差。 （２）ＯＬＡＰ数据立方体方法。偏离探测的 声的点，他们的行为与正常的．普遍的行为 有很大的不同，明显偏离其它数据，是一些不 符合数据的一般模型，与存在的其他数据不一 致的数据对象，所谓异常挖掘就是用数据挖掘 方法来发现“小模式”（相对于聚类）即数据 集中明显不同于其他数据的数据对象的挖掘 过程。它可以描述如下：给定一个ｎ个一数据 点或对象的集合，及预期的异常的数目ｋ，发 现与剩余的数据相比是显著相异的、异常的 或不一致的头ｋ个对象。异常挖掘问题可以 被分为如下两个子问题：①在给定的数据集合 中定义什么样的数据可以被认为是异常；②找 到一个有效的方法来挖掘这样的异常。 ２挖掘孤立点的方法 ２．１基于统计的方法 基于统计的方法对给定的数据集假设了 一个分布或概率模型（例如一个正态分布），然 后根据模型采用不一致检验来确定异常。一 个统计学的不一致性检查有两个假设：一个工 作假设和一个替代假设。一个工作假设Ｈ是 一个命题：ｎ个对象的整个数据集合来自一个 初始的分布模型Ｆ，即Ｈ：０．∈Ｆ，ｉ＝１，２，…， ｎ。如果没有统计上的显著证据支持拒绝这 个假设，它就被保留。不一致检验验证一个 对象。０．关于分布Ｆ是否显著地大或小。估 算显著性概率，如果显著性概率足够的小，那 么工作假设被拒绝，替代假设Ｈ被采用，它声 明０，来自另一个分布模型Ｇ。０．可能在一个 模型下是异常，而在另一个模型下是非异常 的，也就是说，结果非常依赖于分布模型Ｆ的 选择。可以用“当０．真的是异常时工作假 设被拒绝的概率”来衡量检测的能力。 基于统计的方法的主要缺点是：①绝大多 数检测都是针对单个属性的，而许多数据挖掘 问题都要求在空间中发现异常。②使用 该方法需要事先知道数据集参数（如正态分 布）、分布参数（如均值、标准差）和离群数 据的个数，而在大多数情况下，数据分布可能 是未知的。所以，当没有特定的检验时，该方 法不能确保发现所有的异常，或者观测到的分 布不能恰当地被任何标准的分布来模拟。③ 这种方法通常对数值型数据有效，而对高维、 周期性数据、分类数据则较难进行挖掘。 ２．２基于距离的方法 ２．２．１基于距离的孤立点定义 基于距离的孤立点挖掘是这样定义的：如 果数据集合ｓ中对象至少有Ｐ部分与对象Ｏ的 距离大干ｄ，则对象Ｏ是一个带参数Ｐ和ｄ的 基于距离的孤立点，即ＤＢ（ｐ，ｄ）。换句话说， 不依赖于统计检验，我们可以将基于距离的孤 的孤立点检测拓广了不一致性检验的思想。 ＯＬＡＰ方法在大规模的数据中采用数据 对许多不一致性检验来说，如果一个对象 立方体确定反常区域，如果一个立方体的单元 ０根据给定的检验是一个孤立点，那么对恰当 值显著地不同于根据统计模型得到的期望值， 定义的Ｐ和ｄ，Ｏ也是一个ＤＢ（Ｐ，ｄ）孤立点。 该单元值被认为是一个孤立点，并采用可视化 还有这样一个性质：数据集Ｓ中至少ｐ％的对 的提示表示。 象与Ｏ的距离大于距离Ｄ，则数据集Ｓ中一个 ２．４基于密度的方法 对象０称为ＤＢ（ｐ，ｄ）一ｏｕｔｌｉｅｒ。 一个著名的基于密度的聚类算法是 ２．２．２基于距离的孤立点挖掘的算法分 ＤＢｓＣＡＮ算法，它将具有高密度的区域划分 类和算法描述 为类，那些不属于任何类的点被标志为孤立 目前已经开发了若干个高效的基于距离 点。它依赖两个参数实现聚类：对象的邻域 的孤立点挖掘的算法，大致上分为基于索引的 半径ｅ和对象的ｅ半径邻域内的最小对象数 算法、嵌套循环算法和基于单元的方法。 ＭｉｎＰｔｓ。ＤＢＳＣＡＮ通过检查数据库中每个 （１）基于素引的算法。给定一个数据集 点的ｅ邻域来寻找聚类：如果一个点Ｐ的ｅ邻 合，基于索引的算法采用索引结构（例如Ｒ 域包含多于ＭｉｎＰｔｓ个点，￣ｌｌｇ＝Ｊ建一个以Ｐ为 树或ｋ ／ｄ树）来查找每个对象０在半径ｄ范围 核心对象的类。然后，ＤＢＳＣＡＮ反复寻找从 内的邻居，即通过对最近邻查询或以０为中心 这些核心对象直接密度可达的对象，当没有新 的范围查询的回答来实现。设Ｍ是一个孤立 点可被添加到任何类时，聚类过程结束。 点的ｄ ／邻域内的最大对象数目。因此，一旦 ＤＢＳＣＡＮ在数据库使用空间索引结构的时 对象０的Ｍ＋１个邻居被发现，０就不是孤立 候，时间复杂度是Ｏ（ｎｌｏｇｎ），否则是０（ｎ＊ｎ），它 点。此算法在最坏情况下的复杂度为Ｏ（ｋ× 可以发现相对于任意形状聚类的孤立点，但是 ｎ ），这里ｋ是维数据集合中对象的数目，ｎ是 它留给用户决定的参数难以确定，而且它对参 数据点数。此算法的特点是需要建立索 数值非常敏感，设置的细微不同即可能导致差 引结构，比较费时。当ｋ增加时，基于索引的算 别很大的孤立点判别结果。 法具有良好的扩展性。不过之前的算法复杂 度只考虑了搜索时间，而建造索引的任务本身 ３结语 的计算量就是很大的。 孤立点检测研究是一个非常有应用价值 （２）嵌套循环算法ＮＬ。此算法是将内存 的问题，近年来已引起越来越多的关注，但由 缓冲区空间划分成相等的两部分，数据集分成 于孤立点含义的主观性和相对性，发现海量数 几个缓冲区大小相等的逻辑块，通过认真选择 据集中的孤立点仍是比较复杂的问题，至今没 调入每一部分缓冲区的次序，使Ｉ／０次数最 有通用有效的方法来发现数据集中的孤立 小。嵌套循环算法和基于索引的算法有相同 点。本文通过对该领域的深入系统调研，重 的计算复杂度，算法复杂度为Ｏ（ｋ×ｎ２），ｋ表 点介绍了孤立点检测方法中的基于统计模型 示维数，ｎ表示数据点数。它的特点是不需要 的方法、基于距离模型的方法、基于密度模 建立索引结构，通过次序的选择试图最小 型的方法和基于偏离模型的方法，并总结了它 化Ｉ／０的次数。它把内存的缓冲空间分为两 们各自的优劣。数据流、高维数据集以及 半，把数据集合分为若干个缓冲区大４４１１等的 ｗｅｂ数据中孤立点检测的高效方法研究将仍 逻辑块。通过精心选择逻辑块装入每个缓冲 是孤立点检ａｌｌ＇ｌ．３题的研究热点，尤其对欺诈检 区的顺序，使Ｉ／０效率能够改善。 测、反洗钱、网络入侵等具体应用领域的研 ２．３基于偏离的方法 究将具有示范意义。 基于偏离的孤立点挖掘是不采用统计检 验或基于距离的度量值来确定孤立点的。相 参考文献 反，它通过检查一组对象的主要特征来确定孤 ［１】王宏鼎等．异常点挖掘研究进展【Ｊ１．智能挖 立点。与给出的描述“偏离”的对象被认 掘研究进展．２００６，１（１）：６９—７３． 为是孤立点。基于偏离的孤立点挖掘有两种 【２Ｊ Ｊｉａｗｅｉ Ｈａｎ，Ｍｉｃｈｅｌｉｎｅ Ｋａｍｂｅｒ．范明等 常用的技术：第一种序列异常技术是顺序的比 译．数据挖掘概念与技术［Ｍ】．北京：机械 较一个集合中的对象，第二种是采用了一个 工业出版社，２００４．２５４ ２６１． ０ＬＡＰ数据立方体方法。 ［３】李强，李振东．数据挖掘中孤立点的分析研 （１）序列异常技术。是一种基于相异度函 究在实践中应用 ．微计算机应用，２００６， 数的可行方法，这类技术模拟人类区别数据集 ２７（３）：３２３—３２７． 中与众不同的样本的方法，它定义样本集的基 【４Ｊ李丹．异常数据挖掘算法及其在税务上的 本特征，所有背离这些特征的样本都是异常样 应用．山东大学硕士论文，２００５．２２－３０． 科技咨询导报Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ Ｃｏｎｓｕｌｔｉｎｇ Ｈｅｒａｌｄ １３７
