基于Spark平台的聚类算法的优化与实现

作     者：曹鹏 

作者单位：北京交通大学 

学位级别：硕士

导师姓名：卢苇

授予年度：2016年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：大数据 分布式计算 聚类分析 Spark框架 

摘      要：现代信息社会中,随着数据量的增大,对大规模数据集进行聚类分析并生成有用信息的需求也在不断增加。如今对于大规模数据的聚类分析主要有以下难点：第一,聚类对机器内存容量的需求超出了单一计算机的硬件能力;第二,聚类分析时间过长,效率无法得到提高。于是,对大规模数据上聚类算法的优化,可以归结为对数据规模的优化以及对算法在分布式平台上的优化。近年来,分布式计算平台Spark得到了广泛关注, Spark可以对于大规模数据进行内存上的迭代计算,使计算变得更加迅速,有着其它分布式平台无法比拟的优势。本文主要研究了基于Spark平台上特定的聚类分析算法的优化和实现;与此同时,对于聚类数据进行一定的预处理,可以在其不改变聚类效果的前提下减少数据规模,提高运行效率。论文选取了近年来被提出且被广泛应用的聚类算法：近邻传播聚类与谱聚类作为优化对象。论文的主要工作如下：(1)针对聚类算法的数据规模问题,本文通过引入一种新的参数：阈值,对原始数据进行预处理。该方法根据聚类算法需要生成的类簇数,针对数据在空间中的密度计算出一定的阈值,在生成相似度矩阵时将低于该阈值的相似度数据删除,保留有效的相似度数据,从而优化数据结构并生成稀疏矩阵,在保证聚类效果不发生变化的同时减小数据规模。(2)对于近邻传播聚类算法,本文提出了一种基于Spark平台上的分块式的近邻传播聚类算法。通过在Spark平台使用二维索引的数据结构按照行进行分块并分配到每台机器中,在算法迭代中按照行分块计算归属度矩阵,并将生成结果按列存储;再按照列分块计算吸引度矩阵,并将生成结果按行存储,不断迭代最终生成聚类结果。从而实现算法在Spark平台上数据的并行化,减少机器之间的数据传输,提高聚类算法的效率。(3)对于谱聚类算法,本文提出了一种基于Spark 平台上并行Lanczos分解的的谱聚类算法。首先引入一种并行的Lanczos分解方法对原始拉普拉斯矩阵分解生成三元对角矩阵,降低了分解特征值计算的时间复杂度,该矩阵能够保留原矩阵的特征且很容易使用QR分解求解出其特征向量;其次引入上一步提出的分块近邻传播聚类算法替代原有的K-means算法,对降维后的中间结果进行聚类,减小中间结果的规模,从而优化生成聚类结果的时间效率。实验证明,以上对数据规模的预处理以及对两种算法的优化,在保证聚类准确性的同时,能够提高聚类的时间效率。本文的研究方法对数据聚类处理效率的提高有一定的帮助,对今后其他聚类算法的性能提升莫定了理论基础。