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

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

流形學(xué)習(xí)[1]是利用流形局部歐氏空間進(jìn)行維數(shù)約簡的算法，可有效降低高維非線性數(shù)據(jù)的維度。常見的流形學(xué)習(xí)包括局部線性嵌入(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)用在深度學(xué)習(xí)和故障檢測等方面。

融合聚類的監(jiān)督局部線性嵌入算法[6]計算近鄰點距離時，利用類別標(biāo)簽加入類別信息的權(quán)，使得樣本近鄰點多數(shù)為同類樣本，少數(shù)為異類樣本，重構(gòu)時可盡量保持?jǐn)?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ù)未知，依然存在近鄰點選擇不恰當(dāng)?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ù)分布不同，自動為每個樣本點進(jìn)行二次選擇近鄰點，避免將噪聲選為近鄰點。

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選取近鄰點采用歐氏距離準(zhǔn)則，在高維空間中容易把不在同一個線性空間的點選為近鄰點，影響數(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)中的目標(biāo)函數(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求導(dǎo)并令其為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)重矩陣，其每次迭代都能從近鄰點矩陣找到與當(dāng)前樣本點殘差最接近的近鄰點，依次選取近鄰點重構(gòu)樣本點，即最接近x的v和u優(yōu)先被選取，當(dāng)殘差為0時，則x被重構(gòu)，最遠(yuǎn)的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中選出與當(dāng)前樣本點殘差最接近的列向量，重構(gòu)稀疏向量v，得到重構(gòu)向量v′，并根據(jù)殘差判斷v′的重構(gòu)情況。

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

通過Fa更新殘差

(10)

由此可見，SAMP算法通過候選集Ca回溯的方法，將新加入的列向量與選好的列向量進(jìn)行擇優(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}作用在于返回一個下標(biāo)集，且該下標(biāo)集由向量x的前e個最大值所對應(yīng)的下標(biāo)構(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ìn)行降維，根據(jù)Libsvm工具箱[20]對降維數(shù)據(jù)進(jìn)行分類，對比分類正確率。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ù)集分別進(jìn)行近鄰點選擇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中看出，當(dāng)k值小于18時，兩個降維方法的降維效果都不錯；但當(dāng)k值超過18時，LLE降維效果明顯下降。鄰域選擇過大時，將大量錯誤點選為近鄰點，導(dǎo)致鄰域不具備為局部線性的性質(zhì)，低維映射的數(shù)據(jù)結(jié)構(gòu)信息被破壞，從而失去了降維的意義。LSALE由于其自適應(yīng)的能力，對于鄰域進(jìn)行二次選擇，盡管k值超過18，依然保持較好的降維分類效果。

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

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

圖4結(jié)果表明，LSALE降維后的數(shù)據(jù)分類正確性優(yōu)于LLE和LSLE。與原始數(shù)據(jù)相比，LSALE大幅度降維即當(dāng)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ù)進(jìn)行降維分類實驗。將全部18 319個數(shù)據(jù)進(jìn)行降維，然后分別選取3類數(shù)據(jù)的20%，共3 664個數(shù)據(jù)進(jìn)行測試。當(dāng)k=10，d=20時，對不同稀疏度S進(jìn)行降維處理，稀疏度S為二次選擇的近鄰點個數(shù)。利用Libsvm，分別對未降維的原始數(shù)據(jù)、ILLE[17]降維、LSLE降維以及LSALE降維后數(shù)據(jù)進(jìn)行分類，取10次分類結(jié)果的平均值。MNIST數(shù)據(jù)的分類正確率和運行時間如表1所示。

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

表1中，LSLE稀疏度需要手動調(diào)整達(dá)到最優(yōu)解，難以應(yīng)用實時動態(tài)系統(tǒng)中，而LSALE降維稀疏度是自適應(yīng)的，通過自身迭代選擇出最適合的近鄰點數(shù)目，達(dá)到稀疏降維的目的。與同為自適應(yīng)領(lǐng)域選擇的ILLE算法對比，LSLLE的數(shù)據(jù)具有更好的分類效果。MNIST原數(shù)據(jù)識別率很高，但訓(xùn)練與測試速度都很慢，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等降維算法，同時也縮短了運行時間。