1.1 研究目的及意义

数据挖掘是一门从大量数据或者数据库中提取有用信息的科学，它是用人工智能、机器学习、统计学和数据库的交叉方法在相对较大型的数据集中发现模式的计算过程。数据挖掘的实际工作是对大规模数据进行自动或半自动的分析，以提取过去未知的有价值的潜在信息。在数据挖掘中，聚类分析是一个重要的课题。所谓聚类，就是将一整个物理或抽象的数据集分割成为多个簇，使得同一簇内的数据间相似度高而不同簇内的数据间相似度低的一个过程。它被广泛的运用于文本搜索、模式识别、人工智能、图像分析等领域。目前已经存在许多的聚类算法，比如基于划分的 KMeans算法,基于层次的CURE算法，基于密度的DBSCAN算法，基于网格的STING方法，基于模型的COBWEB方法等等^[7]。

近年来，而随着社会信息化程度的不断加深，人类活动在网络中产生的数据也呈爆炸式增长，如何在大数据环境下高效准确地挖掘出数据中的有价值的信息成为了一个亟需解决的问题^[5]。面对急剧增长的数据量，传统的聚类算法已经很难满足实际应用的需求。其问题主要表现在以下两点：（1）当数据规模过大时，受制于内存容量，传统聚类算法往往无法有效地运行；（2）过多的数据使得聚类算法的执行时间大大延长，算法执行效率过低。

针对上述问题，研究人员提出了将并行处理技术与聚类算法相结合，设计出高效的并行聚类算法的解决思路。针对传统聚类算法处理大型数据集时面临的系统资源占用过大及处理效率低下等问题，基于分布式系统的并行聚类算法则通过将过大的系统负载分摊至各节点服务器上，并在节点中对数据进行并行处理来解决。采用Mapreduce框架对聚类算法进行并行扩展即可使其充分利用集群的计算和存储能力以处理海量数据。

1.2 国内外研究现状

K-means聚类算法最早由Hartigan^[1]于1978年提出。Haitgan将数据集划分为两个簇，以此证明了可以采用概率收敛点定义最佳分割点。由于K-means算法实现起来相对简单，且聚类效果较好，因此运用广泛。2007年，D.Arthur^[16]等人提出了K-means 算法，针对Kmeans算法中初始聚类中心的选择进行了优化。它不是直接从样本中直接随机选择K个数据作为初始聚类中心，而是先随机选出一个样本作为一个初始聚类中心，并计算其余样本与当前聚类中心之间的最短距离，并使用其计算该样本成为聚类中心的概率，并重复这一过程直到选出K个聚类中心为止。这样就使得初始聚类中心之间的距离尽可能地远了。

2011年，周爱武^[7]等人进一步提出了改进的K-means算法。其针对传统K-means算法在选择初始聚类中心时受孤立点影响较大的问题进行了改进。改进算法首先计算各个样本之间的距离，并运行孤立点查找算法，排除孤立点,然后进行聚类，孤立点则在聚类算法之后单独聚类，使聚类结果更接近实际数据分布。

近年来，许多研究人员也着手于将聚类算法与并行技术结合起来。2011年，江小平^[6]等人就系统地阐述了在使用MapReduce框架对K-means聚类算法并行化时，map函数及reduce函数的设计思路。周润物^[12]等人则针对大数据环境下K-means聚类算法聚类精度不足和收敛速度慢的问题，提出一种基于优化抽样聚类的K-means算法(OSCK)，基于最佳聚类中心的欧式距离相似性原理排除聚类中心的次优解。Sinha A^[4]等人将并行K-means算法与遗传算法相结合，使得算法对误差的容忍度更优秀。