论文部分内容阅读
随着计算机和互联网技术的迅速发展,数据量呈爆发式增长,海量数据的高效处理和利用成为当前社会面临的最艰巨任务之一;同时如何高效率、低成本、准确地从现有的海量数据中挖掘出潜在、有用的知识是数据挖掘领域研究面临的一大难题。以K-means算法为代表的聚类分析是数据挖掘领域最重要的研究方向之一,K-means是一种典型的基于划分方法的聚类算法,具有思路简单、收敛速度快、时间复杂度近似于线性等特点,较适合应用于海量数据的聚类;群体仿生优化算法能够利用群体优势、并行搜索,以全局寻优的方式快速获得优化问题最优解,被认为是目前处理K-means聚类优化问题最行之有效的方法。当前已有很多学者基于多种不同的群体仿生智能算法对K-means聚类算法进行优化,但现有的K-means聚类改进算法还存在以下两个问题需进一步完善:(1)聚类过程中的全局寻优能力不够突出,容易陷入局部最优;(2)在数据量较大时的聚类效率不高,没有充分利用服务器集群优势。作者所做的主要工作包括:(1)提出一种新型元启发式基于仿生行为的改进的布谷鸟搜索算法(Quantum-based Adaptive Cuckoo Search,QACS),解决了原始布谷鸟算法搜索步长的自适应性问题,并引入量子运算使该算法的搜索方向具有一定的倾向性。(2)针对K-means聚类算法易陷入局部最优的问题,将新算法QACS与K-means聚类算法相结合,提出了一种新的串行K-means聚类算法(K-means clustering algorithm based on QACS,QACS-KMeans),提高了K-means聚类算法的全局搜索能力;(3)针对K-means聚类算法在处理较大数据量时效率较低的问题,利用Hadoop分布式平台的MapReduce编程模型实现了对新算法QACS-KMeans的并行化处理。通过在虚拟机中搭建的Hadoop伪分布式集群对不同样本数据集分别进行10次准确性实验和效率实验,结果表明:(1)并行QACS-KMeans新算法聚类的平均准确率在实验所采用的6种UCI标准数据集上,相比原始K-means聚类算法、利用粒子群优化算法(Particle Swarm Optimization,PSO)改进的K-means聚类算法和自适应布谷鸟搜索(Adaptive Cuckoo Search,ACS)改进的K-means聚类算法都有所提高;(2)并行QACS-KMeans新算法聚类的平均运行效率在实验所采用的5种大小递增的随机数据集上,当数据量较大时,显著优于原始K-means串行算法,稍好于并行PSO-Kmeans算法和并行ACS-KMeans算法。实验结果表明,当数据量较大并且维数较低时,利用并行QACS-KMeans算法的聚类效果较好。