论文部分内容阅读
在当今移动互联网时代,每天都会产生海量的数据,在这些数据中蕴含着巨大的价值,而如何从中发掘出有价值的信息已经成为一个相当重要的研究课题。在传统计算机上处理这些海量数据需要耗费大量的时间,满足不了如今的商业所需。为了解决该问题,本文在传统单机聚类算法的基础上,结合并行计算平台Spark对其进行了并行化设计实现与优化。 CLARANS(Clustering Large Application based upon Randomized Search)算法是一种被广泛应用的基于划分的聚类算法,该算法鲁棒性较好,对噪声(离群点)不敏感,且算法运行时数据的输入顺序不影响聚类的结果。但是该算法有比较高的时间复杂度,难以用于处理海量数据。同时算法本身存在聚类簇数难以确定、聚类结果依赖初始中心点选择且易陷入局部最优等问题,算法聚类效率不高且难以保证聚类稳定性。 本文首先对聚类算法的国内外研究现状进行了综述,在此基础上对聚类算法在并行化方面的研究展开了讨论,进一步又对基于遗传算法的聚类算法优化问题进行了分析。接着详细分析了Spark计算框架的主要概念和原理以及分布式文件系统HDFS的原理。同时,概括分析了聚类算法的相关知识点,为论文后续研究提供了坚实的理论基础。 然后针对算法复杂度较高的问题,提出一种基于Spark平台的并行化SP-CLARANS算法,利用Spark集群基于内存的计算速度优势提高算法的运行效率和数据集处理的规模。针对算法对初始中心点敏感难以获得全局最优的问题提出一种利用并行化遗传算法进行优化的SPGA-CLARANS算法,结合Spark的特性对此算法的染色体编码、选择、交叉和变异算子进行了设计和改进,将遗传算法的全局搜索能力和SP-CLARANS算法的局部搜索能力相结合提高了改进算法聚类质量和稳定性。 最后本文搭建Spark集群进行仿真实验,在集群独立运行模式下利用UCI真实数据集验证算法的准确性和稳定性,接着利用不同规模的人工数据集验证算法的聚类效率,并在大数据集上验证本文算法的并行性能。实验结果表明,本文提出的改进并行化算法具有较高的聚类准确率、聚类效率和并行性能,对于解决传统聚类算法处理海量数据的瓶颈问题,有一定的积极作用。