基于网格技术的分布式空间数据挖掘算法研究

论文摘要

空间数据挖掘是空间信息技术发展的必然结果,其产生主要来自两个方面的推动力。首先,由于数据挖掘研究领域的不断拓展,由最初的关系数据和事务数据挖掘,发展到对空间数据库的挖掘。其次,在地学领域,随着卫星和遥感技术的广泛应用,日益丰富的空间和非空间数据得到收集和存储,海量的地理数据在一定程度上已经超过了人们的处理能力,而传统的地学分析难以胜任从这些海量数据中提取和发现地学知识,正如John Naisbett所说,“我们已被信息所淹没,但是却正在忍受缺乏知识的煎熬”。因此,从空间数据库中自动地挖掘知识,寻找隐藏在空间数据库中不明确的、隐含的知识、空间关系或其它模式,即空间数据挖掘（Spatial Data Mining,SDM）,变得越来越重要。但是,GIS空间数据库一般都具有海量特性并且往往分布存储,利用SDM技术从空间数据库或数据仓库中获取隐含的知识和信息,如果仅仅采用传统的集中式处理模式,则无论从数据处理的效率还是空间数据本身的安全性方面来说,都提出了很大的挑战。因此,分布式并行数据挖掘处理模式是目前研究的热点问题之一。而空间知识网格技术的研究与发展,为数据挖掘提供了良好的计算环境和应用前景。本文主要从空间数据挖掘中关联规则发现的串行算法入手,探讨了关联规则挖掘算法的并行化处理问题,并对网格技术应用于空间数据挖掘的相关体系结构进行了研究。本文的主要贡献在于:（1）对空间关联规则挖掘算法进行了系统研究。首先重点研究了Apriori算法、FP-growth算法及其对它们的改进,并将这两个算法分别在5个不同大小的数据集上进行了性能测试和对比;然后研究了空间统计学理论在空间数据挖掘领域的应用,并以湖南省2004年到2006年各市州的GDP增长率为例,成功的挖掘了各市州GDP增长率之间的空间关联关系;（2）研究了空间关联规则挖掘算法的并行化处理模式。为了适应GIS空间数据库海量且往往分布存储的特性,本文给出了分布式空间关联规则挖掘算法的一般结构,并基于Apriori算法介绍了4种并行计算方法:CD算法、CD-LGP算法、DD算法和HD算法,并对它们做了算法性能分析;（3）研究了基于网格技术的空间数据挖掘体系结构。在遵循OGSA体系结构的基础上,本文对面向服务的空间数据挖掘体系结构基本特征进行了分析,并对该体系结构中的数据访问服务、数据代理服务及空间数据挖掘服务的实现方式和流程做了深入的研究:（4）研究了网格环境下空间数据划分的一般策略和方法。通过基于GridSim的网格仿真实验,证实了在特定情形下该数据划分策略存在一个最优解,为网格代理在接收用户提交的任务后对整个任务进行自动化分解和在网格中进行优化调度提供了依据。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 课题研究背景和意义
• 1.2 国内外研究现状及发展趋势
• 1.3 本文主要研究内容及思路
• 1.4 论文的总体组织结构
• 1.5 本章小结
• 第2章 空间数据挖掘基础理论与方法
• 2.1 空间数据挖掘的基本概念
• 2.2 空间数据挖掘的一般过程
• 2.3 空间数据挖掘可发现的知识类型
• 2.3.1 空间关联/序列规则
• 2.3.2 空间特征/区分规则
• 2.3.3 空间分类/回归规则
• 2.3.4 空间聚类/函数依赖规则
• 2.3.5 普遍的几何知识
• 2.3.6 空间分布规律
• 2.4 空间数据挖掘的一般方法
• 2.4.1 归纳与演绎的方法
• 2.4.2 空间统计分析方法
• 2.4.3 空间分析的方法
• 2.4.4 Rough集方法
• 2.4.5 地理空间聚类方法
• 2.4.6 空间关联规则分析
• 2.4.7 地理空间分类与预测分析
• 2.4.8 基于云理论的方法
• 2.4.9 异常值分析
• 2.4.10 计算几何方法
• 2.5 空间数据挖掘与其它相关学科的关系
• 2.5.1 SDM与DM
• 2.5.2 SDM与机器学习
• 2.5.3 SDM与地学数据分析
• 2.5.4 SDM与空间数据库
• 2.5.5 SDM与空间数据仓库
• 2.5.6 SDM与数字地球
• 2.6 本章小结
• 第3章 空间关联规则挖掘算法研究
• 3.1 基本概念和理论
• 3.2 Apriori算法及其改进
• 3.2.1 Apriori算法
• 3.2.2 由频繁项集产生关联规则
• 3.2.3 Apriori算法的优化
• 3.2.3.1 数据库事务压缩的方法
• 3.2.3.2 基于采样的方法
• 3.2.3.3 基于数据划分的方法
• 3.3 FP—growth算法
• 3.3.1 FP-tree的建立
• 3.3.2 基于FP-tree挖掘关联规则
• 3.3.3 算法性能比较与分析
• 3.4 基于空间统计学的空间关联规则挖掘
• 3.4.1 空间统计学基本理论和相关性质
• 3.4.1.1 空间权重矩阵
• 3.4.1.2 全局空间自相关测度指标—Moran's I和Geary's C
• 3.4.1.3 局部空间自相关的测度指标—G统计量和LISA
• 3.4.2 实例分析
• 3.5 本章小结
• 第4章 分布式空间关联规则挖掘算法
• 4.1 分布式空间关联规则挖掘算法一般结构
• 4.2 空间关联规则挖掘算法的并行化处理
• 4.2.1 计数分布算法（Count Distribution，CD）
• 4.2.2 CD算法的改进
• 4.2.2.1 相关定义
• 4.2.2.2 局部剪枝
• 4.2.2.3 候选项集的全局剪枝
• 4.2.2.4 节点投票机制
• 4.2.2.5 CD-LGP算法描述
• 4.2.3 数据分布算法（Data Distribution，DD）
• 4.2.4 混合算法（Hybrid Distribution，HD）
• 4.3 算法性能分析
• 4.4 本章小结
• 第5章 基于网格技术的空间数据挖掘研究
• 5.1 空间知识网格
• 5.2 面向服务的空间数据挖掘体系结构
• 5.2.1 基于网格技术的SDM体系结构基本特征
• 5.2.2 数据访问和数据代理服务
• 5.2.2.1 数据访问服务
• 5.2.2.2 数据代理服务
• 5.2.3 空间数据挖掘服务
• 5.2.3.1 集中式空间数据挖掘服务（Centralized Spatial Data Mining Service，CSDMS）
• 5.2.3.2 分布式空间数据挖掘服务（Distributed Spatial Data Mining Service，DSDMS）
• 5.3 基于知识网格的空间数据分解算法
• 5.3.1 数据划分的一般原则
• 5.3.2 空间数据划分的方法
• 5.3.3 网格环境下的空间数据划分策略
• 5.4 基于GridSim的网格仿真实验及结果分析
• 5.4.1 GridSim简介
• 5.4.2 仿真实验及结果分析
• 5.5 基于网格技术的空间数据挖掘应用前景
• 5.6 本章小结
• 第6章 结论与展望
• 6.1 主要研究成果
• 6.2 未来工作展望
• 参考文献
• 致谢
• 攻读硕士学位期间取得的科研成果