论文部分内容阅读
聚类分析一直是数据挖掘领域的核心研究议题之一,不仅得到国内外研究者们的长期持续关注,亦在工业中的很多领域得到应用。在大量的聚类方法中,K均值算法因其简洁高效、聚类结果鲁棒且易于解释、适应面广等优点,成为最基础且应用最广的方法。随着研究的深入,K均值方法体系渐趋庞大,形成大量的K均值方法变例,如适合高维稀疏文本聚类的Info-Kmeans、模糊c均值、组合聚类方法KCC等,这些方法都沿袭了K均值的两阶段迭代过程:距离计算和更新类簇中心。大数据时代的到来使得单机聚类算法难以胜任大数据聚类的要求,因此,如何利用分布式计算技术提升大数据聚类的可扩展性成为一个重要问题。本文聚焦于如何将K均值方法体系的通用分布式聚类框架设计与实现,该框架需具备两个特性:首先,可以支撑K均值方法体系中的主流算法,而且可以便捷地纳入新的其他基于K均值的算法,即具有通用性;其次,可以胜任大规模数据的高效聚类,即具有高可扩展性。本文主要研究工作包含以下几个方面:1.基于Spark内存计算框架,提出适用于K均值方法体系的通用分布式聚类框架;并对框架中的各个阶段进行了重新设计,增强了框架的适应性及可扩展性,包括:数据加载模块适应高维稀疏数据,距离计算模块支持K均值多种距离函数、以适应不同类型数据聚类的需求。2.模糊c均值需要利用隶属度矩阵来更新中心,计算框架和K均值有所不同,本文设计出模糊c均值的Spark平台的计算框架,使其具有很强的适应性和可扩展性,包括:距离计算模块支持多种模糊c均值的距离函数,隶属度矩阵的更新部分步骤放在距离计算的map函数中,充分发挥了分布式框架的优势使得算法更新效率更高。3.提出了Spark平台的基于K均值的组合聚类算法,包括硬聚类组合聚类和模糊聚类的组合聚类。基于K均值的组合聚类和K均值算法在初始化和距离计算的步骤都不一样,所以本文要结合Spark分布式计算框架的特点设计出合理的初始化和距离计算的方法。4.本文设计的基于Spark内存框架的K均值方法体系在大型UCI数据集和文本数据集的实验结果都证明了聚类效果和执行效率的可行性。在KDDCUP这种拥有百万条数据的数据集上本文的聚类效果和CLUTO接近,速度快于MLlib。同时在如Weibo数据集这类高维数据文本数据集,也取得了良好的聚类效果。