一种改进的快速聚类算法及并行化研究

摘要

聚类分析是数据挖掘领域中的一个重要分支，研究数据对象的分类问题，广泛地应用于模式识别、图像处理、市场研究以及生命科学等众多领域，所以对聚类算法的研究具有重要意义。为了解决聚类算法普遍存在的参数难以确定，效率低下，聚类质量较差等问题，本文对基于密度的聚类算法进行了深入的探索性的研究，提出了一个新的快速聚类算法，并将该算法并行实现。主要研究工作及取得的创新性成果有以下几个方面： 本文在LDBSCAN的基础上，提出了一种改进的快速聚类算法GLDBSCAN。改进算法设计了一种新的对数据空间进行划分的网格划分方法，并采用空间索引SP-Tree来组织网格结构，它保存了数据的空间位置信息，并只索引非空网格，不但节省了存储空间还降低了算法的时间复杂性。算法同时提出用网格中心对象来代表网格包含的对象集合进行聚类，从而降低聚类时间和I/O消耗，实现快速聚类。 本文为了进一步提高聚类算法的执行效率及可扩展性，对并行GIDBSCAN算法进行了研究，通过运用SPMD的并行算法设计思想，设计了一种高性能计算集群环境下基于数据交叠分区的并行聚类算法PGLDBSCAN。该并行算法采用了基于对等模型的数据并行策略和基于消息传递的异步通信策略。并行GLDBSCAN能够大幅度提高算法的效率，同时降低算法对内存的较高要求，增强了算法的可扩展性。 本文从理论分析和实验两个方面验证了算法GLDBSCAN及其并行实现PGLDBSCAN的高效性，可用性及可扩展性。

目录

文摘

英文文摘

声明

第一章 引言

1.1研究背景与意义

1.2国内外研究现状

1.3研究内容与思路

1.4论文组织结构

第二章 相关知识的研究

2.1聚类分析

2.1.1主要聚类方法及其研究进展评述

2.1.2基于密度的聚类算法

2.1.3基于网格的聚类算法

2.2空间索引结构分析

2.2.1空间索引概述

2.2.2基于空间划分的空间索引结构SP-Tree

2.3本章小结

第三章 基于网格的局部密度聚类算法GLDBSCAN

3.1 LDBSCAN算法简介

3.2快速聚类算法GLDBSCAN

3.2.1相关定义

3.2.2 GLDBSCAN算法的设计与流程

3.2.3伪代码描述

3.2.4参数设置

3.3算法分析

3.3.1复杂度分析

3.3.2实验分析

3.4本章小结

第四章 改进算法的并行化研究

4.1.并行聚类基础

4.1.1并行聚类现状

4.1.2并行策略

4.1.3通信策略

4.1.4并行算法的性能评价

4.2 GLDBSCAN算法的并行

4.2.1算法并行思想

4.2.2算法并行设计与流程

4.2.3伪代码描述

4.3算法分析

4.3.1复杂度分析

4.3.2实验分析

4.4本章小结

第五章 总结

5.1论文主要工作

5.2下一步工作展望

参考文献

硕士在读期间的研究成果及参与项目

致谢