藍(lán)雯飛，汪敦志，張盛蘭

(中南民族大學(xué) 計算機科學(xué)學(xué)院，武漢 430074)

在機器學(xué)習(xí)中，隨著維度的增加，樣本將變得越來越稀疏，在這種情況下，也更容易找到一個超平面將目標(biāo)分開.然而，在高維空間訓(xùn)練形成的分類器，相當(dāng)于在低維空間的一個復(fù)雜的非線性分類器，這種分類器過多地強調(diào)了訓(xùn)練集的準(zhǔn)確率甚至于對一些錯誤、異常的數(shù)據(jù)也進行了學(xué)習(xí)，而正確的數(shù)據(jù)卻無法覆蓋整個特征空間.故而，這樣得到的分類器在對新數(shù)據(jù)進行預(yù)測時將會出現(xiàn)錯誤.這種現(xiàn)象稱為過擬合，同時也是維度災(zāi)難的直接體現(xiàn)[1].

在高維度空間，距離度量逐漸失去了度量差異性的能力.由于分類是基于這些距離度量(如歐幾里得距離、馬氏距離、曼哈頓距離)的，分類算法在低維度空間更容易實現(xiàn)[2,3].

緩解維度災(zāi)難的一個重要途經(jīng)是降維.機器學(xué)習(xí)領(lǐng)域中所謂的降維就是指采用某種映射方法，將原高維空間中的數(shù)據(jù)點映射到低維度空間中.目前大部分降維算法處理向量表達(dá)的數(shù)據(jù)，也有一些降維算法處理高階張量表達(dá)的數(shù)據(jù).之所以使用降維后的數(shù)據(jù)表示，是因為在原始的高維空間中，包含有冗余信息以及噪音信息，在實際應(yīng)用(例如圖像識別)中造成了誤差，降低了準(zhǔn)確率；而通過降維，我們希望減少冗余信息所造成的誤差，提高識別(或其它應(yīng)用)的精度.通過降維算法可以尋找數(shù)據(jù)內(nèi)部的本質(zhì)結(jié)構(gòu)特征[4,5].降維已經(jīng)廣泛應(yīng)用于與數(shù)據(jù)分析處理有關(guān)的生物醫(yī)療、基因測試、圖像、金融、計算機網(wǎng)絡(luò)等領(lǐng)域.

YANG P Y等[6]提出了一種新的流式主成分分析算法.流式主成分分析的目標(biāo)是找到可以解釋順序進入內(nèi)存的d維數(shù)據(jù)點的最大方差的k維子空間.大多數(shù)流式PCA算法僅使用傳入的樣本更新當(dāng)前模型，然后立即轉(zhuǎn)儲信息以節(jié)省內(nèi)存.但是，先前流式數(shù)據(jù)中包含的信息可能很有用.受此想法的啟發(fā)，作者開發(fā)了一種名為History PCA的新型流式PCA算法，可實現(xiàn)此目標(biāo).

ZHANG Y S等[7]研究了魯棒LLE，提出了RLLE算法.在傳統(tǒng)的LLE算法中，通過普通最小二乘法計算幾何結(jié)構(gòu)，使得嵌入結(jié)果對噪聲敏感.在RLLE算法中，最小角度回歸和彈性網(wǎng)絡(luò)(LARS-EN)技術(shù)用于計算局部結(jié)構(gòu).此外，提出了一種基于RLLE和支持向量機(SVM)的故障診斷方法，用于機械故障診斷.在合成和實際數(shù)據(jù)集上進行的實驗證明了所提出的方法在故障診斷方面的優(yōu)點.

圖像是高維的數(shù)據(jù)，通過降維處理，可以降低數(shù)據(jù)的復(fù)雜度，發(fā)現(xiàn)數(shù)據(jù)的內(nèi)在規(guī)律和本質(zhì)，對于分類也有幫助.人臉具有一種典型的流形結(jié)構(gòu)，人臉數(shù)據(jù)集是由于內(nèi)在變量控制形成的非線性流形，人臉圖像數(shù)據(jù)屬于采樣于高維歐氏空間中的低維流形結(jié)構(gòu).通過降維，可以描述不同類別樣本之間的差異，從而有利于分類.

1 PCA與LLE算法介紹

1.1 PCA算法

主成分分析(Principal Component Analysis，PCA)是一種利用線性映射來進行數(shù)據(jù)降維的方法，同時去除數(shù)據(jù)的相關(guān)性，以最大限度保持原始數(shù)據(jù)的方差信息.

給定d維空間中的樣本X=(x1,x2,…,xm)∈Rd×m.為了便于后續(xù)計算，首先對樣本進行中心化:

對其線性變換之后得到d′維空間中的樣本：

Z=WTX，

(1)

其中W∈Rd×d′是變換矩陣，W的各列wi與wj正交.Z是樣本在新空間中的表達(dá).變換矩陣W可視為d′個d維基向量，zi=WTxi是第i個樣本與這d′個基向量分別做內(nèi)積得到的d′維屬性向量.

(2)

PCA原理圖可參見文獻(xiàn)[5].

1.2 LLE算法

局部線性嵌入(Locally Linear Embedding，LLE)是一種借鑒了拓?fù)淞餍胃拍畹慕稻S方法.“流形”是在局部與歐氏空間同胚的空間，它在局部具有歐氏空間的性質(zhì).假設(shè)數(shù)據(jù)是均勻采樣于一個高維歐氏空間中的低維流形，流形學(xué)習(xí)就是從高維采樣數(shù)據(jù)中找到低維流形[8].流形學(xué)習(xí)可以用于實現(xiàn)聚類、分類以及回歸.

局部線性嵌入從局部幾何結(jié)構(gòu)入手，試圖保持鄰域內(nèi)樣本之間的線性關(guān)系[9].LLE原理圖可參見文獻(xiàn)[5].

給定d維空間中的樣本X=(x1,x2,…,xm)∈Rd×m，LLE先為每個樣本xi找到其近鄰下標(biāo)集合Qi，然后計算出基于Qi中的樣本點對xi進行線性重構(gòu)的系數(shù)：

(3)

解出wij，于是xi在低維空間的坐標(biāo)zi可通過下式求解：

(4)

令Z=(z1,z2,…,zm)∈Rd′×m為降維后數(shù)據(jù)，(Wij)=wij，矩陣M如下：

M=(I-W)T(I-W)，

(5)

則優(yōu)化問題可重寫為：

(6)

可通過特征值分解求解：M最小的d′個特征值對應(yīng)的特征向量組成的矩陣即為ZT.

過大的降維后維數(shù)會導(dǎo)致降維后的數(shù)據(jù)存在大量多余的噪聲信息，為分析處理問題帶來麻煩；過小的降維后維數(shù)則會導(dǎo)致數(shù)據(jù)的特征向量缺失，致使降維結(jié)果不完善.只有當(dāng)降維維數(shù)與本征維數(shù)之間基本保持一致時，降維結(jié)果才達(dá)到最佳.

2 融合PCA與LLE的降維方法

2.1 模型的提出

PCA考慮的是數(shù)據(jù)的全局結(jié)構(gòu)，LLE考慮的是數(shù)據(jù)的局部幾何關(guān)系，融合兩個算法可使兩者優(yōu)缺點互補.

首先對樣本中心化，由于中心化只是對樣本進行平移，并不會改變樣本之間的位置關(guān)系，對LLE算法不會有影響.

將LLE算法變?yōu)榫€性的形式，令Z=WTX，(6)式化為：

(7)

結(jié)合(2)，(7)式得：

即：

(8)

(8)式可通過特征值分解求解.該式結(jié)合了主成分分析(PCA)和局部線性嵌入(LLE)，可以提高分類器的準(zhǔn)確率.

2.2 模型求解

令矩陣

G=X(I-γM)XT，

(9)

G=XXT-γXMXT，GT=(XT)TXT-γ(XT)TMTXT=XXT-γXMXT=G，所以G是對稱矩陣.對稱陣的特征值為實數(shù).

設(shè)W的第一主軸方向u1使得u1TGu1最大，則構(gòu)成一個最大化問題：

maxu1TGu1，s.t.u1Tu1=1.

算法流程如下.

輸入:樣本集X=(x1,x2,…,xm)∈Rd×m;近鄰參數(shù)k;低維空間維度d'.輸出:樣本集在低維空間的投影Z=z1,z2,…,zm ∈Rd'×m.過程:對所有樣本中心化;for i=1,2,…,m do確定xi的k近鄰;求得重構(gòu)系數(shù)wij,j∈Qi;對于j?Qi,令wij=0;end for從(5)式得到M;從(9)式得到G;對G進行特征值分解,最大的d'個特征值對應(yīng)的特征向量構(gòu)成W;Z=WTX;

對于新樣本xnew降維，首先減去所有訓(xùn)練樣本的均值，再用WT乘以xnew.

3 高維數(shù)據(jù)降維可視化

圖像數(shù)據(jù)往往是高維的，大量高維樣本圖像的低維嵌入性特征往往并不直觀明顯.將手寫體圖像數(shù)據(jù)集MNIST利用PCA、LLE降維到三維，對這些三維坐標(biāo)值和相應(yīng)的標(biāo)簽，利用Python語言的Matplotlib模塊繪制三維散點圖像，不同類別用不同顏色表示，如圖1～3所示.可以看到，不同類別的樣本降維后的坐標(biāo)點位于低維空間的不同區(qū)域，同一類別的樣本降維后的坐標(biāo)點在低維空間基本上匯聚在一起，這說明利用降維對圖像進行分類和識別的可行性.

圖1 PCA降維Fig.1 Dimension reduction using PCA

圖2 LLE降維Fig.2 Dimension reduction using LLE

圖3 PCA_LLE降維Fig.3 Dimension reduction using PCA_LLE

通過降維，把圖像數(shù)據(jù)映射到低維空間，能夠提取圖像特征.從圖中可以看到，PCA降維后的數(shù)據(jù)分布比較均勻，LLE降維后的數(shù)據(jù)在一些位置比較集中.這是因為PCA是全局性的算法，LLE是局部性的算法.PCA_LLE降維后的數(shù)據(jù)分布是比較均勻的.

單個阿拉伯?dāng)?shù)字(0～9)圖像理論上是一個高維空間中的低維流形.為直觀理解PCA算法、LLE算法對圖像數(shù)據(jù)集的降維效果，選取數(shù)據(jù)集中標(biāo)簽相同的數(shù)字圖像30個，分別運用PCA、LLE、PCA_LLE將圖像數(shù)據(jù)降維成兩個維度，利用Python語言的Matplotlib模塊，以這兩個維度的值為坐標(biāo)，將對應(yīng)的數(shù)字圖像顯示在平面上，如圖4～6所示.

圖4 PCA降維結(jié)果顯示Fig.4 Result of dimension reduction using PCA

圖5 LLE降維結(jié)果顯示Fig.5 Result of dimension reduction using LLE

圖6 PCA_LLE降維結(jié)果顯示Fig.6 Result of dimension reduction using PCA_LLE

圖4為數(shù)字‘5’PCA降維結(jié)果，可以看出相鄰的、空間位置比較靠近的圖片內(nèi)容是比較接近的.相似的圖片降維后的坐標(biāo)點互相靠近.圖5為數(shù)字‘2’LLE降維結(jié)果，可以看到，‘2’下面的筆畫有個圈的圖像降維后匯集在一起，且相似的圖像比較靠近.圖6為數(shù)字‘2’PCA_LLE降維結(jié)果，可以看出內(nèi)容相似的圖像降維后的位置比較靠近，且相較于LLE算法，PCA_LLE降維后的數(shù)據(jù)分布更均勻.

4 實驗與分析

4.1 手寫體圖像識別

4.1.1 實驗方案

下載MNIST手寫數(shù)字圖像數(shù)據(jù)集，加載訓(xùn)練集和測試集.

(1)不進行降維，直接對數(shù)據(jù)集使用KNN算法分類.

(2)使用PCA、LLE、PCA_LLE三種算法對數(shù)據(jù)集降維，并訓(xùn)練分類器.調(diào)整以下參數(shù)：

公式(7)中的參數(shù)γ；

降維后的維數(shù)d′；

近鄰個數(shù)k；

并記錄相應(yīng)的準(zhǔn)確率，找到使準(zhǔn)確率最高的參數(shù)值.

4.1.2 實驗環(huán)境

本文的實驗是在Windows10系統(tǒng)下進行的，CPU:Intel(R) Core(TM) i5-6200U，內(nèi)存4.0GB.使用的編程語言為Python3，開發(fā)工具為Anaconda Spyder.

4.1.3 實驗結(jié)果與分析

不降維，訓(xùn)練樣本為5000個，測試樣本為10000個時，使用KNN算法進行分類，當(dāng)KNN算法的近鄰數(shù)k分別為：4、5、6、10、15時，準(zhǔn)確率分別為：0.9312、0.9325、0.9293、0.9251、0.9194.k值如果太小，預(yù)測結(jié)果就會對近鄰的樣本點十分敏感，如果近鄰的樣本點恰巧是噪聲，預(yù)測就會出錯；k太大，近鄰中又可能包含太多的其他類別的樣本點.

取MNIST數(shù)據(jù)集的前5000個訓(xùn)練樣本進行降維，使用K近鄰算法對降維后的數(shù)據(jù)分類.LLE算法和PCA-LLE算法近鄰個數(shù)k取值8～12效果較好.k的取值過大，就可能會影響整個流形的平滑性，就不能體現(xiàn)其局部特性，這樣會導(dǎo)致LLE算法趨向于PCA算法，甚至丟失流形的一些小規(guī)模的結(jié)構(gòu)；而k的取值過小，就很難保證樣本點在低維空間的拓?fù)浣Y(jié)構(gòu)，可能把連續(xù)的流形脫節(jié)成子流形.PCA-LLE算法當(dāng)γ=0.2時，分類的準(zhǔn)確率最高.

使用PCA和KNN算法進行分類，當(dāng)降維后的維數(shù)分別為：20、30、40、50、70、100時，準(zhǔn)確率分別為：0.9287、0.9352、0.9210、0.9099、0.8814、0.8280.使用LLE和KNN算法進行分類，當(dāng)降維后的維數(shù)分別為：40、50、70、100時，準(zhǔn)確率分別為：0.9266、0.9273、0.9313、0.9262.使用PCA_LLE和KNN算法進行分類，當(dāng)降維后的維數(shù)分別為：30、35、40、50、70、100時，準(zhǔn)確率分別為：0.9457、0.9473、0.9464、0.9448、0.9422、0.9372.

可以看出PCA算法在降維后的維數(shù)為30時分類的準(zhǔn)確率最高，為93.52%.LLE算法在降維后的維數(shù)為70時分類的準(zhǔn)確率最高，為93.13%，說明本征維度在70左右.PCA_LLE在降維后的維數(shù)為35時分類的準(zhǔn)確率最高，為94.73%，說明PCA_LLE算法的效果較PCA和LLE有所提高，而且使用PCA或PCA_LLE降維后的分類準(zhǔn)確率比不降維的要好.

10000個新樣本的情況下降維時間比較見表1.

表1 新樣本降維時間Tab.1 Dimension reduction time of new samples

可見PCA_LLE算法對新樣本的降維時間遠(yuǎn)低于LLE，這是由于它是通過坐標(biāo)變換把新樣本直接映射到低維空間.現(xiàn)有的對流形學(xué)習(xí)的改進算法，如陳鵬飛等[10]提出的核框架下等距映射與局部線性嵌入相結(jié)合的KISOMAPLLE算法，對于新樣本降維仍然要尋找它的近鄰樣本.而PCA_LLE算法不需要尋找近鄰，直接通過正交變換矩陣將新樣本映射到低維空間，因此，降維時間大大減少.

4.2 人臉圖像識別

實驗采用ORL人臉圖像數(shù)據(jù)集，該數(shù)據(jù)集包含40個人的共400張人臉圖像，每人10張.對每個人隨機選取3張作為訓(xùn)練集，其余7張為測試集.

先對訓(xùn)練集進行降維，降維方案有3種：1)先使用PCA降維，再對結(jié)果使用LDA(線性判別分析)降維；2)僅使用PCA降維；3)僅使用LDA降維.降維后，再使用Logistic Regression算法分類.

進行兩次實驗，每次在每個人中隨機選取3張圖片作為訓(xùn)練樣本.3種方案PCA+LDA，PCA,LDA第一次的分類準(zhǔn)確率為：0.90000，0.878571，0.796429；第二次的分類準(zhǔn)確率為：0.896429，0.882143，0.742857. PCA降維后的維數(shù)為30時，準(zhǔn)確率最高.實驗結(jié)果表明PCA結(jié)合LDA的方法準(zhǔn)確率更高.

為了比較PCA_LLE算法同PCA、LLE算法在人臉識別中的優(yōu)劣勢，分別使用PCA_LLE+LDA，PCA+LDA，LLE+LDA對訓(xùn)練集降維，再用Logistic Regression算法分類，進行四次實驗，準(zhǔn)確率見表2.LLE降維后的維數(shù)為80時，準(zhǔn)確率最高.PCA_LLE降維后的維數(shù)設(shè)為30.

表2 PCA_LLE、PCA、LLE算法準(zhǔn)確率比較

四次實驗，PCA_LLE算法的準(zhǔn)確率均高于PCA算法和LLE算法.

5 結(jié)語

PCA算法在降維時考慮到數(shù)據(jù)的全局結(jié)構(gòu)，使得整體方差最大化.LLE算法則考慮樣本的局部幾何結(jié)構(gòu).本文通過在優(yōu)化目標(biāo)中將PCA與LLE的優(yōu)化目標(biāo)加權(quán)相加，使兩種算法的優(yōu)勢互補.在MNIST手寫數(shù)字圖像數(shù)據(jù)集和ORL人臉圖像數(shù)據(jù)集上的實驗表明：融合PCA和LLE的算法PCA_LLE對數(shù)據(jù)降維，再用分類器分類，準(zhǔn)確率有了一定程度的提高.