DBSCAN (Density-Based Spatial Clustering of Applications with Noise) 是一种常用于空间数据聚类的算法。它基于以下两个重要概念：

密度

给定一个半径 $\varepsilon$ 和一个点 $p$，密度表示在以 $p$ 为中心，半径为 $\varepsilon$ 的圆内包含的点的数量。

核心点和边界点

  • 核心点：若一个点 $p$ 的密度大于等于某个阈值（即包含至少 MinPts 个点），则 $p$ 是一个核心点。
  • 边界点：若一个点 $p$ 的密度小于阈值，但它落在某个核心点的 $\varepsilon$ 邻域内，则 $p$ 是一个边界点。
  • 噪声点：既不是核心点也不是边界点的点被认为是噪声点。

基本步骤

  1. 初始化：选择一个未被访问的点，检查其邻域内的点数目是否满足密度要求。
  2. 生长：若该点为核心点，则从该点出发探索其密度可达的点，并将其加入同一个簇中。
  3. 扩展：继续生长过程，直到无法找到更多的密度可达点。
  4. 标记：将所有被访问过的点标记为属于某个簇，而未被访问的点则被标记为噪声点。

DBSCAN 算法的优势在于它能够发现任意形状的簇，对噪声和离群点具有较强的鲁棒性。但它对于参数的选择相对敏感，特别是对于密度阈值和邻域大小的选择需要进行一定的调参。