奇異值分解，singular value decomposition（SVD）是線性代數(shù)中一種重要的矩陣分解。
記得大學(xué)時(shí)學(xué)習(xí)線性代數(shù)中的特征值和特征向量時(shí)，我就一直思考這個(gè)玩意算出來(lái)到底有啥用，難不成就是一群熱（xian）愛(ài)（de）專（dan）研（teng）的人弄出來(lái)的數(shù)學(xué)小把戲？然后隨著時(shí)間的推移，這些純理論的東西就基本忘光了。大學(xué)的知識(shí)往往都這樣的，和實(shí)際不接軌，學(xué)的時(shí)候不知道有啥用，等用的時(shí)候就忘的差不多了。
現(xiàn)在，在我學(xué)習(xí)線性代數(shù)后的第8年，我終于知道特征值這個(gè)玩意有啥用了。首先，先回憶下什么是特征值和特征向量吧。
對(duì)于一個(gè)方陣，其特征值和特征向量滿足：
Aν=λνAν=λν
求出所有的特征值和特征向量后，就得出了方陣A的特征值分解：
A=QΣQ?1A=QΣQ?1
其中 QQ 是特征向量按照與特征值的對(duì)應(yīng)順序組合而成 (ν1,ν2,..)(ν1,ν2,..) ， ΣΣ 是由特征值組成的一個(gè)對(duì)角矩陣。那么對(duì)于方陣A的特征值分解的意義又何在呢？先看下面這個(gè)例子，對(duì)于矩陣A（為了簡(jiǎn)單起見(jiàn)，設(shè)為對(duì)角矩陣）：
A=???100000100001???A=(100000100001)
其特征值為100，10和1，當(dāng)一個(gè)向量與之相乘時(shí)：
???100000100001??????xyz???=???100x10yz???(100000100001)(xyz)=(100x10yz)
這個(gè)式子有何意義呢？一個(gè)典型的場(chǎng)景是降維（Dimensionality Reduction）。如何降維呢？從上面可以看到，當(dāng)xyz發(fā)生變化時(shí)，x的變化將被擴(kuò)大100倍，y的變化被擴(kuò)大10倍，而z則不會(huì)被擴(kuò)大。那么當(dāng)計(jì)算的結(jié)果不需要十分精確時(shí)，z這個(gè)變量對(duì)于我們來(lái)說(shuō)意義是十分小的。當(dāng)處理的數(shù)據(jù)維度十分巨大的時(shí)候，計(jì)算量變得很大，這時(shí)候就可以通過(guò)降維來(lái)去除不是那么重要的維度（如本例中的z維度），這些維度對(duì)最終的計(jì)算結(jié)果的影響遠(yuǎn)遠(yuǎn)小于其它的維度。
這個(gè)讓我想起了高中物理競(jìng)賽時(shí)學(xué)的第一個(gè)知識(shí)點(diǎn)，就是估算：當(dāng)題目中給的數(shù)據(jù)條件十分的多，導(dǎo)致計(jì)算變的十分復(fù)雜時(shí)，需要選擇性的去除那些數(shù)量級(jí)較小的條件，使得計(jì)算量降低?，F(xiàn)在回想，其指導(dǎo)思想和降維是一樣的。
但是，特征值分解在現(xiàn)實(shí)生活中是行不通的（不由自主的想起了rework中話）。原因很簡(jiǎn)單，特征值分解局限于方陣，而現(xiàn)實(shí)生活中，往往都不是方陣。這時(shí)就需要奇異值分解了。
現(xiàn)實(shí)世界里，為了實(shí)現(xiàn)類似特征值分解的計(jì)算，我們使用奇異值分解。奇異值分解適用于任何矩陣，如下所示，其中A是一個(gè)m*n的矩陣：
A=Um?mΣm?nVTn?nA=Um?mΣm?nVn?nT
其中
UU 是一個(gè)m*m的正交矩陣，其向量被稱為左奇異向量
VV 也是一個(gè)n*n的正交矩陣，其向量被成為右奇異向量
ΣΣ 是一個(gè)m*n的矩陣，其對(duì)角線上的元素為奇異值，其余元素皆為0
當(dāng)選取top k個(gè)奇異值時(shí)，可以將矩陣降維成為：
Am?n≈Um?kΣk?kVTk?nAm?n≈Um?kΣk?kVk?nT
奇異值可以通過(guò)特征值來(lái)得出：
求出 ATAATA 的特征值和特征向量， (ATA)νi=λiνi(ATA)νi=λiνi
計(jì)算奇異值 σi=λi??√σi=λi
右奇異向量等于 νiνi
左奇異向量等于 1σiAνi1σiAνi
示例數(shù)據(jù)
示例程序
示例結(jié)果
主成分分析，Principal components analysis（PCA）是一種分析、簡(jiǎn)化數(shù)據(jù)集的技術(shù)。主成分分析經(jīng)常用于減少數(shù)據(jù)集的維數(shù)，同時(shí)保持?jǐn)?shù)據(jù)集中的對(duì)方差貢獻(xiàn)最大的特征。其方法主要是通過(guò)對(duì)協(xié)方差矩陣進(jìn)行特征分解，以得出數(shù)據(jù)的主成分（即特征向量）與它們的權(quán)值（即特征值）。
wiki上PCA的數(shù)學(xué)定義是：一個(gè)正交化線性變換，把數(shù)據(jù)變換到一個(gè)新的坐標(biāo)系統(tǒng)中，使得這一數(shù)據(jù)的任何投影的第一大方差在第一個(gè)坐標(biāo)（稱為第一主成分）上，第二大方差在第二個(gè)坐標(biāo)（第二主成分）上，依次類推。如下圖所示，通過(guò)變化將X-Y坐標(biāo)系映射到signal和noise上：
上圖中通過(guò)坐標(biāo)變化后，找出方差最大的方向?yàn)榈谝粋€(gè)坐標(biāo)（signal），然后在其正交的平面上找出方差最大的方向?yàn)榈诙€(gè)坐標(biāo)（noise）。這樣就可以通過(guò)選取top k個(gè)坐標(biāo)方向來(lái)達(dá)到對(duì)維度（特征）的提煉。其數(shù)學(xué)表達(dá)如下，其中A矩陣表示m行n維的數(shù)據(jù)，P表示坐標(biāo)系的變換：
Am?nPm?n=A?m?nAm?nPm?n=A~m?n
PCA將上述中的維度n進(jìn)行提煉，降維成k（k<n），數(shù)學(xué)表達(dá)如下：
Am?nPm?k=A?m?kAm?nPm?k=A~m?k
前文中提到SVD的降維公式：
Am?n≈Um?kΣk?kVTk?nAm?n≈Um?kΣk?kVk?nT
若將兩邊同時(shí)乘以 Vn?kVn?k ，則得到：
Am?nVn?k≈Um?kΣk?kVTk?nVn?kAm?nVn?k≈Um?kΣk?kVk?nTVn?k
由于 Vn?kVn?k 為正交矩陣，所以：
Am?nVn?k≈Um?kΣk?k≈A?m?kAm?nVn?k≈Um?kΣk?k≈A~m?k
就這樣通過(guò)SVD神奇的實(shí)現(xiàn)了PCA的坐標(biāo)系變換和特征的提煉。此外，SVD還可以進(jìn)行數(shù)據(jù)的壓縮，如下：
UTk?mAm?n≈UTk?mUm?kΣk?kVTk?nUk?mTAm?n≈Uk?mTUm?kΣk?kVk?nT
同樣由于 Un?kUn?k 為正交矩陣，所以：
UTk?mAm?n≈Σk?kVTk?n≈A?k?nUk?mTAm?n≈Σk?kVk?nT≈A~k?n
如此則將m行數(shù)據(jù)壓縮成k行數(shù)據(jù)，其含義就是去除那些十分相近的數(shù)據(jù)。
示例程序
示例結(jié)果
聯(lián)系客服
