PCA分析公式推导

吴老师的CS229课程里讲到了PCA分析,但是感觉有些地方不清晰,查阅了一些资料,自己整理了一下。

特征值分解与奇异值分解

首先我们需要了解一些特征值分解与奇异值分解的一些背景知识。

特征值分解

特征值和特征向量

矩阵 的特征值和特征向量满足关系:

我们注意到对于任何特征向量 ,和特征值 ,因此 一样是 的特征向量。因此,当我们提到与特征值 的特征向量 时,我们一般假定特征向量 是标准化的,即 。但是,我们注意到, 都是特征向量,因此我们无法保证特征向量的符号。

我们可以将上式改写为:

方阵 一定有 个特征值(可能是复数)。

特征值和特征向量有以下性质:

  • 方阵 的迹等于所有特征值之和。

证明如下:

  • 方阵 的行列式等于其所有特征值的乘积(缺证明)

  • 方阵 的秩等于其非零特征值的数目(缺证明)

  • 如果 非奇异,那么 的特征值和特征向量。

    证明,对 左右两项均左乘一个 ,得到

  • 对角矩阵 的特征值就是其对角线元素

    证明:因为, ,那么我们只需要设 为任一非零实数,而其他 ( ) 均为0,那么就满足 ,即对角线元素 的特征值。

我们可以将特征方程写为

其中 ,每一列表示一个特征向量,而 为对角矩阵,对角线为特征值,即:

证明如下:

如果 的特征向量之间线性无关,那么 可逆,因此存在下式

最后,我们的约束条件是 个 线性无关的特征向量,而不是矩阵 本身是否满秩,矩阵 无论是否满秩都有可能有 个线性无关的特征向量。

对称矩阵的特征值和特征向量

对称矩阵 的特征值和特征向量有两个重要的性质,首先,对称矩阵所有的特征值均是实数;第二,对称矩阵的特征向量彼此正交(缺证明)。因此,此时的 矩阵为正交矩阵,此时我们定义特征向量的矩阵为 ,即我们表示对称矩阵 为下式

证明: (其实就是正交矩阵的基本性质)

此时,我们可以表示二次型为

其中

因为 $y_{i}^{2} \geq 0 $, 因此,二次型的符号完全由特征值 决定。如果所有的特征值均满足 ,那么这个矩阵便是正定矩阵;如果所有的特征值 (也就是存在特征值为0),那么这个矩阵就是半正定矩阵。相似地,如果所有的特征值满足 ,此时矩阵 就是一个负定或半负定矩阵。如果矩阵 同时有正数和负数的特征值,说明 为不定矩阵

奇异值分解

下面这段话全部来自于别人的文章^3

当给定一个大小为 的矩阵 ,虽然矩阵 不一定是方阵,但大小为 却是对称矩阵,可以进行特征值分解。若 则矩阵 的奇异值分解为

满足

其中,矩阵 的大小为 ,列向量 的特征向量,也 被称为矩阵 的左奇异向量 (left singular vector) ; 矩阵 的大小为 , 列向量 的特征向量,也被称为矩阵 的右奇异向量 (right singular vector) ; 矩阵 大小为 ,矩阵 大小为 ,两个矩阵对角线上的非零元素相同 (即矩阵 和矩阵 的非零特征值相同,推导过程见下) ; 矩阵 的大小为 ,位 于对角线上的元素被称为奇异值 (singular value)。

接下来,我们来看看矩阵 与矩阵 和矩阵 的关系。令常数 是矩阵 的秩,则 ,当 时,很明显,矩阵 和矩阵 的大小不同,但矩阵 和矩阵 对 角线上的非零元素却是相同的,若将矩阵 (或矩阵 ) 对角线上的非零元素分别为 (因为 ),其中,这些特征值也都是非负的(需证明 是半正定的,见下),再令矩阵 对角线上的非零元素分别为 ,则

即非零奇异值的平方对应着矩阵 (或矩阵 ) 的非零特征值,到这里,我们就不难看出奇异值分解与对称对角化分解(特征分解)的关系了,即我们可以由对称对角化分解得到我们想要的奇异值分解。
为了便于理解,在这里,给定一个大小为 的矩阵 ,虽然这个矩阵是方阵,但 却不是对称矩阵,我们来看看它的奇异值分解是怎样的。
进行对称对角化分解,得到特征值为 ,相应地,特征向量 为 ; 由 进行对称对角化分解,得到特征值为 相应地,特征向量为 。取 ,则矩阵 的奇异值分解为

如果 是一个对称方阵,则 ,此时左奇异向量和右奇异向量构成的矩阵也是相等的,即 。更为神奇的是,对称方阵的奇异值分解与特征分解结果相同,证明见下。

证明:矩阵 和矩阵 的非零特征值相同

下面这段话来自网络^4

For any and matrices and , the nonzero eigenvalues of and are the same. Namely, if with and , then (因为 ,如果 ,则 ,与原条件相悖,因此 )and ,即 同样为 的特征值,因此 的非零特征值相同。

证明:矩阵 和矩阵 半正定

首先,证明 半正定 ,证明如下:

同理,可证 半正定。

证明:对称方阵的奇异值分解与特征分解结果相同

为对称方阵时,

假设 的一个特征值和相应的特征方程,此时存在:

因此, 的特征值和特征向量。

因此,此时, 为特征分解的特征向量矩阵,而 为特征值组成的对角矩阵。也就是说,对称方阵的奇异值分解与特征分解结果相同

PCA 预处理

在使用PCA分析前,我们需要先进行特征缩放

  1. Let .
  2. Replace each with .
  3. Let
  4. Replace each with .

前两步将均值改为 0,后两步将方差均调整为1,使得不同特征具有相同的取值范围 ( “scale”) 。如果你的特征本身就已经是范围一致,那就不用进行后两步,举个例子,假如你的输入特征是图像像素的灰度,那么你的特征取值都是 ,那么就不需要对范围做处理。

PCA 直观解释

吴老师说 PCA 分析结果可以有八九种解释的方式,但是我知道的只有两种。

第一种解释方式是找到一个超平面,使得样本点在这个超平面上尽可能分开,也就是投影点的方差尽可能大。如下图,叉形点是二维空间的样本点,我们想找到某个单位向量 ,使得数据投影到 方向的点的方差最大化。

第二种解释是我们希望所有的样本到这个超平面的距离足够近(所有样本点到超平面距离的平方和最小),对应着下图的虚线。

推导第一主成分的方向

这里就是说,如果我们就像上面图中一样,找一个单位向量 构成的一条直线方向,使得 数据投影到 方向的点的方差最大化。这里设样本数为 ,特征数为 ,我们知道给定一个单位向量 和某个点 投射到 上投影点的长度为 (内积的性质)。我们上面提到了最大化投影点的方差,因此,我们需要最大化下式^5

这里,一个隐含的性质是,投影的点的均值也为 ,证明如下:

我们发现这个解为 的协方差矩阵 主特征值(principal eigenvector) (特征值中模最大的特征值称为主特征值,相应的特征向量称为主特征向量)。

证明:我们可以通过构建拉格朗日乘子式来求解上面的问题:

因此,下式成立,即 分别为 的特征向量和特征值。

代入原式,得到我们要找的特征向量 就是主特征向量

于是,我们得到投影数据最佳的一维子空间,也就是第一主成分。

下面,我们将其一般化,推导 PCA 前 个主成分 。

PCA一般推导

推导过程主要来自于西瓜书和南瓜书[^6][^7]。

最小投影距离

假设 维数据 都已经进行了中心化,即 。经过投影变换后得到的新坐标系为 , 其中 是标准正交基向量 ( 维向量),即

如果我们将数据从 维降到 维,即丟弃新坐标系中的部分坐标,则新的坐标系为 。样本点 维坐标系中的投影为: . 其中, 在低维坐标系里第 维的坐标。

如果我们用 来恢复原始数据 , 则得到的恢复数据 , 其中, 为标准正交基组成的 矩阵

带入上式,易知, 。并且存在, ,证明如下:

现在我们考虑整个样本集,我们莃望所有的样本到这个超平面的距离足够近,即最小化下式:

将这个式子进行整理,可以得到:

注意到 是数据集的协方差矩阵(从协方差矩阵准取定义看,这个公式少了 ,但是对我们这里推导无影响,下同),可以写成设计矩阵的格式(行是样本,列是特征,因此 是一个 的矩阵)。而 是一个常量。

最小化上式等价于:

构建拉格朗日函数如下^8 ,这里拉格朗日乘子矩阵 的矩阵,与约束条件维度相同

若此时仅考虑约束 ,即只考虑 的对角线元素的约束,此时拉格朗日乘子矩阵 对角矩阵,令新的拉格朗日乘子矩阵为 , 此时的拉格朗日函数为

对拉格朗日函数关于 求导可得

由矩阵微分公式 可得

可得

展开可得

显然, 此式为矩阵特征值和特征向量的定义式, 其中 分别表示矩阵 的特征值和单位特征向量。由于以上是仅考虑约束 所求得的结果, 而 还需满足约束 。观察 的定义可知, 是一个实对称矩阵, 实对称矩阵的不同特征值所对应的特征向量之间相互正交, 同一 特征值的不同特征向量可以通过施密特正交化使其变得正交, 所以通过上式求得的 可以同时满足约束 。根据拉格朗日乘子法的原理可知, 此时求得的结果仅是最优解的必要条件, 而且 个相互正交的单位特征向量, 所以还需要从这 个特征向量里找出 个能使得目标函数 达到最优值的特征向量作为最优解。将 代人目标函数可得^9

显然, 此时只需要令 分别为矩阵 的前 个最大的特征值和单位特征向量就能使得目标函数达到最优值。

最大投影方差

我们知道样本点在超平面上的投影为 ,首先我们证明投影点的均值同样为

因此,投影点的协方差矩阵为:

投影点的方差为其协方差矩阵的迹,即为

于是,此时我们的优化目标为

这和上面的最小投影距离的优化目标一致。

选择合适的

当你对协方差矩阵 进行奇异值分解或特征值分解后,你可以得到总共 个特征值。这时你可以指定一个阈值 , 这个阈值 之间,表示保留的方差比例,一般惯例可选 0.90,0.95 和 0.99。假如我们的 个特征值为 ,则n’可以通过下式得到:

吴老师提到过这个公式,很多人的博客也提到了这个公式,但是没有告诉你这个公式怎么来的。这个公式在我看来没有这么一目了然,应该给证明过程的。

我思考了半天,才弄懂原理。这个公式蕴含的一个前提是,协方差矩阵所有特征值之和等于样本点的方差。

因此,当你需要计算方差比例的时候,总方差可以通过对所有特征值求和得到,也可以通过对协方差矩阵对角线所有元素求和得到。

疑问

  1. 为什么对称矩阵就一定可以进行特征值分解(存在 个线性无关的特征向量),并且其特征向量是一个正交矩阵?

    我现在知道这个性质来自于谱定理(Spectral theorem),吴老师说这可能是线性代数中最重要的一个定理,以后有机会再看吧。

  2. 为什么用 来恢复原始数据 的公式为

    这种转换其实就是基变换,基变换的内容可以看我的博客矩阵乘法的内涵和本质 的标准基为 个特征向量 也是 的一组基(为方便称呼,我下面称呼其为”新基“),从”新基“转换到标准基的转移矩阵就是 ,因此如果我们已知某个样本点在”新基“中的坐标为 ,其中我们只用前 维的信息,等同于我们设 维以后的维度的坐标均为 0,因此存在

  3. 不是很清楚拉格朗日函数的矩阵形式

    其实压根就没有什么所谓的矩阵形式的拉格朗日函数,我们采用矩阵的目标是为了方便书写和运算,比如一个线性方程组你直接写出多个等式,你也可以用矩阵表达为 ,二者的内容是一致的。

    这里第一次构建拉格朗日乘子式,限制条件是 ,如果我们把它写成多个等式的形式,其实就是 个等式的约束条件,即可以将 写为下面这种形式:

    此时构建的拉格朗日乘子式即为下式,后面的一项就是 个等式的约束条件,只是表示为迹的形式。

    但是我认为,这里其实没有 个等式的约束条件,因为 是一个对称矩阵,实际上只有 个等式约束条件(上三角的元素数目),因此这里应该要需要限制 为一个 对称矩阵,从而将约束条件数目降为

    第二次构建拉格朗日函数时,我们只考虑 的对角线元素的约束,此时只有 个约束条件,我们将 改为一个对角矩阵

[^6]: 《机器学习》- 周志华
[^7]: https://www.cnblogs.com/pinard/p/6239403.html

  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • Copyrights © 2019-2022 Vincere Zhou
  • 访问人数: | 浏览次数:

请我喝杯茶吧~

支付宝
微信