PCA算法推倒資料

PCA

2016年4月11日主成分分析如何匯報(bào)假定你是一個(gè)公司的財(cái)務(wù)經(jīng)理，掌握了公司的所有數(shù)據(jù)，比如固定資產(chǎn)、流動(dòng)資金、每一筆借貸的數(shù)額和期限、各種稅費(fèi)、工資支出、原料消耗、產(chǎn)值、利潤(rùn)、折舊、職工人數(shù)、職工的分工和教育程度等等。如果讓你介紹公司狀況，你能夠把這些指標(biāo)和數(shù)字都原封不動(dòng)地?cái)[出去嗎？當(dāng)然不能。你必須要把各個(gè)方面作出高度概括，用一兩個(gè)指標(biāo)簡(jiǎn)單明了地把情況說(shuō)清楚。2024/4/12在許多實(shí)際問(wèn)題中，多個(gè)變量之間是具有一定的相關(guān)關(guān)系的。因此，能否在各個(gè)變量之間相關(guān)關(guān)系研究的基礎(chǔ)上，用較少的新變量代替原來(lái)較多的變量，而且使這些較少的新變量盡可能多地保留原來(lái)較多的變量所反映的信息？事實(shí)上，這種想法是可以實(shí)現(xiàn)的.主成分分析原理:是把原來(lái)多個(gè)變量化為少數(shù)幾個(gè)綜合指標(biāo)的一種統(tǒng)計(jì)分析方法，從數(shù)學(xué)角度來(lái)看，這是一種降維處理技術(shù)。2024/4/12

PCA:PrincipalComponentAnalysis,即主成份分析PCA是一種具有嚴(yán)格數(shù)學(xué)基礎(chǔ)并且已被廣泛采用的降維方法。下面我不會(huì)直接描述PCA，而是通過(guò)逐步分析問(wèn)題，讓我們一起重新推倒PCA算法。2024/4/12內(nèi)積運(yùn)算將兩個(gè)向量映射為一個(gè)實(shí)數(shù)。其計(jì)算方式非常容易理解，但是其意義并不明顯。下面我們分析內(nèi)積的幾何意義。推導(dǎo)>>1

內(nèi)積與投影:兩個(gè)維數(shù)相同的向量的內(nèi)積被定義為2024/4/12

假設(shè)A和B是兩個(gè)n維向量，我們知道n維向量可以等價(jià)表示為n維空間中的一條從原點(diǎn)發(fā)射的有向線段，為了簡(jiǎn)單起見我們假設(shè)A和B均為二維向量，

,在二維平面上A和B可以用兩條發(fā)自原點(diǎn)的有向線段表示，見下圖：2024/4/12現(xiàn)在我們從A點(diǎn)向B所在直線引一條垂線。我們知道垂線與B的交點(diǎn)叫做A在B上的投影，再設(shè)A與B的夾角是a，則投影的矢量長(zhǎng)度為其中

是向量A的模也就是A線段的標(biāo)量長(zhǎng)度2024/4/12到這里還是看不出內(nèi)積和這東西有什么關(guān)系，不過(guò)如果我們將內(nèi)積表示為另一種我們熟悉的形式：A與B的內(nèi)積等于A到B的投影長(zhǎng)度乘以B的模。再進(jìn)一步，如果我們假設(shè)B的模為1，即讓那么就變成了也就是說(shuō)，設(shè)向量B的模為1，則A與B的內(nèi)積值等于A向B所在直線投影的矢量長(zhǎng)度！這就是內(nèi)積的一種幾何解釋。2024/4/12

基:一個(gè)二維向量可以對(duì)應(yīng)二維笛卡爾直角坐標(biāo)系中從原點(diǎn)出發(fā)的一個(gè)有向線段。例如下面這個(gè)向量：上面的向量可以表示為(3,2)推導(dǎo)>>22024/4/12向量(x,y)實(shí)際上表示線性組合此處(1,0)和(0,1)叫做二維空間中的一組基要準(zhǔn)確描述向量，首先要確定一組基，然后給出在基所在的各個(gè)直線上的投影值，就可以了。我們之所以默認(rèn)選擇(1,0)和(0,1)為基，當(dāng)然是比較方便，因?yàn)樗鼈兎謩e是x和y軸正方向上的單位向量。2024/4/12(1,1)和(-1,1)也可以成為一組基。一般來(lái)說(shuō)，我們希望基的模是1，因?yàn)閺膬?nèi)積的意義可以看到，如果基的模是1，那么就可以方便的用向量點(diǎn)乘基而直接獲得其在新基上的坐標(biāo)了！那么上面的基可以變?yōu)楹?024/4/12我們想獲得(3,2)在新基上的坐標(biāo)，即在兩個(gè)方向上的投影矢量值，那么根據(jù)內(nèi)積的幾何意義，我們只要分別計(jì)算(3,2)和兩個(gè)基的內(nèi)積，不難得到新的坐標(biāo)為，下圖給出了新的基以及(3,2)在新基上坐標(biāo)值的示意圖：2024/4/12推導(dǎo)>>3基變換的矩陣表示將(3,2)變換為新基上的坐標(biāo)，就是用(3,2)與第一個(gè)基做內(nèi)積運(yùn)算，作為第一個(gè)新的坐標(biāo)分量，然后用(3,2)與第二個(gè)基做內(nèi)積運(yùn)算，作為第二個(gè)新坐標(biāo)的分量。實(shí)際上，我們可以用矩陣相乘的形式簡(jiǎn)潔的表示這個(gè)變換：2024/4/12其中矩陣的兩行分別為兩個(gè)基，乘以原向量，其結(jié)果剛好為新基的坐標(biāo)。可以稍微推廣一下，如果我們有m個(gè)二維向量，只要將二維向量按列排成一個(gè)兩行m列矩陣，然后用“基矩陣”乘以這個(gè)矩陣，就得到了所有這些向量在新基下的值。例如(1,1)，(2,2)，(3,3)，想變換到剛才那組基上，則可以這樣表示：此時(shí)已經(jīng)達(dá)到降維的目的。2024/4/12

協(xié)方差矩陣上面我們討論了選擇不同的基可以對(duì)同樣一組數(shù)據(jù)給出不同的表示，而且如果基的數(shù)量少于向量本身的維數(shù)，則可以達(dá)到降維的效果。但是我們還沒有回答一個(gè)最最關(guān)鍵的問(wèn)題：如何選擇基才是最優(yōu)的?；蛘哒f(shuō)，如果我們有一組N維向量，現(xiàn)在要將其降到K維（K小于N），那么我們應(yīng)該如何選擇K個(gè)基才能最大程度保留原有的信息？推導(dǎo)>>42024/4/12為了避免過(guò)于抽象的討論，我們?nèi)砸砸粋€(gè)具體的例子展開。假設(shè)我們的數(shù)據(jù)由五條記錄組成，將它們表示成矩陣形式：其中每一列為一條數(shù)據(jù)記錄，而一行為一個(gè)字段。為了后續(xù)處理方便，我們首先將每個(gè)字段內(nèi)所有值都減去字段均值，其結(jié)果是將每個(gè)字段都變?yōu)榫禐?（這樣做的道理和好處后面會(huì)看到）。2024/4/12第一個(gè)字段均值為2，第二個(gè)字段均值為3，所以變換后：我們可以看下五條數(shù)據(jù)在平面直角坐標(biāo)系內(nèi)的樣子：2024/4/12通過(guò)上一節(jié)對(duì)基變換的討論我們知道，這個(gè)問(wèn)題實(shí)際上是要在二維平面中選擇一個(gè)方向，將所有數(shù)據(jù)都投影到這個(gè)方向所在直線上，用投影值表示原始記錄。這是一個(gè)實(shí)際的二維降到一維的問(wèn)題。那么如何選擇這個(gè)方向（或者說(shuō)基）才能盡量保留最多的原始信息呢？一種直觀的看法是：希望投影后的投影值盡可能分散。2024/4/12以上圖為例，可以看出如果向x軸投影，那么最左邊的兩個(gè)點(diǎn)會(huì)重疊在一起，中間的兩個(gè)點(diǎn)也會(huì)重疊在一起，于是本身四個(gè)各不相同的二維點(diǎn)投影后只剩下兩個(gè)不同的值了，這是一種嚴(yán)重的信息丟失，同理，如果向y軸投影最上面的兩個(gè)點(diǎn)和分布在x軸上的兩個(gè)點(diǎn)也會(huì)重疊。所以看來(lái)x和y軸都不是最好的投影選擇。我們直觀目測(cè)，如果向通過(guò)第一象限和第三象限的斜線投影，則五個(gè)點(diǎn)在投影后還是可以區(qū)分的。2024/4/12推導(dǎo)>>5方差我們希望投影后投影值盡可能分散，而這種分散程度，可以用數(shù)學(xué)上的方差來(lái)表述。此處，一個(gè)字段的方差可以看做是每個(gè)元素與字段均值的差的平方和的均值，即：2024/4/12由于上面我們已經(jīng)將每個(gè)字段的均值都化為0了，因此方差可以直接用每個(gè)元素的平方和除以元素個(gè)數(shù)表示：于是上面的問(wèn)題被形式化表述為：尋找一個(gè)一維基，使得所有數(shù)據(jù)變換為這個(gè)基上的坐標(biāo)表示后，方差值最大。2024/4/12推導(dǎo)>>6

協(xié)方差對(duì)于上面二維降成一維的問(wèn)題來(lái)說(shuō)，找到那個(gè)使得方差最大的方向就可以了。不過(guò)對(duì)于更高維，還有一個(gè)問(wèn)題需要解決?？紤]三維降到二維問(wèn)題。與之前相同，首先我們希望找到一個(gè)方向使得投影后方差最大，這樣就完成了第一個(gè)方向的選擇，繼而我們選擇第二個(gè)投影方向。2024/4/12如果我們還是單純只選擇方差最大的方向，很明顯，這個(gè)方向與第一個(gè)方向應(yīng)該是“幾乎重合在一起”，顯然這樣的維度是沒有用的，因此，應(yīng)該有其他約束條件。從直觀上說(shuō)，讓兩個(gè)字段盡可能表示更多的原始信息，我們是不希望它們之間存在（線性）相關(guān)性的，因?yàn)橄嚓P(guān)性意味著兩個(gè)字段不是完全獨(dú)立，必然存在重復(fù)表示的信息。2024/4/12數(shù)學(xué)上可以用兩個(gè)字段的協(xié)方差表示其相關(guān)性，由于已經(jīng)讓每個(gè)字段均值為0，則：可以看到，在字段均值為0的情況下，兩個(gè)字段的協(xié)方差簡(jiǎn)潔的表示為其內(nèi)積除以元素?cái)?shù)m。2024/4/12

至此，我們得到了降維問(wèn)題的優(yōu)化目標(biāo)：將一組N維向量降為K維（K大于0，小于N），其目標(biāo)是選擇K個(gè)單位（模為1）正交基，使得原始數(shù)據(jù)變換到這組基上后，各字段兩兩間協(xié)方差為0，而字段的方差則盡可能大（在正交的約束下，取最大的K個(gè)方差）。2024/4/12推導(dǎo)>>7協(xié)方差矩陣最終要達(dá)到的目的與字段內(nèi)方差及字段間協(xié)方差有密切關(guān)系。因此我們希望能將兩者統(tǒng)一表示，仔細(xì)觀察發(fā)現(xiàn)，兩者均可以表示為內(nèi)積的形式，而內(nèi)積又與矩陣相乘密切相關(guān)。假設(shè)我們只有a和b兩個(gè)字段，那么我們將它們按行組成矩陣X：2024/4/12然后我們用X乘以X的轉(zhuǎn)置，并乘上系數(shù)1/m：這個(gè)矩陣對(duì)角線上的兩個(gè)元素分別是兩個(gè)字段的方差，而其它元素是a和b的協(xié)方差。兩者被統(tǒng)一到了一個(gè)矩陣。2024/4/12推導(dǎo)>>8協(xié)方差矩陣對(duì)角化設(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)系：2024/4/12我們要找的P不是別的，而是能讓原始協(xié)方差矩陣對(duì)角化的P。協(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è)特征向量單位正交化。2024/4/12由上面兩條可知，一個(gè)n行n列的實(shí)對(duì)稱矩陣一定可以找到n個(gè)單位正交特征向量，設(shè)這n個(gè)特征向量為,我們將其按列組成矩陣：則對(duì)協(xié)方差矩陣C有如下結(jié)論：2024/4/12其中為對(duì)角矩陣，其對(duì)角元素為各特征向量對(duì)應(yīng)的特征值。矩陣P：2024/4/12PCA的算法步驟：設(shè)有m條n維數(shù)據(jù)。1）將原始數(shù)據(jù)按列組成n行m列矩陣X2）將X的每一行（代表一個(gè)屬性字段）進(jìn)行零均值化，即減去這一行的均值3）求出協(xié)方差矩陣4）求出協(xié)方差矩陣的特征值及對(duì)應(yīng)的特征向量2024/4/125）將特征向量按對(duì)應(yīng)特征值大小從上到下按行排列成矩陣，取前k行組成矩陣P6）即為降維到k維后的數(shù)據(jù)2024/4/12實(shí)例這里以上文提到的為例，我們用PCA方法將這組二維數(shù)據(jù)其降到一維。2024/4/12因?yàn)檫@個(gè)矩陣的每行已經(jīng)是零均值，這里我們直接求協(xié)方差矩陣：