空间聚类的研究现状及其应用＊戴晓燕1 过仲阳1 李勤奋2 吴健平1(1华东师范大学教育部地球信息科学实验室 上海 200062)(2上海市地质调查研究院 上海 200072)摘 要 作为空间数据挖掘的一种重要手段,空间聚类目前已在许多领域得到了应用。
文章在对已有空间聚类分析方法概括和总结的基础上,结合国家卫星气象中心高分辨率有限区域分析预报系统产品中的数值格点预报(HLAFS)值,运用K-均值法对影响青藏高原上中尺度对流系统(MCS)移动的散度场进行了研究,得到了一些有意义的结论。
关键词 空间聚类 K-均值法 散度1 前言随着GPS、GI S和遥感技术的应用和发展,大量的与空间有关的数据正在快速增长。
然而,尽管数据库技术可以实现对空间数据的输入、编辑、统计分析以及查询处理,但是无法发现隐藏在这些大型数据库中有价值的模式和模型。
而空间数据挖掘可以提取空间数据库中隐含的知识、空间关系或其他有意义的模式等[1]。
这些模式的挖掘主要包括特征规则、差异规则、关联规则、分类规则及聚类规则等,特别是聚类规则,在空间数据的特征提取中起到了极其重要的作用。
空间聚类是指将数据对象集分组成为由类似的对象组成的簇,这样在同一簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大,即相异度较大。
作为一种非监督学习方法,空间聚类不依赖于预先定义的类和带类标号的训练实例。
由于空间数据库中包含了大量与空间有关的数据,这些数据来自不同的应用领域。
例如,土地利用、居住类型的空间分布、商业区位分布等。
因此,根据数据库中的数据,运用空间聚类来提取不同领域的分布特征,是空间数据挖掘的一个重要部分。
空间聚类方法通常可以分为四大类:划分法、层次法、基于密度的方法和基于网格的方法。
算法的选择取决于应用目的,例如商业区位分析要求距离总和最小,通常用K-均值法或K-中心点法;而对于栅格数据分析和图像识别,基于密度的算法更合适。
此外,算法的速度、聚类质量以及数据的特征,包括数据的维数、噪声的数量等因素都影响到算法的选择[2]。
本文在对已有空间聚类分析方法概括和总结的基础上,结合国家卫星气象中心高分辨率有限区域分析预报系统产品中的数值格点预报(HLAFS)值,运用K-均值法对影响青藏高原上中尺度对流系统(MCS)移动的散度场进行了研究,得到了一些有意义的结论。
2 划分法设在d维空间中,给定n个数据对象的集合D 和参数K,运用划分法进行聚类时,首先将数据对象分成K个簇,使得每个对象对于簇中心或簇分布的偏离总和最小[2]。
聚类过程中,通常用相似度函数来计算某个点的偏离。
常用的划分方法有K-均值(K-means)法和K-中心(K-medoids)法,但它们仅适合中、小型数据库的情形。
为了获取大型数据库中数据的聚类体,人们对上述方法进行了改进,提出了K-原型法(K-prototypes method)、期望最大法EM(Expectation Maximization)、基于随机搜索的方法(ClAR ANS)等。
K-均值法[3]根据簇中数据对象的平均值来计算———————————————＊基金项目:国家自然科学基金资助。
(资助号:40371080)收稿日期:2003-7-11第一作者简介:戴晓燕,女,1979年生,华东师范大学地理系硕士研究生,主要从事空间数据挖掘的研究。
·41·2003年第4期 上海地质Shanghai Geology相似度,将簇中对象的平均值(或称为质心)作为簇中心。
算法首先在n 个数据对象中随机选择k 个对象,每个对象代表了一簇的平均值;对余下的每个对象,根据其与各个簇中心的距离,按距离最小的原则,将它们分配给最近的簇;在此基础上,重新计算每个簇的平均值;如此往复,直到误差平方和的值最小,即:E =∑kj =1∑i l ∈Cj ︳i l -w j ︳2的值最小,此时,簇中的成员不再发生变化。
式中,il 是给定的数据对象,wj 是簇Cj 的平均值。
其时间复杂度为O (nkt ),其中,n 是数据对象的个数(下同),k 是簇的个数(下同),t 是迭代次数。
该法在实际工作中得到了广泛的应用。
例如,Lucchese 和Mitra 利用K -均值法实现了对彩色图像的非监督分割[4];Linde 和Buzo等人则在对K -均值法修改的基础上,提出了用于图像压缩的LB G 算法[5];Tapas 和David 等人根据kd -树的数据结构特征对K -均值法进行了改进,提出了一种简单而有效的过滤算法(filtering algo -rithm )[6],并将它应用于色彩定量化、数据压缩和图像分割,取得了较好的效果。
此外,Steinbach 的研究也表明,分层划分的K -均值法也适合于文本聚类[7]。
然而,运用该法进行聚类时,其缺点是容易陷入局部最优解,很难找到全局最优解,且对噪声和异常数据敏感,因而限制了其应用范围。
K -中心法将簇中位置最中心的对象作为簇中心,其目的是消除K -均值法对于孤立点的敏感性。
例如,PAM (Partitioning around Medoid )[8]是一种早期提出的K -中心法,该法首先从n 个数据对象中随机选择k 个对象作为初始中心点,进而分析所有可能的对象对,用产生误差平方和值减少的对象代替原来的中心点;迭代过程中产生的最佳对象集就成为下次迭代的中心点,直到误差达到最小。
其每步迭代的时间复杂度为O (k (n -k )2)。
与K -均值法相比,其效率较低。
与前述方法相比,基于选择的方法CLARA(Clustering Large Applications )[8]则适合处理数据量较大的情形。
计算过程中,首先从数据库中随机提取多个样本,对每个样本应用PAM 法选择中心点,在此基础上,选择误差值最小的中心点集合,将误差最小的聚类结果作为输出。
聚类的质量即平均相异度根据整个数据集中的所有对象计算。
CLARA 法每步迭代的时间复杂度为O (ks 2+k (n -k )),其中,s是样本的大小。
然而,运用该法聚类时,若采样的均匀性较差,那么,基于样本的最优聚类结果并不能代表整个数据集合的最优聚类,因而就不能得到最佳的聚类结果。
而ClARANS (Clustering Large Applications basedupon Randomized Search )[9]法则是一种基于随机搜索的方法,其优点是一方面改进了CLARA 的聚类质量,另一方面拓展了数据处理量的伸缩范围。
CL AR ANS 法与CL ARA 法的本质区别在于CLARA 法在搜索的开始是抽取节点的样本,而CLARANS 法在搜索的每一步是抽取邻居的样本。
Ng 与Han 的研究表明[9],与PAM 和CLARA 法相比,Cl A R ANS 法的聚类效果明显占优,但其时间复杂度仍为O (n 2),因此,低效仍是其存在的缺点之一。
为此,Ester 等人在已有研究的基础上,利用R ＊-树和聚焦技术来改善其效率[10],取得了明显的成效。
此外,Ng 与Han 对ClARANS 法进行了改进,提出了空间属性占优法(Spatial Dominant Approach )和非空间属性占优法(Non -Spatial Dominant Ap -proach ),其主要思想是假定输入的空间数据库同时包含空间属性和非空间属性数据,利用CLARANS 法来处理空间属性数据,用DBLE AR N 法来处理非空间属性数据。
DBLE AR N 的实质就是从非空间属性数据中挖掘出有用的信息和知识,根据学习要求,首先用SQL 查询抽取相关维的一个集合,随后,在属性概念分层的基础上循环地概括维。
空间属性占优法首先利用CLAR ANS 法进行空间聚类,并用启发式算法来确定簇的自然个数,然后利用DB LE ARN 对每个簇进行非空间属性概括,它侧重于发现空间簇的非空间特征。
与空间属性占优法不同,非空间属性占优法侧重于发现存在于非空间数据集中的空间簇。
算法首先使用DBLEAR N 对非空间属性进行概括,在此基础上,运用CLAR ANS 法进行空间聚类。
Ng 与Han 通过对Vancouver 地区住房单元数的聚类研究表明,运用这两种方法来处理空间属性数据,效果十分明显[9]。
3 层次法该法通过对给定的数据对象集按层次进行分解,形成一棵以数据子集为节点的树。
层次法可分为凝聚和分裂两类方法。
运用凝聚法进行聚类时,·42· 上海地质Shanghai Geology 总第88期首先将每个数据对象视为一个簇,然后根据某些准则(例如,两个子簇中心的距离),由低向上,直到所有子簇被合并成为一个簇,或满足某个终止条件。
分裂聚类则相反,该法首先将所有数据对象放在一个簇中,然后按照两个子簇中心距离最小准则,将一个簇分裂为若干个子簇,直至每个对象自成一簇,或达到某个终止条件。
AGNE S(Agglomerative Nesting)和DIANA(Divisive Analysis)是早期的层次聚类方法,前者是一种凝聚的层次聚类方法,后者是一种分裂的层次聚类方法,两者都使用简单的准则即根据各簇间距离度量来合并或分裂簇。
由于这两种方法在选择合并或分裂点时有一定困难,并且所进行的合并或分裂的步骤不能被撤消,簇之间也不能交换对象,就会导致发现错误的簇而降低聚类质量。
同时,这种方法没有很好的可伸缩性。
因此,人们在对这两种方法概括和总结的基础上,提出了一些新的层次聚类算法,如BIRC H(Balanced Iterative Reducing and Clustering Using Hierarchies)法,CURE(Clustering Using Representatives)法和C HAMELE ON法。
BIRC H[11]法是一种综合的层次聚类法,聚类过程中,首先运用CF树将数据对象压缩为许多子簇,然后用划分法来提高聚类精度。
此法适合对大型数据库中数据的处理,尤其是空间数据库,其主要原因在于它采用了一种多阶段聚类技术,即扫描一次数据集合就可以产生一个基本的聚类,多次扫描就可以逐步改善聚类质量。
算法的时间复杂度为O(n)。
实验结果揭示了BIRC H法在所需内存大小、运行时间、聚类质量、稳定性和伸缩性方面都胜于CLARANS法和K-均值法[13]。
然而,由于C F树的每个节点只能包含有限数目的子簇,因此一个CF 树的节点并不总对应于用户所认为的一个自然簇,且由于BIRCH法定义了子簇直径的概念,因而对非球形簇情形的聚类效果较差。
CURE[12]法和CHAMELE ON[13]法利用较为复杂的准则进行合并或分裂簇,极大地提高了聚类的准确性。