基于Delaunay三角网的有障碍物聚类算法研究

论文摘要

随着卫星通信与遥感技术的飞速发展,人们获取的空间数据量日益增多。如何高效地从大量的空间数据中提取出有用的信息,对空间数据挖掘技术提出了挑战。空间聚类作为是空间数据挖掘的一种重要方法被广泛应用于空间知识的发现。传统的空间聚类算法通常忽略了障碍物等约束条件,而在现实世界中,地形地貌错综复杂、自然条件各异,为空间聚类带来了困难。研究基于障碍约束的空间聚类算法成为当今空间数据挖掘研究的热点之一。本文对国内外现有的空间聚类算法和障碍约束的空间聚类算法进行了研究与分析。目前基于障碍约束的空间聚类算法大多数是在原有空间聚类算法基础上进行改进而形成的,由于要考虑障碍约束,有些算法受障碍物的大小、形状、数量影响比较大,使聚类精度下降;有些算法则使程序的计算量急剧增加。基于Delaunay三角网的聚类算法具有聚类精度高、用户输入参数少、能发现任意形状簇等优点,代表性的算法是基于Delaunay三角网的AUTOCLUST+障碍聚类算法。但是该算法不能识别密度渐变的簇,且对障碍约束的处理不够灵活,运算量大等缺点。本文针对这些不足,基于Delaunay三角网与AUTOCLUST+的先进思想,提出了一种新的障碍聚类算法-CBDTO算法。该算法将障碍物用一系列障碍三角形表示,这种表示方法不会破坏原三角网的结构,对障碍约束的添加、删除、修改具有较好的灵活性。同时,该算法将Delaunay三角网剖分得到的三角形划分为小三角形、狭长三角形和大三角形,将其作为聚类模型,通过扩展三角形的策略实现空间聚类,使程序的计算量大大减少。经仿真实验,验证了CBDTO算法的有效性。总之,CBDTO算法不但能识别AUTOCLUST+所能识别的簇,而且也能识别AUTOCLUST+不能识别的密度渐变的抽象簇,并且克服了AUTOCLUST+处理障碍约束不灵活、计算量大的缺点。CBDTO算法的研究将为基于空间地形分析的公路选线系统提供有力的算法支持。

论文目录

• 中文摘要
• ABSTRACT
• 第一章 引言
• 1.1 课题研究背景
• 1.2 国内外研究现状
• 1.2.1 空间聚类研究现状
• 1.2.2 基于障碍约束的空间聚类算法研究现状
• 1.3 主要研究内容
• 1.4 论文的组织结构
• 第二章 空间聚类算法
• 2.1 空间聚类
• 2.2 空间聚类算法
• 2.3 几种典型聚类算法的性能比较
• 2.4 空间聚类算法的典型要求
• 2.5 聚类分析中的数据类型
• 2.5.1 数据矩阵
• 2.5.2 相异度矩阵
• 2.6 聚类元素的归属度
• 2.7 本章小结
• 第三章 Delaunay 三角网及生成算法
• 3.1 Voronoi 图的基本概念
• 3.2 生成 Voronoi 图及 Voronoi 图的变形
• 3.3 Delaunay 三角网
• 3.4 Delaunay 三角网生成算法
• 3.5 本章小结
• 第四章 基于 Delaunay 三角网的 CBDTO 算法
• 4.1 基于 Delaunay 三角网的相关聚类算法
• 4.1.1 典型算法介绍
• 4.1.2 算法的比较
• 4.2 CBDT 算法
• 4.2.1 CBDT 算法基本概念
• 4.2.2 CBDT 算法描述
• 4.2.3 CBDT 算法性能分析
• 4.3 CBDTO 算法
• 4.3.1 CBDTO 算法介绍
• 4.3.2 CBDTO 算法基本概念
• 4.3.3 主要的数据结构
• 4.3.4 主要函数
• 4.3.5 CBDTO 算法主要步骤
• 4.3.6 CBDTO 算法性能分析
• 4.4 本章总结
• 第五章 CBDTO 算法的仿真验证
• 5.1 CBDT 算法的验证
• 5.1.1 数据样本
• 5.1.2 实验结果及分析
• 5.2 CBDTO 算法的验证
• 5.2.1 数据样本
• 5.2.2 实验结果及分析
• 5.3 实验总结
• 总结与展望
• 参考文献
• 攻读硕士学位期间的研究成果
• 致谢
• 个人简介