降维、聚类与矩阵分解

本页从“怎样表示数据”和“怎样发现无标签结构”出发，串联降维、聚类、概率模型与推荐系统中的矩阵分解。

一、降维、聚类与概率模型

1.1 主成分分析 PCA

PCA（Principal Component Analysis，主成分分析）是一种无监督降维方法。它不使用类别标签，而是寻找数据中方差最大的方向，把原始特征投影到较低维空间。

对中心化后的数据，第一主成分方向可以写成：

$$\underset{\Vert w{\Vert }_2=1}{max}{w}^{\mathsf{T}}Sw$$

其中 $S$ 是样本协方差矩阵。最优方向是协方差矩阵对应最大特征值的特征向量，后续主成分取其余正交特征向量。

PCA 的关键词：

• 无监督；
• 降维；
• 最大化投影方差；
• 用少量主成分保留主要信息；
• 不直接利用类别标签。

PCA 不等于聚类。它寻找的是新的坐标方向，而不是把样本分成若干类别。

PCA 投影与降维坐标

将样本投影到一个主成分方向，本质上是计算样本与该方向的内积。若 $w$ 是单位主成分方向，则中心化样本 $x_c$ 在该方向上的一维坐标为：

$$\boxed{{\displaystyle z=w^{\mathsf{T}}{x}_c}}$$

如果题目已经说明样本完成中心化处理，可以直接写成：

$$z=w^{\mathsf{T}}x$$

例如：

$$x=\left[\begin{array}{c}3\\ 4\end{array}\right],w=\left[\begin{array}{c}0.8\\ 0.6\end{array}\right]$$

由于：

$$\Vert w{\Vert }_2=\sqrt{{0.8}^2+{0.6}^2}=1$$

所以投影坐标为：

$$z=w^{\mathsf{T}}x=0.8\times 3+0.6\times 4=2.4+2.4=4.8$$

这里的 $4.8$ 是样本在主成分方向 $w$ 上的有符号坐标，也就是降维后的一维表示。它不是样本在原二维空间中的欧氏长度：

$$\Vert x{\Vert }_2=5$$

二者只有在样本恰好沿着 $w$ 方向时才会相等。

如果原始数据没有中心化，PCA 的标准投影应先减去训练集均值 $\mu$：

$$\boxed{{\displaystyle z=w^{\mathsf{T}}(x-\mu )}}$$

直接计算 $w^{\mathsf{T}}x$ 会把均值偏移也混入主成分坐标。多个主成分方向按列组成矩阵：

$$W=[w_1,w_2,\dots ,w_k]$$

若这些方向正交归一，则样本的 $k$ 维 PCA 表示为：

$$\boxed{{\displaystyle z=W^{\mathsf{T}}(x-\mu )}}$$

PCA 计算速记

中心化 → 选择主成分方向 → 用内积计算投影坐标。

截断 SVD 与最佳低秩近似

设数据矩阵 $X\in {\mathbb{R}}^{m\times n}$ 的奇异值分解为：

$$X=U\mathrm{\Sigma }{V}^{\mathsf{T}}$$

设奇异值按降序排列：

$${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_r\ge 0$$

只保留最大的 $k$ 个奇异值及其对应的奇异向量，得到截断 SVD：

$$\boxed{{\displaystyle X_k=U_k{\mathrm{\Sigma }}_k{V}_k^{\mathsf{T}}}}$$

Eckart–Young 定理说明，在所有秩不超过 $k$ 的矩阵中，$X_k$ 是 Frobenius 范数意义下对 $X$ 的最佳近似：

$$\boxed{{\displaystyle X_k=\underset{\mathrm{rank}(Y)\le k}{\arg min}\Vert X-Y{\Vert }_F}}$$

对应的最小重构误差为：

$$\boxed{{\displaystyle \Vert X-X_k{\Vert }_F=\sqrt{\sum _{i=k+1}^r{\sigma }_i^2}}}$$

当目标是降低矩阵秩、进行低秩近似并最小化 Frobenius 重构误差时，应优先想到截断 SVD：

低秩近似速记

低秩近似 + 最小化 Frobenius 重构误差 → 截断 SVD。

PCA 也可以通过 SVD 实现。对中心化后的数据矩阵 $X_c$ 做分解：

$$X_c=U\mathrm{\Sigma }{V}^{\mathsf{T}}$$

前 $k$ 个右奇异向量构成 PCA 的主方向，样本在低维空间中的表示为：

$$Z=X_c{V}_k=U_k{\mathrm{\Sigma }}_k$$

再映射回原特征空间时得到：

$${\hat{X}}_c=Z{V}_k^{\mathsf{T}}=U_k{\mathrm{\Sigma }}_k{V}_k^{\mathsf{T}}$$

所以 PCA 的前 $k$ 个主成分重构，正是中心化数据矩阵的最佳秩 $k$ 近似。

其他常见矩阵分解的典型用途可以这样区分：QR 主要用于正交化和最小二乘，LU 主要用于求解一般线性方程组，Cholesky 适用于对称正定矩阵，而 SVD 常用于降维、低秩近似、伪逆和数值稳定性分析。

1.2 线性判别分析 LDA

线性判别分析（Linear Discriminant Analysis，LDA）是一种使用类别标签的监督降维方法。它寻找投影方向，使同一类别的样本尽量集中，同时让不同类别的类别中心尽量分离。

设共有 $C$ 个类别，第 $c$ 类的样本均值为 ${\mu }_c$，样本数为 $n_c$，所有样本的总体均值为 $\mu$。类内散度矩阵和类间散度矩阵分别定义为：

$$S_W=\sum _{c=1}^C\sum _{x_i\in c}(x_i-{\mu }_c)(x_i-{\mu }_c{)}^{\mathsf{T}}$$$$S_B=\sum _{c=1}^C{n}_c({\mu }_c-\mu )({\mu }_c-\mu {)}^{\mathsf{T}}$$

其中，$S_W$ 描述同类样本内部的分散程度，$S_B$ 描述不同类别中心之间的分离程度。LDA 的 Fisher 判别准则是寻找方向 $w$，最大化类间散度与类内散度的比值：

$$\boxed{{\displaystyle J(w)=\frac{w^{\mathsf{T}}{S}_{B}w}{w^{\mathsf{T}}{S}_{W}w}}}$$

LDA 目标

让类间散度尽量大、类内散度尽量小。

在 $S_W$ 可逆时，最优方向通常由广义特征值问题得到：

$$S_{B}w=\lambda S_{W}w$$

实际数据中如果 $S_W$ 奇异或接近奇异，可以使用正则化 LDA、降维预处理或伪逆等方式提高数值稳定性。

LDA 的最大降维维度

由于类间散度矩阵的秩满足：

$$\mathrm{rank}(S_B)\le C-1$$

所以有 $C$ 个类别时，LDA 能提供的有效判别方向最多为 $C-1$ 个。如果原始特征维度为 $d$，实际最大降维维度是：

$$\boxed{{\displaystyle min(d,C-1)}}$$

这意味着 LDA 的目标维度不能像普通无约束投影那样任意指定，而受到类别数量限制。

PCA 与 LDA 的区别

对比维度	PCA	LDA
是否需要类别标签	不需要	需要
学习范式	无监督降维	监督降维
优化目标	保留总体数据方差	类间分离、类内紧凑
最大有效维度	不超过原始特征维度 $d$	不超过 $min(d,C-1)$
典型用途	压缩、去噪、可视化	判别性降维、分类前特征提取

经典的概率 LDA 分类模型通常还会假设各类别条件分布近似高斯，并共享协方差矩阵；但 Fisher 判别准则本身表达的是散度比优化。不能把 LDA 简单说成适用于任意数据分布，也不能把它和不使用标签的 PCA 混为一谈。

PCA 与 LDA 速记

• PCA：寻找总体方差最大的方向。
• LDA：寻找最容易区分类别的方向。

1.3 K-Means 聚类

K-Means 是典型的无监督聚类算法。给定簇数 $K$，它通过距离把样本划分成 $K$ 个簇，并让每个样本尽量靠近所属簇的中心。

典型目标函数是：

$$\boxed{{\displaystyle \underset{\{C_k,{\mu }_k\}}{min}\sum _{k=1}^K\sum _{x_i\in C_k}\Vert x_i-{\mu }_k{\Vert }_2^2}}$$

其中 $C_k$ 是第 $k$ 个簇，${\mu }_k$ 是该簇的中心。算法通常交替执行：

1. 根据距离把每个样本分配给最近的中心；
2. 根据当前簇内样本重新计算中心；
3. 重复以上步骤，直到目标函数基本不再下降。

K-Means 属于硬聚类：每个样本最终被分配给一个簇。它对距离度量、特征尺度和初始中心比较敏感，实际使用前通常需要考虑标准化和初始化策略。由于簇中心是样本均值，异常值会直接拉动中心位置；当数据含有较强噪声或大量离群点时，K-Means 的聚类结果可能明显受影响。

目标函数与收敛

K-Means 优化的是簇内平方误差和（SSE）：

$$\boxed{{\displaystyle J=\sum _{k=1}^K\sum _{x_i\in C_k}\Vert x_i-{\mu }_k{\Vert }_2^2}}$$

固定簇中心时，把每个样本分配给距离最近的中心，可以使每个样本对应的平方距离尽可能小；固定样本分配时，簇内样本的均值是平方误差和的最小化解：

$$\boxed{{\displaystyle {\mu }_k=\frac{1}{|C_k|}\sum _{x_i\in C_k}{x}_i}}$$

因此，标准的 Lloyd 迭代中，分配步骤和中心更新步骤都会使 $J$ 下降或保持不变：

$$\boxed{{\displaystyle J^{(t+1)}\le J^{(t)}}}$$

实际迭代通常在以下情况之一发生时停止：

• 所有簇中心的移动量小于设定阈值；
• 样本所属簇不再变化；
• 目标函数的下降量小于设定阈值；
• 达到最大迭代次数。

“目标函数不再下降”说明算法到达一个稳定点，通常意味着簇中心和样本分配已经收敛，但不代表一定得到全局最优解。K-Means 对初始中心敏感，不同初始化可能收敛到不同的局部最优解，因此实践中常用多次随机初始化并选择 SSE 较小的结果。

收敛也不意味着簇内方差为零。只有当每个簇中的所有样本都恰好等于该簇中心时，才有 $J=0$。此外，K-Means 的目标是直接最小化簇内距离，而不是直接最大化簇间距离。

常见距离度量

距离度量通常作用在差向量 $x-y$ 上。曼哈顿距离就是 $L_1$ 距离：

$$\boxed{{\displaystyle d_1(x,y)=\sum _{i=1}^n|x_i-y_i|}}$$

也就是每一维的差取绝对值，再将所有维度相加。例如：

$$x=(1,2),y=(4,6)$$

则：

$$d_1(x,y)=|1-4|+|2-6|=3+4=7$$

常见距离之间的关系如下：

距离	公式	常用名称
$L_1$	${\displaystyle \sum _i|x_i-y_i|}$	曼哈顿距离
$L_2$	${\displaystyle \sqrt{\sum _i(x_i-y_i{)}^2}}$	欧氏距离
$L_{\mathrm{\infty }}$	${\displaystyle \underset{i}{max}|x_i-y_i|}$	切比雪夫距离
$L_p$	${\displaystyle {(\sum _i|x_i-y_i{|}^p)}^{1/p}}$	闵可夫斯基距离

闵可夫斯基距离是更一般的形式：

$$d_p(x,y)={(\sum _{i=1}^n|x_i-y_i{|}^p)}^{1/p}$$

取不同的 $p$ 可以得到不同距离：

$$\boxed{{\displaystyle \begin{array}{rl}p=1& ⟹\text{曼哈顿距离 }{L}_1\\ p=2& ⟹\text{欧氏距离 }{L}_2\\ p\to \mathrm{\infty }& ⟹\text{切比雪夫距离 }{L}_{\mathrm{\infty }}\end{array}}}$$

闵可夫斯基距离虽然包含曼哈顿距离，但它本身是更一般的参数化表达；只有指定 $p=1$ 时才是曼哈顿距离。对于 $p\ge 1$，该式构成标准的 $L_p$ 距离；$0<p<1$ 时通常不满足三角不等式，不能称为严格意义上的距离。

K-Means 的经典目标函数使用平方欧氏距离：

$$\sum _{k=1}^K\sum _{x_i\in C_k}\Vert x_i-{\mu }_k{\Vert }_2^2$$

使用距离度量时，要区分 K-Means 默认目标中的欧氏距离和单独定义的曼哈顿距离。改变距离度量可能改变样本分配方式，也可能需要相应调整簇中心的更新方式。

余弦相似度：方向与尺度

余弦相似度比较的是两个非零向量从原点出发的方向夹角，而不是它们之间的平移距离或长度差异：

$$\cos (u,v)=\frac{u^{\mathsf{T}}v}{\Vert u{\Vert }_2\Vert v{\Vert }_2}$$

余弦相似度是相似度指标，不是 $L_1$ 或 $L_2$ 这样的标准距离；如果把它用于聚类，通常需要相应选择样本分配和中心更新方式，不能直接保留 K-Means 的均值更新规则。

因此，余弦相似度对正比例缩放不敏感。对于 $a,b>0$：

$$\cos (au,bv)=\cos (u,v)$$

因为正比例缩放只会改变向量长度，不会改变从原点出发的射线方向。相反，给向量的每个分量加上常数，等价于移动向量终点而保持原点不动，通常会改变方向，因此余弦相似度一般也会改变。这不是“把坐标系和原点一起平移”，而是对向量本身做了加法变换。

变换	几何作用	对余弦相似度的影响
$u\mapsto au,a>0$	沿原射线伸长或缩短	不变
$u\mapsto au,a<0$	反转向量方向	若只反转一个向量，余弦相似度变为相反数
$u\mapsto u+c$	移动终点，原点不动	通常改变

余弦相似度的变换示例

设 $u=(1,2)$。它从原点指向 $(1,2)$，方向比例为 $2/1=2$。若每个分量加 $1$，得到 $u^{\prime }=(2,3)$，此时方向比例变为 $3/2=1.5$，所以方向已经改变。

若改为正比例缩放，例如 $3u=(3,6)$，方向比例仍为 $6/3=2$，只是沿原来的射线变长，余弦相似度不变。

还可以用一组正交向量观察数值变化。原来：

$$u=(1,0),v=(0,1)$$

因此：

$$\cos (u,v)=0$$

同时给两个向量的每个分量加 $1$ 后：

$$u^{\prime }=(2,1),v^{\prime }=(1,2)$$

于是：

$$\cos (u^{\prime },v^{\prime })=\frac{2\times 1+1\times 2}{\sqrt{5}\sqrt{5}}=\frac{4}{5}=0.8$$

原本的余弦相似度为 $0$，加法变换后变为 $0.8$，说明平移一般不会保持方向相似性。

余弦相似度的取值范围通常为 $[-1,1]$：接近 $1$ 表示方向相近，接近 $0$ 表示近似正交，接近 $-1$ 表示方向相反。它要求两个向量都非零；若某个向量是零向量，分母为零，余弦相似度没有定义。实际使用时还应注意，选择是否中心化、标准化会改变向量相对于原点的几何关系。

余弦相似度速记

余弦相似度看方向：正缩放不变，加常数通常改变；它对长度不敏感，但对平移不具有不变性。

1.4 高斯混合模型 GMM

GMM（Gaussian Mixture Model，高斯混合模型）假设数据由多个高斯分布混合产生：

$$\boxed{{\displaystyle p(x)=\sum _{k=1}^K{\pi }_k\mathcal{N}(x\mid {\mu }_k,{\mathrm{\Sigma }}_k)}}$$

其中：

• $K$ 是高斯成分的数量；
• ${\pi }_k$ 是第 $k$ 个成分的混合权重，满足 ${\pi }_k\ge 0$ 且 $\sum _k{\pi }_k=1$；
• ${\mu }_k$ 是均值；
• ${\mathrm{\Sigma }}_k$ 是协方差矩阵；
• $\mathcal{N}(x\mid {\mu }_k,{\mathrm{\Sigma }}_k)$ 是对应的高斯密度。

GMM 通常通过隐藏变量 $z_i$ 表示样本 $x_i$ 来自哪个高斯成分。由于 $z_i$ 不可直接观察，GMM 常使用 EM 算法估计参数。

GMM 与 K-Means 的区别

两者都可以做聚类，但建模方式不同：

方法	聚类方式	主要依据	输出
K-Means	硬聚类	到簇中心的距离	一个确定的簇编号
GMM	软聚类	属于各高斯成分的后验概率	各成分的概率或责任度

例如，对某个样本 $x$：

$$P(z=1\mid x)=0.8,P(z=2\mid x)=0.2$$

表示该样本有较大概率属于第一个高斯成分，但仍保留属于第二个成分的不确定性。K-Means 则通常直接给出一个确定的簇编号。

EM 算法中的 E 步和 M 步

GMM 中，给定当前参数，E 步计算隐藏类别的后验概率，也称责任度：

$${\gamma }_{ik}=P(z_i=k\mid x_i)=\frac{{\pi }_k\mathcal{N}(x_i\mid {\mu }_k,{\mathrm{\Sigma }}_k)}{\sum _{j=1}^K{\pi }_j\mathcal{N}(x_i\mid {\mu }_j,{\mathrm{\Sigma }}_j)}$$

因此：

M 步利用 E 步得到的责任度，重新估计 GMM 的参数：

$$N_k=\sum _{i=1}^N{\gamma }_{ik}$$$${\pi }_k=\frac{N_k}{N},{\mu }_k=\frac{1}{N_k}\sum _{i=1}^N{\gamma }_{ik}{x}_i$$

其中 $N_k$ 可以理解为第 $k$ 个高斯成分获得的有效样本数。由于每个样本的责任度在所有成分之间归一化：

$$\sum _{k=1}^K{\gamma }_{ik}=1$$

所以：

$$\sum _{k=1}^K{N}_k=N,\sum _{k=1}^K{\pi }_k=1$$

混合权重 ${\pi }_k$ 因而始终构成一个合法的概率分布。均值更新不是普通平均，而是按责任度加权的平均：

$$\boxed{{\displaystyle {\mu }_k=\frac{\sum _{i=1}^N{\gamma }_{ik}{x}_i}{\sum _{i=1}^N{\gamma }_{ik}}}}$$

责任度越大的样本，对第 $k$ 个高斯成分的新均值影响越大。

协方差也根据责任度加权更新：

$${\mathrm{\Sigma }}_k=\frac{1}{N_k}\sum _{i=1}^N{\gamma }_{ik}(x_i-{\mu }_k)(x_i-{\mu }_k{)}^{\mathsf{T}}$$

GMM 中的协方差结构不是固定只能取对角矩阵，常见选择包括：

协方差结构	含义	表达能力与代价
full	每个成分使用完整协方差矩阵	能表示特征间相关性，但参数和计算成本较高
diagonal	每个成分使用对角矩阵	假设成分内部各维不相关，计算较简单
spherical	每个成分使用一个标量方差乘单位阵	假设各方向方差相同，参数最少
tied	所有成分共享同一个协方差矩阵	在表达能力和参数量之间折中

需要区分协方差的数学合法性和模型采用的协方差结构。任意协方差矩阵都应当是对称半正定矩阵；对于使用通常多维高斯密度公式的非退化模型，通常要求 ${\mathrm{\Sigma }}_k$ 为正定矩阵：

$$p(x\mid z=k)=\frac{1}{(2\pi {)}^{d/2}|{\mathrm{\Sigma }}_k{|}^{1/2}}\exp (-\frac{1}{2}(x-{\mu }_k{)}^{\mathsf{T}}{\mathrm{\Sigma }}_k^{-1}(x-{\mu }_k))$$

正定性保证 ${\mathrm{\Sigma }}_k^{-1}$ 和 $|{\mathrm{\Sigma }}_k|$ 可以按该公式正常使用。对角协方差只是降低参数量和计算复杂度的一种建模选择，并不是 GMM 的必要条件；若协方差矩阵退化为奇异矩阵，则需要采用退化高斯的专门处理，不能直接套用上面的普通密度公式。

GMM + EM 速记

• E 步：计算隐藏类别的后验概率（责任度）。
• M 步：利用责任度更新混合权重、均值和协方差。

1.5 层次聚类

层次聚类通过不断合并或拆分样本，构造样本之间的层次结构。最常见的是自底向上的凝聚式层次聚类：

1. 开始时每个样本单独作为一个簇；
2. 根据簇间距离合并最相近的两个簇；
3. 重复合并，直到形成一棵树状结构。

最终结果通常用树状图（dendrogram）表示。选择不同的切割高度，可以得到不同粒度的扁平簇集合：

$$\text{高处切割}⟶\text{较少的大簇}$$$$\text{低处切割}⟶\text{较多的小簇}$$

因此，层次聚类并不是“只能生成固定层次结构、无法得到普通簇集合”。它先生成层次结构，再通过选择切割高度得到所需的簇划分。常见的簇间距离或链接方式包括 single linkage、complete linkage、average linkage 和 Ward linkage。

HAC 的链接准则

在凝聚式层次聚类（HAC）中，每一轮都要选择两个最接近的簇进行合并。这里的“两个簇之间的距离”不是唯一规定的，而是由链接准则（linkage criterion）定义。设两个簇为 $A$ 和 $B$，样本间距离为 $d(x,y)$：

链接准则	簇间距离定义	直观含义
Single Linkage	${\displaystyle \underset{x\in A,y\in B}{min}d(x,y)}$	看跨簇样本中最近的一对
Complete Linkage	${\displaystyle \underset{x\in A,y\in B}{max}d(x,y)}$	看跨簇样本中最远的一对
Average Linkage	${\displaystyle \frac{1}{|A||B|}\sum _{x\in A}\sum _{y\in B}d(x,y)}$	看所有跨簇点对距离的平均值
Ward Linkage	合并后簇内平方误差的增加量	选择使簇内 SSE 增加最少的合并

因此，Complete Linkage 的关键公式是：

$$\boxed{{\displaystyle d_{\mathrm{complete}}(A,B)=\underset{x\in A,y\in B}{max}d(x,y)}}$$

它会倾向于避免合并后跨度过大的簇，通常更偏好得到直径较小、较紧凑的簇。相对地，Single Linkage 只关注最近邻，容易产生“链式效应”：一串逐步相邻的样本可能被连接成很长的簇。

Ward Linkage 常在欧氏距离下使用。如果 ${\mu }_A,{\mu }_B$ 是两个簇的均值，则合并它们带来的簇内平方误差增加量可写成：

$${\mathrm{\Delta }}_{\mathrm{Ward}}(A,B)=\frac{|A||B|}{|A|+|B|}\Vert {\mu }_A-{\mu }_B{\Vert }_2^2$$

它每一步选择使 ${\mathrm{\Delta }}_{\mathrm{Ward}}$ 较小的合并，因此可以理解为“尽量控制合并后簇内方差或 SSE 的增长”。

层次聚类的特点是：

• 可以观察不同粒度下的聚类结构；
• 通常不需要像 K-Means 那样一开始就指定 $K$；
• 一旦得到层次树，可以通过不同切割高度获得不同的簇数；
• 计算和存储成本可能随样本数量增加而较高。

“不需要预先指定 $K$”不等于“能够自动判断唯一的最优簇数”。实际使用时仍需根据树状图、领域知识或验证指标选择切割高度，或者直接指定希望得到的簇数。

1.6 DBSCAN 密度聚类

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）根据局部密度形成簇，主要参数是：

• $\epsilon$：邻域半径；
• MinPts：一个点邻域内被视为高密度所需的最少样本数。

对样本 $x$，其 $\epsilon$-邻域可以写成：

$$N_{\epsilon }(x)=\{x_i\mid \Vert x_i-x{\Vert }_2\le \epsilon \}$$

若邻域内的样本数达到 MinPts，则 $x$ 被称为核心点。一个点可以从核心点出发沿着一串相邻核心点密度可达；彼此能够通过这样的密度关系连接起来的样本构成一个簇。既不属于高密度区域、也不能从核心点密度可达的样本，则可以被标记为噪声点。

DBSCAN 不要求预先指定簇数 $K$，而是根据密度连通关系自动形成簇。它还可以把不属于任何高密度区域的样本标记为噪声或异常点：

DBSCAN 速记

不需要预先指定簇数 $K$，并且能够识别噪声点。

直观上，DBSCAN 会把密集且相互可达的样本连成一簇，而把孤立点保留为 Noise。它能够发现非球形簇，这是基于到中心距离的 K-Means 不容易处理的情况。

DBSCAN 的优势包括：

• 不需要事先指定簇数；
• 可以识别噪声点和离群点；
• 可以发现任意形状的高密度区域。

它的局限包括：

• 对 $\epsilon$ 和 MinPts 的选择敏感；
• 不同簇密度差异很大时，单一密度阈值可能不合适；
• 高维空间中的距离和密度判断可能退化。

按聚类机制分类

除了按具体算法记忆，还可以按“簇是如何形成的”进行归类：

聚类类型	核心做法	典型算法	常见特点
划分式聚类	直接把样本划分为若干簇	K-Means、K-Means++、K-Medoids	通常需要指定簇数或其他规模参数
层次聚类	逐步合并或拆分簇，形成树状结构	Agglomerative、Divisive	可通过切割树状图得到不同粒度的结果
密度聚类	根据密度连通区域形成簇	DBSCAN	不必指定 $K$，可以识别噪声和任意形状
模型聚类	假设数据来自若干概率分布	GMM	通过概率或责任度表达软归属
图聚类	根据样本相似图构造嵌入后聚类	谱聚类	利用图结构，适合非凸或非球形簇

K-Means++ 中的“++”表示更合理的初始中心选择策略：它倾向于选择彼此分散的初始中心，以降低 K-Means 落入较差局部最优的概率。K-Means++ 仍然使用 K-Means 的均值中心、样本分配和 SSE 目标，不是与 K-Means 完全不同的聚类目标。

层次聚类还可以按构造方向区分：

• Agglomerative（凝聚式、自底向上）：从每个样本各自成簇开始，不断合并簇；
• Divisive（分裂式、自顶向下）：从所有样本组成一个簇开始，不断拆分簇。

1.7 聚类算法对比

算法	核心思想	是否需要预先指定 $K$	聚类结果或特殊能力
K-Means	距离均值中心、反复更新中心	通常需要	硬聚类，容易受异常值影响
GMM	多个高斯分布混合	通常需要成分数	软聚类，输出概率
层次聚类	构造树状层次结构	不必一开始指定	需选择切割高度得到簇数
DBSCAN	根据局部密度连通	不需要	任意形状聚类、识别噪声
谱聚类	相似度图与图拉普拉斯特征分解	通常需要	适合非凸、非球形簇，但分解成本较高

聚类算法的高频辨析点是：

• K-Means 每轮进行“分配样本 → 重新计算簇中心”；
• GMM 是软聚类，一个样本可以对多个簇具有不同归属概率；
• 层次聚类可以通过切割树状图得到不同数量的扁平簇；
• DBSCAN 不需要提前指定簇数，并且能够识别噪声点；
• K-Means++ 主要改进初始中心选择，仍属于 K-Means 的划分式聚类框架；
• Agglomerative 是自底向上合并，Divisive 是自顶向下拆分；
• HAC 的 Single、Complete、Average、Ward 分别对应最近点、最远点、平均距离和合并后 SSE 增量；
• 谱聚类先构造相似度图，再在图拉普拉斯特征向量构成的低维空间中聚类。

1.8 谱聚类

谱聚类（Spectral Clustering）把样本看成图中的节点，把样本之间的相似性看成边的权重。它不直接在原始特征空间中寻找若干个几何中心，而是先利用图结构提取样本的低维表示，再进行聚类。

典型流程是：

$$\text{样本}⟶\text{相似度图}⟶\text{图拉普拉斯矩阵}⟶\text{特征值分解}⟶\text{低维嵌入}⟶K\text{-Means}$$

图拉普拉斯矩阵

设 $n$ 个样本构成相似度矩阵 $W$，其中 $W_{ij}$ 表示样本 $x_i$ 与 $x_j$ 的相似度。常见做法是使用高斯核：

$$W_{ij}=\exp (-\frac{\Vert x_i-x_j{\Vert }_2^2}{2{\sigma }^2})$$

也可以只连接 $k$ 近邻，以得到稀疏相似度图。由 $W$ 定义度矩阵 $D$：

$$D_{ii}=\sum _{j=1}^n{W}_{ij}$$

最基本的未归一化图拉普拉斯矩阵为：

$$\boxed{{\displaystyle L=D-W}}$$

实际算法还可能使用归一化图拉普拉斯矩阵，例如：

$$L_{\mathrm{sym}}=D^{-1/2}L{D}^{-1/2}$$

不同变体的具体矩阵形式略有区别，但共同思想都是利用图的连接结构表示样本之间的相似关系。

特征分解与低维嵌入

求图拉普拉斯矩阵最小的 $K$ 个特征值对应的特征向量：

$$L{u}_j={\lambda }_j{u}_j$$

将这些特征向量按列组成矩阵：

$$U=[u_1,u_2,\dots ,u_K]\in {\mathbb{R}}^{n\times K}$$

矩阵 $U$ 的第 $i$ 行可以看作样本 $x_i$ 在新的低维空间中的表示。最后对 $U$ 的各行使用 K-Means，得到样本的簇划分。这里的特征分解承担的是图嵌入或降维作用，K-Means 才是最后执行簇划分的步骤。

因此，谱聚类本身的核心不是在原始空间中反复更新簇中心；如果流程最后使用 K-Means，更新的也是图嵌入空间中的中心。相似度图和特征值分解会带来较高的存储与计算开销，这也是谱聚类在超大规模数据上通常需要稀疏图或近似算法的原因。

为什么能处理非凸簇？

K-Means 直接依据样本到均值中心的欧氏距离优化簇内平方误差，因此更适合近似球形或凸形的簇。谱聚类先利用相似度图保留局部连接关系，即使两个样本在原空间中不适合用一个中心描述，只要它们在图上具有较强的连通结构，也可能在低维嵌入空间中被分开。

因此，谱聚类常用于：

• 非球形或非凸形状的簇；
• 由局部相似关系定义的聚类任务；
• 样本关系比原始坐标更重要的场景。

与其他聚类算法的辨析

算法	中心或结构	是否能识别噪声	典型特点
K-Means	簇内样本的均值中心	通常不能单独标记	指定 $K$，适合中心型簇
K-Medoids	簇内实际样本中的代表点	通常不能单独标记	对异常值通常比均值中心更稳健
DBSCAN	局部密度与密度连通	可以	不必指定 $K$，可发现任意形状簇
层次聚类	合并或拆分形成的树状结构	不是核心机制	可按树状图的不同高度切割
谱聚类	相似度图与图拉普拉斯特征向量	不是核心机制	适合非凸簇，通常在嵌入空间中使用 K-Means

需要特别区分“中心”的含义：

• K-Means 更新的是簇内样本的均值，均值不一定是原数据中的某个样本；
• K-Medoids 选择的是簇内一个实际存在的样本作为代表点，也就是 medoid；
• 谱聚类不以某个原始空间中的中心点作为核心，而是通过图结构构造新的嵌入。

谱聚类的代价主要来自相似度图的构造和特征值分解。样本量较大时，通常使用稀疏近邻图、近似特征分解等方式降低存储和计算成本。

二、矩阵分解在推荐系统中的应用

推荐系统常把用户和物品的交互记录组织成用户-物品矩阵：

$$R\in {\mathbb{R}}^{n_u\times n_i}$$

其中 $R_{ui}$ 可以表示用户 $u$ 对物品 $i$ 的评分或交互强度。实际数据通常存在大量未观测项，因此推荐模型的目标不是机械地补全所有零值，而是利用已观测交互学习用户和物品的潜在表示。

2.1 潜在因子矩阵分解

矩阵分解用低维潜在向量表示用户和物品：

$$\boxed{{\displaystyle R\approx U{V}^{\mathsf{T}}}}$$

其中：

• $U\in {\mathbb{R}}^{n_u\times k}$：用户潜在表示；
• $V\in {\mathbb{R}}^{n_i\times k}$：物品潜在表示；
• $k$：潜在因子维度，通常远小于用户数和物品数。

用户 $u$ 对物品 $i$ 的预测评分可以写成：

$${\hat{r}}_{ui}=u_u^{\mathsf{T}}{v}_i$$

也可以加入用户偏置和物品偏置：

$${\hat{r}}_{ui}=\mu +b_u+b_i+u_u^{\mathsf{T}}{v}_i$$

只在已观测交互集合 $\mathrm{\Omega }$ 上训练时，一个常见目标是：

$$\underset{U,V}{min}\sum _{(u,i)\in \mathrm{\Omega }}{(r_{ui}-u_u^{\mathsf{T}}{v}_i)}^2+\lambda (\Vert U{\Vert }_F^2+\Vert V{\Vert }_F^2)$$

这说明推荐系统中的矩阵分解既包含低秩建模，也包含对缺失交互的预测。

2.2 PCA：特征降维与去噪

PCA 可以把高维用户特征、物品特征或交互衍生特征压缩为低维表示：

$$X\in {\mathbb{R}}^{n\times d}⟶Z\in {\mathbb{R}}^{n\times k},k<d$$

它主要用于：

• 降低特征维度；
• 去除部分噪声；
• 减少后续计算量；
• 提取方差较大的主要方向。

PCA 通常是推荐流程中的预处理或表示学习工具，而不是直接针对缺失评分进行预测的协同过滤模型。对中心化数据做 SVD，可以高效实现 PCA。

2.3 NMF：非负潜在因子

NMF（Non-negative Matrix Factorization，非负矩阵分解）要求矩阵及其因子非负：

$$\boxed{{\displaystyle R\approx WH,R\ge 0,W\ge 0,H\ge 0}}$$

非负约束使潜在因子更容易解释为“部分的叠加”。在用户-物品评分矩阵中，可以把 $W$ 理解为用户对潜在兴趣的强度，把 $H$ 理解为物品在潜在属性上的强度。例如潜在因子可能对应动作片、科幻片或喜剧片偏好。

NMF 的特点是：

• 适合非负评分、计数或交互强度；
• 潜在因子通常具有较好的可解释性；
• 属于低秩分解和潜在因子建模方法；
• 真实推荐数据有缺失项时，也需要通过掩码或只在观测项上优化。

2.4 QR：推荐模型训练中的数值求解工具

QR 分解写成：

$$\boxed{{\displaystyle A=QR}}$$

其中 $Q$ 的列正交，$R$ 是上三角矩阵。QR 常用于稳定地求解最小二乘问题：

$$\underset{x}{min}\Vert Ax-b{\Vert }_2^2$$

推荐系统训练潜在因子时，如果固定物品矩阵 $V$，求用户矩阵 $U$ 的过程可能分解成许多最小二乘子问题。例如固定所有物品向量后，某个用户向量可以通过下式求解：

$$\underset{u_u}{min}\sum _{i\in {\mathrm{\Omega }}_u}{(r_{ui}-u_u^{\mathsf{T}}{v}_i)}^2+\lambda \Vert u_u{\Vert }_2^2$$

这类子问题可以使用 QR 等数值线性代数工具求解。因此 QR 虽然不是直接输出推荐结果的协同过滤算法，但可以作为推荐模型训练过程中的数值求解方法。

2.5 SVD：低秩近似与协同过滤

对一个适合分解的评分矩阵，可以做奇异值分解：

$$R=U\mathrm{\Sigma }{V}^{\mathsf{T}}$$

保留最大的 $k$ 个奇异值，得到：

$$R_k=U_k{\mathrm{\Sigma }}_k{V}_k^{\mathsf{T}}$$

低秩矩阵 $R_k$ 可以提取用户和物品的潜在结构，用于近似已知评分并预测部分未观测交互。这是经典协同过滤中矩阵分解思想的重要形式。

不过，标准 SVD 通常要求输入矩阵相对完整，而真实推荐矩阵往往有大量缺失项。实际系统一般会使用带观测掩码的矩阵分解、加权矩阵分解或交替最小二乘等方法，不能简单把所有缺失评分都当成真实的零分再直接做普通 SVD。

2.6 推荐系统中的矩阵分解方法对比

方法	在推荐系统中的主要角色	典型特点
PCA	用户/物品特征降维、去噪	无监督，提取主方向
NMF	非负潜在因子建模	因子非负，解释性较强
QR	训练过程中的最小二乘求解	数值求解工具，不直接定义推荐模型
SVD	低秩近似、经典协同过滤	用奇异值和奇异向量提取潜在结构

因此，“矩阵分解方法在推荐系统中的应用”是一个较宽的概念。判断时要区分：

• 直接学习用户-物品潜在因子的模型：如 SVD 形式的矩阵分解、NMF；
• 用于特征压缩和去噪的表示工具：如 PCA；
• 用于训练子问题求解的数值工具：如 QR。

这些方法的作用不同，但都可能出现在推荐系统的数据处理、模型建模或训练求解流程中。