论文部分内容阅读
聚类分析是数据挖掘、机器学习、模式识别等领域的基础性算法之一,也称作无监督分类,被广泛应用于计算机科学、经济学、医学、社会科学等行业,受到各行业的关注。聚类的目的是使得同一类别的数据具有较高的相似度,不同类之间的相似度尽可能低,从而挖掘出数据中潜在的类别信息。近年来,基于各种分布式平台的聚类算法相继出现。但大规模数据聚类仍存在计算开销大、迭代时间长、聚类效果不够理想等问题。例如,目前基于Spark分布式大数据处理平台的K-means聚类算法具有简单直观、易于分布式实现等优点,但最终聚类结果受初始聚类中心选择的影响较大。再而谱聚类算法能够在任意形状的样本空间上实现聚类,并收敛至全局最优解,但谱聚类算法的计算开销大,不仅需要计算任意两个样本之间的相似性,还需要计算矩阵的特征向量。作为新型聚类算法,联合聚类利用了聚类的二元性,对全局信息的两个维度同时进行聚类,能够得到较单向聚类算法更为全面的聚类结构,然而算法中涉及到的矩阵运算开销大且难以合理并行化,严重限制了其应用范围。基于上述问题背景,本文针对目前大规模聚类算法存在的主要问题,结合现有主流的大数据处理分析平台Spark,研究实现了多种数据场景下的高效并行化聚类算法。本文的主要研究工作和贡献有以下几点:(1)研究实现并行化样本特征预处理方法,为大数据聚类分析提供高效可靠的数据预处理过程。相比于目前已有的特征预处理方法,本文提出的并行化特征预处理方法具有更好的性能和扩展性,并能够进一步提升算法的聚类效果。(2)研究实现快速K-means聚类算法,主要包括密度感知的自适应聚类中心初始化方法,能够根据数据分布情况初始化聚类中心个数和位置,一定程度上降低了迭代轮数,提升了聚类效果;并采用距离计算优化措施,进一步减少每轮迭代中的计算开销。(3)研究实现并行化谱聚类算法,设计实现基于多轮迭代的样本相似度计算方法,有效解决了相似度计算的扩展性问题,避免重复计算。同时,实现基于ScaLAPACK的高效特征向量并行化算法,缩短了特征问题求解的时间。使得算法在大规模数据集下表现出良好的性能和可扩展性。(4)研究实现基于NMF的并行化联合聚类算法,通过迭代求解的方式解决了联合聚类算法中矩阵乘法运算在大规模数据集下的性能和扩展性问题。相关实验表明,该算法仅需较少的迭代轮数,就能保证结果收敛且取得良好的聚类效果。(5)在上述研究工作基础上,基于Spark平台设计实现了快速K-means聚类算法、并行谱聚类算法和并行化联合聚类算法。在保证聚类效果同时,使得算法更好地适用于大规模场景。实验表明,本文提出的聚类算法能够很好地改善大规模数据集下聚类算法的性能问题,并具有良好的数据可扩展性和节点可扩展性。本文工作所实现的快速K-means聚类算法在2017年教育部科技发展中心主办的第三届“全国高校云计算应用创新大赛”大数据技能赛全国总决赛上,以其优异的算法性能与效果,获得聚类赛题第一名的成绩。