基于Spark的超图聚类方法研究

发布时间：2020-01-23 15:46

【摘要】：聚类方法一直是数据挖掘中的研究热点之一,近年来基于图论的谱聚类方法是一个非常活跃的研究方向。与K-Means等传统的聚类算法相比,谱聚类方法能够在任意形状的样本空间上聚类,并且收敛于全局的最优解。谱聚类利用图的邻接矩阵,计算其对应的拉普拉斯矩阵,然后求取特征值和特征向量,在特征向量上做聚类。传统的谱聚类是基于简单图的划分,而简单图模型往往对数据的多元关系表示有一定的缺陷。超图模型与传统的简单图模型相比,能够很好地对数据的高阶信息进行描述,可以将谱聚类算法应用到超图模型上。由于谱聚类本身的计算复杂度较高而且超图模型的建立比简单图也更为复杂,所以在大规模数据集上运行超图谱聚类算法,计算复杂度与存储量都会非常大,单机条件下很难应用。但是,近年来云计算和大数据处理平台的研究非常流行。比如基于MapReduce的Hadoop平台,刚刚兴起的基于RDD的Spark计算平台等都可以实现算法的并行化,提高算法的运行效率。Spark是基于内存计算的分布式平台,处理速度相比Hadoop更优,而且更擅长迭代计算,所以本文选择Spark平台,在Spark上对超图谱聚类进行并行化研究与实现。本文首先介绍了论文涉及的相关技术,包括Spark平台及其编程模型、聚类算法以及聚类效果的评价准则、简单图理论与超图的基本概念;然后介绍谱聚类算法的原理、图的划分与图的拉普拉斯矩阵之间的关系,给出超图谱聚类算法的一般步骤;其次在Spark平台上对超图谱聚类算法实现并行化,包含四个阶段的并行化:超图模型建立的并行、求取拉普拉斯矩阵的并行、求取拉普拉斯矩阵的特征值与特征向量的并行、K-Means聚类的并行;最后在公开的数据集和移动用户广告数据集上分别设计实验,在聚类效果上与传统聚类算法K-Means算法进行对比,得出了超图谱聚类算法在聚类效果上更符合实际的结论,然后在Spark平台上测试算法的运行时间,实验表明并行后的算法在性能上有一定的提升。
【图文】：

技术,并行框架,分布式框架,集群计算

分布式框架，非常适合进行海量数据的批处理与存储。除了批处理务处理的需求，Twitter公司开发的Storm系统则满足此种需求。除 AMP lab 所开发的 Spark 通用并行框架也越来越受关注，可以说是继计算平台。k 简介与系统架构源于美国加州伯克利分校 AMPLab 的集群计算平台，用于对大规具有速度快、易用和容错性等特点。它不同于 MapReduce 的中间，可以保存到内存中，因此 Spark 能够很好地适用于机器学习等rk 有很多运行模式，可以运行在 Hadoop 上，Mesos 上和 standalo以使用 HDFS、Cassandra、HBase 和 S3 等。Spark 可以使用 Sca语言来编写 Spark 应用程序，并且提供了基于 Scala、Python、R

系统架构

华南理工大学硕士学位论文常会在 master 节点上提交整个任务，此时会运行一个驱动器程序(di来发起集群上的各种并行操作，驱动器程序会创建一个 SparkContext行各种访问和操作，这个对象 sc 代表了对分布式集群的一个连接。在，存在一个或多个 executor 进程，，负责对 task 的执行。
【学位授予单位】：华南理工大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP311.13

【相似文献】