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

基于GIS的空间聚类算法研究厍向阳1薛惠锋1李继军1彭文祥21(西北工业大学自动化学院，西安，710072)2(上海交通大学图像处理与模式识别研究所，上海，200030)摘要:面对目前的聚类方法的局限性和空间聚类的特殊性，从基于目标函数聚类的概念出发，以GIS的空间数据管理和空间分析为技术支持，探讨了空间样本间直接可达距离、间接可达距离和可达成本的计算方法。随机选择k个样本作为聚类中心点，以空间样本到各聚类中心点的可达距离为样本划分依据，以空间样本到其聚类中心点的可达成本的总和为聚类目标函数，引入遗传算法，提出一种基于GIS的空间聚类算法。最后，通过实例进行了算法测试。关键词:数据挖掘；聚类算法；地理信息系统(GIS)；遗传算法；中图分类号:TP393.3文献标识码1.引言聚类分析是数据挖掘和知识发现中一项重要内容，它是将物理或抽象的对象,按照对象间的相似性进行区分和分类的过程。聚类所生成的簇是一组数据对象的集合,在同一簇中的对象之间具有较高的相似度,而不同簇间差别较大。聚类分析已经被广泛地应用到模式识别、数据分析、图像处理、市场研究以及服务设施的选址等领域中。目前的聚类方法有：划分方法、层次的方法、基于密度的方法、基于网格的方法和基于模型的方法等[1]。这些聚类方法隐含两个假设：①样本间是可以直达的，一般采用样本间的直线距离来衡量样本间的相似性，忽略了障碍物的约束条件；②所有样本是等权的，也就是所有样本的重要性、代表性是相同的。然而空间数据并不具备这样的假设条件，假如要在一个城市为给定数目的自动提款机（即ATM）选址，可以对城市所有的居民点按照空间位置特征进行聚类，各个簇的中心点即可作为自动提款机位置。在这一聚类过程中，由于城市中的河流、湖泊、高山等障碍物的约束作用，各居民点并非沿着直线，而是沿着一定的道路或网络到达到簇的中心点。各居民点由于总人口不同，它在聚类过程中的重要性是不同的。显然对于空间数据按照目前的聚类方法进行聚类是不基金项目：国家博士后科学基金资助项目（2003034266）作者简介：厍向阳(1968-)，男，陕西周至人，西北工业大学博士生，从事数据挖掘、人工智能、复杂系统建模与仿真等方面研究。E-mail:xiangyangshe@sohu.com符合实际或者是对实际的一种扭曲。文献[2]最早界定了在障碍物约束下的聚类问题(ClusteringwithObstructedDistance,COD),并且提出了COD-CLEARNS算法。COD-CLEARNS算法核心思想：在顾及障碍物约束的条件下计算任意两样本点间的最近距离，将采样技术和PAM相结合来，通过迭代的方法来完成在障碍物约束下的聚类问题。文献[3]以基于密度的算法（DBSCAN）为基础，用多边形表示各种形状、大小的障碍物，并对多边形进行了约简，提出了DBClU0C(Density-BasedClusteringwithObstaclesConstraints)算法。这些算法尽管解决了在障碍物约束下的聚类问题，但存在如下缺陷：①在为数不多的假定障碍物约束下进行空间聚类；②没有考虑空间样本的权重；③相邻空间样本按照直线距离来计算样本间的相似性。这些缺陷使得空间聚类结果与实际仍然存在较大的差距。在现实生活中，人们总是通过修路、架桥、开凿隧道和开通水运或者航线等手段来克服障碍物约束，而人流、物流、信息流总是沿着一定的路线（道路、航线和线路等）流动。空间数据除具有空间属性外，还具有非空间属性及其空间关系属性，具有复杂的数据结构。地理信息系统(GIS)是空间数据采集、管理、分析、建模和可视化的工具[4]。空间数据管理、空间分析是GIS特有的功能。将GIS与聚类算法相结合，它能为聚类算法提供必要的空间数据管理和空间分析的技术支持，使得空间聚类更加符合实际情况。基于以上分析，面对目前的聚类方法的局限性和空间聚类的特殊性，从基于目标函数聚类的概念出发，以GIS的空间数据管理和空间分析为技术支持，探讨了空间样本间直接可达距离、间接可达距离和可达成本的计算方法。随机选择k个样本作为聚类中心点，以空间样本距各聚类中心点的可达距离为样本划分依据，以各空间样本到其聚类中心点的可达成本总和为聚类目标函数，引入遗传算法，提出一种基于GIS的空间聚类算法。最后，通过实例进行...