改进的快速DBSCAN算法

关于基于概率密度的聚类算法

第29卷第9期

2009年9月

文章编号:1001-9081(2009)09-2505-04

计算机应用

JournalofComputerApplications

Vol.29No.9Sep.2009

改进的快速DBSCAN算法

王桂芝,王广亮

(河南商业高等专科学校计算机应用系,郑州450044)

(wgz123@http://www.77cn.com.cn)

摘　要:针对DBSCAN算法时间性能低效的问题,分析快速聚类过程中丢失对象的原因,提出一种新的改进算法IF2DBSCAN。该算法在不丢失对象的基础上,通过选取核心对象邻域中的代表对象来扩展类,从而减少邻域查询次数,提高了算法的时间性能。实验结果表明,IF2DBSCAN算法是正确和高效的。

关键词:聚类;DBSCAN算法;邻域;核心对象中图分类号:TP301　　文献标志码:A

ImprovedfastDBSCANalgorithm

WANGGui2zhi,WANGGuang2liang

(DepartmentofComputerApplication,HenanBusinessCollege,ZhengzhouHenan450044,China)

Abstract:ThetimeperformanceofDensity2BasedSpatialClusteringofApplicationswithNoise()isinefficient.Concerningthisproblem,theauthorsanalyzedthereasonsoflosingobjectintheprocessoffastandproposedanewImprovedFastDBSCAN(IF2DBSCAN)algorithm.Onthebasisofnotlosingacategorybyselectingrepresentativeobjectsfromtheneighborhoodofcoresoitthenumberofregionalinquiriesandimprovedthealgorithmπstimeperformance.ThemIF2DBSCANalgorithmiscorrectandefficient.

Keywords:clustering;DBSCANobject

0　引言

聚类(Clustering)。所谓聚类,(Cluster),在同一个簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大[1]。通过聚类,人们能够识别密集的和稀疏的区域,发现全局的分布模式和数据属性之间有趣的相互关系。在数据挖掘中,聚类分析能作为一个独立的工具来获得数据分布的情况,观察每个簇的特点,集中对特定的某些簇做进一步分析。此外,聚类分析还可以作为其他算法(如特征和分类等)的预处理步骤,这些算法再在生成的簇上进行处理。

迄今为止,人们已经提出了许多聚类算法,如K2[2][3][4][5][6]

MEANS、CLARANS、DBSCAN、CURE、CLIQUE和

[7]

C2P等算法,其中DBSCAN算法是一种基于密度的聚类算法。该算法将具有一定密度的区域划分为簇,可以在含有“噪声”的空间数据集中发现任意形状的聚类。但其时间性能是低效的。本文提出了一个新的DBSCAN改进算法IF2DBSCAN。该算法在时间和空间性能上都比传统的DBSCAN算法有较大提高。

1　基于密度的聚类算法DBSCAN

1.1　基本概念

基于密度的聚类算法的核心思想是:对于构成簇的每个对象,其ε邻域包含的对象个数,必须不小于一个给定值(MinPts),也就是说其邻域的密度必须不小于某个阈值。下面

[4]

给出基于密度聚类算法分析中的一些定义。

ε2定义1　邻域。给定对象半径ε内的区域称为该对象的

ε2邻域。

定义2　核心对象。给定ε,MinPts,若对象p的ε邻域Nε(p)包含的对象个数|Nε(p)|≥MinPts,则称p为核心对象。

定义3　直接密度可达。给定ε,MinPts,当:1)p∈Nε(q)且

2)|Nε(q)|≥MinPts

则称对象p是从对象q出发直接密度可达的。

定义4　密度可达。给定对象集合D,当存在一个对象链p1、p2、…、pn,p1=q,pn=p,对pi∈D,pi+1是从pi关于ε和MinPts直接密度可达的,则称对象p从对象q关于ε和MinPts密度可达(非对称)。

定义5　密度相连。如果对象集合D中存在一个对象o,使得对象p和q是从o关于ε和MinPts密度可达的,那么对象p和q关于ε和MinPts密度相连(对称)。

定义6　簇和噪声。基于密度可达性的最大的密度相连对象的集合称为簇,不在任何簇中的对象被认为是“噪声”。1.2　DBSCAN算法

DBSCAN(Density2BasedSpatialClusteringofApplicationswithNoise)是一个基于密度的聚类算法。该算法采用迭代查找的方法,通过迭代地查找所有直接密度可达的对象,找到各个簇所包含的所有密度可达的对象[4]。具体方法如下:

1)检查数据库中尚未检查过的对象p,如果p未被处理(归入某个簇或标记为噪声),则检查其ε邻域Nε(p),若Nε(p)包含的对象数不小于MinPts,建立新簇C,将Nε(p)中所有点加入C;

2)对C中所有尚未被处理的对象q,检查其ε邻域Nε(q),若Nε(q)包含至少MinPts个对象,则将Nε(q)中未

　　收稿日期:2009-03-23;修回日期:2009-05-10。　　作者简介:王桂芝(1970-),女,河南郑州人,副教授,硕士,主要研究方向:数据挖掘、聚类分析;　王广亮(1970-),男,河南郑州人,副教授,主要研究方向:聚类分析。

关于基于概率密度的聚类算法

2506　　　　计算机应用第29卷

归入任何一个簇的对象加入C;

3)重复步骤2),继续检查C中未处理对象,直到没有新的对象加入当前簇C;

4)重复步骤1)～3),直到所有对象都归入了某个簇或标记为噪声。

DBSCAN算法可以在有噪声的数据中发现任意形状的聚类,但该算法也具有明显的局限性。DBSCAN的时间复杂度为

2

另外,DBSCAN算法要对每个数据对象进行邻域查O(n)。

询,其时间性能低效。

个种子对象再次选择它们各自邻域的4个代表对象时,必定都有一个代表对象已归过类(在初始的核心点邻域内),如果一个种子对象邻域的另外三个代表对象中恰巧有两个代表对象也在初始核心点的邻域内,那么这一种子对象则仅依靠离初始核心对象最远的那个代表对象来扩展类。如图1所示,

p1、p2、p3、p4是第一轮选择的4个代表对象作为种子对象,

其中p1为核心对象,其邻域的代表对象q1、q2、q3、q4,由图示可以看出q2、q3、q4均在初始核心对象的邻域内,即已标记了类,此时仅对q1计算邻域进行类的扩展,这样显然会造成大量数据对象的丢失

。

2　IF2DBSCAN算法

基于DBSCAN算法时间性能问题,周水庚等人[8]提出了

一种快速的聚类算法FDBSCAN,本文的IF2DBSCAN算法正是在此基础上提出的。2.1　IF2DBSCAN算法基础

FDBSCAN算法通过选用核心对象附近区域包含的所有对象的代表对象作为种子对象来扩展类,减少了区域查询的次数,从而减低了聚类时间和I/O开销。该算法提出,在n维

也就是说,在每一维空间上,选空间中,选择2n个代表对象。

择两个对象作为代表对象用于类的扩展[8]。但是,如果某些对象唯一地通过被忽略的核心对象p密度可达,则当p所在的类C扩展完成后,这些对象将未被包含在类C中,此时称之为丢失对象。FDBSCAN聚类后,还必须对丢失对象进行处理。

我们用C语言编程实现了对象的FDBSCN算法,在0,采用二维数据集进行验证理时,FDBSCAN算法比算法的速度要快数倍,甚至十倍以上。但此时,FDBSCAN算法不能进行有效聚类———本来存在几个类的数据集却被分成几十个类。显然,FDBSCAN算法必须对丢失对象进行处理,特别是对丢失对象所引起的许多小类的合并问题必须解决。但是,要进行类的合并必然要对已聚类后的数据库再次进行扫描,并对某些数据对象进行区域查询。这必将降低算法的时间性能。为此提出一种新的快速聚类算法———IF2DBSCAN,可以避免后期对丢失对象的处理过程。2.2　IF2DBSCAN算法思想

下面通过深入分析快速聚类中丢失对象的原因而提出IF2DBSCAN算法的基本思想。2.2.1　丢失对象的原因分析

在二维空间中,对一个核心对象的邻域选择4个代表对象作为 …… 此处隐藏：10024字，全部文档内容请下载后查看。喜欢就下载吧 ……