基于判別信息的近鄰保持嵌入降維方法

張海武, 陳曉云

(福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院, 福建 福州 350116)

基于判別信息的近鄰保持嵌入降維方法

張海武, 陳曉云

(福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院, 福建 福州 350116)

針對(duì)傳統(tǒng)近鄰保持嵌入算法(NPE)側(cè)重保持樣本的局部結(jié)構(gòu)， 而沒有考慮樣本類別信息的不足, 提出判別局部近鄰保持嵌入算法DLNPE. 該算法利用樣本點(diǎn)的局部結(jié)構(gòu)構(gòu)造新定義下的類內(nèi)類間散布矩陣， 并以此作為判別信息引入目標(biāo)函數(shù). 在6個(gè)真實(shí)數(shù)據(jù)上進(jìn)行實(shí)驗(yàn)， 證明了所提算法的有效性.

降維； 近鄰保持嵌入； 判別信息; 局部結(jié)構(gòu)

0 引言

在各種降維方法中， 線性降維方法如主成分分析(principal component analysis, PCA)[1]和線性判別分析(linear discriminant analysis, LDA)[2]因其簡(jiǎn)單有效而被廣泛使用. 但這些線性方法具有難以保持原始數(shù)據(jù)非線性流形的缺點(diǎn). 為此， 研究人員提出流形降維算法如等容特征映射(isometric feature mapping， ISOMAP)[3]、 拉普拉斯特征映射(laplacian eigenmap,LE)[4]、 局部線性嵌入(locally linear embedding，LLE)等[5]. 這些算法在處理非線性結(jié)構(gòu)數(shù)據(jù)時(shí)可以獲得較好結(jié)果. 然而它們都有一個(gè)共同問題， 即在高維觀測(cè)空間和內(nèi)在低維空間之間建立的隱式映射是定義在訓(xùn)練集上， 無法處理新來樣本問題. 為克服上述缺點(diǎn)， He等[6]人提出近鄰保持嵌入算法(neighborhood preserving embedding，NPE). 盡管NPE的改進(jìn)是有效的， 但它沒有考慮樣本的類別信息， 是一種無監(jiān)督降維方法. 于是， 王國(guó)強(qiáng)等[7]受LDA方法啟發(fā)， 在NPE基礎(chǔ)上引入全局判別信息， 提出保持近鄰判別嵌入算法(neighborhood preserving discriminant embedding, NPDE). 但NPDE引入的全局判別信息具有對(duì)噪聲敏感， 易受樣本分布影響的缺點(diǎn).

基于NPE和NPDE算法的不足， 提出判別局部近鄰保持嵌入算法(DLNPE). 該算法對(duì)局部結(jié)構(gòu)中鄰域樣本的類別進(jìn)行區(qū)分， 引入有效判別信息. 在嵌入低維空間后， 類內(nèi)樣本保持固有的近鄰幾何結(jié)構(gòu)， 且類間樣本彼此分離. 為驗(yàn)證所提DLNPE算法的有效性， 將其應(yīng)用于6個(gè)真實(shí)數(shù)據(jù)上， 并與NPDE、 DLPP、 NPE和LPP這4種方法進(jìn)行對(duì)比.

1 近鄰保持嵌入算法及相關(guān)研究

1.1 近鄰保持嵌入(NPE)[6]

假設(shè)X=(x1,x2, …,xn)是由n個(gè)樣本所組成的數(shù)據(jù)集， 每個(gè)樣本維數(shù)為m. 找到一個(gè)投影變換矩陣A， 將數(shù)據(jù)集映射到一個(gè)低維空間Rd(d

近鄰保持嵌入算法(NPE)是一種無監(jiān)督降維方法， 能夠保持近鄰樣本點(diǎn)間的局部結(jié)構(gòu). 它對(duì)每個(gè)數(shù)據(jù)點(diǎn)用其k近鄰進(jìn)行線性重構(gòu). 用yij(j=1, 2, …,k)表示yi的k近鄰點(diǎn)，wij表示yi和yj之間的權(quán)值， 令權(quán)重矩陣為W， 那么NPE的目標(biāo)函數(shù)為：

其中:M=(I-W)T(I-W)， 變換矩陣A可以通過求解以下的最小化問題得到:

1.2 保持近鄰判別嵌入(NPDE)

保持近鄰判別嵌入算法(NPDE)[7]充分利用判別信息， 既保持同類樣本的領(lǐng)域結(jié)構(gòu)， 又使得不同類樣本的平均嵌入向量相互分離. 該算法的目標(biāo)函數(shù)定義如下：

其中:M′=diag(M1,M2, …,Mc)，Mc=(I-Wc)T(I-Wc)；F=[f1,f2, …,fc]，fi是第i類樣本均值；G=(I-B)T(I-B)，I是單位矩陣.

2 判別局部近鄰保持嵌入(DLNPE)

NPE是一種無監(jiān)督降維方法， 沒有考慮樣本的類別信息. 受到半監(jiān)督局部線性判別算法(SELF)[8]啟發(fā)， 本文在NPE基礎(chǔ)上， 引入新定義下的類間散布矩陣S(rlb)和類內(nèi)散布矩陣S(rlw)作為判別信息， 其定義如下：

式(9)、 (10)中sij為樣本xi和xj的相似度，Nci為第ci類樣本總數(shù).ci=cj表示樣本xi和xj屬于同一類，ci≠cj表示樣本xi和xj屬于不同類. 在計(jì)算S(lb)時(shí)， 若ci=cj則賦予負(fù)數(shù)權(quán)重； 若ci≠cj則賦予權(quán)重為1/n. 在計(jì)算S(lw)時(shí)， 若ci=cj則賦予較大權(quán)重； 若ci≠cj則賦予較小權(quán)重0. 這體現(xiàn)了類間最大化， 類內(nèi)最小化的思想. 本文引入S(rlb)-S(rlw)作為判別信息， 將引入判別信息后的算法稱為判別局部近鄰保持嵌入算法(DLNPE)， 其目標(biāo)函數(shù)為：

對(duì)上式分子進(jìn)行化簡(jiǎn)：

則DLNPE的目標(biāo)函數(shù)可以簡(jiǎn)化為：

那么， 求解變換矩陣的最小化問題為：

使目標(biāo)函數(shù)最小化的變換矩陣可以通過求解廣義特征向量得到：

若α1,α2, …,αd為上式前d個(gè)廣義特征值λ1≤λ2≤ … ≤λd所對(duì)應(yīng)的特征向量， 那么最優(yōu)投影矩陣A可表示為A=(α1,α2…αd).

下面給出DLNPE算法的具體描述：

算法名稱： 判別局部近鄰保持嵌入算法(discriminantlocalneighborhoodpreservingembedding，DLNPE)

輸入： 數(shù)據(jù)集X， 權(quán)重參數(shù)β， 近鄰參數(shù)k， 子空間維數(shù)d.

輸出： 降維后的數(shù)據(jù)mappedX.

Step 1： 進(jìn)行PCA投影， 避免高維小樣本問題， 為了方便起見， 將投影后的數(shù)據(jù)集仍記為X(若數(shù)據(jù)集為非高維小樣本數(shù)據(jù)可省略Step 1)；

Step 2： 與NPE算法類似， 計(jì)算近鄰重建權(quán)重矩陣W；

Step 3： 計(jì)算XMXT的值， 并記為Q；

Step 4： 計(jì)算新定義下的類內(nèi)散布矩陣S(rlw)和類間散布矩陣S(rlb)， 并計(jì)算S(rlb)-S(rlw)的值， 記為P；

Step 5： 解廣義特征值問題Qα=λPα， 求出前d個(gè)廣義特征值λ1≤λ2≤…≤λd所對(duì)應(yīng)的特征向量α1,α2, …,αd， 將變換矩陣記為ADLNPE=(α1,α2, …,αd)；

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)數(shù)據(jù)

所有實(shí)驗(yàn)均在CPU為Pentium(R)Dual-CoreE5300， 內(nèi)存為2GB環(huán)境下， 用MATLAB2010b實(shí)現(xiàn). 實(shí)驗(yàn)數(shù)據(jù)來自于warpPIE10P、colon、lymphoma、Coffee、BreastCancerWisconsin(Diagnostic)(wdbc)和Ringnorm(ring). 其中，warpPIE10P是圖像數(shù)據(jù)集， 包含10個(gè)人在不同光線下各種表情的圖像；colon和lymphoma是基因數(shù)據(jù)，Coffee是時(shí)間序列數(shù)據(jù). 數(shù)據(jù)描述詳見表1.

表1 實(shí)驗(yàn)數(shù)據(jù)簡(jiǎn)介

3.2 實(shí)驗(yàn)結(jié)果與分析

為驗(yàn)證DLNPE算法的有效性， 將其與NPE[6]、 NPDE[7]、 LPP[9]、 DLPP[10]4種方法進(jìn)行對(duì)比. 其中NPE、 LPP是無監(jiān)督降維方法， NPDE、 DLPP是有監(jiān)督降維方法. 用這5種方法對(duì)上述6個(gè)數(shù)據(jù)進(jìn)行降維， 在相同維度下用SVM方法進(jìn)行分類. 最后以各維度上分類精度高低作為評(píng)價(jià)降維算法有效性的標(biāo)準(zhǔn).

實(shí)驗(yàn)對(duì)比的5種算法涉及近鄰參數(shù)k， 均設(shè)置在[1, 10]之間. SVM的核函數(shù)采用多項(xiàng)式核函數(shù)， 核函數(shù)參數(shù)設(shè)置為1. 實(shí)驗(yàn)結(jié)果如圖1所示：

由圖1可知， 有監(jiān)督降維方法DLNPE、 NPDE、 DLPP總體上優(yōu)于無監(jiān)督降維方法LPP、 NPE； 在有監(jiān)督方法中， 用DLNPE算法降維后的分類精度和穩(wěn)定性上都優(yōu)于NPDE和DLPP算法. 以圖1(f)ring數(shù)據(jù)為例， DLNPE+SVM、 NPDE+SVM、 DLPP+SVM分類精度和LPP+SVM、 NPE+SVM相比都較優(yōu)； 在有監(jiān)督方法中， DLNPE+SVM算法的分類精度基本上處于NPDE+SVM、 DLPP+SVM算法上方并最終趨于穩(wěn)定狀態(tài). 而對(duì)于圖1(b)colon數(shù)據(jù)， 當(dāng)維數(shù)降至22時(shí)， 部分特征之間的相關(guān)系數(shù)最高可達(dá)0.936 4. 特征之間冗余性很大， 造成DLNPE+SVM算法精度突然下降. 但這不影響算法的整體效果. 通過以上實(shí)驗(yàn)充分說明DLNPE算法是有效可行的.

圖1 六個(gè)數(shù)據(jù)上的實(shí)驗(yàn)結(jié)果

4 結(jié)論

為了提高NPE的性能， 本文通過引入有效的判別信息， 提出判別局部近鄰保持嵌入算法(DLNPE). 該算法能夠反映局部結(jié)構(gòu)中鄰域樣本的不同類差異. 通過優(yōu)化目標(biāo)函數(shù)， 使得嵌入低維空間的數(shù)據(jù)類內(nèi)保持固有的鄰域結(jié)構(gòu)， 且不同類別間的距離最大化， 從而獲得具有鑒別力的投影矩陣. 實(shí)驗(yàn)結(jié)果也表明DLNPE算法與現(xiàn)有四種降維方法比較， 可以獲得較高的分類精度.

[1] Jolliffe I. Principal component analysis[M]. [s.l.]： John Wiley & Sons, 2005.

[2] 邊肇祺, 張學(xué)工. 模式識(shí)別[M]. 2版. 北京： 清華大學(xué)出版社， 2000.

[3] Tenenbaum J B, De S V, Langford J C. A global geometric framework for nonlinear dimensionality reduction[J]. Science, 2000, 290(5 500): 2 319-2 323.

[4] Belkin M, Niyogi P. Laplacian eigenmaps for dimensionality reduction and data representation[J]. Neural Computation, 2003, 15(6): 1 373-1 396.

[5] Roweis S T, Saul L K. Nonlinear dimensionality reduction by locally linear embedding[J]. Science, 2000, 290(5 500): 2 323-2 326.

[6] He Xiaofei, Cai Deng, Yan Shuicheng,etal. Neighborhood preserving embedding[C]//Proceeding of the Tenth IEEE International Conference on Computer Vision. Washington D C: IEEE, 2005: 1 208-1 213.

[7] 王國(guó)強(qiáng), 歐宗瑛, 劉典婷, 等. 基于保持近鄰判別嵌入的人臉識(shí)別[J]. 大連理工大學(xué)學(xué)報(bào), 2008, 48(3): 378-382.

[8] Sugiyama M, Idé T, Nakajima S,etal. Semi-supervised local fisher discriminant analysis for dimensionality reduction[J]. Machine Learning, 2010, 78 (1/2): 35-61.

[9] He Xiaofei, Niyogi P. Locality preserving projections[C]//Advance in Neural Information Processing Systems. Vancouver: MIT Press, 2003: 153-162.

[10] Yu Weiwei, Teng Xiaolong, Liu Chongqing. Face recognition using discriminant locality preserving projections[J]. Image and Vision Computing, 2006, 24(3): 239-248.

(責(zé)任編輯： 林曉)

Dimensionality reduction of neighborhood preserving embedding based on discrimination information

ZHANG Haiwu, CHEN Xiaoyun

(College of Mathematics and Computer Science, Fuzhou University, Fuzhou, Fujian 350116, China)

Because traditional neighborhood preserving embedding (NPE) focuses on keeping a sample of local structure without taking category information into account, the discriminant local neighborhood preserving embedding algorithm is proposed. The algorithm use the local structure of samples points to construct the new definition within-class and between-class scatter matrix, which are introduced into the objective function as the discrimination information. The experimental results on six real data show that the algorithm is effective.

dimensionality reduction; neighborhood preserving embedding; discrimination information; local structure

10.7631/issn.1000-2243.2015.04.0466

1000-2243(2015)04-0466-05

2014-03-13

陳曉云(1970-)， 教授， 主要從事數(shù)據(jù)挖掘、 模式識(shí)別、 機(jī)器學(xué)習(xí)等方面研究， c_xiaoyun@21cn.com

福建省新世紀(jì)優(yōu)秀人才基金資助項(xiàng)目(XSJRC2007-11)

TP311

A