论文部分内容阅读
随着新时代下信息技术的迅猛发展和广泛应用,互联网服务正在影响着人们的生产生活方式,海量的数据也随之产生,这使得利用数据挖掘工具从冗杂的原始数据中筛选出有价值的信息指导社会生产和生活变得越来越重要。DBSCAN(Density-Based Spatial Clustering of Application with Noise)算法作为应用广泛的密度聚类算法之一,具有能够发现任意形状的簇并且聚类效果不受噪声点影响等优点,是重要的数据挖掘方法。然而,该算法也存在一些缺陷:当数据规模较大时其对内存的需求过高;聚类结果对输入参数敏感,算法参数设置是其难点之一;此外,面对分布不均匀的数据其难以取得较好的聚类效果。针对上述不足之处,本文提出了结合闪电连接过程优化算法(Lightning Attachment Procedure Optimization Algorithm,LAPO)的改进DBSCAN算法,并在新一代大规模数据处理框架Spark下进行算法的并行化策略研究。本文的主要研究内容概括如下:(1)提出了一种基于LAPO算法的聚类中心获取方法。K-means聚类算法具有对数据集依赖度高和对初始聚类中心的选取敏感的缺点,利用智能优化算法的迭代搜索替代其递进式类中心寻找方式,可获得高质量的聚类中心。本文利用LAPO算法的优良搜索能力,搜索数据集较优的聚类中心。(2)设计了一种结合LAPO算法获得初始聚类中心划分数据集的改进DBSCAN算法(LAPO-DBSCAN)。改进后的算法分为数据划分、局部聚类以及聚类结果合并三个步骤。将基于LAPO算法的聚类中心获取方法用于改进数据的划分阶段,并使用只需一个输入参数的基于K近邻关系的DBSCAN算法进行密度聚类,设计了新的数据划分和聚类合并策略。改进算法的主要优点是降低了经典DBSCAN算法对内存的需求,增强了算法易用性,提升聚类效果。最后,通过对比实验分析验证了LAPO-DBSCAN算法优良的聚类效果。(3)实现了Spark平台下LAPO-DBSCAN算法的并行化运算。利用分布式计算框架提供的高效率、高可靠的计算能力,本文研究了LAPO-DBSCAN算法在Spark平台下的并行化策略,通过RDD算子编码实现了并行化LAPO-DBSCAN算法,并根据实践经验总结了Spark平台下并行算法的优化思路。最后设计实验验证并行算法的聚类效果和运行效率,结果表明Spark平台下的并行化LAPO-DBSCAN算法与单机上版本运行的聚类效果一致,且算法执行效率显著提高。