特征值分解，奇异值分解和主成份分析 (EVD, SVD and PCA)

范叶亮 / 2017-12-11

分类: 机器学习 / 标签: EVD, SVD, PCA, 降维, Dimensionality Reduction / 字数: 2473

---

首先，定义 α 为列向量，则维度相同的两个向量 α,β 的内积可以表示为：

(1)α⋅β=αTβ=∑i=1nαibi

后续为了便于理解，我们以二维向量为例，则 α=(x1,y1)T,β=(x2,y2)T，在直角座标系中可以两个向量表示如下：

我们从 A 点向向量 β 的方向做一条垂线，交于点 C，则称 OC 为 OA 在 OB 方向上的投影。设向量 α 和向量 β 的夹角为 θ，则：

(2)cos⁡(θ)=α⋅β|α||β|

其中，|α|=x12+y12，则 OC 的长度为 |α|cos⁡(θ)。

在 n 维的线性空间 V 中，n 个线性无关的向量 ϵ1,ϵ2,...,ϵn 称为 V 的一组基。则对于 V 中的任一向量 α 可以由这组基线性表示出来：

(3)α=x1ϵ1+x2ϵ2+...+xnϵn

则对于向量 α=(3,2)T，可以表示为：

(4)α=2(1,0)T+3(0,1)T

其中 (1,0)T 和 (0,1)T 为二维空间中的一组基。

因此，当我们确定好一组基之后，我们仅需利用向量在基上的投影值即可表示对应的向量。一般情况下，我们会选择由坐标轴方向上的单位向量构成的基作为默认的基来表示向量，但我们仍可选择其他的基。例如，我们选择 (−12,12) 和 (12,12) 作为一组基，则向量在这组基上的坐标为 (−12,52)，示例如下：

以二维空间为例，定义一个如下矩阵

(5)A=⟮a11a12a21a22⟯

则对于二维空间中一个向量 α=(x,y)T ，通过同上述矩阵进行乘法运算，可得

(6)α′=Aα=⟮a11a12a21a22⟯⟮xy⟯=⟮x′y′⟯

(1) 通过变换将任意一个点 x 变成它关于 x 轴对称的点 x′

(7)x′=⟮100−1⟯⟮xy⟯=⟮x−y⟯

(2) 通过变换将任意一个点 x 变成它关于 y=x 对称的点 x′

(8)x′=⟮0110⟯⟮xy⟯=⟮yx⟯

(3) 变换将任意一个点 x 变成在它与原点连线上，与原点距离伸缩为 |λ| 倍的点 x′

(9)x′=⟮λ00λ⟯⟮xy⟯=⟮λxλy⟯

(4) 通过变换将任意一个点 x 绕原点旋转了角度 θ 的点 x′

(10)x′=⟮cos⁡θ−sin⁡θsin⁡θcos⁡θ⟯⟮xy⟯=⟮cos⁡θ−sin⁡θsin⁡θcos⁡θ⟯⟮rcos⁡ϕrsin⁡ϕ⟯=⟮rcos⁡(ϕ+θ)rsin⁡(ϕ+θ)⟯

(5) 变换将任意一个点 x 变成它在 x 轴上 的投影点 x′

(11)x′=⟮1000⟯⟮xy⟯=⟮x0⟯

特征值分解

设 A 是线性空间 V 上的一个线性变换，对于一个非零向量 α=(x1,x2,...,xn)T 使得

(12)Aα=λα

则 λ 称为 A 的一个特征值，α 称为 A 的一个特征向量。通过

(13)Aα=λαAα−λα=0(A−λE)α=0A−λE=0

其中 E=diag⁡(1,1,...,1) 为单位对角阵，即可求解其特征值，进而求解特征向量。若 A 是一个可逆矩阵，则上式可以改写为：

(14)A=Q∑Q−1

这样，一个方阵 A 就被一组特征值和特征向量表示了。例如，对于如下矩阵进行特征值分解

(15)A=⟮3−2−0.90−241000−10−0.5−0.50.11⟯

A <- matrix(c(3, -2, -0.9, 0,
              -2, 4, 1, 0,
              0, 0, -1, 0,
              -0.5, -0.5, 0.1, 1),
            4, 4, byrow = T)
A_eig <- eigen(A)
print(A_eig)

# eigen() decomposition
# $values
# [1]  5.561553  1.438447  1.000000 -1.000000
# 
# $vectors
#             [,1]       [,2] [,3]        [,4]
# [1,] -0.61530186  0.4176225    0  0.15282144
# [2,]  0.78806410  0.3260698    0 -0.13448286
# [3,]  0.00000000  0.0000000    0  0.97805719
# [4,] -0.01893678 -0.8480979    1 -0.04431822

则利用特征值和特征向量，可以还原原矩阵

A_re <- A_eig$vectors %*%
    diag(A_eig$values) %*%
    solve(A_eig$vectors)
print(A_re)

#      [,1] [,2] [,3] [,4]
# [1,]  3.0 -2.0 -0.9    0
# [2,] -2.0  4.0  1.0    0
# [3,]  0.0  0.0 -1.0    0
# [4,] -0.5 -0.5  0.1    1

奇异值分解

特征值分解针对的是方阵，对于一个 m∗n 的矩阵是无法进行特征值分解的，这时我们就需要使用奇异值分解来解决这个问题。对于 m∗n 的矩阵 A，可得 AAT 是一个 m∗m 的方阵，则针对 AAT，通过 (AAT)α=λα，即可求解这个方阵的特征值和特征向量。针对矩阵 A，奇异值分解是将原矩阵分解为三个部分

(16)Am∗n=Um∗r∑r∗rVr∗nT

其中 U 称之为左奇异向量，即为 AAT 单位化后的特征向量；V 称之为右奇异向量，即为 ATA 单位化后的特征向量；∑矩阵对角线上的值称之为奇异值，即为 AAT 或 ATA 特征值的平方根。

我们利用经典的 lena 图片展示一下 SVD 的作用，lena图片为一张 512∗512 像素的彩色图片

我们对原始图片进行灰度处理后，进行特征值分解，下图中从左到右，从上到下分别是原始的灰度图像，利用 20 个左奇异向量和 20 个右奇异向量重构图像，利用 50 个左奇异向量和 100 个右奇异向量重构图像，利用 200 个左奇异向量和 200 个右奇异向量重构图像。

从图中可以看出，我们仅用了 200 个左奇异向量和 200 个右奇异向量重构图像与原始灰度图像已经基本看不出任何区别。因此，我们利用 SVD 可以通过仅保留较大的奇异值实现数据的压缩。

主成份分析

主成份分析1可以通俗的理解为一种降维方法。其目标可以理解为将一个 m 维的数据转换称一个 k 维的数据，其中 k<m。对于具有 n 个样本的数据集，设 xi 表示 m 维的列向量，则

(17)Xm∗n=(x1,x2,...,xn)

对每一个维度进行零均值化，即减去这一维度的均值

(18)Xm∗n′=X−uh

其中，u 是一个 m 维的行向量，u[m]=1n∑i=1nX[m,i]；h 是一个值全为 1 的 n 维行向量。

对于两个随机变量，我们可以利用协方差简单表示这两个变量之间的相关性

(19)cov⁡(x,y)=E((x−μx)(x−μx))

对于已经零均值化后的矩阵 X′，计算得出如下矩阵

(20)C=1nX′X′T=⟮1n∑i=1nx1i21n∑i=1nx1ix2i⋯1n∑x1ixni1n∑i=1nx2ix1i1n∑i=1nx2i2⋯1n∑x2ixni⋮⋮⋮1n∑i=1nxmix1i1n∑i=1nxmix2i⋯1n∑xmi2⟯

因为矩阵 X′ 已经经过了零均值化处理，因此矩阵 C 中对角线上的元素为维度 m 的方差，其他元素则为两个维度之间的协方差。

从 PCA 的目标来看，我们则可以通过求解矩阵 C 的特征值和特征向量，将其特征值按照从大到小的顺序按行重排其对应的特征向量，则取前 k 个，则实现了数据从 m 维降至 k 维。

例如，我们将二维数据

(21)⟮1−1002−20011⟯

x <- matrix(c(-1, -1, 0, 0, 2,
              -2, 0, 0, 1, 1),
            5, 2, byrow = F)
x_pca <- prcomp(x)

print(pca)
# Standard deviations (1, .., p=2):
# [1] 1.5811388 0.7071068
# 
# Rotation (n x k) = (2 x 2):
#            PC1        PC2
# [1,] 0.7071068  0.7071068
# [2,] 0.7071068 -0.7071068

summary(pca)
# Importance of components:
#                           PC1    PC2
# Standard deviation     1.5811 0.7071
# Proportion of Variance 0.8333 0.1667
# Cumulative Proportion  0.8333 1.0000

x_ <- predict(x_pca, x)
print(x_)
#             PC1        PC2
# [1,] -2.1213203  0.7071068
# [2,] -0.7071068 -0.7071068
# [3,]  0.0000000  0.0000000
# [4,]  0.7071068 -0.7071068
# [5,]  2.1213203  0.7071068

降维的投影结果如图所示

← 墨尔本之行 (Trip to Melbourne) 马尔科夫链蒙特卡洛方法和吉布斯采样 (MCMC and Gibbs Sampling) →

---