PCA算法總結(jié)

精品文庫(kù)摘要： PCA（Principal Component Analysis),稱主成分分析，從統(tǒng)計(jì)學(xué)的角度來(lái)說(shuō)是一種多元統(tǒng)計(jì)方法。PCA通過(guò)將多個(gè)變量通過(guò)線性變換以選出較少的重要變量。它往往可以有效地從過(guò)于“豐富”的數(shù)據(jù)信息中獲取最重要的元素和結(jié)構(gòu)，去除數(shù)據(jù)的噪音和冗余，將原來(lái)復(fù)雜的數(shù)據(jù)降維，揭示隱藏在復(fù)雜數(shù)據(jù)背后的簡(jiǎn)單結(jié)構(gòu)。近年來(lái)，PCA方法被廣泛地運(yùn)用于計(jì)算機(jī)領(lǐng)域，如數(shù)據(jù)降維、圖像有損壓縮、特征追蹤等等。引言：在人腦的生理特征中，人腦對(duì)外界的認(rèn)知手段多樣，導(dǎo)致人獲取的信息維數(shù)過(guò)高。如果人腦不對(duì)獲取的信息進(jìn)行降維處理，那么人腦對(duì)信息處理的效率和精準(zhǔn)度都會(huì)下降，因此人腦對(duì)這些感知神經(jīng)處理時(shí)，均通過(guò)了復(fù)雜的降維處理。PCA方法廣泛運(yùn)用于從神經(jīng)科學(xué)到計(jì)算機(jī)圖形學(xué)的數(shù)據(jù)分析。因?yàn)樗且环N簡(jiǎn)單的非參方法，能夠從復(fù)雜的數(shù)據(jù)集中提取出數(shù)據(jù)相關(guān)信息。我們進(jìn)行主成分分析的動(dòng)機(jī)是希望計(jì)算出一個(gè)含有噪音數(shù)據(jù)空間的最重要的基，來(lái)重新表達(dá)這個(gè)數(shù)據(jù)空間。但是這些新基往往隱藏在復(fù)雜的數(shù)據(jù)結(jié)構(gòu)中，我們需要濾除噪音來(lái)找到重構(gòu)出數(shù)據(jù)空間的新基。 PCA方法是一個(gè)高普適用方法，它的一大優(yōu)點(diǎn)是能夠?qū)?shù)據(jù)進(jìn)行降維處理，我們通過(guò)PCA方法求出數(shù)據(jù)集的主元，選取最重要的部分，將其余的維數(shù)省去，從而達(dá)到降維和簡(jiǎn)化模型的目的，間接地對(duì)數(shù)據(jù)進(jìn)行了壓縮處理，同時(shí)很大程度上保留了原數(shù)據(jù)的信息，就如同人腦在感知神經(jīng)處理時(shí)進(jìn)行了降維處理。 所以在機(jī)器學(xué)習(xí)和模式識(shí)別及計(jì)算機(jī)視覺領(lǐng)域，PCA方法被廣泛的運(yùn)用。在人臉識(shí)別中，假設(shè)訓(xùn)練集是30幅不同的NN大小的人臉圖像。把圖像中每一個(gè)像素看成是一維信息，那么一副圖像就是N2維的向量。因?yàn)槿四樀慕Y(jié)構(gòu)有極大的相似性，如果是同一個(gè)人臉的話相似性更大。而我們的所希望能夠通過(guò)人臉來(lái)表達(dá)人臉，而非用像素來(lái)表達(dá)人臉。那么我們就可以用PCA方法對(duì)30幅訓(xùn)練集圖像進(jìn)行處理，尋找這些圖像中的相似維度。我們提取出最重要的主成份后，讓被識(shí)別圖像與原圖進(jìn)行過(guò)變化后的主元維度進(jìn)行相似度比較，以衡量?jī)煞鶊D片的相似性。在圖像壓縮方面，我們還可以通過(guò)PCA方法進(jìn)行圖像壓縮，又稱Hotelling或者Karhunen and Leove變換。我們通過(guò)PCA提取出圖像的主分量，去除掉一些次分量，然后變換回原圖像空間，圖像因?yàn)榫S數(shù)的降低得到了很大程度上的壓縮，同時(shí)圖像還很大程度上保留了原圖像的重要信息。正文：PCA方法其實(shí)就是將數(shù)據(jù)空間通過(guò)正交變換映射到低維子空間的過(guò)程。而相應(yīng)的基向量組應(yīng)滿足正交性且由基向量組構(gòu)成的地位子空間最優(yōu)地考慮了數(shù)據(jù)的相關(guān)性。在原數(shù)據(jù)集變換空間后應(yīng)使單一數(shù)據(jù)樣本的相互相關(guān)性降低到最低點(diǎn)。圖1 紅點(diǎn)代表原始數(shù)據(jù)點(diǎn)；綠點(diǎn)代表被映射到低維空間后的點(diǎn)；紫線代表映射平面。方差最大化上面我們說(shuō)過(guò)PCA方法的過(guò)程其實(shí)是尋找低維子空間的過(guò)程。那么什么樣的低維空間才符合我們要求的呢。因?yàn)槲覀兿Ｍ挥成浜蟮臄?shù)據(jù)之間的相關(guān)性降低到最低點(diǎn)，所以我們可以采取求解被映射后方差最大化的最優(yōu)策略來(lái)找到低維空間。假設(shè)我們有N個(gè)樣本數(shù)據(jù)xn,每個(gè)樣本數(shù)據(jù)是D維，我們希望樣本數(shù)據(jù)映射到M1維情況，協(xié)方差矩陣S應(yīng)該有M個(gè)特征特征值：，其對(duì)應(yīng)的特征向量應(yīng)為：u1,un。誤差最小化PCA的另一種構(gòu)造形式是基于誤差最小化。我們引入D維完備正交基向量組，即（6）所以我們可以用完備正交基向量來(lái)線形表示樣本數(shù)據(jù)集中的每一個(gè)數(shù)據(jù)xn，（7）充分利用根據(jù)等式（6）的正交屬性，利用等式（7）可得系數(shù),反代回等式（7），可得等式：（8）我們來(lái)看，表達(dá)等式（8）需要D維信息，而我們的目的是希望用MD維信息近似地表達(dá)出xn：（9）代表的是數(shù)據(jù)點(diǎn)的特殊分量，而bi代表的是所有數(shù)據(jù)點(diǎn)的所共有的分量。我們構(gòu)造一個(gè)目標(biāo)函數(shù):（10）其通俗的含義是我們希望通過(guò)M維表達(dá)的出的數(shù)據(jù)點(diǎn)逼近D維樣本數(shù)據(jù)點(diǎn),這里我們采用歐式距離衡量?jī)蓚€(gè)數(shù)據(jù)點(diǎn)的相似性。那么我們的問(wèn)題又轉(zhuǎn)化為最小化目標(biāo)函數(shù)J。通過(guò)求導(dǎo)，我們可以得出：（11）（12）反代回等式（10），得：（13）因此我們只要找尋協(xié)方差矩陣S的D-M個(gè)最小特征值就可。SVD奇異值分解PCA方法中對(duì)于協(xié)方差矩陣的分解，提取主成分，采用兩種方法：1 特征值分解。該種方法有一定局限性，分解的矩陣必須為方陣。2 SVD奇異值分解。奇異值分解是線性代數(shù)中的一種重要的矩陣分解方法，在信號(hào)處理、統(tǒng)計(jì)學(xué)等領(lǐng)域都有重要的應(yīng)用。奇異值分解可以將一個(gè)比較復(fù)雜的矩陣分解為幾個(gè)更小更簡(jiǎn)單的子矩陣相乘的形式來(lái)表達(dá)，而這些子矩陣描述的是原矩陣的重要的特性。對(duì)于一個(gè)MN大小的矩陣A來(lái)說(shuō)，總是可以分解為:（14）其中U和V分別是AAT和ATA的特征向量，而則是他們的特征根。在PCA方法中，我們選取P個(gè)最大特征根及其所對(duì)應(yīng)的特征向量，對(duì)A進(jìn)行逼近：（15）線性代數(shù)理論證明：A與A在最小二乘法的意義下是逼近的。而當(dāng)P越接近N，則逼近的結(jié)果越接近于原矩陣。所以當(dāng)我們選取的P遠(yuǎn)小于N時(shí)，所需要存儲(chǔ)的信息量就會(huì)越小，達(dá)到了降維和壓縮的目的。一、簡(jiǎn)介 PCA（Principal Components Analysis）即主成分分析，是圖像處理中經(jīng)常用到的降維方法，大家知道，我們?cè)谔幚碛嘘P(guān)數(shù)字圖像處理方面的問(wèn)題時(shí)，比如經(jīng)常用的圖像的查詢問(wèn)題，在一個(gè)幾萬(wàn)或者幾百萬(wàn)甚至更大的數(shù)據(jù)庫(kù)中查詢一幅相近的圖像。這時(shí)，我們通常的方法是對(duì)圖像庫(kù)中的圖片提取響應(yīng)的特征，如顏色，紋理，sift，surf，vlad等等特征，然后將其保存，建立響應(yīng)的數(shù)據(jù)索引，然后對(duì)要查詢的圖像提取相應(yīng)的特征，與數(shù)據(jù)庫(kù)中的圖像特征對(duì)比，找出與之最近的圖片。這里，如果我們?yōu)榱颂岣卟樵兊臏?zhǔn)確率，通常會(huì)提取一些較為復(fù)雜的特征，如sift，surf等，一幅圖像有很多個(gè)這種特征點(diǎn)，每個(gè)特征點(diǎn)又有一個(gè)相應(yīng)的描述該特征點(diǎn)的128維的向量，設(shè)想如果一幅圖像有300個(gè)這種特征點(diǎn)，那么該幅圖像就有300*vector（128維）個(gè)，如果我們數(shù)據(jù)庫(kù)中有一百萬(wàn)張圖片，這個(gè)存儲(chǔ)量是相當(dāng)大的，建立索引也很耗時(shí)，如果我們對(duì)每個(gè)向量進(jìn)行PCA處理，將其降維為64維，是不是很節(jié)約存儲(chǔ)空間?。繉?duì)于學(xué)習(xí)圖像處理的人來(lái)說(shuō)，都知道PCA是降維的，但是，很多人不知道具體的原理，為此，我寫這篇文章，來(lái)詳細(xì)闡述一下PCA及其具體計(jì)算過(guò)程：二、PCA詳解1、原始數(shù)據(jù)：為了方便，我們假定數(shù)據(jù)是二維的，借助網(wǎng)絡(luò)上的一組數(shù)據(jù)，如下：x=2.5, 0.5, 2.2, 1.9, 3.1, 2.3, 2, 1, 1.5, 1.1Ty=2.4, 0.7, 2.9, 2.2, 3.0, 2.7, 1.6, 1.1, 1.6, 0.9T2、計(jì)算協(xié)方差矩陣什么是協(xié)方差矩陣？相信看這篇文章的人都學(xué)過(guò)數(shù)理統(tǒng)計(jì)，一些基本的常識(shí)都知道，但是，也許你很長(zhǎng)時(shí)間不看了，都忘差不多了，為了方便大家更好的理解，這里先簡(jiǎn)單的回顧一下數(shù)理統(tǒng)計(jì)的相關(guān)知識(shí)，當(dāng)然如果你知道協(xié)方差矩陣的求法你可以跳過(guò)這里。（1）協(xié)方差矩陣：首先我們給你一個(gè)含有n個(gè)樣本的集合，依次給出數(shù)理統(tǒng)計(jì)中的一些相關(guān)概念：均值：標(biāo)準(zhǔn)差：方差：既然我們都有這么多描述數(shù)據(jù)之間關(guān)系的統(tǒng)計(jì)量，為什么我們還要用協(xié)方差呢？我們應(yīng)該注意到，標(biāo)準(zhǔn)差和方差一般是用來(lái)描述一維數(shù)據(jù)的，但現(xiàn)實(shí)生活我們常常遇到含有多維數(shù)據(jù)的數(shù)據(jù)集，最簡(jiǎn)單的大家上學(xué)時(shí)免不了要統(tǒng)計(jì)多個(gè)學(xué)科的考試成績(jī)。面對(duì)這樣的數(shù)據(jù)集，我們當(dāng)然可以按照每一維獨(dú)立的計(jì)算其方差，但是通常我們還想了解這幾科成績(jī)之間的關(guān)系，這時(shí)，我們就要用協(xié)方差，協(xié)方差就是一種用來(lái)度量?jī)蓚€(gè)隨機(jī)變量關(guān)系的統(tǒng)計(jì)量，其定義為：從協(xié)方差的定義上我們也可以看出一些顯而易見的性質(zhì)，如：(X的方差)需要注意的是，協(xié)方差也只能處理二維問(wèn)題，那維數(shù)多了自然就需要計(jì)算多個(gè)協(xié)方差，比如n維的數(shù)據(jù)集就需要計(jì)算個(gè)協(xié)方差，那自然而然的我們會(huì)想到使用矩陣來(lái)組織這些數(shù)據(jù)。給出協(xié)方差矩陣的定義：這個(gè)定義還是很容易理解的，我們可以舉一個(gè)簡(jiǎn)單的三維的例子，假設(shè)數(shù)據(jù)集有三個(gè)維度，則協(xié)方差矩陣為可見，協(xié)方差矩陣是一個(gè)對(duì)稱的矩陣，而且對(duì)角線是各個(gè)維度上的方差。（2）協(xié)方差矩陣的求法：協(xié)方差矩陣計(jì)算的是不同維度之間的協(xié)方差，而不是不同樣本之間的。下面我們將在matlab中用一個(gè)例子進(jìn)行詳細(xì)說(shuō)明：首先，隨機(jī)產(chǎn)生一個(gè)10*3維的整數(shù)矩陣作為樣本集，10為樣本的個(gè)數(shù)，3為樣本的維數(shù)。MySample = fix(rand(10,3)*50)根據(jù)公式，計(jì)算協(xié)方差需要計(jì)算均值，那是按行計(jì)算均值還是按列呢，我一開始就老是困擾這個(gè)問(wèn)題。前面我們也特別強(qiáng)調(diào)了，協(xié)方差矩陣是計(jì)算不同維度間的協(xié)方差，要時(shí)刻牢記這一點(diǎn)。樣本矩陣的每行是一個(gè)樣本，每列為一個(gè)維度，所以我們要按列計(jì)算均值。為了描述方便，我們先將三個(gè)維度的數(shù)據(jù)分別賦值：dim1 = MySample(:,1);dim2 = MySample(:,2);dim3 = MySample(:,3);計(jì)算dim1與dim2，dim1與dim3，dim2與dim3的協(xié)方差：sum( (dim1-mean(dim1) .* (dim2-mean(dim2) ) / ( size(MySample,1)-1 ) % 得到 74.5333sum( (dim1-mean(dim1) .* (dim3-mean(dim3) ) / ( size(MySample,1)-1 )% 得到 -10.0889sum( (dim2-mean(dim2) .* (dim3-mean(dim3) ) / ( size(MySample,1)-1 )% 得到 -10*000搞清楚了這個(gè)后面就容易多了，協(xié)方差矩陣的對(duì)角線就是各個(gè)維度上的方差，下面我們依次計(jì)算：std(dim1)2 % 得到 108.3222std(dim2)2% 得到 260.6222std(dim3)2% 得到 94.1778這樣，我們就得到了計(jì)算協(xié)方差矩陣所需要的所有數(shù)據(jù)，調(diào)用Matlab自帶的cov函數(shù)進(jìn)行驗(yàn)證：cov(MySample)可以看到跟我們計(jì)算的結(jié)果是一樣的，說(shuō)明我們的計(jì)算是正確的。但是通常我們不用這種方法，而是用下面簡(jiǎn)化的方法進(jìn)行計(jì)算：先讓樣本矩陣中心化，即每一維度減去該維度的均值，然后直接用新的到的樣本矩陣乘上它的轉(zhuǎn)置，然后除以(N-1)即可。其實(shí)這種方法也是由前面的公式通道而來(lái)，只不過(guò)理解起來(lái)不是很直觀而已。大家可以自己寫個(gè)小的矩陣看一下就明白了。其Matlab代碼實(shí)現(xiàn)如下：X = MySample repmat(mean(MySample),10,1); % 中心化樣本矩陣C = (X*X)./(size(X,1)-1)（為方便對(duì)matlab不太明白的人，小小說(shuō)明一下各個(gè)函數(shù)，同樣，對(duì)matlab有一定基礎(chǔ)的人直接跳過(guò)：B = repmat(A,m,n )%將矩陣 A 復(fù)制 mn 塊，即把 A 作為 B 的元素，B 由 mn 個(gè) A 平鋪而成。B 的維數(shù)是 size(A,1)*m, (size(A,2)*nB = mean(A)的說(shuō)明：如果你有這樣一個(gè)矩陣：A = 1 2 3; 3 3 6; 4 6 8; 4 7 7;用mean(A)（默認(rèn)dim=1）就會(huì)求每一列的均值ans = 3.0000 4.5000 6.0000用mean(A,2)就會(huì)求每一行的均值ans = 2.0000 4.0000 6.0000 6.0000size(A,n)%如果在size函數(shù)的輸入?yún)?shù)中再添加一項(xiàng)n，并用1或2為n賦值，則 size將返回矩陣的行數(shù)或列數(shù)。其中r=size(A,1)該語(yǔ)句返回的是矩陣A的行數(shù)， c=size(A,2) 該語(yǔ)句返回的是矩陣A的列數(shù)）上面我們簡(jiǎn)單說(shuō)了一下協(xié)方差矩陣及其求法，言歸正傳，我們用上面簡(jiǎn)化求法，求出樣本的協(xié)方差矩陣為： 3、計(jì)算協(xié)方差矩陣的特征向量和特征值因?yàn)閰f(xié)方差矩陣為方陣，我們可以計(jì)算它的特征向量和特征值，如下：eigenvectors,eigenvalues = eig(cov)我們可以看到這些矢量都是單位矢量，也就是它們的長(zhǎng)度為1，這對(duì)PCA來(lái)說(shuō)是很重要的。4、選擇成分組成模式矢量求出協(xié)方差矩陣的特征值及特征向量之后，按照特征值由大到小進(jìn)行排列，這將給出成分的重要性級(jí)別。現(xiàn)在，如果你喜歡，可以忽略那些重要性很小的成分，當(dāng)然這會(huì)丟失一些信息，但是如果對(duì)應(yīng)的特征值很小，你不會(huì)丟失很多信息。如果你已經(jīng)忽略了一些成分，那么最后的數(shù)據(jù)集將有更少的維數(shù)，精確地說(shuō)，如果你的原始數(shù)據(jù)是n維的，你選擇了前p個(gè)主要成分，那么你現(xiàn)在的數(shù)據(jù)將僅有p維。現(xiàn)在我們要做的是組成一個(gè)模式矢量，這只是幾個(gè)矢量組成的矩陣的一個(gè)有意思的名字而已，它由你保持的所有特征矢量構(gòu)成，每一個(gè)特征矢量是這個(gè)矩陣的一列。對(duì)于我們的數(shù)據(jù)集，因?yàn)橛袃蓚€(gè)特征矢量，因此我們有兩個(gè)選擇。我們可以用兩個(gè)特征矢量組成模式矢量： 我們也可以忽略其中較小特征值的一個(gè)特征矢量，從而得到如下模式矢量： 5、得到降維后的數(shù)據(jù)其中rowFeatureVector是由模式矢量作為列組成的矩陣的轉(zhuǎn)置，因此它的行就是原來(lái)的模式矢量，而且對(duì)應(yīng)最大特征值的特征矢量在該矩陣的最上一行。rowdataAdjust是每一維數(shù)據(jù)減去均值后，所組成矩陣的轉(zhuǎn)置，即數(shù)據(jù)項(xiàng)目在