空间数据挖掘中的聚类算法

1、空间数据挖掘中的聚类算法朱屹, 刘安丰（中南大学，软件学院，湖南 长沙，410075）摘要:本文系统综述了文献中发表的大量空间聚类算法，依据这些算法的特点，将它们归纳为两类：划分聚类算法、层次聚类算法。针对划分聚类算法，重点分析了PAM、CLARA和CLARANS算法。针对层次聚类算法，重点综述了凝聚和分解层次聚类，分析了BIRCH、CURE、CHAMELEON算法。比较了这些算法的复杂度，并介绍了相关应用。关键词:聚类算法；聚类分析；数据挖掘；空间数据库1. 引言随着数据挖掘技术的出现，学者们开始采用各种方法从大型数据库的数据中发现知识，同样也利用数据挖掘技术对空间数据进行分析。这种空间数据

2、挖掘的方法很好地弥补了传统空间统计分析的不足，很快受到了学者的重视。空间数据挖掘，也称基于空间数据库的数据挖掘和知识发现(Spatial Data Mining and Knowledge Discovery)，作为数据挖掘的一个新的分支，是指从空间数据库中提取用户感兴趣的空间模式与特征、空间与非空间数据的普遍关系及其它一些隐含在数据库中的普遍的数据特征1。目前大多数空间数据挖掘方法都是基于空间聚类与关联规则发现。空间聚类方法是空间数据挖掘中的主要方法之一,是在一个比较大的多维数据集中根据距离的度量找出簇或稠密区域. 聚类算法无需背景知识,能直接从空间数据库中发现有意义的空间聚类结构2。在无先

3、验知识的情况下,聚类分析技术是进行数据挖掘时的首选3，因而运用空间数据聚类方法来处理海量数据,对于提取大型空间数据库中有用的信息和知识具有十分重要的现实意义。2. 概述目前，针对聚类分析提出了许多算法，这些算法可大致分为两类：划分聚类算法、层次聚类算法。划分聚类算法依据对象相似性来分配对象，如k-means4和k-medioid。层次聚类法是一系列连续的合并和分解过程，可以自上向下连续分解，也可以自下向上连续合并。基于格网的聚类算法也可视为层次聚类算法。基于位置的聚类算法依赖局部对象之间的关系来聚类，既可以基于密度，也可以基于随机分布聚类。对于空间数据聚类，则是基于空间数据的特点对聚类算法进行

4、改进, 从而使之适用于空间对象的特性，如DBSCAN 算法5 、CLATIN算法6、DDSC算法7等。3. 划分聚类划分算法大多数是在PAM（Partition Around Medoids）算法、CLARA（Clustering Large Applications）算法和CLARANS（Clustering Large Application based upon Randomized Search） 8算法的基础之上发展起来的。在数据量较大，计算复杂度较高时，PAM和CLARA算法效率较低。因此为了提高效率，提出了基于随机搜索的CLARANS算法。实验表明CLARANS优于PAM与CLA

5、RA。后有学者在CLARANS上进一步发展了新的划分聚类算法，进行了推广，提出了概念聚类的方法。3.1. PAM算法PAM算法4首先在n个对象中随机选取k个对象作为中心点。将余下的n-k个对象(非选择对象)依据与中心点距离或相异程度最小原则划分到上述k个聚类中。即如果是未选择对象，是中心点，当是以为中心点的聚类。表示对象与中心点的相异程度。然后，从非选择对象中选择一个对象与交换，如果交换使得聚类质量提高，则用替换原中心点。3.2. CLARA算法为了减少PAM算法的复杂度，CLARAR算法8选择实际数据的一小部分作为数据样本。然后用PAM算法从样本中选择中心点。它的思想是，如果样本是以非常随机

6、的方式选取的，它应当足以代表原来的数据集合。算法的有效性取决于样本的大小CLARA中心点，在抽取的样本中搜索最佳的k个中心点。但是CLARAR算法的缺点是，如果任何取样得到的中心点不属于最佳中心点，算法将不能得到最佳聚类。3.3. CLARANS算法为了提高算法的有效性，Ng和Han9提出了CLARANS算法。算法结合了PAM和CLARA算法的特点，它只搜索数据集的子集且并不限制固定的搜索样本。该算法将己知n个对象，发现k个中心点的过程抽象为图的搜索过程。在图中一个结点是k个对象的集合，其中是所选的中心点。图中所有点的集合为：如果两个节点仅有一个对象不同，则称此两节点是“邻居”。每个节点有k(

7、n-k)个邻居。每个节点代表一种聚类。每个节点可以赋予一个开销，这个开销可以表示为聚类中每个对象与它的中心点的区别的和。如果目前的节点已经与最大数目的邻居(maxneighbor)进行了比较且仍然是花销最小，目前的节点就可认为是“局部最优”。在局部最优与目前为止获得的最小开销比较，两者中的最小者设为mincost。CLARANS算法是迭代搜索局部最小值过程，直到numlocal个最小值被发现为止。CLARANS与PAM的区别在于CLARANS不检查节点的每个邻居，而是仅检查一个节点所有邻居的样本。与CLARA的区别在于，CLARANS并不将它的搜索限制在特定的子图范围内，而是搜索原始图。CLA

8、RA在搜索的每个阶段有一个固定的样本，而CLARANS在搜索的每一步都随机抽取一个样本。3.4. 改进的划分聚类算法为了提高CLARANS的效率，Ng和Han等9提出了随机搜索的改进K-medoid算法，Ester等10用基于R*-树的数据聚焦法进一步提高搜索效率，此外还有如基于免疫规划的k-means 聚类算法11，启发式的k-medoid算法12等，改进的EM算法13。EM是以概率为背景对k- means算法的扩展，它不把对象分配给一个确定的簇,而是根据对象与簇之间隶属关系的概率分配对象，在簇之间没有严格的边界。以上各种算法虽然都进行了一定的改进，但在面对一些特定情况时，仍有一定的局限性：

9、（1）当聚类尺寸差异较大时，位于大聚类边缘的对象也许更靠近邻近的较小聚类，会导致属于大聚类的对象被分配给较小聚类；（2）采用距离度量相似性易于生成球状聚类，当对象实际分布形状为非球状时，得到的聚类结果与实际情况差别很大；（3）计算准则函数时，需要扫描整个数据集，当对象数较大时，计算时间无法忍受；（4）与其它划分算法一样，CLARANS和CLARA易于收敛于局部最优，效率受取样样本尺寸大小影响；（5）如果不采用聚焦技术，算法需对数据集进行多次I/O扫描，降低算法效率；3.5. 概念聚类概念聚类是分割算法的一种延伸,它用描述对象的一组概念取值将数据划分为不同的类，而不是基于几何距离来实现数据对象之

10、间的相似性度量14。概念聚类能够输出不同类以确定其属性特征的覆盖，并对聚类结果给予解释。当利用概念聚类实行空间数据挖掘时，需对数值型字段数据概念化。Han和Fu1先用相同的小间隔将数值字段中的数据分段，然后将数据段合并成期望的数据个数基本相同的概念段，实现较简单，效率较高。但是这种方法分割每个数值型字段的数据段Interval是一个不变的量，用于概念分段的标准只有数据个数，没有考虑数据的分布。4. 层次聚类4.1. 基础的层次聚类算法层次聚类算法将数据集分解成树状图子集,直到每个子集只包含一个目标，可用凝聚或方法的方法构建。它无需参数，但要定义停止条件。这类算法主要基于两种方法：凝聚层次聚类(

11、agglomerative hierarchical clustering)和分解层次聚类(divisive hierarchical clustering)。一开始将每个对象视为一类。这些类依据它们之间的相似性凝聚，直到仅剩一个聚类为止。分解层次聚类与凝聚层次聚类相反，一开始所有对象属于一类，然后分解聚类，直到每个对象属于某个聚类为止。4.1.1. 凝聚层次算法凝聚层次算法中计算新类与其它类的距离不需要直接从距离公式出发，通过递推公式，可以利用产生新类前的距离来计算得到。其中基于重心法的聚类方法不能发现任意形状和不同尺寸大小的聚类。根据类间距离定义的不同又分为最短聚类方法和最长聚类方法。最短

12、距离的聚类方法又称单链接方法(Single-link cluster algorithm)，该方法能够发现任意形状和不同尺寸大小的聚类，但易受“噪音”数据影响。同时，也易受“链条”现象困影响，以至于很长的点串被分配到同一聚类中。最长距离法又称完全链接法(Complete-link cluster algorithm)，该方法易于产生空间体积趋向于相等和“更紧凑”的聚类。从实用角度来看，完全链接法比单链接方法产生更实用的聚类层次。4.1.2. 分解层次算法分解层次聚类开始时所有对象是一类，为了将对象分为k类，有两种方法。一种是最优分割法，这种方法一次就可将对象分为k类。另一种是二分法，这种方法首

13、先将对象分为两类，然后在这两类之中选取误差较小的那一种分解，从而产生成3个类，这样一直分解下去，知道分为k类为止。4.2. 改进的层次聚类算法对于前两种层次聚类算法，它们终止条件不易确定，而且选择合并或分裂点比较困难。却又非常关键，因为一旦一组对象被合并或者分裂，下一步的处理将在新生成的聚类上进行，已做的处理不能被撤销，聚类之间也不能交换对象：如果在某一步没有很好地选择合并或分裂的决定，可能会导致低质量的聚类结果，不具有很好的可伸缩性13。因此产生了凝聚分层聚类和迭代重定位方法的集成的算法，如BIRCH、CURE和CHAMELEON等。4.2.1. BIRCH算法BIRCH是一个综合的分层聚类

14、方法,其基本思想是:将数据对象压缩成许多子聚类,然后在这些子聚类上执行聚类过程。它采用一个聚类特征三元组表示一个簇的有关信息，从而使一簇点的表示可用对应的聚类特征，而不必用具体的一组点来表示。 它通过构造满足分支因子和簇直径限制的聚类特征树来求聚类。聚类特征树是一个具有两个参数分枝因子(和类直径)的高度平衡树。分枝因子规定了树的每个节点孩子的最多个数，而类直径体现了对一类点的直径大小的限制，即这些点在多大范围内可以聚为一类。BIRCH通过一次扫描就可以进行较好的聚类，由此可见，该算法适合于大数据量。BIRCH 算法只适用于类的分布呈凸形及球形的情况，并且由于BIRCH 算法需提供正确的聚类个数

15、和簇直径限制，对不可视的高维数据不可行。4.2.2. CURE算法CURE（Clustering Using Reprehensives）较好地解决了偏好球形和相似大小的问题，它采用了一种新颖的层次聚类算法，该算法选择基于质心和基于代表对象方法之间的中间策略。它不用单个质心或对象来代表一个簇，而是选择数据空间中固定数目的具有代表性的点。算法通过随机取样和划分两种方法的组合：一个随机样本被划分,每个划分被部分聚类，然后将这些结果簇聚类。CURE算法产生了一些有趣的结果：CURE能发现有趣形状的簇，能过滤边界点，抽样和划分能减少输入规模，对大型高维数据库来说，CURE 时间复杂度关于样本大小是二次

16、的，而与整个数据库大小无关。 虽然CURE 算法有以上优点，但是聚类结果对输入的参数比较敏感，在设置合适的参数值时要用到专家知识。4.2.3. CHAMELEON算法CHAMELEON15是一个在分层聚类中采用动态模型和密度思想的聚类算法。CURE及其相关的方案忽略了关于两个不同簇中对象的聚集互连性的信息，其特点表现在判断子聚类的相似性时既考虑了子聚类之间的互连性，又考虑了子聚类之间的近似度，并提出了综合(包含簇内部分布特性的)互连性与近似度度量的动态模型。CHAMELEON基于k-最近邻居图方法对数据集建模。k-最近邻居图的每个顶点表示一个对象，如果两个对象彼此是对方的k-最近邻居，则两点之

17、间存在一条边。数据集中每个簇对应于图的一个子图。使用k-最近邻居图表示数据集的优点是：彼此远离的对象，在图中是完全断开的。其次，对象与邻居之间半径值由分布区域中对象分布的密度动态控制，在对象稠密区域，半径值小，反之半径值大，实现了动态邻居的特性。在发现高质量的任意形状的聚类方面有更强的能力。但是，它对于高维数据的处理代价仍然是二次非线性的。5. 讨论与结论5.1. 复杂度以上各种算法复杂度如表1所示：表1 算法复杂度算法复杂度PAMO(k(n-k)2)CLARAO(k(s+k)2 +k(n-k)CLARANSO(n2)凝聚算法O(n2)分解算法大于O(n2)BIRCHO(N2)CUREO(nl

18、ogn)CHAMELIONO(nm+nlogn +m2log m)上表中对于PAM而言，共有k(n-k)对与，每对计算总代价需要检查n-k个非选择对象，因此，一次循环的时间复杂度为O(k(n-k)，算法的总时间复杂度是O( (1+)k(n-k)2)，其中是成功交换的次数。而CLARA算法的有效性取决于样本s的大小。对于CLARANS，Ng和Han认为其计算复杂度与对象个数n大约成线性比例关系。Ester等支持了这一观点13。其聚类质量取决于所用的采样方法。凝聚层次聚类在算法开始时需要计算出所有对象两两间的距离，其时间复杂度是O(n2)，而且经常效率较低，其空间复杂度也为O(n2)。尽管其时间复

19、杂度不是很理想，该方法仍被广泛使用。而分裂算法的运算量则比凝聚方法大，凝聚层次聚类方法比分解层次聚类方法使用的更普遍。BIRCH对数据集合的单遍扫描的计算复杂度是O(N)，N是对象的数目。当N远大于子聚类数k时，其复杂度为O(N)，而当N接近k时，复杂度是O(N2)。对于CURE算法最坏情况下的时间复杂度是O(nlogn)。n是随机采样对象个数，而不是数据集对象数N。对低维数据集，时间复杂度减少为O(n2)。在CHAMELION的复杂度 O(nm+nlogn +m2log m)中，n是数据集对象数，m是算法是图划分得到的子聚类个数，可见图划分所得聚类个数对效率影响较大。5.2. 算法应用空间聚

20、类技术的发展为地理数据分析等实际应用提供了许多有用的工具。Lin 等根据类别和特征,研究了空间数据库中的临近关系匹配算法。Murray和Shyy提出了一种交互的探测性空间数据聚类分析技术用于分布显示中集成的属性和空间特征。Lee等通过构造多边形的聚类器，用于数据富集区域，林冬云和刘慧平3将北京市海淀区的企业进行层次聚类，得到了企业的空间分布特征。但是绝大多数聚类算法不能直接解决基于物理约束的聚类问题,为了使得空间聚类更实用,还要对聚类算法深入研究,使用户能将聚类算法和物理约束综合起来考虑。在许多应用中,像山、河等自然障碍物能严重影响地理数据聚类结果。Tung等提出了一种在空间数据挖掘中实行空间

21、聚类时,处理河流、高速公路等阻隔的算法。5.3. 结论空间聚类分析既可以发现隐含在海量数据中的聚类规则，又可以与其它数据挖掘方法结合使用，发掘更深层次的知识，提高数据挖掘的效率和质量，是空间数据挖掘的重研究方向之一。本文系统分析和总结了文献中发表的大量空间聚类算法，依据这些算法的特点，将它们归纳为两类：划分聚类算法、层次聚类算法。针对划分聚类算法，重点分析了PAM、CLARA和CLARANS算法。针对层次聚类算法，重点接受了凝聚和分解层次聚类，分析了BIRCH、CURE、CHAMELEON算法。比较了这些算法的复杂度，并介绍了相关应用。目前在空间数据库聚类算法方面的主要工作的发展方向正朝着能使

22、算法处理更大更高维的数据，使聚类后的信息能真实地保持各类别中对象的原有信息努力。算法还将近一步引进采样、压缩、索引和网格等技术，增强算法的伸缩性。此外，模糊聚类与约束条件的引入，使算法更好地用于现实的地理现象中。参考文献1 J.Han, Y. Fu, W.Wang, J.Chiang, W.Gong et al. DB Miner: A system for mining knowledge in large relational databases.In:Proc.1996 Int'l Conf. on Data Mining and Knowledge Discovery (KDD

23、, 96), 250-255.2 李德仁,王树良,李德毅,等. 论空间数据挖掘和知识发现的理论与方法. 武汉大学学报:信息科学版, 2002,27(3): 1-133 林冬云,刘慧平. 应用空间聚类进行点数据分布研究. 北京师范大学学报(自然科学版), 2006, 42(4):419-4234 R. Agrawal, R. Srikant, Fast algorithms for mining association rules, In: Proceedings of the International Conference on VLDB, Santiago, Chile, Septembe

24、r, 19945 M. Ester, H-P. Kriegel, J. Sander and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the 2nd ACM,. SIGKDD, 1996, 226-231. 6 Zhang, I. Couloigner. A new and efficient k-medoid algorithm for spatial clustering. In Proceedings

25、 of the 2005 ICCSA, 181-189.7 B, Borah, D. K. Bhattacharyya. DDSC: a density differentiated spatial clustering technique. Journal of Computers, 2008, 2:72-79.8 L. Kaufman, P.J. Rousseeuw. Finding groups in data: An introduction to cluster analysis. Wiley&Sons, 1990.9 R.T. Ng, J. Han. Efficient a

26、nd effective clustering methods for spatial data mining. In:proc.1994 Int. Conf. Very Large Data Bases(VLDB'94),144-155,199410 M. Ester. A database interface for clustering in large spatial databases. In: 1st Int.Conf. on Knowledge Discovery and Data Mining, Montreal,199511 T. Kanungo, D. M. Mou

27、nt, N. Netanyahu, et al. A local search approximation algorithm for k-means clustering. Computational Geometry: Theory and Applications ,2004 ,28 ,89-11212 陈金山, 韦岗. 遗传+模糊C-均值混合聚类算法. 电子与信息学报, 2002, 24 (2): 210-21513 J Han, M Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann, 200114 L. Pitt, R.E. Reinke. Criteria for polynomial time (conceptual) Clustering. Machine Learning, 1998, 2(4):371-396Clustering Algorit