一种改进的基于密度的离群数据挖掘算法

摘要：利用基于密度的离群数据挖掘算法离群数据不在非离群数据指定的邻域内的特点，改进了原有的离群数据挖掘算法：首先判断数据是否在某个非离群数据指定的邻域内，如果不在，再判断其邻域内数据的个数。通过对二维空间数据测试表明，改进的算法能够快速有效地挖掘出数据集中的离群数据，速度上数倍于原来的算法。

关键词：数据挖掘；离群数据；基于密度

中图分类号：TP311.13

文献标识码：A

0引言

数据挖掘是从大量的数据中发现正确的、新颖的、潜在有用并能够被理解的知识的过程。现有的数据挖掘研究大多集中在发现适用于大部分数据的常规模式。但在一些应用中，如电信和信用卡欺骗、药物研究、气象预报、电子商务、贷款审批、客户分类、金融领域、网络入侵检测等领域有关例外情况的信息比常规模式更有价值。目前在数据挖掘中，对偏离常规模式的数据即离群数据的研究正得到越来越多的重视。

目前还没有关于离群数据的统一的定义，这里采用Hawkins1980年给出的定义：离群数据是在数据集中与众不同的数据，使人怀疑这些数据并非产生于非随机偏差，而是产生于完全不同的机制。离群数据的来源有两类：错误的数据，如录入错误、测量错误等；数据真实性质的反映，如一个公司的总裁的薪金远大于该公司一个普通员工的薪金等。所谓的离群数据挖掘指给定一个有n个数据点或数据对象的集合及预期的离群数据数目n′，发现与剩余数据相比显著相异的、离群的或不一致的前n′个对象的过程[1]。

早期的统计分析领域的基于统计的离群数据挖掘其前提是待处理数据的分布特征是预先知道的（如正态分布、泊松分布等），这种方法需要知道数据的分布及分布的参数等；郑斌祥等人[2]基于第k个最近邻居的离群挖掘方法只针对时序数据，而且运算性能也不甚理想；基于偏离的离群数据检测方法是知道数据特性选取合适的相异函数，但序列离群数据在概念上仍然有一定的缺陷，遗漏了不少的离群数据，因而没有得到普遍的认可；基于规则的分类离群数据挖掘方法只适合于要求错误数据少，分组粒度细的挖掘；基于距离的方法比较接近Hawkins对离群数据本质的定义，它通过实验确定合适的基准值和距离范围，难以处理分类数据和周期性时态数据；基于密度的离群数据挖掘（DensityBased Outlier Mining，DBOM）的观点比基于距离的离群数据挖掘的观点更贴近Hawkins对离群数据本质的定义，因此能够检测出基于距离离群数据挖掘算法所不能识别的一类离群数据，即局部离群数据，而局部离群数据抛弃了以前所有的离群数据定义中非此即彼的绝对离群数据概念，更加符合现实生活中的应用。另外还有基于相似系数的方法、基于聚类的小波变换聚类的方法、高维空间聚类的方法等。本文首先描述了DBOM算法，而后对其进行了改进。

1基于密度的离群数据挖掘

1.1DBOM算法的基本概念

定义1以数据对象o为圆（球）心，半径ε内的区域称为o的ε―邻域。

定义2若数据对象C的ε―邻域内含有数据对象数目不少于Minpts个，则称C为核心对象，能产生核心对象的ε是有意义的。其中，Minpts是一个可以人为设定的自然数。

定义3D是数据对象集合，p∈D，C∈D。对于给定的一个自然数Minpts，若C是核心对象，p在C的ε―邻域内，则称p是从C出发关于ε和Minpts直接密度可达。

定义4D是数据对象集合，p∈D，p的ε―邻域内数据对象集合称为p的ε擦谟蚣，记为Pε―set。

定义5D是数据对象集合，o∈D，对于任意一个核心数据对象C∈D，从C出发，都不能关于ε和Minpts直接密度可达并且|oε―set|≤Minpts，则称o为关于ε和Minpts的基于密度的离群数据对象。

定义6D是数据对象集合，p∈D，若p的ε擦谟蚰诤有对象数目为零，则称p是数据集D中关于ε邻域的孤立点。

1.2DBOM算法的描述

基于密度的离群数据挖掘算法可以发现任意形状的数据布局中的离群数据，它的基本思想是：对于数据集中的每一个离群数据对象，不能包含在任何一个给定半径和该半径邻域内包含指定数据对象数目的核心对象的邻域内。基于密度的离群数据挖掘为了发现所有的离群数据，需要对每个数据进行处理。DBOM首先从数据集D中任意找一数据对象p，并查找出D中p的关于半径ε邻域内包含所有的邻域对象，若p的ε邻域内某一个数据对象的ε邻域内包含Minpts或多于Minpts个数据对象，则p不是离群数据；反之，若p的ε邻域内所有数据对象的ε邻域内包含的数据对象个数都少于Minpts，或者p的ε邻域内没有数据对象即p是数据集D中关于ε邻域的孤立点，则p是离群数据。接着处理数据集中的下一个数据，直至数据集中的所有数据都被处理完。相应的算法描述如下：

2改进的基于密度的离群数据挖掘IDBOM

上述的基于密度的离群数据挖掘算法能够较好地挖掘出数据集中的离群数据，该算法的平均执行时间复杂度为O（n2）（n为数据集中包含的数据对象数目）。它主要是通过对数据集中每个数据对象进行判断，如果它的邻域内某一个数据对象是一个核心对象，即它包含在某一个核心对象的邻域内，该数据对象就不是离群数据，否则是离群数据。从离群数据的特征来看，离群数据往往是比较稀疏的、在数据集中所占比例比较小的数据因此，上述算法对每个数据及其邻域内的数据进行相关判断，显然效率就比较低下。

定理1如果一个数据对象是核心对象，那么该数据的邻域内的数据都不是离群数据。

证明假设存在一个数据集D，C为D中关于ε和Minpts的核心数据对象，Cε―set为C的ε―邻域集，那么对Cε―set中的任意一个数据对象p，都有d（C，p）≤ε，即从核心数据对象C出发，可以直接密度到达数据对象p，由定义5可知，数据对象p不是离群数据对象。

定理2某个数据对象是离群数据是其ε―邻域内数据对象的个数少于Minpts个的充分条件。

证明设存在一个数据集D，o为D中关于ε和Minpts的离群数据对象，oε―set为o的ε―邻域集，由定义5可知，｜oε―set｜≤Minpts；假设在数据集的边缘存在一个数据对象q∈｜qεset｜≤Minpts, C为数据集中一个核心数据对象，且有q∈Cε―set，根据定义5可知q不是离群数据对象。

基于上述定理，我们不对数据集中每个数据对象的邻域内判断是否存在一个核心数据对象，而是只判断邻域内数据对象个数少于Minpts个的数据对象的邻域内是否存在核心数据对象。如果某一个数据对象p是核心数据对象则将其及其邻域内的数据对象打上暂不运算的标签及非离群数据的标签；反之按下述方式处理其邻域内的数据对象：若p的邻域和某个核心数据对象C的邻域数据对象交集不为空，那么判断这些交集中的数据对象是否存在核心数据对象，若存在则p不是离群数据。如果和任何核心数据对象的ε擦谟蚪患为空或交集内不含核心数据对象则p就是离群数据对象。改进的算法描述如下：

3算法测试

这里对基于密度的离群数据挖掘算法进行了测试，算法是用Matlab实现的，实验的环境是一台P4 2.93G、内存1GB的计算机，通过对网络中心的某数据集进行测试，在ε＝50和Minpts＝3的条件下，共挖掘出3个离群数据，经过检测，其中两个离群点是由病毒造成的网络不正常，另外一个是由于一个实验室进行网络对拷发送广播报文引起的网络堵塞造成的。其中优化后的算法的运算时间是优化前的三分之一。在运算的过程中发现，ε和Minpts取值不同，挖掘出的离群数据的个数也可能不同，这说明了基于密度的离群数据挖掘算法对输入参数有一定的敏感性。