Press "Enter" to skip to content

聚类算法DBSCAN

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( D ensity- B ased S patial C lustering of A pplications with N oise,具有噪声的基于密度的聚类方法) 算法。

 

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

 

 

我在翻阅 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 与所有可达点(包含直接密度可达和间接密度可达,包含核心点与非核心点)构成一个簇。每个簇包含至少一个核心点;非核心点也可以构成簇内成员,位于簇的边界。

 

 

如上图,设定 \(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\) (包含样本点自身) 来定义空间密度;具有噪声:并不是每个样本点都会被划分到簇中,那些不满足密度定义的点称为离群点或噪声

 

实现步骤

 

原始算法

 

算法原理比较简单,原始算法伪码表示:

 

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 是无监督聚类算法,不需要标记样本分类
相较于其他聚类算法 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 实例

 

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

 

 

参考

kdd
DBSCAN WIKI
A density-based algorithm for discovering clusters in large spatial databases with noise
DBSCAN Revisited, Revisited:Why and How You Should (Still) Use DBSCAN
DBSCAN 算法可视化
DBSCAN聚类算法——机器学习(理论+图解+python代码)
Demo of DBSCAN clustering algorithm

Be First to Comment

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注