空间数据库中基于网格的自适应聚类算法研究

摘要

随着空间数据获取技术的快速发展，空间数据量呈指数级快速增长，造成了“数据丰富，知识贫乏”的现象。如何从大量的、高维的、含有多种不确定性的空间数据中挖掘隐含的、有价值的知识，是一个十分重要的前沿性课题。经过十几年的研究和实践，空间数据挖掘技术已经吸收了许多学科的最新研究成果而形成独具特色的研究分支。空间聚类分析是空间数据挖掘中一个重要的研究方向，在地理信息系统、遥感、生物、医学图像处理、环境研究等领域都有着非常重要的应用价值。 空间聚类分析就是按照某种相似性度量值，对空间数据集中的数据对象进行归类和标识成簇，使得同簇中的对象尽可能相似，而不同簇间的对象彼此不相似。典型的空间聚类算法主要有基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法和基于模型的方法。虽然其中很多算法得到成功应用，但是在某些方面仍然存在一些问题：可伸缩性问题、处理不同类型属性的问题、发现任意形状的问题、对输入顺序的敏感性问题、高维数据的处理问题、算法对输入参数的依赖性问题。针对这些问题，本文提出了一种基于网格的自适应聚类算法 SACBG。 SACBG 算法思路是将高维数据空间划分为等量的超立方体网格，把空间数据映射到相应的网格中，选择密度最大且未聚类过的网格单元为核心单元，围绕核心单元深度遍历其所有的邻接单元，把大于密度阈值的邻接单元合并为一类，如此循环直到所有的网格都被处理过。本算法能够发现任意形状的聚类问题，避免参数的输入问题，有效地解决高维数据的聚类问题。 实验分析结果表明，对于大型、高维空间数据库而言，本算法具有良好的可伸缩性，对输入顺序不敏感，可以发现任意形状的聚类，受“噪声”的影响也不明显。

目录

文摘

英文文摘

声明

第一章绪论

1.1论文的研究背景

1.1.1空间数据挖掘

1.1.2空间聚类分析

1.2国内外研究现状

1.3论文的研究目的

1.4论文的组织结构

第二章空间数据挖掘简介

2.1基本概念

2.2空间数据挖掘的任务

2.3空间数据挖掘的特点

2.4从空间数据库中可发现的知识类型

2.5空间数据挖掘有待研究的问题

2.6空间数据挖掘的研究方向

2.7本章小结

第三章空间聚类分析

3.1空间聚类分析概述

3.2空间聚类算法的分类

3.2.1基于划分的聚类算法

3.2.2基于层次的聚类算法

3.2.3基于密度的聚类算法

3.2.4基于网格的聚类算法

3.2.5基于模型的聚类算法

3.3聚类算法比较

3.4空间数据挖掘对聚类算法的要求

3.5本章小结

第四章基于网格的自适应聚类算法

4.1问题描述

4.2算法思路

4.3算法的数据结构

4.4算法的详细内容

4.4.1算法的详细描述

4.4.2参数大小的选取

4.4.3数据的映射

4.4.4两个参考点间的距离度量

4.4.5算法的实现

4.5算法复杂性分析

4.5.1算法的时间复杂度

4.5.2算法的空间复杂度

4.6本章小结

第五章实验结果及性能分析

5.1聚类质量分析

5.2参数的自适应性分析

5.3可扩展性分析

第六章结论及未来的工作

6.1结论

6.2未来的工作

致谢

攻读硕士学位期间从事的主要科研工作及发表的论文

参考文献