聚类算法

聚类算法的目标是在没有预先定义类别的情况下，将数据集划分为若干个有意义的群组, 使得同一类中的数据点彼此相似，而不同类中的数据点差异较大。

K-均值聚类 (K-Means Clustering)

K-means 聚类是一种非常流行且基础的无监督学习 (Unsupervised Learning) 算法。它的主要目标是将一个给定的数据集根据数据点之间的相似性，自动划分为 K 个不同的簇 (Cluster)。这里的”K”是一个需要预先指定的超参数，代表你希望最终得到的簇的数量。

它的核心思想是 “物以类聚，人以群分”。它通过迭代的方式，不断地优化每个簇的中心点————即质心 (Centroid)，并根据数据点与质心的距离，将每个数据点分配给最近的簇。这个过程持续进行，直到质心的位置不再发生显著变化，或者达到了预设的迭代次数，此时我们认为聚类结果已经收敛。

算法的目标是最小化簇内平方和(Within-Cluster Sum of Squares, WSS)，也被称为惯性 (Inertia)。简单来说，就是让同一个簇内的数据点尽可能地紧密，不同簇之间的数据点尽可能地远离。

算法步骤

初始化 (Initialization)
- 操作：从数据集中随机选择 K 个数据点作为初始的质心 (μ₁, μ₂, …, μ_K)。
- 说明：这是算法的起点。质心的初始位置会影响算法的收敛速度和最终结果。因为是随机选择，所以多次运行 K-means 可能会得到不同的聚类结果。
分配 (Assignment)
- 操作：对于数据集中的每一个数据点 x_i，计算它到 K 个质心 μ_j 的距离，并将其分配给距离最近的那个质心所在的簇 c_j。
- 说明：此步骤的目的是根据当前的质心位置，为每个数据点找到一个”归属”。最常用的距离度量是欧几里得距离 (Euclidean Distance)。其数学表达式为：在实际计算中，为了提高效率，通常使用平方欧几里得距离，因为它省去了开方的计算，并且不会改变距离的相对大小关系。
更新 (Update)
- 操作：对于每一个簇 c_j，重新计算其质心 μ_j。新的质心是该簇内所有数据点的均值。
- 说明：在第二步中，簇内的成员发生了变化，原来的质心可能不再是簇的几何中心。因此，需要通过计算均值来更新质心，使其移动到簇内数据点的中心位置。新的质心计算公式为：其中 |c_j| 是簇 c_j 中数据点的数量。
迭代 (Iteration)
- 操作：重复执行第二步（分配）和第三步（更新）。
- 说明：这个迭代过程会不断地优化数据点的分配和质心的位置。当满足以下任一条件时，算法停止：
  - 质心的位置不再发生变化（或变化非常小，小于一个预设的阈值）。
  - 数据点的分配不再改变。
  - 达到了预设的最大迭代次数。

数学原理

K-means 算法的最终目标是最小化一个目标函数 (Objective Function)，这个函数就是我们前面提到的簇内平方和 (WSS)。其数学表达式为：

J：目标函数，即总的 WSS。
K：簇的数量。
c_j：第 j 个簇。
μ_j：第 j 个簇的质心。
x_i：属于簇 c_j 的一个数据点。
∥x_i − μ_j∥²：数据点 x_i 到其所属簇质心 μ_j 的平方欧几里得距离。

上述公式表示所有数据点与其所属簇质心之间的距离平方和。

算法的两个核心步骤（分配和更新）正是为了以迭代的方式最小化这个 J 值：

分配步骤：在保持质心 μ_j 不变的情况下，将每个 x_i 分配给能使其 ∥x_i − μ_j∥² 最小的簇。这一步是在对 c_j 进行优化。
更新步骤：在保持簇分配 c_j 不变的情况下，为每个簇寻找一个新的质心 μ_j，使得该簇内的平方和 ∑_{x_i ∈ c_j}∥x_i − μ_j∥² 最小。可以证明，这个最优的 μ_j 就是簇内所有数据点的均值。

这是一个典型的期望最大化 (Expectation-Maximization, EM) 思想的应用。

K-means 的优缺点

优点：

简单高效：算法原理简单，容易实现，计算速度快。对于大规模数据集，其可伸缩性很好。
解释性强：聚类结果直观，容易解释。

缺点：

K值需要预先指定：如何选择最优的 K 值是 K-means 的一个核心难题。
对初始质心敏感：不同的初始质心可能会导致完全不同的聚类结果，甚至可能陷入局部最优解。
对异常值敏感：因为质心是基于均值计算的，个别的异常值（离群点）会对质心的位置产生较大影响。
对非球形簇效果不佳：K-means 倾向于发现大小相似、形状为球形的簇，对于形状不规则的簇、密度不均匀的簇效果较差。

DBSCAN (Density-Based Spatial Clustering)

DBSCAN，全称为 Density-Based Spatial Clustering of Applications with Noise（基于密度的含噪声应用空间聚类），是一种非常流行且强大的聚类算法。

与 K-均值 (K-Means) 算法试图找到球状的簇并且每个点都必须属于一个簇不同，DBSCAN 的核心思想是：一个簇是数据空间中一个连续的高密度区域，并由低密度区域分隔开。

这使得 DBSCAN 具有两大显著优势：

能够发现任意形状的簇（例如，环形、S形），而不像 K-均值那样只能处理凸形的簇。
能够自动识别并标记出噪声点（离群点），而不是强行将它们分配到某个簇中。

核心概念

要理解 DBSCAN 的工作原理，必须先掌握它的三个基本概念，这些概念都围绕着”密度”来定义。这需要我们先设定两个关键参数：

半径 ϵ (Epsilon)： 定义了一个点的”邻域”范围。它是一个距离值，用来画一个圈，圈内的所有点都被认为是这个点的邻居。
最小点数 MinPts： 定义了形成一个”高密度区域”所需要的点的最小数量阈值。

基于这两个参数，我们可以定义三种类型的点：

核心点 (Core Point)： 如果一个数据点 p 在其 ϵ 半径的邻域内，包含了至少 MinPts 个点（包括 p 自身），那么 p 就是一个核心点。
- 核心点是高密度区域的”内部成员”。它们是簇的”骨架”，簇就是从这些点开始生长和扩展的。
边界点 (Border Point)： 如果一个数据点 q 不是核心点，但它落在了某个核心点 p 的 ϵ 邻域内，那么 q 就是一个边界点。
- 边界点位于簇的”边缘”。它们本身密度不够，但它们是某个核心点的”邻居”，因此可以被归入该核心点所在的簇。
噪声点 (Noise Point)： 如果一个数据点既不是核心点，也不是边界点，那么它就是噪声点（或离群点）。
- 这些点是稀疏区域中的孤立点，不属于任何一个簇。DBSCAN 能够将它们有效地识别并分离出来。

工作流程

DBSCAN 的聚类过程就像在一个区域里寻找”人群”，并将它们连接起来。

选择起点： 从数据集中任意选择一个尚未被访问过的点 p。 > 算法会遍历所有点，所以从哪里开始并不影响最终结果，只会影响发现簇的顺序。
判断点的类型： 检查点 p 的 ϵ 邻域。
- 情况一： 如果 p 是一个核心点（其邻域内的点数 ≥ MinPts）：
  - 创建一个新的簇，并将 p 分配给这个簇。
  - 然后，扩展这个簇：检查 p 的所有邻居点。对于每一个邻居点 q，如果 q 也是一个核心点，就将 q 的所有邻居也加入到待处理的队列中。这个过程不断进行，直到所有通过核心点连接起来的（密度可达的）点都被加入到同一个簇中。
  - 这是算法最关键的一步，称为密度可达性扩展。它确保了一个完整的、高密度的区域被完整地识别为一个簇。
- 情况二： 如果 p 不是一个核心点：
  - 暂时将 p 标记为噪声点。
  - 这个点可能是真正的噪声，也可能是一个边界点。它未来的归属取决于它是否落入其他核心点的邻域内。如果后续在扩展其他簇时发现了它，它就会被吸纳为边界点并加入那个簇。
重复过程： 继续选择下一个尚未被访问过的点，重复步骤2，直到数据集中所有的点都被访问过。
完成聚类： 当所有点都被访问后，聚类过程结束。一些点被分配到不同的簇中，而另一些点则被最终标记为噪声。

DBSCAN 的优缺点

优点：

无需指定簇数量： 与 K-均值不同，DBSCAN 可以自动确定簇的数量。
可发现任意形状的簇： 其基于密度的特性使其不受簇形状的限制。
对噪声不敏感： 能够有效地识别并处理离群点，这在金融欺诈检测等场景中非常有用。

缺点：

对参数敏感： ϵ 和 MinPts 的选择对结果影响巨大，调参可能需要经验和多次试验。
不适合密度差异大的数据集： 如果数据集中不同簇的密度相差很大，DBSCAN 可能难以用一套全局的 ϵ 和 MinPts 参数来正确地识别所有簇。
高维数据下的问题： 在非常高的维度下（维度灾难），所有点之间的距离可能趋于一致，这使得基于距离的”密度”概念变得不那么有意义。

谱聚类 (Spectral Clustering)

谱聚类是一种基于图论的聚类方法，其核心思想是将聚类问题转化为图的分割问题。与传统的K-Means等基于距离的聚类算法不同，谱聚类能够识别任意形状的样本空间，并且对数据分布的适应性更强，因此在许多场景下表现优越。

想象一下，我们有许多数据点，如何将它们分组？ - 传统方法（如K-Means）：找到每个簇的中心点，然后将每个数据点分配给离它最近的中心点。这种方法隐含了一个假设：每个簇都是凸的（比如圆形或球形）。如果簇的形状是弯曲的、不规则的（例如月牙形），K-Means就很难处理。 - 谱聚类的思路：将所有数据点看作是图（Graph）中的节点（Vertices）。如果两个点彼此相似（距离近），就在它们之间连接一条边（Edge），边的权重表示它们的相似度。这样，整个数据集就变成了一张”相似度图”。现在，聚类的任务变成了如何切割这张图，使得分割后的不同子图之间连接的边的权重之和尽可能小（类间相似度低），而每个子图内部的边的权重之和尽可能大（类内相似度高）。 - 这个”切图”的思想就是谱聚类的精髓。它将一个在原始特征空间中难以解决的非线性问题，通过图论转化为了一个更容易处理的线性代数问题。

谱聚类算法步骤

原始数据 (N, P) ➔ [构建相似度图] ➔ 邻接矩阵 W (N, N) ➔ [计算D和L] ➔ 拉普拉斯矩阵 L_sym (N, N) ➔ [特征分解] ➔ 新特征矩阵 U (N, k) ➔ [K-Means聚类] ➔ 最终聚类标签 (N, 1)

构建相似度图 (Construct Similarity Graph)

将每一个数据点看作图中的一个节点 (Vertex)。根据数据点之间的”相似度”，在节点之间连接边 (Edge)。如果两个点非常相似，它们之间的边权重就高；反之则低。

这是算法的奠基之举，它将原始的、可能呈非线性复杂分布的数据集，转化为了一个可以用图论工具分析的结构。图的结构（谁和谁相连，连接有多强）编码了数据的内在关联。

如何定义”相似”并建图至关重要，常用方法有：

k-近邻图 (k-NN Graph)：每个点只与它最近的 k 个点相连。这是最常用、最稳健的方法之一。
全连接图 (Fully-connected Graph)：所有点之间都有连接，边的权重通常由高斯核函数决定。你需要选择合适的 σ 值。
ε-近邻图 (ε-neighborhood Graph)：连接所有距离在阈值 ε 内的点对。(有时会将k-近邻图和ε-近邻图结合使用)

计算邻接矩阵 W 和度矩阵 D

即将上一步构建的图用数学语言来描述, 将图的拓扑结构数字化、矩阵化，为下一步的计算做好准备。

邻接矩阵 W：一个 N×N 的方阵（N 是数据点总数），W_ij 就是节点 i 和节点 j 之间边的权重。如果两点不相连，则为0 (W是对称的稀疏矩阵)

度矩阵 D：一个 N×N 的对角矩阵，D_ii 是节点 i 的”度”，即与它相连的所有边的权重之和 (D_ii = ∑_jW_ij)。

计算拉普拉斯矩阵 L

利用 W 和 D 计算拉普拉斯矩阵。为了获得最好的效果，我们通常计算对称标准化的拉普拉斯矩阵 (L_sym)。

L_sym = I − D^−1/2WD^−1/2

（其中 I 是单位矩阵）

这是整个算法的核心。拉普拉斯矩阵是一个神奇的矩阵，它的特征值和特征向量（合称”谱”）蕴含了图的最佳分割信息。可以说，这个矩阵内部就”藏着”如何切分图的答案。

计算特征值和特征向量 (执行”谱”分析)

对拉普拉斯矩阵 L 进行特征分解，求出其所有的特征值和对应的特征向量。

这就是”谱聚类”中”谱”这个词的来源。我们通过这一步来”解锁”拉普拉斯矩阵中隐藏的分割信息。其中，最小的几个特征值对应的特征向量对我们来说最重要。

降维与投影

从上一步得到的所有特征向量中，选取与前 k 个最小特征值相对应的 k 个特征向量。然后，将这 k 个特征向量按列排成一个新的 N×k 的矩阵 U。

这是一个降维的过程。它将每个原始数据点从它原来的特征空间，投影到了一个全新的、低维的”谱空间”中。在这个谱空间里，原始数据复杂的非线性结构被”拉平”和”理顺”，变得更容易被区分。矩阵 U 的每一行就是原始数据点在这个新空间里的新坐标。

使用 K-Means 进行最终聚类

将第5步得到的新矩阵 U 作为输入，对其每一行（即每个数据点的新坐标）运行一次标准的 K-Means 算法，将其聚为 k 个簇。

在前几步谱聚类已经完成了最困难的”结构梳理”工作。在新空间中，不同簇的数据已经变得界限分明，因此一个像 K-Means 这样简单的算法就足以完成最后的”收尾”工作，为每个点分配最终的聚类标签。

示例代码

使用sklearn包的SpectralClustering

import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_circles
from sklearn.cluster import SpectralClustering

# 1. 生成数据集
# 我们生成一个同心圆数据集
# n_samples: 样本总数
# factor: 内外圆之间的比例
# noise: 噪声水平
X, y_true = make_circles(n_samples=1000, factor=0.5, noise=0.05, random_state=0)

# 2. 使用谱聚类进行聚类
# n_clusters: 要找到的簇数
# affinity: 构建邻接矩阵的方式。'rbf'是高斯核函数, 'nearest_neighbors'是k-NN图
spectral = SpectralClustering(n_clusters=2, 
                              affinity='nearest_neighbors', # 使用k-NN构建图
                              n_neighbors=20,             # k-NN的k值
                              random_state=0)
y_spectral = spectral.fit_predict(X)

# 4. 可视化聚类结果
plt.figure(figsize=(12, 6))
plt.scatter(X[:, 0], X[:, 1], c=y_spectral, s=10, cmap='viridis')
plt.title("Spectral Clustering (Success)")
plt.gca().set_aspect('equal', adjustable='box')
plt.show()

手写SpectralClustering

import numpy as np
# 假设 kmeans 函数已经定义好
# from somewhere import kmeans 

def spectral(W, k):
    """
    谱聚类算法 (使用标准化的拉普拉斯矩阵)
    这个函数实现了谱聚类的核心流程。

    输入:
        W: 邻接矩阵 (Adjacency Matrix)，一个 N-by-N 的对称矩阵，表示数据点之间的相似度。
        k: 目标聚类的簇数。
    输出:
        idx: 每个数据点最终的簇标签，一个长度为 N 的一维向量。
    """
    
    # 获取数据点的数量 N
    N = W.shape[0]

    # --- 步骤1: 计算度矩阵 D (Degree Matrix) ---
    # 度矩阵 D 是一个对角矩阵，其对角线上的元素 D[i, i] 是邻接矩阵 W 第 i 行所有元素的和。
    # 它代表了图中每个节点的"连接总强度"或"度"。
    D = np.diag(np.sum(W, axis=1))

    # --- 步骤2: 计算对称标准化的拉普拉斯矩阵 L_sym (Symmetric Normalized Laplacian) ---
    # 这是整个算法最关键的一步。相比非标准化的拉普拉斯矩阵(L = D - W)，
    # 标准化的版本对不同大小和密度的簇有更好的适应性，聚类效果更鲁棒。
    # 公式为: L_sym = I - D^(-1/2) * W * D^(-1/2)
    
    # 为了计算 D^(-1/2)，我们先计算 D 的平方根的逆。
    # 这里加上一个极小的数 1e-10 是为了防止 D 的对角线上有0（孤立点），从而导致除以零的错误，保证数值稳定性。
    D_inv_sqrt = np.linalg.inv(np.sqrt(D + 1e-10))
    
    # 根据公式计算 L_sym。`@` 是 Python 中的矩阵乘法运算符。
    L_sym = np.identity(N) - D_inv_sqrt @ W @ D_inv_sqrt

    # --- 步骤3: 特征分解 (Eigendecomposition) ---
    # 我们对 L_sym 进行特征分解，求解其特征值和特征向量。这是"谱"分析的核心。
    # 拉普拉斯矩阵的谱（特征值）蕴含了图的结构信息。
    # np.linalg.eigh 专门用于求解对称/厄米矩阵，性能更高，且保证返回的特征值是实数并已从小到大排序。
    eigenvalues, eigenvectors = np.linalg.eigh(L_sym)

    # --- 步骤4: 构建新的低维特征空间 U ---
    # 根据谱聚类理论，我们选取与 k 个最小特征值相对应的特征向量。
    # 由于 eigh 的结果已排序，我们直接取特征向量矩阵的前 k 列即可。
    # 这 k 个特征向量构成了一个新的、低维的表示空间，原始数据的复杂结构在这个空间中被简化。
    U = eigenvectors[:, :k]

    # --- 步骤5: (推荐的最佳实践) 标准化新的特征矩阵 U ---
    # 将矩阵 U 的每一行都标准化为单位长度（L2范数为1）。
    # 这样做可以消除 K-Means 算法对向量长度的敏感性，使得聚类更多地关注点在超球面上的角度关系，
    # 从而在新空间中取得更稳定、更准确的聚类效果。
    
    # 计算每一行（每个数据点在新空间中的向量）的L2范数。
    # keepdims=True 确保结果是 (N, 1) 的列向量，以便于下一步的广播除法。
    norm = np.linalg.norm(U, axis=1, keepdims=True)
    
    # 执行行标准化。同样加上一个极小的数防止除以零。
    U_norm = U / (norm + 1e-10)

    # --- 步骤6: 使用 K-Means 在新空间中进行最终聚类 ---
    # 谱聚类已经完成了最困难的"特征转换"工作。
    # 在这个新的特征空间 U_norm 中，数据点已经被变换得更容易被线性分割。
    # 因此，我们调用一个简单的 K-Means 算法来完成最后的分类任务。
    idx = kmeans(U_norm, k)

    # 返回最终的聚类结果
    return idx