奇異值分解,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)系客服