PCA的工作機制 數(shù)據(jù)的向量表示及降維問題 一般情況下，在數(shù)據(jù)挖掘和機器學(xué)習(xí)中，數(shù)據(jù)被表示為向量。例如某個淘寶店2012年的全年流量以及交易情況可以看成一組記錄的集合，其中每一天的數(shù)據(jù)是一條記錄，格式如下：
數(shù)據(jù)挖掘關(guān)心的大多是度量值，因此我們忽略掉日期這個字段后，我們得到一組數(shù)據(jù)，每條記錄可以表示成一個5維列向量，其中一條看起來大約的樣子： 我們當然可以對這一組五維向量進行分析和挖掘，但是大部分機器學(xué)習(xí)算法的復(fù)雜度和數(shù)據(jù)的維數(shù)有著密切關(guān)系，甚至與維數(shù)呈指數(shù)級關(guān)聯(lián)，當然五維還好，但是實際機器學(xué)習(xí)中處理成千上萬維的情況并不罕見，考慮到機器學(xué)習(xí)資源消耗的問題，必須對數(shù)據(jù)進行降維。 降維當然意味著信息丟失，但是鑒于數(shù)據(jù)本身常常存在相關(guān)性，我們可以想辦法把信息損失降到最低。 舉個例子，某學(xué)籍數(shù)據(jù)有兩列M和F，其中M列，學(xué)生為男性，取值為1，學(xué)生為女性取值為0，F(xiàn)列，學(xué)生為女性，取值為1，學(xué)生為男性，取值為0。這樣對任何一條記錄來說，只要M為1，F(xiàn)必為0，反之M為0，F(xiàn)必為1。在這種情況下，我們將M或F去掉，實際上沒有任何信息損失，因為只要保留一列，就能完全還原另一列。 當然這種極端的情況是不存在的，但是類似的情況還是很常見的，例如上面的淘寶店的數(shù)據(jù)，“瀏覽量”和“訪客數(shù)”往往具有較強的相關(guān)關(guān)系，而“下單數(shù)”和“成交數(shù)”也存在較強的相關(guān)關(guān)系，這時，如果刪除瀏覽量或者下單數(shù)其中的某一個指標，我們應(yīng)該并不會丟失太多的信息。因此可以刪除一個，以降低機器學(xué)習(xí)算法的復(fù)雜度。 上面給出的是降維的樸素思想描述，可以直接理解降維的動機和可行性，但是并不具有實際操作意義。例如，我們到底刪除了那一列的損失的信息更少一點呢？亦或是根本不是刪除幾列而是通過某些變換將原始數(shù)據(jù)變?yōu)楦俚牧械菗p失的信息更少？到底如何度量丟失的信息多少呢？如何根據(jù)原始數(shù)據(jù)決定具體的降維操作步驟呢？ 要回答上面的問題，就要對降維問題進行數(shù)學(xué)化和形式化的討論。而PCA是一種具有嚴格數(shù)學(xué)證明并且已經(jīng)被廣泛采用的降維方法。下面我一起從新“發(fā)明”一遍PCA。 向量的表示及基變換 下面有必要研究一下向量的數(shù)學(xué)性質(zhì)，這些性質(zhì)是后續(xù)導(dǎo)出PCA的基礎(chǔ) 內(nèi)積與投影 下面看一下，高中就學(xué)過的向量運算：內(nèi)積。兩個維數(shù)相同的向量的內(nèi)積被定義為： 內(nèi)積運算將兩個向量映射為一個實數(shù)。其計算方式非常容易理解，但是其意義并不明顯。下面我們分析內(nèi)積的幾何意義。假設(shè)A和B是兩個n維向量，我們知道n維向量可以等價表示為n維空間中一條從原點發(fā)射的有向線段，為了簡單起見，先假設(shè)A和B均為二維向量，用下面圖中的有向線段表示，見下圖： A和B的內(nèi)積就是A在B上的投影長度乘以B的模。再進一步，如果我們假設(shè)B的模為1，則A與B的內(nèi)積就是A向B所在直線投影的矢量長度！這就是內(nèi)積的一個幾何解釋。 基 一個二維向量可以對應(yīng)二維笛卡爾直角坐標系中從原點出發(fā)的一條有向線段。例如： 上面的向量可以用（3，2）表示，但是一個（3，2）本身是不能明確表示一個向量的。準確的表達是：假如以x軸和y軸上正方向長度為1的向量為標準，那么（3，2）實際上是說在x上投影為3，在y上投影為2，這里（1，0）和（0，1）叫做二維空間中的一組基。 所以要準確的描述向量，要先確定一組基，然后給出向量在各個基上的投影值，就可以了。 實際上，任何兩個不共線的向量，都可以成為一組基。但是一般我們希望基的模為1，因為如果是1，就像上文所說的一樣，根據(jù)點乘的幾何意義，可以方便的用“向量”點乘“新基”來獲取在新基下的坐標了。 現(xiàn)在想要獲?。?，2）在藍色基下的坐標，分別計算（3，2）和兩個基的內(nèi)積，就得到了新坐標： 基變換的矩陣表示 以上列舉的例子用矩陣相乘的形式簡潔的表示： 稍稍推廣一下，如果我們有m個二維向量，只要將二維向量按列拍成利益兩行m列矩陣，然后用“基矩陣”乘以這個矩陣，就可以得到這些向量在新基下的值。例如： 于是一組向量的基變換被干凈的表示為矩陣的相乘。 以上是3個二維向量的情況，下面演繹到一般的情況： 如果我們有M個N維向量，想將其變換為由R個N維向量表示的新空間中，那么首先將R個基按行組成矩陣A，然后將向量按列組成矩陣B，其中AB的第m列為A中第m列變換后的結(jié)果。 兩個矩陣相乘的意義在于將右邊矩陣中的每一列變換到左邊矩陣的每一行行向量為基表示的新空間中。更抽象的說，一個矩陣可以表示一種線性變換。 ##協(xié)方差矩陣及優(yōu)化目標 上面討論了不同的基可以對同一數(shù)據(jù)給出不同的表示，而且如果基的數(shù)量本身小于向量本身的維數(shù)，則可以達到降維的效果。但是如何選擇基才是最優(yōu)的呢？或者說，如果有一組N維向量，現(xiàn)在要想將其降到K維，那么我們應(yīng)該如何選擇K個基才能最大程度的保留原來的信息呢？ 現(xiàn)在先用一種非形式化的語言來描述。假設(shè)現(xiàn)在有5條記錄，將他們表示成矩陣： 其中每一列為一條數(shù)據(jù)記錄，而一行為一個字段。為了后續(xù)處理方便，首先將每個字段所有值減去均值，這樣每個字段都變成均值為0：
可以看到五條數(shù)據(jù)在坐標系中的樣子：
現(xiàn)在問題上來了：如果我們必須用一維來表示這些數(shù)據(jù)，又希望盡量保留原始信息，要如何選擇呢？ 這個問題實際上是要在二維平面上選擇一個方向，將所有的數(shù)據(jù)都投影到這個方向所在的直線上，用投影值表示原始數(shù)據(jù)。這是一個二維降到一維的問題。 那么應(yīng)該如何選擇呢？一種直觀的理解是：希望投影后投影值盡可能的分散。也就是變換后，仍然可以很好的區(qū)分。 下面用數(shù)學(xué)的語言描述： 方差 上文說到，我們希望投影后，投影值盡可能的分散，而這種分散程度，可以用數(shù)學(xué)上的方差來表達。一個字段的方差可以看做每個元素與字段均值差的平方和的均值，即：
上面已經(jīng)將每個字段的均值都化為零了，因此方差可以直接用每個元素的平方和除以元素個數(shù)表示：
于是上面的問題被形式化的表述為：尋找一個一維基，使得所有數(shù)據(jù)變換為這個基上的坐標后，方差值最大。 協(xié)方差 對于上面二維降為一維的問題來說，找到那個使得方差最大的方向就可以了。不過對于更高維，還有一個問題需要解決。考慮三維降到二維的問題，與之前相同，首先我們需要找到一個方向使得投影后方差最大，這樣就完成了第一個方向的選擇，繼而我們選擇第二個投影方向。 如果還是單純的選擇方差最大的方向，顯然，這個方向與第一個方向應(yīng)該是幾乎重合在一起，顯然這樣的維度是沒有用的，因此，應(yīng)該有其他約束。從直觀上說，讓兩個字段盡可能的表示更多原始信息，我們不希望它們之間存在（線性）相關(guān)性的，因此相關(guān)性意味著兩個字段不是完全獨立，必然存在重復(fù)表示的信息。 數(shù)學(xué)上可以用兩個字段的協(xié)方差表示其相關(guān)性，由于已經(jīng)讓每個字段的均值為0，則：
可以看到，在字段均值為0的情況下，兩個字段的協(xié)方差簡潔的表示為其內(nèi)積除以元素數(shù)m。 當協(xié)方差為0時，表示兩個字段完全獨立。為了讓協(xié)方差為0，我們選擇第二個基時只能在與第一個基正交的方向上選擇。因此最終選擇的兩個方向一定是正交的 因此我們得到了降維問題的優(yōu)化目標：將一組N維向量降為K維（K大于0，小于N），其目標是選擇K個單位正交基，使得原始數(shù)據(jù)變換到這組基上后，各字段兩兩之間的協(xié)方差為0（約束），而字段內(nèi)的方差盡可能大（在正交的約束下，取最大的K個方差）。 協(xié)方差矩陣 最終要達到的目的與字段內(nèi)方差以及字段之間的協(xié)方差有密切的關(guān)系。因此我們希望兩者統(tǒng)一表示，仔細觀察就會發(fā)現(xiàn)，兩者均可以表示為內(nèi)積的形式，而內(nèi)積又與矩陣相乘密切相關(guān)，于是我們涼了靈感： 假設(shè)我們只有A和B兩個字段，我們按行組成矩陣X：
然后我們用X乘以X的轉(zhuǎn)置，并乘上系數(shù)1/m：
奇跡出現(xiàn)了！這個矩陣對角線上的兩個元素分別是兩個字段的方差，而其他元素是a與b的協(xié)方差。兩者被統(tǒng)一到了一個矩陣的。 根據(jù)矩陣運算的法則，這個結(jié)論很容易被推廣到一般的情況： 假設(shè)我們有m個n維數(shù)據(jù)記錄，將其按列排成n乘m的矩陣X，設(shè)
則C是一個對稱矩陣，其對角線分別是各個字段的方差，而第j行j列和j行i列的元素相同，表示i和j兩個字段的協(xié)方差。 協(xié)方差矩陣的對角化 根據(jù)上訴推導(dǎo)，我們發(fā)現(xiàn)達到優(yōu)化目標（就是字段之間的協(xié)方差最小，字段內(nèi)方差最大）等價于將協(xié)方差矩陣對角化，對角線上元素從大到小排列：即除對角線外的其它元素化為0，并且在對角線上將元素按大小從上到下排列，這樣我們就達到了目的。 上面的這句話，換一種說法：設(shè)原始數(shù)據(jù)矩陣X對應(yīng)的協(xié)方差矩陣為C，而P是一組基按行組成的矩陣，設(shè)Y=PX，則Y為X對P做基變換后的數(shù)據(jù)。設(shè)Y的協(xié)方差矩陣為D，我們推導(dǎo)一下D與C的關(guān)系：
現(xiàn)在事情很明白了！優(yōu)化目標變成了：尋找一個矩陣P，滿足 至此，我們離“發(fā)明”PCA還有僅一步之遙！ 現(xiàn)在所有焦點都聚焦在了協(xié)方差矩陣對角化問題上，有時，我們真應(yīng)該感謝數(shù)學(xué)家的先行，因為矩陣對角化在線性代數(shù)領(lǐng)域已經(jīng)屬于被玩爛了的東西，所以這在數(shù)學(xué)上根本不是問題。 由上文知道，協(xié)方差矩陣C是一個是對稱矩陣，在線性代數(shù)上，實對稱矩陣有一系列非常好的性質(zhì)： 1）實對稱矩陣不同特征值對應(yīng)的特征向量必然正交。 2）設(shè)特征值 λ 重數(shù)為r，則必然存在r個線性無關(guān)的特征向量對應(yīng)于λ，因此可以將這r個特征向量單位正交化。 由上面兩條可知，一個n行n列的實對稱矩陣一定可以找到n個單位正交特征向量，設(shè)這n個特征向量組成矩陣：
則對協(xié)方差矩陣C有如下結(jié)論：
其對角元素為各特征向量對應(yīng)的特征值（可能有重復(fù)）。 換句話說，只要求出C的特征值，再求出每一個特征值對應(yīng)的特征向量，根據(jù)特征值的大小把特征向量排列成矩陣E，則E的轉(zhuǎn)置就是矩陣P。 我們已經(jīng)找到了需要的矩陣P：
P是協(xié)方差矩陣的特征向量單位化后按行排列出的矩陣，其中每一行都是C的一個特征向量。如果設(shè)P按照Λ中特征值的從大到小，將特征向量從上到下排列，則用P的前K行組成的矩陣乘以原始數(shù)據(jù)矩陣X，就得到了我們需要的降維后的數(shù)據(jù)矩陣Y。 至此我們完成了整個PCA的數(shù)學(xué)原理討論。在下面的一節(jié)，我們將給出PCA的一個實例。 算法與實例 PCA算法 下面總結(jié)一下PCA的算法步驟： 設(shè)m條n維數(shù)據(jù)。
實例 這里以上文提到的
為例，我們用PCA方法將這組二維數(shù)據(jù)其降到一維。 因為這個矩陣的每行已經(jīng)是零均值，這里我們直接求協(xié)方差矩陣：
然后求其特征值和特征向量，具體求解方法不再詳述，可以參考相關(guān)資料。求解后特征值為：
其對應(yīng)的特征向量分別是：
那么標準化后的特征向量為：
因此我們的矩陣P是：
可以驗證協(xié)方差矩陣C的對角化：
最后我們用P的第一行乘以數(shù)據(jù)矩陣，就得到了降維后的表示：
降維投影結(jié)果如下圖：
MATLAB實現(xiàn) MATLAB實現(xiàn)PCA的方法主要有2種：
方法1 [COEFF SCORE latent] = princomp(x) 參數(shù)說明： 1）. COEFF是主成分分量，即樣本協(xié)方差矩陣的特征向量；就是P 2）. SCORE主成分即樣本X在主成份分量COEFF上的投影 ，若需要降k維，則只需要取前k列主成分分量即可；就是Y 3）. lantent是協(xié)方差矩陣特征值組成的向量。 用SCORE( : , 1:K)就是要求的降維后的目標矩陣 下面實現(xiàn)這13個4維行向量組成的矩陣：
得到：
和結(jié)果：
這樣13個思維向量就降為了13個2維向量： 求貢獻率：
得到前2維就占到了貢獻率的98%； 所以用一下命令看到四個維度在兩個維度上的投影，藍色線表示每個維度的投影，紅點表示每組值的投影，其中紅色值是等比例縮放的，為了保證最大的值為正的，藍色的線的正負也做了變化：
方法2 PCA算法一句話表示就是“將所有樣本X均值m，再乘以樣本的協(xié)方差矩陣C的特征向量V，即為PCA主成分分析”。 [1].將原始數(shù)據(jù)按行組成ｍ行ｎ列樣本矩陣X（每行一個樣本，每列為一維特征） [2].求出樣本X的協(xié)方差矩陣C和樣本均值m；（Matlab可使用cov()函數(shù)求樣本的協(xié)方差矩陣C，均值用mean函數(shù)） [3].求出協(xié)方差矩陣的特征值D及對應(yīng)的特征向量V；（Matlab可使用eigs()函數(shù)求矩陣的特征值D和特征向量V） [4].將特征向量按對應(yīng)特征值大小從上到下按行排列成矩陣，取前k行組成矩陣P；（eigs()返回特征值構(gòu)成的向量本身就是從大到小排序的） [5].Y=(X-m)×P即為降維到k維后的數(shù)據(jù)；
Java實現(xiàn) 編寫代碼庫如下：
此處不再詳細說明。 思考 根據(jù)上面對PCA的數(shù)學(xué)原理的解釋，我們可以了解到一些PCA的能力和限制。PCA本質(zhì)上是將方差最大的方向作為主要特征，并且在各個正交方向上將數(shù)據(jù)“離相關(guān)”，也就是讓它們在不同正交方向上沒有相關(guān)性。 因此，PCA也存在一些限制，例如它可以很好的解除線性相關(guān)，但是對于高階相關(guān)性就沒有辦法了，對于存在高階相關(guān)性的數(shù)據(jù)，可以考慮Kernel PCA，通過Kernel函數(shù)將非線性相關(guān)轉(zhuǎn)為線性相關(guān)。另外，PCA假設(shè)數(shù)據(jù)各主特征是分布在正交方向上，如果在非正交方向上存在幾個方差較大的方向，PCA的效果就大打折扣了。 最后需要說明的是，PCA是一種無參數(shù)技術(shù)，也就是說面對同樣的數(shù)據(jù)，如果不考慮清洗，誰來做結(jié)果都一樣，沒有主觀參數(shù)的介入，所以PCA便于通用實現(xiàn)，但是本身無法個性化的優(yōu)化。 希望這篇文章能幫助朋友們了解PCA的數(shù)學(xué)理論基礎(chǔ)和實現(xiàn)原理，借此了解PCA的適用場景和限制，從而更好的使用這個算法 注：本文主要根據(jù)網(wǎng)絡(luò)博客內(nèi)容和MATLAB幫助文檔撰寫
|
|
|
來自： 吳敬銳 > 《數(shù)學(xué)》
