空间聚类分析算法及其参数选择

聚类分析(clustering analysis)主要根据空间对象的特征将描述个体的数据集划分成一系列相互区分的组，使得属于同一类别的个体之间的差异尽可能地小，而不同类别的个体之间的差异尽可能地大或者说类间相似性尽量小，而类内相似性尽量大(Kaufman and Rousseew，1990；Murray and Shyy，2000)。与规则归纳不同的是，聚类算法无需背景知识，能直接从空间数据库中发现有意义的空间聚类结构。

聚类算法用特征表示空间对象，一个空间对象为特征空间的一个点(Murray and Esti vill-Castro，2008)。空间数据库中的聚类是对目标的图形直接聚类，空间目标有点状、线状、面状等多种类型，有时聚类形状复杂，同时数据量庞大，这就使空间数据挖掘对聚类算法提出了更高的要求：能处理任意形状的聚类；适用于点、线、面等任意形状对象的聚类；处理大型空间数据库时效率较高；算法需要的参数能自动确定或用户容易确定。在数据挖掘中，聚类按一定的距离或相似性测度在空间数据集中标识聚类或稠密分布的区域，以期从中发现数据集的整个空间分布规律和典型模式，它不仅是知识发现任务的一个重要组成部分，也是数据挖掘系统中发现分类知识、广义知识、关联知识等共性知识和离群知识的先决条件。聚类的质量主要体现在紧凑性(compactness)和可区分性(separation)，紧凑性反映每个聚类的紧凑或密集程度，而可区分性反映不同聚类之间的差异或距离。

根据相似性度量和聚类评价准则等的不同，常用的聚类方法包括分割方法(pmtitioning methods)、层次方法(hierarchical methods)、基于密度方法(density-based methods)和基于网格方法(grid-based methods)等(Kaufman and Rousseew，1990；Agrawal and Srikant，1994；Zhang el al.，1996；Guha et a1.，1998；Sheikholeslami et a1.，1998；George et al.，1999；Hinneburg and Keim，1999；Grabmeier and Rudolph，2002；淦文燕，2003；Wang et al.，2011)。

分割算法根据目标到聚类中心的距离迭代聚类，对于给定的聚类个数和某个基于距离的目标准则函数划分数据，使目标准则函数在此划分下达到最优。典型算法包括Kmeans、K-mediods、PAM(paltitioning around medoids)、CLARA(clustering large appplication)和CLARANS(clustering large application based upon randomized search)算法等。这些分割算法都采用了距离平方和准则及基于单代表点(类均值或者类中心)的类原型表示方法，都面临共同的球形偏见问题。针对任意形状的聚类发现，一种有效的解决方法是采用连续光滑的非线性映射将数据空间中的对象映射到高维特征空间中，使之具有较好的线性可分性，然后在特征空间中实现聚类划分，代表算法有Mercer-Kernel Cluslering和SVC(support vector clustering)、DBCLASD(distribution based clusteling of large spatial databases)等。概念聚类是分割算法的一种延伸，它用描述对象的一组概念取值将数据划分为不同的类，而不是基于几何距离来实现数据对象之间的相似性度量。概念聚类能够输出不同类确定其属性特征的覆盖，并对聚类结果给予解释。

层次方法递归地对数据进行合并或分裂，将数据集划分为嵌套的类层次结构或类谱系图，可分为凝聚式和分裂式。一般地，分裂式层次方法的运算量比凝聚式层次方法更大，应用也不如后者广泛。凝聚式层次聚类算法结合自下而上聚类生成策略与循环重定位技术实现数据集的分层聚集，如Single-Link、Complete-Link、Group Average和Cenlroid等，它们采用链式距离衡量类间相似性，聚类结果存在球形偏见，且算法的时间复杂度很高。改进的层次聚类算法通过有机地集成划分方法、层次方法、随机抽样等多种聚类技术来提高聚类结果的质量和改善聚类算法的性能代，代表算法包括BIRCH(balanced iterative reducing and clustering using hierarchies)、CURE(clustering using representatives)、chameleon和CLIQUE(clustering in quest)，聚类结果严重依赖于用户参数的合理设置。

基于密度的聚类针对复杂形状的聚类发现而提出，每个聚类对应数据分布的一个相对密集区，通过将空间划分为若干由低密度区域(对应噪声或离群数据)所分割的连通高密度区域来实现聚类分析。典型算法包括：DBSCAN(density based spatial clustering of applications wilh noise)、OPTICS(ordering points to identify the clustering structure)和DENCLUE(density based clust ering)等。聚类质量严重依赖于算法参数的仔细选择。 (www.xing528.com)

基于网格的聚类通过空间划分实现聚类分析将空间划分为有限数目的网格单元形成网格结构，所有聚类操作都在网格结构上进行。典型算法有STING(statistical information grid-based method)、Wave Cluster、CLIQUE和OptiGrid等。算法的处理时间与对象个数无关，具有良好的效率和可扩展性，但聚类结果的质量依赖于网格划分的量化尺度。

根据数据挖掘中聚类算法的典型性能要求，如算法的可扩展性、发现任意形状聚类的能力、对用户输入参数的依赖性、处理噪声或异常数据的能力、处理高维数据的能力、对数据输入顺序的不敏感性等对上述常用聚类算法的效率和有效性进行分析和比较。

分割方法的聚类质量比较差，仅适于发现大小相等的球形聚类，抗噪声能力弱，对数据的输入顺序很敏感，需要用户预先确定聚类个数；改进的层次方法具有相对较好的聚类质量，但算法的时间复杂度比较高；基于密度的方法和基于网格的方法具有良好的聚类质量和算法性能，能够发现任意形状的聚类，能够有效处理噪声数据，对数据输入顺序不敏感，但是聚类结果的质量都依赖于多个算法参数的合适选取；此外，除了DENCLUE和CLIQUE等少数算法以外，大多数聚类算法都不能有效处理高维数据。

此外，还有数据场聚类、模型聚类、图聚类、模糊聚类、神经网络聚类、数学形态学等聚类方法。邸凯昌(2001)分析了空间数据挖掘中的聚类和特征关系，提出了发现聚合亲近关系和公共特征的算法。Ester等(1995)使用聚类方法研究了在大型空间数据库中挖掘类别判读知识的技术。Tung等(2007)提出了一种在空间数据挖掘中实行空间聚类时，处理河流、高速公路等阻隔的算法。Murray和Shyy(2010)提出了一种探测性空间数据聚类方法。