基于GIS的空间聚类算法研究

1、基于GIS的空间聚类算法研究厍向阳1 薛惠锋1 李继军1 彭文祥21(西北工业大学自动化学院，西安，710072)2(上海交通大学图像处理与模式识别研究所，上海，200030)摘基金项目：国家博士后科学基金资助项目（2003034266）作者简介：厍向阳(1968-)，男，陕西周至人，西北工业大学博士生，从事数据挖掘、人工智能、复杂系统建模与仿真等方面研究。E-mail: xiangyangshe要:面对目前的聚类方法的局限性和空间聚类的特殊性，从基于目标函数聚类的概念出发，以GIS的空间数据管理和空间分析为技术支持，探讨了空间样本间直接可达距离、间接可达距离和可达成本的计算方法。随机选择k个

2、样本作为聚类中心点，以空间样本到各聚类中心点的可达距离为样本划分依据，以空间样本到其聚类中心点的可达成本的总和为聚类目标函数，引入遗传算法，提出一种基于GIS的空间聚类算法。最后，通过实例进行了算法测试。关 键 词:数据挖掘；聚类算法；地理信息系统(GIS)；遗传算法；中图分类号:TP393.3 文献标识码1. 引言聚类分析是数据挖掘和知识发现中一项重要内容，它是将物理或抽象的对象,按照对象间的相似性进行区分和分类的过程。聚类所生成的簇是一组数据对象的集合,在同一簇中的对象之间具有较高的相似度,而不同簇间差别较大。聚类分析已经被广泛地应用到模式识别、数据分析、图像处理、市场研究以及服务设施的选

3、址等领域中。目前的聚类方法有：划分方法、层次的方法、基于密度的方法、基于网格的方法和基于模型的方法等1。这些聚类方法隐含两个假设：样本间是可以直达的，一般采用样本间的直线距离来衡量样本间的相似性，忽略了障碍物的约束条件；所有样本是等权的，也就是所有样本的重要性、代表性是相同的。然而空间数据并不具备这样的假设条件，假如要在一个城市为给定数目的自动提款机（即ATM）选址，可以对城市所有的居民点按照空间位置特征进行聚类，各个簇的中心点即可作为自动提款机位置。在这一聚类过程中，由于城市中的河流、湖泊、高山等障碍物的约束作用，各居民点并非沿着直线，而是沿着一定的道路或网络到达到簇的中心点。各居民点由于总

4、人口不同，它在聚类过程中的重要性是不同的。显然对于空间数据按照目前的聚类方法进行聚类是不符合实际或者是对实际的一种扭曲。文献2最早界定了在障碍物约束下的聚类问题(Clustering with Obstructed Distance, COD),并且提出了COD-CLEARNS算法。COD-CLEARNS算法核心思想：在顾及障碍物约束的条件下计算任意两样本点间的最近距离，将采样技术和PAM相结合来，通过迭代的方法来完成在障碍物约束下的聚类问题。文献3以基于密度的算法（DBSCAN）为基础，用多边形表示各种形状、大小的障碍物，并对多边形进行了约简，提出了DBClU0C(Density-Based

5、 Clustering with Obstacles Constraints)算法。这些算法尽管解决了在障碍物约束下的聚类问题，但存在如下缺陷：在为数不多的假定障碍物约束下进行空间聚类；没有考虑空间样本的权重；相邻空间样本按照直线距离来计算样本间的相似性。这些缺陷使得空间聚类结果与实际仍然存在较大的差距。在现实生活中，人们总是通过修路、架桥、开凿隧道和开通水运或者航线等手段来克服障碍物约束，而人流、物流、信息流总是沿着一定的路线（道路、航线和线路等）流动。空间数据除具有空间属性外，还具有非空间属性及其空间关系属性，具有复杂的数据结构。地理信息系统(GIS)是空间数据采集、管理、分析、建模和可视

6、化的工具4。空间数据管理、空间分析是GIS特有的功能。将GIS与聚类算法相结合，它能为聚类算法提供必要的空间数据管理和空间分析的技术支持，使得空间聚类更加符合实际情况。基于以上分析，面对目前的聚类方法的局限性和空间聚类的特殊性，从基于目标函数聚类的概念出发，以GIS的空间数据管理和空间分析为技术支持，探讨了空间样本间直接可达距离、间接可达距离和可达成本的计算方法。随机选择k个样本作为聚类中心点，以空间样本距各聚类中心点的可达距离为样本划分依据，以各空间样本到其聚类中心点的可达成本总和为聚类目标函数，引入遗传算法，提出一种基于GIS的空间聚类算法。最后，通过实例进行了算法测试。2. 空间数据聚类

7、的基础2.1. 基于目标函数的聚类模型设为待聚类样本的全体（称为论域），为观测样本的特征矢量或模式矢量，对应特征空间中的一个点，为特征矢量的第维特征取值。设为聚类数，为样本数，聚类中心点集，为硬划分矩阵。若按照最近距离进行样本划分，则样本硬划分矩阵计算如下：（1）式中表示样本与中心点之间的欧氏距离。若以类内平方误差和（WGSS）最小化为聚类目标函数，则聚类的目标函数表示为：聚类就是通过分析论域中的个样本所对应模式矢量间的相似性，按照样本间的亲疏关系，在满足（2）式的前提下，将划分成个子集（也称为族），并满足如下条件：2.2. 基于GIS的空间聚类样本表达空间待聚类样本可以抽象为空间上的点和点间

8、的弧段，如图1（a）所示。空间上的点除了具有空间属性外，还具有非空间属性及其空间关系属性（拓扑关系、距离关系和方位关系）。由于空间上的点并非假想的均质平原上的点，而是实际地理空间上的点，必然受到一些障碍物的约束，并通过特定的网络来连接。地理信息系统作为管理和分析空间数据的工具，它按照主题图方法来描述空间对象。对于待聚类的空间样本，可用点、线两个主体图来描述。例如：使用点主题图层表示空间样本点，它的综合属性表如图1（b）所示,表中第二列表示空间样本点的空间属性（如空间坐标等），其余表示空间样本点的非空间属性（如居民点的人口、地价等）。使用线图层表示空间样本点间的空间关系，它的综合属性表如图1（c

9、）所示，第二列表示弧段的空间属性（如构成弧段的所有点的空间坐标对），其余表示弧线段的非空间属性（如弧段长度、起始端点号等）。(a) (b) (c)图1 GIS对空间聚类样本的表达2.3. 可达距离和可达成本的定义障碍物的存在使得空间样本间通过弧段相连接，它们之间的距离并非是两点间的直线距离，而是弧段长度的代数和。样本距各个聚类中心点（从样本点集中选择的一组点）的距离是样本划分的依据，也是聚类质量评价的基础。在空间样本点中，有一些点是直接可达的，如图1（a）中的0和1、0和5、0和4空间样本点之间，另外一些点是借助其它空间点间接可达的，如图1（a）中的1和3、0和2、4和2空间样本点之间。【直接

10、可达距离】直接可达的空间样本点之间所对应的弧段长度称为直接可达距离。空间样本点0和1之间的直接可达距离可由来表示。为了便于计算，特作如下的约定：GIS软件一般可以计算直接可达空间样本点间的弧段长度。按照（4）式的定义可以构造空间样本点直接可达矩阵，它是一个对称矩阵。图1中的空间样本点的直接可达矩阵如表1所示。直接可达矩阵 表1点号点号0123450081.0289.9992.02181.020140.4770.702140.470111.4591.933111.450107.4078.73489.99107.40079.19592.0270.7091.9378.7379.190【间接可达距离】

11、以其它空间点作为传递点而间接可达的空间样本点间的最短路径长度称为间接可达距离。以直接可达距离为基础，使用一些空间样本点或者接点（非空间样本点，而是弧段连接点）作为传递点，来计算间接可达距离。由于选取不同的传递点（即计算路径不同），则路径长度不同。间接可达距离是按照最短路径所计算的弧段长度和，这是符合空间聚类实际的，因为某一个居民点的人到服务中心接受服务一般会选择最短路径到达。以直接可达矩阵为基础使用Dijkstra算法可以计算任意两样本点间的间接可达距离5。任何两个空间样本点间总是可以通达的，也就是说不是直接可达，就是间接可达。空间样本点间直接可达距离和间接可达距离，统称为可达距离。由直接可达

12、距离和间接可达距离可以构成任何两个空间样本点间的可达矩阵，它是一个对称矩阵。图1中的可达距离可以构成如表2所示的可达矩阵。可达矩阵 表2点号点号0123450081.21183.94170.7389.9992.02181.210140.47149.42149.8970.702183.94140.470111.45171.1291.933170.73149.42111.450107.4078.73489.99149.89171.12107.40079.19592.0270.7091.9378.7379.190【可达成本】某一个居民点的人到服务中心接受服务的总成本不仅与可达距离相关，而且与居民点的

13、总人口有关。空间样本点的权重乘以到某一特定空间样本点的可达距离称为该空间样本点到某一特定空间样本点的可达成本，计算公式如下：式中：空间样本点到空间样本点可达成本；样本点的权重；空间样本点和间可达距离。3. 基于GIS的空间聚类算法3.1. 基本思想基于GIS空间技术的空间聚类可以归纳为一个基于目标函数的优化问题。遗传算法是由美国Holland教授于1975年提出的，它是一种基于生物进化论和自然遗传学说的自适应、随机全局优化的并行算法6。具有较强的的鲁棒性，并具有收敛到全局最优的能力，对目标函数既不要求连续，也不要求可微。因而，使用遗传算法解决空间聚类问题具有明显的优势。1.样本划分方法：在待聚

14、类样本集合中，随机选择与聚类数目相同个数的样本点作为聚类中心点，其余待聚类样本点根据距各个聚类中心点的可达距离，划分给最近的中心点，样本划分方法可按（6）进行：（1）式中表示样本与聚类中心点之间的可达距离。2.目标函数：目标函数对应于遗传算法中的适应度函数。所有空间样本点到其聚类中心点的可达成本总和的最小化可以作为空间聚类的目标函数。这样（2）式可改写为：3.染色体编码基于遗传算法聚类的关键是如何将聚类问题的解编码到基因串中67。由（7）式得目标函数与聚类中心点集和样本划分矩阵有关，而划分矩阵又与聚类中心点集相关。因而，使用遗传算法来求解这一聚类问题可以直接对聚类中心点进行编码。若采用自然编码

15、方案，则染色体编码为：其中表示聚类中心点取自样本集中第个样本。3.2. 聚类算法算法：基于GIS的空间聚类算法。输入：聚类数目K，包含n个待聚类样本的空间数据库（点和网络图层）。输出：空间样本划分矩阵和聚类中心点集，使空间样本点间的可达成本总和最小。方法：Step1.设置GA相关参数，包括最大迭代次数、群体大小、交叉概率、变异概率；Step2.群体初始化，按照染色体编码方案对染色体群体进行初始化；Step3.群体评价，对染色体进行解码，获得聚类中心点，基于可达距离对样本集进行划分，采用空间样本点的可达成本总和对染色体群体进行评价；Step4.染色体选择，依据评价结果，选择较优的染色体，进行下一

16、步操作；Step5.染色体交叉；Step6.染色体变异；Step7.染色体保留；Step8.中止条件检验，如果小于最大迭代次数，则转向Step3，否则停止迭代，输出空间样本划分矩阵和聚类中心点集。4. 算法测试为了测试本文提出的聚类算法的有效性，使用Matlab语言编制了相应的计算机程序。以陕西省所辖市县为空间聚类样本点，以陕西省境内的道路网络为空间样本点的联接关系，以各县市总人口为空间样本点的权重。使用地理信息系统ArcGIS8.3软件建立空间信息系统，并将各县市总人口、县市间的直接可达矩阵输出为*.Text文本文件。使用Matlab语言编制相应的计算机程序，读取*.Text文本文件，并计算

17、各县市间的可达矩阵，进行空间聚类分析。最后将聚类结果通过ArcGIS8.3软件进行可视化表达。遗传算法中参数设置：染色体群体大小为30；最大迭代次数为500次；交叉概率为0.7；变异概率为0.05。当聚类数目为5时，染色体群体在223代时达到最优值：，空间聚类结果如图2所示。5. 结束语面对目前的聚类方法的局限性，引入GIS技术来管理和分析空间数据。在此基础上，探讨了空间对象间直接可达距离、间接可达距离和可达成本的计算方法。引入遗传算法，提出一种基于GIS的空间聚类算法。基于GIS的空间聚类使得空间数据的聚类结果更加符合实际情况。图2 基于GIS的空间聚类结果参考文献:1 Jiawei Han

18、, Micheline kamber,范明，孟小峰译数据挖掘概念与技术M北京：机械工业出版社，20012 A K H Tung, J HOU, J Han. Spatial clustering in the presence of obstacleCIn: Proc 2001 Int. Conf. On Data Engineering ICDE (01), 2001,359-3673 邱长春，薛超英，刘海波一种基于障碍约束的空间数据聚类方法J计算机工程与应用，2003 (31): 186-1874 陈述彭，鲁学军，周成虎地理信息导论M北京：科学出版社19995 钱颂迪等运筹学M北京：清华大

19、学出版社19906 李敏强，寇纪淞，林丹等遗传算法的基本理论与应用M北京：科学出版社，20027 高新波模糊聚类分析及其应用M西安：西安电子科技大学出版社，2004The research on the spatial clustering algorithm based on GISShe xiangyang1, Peng wenxiang2, Xue huifeng1, Li jijun11 (College of Automation, Northwest Polytechnic university, Xian, 710072,China)2(Institute of Image Pr

20、ocessing & Pattern Recognition, Shanghai Jiao Tong University, Shanghai, 200030,China)Abstract: Facing the localization of present cluster approach and spatial data particularity, the direct accessibility distance, the indirect accessibility distance and accessibility cost are defined between spatial samples, from cluster concept based on aim function, by the way of GIS