The quiter you become,the more you are able to hear!

聚类算法DBSCAN

Posted on Edited on

Author: geneblue

Blog: https://geneblue.github.io/

背景

1996年，德国慕尼黑大学(LMU Ludwig Maximilians University of Munich)的 Martin Ester(助理教授) 和 Hans-Peter Kriegel(教授) 与博士生 Jörg Sander，Xiaowei Xu一起发表了他们在数据挖掘领域的最新研究 DBSCAN(Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法) 算法。

原版论文 A density-based algorithm for discovering clusters in large spatial databases with noise 最初发表在 1996 年的 KDD（专注数据挖掘，知识发现领域的计算机会议）上。算法 DBSCAN 在 2014 年的会议上授予了经受住时间考验的赞誉，表明该算法在理论和实践中都长期获得很大关注。这一点，我们从论文他引次数上也能看出来：

dbscan-paper

我在翻阅 DBSCAN 相关论文时发现了一件趣事。在 SIGMOD 2015 上，有一篇名为 DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation 的论文获得了当年的最佳论文奖。这篇文章主要讲 DBSCAN 算法复杂度并不像 96 版论文说的那样为 \(O(n\log{n})\), 在高纬数据集中，实际需要 \(O(n^2)\) 的复杂度，n 是样本数量。然后他们改进了 DBSCAN 算法，称为 \(\rho-approximate\) DBSCAN，改进后，算法复杂度可以降低到 \(O(n)\)，并且确信 \(\rho-approximate\) DBSCAN 可以在工业上替换掉 DBSCAN。DBSCAN 的原四位作者在看了上述文章后，发现文章已经被 SIGMOD 2015接收，觉得有必要指出文中的夸大和误导，而且文章中描述的方法仅适用欧几里得距离并且没有选择合适的 \(\epsilon\) 参数。于是发表了一篇 DBSCAN Revisited, Revisited:Why and How You Should (Still) Use DBSCAN 的文章作为对上述文章的回应:joy:。

Clustering 简介

Clustering 聚类算法是无监督学习的一种。聚类算法会将数据集划分成指定的群组或簇，让相同群组内的数据成员在指定的一些维度上具有相似属性(相近性)，不同群组的数据成员在同样的维度上属性不同。换句话说，聚类算法会按照维度相近程度将数据集划分成不同的簇。

Clustering 算法目前有 5 种常见类别：

  • Connectivity-based clustering（基于连通性的聚类）：基于整个数据集对象间距离计算的聚类方法，近邻点比更远距离的点更具有相关性。
  • Centroid-based clustering（基于质心的聚类）：计算每个簇的中心向量，以此来确定每个样本所属的类别
  • Distribution-based clustering（基于分布的聚类）：同一簇内的数据点满足相同的分布（正态分布或高斯分布）
  • Density-based clustering（基于密度的聚类）：在数据空间中，搜索不同数据密度的空间区域，然后将不同密度的区域分开，同一区域内的数据点归为同一个簇
  • Grid-based clustering（基于网格的聚类）：通过扫描数据集，将数据空间根据所选属性划分为数个网格单元，并将样本点划分到相应的单元中，最后根据单元的密度形成簇，这种方法在低维空间中比较有效，而且只需通过扫描一遍数据集，就可以得到每个单元格中样本点的分布情况

DBSCAN 思想与实现

主要思想

密度聚类算法的核心思想是如何描述数据集的密度。DBSCAN 使用一组参数 \((\epsilon, minPts)\) 来描述密度。\(\epsilon\) 是选定点的空间半径阈值，\(minPts\) 是半径 \(\epsilon\) 下最小包含的样本数阈值。这种根据数据点近邻数来定义空间密度的方式，无需事先指定簇的数量，并且可以找出空间中形状不规则的簇。

假设需要对一组空间数据集 D 进行聚类。定义参数 \(\epsilon\) 为样本点的半径，半径内的其他样本点为该点的邻域点。在 DBSCAN 算法中，所有样本点被分类为三种：核心点，可达点，离群点（噪声）:

  • 点 p 满足核心点的条件：在 \(\epsilon\) 半径内，包含 p 在内，至少要满足 \(minPts\) 个样本点，这些样本点称为近邻点, 此时 p 称为核心点。表达式： \(N_{Eps}(p) = \lbrace q\in{D}|dist(p,q)\leq\epsilon \rbrace\)
  • 点 q 从点 p 密度直达的条件：点 q 在核心点 p 的可达半径 \(\epsilon\) 内，此时称点 q 从核心点 p 直接密度可达
  • 点 q 从点 p 密度可达的条件：在路径 \(p_1\),...,\(p_n\) 中，对于每个 \(p_{i+1}\) 都是从 \(p_i\) 直接可达的话，就表明除了点 q，初始点和路径上的所有点都是核心点。q 点是簇的边界，可以称为边界点
  • 所有其他从核心点不可达的样本点称为离群点或噪声

设定 p 为核心点，则 p 与所有可达点(包含直接密度可达和间接密度可达，包含核心点与非核心点)构成一个簇。每个簇包含至少一个核心点；非核心点也可以构成簇内成员，位于簇的边界。

DBSCAN-Illustration.svg

如上图，设定 \(minPts\) 为 4，红圈内的所有红点为核心点，因为在半径 \(\epsilon\) 内，他们的邻域点 >= 4，满足 \(minPts\) 条件；B，C 两个黄色点为边界点，从核心点可以到达 B，C两点，但从 B，C无法再到达其他样本点；没有任何点可以在满足 \(\epsilon\) 和 \(minPts\) 两个条件下到达点 N，所以点 N 被判定为离群点或噪声。

DBSCAN 中路径可达是不具备对称性的，从核心点可以到达非核心点，但从非核心点不可到达任何其他点。但 DBSCAN 中定义的密度连接(density-connected)具有对称性：如果 p 和 q 均从 o 点可达，则称 p 和 q 是密度连接的。

簇满足两个属性：

  • 簇内所有点都是互相密度连接的
  • 如果一个点从一个簇内的其中一个点可以密度可达，则这个点也属于这个簇

通过以上，我们可以理解 DBSCAN 中基于密度和具有噪声这两个关键词的含义。基于密度：用空间半径 \(\epsilon\) 和最小邻域点个数 \(minPts\)(包含样本点自身) 来定义空间密度；具有噪声：并不是每个样本点都会被划分到簇中，那些不满足密度定义的点称为离群点或噪声

实现步骤

原始算法

算法原理比较简单，原始算法伪码表示： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
RangeQuery(DB, distFunc, Q, eps) {
    Neighbors N := empty list
    for each point P in database DB {                      /* Scan all points in the database */
        if distFunc(Q, P) ≤ eps then {                     /* Compute distance and check epsilon */
            N := N ∪ {P}                                   /* Add to result */
        }
    }
    return N
}

DBSCAN(DB, distFunc, eps, minPts) {
    C := 0                                                  /* Cluster counter */
    for each point P in database DB {
        if label(P) ≠ undefined then continue               /* Previously processed in inner loop */
        Neighbors N := RangeQuery(DB, distFunc, P, eps)     /* Find neighbors */
        if |N| < minPts then {                              /* Density check */
            label(P) := Noise                               /* Label as Noise */
            continue
        }
        C := C + 1                                          /* next cluster label */
        label(P) := C                                       /* Label initial point */
        SeedSet S := N \ {P}                                /* Neighbors to expand */
        for each point Q in S {                             /* Process every seed point Q */
            if label(Q) = Noise then label(Q) := C          /* Change Noise to border point */
            if label(Q) ≠ undefined then continue           /* Previously processed (e.g., border point) */
            label(Q) := C                                   /* Label neighbor */
            Neighbors N := RangeQuery(DB, distFunc, Q, eps) /* Find neighbors */
            if |N| ≥ minPts then {                          /* Density check (if Q is a core point) */
                S := S ∪ N                                  /* Add new neighbors to seed set */
            }
        }
    }
}

DBSCAN 只需要两个基本参数：\((\epsilon, minPts)\)，基本步骤为：

  • 从数据集 DB 中随机选择一个之前从未标记过的样本点 P，计算 P 所有满足半径 \(\epsilon\) 条件下的近邻 N
  • 如果 P 的近邻数 \(< minPts\)，则将 P 标记为噪音 noise，返回步骤 1 重新选取样本点
  • 如果 P 的近邻数 \(\geq minPts\)，则将 P 标记为一个新的簇 C
  • 对 P 的所有近邻进行展开 S，依次遍历近邻点 Q。如果 Q 之前被标记为 noise，则重置标记为 C；如果 Q 之前被标记为其他簇，则跳过取下一个近邻点；其他情况 Q 被标记为簇 C，并对 Q 继续计算近邻，如果近邻数 \(\geq minPts\)，则将近邻添加到 S 中，加入遍历流程。这样，知道达到极限条件，C 不在增长。
  • 从步骤1继续重复

简要算法

可以将聚类过程简要为以下三步骤：

  • 找到数据集 DB 中每个点的近邻点，并且根据 \(minPts\) 标记出所有核心点
  • 忽视所有非核心点，利用图的连通算法，将所有核心点邻边相连成不同部分，组成不同簇
  • 对于剩下的非核心点，如果满足与相邻簇距离 \(\leq \epsilon\) 则标记为对应簇；否则，标记为噪音

原始算法只需要对数据集 DB 整体遍历一次，相比较简要算法，原始算法更加节省内存。

DBSCAN 过程动图

限定 \((\epsilon, minPts)\) 后，DBSCAN 聚类动图过程，visualizing-dbscan：

dbscan-01

dbscan-02

dbscan-03

dbscan-04

dbscan-05

dbscan-06

dbscan-07

dbscan-08

算法优劣

优点

  • DBSCAN 是无监督聚类算法，不需要标记样本分类
  • 相较于其他聚类算法 DBSCAN 不需要事先指定簇数量 k，完全有密度决定最终的簇数量
  • DBSCAN 可以处理噪声数据，对异常点具有比较好的鲁棒性，另一方面，这些噪音点也可以被认为是异常点
  • DBSCAN 只需要两个参数 \((\epsilon, minPts)\)，并且对簇内样本点次序不敏感
  • DBSCAN 能够发现任意大小和形状的簇，并且具有较强的抗噪性，不受噪声和离群点的影响
  • DBSCAN 不需要对数据有特殊的专家知识，但对数据有专家经验的情况下，可以更好的设置合适的 \((\epsilon, minPts)\)

缺点

  • DBSCAN 并不是确定性算法，因为数据处理过程具有随机性，对同样的样本数据多次做 DBSCAN 运算，得到的结果不一定完全相同，对于边界非核心点，在前后两次处理后，可能会被划分到不同的簇。但核心点和噪声，多次处理，结果是相同的。
  • DBSCAN 的算法复杂度依赖空间样本点的距离计算 \(dist(p,q)\)，一般常用欧几里得距离。当计算是否是核心点时，需要扫描整个数据集查找满足参数的样本点，在高纬数据下，更加提升计算的复杂度(Curse of dimensionality)。采用欧氏距离的算法大多都会有这个问题。
  • DBSCAN 不能处理所有的聚类问题，这里对簇的定义是基于密度的，但在一些分类场景下，我们对簇的定义可能不单单从密度去考量，簇内成员的空间距离可能会很大，这时候就较难选取合适的参数。
  • DBSCAN 在设置参数时就假设了最终所有簇的密度都是相似的，但在实际中，不同簇，密度可能不同
  • DBSCAN 会合并明显分离的簇，只要簇满足密度条件就会被合并

DBSCAN 这种基于密度的聚类方法在使用的时候有个前提，样本的类别是由样本的分布密度决定的，同一簇下的样本，他们在空间分布下更为紧密。

scikit-learning 实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import numpy as np

from sklearn.cluster import DBSCAN
from sklearn import metrics
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler

import matplotlib.pyplot as plt


if __name__ == '__main__':

    centers = [[1, 1], [-1, -1], [1, -1]]
    X, labels_true = make_blobs(n_samples=800, centers=centers, cluster_std=0.4, random_state=0)

    # 特征去均值和归一化，计算距离类的算法经常要这样预处理，这样在计算距离时更高效，
    X = StandardScaler().fit_transform(X)

    db = DBSCAN(eps=0.1, min_samples=4).fit(X)

    # db.labels_ 是对所有的数据样本运算后打的 cluster 标签，-1 表示 noise
    # db.core_sample_indices_ 是核心点的 index 数组

    # 新建一个置0的同样数组，标记核心点
    core_samples_mask = np.zeros_like(db.labels_, dtype=bool)
    core_samples_mask[db.core_sample_indices_] = True
    labels = db.labels_

    # 簇数量
    n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)
    # 噪音数量
    n_noise_ = list(labels).count(-1)

    print("Estimated number of clusters: %d" % n_clusters_)
    print("Estimated number of noise points: %d" % n_noise_)
    print("Homogeneity: %0.3f" % metrics.homogeneity_score(labels_true, labels))
    print("Completeness: %0.3f" % metrics.completeness_score(labels_true, labels))
    print("V-measure: %0.3f" % metrics.v_measure_score(labels_true, labels))
    print("Adjusted Rand Index: %0.3f" % metrics.adjusted_rand_score(labels_true, labels))
    print(
        "Adjusted Mutual Information: %0.3f"
        % metrics.adjusted_mutual_info_score(labels_true, labels)
    )
    print("Silhouette Coefficient: %0.3f" % metrics.silhouette_score(X, labels))

    unique_labels = set(labels)
    colors = [plt.cm.Spectral(each) for each in np.linspace(0, 1, len(unique_labels))]
    for k, col in zip(unique_labels, colors):
        if k == -1:
            # Black used for noise.
            col = [0, 0, 0, 1]

        class_member_mask = labels == k

        xy = X[class_member_mask & core_samples_mask]
        plt.plot(
            xy[:, 0],
            xy[:, 1],
            "o",
            markerfacecolor=tuple(col),
            markeredgecolor="k",
            markersize=14,
        )

        xy = X[class_member_mask & ~core_samples_mask]
        plt.plot(
            xy[:, 0],
            xy[:, 1],
            "o",
            markerfacecolor=tuple(col),
            markeredgecolor="k",
            markersize=6,
        )

    plt.title("Estimated number of clusters: %d" % n_clusters_)
    plt.show()

    pass

dbscan-example-01

参考