基于Spark的层次聚类算法的并行化研究
2020-06-16余胜辉李玲娟
计算机技术与发展 2020年6期
关键词:实验
余胜辉,李玲娟
(南京邮电大学 计算机学院,江苏 南京 210023)
0 引 言
大数据时代的来临导致行业领域产生的信息数据呈爆炸式的增长。对海量数据的挖掘以及利用成为了当下最热门的重点研究课题之一。聚类方法是数据挖掘领域中最为重要的方法之一,是一种无监督的机器学习算法,能够将数据对象中具有相同属性的数据划分为若干个子集,每个子集形成一个簇,同一个簇中的数据具有相似的特征,不同簇中的数据相异[1]。层次聚类算法是聚类算法中最常见的一类方法,“类内的点都足够近,类间的点都足够远”[2]是其最重要的判断标准。CURE算法是一种典型的层次聚类算法,该算法简单、速度快,对大数据集有较高的聚类效率和可伸缩性,时间复杂度近于线性,适合对大规模数据集进行挖掘[3-4]。Spark[5-6]是专门为大规模数据处理设计的快速通用计算引擎,是以Hadoop MapReduce为基础框架的一个新的开源平台。Spark支持交互式计算和复杂算法,速度很快;具有很高的通用性;支持多种资源管理器。为了进一步提升CURE层次聚类算法的效率和可伸缩性,文中基于Spark平台对其进行并行化,并通过对不同的数据集的聚类实验来证明该并行化方案的有效性。
1 CURE算法的原理
CURE是一种基于取样和代表点的层次聚类算法,它采用迭代的方式,自底向上地合并两个距离最近的簇[7]。CURE算法在传统的划分聚类算法受异常数据比较敏感这一特点上能够得到很好的解决。CURE算法在计算过程中将每一类当成一个点,用这个点代表其中一个类型的数据,然后计算一个类与另一个类之间的距离,最相似的两个点进行合并,不需要计算类内每个数据点之间的距离,这样计算有利于减少运算量,提高效率。……
登录APP查看全文
