基于改進(jìn)局部切空間排列的流形學(xué)習(xí)算法

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

?

基于改進(jìn)局部切空間排列的流形學(xué)習(xí)算法

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

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

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

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

1 引言

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

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

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

2 LTSA算法及其局限性

即

圖1給出了對Swiss roll數(shù)據(jù)進(jìn)行稠密采樣(2000個樣本點)和稀疏采樣(400個樣本點)后運(yùn)行LTSA算法的2維嵌入結(jié)果。比較圖1(b)和圖1(d)可以看出，稠密采樣條件下LTSA算法能夠較好地保持原始數(shù)據(jù)的拓?fù)鋷缀谓Y(jié)構(gòu)，而稀疏采樣下的低維嵌入結(jié)果則較為雜亂，無法反映數(shù)據(jù)的幾何結(jié)構(gòu)。

圖1 LTSA算法的低維嵌入結(jié)果

3 改進(jìn)的局部切空間排列算法

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

3.1 基于L1范數(shù)的切空間估計方法

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

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

為進(jìn)一步提高性能，本節(jié)提出一種精細(xì)的切空間估計方法：(1)考慮到鄰域內(nèi)各點的切空間不一致，取當(dāng)前樣本而非鄰域均值作為切空間中心；(2)考慮到鄰域內(nèi)各點對切空間估計的貢獻(xiàn)不一致，從距離和結(jié)構(gòu)兩個因素進(jìn)行加權(quán)。據(jù)此，本文提出求解投影矩陣的目標(biāo)函數(shù)為

表1 干擾點的權(quán)值

3.2 基于流形結(jié)構(gòu)的加權(quán)排列方法

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

對式(9)作進(jìn)一步推導(dǎo)，有

圖2 切空間估計示例

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

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

4.1 人造數(shù)據(jù)實驗

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

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

4.2 真實數(shù)據(jù)實驗

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

4.3 計算效率分析

圖3 Swiss roll數(shù)據(jù)的2維嵌入結(jié)果

圖4 Punctured Sphere數(shù)據(jù)的2維嵌入結(jié)果

圖5 ISOFACE數(shù)據(jù)的2維嵌入結(jié)果

圖6 LLEFACE數(shù)據(jù)的2維嵌入結(jié)果

5 結(jié)束語

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

[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]. 測繪學(xué)報, 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] 張強(qiáng), 戚春, 蔡云澤. 基于判別改進(jìn)局部切空間排列特征融合的人臉識別方[J]. 電子與信息學(xué)報, 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年生，博士生，研究方向為模式識別、機(jī)器學(xué)習(xí).

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

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

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改回

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