【原】奇异值分解SVD

矩阵分解在机器学习领域有着广泛应用，是降维相关算法的基本组成部分。常见的矩阵分解方式有以下两种

1. 特征分解Eigendecomposition, 也叫作谱分解Spectral decomposition

2. 奇异值分解Singular Value decompositon

特征分解建立在特征值和特征向量的基础上，适合行列数目相等的方阵，其分解的结果如下

将一个方阵A, 拆分成3个矩阵的乘积，其中Q是矩阵A的特征向量构成的矩阵，∧是对角线为特征值的方阵，最后一个为Q的逆矩阵。下面通过numpy来验证下特征分解的过程

>>> import numpy as np
>>> A = np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]])
# 原始方阵A
>>> A
array([[1, 2, 3],
       [4, 5, 6],
       [7, 8, 9]])
>>> eigenvalues, eigenvectors = np.linalg.eig(A)
# 特征值
>>> eigenvalues
array([ 1.61168440e+01, -1.11684397e+00, -1.30367773e-15])
# 特征向量
>>> eigenvectors
array([[-0.23197069, -0.78583024, 0.40824829],
       [-0.52532209, -0.08675134, -0.81649658],
       [-0.8186735 , 0.61232756, 0.40824829]])
# 对角线为特征值的矩阵
>>> np.diag(eigenvalues)
array([[ 1.61168440e+01, 0.00000000e+00, 0.00000000e+00],
       [ 0.00000000e+00, -1.11684397e+00, 0.00000000e+00],
       [ 0.00000000e+00, 0.00000000e+00, -1.30367773e-15]])
# 特征向量矩阵的逆矩阵
>>> np.linalg.inv(eigenvectors)
array([[-0.48295226, -0.59340999, -0.70386772],
       [-0.91788599, -0.24901003, 0.41986593],
       [ 0.40824829, -0.81649658, 0.40824829]])
# 三个矩阵的乘积是原始方阵A
>>> eigenvectors.dot(np.diag(eigenvalues)).dot(np.linalg.inv(eigenvectors))
array([[1., 2., 3.],
       [4., 5., 6.],
       [7., 8., 9.]])

特征分解求解方便，但是只适用于方阵。当矩阵的行数和列数不相等时，就只能采用奇异值分解了。SVD也是同样将矩阵拆分成3个子矩阵的乘积，图示如下

对于m行n列的矩阵A, 通过SVD分解之后，拆分成了3个子矩阵，其中U矩阵为m行m列的方阵，V为n行n列的方阵，∑为只有对角线有值的矩阵，其中的值称之为奇异值。

看一个维基百科的例子，原始矩阵如下

奇异值分解的结果如下

对于矩阵U和V而言，其乘以对应的转置矩阵，都会得到一个单位矩阵，这样的矩阵称之为酉矩阵

在奇异值分解中，矩阵的奇异值是按照从大到小的顺序排列的，而且减少的特别快，经常前10%的奇异值就占据了全部奇异值99%以上的比例。基于这个性质，我们可以只提取前几个奇异值及其对应的矩阵来近似的描述原来的矩阵，图示如下

这个性质和PCA算法完美契合，所以在scikit-learn的PCA求解中，就是通过SVD分解来求取最大的K个特征。

·end·