孤立点挖掘算法研究

《孤立点挖掘算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、孤立点挖掘算法研宄杨永铭，王喆（兰州交通大学电子与信息工程学院，甘肃兰州730070）摘要：本文针对孤立点检测算法在现时屮的应用展开研究。通过对当前的儿种孤立点检测算法进行全面深入的分析与比较，归纳和总结了它们的特点。本文还对现冇的高维和空间数裾屮孤立点检测算法进行了分析和研宄，从而便•丁•研究者以这些算法力基础，做进一步分析，提出新的改进算法。关键词：数据挖掘；孤立点；空间数据；数据流；异常检测中图分类号：TN92文献标识码：AResearchofOutlierMiningAlgorithmYangYongMing,WangZhc（Institu

2、teofElectronicandInformationEngineering,LanzhoujiaotongUniversity,Gansu730070,China）Abstract:Thispapermainlystudytheoutlierdetectionalgorithmintheapplicationofthepresent.Throughacomprehensivein-depthanalysisandcomparisontoseveralofthecurrentoutlierdetectionalgorithm,theirfeatu

3、resweresummarized.Thispaperalsoanalyseandresearchtheoutlierdetectionalgorithminhighdimensionaldataandspatialdata.Basedonthesealgorithm，resercherscanproceedafurtheranalysisandposeanewimprovedalgorithm.Keywords:datamining;outlier;spatialdata;datastream;anomalydetection1引言孤立点检测是数

4、据挖掘中的一个重要方面。最早Hawking11给出了孤立点（离群点或异常点）的本质性定义：孤立点如此不同与数据集巾的其它数据，以至于使人怀疑这些数据并非随机偏差，而是产生于完全不同的机制。孤立点可能是由于度量或执行错误产生的，也有可能是由于固有数据变异产生的，或者其它原因。很多数据挖掘算法通过各种改进来尽垃减少孤立点对挖掘结果的影响，或者在挖掘过程屮排除孤立点。然而孤立点可能隐藏着重要的信息，也许比一般的数据更有价值。因此人们开始逐渐研究孤立点挖掘算法。孤立点检测的基本思想是给定一个包含tr个数据对象的集合，及预期的孤立点的数目k，发现与剩余的数据

5、相比是显著相异的、异常的或不一致的前k个对象。孤立点挖掘问题可分为两个子问题[1]:（1）在给定的数据集合屮定义数据的不一致。（2）找到有效的方法来挖掘这样的孤立点。孤立点挖掘最早应用在统计学领域，在一定程度上，它与聚类分析有相似性。但是两者在概念和0的性方Ifif还有偏差。实际生活中，孤立点挖掘有着广泛的应用，例如M络入侵检测，信用卡欺诈，金融审计，影像处理，恶劣天气预测等。2孤立点挖掘算法近些年来人们提出了大量的孤立点检测算法，大致可以归纳为以下儿类：基于统计的方法，基于距离的方法，基于偏移的方法，基于聚类的方法，基于密度的方法。2.1基于统计

6、的孤立点检测算法基于统计的方法是出现得最早的离群点检测方法。对给定的数据集合假没了一个分布或概率模型，然后根据模型采用不一致性检验来确立孤立点。基于统计的孤立点挖掘方法易于理解，实现起来也比较方便，但主要的缺点是绝大多数检测仅对数据分布满足某种概率分布收榀R期：2007-10-17；修回R期：基金项目：教育部春辉计划科研项目（编号：20567）；兰州交通大学光电技术与智能控制教育部重点实验室开放项目作者简介：杨永铭（1981），男，山东泰安人，硕士研究生的数值沏单维数据集较为有效，然而许多数据挖掘问题要求在多维空间屮发现孤立点。同时,统计学的方法要

7、求关于数据集合参数的知识，侃是，这参数有可能是米知的。当没有特定的检验时，该类方法不能确保所有的孤立点被发现。2.2基于距离的孤立点检测算法(distance-based)基于距离的方法最早是巾Knorr和Ng［2］在1998年提出的。他们用DB(p，d)来表示数据集屮的孤立点，采用不同的参数p与d,DB(p,d)可以表示所有的孤立点。与此定义相应的算法有三种，它们是基于索引(index-based)的算法［3］，嵌套循环(nested-loop)算法f4’51，基于单元或划分(cell-based)的算法［61等。它们的具体算法不在赘述。基于索引

8、的方法依赖多维索引结构(R-trees,X-trees，KD-tress等)的性能。随着维数的增加，所有的索引结构的性能迅