空间数据挖掘中的聚类分析研究

论文摘要

空间聚类分析作为空间数据挖掘中一种非常重要的技术和方法,得到了人们的普遍关注。与分类不同,聚类的目标是在没有任何先验知识的前提下,根据数据的相似性将数据聚合成不同的簇,使得相同簇中的元素尽可能相似,不同簇中的元素差别尽可能大。空间聚类分析作为空间数据挖掘系统中的一个模块,既可以发现隐含在大量空间数据中的聚类规则,也可以作为其他数据挖掘算法的一个预处理步骤,辅助其他的数据挖掘方法发掘出更深层次的知识,从而提高数据挖掘的整体效率和质量。因此,如何提高空间聚类算法的性能,使其在质量和效率上均能有所改进,并在客观世界中满足实际应用的需求,具有重要的研究意义。本文主要对空间聚类分析方法进行研究,主要研究内容如下:（1）介绍了空间聚类的基本理论,描述了聚类的过程,系统地总结了五种具有代表性的空间聚类方法及每种方法的性能和优缺点。（2）根据模拟退火具有寻求全局最优解的特性,本文在介绍模拟退火基本理论的基础上,利用模拟退火基本思想对传统的空间聚类方法——K-means算法进行优化,优化后的方法以概率接受劣解的方式跳出局部极小值,从而为寻求全局的最优解提供了可能。另外,在优化过程中提出并应用了点密度的思想,使得聚类结果不受初始值影响,其执行效率也有所提高。（3）根据三角网的相关特性,本文提出了一种基于三角网断边的空间聚类方法。首先通过构网、断边,来获得空间实体的初始划分;然后利用K-means算法对初始划分的结果做进一步的聚类,得到最终的聚类结果。该方法也是对传统聚类方法的一种改进,不仅聚类结果的质量有所提高,在发现任意形聚类方面也具有一定的优越性。（4）针对现实世界中存在障碍物约束的空间聚类问题,本文提出了一种利用凸包求取障碍距离的方法,并用微聚类技术和定义距离数组的方法对传统的k-中心点算法进行改进,然后以求取的障碍距离为基础,利用改进后的k-中心点算法进行聚类,即可得到顾及障碍物约束的聚类结果。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 空间数据挖掘的概述
• 1.1.1 空间数据挖掘的定义
• 1.1.2 空间数据挖掘的过程
• 1.1.3 空间数据挖掘的知识表示
• 1.1.4 空间数据挖掘的主要方法
• 1.2 空间聚类分析的研究意义
• 1.2.1 空间聚类是空间数据挖掘的重要研究内容
• 1.2.2 空间聚类分析是其他挖掘方法的基础
• 1.3 现有聚类方法存在的主要问题
• 1.4 论文的主要研究内容与组织框架
• 第二章 空间数据挖掘中聚类分析的基本概述
• 2.1 聚类的基本理论
• 2.1.1 聚类的定义
• 2.1.2 聚类分析中常见的数据结构
• 2.1.3 聚类分析中相似性的测度
• 2.1.4 聚类分析中的准则确定
• 2.2 聚类的基本过程
• 2.3 具有代表性的聚类分析方法
• 2.3.1 基于划分的方法（Partitioning Method）
• 2.3.2 基于层次的方法（Hierarchical Method）
• 2.3.3 基于密度的方法（Density-based Method）
• 2.3.4 基于网格的方法（Grid-based method）
• 2.3.5 基于模型的方法（Model-based method）
• 2.4 本章小结
• 第三章 基于模拟退火思想的空间聚类分析
• 3.1 模拟退火的理论概述
• 3.1.1 模拟退火思想的引入
• 3.1.2 高温物理退火的过程和Metropolis准则
• 3.1.3 模拟退火的基本过程
• 3.2 模拟退火思想对空间聚类的模拟
• 3.3 利用模拟退火思想对空间聚类方法的优化
• 3.3.1 K-means算法的基本概述
• 3.3.2 利用模拟退火思想优化的K-means算法
• 3.4 实验与分析
• 3.5 本章小结
• 第四章 基于三角网断边的空间聚类分析
• 4.1 三角网的相关概述
• 4.1.1 三角网的基本概念
• 4.1.2 三角网的构建过程
• 4.1.3 三角网的存储结构
• 4.2 利用三角网断边法对空间实体的初始划分
• 4.2.1 三角网对于空间聚类的参考意义
• 4.2.2 利用三角网断边法进行聚类初始划分的过程
• 4.3 基于三角网断边的空间聚类过程
• 4.4 实验与分析
• 4.5 本章小结
• 第五章 顾及障碍物约束的空间聚类分析
• 5.1 顾及障碍物空间聚类问题的提出与研究现状
• 5.1.1 顾及障碍物空间聚类问题的提出
• 5.1.2 顾及障碍物空间聚类分析的研究现状
• 5.2 顾及障碍物的空间距离
• 5.3 利用凸包求取障碍距离的方法
• 5.3.1 凸包的基本概念
• 5.3.2 利用凸包求取障碍距离的方法
• 5.4 利用改进k-中心点方法顾及障碍物的聚类
• 5.4.1 传统k-中心点算法
• 5.4.2 两点改进措施
• 5.4.3 改进k-中心点算法的实现过程
• 5.5 实验与分析
• 5.6 本章小结
• 第六章 总结与展望
• 6.1 论文总结
• 6.2 今后工作展望
• 参考文献
• 作者简历 攻读硕士学位期间完成的主要工作
• 致谢