随着GIS技术的发展, 越来越多的行业开始引入GIS概念, GIS的应用逐渐深入到人们的生产和生活中。计算机数据库技术(DBMS)、计算机辅助设计(CAD)、计算机辅助制图(CAM)、计算机图形学(computer graphics)的发展对GIS的进步起着强烈的支持作用。

空间分析作为地理信息系统的主要功能特征, 也是评价一个地理信息系统成功与否的主要指标。它基于地理对象的位置和形态的空间数据分析技术, 目的在于提取和传输空间信息(郭仁忠, 2001)。根据空间分析作用数据性质的不同, 一般把空间分析分为基于空间图形数据的分析运算、基于非空间属性的数据运算、空间和非空间数据的联合运算(汤国安, 2002)。

空间分析的方法有很多种, 其中空间聚类是最常用的一种, 它是基于空间图形数据进行空间信息提取的一种空间分析方法。所谓空间聚类, 就是将一组空间对象划分为一定数目的有意义的簇, 使得同一簇中的对象有较大的相似度, 而属于不同簇的对象差别较大, 即相异度较大(Han et al., 2001)。聚类技术在许多领域得到了广泛应用, 如统计数据分析、模式匹配和图像处理以及商业领域等。大到地球和宇宙观察数据处理, 小到生物基因结构分析, 聚类技术都有其用武之地(戴晓燕等, 2003)。例如, 根据全国各个气象观测点的多维数据, 利用空间聚类技术分析国家各个地区的气候条件, 制定气象分布图; 对国土资源的聚类分析, 可以得到国家的国土资源的分布情况, 对于发展地方经济和加强国家建设都有较强的指导意义; 对不同城市经济发展水平的聚类分析, 可以了解我国经济发展的趋势; 目前, 数字地球、数字城市、数字农业、数字林业等一系列“数字化”工程的提出, 使得空间聚类分析作为地理信息系统的一项基本功能得到了前所未有的重视和应用。

然而, 空间聚类一直是空间分析中一个相对比较困难的问题, 大规模、多维空间数据的聚类尤其突出(邸凯昌, 2001)。许多专家学者从算法本身的角度针对一些应用提出了各种改进或创新的算法(刘夫涛等, 2000; 王美华, 2004), 这些算法的提出很少考虑到计算机实现的难易程度和执行效率问题(田纪春等, 1994), 所以导致一些空间聚类算法虽然在思想上很容易理解, 但实施时却往往碰到了一些难以克服的问题。本文从计算机数据结构的角度来分析一种典型的空间聚类算法——系统聚类, 使之不但在算法上容易理解, 而且在执行时也有较高的效率。

1 系统聚类算法

系统聚类算法是一种被广泛使用的典型空间聚类算法。首先假定每一个空间数据对象自成一类, 然后根据一定的聚类判别准则对最相似的2个类进行合并。随着相似类的合并, 类越来越少, 直至达到所要求的分类数目(李仲来, 1994)。不同的应用所采用的聚类准则也不尽相同, 一般认为点与点之间的空间距离是决定点群集聚特征的最主要的统计量, 只有聚类靠近的点才可以归为同一子群, 因此空间聚类最常用的准则是欧式距离准则。但从聚类本身的含义出发, 同一类中的点应尽可能集中, 不同类的点尽可能分离, 也就是类内的方差尽可能小, 类之间的方差尽可能大, 这就是离差准则(郭仁忠, 2001)。为了叙述的方便, 本文采用欧式最短距离作为聚类的准则, 离差准则的算法设计和欧式距离准则相同。系统聚类的算法可以用下面的步骤表示: 1)设P_i(i =0, 1, …n)为空间数据对象, 每一个数据对象都构成一类G_i (i =0, 1, …n); 2)计算类两两之间的距离D_{i, j}(i =0, 1, …n; j =0, 1, …n; i ≠j), 构成上三角或下三角距离矩阵M; 3)查找距离矩阵M中D_{k, l} = MIN(D_{i, j})(i =0, 1, …n; j =0, 1, …n; i ≠j)的2个类G_k、G_l, 合并这2个类为一新类G_{k, l}; 4)计算新类G_{k, l}与其他类G_i(i =0, 1, …n; i ≠k, i ≠l)的距离, 并刷新聚类矩阵M; 5)重复步骤3), 继续合并距离最近的类, 直到达到所要求的聚类数目。

2 算法实现设计 2.1 算法分析

系统聚类算法的原理简单易懂, 易用计算机程序实现, 但执行效率低下。设计合理的数据结构来优化算法成为系统聚类程序实现的关键问题。

分析系统聚类算法的实现步骤可以得到, 有4个关键点直接影响着程序的执行效率问题: 1)原始数据对象的存贮; 2)原始距离矩阵M的计算; 3)合并新类后距离矩阵M的刷新; 4)新类的存贮。

2.1.1 原始数据对象的存贮

原始数据对象是空间聚类分析的基础, 原始数据对象的存贮结构直接影响着后面聚类算法的简洁程度。另外, 有些数据对象不但包含着空间位置的信息, 而且还有非空间的属性信息, 因此还要使原始数据对象的数据结构有一定的扩展性能。链表结构是程序设计时常用的数据结构形式, 将原始数据对象的数据结构设计成链表的形式, 可以充分发挥链表的可扩展、不需要大量连续内存空间的特点。原始数据链表的节点有代表空间位置信息的x、y、z数据项, 有代表属性信息的指针变量, 还有指明该数据对象索引的变量。该数据结构见表 1。

2.1.2 原始距离矩阵M的计算

距离矩阵仅仅用来存储聚类的统计量, 所以采用最简单的二维矩阵作为其存贮结构。在分配二维矩阵空间时, 将所有的数据初始化为零, 这样在计算统计量时, 仅仅考虑矩阵的上三角或下三角的统计量就够了。该二维矩阵如下。

2.1.3 合并新类后距离矩阵M的刷新

这是算法中的核心步骤, 也是决定算法执行效率、占用系统资源多少的关键环节。该算法实现时, 为了节省内存空间, 所有的矩阵统计量刷新在原始距离矩阵M上实现。假设2个类G_k、G_l合并成一个新类G_{k, l}, 且l大于k, 分别比较距离矩阵M中存贮的D_{k, i}与D_{l, i}(i =0, 1, …n)的大小, 用二者中较小的数据刷新距离矩阵M所对应的l列和l行上, 并将新类的G_{k, l}的索引设定为l, 将矩阵中的k行和k列数据都刷新为零。充分利用已分配的内存空间来进行数据的频繁变换, 不但在空间上节省了很多资源, 而且在时间上也避免了频繁分配和回收空间所造成的时间消耗。下面示意了2个类合并时刷新距离矩阵统计量的过程。

在矩阵a中, 找到D_{3, 4}是最小的统计量(加黑斜体数据), 说明需要将类3和类4合并成一个新类, 此时分别比较D_{1, 3}与D_{1, 4}、D_{2, 3}与D_{2, 4}、D_{3, 5}与D_{4, 5}、D_{3, 6}与D_{4, 6}的大小, 将最小的距离量刷新到列4和行4中(矩阵b中加下划线的数据), 然后将列3和行3的数据刷新为零(矩阵b中加黑斜体数据)。

2.1.4 新类的存贮

新类的存贮仍采用链表的形式, 与原始数据对象存贮结构的不同在于新类的链节点采用二维的存贮方式, 因为每个类链节点不但要含有自身类中所有数据对象的信息, 而且还要有邻接类的信息。对于类中所包含的数据对象的信息, 设计了另外的数据节点来存贮, 该数据节点中仅简单的包含数据对象的索引信息。这样的类数据结构对聚类结果的遍历输出和后期的微调整都较强的适应性。其结构示意图可用图 1表示。

2.2 伪代码算法实现

上文给出了系统聚类算法的详细分析, 并设计了比较优化的几个关键点的数据结构, 下面给出相关的伪代码并作简要的分析。

1) 原始数据对象的数据结构

struct tagData

{int       index;        //原始数据对象索引

double       x, y, z;        //空间位置信息

void^*       prop;}       //属性信息

2) 原始距离矩阵M的定义及初始化

double^**       Matrix;        //定义浮点型的二维矩阵

Matrix =new double^*[RecordCount];        //分配二维矩阵内存空间

for(int i =0; i < RecordCount; i ++)

    Matrix[i] =new double[RecordCount];

for(int i =0; i < RecordCount; i ++)       //初始化二维矩阵

    for(int j =0; j < RecordCount; j ++)

      Matrix[i][j] =0;

该段代码的主要运算量在初始化二维矩阵时, 其时间复杂度为O(n²)。

3) 新类的存贮结构

struct tagSublist       //数据对象节点

{int       index;      //数据对象索引

Sublist^*       pnext;};        //下一节点指针

struct tagClusterlist       //类节点

{int       index;       //类索引

int       count;        //数据对象数

Sublist^*       sublist;        //数据对象指针

Clusterlist^*       pnext;};        //下一节点指针

4) 距离矩阵M的刷新

变量tempClusterlist为指向类链表的头结点的指针变量。

while(tempClusterlist&& tempClusterlist ->index! =Col)

{  int i =tempClusterlist ->index;

    //获得2个要合并的类需要进行比较的距离

    if(i < Row)

    FirstValue = Matrix[i][Row];

      else

    FirstValue = Matrix[Row][i];

      if(i < Col)

    SecondValue=Matrix[i][Col];

      else

    SecondValue=Matrix[Col][i];

tempValue =min(FirstValue, SecondValue);

    //将二者中较小的数据刷新到新类的行和列中

    if(i < Col)

  Matrix[i][Col] =tempValue;

    else

  Matrix[Col][i] =tempValue;

    tempClusterlist =tempClusterlist ->pnext;

}

//将较小的行所有的统计值置为0

for(int k =0; k < m -Recordcount; k ++)

{  if(k < Row)

        Matrix[k][Row] =0;

    else

        Matrix[Row][k] =0;}

这是算法的核心代码部分, 但从代码分析可以看出, 该段代码的时间复杂度也仅仅是O(n), 与参加聚类的数据对象数成正比; 并且在空间上也仅仅只是利用先前分配的内存空间。

3 与其他软件系统聚类模块的比较

目前许多统计分析软件或具有统计分析软件功能的其他软件都具有聚类功能, 如Matlab、SAS等, 但由于各个软件所针对的应用领域不尽相同, 所以存在着这样或那样的缺点, 如Matlab虽然也有系统聚类模块, 但其在选择聚类准则时, 只能使用固定的欧式距离, 这大大地限制了其应用的灵活性(宋兆基等, 2005)。而SAS虽然可以选择多种聚类准则, 但其对数据的输入格式和操作步骤有较严格的要求, 而且运行SAS所需的内存资源消耗也较大。而本文所实现的该算法程序, 从最底层的算法设计来优化程序的执行效率, 不但克服了这些软件的局限性, 而且能够直接对用空间坐标对表达的空间数据(如shape格式文件)进行聚类分析。

图 2是利用该算法程序对速生丰产林部分企业的集群特性进行分析研究的结果示意图, 聚类准则采用欧式距离的最小距离准则, 图中共有1 300多个数据点, 聚为6类, 在P41.6G/256 M的电脑上仅仅耗时2 s左右。同样的数据, 在用Matlab或SAS运算时, 则需要3 s以上才能完成。应用实践证明, 该数据结构有效的提高了系统聚类执行的效率。

4 结论

本文从数据结构、计算机程序设计的角度对系统聚类算法进行了优化分析。利用了较少的内存空间, 程序的时间复杂度与参加聚类数据点的平方成正比, 在文章的最后给出了相应的伪代码实现, 使得这种典型的聚类算法具有更高的执行效率, 加强了系统聚类算法对大量空间数据的处理能力。