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

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