基于兩階段流形學(xué)習(xí)的半監(jiān)督維數(shù)約簡算法

徐金成，李曉東，劉 輝

(1.廣東司法警官職業(yè)學(xué)院 信息管理系，廣東 廣州 510520； 2.國家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心廣東分中心， 廣東 廣州 510665)

0 引 言

維數(shù)約減算法的目的是在保持?jǐn)?shù)據(jù)的本質(zhì)信息的前提下減少數(shù)據(jù)的復(fù)雜度。目前有大量半監(jiān)督維數(shù)約簡算法提及：半監(jiān)督維數(shù)約減算法能夠同時(shí)利用有標(biāo)簽和無標(biāo)簽訓(xùn)練樣本進(jìn)行綜合考慮。

一些研究者定義新的優(yōu)化目標(biāo)。Jincheng Xu[1]提出了一種對(duì)稱局部保持的半監(jiān)督維數(shù)約減(SLPSDR)算法，該方法主要是針對(duì)自然界較多圖像具有對(duì)稱的特點(diǎn)以及數(shù)據(jù)分布大多呈一定的流行結(jié)構(gòu)情況。Yi Yang等[4]提出一種排序?qū)W習(xí)的半監(jiān)督維數(shù)約減算法，使用局部預(yù)測誤差表示樣本之間的流形結(jié)構(gòu)，該方法假設(shè)的流形結(jié)構(gòu)與多媒體數(shù)據(jù)有較好的一致性，但是該方法沒有處理全局流形結(jié)構(gòu)。Jia Wei等[3]提出一種結(jié)合局部和全局拓?fù)浣Y(jié)構(gòu)的半監(jiān)督維數(shù)約簡算法，該方法通過最小化類內(nèi)距離和類間距離來突出分類結(jié)構(gòu)，局部拓?fù)浣Y(jié)構(gòu)通過最小化局部重構(gòu)誤差實(shí)現(xiàn)，全局拓?fù)浣Y(jié)構(gòu)通過最大化不在鄰域的樣本之間的距離實(shí)現(xiàn)。

一些研究者定義新的流形結(jié)構(gòu)。Tingjin Luo等[8]提出一種判別正交彈性投影保持方法(DOEPP)，該方法使用EPP中的方法構(gòu)建局部圖和全局圖，使用最大間距準(zhǔn)則中的方法提取判別信息和正交信息。Puhua Chen等[5]提出一種基于稀疏圖的半監(jiān)督維數(shù)約簡方法，該方法首先利用鄰域?qū)o標(biāo)簽樣本賦予偽標(biāo)簽，然后根據(jù)標(biāo)簽建立類內(nèi)和類間稀疏表示圖，最后使用特征分解方法得到映射矩陣。蘭遠(yuǎn)東等[6]通過最小化樣本到其所屬類別的中心點(diǎn)之間的距離，得出其鄰域的拓?fù)浣Y(jié)構(gòu)；再通過最大化不同類別邊緣間的距離，在投影子空間中就可以增強(qiáng)類別間的分離度。王憲保等[7]提出了一種半監(jiān)督等距映射算法，該方法使用訓(xùn)練樣本的標(biāo)簽樣本構(gòu)建K連通圖，得到近似樣本間測地線距離，并把它作為矢量特征代替原始數(shù)據(jù)點(diǎn)；然后通過測地線距離計(jì)算核矩陣，用半監(jiān)督正則化方法代替多維尺度分析算法處理矢量特征；最后利用正則化回歸模型構(gòu)建目標(biāo)函數(shù)，得到低維表示的顯式映射。Xianglei Xing等[9]通過融合多種局部集合信息來獲得可信度更高的流形結(jié)構(gòu)。ShengHuang等[10]提出一種全局局部保持的維數(shù)約簡算法，該方法使用薄板樣條和核徑向基核擬合數(shù)據(jù)的流形結(jié)構(gòu)，能夠捕獲到步態(tài)中動(dòng)態(tài)和靜態(tài)特征。

上述方法在建立數(shù)據(jù)流形結(jié)構(gòu)時(shí)，直接使用高維數(shù)據(jù)。但是高維數(shù)據(jù)在樣本空間非常稀疏，流形結(jié)構(gòu)可能不明顯，并且流形結(jié)構(gòu)也容易受到噪聲的影響，導(dǎo)致保持該流形結(jié)構(gòu)對(duì)分類的意義減小。為了克服上述問題，本文提出先利用原始數(shù)據(jù)建立數(shù)據(jù)的流形結(jié)構(gòu)，并在該流形結(jié)構(gòu)的基礎(chǔ)上，將訓(xùn)練數(shù)據(jù)映射到低維空間。然后在低維空間中，建立新的數(shù)據(jù)流形結(jié)構(gòu)，并在該流形結(jié)構(gòu)的基礎(chǔ)上，得到最終的映射矩陣。顯然，在低維空間建立流形結(jié)構(gòu)有3個(gè)好處：①低維空間由根據(jù)整個(gè)訓(xùn)練數(shù)據(jù)學(xué)習(xí)到的映射矩陣獲得，能夠過濾掉噪聲的影響；②低維空間獲得時(shí)，還考慮了有標(biāo)簽訓(xùn)練數(shù)據(jù)，建立的流形結(jié)構(gòu)考慮了類別結(jié)構(gòu)；③在低維空間中數(shù)據(jù)維度更低，流形結(jié)構(gòu)更明顯。

1 算法基礎(chǔ)

TSMSDR算法是在線性判別分析和局部嵌入的基礎(chǔ)上研究得到，所以本節(jié)對(duì)這兩種算法進(jìn)行簡單介紹。

1.1 線性判別分析(LDA)

(1)計(jì)算樣本的類內(nèi)距離Sw和類間距離Sb

(1)

(2)

其中，C為類的個(gè)數(shù)，ui為第i類樣本的均值，ni為第i類樣本的個(gè)數(shù)。

(2)計(jì)算Sw=λSb的特征值，并將特征值從大到小排序，選取前k個(gè)特征值對(duì)應(yīng)的特征向量w1,w2,…,wk構(gòu)成m×k的映射矩陣W。

(3)可使用Y=WTX將數(shù)據(jù)從高維空間映射到低維空間。

1.2 局部與全局保持的半監(jiān)督維數(shù)約減(LGSSDR)

(3)

(4)

Sw定義如下

(5)

Sb定義如下

(6)

Sf定義如下

(7)

1.3 判別正交彈性投影保持方法(DOEPP)

(8)

(9)

(10)

2 兩階段流形學(xué)習(xí)半監(jiān)督維數(shù)約簡算法(TSMSDR)

本節(jié)將給出本文提出的對(duì)稱局部保持半監(jiān)督維數(shù)約簡算法，首先給出視覺信息處理中的對(duì)稱現(xiàn)象及其保持方法，然后給出TSMSDR的目標(biāo)函數(shù)及其優(yōu)化方法，最后給出本文提出的TSMSDR算法。

2.1 TSMSDR的目標(biāo)函數(shù)及其優(yōu)化

(11)

其中，Lb與Lw的定義與式(3)中的Lb與Lw相同，Lg′=Dg′-Sg′,Sg′定義如下

(12)

Lm′分成兩階段定義，第一階段Lm′的定義與式(3)中的Lm定義相同。第二階段Lm′的定義如下

Lm′=(I-A′)T(I-A′)

(13)

其中，A′使用下式優(yōu)化得到

(14)

可以看到優(yōu)化式(11)是一個(gè)廣義瑞利商的問題[3]，如果Lw+aLm′非奇異，那么式(11)的優(yōu)化可通過求解下式的特征值和特征向量完成

X(Lb+aLg′)XTw=λ(Lw+aLm′)w

(15)

將特征值從大到小排序，選取前k個(gè)特征值對(duì)應(yīng)的特征向量w1,w2,…,wK構(gòu)成m×K的映射矩陣W。

2.2 TSMSDR算法

根據(jù)前面一節(jié)的描述，TSMSDR可總結(jié)成如下算法：

算法TSMSDR:

輸出：映射矩陣W

(1)在輸入數(shù)據(jù)的基礎(chǔ)上。根據(jù)式(5)和式(6)計(jì)算Lb和Lw。根據(jù)式(12)計(jì)算Lg′。根據(jù)式(13)計(jì)算第一階段的Lm′。

(5)使用Lb,Lw,Lg′和第二階段的Lm′，根據(jù)式(11)計(jì)算第二階段的映射矩陣W。

2.3 TSMSDR算法的理論依據(jù)

本小節(jié)依次分析式(11)中各個(gè)組成部分的原理與作用。

Lb,Lw的定義與式(3)中的Lb,Lw一樣。其中最大化WTXLbXTW，可以最大化低維空間中類間樣本之間的距離；最小化WTXLbXTW，可以最小化低維空間中同類樣本之間的距離。達(dá)到使分類結(jié)構(gòu)更突出的目的。

Lg′的定義根據(jù)式(10)改進(jìn)而來。該式的功能與式(3)中Lf的功能相似，能夠保持?jǐn)?shù)據(jù)的全局流形結(jié)構(gòu)。但是式(3)中Lf有一定的缺點(diǎn)。首先式(7)在定義Lf時(shí)樣本對(duì)之間的權(quán)重相同，導(dǎo)致即使兩個(gè)樣本之間的距離非常大時(shí)，依舊有可能最大化這兩個(gè)樣本之間的距離。顯然，使兩個(gè)離得非常遠(yuǎn)的樣本之間的距離離得更遠(yuǎn)意義不大。其次，式(7)在定義Lf時(shí)，只定義鄰域之外的樣本對(duì)之間的關(guān)系，這會(huì)導(dǎo)致鄰域之外和鄰域之內(nèi)的樣本之間的關(guān)系在優(yōu)化時(shí)，賦予的職能會(huì)發(fā)生突然變化，影響樣本之間流形結(jié)構(gòu)的保持。這對(duì)本文算法的影響較大，因?yàn)楸疚乃惴ㄐ枰玫谝浑A段維數(shù)約減結(jié)果建立流形結(jié)構(gòu)。

Lm′的計(jì)算公式與式(3)中Lm的計(jì)算公式相同，兩者的差別是Lm′分成兩階段計(jì)算得到。第一階段直接使用原始高維數(shù)據(jù)計(jì)算得到，第二階段使用第一階段獲得的低維數(shù)據(jù)計(jì)算得到。本文使用兩階段的方法計(jì)算Lm的原因是：在大部分實(shí)際應(yīng)用中，訓(xùn)練樣本的維度經(jīng)常遠(yuǎn)遠(yuǎn)大于訓(xùn)練樣本的個(gè)數(shù)，即容易出現(xiàn)高維度小樣本的問題。這會(huì)導(dǎo)致在原始高維數(shù)據(jù)上的流形結(jié)構(gòu)不明顯，并且容易受到噪聲的影響。

使用兩階段的流形結(jié)構(gòu)建立方法有如下好處：①本文使用式(12)定義一種漸變的全局流行結(jié)構(gòu)定義方法，可以使第一階段獲得的低維空間中的流形結(jié)構(gòu)并不會(huì)發(fā)生較大的變化，為第二階段流行結(jié)構(gòu)的建立打下了基礎(chǔ)；②另外在第一階段獲得低維空間時(shí)，還考慮了類別結(jié)構(gòu)，使第二階段建立的流形結(jié)構(gòu)中蘊(yùn)含分類信息；③第二階段建立流形結(jié)構(gòu)的輸入數(shù)據(jù)維度更低，可以使流形結(jié)構(gòu)更加明顯；④經(jīng)過一次維數(shù)約簡之后建立的流行結(jié)構(gòu)，對(duì)數(shù)據(jù)小的變化和噪聲有一定的克服能力。

3 實(shí)驗(yàn)結(jié)果

3.1 對(duì)比算法與實(shí)驗(yàn)設(shè)置

TSMSDR是一種維數(shù)約簡算法，其中維數(shù)約簡算法有無監(jiān)督、有監(jiān)督和半監(jiān)督維數(shù)約簡算法，所以本文將與以下算法比較：①無監(jiān)督維數(shù)約簡算法，包含主成分分析法(principal components analysis，PCA)；②有監(jiān)督維數(shù)約簡算法，局部投影保持(locality preserving projection，LPP)[2]，包含線性判別分析(linear discriminant analysis，LDA)[2]，判別正交彈性投影保持方法(discriminative orthogonal elastic preserving projections，DOEPP)[8]；③半監(jiān)督維數(shù)約簡算法，包含局部與全局拓?fù)浣Y(jié)構(gòu)保持半監(jiān)督維數(shù)約簡算法(local and global structures for semi-supervised dimensionality reduction，LGSSDR)[3]，邊緣判別嵌入與局部保持的半監(jiān)督維數(shù)約減算法(semisupervised marginal discriminant embedding and local preserving for dimensionality reduction，SSMDELPDR)[6]。其中LGSSDR，DOEPP，SSMDELPDR均需要設(shè)置平衡參數(shù)。其中LGSSDR需要設(shè)置全局保持和局部保持平衡參數(shù)，均設(shè)為0.1。DOEPP需要設(shè)置彈性保持能力平衡參數(shù)，設(shè)為0.1。SSMDELPDR需要設(shè)置邊緣嵌入平衡參數(shù)，設(shè)為0.1。

一般來說維數(shù)約簡的主要目的是分類，所以在維數(shù)約簡后使用分類器驗(yàn)證各個(gè)半監(jiān)督維數(shù)約簡的效果。支持向量機(jī)(support vector machine，SVM)[12]是一種非常經(jīng)典的分類器，并且能取得較為穩(wěn)定的結(jié)果。所以本文使用SVM作為分類器。另外因?yàn)榫S數(shù)約簡后，以及本文算法在人臉數(shù)據(jù)庫上驗(yàn)證，在維數(shù)約簡之后，各個(gè)類的訓(xùn)練數(shù)據(jù)均能較為密集的聚集在一起，所示SVM使用線性核函數(shù)。

驗(yàn)證半監(jiān)督維數(shù)約簡算法需要3種數(shù)據(jù)：有標(biāo)簽訓(xùn)練數(shù)據(jù)，無標(biāo)簽訓(xùn)練數(shù)據(jù)，以及測試數(shù)據(jù)。本文采用兩種實(shí)驗(yàn)設(shè)置驗(yàn)證算法。第一種從每個(gè)類別中隨機(jī)選擇3個(gè)作為有標(biāo)簽訓(xùn)練數(shù)據(jù)，再從剩下的數(shù)據(jù)中再隨機(jī)選擇3個(gè)作為無標(biāo)簽訓(xùn)練數(shù)據(jù)，其它剩下的數(shù)據(jù)為測試數(shù)據(jù)。第二種從每個(gè)類別中隨機(jī)選擇6個(gè)作為有標(biāo)簽訓(xùn)練數(shù)據(jù)，再從剩下的數(shù)據(jù)中再隨機(jī)選擇3個(gè)作為無標(biāo)簽訓(xùn)練數(shù)據(jù)，其它剩下的數(shù)據(jù)為測試數(shù)據(jù)。這里使用不同的有標(biāo)簽訓(xùn)練數(shù)據(jù)的目的是為了說明本文算法對(duì)訓(xùn)練數(shù)據(jù)的個(gè)數(shù)不敏感。為了減小樣本不一樣帶來實(shí)驗(yàn)結(jié)果的差異，以上實(shí)驗(yàn)重復(fù)執(zhí)行50次，這50次實(shí)驗(yàn)的均值作為最終實(shí)驗(yàn)結(jié)果。另外，本文對(duì)比的大部分算法均能達(dá)到較高維度的維數(shù)約簡結(jié)果，本文將維數(shù)約簡之后的維度取值為20,40,60,80,100,120,140,160等，其目的是為了說明維數(shù)約簡之后的衛(wèi)隊(duì)對(duì)對(duì)比算法的影響。實(shí)驗(yàn)結(jié)果使用準(zhǔn)確度(accuracy)評(píng)價(jià)。

3.2 分類結(jié)果

為了驗(yàn)證TSMSDR，分別使用所有參與對(duì)比算法進(jìn)行維數(shù)約簡，使用SVM作為分類器，根據(jù)分類結(jié)果評(píng)價(jià)TSMSDR。先給實(shí)驗(yàn)策略1在4個(gè)人臉數(shù)據(jù)庫上的分類結(jié)果，實(shí)驗(yàn)結(jié)果在表1中給出，在該實(shí)驗(yàn)策略中有標(biāo)簽訓(xùn)練數(shù)據(jù)從每個(gè)類別隨機(jī)選取3個(gè)，無標(biāo)簽訓(xùn)練數(shù)據(jù)從每個(gè)類別剩余的數(shù)據(jù)中隨機(jī)選取3個(gè)，其它數(shù)據(jù)為測試樣本。從表1中可以看到，TSMSDR的實(shí)驗(yàn)結(jié)果比第二好的實(shí)驗(yàn)結(jié)果在4個(gè)數(shù)據(jù)庫中分別高1.08%，1.160%，0.78%，2.33%，驗(yàn)證了TSMSDR的有效性。

表1 所有算法在4個(gè)數(shù)據(jù)庫的最大分類準(zhǔn)確度(使用3個(gè)有標(biāo)簽訓(xùn)練樣本)

另外為了對(duì)比TSMSDR與其它對(duì)比的算法投影到不同維度時(shí)的實(shí)驗(yàn)結(jié)果，將使用實(shí)驗(yàn)策略1時(shí)，所有算法在4個(gè)數(shù)據(jù)庫上投影到不同維度時(shí)的準(zhǔn)確度分別在圖1到圖4給出。從圖1到圖4可以看到，在4個(gè)數(shù)據(jù)庫上，TSMSDR能在較低維度上就能達(dá)到較高的分類準(zhǔn)確度，這在對(duì)速度要求非常高的應(yīng)用環(huán)境中，可以將數(shù)據(jù)投影到更低的維度，以加快算法的執(zhí)行速度。另外從圖1到圖4還可以看到，TSMSDR能在較多的維度上取得較為穩(wěn)定的準(zhǔn)定度，對(duì)在實(shí)際應(yīng)用中選擇合適的投影子空間的維度K更有利。

圖1 所有算法在PIE數(shù)據(jù)庫上投影到不同維度時(shí)的準(zhǔn)確度

圖3 所有算法在ORL數(shù)據(jù)庫上投影到不同維度時(shí)的準(zhǔn)確度

圖4 所有算法在AR數(shù)據(jù)庫上投影到不同維度時(shí)的準(zhǔn)確度

同樣，在表2中給出實(shí)驗(yàn)策略2在4個(gè)數(shù)據(jù)庫上的實(shí)驗(yàn)結(jié)果，在該實(shí)驗(yàn)策略中有標(biāo)簽訓(xùn)練數(shù)據(jù)從每個(gè)類別隨機(jī)選取6個(gè)，無標(biāo)簽訓(xùn)練數(shù)據(jù)從每個(gè)類別剩余的數(shù)據(jù)中隨機(jī)選取3個(gè)，其它數(shù)據(jù)為測試樣本。從表2中可以看到，TSMSDR的實(shí)驗(yàn)結(jié)果比第二好的實(shí)驗(yàn)結(jié)果在4個(gè)數(shù)據(jù)庫中分別高1.27%，1.79%，0.90%，0.70%，驗(yàn)證了TSMSDR的有效性。

表2 對(duì)比算法在4個(gè)數(shù)據(jù)庫的最大分類準(zhǔn)確度(使用6個(gè)有標(biāo)簽訓(xùn)練樣本)

同樣，為了對(duì)比TSMSDR與其它對(duì)比的算法投影到不同維度時(shí)的實(shí)驗(yàn)結(jié)果，將使用實(shí)驗(yàn)策略2時(shí)，所有算法在4個(gè)數(shù)據(jù)庫上投影到不同維度時(shí)的準(zhǔn)確度分別在圖5到圖8給出。從圖5到圖8可以看到，TSMSDR能在較低維度上就能達(dá)到較高的分類準(zhǔn)確度，能在較多的維度上取得較為穩(wěn)定的準(zhǔn)定度，以及在大部分維度上的識(shí)別均高于其它算法的識(shí)別率。

圖5 所有算法在PIE數(shù)據(jù)庫上投影到不同維度時(shí)的準(zhǔn)確度

圖6 所有算法在YaleB數(shù)據(jù)庫上投影到不同維度時(shí)的準(zhǔn)確度

圖7 所有算法在ORL數(shù)據(jù)庫上投影到不同維度時(shí)的準(zhǔn)確度

圖8 所有算法在AR數(shù)據(jù)庫上投影到不同維度時(shí)的準(zhǔn)確度

4 結(jié)束語

本文算法注意到在大部分實(shí)際應(yīng)用中，在原始高維數(shù)據(jù)上建立的流形結(jié)構(gòu)不穩(wěn)定，不突出，提出一種兩階段的流形結(jié)構(gòu)建立方法。第一階段在原始高維數(shù)據(jù)上建立流形結(jié)構(gòu)，第二階段在第一階段獲取的低維空間中建立流形結(jié)構(gòu)。另外為了使第一階段獲取的低維空間流形結(jié)構(gòu)不發(fā)生較大的變化，本來還使用一種新的方法建立樣本的全局關(guān)系。

實(shí)驗(yàn)結(jié)果表明，本文算法在人臉識(shí)別上能有較好的維數(shù)約簡的效果。但是，本文通過數(shù)據(jù)的全局結(jié)構(gòu)保持，以減小第一階段獲得的低維空間的流形結(jié)構(gòu)與原始數(shù)據(jù)的流形結(jié)構(gòu)之間的差別，從而為兩階段的流形結(jié)構(gòu)打下基礎(chǔ)。該方法可能在一定程度上使第二階段的流形結(jié)構(gòu)并不完全正確。所以在將來研究一種更好的方法使建立的流形結(jié)構(gòu)能夠克服高維小樣本的問題。