聚类是无监督学习的核心任务，目标是将数据集中的样本划分为若干个通常不相交的子集（簇），使得同一簇内样本尽可能相似、不同簇间样本尽可能不同。本章从距离度量出发，逐步讨论原型聚类、密度聚类和层次聚类三大范式。

第九章聚类

聚类任务与性能度量

聚类属于无监督学习——训练样本没有标记信息，算法依靠数据的内在结构自动分组。

聚类性能度量分两大类：

外部指标（有参考模型）：Jaccard系数、FM指数、Rand指数 → 越高越好
内部指标（无参考模型）：DB指数（越小越好）、Dunn指数（越大越好）

轮廓系数 (Silhouette Coefficient)：综合衡量凝聚度和分离度，$s(i) = \frac{b(i) - a(i)}{\max\{a(i), b(i)\}}$，其中 $a(i)$ 为样本 $i$ 到同簇其他样本的平均距离，$b(i)$ 为到最近异簇的平均距离。$s(i)$ 接近1表示聚类效果好。

距离度量

闵可夫斯基距离族统一了三种常用距离：

$D(X,Y) = \left( \sum_{i=1}^n |x_i - y_i|^p \right)^{\frac{1}{p}}$

$p=1$：曼哈顿距离（城市街区距离）$D = \sum |x_i - y_i|$
$p=2$：欧几里得距离（直线距离）$D = \sqrt{\sum (x_i - y_i)^2}$
$p \to \infty$：切比雪夫距离 $D = \max_i |x_i - y_i|$

切比雪夫距离在多维异常检测中尤其有用——它只关注变化最大的那个维度，相当于用”最短板”衡量距离。

有序属性 vs 无序属性：有序属性（如”高>中>低”）可用闵氏距离；无序属性（如”红、蓝、绿”）需用VDM。

原型聚类：K-means

K-means是原型聚类的最经典代表——每个簇用一个均值向量（原型）来代表。核心是最小化平方误差：

$E = \sum_{i=1}^k \sum_{\mathbf{x} \in C_i} \|\mathbf{x} - \boldsymbol{\mu}_i\|_2^2$

算法流程：

随机选 $k$ 个样本作为初始均值向量
将每个样本分配到最近均值向量的簇
重新计算每个簇的均值向量
重复2-3直到收敛（均值向量不再变化）

K-means的三大局限性：k需预设、对初始值敏感（不同初始化可能收敛到不同局部最优）、仅发现球形簇。实践中常用K-means++初始化来缓解初始值敏感问题——让初始中心点尽可能分散。

LVQ（学习向量量化）

LVQ是K-means的有监督变体：利用样本的类别标签辅助聚类，使原型向量向同类样本靠近、远离异类样本。适合有部分标记信息的场景。

高斯混合聚类 (GMM)

用多个高斯分布的线性组合拟合数据，每个样本以概率归属于各高斯分量——属于软聚类。

$P(\mathbf{x}) = \sum_{i=1}^k \alpha_i \cdot \mathcal{N}(\mathbf{x} | \boldsymbol{\mu}_i, \boldsymbol{\Sigma}_i)$

参数估计使用EM算法：E步计算样本属于各分量的后验概率，M步更新 $\alpha_i, \boldsymbol{\mu}_i, \boldsymbol{\Sigma}_i$。

密度聚类：DBSCAN

DBSCAN基于密度的空间聚类，不预设簇的数量、能发现任意形状的簇、自动识别噪声。

核心概念：

$\varepsilon$-邻域：以样本为中心、$\varepsilon$ 为半径的超球体区域
核心点：$\varepsilon$-邻域内包含至少 MinPts 个样本
边界点：在核心点的邻域内，但自身不满足核心点条件
噪声点：既非核心也非边界
密度直达 / 密度可达 / 密度相连：递进式的点间关系，用于定义簇

DBSCAN的一个簇 = 所有密度相连的核心点及其边界点。参数选择：$\varepsilon$ 可用k-距离图确定拐点，MinPts通常取 $\geq$ 维度+1。

优缺点：自动识别噪声、发现任意形状 → 但高维数据效果差（维度灾难导致密度概念退化）、$\varepsilon$ 和 MinPts 敏感。

层次聚类

层次聚类构建树状簇结构（Dendrogram），无需预设 $k$。

自底向上 (AGNES)：初始每个样本各为一簇，每次合并距离最近的两簇
自顶向下 (DIANA)：初始所有样本为一簇，每次分裂

簇间距离度量决定了合并/分裂策略：

策略	定义	特点
最小距离（单链接）	$d_{\min}(C_i, C_j)=\min_{\mathbf{x}\in C_i,\mathbf{y}\in C_j}\Vert\mathbf{x}-\mathbf{y}\Vert$	对噪声敏感
最大距离（全链接）	$d_{\max}(C_i, C_j)=\max_{\mathbf{x}\in C_i,\mathbf{y}\in C_j}\Vert\mathbf{x}-\mathbf{y}\Vert$	倾向发现紧凑簇
平均距离（均链接）	$d_{\text{avg}}(C_i, C_j)=\frac{1}{\lvert C_i\rvert\lvert C_j\rvert}\sum_{\mathbf{x}\in C_i}\sum_{\mathbf{y}\in C_j}\Vert\mathbf{x}-\mathbf{y}\Vert$	折中方案

层次聚类的计算复杂度为 $O(n^3)$（朴素实现）或 $O(n^2 \log n)$（优化实现），不适用于超大规模数据。但Dendrogram可视化在探索性数据分析中极具价值。

第九章 聚类