9.1 聚类算法全览：K-means、层次聚类、DBSCAN与谱聚类

9.1 聚类算法全览：K-means、层次聚类、DBSCAN与谱聚类

聚类是无监督学习中最核心的任务之一，其目标是在没有先验标签的情况下，根据数据的内在相似性将样本划分成若干个簇，使得同一簇内的样本尽可能相似，不同簇间的样本尽可能不同。聚类分析被广泛应用于客户细分、图像分割、异常检测和生物信息学等领域。不同的聚类算法基于不同的数据相似性度量和簇结构假设。本节将系统阐述四种最具代表性的聚类算法：基于原型的K-means、基于层次的层次聚类、基于密度的DBSCAN以及基于图论的谱聚类，分析其核心原理、算法流程、关键参数与各自适用的场景。

9.1.1 K-means 聚类

K-means 是基于原型的聚类算法的典范，它假设每个簇可以由一个中心点（质心）来代表，并通过最小化样本到其所属簇质心的距离平方和来进行划分。

9.1.1.1 算法原理与目标

给定样本集D = { x 1 , x 2 , . . . , x n } , x i ∈ R d D = \{\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_n\}, \mathbf{x}_i \in \mathbb{R}^dD={x1​,x2​,...,xn​},xi​∈Rd，K-means 的目标是将n nn个样本划分到k kk个互斥的簇{ C 1 , C 2 , . . . , C k } \{C_1, C_2, ..., C_k\}{C1​,C2​,...,Ck​}中，以最小化簇内平方误差：
J = ∑ j = 1 k ∑ x ∈ C j ∥ x − μ j ∥ 2 J = \sum_{j=1}^{k} \sum_{\mathbf{x} \in C_j} \|\mathbf{x} - \boldsymbol{\mu}_j \|^2J=j=1∑k​x∈Cj​∑​∥x−μj​∥2
其中μ j = 1 ∣ C j ∣ ∑ x ∈ C j x \boldsymbol{\mu}_j = \frac{1}{|C_j|} \sum_{\mathbf{x} \in C_j} \mathbf{x}μj​=∣Cj​∣1​∑x∈Cj​​x是簇C j C_jCj​的质心向量。最小化J JJ是一个 NP 难问题，因此 K-means 采用了一种启发式的迭代优化算法（Lloyd算法）。

9.1.1.2 算法流程

1. 初始化：随机选择k kk个样本作为初始质心{ μ 1 ( 0 ) , . . . , μ k ( 0 ) } \{\boldsymbol{\mu}_1^{(0)}, ..., \boldsymbol{\mu}_k^{(0)}\}{μ1(0)​,...,μk(0)​}。
2. 迭代直至收敛：
   a.分配步骤：对于每个样本x i \mathbf{x}_ixi​，计算其到所有质心的距离（通常为欧氏距离），将其分配到距离最近的质心所对应的簇中。
   C j ( t ) = { x i : ∥ x i − μ j ( t ) ∥ 2 ≤ ∥ x i − μ l ( t ) ∥ 2 ,   ∀ l , 1 ≤ l ≤ k } C_j^{(t)} = \{ \mathbf{x}_i : \| \mathbf{x}_i - \boldsymbol{\mu}_j^{(t)} \|^2 \le \| \mathbf{x}_i - \boldsymbol{\mu}_l^{(t)} \|^2, \ \forall l, 1 \le l \le k \}<