面向大规模数据集的自适应聚类算法并行化研究

摘要

目前，随着网络的普及，各种应用设备逐渐日常化，产生的数据量日益增多，因此需要分析处理的数据规模越来越大，从而使数据挖掘任务变得愈加复杂。作为一种无监督学习方式，聚类是数据挖掘领域的一种重要工具。按照相似性度量原则，聚类尽可能地将具有相同性质的数据对象归于一类，有助于从数据集中提取潜藏的、有价值的信息。一般而言，传统聚类算法在处理大规模数据集时由于受到时间、内存、CPU等资源的限制，很难实现高效处理。因此，针对大规模数据集，如何快速、高效、自适应地对其聚类，并从中挖掘到有价值的信息极具研究意义。
　　近年来，分布式计算、云计算以及分布式存储等技术的迅速发展，为大规模数据集的高效聚类提供了新的研究方向。Hadoop作为Apache的开源项目，采用HDFS（Hadoop Distributed File System）进行数据存储，利用MapReduce编程模型完成对海量数据集的并行处理。Spark作为一种以内存计算为基础的高效并行计算框架，在数据处理过程中，通过将聚类产生的中间结果直接存放到内存中，提高了迭代运算的效率。
　　本文将并行化的思想引入到大规模数据的聚类处理过程中，基于Hadoop和Spark架构对聚类算法做了如下三方面的研究：
　　第一，针对大规模数据集的特点，总结了大规模数据集聚类的主要相关技术及其应用领域；在分析Hadoop架构与MapReduce编程模型的基础上，深入研究了Spark计算框架，并阐释了K-means、Canopy和基本粒子群算法的核心思想及算法流程图。
　　第二，在研究传统K-means、Canopy算法的基础上，针对中心点选取存在的盲目性和随机性问题，提出了一种面向大规模数据集的二分Canopy-Kmeans并行聚类算法（下文简称BCK-means）。该算法采用“动态迭代初始化原则”与“二分法”结合的策略，在确定Canopy初始中心点和T1的基础上，利用MapReduce编程模型实现了算法的并行化处理，在一定程度上适应了大规模数据集的分布式存储应用环境。实验表明，算法的聚类结果能够较好地反映大规模数据集合内在的结构属性划分，尽可能高效地利用了集群的计算和存储能力。
　　第三，在问题二研究的基础上，结合基本粒子群算法的自适应性特点，提出了一种动态自适应惯性权重的粒子群优化K-means并行聚类算法（下文简称dsPSOK-means）。该算法通过适应函数动态调整惯性权重，使dsPSO算法具有自适应特性，然后将dsPSO算法的输出作为K-means算法的输入，从而提高了K-means算法在选择初始中心点的智能性和自适应性。进而，借助Spark平台，设计并实现了集群环境下的dsPSOK-means并行化聚类算法。实验结果表明，dsPSOK-means算法可以有效地减少执行过程中节点间的通信量，能够实现数据的高效处理。
　　总之，本文针对大规模数据集的自适应聚类并行化算法研究，对于解决传统聚类算法处理海量数据的瓶颈问题，有一定的积极作用，为有效提高聚类算法的效率和聚类质量提供了一种新的解决方案。