十大聚类算法介绍

Typora Markdown
Markdown
发布日期:   2025-02-28 
1
2
3
4
5
6
7
8
9
10
11
<head>
    <script src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML" type="text/javascript"></script>
    <script type="text/x-mathjax-config">
        MathJax.Hub.Config({
            tex2jax: {
            skipTags: ['script', 'noscript', 'style', 'textarea', 'pre'],
            inlineMath: [['$','$']]
            }
        });
    </script>
</head>

最强总结！十大聚类算法 ！！

哈喽，我是小白~

今天聊聊聚类算法。

聚类算法在机器学习实验中非常重要，因为它们能够在无监督学习场景下发现数据的内在结构和分布模式。它们广泛应用于数据预处理、特征提取以及领域探索，为后续分析和决策提供关键支持。通过聚类，研究者可以更好地理解数据的潜在类别关系，挖掘隐藏的模式和信息。

涉及到的10种最重要、最常用的算法有：

  • K-Means
  • 层次聚类
  • DBSCAN
  • Mean-Shift
  • 高斯混合模型
  • Spectral Clustering
  • OPTICS
  • Affinity Propagation
  • Birch
  • SOM

如果需要本文PDF版本的同学，文末获取~ 另外，文末有总结性的干货~ 一起来看下具体细化内容~

K-Means

K-Means 是一种广泛使用的聚类算法，用于将数据划分为 个簇，使得簇内数据点彼此更相似，而簇间数据点差异较大。它是一种无监督学习方法，主要用于探索性数据分析。

原理

K-Means 算法的核心目标是最小化数据点到其所属簇中心的欧几里得距离平方和，即 簇内离差平方和（Within-Cluster Sum of Squares, WCSS）。

算法步骤：

  1. 随机初始化 个簇中心。
  2. 将每个数据点分配到最近的簇中心。
  3. 更新簇中心为簇中所有数据点的均值。
  4. 重复步骤 2 和 3，直到簇中心不再发生显著变化或达到最大迭代次数。

核心公式

1. 距离公式（欧几里得距离）：

其中：

  • ：第 个数据点。
  • ：第 个簇中心。
  • ：数据的维度。

2. 簇内离差平方和（WCSS）：

其中：

  • ：属于簇 的数据点数目。

3. 更新簇中心：

其中：

  • ：簇 中的所有数据点集合。

公式推导

1. 目标函数：

每次迭代通过两个步骤优化：

  • 分配步骤（Assignment Step）：对每个数据点，找到最近的簇：

  • 更新步骤（Update Step）：重新计算每个簇中心：

2. 收敛性：

在每次迭代中，目标函数 的值都会减少，因此算法收敛到局部最优解。

完整案例

生成一个二维虚拟数据集，采用 K-Means 算法将数据分为 3 个簇：

1. 数据点的聚类结果：展示每个数据点的聚类类别及簇中心。

2. WCSS 收敛曲线：展示随着迭代次数的增加，目标函数 值的变化。

这些图形可以看到：

  • 聚类结果是否合理。
  • 算法收敛性是否达到预期。
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
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans

# 生成虚拟数据集
np.random.seed(42)
X, _ = make_blobs(n_samples=3000, centers=3, cluster_std=1.0, random_state=42)

# K-Means 聚类
kmeans = KMeans(n_clusters=3, init='random', max_iter=300, n_init=10, random_state=42)
kmeans.fit(X)

# 获取聚类结果
labels = kmeans.labels_
centers = kmeans.cluster_centers_
inertia = kmeans.inertia_

# WCSS 收敛曲线
inertia_values = []
kmeans_temp = KMeans(n_clusters=3, init='random', max_iter=1, n_init=1, random_state=42)
for i in range(1, 20):
    kmeans_temp.max_iter = i
    kmeans_temp.fit(X)
    inertia_values.append(kmeans_temp.inertia_)

# 绘制图像
plt.figure(figsize=(14, 6))

# 子图 1：聚类结果
plt.subplot(1, 2, 1)
for cluster_idx in range(3):
    cluster_points = X[labels == cluster_idx]
    plt.scatter(cluster_points[:, 0], cluster_points[:, 1], label=f'Cluster {cluster_idx}', s=50)
plt.scatter(centers[:, 0], centers[:, 1], c='black', marker='X', s=200, label='Centers')
plt.title('K-Means Clustering Results', fontsize=14)
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.legend()

# 子图 2：WCSS 收敛曲线
plt.subplot(1, 2, 2)
plt.plot(range(1, 20), inertia_values, marker='o', color='red', linewidth=2)
plt.title('WCSS Convergence Curve', fontsize=14)
plt.xlabel('Iterations')
plt.ylabel('WCSS')

plt.tight_layout()
plt.show()
img

1. 聚类结果图：直观显示了每个数据点的聚类类别及簇中心位置。可以用来验证簇的分布是否合理，是否符合数据的真实结构。

2. WCSS 收敛曲线：展示了目标函数的收敛过程，分析算法的收敛性。检查是否存在明显的 "肘部" 现象，帮助选择最优 值。

层次聚类

层次聚类是一种将数据点分层组织的聚类方法，最终形成一个树状的层次结构（即 聚类树 或 树状图）。它通过反复地将数据点或聚类合并或分裂，逐步构建出层次结构。

层次聚类分为两种主要方法：

1. 凝聚型（自底向上）：从每个数据点作为单独的聚类开始，不断合并最近的两个聚类。

2. 分裂型（自顶向下）：从所有数据点作为一个整体开始，不断分裂成更小的聚类。

核心原理

层次聚类的核心是通过计算数据点之间的相似性（或距离），逐步构建聚类树。

关键步骤：

1. 计算距离矩阵：计算所有数据点之间的距离（通常使用欧几里得距离）。

2. 合并/分裂策略：

  • 凝聚型：选择两个最近的聚类合并。
  • 分裂型：选择一个聚类分裂成两个子聚类。

3. 更新距离矩阵：根据新的聚类更新距离矩阵。

4. 重复步骤2和3，直到满足终止条件（例如，只有一个聚类或达到指定的层次）。

核心公式

距离计算公式（欧几里得距离）

聚类间距离（链接方法）

1. 最小距离（单链接）:

2. 最大距离（全链接）:

3. 平均距离（平均链接）:

推导

以平均链接为例，假设有两个聚类 和 ，其大小分别为 和 。当合并形成新的聚类 时，新聚类和另一个聚类 的距离可以递归计算：

这种递归关系是层次聚类高效实现的基础。

完整案例

包含数据生成、聚类分析：

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
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from scipy.cluster.hierarchy import dendrogram, linkage, fcluster
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler

# Step 1: 生成虚拟数据集
np.random.seed(42)
data, labels_true = make_blobs(n_samples=2000, centers=4, cluster_std=1.5, random_state=42)
data = StandardScaler().fit_transform(data)

# Step 2: 计算层次聚类
Z = linkage(data, method='ward')  # 使用 Ward 方法

# Step 3: 提取聚类标签
cluster_labels = fcluster(Z, t=4, criterion='maxclust')  # 指定聚类数目为 4

# Step 4: 可视化分析
fig, ax = plt.subplots(1, 2, figsize=(16, 8))

# 图1：数据点的聚类分布
scatter = ax[0].scatter(data[:, 0], data[:, 1], c=cluster_labels, cmap='tab10', s=50, alpha=0.7)
legend1 = ax[0].legend(*scatter.legend_elements(), title="Clusters")
ax[0].add_artist(legend1)
ax[0].set_title("Clustered Data Points")
ax[0].set_xlabel("Feature 1")
ax[0].set_ylabel("Feature 2")

# 图2：树状图
ax[1].set_title("Dendrogram")
dendrogram(Z, truncate_mode='level', p=6, ax=ax[1], color_threshold=0.7 * max(Z[:, 2]), above_threshold_color='gray')
ax[1].set_xlabel("Sample Index")
ax[1].set_ylabel("Distance")

plt.tight_layout()
plt.show()
img

1. 图1：数据点的聚类分布：通过颜色和空间分布直观显示每个数据点所属的聚类，便于观察聚类结果的分布情况。

2. 图2：树状图（Dendrogram）：展示了层次聚类的合并过程，显示了数据点的层次关系及相似性，可以帮助理解不同聚类之间的合并逻辑。

DBSCAN

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种基于密度的聚类算法，擅长发现形状复杂的聚类结构并能有效处理噪声点。其核心思想是基于密度连接的概念，将高密度区域的点归为一个簇，同时将低密度区域的点视为噪声。

DBSCAN 原理

1. 密度定义：

  • ϵ-邻域：以点 为中心、半径为 的圆内的所有点集合。
  • 核心点：若一个点的 -邻域内包含至少 个点，则该点为核心点。
  • 边界点：位于某核心点的 -邻域内，但其自身的 -邻域内点数少于 。
  • 噪声点：既不是核心点，也不是边界点的点。

2. 聚类过程：

  • 从任意一个未访问点开始。
  • 若该点为核心点，则将其邻域内的点加入同一个簇。
  • 对新增点的邻域重复检查，直到簇不再扩展。
  • 若点是噪声或非核心点，则跳过。

核心公式和推导

1. ϵ-邻域公式：

其中 是数据集， 是 和 之间的距离。

2. 核心点判定：

3. 密度可达性：

如果存在一个点序列 ，使得 是核心点，且 在 的 -邻域内，则称 密度可达于 。

4. 簇扩展：

每个核心点的 -邻域点都必须在同一簇中递归标记。

完整案例

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
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons, make_blobs

# 生成虚拟数据集
np.random.seed(42)
X1, _ = make_moons(n_samples=5000, noise=0.05)
X2, _ = make_blobs(n_samples=3000, centers=3, cluster_std=0.6, random_state=0)
X = np.vstack((X1, X2))

# 运行 DBSCAN
eps = 0.2
min_samples = 5
db = DBSCAN(eps=eps, min_samples=min_samples)
labels = db.fit_predict(X)

# 获取分类结果
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = list(labels).count(-1)

# 创建图形
fig, axs = plt.subplots(1, 2, figsize=(16, 6), dpi=100)

# 图1：聚类结果
unique_labels = set(labels)
colors = [plt.cm.tab10(each) for each in np.linspace(0, 1, len(unique_labels))]
for k, col in zip(unique_labels, colors):
    if k == -1:
        col = [0, 0, 0, 1]  # 噪声点为黑色
    class_member_mask = (labels == k)
    xy = X[class_member_mask]
    axs[0].plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=tuple(col), markersize=6, label=f'Cluster {k}')
axs[0].set_title(f"DBSCAN Clustering (eps={eps}, min_samples={min_samples})")
axs[0].legend(loc='best')

# 图2：簇的密度分布
axs[1].hist(labels, bins=np.arange(-1, n_clusters + 1) - 0.5, color='orange', edgecolor='black')
axs[1].set_xticks(np.arange(-1, n_clusters + 1))
axs[1].set_title("Cluster Size Distribution")
axs[1].set_xlabel("Cluster Label")
axs[1].set_ylabel("Number of Points")

# 显示图形
plt.tight_layout()
plt.show()
img

1. 聚类结果图：展示数据点的分类结果，不同簇用不同颜色表示，噪声点以黑色表示。这可以直观展示 DBSCAN 如何将点归类以及噪声点分布。

2. 簇的密度分布直方图：统计各簇的点数量，评估簇的大小和分布情况。这有助于理解聚类的密度特征和噪声点比例。

Mean-Shift

Mean-Shift 是一种基于密度的非参数聚类算法，不需要预先设定聚类的数量。它通过迭代地移动数据点到密度最大的位置（即模式）来实现聚类。适用于空间分布未知或复杂的情况。

算法原理

1. 初始化：选择一个点作为种子点，计算其在核函数影响下的密度。

2. 质心更新：在当前窗口内，计算数据点加权平均值作为新的质心。

3. 窗口移动：将窗口中心移动到新的质心。

4. 迭代停止：当质心移动的距离小于阈值时停止迭代。

5. 聚类形成：将所有收敛到同一质心的点归为一类。

核心公式

核密度估计：

  • ：窗口带宽（控制核的范围）。
  • ：核函数，常用高斯核：

质心更新公式：

通过不断更新 ，最终所有点会收敛到密度的局部最大值。

公式推导

1. 核密度梯度：

Mean-Shift 是核密度估计的梯度上升方法。核密度函数的梯度为：

2. 移动方向：

通过将核函数的梯度替换为高斯核形式，得出：

3. 收敛性：

每次更新会使质心移动到核密度更高的方向，最终所有点会收敛到密度的局部最大值。

完整案例

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
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import MeanShift, estimate_bandwidth

# 生成虚拟数据集
np.random.seed(42)
cluster_1 = np.random.normal(loc=[2, 2], scale=0.7, size=(1000, 2))
cluster_2 = np.random.normal(loc=[8, 8], scale=0.9, size=(1000, 2))
cluster_3 = np.random.normal(loc=[5, 0], scale=0.6, size=(1000, 2))
data = np.vstack([cluster_1, cluster_2, cluster_3])

# Mean-Shift 聚类
bandwidth = estimate_bandwidth(data, quantile=0.2)
mean_shift = MeanShift(bandwidth=bandwidth, bin_seeding=True)
mean_shift.fit(data)
labels = mean_shift.labels_
cluster_centers = mean_shift.cluster_centers_

# 提取聚类结果
n_clusters = len(np.unique(labels))
print(f"Number of clusters: {n_clusters}")

# 图形绘制
fig, ax = plt.subplots(1, 2, figsize=(14, 6), dpi=100)

# 图1: 原始数据及聚类结果
for cluster in range(n_clusters):
    cluster_points = data[labels == cluster]
    ax[0].scatter(cluster_points[:, 0], cluster_points[:, 1], s=50, label=f"Cluster {cluster}")
ax[0].scatter(cluster_centers[:, 0], cluster_centers[:, 1], s=200, c='red', marker='x', label='Centroids')
ax[0].set_title("Mean-Shift Clustering Results")
ax[0].legend()
ax[0].grid(True)

# 图2: 核密度估计 (KDE)
from scipy.stats import gaussian_kde
kde = gaussian_kde(data.T)
x = np.linspace(data[:, 0].min() - 1, data[:, 0].max() + 1, 100)
y = np.linspace(data[:, 1].min() - 1, data[:, 1].max() + 1, 100)
X, Y = np.meshgrid(x, y)
positions = np.vstack([X.ravel(), Y.ravel()])
Z = kde(positions).reshape(X.shape)
ax[1].imshow(np.rot90(Z), cmap=plt.cm.viridis, extent=[x.min(), x.max(), y.min(), y.max()])
ax[1].scatter(data[:, 0], data[:, 1], c=labels, cmap='rainbow', s=30)
ax[1].set_title("Kernel Density Estimation")
ax[1].grid(True)

plt.tight_layout()
plt.show()
img

1. 原始数据及聚类结果：展示 Mean-Shift 聚类后每个点所属的类别及其质心位置。帮助直观理解聚类效果。

2. 核密度估计图：展示数据点的密度分布情况。验证 Mean-Shift 聚类的核心思想，即点向密度高的区域聚集。

高斯混合模型

高斯混合模型（Gaussian Mixture Model, GMM）是一种基于概率统计的聚类算法。它将数据看作由多个高斯分布的子分布混合而成，适用于处理具有复杂分布形状的数据。GMM 是无监督学习中广泛应用的模型。

核心思想

GMM 通过期望最大化（EM）算法，迭代优化参数，估计数据中潜在的高斯分布，最终实现聚类。相比 K-means，GMM 能够捕捉数据分布的协方差结构和不均匀形状。

核心公式

1. 高斯分布公式

对于 维数据点 ，高斯分布的概率密度函数为：

其中：

  • ：均值向量
  • ：协方差矩阵

2. 高斯混合模型

GMM 假设数据来自 个高斯分布的混合，即：

其中：

  • ：第 个高斯分量的权重，满足 。

3. EM算法推导

EM算法分为两步：

(1) E 步：计算后验概率

计算每个点属于第 个分布的概率（责任度）：

(2) M 步：更新参数

根据 更新参数：

案例分析

生成一个 2D 的虚拟数据集，包括三个混合高斯分布，用 GMM 对其聚类。

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
import numpy as np
import matplotlib.pyplot as plt
from sklearn.mixture import GaussianMixture
from sklearn.datasets import make_blobs

# 设置随机种子
np.random.seed(42)

# 生成虚拟数据集：三类数据
n_samples = 1000
centers = [(0, 0), (5, 5), (10, 0)]
cluster_std = [1.5, 1.2, 1.8]
X, y_true = make_blobs(n_samples=n_samples, centers=centers, cluster_std=cluster_std, random_state=42)

# 拟合高斯混合模型
gmm = GaussianMixture(n_components=3, covariance_type='full', random_state=42)
gmm.fit(X)
y_gmm = gmm.predict(X)

# 计算责任度
responsibilities = gmm.predict_proba(X)

# 绘制图形
fig, ax = plt.subplots(1, 3, figsize=(18, 6))

# 图1：真实数据分布
ax[0].scatter(X[:, 0], X[:, 1], c=y_true, cmap='viridis', s=30, edgecolor='k', alpha=0.7)
ax[0].set_title('True Distribution')
ax[0].set_xlabel('X1')
ax[0].set_ylabel('X2')

# 图2：GMM聚类结果
ax[1].scatter(X[:, 0], X[:, 1], c=y_gmm, cmap='plasma', s=30, edgecolor='k', alpha=0.7)
ax[1].set_title('GMM Clustering Result')
ax[1].set_xlabel('X1')
ax[1].set_ylabel('X2')

# 图3：责任度热力图
scatter = ax[2].scatter(X[:, 0], X[:, 1], c=responsibilities.max(axis=1), cmap='coolwarm', s=30, edgecolor='k', alpha=0.7)
ax[2].set_title('Responsibility Heatmap')
ax[2].set_xlabel('X1')
ax[2].set_ylabel('X2')
fig.colorbar(scatter, ax=ax[2], label='Max Responsibility')

# 调整布局并显示
plt.tight_layout()
plt.show()
img

1. 真实数据分布：展示了数据生成的三个簇及其分布中心，帮助我们了解真实数据特征。

2. GMM 聚类结果：展现了 GMM 模型对数据的分组情况，每种颜色代表一个聚类。

3. 责任度热力图：通过颜色表示每个点的最大后验概率，反映 GMM 对点的分类信心。颜色越深，模型越确定属于某类。

Spectral Clustering

Spectral Clustering 是一种基于图论的聚类算法，通过构造图（Graph）来表示数据点之间的关系，利用图的拉普拉斯矩阵的特征向量进行降维和聚类。该方法在处理非凸形状的聚类问题上具有优势。

Spectral Clustering 原理

1. 构造图（Graph Construction）：

  • 使用数据点作为图的节点，构造加权图，权重通常表示数据点之间的相似性。
  • 常用的相似性度量包括高斯核函数：

2. 计算拉普拉斯矩阵（Laplacian Matrix）：

  • 度矩阵 是一个对角矩阵，，其中 是权重矩阵。
  • 非归一化拉普拉斯矩阵：。
  • 归一化拉普拉斯矩阵：。

3. 特征分解：

  • 对 或 进行特征分解，提取前 个最小特征值对应的特征向量，形成特征矩阵 。

4. 聚类：

  • 将特征矩阵 的行视为新的数据点，应用 K-means 或其他算法进行聚类。

核心公式及推导

1. 拉普拉斯矩阵的性质：

对于非归一化拉普拉斯矩阵 ，满足：

其中 是全 1 向量，表示拉普拉斯矩阵至少有一个零特征值。

2. 归一化拉普拉斯矩阵：

归一化后，矩阵 满足：

3. 特征分解的意义：

通过拉普拉斯矩阵的特征向量将数据嵌入到低维空间，特征向量的行表示数据点的新表示，便于后续聚类。

完整案例

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
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons, make_blobs
from sklearn.cluster import SpectralClustering
from sklearn.metrics import silhouette_score

# 生成虚拟数据
np.random.seed(42)
X1, _ = make_moons(n_samples=3000, noise=0.05)
X2, _ = make_blobs(n_samples=3000, centers=3, cluster_std=1.0)

# 创建子图
fig, axes = plt.subplots(1, 3, figsize=(18, 6), dpi=120)

# 原始数据图
axes[0].scatter(X1[:, 0], X1[:, 1], c='blue', label='Moon Dataset', alpha=0.7)
axes[0].scatter(X2[:, 0], X2[:, 1], c='green', label='Blob Dataset', alpha=0.7)
axes[0].set_title('Original Datasets')
axes[0].legend()

# 对 Moon 数据进行 Spectral Clustering
sc_moons = SpectralClustering(n_clusters=2, affinity='rbf', gamma=10, random_state=42)
labels_moons = sc_moons.fit_predict(X1)
axes[1].scatter(X1[:, 0], X1[:, 1], c=labels_moons, cmap='viridis', alpha=0.7)
axes[1].set_title('Spectral Clustering on Moon Dataset')

# 对 Blob 数据进行 Spectral Clustering
sc_blobs = SpectralClustering(n_clusters=3, affinity='nearest_neighbors', n_neighbors=10, random_state=42)
labels_blobs = sc_blobs.fit_predict(X2)
axes[2].scatter(X2[:, 0], X2[:, 1], c=labels_blobs, cmap='plasma', alpha=0.7)
axes[2].set_title('Spectral Clustering on Blob Dataset')

plt.tight_layout()
plt.show()

# 计算轮廓系数
silhouette_moons = silhouette_score(X1, labels_moons)
silhouette_blobs = silhouette_score(X2, labels_blobs)
print(f"Silhouette Score for Moon Dataset: {silhouette_moons:.2f}")
print(f"Silhouette Score for Blob Dataset: {silhouette_blobs:.2f}")
img

1. 原始数据图：展示数据的分布特征。通过观察数据形状，理解其复杂性。

2. 聚类结果图：使用颜色标注不同簇，展示 Spectral Clustering 对复杂形状的聚类效果。对比不同数据集的聚类性能。

3. 轮廓系数分析：定量评估聚类质量，验证模型的有效性。

OPTICS

OPTICS (Ordering Points To Identify the Clustering Structure) 是一种密度聚类算法，扩展了 DBSCAN 算法，适用于具有不同密度的复杂数据集。OPTICS 的核心思想是通过按点的密度可达性排序，形成一种可视化的聚类结构，以便提取任意密度的聚类。

OPTICS 原理

OPTICS 算法通过计算以下两个核心属性实现密度聚类：

1. 核心距离 (Core Distance)：点 成为核心点的最小半径，定义为其 -邻域的最远点的距离。

2. 可达距离 (Reachability Distance)：点 相对于点 的可达性定义为：

算法步骤：

  1. 初始化所有点的 core distance 和 reachability distance。
  2. 从未访问点中选择一个点 ，计算其 -邻域并标记为已访问。
  3. 更新 -邻域内点的 reachability distance，按升序将它们加入一个优先队列。
  4. 重复步骤 2 和 3，直至所有点被处理。
  5. 根据 reachability distance 的排序，绘制可达性图，以帮助提取不同密度的簇。

核心公式

  1. 核心距离：

  1. 可达距离：

公式推导过程结合了欧几里得距离及排序算法，用于动态更新点间的可达关系。

完整案例

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
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import OPTICS
from sklearn.datasets import make_blobs

# 1. 创建虚拟数据集
np.random.seed(42)
centers = [[5, 5], [0, 0], [10, 0]]
cluster_std = [1.0, 0.5, 2.0]
X, labels_true = make_blobs(n_samples=5000,
                            centers=centers,
                            cluster_std=cluster_std,
                            random_state=42)

# 2. 应用 OPTICS 算法
optics_model = OPTICS(min_samples=10, xi=0.05, min_cluster_size=0.1)
optics_model.fit(X)
labels = optics_model.labels_
reachability = optics_model.reachability_[optics_model.ordering_]
ordering = optics_model.ordering_

# 3. 可视化分析
fig, ax = plt.subplots(1, 3, figsize=(18, 6))

# (a) 原始数据分布
ax[0].scatter(X[:, 0], X[:, 1], c='gray', s=10, alpha=0.7)
ax[0].set_title('Original Data Distribution')
ax[0].set_xlabel('Feature 1')
ax[0].set_ylabel('Feature 2')

# (b) 可达距离图
space = np.arange(len(X))
ax[1].plot(space, reachability[ordering], 'r-', alpha=0.8, linewidth=1.5)
ax[1].set_title('Reachability Plot')
ax[1].set_xlabel('Points Ordered by Reachability')
ax[1].set_ylabel('Reachability Distance')

# (c) 聚类结果分布
colors = ['b', 'g', 'r', 'c', 'm', 'y', 'k']
for cluster_id in np.unique(labels):
    if cluster_id == -1:
        # 噪声点
        color = 'k'
        size = 10
    else:
        color = colors[cluster_id % len(colors)]
        size = 50
    cluster_points = X[labels == cluster_id]
    ax[2].scatter(cluster_points[:, 0], cluster_points[:, 1], c=color, s=size, alpha=0.7, label=f'Cluster {cluster_id}')
ax[2].legend()
ax[2].set_title('OPTICS Clustering Result')
ax[2].set_xlabel('Feature 1')
ax[2].set_ylabel('Feature 2')

plt.tight_layout()
plt.show()
img

1. 原始数据分布图：帮助观察数据的初始形态。

2. 可达性距离图：展示点按可达性排序的关系，用于发现簇。

3. 聚类结果分布图：直观展示聚类后的数据点划分及噪声点。

Affinity Propagation

Affinity Propagation (AP) 是一种基于消息传递的聚类算法，适用于寻找一组数据的“代表性样本”或“中心点”（称为代表点或 exemplars）。与传统的 K-Means 不同，它不需要预定义簇的数量，而是通过输入数据之间的相似度矩阵来自动确定簇的数量。

原理

AP 算法的核心思想是通过数据点之间的相似度信息，反复传递“责任值”（Responsibility）和“可用性值”（Availability），最终确定每个点属于哪个簇及其簇中心。

  • 相似度矩阵：相似度 描述点 和点 的相似性，通常为负的欧氏距离或负的平方距离。
  • 偏好值：每个点都有一个偏好值 ，表示其作为簇中心的可能性。偏好值越大，越可能成为簇中心。

核心公式

AP 算法主要涉及两种消息传递值：责任值 和可用性值 。

1. 责任值更新：

表示点 是否适合作为点 的簇中心，计算时排除了其他潜在中心的竞争。

2. 可用性值更新：

表示点 对点 作为簇中心的支持程度。

3. 对角线更新：

簇中心点的可用性值更新为：

算法流程

  1. 初始化相似度矩阵 和偏好值 。
  2. 初始化 和 为 0。
  3. 迭代更新 和 。
  4. 判断收敛：如果簇中心和分配的簇稳定，则停止迭代。
  5. 输出簇中心和簇分配结果。

完整案例

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
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import AffinityPropagation
from sklearn.metrics import pairwise_distances
from sklearn.datasets import make_blobs

# 1. 数据生成
np.random.seed(42)
X, _ = make_blobs(n_samples=3000, centers=4, cluster_std=1.0, random_state=42)

# 2. Affinity Propagation 聚类
similarity = -pairwise_distances(X, metric='euclidean')  # 负欧氏距离作为相似度
ap = AffinityPropagation(affinity='precomputed', random_state=42)
ap.fit(similarity)

# 获取聚类结果
cluster_centers_indices = ap.cluster_centers_indices_
labels = ap.labels_
n_clusters = len(cluster_centers_indices)

# 3. 数据分析图形
fig, axs = plt.subplots(1, 2, figsize=(14, 6))

# 图 1: 聚类结果
colors = plt.cm.tab10(np.linspace(0, 1, n_clusters))
for k, col in zip(range(n_clusters), colors):
    class_members = (labels == k)
    cluster_center = X[cluster_centers_indices[k]]
    axs[0].scatter(X[class_members, 0], X[class_members, 1], s=50, color=col, label=f'Cluster {k}')
    axs[0].scatter(cluster_center[0], cluster_center[1], s=200, color=col, edgecolor='k', marker='*')
axs[0].set_title('Affinity Propagation Clustering')
axs[0].legend()

# 图 2: 相似度矩阵热图
axs[1].imshow(similarity, cmap='viridis', aspect='auto')
axs[1].set_title('Similarity Matrix Heatmap')
axs[1].set_xlabel('Data Points')
axs[1].set_ylabel('Data Points')

plt.tight_layout()
plt.show()
img

1. 聚类结果图：直观展示了数据点的分布及其分配的簇。簇中心以星号标记，便于识别每个簇的中心点。

2. 相似度矩阵热图：展示了数据点之间的相似度分布。热图中的高值区域对应可能的簇中心，便于观察数据的整体结构。

Birch

BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies) 是一种针对大规模数据的聚类算法。它通过构建一个树状结构（CF Tree，Clustering Feature Tree）来表示数据，并逐步聚类，从而在内存限制下高效处理大型数据集。

Birch核心原理

BIRCH 算法的基本思想是构建一个具有以下特性的聚类特征树（CF Tree）：

1. 紧凑性：通过 CF（Clustering Feature）节点记录聚类信息。

2. 分层结构：CF Tree 是平衡的树，叶子节点记录簇的信息。

3. 动态性：支持增量式插入新数据点。

CF Vector 是 CF Tree 的核心组成部分，用于描述数据簇的信息：

  • N: 数据点个数。
  • LS (Linear Sum): 数据点的线性和。
  • SS (Square Sum): 数据点的平方和。

核心公式

通过这些信息，可以快速计算簇的质心 () 和方差 ():

算法步骤

1. 构建 CF Tree:

  • 根据阈值参数 控制每个簇的紧凑性。
  • 如果新数据点不能插入现有簇，则创建新的子节点或调整树的结构。

2. 初步聚类:

  • 基于 CF Tree，将数据划分为多个初步簇。

3. 全局聚类（可选）:

  • 使用传统聚类算法（如 k-means）对初步簇再进行进一步聚类。

完整案例

以下是使用 BIRCH 算法的 Python 实现，包括数据分析图：

  • 数据分布图（原始数据点及簇分布），清晰显示了数据的原始形状和簇的划分。
  • 聚类结果的二维投影（可视化簇分布），帮助观察聚类质量。
  • CF Tree 叶节点数量随阈值变化的关系，用于分析树的复杂度对参数的敏感性。
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
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.cluster import Birch

# 1. 生成虚拟数据集
np.random.seed(42)
n_samples = 1500
data, _ = make_blobs(n_samples=n_samples, centers=5, cluster_std=1.2, random_state=42)

# 2. BIRCH 聚类
thresholds = [0.3, 0.5, 1.0]
fig, axes = plt.subplots(1, 3, figsize=(18, 6), dpi=120)
for i, t in enumerate(thresholds):
    birch = Birch(threshold=t, n_clusters=None)
    birch.fit(data)
    labels = birch.labels_
    n_clusters = len(np.unique(labels))

    # 3. 绘制数据分布和聚类结果
    axes[i].scatter(data[:, 0], data[:, 1], c=labels, cmap='rainbow', s=10)
    axes[i].set_title(f"BIRCH Clustering (Threshold={t}, Clusters={n_clusters})")
    axes[i].set_xlabel("Feature 1")
    axes[i].set_ylabel("Feature 2")
plt.suptitle("BIRCH Clustering Results with Different Thresholds", fontsize=16)
plt.tight_layout()
plt.show()

# 4. 聚类性能评估（CF Tree 节点分析）
leaf_sizes = []
for t in thresholds:
    birch = Birch(threshold=t, n_clusters=None)
    birch.fit(data)
    leaf_sizes.append(len(birch.subcluster_centers_))
plt.figure(figsize=(10, 6), dpi=120)
plt.plot(thresholds, leaf_sizes, marker='o', color='red', label="Leaf Node Count")
plt.title("CF Tree Leaf Node Count vs. Threshold", fontsize=14)
plt.xlabel("Threshold")
plt.ylabel("Leaf Node Count")
plt.grid(True)
plt.legend()
plt.show()

1. 不同阈值的聚类结果：展示 BIRCH 在不同紧凑性约束下的聚类效果。

2. CF Tree 叶节点数量变化：反映了阈值参数对树结构复杂度的影响，帮助选择适当的聚类参数。

SOM

SOM（Self-Organizing Map）是一种基于无监督学习的神经网络算法，用于将高维数据映射到低维空间（通常是二维）。它通过保持数据的拓扑结构，使相似的数据点在映射后仍然保持相邻。SOM 被广泛用于数据可视化、聚类和降维。

SOM核心原理

1. 网络结构：

  • SOM由输入层和输出层组成。
  • 输入层接受多维特征向量。
  • 输出层是一个二维网格（通常是矩形或圆形拓扑），每个节点（神经元）对应一个权重向量。

2. 学习过程：

  1. 初始化权重向量（随机分配或从数据分布中采样）。
  2. 从数据集中随机选择一个样本。
  3. 找到与样本最接近的神经元（称为胜者神经元，Best Matching Unit, BMU）。
  4. 更新BMU及其邻域内神经元的权重，使其更接近样本向量。
  5. 重复上述步骤，逐渐减小学习率和邻域范围。

3. 收敛：

  • 随着迭代次数的增加，网络收敛，权重向量稳定，映射结果形成。

核心公式

1. 距离计算（用于找到BMU）：

其中， 是输入样本， 是第 个神经元的权重向量。

2. 权重更新：

  • ：当前迭代次数。
  • ：学习率，通常随时间递减。
  • ：邻域函数，定义为：

其中， 是神经元 和 的网格位置距离， 是邻域半径。

3. 邻域范围与学习率更新：

其中， 和 是初始值， 和 是最终值， 是时间常数。

完整案例

步骤

  1. 创建一个虚拟高维数据集。

  2. 使用SOM对数据进行聚类。

  3. 可视化：

    • 数据的二维映射结果。
    • 聚类结果和神经元权重分布。
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
import numpy as np
import matplotlib.pyplot as plt
from minisom import MiniSom

# 1. 创建虚拟数据集
np.random.seed(42)
data_class1 = np.random.normal(loc=[2, 2, 2], scale=0.5, size=(1000, 3))
data_class2 = np.random.normal(loc=[6, 6, 6], scale=0.5, size=(1000, 3))
data_class3 = np.random.normal(loc=[10, 2, 10], scale=0.5, size=(1000, 3))
data = np.vstack([data_class1, data_class2, data_class3])

# 2. 初始化SOM
som_dim = (10, 10)  # 10x10的SOM网格
som = MiniSom(som_dim[0], som_dim[1], input_len=3, sigma=1.0, learning_rate=0.5)
som.random_weights_init(data)
som.train_random(data, 1000)  # 训练1000次

# 3. 可视化结果
# 获取每个数据点的BMU
mapped = np.array([som.winner(d) for d in data])
clusters = np.array([x[0] * som_dim[1] + x[1] for x in mapped])  # 转化为线性索引

# 绘制数据点的二维映射
plt.figure(figsize=(12, 6))

# 图1：数据的二维映射
plt.subplot(1, 2, 1)
for idx, color in enumerate(['red', 'green', 'blue']):
    mask = clusters // (som_dim[0] * som_dim[1] // 3) == idx
    plt.scatter(mapped[mask, 0], mapped[mask, 1], label=f'Class {idx+1}', alpha=0.7, s=50, c=color)
plt.title("Data Mapping on SOM")
plt.xlabel("SOM X")
plt.ylabel("SOM Y")
plt.legend()

# 图2：SOM神经元权重
plt.subplot(1, 2, 2)
weights = som.get_weights()
for i in range(som_dim[0]):
    for j in range(som_dim[1]):
        plt.scatter(weights[i, j, 0], weights[i, j, 1], c='black', s=10)  # 权重点
plt.title("Neuron Weights Distribution")
plt.xlabel("Weight Dimension 1")
plt.ylabel("Weight Dimension 2")

plt.tight_layout()
plt.show()
img

1. 数据映射图：直观展示了高维数据在SOM二维网格上的映射结果。不同类别的数据点在网格上的分布，可以看出聚类效果。

2. 神经元权重分布图：展示了SOM中神经元权重在数据空间中的分布。可以观察权重的覆盖范围和分布密度，验证SOM的训练效果。

文章作者: gzh
文章链接: https://gongzihang6.github.io/2025/02/28/ju-lei-suan-fa/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 gzh !
Typora Markdown
赏
  目录