论文部分内容阅读
随着信息化社会的快速发展,累积的数据急速攀升,如何从海量数据中快速地挖掘出有效信息成为应用上的难题。聚类分析是数据挖掘常用的方法,但随着所涉及的数据规模越来越大,许多常规算法越来越力不从心。K-均值聚类(K-Means)和K-中心点聚类(K-Medoids)算法是两种简单的基于划分的聚类算法,现实场景中最常用的基于其基本思路的改进算法。PAM(Partitioning AroundMedoids,基于中心点的分类)是最先提出的K-中心点聚类算法,随后的CLARA (Clustering LARge Applications,大量应用数据聚类)和CLARANS(Clustering Large Application based upon RANdomized Search,基于随机搜索的大量应用数据聚类)通过减少每次计算样本量对其做了改进,也有通过预先分析获得初始点或使用空间距离矩阵等方式对其改进。但是,对于当前超大数据而言,这些改进后的算法在时间复杂度和处理能力上仍然不足。在并行计算平台上进行数据挖掘计算己逐渐成为新的研究热,Hadoop云平台的提出与运用为解决这一瓶颈提供了新的途径。基于H[adoop云平台的数据挖掘分析项目Mahout实现了并行的K-Means等众多数据分析经典算法,并得到了业界的广泛认可和应用,但Mahout未实现K-Medoids算法。本文结合K-Medoids算法的特点与Hadoop平台的优势,借鉴Mahout开源项目中已经实现的并行K-Means聚类算法的实现方案,提出了一种基于MapReduce的并行聚类算法HK-Medoids,大幅提升传统聚类算法的运算速率。另外,为了进一步提高聚类效率,本文从完善MapReduce调度、采取抽样方法、预设聚类初值中心点和优化数据源等方面对HK-Medoids作了进一步的优化。为了验证HK-Medoids算法及其优化的有效性,我们做了大量的实验,比较和分析了算法的优化率和加速比等指标,从而验证了HK-Medoids算法的的有效性。