数据挖掘中孤立点挖掘算法研究

1、福建电脑年第期数据挖掘中孤立点挖掘算法研究钱敏（贵州大学资源与环境工程学院贵州贵阳）欺诈检测、网络入侵、隐私保护等问题的关注，孤立点挖掘在数据挖掘领域日益受到摘要】【：随着人们对数据质量、重视。本文在调研国内外孤立点挖掘研究算法文献的基础上，对已有各种孤立点挖掘算法进行了总结和比较，并结合当前研究热点，展望了孤立点挖掘未来的研究方向及其面临的挑战。关键词】【：孤立点挖掘；网络入侵；隐私保护；孤立点挖掘算法引言较费时的特点。基于单元（）的方法：数据空间被划分为边长为孤立点是数据集中不符合一般模型的那些对象，即和其它的数据有着不同的性质。它可能是度量或执行错误所导致的，也的单元；每个单元有两个包围

2、层；第一层为倍的单元可能是固有数据变异性的结果。对此，给出了其本质性厚，第二层为（）倍的单元厚。对于该种基于距离的方法小结：由于索引建立的开销很大，定义：孤立点是在数据集中与众不同的数据，使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。一般的，孤立点挖简单索引算法没有竞争性；当时，基于单元的算法在越掘问题可以被看作两个子问题：大时优越性越明显；当之后，嵌套循环算法开始显现出优（）在给定的数据集合中定义什么样的数据可以被认为不势。一致的；基于距离的算法的改进（）找到一个有效的方法来挖掘这样的孤立点。和基于距离的孤立探测方法的缺陷在于：输入参数与很难确定，并且对于不同参数，结果有很大不稳定

3、性。孤立点挖掘算法的分类及应用孤立点探测是数据挖掘中一个重要方面，用来发现小的模这就需要用户反复输入与进行测试，以确定一个满意解；不式（相对于聚类），即数据集中间显著不同于其它数据的对象。能给定孤立的程度，且算法的复杂度较高。和孤立点探测算法大致可以分为基于统计（）的方提出了一个新的基于距离孤立点定义，用（）表示点法，基于距离（）的方法，基于偏差（和它的第个最近邻的距离，给定维空间中包含个点的）的方法，基于密度（）的方法，以及高维数据数据集，参数和（自然数），如果满足（）（）的点不的孤立点探测。超过个，那么称为孤立点。如果对数据点根据它们的孤立点挖掘有着广泛的应用：在信用卡欺诈探测中发现的（）

4、距离进行排序，那么前个点就被看作孤立点。孤立点可能预示着欺诈行为，而及时发现这种信用卡欺诈行为循环嵌套算法（）作为改进后的基于距对商业银行而言相当重要，可以避免不必要的经济损失；在市场离的算法，每次处理一个点，需要扫描一遍数据库，总共需要分析中，可用于确定极低或极高收入的客户的消费行为；在医疗扫描遍（为数据点数）。基于索引的算法（分析中，可用于对多种治疗方式的不寻常的反应等；在网络安全）用类似树的空间索引结构存储，可以减少扫描数据方面；孤立点挖掘应用于网络入侵检测；在数据质量分析中，可库的次数。改进后的基于划分的算法，如果某个点的（）较小的话，以用孤立点挖掘算法检测错误数据；此外还可以应用到气

5、象预报，个人隐私保护等方面。那么不可能是孤立点，可以先对数据集进行划分，然后估计每个划分的（）的上、下界，如果能判定某个划分不可能包含传统的孤立点挖掘算法孤立的话，那么就可以直接把它删除掉；然后再从剩下的划分基于统计的方法基于统计的方法假设给定的数据集服从一个随机分布（如（侯选划分）来计算孤立点；现有的许多聚类算法可以用来划分正态分布等），用不一致性测试（）识别孤立点。但数据集，如算法。是这种方法存在一个问题：在许多情况下，用户并不知道这个数基于偏差的方法据分布，而且现实数据也往往不符合任何一种理想状态的数学和提出了序列孤立（分布；即使在低维（一维或二维）时的数据分布已知，在高维情况）的概念中

6、，对于给定个对象的集合，建立一个子集序列下，估计数据点的分布也是极其困难的。，对每个子集，确定该子集与前序子集的差异度的差。为减少输入数据的顺序对结果的影响，可以用不同的次序多基于距离的方法这个算法复杂和提出一种基于距离的孤立点探测方法：数据集次重复上述过程，找出其中光滑因子最大的子集。但是序列孤立中至少的对象与的距离大于距离。采用不同的参度与数据集大小呈线性关系，有优异的计算性能。数和，（，）可以表示所有的基于统计的孤立点。在对孤立存在的假设太过理想化，对现实复杂数据效果不太好。在基于距离的孤立点定义下，分别有基于索引（）的基于密度的方法算法，嵌套循环（）算法和基于单元（）的算如图所示，由于

7、基于距离的孤立点对于高密度区域和低密度法。基于索引的算法可以通过对最近邻查询或以为中心的区域采用统一的标准，对于局部孤范围查询的回答来实现寻找所有（，）。基于多维索引立点与全局孤立点无法区分。针对这一缺陷，结构或算法复杂度是（），但它的缺点是：需要建立多维索引结构，费时；，提出基于嵌套循环算法将内存缓冲区空间划分成相等的两部分，数密度的孤立点概念。据集分成几个大小和每部分缓冲区相等的逻辑块，通过认真选对象的距离（）：择调入每一部分缓冲区的次序，使次数最小算法复杂度是对任意的自然数，定义的距图基于距离的（），它具有：不需要建立多维索引结构，但选择划分区域也离（）为和某个对象孤立点定义的缺陷年第期

8、福建电脑之间的距离，这里的满足：（）至少存在个对象，使得（，）（，）；（）至多存在个对象，使得（，）（，）；对象的距离邻域：给定的距离（），的距离邻域包含所有与的距离不超过（）的对象：Nk-distance(p)=q|d(p,q)£k-distance(p)（）对象相对于对象的可达距离：给定自然数，对象相对于对象的可达距离为：reach-distk(p,o)=maxk-distance(o),d(p,o)（）如下图所示：图对象相对与对象的可达距离对象的局部可达密度（）：对象的局部可达密度为对象与它的邻域的平均可达距离的倒数： (p,o)åreach-disMinPtslrd

9、MinPts(p)=1(oÎNMinPts(p)NMinPts(p)（）对象的局部孤立因子（）：LOFMinPts（）这里，对中维或中高维数据，必须采用索引结构如树，使得作查询的时间为（），整个计算时间为（）；对特高维数据，索引结构不再有效，时间复杂度提高到（）。高维数据孤立点挖掘方法和提出了一个高维数据孤立挖掘方法。它把MinPts(p)=oÎNåMinPts(p)lrdMinPts(o)lrdMinPts(p)(p)N立点挖掘，算法的效果明显。在孤立点挖掘算法的应用方面也有一些进展：文献将孤立点挖掘算法应用到气象数据的分析中，进行气象预报；文献改进遗传算法，用

10、于生物基因数据中的孤立点分析；文献将孤立点挖掘算法应用到大型分布式数据库中，进行个人隐私保护。小结基于统计的孤立挖掘应用主要局限于科研计算，这主要是因为必须事先知道数据的分布特征这就限制了它的应用范围。序列孤立挖掘算法提出的序列孤立的概念并没有得到普遍的认同。这是因为序列孤立在概念上仍然有一定缺陷，遗漏了不少的孤立数据。基于距离的算法跟基于统计的算法相比，不需要用户拥有任何领域知识。与序列孤立相比，在概念上更加直观。更重要的是，距离孤立更接近的孤立本质定义。基于密度的孤立观点比基于距离的孤立观点更贴近的孤立定义，因此能够检测出基于距离孤立算法所不局部孤立点观点摈弃了以前能识别的一类孤立数据局部

11、孤立。所有的孤立点定义中非此即彼的绝对孤立观念，更加符合现实生活中的应用。实际数据往往具有较大的噪声，因此孤立模式经常只存在于低维子空间中，而在高维空间中难以确定；且以前算法在维数较高时，性能急剧下降。因此和提出的高维数据孤立挖掘的方法，采用遗传优化算法，获得良好的计算性能。近几年来，孤立点挖掘算法取得了许多进展：将基于距离和基于密度的算法并行化，能显著提高算法的性能；将高维空间中的点映射到低维空间，进而发现孤立点是高维数据孤立点挖掘的常用措施；而孤立点挖掘算法在气象数据分析，基因数据分析，个人隐私保护等方面的应用，也显示出孤立点挖掘算法具有独特的应用价值。当数据维数较高时，传统孤立点挖掘算法

12、性能急剧下降，高维数据的孤立点的挖掘仍然是研究的难点。参考文献：，？：，：，高维数据集映射到低维子空间，根据子空间映射数据的稀疏程度来确定孤立数据是否存在。高维数据的孤立探测算法思想是将数据空间的每一维分成个等深度区间。设（）为维立方体所包含点数，为总的点数，定义稀疏系数（）为：s(D)=k（）当（）为负数时，说明立方体中数据点低于期望值；（）越小，说明此立方体中数据越稀疏。数据空间的任一模式可以用来表示。表示数据在第维子空间映射区间，可以取值到!，或者（表示可以为任意映射值）。因此，孤立点挖掘问题可以转化成为寻找映射在（作为参数输入）维子空间上的孤立模式以及符合这些孤立模式的数据（如维空间中一个映射在维子空间上的模式（!）。高维数据中寻找孤立模式是非常困难的，一个简单办法是对所有数据维进行组合，来搜索可能孤立模式，但是效率极其低下。和运用遗传算法优化这个问题的求解过程，它以随机选择个合法模式作为候选解开始，反复经历选择，交叉，变异等几个过程，直至得到较满意的解。孤立点挖掘算法的新进展近几年来，孤立点挖掘算法取得了一些新的进展；文献改进了基于距离的循环嵌套算法，应用了一条剪枝规则，具有线性时间