前言

本文列举了几个常见的聚类算法。

基于划分的方法

特点：

  • 划分方法: 将数据集中的数据对象分配到n个簇中，并且通过设定目标函数来驱使算法趋向于目标
  • 每个组至少包含一个对象
  • 每个对象必须属于且只属于一个组

K-Means（K均值聚类）

  • 原理：簇的中心点是该簇所有数据点的均值。
  • 流程：随机选K个点作为初始中心 -> 将每个点分配到最近的中心点 -> 重新计算每个簇的中心点（求均值） -> 重复上述两步直到收敛。

优点&缺点

  • 计算速度快，适合大规模数据；
  • 对噪声和异常值极其敏感，且容易陷入局部最优。
  • 改进：K-Means++ 优化了初始中心点的选择，使初始中心点尽可能分散，降低了陷入局部最优的概率。
1
2
3
4
5
6
7
8
9
10
11
12
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
X, y = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=42)
kmeans = KMeans(n_clusters=4, init='k-means++', random_state=42, n_init=10)
labels = kmeans.fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=labels, s=15, cmap='viridis')
plt.scatter(kmeans.cluster_centers_[:, 0], kmeans.cluster_centers_[:, 1],
            c='red', marker='X', s=100, label='Centers')
plt.title("K-Means (k-means++)")
plt.legend()
plt.show()

K-Medoids（K中心点聚类 / PAM算法）

  • 原理：簇的中心点必须是数据集中实际存在的某个数据点，而不是计算出来的均值。
  • 流程：随机选K个实际数据点作为中心 -> 将其他点分配到最近的中心点 -> 尝试用非中心点替换中心点，如果替换能降低总代价（如绝对误差和），则执行替换 -> 重复直到无法优化。

优点&缺点

  • 使用实际数据点作为中心，所以对噪声和异常值非常鲁棒；
  • 每次迭代的计算量远大于K-Means，不适合大数据集。
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 matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.metrics import pairwise_distances
def kmedoids_pam(X, k, max_iter=100, random_state=42):
    rng = np.random.RandomState(random_state)
    n = X.shape[0]
    D = pairwise_distances(X)  # 距离矩阵
    # 1. 随机选 k 个 medoid
    medoid_indices = rng.choice(n, k, replace=False)
    for _ in range(max_iter):
        # 2. 分配：每个点分到最近的 medoid
        labels = np.argmin(D[:, medoid_indices], axis=1)
        # 3. 更新：每个簇内尝试用其他点替换，使总代价最小
        new_medoids = []
        for j in range(k):
            cluster_points = np.where(labels == j)[0]
            if len(cluster_points) == 0:
                new_medoids.append(medoid_indices[j])
                continue
            sub_D = D[np.ix_(cluster_points, cluster_points)]
            costs = sub_D.sum(axis=1)
            best = cluster_points[np.argmin(costs)]
            new_medoids.append(best)
        new_medoids = np.array(new_medoids)
        if np.array_equal(np.sort(new_medoids), np.sort(medoid_indices)):
            break  # 收敛
        medoid_indices = new_medoids
    labels = np.argmin(D[:, medoid_indices], axis=1)
    return labels, medoid_indices
X, y = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=42)
labels, medoids = kmedoids_pam(X, k=4)
plt.scatter(X[:, 0], X[:, 1], c=labels, s=15, cmap='viridis')
plt.scatter(X[medoids, 0], X[medoids, 1], c='red', marker='X', s=100, label='Medoids')
plt.title("K-Medoids (PAM)")
plt.legend()
plt.show()

K-Medians（K中位数聚类）

  • 原理：使用簇内各维特征的中位数作为中心点，通常配合曼哈顿距离（L1范数）使用。

优点&缺点

  • 特点：相比K-Means，中位数受极端值影响较小，因此对异常值有一定鲁棒性；但计算中位数需要排序，开销比求均值大。
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
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
def kmedians(X, k, max_iter=100, random_state=42):
    rng = np.random.RandomState(random_state)
    n = X.shape[0]
    # 随机初始化中心
    centers = X[rng.choice(n, k, replace=False)].astype(float)
    for _ in range(max_iter):
        # 分配：使用曼哈顿距离（L1）
        dists = np.abs(X[:, None, :] - centers[None, :, :]).sum(axis=2)  # (n, k)
        labels = np.argmin(dists, axis=1)
        # 更新：取中位数作为新中心
        new_centers = np.array([np.median(X[labels == j], axis=0) for j in range(k)])
        if np.allclose(new_centers, centers):
            break
        centers = new_centers
    return labels, centers
X, y = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=42)
labels, centers = kmedians(X, k=4)
plt.scatter(X[:, 0], X[:, 1], c=labels, s=15, cmap='viridis')
plt.scatter(centers[:, 0], centers[:, 1], c='red', marker='X', s=100, label='Medians')
plt.title("K-Medians")
plt.legend()
plt.show()

CLARANS（基于随机搜索的K中心点聚类）

  • 原理：是对PAM（K-Medoids）算法的优化，结合了随机采样和随机搜索的思想。
  • 特点：降低了计算复杂度，能够处理比PAM更大的数据集。
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.metrics import pairwise_distances
def clarans(X, k, numlocal=5, maxneighbor=10, random_state=42):
    """简化版 CLARANS"""
    rng = np.random.RandomState(random_state)
    n = X.shape[0]
    D = pairwise_distances(X)
    best_cost = np.inf
    best_medoids = None
    for _ in range(numlocal):
        # 随机初始化 medoids
        medoids = rng.choice(n, k, replace=False)
        labels = np.argmin(D[:, medoids], axis=1)
        cost = sum(D[i, medoids[labels[i]]] for i in range(n))
        for _ in range(maxneighbor):
            # 随机选一个 medoid 和一个非 medoid 进行交换
            swap_medoid = rng.choice(k)
            swap_candidate = rng.choice(n)
            while swap_candidate in medoids:
                swap_candidate = rng.choice(n)
            new_medoids = medoids.copy()
            new_medoids[swap_medoid] = swap_candidate
            new_labels = np.argmin(D[:, new_medoids], axis=1)
            new_cost = sum(D[i, new_medoids[new_labels[i]]] for i in range(n))
            if new_cost < cost:
                medoids = new_medoids
                cost = new_cost
                break  # 找到更优解，重新开始邻居搜索
        if cost < best_cost:
            best_cost = cost
            best_medoids = medoids
    labels = np.argmin(D[:, best_medoids], axis=1)
    return labels, best_medoids
X, y = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=42)
labels, medoids = clarans(X, k=4, numlocal=10, maxneighbor=15)
plt.scatter(X[:, 0], X[:, 1], c=labels, s=15, cmap='viridis')
plt.scatter(X[medoids, 0], X[medoids, 1], c='red', marker='X', s=100, label='Medoids')
plt.title("CLARANS")
plt.legend()
plt.show()

基于层次的方法

特点：

  • 不需要输入聚类数目k；
  • 一旦一个合并被执行，就不能修正；
  • 没有一个全局最优化的目标函数；
  • 计算量较大。

单连接

将两个簇的数据点中距离最近的两个数据点间的距离作为这两个簇的距离。

优点&缺点

  • 这种方法容易受到极端值的影响。两个并非很相似的簇可能由于其中的某个极端的数据点距离较近而组合在一起。
  • 单连接产生非常分散的簇，擅长处理非球形簇。
  • 对离群点和噪声敏感。

全连接

将两个簇的数据点中距离最远的两个数据点间的距离作为这两个簇的距离。

优点&缺点

  • 对与总体结构不太一致的离群点给予了过多的关注（并不能找出最直观的簇结构）。
  • 对离群点和噪声敏感。

组平均

计算两个簇的数据点中的每个数据点与其他所有数据点的距离。

优点&缺点

  • 对单链接和全链接的权衡，方法计算量比较大，但结果比前两种方法合理。
  • 对噪声和离群点没那么敏感。

质心距离

将两个簇的质心距离作为这两个簇的距离。

优点&缺点

  • 减少组平均方法计算量比较大问题
  • 对噪声和离群点没那么敏感
  • 偏向于球型簇

基于密度的划分

特点：
基于密度的聚类算法是机器学习中非常重要的一类无监督学习方法。与 K-means 等基于距离的算法不同，它的核心思想是将簇定义为被低密度区域分割的高密度区域。
以下是对基于密度的聚类算法的系统总结：

一、 核心概念（以 DBSCAN 为例）

这类算法通常围绕以下几个基础概念展开：

  • ϵ\epsilon-邻域：以某点为圆心，半径为 ϵ\epsilon 的区域。
  • 最小点数：一个 ϵ\epsilon-邻域内至少需要包含的数据点数量。
  • 核心点：ϵ\epsilon-邻域内点数 ≥\ge MinPts 的点。
  • 边界点：落在某个核心点的 ϵ\epsilon-邻域内，但其自身邻域内点数不足 MinPts 的点。
  • 噪声点：既不是核心点也不是边界点的点（即孤立点）。
  • 密度相连：如果点 A 和点 B 可以通过一系列核心点相互连接，则它们是密度相连的，属于同一个簇。

二、 经典及常见算法

1. DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

  • 地位：最经典、最基础的密度聚类算法。
  • 原理：从任意一个未被访问的点开始，如果它是核心点，则创建一个新簇，并递归地将其 ϵ\epsilon-邻域内的所有密度相连的点加入该簇；如果不是核心点，则暂时标记为噪声。
  • 特点：能发现任意形状的簇，自带噪声过滤功能；但对参数（ϵ\epsilon 和 MinPts）非常敏感，且无法很好地处理密度差异较大的数据集。
1
2
3
4
5
6
7
8
9
10
11
12
from sklearn.cluster import DBSCAN
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
X, y = make_moons(n_samples=300, noise=0.05, random_state=42)
dbscan = DBSCAN(eps=0.2, min_samples=5)
labels = dbscan.fit_predict(X)
# labels == -1 表示噪声点
plt.scatter(X[labels != -1, 0], X[labels != -1, 1], c=labels[labels != -1], s=15, cmap='viridis')
plt.scatter(X[labels == -1, 0], X[labels == -1, 1], c='red', s=15, marker='x', label='Noise')
plt.title("DBSCAN")
plt.legend()
plt.show()

2. OPTICS (Ordering Points To Identify the Clustering Structure)

  • 解决的问题：DBSCAN 对单一 ϵ\epsilon 敏感的问题。
  • 原理：不直接生成聚类结果，而是计算每个点的“核心距离”和“可达距离”，并对数据点进行排序，生成一个簇排序图。用户可以在该图上根据不同密度“切分”出聚类结果。
  • 特点：能够处理具有不同密度的簇，但计算开销比 DBSCAN 更大，且结果解释需要一定经验。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from sklearn.cluster import OPTICS
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
X, y = make_moons(n_samples=300, noise=0.05, random_state=42)
optics = OPTICS(min_samples=5, xi=0.05, min_cluster_size=0.1)
labels = optics.fit_predict(X)
# 绘制可达距离图
fig, axes = plt.subplots(1, 2, figsize=(12, 4))
# 左图：聚类结果
axes[0].scatter(X[labels != -1, 0], X[labels != -1, 1], c=labels[labels != -1], s=15, cmap='viridis')
axes[0].scatter(X[labels == -1, 0], X[labels == -1, 1], c='red', s=15, marker='x', label='Noise')
axes[0].set_title("OPTICS - Clustering")
axes[0].legend()
# 右图：可达距离图
space = np.arange(len(X))
reachability = optics.reachability_[optics.ordering_]
axes[1].plot(space, reachability, 'k-', alpha=0.5)
axes[1].set_title("OPTICS - Reachability Plot")
axes[1].set_xlabel("Points (ordered)")
axes[1].set_ylabel("Reachability Distance")
plt.tight_layout()
plt.show()

3. HDBSCAN (Hierarchical DBSCAN)

  • 解决的问题：简化参数选择，处理变密度数据。
  • 原理：结合了层次聚类和密度聚类的思想。它首先构建数据的最小生成树，然后基于“相互可达距离”建立聚类层次树，最后通过一种稳定性度量自动提取最稳定的簇。
  • 特点：目前工业界和学术界最推荐的密度聚类算法之一。只需一个参数（最小簇大小 min_cluster_size），对超参数极度鲁棒，不需要人工指定 ϵ\epsilon。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 需要 pip install hdbscan
import hdbscan
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons
X, y = make_moons(n_samples=300, noise=0.05, random_state=42)
clusterer = hdbscan.HDBSCAN(min_cluster_size=10, min_samples=5)
labels = clusterer.fit_predict(X)
fig, axes = plt.subplots(1, 2, figsize=(12, 4))
# 左图：聚类结果
axes[0].scatter(X[labels != -1, 0], X[labels != -1, 1], c=labels[labels != -1], s=15, cmap='viridis')
axes[0].scatter(X[labels == -1, 0], X[labels == -1, 1], c='red', s=15, marker='x', label='Noise')
axes[0].set_title("HDBSCAN - Clustering")
axes[0].legend()
# 右图：层次树
clusterer.condensed_tree_.plot(select_clusters=True,
                                selection_palette=plt.cm.viridis.colors,
                                axis=axes[1])
axes[1].set_title("HDBSCAN - Condensed Tree")
plt.tight_layout()
plt.show()

4. Mean Shift (均值漂移)

  • 原理：基于核密度估计。算法计算当前窗口内的平均偏移向量，将窗口向密度更高的方向移动，不断迭代直到收敛到局部密度最大值（模式）。
  • 特点：常用于计算机视觉（如图像分割、目标跟踪），不需要指定簇数量，但计算成本较高，且依赖于带宽参数的选择。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
from sklearn.cluster import MeanShift, estimate_bandwidth
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
X, y = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=42)
# 自动估计带宽
bandwidth = estimate_bandwidth(X, quantile=0.2, n_samples=150)
ms = MeanShift(bandwidth=bandwidth, bin_seeding=True)
labels = ms.fit_predict(X)
plt.scatter(X[:, 0], X[:, 1], c=labels, s=15, cmap='viridis')
plt.scatter(ms.cluster_centers_[:, 0], ms.cluster_centers_[:, 1],
            c='red', marker='X', s=100, label='Centers')
plt.title(f"Mean Shift (bandwidth={bandwidth:.2f}, n_clusters={ms.cluster_centers_.shape[0]})")
plt.legend()
plt.show()

5. DENCLUE

  • 原理：利用核密度估计函数模拟数据分布，聚类的中心即为密度函数的局部最大值（密度吸引子）。通过梯度上升法寻找这些局部最大值。
  • 特点：具有坚实的数学基础，适合处理高维数据中的噪声，但在大规模数据上计算复杂度高。
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
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
from sklearn.neighbors import KernelDensity
from scipy.ndimage import label as scipy_label
def denclue(X, h=0.5, eps=1e-3, max_iter=100):
    """
    简化版 DENCLUE：基于核密度估计 + 梯度上升寻找密度吸引子
    h: 核带宽, eps: 收敛阈值
    """
    n = X.shape[0]
    points = X.copy()
    # 梯度上升：每个点向密度最大方向移动
    for _ in range(max_iter):
        new_points = np.zeros_like(points)
        for i in range(n):
            # 高斯核
            diff = points[i] - points
            dists_sq = np.sum(diff ** 2, axis=1)
            weights = np.exp(-dists_sq / (2 * h ** 2))
            # 梯度方向：加权平均
            grad = np.sum(points * weights[:, None], axis=0) / (np.sum(weights) + 1e-10)
            new_points[i] = grad
        if np.max(np.linalg.norm(new_points - points, axis=1)) < eps:
            break
        points = new_points
    # 合并收敛到相同吸引子的点
    from sklearn.cluster import DBSCAN
    db = DBSCAN(eps=h * 0.5, min_samples=1).fit(points)
    labels = db.labels_
    return labels
X, y = make_blobs(n_samples=200, centers=3, cluster_std=0.8, random_state=42)
labels = denclue(X, h=0.5)
plt.scatter(X[:, 0], X[:, 1], c=labels, s=15, cmap='viridis')
plt.title("DENCLUE")
plt.show()

三、 优点

  1. 无需预设簇数量：不像 K-means 需要提前指定 KK，算法会根据密度自动发现簇的数量。
  2. 能发现任意形状的簇：不受限于球状/凸状分布，可以很好地处理环状、半月形等复杂结构的数据。
  3. 对噪声鲁棒：天然具备异常检测能力，能将离群点识别为噪声点而不将其归入任何簇。
  4. 结果相对确定：在大多数实现中，除了边界点的归属可能因遍历顺序略有不同，核心点的聚类结果是稳定不变的。

四、 缺点

  1. 参数敏感（DBSCAN）：ϵ\epsilon 和 MinPts 的选择对结果影响巨大，在高维数据中尤其难以调参。
  2. 密度差异处理困难：传统 DBSCAN 在处理“有的簇很密，有的簇很稀疏”的数据时表现不佳（需依赖 OPTICS 或 HDBSCAN 解决）。
  3. 高维灾难：在极高维空间中，距离度量失效（所有点之间的距离趋于一致），导致“密度”概念失去意义。通常需要先进行降维（如 PCA, t-SNE, UMAP）再使用。
  4. 计算复杂度：基础实现复杂度为 O(N2)O(N^2)，即使使用空间索引树（如 KD-tree、Ball-tree）优化为 O(Nlog⁡N)O(N \log N)，在大规模数据集上仍比 K-means 慢。

总结对比表

方法 类别 是否需要指定 K 对噪声鲁棒 簇形状 主要库
K-Means 划分 ✅ ❌ 球形 sklearn.cluster.KMeans
K-Medoids 划分 ✅ ✅ 球形 sklearn_extra.cluster.KMedoids / 手动实现
K-Medians 划分 ✅ ⚠️ 较好 球形 手动实现
CLARANS 划分 ✅ ✅ 球形 手动实现 / pyclustering
单连接 层次 ❌ ❌ 链状 scipy.cluster.hierarchy
全连接 层次 ❌ ❌ 紧凑 scipy.cluster.hierarchy
组平均 层次 ❌ ✅ 中等 scipy.cluster.hierarchy
质心距离 层次 ❌ ✅ 球形 scipy.cluster.hierarchy
DBSCAN 密度 ❌ ✅ 任意 sklearn.cluster.DBSCAN
OPTICS 密度 ❌ ✅ 任意 sklearn.cluster.OPTICS
HDBSCAN 密度 ❌ ✅✅ 任意 hdbscan / sklearn.cluster.HDBSCAN
Mean Shift 密度 ❌ ⚠️ 任意 sklearn.cluster.MeanShift
DENCLUE 密度 ❌ ✅ 任意 手动实现 / pyclustering