论文部分内容阅读
随着互联网技术的飞速发展,海量数据环境变得更为普遍,如何从大数据中快速有效地挖掘出有价值的信息成为了研究的热点。面对海量数据的分析计算,分布式计算框架逐渐成为解决这类问题的主要方法,通过Spark等分布式计算框架能有效解决单机环境下的内存溢出问题,利用集群资源提高传统数据挖掘技术的扩展性和运行效率,并转入实际的应用中,对充分利用大数据中蕴含的信息具有重要的意义。本文重点研究了K-means聚类算法及其优化方法在Spark平台上的并行化设计与实现,从算法的运行效率角度进行性能提升。首先,对传统K-means算法的基本原理和Spark框架的并行化特点进行了介绍。然后,在充分研究Spark编程模型和并行化设计的基础上,分别从减少冗余计算量、提高样本代表性这两个方面对K-means算法进行改进,同时基于Spark平台设计并实现了改进算法的并行化策略。本文的主要内容和创新点如下:1)针对传统K-means算法存在的冗余计算量大的问题,对Spark机器学习库采用的三角不等式优化方法的原理和局限性进行了详细的分析,提出了基于空间分布信息的改进方法。改进方法通过引入空间分布信息对数据点与聚类中心的关系进行量化描述,从而实现在数据点分配过程中对聚类中心的过滤,以此加速数据分配的过程,避免了原始算法中的绝大多数冗余的距离计算,能够从根本上提高算法的运行效率。2)针对传统的随机取样策略样本代表性不足的问题,提出了基于密度加权的取样方法。通过新的取样策略使全体数据都能在样本中不同程度地有所体现,以此提高样本的质量,并结合预聚类的方法提升算法运行效率。基于上述研究成果,将改进后的两种策略分别在Spark平台上进行了并行化设计与实现,通过实验对改进后算法的运行效率、扩展性、聚类质量进行验证。实验结果表明,两种改进策略均能显著提高算法在Spark平台上的运行效率,并且在集群环境中表现出了较好的扩展性、加速比。