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

基于GIS的空间聚类算法研究 厍向阳1 薛惠锋1 李继军1 彭文祥2 1(西北工业大学自动化学院，西安，710072) 2(上海交通大学图像处理与模式识别研究所，上海，202330) 摘基金项目：国家博士后科学基金资助项目〔2023034266〕 作者简介：厍向阳(1968-)，男，陕西周至人，西北工业大学博士生，从事数据挖掘、人工智能、复杂系统建模与仿真等方面研究。E-mail: xiangyangshe@sohu 要:面对目前的聚类方法的局限性和空间聚类的特殊性，从基于目标函数聚类的概念出发，以GIS的空间数据管理和空间分析为技术支持，探讨了空间样本间直接可达距离、间接可达距离和可达本钱的计算方法。随机选择k个样本作为聚类中心点，以空间样本到各聚类中心点的可达距离为样本划分依据，以空间样本到其聚类中心点的可达本钱的总和为聚类目标函数，引入遗传算法，提出一种基于GIS的空间聚类算法。最后，通过实例进行了算法测试。 关 键 词:数据挖掘；聚类算法；地理信息系统(GIS)；遗传算法； 中图分类号:TP393.3 文献标识码 1. 引言 聚类分析是数据挖掘和知识发现中一项重要内容，它是将物理或抽象的对象,按照对象间的相似性进行区分和分类的过程。聚类所生成的簇是一组数据对象的集合,在同一簇中的对象之间具有较高的相似度,而不同簇间差异较大。聚类分析已经被广泛地应用到模式识别、数据分析、图像处理、市场研究以及效劳设施的选址等领域中。目前的聚类方法有：划分方法、层次的方法、基于密度的方法、基于网格的方法和基于模型的方法等[1]。这些聚类方法隐含两个假设：①样本间是可以直达的，一般采用样本间的直线距离来衡量样本间的相似性，忽略了障碍物的约束条件；②所有样本是等权的，也就是所有样本的重要性、代表性是相同的。然而空间数据并不具备这样的假设条件，假设要在一个城市为给定数目的自动提款机〔即ATM〕选址，可以对城市所有的居民点按照空间位置特征进行聚类，各个簇的中心点即可作为自动提款机位置。在这一聚类过程中，由于城市中的河流、湖泊、高山等障碍物的约束作用，各居民点并非沿着直线，而是沿着一定的道路或网络到到达簇的中心点。各居民点由于总人口不同，它在聚类过程中的重要性是不同的。显然对于空间数据按照目前的聚类方法进行聚类是不符合实际或者是对实际的一种扭曲。文献[2]最早界定了在障碍物约束下的聚类问题(Clustering with Obstructed Distance, COD),并且提出了COD-CLEARNS算法。COD-CLEARNS算法核心思想：在顾及障碍物约束的条件下计算任意两样本点间的最近距离，将采样技术和PAM相结合来，通过迭代的方法来完成在障碍物约束下的聚类问题。文献[3]以基于密度的算法〔DBSCAN〕为根底，用多边形表示各种形状、大小的障碍物，并对多边形进行了约简，提出了DBClU0C(Density-Based Clustering with Obstacles Constraints)算法。这些算法尽管解决了在障碍物约束下的聚类问题，但存在如下缺陷：①在为数不多的假定障碍物约束下进行空间聚类；②没有考虑空间样本的权重；③相邻空间样本按照直线距离来计算样本间的相似性。这些缺陷使得空间聚类结果与实际仍然存在较大的差距。在现实生活中，人们总是通过修路、架桥、开凿隧道和开通水运或者航线等手段来克服障碍物约束，而人流、物流、信息流总是沿着一定的路线〔道路、航线和线路等〕流动。空间数据除具有空间属性外，还具有非空间属性及其空间关系属性，具有复杂的数据结构。地理信息系统(GIS)是空间数据采集、管理、分析、建模和可视化的工具[4]。空间数据管理、空间分析是GIS特有的功能。将GIS与聚类算法相结合，它能为聚类算法提供必要的空间数据管理和空间分析的技术支持，使得空间聚类更加符合实际情况。基于以上分析，面对目前的聚类方法的局限性和空间聚类的特殊性，从基于目标函数聚类的概念出发，以GIS的空间数据管理和空间分析为技术支持，探讨了空间样本间直接可达距离、间接可达距离和可达本钱的计算方法。随机选择k个样本作为聚类中心点，以空间样本距各聚类中心点的可达距离为样本划分依据，以各空间样本到其聚类中心点的可达本钱总和为聚类目标函数，引入遗传算法，提出一种基于GIS的空间聚类算法。最后，通过实例进行了算法测试。 2. 空间数据聚类的根底 2.1. 基于目标函数的聚类模型 设为待聚类样本的全体〔称为论域〕，为观测样本的特征矢量或模式矢量，对应特征空间中的一个点，为特征矢量的第维特征取值。 设为聚类数，为样本数，聚类中心点集，为硬划分矩阵。假设按照最近距离进行样本划分，那么样本硬划分矩阵计算如下： 〔1〕式中表示样本与中心点之间的欧氏距离。 假设以类内平方误差和〔WGSS〕最小化为聚类目标函数，那么聚类的目标函数表示为： 聚类就是通过分析论域中的个样本所对应模式矢量间的相似性，按照样本间的亲疏关系，在满足〔2〕式的前提下，将划分成个子集〔也称为族〕，并满足如下条件： 2.2. 基于GIS的空间聚类样本表达 空间待聚类样本可以抽象为空间上的点和点间的弧段，如图1〔a〕所示。空间上的点除了具有空间属性外，还具有非空间属性及其空间关系属性〔拓扑关系、距离关系和方位关系〕。由于空间上的点并非假想的均质平原上的点，而是实际地理空间上的点，必然受到一些障碍物的约束，并通过特定的网络来连接。地理信息系统作为管理和分析空间数据的工具，它按照主题图方法来描述空间对象。对于待聚类的空间样本，可用点、线两个主体图来描述。例如：使用点主题图层表示空间样本点，它的综合属性表如图1〔b〕所示,表中第二列表示空间样本点的空间属性〔如空间坐标等〕，其余表示空间样本点的非空间属性〔如居民点的人口、地价等〕。使用线图层表示空间样本点间的空间关系，它的综合属性表如图1〔c〕所示，第二列表示弧段的空间属性〔如构成弧段的所有点的空间坐标对〕，其余表示弧线段的非空间属性〔如弧段长度、起始端点号等〕。 (a) (b) (c) 图1 GIS对空间聚类样本的表达 2.3. 可达距离和可达本钱的定义 障碍物的存在使得空间样本间通过弧段相连接，它们之间的距离并非是两点间的直线距离，而是弧段长度的代数和。样本距各个聚类中心点〔从样本点集中选择的一组点〕的距离是样本划分的依据，也是聚类质量评价的根底。 在空间样本点中，有一些点是直接可达的，如图1〔a〕中的0和1、0和5、0和4空间样本点之间，另外一些点是借助其它空间点间接可达的，如图1〔a〕中的1和3、0和2、4和2空间样本点之间。 【直接可达距离】直接可达的空间样本点之间所对应的弧段长度称为直接可达距离。空间样本点0和1之间的直接可达距离可由来表示。为了便于计算，特作如下的约定： GIS软件一般可以计算直接可达空间样本点间的弧段长度。按照〔4〕式的定义可以构造空间样本点直接可达矩阵，它是一个对称矩阵。图1中的空间样本点的直接可达矩阵如表1所示。 直接可达矩阵 表1 点号 点号 0 1 2 3 4 5 0 0 81.02 ∞ ∞ 89.99 92.02 1 81.02 0 140.47 ∞ ∞ 70.70 2 ∞ 140.47 0 111.45 ∞ 91.93 3 ∞ ∞ 111.45 0 107.40 78.73 4 89.99 ∞ ∞ 107.40 0 79.19 5 92.02 70.70 91.93 78.73 79.19 0 【间接可达距离】以其它空间点作为传递点而间接可达的空间样本点间的最短路径长度称为间接可达距离。 以直接可达距离为根底，使用一些空间样本点或者接点〔非空间样本点，而是弧段连接点〕作为传递点，来计算间接可达距离。由于选取不同的传递点〔即计算路径不同〕，那么路径长度不同。间接可达距离是按照最短路径所计算的弧段长度和，这是符合空间聚类实际的，因为某一个居民点的人到效劳中心接受效劳一般会选择最短路径到达。以直接可达矩阵为根底使用Dijkstra算法可以计算任意两样本点间的间接可达距离[5]。任何两个空间样本点间总是可以通达的，也就是说不是直接可达，就是间接可达。空间样本点间直接可达距离和间接可达距离，统称为可达距离。由直接可达距离和间接可达距离可以构成任何两个空间样本点间的可达矩阵，它是一个对称矩阵。图1中的可达距离可以构成如表2所示的可达矩阵。 可达矩阵 表2 点号 点号 0 1 2 3 4 5 0 0 81.21 183.94 170.73 89.99 92.02 1 81.21 0 140.47 149.42 149.89 70.70 2 183.94 140.47 0 111.45 171.12 91.93 3 170.73 149.42 111.45 0 107.40 78.73 4 89.99 149.89 171.12 107.40 0 79.19 5 92.02 70.70 91.93 78.73 79.19 0 【可达本钱】某一个居民点的人到效劳中心接受效劳的总本钱不仅与可达距离相关，而且与居民点的总人口有关。空间样本点的权重乘以到某一特定空间样本点的可达距离称为该空间样本点到某一特定空间样本点的可达本钱，计算公式如下： 式中：――空间样本点到空间样本点可达本钱；――样本点的权重；――空间样本点和间可达距离。 3. 基于GIS的空间聚类算法 3.1. 根本思想 基于GIS空间技术的空间聚类可以归纳为一个基于目标函数的优化问题。遗传算法是由美国Holland教授于1975年提出的，它是一种基于生物进化论和自然遗传学说的自适应、随机全局优化的并行算法[6]。具有较强的的鲁棒性，并具有收敛到全局最优的能力，对目标函数既不要求连续，也不要求可微。因而，使用遗传算法解决空间聚类问题具有明显的优势。 1.样本划分方法：在待聚类样本集合中，随机选择与聚类数目相同个数的样本点作为聚类中心点，其余待聚类样本点根据距各个聚类中心点的可达距离，划分给最近的中心点，样本划分方法可按〔6〕进行： 〔1〕式中表示样本与聚类中心点之间的可达距离。 2.目标函数：目标函数对应于遗传算法中的适应度函数。所有空间样本点到其聚类中心点的可达本钱总和的最小化可以作为空间聚类的目标函数。这样〔2〕式可改写为： 3.染色体编码 基于遗传算法聚类的关键是如何将聚类问题的解编码到基因串中[6][7]。由〔7〕式得目标函数与聚类中心点集和样本划分矩阵有关，而划分矩阵又与聚类中心点集相关。因而，使用遗传算法来求解这一聚类问题可以直接对聚类中心点进行编码。 假设采用自然编码方案，那么染色体编码为： 其中表示聚类中心点取自样本集中第个样本。 3.2. 聚类算法 算法：基于GIS的空间聚类算法。 输入：聚类数目K，包含n个待聚类样本的空间数据库〔点和网络图层〕。 输出：空间样本划分矩阵和聚类中心点集，使空间样本点间的可达本钱总和最小。 方法： Step1.设置GA相关参数，包括最大迭代次数、群体大小、交叉概率、变异概率； Step2.群体初始化，按照染色体编码方案对染色体群体进行初始化； Step3.群体评价，对染色体进行解码，获得聚类中心点，基于可达距离对样本集进行划分，采用空间样本点的可达本钱总和对染色体群体进行评价； Step4.染色体选择，依据评价结果，选择较优的染色体，进行下一步操作； S