基于改進ISOMAP算法的手寫數據非線性結構分析

郭愛心

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

1 引言

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

2 ISOMAP算法

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

（1）通過k近鄰或固定閾值的方法構建數據點的鄰域圖G，鄰域圖中的每條邊的權重為d(xi,xj)。

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

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

3 改進ISOMAP算法（IL-ISOMAP）

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

3.1 地標點的選擇

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

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

（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即為地標點集合

3.2 算法描述

本文改進的ISOMAP算法包括地標點的選擇、基于MDS的地標點d維嵌入，基于LMDS[8]（Landmark MDS）的其余點d維嵌入，具體描述為：

（1）構建鄰域圖G，根據2.1所提地標點選擇策略選取地標點，設其個數為p。

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

（3）對于地標點，將MDS算法應用到測地距離矩陣Dp,p，構建地標點的d維嵌入；對于其余點，將LMDS算法應用到測地距離矩陣Dp,n，構建其余點的d維嵌入。最終得到數據X的d維嵌入Y。

3.3 算法性能分析

為檢驗本文所提IL-ISOMAP算法的有效性，本文在Swiss Roll數據集上進行實驗，從地標點的分布、數量、算法效率和準確性方面進行分析，并與具有代表性的Fast-ISOMAP算法[9]進行比較。

圖1為當Swiss Roll數據集的數據點取2000，IL-ISOMAP和Fast-ISOMAP算法地標點（圓圈圈出的點）的分布，由圖1可知，IL-ISOMAP算法選取的地標點數量更為稀疏分布更為均勻。

圖1 地標點的分布

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

圖2 不同算法地標點數比較

圖3 不同算法計算時間比較

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

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

4 手寫數據的非線性結構分析

本文選取了MINIST、USPS和LETTER三個手寫數據集進行非線性結構分析，探索其本征維度并進行三維聚類可視化。

4.1 手寫數據集

三種手寫數據集的簡要介紹如下：

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

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

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

4.2 本征維度估計

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

圖5 MINIST數據殘差曲線

圖6 USPS數據殘差曲線

圖7 LETTER數據殘差曲線

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

4.3 聚類可視化

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

圖8 手寫數據集可視化

5 結語

本文提出了一種互不為鄰接點的地標點選擇策略，在此基礎上，改進了ISOMAP算法，并將改進算法IL-ISOMAP應用于手寫數據的非線性結構分析中，探索出MINIST、USPS和LETTER三個手寫數據集的本征維度和內在結構，這也為其他高維數據的分析和處理提供了有效參考。