PCA算法推倒精要課件

1、PCA李洋 2016年4月11日主 成 分 分 析第1頁，共39頁。如何匯報(bào)假定你是一個(gè)公司的財(cái)務(wù)經(jīng)理，掌握了公司的所有數(shù)據(jù)，比如固定資產(chǎn)、流動(dòng)資金、每一筆借貸的數(shù)額和期限、各種稅費(fèi)、工資支出、原料消耗、產(chǎn)值、利潤、折舊、職工人數(shù)、職工的分工和教育程度等等。如果讓你介紹公司狀況，你能夠把這些指標(biāo)和數(shù)字都原封不動(dòng)地?cái)[出去嗎？當(dāng)然不能。你必須要把各個(gè)方面作出高度概括，用一兩個(gè)指標(biāo)簡單明了地把情況說清楚。 2022/8/19第2頁，共39頁。在許多實(shí)際問題中，多個(gè)變量之間是具有一定的相關(guān)關(guān)系的。因此，能否在各個(gè)變量之間相關(guān)關(guān)系研究的基礎(chǔ)上，用較少的新變量代替原來較多的變量，而且使這些較少的新變量盡可

2、能多地保留原來較多的變量所反映的信息？事實(shí)上，這種想法是可以實(shí)現(xiàn)的.主成分分析原理: 是把原來多個(gè)變量化為少數(shù)幾個(gè)綜合指標(biāo)的一種統(tǒng)計(jì)分析方法，從數(shù)學(xué)角度來看，這是一種降維處理技術(shù)。2022/8/19第3頁，共39頁。 PCA:Principal Component Analysis,即主成份分析 PCA是一種具有嚴(yán)格數(shù)學(xué)基礎(chǔ)并且已被廣泛采用的降維方法。下面我不會(huì)直接描述PCA，而是通過逐步分析問題，讓我們一起重新推倒PCA算法。2022/8/19第4頁，共39頁。內(nèi)積運(yùn)算將兩個(gè)向量映射為一個(gè)實(shí)數(shù)。其計(jì)算方式非常容易理解，但是其意義并不明顯。下面我們分析內(nèi)積的幾何意義。推導(dǎo)1 內(nèi)積與投影: 兩個(gè)

3、維數(shù)相同的向量的內(nèi)積被定義為2022/8/19第5頁，共39頁。 假設(shè)A和B是兩個(gè)n維向量，我們知道n維向量可以等價(jià)表示為n維空間中的一條從原點(diǎn)發(fā)射的有向線段，為了簡單起見我們假設(shè)A和B均為二維向量， ,在二維平面上A和B可以用兩條發(fā)自原點(diǎn)的有向線段表示，見下圖：2022/8/19第6頁，共39頁。現(xiàn)在我們從A點(diǎn)向B所在直線引一條垂線。我們知道垂線與B的交點(diǎn)叫做A在B上的投影，再設(shè)A與B的夾角是a，則投影的矢量長度為 其中 是向量A的模也就是A線段的標(biāo)量長度2022/8/19第7頁，共39頁。到這里還是看不出內(nèi)積和這東西有什么關(guān)系，不過如果我們將內(nèi)積表示為另一種我們熟悉的形式：A與B的內(nèi)積等于

4、A到B的投影長度乘以B的模。再進(jìn)一步，如果我們假設(shè)B的模為1，即讓那么就變成了也就是說，設(shè)向量B的模為1，則A與B的內(nèi)積值等于A向B所在直線投影的矢量長度！這就是內(nèi)積的一種幾何解釋。2022/8/19第8頁，共39頁?；?一個(gè)二維向量可以對應(yīng)二維笛卡爾直角坐標(biāo)系中從原點(diǎn)出發(fā)的一個(gè)有向線段。例如下面這個(gè)向量：上面的向量可以表示為(3,2)推導(dǎo)22022/8/19第9頁，共39頁。向量(x,y)實(shí)際上表示線性組合此處(1,0)和(0,1)叫做二維空間中的一組基要準(zhǔn)確描述向量，首先要確定一組基，然后給出在基所在的各個(gè)直線上的投影值，就可以了。我們之所以默認(rèn)選擇(1,0)和(0,1)為基，當(dāng)然是比較方

5、便，因?yàn)樗鼈兎謩e是x和y軸正方向上的單位向量。2022/8/19第10頁，共39頁。 (1,1)和(-1,1)也可以成為一組基。一般來說，我們希望基的模是1，因?yàn)閺膬?nèi)積的意義可以看到，如果基的模是1，那么就可以方便的用向量點(diǎn)乘基而直接獲得其在新基上的坐標(biāo)了！那么上面的基可以變?yōu)?和2022/8/19第11頁，共39頁。我們想獲得(3,2)在新基上的坐標(biāo)，即在兩個(gè)方向上的投影矢量值，那么根據(jù)內(nèi)積的幾何意義，我們只要分別計(jì)算(3,2)和兩個(gè)基的內(nèi)積，不難得到新的坐標(biāo)為 ，下圖給出了新的基以及(3,2)在新基上坐標(biāo)值的示意圖：2022/8/19第12頁，共39頁。推導(dǎo)3基變換的矩陣表示將(3,2)變

6、換為新基上的坐標(biāo)，就是用(3,2)與第一個(gè)基做內(nèi)積運(yùn)算，作為第一個(gè)新的坐標(biāo)分量，然后用(3,2)與第二個(gè)基做內(nèi)積運(yùn)算，作為第二個(gè)新坐標(biāo)的分量。實(shí)際上，我們可以用矩陣相乘的形式簡潔的表示這個(gè)變換：2022/8/19第13頁，共39頁。其中矩陣的兩行分別為兩個(gè)基，乘以原向量，其結(jié)果剛好為新基的坐標(biāo)?？梢陨晕⑼茝V一下，如果我們有m個(gè)二維向量，只要將二維向量按列排成一個(gè)兩行m列矩陣，然后用“基矩陣”乘以這個(gè)矩陣，就得到了所有這些向量在新基下的值。例如(1,1)，(2,2)，(3,3)，想變換到剛才那組基上，則可以這樣表示： 此時(shí)已經(jīng)達(dá)到降維的目的。2022/8/19第14頁，共39頁。協(xié)方差矩陣上面我

7、們討論了選擇不同的基可以對同樣一組數(shù)據(jù)給出不同的表示，而且如果基的數(shù)量少于向量本身的維數(shù)，則可以達(dá)到降維的效果。但是我們還沒有回答一個(gè)最最關(guān)鍵的問題：如何選擇基才是最優(yōu)的?；蛘哒f，如果我們有一組N維向量，現(xiàn)在要將其降到K維（K小于N），那么我們應(yīng)該如何選擇K個(gè)基才能最大程度保留原有的信息？推導(dǎo)42022/8/19第15頁，共39頁。為了避免過于抽象的討論，我們?nèi)砸砸粋€(gè)具體的例子展開。假設(shè)我們的數(shù)據(jù)由五條記錄組成，將它們表示成矩陣形式：其中每一列為一條數(shù)據(jù)記錄，而一行為一個(gè)字段。為了后續(xù)處理方便，我們首先將每個(gè)字段內(nèi)所有值都減去字段均值，其結(jié)果是將每個(gè)字段都變?yōu)榫禐?（這樣做的道理和好處后面會(huì)

8、看到）。2022/8/19第16頁，共39頁。第一個(gè)字段均值為2，第二個(gè)字段均值為3，所以變換后：我們可以看下五條數(shù)據(jù)在平面直角坐標(biāo)系內(nèi)的樣子：2022/8/19第17頁，共39頁。通過上一節(jié)對基變換的討論我們知道，這個(gè)問題實(shí)際上是要在二維平面中選擇一個(gè)方向，將所有數(shù)據(jù)都投影到這個(gè)方向所在直線上，用投影值表示原始記錄。這是一個(gè)實(shí)際的二維降到一維的問題。那么如何選擇這個(gè)方向（或者說基）才能盡量保留最多的原始信息呢？一種直觀的看法是：希望投影后的投影值盡可能分散。2022/8/19第18頁，共39頁。以上圖為例，可以看出如果向x軸投影，那么最左邊的兩個(gè)點(diǎn)會(huì)重疊在一起，中間的兩個(gè)點(diǎn)也會(huì)重疊在一起，于

9、是本身四個(gè)各不相同的二維點(diǎn)投影后只剩下兩個(gè)不同的值了，這是一種嚴(yán)重的信息丟失，同理，如果向y軸投影最上面的兩個(gè)點(diǎn)和分布在x軸上的兩個(gè)點(diǎn)也會(huì)重疊。所以看來x和y軸都不是最好的投影選擇。我們直觀目測，如果向通過第一象限和第三象限的斜線投影，則五個(gè)點(diǎn)在投影后還是可以區(qū)分的。2022/8/19第19頁，共39頁。推導(dǎo)5方差我們希望投影后投影值盡可能分散，而這種分散程度，可以用數(shù)學(xué)上的方差來表述。此處，一個(gè)字段的方差可以看做是每個(gè)元素與字段均值的差的平方和的均值，即：2022/8/19第20頁，共39頁。由于上面我們已經(jīng)將每個(gè)字段的均值都化為0了，因此方差可以直接用每個(gè)元素的平方和除以元素個(gè)數(shù)表示：于是

10、上面的問題被形式化表述為：尋找一個(gè)一維基，使得所有數(shù)據(jù)變換為這個(gè)基上的坐標(biāo)表示后，方差值最大。2022/8/19第21頁，共39頁。推導(dǎo)6 協(xié)方差對于上面二維降成一維的問題來說，找到那個(gè)使得方差最大的方向就可以了。不過對于更高維，還有一個(gè)問題需要解決。考慮三維降到二維問題。與之前相同，首先我們希望找到一個(gè)方向使得投影后方差最大，這樣就完成了第一個(gè)方向的選擇，繼而我們選擇第二個(gè)投影方向。2022/8/19第22頁，共39頁。如果我們還是單純只選擇方差最大的方向，很明顯，這個(gè)方向與第一個(gè)方向應(yīng)該是“幾乎重合在一起”，顯然這樣的維度是沒有用的，因此，應(yīng)該有其他約束條件。從直觀上說，讓兩個(gè)字段盡可能表

11、示更多的原始信息，我們是不希望它們之間存在（線性）相關(guān)性的，因?yàn)橄嚓P(guān)性意味著兩個(gè)字段不是完全獨(dú)立，必然存在重復(fù)表示的信息。2022/8/19第23頁，共39頁。數(shù)學(xué)上可以用兩個(gè)字段的協(xié)方差表示其相關(guān)性，由于已經(jīng)讓每個(gè)字段均值為0，則：可以看到，在字段均值為0的情況下，兩個(gè)字段的協(xié)方差簡潔的表示為其內(nèi)積除以元素?cái)?shù)m。2022/8/19第24頁，共39頁。 至此，我們得到了降維問題的優(yōu)化目標(biāo)：將一組N維向量降為K維（K大于0，小于N），其目標(biāo)是選擇K個(gè)單位（模為1）正交基，使得原始數(shù)據(jù)變換到這組基上后，各字段兩兩間協(xié)方差為0，而字段的方差則盡可能大（在正交的約束下，取最大的K個(gè)方差）。2022/8

12、/19第25頁，共39頁。推導(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：2022/8/19第26頁，共39頁。然后我們用X乘以X的轉(zhuǎn)置，并乘上系數(shù)1/m：這個(gè)矩陣對角線上的兩個(gè)元素分別是兩個(gè)字段的方差，而其它元素是a和b的協(xié)方差。兩者被統(tǒng)一到了一個(gè)矩陣。2022/8/19第27頁，共39頁。推導(dǎo)8協(xié)方差矩陣對角化設(shè)原始數(shù)據(jù)矩陣X對應(yīng)的協(xié)方差矩陣為C，而P是一組基按行組成的矩陣，設(shè)Y=PX，則Y為X對P做基變換后的數(shù)

13、據(jù)。設(shè)Y的協(xié)方差矩陣為D，我們推導(dǎo)一下D與C的關(guān)系：2022/8/19第28頁，共39頁。我們要找的P不是別的，而是能讓原始協(xié)方差矩陣對角化的P。協(xié)方差矩陣C是一個(gè)是對稱矩陣，在線性代數(shù)上，實(shí)對稱矩陣有一系列非常好的性質(zhì)：1）實(shí)對稱矩陣不同特征值對應(yīng)的特征向量必然正交。2）設(shè)特征向量 重?cái)?shù)為r，則必然存在r個(gè)線性無關(guān)的特征向量對應(yīng)于，因此可以將這r個(gè)特征向量單位正交化。2022/8/19第29頁，共39頁。由上面兩條可知，一個(gè)n行n列的實(shí)對稱矩陣一定可以找到n個(gè)單位正交特征向量，設(shè)這n個(gè)特征向量為 ,我們將其按列組成矩陣：則對協(xié)方差矩陣C有如下結(jié)論：2022/8/19第30頁，共39頁。其中

14、為對角矩陣，其對角元素為各特征向量對應(yīng)的特征值。矩陣P：2022/8/19第31頁，共39頁。PCA的算法步驟：設(shè)有m條n維數(shù)據(jù)。1）將原始數(shù)據(jù)按列組成n行m列矩陣X2）將X的每一行（代表一個(gè)屬性字段）進(jìn)行零均值化，即減去這一行的均值3）求出協(xié)方差矩陣4）求出協(xié)方差矩陣的特征值及對應(yīng)的特征向量2022/8/19第32頁，共39頁。5）將特征向量按對應(yīng)特征值大小從上到下按行排列成矩陣，取前k行組成矩陣P6） 即為降維到k維后的數(shù)據(jù)2022/8/19第33頁，共39頁。實(shí)例這里以上文提到的為例，我們用PCA方法將這組二維數(shù)據(jù)其降到一維。2022/8/19第34頁，共39頁。因?yàn)檫@個(gè)矩陣的每行已經(jīng)是零均值，這里我們直接求協(xié)方差矩陣：然后求其特征值和特征向量，具體求解方法不再