论文部分内容阅读
随着云计算、社交网络和物联网等技术的兴起,各种海量数据正在不断的增长和积累,传统的数据挖掘处理方式已经不能满足用户的需求。快速准确地实现大数据挖掘任务已成为目前的研究热点。相对于近年来流行的Hadoop平台处理数据挖掘问题效率低下的状况,基于内存计算的大数据平台Spark,对数据挖掘算法的实现有着更好的优势。本文研究了基于Spark的分布式数据挖掘现状和相关技术,提出了两个不同类型的分布式数据挖掘算法:(1)不考虑数据分区的分布式聚类优化算法CK-means;(2)需要做数据分区预处理的分布式离群点检测算法VDOD(Variance–based Distributed Outlier Detection)。主要工作如下:(1)分析总结了K-means聚类算法与基于距离的离群点检测算法的国内外研究现状。分别从Spark大数据处理框架、聚类算法、离群点检测算法三个方面对基于Spark的分布式数据挖掘相关技术进行了研究。(2)首先,研究了传统聚类算法K-means及其在Spark上的并行实现。然后,针对其聚类结果不稳定的弊端,采用Canopy算法选取聚类初始簇中心,提出优化算法CK-means。CK-means算法基于概率选取Canopy中心点,提升了聚类的稳定性,而且增大单次选取Canopy中心点个数的期望,并行选取Canopy中心点,提高了计算效率。同时在Spark平台上完成了CK-means算法的实现。最后通过实验验证,与Spark上实现的K-means对比,CK-means算法在大规模数据集上计算效率和聚类准确度上均有有效的提升。(3)研究了基于距离的DB(k,r)离群点检测方法,提出了一种改进的分布式离群点检测算法VDOD。在数据预处理阶段,设计了一种基于方差的数据划分方法,该方法不仅可以均衡每个计算节点的工作负载,而且减少对数据近邻性的破坏,从而降低了离群点检测时的网络通信量。在离群点检测阶段,VDOD算法采用R索引树快速计算出局部离群点,然后通过少量网络的通信得到最终的全局离群点,同时在Spark平台上完成了VDOD算法的实现。最后通过大量实验证明了VDOD算法的有效性。实验结果表明,相对于已有算法,VDOD算法可以提高计算效率、降低网络开销。