基于Hadoop平台的机器学习聚类算法研究

作     者：孙超 

作者单位：西安电子科技大学 

学位级别：硕士

导师姓名：李志武

授予年度：2018年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：大数据 聚类分析 K-means算法 Fuzzy C-means算法 Hadoop Spark 

摘      要：聚类分析作为一种建模技术,在数据挖掘和机器学习中起着重要作用。聚类是从没有类别信息的数据中获取规律和组织结构,通过将给定数据集划分为多个类或簇,使得同一簇中的对象相似度较大,而不同簇中的对象相似度较小。聚类技术已广泛应用于社交网络、生物学、医学、工程和交通等领域。然而随着信息技术发展,各领域产生的数据量都以指数级增长,传统聚类算法已经不足以应对当前数据规模,因此开发高效和可伸缩的并行聚类方法分析大数据具有重要现实意义。Hadoop和Spark等分布式平台的出现有效地解决了大数据可靠存储和处理,为扩展聚类算法提供了一个新的研究方向。本文以提高聚类算法的效率和可扩展性为主要研究目标,通过将聚类算法部署到分布式平台架构上,有效解决了传统聚类算法和软件工具难以应对大数据聚类的问题。论文主要有以下工作:(1)聚类算法根据数据特点和所需聚类特征划分为不同类型。本文首先对众多聚类算法的性质特点进行综合对比,选择了基于划分的K-means算法和更精确的Fuzzy C-means(FCM)算法进行扩展研究,详细介绍了这两种算法的基本原理和执行流程。(2)针对K-means算法和FCM算法面对海量数据时具有时效性差的特点,给出两种算法在Hadoop和Spark分布式平台上的并行化实现方案。基于Hadoop MapReduce框架的并行算法在设计Map函数和Reduce函数的基础上增加了Combine函数,通过合并Map节点中的数据降低了节点间通信成本,提高了计算效率。而基于Spark框架的并行K-means算法使用弹性分布式数据集(RDD)数据结构将中间结果保存到内存中,使得算法可以非常高效地多次迭代RDD数据,避免了磁盘I/O开销。另外FCM算法具有复杂度高的缺点,本文提出的基于Spark框架的并行FCM算法避免了直接存储隶属度矩阵,减少了算法的空间需求,也在一定程度上减少了时间需求。(3)为了比较聚类算法在Hadoop和Spark平台上的性能,本文通过收敛速度、聚类质量和加速比等性能指标对基于MapReduce和Spark框架的并行算法进行分析,实验数据集选用随机生成的人工数据集和真实数据集。研究结果表明基于Spark的Kmeans算法和FCM算法在保证聚类质量的前提下,运行时间显著小于基于MapReduce的并行算法。且随着节点数的增加,加速比和扩展率均大于基于MapReduce的并行算法,说明Spark平台在处理迭代型聚类算法方面比Hadoop平台更有优势,同时提高了算法效率、聚类质量和扩展性。总之,基于Spark平台的聚类算法在面对大数据时能够提供更加高效的聚类分析。