分布式处理与计算：数据降维

一、主成分分析(PCA)

PCA(Principal Component Analysis)，即主成分分析方法，是一种使用最广泛的数据降维算法。PCA的主要思想是将n维特征映射到k维上，这k维是全新的正交特征也被称为主成分，是在原有n维特征的基础上重新构造出来的k维特征。PCA的工作就是从原始的空间中顺序地找一组相互正交的坐标轴，新的坐标轴的选择与数据本身是密切相关的。其中，第一个新坐标轴选择是原始数据中方差最大的方向，第二个新坐标轴选取是与第一个坐标轴正交的平面中使得方差最大的，第三个轴是与第1,2个轴正交的平面中方差最大的。依次类推，可以得到n个这样的坐标轴。通过这种方式获得的新的坐标轴，我们发现，大部分方差都包含在前面k个坐标轴中，后面的坐标轴所含的方差几乎为0。于是，我们可以忽略余下的坐标轴，只保留前面k个含有绝大部分方差的坐标轴。事实上，这相当于只保留包含绝大部分方差的维度特征，而忽略包含方差几乎为0的特征维度，实现对数据特征的降维处理。

PCA 的目标是把高维数据投影到少数几个方向上,既保留尽量多的信息,又大幅降低维度。它有两个等价的视角:最大方差投影和最小重构误差——两条路推出来的最优方向是同一组特征向量。

*视角一:从最大方差考虑

给定训练样本 $x_1, \dots, x_n$,其中 $x_i \in \mathbb{R}^p$。假设数据已被标准化(中心化),使得 $\sum_i x_i = 0$。PCA 想找一个方向 $w$(单位向量),使得原始数据在该方向上的投影 $w^{\top}x_i$ 的方差最大。

投影后的方差为

$\frac{1}{n}\sum_{i=1}^{n}(w^{\top}x_i)^2 = w^{\top}\Big(\frac{1}{n}\sum_i x_i x_i^{\top}\Big)w = w^{\top}\Sigma w$

其中 $\Sigma = \frac{1}{n}\sum_i x_i x_i^{\top}$ 是样本协方差矩阵。于是优化问题写成(约束 $w$ 为单位向量):

$\max_{w}\ w^{\top}\Sigma w \quad \text{s.t.}\quad w^{\top}w = 1$

用拉格朗日乘子法,构造 $L = w^{\top}\Sigma w - \lambda(w^{\top}w - 1)$,对 $w$ 求偏导并令其为零:

$\frac{\partial L}{\partial w} = 2\Sigma w - 2\lambda w = 0 \ \Longrightarrow\ \Sigma w = \lambda w$

这正是特征方程。所以最优的 $w$ 就是协方差矩阵 $\Sigma$ 的最大特征值所对应的特征向量(此时方差 $w^{\top}\Sigma w = \lambda$ 取最大)。

求第二个主成分:要求它在最大化方差的同时,与第一个主成分 $w_1$ 正交。优化问题为

$\max_{w_2}\ w_2^{\top}\Sigma w_2 \quad \text{s.t.}\quad w_2^{\top}w_2 = 1,\ w_2^{\top}w_1 = 0$

用带两个乘子的拉格朗日函数求导,可以得到 $\Sigma w_2 = \lambda_2 w_2$,即 $w_2$ 是第二大特征值对应的特征向量。依此类推,前 $d$ 个主成分就是 $\Sigma$ 前 $d$ 大特征值对应的特征向量。

视角二:从最小重构误差考虑

换个角度:找一组正交基底 $\{u_1, \dots, u_p\}$($u_j^{\top}u_k = \delta_{jk}$),把每个样本用这组基表示。只保留前 $d$ 个基方向做投影,得到近似(重构):

$\hat{x}_i = \sum_{j=1}^{d}(u_j^{\top}x_i)\,u_j$

PCA 尝试最小化重构误差——原始点与其低维重构之间的平方距离之和:

$\min_{\{u_j\}}\ \sum_{i=1}^{n}\big\|x_i - \hat{x}_i\big\|^2$

推导后可以证明,这等价于取协方差矩阵前 $d$ 个最大特征值对应的特征向量作为基底。也就是说,"投影后方差最大"与"重构误差最小"选出的是同一组方向——这就是 PCA 两个视角的统一。

二、正则化框架下的降维

除了 PCA 这种"换基投影"的降维,还可以在正则化框架下做降维:通过在损失里加惩罚项,让部分参数被压成 0,从而自动做变量选择(相当于在原始特征维度上降维)。

基于正则化框架的方法尝试解决如下问题:

$\min_{\beta}\ \frac{1}{2}\sum_{i=1}^{n}\big(y_i - \beta_0 - x_i^{\top}\beta\big)^2 + \lambda\, P(\beta)$

可以通过中心化把常数项 $\beta_0$ 移除(中心化后截距为 0),进而得到只含 $\beta$ 的形式。

Lasso 估计取惩罚项为 $L_1$ 范数,即

$\hat\beta^{\text{Lasso}} = \arg\min_{\beta}\ \frac{1}{2}\|y - X\beta\|^2 + \lambda\|\beta\|_1$

它等价于带约束形式 $\min \frac{1}{2}\|y-X\beta\|^2$ s.t. $\|\beta\|_1 \le t$。

L1 正则化产生稀疏性的原理

为什么 L1 正则能让模型参数变稀疏(很多恰好为 0)?

考虑最简单的一维情形。原始目标函数加上 L1 正则项后,目标函数变成 $f(\beta) + \lambda|\beta|$。此时最小值点常常恰好落在 $\beta = 0$ 处,于是产生了稀疏性。

原因很直观:加入 L1 正则项后,对带正则项的目标函数求导,正则项部分产生的导数在原点左边是 $-\lambda$、在原点右边是 $+\lambda$(因为 $|\beta|$ 的导数是 $\text{sign}(\beta)$)。因此,只要原目标函数在原点处导数的绝对值小于 $\lambda$,那么带正则项的目标函数在原点左边始终递减、在原点右边始终递增——最小值点自然就卡在原点 $\beta=0$ 处,该参数被直接压到 0。

对比之下,L2 正则项 $\lambda\beta^2$ 在原点的导数是 0(平滑),不会制造这种"尖角",所以 L2 只会把参数压小、不会压到恰好为 0。这就是 L1 稀疏、L2 不稀疏的根本原因。

三、总结

• PCA 两视角等价:最大方差投影 ⟺ 最小重构误差,选出的都是协方差矩阵 Σ 的前 d 大特征值对应的特征向量。
• 最大方差推导:$\max w^{\top}\Sigma w$ s.t. $\|w\|=1$ → 拉格朗日求导得 $\Sigma w=\lambda w$ → 最优方向是最大特征值的特征向量,方差就等于该特征值。
• 主成分排序:第 k 个主成分 = 第 k 大特征值对应的特征向量,且与前面的主成分正交。
• 前提:数据要先中心化(标准化)。
• 正则化降维:在损失上加惩罚做变量选择;Lasso = 平方损失 + λ‖β‖₁。
• L1 稀疏原理:|β| 的导数在原点左 −λ、右 +λ;只要原目标在原点导数绝对值 < λ,最小值就卡在 β=0,产生稀疏。L2 平滑无尖角,只压小不压零。