自適應(yīng)局部稀疏線性嵌入降維算法

吳 青, 祁宗仙, 臧博研, 張 昱

(西安郵電大學 自動化學院， 陜西 西安 710121)

流形學習[1]是利用流形局部歐氏空間進行維數(shù)約簡的算法，可有效降低高維非線性數(shù)據(jù)的維度。常見的流形學習包括局部線性嵌入(locally linear embedding, LLE)[2]，拉普拉斯特征映射(laplacian eigenmaps, LE)[3]，距映射算法(isometric mapping, ISOMAP)[4]和局部切空間排列(local tangent space alignment, LTSA)[5]等。LE采用局部領(lǐng)域相似度表示流形的距離，計算復(fù)雜度低但精度不高。ISOMAP采用測地線距離表示全局流形上的距離，降維的精度高但復(fù)雜度也高，不適合大量數(shù)據(jù)降維。而LLE是假設(shè)數(shù)據(jù)在很小的局部空間鄰域上，可近似看成線性相關(guān)，每個數(shù)據(jù)點都可由它最近的幾個點線性表示，具有算法思想直觀、易實現(xiàn)和速度快等優(yōu)點，已廣泛應(yīng)用在深度學習和故障檢測等方面。

融合聚類的監(jiān)督局部線性嵌入算法[6]計算近鄰點距離時，利用類別標簽加入類別信息的權(quán)，使得樣本近鄰點多數(shù)為同類樣本，少數(shù)為異類樣本，重構(gòu)時可盡量保持數(shù)據(jù)的分布信息，但需要樣本提供類別信息，適用性較小。領(lǐng)域選擇的LLE算法[7]運用系數(shù)主分量估測每個樣本點噪聲的概率，避免了選擇高概率噪聲的樣本點作為近鄰點。在數(shù)據(jù)集稀疏的情況下，稀疏局部線性嵌入算法[8]利用數(shù)據(jù)的統(tǒng)計信息動態(tài)確定局部線性化范圍，能夠較好地把握數(shù)據(jù)的局部和整體信息，提高了算法的抗噪性，但沒有解決權(quán)重矩陣奇異性的問題。局部稀疏線性嵌入(locally and sparsely linear embedding, LSLE)算法[9]采用正交匹配追蹤算法求解權(quán)重矩陣，避免了求權(quán)重矩陣的逆運算,但在實時的動態(tài)系統(tǒng)中，有效近鄰點的個數(shù)未知，依然存在近鄰點選擇不恰當?shù)膯栴}。

為了優(yōu)化近鄰點選取和避免權(quán)重矩陣奇異，本文提出一種自適應(yīng)局部稀疏線性嵌入方法(locally and sparsity adaptive linear embedding, LSALE)。采用壓縮感知(compressed sensing, CS)[10-12]中的稀疏度自適應(yīng)匹配追蹤算法(sparsity adaptive matching pursuit, SAMP)[13-15]求解樣本點的近鄰權(quán)重系數(shù)，自適應(yīng)地選擇有效近鄰點，避免權(quán)重矩陣求逆。依據(jù)數(shù)據(jù)分布不同，自動為每個樣本點進行二次選擇近鄰點，避免將噪聲選為近鄰點。

1 局部線性嵌入

在局部空間內(nèi)，數(shù)據(jù)樣本點xi(i=1,2,…,n)可由離它最近的k個樣本點x1,x2,…,xk線性[1]表示為

xi=wi1x1+wi2x2+…+wikxk。

(1)

其中wi1,wi2,…,wik為權(quán)重系數(shù)。利用LLE降維后，xi的低維映射像x′i，則可由x1,x2,…,xk對應(yīng)的像x′1,x′2,…,x′k線性[1]表示為

x′i=wi1x′1,wi2x′2,…,wikx′k。

(2)

映射前后線性關(guān)系的權(quán)重系數(shù)wi1,wi2,…,wik不變。

顯然，xi只需要求得k個近鄰點x1,x2,…,xk的權(quán)重系數(shù)便可以降維，無需全局參與運算，即可降低計算量，提高運算效率。因此，LLE算法要先求解原空間中每個樣本點線性表示的權(quán)重系數(shù)，然后利用樣本點在原空間的權(quán)重系數(shù)，求它在某低維空間的像。

1.1 權(quán)重系數(shù)

已知數(shù)據(jù)集{x1,x2,…,xn},xi∈D，確定樣本點xi的k個最近鄰點，求出xi和k個最近鄰點之間的線性關(guān)系，即找到線性關(guān)系的權(quán)重系數(shù)，滿足[2]

(3)

其中，xj為xi的近鄰點，wij為xj的權(quán)重系數(shù)。

利用最小二乘方法求得xi所有近鄰點的權(quán)重向量[2]為

(4)

(5)

式中，α為極小的常數(shù)值，I為k×k階單位矩陣，tr(Zi)表示Zi的跡。

無參數(shù)和非迭代的特性使得LLE計算量小，容易實現(xiàn)，但求解權(quán)重矩陣時需要求Zi的逆，若Zi奇異，則式(4)解不存在；添加擾動項式(5)，則可求得式(4)解，但影響了降維效果。同時LLE選取近鄰點采用歐氏距離準則，在高維空間中容易把不在同一個線性空間的點選為近鄰點，影響數(shù)據(jù)降維的有效性。LLE近鄰點選取示意圖如圖1所示。

圖1 LLE近鄰點選取

1.2 低維映射

利用權(quán)重向量wi對數(shù)據(jù)降維。假設(shè)D維樣本集{x1,x2,…,xn},xi∈D在低維空間d對應(yīng)的投影為{y1,y2,…,yn},yi∈d,保持相同的線性關(guān)系，則低維映射滿足[2]

(6)

其中yi為xi降維后的樣本點，yj為yi的近鄰點。I是單位矩陣。

將式(6)中的目標函數(shù)矩陣化[2]為

J(y)=tr[YT(I-W)T(I-W)Y],

(7)

其中

Y=(y1,y2,…,yn),
W=(w1,w2,…,wn)T。

令M=(I-W)T(I-W)，則式(7)可以表示為

J(y)=tr(YTMY)。

(8)

通過拉格朗日乘子法，對Y求導并令其為0，得到MYT=λYT。式(8)的解等價于求M的特征值對應(yīng)的特征向量。為使式(6)取最小值，選擇M中最小的d個特征值對應(yīng)的特征向量。由于最小的特征值無限接近于0，所以應(yīng)取第二個到第d+1個特征值對應(yīng)的特征向量組成低維映射Y。

2 局部稀疏自適應(yīng)線性嵌入

在LSALE中，采用SAMP算法求近鄰點的權(quán)重矩陣，其每次迭代都能從近鄰點矩陣找到與當前樣本點殘差最接近的近鄰點，依次選取近鄰點重構(gòu)樣本點，即最接近x的v和u優(yōu)先被選取，當殘差為0時，則x被重構(gòu)，最遠的y不會被選取。LSALE近鄰點選取示意圖如圖2所示。

圖2 LSALE近鄰點選取

2.1 稀疏度自適應(yīng)匹配追蹤

采用SAMP算法求解LLE的權(quán)重矩陣，利用樣本點被重構(gòu)的殘差動態(tài)地選取有效近鄰點。SAMP的優(yōu)化問題[13-15]為

(9)

其中v是稀疏向量，u是觀測向量，A是稀疏矩陣，‖·‖0表示求解0范數(shù)。SAMP算法以觀測向量u和殘差r為參考，從矩陣A中選出與當前樣本點殘差最接近的列向量，重構(gòu)稀疏向量v，得到重構(gòu)向量v′，并根據(jù)殘差判斷v′的重構(gòu)情況。

在SAMP算法中，將觀測矩陣A中選出與當前殘差ra-1最相近的e個列向量的下標存放在預(yù)選集Sa中，a為迭代次數(shù)，則對應(yīng)在觀測矩陣A的列向量集合為ASa。支撐集Fa存放用于重構(gòu)v的列向量下標，首次迭代為空集。通過殘差ra-1選擇A中列向量集合AFa重構(gòu)v，并將其下標放在支撐集Fa中。合并預(yù)選集Sa與支撐集Fa-1得到候選集Ca，對應(yīng)的列向量集合為ACa。將ACa中元素與u內(nèi)積，找到與v最接近的e個列向量的下標，放入支撐集Fa中。

通過Fa更新殘差

(10)

由此可見，SAMP算法通過候選集Ca回溯的方法，將新加入的列向量與選好的列向量進行擇優(yōu)選取，實現(xiàn)全局最優(yōu)選取。

2.2 局部稀疏自適應(yīng)嵌入

(11)

式(10)中0范數(shù)正則化[16]的引入，可稀疏wi，再通過式(8)，求解得出低維映射Y。

LSALE算法具體步驟如下。

輸入高維樣本矩陣

X=[x1,x2,…,xn]∈D，

近鄰點個數(shù)為k，低維空間維數(shù)為d，其中D>d。

輸出低維樣本矩陣

Y=[y1,y2,…,yn]∈d。

步驟2利用式(11)計算每個樣本點xi的k個近鄰點的權(quán)重向量wi。

max{|x|,e}作用在于返回一個下標集，且該下標集由向量x的前e個最大值所對應(yīng)的下標構(gòu)成，“*”表示共軛轉(zhuǎn)置。將預(yù)選集Sa與支撐集Fa-1合并為候選集，即

Ca=Fa-1∪Sa。

支撐集

步驟5根據(jù)式(10)，得出殘差

步驟8將所有的重構(gòu)權(quán)重向量w′i組成權(quán)重矩陣W，利用式(8)求得低維映射Y，降維結(jié)束。

3 實驗結(jié)果分析

選取UCI數(shù)據(jù)集中的Wine數(shù)據(jù)和MNIST手寫體數(shù)據(jù)[17-18]，分別利用LSALE與LLE、LSLE和自適應(yīng)鄰域選擇的局部線性嵌入(improved locally linear embedding, ILLE)[19]降維算法對數(shù)據(jù)進行降維，根據(jù)Libsvm工具箱[20]對降維數(shù)據(jù)進行分類，對比分類正確率。Libsvm中的核函數(shù)選擇徑向基核函數(shù)。實驗環(huán)境為Intel(R)Core i7-6700HQ CPU、8G內(nèi)存和MATLAB R2015A。

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

Wine數(shù)據(jù)集是一組13維的3類數(shù)據(jù)。Wine數(shù)據(jù)集分別進行近鄰點選擇k對數(shù)據(jù)正確率的影響和不同低維維度d對數(shù)據(jù)正確率的影響兩組實驗。

實驗1近鄰點選擇k對數(shù)據(jù)正確率的影響。通過尋找Wine數(shù)據(jù)集最適合的近鄰點個數(shù)，對比LLE和LSALE算法k值不同對分類結(jié)果的影響。降維維度d=4，e=2。LSALE和LLE算法k值變化對分類正確率的影響如圖3所示。

圖3 LSALE和LLE不同近鄰點的分類正確率

從圖3中看出，當k值小于18時，兩個降維方法的降維效果都不錯；但當k值超過18時，LLE降維效果明顯下降。鄰域選擇過大時，將大量錯誤點選為近鄰點，導致鄰域不具備為局部線性的性質(zhì)，低維映射的數(shù)據(jù)結(jié)構(gòu)信息被破壞，從而失去了降維的意義。LSALE由于其自適應(yīng)的能力，對于鄰域進行二次選擇，盡管k值超過18，依然保持較好的降維分類效果。

實驗2不同低維維度d對數(shù)據(jù)正確率的影響。取實驗1中分類正確率最高的近鄰點個數(shù)k=16，稀疏度S=2。利用Libsvm，分別對未降維時的原始數(shù)據(jù)、LLE降維、LSLE降維和LSALE降維后的數(shù)據(jù)進行分類，結(jié)果如圖4所示。

圖4 Wine數(shù)據(jù)集分類結(jié)果對比

圖4結(jié)果表明，LSALE降維后的數(shù)據(jù)分類正確性優(yōu)于LLE和LSLE。與原始數(shù)據(jù)相比，LSALE大幅度降維即當d<6時，原樣本特征缺失，分類效果不理想，但d≥8時，LSALE的分類效果要明顯優(yōu)于原始數(shù)據(jù)的分類結(jié)果。

3.2 MNIST數(shù)據(jù)集

MNIST數(shù)據(jù)包含數(shù)字為0～9的手寫體圖片。對MNIST中數(shù)字為1、3、7等3類相似的數(shù)據(jù)進行降維分類實驗。將全部18 319個數(shù)據(jù)進行降維，然后分別選取3類數(shù)據(jù)的20%，共3 664個數(shù)據(jù)進行測試。當k=10，d=20時，對不同稀疏度S進行降維處理，稀疏度S為二次選擇的近鄰點個數(shù)。利用Libsvm，分別對未降維的原始數(shù)據(jù)、ILLE[17]降維、LSLE降維以及LSALE降維后數(shù)據(jù)進行分類，取10次分類結(jié)果的平均值。MNIST數(shù)據(jù)的分類正確率和運行時間如表1所示。

表1 MNIST數(shù)據(jù)實驗

表1中，LSLE稀疏度需要手動調(diào)整達到最優(yōu)解，難以應(yīng)用實時動態(tài)系統(tǒng)中，而LSALE降維稀疏度是自適應(yīng)的，通過自身迭代選擇出最適合的近鄰點數(shù)目，達到稀疏降維的目的。與同為自適應(yīng)領(lǐng)域選擇的ILLE算法對比，LSLLE的數(shù)據(jù)具有更好的分類效果。MNIST原數(shù)據(jù)識別率很高，但訓練與測試速度都很慢，LSALE降維后的數(shù)據(jù)不僅提高了識別率，同時縮短了運行時間。相比于LLE、LSLE、ILLE算法，LSALE能夠自動選擇每一個樣本近鄰點的稀疏度，得到更高的分類正確率，從而表明稀疏自適應(yīng)方法的合理有效。

4 結(jié)語

自適應(yīng)局部稀疏嵌入降維算法，根據(jù)樣本點和近鄰矩陣重構(gòu)出近鄰點的權(quán)重矩陣，避免了求權(quán)重矩陣的逆運算，提高了降維的有效性。該方法自適應(yīng)選取近鄰點，優(yōu)化了鄰域大小，保留了更多的局部結(jié)構(gòu)信息。實驗結(jié)果表明，LSALE算法的分類正確率均高于LLE、LSLE和ILLE等降維算法，同時也縮短了運行時間。