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

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

隨著數(shù)據(jù)維數(shù)的增加，傳統(tǒng)機器學(xué)習(xí)算法的性能及可解釋性都受到了嚴重影響．降維是緩解“維度災(zāi)難”[1]的一種有效手段．根據(jù)降維過程中所使用監(jiān)督信息的多少，降維可被分為有監(jiān)督降維[2-4]、半監(jiān)督降維[5-7]和無監(jiān)督降維．無監(jiān)督降維指不利用任何監(jiān)督信息的降維，它通常以保持某種數(shù)據(jù)分布信息(如幾何信息和統(tǒng)計信息等)為準(zhǔn)則[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保持的是局部線性重構(gòu)關(guān)系，在原始高維空間學(xué)習(xí)近鄰線性重構(gòu)系數(shù)，在低維空間中保持學(xué)到的線性重構(gòu)關(guān)系．LPP保持的是樣本間的局部相似性．由于LPP的相似性圖是預(yù)先定義的，所以降維的結(jié)果很大程度上依賴于圖的構(gòu)建，而圖構(gòu)建本身是一個開放性問題，自適應(yīng)圖構(gòu)建[11]是解決此問題的有效方法．圖優(yōu)化局部保持投影(graph-optimized locality preserving projections, GOLPP)[12]將圖構(gòu)建和降維任務(wù)統(tǒng)一到一個框架中，實現(xiàn)了圖構(gòu)建和降維相互指導(dǎo)，使得到的圖對于具體任務(wù)是最優(yōu)的．與GOLPP不同，自適應(yīng)近鄰?fù)队熬垲?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ù)分布的全局信息，在低維空間中保持學(xué)到的全局線性重構(gòu)關(guān)系．為挖掘更多數(shù)據(jù)分布信息，QI等[17]提出基于自表示和鄰接學(xué)習(xí)的維度約簡(dimensionality reduction via representation and affinity learning, DRRAL)，采用文獻[18]的模型進行鄰接矩陣的學(xué)習(xí)并指導(dǎo)降維．HINTON等[19]利用神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)高維數(shù)據(jù)的低維表示(自編碼器)提出基于神經(jīng)網(wǎng)絡(luò)的維度約簡方法．為學(xué)到更魯棒的特征，ABAVISANI等[20]提出基于自動編碼模型的稀疏深度編碼．

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

1 基礎(chǔ)知識

1.1 符號描述

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

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

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

(1)

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

(2)

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

1.3 局部保持投影

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

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

(3)

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

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

(4)

最小化后等價為

(5)

(6)

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

2.1 模型構(gòu)建

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

(7)

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

XLXTp=λXHXTp

(11)

其中，p為特征值λ對應(yīng)的特征向量．

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

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

(12)

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

(13)

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

(14)

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

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

(15)

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

2.3 算法的描述

自適應(yīng)稀疏表示引導(dǎo)的無監(jiān)督降維算法描述見圖1，算法收斂準(zhǔn)則設(shè)為連續(xù)兩次迭代目標(biāo)函數(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)對應(yīng)的廣義特征值問題更新變量 P; 求解式(15)對應(yīng)的凸二次規(guī)劃問題更新矩陣 S的每一列;end while3)計算: Y=PTX結(jié)束

圖1 自適應(yīng)稀疏表示引導(dǎo)的無監(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è)置

對比算法包括原始的高維數(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ù)設(shè)置如下：

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

(16)

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

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

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

GLSPP算法利用k-means聚類發(fā)現(xiàn)數(shù)據(jù)的標(biāo)簽信息，從全局角度和局部兩個角度保持該信息．其中，用于平衡全局和局部信息的超參數(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聚類得到的類標(biāo)簽向量與真實類標(biāo)簽向量的聚類精度(accuracy, ACC)和歸一化互信息(normalized mutual information, NMI).為降低k-means聚類的隨機性，此過程重復(fù)50次，再求平均值，以此來衡量降維結(jié)果的質(zhì)量．

3.3 結(jié)果及分析

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

%

1)括號內(nèi)數(shù)值為對應(yīng)的維數(shù)

%

1)括號內(nèi)數(shù)值為對應(yīng)的維數(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)一到一個框架中，相互指導(dǎo)，自適應(yīng)得到數(shù)據(jù)的低維表示．

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

圖2和圖3分別展示了5個數(shù)據(jù)集在不同α和β值下，采用ASR_UDR算法得到的聚類ACC和NMI值實驗結(jié)果．由圖2可見，ASR_UDR算法的ACC指標(biāo)對參數(shù)α和β不是很敏感，且當(dāng)α相同時，算法的ACC指標(biāo)對β不敏感；當(dāng)β相同時，算法對α較為敏感．由圖3可見，相比聚類ACC指標(biāo)，ASR_UDR算法的NMI指標(biāo)對α和β較敏感，且當(dāng)α相同時，算法的NMI指標(biāo)對β不敏感；當(dāng)β相同時，算法對α較為敏感．在少量參數(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

結(jié) 語

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