基于密度峰值聚类算法的研究与实现

发布时间：2020-03-28 22:51

【摘要】：随着互联网在全球范围内的快速普及,我们每天都会面对来自社会、商业、医学、工程和科学以及我们日常生活各个方面的海量数据。数据的爆炸式增长、广泛可用和巨大规模把我们带入了一个真正的数据时代。而如何可以快速方便地从这些杂乱无章的大规模数据中挖掘出有用的信息,并将这些非结构化的数据转变成知识,已经成为当今科学领域的一个热门研究课题。基于密度峰值聚类算法(Clustering by fast search and find of density peaks,FSDP)是Rodriguez等人于2014年在Science杂志上发表的一种新型密度聚类算法。因其具有算法原理简单、易于实现且能够快速发现任意形状簇的优点,自该算法被出以来,大量的研究学者对其进行了研究与应用。FSDP聚类算法的优点突出,然而其缺点也很明显。FSDP聚类算法主要存在以下几个方面的不足:(1)截断距离参数?_?的取值难以确定,主要依靠主观经验,缺乏一定的选择依据;(2)聚类中心的选取需要人为参与,聚类结果的客观性和准确性得不到保障;(3)在计算数据对象的局部密度和最小距离时,由于需要遍历数据集中所有的数据对象,导致算法的时间复杂度过高,不适用于大规模数据集的聚类分析工作。针对FSDP聚类算法存在的上述问题,本文分别出了相应的改进方案:(1)针对FSDP聚类算法中截断距离参数?_?的取值难以确定和聚类中心的选取需要人为参与的问题,出了一种将布谷鸟搜索算法与基于密度峰值聚类算法相融合的聚类算法。首先,改进后的算法利用布谷鸟搜索算法通过预定义的局部密度信息熵适应度函数,为FSDP聚类算法搜索到恰当的截断距离,并通过得到的截断距离求得数据集中数据对象的局部密度和最小距离。然后,利用布谷鸟搜索算法通过预定义的Rand适应度函数在数据集的局部密度和最小距离空间内为FSDP寻找到一组合适的局部密度和最小距离阀值(这里为了加快这组阀值的搜索速度,针对原始布谷鸟搜索算法存在后期收敛速度慢、搜索精度低的缺点,出了一种改进的布谷鸟搜索算法来替代原始布谷鸟搜索算法执行搜索操作)。通过比较数据集中数据对象的局部密度和最小距离与这组阀值的大小关系,选取局部密度和最小距离均大于这组阀值的数据对象作为聚类中心执行聚类。通过实验证明,改进后的聚类算法在不需要人为参与的情况下,不仅能够有效地自动选取到正确的聚类中心,并且可以取得较好的聚类效果。(2)针对FSDP聚类算法对大规模数据集进行聚类分析时,由于算法的时间复杂度过高而导致算法运行效率过低的问题,出了一种基于Spark的并行FSDP聚类算法SFSDP,并将SFSDP算法应用到城市热点区域探测应用中。通过对城市热点区域的有效探测验证了该算法的实用性。首先,算法通过空间网格划分将待聚类数据集划分成多个数据量相对均衡的数据分区;然后,利用改进的FSDP聚类算法并行地对各个数据分区内的数据对象执行聚类分析工作;最后,通过将各个数据分区聚类得到的局部聚簇集合并,生成全局聚簇集。实验结果表明,SFSDP并行聚类算法与FSDP聚类算法相比能够有效地进行大规模数据集的聚类分析工作,并且SFSDP聚类算法在准确性和扩展性方面都有很好的表现。
【图文】：

组件图,组件,数据分析

图 2-2 Spark 分布式执行涉及的组件[29] Spark 数据分析栈为大数据分析应用供了一个统一数据处理的平台，在这个平的组件。Spark 在架构上主要包含内核（Spark Core）部分和多QL、Spark Streaming、MLlib、GraphX）。图 2-3 给出了 Spark 的它们进行简单介绍。图 2-3 Spark 数据分析栈Spark Core 模块

模块图,数据分析,模块

图 2-3 Spark 数据分析栈Spark Core 模块park 整个计算框架实现的基石，Spark 核心模块除了为 Spark 计须的基础功能外，还给出了弹性分布式数据集 RDD 的 API 定义是 Spark 的主要编程接口，自 Spark 2.0 起，RDD 被 Dataset 所DD 的强类型，但对其进行了更多的优化。Spark Core 供了创的多个 API。Spark SQL 模块SQL 是 Spark 用来对结构化数据进行操作的程序包。与基本的SQL 所供的接口为 Spark 应用供了更多与正在执行的数据在内部，Spark SQL 通过利用这些额外的信息为应用供更多供了多种与 Spark SQL 进行交互的方式，包括 SQL 和 Data，不管上层使用哪种方式或编程语言来表示计算，底层都会使开发人员在不同 API 之间来回切换时供了很大的便利。Spark Streaming 模块
【学位授予单位】：江南大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP311.13

【参考文献】