摘 要

随着近年来，互联网服务在功能和规模上的扩展和智能应用的广泛研究与应用，海量的数据也源源不断地产生。数据的分析与处理也逐渐成为了改善效率，提高精确度，预测发展趋势等目标的重要手段。为了解决如何对海量数据进行处理，研究，分析，得到对实际工作有用的信息的问题，数据挖掘的相关研究工作便随之得到重视和发展。

K-Means作为划分聚类的算法，因其简洁和较高的收敛效率，而在数据分析中得到了广泛地使用。但是在传统的单机模式下，易受制于内存，存储空间，效率等方面的限制，无法满足大型数据的处理需求。针对如何在大量的数据中归纳出有用的信息的问题，可以采用并行的方式来运行数据挖掘算法加以解决。

本文借助较为常用的分布式系统基础架构软件Hadoop，分析和研究分布式K-Means算法的原理。在此基础上对于K-Means聚类算法实现了并行化。通过实验对比单机环境和分布式运算下算法效率的差异，表明基于Hadoop的K-Means算法具有可行性，利用分布式架构进行算法的并行化适用于大数据的处理。并衡量不同Map节点数和Reduce节点数对算法执行速度的影响。

关键词：Hadoop；K-Means；聚类分析；云计算

Abstract

In recent years, with the expansion of Internet services in function and scale and the extensive research and application of intelligent applications, a large amount of data has been generated continuously. Data analysis and processing has gradually become an important means to improve efficiency, improve accuracy and predict development trend. In order to solve the problem of how to process, research, analyze and get useful information for practical work, the related research work of data mining will be paid attention to and developed.

As an algorithm of clustering, K-Means is widely used in data analysis because of its simplicity and high convergence efficiency. However, in the traditional stand-alone mode, it is easy to be constrained by the limitations of memory, storage space, efficiency and so on, which can not meet the needs of large-scale data processing. To solve the problem of how to induce useful information from a large number of data, we can run data mining algorithm in parallel.

With the help of Hadoop, a common distributed system infrastructure software, I have conducted the research to analyzes and studies the principle of distributed K-Means algorithm. On this basis, K-Means clustering algorithm is parallelized. The experiment results show that K-Means algorithm based on Hadoop is feasible by comparing the algorithm efficiency between single machine environment and distributed computing. The parallel algorithm based on distributed architecture is suitable for big data processing. The influence of the number of map nodes and reduce nodes on the execution speed of the algorithm is measured.

Key Words：Hadoop；K-Means；cluster analysis；cloud computing

目 录

第1章 绪论 1

1.1 研究背景与意义 1

1.2 国内外发展现状 1

1.3 论文研究内容 3

1.4 论文组织结构 3

第2章 相关技术介绍 4

2.1 云计算 4

2.1.1 云计算概念 4

2.1.2 云计算的特点 4

2.2 Hadoop平台 5

2.2.1 Hadoop架构描述 5

2.2.2 HDFS分布式文件系统 6

2.2.3 MapReduce架构模型 7

2.3数据挖掘及聚类分析 8

2.3.1 数据挖掘技术 8

2.3.2 聚类分析 9

第3章 K-Means聚类算法研究 10

3.1 K-Means算法 10

3.1.1 算法思想 10

3.1.1 算法流程 11

3.1.3 算法分析 12

3.2 分布式的K-Means算法 13

3.2.1 算法思想 13

3.2.2 初始划分 14

3.2.3 迭代过程 15

第4章 实验与分析 17

4.1 实验平台搭建 17

4.1.1 实验环境 17

4.1.2 Hadoop配置 18

4.2 实验结果与分析 18

4.2.1 实验数据 18

4.2.1 实验分析 19

第5章 结论 24

参考文献 25

致谢 27

第1章 绪论

1.1 研究背景与意义

进入二十一世纪以来，互联网成为了发展最为迅猛的产业之一获得了高速发展。随之不断增长的还有海量的数据。根据预测，2020全年，全球产生数据总量可达50.5ZB，相较2010年的1.2ZB增长了超过40倍，且至今依然维持着每年超过20%的高增长态势。通常信息转化为价值，要经历信息、数据、知识、价值四个层面，我们目前仍处于信息量巨大而“知识”匮乏的状态。为了解决如何对海量数据进行处理，研究，分析，得到对实际工作有用的信息的问题，数据挖掘的相关研究工作便随之得到重视和发展。数据挖掘所做的便是采用科学的手段是从数据中发现隐藏的知识，发现潜在的规律。 数据挖掘是一种使用广泛地决策支持过程，广泛地应用于AI、机器学习、统计、数据库等方向的研究^[1]。通过数据挖掘，自动的，高效的地分析企业数据，进行推理和归纳，在数据中提取对企业发展有益的信息，以此做到适时地调整市场策略，降低风险。数据挖掘的应用广泛，包括医疗卫生、金融、保险业、电子商务和市场营销等多个领域，并取得了很好的效果。

在数据挖掘中，聚类分析经常被用来作为预处理的手段，辅助其他挖掘算法的开展。 它可以预先对数据进行一定的处理，比如标准化数据，精简数据集等。以便进一步的分析和研究。很多时候，聚类分析也作为单独的算法开展工作。 k均值聚类算法作为一种通过多次迭代，减少误差进行求解的层次聚类分析算法，具有简洁以及效率高等特点。