logo

基于密度的聚类

wangzf / 2022-11-22

目录

DBSCAN

算法原理介绍

基本原理

DBSCAN (Density-Based Spatial Clustering of Applications with Noise)是一种基于密度的聚类算法， 其可以有效地发现任意形状的簇，并能够处理噪声数据。DBSCAN算法的核心思想是：对于一个给定的数据点， 如果它的密度达到一定的阈值，则它属于一个簇中；否则，它被视为噪声点

DBSCAN算法的优点是能够自动识别簇的数目，并且对于任意形状的簇都有较好的效果。并且还能够有效地处理噪声数据， 不需要预先指定簇的数目。缺点是对于密度差异较大的数据集，可能会导致聚类效果不佳，需要进行参数调整和优化。 另外该算法对于高维数据集的效果也不如其他算法

DBSCAN (Density-Based Spatial Clustering of Application with Noise)，具有噪声的基于密度的聚类方法。 是一种基于密度的空间聚类算法。该算法将具有足够密度的区域划分为簇，并在具有噪声的空间数据库中发现任意形状的簇， 它将簇定义为密度相连的点的最大集合。使用 DBSCAN 进行聚类的时候, 不需要预先指定簇的个数, 最终的簇的个数不确定

举例解释

下面这些点是分布在样本空间的众多样本，现在的目标是把这些在样本空间中距离相近的聚成一类。 发现 A 点附近的点密度较大，红色的圆圈根据一定的规则在这里滚啊滚，最终收纳了 A 附近的 5 个点， 标记为红色也就是定为同一个簇。其它没有被收纳的根据一样的规则成簇。

形象来说，可以认为这是系统在众多样本点中随机选中一个，围绕这个被选中的样本点画一个圆， 规定这个圆的半径以及圆内最少包含的样本点，如果在指定半径内有足够多的样本点在内， 那么这个圆圈的圆心就转移到这个内部样本点，继续去圈附近其它的样本点， 类似传销一样，继续去发展下线。等到这个滚来滚去的圈发现所圈住的样本点数量少于预先指定的值，就停止了。 那么称最开始那个点为核心点，如 A，停下来的那个点为边界点，如 B、C，没得滚的那个点为离群点，如 N

img

基于密度这点有什么好处呢，由于 K-Means 聚类算法只能处理球形的簇， 也就是一个聚成实心的团(这是因为算法本身计算平均距离的局限)。 但往往现实中还会有各种形状，比如下面两张图，环形和不规则形， 这个时候，那些传统的聚类算法显然就悲剧了。 于是就思考，样本密度大的成一类，这就是 DBSCAN 聚类算法

img

算法数学模型

给定数据集 $D=\{x_{1}, x_{2}, \ldots, x_{n}\}$, 定义:

基于这些概念, DBSCAN 将"簇”定义为: 由密度可达关系导出的最大的密度相连样本集合. 形式化的说: 给定邻域参数 $(\epsilon, MinPts)$, 聚类簇 $C \subseteq D$ 是满足以下性质的非空样本子集:

从数据集 $D$ 中找出满足以上性质的聚类簇：

算法伪代码

输入:

过程:

  1. 初始化核心对象集合: $\Omega=\emptyset$

  2. for $j=1, 2, \ldots, n$ do

    • 确定样本 $x_{j}$ 的 $\epsilon$-领域 $N_{\epsilon}(x_{j})$

    if $|N_{\epsilon}(x_{j})|\geqslant MinPts$ then

    • 将样本 $x_{j}$ 加入核心对象集合: $\Omega=\Omega\cup\{x_{j}\}$

    end if

    end for

  3. 初始化聚类簇数: $k=0$

  4. 初始化未访问样本集合 $\Gamma=D$

  5. while $\Omega \neq \emptyset$ do

    • 记录当前未访问样本集合 $\Gamma_{old} = \Gamma$;

    • 随机选取一个核心对象 $o\in \Omega$, 初始化队列 $Q=<o>$;

    • $\Gamma=\Gamma \setminus \{o\}$

    • while $Q \neq \emptyset$ do

      • 取出队列 $Q$ 中的首个样本 $q$;

      if $|N_{\epsilon}(q)|\geqslant MinPts$ then

      • 令 $\Delta=N_{\epsilon}(q) \cap \Gamma$;
      • 将 $\Delta$ 中的样本加入队列 $Q$;
      • $\Gamma=\Gamma \setminus \Delta$;

      end if

      end while

    • $k=k+1$, 生成聚类簇 $C_{k}=\Gamma_{old} \setminus \Gamma$;

    • $\Omega=\Omega \setminus C_{k}$

    end while

输出:

算法说明:

算法参数选择

算法迭代可视化展示

算法优劣性

优点

缺点

当数据簇密度不均匀时, 效果不如其他算法好, 这是因为当密度变化时, 用于识别邻近点的距离阈值 $\epsilon$ 和 $MinPts$ 的设置将随着簇而变化

在处理高维数据时也会出现这种缺点, 因为难以估计距离阈值 $\epsilon$

算法示例

from sklearn.cluster import DBSCAN

db = DBSCAN(eps=3, min_samples=10).fit(X)
DBSCAN_labels = db.labels_

# Number of clusters in labels, ignoring noise if present.
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_)

unique_labels = set(labels)
core_samples_mask = np.zeros_like(labels, dtype=bool)
core_samples_mask[db.core_sample_indices_] = True

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[:, -1],
        xy[:, 1],
        "o",
        markerfacecolor=tuple(col),
        markeredgecolor="k",
        markersize=6,
)

plt.title(f"Estimated number of clusters: {n_clusters_}")
plt.show()

ADBSCAN

算法介绍

算法实现

DENCLUE

算法介绍

算法实现

OPTICS

OPTICS（Ordering Points To Identify the Clustering Structure）是一种基于密度的聚类算法， 其能够自动确定簇的数量，同时也可以发现任意形状的簇，并能够处理噪声数据。 OPTICS 算法的核心思想是：对于一个给定的数据点，通过计算它到其它点的距离， 确定其在密度上的可达性，从而构建一个基于密度的距离图。然后，通过扫描该距离图， 自动确定簇的数量，并对每个簇进行划分

OPTICS算法的优点是能够自动确定簇的数量，并能够处理任意形状的簇，并能够有效地处理噪声数据。 该算法还能够输出聚类层次结构，便于分析和可视化。缺点是计算复杂度较高，尤其是在处理大规模数据集时， 需要消耗大量的计算资源和存储空间。另外就是该算法对于密度差异较大的数据集，可能会导致聚类效果不佳

OPTICS(Ordering Points To Identify the Clustering Structure) 和 DBSCAN 聚类相同, 都是基于密度的聚类, 但是, OPTICS 的好处在于可以处理不同密度的类, 结果有点像基于连通性的聚类, 不过还是有些区别的. 上段伪代码

算法原理介绍

算法数学模型

算法伪代码

算法优劣性

算法实现

from sklearn.cluster import OPTICS
import matplotlib.gridspec as gridspec

#Build OPTICS model:
clust = OPTICS(min_samples=3, min_cluster_size=100, metric='euclidean')

# Run the fit
clust.fit(X)

space = np.arange(len(X))
reachability = clust.reachability_[clust.ordering_]
OPTICS_labels = clust.labels_[clust.ordering_]
labels = clust.labels_[clust.ordering_]

plt.figure(figsize=(10, 7))
G = gridspec.GridSpec(2, 3)
ax1 = plt.subplot(G[0, 0])
ax2 = plt.subplot(G[1, 0])


# Reachability plot
colors = ["g.", "r.", "b.", "y.", "c."]
for klass, color in zip(range(0, 5), colors):
    Xk = space[labels == klass]
    Rk = reachability[labels == klass]
    ax1.plot(Xk, Rk, color, alpha=0.3)
ax1.plot(space[labels == -1], reachability[labels == -1], "k.", alpha=0.3)
ax1.set_ylabel("Reachability (epsilon distance)")
ax1.set_title("Reachability Plot")

# OPTICS
colors = ["g.", "r.", "b.", "y.", "c."]
for klass, color in zip(range(0, 5), colors):
    Xk = X[clust.labels_ == klass]
    ax2.plot(Xk[:, 0], Xk[:, 1], color, alpha=0.3)
ax2.plot(X[clust.labels_ == -1, 0], X[clust.labels_ == -1, 1], "k+", alpha=0.1)
ax2.set_title("Automatic Clustering\nOPTICS")


plt.tight_layout()
plt.show()

Mean Shift

Mean Shift Clustering 是一种基于密度的非参数聚类算法，其基本思想是通过寻找数据点密度最大的位置（称为"局部最大值"或"高峰"）， 来识别数据中的簇。算法的核心是通过对每个数据点进行局部密度估计，并将密度估计的结果用于计算数据点移动的方向和距离。 算法的核心是通过对每个数据点进行局部密度估计，并将密度估计的结果用于计算数据点移动的方向和距离

Mean Shift Clustering 算法的优点是不需要指定簇的数目，且对于形状复杂的簇也有很好的效果。 算法还能够有效地处理噪声数据。他的缺点也是计算复杂度较高，尤其是在处理大规模数据集时， 需要消耗大量的计算资源和存储空间，该算法还对初始参数的选择比较敏感，需要进行参数调整和优化

from itertools import cycle
from sklearn.cluster import MeanShift, estimate_bandwidth

# The following bandwidth can be automatically detected using
bandwidth = estimate_bandwidth(X, quantile = 0.2, n_samples = 100)

# model
ms = MeanShift(bandwidth = bandwidth)
ms.fit(X)
MS_labels = ms.labels_
cluster_centers = ms.cluster_centers_

labels_unique = np.unique(labels)
n_clusters_ = len(labels_unique)
print("number of estimated clusters : %d" % n_clusters_)

# result
plt.figure(1)
plt.clf()
colors = cycle("bgrcmykbgrcmykbgrcmykbgrcmyk")
for k, col in zip(range(n_clusters_), colors):
    my_members = labels == k
    cluster_center = cluster_centers[k]
    plt.plot(X[my_members, 0], X[my_members, 1], col + ".")
    plt.plot(
        cluster_center[0],
        cluster_center[1],
        "o",
        markerfacecolor = col,
        markeredgecolor = "k",
        markersize = 14,
)
plt.title("Estimated number of clusters: %d" % n_clusters_)
plt.show()

算法实现

R 实现聚类

R 中提供了 dbscan 包, dbscan 底层使用 C++ 编程, 并建立 kd 树的数据结构进行更快的 K 最近邻搜索, 从而实现加速. 该包提供了基于密度的有噪声聚类算法的快速实现, 包括:

函数列表:

Python 实现聚类

sklearn

import pandas as pd
from sklearn.cluster import DBSCAN
from sklearn import metrics

# data
beer = pd.read_csv("data.txt", sep = " ")
print(beer)
X = beer[["calories","sodium","alcohol","cost"]]

# model
db = DBSCAN(eps = 10, min_samples = 2).fit(X)

# result
labels = db.labels_
beer["cluster_db"] = labels
berr.sort_values("cluster_db")
print(berr.groupby("cluster_db").mean())

# 不同两个指标下样本的分布情况
pd.scatter_matrix(
    X, 
    c = colors[beer.cluster_db], 
    figsize = (10, 10), 
    s = 100
)

# 轮廓系数
score = metrics.silhouette_score(X, beer.cluster_db)
print(score)

pyclustering

参考