跳转至

降维

动机

有一些机器学习算法的样本可能包含成百上千个特征. 这就会导致训练时候的维度很高, 进而导致训练速度变慢, 不可靠的分类(样本在高维空间的分布非常稀疏), 过拟合, 不易于解释, 无法可视化(人类只能翻译低维数据, 最高\(3\)维). 并且不是所有的特征对于结果都是重要的, 需要的是找到一小个必须的, 充分的特征子集以进行分类. 降维就是一个除去多余的, 重复的特征并减少噪音的过程.

PCA

Principle Component Analysis (PCA), 主成分分析, 是一种最人们的降维方法, 又被称为特征投影方法. 主要思想是找到一个当前维度的子维度, 然后将数据投影到新的维度上. 新的维度对应的训练集(投影)可以被用作机器学习算法的输入用于训练模型.

现在, 我们来看一个例子, 请解答, 下列数据沿着哪根轴的离散程度最大, \(X\)还是\(Y\)?

答案是\(X\)轴.

我们再来看另一个例子, 请解答, 下列数据沿着哪根轴的离散程度最大, \(X\), \(Y\)还是其他轴?

答案是\(Z_1\)轴, 如图所示.

注意看上图, 我们有两个多出来的轴, 一个是\(Z_1\), 另一个是\(Z_2\), \(Z_1\)方向的离散程度是最大的, \(Z_2\)方向的离散程度是最小的. 事实上, \(Z_1\)和\(Z_2\)是\(X\)和\(Y\)的线性组合: \(Z_1=1\times X+1\times Y\), \(Z_2=-1\times X+1\times Y\). 事实上, 我们可以想象, 将这些数据投影到\(Z_1\)轴上, 投影后的值为在\(Z_1\)轴上的坐标, 投影后的值的方差(关于什么是方差, 请见这里)表示的就是数据的离散程度, 而数据分布越离散, 每个数据点的概率取值就比较小, 此时该分布的熵就更大, 包含更多信息.1

现在, 有\(N\)个样本, 每个样本有\(m\)个特征(维度), 目标是找到\(k\)个新的坐标轴\(Z_1, Z_2, ..., Z_k(k<m)\), 这些坐标轴之间相互正交(不相关)且数据在轴上离散程度的排序为\(Var(Z_1)>Var(Z_2)>...>Var(Z_k)\), 我们称\(Z_1, ..., Z_k\)是主成分. 主成分是在数据中找到的新的坐标轴, 这些坐标轴按照数据在上面离散程度(方差)的大小进行排序, 每个主成分都是原始特征的线性组合. 第一个主成分是使得数据方差最大的方向, 第二个主成分是与第一个主成分正交的条件下, 方差最大的方向, 依此类推... 由于我们选出的是\(k\)个轴, 所以原始数据从\(m\)维降为了\(k\)维. 如果我们选择了\(k=m\)个轴, 则相当于没有降维, 也就是说仅仅只是更换了坐标系, 复杂程度没有降低.

对于上面的例子, 原始维度为\(2\)维, 坐标轴为\(X\)和\(Y\), \(Z_1\)是数据方差最大的方向, 我们通过线性组合\(X\)和\(Y\), 将数据降为\(1\)维. 如图, 红色的点就是将原始绿点映射到第一主成分\(Z_1\)后的数据, 我们只需要用\(Z_1\)的坐标描述红点就行了.

确定PC的数量

由于所有的主成分都是正交的, 所以彼此之间是不相关的, 因此这些主成分之间的方差满足\(Var(X+Y)=Var(X)+Var(Y)\), 即样本的总方差等于所有主成分的方差之和.

那么, 我们怎么选择需要多少的主成分呢? 是一个? 两个? 还是\(m-1\)个? 主要的方法有两种:

  1. 设置一个最小方差百分比, 比如\(95\%\), 然后选择前\(k\)个主成分\(Z_1, Z_2, ..., Z_k\), 使得它们能够解释总方差的\(95\%\). 如你有一个包含\(100\)个特征的数据集, 通过PCA, 你计算出每个主成分能够解释的方差百分比, 结果如下: 第一个主成分解释了\(40\%\)的方差, 第二个主成分解释了\(30\%\)的方差, 第三个主成分解释了\(15\%\)的方差, 第四个主成分解释了\(10\%\)的方差, 其余的\(96\)个主成分解释了\(5\%\)的方差, 如果你想保留总方差的\(95\%\), 你可以选择前四个主成分, 来替代原来的\(100\)个主成分

  2. 肘部法, Elbow Method. 绘制主成分的数量和累积方差图, 通常会在曲线上出现一个"肘点", 表示方差的增长速度开始减缓的地方, 这通常是一个合理的选择, 因为在此之后增加更多的维度带来的方差增益有限, 如下图, 总方差的\(95\%\)对应的是\(153\)维, 而肘点对应的是\(100\)维

确定PC

我们可以通过奇异值分解, Singular Value Decomposition, SVD确定PC. 它是一种标准的矩阵分解方法, 能够进行坐标系的变换. 具体来说, 任何一个\(n\times m(n\geq m)\)的矩阵\(\bm{X}\)可以被分解为三个矩阵的乘积: \(\bm{X}=\bm{U}\times \bm{\Lambda} \times \bm{V^T}\), 其中:

  • \(\bm{U}\): 这是一个\(n\times m\)(无降维), \(n\times k\)(有降维)的正交矩阵
  • \(\bm{V^T}\): 这是一个\(m\times m\)(无降维), \(k\times m\)(有降维)的正交矩阵\(V\)的转置
  • \(\bm{\Lambda}\): 这是一个\(m\times m\)(无降维), \(k\times k\)(有降维)的对角矩阵, 其中包含奇异值

对应到PCA中, 这些矩阵的含义是:

  • \(\bm{X}\): 原始样本数据, 原始坐标系
  • \(\bm{U}\): 数据在新坐标系(左奇异向量空间)中的表示, 如第\(i\)行的数据包含的是在新坐标系下的坐标, 即投影后的新坐标
  • \(\bm{\Lambda}\): 数据在新坐标系中尺度的变化. 每个奇异值\(\lambda_i\)对应一个特定方向(特定主成分), 表示数据在该方向上的尺度或者重要性, 奇异值越大, 意味着数据在对应方向上的变动越大, 离散程度越高, 方差越大, 熵越大, 在主成分排序里面越靠前
  • \(\bm{V}\): 定义了新的坐标系(右奇异向量空间)

经过分解后, 原始样本数据可以被写为\(\bm{X}=\lambda_1\bm{u_1}\bm{v_1}^T+\lambda_2\bm{u_2}\bm{v_2}^T+...+\lambda_m\bm{u_m}\bm{v_m}^T\), 其中, \(\bm{v_1}\), \(\bm{v_2}, ..., \bm{v_m}\)对应的就是第\(1\)到第\(m\)主成分. 对于降维操作来说, 我们只需要其中的\(k(k<m)\)个主成分, 所以\(\bm{X}_{reduced}=\lambda_1\bm{u_1}\bm{v_1}^T+\lambda_2\bm{u_2}\bm{v_2}^T+...+\lambda_k\bm{u_k}\bm{v_k}^T\)

可以在这里找到一个例子.

压缩

举一个灰度图像压缩的例子. 对于一张没有压缩的灰度图像, 有\(n\times m\)像素, 在未压缩之前, 我们需要存储\(n\times m\)个整数.

现在, 我们进行压缩. 我们会取前\(k\)个主成分, 我们需要存储:

  • \(k\)个奇异值
  • \(\bm{U}\)矩阵的前\(k\)列, 总共\(k\times n\)个数
  • \(\bm{V}\)矩阵的前\(k\)列, 总共\(k\times m\)个数

总共, 需要存储\(k\times (1+n+m)\)个数. 压缩率为\(r=\frac{k(1+n+m)}{n\times m}\). 下面是一张表示压缩前和压缩后显著差异的图示.

  1. 郑之杰. (2011, April 20). 主成分分析(Principal Component Analysis, PCA). 郑之杰的个人网站. https://0809zheng.github.io/2020/04/11/PCA.html ↩