基于高性能计算机并行聚类算法研究

摘要

当今信息化时代,各种以数据形式表达的信息几乎以指数的量级在迅速增长,许多隐含在海量数据中的知识正等待人们去挖掘、去发现.作为数据库研究、开发和应用最活跃的分支,数据挖掘—从大量数据中用非平凡的方法发现有用的知识--有着广泛的应用.但是,数据挖掘面临的是海量数据和极其复杂的运算,而以往的数据挖掘技术主要是基于传统的(串行)计算机系统,尽管人们为了解决运算的时间和空间的复杂性问题花费了大量的精力,却仍然得不到满意的结果.有些数据挖掘方法,即使有并行挖掘的概念,也因缺乏并行运行环境而只能在串行计算机上运行,因而大大降低了挖掘效率.随着网络技术、高性能计算机的发展,对大规模数据的分布式并行处理已成为可能.并行数据挖掘技术的研究成为当前研究热点和今后重点发展的方向,国内外都在进行一些数据挖掘并行算法的研究.上海大学峰值速度达到每秒4500亿次浮点操作的自强2000机群系统为我们开展并行数据挖掘技术的研究提供了良好的基础条件.数据聚类在数据挖掘、模式识别、图象处理和数据压缩等领域有广泛的应用,是数据挖掘的一个重要分支.本文总结了聚类算法的基本模型,选择DBSCAN算法,提出几种适合在高性能机群系统上运行的并行DBSCAN算法,通过实验和比较,分析几种并行DBSCAN算法的优缺点.这些算法都收集在基于自强2000机群系统并行数据挖掘系统中,该系统除了运行算法之外,还实现了数据清洗、数据划分及数据发送(发送到各个处理机上)、参数选择及聚类质量评估等功能.具体而言,本文的工作如下:1)分析基本的聚类算法,对它们的可并行性进行讨论,选择一种聚类性能好,适合并行的聚类算法——DBSCAN算法;2)在串行DBSCAN算法基础上提出三种并行DBSCAN算法,一种是建立在全局数据库上的全局并行DBSCAN算法——PDBSCAN,其他两个是基于数据分区的并行DBSCAN算法——DPDBSCAN和OPDBSCAN;3)分析比较了三种算法的优缺点;4)建立聚类性能评估模型,向用户反馈聚类性能信息,介绍如何指导用户选择相关参数;5)介绍基于机群系统并行数据挖掘系统的结构及功能,并在该系统上实现一个并行聚类算法应用实例.

目录

文摘

英文文摘

原创性声明和本论文使用授权说明

资助

第一部分数据挖掘及并行计算

第一章引言

1.1数据挖掘的定义

1.2数据挖掘过程

1.3并行计算介绍

1.4课题背景

1.5小结

第二部分并行聚类算法研究

第二章聚类算法综述及其可并行性研究

2.1聚类分析定义

2.2聚类算法典型要求

2.3聚类算法简单介绍

2.4小结

第三章DBSCAN算法介绍及性能分析

3.1关于DBSCAN算法

3.2DBSCAN算法优缺点

3.3并行DBSCAN探讨

3.4小结

第四章全局并行DBSCAN算法研究

4.1引言

4.2数据分区

4.3聚类

4.4算法性能分析

4.5性能评估

4.6算法的优缺点

4.7小结

第五章基于数据分区的并行DBSCAN算法

5.1引言

5.2理论依据

5.3数据分区

5.4局部聚类

5.5局部聚类合并

5.6算法的基本框架与主要调用过程的伪代码

5.7算法性能分析

5.8实验和算法性能评估

5.9算法的优缺点

5.10小结

第六章基于数据交叠分区并行DBSCAN算法

6.1引言

6.2交叠分区

6.3局部聚类及其聚类合并

6.4算法有效性讨论

6.5算法的复杂性讨论

6.6算法的基本框架与主要调用过程的伪代码

6.7实验和算法性能评估

6.8算法的优缺点

6.9小结

第三部分算法的性能评估与并行数据挖掘系统

第七章聚类算法性能评估和参数选择

7.1算法性能评估

7.2算法参数的选择

7.3小结

第八章基于“自强2000”并行数据挖掘系统极其并行数据挖掘的典型应用

8.1基于机群系统的并行数据挖掘平台体系结构

8.2并行数据挖掘的一个典型应用

8.3小结

第九章总结与展望

9.1本文总结

9.2下一步工作的展望

参考文献

致谢

攻读硕士学位期间发表论文

论文说明