自適應稀疏表示引導的無監(jiān)督降維

岳 琴，魏 巍，2，馮 凱，2，崔軍彪

1) 山西大學計算機與信息技術學院，山西太原030006；2)山西大學計算智能與中文信息處理教育部重點實驗室，山西太原030006

隨著數(shù)據(jù)維數(shù)的增加，傳統(tǒng)機器學習算法的性能及可解釋性都受到了嚴重影響．降維是緩解“維度災難”[1]的一種有效手段．根據(jù)降維過程中所使用監(jiān)督信息的多少，降維可被分為有監(jiān)督降維[2-4]、半監(jiān)督降維[5-7]和無監(jiān)督降維．無監(jiān)督降維指不利用任何監(jiān)督信息的降維，它通常以保持某種數(shù)據(jù)分布信息(如幾何信息和統(tǒng)計信息等)為準則[8]．然而，在高維場景中，如何有效挖掘數(shù)據(jù)分布信息是非常困難的．因此，相比其他兩種降維方法，無監(jiān)督降維更具挑戰(zhàn)性．根據(jù)保持的數(shù)據(jù)分布信息的不同，無監(jiān)督降維又可分為保持數(shù)據(jù)分布的局部信息降維和保持數(shù)據(jù)分布的全局信息降維兩種．經(jīng)典的保持數(shù)據(jù)分布局部信息的無監(jiān)督降維方法有局部線性嵌入(locally linear embedding, LLE)[9]和局部保持投影(locality preserving projection, LPP)[10]等．LLE保持的是局部線性重構關系，在原始高維空間學習近鄰線性重構系數(shù)，在低維空間中保持學到的線性重構關系．LPP保持的是樣本間的局部相似性．由于LPP的相似性圖是預先定義的，所以降維的結果很大程度上依賴于圖的構建，而圖構建本身是一個開放性問題，自適應圖構建[11]是解決此問題的有效方法．圖優(yōu)化局部保持投影(graph-optimized locality preserving projections, GOLPP)[12]將圖構建和降維任務統(tǒng)一到一個框架中，實現(xiàn)了圖構建和降維相互指導，使得到的圖對于具體任務是最優(yōu)的．與GOLPP不同，自適應近鄰投影聚類(projected clustering with adaptive neighbors, PCAN)[13]保持的是概率近鄰圖，若樣本對是近鄰的概率大，則該樣本對降維后的距離近．經(jīng)典的保持數(shù)據(jù)分布全局信息的無監(jiān)督降維方法有多維縮放(multiple dimensional scaling, MDS)[14]、等度量映射(isometric mapping, IOSMAP)[15]和稀疏保持投影(sparsity preserving projections, SPP)[16]等．MDS保持降維前后樣本間的歐式距離不變；IOSMAP保持降維前后樣本間的測地距離不變；SPP通過稀疏表示挖掘數(shù)據(jù)分布的全局信息，在低維空間中保持學到的全局線性重構關系．為挖掘更多數(shù)據(jù)分布信息，QI等[17]提出基于自表示和鄰接學習的維度約簡(dimensionality reduction via representation and affinity learning, DRRAL)，采用文獻[18]的模型進行鄰接矩陣的學習并指導降維．HINTON等[19]利用神經(jīng)網(wǎng)絡學習高維數(shù)據(jù)的低維表示(自編碼器)提出基于神經(jīng)網(wǎng)絡的維度約簡方法．為學到更魯棒的特征，ABAVISANI等[20]提出基于自動編碼模型的稀疏深度編碼．

在實際應用中，高維數(shù)據(jù)的潛在分布往往是復雜的，單獨采用全局或局部的方法很難完全捕獲數(shù)據(jù)的分布信息[21]．為同時挖掘數(shù)據(jù)分布的全局信息和局部信息，本研究提出一種自適應挖掘數(shù)據(jù)分布的局部和全局信息的無監(jiān)督降維(adaptive sparse representation guided unsupervised dimensionality reduction, ASR_UDR)方法，用稀疏表示挖掘數(shù)據(jù)的類簇結構，再將稀疏表示的系數(shù)約束為凸組合，可直觀地刻畫樣本間的概率近鄰關系，并在投影后的低維數(shù)據(jù)中保持該關系，最后將上述兩個過程統(tǒng)一到一個框架中，讓二者相互指導，實現(xiàn)數(shù)據(jù)分布信息的自適應挖掘與數(shù)據(jù)降維．

1 基礎知識

1.1 符號描述

給定數(shù)據(jù)集X=(xji)∈RD×n，xji為第i個樣本的第j個特征．降維后的數(shù)據(jù)集為Y=(yji)∈Rd×n，d

1.2 稀疏表示與稀疏子空間聚類

稀疏表示指用所有樣本的線性組合重構第i個樣本，在重構系數(shù)si上加l0范數(shù)正則項，要求系數(shù)是稀疏的．在線性子空間中，si中的非零元素表示與樣本xi在同一子空間中的樣本在重構該樣本時的貢獻，表達式為

(1)

式(1)的求解是一個非確定性多項式困難(nondeterministic polynomially hard, NP-hard)問題，一般用l1范數(shù)近似l0范數(shù)，則式(1)重寫為

(2)

將稀疏表示的重構系數(shù)用作鄰接矩陣系數(shù)，此時當子空間是相互獨立時，鄰接矩陣S呈稀疏塊對角結構，每一塊對應一個子空間．

1.3 局部保持投影

局部保持投影目的是挖掘高維空間中的數(shù)據(jù)鄰域信息并在低維數(shù)據(jù)空間得以保持[10]．其中，高維數(shù)據(jù)的鄰域信息是通過鄰接矩陣刻畫的．算法步驟為：

1)構建鄰接矩陣S=(sij)∈Rn×n． 若兩個樣本xi與xj相近，則節(jié)點i和節(jié)點j之間用邊相連，且不同樣本間邊的權重sij不同．具體構建方法為

(3)

其中，Nk(xi)為xi的k近鄰集合．

2)特征映射．在投影后的低維空間中若要保持高維空間中數(shù)據(jù)的鄰域信息，則目標函數(shù)為

(4)

最小化后等價為

(5)

(6)

2 稀疏表示引導的無監(jiān)督降維

2.1 模型構建

降維目的是在保持數(shù)據(jù)分布信息的前提下減少數(shù)據(jù)維度：一方面，將稀疏子空間聚類思想用于維度約簡，用子空間學習挖掘到的數(shù)據(jù)分布的全局信息指導降維；另一方面，在降維中引入局部保持投影，并將子空間學習和降維統(tǒng)一到一個框架中，完成自適應地挖掘數(shù)據(jù)分布的全局信息和局部信息與降維相互指導的過程．目標函數(shù)為

(7)

其中，α為稀疏表示中重構誤差和稀疏正則項的平衡參數(shù)；β為用于平衡全局和局部信息的參數(shù)．目標函數(shù)中的第1項是稀疏表示的目標函數(shù)，用來挖掘數(shù)據(jù)分布的全局信息；第2項是用稀疏表示的系數(shù)矩陣構建鄰接圖，使降維后的樣本保持該圖上的平滑性，即在圖上相似的樣本降維后也相似．為避免平凡解，增加約束項PTXHXTP=I， 約束降維后的特征與特征之間線性無關．其中，I為單位矩陣；H=I-(1/n)FFT是中心化矩陣，F(xiàn)為元素全為1的n×1維矩陣．為使稀疏表示的系數(shù)矩陣能更好地反映樣本之間的相似性，采用除樣本以外的其余樣本的凸組合重構目標樣本．凸組合系數(shù)具有天然的概率意義，稀疏性能直觀地反映數(shù)據(jù)分布的局部信息．在降維過程中，若樣本對(xi,xj)是近鄰的概率大，則希望降維后的樣本對(yi,yj)近．同時，降維后的樣本也指導相似性矩陣的學習，即若(yi,yj)遠，則希望該樣本對的相似性?。裕罱K的優(yōu)化模型為

(8)

2.2 模型的求解

采用交替優(yōu)化方法求解優(yōu)化問題(8)．首先，固定S，優(yōu)化P， 則優(yōu)化問題可寫為

s.t.PTXHXTP=I

(9)

式(9)可等價為

s.t.PTXHXTP=I

(10)

上述優(yōu)化問題對應一個廣義特征值分解問題，

XLXTp=λXHXTp

(11)

其中，p為特征值λ對應的特征向量．

式(11)的最優(yōu)解P*為由d個最小的廣義特征值對應的特征向量組成的矩陣，具體的構造過程可參考文獻[10]．

其次，固定P， 優(yōu)化S， 則式(8)可寫為

(12)

其中，yi=PTxi是第i個樣本的低維表示．

(13)

對目標函數(shù)進行化簡，可得

(14)

其中，F(xiàn)為元素全為1的n×1維矩陣.

由式(14)可見，S的每列都相互獨立，可單獨進行優(yōu)化．對于S的第i列si， 去掉與目標函數(shù)中與si無關的常量后可得

(15)

優(yōu)化問題(15)是一個凸的二次規(guī)劃問題，可采用求解二次規(guī)劃的算法[22]進行求解．

2.3 算法的描述

自適應稀疏表示引導的無監(jiān)督降維算法描述見圖1，算法收斂準則設為連續(xù)兩次迭代目標函數(shù)值的差的絕對值小于1×10-5．

輸入:數(shù)據(jù)矩陣X∈RD×n, 超參數(shù)α和β, 降維后數(shù)據(jù)的維數(shù)d輸出:數(shù)據(jù)的低維表示Y∈Rd×n1)初始化 S=0;2)迭代優(yōu)化各變量while 不滿足收斂條件 求解式(10)對應的廣義特征值問題更新變量 P; 求解式(15)對應的凸二次規(guī)劃問題更新矩陣 S的每一列;end while3)計算: Y=PTX結束

圖1 自適應稀疏表示引導的無監(jiān)督降維算法描述

Fig.1 The algorithm description of adaptive sparse representation guided unsupervised dimensionality reduction

3 實 驗

3.1 數(shù)據(jù)集

實驗共使用5個數(shù)據(jù)集，基本信息見表1．其中，WarpAR10P為人臉圖像數(shù)據(jù)集；USPS為手寫字體數(shù)據(jù)集；MultiB、DLBCLA和DLBCLB為3個基因數(shù)據(jù)集．

表1 實驗所用數(shù)據(jù)集基本信息Table 1 The information of data sets used in this experiment 個

3.2 實驗設置

對比算法包括原始的高維數(shù)據(jù)(baseline)和5種經(jīng)典的無監(jiān)督降維算法GOLPP[12]、PCAN[13]、DRRAL[17]、SPP[16]和全局和局部保持投影(global and local structure preserving projection, GLSPP)[23]．其中，GOLPP和PCAN是只考慮數(shù)據(jù)分布局部信息的無監(jiān)督降維算法；DRRAL和SPP是只考慮數(shù)據(jù)分布全局信息的無監(jiān)督降維算法；GLSPP算法同時考慮了數(shù)據(jù)的全局信息和局部信息．在實驗中，各種算法的參數(shù)設置如下：

GOLPP算法是對LPP[10]算法的改進．在LPP算法中，樣本之間的相似性矩陣是預定義的，缺乏自適應能力，為此，GOLPP算法將相似性矩陣的學習與降維過程統(tǒng)一在一個框架中，相互指導．該方法需初始化鄰接矩陣S，本實驗采用文獻[12]的初始化方式：

(16)

PCAN算法的主要思想是利用歐式距離指導概率近鄰的學習，從而指導降維．在實驗中，類簇的個數(shù)設置為數(shù)據(jù)集真實的類別個數(shù)，另外兩個參數(shù)采用文獻[13]中的設置．

DRRAL是基于自表示的無監(jiān)督降維方法，算法分兩個階段：① 用文獻[18]算法得到相似性矩陣，超參數(shù)λ1=λ2=λ3=λ∈{0.1, 0.2, …, 1.0}， 簇的個數(shù)設為數(shù)據(jù)集的真實類別數(shù)；② 將得到的相似性矩陣用于指導降維．

SPP算法是用稀疏表示學習重構系數(shù)關系，在低維數(shù)據(jù)中保持該重構系數(shù)關系．本實驗采用文獻[16]中的優(yōu)化問題(16)進行稀疏重構．

GLSPP算法利用k-means聚類發(fā)現(xiàn)數(shù)據(jù)的標簽信息，從全局角度和局部兩個角度保持該信息．其中，用于平衡全局和局部信息的超參數(shù)β∈{0.01, 0.1, 1, 10, 100}. 本研究方法超參數(shù)集合α∈{0.001, 0.005, 0.010, 0.050, 0.100}，β∈{0.001, 0.01, 0.1, 1, 10, 100, 1 000}．

除baseline算法外，其他算法降維后的維數(shù)d∈{50, 60, …, 120}. 首先，在所得數(shù)據(jù)的低維表示數(shù)據(jù)集上執(zhí)行k-means聚類，類的個數(shù)為真實類別數(shù)，類中心采用隨機方法進行初始化.然后，計算k-means聚類得到的類標簽向量與真實類標簽向量的聚類精度(accuracy, ACC)和歸一化互信息(normalized mutual information, NMI).為降低k-means聚類的隨機性，此過程重復50次，再求平均值，以此來衡量降維結果的質量．

3.3 結果及分析

表2和表3分別展示了7種方法在5個數(shù)據(jù)集上所有維度d∈{50, 60, …, 120}中的最優(yōu)ACC值和NMI值，以及對于對應的維度.

%

1)括號內數(shù)值為對應的維數(shù)

%

1)括號內數(shù)值為對應的維數(shù)

由表2可見，與其他方法相比，本研究方法在5個數(shù)據(jù)集上的ACC值都有提升，升幅3.02%～8.20%．由表3可見，本研究方法的NMI值比其他方法在5個數(shù)據(jù)集上都有提升，升幅為0.01%～6.20%．這是由于本研究方法利用稀疏表示挖掘數(shù)據(jù)分布的全局信息，約束降維后的樣本保持該信息，同時約束系數(shù)矩陣是凸組合，進而有概率近鄰的含義，以此挖掘數(shù)據(jù)分布的局部信息，而且將數(shù)據(jù)分布的挖掘和降維統(tǒng)一到一個框架中，相互指導，自適應得到數(shù)據(jù)的低維表示．

3.4 參數(shù)敏感性分析

圖2和圖3分別展示了5個數(shù)據(jù)集在不同α和β值下，采用ASR_UDR算法得到的聚類ACC和NMI值實驗結果．由圖2可見，ASR_UDR算法的ACC指標對參數(shù)α和β不是很敏感，且當α相同時，算法的ACC指標對β不敏感；當β相同時，算法對α較為敏感．由圖3可見，相比聚類ACC指標，ASR_UDR算法的NMI指標對α和β較敏感，且當α相同時，算法的NMI指標對β不敏感；當β相同時，算法對α較為敏感．在少量參數(shù)組合下，算法可達到較高性能．

圖2 ASR_UDR方法在5個數(shù)據(jù)集上不同參數(shù)下的聚類ACCFig.2 (Color online) Clustering ACC on five data sets with different parameters for ASR_UDR

圖3 ASR_UDR方法在5個數(shù)據(jù)集上不同參數(shù)下的聚類NMIFig.3 (Color online) Clustering NMI on five data sets with different parameters for ASR_UDR

結 語

挖掘并保持數(shù)據(jù)的分布信息是無監(jiān)督降維的關鍵問題．本研究用稀疏表示挖掘高維數(shù)據(jù)的子空間結構用于指導無監(jiān)督降維，同時用無監(jiān)督降維的結構進一步指導稀疏子空間的學習，二者相互提升從而自適應地挖掘數(shù)據(jù)分布的全局和局部信息并完成降維．在大量真實高維數(shù)據(jù)集上的實驗結果表明，本研究方法可在顯著降低數(shù)據(jù)維數(shù)的同時，有效提升后續(xù)學習方法的性能．