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

關(guān)鍵詞： 維數(shù)約簡；監(jiān)督分類；樣本外點問題

0 引言

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

　　在高維數(shù)據(jù)降維方面，目前使用的降維方法可分兩大類：線性降維和非線性降維。比較有代表性的線性降維方法有：投影尋蹤（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]、無監(jiān)督判別映射（Unsupervised Discriminant Projection，UDP）[8]等。常見的非線性降維方法包括：局部線性嵌入（Locally linear Embedding，LLE）[9]、等距映射（Isometric Mapping，ISOMap）[10]、黎曼流形學(xué)習(xí)（Riemannian Manifold Learning，RML）[11]、多流形（Multiple Manifolds，MM）[12]、層次流形學(xué)習(xí)（Hierarchical Manifold Learning，HML）[13]等。

1 典型線性降維算法

　　1.1 LDA

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

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

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

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

　　1.2 PCA

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

　　（1）計算所有訓(xùn)練樣本的均值向量：

　　（2）計算所有訓(xùn)練樣本的協(xié)方差矩陣W：

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

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

　　2 典型非線性降維算法

　　2.1 ISOMap

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

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

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

　　（3）應(yīng)用經(jīng)典的MDS算法計算出低維嵌入。

　　2.2 LLE

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

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

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

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

3 實驗

　　3.1 數(shù)據(jù)數(shù)據(jù)與評價策略

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

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

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

　　3.2 實驗結(jié)果與分析

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

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

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

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

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

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

4 結(jié)論

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

　　參考文獻

　　[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.