2024年3月15日发(作者：)

计算机技术与发展

第29卷摇第5期

摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇

Vol.29摇No.5

2019年5月May摇2019

COMPUTERTECHNOLOGYANDDEVELOPMENT

DBSCAN聚类算法的参数配置方法研究

(1.解放军陆军工程大学指挥控制工程学院,江苏南京210007;

2.解放军陆军工程大学教学考试中心,江苏镇江212000)

宋金玉

1

,郭一平

1

,王摇斌

2

摘摇要:随着互联网技术的飞速发展,海量数据涌现。在海量的数据中,存在大量无用甚至错误的“脏数据冶,这些低质量

的数据难以提供有价值的信息。数据质量低的一个方面就是数据异常。对数据异常检测问题进行了研究,将基于密度的

DBSCAN聚类算法应用于数据的异常检测,并针对该算法在应用过程中对参数设置敏感的问题,提出了一种邻域阈值

(Eps)和点数阈值(Minpts)的配置方法。该方法可根据数据集本身的统计特性以及图表的可视化展示来为算法确定合适

的参数。利用MATLAB工具,编程实现了DBSCAN聚类算法及辅助参数的计算,并在Iris数据集上进行了实验验证。实

验结果表明,用该方法进行DBSCAN聚类算法参数的设置是可行的,弥补了DBSCAN聚类算法参数设置的传统做法单靠

经验的不足,使得检测结果的准确性和可伸缩性更好。

关键词:数据异常检测;聚类算法;DBSCAN;参数配置

中图分类号:TP311摇摇摇摇摇摇文献标识码:A摇摇摇

doi:10.3969/.1673-629X.2019.05.009

摇摇摇文章编号:1673-629X(2019)05-0044-05

ResearchonParameterConfigurationMethodofDBSCAN

ClusteringAlgorithm

(ofCommandandControlEngineering,ArmyEngineeringUniversityofPLA,Nanjing210007,China;

ofTeachingandTesting,ArmyEngineeringUniversityofPLA,Zhenjiang212000,China)

SONGJin-yu

1

,GUOYi-ping

1

,WANGBin

2

Abstract:WiththerapiddevelopmentofInternettechnology,realargenumberofuselessorevenwrong

“dirtydata冶inthesedata,ceptionisoneaspectoflow

perdiscussestheappatthe

problemthatthealgorithmissensitivetoparametersettingintheapplicationprocess,weproposeaconfigurationmethodofthe

neighborhoodthreshold(Eps)andthepointthreshold(Minpts)byapplyingtheDBSCANalgorithmbasedondensitytotheanomaly

thodcandeterminetheappropriateparametersaccordingtothestatisticalcharacteristicsofthedatasetitselfand

ATLABtool,theDBSCANclusteringalgorithmandthecalculationofauxiliaryparameters

areprogrammed,erimentshowsthatthemethodisfeasibleto

settheparametersofDBSCANclusteringalgorithm,

accuracyandscalabilityofthedetectionresultareimproved.

Keywords:abnormaldatadetect;clusteringalgorithm;DBSCAN;parameterconfiguration

0摇引摇言

全球知名咨询公司麦肯锡称:“数据,已经渗透到

当今每一个行业和业务职能领域,成为重要的生产因

素。冶但现实生活中,人们常常抱怨“数据丰富,信息贫

乏冶。这是因为在海量的数据中,存在大量无用甚至

错误的“脏数据冶,根据“垃圾进,垃圾出(garbagein,

garbageout)冶

[1]

原理,低质量的数据难以提供有价值

的信息,反而会带来负面影响,会因各种数据/信息质

量(data/informationquality,DQ/IQ)问题给用户带来

麻烦甚至损失

[2-4]

。

数据质量低的一个方面就是数据异常,即数据集

中出现明显区别于其他正常数据的数据。由于数据异

收稿日期:2018-06-27摇摇摇摇摇摇修回日期:2018-10-30摇摇摇摇摇摇网络出版时间:2019-03-06

基金项目:国家自然科学基金(61371196)

作者简介:宋金玉(1967-),女,硕士,副教授,研究方向为数据工程;郭一平(1994-),女,硕士,研究方向为数据工程。

网络出版地址:/kcms/detail/

摇第5期摇摇摇摇摇摇摇摇摇摇摇摇宋金玉等:DBSCAN聚类算法的参数配置方法研究

·45·

常往往使数据表现为孤立点

[5]

,也称之为离群点或异

常点。这些数据可能是需要消除的错误数据,也可能

是重要的报警点,预示出现问题或者发生了重要变化。

离群点检测(又称为异常检测)是找出其行为不

同于预期对象的过程,通过检测并去除数据源中的这

些孤立点可达到消除数据异常的目的,从而提高数据

源的数据质量。

数据挖掘技术中的聚类分析工具,可以用于离群

点(噪声)检测。聚类分析采用某种算法将大的数据

集合根据数据相似性把所有数据划分成簇,即采用相

X

1

,X

2

代表数据集中的两个数据对象,n是参与计算的

X

i2

,…,X

in

)表示,X

1k

,X

2k

分别为两个数据点的第k维

坐标。d

12

是两点间距离,有多种形式的距离度量可采

用。如欧几里德函数,则d

12

可由如下公式计算:

d

12

=

数据对象的属性个数,每个数据对象用n维向量(X

i1

,

个对象越相似或接近时,d

12

值越接近0,而当两个对

象越不相同或相距较远时,d

12

值越大。还可以根据每

其中,d

12

就表示这两个数据对象的相异度。当两

移

(x

n

k=1

1k

-x

2k

)

2

(1)

似度进行归类,相似度较高的归为一类,明显不属于任

何一类的单个(或少量)数据集可认为是异常数据。

聚类算法有很多种,其中基于密度的方法(density-

basedmethod)考虑数据集中的每个对象,根据一定距

离内数据密度来划分簇数,数据比较密集的可以被认

为一个簇,而比较稀疏的区域则被认为是噪声。

有代表性的基于密度的全局邻域(density-based

spatialclusteringofapplicationswithnoise,DBSCAN)

算法将数据空间中的数据抽象为数据点,通过计算点

之间距离和点密度来进行聚类,可将噪声或离群点从

簇内分离。在DBSCAN算法使用中,需设置邻域阈值

(

一定密度的区域划分为簇

Eps)和点数阈值(Minpts

,

)

且聚类结果对参数值敏感

两个参数,根据参数将有

。

目前已有许多文献对Eps和Minpts参数值的设

定方法进行了研究。对于密度均匀的数据,文献[6]

通过分析数据的统计特性来自适应确定Eps和

Minpts。对于不同密度数据的聚类,文献[7]采用自适

应的Eps参数;文献[8]根据基于网络与基于密度的

聚类算法间的等效规则来计算不同密度的密度阈值;

文献[9]提出基于数据分区的PDBSCAN算法;文献

[10]

文中根据数据的统计特性

提出基于网格分区来确定

,

Eps

利用图表的可视化结

的方法。

果,提出了一种确定DBSCAN算法参数的方法。

1摇DBSCAN聚类算法的分析与实现

由于数据集中相似重复记录的个数是不确定的,

因此,要求聚类算法应具有能够发现任意形状簇的能

力。DBSCAN算法

[11]

可将具有足够高密度的区域划

分为一个簇,簇数事先是不确定的,点的邻域的形状取

决于两点间的距离函数dist(p,q),对象间的距离是

根据对象的属性值计算得来的。因此,聚类结果取决

于选择哪些属性变量、采用何种距离度量以及如何计

算度量的属性。

下面介绍用来描述算法的相关概念

[12]

(1)距离。

。

对象间的距离采用求数据相异度的方法。假设

个属性的重要性为其赋一个权重。

(2)

数据集中任意一点的邻域记为

邻域、密度、核心点、边界点。

N

集中与p点的距离小于给定Eps的点的集合

Eps

(p)

。

,是数据

N

邻域中点的个数称为该点的密度

Eps

(p)={q沂D椰dist(p,q)臆Eps}

,若其大于或等

(2)

于给定的最小值MinPts,则称点p为核心点,否则称为

边界点。

(3)

数据

直接密度可达

集中任意两

、

点

密度可达

p,q,如

、

果

密度相连

q沂N

。

MinPts

|N

Eps

(p

直接密度可达的

)|逸MinPts,则称点

。

q是从点p关于

Eps

(p

Eps

),

和

且

如果p,q两点间存在一个点的序列p

且p

1

,p

2

,…,p

n

,

1

=p,p

关于

n

=q,p

Eps

i+

和

1

是从p

MinPts

i

直接密度可达的,则称点

q是从点p密度可达的。

如果存在一个点o,q和p都是从点o关于Eps和

MinPts密度可达的,则称点q是从点p关于Eps和

MinPts密度相连的。

(4)

数据集中基于密度的簇是基于密度可达的最大密

簇。

度相连的点的集合。簇中的任意两点是关于Eps和

MinPts密度相连的。

给定参数Eps和MinPts,DBSCAN算法的实现就

是生成相应的簇。DBSCAN算法从任意点p开始,检

索所有从点p关于Eps和MinPts密度可达的点。如果

p是核心点,就生成一个关于Eps和MinPts的簇;如果

p是边界点,且没有从p密度可达的点,算法就去处理

数据集中的下一个点。算法实现的流程参见图1。

相比其他聚类算法,例如基于层次的算法等,

DBSCAN算法的优点是可以发现数据集中任意形状

的簇,它的聚类速度比较快,聚类能力也很强。但必须

为每个簇指定恰当的Eps和MinPts,及每个簇中的至

少一个点。由于很难事先获得数据集中所有簇的相关

信息,DBSCAN算法实现时对所有簇采用相同的全局

参数值Eps和MinPts,但把确定参数的任务留给用户,

而且算法生成的结果对参数是敏感的。如若根据数据

·

摇

46

摇

·

摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇计算机技术与发展摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇第29卷

集中存在的比较密集的区域,选取了一个较大的

Minpts值,那么数据集中其他区域会因为密度不够大

而不能被划分成簇,会造成噪声点过多现象;若根据数

据集中存在的比较稀疏的区域,选取了一个较小的

Minpts值,那么整个数据集很容易直接被划成一个大

簇,参数值的微小变化往往会导致差异很大的聚类

结果。

2.1摇Eps参数的确定方法

阵Dist

n伊n

。

首先按式1计算数据对象间的距离,得到距离矩

Dist

n伊n

={dist(i,j),1臆i臆n,1臆j臆n}(3)

其中,n是数据集D中的数据对象个数,每个元素

表示对象i到对象j的距离。

求出矩阵后,将行向量按升序排序。这样,每行就

是相应数据点到其他所有点距离的一个排序。则矩阵

Dist

n伊i

中第i列的数据的意义是距每个数据点最近的

第i个距离值的集合。为观察取不同i值(如1,2,…,

图1摇DBSCAN算法流程

2摇DBSCAN聚类算法的参数配置

传统DBSCAN算法中Eps和Minpts两个参数是

根据经验设置的,并根据聚类结果进行调整。这样做

显然盲目性大,工作量也大,而且效果也不一定好。因

此,文中提出了一种参数的判断方法,该方法的主要思

想是根据数据集本身的统计特性以及图表的可视化结

果由人工来选择参数。

7)

值的概率密度分布曲线

时数值集合的统计特点

,图

,绘制图形

3是对第

,其中图

i列数据进行升

2是距离

序排序后的曲线。数据采用的是随机生成的含有150

个数据点的二维数据集Dataset1。

图2摇距离值的概率密度分布曲线

图3摇距每个数据点最近的第i个距离值的升序曲线

图2中,曲线均值越大的是对应i值越大的曲线。

可以看到,无论i取多少,曲线的分布都大概成泊松分

布。曲线右侧,距离比较大的地方(图中接近0.4)密

度已变得非常小,这些比例很小却和其他点相比距离

明显偏大很多的点,噪声的可能性较大。因此,可以考

虑以此来确定Eps参数。

图3中,曲线由下至上依次是i值增大对应的曲

线。曲线的趋势大致相同,前期和中间都比较平缓,末

端陡峭。可以发现,当i大于4以后,曲线的陡峭点都

大概集中在一个区域,即图中圆形标注内。在Martin

Ester等的研究

[13]

中,对此问题也有描述。若取陡峭

点对应的距离作为邻域阈值,可以估计,当i大于4以

后,对噪声的划分情况是近似一样的,也就是聚类和噪

声检测结果趋于稳定。

摇第5期摇摇摇摇摇摇摇摇摇摇摇摇宋金玉等:DBSCAN聚类算法的参数配置方法研究

·47·

所以,取i等于4时,曲线的陡峭点对应的距离值

作为DBSCAN算法中的Eps参数,即图3中圆圈标注

的纵坐标,大概在0.3~0.4之间,与图2的分析一致。

2.2摇Minpts参数的确定方法

前面Eps的取值是取距每个数据点最近的第4个

距离值集合升序排序后曲线的陡峭点对应的距离值,

即假定Minpts为4。但由于第一步需人工参与判断,

很可能出现误差,而且固定的Minpts值设定不能保证

对任意的数据集检测都有比较好的效果。为了能够更

匹配已经确定的Eps值,可根据人们实际中对噪声判

Minpts为7(籽=7),可以预测聚类检测结果,横轴坐

标为7右侧的点肯定是核心点,不会是噪声,而左边那

4中,可以判断数据集大概集中在两个区域,也有可能

存在噪声。若选取Minpts为2(籽=2),横坐标为2左

侧的三个点有可能是要检测的异常噪声点;若选取

Minpts为5,横坐标为5左侧的六个点都有可能是要

检测的异常噪声点。

些比较稀疏的点则有可能存在要寻找的噪声点。在图

断的标准,再重新确定Minpts值。该思想融合了Alex

Rodriguez等

[14]

提出的新型聚类算法的思想,即对于

一般数据集,簇中心被局部密度较高的邻居点所包围,

而高局部密度的点之间距离比较大。首先,根据2.1

中确定Eps的方法得到Eps的值,然后计算每个数据

点i的局部密度值籽

i

含的邻居点数,再利用式

,即数据点邻域半径

4计算每个数据点

(Eps

i距更高

)内包

密度点的距离啄

i

为其到数据集中最远点的距离

,对于具有最高密度的点

。

,啄

i

的取值

啄

i

=min

j:籽>籽

i

数据集仍采用随机生成的含有

(dist(i,j))

150个数据点的二

(4)

维数据集Dataset1,对每个数据点计算上述两个值,并

以点图(如图4)的形式表现,图中的点就是数据集的

每个对象。

图4摇Dataset1中每个点啄

i

与籽

i

的函数关系

为了进一步说明该图的意义,又采用随机生成的

含有51个数据点的二维数据集Dataset2,计算得到每

个点啄

i

与籽

i

的函数关系,如图5所示。

在图5中,右上角的点啄

i

比较大并且籽

i

也比较

高,应该是一个簇的中心,而图中左边的点籽

i

非常小、

啄

i

又相对比较大的点更多是噪声。根据啄

i

与籽

i

的函

数关系点图,在聚类前,就可以得到数据聚类后的一个

大概情况。对于数据集Dataset2,由图5可知数据集大

概集中在一个区域,并且有少量噪声点,其中,数据对

象点1(图中箭头标注),其籽为0,并且啄非常大,可以

肯定是一个噪声点;数据对象点2和3虽然籽也比较

小,但啄相对不是很大,所以只是有可能是噪声点,因

为DBSCAN聚类的簇是密度相连接的点集。若选取

图5摇Dataset2中每个点啄

i

与籽

i

的函数关系

因此,利用啄

i

与籽

i

的函数关系点图,Minpts值的

设置就转换成了籽阈值的选取问题,可选取图中左边

稀疏点和密集点分界处的横坐标(籽值)。在实际应

用中,若对噪声的要求不是很严格,即偏差度不是很大

就可以认为是噪声的话,可选取比较大的籽阈值(Min鄄

pts值);否则,可选取比较小的籽阈值(Minpts值)。

3摇数据异常检测分析

下面在美国加州大学信息与计算机科学系的Iris

(

进行异常检测分析

鸢尾花)数据集上

,

,

检验所提出的参数配置方法的有

应用DBSCAN聚类算法对数据

效性。

首先对数据集进行改造,添加了两个异常点,即补

充了第151个数据点(第152行),该数据点因花瓣的

长度(12)录入有误,造成异常;修改第70个数据点

(

versicolor

第71行),

改为

使其

Iris

class

-virginica

属性值由原数据集中的

。处理后的Iris(鸢尾花

Iris-

)

数据集的部分数据如表1所示,数据集有4个数值型

属性,1个字符型属性。

DBSCAN算法通过计算各个数据点的欧氏距离

来聚类,要求参与计算的是数值型的属性。但是,在实

际中,通常会有字符型属性,若将其舍弃,必然会丧失

数据信息的完整性。文中将这类属性分为两类。一类

是序数类型属性,比如军衔(少尉,中尉,上尉……)。

这类属性的特点是不同属性之间有联系,而且是等距

离的。所以,可将其替换为数值1,2,3……。另一类

是标称分类属性的,比如国别(中国,美国,俄罗

斯……)。若数据中有多个此类型的属性,通常只选

·

摇

48

摇

·

摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇计算机技术与发展摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇摇第29卷

取一个有代表性的参与运算。文中是在数据处理中按

标称属性产生概念分层的方法。在聚类前,自动按标

称属性分区聚类,不同的分区选取不同的参数设定。

这样的处理虽然增加了工作量,但是不仅保证了信息

的完整性,而且解决了数据密度不均匀却只有一个全

局参数设定的缺陷。

法。该方法可根据数据集本身的统计特性以及图表的

可视化展示,为算法确定合适的参数。编程实现了

DBSCAN聚类算法及辅助参数确定的计算,并利用

MATLAB工具进行可视化展现。并在Iris数据集上

进行检测,通过对比测试,验证了用该方法进行

DBSCAN聚类算法参数的设置是可行的,弥补了

表1摇待检测的Iris数据集的部分数据

SepalSepalPetalPetal

lengthwidthlengthwidthClass(分析)

2

(萼片长)(萼片宽)(花瓣长)(花瓣宽)

3

5

4

.18.0

44

.3

51

3

1

.

0

.Iris

Iris

-setosa

70

54

.

9

7

3

.1

.

4

1

.

4

30

.

2

2

Iris

-

Iris

-

setosa

-

setosa

setosa

71

6

.6

5

.2

.

2

1

2

.4

.50

.

3

.1

.

2

Iris

-virginica

150

725

.

2

6

3

.

2

5

4

.

5

91

.

2

1

.

5

1Iris

-versicolor

151

6

.

5

.

9

23

.

.

2

45

.

摇

15212

.9

3.

3

4

5

.

8

42

.8Iris

3

.

.

1

5

1

.Iris

-versicolor

1

.

3

.

8

2

Iris

-virginica

Iris

-virginica

-setosa

setosa

摇对

,Iris

Iris

-

(

versicolor

鸢尾花)数据集的检测按

,Iris-virginica进行分区

class属性值

,即分为

Iris-

3

个区,对每个分区分别进行算法的参数设置。采用前

述的参数配置方法,通过可视化的判定,设置Eps分别

取值1.5、0.9、1,Minpts分别取值12、2、2,从程序输出

检测结果可以看到,除了检测出之前添加的两个异常

点外,还检测出两个异常点,分别是第42个数据点和

第61个数据点。在原数据集中找到这两个点并进行

人工检查,可以发现第42个数据点的sepalwidth属性

值和其他Iris-setosa类鸢尾花相比是最小的,而且偏

差比较大,而第61个数据点的四个数值属性值和其他

Iris-versicolor类鸢尾花相比都是比较小的,这也就解

释了这两个点被认为是离群噪声点的原因。因此,从

数据集的检测结果来看,该方法的参数设置是比较准

确的,异常检测的结果也是非常有效的。

为了进一步说明参数设置的准确性,将参数Eps

统一取值为1,Minpts统一取值为4,得到的异常检测

结果输出了7个异常点,其中一些异常点并不符合对

异常点的判断标准。这说明DBSCAN算法对参数是

敏感的,当参数设置不合适时,其检测结果也将不准

确,也验证了文中算法是有效的。

4摇结束语

对数据异常检测问题进行了研究,将基于密度的

DBSCAN聚类算法用于数据的异常检测,并针对该算

法在应用过程中对参数设置敏感的问题,提出了一种

配置算法邻域阈值(Eps)和点数阈值(Minpts)的方

DBSCAN聚类算法参数设置单靠经验的传统做法,使

得检测结果的准确性和可伸缩性更好。

目前,该DBSCAN聚类算法参数配置方法需要人

工参与判定,仍存在一定的人为因素,同时参数判定的

过程还比较麻烦耗时,这些都有待进一步的改进提高。

参考文献:

[1]摇LEE

mining

M

and

L,LU

warehousing

Hongjun,

[

LING

C]//

T

Proceedings

W,ing

ofthe10th

data

inter鄄

for

nationalconferenceondatabaseandexpertsystemsapplica鄄

ce,Italy:[s.n.],1999:751-760.

[2]摇MCGILVRAY

军,张健美,等,

D.

译

数据质量工程实践

.北京:电子工业出版社

[M

,2010:245-246

].刁兴春,曹建

.

[3]摇

and

MADNICK

framework

SE

for

,WANG

dataand

R

information

Y,LEEY

quality

W,et

research

ew

[J].

JournalofDataandInformationQuality,2009,1(1):1-22.

[4]摇韩京宇

学,2008,35(2):1-5

,徐立臻,董逸生

.

.数据质量研究综述[J].计算机科

[5]摇

Chapman

HAWKINS

and

D

Hall

M.

,1980

Identification

.

ofoutliers[M].London:

[6]摇夏鲁宁

算法[J

,

]

荆继武

.中国科学院研究生院学报

.Sa-DBSCAN:一种自适应基于密度聚类

,2009,26(4):530-

[7]摇

538

赵

[

摇

.

文,夏桂书,苟智坚,等.一种改进的DBSCAN算法

[8]摇

316

J].

谭

.

四川师范大学学报:自然科学版,2013,36(2):312-

法

摇

[J

颖

].

,

计算机应用

胡瑞飞,殷国富

,2008,28(3):745-748

.多密度阈值的DBSCAN

.

改进算

[9]摇周水庚

[J].计算机研究与发展

,周傲英,曹摇晶

,2000,37(11):1153-1159

.基于数据分区的DBSCAN

.

算法

[10]庞

[J

摇

].

洋

计算机与现代化

,徐巧凤.基于网格分区确定

,2010(5):16-18

DBSCAN

.

参数的方法

[11]刘世平

社,2010:33-40

.数据挖掘技术及应用

.

[M].北京:高等教育出版

[12]李雄飞

京:高等教育出版社

,董元方,李摇

,2010:172-189

军,等.数据挖掘与知识发现

.

[M].北

[13]ESTER

basedalgorithm

M,KRIEGEL

fordiscovering

HP,SANDER

clusters

J

in

,et

large

al.

spatial

Adensity

data鄄

-

baseswithnoise[C]//Proceedingsof2ndinternationalcon鄄

nd,

Oregon:AAAIPress,1996:226-231.

[14]LAIO

ofdensity

A,RODRIGUEZ

peaks[J].Science

ring

,2014,344(6191):1492-1496

byfastsearchandfind

.