基于稀疏和近鄰保持的極限學習機降維

陳曉云 廖夢真

隨著大數據時代的到來,人們對數據的處理正面臨巨大挑戰.在大數據應用研究中,高維數據分析與研究是其主要內容之一.在現代機器學習與統計學的研究背景下,高維數據所引發的維數災難主要表現為:眾多低維空間中表現良好的算法在面對高維數據時性能急劇下降.其主要原因有:1)維數增加導致數據空間體積急劇膨脹、同等數量樣本分布非常稀疏,難以形成有效的簇;2)高維空間中存在測度“集中現象”,使樣本點間距離度量的類區分性隨著維數增加而減弱;3)樣本數據包含大量冗余信息對聚類或分類無用,甚至會降低算法的性能.基于上述原因,對降維方法進行研究是十分有必要的.

總體上說,面向聚類的降維方法均為無監督降維方法,可分為線性降維和非線性降維.當前,多數無監督線性降維方法假設觀測數據落在一個低維流形子空間中,通過尋找高維空間到低維子空間的線性投影實降維,如主成分分析(Principal component analysis,PCA)[1]、局部保持投影 (Locality preserving projections,LPP)[2]、近鄰保持嵌入(Neighborhood preserving embedding,NPE)[3]和稀疏保持投影(Sparsity preserving projections,SPP)[4].PCA是最經典的線性降維方法,以最大化投影散度為目標,但未考慮樣本間的近鄰結構關系,不適合分布于流形上的非線性數據;LPP和NPE則考慮了樣本間的近鄰結構,LPP以保持降維前后樣本間的近鄰關系不變為目標,而NPE旨在保持降維前后樣本間的局部近鄰結構;SPP的優化目標是使降維前后樣本間的稀疏表示結構得以保持.但當數據非線性分布時,上述線性降維算法就會失效.為彌補線性降維算法的不足,各種非線性擴展方法被提出,如核主成分分析(Kernel principal component analysis,KPCA)[5]和局部線性嵌入(Locally linear embedding,LLE)[6].KPCA是PCA基于核技巧的非線性推廣,用于對非線性分布數據降維;LLE以保持投影前后局部線性關系不變為目的構造目標函數.然而這些非線性降維方法無法求出顯式的映射函數,當有新樣本加入時,需要重新學習優化模型.

極限學習機(Extremelearningmachine,ELM)[7?8]最早被用于訓練單隱層前饋神經網絡,具有學習速度快、泛化能力強等特點,為有監督學習如分類和回歸提供了簡單有效的方法[9?10].2014年,Huang等基于流形正則的思想將ELM推廣到無監督學習任務,提出了一種新的非線性降維方法無監督極限學習機(Unsupervised extreme learning machine,US-ELM)[11].該方法很好地利用了ELM的逼近能力,通過非線性映射將原數據投影到低維空間中,并能夠得到顯式的非線性映射函數.但該方法利用高斯函數描述近鄰樣本間的相似度,由于高斯函數用到距離測度,難以避免地也存在高維空間中測度“集中現象”,即樣本點間高斯相似性度量的類區分性隨著維數增加而減弱,進而影響降維算法性能.此外,US-ELM 直接利用給定高斯函數計算樣本近鄰表示系數,不具有數據自適應性.

針對上述問題,本文對US-ELM進行改進,同時考慮非線性數據的局部線性表示和全局稀疏表示.其中,局部線性表示用于解決非線性流形數據的刻畫問題,以獲取數據的局部結構[12];全局稀疏表示用于描述數據的全局結構[13];并通過加權參數融合近鄰線性表示信息和稀疏表示信息.由此,我們提出基于稀疏和近鄰保持的極限學習機降維方法(SNP-ELM),使得降維前后樣本間的局部近鄰表示關系和全局稀疏性保持不變.SNP-ELM通過學習得到近鄰表示系數,較之US-ELM具有更好的數據自適應性.

1 極限學習機

極限學習機本質上是一種單隱含層前饋神經網絡,其結構如圖1所示[14].ELM 網絡的訓練主要分為兩個階段.第一個階段是ELM網絡結構構建,隱含層將輸入數據映射到n維的特征空間中,nh為隱節點個數.定義隱含層關于xi的輸出向量為h(x)=[h1(x),h2(x),···,hnh(x)]∈R1×nh。其中,x∈Rm,hi(x)是第i個隱節點的輸出,其輸出函數可以表示為:

其中,g(ai,bi,x)為非線性激勵函數,常用的函數有Sigmoid函數和Gaussian函數.本文采用Sigmoid函數,其表達式為:

式中,ai為第i個隱節點的輸入權值,bi為第i個隱節點的偏差,在ELM網絡中輸入權向量ai和隱節點偏差bi是隨機產生的.

圖1 ELM網絡結構示意圖Fig.1 ELM network structure

對于數據集X,ELM隱藏層輸出為:

若隱藏層到輸出層的權重矩陣為β=[β1,β2,···,βm],則 ELM 網絡的輸出為

第二階段是基于ELM網絡結構求解輸出權重矩陣β,通常根據ELM網絡學習任務的不同構建不同的模型來求解輸出權重矩陣β.經典的ELM模型用于解決有監督學習問題,如:分類和回歸.對于含n個樣本的訓練集S={(xi,yi)|xi∈X?Rm,yi∈Y?Rd,i=1,···,n},xi為輸入變量,yi為輸出變量,則其模型表示:

其中,目標函數的第一項為正則項,用來控制模型的復雜度;第二項為表示誤差,ei∈Rd是第i個樣本的誤差向量,C為懲罰系數.

近年來,Huang等將ELM推廣到無監督學習,提出基于流形無監督極限學習機,其模型為:

第二項為流形正則項,目的是使網絡結構輸出Y保持原輸入數據X的流形結構不變,其中,tr(·)表示矩陣的跡,L為數據X的拉普拉斯矩陣,I為單位陣,H(X)∈Rn×nh為隱含層輸出矩陣.USELM將輸入數據投影到d維空間中,當d

2 基于稀疏和近鄰保持的極限學習機降維

US-ELM算法引入流形正則化的思想,使得原始數據的流形結構經過US-ELM投影后得以保持,即若在原空間近鄰的兩個樣本在投影空間中仍然保持近鄰[2].US-ELM算法的流形結構直接用Gaussian距離刻畫,隨著數據維數的增加,該距離度量的類分類性會隨之減弱.針對這一問題,本文采用近鄰表示來自適應地獲取數據的低流形結構,同時用稀疏表示來挖掘數據的全局結構.在此基礎上提出SNP-ELM 算法,使得數據在新的投影空間中保持其在原空間的近鄰和稀疏表示結構.

2.1 近鄰表示和稀疏表示

近鄰表示[4]:在樣本集X=[x1,x2,···,xn]∈Rm×n中用xi的k近鄰進行線性表示xi,其表達式為:

其中,Nk(xi)表示xi的k近鄰,wij為近鄰表示系數,當xi∈Nk(xi)時,wij=0.

稀疏表示[5]:樣本xi可大致由該樣本集中的少量樣本線性表示.而當xi由整個樣本空間X進行線性表示時,其表示系數是稀疏的.其數學模型表示為:

其中,si∈Rn為稀疏表示系數,||s||0是s非零元素個數.由于l0范數非凸且NP難,因此用凸的l1范數代替.同時為了確保稀疏表示的平移不變性,我們引入表示系數和為1的約束,則式(8)變為:

其中,I1為所有元素均為1的n維向量.式(9)是凸的,可以利用線性規劃方法求解,如基追蹤算法(Basis pursuit,BP)[15].

2.2 基于稀疏和近鄰保持的極限學習機降維算法

SNP-ELM模型為:

第二項的目的是使得投影后的數據保持原數據的近鄰和稀疏表示結構,其中W=[w1,w2,···,wn]為近鄰表示系數矩陣,wi表示xi的近鄰表示系數,可以用模型(7)求解:S=[s1,s2,···,sn]為稀疏表示系數矩陣,si表示xi的稀疏表示系數,可以用模型(9)求解.δ∈R和η∈R是權重系數,分別反映W和S的重要性.映射函數為y=f(x)=(h(x)β)T.

令Z=δW+ηS,則式(10)可寫成:

通過簡單的代數運算,可以得到:

令ei為n維單位向量,則式(12)等價于:

式(11)可變形為:

為避免平凡解,在此引入約束(H(X)β)TH(X)β=I,則模型變為:

2.3 模型求解

為求解模型(15),利用拉格朗日乘子法,得到以下拉格朗日函數:

求解廣義特征值問題(17)得到最小的d個特征值及對應的特征向量構成最優的輸出權重矩陣β?.

當nh>n時,HT(X)H(X)的維數比較高,直接求解式(17)廣義特征值問題,需要消耗較大的內存.為解決這個問題,令β=HT(X)α,式(17)兩邊同時左乘(H(X)HT(X))?1H(X).得到:

易知模型(17)與模型(18)具有相同特征值.特征向量具有以下關系

因此解得廣義特征值問題(18)的最小的d個特征值及對應的特征向量構成矩陣α?.進而可獲得模型(17)的解矩陣β?=HT(X)α?.

基于上述分析,基于稀疏和近鄰保持的極限學習機降維算法歸納如下:

算法1.SNP-ELM算法

輸入:數據矩陣X,參數λ,δ,η.

輸出:降維后樣本矩陣Y.

1)計算k近鄰圖.

2)通過式(8)計算近鄰重構矩陣W.

3)通過式(10)計算稀疏重構矩陣S,計算Z=δW+ηS,A=I?Z?ZT+ZTZ.

4)初始化ELM 網絡,nh為隱藏層節點個數,隨機初始化輸入權重a∈Rn×nh,偏置b∈Rnh根據式(3)計算隱藏層輸出矩陣H(X)∈Rn×nh.

5)當n>nh時,利用式(17)計算得到輸出權重矩陣β;否則,利用式(18)計算得到α,再計算輸出權重矩陣β=HT(X)α.

6)計算降維后樣本矩陣Y=H(X)β

2.4 算法分析

SNP-ELM算法中計算k近鄰圖的時間復雜度是O(mnlogn);計算近鄰重構矩陣W是求解了n次式(8),其時間復雜度為O(nk3);用BP算法求解式(10)的時間復雜度為O(n3),因此計算稀疏重構矩陣S的時間復雜度為O(n4);計算廣義特征值式(18)的時間復雜度為O(n3h),求解廣義特征值式(20)的時間復雜度為O(n3).因此SNP-ELM算法的時間復雜度為O(mnlogn+n4+nk3).

3 實驗

本文提出的SNP-ELM降維算法有兩個重要目的,其一是便于高維數據的可視化分析,其二是面向聚類分析的降維可有效地提高聚類準確性,故進行數據可視化及高維基因數據降維聚類實驗,兩個實驗的實驗環境均為Win7系統,內存4GB,所有方法均用Matlab2012b編程實現.兩個實驗均采用相同的參數設置,LPP、NPE、US-ELM和SNP-ELM的近鄰數k均設為5;US-ELM和SNP-ELM的隱藏層節點個數均設為1000;US-ELM的參數λ及SNP-ELM 的參數λ統一取{10?4,10?3,···,104},SNP-ELM 的參數δ和η的搜索范圍為[?1,1],變化步長為0.2.

本文實驗所對比的降維方法主要有以下幾種:1)線性降維方法:PCA、LPP、NPE和SPP;2)非線性降維方法:LLE和US-ELM.其中LPP、NPE、LEE和US-ELM都使得降維后的數據保持原數據的近鄰結構,SPP保持數據的稀疏表示結構,PCA的目標是使得降維后數據方差最大.

3.1 數據可視化實驗

本實驗中,我們分別用PCA、LPP、NPE、SPP、LEE、US-ELM和SNP-ELM 7種方法將一個人造數據和一個真實的UCI數據Wine分別投影到一維和二維空間,直觀地展示SNP-ELM算法的性能,并選取每個降維方法的最優結果進展示.

1)一維可視化

本實驗使用的三維人造數據如圖2所示,該數據包含3類,每類有50個樣本,該實驗分別將數據降到一維,實驗結果如圖3所示.

圖2 人造數據集Fig.2 The toy dataset

圖3 人造數據一維可視化結果Fig.3 The 1D visualization results of toy dataset

從圖3可以看出PCA以投影后的樣本方差最大為目標,其降維結果近似于把該數據投影到Z軸方向,但其將該數據投影到一維時三類數據的可分性較差.LPP、NPE、LLE和US-ELM 均以降維后樣本保持原樣本的近鄰結構為目的,因此其降維效果略有改善.其中LLE和US-ELM是非線性降維方法,其降維后不同類樣本的分離程度較LPP和NPE高些.稀疏保持投影方法SPP以降維后樣本保持原樣本的稀疏結構為目的,該方法將數據投影到一維后不同類樣本的分離程度與US-ELM相當.SNP-ELM 是一種非線性降維方法,它使降維后樣本同時保持數據的近鄰結構和稀疏結構不變.SNP-ELM雖然無法使得該數據投影到一維后三類樣本完全分離,但其降維后不同類樣本可分性是7種降維方法中最優的,只有少數第三類樣本與第二類樣本相互重疊.

2)二維可視化

本實驗使用UCI數據集Wine數據,Wine數據包含來自3個類的178個樣本,每個樣本有14個特征.實驗結果如圖4所示.

由圖4可以看出,經7種降維方法將Wine數據投影到2維時仍無法完全分離3類樣本.但從不同類樣本的重疊程度上可以看出,SPP將數據降到二維后3類數據完全重疊在一起,降維效果最差.用PCA、LPP、NPE、LLE和US-ELM 這5種方法降維后第一類數據能較好地分離,而第二類和第三類數據完全重疊在一起.本文方法將Wine數據降到二維后,不同類數據的重疊程度最低,不同類樣本的可分性最好.

3.2 基因表達數據實驗

本實驗采用高維基因表達數據測試本文方法與對比方法面向聚類任務時的降維效果.為了觀察本文降維方法將數據投影到不同維數,特別是投影到較低維時基因表達數據聚類效果,將數據分別投影到21,22,23,24,···,2n維.該實驗以降維后樣本的k-means聚類準確率衡量降維質量,實驗中的聚類準確類采用文獻[13]的計算方法.計算公式如下:

其中,n為樣本數,δ(x,y)表示當x=y時,δ=1,否則δ=0;si和ri分別為樣本原始類標簽和經聚類算法聚類后得到的類標簽:map(ri)將聚類得到的類標簽映射成與樣本數據自帶的類標簽等價的類標簽.

1)實驗數據集

實驗所選用的6個公開的基因數據集:SBCRT、DLBCL、Leukemia2、Prostate[16]、Prostate0和Colon[17],這些數據的詳細描述見表1.

2)聚類準確率比較

圖4 Wine數據二維可視化結果Fig.4 The 2D visualization results of Wine

表1 基因表達數據集描述Table 1 Summary of gene expression data sets

為減少k-means初始中心隨機選取以及USELM和SNP-ELM 方法隨機權重產生的隨機誤差.為便于比較,減少實驗結果隨機性的影響,實驗中US-ELM和SNP-ELM分別運行10次,再將每次降維后數據集執行10次k-means聚類,取100次聚類準確率的平均值作為各自方法的最終準確率,而其他降維方法的聚類準確率是10次k-means聚類準確率的平均值.最終實驗結果如表2所示,表中給出聚類準確率的均值 (方差、維數),其中維數為每個數據最優聚類結果所對應的維數.對兩種極限學習機降維方法US-ELM 和SNP-ELM 分別給出最優聚類結果所對應的參數.LPP、NPE、LLE、US-ELM 和SNP-ELM 這5種方法都在降維時保持了原始數據的近鄰結構,SPP和SNP-ELM都保持了原始數據的稀疏結構,其中LLE、US-ELM 和SNP-ELM 是非線性降維方法,SNP-ELM同時保持原始數據的近鄰結構和稀疏結構.將這5種方法降維后的聚類準確率進行對比可以發現:1)將NPE和LPP分別與LLE和USELM的準確率進行對比,可以發現后者的準確率比前者高,這是因為LEE和US-ELM分別是NPE和LPP的非線性推廣,非線性降維方法更適用于非線性分布的基因表達數據.2)SPP與LPP、NPE進行比較其聚類結果各有千秋,在DLBCL、Prostate0和Colon這3個數據集上SPP的結果較好,而在其他數據集上LPP和NPE的結果較好,這說明稀疏保持和近鄰保持各有優勢.3)SNP-ELM的聚類準確率是最高的,其主要原因是SNP-ELM既是非線性降維方法,又同時保持了原始數據的近鄰表示結構和稀疏表示結構使得降維后低維空間的數據保持了更多的判別信息.將表2中的所有方法進行對比,可以發現基于ELM的2種降維方法的準確率普遍優于其他降維方法.特別是SNP-ELM算法考慮到降維后樣本局部近鄰關系和全局稀疏性保持不變,從而使其在全部6個基因數據降維后的聚類準確率最高,且高于其他方法及US-ELM方法10%以上.這說明SNP-ELM是一種有效的高維非線性降維方法.

為進一步對比幾種降維方法在不同維數下的聚類準確率,分別選取目標維數2,4,8,16,32,···執行各種降維算法,各種降維算法在不同維數下的聚類準確率如圖5所示.從圖5可以看出SNPELM及其余6種降維算法將6個數據集投影到相同維數的特征空間時,SNP-ELM的聚類準確率都是最高的.而對于SNP-ELM算法,除Prostate和Prostate0兩個數據集,在其他4個基因數據集上都在8維處得到最高的聚類準確率.

表2 基因數據集上聚類準確率(%)Table 2 Clustering accuracy comparison(variance)on gene expression data sets(%)

圖5 將6個數據集映射到不同維度特征空間時的聚類準確率Fig.5 Clustering accuracy on six gene expression data in different dimensions

3)參數分析

SNP-ELM 模型有3個參數λ,δ和η,其中λ為正則參數.δ和η為權重系數,分別表示近鄰重構系數和稀疏重構系數的重要性.本節討論不同參數對實驗結果的影響,由前面的實驗結果可知將基因表達數據降到8維時能夠得到較高的聚類準確率,因此在進行參數分析時我們固定維數為8.根據3個參數在SNP-ELM 中的不同作用,將其分為兩組分別進行分析,正則參數λ單獨分析,權重系數δ和η一起分析.其中,λ的取值范圍為{10?4,10?3,···,104},δ和η的取值范圍為[?1,1],取值步長為0.2.

圖6給出δ=η=?0.2時,SNP-ELM降維的聚類準確率隨參數λ不同取值的變化情況.從圖6可以看出,除了Leukema2在λ=10?4時聚類準確率達到最高,其余5個基因表達數據均在λ=10?3時聚類準確率達到最高.這說明對高維基因數據而言,λ取較小值時本文方法能達到較好效果.

圖6 聚類準確率隨參數λ的變化情況(δ=η=?0.2)Fig.6 Variation of accuracy with respect of parametersλ(δ= η= ?0.2))

圖7給出λ=0.001時,不同δ和η取值下的聚類準確率.從圖7可以看出當δ取值自[?0.6,?0.2],η取值自[?0.2,0.2]時,對高維基因表達數據而言SNP-ELM算法可以取得較高的聚類準確率.

圖7 不同δ和η取值下的聚類準確率(λ=0.001)Fig.7 ariation of accuracy with respect of parametersδandη(λ=0.001)

4 結論

目前,ELM模型主要用于有監督分類或回歸問題,本文則對ELM模型推廣到無監督降維問題進行了進一步研究,提出基于稀疏和近鄰結構保持的極限學習機降維算法SNP-ELM.SNP-ELM通過模型優化求解計算近鄰表示系數,具有一定的數據自適應性,實驗結果表明SNP-ELM算法在Wine數據和基因表達數據集上性能優于其他對比方法.從研究中我們可以得到以下2個結論:1)對Wine數據、高維基因表示數據降維時,同時考慮稀疏結構和近鄰結構比只考慮單一結構更有效;2)基于ELM的非線性降維方法在Wine數據和基因表達數據上優于線性降維方法.