一种基于参考点和密度的快速聚类算法

©2003 Journal of Software 软 件 学 报 Vol.14, No.6

一种基于参考点和密度的快速聚类算法

马 帅1+, 王腾蛟1, 唐世渭1,2, 杨冬青1, 高 军1 12

∗

(北京大学 计算机科学技术系,北京 100871)

(北京大学 视觉与听觉信息处理国家重点实验室,北京 100871)

A Fast Clustering Algorithm Based on Reference and Density

MA Shuai1+, WANG Teng-Jiao1, TANG Shi-Wei1,2, YANG Dong-Qing1, GAO Jun1

12

(Department of Computer Science and Technology, Peking University, Beijing 100871, China)

(National Laboratory on Machine Perception, Peking University, Beijing 100871, China)

+ Corresponding author: Phn: 86-10-62756374, E-mail: mashuai@db.pku.edu.cn; mashuai@cis.pku.edu.cn http://www.pku.edu.cn

Received 2002-04-19; Accepted 2002-07-02

Ma S, Wang TJ, Tang SW, Yang DQ, Gao J. A fast clustering algorithm based on reference and density. Journal of Software, 2003,14(6):10~1095. http://www.jos.org.cn/1000-9825/14/10.htm Abstract: The efficiency of data mining algorithms is strongly needed with data becoming larger and larger. Density-Based clustering analysis is one kind of clustering analysis methods that can discover clusters with arbitrary shape and is insensitive to noise data. In this paper, a new kind of clustering algorithm that is called CURD (clustering using references and density) is presented. The creativity of CURD is capturing the shape and extent of a cluster by references, and then analyzes the data based on the references. CURD keeps the ability of density based clustering method’s good features, and it can reach high efficiency because of its linear time complexity, so it can be used in mining very large databases. Both theory analysis and experimental results confirm that CURD can discover clusters with arbitrary shape and is insensitive to noise data. In the meanwhile, its executing efficiency is much higher than traditional DBSCAN algorithm based on R*-tree.

Key words: clustering; density; high dimension; reference; data mining

摘　　要:　　数据的规模越来越大,要求数据挖掘算法有很高的执行效率.基于密度的聚类是聚类分析中的一种,其主要优点是发现任意形状的聚类和对噪音数据不敏感.提出了一种新的基于参考点和密度的CURD(clustering using references and density)聚类算法,其创新点在于,通过参考点来准确地反映数据的空间几何特征,然后基于参考点对数据进行分析处理.CURD算法保持了基于密度的聚类算法的上述优点,而且CURD算法具有近似线性的时间复杂性,因此CURD算法适合对大规模数据的挖掘.理论分析和实验结果也证明了CURD算法具有处 ∗　Supported by the National High-Tech Research and Development Plan of China under Grant No.2002AA483440 (国家高技术研究

发展计划(863)); the National Grand Fundamental Research 973 Program of China under Grant No.G1999032705 (国家重点基础研究发展规划(973)); the Foundation of the Innovation Research Institute of PKU-IBM of China (北京大学-IBM创新研究院项目)

第一作者简介: 马帅(1975－),男,山东潍坊人,博士生,主要研究领域为数据库,信息系统.

1090

Journal of Software 软件学报 2003,14(6)

理任意形状的聚类、对噪音数据不敏感的特点,并且其执行效率明显高于传统的基于R*-树的DBSCAN算法. 关键词:　　聚类;密度;高维;参考点;数据挖掘 中图法分类号: TP181 文献标识码: A

聚类分析是数据挖掘领域中的一项重要的研究课题.它既可以作为一个单独的工具以发现数据库中数据分布的一些深入的信息,也可以作为其他数据挖掘分析算法的一个预处理步骤.聚类分析同时也是一个具有很强挑战性的领域,它的一些潜在应用对分析算法提出了特别的要求.下面是关于聚类的一些典型的要求[1]:可扩展性、处理不同数据类型的能力、发现具有任意形状的聚类的能力、输入参数对领域知识的最小限度的依赖性、能够处理异常数据的能力、数据输入顺序对聚类结果的不敏感性、处理高维数据的能力、基于约束的聚类以及聚类结果的可解释性和可用性.迄今为止,人们已经提出了许多聚类算法,如K-MEANS[2],DBSCAN[3], CURE[4],CLIQUE[5]和C2P[6],所有这些算法都试图通过不同的途径实现对大规模数据库的有效聚类,但总的来说,都没有取得理想的效果.可以说,对大规模、高维数据库的高效聚类分析仍然是一个有待研究的开放问题.

(1) 相关工作

K-MEANS是一种基于划分的聚类算法,它试图找出满足某一特定标准的k个划分(聚类),通常采用平方差的标准.K-MEANS算法的时间复杂度为O(tkn),其中n是数据的总数,k是聚类的个数,t是算法循环的次数,通常有k,t<CURE是一种自底向上的层次聚类算法,首先将输入的每个点作为一个聚类,然后合并相似的聚类,直到聚类的个数为k时为止.在CURE中指出,基于中心点的方法和所有的点的距离计算方法都不适合非球形或任意形状的聚类,因此CURE采用了折衷的方法,即用固定数目的点表示一个聚类,从而提高了算法挖掘任意形状的聚类的能力.CURE算法的时间复杂性为O(n⋅n)(低维数据)和O(n⋅n⋅logn)(高维数据),算法在处理大量数据时必须基于抽样、划分等技术.

DBSCAN是一种基于密度的聚类算法,其基本思想是:对于一个聚类中的每一个对象,在其给定半径的邻域中包含的对象不能少于某一给定的最小数目,然后对具有密度连接特性的对象进行聚类.在该算法中,发现一个聚类的过程是基于这样的事实:一个聚类能够被其中的任意一个核心对象所确定.DBSCAN算法可以挖掘任意形状的聚类,对数据输入顺序不敏感,并且具有处理异常数据(噪音)的能力.该算法的时间复杂性为O(n⋅n);在空间索引如R*-树的支持下,其复杂性为O(n⋅logn).需要指出的是,DBSCAN算法没有考虑建立索引的时间,而建立索引通常需要消耗大量的时间.

CLIQUE是一种基于网格和密度的聚类算法,具有网格类算法效率高的优点,并且可以处理高维的数据.但是不可避免地具有网格聚类算法的缺点,即在划分网格时没有或者很少考虑数据的分布,而且用一个网格内的统计信息来代替该网格内的所有点,从而导致了聚类质量的降低.

(2) 本文的工作

本文提出了一种基于参考点和密度的快速聚类算法CURD(clustering using references and density).CURD算法受CURE算法的启发,采用一定数目的参考点(references)来有效地表示一个聚类区域和形状.与CURE算法不同的是,参考点是虚拟的点,不是实际输入数据的点,而且一个聚类中的参考点数目是不固定的.CURD算法采用密度的方法屏蔽异常数据(噪音)对算法的影响,与DBSCAN算法在处理任意形状聚类方面的能力接近.CURD算法具有和K-MEANS算法相同的时间复杂性,因此效率很高.此外,采用距离的方法可以将对高维数据的处理转换到一维空间[7,8],在这个意义上,CURD算法可以处理高维数据,同时CURD算法的参考点充分考虑了输入数据的空间几何特征,因此聚类的质量要高于网格类算法.空间与二维空间的距离计算相似,为了方便地描述算法,我们在本文中以二维空间为例来分析CURD算法.

本文首先介绍CURD算法,然后从多个角度具体分析CURD算法的性能,最后进行讨论.

马帅 等:一种基于参考点和密度的快速聚类算法

1091

1 CURD聚类算法

1.1 概 念

定义1(点的密度). 对空间中任意点p和距离Radius,以p点为中心,半径为Radius的区域内的点的个数称为点p基于距离Radius的密度(density),记作Density(p,Radius).

定义2(参考点). 对空间中任意点p、距离Radius和阈值t,如果满足Density(p,Radius)>=t,则称p为参考点(reference),同时我们称t为密度阈值(density threshold).

参考点不是实际输入数据中的点,而是虚拟的点或称为假想点.

定义3(代表区域). 每个参考点代表了以该点为圆心、半径为Radius的圆形区域,我们称该区域为参考点的代表区域(representing region).

定义4(邻接参考点). 给定距离Radius和阈值t,如果参考点p,q满足Dist(p,q)<=2⋅Radius,即p和q之间的距离小于或等于2倍于Radius,则称p,q为邻接参考点(neighboring references).

实际上,如果两个参考点的代表区域相切、相交或重合(圆心距离小于或等于半径之和),那么这两个参考点就是邻接参考点. 1.2 CURD算法

在本节中,我们将详细介绍CURD算法,算法的整体框架如图1所示.CURD算法首先寻找可以准确反映输入数据空间几何特征的参考点;接着建立参考点与其代表区域内点的映射;然后对参考点进行分类,每一类参考点构成了一个聚类的基本信息;属于同一类的参考点代表区域内的点的集合,最终构成了一个聚类.

1.2.1 数据结构

基于参考点的重要性,我们首先介绍参考点的数据结构.每个参考点包含4部分信息:参考点的X坐标Xm和Y坐标Ym;参考点代表区域内的所有点的X坐标之和Xs和Y坐标之和Ys;参考点的密度(参考点代表区域内点的总数)Ns;参考点代表区域内的点的集合Ps. 1.2.2 寻找参考点

对参考点的寻找分为两步:第1步,寻找候选参考点集;第2步,将不符合密度阈值条件的候选参考点筛选过滤掉,剩下的候选参考点是参考点.对候选参考点的筛选非常简单,因此我们主要描述寻找候选参考点的过程(如图2所示).从图2可以看出,生成候选参考点的过程实际上是对Single_Scan过程(如图3所示)和Regenerate_Candidate_References过程的反复调用,因此我们将首先加以介绍.

Finding_Candidate_References (PointSet, dRadius, Iterate){

//Input: data set: PointSet, distance: dRadius, number of iterate times: Iterate //Output: candidate reference set: CandidateReferenceSet Begin

Step 1. CandidateReferenceSet=∅,I=1 Step 2. While (IStep 3. Single_Scan (PointSet, dRadius, CandidateReferenceSet) Step 4. Regenerate_Candidate_References (CandidateReferenceSet) Step 5. I++}

Step 6. Single_Scan (PointSet, dRadius, CandidateReferenceSet) End

Fig.2 Finding_Candidate_References procedure 图2 Finding_Candidate_References过程

1092

Journal of Software 软件学报 2003,14(6)

每次调用Single_Scan过程都会产生新的候选参考点集,其主要操作是将点p的坐标信息加入到候选参考点集中.如果点p与所有的候选参考点的距离都大于Radius,则生成一个新的候选参考点;否则将点p的坐标信息加入到所有与点p距离小于等于Radius的候选参考点,如图3所示.

Single_Scan (PointSet, dRadius, CandidateReferenceSet)

//Input: data set: PointSet, distance: dRadius, candidate reference set: CandidateReferenceSet //Output: candidate reference set: CandidateReferenceSet Begin

Step 1. I=1

Step 2. While (I<=PointSet.Size) { Step 3. For each point Pi:

Adding Pi’s information to every candidate reference R, whose distance with p is equal to or less than the distance dRadius: R.Xs=R.Xs+Pi.X, R.Ys=R.Ys+Pi.Y, R.Ns=R.Ns+1

If the distances between Pi and all candidate references are larger than the distance dRadius, a new candidate reference R is generated: R.Xm=Pi.X, R.Ym=Pi.Y, R.Xs=Pi.X, R.Ys=Pi.Y, R.Ns=1, which is added to CandidateReferenceSet

Step 4. I++} End

Fig.3 Single_Scan procedure 图3 Single_Scan过程

过程Regenerate_Candidate_References生成新的候选参考点,将候选参考点代表区域内的点的中心作为新的候选参考点.在Single_Scan过程中已经保存了候选参考点代表区域内所有点的X坐标和、Y坐标和以及参考点的密度.对于所有候选参考点R,用新的候选参考点R′代替,其中R′.Xm=R.Xs/R.Ns,R′.Ym=R.Ys/R.Ns,R′.Xs=0, R′.Ys=0,R′.Ns=0.

寻找候选参考点的过程需要多次调用Single_Scan过程和Regenerate_Candidate_References过程,每次调用都趋向于产生更加能够准确表示输入数据空间几何特征的候选参考点.这样,经过一系列的优化,使得产生的候选参考点就可以粗略地反映输入点集的空间几何特征,然后筛选候选参考点,将密度小于密度阈值t的候选参考点过滤掉,实际上是将代表噪音数据的候选参考点过滤掉,这样得到的参考点集就可以准确地反映输入数据的空间几何特征.

1.2.3 建立参考点与对应数据的映射

定理1. 在CURD算法中,点p具体与哪个参考点之间建立映射不会对聚类的结果产生影响,只需满足点p与该参考点的距离小于等于Radius.

证明:如果参考点R1和R2与点p的距离都小于等于Radius,由三角形边长定理:任意一边的边长小于其余两边的边长之和可知,参考点R1和R2之间的距离小于2倍的Radius,因此参考点R1和R2是相邻参考点.在空间中,由于任意不在同一直线上的3个点形成一个平面,因此上面的三角形定理仍然适用.当点p,R1和R2在同一直线时,R1和R2之间的距离等于2倍的Radius,R1和R2是邻接参考点.CURD算法中相邻参考点属于同一个聚类的基本信息,因此点p无论与参考点R1还是R2建立映射,点p最终都属于同一个聚类,定理1得证.

□

Mapping_References_and_Points过程建立参考点与其代表区域内输入数据的对应关系.理论上,对于任意点p将其与所有参考点中距离最近的参考点建立映射比较合理,由定理1可知,点p具体与哪个参考点之间建立映射不会对聚类的结果产生影响,只要点p与该参考点的距离小于等于Radius.因此,在Mapping_References_and_Points过程中,点p顺序地与参考点集中的参考点进行比较,如果两者之间的距离小于等于Radius,则在该参考点和点p之间建立映射,这样的处理可以提高算法的效率,如图4所示. 1.2.4 对参考点进行分类

在给定距离Radius和阈值t产生的参考点集中,如果两个参考点R1和R2的距离小于等于2倍的Radius,则R1和R2是邻接参考点.这样我们就可以用无向图来描述生成的参考点集,图的顶点是参考点,相邻参考点之间有一条边,处于同一个连通子图中的参考点组成一类.利用图的广度优先搜索算法(BFS)就可以将处于同一连通子图的顶点找出来,因此我们对参考点进行分类的过程不再详细地加以描述.处于同一个分类中的参考点组成了一个聚类的基本信息,可以准确地表示该聚类的空间几何特征.

马帅 等:一种基于参考点和密度的快速聚类算法

Mapping_References_and_Points (PointSet, ReferenceSet, t, dRadius)

//Input: data set: PointSet, reference set: ReferenceSet, density threshold: t, distance: dRadius //Output: reference set: ReferenceSet Begin

Step 1. Each reference, R.Ps=∅, I=1 Step 2. While (I<=PointSet.Size) { Step 3. For each point Pi:

If the distance between Pi and some reference R is equal to or less than dRadius, R.Ps=R.Ps∪{Pi}.

Otherwise, the distances between Pi and all the references are larger than dRadius, Pi is considered as noise and is discarded.

Step 4. I++} End

1093

Fig.4 Mapping_References_and_Points procedure 图4 Mapping_References_and_Points过程

1.2.5 建立聚类与对应数据的映射

由于参考点和数据之间已经建立了映射,在对参考点进行分类过程的同时实际上已经建立了聚类和参考点之间的映射,属于同一个分类中的参考点代表区域内的输入数据的集合就是一个聚类,因此聚类和数据之间的映射非常简单.

1.2.6 算法的时空复杂性分析

我们假定数据量为N,在生成候选参考点集的过程中,候选参考点的数目最大为K,循环次数为I,参考点的数目为M,聚类的个数为C.

容易知道,Single_Scan过程的时间复杂性为O(K⋅N),Regenerate_Candidate_References过程的时间复杂性为O(K),因此寻找候选参考点的过程的时间复杂性为O(I⋅K⋅N+(I−1)⋅K),对候选参考点的筛选过滤可以在O(K)内完成,这样,整个寻找参考点的过程的时间复杂性为O(I⋅K⋅N+(I−1)⋅K)+O(K).每个点可以在O(M)时间内找到对应的参考点,因此建立参考点与对应数据的映射的时间复杂性为O(M⋅N).采用图的广度优先算法对参考点进行分类的时间复杂性为O(M⋅M).聚类和数据之间的映射实际上在对参考点进行分类后就已经建立了.从上面的分析可以看出,CURD聚类算法的时间复杂性为O(I⋅K⋅N+(I−1)⋅K)+O(K)+O(M⋅N)+O(M⋅M),通常地,K,I,M<容易知道,算法的空间复杂性为O(N)+O(K)+O(C).

2 算法的性能分析

我们的测试数据集来自CURE算法中的data set 1(DS1)、DBSCAN算法中的database 3(DS2)和采用Dr. Jörg Sander提供的DBSCAN程序仿照DBSCAN中database 2生成的数据集(DS3),数据量分别为100000,203,306(如图5所示).我们实验的硬件环境是IBM Netfinity 5500:两个X86 Family 6 Model 10 Stepping 1 GenuineIntel~700Mhz的CPU、主存为512M、

硬盘为20G;软件环境是:操作系统为Microsoft Windows 2000 Server,算法采用Java编写. 2.1 聚类效果的比较

CURD算法的参数Radius和t与DBSCAN算法的Eps和MinPts有着相似的特点,此外,DBSCAN算法也是一种基于密度的聚类算法,因此选择该算法与CURD算法作比较.图6、图7分别是DBSCAN算法和CURD算法对数据集DS1,DS2和DS3的聚类结果.图8、图9是CURD算法发现的候选参考点和参考点.

1094

Journal of Software 软件学报 2003,14(6)

可以看出,CURD算法可以很好地处理任意形状的数据集,同时也较好地屏蔽了异常数据的影响.比较图6和图7也可以发现,CURD算法和DBSCAN算法聚类的结果非常接近.从图8可以看出,候选参考点基本上反映了输入数据的几何空间特征,但是仍然受到噪音数据的影响;从图9可以看出,经过对候选参考点的筛选过滤,得到的参考点准确地反映了原有数据的空间几何特征. 2.2 输入参数的设定

CURD算法有3个主要参数:距离Radius、密度阈值t和循环次数Iterate.参数的选择会影响算法的聚类结果和执行效率.

在实验中我们发现,如果距离Radius,密度阈值t与DBSCAN算法的参数Eps,MinPts取值相同,则两个算法会产生类似的结果.在DBSCAN算法中,参数Eps,MinPts的取值通常难以确定,但是在CURD算法中,距离Radius和密度阈值t的选取可以近似得到.距离Radius需要考虑的是整个数据的空间,距离Radius越小,聚类的结果越好,但是参考点的数目也就越多,算法的执行效率就会变低.我们经过实验还发现,在Radius取整个数据空间的1/50~1/100时就可以取得较好的效果,如:DS1是30×30的二维空间,取距离为0.5;DS2和DS3是100×100

马帅 等:一种基于参考点和密度的快速聚类算法

1095

的二维数据空间,取距离为2.同时也发现,使用数据总量与候选参考点的数目比值,即候选参考点的平均密度作为密度阈值可以取得较好的效果.至于循环次数Iterate,需要指出的是,我们所有的实验结果都是在Iterate=4的情况下得到的,在条件允许的情况下,Iterate的值越大,聚类的结果就越好,同时所需时间也就越长. 2.3 执行效率的比较

我们选择基于R*-树的DBSCAN算法与CURD算法进行算法的比较,有3个主要原因:(1) 两个算法都是基于密度的聚类算法;(2) 两个算法的输入参数有相似性;(3) 基于R*-树的DBSCAN算法的时间复杂性为O(n⋅logn),因此,DBSCAN算法是一种效率比较高的聚类算法.

从图10中可以看出,CURD算法的效率明显高于DBSCAN算法,因此CURD算法是一种效率非常高的聚类算法.此外,由于基于R*-树的DBSCAN算法需要建立索引,而建立索引的时间代价是很大的;如果把建立索引的时间也考虑进去,则CURD算法将会大大优于DBSCAN算法.

3 讨 论

在本文中我们提出了一种使用参考点来描述数据空间几何特征的方法,并提出了一种基于参考点和密度的快速聚类算法CURD,CURD算法保持了基于密度的聚类算法可以发现任意形状的聚类和对噪音数据不敏感的优点;保持了K-MEANS算法的高效性,具有接近线性的时间复杂性,适合对大规模数据的挖掘.我们的理论分析和实验结果也证明了上述结论.

采用距离的方法可以将对高维数据的处理转换到一维空间[7,8],从这个意义上看,CURD算法可以处理高维数据.我们下一步的工作是测试CURD算法在高维情况下的性能.此外,本文的算法找到的参考点可以准确地反映数据的几何空间特征,因此,我们正在考虑如何利用CURD算法对数据进行有效的抽样处理.

致谢 IBM信息基础设施技术组陈捷博士后、宋国杰、遇辉等博士生对本文的完成给予了很大帮助,DBSCAN算法的作者之一Dr.Jörg Sander先生提供了DBSCAN程序和相应的信息,在此一并表示感谢. References:

[1] Han JW, Kambr M. Data Mining Concepts and Techniques. Beijing: Higher Education Press, 2001. 145~176.

[2] Kaufan L, Rousseeuw PJ. Finding Groups in Data: an Introduction to Cluster Analysis. New York: John Wiley & Sons, 1990. [3] Ester M, Kriegel HP, Sander J, Xu X. A density based algorithm for discovering clusters in large spatial databases with noise. In:

Simoudis E, Han JW, Fayyad UM, eds. Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Portland: AAAI Press, 1996. 226~231.

[4] Guha S, Rastogi R, Shim K. CURE: an efficient clustering algorithm for large databases. In: Haas LM, Tiwary A, eds. Proceedings

of the ACM SIGMOD International Conference on Management of Data. Seattle: ACM Press, 1998. 73~84.

[5] Agrawal R, Gehrke J, Gunopolos D, Raghavan P. Automatic subspace clustering of high dimensional data for data mining

application. In: Haas LM, Tiwary A, eds. Proceedings of the ACM SIGMOD International Conference on Management of Data. Seattle: ACM Press, 1998. 94~105.

[6] Alexandros N, Yannis T,Yannis M. C2P: clustering based on closest pairs. In: Apers PMG, Atzeni P, Ceri S, Paraboschi S,

Ramamohanarao K, Snodgrass RT, eds. Proceedings of the 27th International Conference on Very Large Data Bases. Roma: Morgan Kaufmann Publishers, 2001. 331~340.

[7] Berchtold S, Bohm C, Kriegel H-P. The pyramid-technique: towards breaking the curse of dimensionality. In: Haas LM, Tiwary A,

eds. Proceedings of the ACM SIGMOD International Conference on Management of Data. Seattle: ACM Press, 1998. 142~153. [8] Yu C, Ooi BC, Tan K-L, Jagadish HV. Indexing the distance: an efficient method to KNN processing. In: Apers PMG, Atzeni P,

Ceri S, Paraboschi S, Ramamohanarao K, Snodgrass RT, eds. Proceedings of the 27th International Conference on Very Large Data Bases. Roma: Morgan Kaufmann Publishers, 2001. 421~430.