快速密度峰值聚类算法研究与应用

发布时间：2021-04-10 01:12

　　由于存储技术的进步和日常生活工作中不断产生各种数据,加快了大数据时代的到来。人们可以通过对大量的数据进行分析和挖掘,得到所需要的有价值的信息。然而目前处理海量数据的速度仍难以满足人们的需求,因此从大规模数据中高效的挖掘出人们所需要的有价值的信息成为了数据处理的一个难题。机器学习在解决这类问题中发挥了重要的作用,其中聚类算法是机器学习十大经典算法之一。密度峰值聚类算法（DPeak）是目前热门聚类算法的一种。该算法具有思想简单、参数唯一且能聚类成任意形状簇等优点。凭借这些优点,DPeak一经提出就吸引了大量科研人员的关注。虽然DPeak有许多优势,但是其时间复杂度为O（n²）,难以满足海量数据的处理。因为该算法中ρ和δ这两个量都是通过复杂度为O（n²）的蛮力算法得到的,故计算当中存在大量的冗余计算。本文对DPeak算法进行了深入的分析,并在总结前人的基础上取其精华弃其糟粕,提出了快速密度峰值聚类算法。该算法显著的提高了DPeak算法处理大规模数据的速度。本文主要包括以下几个方面的内容:（1）分析了DPeak算法的性质,对其在整个聚类算法体系中位置... 

【文章来源】：华侨大学福建省

【文章页数】：63 页

【学位级别】：硕士

【部分图文】：

DCore的密度核心区与数据漂移[51]

25(1)这两种算法形成簇的方式都是沿着点密度变大的方向。(2)在meanshift中，漂移的中间点可能是虚拟点，而在DPeak中，漂移的中间点为真实点。(a)实例1(b)实例2图3.3DPeak的局部峰值中心2个实例(3)meanshift实际上是ShadowKernel(影子)梯度上升法，但其步长是动态变化的[74]。如果数据为标准的高斯分布，那么该方法为SteepestAscentMethod(最速上升法)。当它的核函数是PiecewiseConst（分段常数)时，均值漂移过程实际上又是牛顿法[81]。当核函数是其它任意形式时，该算

37图4.1在三个二维合成数据集的实验4.2.2实验二FastDPeak的速度在这一小节中，本文介绍了一些在大规模数据集上进行的实验，并与其他算法进行了比较。第一个实验在BigCross200k，BigCross500k和KDD04上进行，其中BigCross200k和BigCross500k分别有20万和50万个点，均是从BigCross中随机选取的。结果如表4.2所示，从表中可以看出，在K=50和K=100的两个数据集上，FastDPeak算法都比EDDPC算法好的多。以BigCross200k为例，FastDPeak算法对EDDPC算法的速度提升为2-3倍，BigCross500k的速度约为LSH-DDP算法的1.635-2.7倍。在KDD04上，FastDPeak算法相对于其他两种算法的优势更加明显。表4.2三个数据集上运行时间比较(单位:秒)BigCross200kBigCross500kKDD04EDDPC15599768FastDPeak(K=50)3812228FastDPeak(K=100)5115034FastDPeak(K=150)6620142第二个实验也是在BigCross上进行的。其中K是固定的，而n从100000到500000不等。结果如图4.2所示。从图中可以看出FastDPeak在BigCross上，随着K=50，K=100，K=150，运行时间越来越短，其速度比EDDPC快很多。EDDPC的时间复杂度大于O(nlog(n))，随着数据量的增大，运行时间迅速会增加。FastDPeak的时间复杂度为O(nlog(n))，满足上述复杂度分析。图4.3为BigCross上FastDPeak算法和EDDPC算法的距离计算量随n增加的情况，其中FastDPeak的距离计算量包括距离计算的KNN算法。还发现FastDPeak的距离

【参考文献】：
博士论文
[1]基于流形学习的分类与聚类方法及其应用研究[D]. 王勇.国防科学技术大学 2011



本文编号：3128662