摘要：相对于传统并行编程模型，Mapreduce编程模型因其具有良好的抽象性，方便的接口与完备的 运行支持库，大大降低了并行计算编程的难度。本文运用Mapreduce编程模型对聚类分析中经典的K-means算法进行并行化实现。同时，针对K-means算法对离群数据样本敏感，以及在无先验知识下其初始聚类中心难以选取的特点，本文提出了一种初始聚类中心优化选取的算法OICP算法，并对其性能（聚类有效性）进行了测试。由于K-means算法迭代的特点，运用Mapreduce进行计算时会有多次迭代，每次迭代Mapper函数都要从HDFS文件系统中读取数据，随后的过程中数据会在集群中洗牌，在海量数据下会造成大量的IO与网络开销，影响聚类速度与计算效率，对此本文提出一种基于均匀概率抽样与上述OICP算法相结合的解决方案,同时对于该方案提出了相应的中间数据合并策略。

关键词 MapReduce；Hadoop；海量数据；K-means；聚类有效性；

毕业设计说明书外文摘要

Title    Research on MapReduce based Big Data K-means Clustering Algorithm                                              

Abstract：Compared to traditional parallel programming models,the MapReduce model has good abstractness,convenient user interfaces and complete run time support library.So it greatly reduced the difficulty of parallel programming. In this paper,we actualize the K-means algorithm using the MapReduce. Moreover,K-means algorithm is sensitive to outlier data,and it’s hard to select initial centers if we don’t have  priori knowledge. To solve the problem mentioned above,we propose an optimal initial-candidate-picking algorithm called OICP,and test it on typical datasets . K-means algorithm has the feature of iteration, and in each process of iteration the mapper shall read the data from HDFS,then the data will shuffle in nodes. It causes big io and network overhead and decreases the efficiency of computing. To solve the promblem,we propose a solution based on probability sampling and OICP algorithm,and the strategy of merging intermediate data is also presented.

Keywords  MapReduce;Hadoop;Big Data;K-means;Cluster validity;

目   次

1  绪论 1

1.1  选题背景 1

1.2  研究现状分析  2

1.2.1 MapReduce研究现状 2

1.2.2基于MapReduce高维数据聚类研究现状 2

1.3  总体技术方案及社会影响  3

1.4  技术方案的经济因素分析  3

1.5  主要工作与创新点  4

2  预备知识与相关技术概述  5

2.1   Hadoop平台概述 5

2.1.1  HDFS 5

2.1.2  HBase与ZooKeeper6

2.2   MapReduce编程模型概述  7

2.3  聚类概述 8

2.3.1 聚类中的度量与相关定义 8

2.3.2 聚类的主要分类 9

2.3.3 聚类有效性评价 11

3    K-means初始中心选取优化方案 13

3.1  K-means算法 13

3.2  改进的UPGMA算法 14

3.3  最大最小距离算法 15

3.4  OICP K-means算法 16

4    基于MapReduce海量数据下K-means优化策略 18

4.1  K-means并行化实现  18

4.2  多样本抽样 18

4.3  多样本处理与中间数据合并策略 19

5  平台搭建与算法测试 20

5.1  利用Cygwin搭建Hadoop运行环境  20

5.2  基于MapReduce 的K-means算法测试  22

5.3  OICP K-means算法测试 23

结论  25

致谢  26

参考文献27

附录A  OICP K-means算法 29

附录B  基于MapReduce 的K-means算法 42

附录C  F-measure实现代码  45

1  绪论