二、主成分分析 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 降维对于类别的区分效果要好的多。

   

2.5 PCA 与 SVD

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

   为酉矩阵的充要条件是： 。

2. 奇异值分解：设 为 阶矩阵，且 ，则存在 阶酉矩阵 和 阶酉矩阵 ，使得：

   

   其中

   

   称作矩阵 的奇异值。

3. 根据酉矩阵的性质， ，则有：

   

   则有 ， 其中 是个 阶对角矩阵：

   

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

   

   • 根据 ，则有： 。

   • 根据 是个对角矩阵的性质，有： ，则有： 。

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

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