DBSCAN 算法-工具盒子

DBSCAN （Density-Based Spatial Clustering of Applications with Noise）算法是一种基于密度的聚类算法，相比 Kmeans 算法，DBSCAN 可以有效处理噪声，并且能够发现任意形状的簇。

DBSCAN 算法中有两个超参数：

ε（epsilon）表示样本点邻域的半径；
M 表示核心点的样本阈值。例如：如果一个样本在它的邻域范围内存在至少 M 个样本的话，当前样本被称作核心点。

算法的流程如下：

第一阶段初始化:

计算每个样本的邻域 N
令 k=1, \(m_i = 0\)，初始化待处理样本集合 I={1, 2, 3 ... N}

第二阶段生成所有的簇：

循环，当 I 不为空
1. 从 I 中取出一个样本 i，并将其从集合 I 中删除
2. 如果 i 没有被处理过，即 \(m_i=0\)
  1. 初始化集合 T = \(N(x_i)\)
  2. 如果 i 为非核心点
    - 令 \(m_i=-1\) 暂时标记为噪声
  3. 如果 i 为核心点
    1. 令 \(m_i=k\)，将当前簇的编号赋予该样本
    2. 循环，当 T 不为空
      1. 从集合 T 中取出一个样本 j，并从该集合中将其删除
      2. 如果 \(m_j=0\) 或者 \(m_j=-1\)，则 \(m_j=k\)
      3. 如果 j 是核心点，将 j 的邻居集合 \(N(x_j)\) 加入到集合 T 中
    3. 结束循环
    4. 令 k = k + 1
结束循环

DBSCAN 算法无须指定簇的数量，其也可以发现任意形状的簇，并且对噪声不敏感。缺点是其效果受 2 个超惨 ε 和 M 的影响很大。

scikit-learn 中有 DBSCAN 算法的实现：

from sklearn.cluster import DBSCAN
from sklearn.datasets import make_circles
import matplotlib.pyplot as plt


if __name__ == '__main__':

    x, y_true = make_circles(n_samples=500, noise=0.08, factor=0.5, random_state=0)
    plt.scatter(x[:, 0], x[:, 1], c=y_true)
    plt.show()

    # 设置超参数 epsilong=0.15, M=5
    model = DBSCAN(eps=0.15, min_samples=3)
    y_pred = model.fit_predict(x)
    plt.scatter(x[:, 0], x[:, 1], c=y_pred)
    plt.show()

    # 每个训练样本的预测标签
    # label = -1 的点为模型标记的噪声点
    print(model.labels_)

程序输出结果：

左侧为真实样本，右侧为 DBSCAN 预测结果

[ 0  1  1  1  1  0  1  1  0  0  0  1  1  1  0  1  1  1  0  0  0  1  0  0
  0  1  0  1  0  0  1  0  0  0  1  1  1  1  1  0  1  0  1  0  0  0  0  1
  1  0  1  0  1  0  0  0  1  0  0  1  0  1  1  1  1  0  0  1  1  0  0  0
  1  1  0  1  1  0  1  1  1  0  1  0  1  1  1  0  1  0  0  1  1  0  0  1
 -1  1  0  0  0  1  0  1  0  1  0  0  1  0  1  0  0  0  1  1  1  1  0  0
  1  0  0  1  1  0  0  1  1  1  1  0  1  0  1  1  1  1  1  0  0  0  0  0
  1  0  1  1  0  0  0  1  0  1  0  0  0  0  1  0  1  0  0  1  0  0  1  1
  1  1  1  0  1  1  1  0  1  0  1  1  1  0  0  1  0  1  1  1  1  0  1  1
  0  1  1  1  1  0  0  0  0  0  0  1  0  1  0  1  0  1  1  0  0  1  0  1
  0  0  0  1  0  0  0  0  1  1  0  0  0  0  1  0  1  0  1  1  1  0  0  1
  0  0  1  1  1  1  1  0  0  0  1  0  0  0  0  0  0  0  1  0  0  0  1  0
  1  1  1  0  0  1  1  0  1  1  0  0  0  1  1  1  0  1  0  0  0  0  1  0
  0  0  0  0  0  0  1  1  0  1  1  0  1  1  0  1  1  1  0  0  0  1  1  0
  0  0  0  1  0  1  0  0  1  1  1  1  1  0  1  0  1  1  1  0  1  0  1  0
  1  1  0  0  1  1  1  1  1  0  1  0  1  1  0  1  0  1  0  1  0  0  1  0
  0  1  1  1  0  0  0  1  0  0  0  0  1  0  0  1  1  0  1  1  1  0  1  1
  0  1  0  1  0  0  1  0  1  1  0  1  0  0  0  1  0  1  0  1  1  1  1  0
  0  0  1  1  1  1  1  0  0  1  0  1  1  0  1  1  1  1 -1  0  1  1  1  1
  0  1  0  1  1  0  1  0  0  1  0  0  0  0  0  0  0  0  1  1  1  1  1  1
  0  1  1  0  0  1  1  1  1  0  0  1  0  1  1  0  1  0  0  1  1  0  1  0
  0  1  1  0  1  0  0  1  0  1  0  0  1  0  1  1  0  0  0  0]

从这个实验中，也看到了稍微改动下 eps 和 min_samples 参数，结果变化很大。另外 scikit-learn 的 DBSCAN 并没有 predict 方法，即：无法对新的样本做出预测。我们也可以通过 DBSCAN 帮我们去分析样本中的离群点。