基于改進局部切空間排列的流形學習算法

杜 春 鄒煥新 孫即祥 周石琳 趙晶晶

?

基于改進局部切空間排列的流形學習算法

杜 春*鄒煥新 孫即祥 周石琳 趙晶晶

(國防科學技術大學電子科學與工程學院 長沙 410073)

局部切空間排列是一種廣受關注的流形學習算法，其具備實現簡單、全局最優等特點，但其難以有效處理稀疏采樣或非均勻分布的高維觀測數據。針對這一問題，該文提出一種改進的局部切空間排列算法。首先，提出一種基于L1范數的局部切空間估計方法，由于同時考慮了距離和結構因素，該方法得到的切空間較主成分分析方法更為準確。其次，在坐標排列步驟為了減小排列誤差，設計了一種基于流形結構的加權坐標排列方案，并給出了具體的求解方法。基于人造數據和真實數據的實驗表明，該算法能夠有效地處理稀疏和非均勻分布的流形數據。

模式識別；流形學習；降維；局部切空間排列(LTSA)；L1范數

1 引言

降維是當前模式識別、機器學習等領域的研究熱點，其算法大致可以分為線性降維和非線性降維兩類。線性降維以主成分分析(Principal Component Analysis, PCA)[1]和多維尺度(Multi-Dimensional Scaling, MDS)變換[2]為代表，其一般假設觀測數據具有線性結構或滿足高斯分布，通過定義不同的準則函數來尋求最佳線性模型，將高維數據投影到線性子空間完成降維。非線性降維以流形學習為主要代表，其假設數據位于或接近于一個或多個光滑流形，通過保持數據隱含的幾何拓撲結構來進行降維。相比于線性降維，非線性降維算法在處理非線性結構數據時更具優勢。

作為一種典型的非線性流形學習算法，局部切空間排列(Local Tangent Space Alignment, LTSA)[3]算法思想直觀，實現方便，并且能處理非凸流形，在高維數據可視化[4]、基因數據分析[5]、人臉識別[6,7]、遙感圖像分類[8,9]等方面取得了成功應用。然而，由于對處理數據的要求較高(數據稠密，滿足均勻分布并呈局部線性)，以及對數據的曲率和噪聲敏感，LTSA算法在實際應用中受到很大限制。為了彌補LTSA算法的不足，若干學者從不同角度對算法進行了擴展和改進。文獻[10]基于迭代加權PCA提出一種改進算法，提高了LTSA的抗噪性能。文獻[11]考慮LTSA算法的自適應局部鄰域構造和全局嵌入誤差最小化問題，提高了LTSA算法的自適應學習能力。文獻[12]將LTSA算法進行監督化擴展，使其能夠更好地適用于模式識別問題。最近，Zhang等人[13]提出一種逼近流形切空間的加權PCA方法并將其應用于LTSA，有效提高了算法處理稀疏采樣數據的能力。然而，由于僅僅考慮鄰域樣本間的距離因素而沒有顧及流形本身的結構，該方法估計的切空間并不穩定，對參數的變化也較為敏感。

為了進一步提高流形學習處理稀疏采樣或非均勻分布數據的能力，本文提出一種改進的局部切空間排列(Modified Local Tangent Space Alignment, MLTSA)算法。本文章節安排如下：第2節簡述LTSA算法及其局限性；第3節對局部切空間估計和局部坐標排列兩個問題進行研究，提出MLTSA算法；第4節通過人工數據和實際數據的實驗驗證算法的有效性；第5節是結束語。

2 LTSA算法及其局限性

即

圖1給出了對Swiss roll數據進行稠密采樣(2000個樣本點)和稀疏采樣(400個樣本點)后運行LTSA算法的2維嵌入結果。比較圖1(b)和圖1(d)可以看出，稠密采樣條件下LTSA算法能夠較好地保持原始數據的拓撲幾何結構，而稀疏采樣下的低維嵌入結果則較為雜亂，無法反映數據的幾何結構。

圖1 LTSA算法的低維嵌入結果

3 改進的局部切空間排列算法

鑒于LTSA算法的不足，MLTSA算法考慮從以下方面來對其進行改進：(1)在局部切空間估計方面，針對經典PCA方法估計不夠精細以及文獻[13]中方法對參數敏感的缺陷，提出一種基于L1范數的精細切空間估計方法；(2)在局部坐標排列方面，考慮各個樣本點對局部流形結構的貢獻，通過對坐標排列進行加權來減小流形嵌入誤差。

3.1 基于L1范數的切空間估計方法

3.1.1目標函數 在利用PCA估計切空間時，通常采用奇異值分解算法進行計算，即將式(1)轉化為如式(3)的等價問題

采用式(4)估計切空間可以有效克服噪聲數據的干擾。然而，當局部鄰域樣本分布較為稀疏且不滿足局部線性要求時，該方法仍不夠精細，主要體現在：(1)該方法將樣本均值作為切空間中心并假設鄰域內所有樣本點的切空間完全一致，這與真實的切空間分布情況不符；(2)該方法在最大化L1范數離差之和時平等對待每一個樣本，沒有考慮各個樣本點處的流形結構。

為進一步提高性能，本節提出一種精細的切空間估計方法：(1)考慮到鄰域內各點的切空間不一致，取當前樣本而非鄰域均值作為切空間中心；(2)考慮到鄰域內各點對切空間估計的貢獻不一致，從距離和結構兩個因素進行加權。據此，本文提出求解投影矩陣的目標函數為

表1 干擾點的權值

3.2 基于流形結構的加權排列方法

對于非均勻分布或稀疏采樣數據，局部鄰域中各個樣本處的幾何結構(例如曲率)不完全相同，各個樣本引起的坐標排列誤差也存在較大差異。因此，為了進一步減小全局排列誤差，本文設計基于流形結構的加權排列方法。

對式(9)作進一步推導，有

圖2 切空間估計示例

4 實驗結果與分析

為了驗證MLTSA算法的有效性，分別對人造數據和實際數據進行實驗，并與LTSA和文獻[13]方法進行比較。實驗中采用Dijkstra方法來計算點對之間的測地線距離[17]，軟件環境為Matlab 7.8.0，配置平臺為Intel Pentium CPU 2.5 GHz, 2 GB RAM。

4.1 人造數據實驗

首先，選用流形學習基準數據集Swiss roll來驗證MLTSA算法處理稀疏采樣數據的性能。對于Swiss roll數據，現有文獻通常使用800個以上的樣本來進行實驗。不同于此，本文僅采用如圖1(c)所示的400個樣本進行測試，圖3給出了對應的2維嵌入結果。由實驗結果可以看出，在樣本稀疏的情況下，LTSA算法在降維后難以準確保持數據的幾何拓撲結構。文獻[13]方法降維性能優于LTSA，但是其對鄰域參數和熱核參數很敏感。本文的MLTSA算法由于估計的切空間更為準確，排列誤差更小，因此能夠較好地保持高維數據的幾何拓撲結構。同時，MLTSA算法對參數變化不敏感，因而具有更好的適應性。此外，本文還在文獻[13]方法中利用3.1.2節所提權值代替熱核權值進行了測試，實驗結果如圖3(d), 3(i), 3(n)所示。通過比較可以看出，在取相同鄰域參數時，本文所提權值在局部幾何結構保持方面優于熱核權值。然而，由于在全局坐標排列時沒有考慮樣本點對流形結構的貢獻，文獻[13]方法使用這兩種權值的全局排列效果均不如MLTSA算法(如圖3(e), 3(j), 3(o)所示)。

其次，選用Punctured Sphere數據來驗證MLTSA算法處理非均勻分布數據的性能。Punctured Sphere數據來自于對球面的采樣，沿著經線采樣數據的密度不斷發生變化，呈現北部稠密南極稀疏的特點。圖4給出了數據的2維嵌入結果，其中算法參數=10,=5。由實驗結果可以看出，LTSA和文獻[13]方法傾向于將樣本往原本“稠密”的區域嵌入，MLTSA算法根據樣本對流形結構的貢獻進行加權處理，即使在非均勻分布的區域也能較好地保持流形的幾何結構。

4.2 真實數據實驗

為了驗證MLTSA算法在真實高維數據上的性能，采用ISOFACE[17]和LLEFACE[18]人臉圖像數據來進行測試。ISOFACE數據共含698幅圖像，每幅圖像分辨率為64×64，呈現不同姿態和光照的變化。LLEFACE數據共含1965幅圖像，每幅圖像分辨率為28×20，呈現不同表情的變化。實驗中，首先從ISOFACE數據和LLEFACE數據中隨機抽取500幅圖像構成稀疏采樣數據，然后將每幅圖像按列連接轉化為一個列向量，分別構成4096維和560維的數值矩陣，最后使用MLTSA算法將數據映射到2維平面。實驗中設置參數=5。圖5和圖6分別給出了ISOFACE和LLEFACE的2維嵌入結果。在圖5中，左側、右側和下側的人臉圖像分別對應圖中用折線、和連接的圓圈圈起的坐標點。觀察可以看出，降維后的ISOFACE人臉圖像從左到右，從上到下呈現明顯的朝向變化，從上到下呈現明顯的光照變化。在圖6中，右側的人臉圖像對應圖中用折線連接的圓圈圈起的坐標點。觀察圖6可以看出，降維后的LLEFACE人臉圖像從右上到左下呈現明顯的表情變化(由悲傷到高興)。兩組實驗表明，MLTSA算法在樣本較為稀疏且非均勻分布的情況下仍然可以較好地挖掘數據內在的幾何結構。

4.3 計算效率分析

圖3 Swiss roll數據的2維嵌入結果

圖4 Punctured Sphere數據的2維嵌入結果

圖5 ISOFACE數據的2維嵌入結果

圖6 LLEFACE數據的2維嵌入結果

5 結束語

本文研究了稀疏采樣和非均勻分布數據的流形學習問題，提出一種改進的局部切空間排列算法。該算法針對現有算法的不足，從影響LTSA算法性能的兩個因素入手，提出了更為精細的局部切空間估計方法和誤差更小的加權坐標排列方法。實驗表明，改進的局部切空間排列算法對人造數據和真實數據進行降維，能夠較好地保持數據的內在幾何結構，并且對鄰域參數的變化不敏感，算法有效且穩健。需要指出的是，當樣本維數過高時，本文求解局部切空間的耗時較長，如何對其加速還有待進一步研究。此外，將本文方法進行監督擴展并應用于小樣本條件下的分類問題，也是潛在的研究方向。

[1] Jolliffe I T. Principal Component Analysis[M]. Second Edition, New York: Springer-Verlag, 2002: 1-10.

[2] Cox T F and Cox M A. Multidimensional Scaling[M]. London: Chapman & Hall, 2001: 1-5.

[3] Zhang Zhen-yue and Zha Hong-yuan. Principal manifolds and nonlinear dimensionality reduction via tangent space alignment[J]., 2004, 26(1): 313-338.

[4] Tsai F S. Comparative study of dimensionality reduction techniques for data visualization[J]., 2010, 3(3): 119-134.

[5] Carlotta O and Carlo V. A comparative study of nonlinear manifold learning methods for cancer microarray data classification[J]., 2013, 40(6): 2189-2197.

[6] Li Yong-zhou, Luo Da-yong, Liu Shao-qiang. Orthogonal discriminant linear local tangent space alignment for face recognition[J]., 2009, 72(4): 1319-1323.

[7] Wang Jing, Jiang Wen-xian, and Gou Jin. Extended local tangent space alignment for classification[J]., 2012, 77(1): 261-266.

[8] Ma L, Crawford M M, and Tian J W. Generalised supervised local tangent space alignment for hyperspectral image classification[J]., 2010, 46(7): 497-498.

[9] 石茜, 杜博, 張良培. 一種基于局部判別正切空間排列的高光譜遙感影像降維方法[J]. 測繪學報, 2012, 41(3): 417-420.

Shi Qian, Du Bo, and Zhang Liang-pei. A dimensionality reduction method for hyperspectral imagery based on local discriminative tangent space alignment[J]., 2012, 41(3): 417-420.

[10] Zhan Yu-bin and Yin Jian-ping. Robust local tangent space alignment via iterative weighted PCA[J]., 2011, 74(11): 1985-1993.

[11] Zhang Zhen-yue, Wang Jing, and Zha Hong-yuan. Adaptive manifold learning[J]., 2012, 34(2): 253-265.

[12] 張強, 戚春, 蔡云澤. 基于判別改進局部切空間排列特征融合的人臉識別方[J]. 電子與信息學報, 2012, 34(10): 2396-2401.

Zhang Qiang, Qi Chun, and Cai Yun-ze. Discriminant improved local tangent space alignment feature fusion for face recognition[J].&, 2012, 34(10): 2396-2401.

[13] Zhang Peng, Qiao Hong, and Zhang Bo. An improved local tangent space alignment method for manifold learning[J]., 2011, 32(2): 181-189.

[14] Ke Q and Kanade T. Robust subspace computation using L1 norm[R]. CMU-CS-03-172, Carnegie Mellon University, Technical Report, Aug. 2003.

[15] Kwak N. Principal component analysis based on L1-norm maximization[J]., 2008, 30(9): 1672-1680.

[16] Pang Yan-wei and Yuan Yuan. Outlier-resisting graph embedding[J]., 2010, 73(4): 968-974.

[17] Tenenbaum J B, Silva V D, and Langford J C. A global geometric framework for nonlinear dimensionality reduction[J]., 2000, 290(5500): 2319-2323.

[18] Roweis S T and Saul L K. Nonlinear dimensionality reduction by locally linear embedding[J]., 2000, 290(5500): 2323-2326.

杜 春： 男，1983年生，博士生，研究方向為模式識別、機器學習.

鄒煥新： 男，1973年生，副教授，研究方向為圖形圖像分析與處理.

孫即祥： 男，1946年生，教授，博士生導師，研究方向為計算機視覺與智能信息處理、模式識別、圖像處理.

Manifold Learning Algorithm Based on Modified Local Tangent Space Alignment

Du Chun Zou Huan-xin Sun Ji-xiang Zhou Shi-lin Zhao Jing-jing

(,,410073,)

The Local Tangent Space Alignment (LTSA) is one of the popular manifold learning algorithms since it is straightforward to implementation and global optimal. However, LTSA may fail when high-dimensional observation data are sparse or non-uniformly distributed. To address this issue, a modified LTSA algorithm is presented. At first, a new L1 norm based method is presented to estimate the local tangent space of the data manifold. By considering both distance and structure factors, the proposed method is more accurate than traditional Principal Component Analysis (PCA) method. To reduce the bias of coordinate alignment, a weighted scheme based on manifold structure is then designed, and the detailed solving method is also presented. Experimental results on both synthetic and real datasets demonstrate the effectiveness of the proposed method when dealing with sparse and non-uniformly manifold data.

Pattern recognition; Manifold learning; Dimensionality reduction; Local Tangent Space Alignment (LTSA); L1 norm

TP391.4

A

1009-5896(2014)02-0277-08

10.3724/SP.J.1146.2013.00135

杜春 dc.dd@163.com

2013-01-25收到，2013-11-18改回

國家自然科學基金(40901216)資助課題