数据降维

一、维度灾难

  1. 近邻法要求样本点比较密集。给定测试样本点 ,理论上希望在 附近距离 范围内总能找到一个训练样本 ,其中 是个充分小的正数。即:要求训练样本的采样密度足够大,也称作“密采样”。

    • 假设 , 且假设样本点只有一个特征,且该特征归一化后范围是 [0,1] ,则需要 1000 个样本点平均分布在 [0,1] 之间。

      此时任何测试样本在其附近 0.001 距离范围内总能找到一个训练样本。

    • 假设 , 且假设样本点只有十个特征,且该特征归一化后范围是 [0,1],则需要 个样本点平均分布[0,1] 之间。

      此时任何测试样本在其附近 0.001 距离范围内总能找到一个训练样本。

  2. 现实应用中特征维度经常成千上万,要满足密采样所需的样本数目是个天文数字。

    另外许多学习方法都涉及距离计算,而高维空间会给距离计算带来很大的麻烦(高维空间中计算内积都麻烦)。

    在高维情形下出现的数据样本稀疏、距离计算困难等问题是所有机器学习方法共同面临的严重障碍,称作“维度灾难”(curse of dimensionality)。

  3. 缓解维度灾难的一个重要途径是降维(dimension reduction)。

    降维之所以有效的原因是:人们观测或者收集到的数据样本虽然是高维的,但是与学习任务密切相关的也许仅仅是某个低维分布,即高维空间中的一个低维“嵌入”。

  4. 常见的降维方法:

    • 监督降维算法。如:线性判别分析Linear Discriminant Analysis:LDA
    • 无监督降维算法。如:主成分分析PCA
  5. 对于降维效果的评估,通常是比较降维前后学习器的性能。如果性能有所提高,则认为降维起了作用。

    也可以将维数降至二维或者三维,然后通过可视化技术来直观地判断降维效果。

  6. 对于常见的降维算法,无论是PCA 还是流形学习,都是基于距离来计算重构误差。此时建议对特征进行标准化,因为距离的计算依赖于特征的量纲。如身高特征:

    • 如果采用m量纲,则取值范围通常在1~2 之间。
    • 如果采用cm 量纲,则取值范围通常在100~200 之间。

    采用不同的量纲会导致不同的重构误差。

二、主成分分析 PCA

  1. 主成分分析Principal Component Analysis:PCA是最常用的一种降维方法。

2.1 PCA 原理

2.1.1 坐标变换

  1. 给定数据集 ,其中 。假定样本经过了中心化,即:

    • 称作数据集 的中心向量,它的各元素就是各个特征的均值。
    • 之所以进行中心化,是因为经过中心化之后常规的线性变换就是绕原点的旋转变换,也就是坐标变换。
  2. 假设坐标变换矩阵为 ,经过变换之后样本 的坐标为: 。其中

    ,它表示样本 降低到 维度。令 ,则有:

    根据坐标变换矩阵的性质,有:

  3. 对数据集 中的样本 ,降维后的数据为 。令:

    的第 行就是样本 的第 行就是降维后的数据

    • ,它表示 的第 列,也就是原始的第 个特征。
    • ,它表示 的第 列 ,也就是降维之后的第 个特征。

    则根据 ,有 :

    因此降维的物理意义为:通过线性组合原始特征,从而去掉一些冗余的或者不重要的特征、保留重要的特征。

2.1.2 重构误差

  1. 考虑对 进行重构,重构之后的样本为:

    对整个数据集 所有重建样本与原始样本的误差为:

  2. 根据定义有:

    由于 是标量,所以有:

    由于标量的转置等于它本身,所以有:

    则有:

  3. 根据 的定义,可以证明( 为矩阵的Frobenius范数):

    证明:

    则有:

    将最后的下标从 替换为 即可得证。

  4. PCA降维要求重构误差最小。现在求解最优化问题:

    • 因为矩阵及其转置的迹相等,因此

      由于可以在 中调整矩阵的顺序,则

      考虑到:

      代入上式有:

      于是有:

    • 由于 无关,因此:

    • 调整矩阵顺序,则有: 。其约束条件为:

  5. PCA 最优化问题需要求解就是 的特征值。

    • 只需要对矩阵 进行特征值分解,将求得的特征值排序: 。然后取前 个特征值对应的单位特征向量构成坐标变换矩阵
    • 当样本数据进行了中心化时 , 就是样本集的协方差矩阵。这也是为什么需要对样本进行中心化的一个原因。

2.2 PCA 算法

  1. PCA 算法:

    • 输入:

      • 样本集
      • 低维空间维数
    • 输出:投影矩阵

    • 算法步骤:

      • 对所有样本进行中心化操作:
      • 计算样本的协方差矩阵
      • 对协方差矩阵 做特征值分解。
      • 取最大的 个特征值对应的单位特征向量 ,构造投影矩阵
  2. 通常低维空间维数 的选取有两种方法:

    • 通过交叉验证法选取较好的 。“比较好”指的是在降维后的学习器的性能比较好。

    • 从算法原理的角度设置一个阈值,比如 ,然后选取使得下式成立的最小的 的值:

      其中 从大到小排列。

2.3 性质

  1. 从物理意义上看: 给定协方差矩阵 ,通过坐标变换将其对角化为矩阵:

    这相当于在新的坐标系中:

    • 任意一对特征之间的协方差为 0 。
    • 单个特征的方差为

    即:数据在每个维度上尽可能分散,且任意两个维度之间不相关。

    降维的过程就是寻找这样的一个坐标变换,也就是坐标变换矩阵

    由于协方差矩阵 是对称矩阵,根据实对称矩阵的性质,这样的坐标变换矩阵一定存在。

  2. PCA算法中,低维空间与高维空间必然不相同。因为末尾 个最小的特征值对应的特征向量被抛弃了,这就是降维导致的结果。

    • 舍弃这部分信息之后能使得样本的采样密度增大(因为维数降低了),这是缓解维度灾难的重要手段。
    • 当数据受到噪声影响时,最小特征值对应的特征向量往往与噪声有关,将它们舍弃能在一定程度上起到降噪的效果。
  3. PCA降低了输入数据的维度同时保留了主要信息/能量,但是这个主要信息只是针对训练集的,而且这个主要信息未必是重要信息。

    有可能舍弃了一些看似无用的信息,但是这些看似无用的信息恰好是重要信息,只是在训练集上没有很大的表现,所以PCA也可能加剧了过拟合。

  4. PCA中训练样本越多越好。

    • 如果训练样本太少,则训练集很有可能“偶然”近似落在同一个平面上。

    • 极端情况下,如果样本数量小于目标维度,比如样本数量为 100,目标维度为 1000 维。则这 100个样本总可以构成一个 1000 维的平面,且这样的平面有无穷多个。此时如果进行PCA降维,则前几个特征值 占比非常大。

      但是如果将样本数量扩充为 10000 ,则这些样本构成一个 1000 维的平面的巧合就几乎很难成立。此时如果进行PCA降维,则前几个特征值 占比就会降低。

    • 本质上是因为 决定了协方差矩阵 的秩的上界。

      较小时, 也会很小,导致大量的特征值 为 0 。

  5. PCA不仅将数据压缩到低维,它也使得降维之后的数据各特征相互独立。

    注意:PCA推导过程中,并没有要求数据中心化;但是在推导协方差矩阵时,要求数据中心化。此时:

    其中:

    • 的最大的 个特征值组成的对角矩阵。
    • 为降维后的样本集组成的矩阵。
  6. 对于训练集、验证集、测试集,当对训练集进行PCA 降维时,也需要对验证集、测试集执行同样的降维。

    注意:对验证集、测试集执行中心化操作时,中心向量必须从训练集计算而来。不能使用验证集的中心向量,也不能用测试集的中心向量。

2.4 最大可分性

  1. PCA降维的准则有两个:

    • 最近重构性:样本集中所有点,重构后的点距离原来的点的误差之和最小(就是前面介绍的内容)。
    • 最大可分性:样本点在低维空间的投影尽可能分开。
  2. 可以证明,最近重构性就等价于最大可分性。证明如下:

    对于样本点 , 它在降维后空间中的投影是 。 则有:

    由于样本数据进行了中心化,则投影后样本点的方差是:

    根据 的定义,有: 。则样本点的方差最大的优化目标可写作:

    这就是前面最近重构性推导的结果。

  3. LDA 也可以用于降维。对于2维空间降低到1维直线的情况下,它设法将样例投影到某一条直线上,使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离。

    • LDA 考虑的是:向类别区分最大的方向投影。如下图中的绿色投影直线。
    • PCA 考虑的是:向方差最大的方向投影。如下图中的紫色投影直线。

    因此LDA 降维对于类别的区分效果要好的多。

    pca_lda

2.5 PCA 与 SVD

  1. 酉矩阵:若 阶矩阵满足 ,则它是酉矩阵。其中 的共轭转置。

    为酉矩阵的充要条件是:

  2. 奇异值分解:设 阶矩阵,且 ,则存在 阶酉矩阵 阶酉矩阵 ,使得:

    其中

    称作矩阵 的奇异值。

  3. 根据酉矩阵的性质, ,则有:

    则有 , 其中 是个 阶对角矩阵:

  4. 由数据集 中样本构成的 为实矩阵,因此有 。另外考虑到 为实对称矩阵,因此 也是实矩阵,因此 。 则有:

    • 根据 ,则有:

    • 根据 是个对角矩阵的性质,有: ,则有:

      就是的 特征值, 其对应的单位特征向量组成正交矩阵

      因此SVD奇异值分解等价于PCA主成分分析,核心都是求解 的特征值以及对应的单位特征向量。

三、核化线性降维 KPCA

  1. PCA方法假设从高维空间到低维空间的映射是线性的,但是在不少现实任务中可能需要非线性映射才能找到合适的低维空间来降维。

    非线性降维的一种常用方法是基于核技巧对线性降维方法进行核化kernelized, 如核主成分分析Kernelized PCA:KPCA ,它是对PCA的一种推广。

  2. 假定原始特征空间中的样本点 通过映射 映射到高维特征空间的坐标为 ,即 。且假

    设高维特征空间为 维的,即: 。假定要将高维特征空间中的数据投影到低维空间中,投影矩阵为 维矩阵。

    根据 PCA 推导的结果,求解方程: 。其中 维矩阵。

    于是有:

  3. 通常并不清楚 的解析表达式,因此并不会直接得到 ,所以无法直接求解方程:

    于是引入核函数:

    • 定义核矩阵 :

      则有:

    • 定义 ,则 维行向量 。定义: 维矩阵

      则有:

  4. 代入 ,有:

    • 两边同时左乘以 ,再代入 有:

    • 通常会要求核矩阵可逆,上式两边同时左乘以 ,则有:

      同样该问题也是一个特征值分解问题,取 最大的 个特征值对应的特征向量组成 即可。

  5. 对于新样本 , 其投影后第 维的坐标为:

    其中 为行向量 的第 个分量。

    可以看到:为了获取投影后的坐标, KPCA需要对所有样本求和,因此它的计算开销较大。

四、流形学习

  1. 流形学习manifold learning是一类借鉴了拓扑流形概念的降维方法。

  2. 流形是在局部和欧氏空间同胚的空间,它在局部具有欧氏空间的性质,能用欧氏距离进行距离计算。

    如果低维流形嵌入到高维空间中,则数据样本在高维空间的分布虽然看起来非常复杂,但是在局部上仍然具有欧氏空间的性质。

  3. 当维数被降低至二维或者三维时,能对数据进行可视化展示,因此流形学习也可用于可视化。

  4. 流形学习若想取得很好的效果,则必须对邻域保持样本密采样,但这恰恰是高维情形下面临的重大障碍。因此流形学习方法在实践中的降维性能往往没有预期的好。

  5. 流形学习对于噪音数据非常敏感。噪音数据可能出现在两个区域连接处:

    • 如果没有出现噪音,这两个区域是断路的。
    • 如果出现噪音,这两个区域是短路的。

4.1 多维缩放

4.1.1 多维缩放原理

  1. 多维缩放Multiple Dimensional Scaling:MDS要求原始空间中样本之间的距离在低维空间中得到保持。

  2. 假设 个样本在原始空间中的距离矩阵为 :

    其中 为样本 到样本 的距离。

    假设原始样本是在 维空间,目标是获取样本在 维空间且欧氏距离保持不变,其中满足

    假设样本集在原空间的表示为 ,样本集在降维后空间的表示为