DBSCAN 聚类

作者: 魏允臣 | 来源:发表于2019-01-26 18:47 被阅读0次

以下使用`Out[数字]:`的方式表示代码输出结果

Out[数字]:
代码输出

DBSCAN 密度聚类算法

密度聚类是一类常用并且有效的聚类方法，通过评估样本的紧密程度来划分对应的类别，理论上可以找出任何形状的聚类，包括非凸（non-convex）数据。除此之外，密度聚类不需要事先知道要形成的簇类的数量，还能有效识别噪声点。
密度聚类算法中最为常用的就属 DBSCAN 算法了，DBSCAN 是英文 Density-based spatial clustering of applications with noise 的缩写，直译过来就是「具有噪声的基于密度的聚类方法」。这种方法是由 Martin Ester 等在 1996 年提出。
相比其他的聚类方法，DBSCAN 的显著优点是可以在有噪音的数据中发现形状与大小各异的类别。另外，相比于划分聚类方法，DBSCAN 不需要预先声明聚类数量，这一点和层次聚类非常相似。

DBSCAN 聚类原理

DBSCAN 作为一种典型的密度聚类方法，它的聚类原理当然是和密度有关。简单来讲，DBSCAN 一般假定样本的类别可以通过样本分布的紧密程度决定，于是先发现密度较高的点，然后把相近的高密度点逐步连成一片，进而找到不同的类别（簇）。

DBSCAN 具体的运作过程

首先，DBSCAN 会以各数据点为圆心，以 $eps$ （ $\varepsilon$ -邻域）为半径画圆。
然后，DBSCAN 会计算相应圆中有多少个其他点，并以该数目作为圆心数据点的密度值。
接下来，我们需要确定密度阈值 MinPts，并分别将小于或大于该密度阈值的数据点（包含自己）称作低密度或高密度点（核心点）。
如果，此时有一个高密度的点在另一个高密度的点的圆圈范围内，我们就把这两个点串联起来。
之后，如果有低密度的点也在高密度的点的圆圈范围内，也将其连接到最近的高密度点上，并称之为边界点。
下面根据一个图示来详细阐述该过程

如上图所示，假设我们指定密度阈值 MinPts = 4，那么图中的红色点就是核心点，因为它们的 $\varepsilon$ -邻域里包含最少 4 个点（包括自己），由于它们之间相互可达，它们形成了一个聚类。图中蓝色的点不是核心点，但它们在核心点的圆圈内，所以也属于同一个聚类，也就是边界点。而紫色点既不是核心点，又不是边界点，即被称之为异常点。

DBSCAN 相关定义

首先，我们假设样本集是 $D=(x_1,x_2,\cdots,x_m)$ ，则 DBSCAN 中相关的定义描述如下：

$\varepsilon$ -邻域：

对于 $x_j \in D$ ，其 $\varepsilon$ -邻域包含样本集 $D$ 中与 $x_j$ 的距离不大于 $\varepsilon$ 的子样本集，即
$N_{\epsilon}(x_j) = \{x_i \in D| distance(x_i, x_j) \leq \epsilon\},$
这个子样本集的个数记为 $|N_{\epsilon}(x_j)|$ 。

核心对象（核心点）：

对于任一样本 $x_j \in D$ ，如果其 $\varepsilon$ -邻域对应的 $N_{\epsilon}(x_j)$ 至少包含 $MinPts$ 个样本，即如果
$|N_{\epsilon}(x_j)| \geq MinPts，$
则 $x_j$ 是核心对象。

密度直达：

如果 $x_i$ 位于 $x_j$ 的 $\varepsilon$ -邻域中，且 $x_j$ 是核心对象，则称 $x_i$ 由 $x_j$ 密度直达。注意反之不一定成立，即此时不能说 $x_j$ 由 $x_i$ 密度直达, 除非 $x_i$ 也是核心对象。

密度可达：

对于 $x_i$ 和 $x_j$ ，如果存在样本序列 $p_1, p_2,\cdots,p_t$ ，满足 $p_1=x_i$ , $p_t=x_j$ , 且 $p_{k+1}$ 由 $p_k$ （其中 $k = 1, 2, \cdots, t-1$ ）密度直达，则称 $x_j$ 由 $x_i$ 密度可达。也就是说，密度可达满足传递性。此时序列中的传递样本 $p_1, p_2,\cdots,p_{t-1}$ 均为核心对象，因为只有核心对象才能使其他样本密度直达。

密度相连：

对于 $x_i$ 和 $x_j$ ，如果存在核心对象样本 $x_k$ ，使 $x_i$ 和 $x_j$ 均由 $x_k$ 密度可达，则称 $x_i$ 和 $x_j$ 密度相连。注意密度相连关系是满足对称性的。

另外，关于确定某样本是否在核心样本的 $\varepsilon$ -邻域内，其实也就是二者之间距离度量的问题，我们一般可以使用欧式距离计算。其实你会发现，这里 $\varepsilon$ -邻域确定了一个圆，而这就类似于 K-近邻算法中找最近邻的 K 个点的情形。

DBSCAN 聚类算法 Python 实现

实现 DBSCAN 聚类过程前，我们同样需要先生成一组示例数据。这里用到了 make_moons 方法。

import numpy as np
from sklearn import datasets
from matplotlib import pyplot as plt
%matplotlib inline

# 生成 100 个样本并添加噪声
noisy_moons, _ = datasets.make_moons(n_samples=100, noise=.05, random_state=10) 
noisy_moons[:5]

Out[2]:
array([[ 0.2554364 ,  0.90420806],
       [ 0.55299636,  0.84445141],
       [-0.90343862,  0.39161309],
       [-0.62792219,  0.62502915],
       [ 0.60777269, -0.33777687]])

plt.scatter(noisy_moons[:,0], noisy_moons[:,1])

从上图可以看出，虽然数据点的分布比较奇怪，但肉眼观察明显呈现出 2 类

image

此时，我们尝试使用划分聚类中的 K-Means 和层次聚类中的 BIRCH 方法来尝试对上面的数据集进行聚类，这两种方法是划分和层次聚类法中的代表，这里为了方便直接使用 scikit-learn 实现。

from sklearn.cluster import KMeans, Birch

kmeans_c = KMeans(n_clusters=2).fit_predict(noisy_moons)
birch_c = Birch(n_clusters=2).fit_predict(noisy_moons)

fig, axes = plt.subplots(nrows=1, ncols=2, figsize=(15, 5))
axes[0].scatter(noisy_moons[:,0], noisy_moons[:,1], c=kmeans_c, cmap='bwr')
axes[1].scatter(noisy_moons[:,0], noisy_moons[:,1], c=birch_c, cmap='bwr')
axes[0].set_xlabel('K-Means')
axes[1].set_xlabel('BIRCH')

K-Means 和 BIRCH 方法无法对上面的示例数据正确聚类。面对这种凹状数据集，划分和层次聚类法往往都无法正确聚类，此时需要用到密度聚类方法。
下面，我们使用 Python 实现 DBSCAN 密度聚类算法
首先，我们实现一个 search_neighbors() 函数，这个函数的目的是找出核心点周围可到达的数据点。
其中，计算距离的方式使用欧式距离。

"""欧式距离
"""
def euclidean_distance(a, b):
    """
    参数:
    a -- 数组 a
    b -- 数组 b
    
    返回:
    dist -- a, b 间欧式距离
    """
    x = float(a[0]) - float(b[0])
    x = x * x
    y = float(a[1]) - float(b[1])
    y = y * y
    dist = round(np.sqrt(x + y), 2)
    return dist

"""找出数据集中距核心点 P 在 eps 范围内的邻近点
"""
def search_neighbors(D, P, eps):
    """
    参数:
    D -- 数据集（二维数组）
    P -- 核心点
    eps -- eps 邻域
    
    返回:
    neighbors -- 核心点在 eps 范围内的邻居
    """
    neighbors = []
    for Pn in range(0, len(D)):
        # 距离判断是否在 eps 范围内
        if euclidean_distance(D[P], D[Pn]) < eps:
            neighbors.append(Pn)
            
    return neighbors

接下来实现 DBSCAN 的主体代码：

"""DBSCAN 密度聚类算法
"""
def dbscan_cluster(D, eps, MinPts):
    """
    参数:
    D -- 数据集（二维数组）
    eps -- eps 邻域
    MinPts -- 密度阀值

    返回:
    labels -- 聚类标签
    """
    labels = [0]*len(D)  # 初始化数据集中的数据类别全部为 0
    C = 0
    # 选择 P 作为核心点
    for P in range(0, len(D)):

        # 选择类别为 0 的点作为中心
        if not (labels[P] == 0):
            continue

        # 搜寻该数据点在 eps 圆中的邻居
        Neighbors = search_neighbors(D, P, eps)

        # 标记噪声点为 -1
        if len(Neighbors) < MinPts:
            labels[P] = -1

        # 非噪声点作为新类别中心
        else:
            C += 1  # 原类别 +1 作为新类别的标签
            labels[P] = C  # 将非噪声点设定为新类别

            # 开始检查 P 在 eps 圆中邻居的可达性
            for i, n in enumerate(Neighbors):
                Pn = Neighbors[i]  # 从 P 的邻居中取 1 个点

                # P 的邻居，设定为一样的类别
                if labels[Pn] == 0:
                    labels[Pn] = C

                    # 进一步搜索 P 的邻居的邻居
                    PnNeighbors = search_neighbors(D, Pn, eps)
                    if len(PnNeighbors) >= MinPts:  # 如果满足密度阈值要求则连通
                        Neighbors += PnNeighbors

                # 如果该点曾被标记为噪声点, 则重新连接到类别中
                elif labels[Pn] == -1:
                    labels[Pn] = C

    return labels

然后使用 DBSCAN 算法对上面的月牙形示例数据进行聚类，得到聚类标签。这里设定 εε -邻域的值为 0.5，而密度阈值 MinPts=5，即半径为 0.5 的圆内至少有 5 个其他点才能被看作是核心点。

dbscan_c = dbscan_cluster(noisy_moons, eps=0.5, MinPts=5)
np.array(dbscan_c) # 显示聚类标签

Out[8]:
array([1, 1, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 2, 2, 2, 1, 2, 1, 2, 2,
       2, 1, 2, 2, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2,
       1, 2, 1, 2, 2, 1, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 1, 1, 2, 2, 1, 1,
       2, 2, 1, 2, 1, 2, 1, 2, 1, 1, 2, 2, 2, 2, 1, 2, 2, 1, 2, 2, 1, 1,
       1, 1, 1, 2, 1, 1, 2, 2, 1, 2, 1, 1])

依照 DBSCAN 算法得到的聚类标签，重新对散点图进行着色，查看聚类效果。

plt.scatter(noisy_moons[:,0], noisy_moons[:,1], c=dbscan_c, cmap='bwr')

如上图所示，DBSCAN 聚类结果符合我们的心理预期，同时弥补了划分和层次聚类的不足。

DBSCAN 聚类算法 scikit-learn 实现

sklearn.cluster.DBSCAN(eps=0.5, min_samples=5, metric='euclidean', metric_params=None, algorithm='auto', leaf_size=30, p=None, n_jobs=1)

其中，主要参数有：

eps: 即 $\varepsilon$ -邻域的值。
min_samples: 即密度阈值 MinPts 的值。
metric: 距离度量方式，默认为欧式距离。
algorithm：近邻算法求解方式：auto, ball_tree, kd_tree, brute 可选。

对示例数据完成聚类:

from sklearn.cluster import DBSCAN

dbscan_sk = DBSCAN(eps=0.5, min_samples=5, metric='euclidean')
dbscan_sk_c = dbscan_sk.fit_predict(noisy_moons)
dbscan_sk_c

array([0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1,
       1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
       0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0,
       1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0,
       0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0])

依照得到的聚类标签，重新对散点图进行着色，查看聚类效果。

plt.scatter(noisy_moons[:,0], noisy_moons[:,1], c=dbscan_sk_c, cmap='bwr')

聚类结果和使用 Python 手动实现的算法计算结果一模一样

DBSCAN 聚类

以下使用`Out[数字]:`的方式表示代码输出结果

DBSCAN 密度聚类算法

DBSCAN 聚类原理

DBSCAN 具体的运作过程

DBSCAN 相关定义

DBSCAN 聚类算法 Python 实现

DBSCAN 聚类算法 scikit-learn 实现

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

DBSCAN 聚类

以下使用Out[数字]:的方式表示代码输出结果

DBSCAN 密度聚类算法

DBSCAN 聚类原理

DBSCAN 具体的运作过程

DBSCAN 相关定义

DBSCAN 聚类算法 Python 实现

DBSCAN 聚类算法 scikit-learn 实现

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

以下使用`Out[数字]:`的方式表示代码输出结果