摘  要： 對ISOMap、LDA、LLE、PCA這4種典型降維算法的主要思想和算法步驟進行了詳細分析，并將它們用于有監督分類。從實驗結果分析得到結論，其可為有監督分類提供有益的借鑒。

關鍵詞： 維數約簡；監督分類；樣本外點問題

0 引言

　　隨著信息技術和空間技術的快速發展，人類每天都可以獲得海量的數據，很多數據往往都是高維的，例如生物基因序列分析、高光譜遙感圖像處理等領域所要處理的數據。而高維數據難以被人理解、表示和處理[1]，降維是解決問題的一個可行途徑。近年來，降維已經成為信息處理領域的一個研究熱點。

　　在高維數據降維方面，目前使用的降維方法可分兩大類：線性降維和非線性降維。比較有代表性的線性降維方法有：投影尋蹤（Projection Pursuit，PP）[2]、主成分分析（Principal Component Analysis，PCA）[3]、多維尺度變化（MultiDimensional Scaling，MDS）[4]、獨立成分分析（Independent Component Analysis，ICA）[5]、線性判別分析（Linear Discriminant Analysis，LDA）[6]、邊際Fisher分析（Marginal Fisher Analysis，MFA）[7]、無監督判別映射（Unsupervised Discriminant Projection，UDP）[8]等。常見的非線性降維方法包括：局部線性嵌入（Locally linear Embedding，LLE）[9]、等距映射（Isometric Mapping，ISOMap）[10]、黎曼流形學習（Riemannian Manifold Learning，RML）[11]、多流形（Multiple Manifolds，MM）[12]、層次流形學習（Hierarchical Manifold Learning，HML）[13]等。

1 典型線性降維算法

　　1.1 LDA

　　LDA的基本思想是利用樣本的類別標簽信息，通過對樣本集（X1，X2，…，Xk，…，XN）的總類內散布矩陣和總類間散布矩陣這兩個帶有類標簽信息的統計量計算廣義特征值，得到相應的映射矩陣，最后通過映射矩陣將樣本從高維空間映射到低維空間。LDA算法的核心是廣義特征值分解。不妨用N表示訓練樣本總數，num為類別總數，第k類樣本的樣本總數為Nk，Xk表示第k類訓練樣本特征向量的均值，X表示所有訓練樣本特征向量的均值，X（k）j表示第k類中的第j個樣本，LDA的計算步驟如下[6]：

　　（1）計算第k類樣本的協方差矩陣：

　　變化矩陣W的d個列向量由廣義特征方程最大的d個廣義特征值λ1≥λ2≥…≥λd所對應的廣義特征向量w1，w2，…，wd組成，即W=[w1，w2，…，wd]。

　　（5）根據公式Yn=（W*）TXn，計算出訓練樣本Xn的低維嵌入Yn，其中T表示矩陣的轉置，1≤n≤N。

　　1.2 PCA

　　PCA在標準正交變換的基礎上進行降維，基本思想是對樣本的散布矩陣進行特征值分解。用N表示訓練樣本的總數，訓練樣本為（X1，X2，…，Xk，…，XN），映射變化后的低維嵌入維數為d，PCA算法的主要步驟如下[3]：

　　（1）計算所有訓練樣本的均值向量：

　　（2）計算所有訓練樣本的協方差矩陣W：

　　（3）計算協方差矩陣W的特征值和特征向量，并對特征值從大到小排序；

　　（4）選擇最大的d個特征值λ1≥λ2≥…≥λd對應的特征向量w1，w2，…，wd組成變換矩陣W*，即W*=[w1，w2，…，wd]，根據公式Yn=（W*）TXn，計算出訓練樣本Xn的低維嵌入Yn，其中1≤n≤N。

　　2 典型非線性降維算法

　　2.1 ISOMap

　　ISOMap算法的基本思想是離得很近的兩個點之間的測地線距離用歐氏距離來代替，離得較遠的兩個點之間的測地線距離用最短路徑距離來代替，然后用經典的MDS算法計算出低維嵌入坐標。ISOMap算法的主要步驟如下[10]：

　　（1）構造局部鄰域。用N表示訓練樣本總數，對數據集X={x1，x2，…，xN}計算任意兩個樣本點xi和xj之間的歐式距離dx（xi，xj），為每個樣本點尋找出k個近鄰點，將互為近鄰的樣本點用線段連接起來得到鄰接圖G。

　　（2）計算最短距離。在圖G中，設任意兩個樣本點xi和xj之間的最短距離為dG（xi，xj）。若xi和xj之間存在連線，則dG（xi，xj）的初始值為dx（xi，xj），否則令dG（xi，xj）=∞。對所有的k=1，2，…，N，根據dG（xi，xj）=min{dG（xi，xj），dG（xi，xk）+dG（xk，xj）}，計算出最短距離dG（xi，xj），最后得到距離矩陣DG={dG（xi，xj）}。

　　（3）應用經典的MDS算法計算出低維嵌入。

　　2.2 LLE

　　LLE算法的基本思想是流形在很小的局部鄰域上可以看成局部線性的，可將每個高維數據點用若干個近鄰點的線性組合來近似表示，通過計算重構權值矩陣進行降維，將高維流形上的近鄰點映射到低維空間。LLE算法的主要計算步驟如下[9]：

　　（1）尋找每個樣本點的k個近鄰點。

　　（2）定義重構誤差min（W）=（xp-wjpxpj）2，其中N表示訓練樣本總數，xpj表示樣本點xp的第j個近鄰點，wjp表示重構權值，同一個樣本點xj的k個近鄰的重構權值的和滿足wjp=1。根據重構誤差最小原則，利用最小二乘法計算出重構權值矩陣W。

　　（3）根據重構權值矩陣W，計算矩陣M=（I-W）T（I-W）的特征值和特征向量，其中I表示單位矩陣。將特征值從小到大排列，通常取最小的d個非零特征值對應的特征向量作為LLE最終的低維嵌入。

3 實驗

　　3.1 數據數據與評價策略

　　為了對比上述4種降維方法的分類性能，采用參考文獻[14]中的遙感影像SPOT 5進行分類實驗，影像原圖和分類參考圖如圖1所示。實驗中選取了4類土地覆蓋類型進行分類，分類前先對SPOT 5影像進行多尺度分割。參考文獻[15]計算出81維特征。在實驗區域中隨機選取對象，其中農村宅基地選取了32個對象，河流選取了28個對象，灌溉水田選取了56個對象，養殖水面選取了72個對象。通過2折交叉驗證比較4種降維算法的分類性能。

　　ISOMap、LDA、LLE、PCA這4種降維算法只是對訓練樣本的高維特征進行降維，對于測試樣本的低維嵌入應該如何計算，并沒有提供有效的解決途徑。對于LDA和PCA，本文采用在訓練樣本的基礎上計算得到的映射矩陣計算測試樣本的低維嵌入；對于ISOMap和LLE，采用流形學習中經典的Non-parametric mapping[16]計算測試樣本的低維嵌入。實驗中所采用的分類器為1NN，并根據總體精度（Overall Accuracy，OA）對算法的分類性能進行評估，OA的計算公式如下：

　　其中，N表示訓練樣本的總數，mkk表示第k類訓練樣本中正確分類的個數，num表示訓練樣本的類別總數。

　　3.2 實驗結果與分析

　　在ISOMap、LDA、LLE、PCA這4種算法的分類實驗中，降維后的特征維數分別取2、5、8、10、15、20、25、30，取這8個結果的平均值作為相應算法在區間[2，30]的平均分類精度。由于近鄰個數對ISOMap、LLE算法的分類性能有較大影響，在ISOMap、LLE的實驗中重點對比了不同的近鄰個數2、4、6、8、10、12對算法性能的影響。對LDA和PCA而言，由于不存在近鄰個數，因此在LDA和PCA的分類實驗中重點對比了不同歸一化方式對算法分類性能的影響。4種算法的分類結果如圖2所示。

　　ISOMap不同近鄰個數得到的分類精度如圖2（a）所示。當近鄰個數取4時ISOMap的平均OA最高為33.85%，近鄰個數取4時的最高OA為55.32%。

　　LDA不同歸一化方式得到的分類結果如圖2（b）所示。當LDA歸一化到區間[0，1]時得到的平均OA為48.01%，最高OA為52.7%；而當LDA歸一化到[-1，1]區間時平均OA為40.16%，最高OA為48.94%。很明顯，當LDA歸一化到[0，1]區間時分類性能會更好一些。

　　LLE不同近鄰個數得到的分類精度如圖2（c）所示，當近鄰個數取4時LLE的平均OA最高為45.22%，近鄰個數取4時的最高OA為64.9%。

　　PCA算法不同的歸一化方式得到的分類精度如圖2（d）所示。當高維特征歸一化到[0，1]區間時，PCA的平均OA為66.59%，最高OA為73.99%；而當歸一化到 [-1，1]區間時，PCA的平均OA為66.96%，最高OA為72.87%。可以看出，無論是平均OA還是最高OA，兩種歸一化方式對PCA的分類結果影響并不大。

　　可以看出，就平均OA而言，PCA的分類性能最好，ISOMap算法的OA最低，4種降維算法的平均OA均達不到70%，換句話說，ISOMap、LDA、LLE、PCA這4種算法直接用于監督分類的效果并不好。分析其中的原因，一方面是因為在降維過程中樣本的類別標簽信息并沒有得到充分利用，計算得到的低維嵌入與分類并沒有密切的聯系；另一方面是因為4種降維算法并沒有提供一種有效途徑來解決樣本外點學習問題。

4 結論

　　本文詳細分析了ISOMap、LDA、LLE、PCA這4種降維算法的主要思想和算法步驟并將它們用于有監督分類。在降維過程中，樣本的類別標簽信息是否得到充分利用會在很大程度上影響到低維嵌入的可區分性。另一方面，樣本外點學習問題是降維方法用于有監督分類時必須要妥善解決的一個問題，該問題能否很好解決將在很大程度上影響到降維方法在有監督分類中的應用。

　　參考文獻

　　[1] ANIL K J， ROBERT P W  D， Mao Jianchang. Statistical pattern recognition： a review[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2000，21（1）：4-37.

　　[2] HUBER P J. Projection pursuit[J]. Annals of Statistics， 1985， 13（2）： 435-475.

　　[3] JOLLIFFE I T. Principle component analysis[M]. Springer， 1986.

　　[4] THOMAS L G， MICHAEL L K. A multidimensional scaling approach to mental multiplication [J]. Memory & Congnition， 2002， 30（1）：97-106.

　　[5] COMON P. Independent component analysis： a new concept[J]. Signal Processing， 1994， 36（3）：287-314.

　　[6] FUKUNNAGA K. Intoduction to statistical pattern recogni-tion[M]. Academic Press， second edition， 1991.

　　[7] Yan Shuicheng， Xu Dong， Zhang Benyu， et al. Graph embedding and extensions：a general framework for dimensionality reduction[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2007， 29（1）：40-51.

　　[8] Yang Jian， ZHANG D. Globally maximizing， locally minimizing： unsupervised discriminant projection with applications to face and palm biometrics[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2007，29（4）： 650-664.

　　[9] ROWEIS S， SAUL L. Nonlinear dimensionality reduction by locally linear embedding[J]. Science， 2000， 290：2323-2326.

　　[10] TENENBAUM J B， SILVA V， LANGFORD J C. A global geometric framework for nonlinear dimensionality reduction[J]. Science， 2000， 290：2319-2323.

　　[11] Lin Tong， Zha Hongbin. Riemannian manifold learning[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2008，30（5）：796-809.

　　[12] Xiao Rui， Zhao Qijun， ZHANG D， et al. Facial expression recognition on multiple manifolds [J]. Pattern Recognition， 2011， 44 （1）：107-116.

　　[13] Huang Hongbing， Hong Huo， Fang Tao. Hierarchical manifold learning with applications to supervised classification for high resolution remotely sensed images[J]. IEEE Transactions on Geoscience and Remote Sensing，2014，52（3）：1677-1692.

　　[14] Qing Jianjun， Huo Hong， Fang Tao. Supervised classification of multispectral remote sensing images based on the nearest reduced convex hull approach[J]. Journal of Applied Remote Sensing， 2009（3）：1-18.

　　[15] Chen Xi， Fang Tao， Huo Hong， et al. Graph-based feature selection for object-oriented classification in VHR airborne imagery[J]. IEEE Transactions on Geoscience and Remote Sensing， 2011， 49（1）： 353-365.

　　[16] SAUL L K， ROWEIS S T. Think globally， fit locally： unsupervised learning of low dimensional manifolds[J]. Journal of Machine Learning Research， 2003（4）：119-155.