基于最近鄰子空間的鄰域保持嵌入

徐劍豪，胡文軍,胡天杰，王哲昀

(1.湖州師范學(xué)院 信息工程學(xué)院，浙江 湖州 313000； 2.浙江省現(xiàn)代農(nóng)業(yè)資源智慧管理與應(yīng)用研究重點(diǎn)實(shí)驗(yàn)室，浙江 湖州 313000)

0 引 言

流形學(xué)習(xí)雖然是一種應(yīng)用廣泛的非線性特征提取方法，但它需要發(fā)現(xiàn)嵌入在高維數(shù)據(jù)空間的低維流形結(jié)構(gòu)，才能給出一個(gè)有效的低維表示[1].因?yàn)閿?shù)據(jù)流形未知，所以需要解決3個(gè)關(guān)鍵問(wèn)題：第一，如何定義和描述局部，即利用嵌入在高維空間的數(shù)據(jù)來(lái)描述流形的局部，通常的做法是K近鄰.第二，如何捕獲局部的結(jié)構(gòu)關(guān)系.局部關(guān)系通常包括加權(quán)圖、局部線性重構(gòu)和距離等.例如，在拉普拉斯特征映射(Laplacian Eigenmaps,LE)[2]和局部保持投影(Locality Preserving Projections,LPP)[3]中，通過(guò)K個(gè)最近鄰構(gòu)造無(wú)向圖，其邊由熱核函數(shù)或0-1函數(shù)加權(quán)，局部幾何關(guān)系體現(xiàn)在加權(quán)圖中；在局部線性嵌入(Locally Linear Embedding,LLE)[4]和鄰域保持嵌入(Neighborhood Preserving Embedding,NPE)[5]中，一個(gè)樣本點(diǎn)由K個(gè)最近鄰線性逼近，其線性權(quán)值表示局部幾何關(guān)系；在等度量映射(Isometric Mapping,ISOMAP)[6]中，通過(guò)測(cè)地距離來(lái)求解最短路徑，并利用最短距離來(lái)描述局部幾何關(guān)系.第三，如何將所有的局部結(jié)構(gòu)拼接在一起.為在低維空間中生成全局表示，并使低維表示具有更強(qiáng)的區(qū)分能力，最常見(jiàn)的方法是最小化所有的局部和，但這需要通過(guò)調(diào)整實(shí)驗(yàn)參數(shù)來(lái)實(shí)現(xiàn).局部關(guān)系過(guò)程是本文關(guān)注的重點(diǎn).

顯然，局部對(duì)流形學(xué)習(xí)方法具有至關(guān)重要的作用.流形學(xué)習(xí)的假設(shè)數(shù)據(jù)采樣于高維空間，而高維空間由低維流形生成.遺憾的是，我們還不知道真正的低維流形.因此，利用高維空間的數(shù)據(jù)捕獲未知流形存在一定的風(fēng)險(xiǎn)，尤其在數(shù)據(jù)存在大量噪聲和冗余信息的情況下.換言之，上述方法存在爭(zhēng)議.由于無(wú)法在一個(gè)真正的低維流形中定義局部，因此一個(gè)可行的方法就是提高局部的置信度(Locality Confidence).事實(shí)上，用K個(gè)最近鄰點(diǎn)來(lái)定義每個(gè)局部，其體積是不同的，體積大的局部會(huì)與其他局部產(chǎn)生重疊，而足夠的重疊能確保它們之間的連通性.大部分的流形學(xué)習(xí)方法不考慮局部體積，而是將所有局部簡(jiǎn)單地拼接在一起.本文將每個(gè)點(diǎn)和K個(gè)最近鄰視為一個(gè)局部，利用該局部來(lái)形成一個(gè)最近鄰子空間，并通過(guò)體積來(lái)度量局部結(jié)構(gòu)關(guān)系,提出一種最近鄰子空間鄰域保持嵌入算法(Nearest Subspace Neighborhood Preserving Embedding,NSNPE).

1 鄰域保持嵌入

數(shù)據(jù)集X=xi∈Rd×N，經(jīng)投影向量a∈Rd變換后為Y=yi∈R1×N，其中yi=aTxi.NPE利用K近鄰或ε鄰域方法找到樣本xi的近鄰集合N(xi)，并將它們的近鄰關(guān)系表示為xi=∑xj∈N(xi)Wijxj，其中xj為xi的K個(gè)近鄰之一，Wij為它們之間的近鄰關(guān)系.權(quán)重矩陣的具體計(jì)算為：

(1)

在上述鄰域關(guān)系的基礎(chǔ)上，NPE認(rèn)為樣本點(diǎn)在低維空間仍應(yīng)保持這種結(jié)構(gòu)關(guān)系，故最小化代價(jià)函數(shù)為：

(2)

經(jīng)簡(jiǎn)單的數(shù)學(xué)推導(dǎo)，式(2)等價(jià)于：

(3)

其中，M=(I-W)T(I-W).利用拉格朗日乘數(shù)法，式(3)等價(jià)于求解廣義特征問(wèn)題：

XMXTa=λXXTa.

(4)

顯然，最小化目標(biāo)函數(shù)的解是上述廣義特征問(wèn)題最小特征值所對(duì)應(yīng)的特征向量.正是著眼于局部，NPE可以學(xué)習(xí)任意維局部線性的低維流形，并能將其歸結(jié)為稀疏矩陣特征值的計(jì)算問(wèn)題[7]，且計(jì)算復(fù)雜度相對(duì)較小.但它也存在一些缺點(diǎn)：其低維嵌入所保持的并不是一個(gè)距離關(guān)系，不適用于對(duì)等距流形；只關(guān)注保持近鄰點(diǎn)的幾何性質(zhì)，對(duì)于樣本稀疏、關(guān)聯(lián)性較弱、有噪聲的數(shù)據(jù)集，其相隔較遠(yuǎn)的點(diǎn)之間的關(guān)聯(lián)性會(huì)減弱，從而導(dǎo)致映射結(jié)果產(chǎn)生偏差[8]；NPE構(gòu)建的局部存在置信度不足的問(wèn)題.針對(duì)以上問(wèn)題，本文將進(jìn)行分析討論，并給出合理的改善方法.

2 最近鄰子空間鄰域保持嵌入

NPE算法雖然能較好地保持非線性數(shù)據(jù)的局部結(jié)構(gòu)特征，但并未考慮局部體積問(wèn)題.針對(duì)這一不足，本文在簡(jiǎn)要分析局部特性的基礎(chǔ)上，提出最近鄰子空間概念，并將其引入NPE方法，給出NSNPE的函數(shù)模型和求解方式，同時(shí)進(jìn)行時(shí)間復(fù)雜度分析.

2.1 最近鄰子空間

圖1 局部幾何結(jié)構(gòu)

(5)

根據(jù)上述研究，可以總結(jié)出局部的幾個(gè)性質(zhì)：

性質(zhì)1(可構(gòu)性)：一個(gè)局部通常由K+1個(gè)點(diǎn)構(gòu)成，包括唯一主點(diǎn)和K個(gè)最近鄰點(diǎn).

性質(zhì)2(近鄰性)：只有連接主點(diǎn)的邊才能與其產(chǎn)生近鄰關(guān)系.

性質(zhì)3(累加性)：所有的局部結(jié)構(gòu)都可在低維空間中累加.

性質(zhì)4(體積性)：局部中的點(diǎn)可形成一個(gè)平行多面體，且局部體積可通過(guò)測(cè)量平行多面體體積得到.

回顧流形學(xué)習(xí)的3個(gè)問(wèn)題，并將它們與4個(gè)性質(zhì)聯(lián)系起來(lái)，發(fā)現(xiàn)性質(zhì)1、性質(zhì)2和性質(zhì)3分別對(duì)應(yīng)解決了流形學(xué)習(xí)的第一、第二和第三個(gè)問(wèn)題.由性質(zhì)4可知，充分考慮各局部的體積，使相近的鄰域數(shù)據(jù)間具有足夠的聯(lián)系，能夠加強(qiáng)局部信息的傳播效率，改善局部的置信度問(wèn)題.

2.2 NSNPE模型

從直觀上想象，體積大的局部會(huì)與其他局部產(chǎn)生大量的交疊，而足夠的交疊能確保整個(gè)數(shù)據(jù)的連通性和較遠(yuǎn)點(diǎn)之間的聯(lián)系，其符合數(shù)據(jù)分布的隱性要求[11].本文使用以下方法對(duì)所有最近鄰子空間的體積進(jìn)行歸一化：

(6)

將式(6)的每個(gè)歸一化體積加入到NPE的局部損失函數(shù)中，得到NSNPE函數(shù)模型：

(7)

其中，最小化NPE的局部損失函數(shù)在低維表示中評(píng)估了最近鄰子空間的代價(jià)，并保持了局部的內(nèi)部關(guān)系.當(dāng)拼接所有最近鄰子空間后，歸一化體積強(qiáng)制縮放了每個(gè)局部的結(jié)構(gòu)風(fēng)險(xiǎn).

2.3 模型求解

對(duì)式(7)，可先定義：

(8)

將式(8)表示為矩陣形式：

Z=aTXU1/2(I-W),

(9)

其中，I為N×N的單位陣.通過(guò)簡(jiǎn)單的數(shù)學(xué)推導(dǎo)，式(7)等價(jià)于：

(10)

(11)

對(duì)式(11)構(gòu)造拉格朗日函數(shù)：

(12)

其中，λ為拉格朗日乘子.對(duì)投影向量a求偏導(dǎo)，并設(shè)為0，可得：

(13)

即

(14)

顯然，這是一個(gè)廣義特征方程的計(jì)算問(wèn)題.在式(14)中，將l個(gè)最小非零特征值對(duì)應(yīng)的特征向量記為a1,a2,…,al，并組成投影矩陣A=[a1,a2,…,al]∈Rd×l，則數(shù)據(jù)集X=[x1,x2,…,xN]∈Rd×N降至l維可由下式實(shí)現(xiàn)：

Y=ATX.

(15)

由此歸納出NSNPE的實(shí)現(xiàn)算法，見(jiàn)表1.

表1 NSNPE算法

2.4 復(fù)雜度

3 實(shí) 驗(yàn)

為驗(yàn)證NSNPE算法的有效性，本研究利用KPCA[13]、ISOMAP、LLE、NPE和NSNPE對(duì)數(shù)據(jù)集進(jìn)行降維，通過(guò)聚類(lèi)和分類(lèi)任務(wù)實(shí)驗(yàn)，比較分析5種算法的低維表示能力.所有實(shí)驗(yàn)均在同一臺(tái)機(jī)器上進(jìn)行，其CPU為Intel Core(TM)i5-8500 3.00 GHz，內(nèi)存為8 GB，操作系統(tǒng)為Windows 1064位，編譯環(huán)境為MATLAB 2018b.

3.1 數(shù)據(jù)集與參數(shù)設(shè)置

實(shí)驗(yàn)選取的3個(gè)數(shù)據(jù)集分別為COIL20、ORL、YALE.數(shù)據(jù)集的描述為：COIL20包含20個(gè)日常生活物品，每個(gè)物品按順時(shí)針旋轉(zhuǎn)1周，每隔5°拍攝1張照片，每個(gè)物品有72張照片，總計(jì)1 440張灰度圖像，每張照片的圖像大小均為64×64.COIL20可從 http:∥www.cs.columbia.edu/CAVE/software/softlib/coil-20.html網(wǎng)址下載.ORL包含40人，每人拍攝10張人臉照片，總計(jì) 400 張灰度圖片，每張照片的圖像大小為 92×112，這些圖像包含人物表情和面部細(xì)節(jié)的變化過(guò)程.ORL可從http:∥www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html網(wǎng)址下載.YALE包含15人，每人拍攝11張人臉照片，總計(jì)165張灰度圖片，每張照片的圖像大小為100×100，這些人像圖片包含在不同的燈光環(huán)境下拍攝的每個(gè)人不同的神情和臉部姿態(tài)變化.YALE可從http:∥vision.ucsd.edu/datasets/yale_face_dataset_original/yalefaces.zip網(wǎng)址下載得到.為便于實(shí)驗(yàn)操作和數(shù)據(jù)集的規(guī)范化，本研究將數(shù)據(jù)集每張照片的像素值統(tǒng)一處理為1 024，并對(duì)數(shù)據(jù)集進(jìn)行歸一化處理.處理后的數(shù)據(jù)集信息見(jiàn)表2.

表2 實(shí)驗(yàn)數(shù)據(jù)集

由表2可知，ORL和YALE的樣本數(shù)遠(yuǎn)大于特征數(shù)，而采用LLE、NPE和本文的NSNPE在對(duì)其進(jìn)行降維時(shí)會(huì)出現(xiàn)小樣本問(wèn)題，從而導(dǎo)致計(jì)算結(jié)果不準(zhǔn)確.為此，本研究采用奇異值分解方法對(duì)其進(jìn)行處理.此外，流形學(xué)習(xí)算法會(huì)面臨鄰域選擇問(wèn)題，若選擇的K值較小，雖然能較明顯地體現(xiàn)局部的線性結(jié)構(gòu)，但又會(huì)使局部之間沒(méi)有更多的交疊部分；若選擇的K值較大，則會(huì)使局部包含較多的冗余信息.由此可見(jiàn)，鄰域選取的結(jié)果會(huì)直接影響最終嵌入效果的好壞.在實(shí)驗(yàn)中，為保證參數(shù)的統(tǒng)一性，當(dāng)涉及到K近鄰設(shè)置問(wèn)題時(shí)，將其值統(tǒng)一確定為5.

3.2 聚類(lèi)實(shí)驗(yàn)

3.2.1 評(píng)價(jià)指標(biāo)

模糊C均值聚類(lèi)(Fuzzy C-Means,FCM)[14]是模糊聚類(lèi)領(lǐng)域發(fā)展較完善的一種算法，其具有良好的魯棒性和實(shí)用性，被廣泛應(yīng)用于大部分的聚類(lèi)問(wèn)題.本研究采用FCM對(duì)降維后的數(shù)據(jù)進(jìn)行聚類(lèi)，并通過(guò)聚類(lèi)的準(zhǔn)確率(Accuracy of Clustering,AC)[15]和歸一化互信息(Normalized Mutual Information,NMI)[16]來(lái)評(píng)價(jià)特征的鑒別能力.假設(shè)給定的數(shù)據(jù)集樣本的正確標(biāo)簽向量為s，si∈s，且i=1,2,…,N，聚類(lèi)后的標(biāo)簽向量為r，ri∈r且i=1,2…,N，則聚類(lèi)準(zhǔn)確率AC可定義為：

(16)

其中，當(dāng)x=y時(shí),δ(x,y)函數(shù)為1，否則為0；N為樣本總數(shù)；map(ri)為映射函數(shù)，其作用基于Kuhn-Munkres算法[17]，將得到的聚類(lèi)標(biāo)簽與數(shù)據(jù)集給定的標(biāo)簽進(jìn)行匹配，其值越大說(shuō)明聚類(lèi)的效果越好.

假設(shè)C為數(shù)據(jù)集給定的類(lèi)集，C′為聚類(lèi)后的類(lèi)集，則互信息(Mutual Information,MI)定義為：

(17)

(18)

其中，H(C)和H(C′)分別為C和C′的熵;NMI(C,C′)的范圍被約束為0～1，其值越大說(shuō)明聚類(lèi)效果越好.

3.2.2 結(jié)果與分析

圖2給出了COIL20數(shù)據(jù)集聚類(lèi)準(zhǔn)確率和歸一化互信息折線，其中BaseLine代表數(shù)據(jù)集未降維的聚類(lèi)指標(biāo).由圖2(a)可知，除在60維外，ISOMAP整體都低于BaseLine，其聚類(lèi)效果不理想，由此反映出提取的特征不佳；相對(duì)來(lái)說(shuō)，KPCA優(yōu)于ISOMAP，但圍繞BaseLine，其準(zhǔn)確率上下波動(dòng)，穩(wěn)定性不好；LLE在30維時(shí)，其準(zhǔn)確率達(dá)到最高值，之后便一直呈下降趨勢(shì)，在50維后甚至低于BaseLine，并隨著特征提取維度的增加，出現(xiàn)了負(fù)優(yōu)化問(wèn)題.從整體看，NPE和NSNPE的準(zhǔn)確率高于其他3種，且呈上升趨勢(shì).相比而言，NSNPE的特征表現(xiàn)最佳.從圖2(b)可知，NSNPE的歸一化互信息NMI高于其他算法.

圖2 COIL20數(shù)據(jù)集聚類(lèi)結(jié)果

圖3給出了ORL數(shù)據(jù)集聚類(lèi)準(zhǔn)確率和歸一化互信息折線，其中BaseLine代表數(shù)據(jù)集未降維的聚類(lèi)指標(biāo).從圖3(a)可知，KPCA在10～70維時(shí)波動(dòng)較明顯，穩(wěn)定性不高；ISOMAP整體低于BaseLine，提取的特征效果不佳；LLE在20維時(shí)表現(xiàn)最佳，在20～50維之間持續(xù)降低，之后便上下波動(dòng)，穩(wěn)定性不高；NPE在30維后較穩(wěn)定.相比較而言，NSNPE準(zhǔn)確率更高，總體更加穩(wěn)定，且呈逐漸上升趨勢(shì)，體現(xiàn)出較好的低維表現(xiàn)能力.由圖3(b)可知，在10和20維時(shí)，雖然NSNPE的NMI低于PE，但在其他維度上高于其他算法.

圖3 ORL數(shù)據(jù)集聚類(lèi)結(jié)果

圖4給出了YALE數(shù)據(jù)集聚類(lèi)準(zhǔn)確率和歸一化互信息折線，其中BaseLine代表數(shù)據(jù)集未降維的聚類(lèi)指標(biāo).由圖4(a)可知，LLE在30～60維之間波動(dòng)較明顯，在50維和100維時(shí)出現(xiàn)低于BaseLine的情況；ISOAMP和KPCA相對(duì)較穩(wěn)定，且高于BaseLine，但I(xiàn)SOMAP的準(zhǔn)確率只維持在0.62～0.64之間；除在10、20、50維時(shí)NSNPE低于NPE外，其他維度的準(zhǔn)確率都是最好的.由圖4(b)可知，NSNPE的歸一化互信息NMI高于其他算法.

圖4 YALE數(shù)據(jù)集聚類(lèi)結(jié)果

3.3 分類(lèi)實(shí)驗(yàn)

3.3.1 評(píng)價(jià)指標(biāo)

支持向量機(jī)分類(lèi)(Support Vector Machine,SVM)主要是為求得最優(yōu)分類(lèi)超平面，以達(dá)到結(jié)構(gòu)風(fēng)險(xiǎn)最小化.由于其不存在過(guò)擬合和擬合不足的現(xiàn)象，故在小樣本和高維度空間中表現(xiàn)出良好的泛化能力，是一種應(yīng)用廣泛的分類(lèi)算法[18].本實(shí)驗(yàn)采用SVM對(duì)降維后的數(shù)據(jù)進(jìn)行分類(lèi).為保證分類(lèi)結(jié)果的有效性，本研究采用十折交叉驗(yàn)證方法，通過(guò)準(zhǔn)確率均值(Mean of Accuracy,MA)和方差均值(Mean of Variance,MV)來(lái)評(píng)價(jià)不同特征提取算法的分類(lèi)性能.假設(shè)測(cè)試集的正確標(biāo)簽向量為p，pi∈p且i=1,2,…，n，測(cè)試集分類(lèi)后的標(biāo)簽向量為q，qi∈q且i=1,2,…,n，則準(zhǔn)確率T的計(jì)算方式為：

(19)

其中，當(dāng)pi=qi時(shí)，δ(pi,qi)函數(shù)為1，否則為0；n為測(cè)試樣本數(shù)；N為樣本總數(shù).

利用式(19)可得所有準(zhǔn)確率的值.準(zhǔn)確率均值MA和方差均值MV的計(jì)算公式為：

(20)

(21)

其中，m=10為交叉驗(yàn)證次數(shù).MA越大說(shuō)明分類(lèi)精度越高，MV越小說(shuō)明分類(lèi)的“穩(wěn)定性”或“魯棒性”越好.

3.3.2 結(jié)果與分析

表3、表4和表5分別給出了COIL20 、ORL和YALE數(shù)據(jù)集的準(zhǔn)確率均值和方差均值，其中最佳數(shù)值用黑體表示.由表3可見(jiàn)，除在50維外，NSNPE的分類(lèi)準(zhǔn)確率高于其他算法.從方差角度看，NSNPE的方差維持在2.33上下波動(dòng)，低于其他算法，表明其在10個(gè)維度上的準(zhǔn)確率波動(dòng)較小.由表4可見(jiàn)，NSNPE在20，30，50，60維的準(zhǔn)確率雖然低于其他算法，但在其他維度上，其準(zhǔn)確率最高.從整體方差看，KPCA、ISOMAP和LLE的方差都出現(xiàn)了大于5的情況，而NSNPE依然維持在較低值.由表5可見(jiàn)，NSNPE的兩個(gè)指標(biāo)都有較好的分類(lèi)表現(xiàn).

表3 COIL20數(shù)據(jù)集準(zhǔn)確率均值和方差均值

表4 ORL數(shù)據(jù)集準(zhǔn)確率均值和方差均值

表5 YALE數(shù)據(jù)集準(zhǔn)確率均值和方差均值

4 結(jié) 語(yǔ)

與大部分基于流形學(xué)習(xí)的特征提取方法不同，本文從空間體積角度考慮了局部的結(jié)構(gòu)關(guān)系，并將這一思想與NPE算法結(jié)合，以實(shí)現(xiàn)同步保持局部的內(nèi)部關(guān)系和空間關(guān)系.從真實(shí)數(shù)據(jù)的聚類(lèi)和分類(lèi)實(shí)驗(yàn)結(jié)果看，NSNPE獲得了較好的性能.但最近鄰參數(shù)K的選擇是否會(huì)影響NSNPE的降維效果,以及如何將最近鄰子空間與其他基于流形學(xué)習(xí)的特征提取和特征選擇等方法進(jìn)行結(jié)合，本文均未進(jìn)行更深入的研究，這將是今后研究的重點(diǎn).