recognize空间聚类分析概念与算法

空间聚类概念

空间聚类作为聚类分析的一个研 究方向，是指将空间数据集中的对象分成由相似对象

组成的类。同类中的对象间具有较高 的相似度，而不同类中的对象间差异较大。作为一种

无监督的学习方法，空间聚类不需要 任何先验知识，比如预先定义的类或带类的标号等。

由于空间聚类方法能根据空间对象的 属性对空间对象进行分类划分，其已经被广泛应用在

城市规划、环境监测、地震预报等领 域，发挥着较大的作用。同时，空间聚类也一直都是

空间数据挖掘研究领域中的一个重要 研究分支。目前，己有许多文献资料提出了针对不同

数据类型的多种空间聚类算法，一些 著名的软件，如

WEAK

、

SPSS< /p>

、

SAS

等软件中已经集成

了各种聚类分析软件包。

1

空间数据的复杂性

空间聚类分析的对 象是空间数据。由于空间数据具有空间实体的位置、大小、形状、

方位及几何拓扑关系等 信息，使得空间数据的存储结构和表现形式比传统事务型数据更为

复杂，空间数据的复杂 特性表现：

(1)

空间属性间的非线 性关系。由于空问数据中蕴含着复杂的拓扑关系，因此，空间属

性间呈现出一种非线性关 系。这种非线性关系不仅是空间数据挖掘中需要进一步研究的问

题，也是空问聚类所面临 的难点之一。

(2)

空间数据的尺度 特征。空间数据的尺度特征足指在不同的层次上，空间数据所表现

出来的特征和规律都不 尽相同。虽然在空间信息的概化和细化过程中可以利用此特征发现

整体和局部的不同特点 ，但对空间聚类任务来说，实际上是增加了空间聚类的难度。

(3)

间信息的模糊性。空间信息的模糊性足指各种类型的窄 问信息中，包含大量的模

糊信息，如空问位置、

间关系的模糊性，这种特性最终会导致空间聚类结果的不确定性。

(4)

空间数据的高维度。空问数据的高维度性是指空间数据的属性

(

包括空间属性和非

空间属性

)

个数迅速增加，

比如在遥感领域，

获取的空间数据的维度已经快速增加到几十甚

至上百个，这会给空间聚类的研究 增加很大的困难。

2

空间聚类算法

目前，研究人员已经对 空间聚类问题进行了较为深入的研究，提出了多种算法。根据

空间聚类采用的不同思想， 空间聚类算法主要可归纳为以下几种：基于划分的聚类算法、

基于层次的聚类算法、基于 密度的聚类算法、基于网格的聚类算法、基于模型的聚类算法

以及其它形式的聚类算法， 如图

l

所示。

(1)

基于划分的聚类

基于划分的聚类方法是最早出现并被经常使用的经典聚类算法。其基本思想是：在给

< br>定的数据集随机抽取

n

个元组作为

n

个聚类的初始中心点，然后通过不断计算其它数据与这

几个 中心点的距离

(

比如欧几里得距离

)< /p>

，将每个元组划分到其距离最近的分组中，从而完

成聚类的划分。 由于基于划分的聚类方法比较容易理解，且易实现，目前其已被广泛的弓

l

入到空间聚类中，用于空间数据的分类。其中最为常用的几种算法是：

k

一平均

(k-means)

算法、

kl

中心点

(k

—

medoids)

算法和

EM(expec tation maximization)

算法。

k

一平均算法

’使

用每 个聚类中所有对象的平均值作为该聚类的中心；

k

一中心点算法

I

贝

0

选用簇中位置最

中心的对象作为聚类中心；而

EM

算法“’则采用一个平均概率分布和一个

d

×

d

协方差矩

阵来表示一个 聚类。除上述

3

种算法外，也出现了众多的基于上述算法的变异 算法，如基

于选择的方法

(CLARA)

、基于随机搜索的方法

(cLARANs)

等。

(2)

基于层次的聚类

基于层次的聚类方法就是将数据对象组成一棵聚类的树。根据层次的分解方向，分为

凝聚法和分裂法。凝聚法最初假定数据集中的每个对象都为一个单独的类，然后通过不

断合并相近的对象，直到满足条件为止；分裂法同凝聚法的分解方向 相反，其开始假

设所有的对象都在一个类中，之后不断进行分裂，直到满足条件为止。由 于一个类一旦分

裂或凝聚就不能撤消，因此基于层次的算法的灵活性较差，故很少有纯粹 的层次算法，层

次方法往往和其它方法相结合进行聚类。

代表性 算法有：

CURE

算法、

CHAMEL EON

算法。

CURE(clustering using representatives)

算法

是一种新颖的层次算法，

它采取随机取样和划分

相结合的方 法：一个随机样本首先被划分，每个划分被局部聚类，最后把每个划分中产生

的聚类结果 用层次聚类的方法进行聚类。较好的解决了偏好球形和相似大小的问题，在处

理孤立点时 也更加健壮。

CHAMELEON(hierarchical clustering using dynamic modeling)

算法

的主要思想是首先使用图划分算法将数据对象聚类为大量相对较小的子类，其次使用凝聚

的层次聚类算法反复地合并子类来找到真正的结果类。

CHAMEL EON

算法是在

CURE

等算