距离邻近与自然邻近典型聚类方法比较

论文摘要

空间聚类（spatial clustering）是空间数据挖掘和知识发现（SDMKD, Spatial Data Mining and Knowledge Discovery）领域中一个极其重要的研究方向,以数学建模提取空间特征模式为前提,采用指定的相似性测度来计算空间实体之间的邻近程度,进而解译与评估空间实体分布的聚集性。针对复杂空间目标几何形体的直接聚类,是空间聚类区别于传统聚类分析的标志。然而空间实体形状的多样性和位置的随机性,使得几何要素之间的相似性难以定义和计算,导致空间聚类分析的应用较为局限。目前,多数商业空间数据库系统所支持的聚类分析算法是采用欧氏距离（Euclidean）、曼哈坦距离（Manhattan）、马氏距离（Mahalanobis）等作为聚类统计量,既缺乏点、线、面等复杂形状的正确表达,也难以计算要素之间的邻近程度,最终导致算法难以自适应地发现任意形状的簇类,特别是在处理有障碍物约束的聚类时,传统基于距离邻近的聚类算法就无法实施。结合实验分析,造成以上缺陷的根本原因来自距离度量的局限,主要表现在以下两方面：（1）基础理论方面,距离邻近的计算模型与人类的空间认知习惯有明显的差距,理想化的距离定义难以描述实际空间的复杂分布；（2）实际应用方面,距离邻近计算模型忽略了实际应用所依托的客观环境,缺乏空间障碍物的识别与处理的能力,降低了聚类结果的准确性和可解释性,进而限制了实际应用。基于Voronoi图所定义的自然邻近（natural adjacency）空间关系能够有效地克服距离邻近的不足,为空间数据聚类提供了一种有效的度量途径。本文以实现二维空间几何数据聚类为目标,首先采用距离邻近测度,基于改进的树ART2神经网络,实现了空间带状分布数据点的聚类；然后进一步考虑到空间数据的复杂几何属性和障碍物阻隔,引入自然邻近测度,借助Voronoi多边形的直接邻近表达和优化面积阈值计算,提出自然邻近空间聚类算法（SCBNA, Spatial Clustering Base on Natural Adjacency）;最终结合实际应用,对距离邻近和自然邻近的聚类方法进行了比较。同时,为了有效地提取Voronoi邻近关系,文中提出了基于栅格数据的变速Voronoi图构建算法和基于矢量数据的全要素Voronoi图生成方法,并对算法的复杂度和收敛性进行了分析。论文的主要内容及成果分述为以下三点：（1）经典ART2神经网络采用向量的相位信息作为相似性测度以实施聚类,具有伸缩性好、结构相对简单、识别能力强等特点。但其作用于二维空间数据,不仅存在模式漂移和向量幅度信息缺失的问题,而且网络不能自适应地以不同粒度划分空间,难以适应不规则形态分布的空间数据聚类。本文提出了树ART2（TART2, Tree-ART2）网络模型,通过长期记忆模式（LTM, Long Time Memory）的调整和向量幅度信息的学习,该网络保持了带空间欧氏距离约束的旧模式记忆,并引入树结构优化,降低了警戒参数设置的主观要求和模式交混现象的发生。对比实验结果表明,更适用于带状分布的空间数据聚类,具有较高的可塑性和自适应性,是一种典型的距离邻近聚类方法。（2）结合实际考虑,河流、湖泊、公园、铁路等障碍物的存在破坏了空间的连续性,以距离邻近的聚类方法不能准确表达空间障碍物的复杂几何形体,且难以正确定义离散待聚类实体的空间邻近关系。本文引入自然邻近计算方法,以两个相离空间目标是否共享Voronoi边来判断邻近关系,提出了一种带障碍物约束的聚类方法——SCBNA,通过构建全要素Voronoi图,采用自然邻近测度准确表达空间实体间的相对位置,优化分析面积阈值以划分数据归属,算法无需自定义参数,能够发现任意形态且密度渐变的簇,可以精确识别带障碍物约束的空间集群目标,提升了聚类的准确性和自适应性。（3）以考查生长源的生长过程为出发点,通过置换权重常数为权重函数,使生长速度描述为权重距离的时间导数形式,提出一种新的Voronoi图-变速Voronoi图,其核心思想是顾及数字高程模型的高程变化并以形态学膨胀操作为基础,用高程的变化建立权重函数及依据时间消耗的膨胀过程收敛。在表达势力范围及Voronoi邻近关系计算方面,变速Voronoi图具有更佳的实际应用价值与意义。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 问题的提出
• 1.1.1 聚类分析的关键理论与方法
• 1.1.2 聚类分析作用于空间数据的局限性
• 1.1.3 几种常见的距离定义
• 1.1.4 简单距离邻近与复杂空间邻近之间的矛盾
• 1.2 空间邻近关系的概述与表达
• 1.2.1 空间邻近关系的提出
• 1.2.2 空间邻近关系的表达
• 1.2.3 空间邻近关系的计算
• 1.3 国内外相关问题研究现状及分析
• 1.3.1 空间聚类算法研究
• 1.3.2 Voronoi图的生成算法研究
• 1.3.3 自然邻近关系的应用与研究
• 1.4 本文研究内容及章节安排
• 第二章 支持二维空间聚类的树ART2模型构建方法
• 2.1 自适应共振理论
• 2.1.1 竞争学习的相关概念
• 2.1.2 ART2神经网络模型的局限性
• 2.2 树ART2神经网络模型
• 2.2.1 TART2模型结构
• 2.2.2 TART2模型聚类算法
• 2.3 实验与分析
• 2.3.1 实验算法
• 2.3.2 实验结果
• 2.4 本章小结
• 第三章 变速Voronoi图及其构建算法
• 3.1 Voronoi图生成方法简介
• 3.1.1 Voronoi图的定义
• 3.1.2 Voronoi图的生成
• 3.2 变速Voronoi图的定义
• 3.3 变速Voronoi图算法
• 3.3.1 w（·）权重函数
• 3.3.2 膨胀过程
• 3.3.3 收敛条件
• 3.4 实验与分析
• 3.4.1 实验结果
• 3.4.2 实验分析
• 3.5 本章小结
• 第四章 自然邻近空间聚类算法
• 4.1 空间聚类的瓶颈分析
• 4.2 空间聚类的自然邻近表达
• 4.3 SCBNA算法的原理
• 4.4 SCBNA算法的提出与构建
• 4.4.1 面积阈值η的选取
• 4.4.2 空间数据聚类过程
• 4.5 实验与分析
• 4.5.1 SCBNA算法实现
• 4.5.2 时间复杂度
• 4.5.3 实验结果
• 4.6 本章小结
• 第五章 距离邻近与自然邻近的聚类方法比较
• 5.1 树ART2模型的距离邻近聚类方法实现
• 5.1.1 网络参数设置
• 5.1.2 实验结果分析
• 5.2 SCBNA的自然邻近聚类方法实现
• 5.2.1 实验演示
• 5.2.2 实验分析
• 5.3 距离邻近与自然邻近的聚类方法比较
• 5.4 本章小结
• 第六章 结论与展望
• 6.1 主要工作
• 6.2 论文创新点
• 6.3 展望
• 致谢
• 参考文献
• 附录A
• 一、攻读硕士学位期间发表的论文目录
• 二、攻读硕士学位期间参与科研项目情况
• 三、攻读硕士学位期间主要获奖情况