孙 璐,梁永全
山东科技大学 计算机科学与工程学院,山东 青岛 266590
近年来,信息技术的快速发展使得可用数据爆炸式增长,数据分析在现实生活场景中的应用范围不断被拓展,这对数据分析技术的精度和效率都提出了更高的要求,如何对大规模数据集进行快速、有效的分析和处理变得越来越重要。聚类是一种重要的数据分析技术,是最早研究空间数据集中数据结构和模式的数据挖掘技术之一[1-2],在图像分析[3]、模式识别[4]、知识发现[5]和生物信息学[6]等多个学科领域具有一定的应用价值。随着国内外研究人员对聚类算法研究的不断深入,产生了许多优秀的算法。根据算法实现原理和探究方向不同,目前五种主流的聚类算法为基于划分的方法、基于密度的方法、基于层次的方法、基于网格的方法和基于模型的方法[7]。
DBSCAN是最经典的基于密度的聚类算法之一,其根据数据集的空间分布密度对样本点进行聚类,可以在有噪声的数据中发现任意形状的类簇[8-9],在真实应用场景中处理复杂数据时算法性能优越,得到了国内外学者的广泛关注。然而,DBSCAN算法也存在一些缺陷:(1)采用全局参数导致其在密度不均匀数据集中的聚类质量不高;(2)采用暴力破解法为每个样本点计算邻域密度,计算复杂度较高[10],传统DBSCAN算法在最差情况下的时间复杂度为O(n2),在运行时间为O(nlogn)时,随着数据集的维度或者规模的增加,平方级的时间开销逐渐显现[11],这极大地限制了其在大规模数据集中的应用。……