论文部分内容阅读
由于存储技术的进步和日常生活工作中不断产生各种数据,加快了大数据时代的到来。人们可以通过对大量的数据进行分析和挖掘,得到所需要的有价值的信息。然而目前处理海量数据的速度仍难以满足人们的需求,因此从大规模数据中高效的挖掘出人们所需要的有价值的信息成为了数据处理的一个难题。机器学习在解决这类问题中发挥了重要的作用,其中聚类算法是机器学习十大经典算法之一。密度峰值聚类算法(DPeak)是目前热门聚类算法的一种。该算法具有思想简单、参数唯一且能聚类成任意形状簇等优点。凭借这些优点,DPeak一经提出就吸引了大量科研人员的关注。虽然DPeak有许多优势,但是其时间复杂度为O(n~2),难以满足海量数据的处理。因为该算法中ρ和δ这两个量都是通过复杂度为O(n~2)的蛮力算法得到的,故计算当中存在大量的冗余计算。本文对DPeak算法进行了深入的分析,并在总结前人的基础上取其精华弃其糟粕,提出了快速密度峰值聚类算法。该算法显著的提高了DPeak算法处理大规模数据的速度。本文主要包括以下几个方面的内容:(1)分析了DPeak算法的性质,对其在整个聚类算法体系中位置进行了讨论。将DPeak与k-means、DBCAN、谱聚类算法、近邻传播聚类、mean shift这5个经典聚类算法进行比较之后,发现DPeak算法与mean shift算法十分相似。因而本文提出了一个猜想:认为DPeak是一种特殊的mean shift算法,是否可以在mean shift框架下解释,还有待进一步研究。(2)密度峰值聚类算法(DPeak)算法复杂度为O(n~2),不适用于大规模数据。因此,本文提出了一个简单且快速的DPeak,即FastDPeak。该算法用覆盖树算法加快了密度ρ的计算。另外,又将δ值的计算从全局搜索降为局部搜索,使得δ的计算时间复杂度降为O(n)。综合而言,FastDPeak算法的复杂度为O(nlog(n))。在多个数据集上实验结果表明,FastDPeak是一种有效的、性能优于其他DPeak变体的算法。对于数据处理和DPeak速度方面的提升有重要意义。