,,

(1.杭州电子科技大学 自动化学院,杭州 310018; 2.浙江省电子信息产品检验所,杭州 310007)

0 概述

聚类[1]是将对象集分成由类似对象组成的多个聚簇的过程,常用于统计分析方法,目前已经在图像识别、模式识别、数据挖掘等诸多方面大规模应用。

随着互联网的兴起和数据库技术的发展,数据集的规模不断扩大,传统的聚类方法因限于运行速度和准确率无法适用于大规模的数据集。以MapReduce[2-3]为代表的并行化编程框架的出现,为聚类算法应用于大规模数据集提供了一种新的途径。其中,文献[4]提出利用MapReduce对生物医学概念之间的关联进行提取的方法,文献[5]将MapReduce应用于数据分类方向,并对MapReduce进行稳定性测试。

目前已经有很多算法实现在MapReduce框架上,如使用范围最广的K-means算法[6-7],其中具有代表性的改进有基于MapReduce模型的单通和线性时间K-均值聚类算法[8]和基于海量数据分析的改进K-Medoids算法[9]。

MapReduce框架上较为常见的算法还有Canopy聚类算法,其中最具代表性的是文献[10]提出的改进Canopy高效算法。该文将改进的Canopy算法实现在Hadoop平台上,极大地节省了聚类运行的时间。

上述2种算法各有优劣：K-Means算法原理简单、便于操作,但类别数需要人为设置,而且初始聚类中心也很难选择,容易出现局部最优的情况；Canopy算法无需指定类别数,运行速度极快,适合处理大规模的数据集,但聚类效果一般,尤其是在不同类别的边界,极容易出现聚类重叠的现象。

文献[11]提出最近邻优先吸收(Nearest Neighbor Absorption First,NNAF)聚类算法,该算法适用于任意形状的聚类,可快速处理高维数据,但在数据密度和聚类间距离不均匀时聚类质量较差,文献[12]针对此问题提出基于数据分区的NNAF算法。……