孤立点挖掘算法研究.docVIP

孤立点挖掘算法研究 杨永铭，王喆 （兰州交通大学 电子与信息工程学院，甘肃 兰州 730070） 摘 要：针对孤立点检测算法在现时中的应用展开研究。通过对当前的几种孤立点检测算法进行全面深入的分析与比较，归纳和总结了它们的特点。研究者些算法为基础，做进一步分析，提出新的改进算法。 关 键 词：数据挖掘；孤立点；空间数据；数据流；异常检测 中图分类号：TN92 文献标识码：A Re of Outlier Mining Algorithm Yang 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 detection 1 引言 孤立点检测是数据挖掘中的一个重要方面。最早Hawkins[1]给出了孤立点（离群点或异常点）的本质性定义：孤立点如此不同与数据集中的其它数据，以至于使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。孤立点可能是由于度量或执行错误产生的，也有可能是由于固有数据变异产生的，或者其它原因。很多数据挖掘算法通过各种改进来尽量减少孤立点对挖掘结果的影响，或者在挖掘过程中排除孤立点。然而孤立点可能隐藏着重要的信息，也许比一般的数据更有价值。因此人们开始逐渐研究孤立点挖掘算法。 孤立点检测的基本思想是给定一个包含n个数据对象的集合，及预期的孤立点的数目k，发现与剩余的数据相比是显著相异的、异常的或不一致的前k个对象。孤立点挖掘问题可分为两个子问题[1]：（1）在给定的数据集合中定义数据的不一致。（2）找到有效的方法来挖掘这样的孤立点。孤立点挖掘最早应用在统计学领域，在一定程度上，它与聚类分析有相似性。但是两者在概念和目的性方面还有偏差。实际生活中，孤立点挖掘有着广泛的应用，例如网络入侵检测，信用卡欺诈，金融审计，影像处理，恶劣天气预测等。 2 孤立点挖掘算法 近些年来人们提出了大量的孤立点检测算法，大致可以归纳为以下几类：基于统计的方法，基于距离的方法，基于偏移的方法，基于聚类的方法，基于密度的方法。 2.1基于统计的孤立点检测算法 基于统计的方法是出现得最早的离群点检测方法。对给定的数据集合假设了一个分布或概率模型，然后根据模型采用不一致性检验来确立孤立点。基于统计的孤立点挖掘方法易于理解，实现起来也比较方便，但主要的缺点是绝大多数检测仅对数据分布满足某种概率分布的数值型单维数据集较为有效，然而许多数据挖掘问题要求在多维空间中发现孤立点。同时，统计学的方法要求关于数据集合参数的知识，但是，这参数有可能是未知的。当没有特定的检验时，该类方法不能确保所有的孤立点被发现。 2.2基于距离的孤立点检测算法（distance-based） 基于距离的方法最早是由Knorr和Ng[2]在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等）的性能。随着维数的增加，所有的索引结构的性能迅速下降，使得算法性能不佳。N