云计算环境下海量数据的并行聚类算法研究

摘要

聚类是数据分析和管理最基础的算法之一，它已经被广泛应用于计算机科学及其相关领域。然而海量数据的出现使得传统的聚类算法受到了极大的挑战，例如聚类算法的可扩展性差、效率低等。目前，以MapReduce为代表的云计算技术越来越受到商业界和学术界的关注，并且MapReduce已经发展成为最流行的海量数据处理模型之一。本文研究云计算环境下海量数据的并行聚类算法，重点是在MapReduce处理模型中对k-means、k-means++和scalable k-means++聚类算法的研究，目的是提高这些聚类算法的可扩展性和效率。论文完成的工作和主要的研究成果如下:
　　在MapReduce并行处理框架下，针对k-means++初始化方法序列化特性导致其可扩展性差并且需要大量MapReduce作业迭代的问题，本文提出了并行可扩展的k-means++聚类算法，它的初始化方法仅需要一次MapReduce作业迭代就可以选出k个中心点，在Map阶段运行标准的k-means++初始化算法，而在Reduce阶段运行加权的k-means++初始化算法。这种方法不仅提高了 k-means++聚类算法在处理海量数据时的效率，而且它被证明是k-means最优聚类结果的O(α2)近似，其中α=8(2+ lnk)。
　　考虑到MapReduce并行处理框架下scalable k-means++聚类算法的初始化方法每次迭代仍然需要启动两个MapReduce作业的缺点，通过Map阶段的过采样技术以及Reduce阶段的修正技术，提出了快速的scalable k-means++聚类算法。它的每次迭代仅需要一个MapReduce作业，节省了大量的I/O成本和时间，提高了scalablek-means++聚类算法的效率。
　　MapReduce环境下的k-means聚类算法在处理海量的倾斜数据时会导致Reduce任务的负载不均衡，使得Reduce任务的运行时间差异较大，整个聚类算法的运行时间变长，严重降低了云计算平台的资源利用率。针对此问题本文提出了基于抽样估计的数据划分方法。该方法采用抽样估计理论对原始数据进行分析处理，并根据提出的C2和CSC划分方法得到较好的数据划分方案，最后把该方案应用于MapReduce k-means聚类算法中，实验结果表明此方法平衡了Reduce任务的负载，缩短了聚类算法的运行时间。

目录

声明

摘要

第1章 绪论

1．1 课题背景及研究意义

1．2 聚类理论

1．2．1 聚类的定义及过程

1．2．2 相似性度量

1．2．3 常用的聚类算法

1．2．4 聚类结果检验

1．3 国内外研究现状

1．4 主要研究内容

第2章 云计算环境下海量数据聚类的相关技术

2．1 云计算

2．1．1 云计算概述

2．1．2 云计算关键技术

2．2 MapReduce介绍

2．2．1 MapReduce编程模型及运行原理

2．2．2 Hadoop MapReduce实现

2．3 k-means聚类算法

2．3．1 k-means算法概述

2．3．2 k-means算法存在的问题

2．3．3 k-means的MapReduce实现

2．4 k-means++和scalable k-means++

2．5 本章小结

第3章 并行可扩展的k-means++聚类算法

3．1 引言

3．2 并行可扩展的k-means++聚类算法

3．2．1 PSKMI算法实现

3．2．2 PSKM++理论分析

3．2．3 PSKMI算法的优化

3．3 实验及结果分析

3．3．1 实验环境设置

3．3．2 实验结果及分析

3．4 本章小节

第4章 快速的scalable k-means++聚类算法

4．1 引言

4．2 快速的scalable k-means++聚类算法

4．2．1 MRSKMI实现

4．2．2 过采样修正方法

4．2．3 优化策略

4．3 实验及结果分析

4．3．1 实验环境设置

4．3．2 实验结果及分析

4．4 本章小结

第5章 基于抽样估计的数据划分方法

5．1 引言

5．2 同步MaD和Reduce

5．3 解决方法概述

5．4 抽样

5．5 数据划分方法

5．5．1 簇组合

5．5．2 簇分割组合

5．6 应用

5．7 实验及结果分析

5．7．1 实验环境设置

5．7．2 实验结果及分析

5．8 本章小结

第6章 总结与展望

6．1 工作总结

6．2 研究展望

参考文献

攻读学位期间公开发表论文

致谢

作者简介