機(jī)器學(xué)習(xí)基礎(chǔ)：奇異值分解（SVD）

SVD 原理

奇異值分解（Singular Value Decomposition）是線性代數(shù)中一種重要的矩陣分解，也是在機(jī)器學(xué)習(xí)領(lǐng)域廣泛應(yīng)用的算法，它不光可以用于降維算法中的特征分解，還可以用于推薦系統(tǒng)，以及自然語言處理等領(lǐng)域。

有一個??×??的實數(shù)矩陣??，我們想要把它分解成如下的形式：

其中??和??均為單位正交陣，即有和，??稱為左奇異矩陣，??稱為右奇異矩陣，Σ僅在主對角線上有值，我們稱它為奇異值，其它元素均為0。

上面矩陣的維度分別為,,。

一般地Σ有如下形式

越大意味著對應(yīng)的 的特征值 越大, 從而其主成分 (principal component) 的樣本方差越大, 我們把方差大視為提供了更多信息.

求解U, Σ, V

假設(shè)我們的矩陣A是一個m×n的矩陣，則是方陣，求其特征值及特征向量：

得到矩陣的n個特征值和對應(yīng)的n個特征向量

因 =

將特征向量張成一個的矩陣，就是SVD公式里面的矩陣,中的每個特征向量叫做的右奇異向量。

同理：，可得矩陣。

求得，然后求Σ，因Σ為奇異值矩陣，所以只需要求出每個奇異值即可。

其實特征值矩陣等于奇異值矩陣的平方，也就是說特征值和奇異值滿足如下關(guān)系：

所以不用也可以通過求出的特征值取平方根來求奇異值。

SVD算法

輸入：樣本數(shù)據(jù)
輸出：左奇異矩陣，奇異值矩陣，右奇異矩陣

1 計算特征值：特征值分解，其中為原始樣本數(shù)據(jù)

得到左奇異矩陣和奇異值矩陣

2 間接求部分右奇異矩陣：求

利用A=UΣ′V′可得

3 返回U, Σ′, V′，分別為左奇異矩陣，奇異值矩陣，右奇異矩陣。

Python 求解SVD

from?numpy?import?array
from?numpy?import?diag
from?numpy?import?zeros
from?scipy.linalg?import?svd
#?define?a?matrix
A?=?array([
?[1,2,3,4,5,6,7,8,9,10],
?[11,12,13,14,15,16,17,18,19,20],
?[21,22,23,24,25,26,27,28,29,30]])
print(A)

>>>?A
array([[?1,??2,??3,??4,??5,??6,??7,??8,??9,?10],
???????[11,?12,?13,?14,?15,?16,?17,?18,?19,?20],
???????[21,?22,?23,?24,?25,?26,?27,?28,?29,?30]])

#?Singular-value?decomposition
U,?s,?VT?=?svd(A)
#?create?m?x?n?Sigma?matrix
Sigma?=?zeros((A.shape[0],?A.shape[1]))
#?populate?Sigma?with?n?x?n?diagonal?matrix
Sigma[:A.shape[0],?:A.shape[0]]?=?diag(s)
#?select
n_elements?=?2
Sigma?=?Sigma[:,?:n_elements]
VT?=?VT[:n_elements,?:]
#?reconstruct
B?=?U.dot(Sigma.dot(VT))
print(B)

>>>?B
array([[?1.,??2.,??3.,??4.,??5.,??6.,??7.,??8.,??9.,?10.],
???????[11.,?12.,?13.,?14.,?15.,?16.,?17.,?18.,?19.,?20.],
???????[21.,?22.,?23.,?24.,?25.,?26.,?27.,?28.,?29.,?30.]])

#?transform
T?=?U.dot(Sigma)
print(T)

>>>?T
array([[-18.52157747,???6.47697214],
???????[-49.81310011,???1.91182038],
???????[-81.10462276,??-2.65333138]])

T?=?A.dot(VT.T)
print(T)

[[-18.52157747???6.47697214]
?[-49.81310011???1.91182038]
?[-81.10462276??-2.65333138]]

參考：
https://www.cnblogs.com/pinard/p/6251584.html
https://www.cnblogs.com/endlesscoding/p/10033527.html