郭愛心

（山西師范大學(xué)物理與信息工程學(xué)院，山西 太原 030006）

1 引言

隨著信息技術(shù)的發(fā)展和海量數(shù)據(jù)的積累，數(shù)據(jù)處理與挖掘日益重要。而現(xiàn)實(shí)中的數(shù)據(jù)往往具有很高的維度，如手寫數(shù)據(jù)、人臉數(shù)據(jù)和監(jiān)控視頻等，難以用現(xiàn)有的數(shù)據(jù)分析方法去處理，故需要對高維數(shù)據(jù)進(jìn)行降維處理，分析其內(nèi)在結(jié)構(gòu)和特征。手寫數(shù)據(jù)的非線性結(jié)構(gòu)分析在手寫數(shù)據(jù)識別[1]和手寫簽名認(rèn)證[3]中扮演了重要角色。鑒于手寫數(shù)據(jù)的高維非線性特征，應(yīng)使用非線性降維算法進(jìn)行降維分析。常用的非線性降維算法有等距特征映射算法[4]（Isometric Feature Mapping,ISOMAP）、局部線性嵌入算法[5]（Locally Linear Embedding,LLE）、拉普拉斯映射算法[6]（Laplacian Eigenmaps,LE）和局部切空間排列算法[7]（Local Tangent Space Alignment,LTSA）等。其中ISOMAP算法可以保留全局特征，廣泛應(yīng)用于圖像處理、數(shù)據(jù)可視化和信號處理。然而，由于要計(jì)算最短距離和特征值分解，當(dāng)數(shù)據(jù)量過大的時(shí)，ISOMAP算法的效率會降低。為了提高ISOMAP的可擴(kuò)展性，Silva等提出了隨機(jī)選擇地標(biāo)點(diǎn)的ISOMAP算法，即Landmark-ISOMAP(L-ISOMAP)算法[8]，但隨機(jī)選擇地標(biāo)點(diǎn)會導(dǎo)致算法性能不穩(wěn)定。在此基礎(chǔ)上，文獻(xiàn)[9]基于最小子集覆蓋進(jìn)行地標(biāo)點(diǎn)的選擇，提出了Fast-ISOMAP算法，但地標(biāo)點(diǎn)仍存在冗余。本文從地標(biāo)點(diǎn)的選擇出發(fā)，提出了改進(jìn)ISOMAP算法（Improved ISOMAPBased on Landmark,IL-ISOMAP），并將其應(yīng)用于手寫數(shù)據(jù)的非線性結(jié)構(gòu)分析。

2 ISOMAP算法

ISOMAP算法降維的實(shí)質(zhì)是通過保持高維空間和低維空間的距離相似來保持?jǐn)?shù)據(jù)的內(nèi)在特征。設(shè)流形數(shù)據(jù)X={x1,x2,…,xn}?M?Rd,其中M為D維流形。設(shè)Y={y1,y2,…,yn}?Rd為d維歐幾里得空間的嵌入結(jié)果，其中d<

（1）通過k近鄰或固定閾值的方法構(gòu)建數(shù)據(jù)點(diǎn)的鄰域圖G，鄰域圖中的每條邊的權(quán)重為d(xi,xj)。

（2）計(jì)算數(shù)據(jù)點(diǎn)之間的測地距離。對于近鄰的數(shù)據(jù)點(diǎn)，點(diǎn)之間的歐氏距離即為測地距離，而對于互不為鄰域數(shù)據(jù)點(diǎn)，可通過Dijkstras或Floyds算法計(jì)算數(shù)據(jù)點(diǎn)之間的最短路徑進(jìn)行近似，得出測地距離矩陣Dn,n。

（3）將多維尺度分析算法[10]（Multidimensional Scaling,MDS）應(yīng)用到測地距離矩陣Dn,n中，即可得到d維嵌入數(shù)據(jù)Y。

3 改進(jìn)ISOMAP算法（IL-ISOMAP）

在ISOMAP算法中，其時(shí)間復(fù)雜度主要來源于最短路徑的計(jì)算和特征值分解。若采用Floyds算法計(jì)算最短路徑，其時(shí)間復(fù)雜度為O(n3)，若采用Dijkstras算法為O(kn2logn)，而MDS特征值分解的時(shí)間復(fù)雜度為O(n3)。當(dāng)輸入數(shù)據(jù)量n過大時(shí)，算法時(shí)間復(fù)雜度指數(shù)級增長，ISOMAP會出現(xiàn)計(jì)算瓶頸，故改進(jìn)ISOMAP算法多從減少最短路徑和特征值分解的計(jì)算量入手。本文提出了一種基于地標(biāo)點(diǎn)選擇的改進(jìn)ISOMAP算法。

3.1 地標(biāo)點(diǎn)的選擇

文獻(xiàn)[11]指出流形局部線性區(qū)域的數(shù)據(jù)點(diǎn)或靠近該區(qū)域的點(diǎn)可以互相用其鄰域內(nèi)的點(diǎn)進(jìn)行表示，因此鄰域圖中相連的數(shù)據(jù)點(diǎn)具有相似的測地距離。地標(biāo)點(diǎn)的選擇原則是盡可能用較少的地標(biāo)點(diǎn)去表示輸入數(shù)據(jù)較多的特征。基于此，本文提出了一種新的地標(biāo)點(diǎn)選擇策略，即選取互不相鄰的數(shù)據(jù)點(diǎn)集合作為地標(biāo)點(diǎn)。

設(shè)N={N1,N2,…,Nn}為鄰域點(diǎn)的集合，其中Ni為xi鄰域內(nèi)的數(shù)據(jù)點(diǎn)的集合。設(shè)C=X={x1,x2,…,xn}為初始的地標(biāo)點(diǎn)集合，如果xi是xj的近鄰點(diǎn)（i≠j），則從集合N中移除xj，從集合C中移除xi，此時(shí)C中所有點(diǎn)的鄰域都不包含xj，在輸入數(shù)據(jù)X上執(zhí)行該操作，可以得到互不為鄰接點(diǎn)的地標(biāo)點(diǎn)集合。該地標(biāo)點(diǎn)選擇策略偽碼可以描述為：

（1）C=X={x1,x2,…,xn}

（2）N={N1,N2,…,Nn}

（3）for i=x1:xn

（4） for j=N1:Nn

（5） if xi∩Nj非空

（6） 從N中刪除xj

（7） end

（8）從C中刪除xi

（9）end

（10）最終得到的C即為地標(biāo)點(diǎn)集合

3.2 算法描述

本文改進(jìn)的ISOMAP算法包括地標(biāo)點(diǎn)的選擇、基于MDS的地標(biāo)點(diǎn)d維嵌入，基于LMDS[8]（Landmark MDS）的其余點(diǎn)d維嵌入，具體描述為：

（1）構(gòu)建鄰域圖G，根據(jù)2.1所提地標(biāo)點(diǎn)選擇策略選取地標(biāo)點(diǎn)，設(shè)其個(gè)數(shù)為p。

（2）計(jì)算測地距離矩陣Dp,p和Dp,n。

（3）對于地標(biāo)點(diǎn)，將MDS算法應(yīng)用到測地距離矩陣Dp,p，構(gòu)建地標(biāo)點(diǎn)的d維嵌入；對于其余點(diǎn)，將LMDS算法應(yīng)用到測地距離矩陣Dp,n，構(gòu)建其余點(diǎn)的d維嵌入。最終得到數(shù)據(jù)X的d維嵌入Y。

3.3 算法性能分析

為檢驗(yàn)本文所提IL-ISOMAP算法的有效性，本文在Swiss Roll數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，從地標(biāo)點(diǎn)的分布、數(shù)量、算法效率和準(zhǔn)確性方面進(jìn)行分析，并與具有代表性的Fast-ISOMAP算法[9]進(jìn)行比較。

圖1為當(dāng)Swiss Roll數(shù)據(jù)集的數(shù)據(jù)點(diǎn)取2000，IL-ISOMAP和Fast-ISOMAP算法地標(biāo)點(diǎn)（圓圈圈出的點(diǎn)）的分布，由圖1可知，IL-ISOMAP算法選取的地標(biāo)點(diǎn)數(shù)量更為稀疏分布更為均勻。

圖1 地標(biāo)點(diǎn)的分布

圖2為不同數(shù)據(jù)點(diǎn)下IL-ISOMAP和Fast-ISOMAP算法地標(biāo)點(diǎn)數(shù)量的比較，由圖2可知，IL-ISOMAP算法的地標(biāo)點(diǎn)數(shù)量要比Fast-ISOMAP算法少得多，且隨輸入數(shù)據(jù)的增長速度緩慢，這意味著IL-ISOMAP算法的效率比Fast-ISOMAP算法高，該結(jié)論也可從圖3中得到驗(yàn)證。圖3為ISOMAP、Fast-ISOMAP、IL-ISOMAP算法計(jì)算輸入數(shù)據(jù)二維嵌入的時(shí)間，可以得出IL-ISOMAP算法的效率最高。

圖2 不同算法地標(biāo)點(diǎn)數(shù)比較

圖3 不同算法計(jì)算時(shí)間比較

文獻(xiàn)[4]指出用殘差評價(jià)算法低維嵌入的質(zhì)量，殘差越小降維效果越好。圖4為三種算法降維的殘差曲線，由圖4可知，三種算法的殘差曲線基本重合，說明IL-ISOMAP在提高算法效率的同時(shí)沒有犧牲太多的準(zhǔn)確性。

圖4 不同算法殘差曲線比較

4 手寫數(shù)據(jù)的非線性結(jié)構(gòu)分析

本文選取了MINIST、USPS和LETTER三個(gè)手寫數(shù)據(jù)集進(jìn)行非線性結(jié)構(gòu)分析，探索其本征維度并進(jìn)行三維聚類可視化。

4.1 手寫數(shù)據(jù)集

三種手寫數(shù)據(jù)集的簡要介紹如下：

（1）MINIST數(shù)據(jù)集包含60000張28×28的手寫數(shù)字圖片，手寫數(shù)字包括0～9共10個(gè)類。

（2）USPS數(shù)據(jù)集包括9298張16×16的手寫數(shù)字灰度圖片，手寫數(shù)字包括0～9共10個(gè)類。

（3）LETTER數(shù)據(jù)集包含20000個(gè)由16個(gè)屬性描述的大寫英文字母，手寫字母包括A～Z共26個(gè)類。

4.2 本征維度估計(jì)

數(shù)據(jù)降維應(yīng)盡可能保持原高維數(shù)據(jù)的內(nèi)在特征，故降維的維數(shù)至關(guān)重要，能夠準(zhǔn)確描述數(shù)據(jù)特征的最小維度稱為數(shù)據(jù)的本征維度[11]。本征維度可以通過殘差曲線的“拐點(diǎn)”對應(yīng)的維度進(jìn)行估計(jì)。圖5、圖6和圖7分別為IL-ISOMAP算法對三個(gè)手寫數(shù)據(jù)集降維的殘差曲線，由圖可估計(jì)出中MINIST中高維數(shù)據(jù)的本征維度為24，USPS中高維數(shù)據(jù)的本征維度為24，LETTER中高維數(shù)據(jù)的本征維度為5。

圖5 MINIST數(shù)據(jù)殘差曲線

圖6 USPS數(shù)據(jù)殘差曲線

圖7 LETTER數(shù)據(jù)殘差曲線

在手寫數(shù)據(jù)識別相關(guān)的領(lǐng)域，由于手寫數(shù)據(jù)集通常具有高維特征，使得直接分析這些數(shù)據(jù)非常困難，研究者可以將原始數(shù)據(jù)降維至其本征維度空間進(jìn)行預(yù)處理。

4.3 聚類可視化

可視化是分析數(shù)據(jù)內(nèi)部結(jié)構(gòu)的重要工具，本文將ILISOMAP算法應(yīng)用于三個(gè)手寫數(shù)據(jù)集進(jìn)行可視化處理。在手寫數(shù)據(jù)原始的高維空間，相同類的手寫數(shù)據(jù)具有相似的表示，故在其低維嵌入空間，相同的類應(yīng)聚集在一起。為了得到更好的可視化效果，本文選取部分類進(jìn)行展示，如圖8所示，可以得出IL-ISOMAP算法在降維的同時(shí)可以進(jìn)行很好的聚類，保留高維數(shù)據(jù)的內(nèi)在結(jié)構(gòu)。

圖8 手寫數(shù)據(jù)集可視化

5 結(jié)語

本文提出了一種互不為鄰接點(diǎn)的地標(biāo)點(diǎn)選擇策略，在此基礎(chǔ)上，改進(jìn)了ISOMAP算法，并將改進(jìn)算法IL-ISOMAP應(yīng)用于手寫數(shù)據(jù)的非線性結(jié)構(gòu)分析中，探索出MINIST、USPS和LETTER三個(gè)手寫數(shù)據(jù)集的本征維度和內(nèi)在結(jié)構(gòu)，這也為其他高維數(shù)據(jù)的分析和處理提供了有效參考。