基于Hadoop的聚类算法并行化分析及应用研究.pdf

摘要
伴随着计算机技术的迅猛发展以及互联网的快速普及，人们所接触的数据量
（包括有结构和无结构的文本数据）呈现爆炸式增长。当前，如何有效快速地从
海量数据中挖掘出有价值的信息具有重要的意义。聚类分析是进行数据挖掘的核
心技术之一。传统单机的聚类算法无论从效率上，还是从计算复杂度上都已无法
满足海量信息的处理需要，云计算技术的发展为聚类分析提供了新的研究方向。
Hadoop，作为 Apache 下的开源的项目，是一个用于构建云平台的分布式的
计算框架。在 Hadoop 平台上，采用 HDFS（分布式文件系统）存储数据，采用
MapReduce 编程模式来实现对海量数据的并行化处理。根据传统聚类算法本身的
特点，并且结合 MapReduce 的编程模式，使得开发人员不需过多了解并行化的具
体通信实现，就可以实现聚类算法的快速并行化，高效而且容易实现。
本文对传统的各种聚类算法进行了比较，针对传统的 K-means 算法在初始聚
类中心选择的随机性以及聚类结果的局部最优性进行了适当的改进，并将改进结
果结合 Hadoop 框架进一步应用到实际项目中的相关领域，而且进行了深入的研
究。结果表明，这些改进使得算法在执行效率和结果的精确性方面都有明显提高。
本文的工作重点总结如下：
1) 研究了 MapReduce 编程模型，分析了传统 K-means 算法以及 Canopy 算
法的优缺点，提出了基于 canopy 的二次聚类算法(CTK)的思想，并给出了该算法
在 Hadoop 上的并行设计框架，描述了其具体实现。
2) 分析了最大最小距离算法，提出了基于最大最小距离原理的 K-means 聚类
算法(MMKMEANS)的思想。结合 MapReduce 编程模型，实现了该算法在 Hadoop
平台上的并行化。
3) 分析了聚类应用于热点生成的整体流程。研究了使用 nutch 采集网页信息
的策略，以及解析后的网页内容表示成文本向量的并行化实现过程，并以此提供
上述算法的实验数据，并且还给出了聚类用于热点生成的并行化实现。
4) 通过实验结果验证了上述算法在文本聚类中的聚类质量、查准率、查全率
以及并行化的加速比等方面的优越性。

关键词：K-means 聚类，CTK，MMKMEANS，MapReduce
I
ABSTRACT
With the increasingly rapid development of computer technology and the rapid
spread of the Internet, the data (including structured and unstructured text data) which
people in contact with is growing explosively. At present, how to effectively mining
valuable information from massive data is of great significance. Cluster analysis is one
of the core technologies of data mining. No matter from efficiency or from the
computational complexity, the traditional single clustering algorithms have been
unable to meet the processing needs of massive information, cloud computing
technology development provides a new research direction for cluster analysis.
As an open source project of Apache, Hadoop is a distributed computing
framework