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

1基于GIS的空间聚类算法研究厍向阳1薛惠锋1李继军1彭文祥21(西北工业大学自动化学院，西安，710072)2(上海交通大学图像处理与模式识别研究所，上海，200030)摘要:面对目前的聚类方法的局限性和空间聚类的特殊性，从基于目标函数聚类的概念出发，以GIS的空间数据管理和空间分析为技术支持，探讨了空间样本间直接可达距离、间接可达距离和可达成本的计算方法。随机选择k个样本作为聚类中心点，以空间样本到各聚类中心点的可达距离为样本划分依据，以空间样本到其聚类中心点的可达成本的总和为聚类目标函数，引入遗传算法，提出一种基于GIS的空间聚类算法。最后，通过实例进行了算法测试。关键词:数据挖掘；聚类算法；地理信息系统(GIS)；遗传算法；中图分类号:TP393.3文献标识码1.引言聚类分析是数据挖掘和知识发现中一项重要内容，它是将物理或抽象的对象,按照对象间的相似性进行区分和分类的过程。聚类所生成的簇是一组数据对象的集合,在同一簇中的对象之间具有较高的相似度,而不同簇间差别较大。聚类分析已经被广泛地应用到模式识别、数据分析、图像处理、市场研究以及服务设施的选址等领域中。目前的聚类方法有：划分方法、层次的方法、基于密度的方法、基于网格的方法和基于模型的方法等[1]。这些聚类方法隐含两个假设：①样本间是可以直达的，一般采用样本间的直线距离来衡量样本间的相似性，忽略了障碍物的约束条件；②所有样本是等权的，也就是所有样本的重要性、代表性是相同的。然而空间数据并不具备这样的假设条件，假如要在一个城市为给定数目的自动提款机（即ATM）选址，可以对城市所有的居民点按照空间位置特征进行聚类，各个簇的中心点即可作为自动提款机位置。在这一聚类过程中，由于城市中的河流、湖泊、高山等障碍物的约束作用，各居民点并非沿着直线，而是沿着一定的道路或网络到达到簇的中心点。各居民点由于总人口不同，它在聚类过程中的重要性是不同的。显然对于空间数据按照目前的聚类方法进行聚类是不符合实际或者是对实际的一种扭曲。文献[2]最早界定了在障碍物约束下的聚类问题(ClusteringwithObstructedDistance,COD),并且提出了COD-CLEARNS算法。COD-CLEARNS算法核心思想：在顾及障碍物约束的条件下计算任意两样本点间的最近距离，将采样技术和PAM相结合来，通过迭代的方法来完成在障碍物约束下的聚类问题。文献[3]以基于密度的算法（DBSCAN）为基础，用多边形表示各种形状、大小的障碍物，并对多边形进行了约简，提出了DBClU0C(Density-BasedClusteringwithObstaclesConstraints)算法。这些算法尽管解决了在障碍物约束下的聚类问题，但存在如下缺陷：①在为数不多的假定障碍物约束下进行空间聚类；②没有考虑空间样本的权重；③相邻空间样本按照直线距离来计算样本间的相似性。这些缺陷使得空间聚类结果与实际仍然存在较大的差距。在现实生活中，人们总是通过修路、架桥、开凿隧道和开通水运或者航线等手段来克服障碍物约束，而人流、物流、信息流总是沿着一定的路线（道路、航线和线路等）流动。空间数据除具有空间属性外，还具有非空间属性及其空间关系属性，具有复杂的数据结构。地理信息系统(GIS)是空间数据采集、管理、分析、建模和可视化的工具[4]。空间数据管理、空间分析是GIS特有的功能。将GIS与聚类算法相结合，它能为聚类算法提供必要的空间数据管理和空间分析的技术支持，使得空间聚类更加符合实际情况。基于以上分析，面对目前的聚类方法的局限性和空间聚类的特殊性，从基于目标函数聚类的概念出发，以GIS的空间数据管理和空间分析为技术支持，探讨了空间样本间直接可达距离、间接可达距离基金项目：国家博士后科学基金资助项目（2003034266）作者简介：厍向阳(1968-)，男，陕西周至人，西北工业大学博士生，从事数据挖掘、人工智能、复杂系统建模与仿真等方面研究。E-mail:[e-mail]2和可达成本的计算方法。随机选择k个样本作为聚类中心点，以空间样本距各聚类中心点的可达距离为样本划分依据，以各空间样本到其聚类中心点的可达成本总和为聚类目标函数，引入遗传算法，提出一种基于GIS的空间聚类算法。最后，通过实例进行了算法测试。2.空间数据聚类的基础2.1.基于目标函数的聚类模型设snRxxxX,,,21为待聚类样本的全体（称为论域），sTkskkkRxxxx),,(21为观测样本kx的特征矢量或模式矢量，对应特征空间中的一个点，kjx为特征矢量kx的第j维特征取值。设c为聚类数，n为样本数，聚类中心点集XPRppppsc且,,,,21，ncikU为硬划分矩阵。若按照最近距离进行样本划分，则样本硬划分矩阵计算如下：）（其它1),,2,1();,,2,1(0,,,min121cinkddddukpkpkpkpikci（1）式中kpid表示样本kx与中心点ip之间的欧氏距离。若以类内平方误差和（WGSS）最小化为聚类目标函数，则聚类的目标函数表示为：)2()(min),(112nkcikpikidPUf聚类就是通过分析论域X中的n个样本所对应模式矢量间的相似性，按照样本间的亲疏关系，在满足（2）式的前提下，将nxxx21,划分成c个子集（也称为族）cXXX,,21，并满足如下条件：)3(1,,1,21ciXXXcjiXXXXXXiijin2.2.基于GIS的空间聚类样本表达空间待聚类样本可以抽象为空间上的点和点间的弧段，如图1（a）所示。空间上的点除了具有空间属性外，还具有非空间属性及其空间关系属性（拓扑关系、距离关系和方位关系）。由于空间上的点并非假想的均质平原上的点，而是实际地理空间上的点，必然受到一些障碍物的约束，并通过特定的网络来连接。地理信息系统作为管理和分析空间数据的工具，它按照主题图方法来描述空间对象。对于待聚类的空间样本，可用点、线两个主体图来描述。例如：使用点主题图层表示空间样本点，它的综合属性表如图1（b）所示,表中第二列表示空间样本点的空间属性（如空间坐标等），其余表示空间样本点的非空间属性（如居民点的人口、地价等）。使用线图层表示空间样本点间的空间关系，它的综合属性表如图1（c）所示，第二列表示弧段的空间属性（如构成弧段的所有点的空间坐标对），其余表示弧线段的非空间属性（如弧段长度、起始端点号等）。32.3.可达距离和可达成本的定义障碍物的存在使得空间样本间通过弧段相连接，它们之间的距离并非是两点间的直线距离，而是弧段长度的代数和。样本距各个聚类中心点（从样本点集中选择的一组点）的距离是样本划分的依据，也是聚类质量评价的基础。在空间样本点中，有一些点是直接可达的，如图1（a）中的0和1、0和5、0和4空间样本点之间，另外一些点是借助其它空间点间接可达的，如图1（a）中的1和3、0和2、4和2空间样本点之间。【直接可达距离】直接可达的空间样本点之间所对应的弧段长度称为直接可达距离。空间样本点0和1之间的直接可达距离可由01d来表示。为了便于计算，特作如下的约定：）（之间间接通达和之间直接通达和＝直40)(jijidjidijijGIS软件一般可以计算直接可达空间样本点间的弧段长度。按照（4）式的定义可以构造空间样本点直接可达矩阵，它是一个对称矩阵。图1中的空间样本点的直接可达矩阵如表1所示。直接可达矩阵表1点号点号0123450081.02∞∞89.9992.02181.020140.47∞∞70.702∞140.470111.45∞91.933∞∞111.450107.4078.73489.99∞∞107.40079.19592.0270.7091.9378.7379.190【间接可达距离】以其它空间点作为传递点而间接可达的空间样本点间的最短路径长度称为间接可达距离。以直接可达距离为基础，使用一些空间样本点或者接点（非空间样本点，而是弧段连接点）作为传递点，来计算间接可达距离。由于选取不同的传递点（即计算路径不同），则路径长度不同。间接可达距离是按照最短路径所计算的弧段长度和，这是符合空间聚类实际的，因为某一个居民点的人到服务中心接受服务一般会选择最短路径到达。以直接可达矩阵为基础使用Dijkstra算法可以计算任意两样本点间的间接可(a)(b)(c)图1GIS对空间聚类样本的表达4达距离[5]。任何两个空间样本点间总是可以通达的，也就是说不是直接可达，就是间接可达。空间样本点间直接可达距离和间接可达距离，统称为可达距离。由直接可达距离和间接可达距离可以构成任何两个空间样本点间的可达矩阵，它是一个对称矩阵。图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【可达成本】某一个居民点的人到服务中心接受服务的总成本不仅与可达距离相关，而且与居民点的总人口有关。空间样本点的权重乘以到某一特定空间样本点的可达距离称为该空间样本点到某一特定空间样本点的可达成本，计算公式如下：)5(ijiijdwCost式中：ijCost――空间样本点i到空间样本点j可达成本；iw――样本点i的权重；ijd――空间样本点i和j间可达距离。3.基于GIS的空间聚类算法3.1.基本思想基于GIS空间技术的空间聚类可以归纳为一个基于目标函数的优化问题。遗传算法是由美国Holland教授于1975年提出的，它是一种基于生物进化论和自然遗传学说的自适应、随机全局优化的并行算法[6]。具有较强的的鲁棒性，并具有收敛到全局最优的能力，对目标函数既不要求连续，也不要求可微。因而，使用遗传算法解决空间聚类问题具有明显的优势。1.样本划分方法：在待聚类样本集合中，随机选择与聚类数目相同个数的样本点作为聚类中心点，其余待聚类样本点根据距各个聚类中心点的可达距离，划分给最近的中心点，样本划分方法可按（6）进行：）（其它6),,2,1();,,2,1(0,,,min121cinkddddukpkpkpkpikci（1）式中kpid表示样本kx与聚类中心点ip之间的可达距离。2.目标函数：目标函数对应于遗传算法中的适应度函数。所有空间样本点到其聚类中心点的可达成本总和的最小化可以作为空间聚类的目标函数。这样（2）式可改写为：)7()(min),(112nkcikpikkidwPUf3.染色体编码5基于遗传算法聚类的关键是如何将聚类问题的解编码到基因串中[6][7]。由（7）式得目标函数与聚类中心点集P和样本划分矩阵U有关，而划分矩阵U又与聚类中心点集P相关。因而，使用遗传算法来求解这一聚类问题可以直接对聚类中心点进行编码。若采用自然编码方案，则染色体编码为：)8(,,,,,21cippppNumNumNumNumb其中)1(nNumNumiipp表示聚类中心点),,2,1(cipi取自样本集中第ipNum个样本。3.2.聚类算法算法：基于GIS的空间聚类算法。输入：聚类数目K，包含n个待聚类样本的空间数据库（点和网络图层）。输出：空间样本划分矩阵U和聚类中心点集P，使空间样本点间的可达成本总和最小。方法：Step1.设置GA相