1. 研究目的与意义（文献综述）

1背景：随着互联网的高速发展，我们正处于并将长期处于数据爆炸的时代。很难估算全球电子设备中存储的数据总共有多少，国际数据公司（idc）曾经发布报告称，2006年数字世界（digital universe）项目统计得出全球数据总量为0.18zb，1zb等于大家所熟悉的10亿tb，这相当于全球每人一个硬盘中保存的数据总量。纽约证交所每天产生的交易数据多达1tb，facebook存储的照片约为100亿张，存储容量约为1pb，这样的数据“洪流”还有很多。如此庞大的数据集是无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的，这就是所谓的大数据。伴随着数据的急剧增长，对传统的数据挖掘技术提出了新的挑战，尤其是在数据量大到一台主机上无法运算或者运算时间过长的情况下，这时候便需要对传统聚类算法的实现形式做出改进，以满足在大数据环境下进行数据挖掘的需求。并行处理就是一种有效的大数据处理方式，而hadoop下的mapreduce计算模型正是用来做大规模数据集（大于1tb）的并行运算，把对一个大数据集的操作分割成对多个小数据集的操作，最后再把各个小数据集的操作结果合并起来得到最终的结果。

2 目的及意义：在对海量数据进行知识挖掘的时候，为了保证准确度的同时提高算法的效率，我们可以采取并行的方法进行数据运算，由google提出的mapreduce并行计算模型主要是针对海量数据的处理,并极大的简化了并行程序设计。在使用mapreduce进行并行计算开发时, 我们需要将传统算法进行改进使其能够以并行的方式完成计算任务。本次毕业设计的主要内容便是针对经典的k-means聚类算法，使用mapreduce计算模型,在hadoop平台上实现k-means算法的并行化。与此同时，还要研究hadoop集群中节点数对于算法执行效率的影响，通过观察算法执行并记录相关的数据，最后根据相关的统计方法总结出集群中节点对算法执行效率影响的趋势。总之，在海量数据集的知识发现中，特别是在数据量大到单机无法运行的情形下引入并行技术，不仅可以加快数据处理的速度，而且还可以提高数据挖掘处理海量数据的能力，因此对并行聚类算法的实现和研究具有十分重要的意义。

3 研究现状：毫无疑问，任何一种类型的聚类算法都不能普遍的适合所有的数据类型，基于划分等传统聚类算法各有侧重也各有优劣，因而目前也提出了许多新型的聚类算法^[2]，包括基于样本归属关系，基于样本预处理等；针对相对较简单的k-means算法，由于需要的参数包括聚类数k值，样本初始中心点，以及距离度量需要人为指定，k-means算法出现了许多的变种。原始的k-means算法执行时的初始k个中心点是随机的，这导致了算法的稳定性不强，准确度不高，而通过优化初始中心点^[8]，首先，采用一次mapreduce程序，用实现抽样时的最大最小距离法，得到首个聚类的初始中心点。其次，进行k-means的迭代优化初始中心点可以提高算法的稳定性和准确性。然而k-means算法仍然被认定是一个np难优化问题，在多项式时间内，只能得到局部最优解，需要更加严格的数学理论证明。目前对于该算法的研究着重体现在：

2. 研究的基本内容与方案

本次毕业设计主要是在Hadoop集群中实现经典聚类算法k-means算法的并行运算，所以首先是要理解k-means算法，包括算法的功能作用，数据处理，执行流程，以及影响因素等，这些可以通过阅读相关文献以及书籍。随后要学习Hadoop上MapReduce的执行机制，并结合k-means算法，加深理解MapReduce如何使得算法得以并行化(map函数的作用，reduce函数的作用等)，方便为后面设置相关参数（集群节点数，聚类数等）；通过观察和记录相关的数据，并加以整理，统计分析，归纳出相应的结论，并以图表的形式展现出不同参数对于并行化后的算法执行效率的影响程度。本次毕业设计的任务主要是在于实现算法的并行化以及观察Hadoop集群中相应节点数对算法执行效率的影响，因此将借助Apache旗下已经集成k-means算法的mahout这一软件包来达到预期目标。基于Hadoop的系统实现将依托学院实验室的云平台来实现。

综上所述，本次毕业设计将采用文献资料阅读法，实验法，观察法，统计法，比较研究法等。

3. 研究计划与安排

1．2017/3/1—2017/3/31：阅读相关文献及书籍，理解k-means算法相关知识以及学习hadoop集群知识，学习mapreduce运行机制，调试hadoop集群，做好相关测试为k-means算法的运行做好准备；

2．2017/4/1—2017/4/30：在hadoop上实现k-means算法的并行化，分析和统计得出结果；

4. 2017/5/1—2017/5/27：撰写论文初稿；修改论文，定稿并提交论文评审；

4. 参考文献（12篇以上）

[1]．姜园，张朝阳，仇佩亮，周东方； “用于数据挖掘的聚类算法”；电子与信息学报 2005 第27卷 第4期

[2]．周涛，陆惠玲；“数据挖掘中聚类算法研究进展”；计算机工程与应用 2012 第48卷 第12期

[3]. 周爱武, 于亚飞； “k-means 聚类算法的研究”；计算机技术与发展 2011 第21卷 第2期