Hadoop平台下的分布式聚类算法研究与实现

论文摘要

随着互联网的广泛应用,各行各业需要分析处理的数据量飞速增长,甚至达到海量数据的水平。传统的聚类分析算法往往由于物理机器内存不足或效率低而不能满足处理大数据网络数据的需求。分布式计算的出现,为解决以上问题提供了有效途径。但对结构化网络还没有高效的分布式算法进行有效处理。此外分布式k-means聚类算法初始中心点选取的主观性使得聚类结果不稳定,聚类时间长,而改进的分布式k-means聚类算法初始中心点选取的过程比较复杂,时间和空间复杂度比较高。针对以上问题,本文分析了聚类算法方面的国内外研究现状,对SCAN算法、Clique算法及分布式k-means算法的基本原理及优缺点进行研究,并对Hadoop平台的分布式文件系统和分布式框架的特性和运行机制进行深入研究。本文根据Hadoop平台的工作原理,提出两种分布式聚类算法：（1）结构化分布式聚类算法,结合SCAN算法思想,采用MRC理论设计有限MapReduce轮数,控制混洗排序所需时间,利用Map内合并技术对网络流量进行控制,控制内存开销；（2）基于密度的分布式聚类算法,结合分布式k-means算法和Clique算法,利用分布式CLIQUE算法自动快速地确定聚类个数,选取全局初始聚类中心点,利用格密度除去噪声点,。利用模拟生成结构化网络和空间网络在Hadoop集群中进行实验,实验结果表明结构化分布式聚类算法具有良好的加速比与扩展性,基于密度的分布式算法在划分效果和效率方面优于分布式k-means算法,算法对含噪声数据的数据集处理效果更好,具有聚类稳定、准确率高与效率高的特点。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 研究背景和目的
• 1.2 国内外研究现状
• 1.2.1 聚类算法的研究现状
• 1.2.2 分布式聚类算法的研究现状
• 1.3 论文研究内容与方法
• 1.4 论文组织结构
• 第2章 相关技术
• 2.1 网络数据的生成技术
• 2.2 聚类算法
• 2.2.1 聚类算法分类
• 2.2.2 网络结构化聚类算法
• 2.2.3 k-means算法
• 2.2.4 Clique算法
• 2.3 Hadoop相关技术
• 2.3.1 HDFS
• 2.3.2 MapReduce
• 2.4 本章小结
• 第3章 一种结构化分布式聚类算法
• 3.1 SDCA算法设计思想
• 3.2 相关概念
• 3.3 局部网络聚类
• 3.3.1 LNC算法设计思想
• 3.3.2 LNC算法设计
• 3.4 局部结果合并
• 3.4.1 LRM算法设计思想
• 3.4.2 LRM算法设计
• 3.5 最终结果判定
• 3.6 本章小结
• 第4章 一种基于密度的分布式聚类算法
• 4.1 Clique-k-means聚类算法思想
• 4.2 初始中心点的选取
• 4.2.1 GBSA算法设计思想
• 4.2.2 相关概念
• 4.2.3 GBSA算法并行阶段设计
• 4.2.4 GBSA算法串行部分设计
• 4.3 最终中心点的确定
• 4.3.1 DBDA算法设计思想
• 4.3.2 相关概念
• 4.3.3 DBDA算法并行阶段设计
• 4.3.4 DBDA算法串行阶段设计
• 4.4 聚类及结果输出
• 4.5 本章小结
• 第5章 实验设计与分析
• 5.1 实验环境
• 5.1.1 硬件环境
• 5.1.2 软件环境
• 5.1.3 集群拓扑结构
• 5.2 网络结构化分布式聚类算法
• 5.2.1 实验数据
• 5.2.2 实验设计
• 5.2.3 结果与分析
• 5.3 基于密度的分布式聚类算法
• 5.3.1 实验数据
• 5.3.2 实验设计
• 5.3.3 结果与分析
• 5.4 本章小结
• 第6章 总结与展望
• 6.1 工作总结
• 6.2 展望
• 参考文献
• 攻读学位期间发表的论文及参与的科研项目
• 发表的论文
• 致谢