DBSCAN

定义

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)由 Ester、Kriegel 等人于 1996 年提出,是基于密度的聚类代表算法,2014 年获 KDD 时间检验奖。

原理

算法由两个参数驱动:邻域半径 eps 与最小点数 minPts。邻域内点数不少于 minPts 的点称为核心点;由核心点出发通过密度可达关系不断扩张,形成一个簇;既非核心点又不在任何核心点邻域内的样本被标记为噪声。整个过程不需要预先指定簇的数量。

优点

能发现任意形状(如环形、月牙形)的簇,对离群点鲁棒且能显式输出噪声标签,这些都是 K-means 难以做到的。

局限

对 eps 和 minPts 敏感,密度差异悬殊的数据难以用一组全局参数处理(改进算法 OPTICS、HDBSCAN 针对此问题);高维空间中距离趋同也会削弱密度定义的有效性。

应用

常用于地理空间数据分析、异常检测和图像分割。