本文由 GPT-5.6-sol 完成。

监督学习有标签告诉模型“应该预测什么”，无监督学习却只有样本 $\{x_i\}_{i=1}^n$。它必须自己寻找数据中的结构：哪些样本相近，数据是否集中在低维子空间，能否用少量原型或部件表示大量观测。

这类问题没有唯一正确答案。所谓“结构”始终依赖距离、图、表示方式和目标函数。先明确这些假设，比直接运行某个聚类命令更重要。

一、聚类问题与相似性

聚类希望把样本划分为若干组，使组内样本相似、组间样本不同。最常见的距离包括：

$$d_2(x,z)=\|x-z\|_2,$$

以及更一般的 Minkowski 距离

$$d_p(x,z)= \left(\sum_{j=1}^d|x_j-z_j|^p\right)^{1/p}.$$

欧氏距离对量纲非常敏感。若一个特征以万元计、另一个以小数计，前者可能主导全部距离，因此聚类前通常需要标准化。高维空间里距离还会趋于集中，稀疏向量则常更适合余弦相似度。

核函数提供另一种相似性：

$$k(x,z)=\langle\phi(x),\phi(z)\rangle.$$

它相当于在隐式特征空间比较样本，使“相似”的含义能够超越原始坐标中的直线距离。

二、K-means：用质心压缩数据

1. 目标函数

给定簇数 $K$，K-means 寻找簇指派 $c_i\in\{1,ldots,K\}$ 和质心 $\mu_k$，最小化簇内平方和：

$$J(\boldsymbol c,\boldsymbol\mu) =\sum_{i=1}^n \|x_i-\mu_{c_i}\|_2^2.$$

这是非凸问题，但在固定一组变量时，另一组变量有简单最优解。

2. 交替优化

固定质心，样本分配给最近的簇：

$$c_i\leftarrow \arg\min_k\|x_i-\mu_k\|_2^2.$$

固定分配，质心更新为簇内均值：

$$\mu_k\leftarrow \frac{1}{|C_k|}\sum_{i:c_i=k}x_i.$$

两步都会使目标不增，因此算法会在有限种指派中收敛。不过收敛只保证到局部最优或稳定点，结果强烈依赖初始化。

3. K-means++

K-means++ 先随机选择一个质心，之后以样本到最近已选质心的平方距离成比例地选择新质心。远离现有中心的区域更可能被覆盖，通常比完全随机初始化稳定。实践中仍应运行多次并选择目标最小的结果。

4. K-means 的隐含假设

它偏好近似球形、尺度相近的簇，使用欧氏平方距离，也要求质心有意义。细长簇、环形簇、密度差异明显的簇，或纯类别型特征都可能让 K-means 给出误导结果。

簇数 $K$ 可以结合肘部法、轮廓系数、稳定性以及 AIC/BIC 一类模型选择思想判断，但没有只靠曲线就必然正确的答案。聚类是否有用，最终仍要回到任务语义。

三、向量量化与近邻搜索

K-means 的质心也可视作码本（codebook）。对向量 $x$，只保存最近质心的编号

$$q(x)=\arg\min_k\|x-\mu_k\|_2,$$

重建时使用 $\mu_{q(x)}$，这就是向量量化。它把连续向量压缩为有限符号，也可用于近似最近邻检索。

高维向量若使用一个巨大码本，存储和搜索代价都很高。乘积量化（Product Quantization）把向量拆成若干子空间，对每个子向量独立量化：

$$x=(x^{(1)},\ldots,x^{(m)}).$$

组合码本数量呈乘法增长，而实际存储只需保存各子空间编号。代价是忽略了跨子空间的部分相关性，因此子空间划分与旋转方式会影响量化误差。

四、从“紧凑”到“连通”：谱聚类

K-means 追求围绕质心的紧凑性；谱聚类则把样本看成图上的节点，更关注连接结构。

1. 相似图

构造权重矩阵 $W$，常见高斯权重为

$$w_{ij}= \exp\left(-\frac{\|x_i-x_j\|_2^2}{2\sigma^2}\right),$$

也可以只连接 $k$ 近邻或距离小于阈值的样本。度矩阵为

$$D_{ii}=\sum_jw_{ij}.$$

图的构造决定了之后所有结果：邻居数太小会让图断裂，太大又会抹掉局部流形；$\sigma$ 太小或太大也会分别导致孤立或过度平滑。

2. 图 Laplacian

三种常见形式是

$$L=D-W,$$

$$L_{\mathrm{sym}} =I-D^{-1/2}WD^{-1/2},$$

$$L_{\mathrm{rw}} =I-D^{-1}W.$$

对任意向量 $f$，未归一化 Laplacian 满足

$$f^\top Lf =\frac12\sum_{i,j}w_{ij}(f_i-f_j)^2.$$

若相连节点的 $f_i$ 相近，这个量就小。因此 Laplacian 的低特征值特征向量描述了图上的平滑变化方向。

3. Normalized Cut 与松弛

把图分成 $A$ 与 $\bar A$ 时，普通 cut 只最小化跨边权重，容易切出孤立小集合。Normalized Cut 用两侧总体连接量归一化：

$$\operatorname{Ncut}(A,\bar A) =\frac{\operatorname{cut}(A,\bar A)}{\operatorname{vol}(A)} +\frac{\operatorname{cut}(A,\bar A)}{\operatorname{vol}(\bar A)}.$$

离散划分本身难解。放松指示变量的离散约束后，会得到广义特征值问题

$$Lf=\lambda Df,$$

或等价的归一化 Laplacian 特征分解。

4. 谱聚类算法

对 $K$ 个簇，典型步骤为：

1. 构造相似图 $W$ 与 $D$；
2. 计算 $L_{\mathrm{sym}}$ 的前 $K$ 个最小特征值对应特征向量；
3. 将这些特征向量按行组成新表示；
4. 对行向量归一化；
5. 在新表示上运行 K-means。

图 Laplacian 的零特征值重数等于图的连通分量数。近似分块图中，较小特征值与其后的 eigengap 常为簇数提供线索。谱聚类能识别非凸形状，但需要构造并分解图矩阵，大规模数据上必须使用稀疏图或近似算法。

五、PCA：寻找最大方差子空间

1. 投影与重建

先将数据中心化：

$$\tilde x_i=x_i-\bar x.$$

希望用正交矩阵 $U\in\mathbb R^{d\times r}$、$U^\top U=I$ 表示低维坐标

$$z_i=U^\top\tilde x_i,$$

并重建为 $Uz_i=UU^\top\tilde x_i$。PCA 最小化重建误差：

$$\min_{U^\top U=I} \sum_{i=1}^n \|\tilde x_i-UU^\top\tilde x_i\|_2^2.$$

利用勾股分解，这等价于最大化投影方差

$$\max_{U^\top U=I} \operatorname{tr}(U^\top SU),$$

其中

$$S=\frac1n\sum_i\tilde x_i\tilde x_i^\top$$

是协方差矩阵。

2. 特征分解与 SVD

最优 $U$ 由 $S$ 最大的 $r$ 个特征值对应特征向量组成。若中心化数据矩阵为 $X_c$，也可直接做

$$X_c=Q\Sigma V^\top.$$

右奇异向量给出主方向，奇异值平方与解释方差成比例。累计解释方差比

$$\frac{\sum_{j=1}^r\lambda_j} {\sum_{j=1}^d\lambda_j}$$

常用来选择维数。

PCA 找到的是最大线性方差方向，不保证这些方向最有利于分类，也不等同于“最重要的语义”。没有中心化时，第一主成分还可能主要指向数据均值而非变化方向。

六、NMF：用非负部件表示数据

对非负矩阵 $X\in\mathbb R_+^{n\times d}$，非负矩阵分解寻找

$$X\approx WH, \qquad W\ge0, H\ge0,$$

例如最小化

$$\min_{W,H\ge0}\frac12\|X-WH\|_F^2.$$

固定 $W$ 时关于 $H$ 是凸问题，固定 $H$ 时关于 $W$ 也是凸问题，但联合起来非凸。常用交替最小化、投影梯度或乘法更新。

非负约束禁止正负系数互相抵消，因而常产生“部件相加”的表示：每个样本由若干非负基向量以非负权重组合。不过分解一般不唯一，初始化、归一化与正则项都会改变得到的部件。

七、稀疏编码与字典学习

稀疏编码希望用字典 $D=[d_1,\ldots,d_m]$ 的少量原子重建样本：

$$x_i\approx D\alpha_i,$$

并求解

$$\min_{D,\{\alpha_i\}} \sum_i\left[ \frac12\|x_i-D\alpha_i\|_2^2 +\lambda\|\alpha_i\|_1 \right], \qquad \|d_j\|_2\le1.$$

$L_1$ 正则鼓励每个样本只使用少数原子；字典列范数约束则防止把 $D$ 无限放大、同时把 $\alpha$ 缩小来逃避惩罚。

固定字典时，每个编码问题是 Lasso，可用近端梯度：

$$\alpha^{(t+1)} =S_{\eta\lambda} \left( \alpha^{(t)}- \eta D^\top(D\alpha^{(t)}-x) \right).$$

固定编码时再更新字典，整体采用交替优化。它与 PCA 的差别很鲜明：PCA 使用一组正交方向和稠密系数，稀疏编码允许过完备、非正交字典，却要求单个样本只激活少数原子。

八、几种方法的统一观察

方法	学到的结构	主要约束或偏好
K-means	质心与硬簇指派	欧氏距离、近似球形簇
谱聚类	图上的低频表示	局部连通性、相似图质量
PCA	正交低维子空间	线性、最大方差、稠密表示
NMF	非负部件	加性组合、输入非负
稀疏编码	字典与稀疏系数	少量原子激活、可过完备

它们都在压缩数据，却对“好表示”给出不同答案。没有标签时，目标函数本身就是归纳偏置；选择方法，实际上是在选择希望数据遵循哪一种结构。

九、小结

本讲的两条主线分别是

$$\text{距离} \longrightarrow \text{质心聚类} \longrightarrow \text{图与谱聚类},$$

以及

$$\text{重建} \longrightarrow \text{正交子空间} \longrightarrow \text{非负或稀疏表示}.$$

无监督学习最值得警惕的地方，是算法总会输出某种结构，而输出存在并不等于结构有意义。距离是否合理、图是否可靠、维度是否合适、结果是否稳定，都需要结合下游任务与领域知识验证。

更新日志

2026/9/27 10:05

查看所有更新日志

• eea03-update 0927 japaneseVocabulary.js于 2026/9/27

版权所有

版权归属：Luminosity

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)

编辑此页

贡献者: avephysica

上一页第六讲：集成学习、AdaBoost 与梯度提升

下一页第八讲：强化学习 I——MDP 与动态规划