计算机研究与发展

作者：陈叶旺,曹海露,陈谊,康昭,雷震,杜吉祥,

关键词：快速化DBSCAN, 密度聚类, 聚类算法, 大数据, 数据挖掘,

DBSCAN(density-basedspatialclusteringofapplicationswithnoise)是应用最广的密度聚类算法之一.然而，它时间复杂度过高(O(n2))，无法处理大规模数据.因而，对它进行加速成为一个研究热点，众多富有成效的工作不断涌现.从加速目标上看，这些工作大体上可分为减少冗余计算和并行化两大类；就具体加速手段而言，可分为6个主要类别：基于分布式、基于采样化、基于近似模糊、基于快速近邻、基于空间划分以及基于GPU加速技术.根据该分类，对现有工作进行了深入梳理与交叉比较，发现采用多重技术的融合加速算法优于单一加速技术；近似模糊化、并行化与分布式是当前最有效的手段；高维数据仍然难以应对.此外，对快速化DBSCAN算法在多个领域中的应用进行了跟踪报告.最后，对本领域未来的方向进行了展望.

来源：2023年第9期

《计算机研究与发展》期刊编辑部

查看计算机研究与发展杂志2023年第9期