機器學習實戰——利用 SVD 簡化資料

• 1 SVD 的介紹
• 2 Python 中的實作
• 3 參考資料

1 SVD 的介紹

假設 A 是一個 n × n n\times n n×n 的方陣，則其具有如下形式：

A ν = λ ν A\nu=\lambda\nu Aν=λν

其中 λ \lambda λ 是矩陣 A 的一個特征值， ν \nu ν 是矩陣 A 的一個 n n n 維特征向量。若把矩陣 A 的 n n n 個特征值及其對應的特征向量均求出，且按照特征值的大小由大到小排列，則其可以分解成如下形式：

A = W Σ W − 1 A=W\Sigma W^{-1} A=WΣW−1

其中 W W W 是 n n n 個機關特征向量構成的矩陣，則 W W T = I ⇒ W T = W − 1 WW^{T}=I\Rightarrow W^{T}=W^{-1} WWT=I⇒WT=W−1，是以上式可以轉換成如下形式：

A = W Σ W − 1 ⇒ A = W Σ W T A=W\Sigma W^{-1}\Rightarrow A=W\Sigma W^{T} A=WΣW−1⇒A=WΣWT

隻有當矩陣 A 是方陣時才能對其進行特征值分解。若矩陣 A 是一個 m × n m\times n m×n 的矩陣，線上性代數中可以對其進行奇異值分解（SVD），線性代數中定義 SVD 的分解形式如下：

A = U Σ V T A=U\Sigma V^{T} A=UΣVT

其中 U U U （左奇異矩陣）是一個 m × m m\times m m×m 的方陣， Σ \Sigma Σ 是一個 m × n m\times n m×n 的矩陣， V V V （右奇異矩陣）是一個 n × n n\times n n×n 的方陣，且 U U T = I UU^{T}=I UUT=I , V V T = I VV^{T}=I VVT=I 。接下來對求解 U 、 Σ 、 V U、\Sigma、V U、Σ、V 進行推導：

由于 A T A 、 A A T A^{T}A、AA^{T} ATA、AAT 分别為 n × n 、 m × m n\times n、m\times m n×n、m×m 的方陣，則根據特征值的分解原理，其可以分解成如下形式：

( A T A ) ν = λ ν (A^{T}A)\nu=\lambda\nu (ATA)ν=λν

( A A T ) μ = λ μ (AA^{T})\mu=\lambda\mu (AAT)μ=λμ

上述兩式中的特征值相同，因為 ( A B ) α = λ α ⇒ ( B A ) ( B α ) = λ ( B α ) (AB)\alpha=\lambda\alpha\Rightarrow (BA)(B\alpha)=\lambda (B\alpha) (AB)α=λα⇒(BA)(Bα)=λ(Bα) ，則 U U U 可以由特征向量 μ \mu μ 構成， V V V 可以由特征向量 ν \nu ν 構成。由于 Σ \Sigma Σ 除對角線上為奇異值外其他位置均為 0，假設其對角線上的奇異值為 σ \sigma σ，則其推導如下：

A = U Σ V T ⇒ A V = U Σ V T V ⇒ A V = U Σ ⇒ A ν = σ μ A=U\Sigma V^T\Rightarrow AV=U\Sigma V^TV\Rightarrow AV=U\Sigma \Rightarrow A\nu=\sigma\mu A=UΣVT⇒AV=UΣVTV⇒AV=UΣ⇒Aν=σμ

其實也可以通過 A T A 或 A A T A^TA 或 AA^T ATA或AAT 的特征值取平方根來求奇異值，本文以 A T A A^TA ATA 為例，其推導過程如下：

A = U Σ V T ⇒ A T = V Σ T U T ⇒ A T A = V Σ T U T U Σ V T ⇒ A T A = V ( Σ T Σ ) V T A=U\Sigma V^T\Rightarrow A^T=V\Sigma^T U^T\Rightarrow A^TA=V\Sigma^T U^TU\Sigma V^T \Rightarrow A^TA=V(\Sigma^T\Sigma)V^T A=UΣVT⇒AT=VΣTUT⇒ATA=VΣTUTUΣVT⇒ATA=V(ΣTΣ)VT

即 σ = λ \sigma =\sqrt{\lambda} σ=λ

​

奇異值矩陣中的奇異值與特征分解中的特征值類似，其對角線上的奇異值也是按照從大到小排列，且奇異值的減小特别的快。在大多數情況下，前 r r r 個奇異值（個數占比在前 10% 或者 1%）的和占全部奇異值之和的比例超過 99%，也就是說可以用前 r r r 個奇異值和對應的左右奇異向量來近似描述矩陣。即：

A m × n = U m × r Σ r × r ( V T ) r × n A_{m\times n}=U_{m\times r}\Sigma_{r\times r}(V^T)_{r\times n} Am×n​=Um×r​Σr×r​(VT)r×n​

其分解圖形如下：

通過 SVD 分解，可以對高維資料進行降維去噪，是以其在降維算法中的特征分解、推薦系統及自然語言處理等領域均有應用，是很多機器學習算法的基石。

2 Python 中的實作

# 可以調用numpy中的linalg對矩陣進行奇異值分解
import numpy as np

A = np.mat([[1,2,3],[4,5,6]])
U,sigma,VT=np.linalg.svd(A)
U
matrix([[-0.3863177 , -0.92236578],
        [-0.92236578,  0.3863177 ]])
# 隻傳回非零奇異值,在應用中需要轉化成相應次元的矩陣
sigma
array([9.508032  , 0.77286964])
VT
matrix([[-0.42866713, -0.56630692, -0.7039467 ],
        [ 0.80596391,  0.11238241, -0.58119908],
        [ 0.40824829, -0.81649658,  0.40824829]])
           

3 參考資料

推薦如下兩篇本文參考的文章：

1 https://www.cnblogs.com/pinard/p/6251584.html

2 http://coldjune.com/2018/05/31/SVD/