基于MapReduce的K-Medoids并行算法研究

发布时间：2018-02-02 02:05

本文关键词： K-Medoids 分布式计算 Hadoop 并行采样　出处：《辽宁工程技术大学》2015年硕士论文　论文类型：学位论文

【摘要】：大数据时代,信息呈爆炸性增长,准确的从海量数据中进行数据的挖掘对当今信息化社会具有重要的价值意义。作为基于划分的聚类算法K-Medoids,其较大的时间复杂度以及传统的初始中心点随机选择策略已经无法适应海量数据下的聚类要求。使用MapReduce并行计算模型对算法进行改进,虽然能够提高算法的运行效率,但是无法解决大数据量下的聚类结果不精确,以及收敛性低下的问题,所以必须还要从算法本身出发去解决这些问题。针对传统的K-Medoids算法对初始聚类中心敏感、收敛速度较慢,以及在海量数据环境下所面临的单台计算机的性能瓶颈问题,从中心点替换方法以及初始簇心选择方案入手,并利用MapReduce分布式编程模型结合并行随机采样策略,实现了一种高效的K-Medoids算法,最后利用Hadoop的分布式存储及计算特性,实现算法的二次优化。通过和传统的K-Medoids算法以及K-Means算法比较,改进后的K-Medoids算法在集群环境下不仅有着良好的加速比,在聚类精度以及收敛性上都有了一定程度上的改善。
[Abstract]:In the big data era, the information is increasing explosively. It is of great value to mine the data accurately from the massive data. As a clustering algorithm based on partition K-Medoids, it is of great value to the information society today. Its large time complexity and the traditional random selection strategy of initial center can not meet the clustering requirements of massive data. The algorithm is improved by using MapReduce parallel computing model. Although it can improve the efficiency of the algorithm, it can not solve the problem of inaccurate clustering results and low convergence under the large amount of data. The traditional K-Medoids algorithm is sensitive to the initial clustering center and the convergence speed is slow. And the performance bottleneck of a single computer in the environment of massive data, starting with the center replacement method and the initial cluster center selection scheme. Using MapReduce distributed programming model and parallel random sampling strategy, an efficient K-Medoids algorithm is implemented. Finally, by using the distributed storage and computing characteristics of Hadoop, the quadratic optimization of the algorithm is realized, which is compared with the traditional K-Medoids algorithm and K-Means algorithm. The improved K-Medoids algorithm not only has a good speedup in the cluster environment, but also improves the clustering accuracy and convergence to some extent.
【学位授予单位】：辽宁工程技术大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP338.6

【相似文献】