基于网格的具有周期性边界条件的DBSCAN聚类优化

《Scientific Reports》：Grid-based optimization for DBSCAN clustering with periodic boundary conditions

　　

摘要

周期边界条件（PBC）出现在科学数据和地理空间数据中，在这种情况下，传统的带噪应用密度聚类（DBSCAN）算法可能会在域边界处将簇割裂。本研究提出了一种无需副本的网格索引 DBSCAN 算法——GPDBSCAN，适用于具有周期维度的矩形域。GPDBSCAN 对周期坐标进行正则化处理，将原始样本索引至由 \(\varepsilon \) 控制的单元中，沿周期面环绕相邻单元坐标，并采用最小镜像欧氏距离来验证候选点。宽度满足 \(h\ge \varepsilon \) 的单元构建方式保证了候选点的完备性，并通过自适应策略在偏移枚举与占用单元比较之间进行选择。形式化分析表明，所得邻域和密度连通核组件与精确周期 DBSCAN 的结果等价。在代表性数据集和受控合成数据集上的实验表明，PBC-DBSCAN 与 GPDBSCAN 的聚类结果完全一致，而 GPDBSCAN 能持续降低 Python 管理的峰值内存。运行时间依赖于数据：当 PBC 副本开销较大时，GPDBSCAN 更快；而当网格候选成本占主导时，则更慢。在 17 条跨越国际日期变更线的 IBTrACS 风暴路径上，两种周期方法均实现了 ARI、NMI 和 FMI 为 1.000；GPDBSCAN 在完整子集上降低了 26.4% 的峰值内存，但需要更多运行时间。因此，当精确周期聚类和降低内存开销为首要目标时，GPDBSCAN 最为适用。