基于密度的空间聚类(DBSCAN)

概念

• Density-Based Spatial Clustering of Applications with Noise （基于密度的空间聚类）
• 相比k-means不需要预先指定聚类数量，适合任意形状的簇发现和异常检测
• 核心对象：以某点为中心，r为半径的邻域内包含的点数不小于阈值minPts
• ∈-领域的距离阈值：设定的半径r
• 直接密度可达：B在某点A的领域r内，且A是核心对象，则A-B直接密度可达
• 密度可达：A-B密度可达，B-C密度可达，则A-C密度可达，A-C也叫密度相连
• 边界点：某类的非核心对象，不能再发展下线
• 噪声点：某类对象，既不是核心对象，也不是边界对象，密度不可达，不属于任何簇的孤立点，离群点（可以做异常检测）
• 优点
  • 无需预设簇数：自动发现数据中的自然簇结构
  • 任意形状识别：能发现环形、线形等非凸形状的簇
  • 离群点检测：自动标识噪声点（标记为-1）
  • 参数简洁：仅需半径和密度阈值两个参数
• 缺点
  • 高维挑战：维度灾难问题显著,可配合降维技术使用（如PCA）
  • 参数敏感：参数选择对结果影响极大
  • 计算效率慢：可以使用数据削减策略（相似数据抽样）
  • 密度差异小时，效果不明显

步骤

• 初始化所有对象为未访问状态
• 随机选择未访问对象p并标记为已访问
• 检查的∈-邻域：
  • 若邻域点数≥minpts，创建新簇C，将p加入C
  • 否则标记为噪声点
  • 创建p的邻域集合N
  • 遍历每个邻域点：
    • 若未访问则标记为已访问，否则continue
    • 若是核心对象，将其邻域点加入当前邻域集合N
    • 若不属于任何簇，将其加入当前簇C
• 重复上述过程直到所有对象被访问

参数

• 半径的选择
  • 对每个点计算到其他点的距离并排序
  • 寻找距离序列中的突变点（如从0.12突变为0.3）
  • 取突变点前的距离作为的参考值
• minpts的选择
  • k-距离中的k值