1、數(shù)值實驗03:奇異值分解與主成分分析選作問題（研究性的）6、假設(shè)數(shù)據(jù)源是一系列的圖像，每幅圖像都是一個矩陣。分別用經(jīng)典的主成分分析方法和奇異值分解方法計算特征臉。注意數(shù)據(jù)的中心化與歸一化處理的影響。（1）奇異值分解：是一個能夠適用于任意矩陣的一種分解方法：A（n*ri=VU為M*M方陣（U里面的正交向量稱為左奇異向量），另是一個M*N的矩陣（除了對角線的元素都是0,對角線上的元素稱為奇異值），W是一個N*N的方（V里面正交的向量稱為右奇異向量）。我們將一個矩陣A的轉(zhuǎn)置乘以A,并對ATA求特征值（ATA）Vi二入m則v就為右奇異向量，且奇異值6=/石，左奇異值ub就為奇異值，U就為奇異向量。奇異

2、值b跟特征值類似，在矩陣2中也是從大到小排列，而且G的減少特別的快，在很多情況下，前10%甚至1%的奇異值的和就占了全部的奇異值之和的99%以上了。也就是說，我們也可以用前r大的奇異值來近似描述矩陣，部分奇異值分解：Amxn«U.XrErxrVTrxnG是一個遠小于m、11的數(shù)）給定一幅M*N大小的圖像，將它表示成M*N*1維向量，向量中元素為像素點的灰度，按行存儲，則如下公式分別表示第i張圖片和n張圖片的平均值：兀1乞1X,=兀2Xi2n/=1令M*N*n矩陣X為：X-X一X,X?一X,X“_X即中心化，將坐標(biāo)原點移動到平均值位置。設(shè)Q=XXT,則Q是一個MN*MN矩陣:0被稱為協(xié)

3、方差矩陣。那么X中每一個元素Xj可以表達成:X/i+工gjiei/=i其中e,是非零特征值對應(yīng)的特征向量，對于M*N圖像，e1,e2,.,en是M*N*1維相互正交的向量。尺度g”是X在空間中的坐標(biāo)。為了降維，可以對特征值設(shè)定閾值或按照其他準(zhǔn)則，尋找協(xié)方差矩陣Q中前k個特征向量。Q為M*N*M*N,通常很龐大。考慮矩陣P=XTXQ的大小為M*N*M*N,而P的大小為n*n,N為訓(xùn)練樣本圖像數(shù)量，通常n«M*N設(shè)e是矩陣P的特征值九對應(yīng)的特征向量，則有：Pe=XeXTXe=XeXXTXe=XXeQ(Xe)=%(Xe)所以X*e是矩陣Q的特征值入對應(yīng)的特征向量。這就是用求特征值分解的方法

4、。對Q進行奇異值分解OmN*MN=UwnMnZhnMhVvnW<U就是QQT的特征向量，V就是Q9的特征向量，另中奇異值的平方就是QQ和QTQ的特征值。(2)主成分分析(PCA)的原理就是將一個高維向量x,通過一個特殊的特征向量矩陣U,投影到一個低維的向量空間中，表征為一個低維向量y,并且僅僅損失了一些次要信息。也就是說，通過低維表征的向量和特征向量矩陣，可以基本重構(gòu)出所對應(yīng)的原始高維向量。在人臉識別中，特征向量矩陣U稱為特征臉空間，因此其中的特征向量m進行量化后可以看出人臉輪廓，在下面的實驗中可以看出。設(shè)有n個人臉訓(xùn)練樣本，每個樣本由其像素灰度值組成一個向量X，則樣本圖像的像素點數(shù)即為

5、Xi的維數(shù),由向量構(gòu)成的訓(xùn)練樣本集為%1,%2,-,%no該樣本集的平均向量為：1C八_£X,門7=1平均向量又叫平均臉。樣本集的協(xié)方差矩陣為：1n一一1c二一£(心一幻(心一Qn1=1求出協(xié)方差矩陣的特征向量u,和對應(yīng)的特征值入：，這些特征向量組成的矩陣u就是人臉空間的正交基底，用它們的線性組合可以重構(gòu)出樣本中任意的人臉圖像。并且圖像信息集中在特征值大的特征向量中，即使丟棄特征值小的向量也不會影響圖像質(zhì)量。將協(xié)方差矩陣的特征值按從大到小順序：人二仏二二幾dn«+1=由大于入d的入對應(yīng)的特征向量構(gòu)成主成分，主成分構(gòu)成的變換矩陣為：U=(5,“2,，u這樣每一幅人臉

6、圖像都可以投影到二（q,勺，4）構(gòu)成的特征臉子空間中。MATLAB實踐:選取16張人臉圖像作為數(shù)據(jù)源，大小為80X80（這里的人臉圖像要求大小相同，人眼部位盡可能對齊），把圖像存儲為80X80,16的矩陣A,每列表示一張圖像，每行代表同一個位置的像素，因此一共有80X80個維度。中心化時各自減去每個維度的均值，由于圖像數(shù)據(jù)的量綱一樣，所以不需要歸一化。16張人臉為：-（a）對X用經(jīng)典的主成分分析法計算特征臉，取前15個對應(yīng)主成分特征臉:51525354555657585960jTFin亡乂1(刃2);Trainnujnber=size(y:2):A=：fori=l:Iraiii_nujnber

7、;temp二double(y(:,i)A=Atemp:endL二A'#A;VD=eig(L):L_eig_vec=:61-Ffori=l:size(V,2):62636465L.eis.,vec=L_eig_vecV(:,i):endend66一67 _68 一69 -70 _71 一Eigenfaces=A#L_eig_vec:fori=l;15eigenfaces=reshape(Eigerifaces?i)S0?80):figure(i):imshov(jnat2gray(eigexi-faces');|end72一Nean=reshape(%80,80):73一imsh

8、ow(juat2gray(Mean');通常情況下MN»P的，而矩陣非零特征值的個數(shù)為minMN-1,P-1,所以在實現(xiàn)中使用維數(shù)少的P*P矩陣來代替理論上的協(xié)方差矩陣（MN*MN）,減少計算。接著我們根據(jù)PCA算法的理論對得到的特征值進行排序，并舍棄一部分特征值（所占能量少，即特征值小的部分）在實現(xiàn)中我們設(shè)定的閾值為1,保留特征值大于1的，小于1的將被舍棄。由此我們再求得協(xié)方差矩陣的特征向量，并且此特征向量就是所謂的“特征臉”。平均臉特征臉特征臉特征臉平均臉特征臉特征臉特征臉特征臉特征臉特征臉特征臉特征臉特征臉特征臉特征臉51 一52 _53 _54 一55 _56 -57

9、 一58 _5959 6162一63 _64 65 _66 67-6S一69 _70 _71 _72 _73 -(b) 對X用奇異值方法計算特征臉，取前15個對應(yīng)主成分特征臉:m二mea2i(y)2):Irain_number=size(yJ2):A=:EJfori=l:Irainnimber:teinp=double(y(:,i)一m:A=A1einp；endeu.jed?ev=svd(Aj0):96ed=diag：(ed)2:L-eig_vec=:EJfori=l:size(ev?2)if(ed(iji)>1)L.e.ig.,ye£=L_eig.vecev(:,i)l;en

10、dendEigenfaces=A*L_eig_vec:fori二1:15eigenfaces=reshape(Eigenfaces(:>i)8080);figure(i);ijnshov(nat2gray(eigenfaces'):endMean=reshape(叫80,80):inshow(mat2gray(Mean"):采用svd分解來得到特征值和特征向量。平均臉特征臉特征臉特征臉特征臉特征臉特征臉特征臉特征臉特征臉特征臉特征臉特征臉特征臉特征臉特征臉由于SVD與PCA得到的特征向量可能符號相反，所以特征臉不同。7、奇異值分解與主成分分析是線性的降維方法。研究非線性

11、的方法如LLE,并應(yīng)用于適當(dāng)選擇的數(shù)據(jù)進行計算。分析和研究LLE與PCA的差別。答：(1)LLE分析：LLE(局部線性嵌入)方法是流形學(xué)習(xí)的一種算法。流形學(xué)習(xí)，它是用非線性方法去發(fā)現(xiàn)高維數(shù)據(jù)潛在的低維流形，然后在低維流形坐標(biāo)上展示出這種流形結(jié)構(gòu)。總之，流形學(xué)習(xí)是把一組高維空間中的數(shù)據(jù)在低維空間中重新展示，最終達到降維的目的。假設(shè)*=比，卩，X,G,ie1,.,冊是原始高維空間的n個樣本點，通過流行學(xué)習(xí)，發(fā)現(xiàn)嵌入在高維空間中的低維流形，Y=匕，yn>兒eRd,，丘1,«0。LLE是一種局部優(yōu)化算法，其基本思想是：認為在局部意義下，數(shù)據(jù)的結(jié)構(gòu)是線性的，因此在局部區(qū)域內(nèi)數(shù)據(jù)點兀可以用

12、其近鄰點虧的線性組合工尸iWXj來近似表示，即耳対工冋W%,這樣在數(shù)據(jù)點和其近鄰點之間就構(gòu)造了一個重構(gòu)權(quán)"，由此重構(gòu)權(quán)組成的權(quán)向量恰好保持了高維數(shù)據(jù)的局部線性結(jié)構(gòu)，在低維空間中也保持這種局部的線性結(jié)構(gòu)，即在低維空間中有門工j=】wyj因為局部區(qū)域內(nèi)兀是近似地由W和線性表示出來的，因此會有誤差存在,此誤差盡管不能消除，但可以使其達到最小，故引入誤差函數(shù)：其限制條件為：1）若Xj不在Xj的鄰域內(nèi)，則褊=°；2）若Xj在兀的鄰域內(nèi),則WjHO,且滿足工丿/=。（2）LLE算法的實現(xiàn)在MATLAB實現(xiàn)中，我們將LLE的實現(xiàn)用下述函數(shù)表示：1JfunctionY=Lle（爲(wèi)K,d）其

13、中X為我們的數(shù)據(jù)集，它是一個D*N的矩陣，D為采樣點的維度，N為采樣點的個數(shù)；K為近鄰點的個數(shù)，d是我們想要降到的維度，最終輸出為降維后新的d*N矩陣。D-步驟-：利用歐式距離*語區(qū)wl求得每個數(shù)據(jù)點林個緊鄰點步驟二：根據(jù)第一步求取的緊鄰點對數(shù)據(jù)線性重構(gòu)并計算重構(gòu)權(quán)值矩陣W。將誤差函數(shù)化簡為：min£（）=環(huán)-工爲(wèi)s=工:摳爲(wèi)S=瑁陽九ay）=必化-訃=九譏旳V1w=w1=1利用拉格朗日乘子法在乙円。"J"的約束條件下，求mi"")=工;R-工;/凡的最小值，即:對上式W求導(dǎo)并令其為0,則可推出:其中乙eRS=a-x"匕-X2J）,孔

14、=嘰仏2,，唧,兀為k維全1列向量。MATLAB對重構(gòu)權(quán)值矩陣W的實現(xiàn)如下：if(K>D)tol=le-3;elsetol=0：end¥=zeros(K,N):forii=l:Nz=K(:neighborhood(:,ii)-repmat(K(:，ii),1,K):C=z?*z:C=C+eye(K,K)*tol*trace(C):W(:ii)=Cones(KJ);W(：il)=W(:jii)/swn(V(:,iil);步驟三：求低維嵌入Y由于重構(gòu)權(quán)向量所描述的流形的局部幾何結(jié)構(gòu)在降維后也是保持不變的。因此，利用上步求得的在低維空間內(nèi)重構(gòu)，使下面局部重建損失函數(shù)最?。簃in僅F）

15、=卜-乞：=】化宀|2=乙J乩-兩I=trYI一0）（Z-）7廠）=trYMY為了限定低維數(shù)據(jù)均勻分布和避免產(chǎn)生退化解，對Y加了兩個約束條件：工打兒=/利用拉格朗日乘子，并結(jié)合約束條件得：厶（卩）=+兄（"7-NI）上式對Y求導(dǎo)得：加=兄廠，所以（一W=0,則有1-1=0,M最小的d個（2d+1）非零特征值所對應(yīng)特征向量為4,5,耳+1,則廠="2,口3,耳+J即為所求的低維嵌入（最小特征值為0時不能反映原始數(shù)據(jù)的特征，所以必須舍棄）sparse(1:N51:%ones(1=N),虬皿4*K*N):Hforii=l:Njj=neighborhood(:jii):jj)-w?

16、:M(jjj®(jj.jj)+w*w5；end：options.disp=0:options.isreal=l:options.issym.=1:Y5eig&nyals=eigs(%d+l305options):Y=Y(;,2:d+l),*sqrt(N):(3) 比較PCA與LLE的區(qū)別：(a) 從降維方法來看：降維方法通常分為線性降維和非線性降維O線性降維是假設(shè)高維數(shù)據(jù)位于全局線性的結(jié)構(gòu)中，使得降維后的低維數(shù)據(jù)能保持數(shù)據(jù)點的線性關(guān)系，PCA是常用的線性降維方法；但當(dāng)數(shù)據(jù)是非線性時，線性降維方法將破壞原始數(shù)據(jù)間的拓撲結(jié)構(gòu)，無法探索數(shù)據(jù)間的內(nèi)部規(guī)律，因此出現(xiàn)了揭示數(shù)據(jù)間非線性性

17、質(zhì)的非線性降維方法，流形學(xué)習(xí)是非線性降維方法的一個重要分支?？傊琍CA的特點是全局線性；LLE特點是局部線性、全局非線性。(b) 從適用性來看：對于非線性的高維數(shù)據(jù)，LLE算法能展現(xiàn)其流形分布，而PCA可能會發(fā)生明顯扭曲而失效。PCA可能會使流形中相隔很遠的點映射到低維空間后變得相近，這樣便很難揭示其流形分布；而LLE能保持原始數(shù)據(jù)拓撲結(jié)構(gòu)不變。由于PCA的目的是尋找最小均方意義下最能夠代表原始數(shù)據(jù)的投影方法(尋找最優(yōu)方向)，所以PCA對橢球狀分布的樣本集有很好的效果，學(xué)習(xí)所得的主方向就是橢球的主軸方向。而LLE適用于分布均勻并稠密的數(shù)據(jù)集的降維，而當(dāng)數(shù)據(jù)集的分布稀疏時，數(shù)據(jù)點的關(guān)聯(lián)性較弱，選擇的k近鄰容易造成信息選取方向的缺失，線性重構(gòu)誤差大。(c) 從算法實現(xiàn)來看：PCA將方差的大小作為保持原始高維數(shù)據(jù)信息量多少標(biāo)準(zhǔn)，通過求解中心化和歸一化后的數(shù)據(jù)集