前言
PCA是一種無(wú)參數(shù)的數(shù)據(jù)降維方法，在機(jī)器學(xué)習(xí)中很常用勤庐，這篇文章主要從三個(gè)角度來(lái)說(shuō)明PCA是怎么降維的分別是方差角度塘装，特征值和特征向量以及SVD奇異值分解锹淌。
PCA的推導(dǎo)過(guò)程
推導(dǎo)主要來(lái)源于下面網(wǎng)址的這篇文章硬耍，是通過(guò)方差和協(xié)方差矩陣來(lái)說(shuō)明：
http://blog.codinglabs.org/articles/pca-tutorial.html
PCA通過(guò)線性變換將原始數(shù)據(jù)變換為一組各維度線性無(wú)關(guān)的表示垄琐，可用于提取數(shù)據(jù)的主要特征分量，常用于高維數(shù)據(jù)的降維经柴。
在上面網(wǎng)址的文章中狸窘，從頭到尾發(fā)明了一遍PCA我覺(jué)得很有借鑒意義。我們知道PCA是一種數(shù)據(jù)降維的方法坯认，在降低維度的過(guò)程中翻擒，我們當(dāng)然想要保留更多的特征，PCA就是經(jīng)過(guò)數(shù)學(xué)推導(dǎo)牛哺，保留最多特征同時(shí)降維的方法陋气。
在推導(dǎo)之前要先知道幾個(gè)基礎(chǔ)知識(shí)：
內(nèi)積與投影
兩個(gè)維數(shù)相同的向量的內(nèi)積被定義為：
內(nèi)積的幾何意義
假設(shè)A和B是兩個(gè)n維向量，我們知道n維向量可以等價(jià)表示為n維空間中的一條從原點(diǎn)發(fā)射的有向線段引润，為了簡(jiǎn)單起見(jiàn)我們假設(shè)A和B均為二維向量巩趁，則A=(x1,y1),B=(x2,y2)。則在二維平面上A和B可以用兩條發(fā)自原點(diǎn)的有向線段表示椰拒，見(jiàn)下圖：
現(xiàn)在我們從A點(diǎn)向B所在直線引一條垂線晶渠。我們知道垂線與B的交點(diǎn)叫做A在B上的投影凰荚，再設(shè)A與B的夾角是a燃观，則投影的矢量長(zhǎng)度為|A|cos(a)，其中|A|是向量A的模便瑟，也就是A線段的標(biāo)量長(zhǎng)度缆毁。
到這里還是看不出內(nèi)積和這東西有什么關(guān)系，不過(guò)如果我們將內(nèi)積表示為另一種我們熟悉的形式：
現(xiàn)在事情似乎是有點(diǎn)眉目了：A與B的內(nèi)積等于A到B的投影長(zhǎng)度乘以B的模到涂。再進(jìn)一步脊框，如果我們假設(shè)B的模為1颁督，即讓|B|=1，那么就變成了：
也就是說(shuō)浇雹，設(shè)向量B的模為1沉御，則A與B的內(nèi)積值等于A向B所在直線投影的矢量長(zhǎng)度！這就是內(nèi)積的一種幾何解釋昭灵，也是我們得到的第一個(gè)重要結(jié)論吠裆。在后面的推導(dǎo)中，將反復(fù)使用這個(gè)結(jié)論烂完。
基
下面我們繼續(xù)在二維空間內(nèi)討論向量试疙。上文說(shuō)過(guò)，一個(gè)二維向量可以對(duì)應(yīng)二維笛卡爾直角坐標(biāo)系中從原點(diǎn)出發(fā)的一個(gè)有向線段抠蚣。例如下面這個(gè)向量：
在代數(shù)表示方面祝旷，我們經(jīng)常用線段終點(diǎn)的點(diǎn)坐標(biāo)表示向量，例如上面的向量可以表示為(3,2)嘶窄，這是我們?cè)偈煜げ贿^(guò)的向量表示怀跛。
不過(guò)我們常常忽略，只有一個(gè)(3,2)本身是不能夠精確表示一個(gè)向量的柄冲。我們仔細(xì)看一下敌完，這里的3實(shí)際表示的是向量在x軸上的投影值是3，在y軸上的投影值是2羊初。也就是說(shuō)我們其實(shí)隱式引入了一個(gè)定義：以x軸和y軸上正方向長(zhǎng)度為1的向量為標(biāo)準(zhǔn)滨溉。那么一個(gè)向量(3,2)實(shí)際是說(shuō)在x軸投影為3而y軸的投影為2。注意投影是一個(gè)矢量长赞，所以可以為負(fù)晦攒。
更正式的說(shuō)，向量(x,y)實(shí)際上表示線性組合：
不難證明所有二維向量都可以表示為這樣的線性組合得哆。此處(1,0)和(0,1)叫做二維空間中的一組基脯颜。
我們之所以默認(rèn)選擇(1,0)和(0,1)為基，當(dāng)然是比較方便贩据，因?yàn)樗鼈兎謩e是x和y軸正方向上的單位向量栋操，因此就使得二維平面上點(diǎn)坐標(biāo)和向量一一對(duì)應(yīng)，非常方便饱亮。但實(shí)際上任何兩個(gè)線性無(wú)關(guān)的二維向量都可以成為一組基矾芙，所謂線性無(wú)關(guān)在二維平面內(nèi)可以直觀認(rèn)為是兩個(gè)不在一條直線上的向量。
例如近上，(1,1)和(-1,1)也可以成為一組基剔宪。一般來(lái)說(shuō)，我們希望基的模是1，因?yàn)閺膬?nèi)積的意義可以看到葱绒，如果基的模是1感帅，那么就可以方便的用向量點(diǎn)乘基而直接獲得其在新基上的坐標(biāo)了！實(shí)際上地淀，對(duì)應(yīng)任何一個(gè)向量我們總可以找到其同方向上模為1的向量失球，只要讓兩個(gè)分量分別除以模就好了。例如帮毁，上面的基可以變?yōu)?1/√2她倘，1/√2)和(-1/√2，1/√2)
現(xiàn)在作箍，我們想獲得(3,2)在新基上的坐標(biāo)硬梁，即在兩個(gè)方向上的投影矢量值，那么根據(jù)內(nèi)積的幾何意義胞得，我們只要分別計(jì)算(3,2)和兩個(gè)基的內(nèi)積荧止，不難得到新的坐標(biāo)為(5/√2，-1/√2)阶剑。下圖給出了新的基以及(3,2)在新基上坐標(biāo)值的示意圖：
另外這里要注意的是跃巡，我們列舉的例子中基是正交的（即內(nèi)積為0，或直觀說(shuō)相互垂直）牧愁，但可以成為一組基的唯一要求就是線性無(wú)關(guān)素邪，非正交的基也是可以的。不過(guò)因?yàn)檎换休^好的性質(zhì)猪半，所以一般使用的基都是正交的兔朦。
基變換的矩陣表示
一般的，如果我們有M個(gè)N維向量磨确，想將其變換為由R個(gè)N維向量表示的新空間中沽甥，那么首先將R個(gè)基按行組成矩陣A，然后將向量按列組成矩陣B乏奥，那么兩矩陣的乘積AB就是變換結(jié)果摆舟，其中AB的第m列為A中第m列變換后的結(jié)果。（新基按行邓了，向量按列）
特別要注意的是恨诱，這里R可以小于N，而R決定了變換后數(shù)據(jù)的維數(shù)骗炉。也就是說(shuō)照宝，我們可以將一N維數(shù)據(jù)變換到更低維度的空間中去，變換后的維度取決于基的數(shù)量痕鳍。因此這種矩陣相乘的表示也可以表示降維變換硫豆。
最后龙巨，上述分析同時(shí)給矩陣相乘找到了一種物理解釋：兩個(gè)矩陣相乘的意義是將右邊矩陣中的每一列列向量變換到左邊矩陣中每一行行向量為基所表示的空間中去笼呆。更抽象的說(shuō)熊响，一個(gè)矩陣可以表示一種線性變換。很多同學(xué)在學(xué)線性代數(shù)時(shí)對(duì)矩陣相乘的方法感到奇怪诗赌，但是如果明白了矩陣相乘的物理意義汗茄，其合理性就一目了然了。
協(xié)方差矩陣與優(yōu)化目標(biāo)
我們從上面的矩陣乘法與基變換可以看出铭若，當(dāng)新基的維數(shù)小于原來(lái)的維數(shù)時(shí)可以做到數(shù)據(jù)的降維洪碳，但是究竟如何選擇新基就是我們現(xiàn)在面臨的問(wèn)題，我們想要選擇一個(gè)維數(shù)更小的新基叼屠，同時(shí)新基保留有更多的信息瞳腌。我們知道矩陣向新基投影的形式，也就是PCA是將一組N維的特征投影到K維（K<N）同時(shí)保留更多的特征镜雨。
那么怎么衡量更多的特征嫂侍，也就是投影后盡量少的重疊，投影值盡可能分散荚坞。
方差
這種投影值的分散數(shù)學(xué)上可以用方差表示挑宠。方差公式這里不表，所以PCA現(xiàn)在的問(wèn)題就變成了颓影，尋找K維的新基各淀，使得數(shù)據(jù)變換到這組基上后方差值最大。
協(xié)方差
從二維到一維的降維诡挂，只需要找到一個(gè)一維基使得方差最大碎浇，但是三維降到二維呢？我們需要找到兩個(gè)基讓這個(gè)三維數(shù)據(jù)投影到兩個(gè)基上璃俗，如果我們找方差最大的兩個(gè)基南捂，會(huì)發(fā)現(xiàn)他們完全一樣或者線性相關(guān)，這和一個(gè)基沒(méi)什么區(qū)別旧找，不能表達(dá)更多的信息溺健，所以我們需要添加限制條件，我們希望這兩個(gè)基彼此線性無(wú)關(guān)钮蛛，擴(kuò)展到K個(gè)基也是一樣鞭缭。
在數(shù)學(xué)上使用協(xié)方差表示兩個(gè)向量的相關(guān)性，在我們將均值歸一化為0后魏颓，協(xié)方差可以表示為：
=\frac{1}{m}\sum_{i=1}^{m}a_ib_i)
m為向量的元素?cái)?shù)岭辣。可以看到甸饱，在字段均值為0的情況下沦童，兩個(gè)字段的協(xié)方差簡(jiǎn)潔的表示為其內(nèi)積除以元素?cái)?shù)m仑濒。
當(dāng)協(xié)方差為0時(shí)，表示兩個(gè)字段完全獨(dú)立偷遗。為了讓協(xié)方差為0墩瞳，我們選擇第二個(gè)基時(shí)只能在與第一個(gè)基正交的方向上選擇。因此最終選擇的兩個(gè)方向一定是正交的氏豌。
至此喉酌，我們得到了降維問(wèn)題的優(yōu)化目標(biāo)：將一組N維向量降為K維（K大于0，小于N）泵喘，其目標(biāo)是選擇K個(gè)單位（模為1）正交基泪电，使得原始數(shù)據(jù)變換到這組基上后，各字段兩兩間協(xié)方差為0纪铺，而字段的方差則盡可能大（在正交的約束下相速，取最大的K個(gè)方差）。
協(xié)方差矩陣
上面我們導(dǎo)出了優(yōu)化目標(biāo)鲜锚，但是這個(gè)目標(biāo)似乎不能直接作為操作指南（或者說(shuō)算法）突诬，因?yàn)樗徽f(shuō)要什么，但根本沒(méi)有說(shuō)怎么做烹棉。所以我們要繼續(xù)在數(shù)學(xué)上研究計(jì)算方案攒霹。
我們看到，最終要達(dá)到的目的與字段內(nèi)方差及字段間協(xié)方差有密切關(guān)系浆洗。因此我們希望能將兩者統(tǒng)一表示催束，仔細(xì)觀察發(fā)現(xiàn)，兩者均可以表示為內(nèi)積的形式伏社，而內(nèi)積又與矩陣相乘密切相關(guān)抠刺。于是我們來(lái)了靈感：
假設(shè)我們只有a和b兩個(gè)特征，那么我們將它們按行組成矩陣X：
然后我們用X乘以X的轉(zhuǎn)置摘昌，并乘上系數(shù)1/m：
這個(gè)矩陣對(duì)角線上的兩個(gè)元素分別是兩個(gè)字段的方差速妖，而其它元素是a和b的協(xié)方差。兩者被統(tǒng)一到了一個(gè)矩陣的聪黎。
根據(jù)矩陣相乘的運(yùn)算法則罕容，這個(gè)結(jié)論很容易被推廣到一般情況：
設(shè)我們有m個(gè)n維數(shù)據(jù)記錄，將其按列排成n乘m的矩陣X稿饰，設(shè)C=1/mXXT锦秒，則C是一個(gè)對(duì)稱矩陣，其對(duì)角線分別個(gè)各個(gè)字段的方差喉镰，而第i行j列和j行i列元素相同旅择，表示i和j兩個(gè)字段的協(xié)方差。
協(xié)方差矩陣對(duì)角化
根據(jù)上述推導(dǎo)侣姆，我們發(fā)現(xiàn)要達(dá)到優(yōu)化目前生真，等價(jià)于將協(xié)方差矩陣對(duì)角化：即除對(duì)角線外的其它元素化為0沉噩，并且在對(duì)角線上將元素按大小從上到下排列，這樣我們就達(dá)到了優(yōu)化目的柱蟀。這樣說(shuō)可能還不是很明晰川蒙，我們進(jìn)一步看下原矩陣與基變換后矩陣協(xié)方差矩陣的關(guān)系：
設(shè)原始數(shù)據(jù)矩陣X對(duì)應(yīng)的協(xié)方差矩陣為C，而P是一組基按行組成的矩陣产弹，設(shè)Y=PX派歌，則Y為X對(duì)P做基變換后的數(shù)據(jù)弯囊。設(shè)Y的協(xié)方差矩陣為D痰哨，我們推導(dǎo)一下D與C的關(guān)系：
現(xiàn)在事情很明白了！我們要找的P不是別的匾嘱，而是能讓原始協(xié)方差矩陣對(duì)角化的P斤斧。換句話說(shuō)，優(yōu)化目標(biāo)變成了尋找一個(gè)矩陣P霎烙，滿足PCPT是一個(gè)對(duì)角矩陣撬讽，并且對(duì)角元素按從大到小依次排列，那么P的前K行就是要尋找的基悬垃，用P的前K行組成的矩陣乘以X就使得X從N維降到了K維并滿足上述優(yōu)化條件游昼。
由上文知道，協(xié)方差矩陣C是一個(gè)是對(duì)稱矩陣尝蠕，在線性代數(shù)上烘豌，實(shí)對(duì)稱矩陣有一系列非常好的性質(zhì)：
1）實(shí)對(duì)稱矩陣不同特征值對(duì)應(yīng)的特征向量必然正交。
2）設(shè)特征向量λ重?cái)?shù)為r看彼，則必然存在r個(gè)線性無(wú)關(guān)的特征向量對(duì)應(yīng)于λ廊佩，因此可以將這r個(gè)特征向量單位正交化。
由上面兩條可知靖榕，一個(gè)n行n列的實(shí)對(duì)稱矩陣一定可以找到n個(gè)單位正交特征向量标锄，設(shè)這n個(gè)特征向量為e1,e2,...,en，我們將其按列組成矩陣：
則對(duì)協(xié)方差矩陣C有如下結(jié)論：
其中Λ為對(duì)角矩陣茁计，其對(duì)角元素為各特征向量對(duì)應(yīng)的特征值（可能有重復(fù)）料皇。以上結(jié)論不再給出嚴(yán)格的數(shù)學(xué)證明，對(duì)證明感興趣的朋友可以參考線性代數(shù)書(shū)籍關(guān)于“實(shí)對(duì)稱矩陣對(duì)角化”的內(nèi)容星压。
到這里践剂，我們發(fā)現(xiàn)我們已經(jīng)找到了需要的矩陣P：
P是協(xié)方差矩陣的特征向量單位化后按行排列出的矩陣，其中每一行都是C的一個(gè)特征向量租幕。如果設(shè)P按照Λ中特征值的從大到小舷手，將特征向量從上到下排列，則用P的前K行組成的矩陣乘以原始數(shù)據(jù)矩陣X劲绪，就得到了我們需要的降維后的數(shù)據(jù)矩陣Y男窟。
至此我們完成了整個(gè)PCA的數(shù)學(xué)原理討論盆赤。
關(guān)于PCA的貢獻(xiàn)率與K的選擇
在我的文章特征值和特征向量中說(shuō)過(guò)，特征值反映了矩陣對(duì)于特征向量的拉伸程度歉眷，只有拉伸而沒(méi)有旋轉(zhuǎn)牺六，也就是在特征向量方向上的作用程度，所以在PCA中我們選取前K個(gè)特征向量組成新基進(jìn)行投影汗捡，就是因?yàn)樵卣髟谇癒個(gè)特征向量有最大的作用程度淑际，投影過(guò)后可以保留更多的信息，作用程度是用特征值表示的扇住，所以我們可以使用下面的式子表示貢獻(xiàn)率春缕，貢獻(xiàn)率是表示投影后信息的保留程度的變量，可以用下面的式子表示：
也就是特征值的總和比上前K個(gè)特征值艘蹋，一般來(lái)說(shuō)貢獻(xiàn)率要大于85%锄贼。
關(guān)于SVD
上面的推導(dǎo)中我們看到
其實(shí)就是對(duì)于D的奇異值分解。但是其實(shí)兩者還有一些區(qū)別：
1） SVD可以獲取另一個(gè)方向上的主成分女阀，而PCA只能獲得單個(gè)方向上的主成分：
LSI
隱語(yǔ)義索引（Latent semantic indexing宅荤，簡(jiǎn)稱LSI）通常建立在SVD的基礎(chǔ)上，通過(guò)低秩逼近達(dá)到降維的目的浸策。
注意到PCA也能達(dá)到降秩的目的冯键，但是PCA需要進(jìn)行零均值化，且丟失了矩陣的稀疏性庸汗。
數(shù)值穩(wěn)定性
通過(guò)SVD可以得到PCA相同的結(jié)果惫确，但是SVD通常比直接使用PCA更穩(wěn)定。因?yàn)镻CA需要計(jì)算XTX的值夫晌，對(duì)于某些矩陣雕薪，求協(xié)方差時(shí)很可能會(huì)丟失一些精度。例如Lauchli矩陣：
在Lauchli矩陣?yán)锵恚琫是很小的數(shù)所袁，e2無(wú)法用計(jì)算機(jī)精確表示，從而計(jì)算XTX會(huì)丟失e這部分信息凶掰。
PCA的步驟
1）將原始數(shù)據(jù)按列組成n行m列矩陣X
2）將X的每一行（代表一個(gè)屬性字段）進(jìn)行零均值化燥爷，即減去這一行的均值
3）求出協(xié)方差矩陣
4）求出協(xié)方差矩陣的特征值及對(duì)應(yīng)的特征向量
5）將特征向量按對(duì)應(yīng)特征值大小從上到下按行排列成矩陣礁遣，取前k行組成矩陣P
6）Y=PX即為降維到k維后的數(shù)據(jù)
至于練習(xí)
courser里吳恩達(dá)的PCA的習(xí)題就不錯(cuò)沧竟。
