基于最小熵的流形學習排列方法

陳 靜，劉 洋

(廣東工業(yè)大學 1.物理與光電工程學院；2.信息工程學院，廣東 廣州 510006)

基于最小熵的流形學習排列方法

陳 靜1，劉 洋2

(廣東工業(yè)大學 1.物理與光電工程學院；2.信息工程學院，廣東 廣州 510006)

提出一種漸進式的排列方法：每次只是排列當前階段交集最大的二個分片的局部坐標.該方法具有以下特點：方法簡單，避免了全局排列方法中大型稀疏矩陣的特征值問題；每次排列都保證是誤差最小的排列；減輕誤差的積累和傳播.

流形學習； 降維； 排列

流形學習作為1種非線性數據降維的方法，受到人們的廣泛關注.經過多年的研究，流形學習已經形成一些有代表性的經典算法，如Isomap[1]、LLE[2-3]及其改進算法[4-6]、LE[7]、HE[8]、LTSA[9]、MVU[10]和Diffusion Map[11]等.流形學習的研究，大都圍繞著這些經典算法而展開.

數學上，1個d維流形就是與d維歐氏空間局部同胚的拓撲空間，即對于流形中的每一點，都存在這個點的1個鄰域，使得該鄰域與d維歐氏空間的1個連通開集同胚.該鄰域稱為流形的1個分片，而與該分片同胚的連通開集稱為分片的局部坐標，或者直接稱為流形的局部坐標.流形中所有點的鄰域的集合構成這個流形的1個開覆蓋.如果流形是緊的，則存在流形中有限個點的鄰域構成流形的有限開覆蓋.根據流形的數學定義，結合數據降維的要求，對于1組從d維流形上采集的N個數據，流形學習的步驟如下：(1) 有限開覆蓋：利用d維流形上采集的N個數據構造流形的有限開覆蓋.(2) 局部同胚：為流形有限開覆蓋中的每個分片尋找它的局部坐標，即d維歐氏空間中與分片同胚的連通開集.(3) 排列：在d維歐氏空間中排列流形的局部坐標，從而得到流形的全局坐標.

本文提出1種新的漸進式的排列方法.在漸進的過程中，這種方法每次只是把在當前階段交集最大的2個分片的局部坐標融合為1個新的局部坐標，代替原來的2個局部坐標.整個排列的過程與霍夫曼最小熵編碼的過程相似,即每次只是把在當前階段概率最小的2個隨機事件合并為1個隨機事件.因此，本文把這種方法稱為最小熵的排列方法(MinimumEntropyAlignment，MEA).

1 流形學習

1.1 流形學習的數學定義

(1) 構造流形M的有限開覆蓋A1,…,AM，也即構造流形M的分片；

(2) 為流形M上的每個分片Ai，在Rd中尋找一個開集Bi，使得Ai與Bi同胚，也即在 Rd中尋找Ai的局部坐標Bi，這里i=1,…,M；

(3) 在Rd中按照分片之間位置的相互關系排列它們的局部坐標，構成流形M的全局坐標.

局部同胚是各種流形共享的唯一數學特征，是高維歐氏空間中的低維流形與低維歐氏空間聯(lián)系的紐帶，是流形數據降維的依據.因此，本文認為，所謂流形學習可以嚴格定義為一種具有局部同胚保持性質的流形數據的降維方法.

1.2 流形學習算法的框架

(1) 有限開覆蓋.

總而言之，流形學習算法在流形學習的這個階段完成流形的有限開覆蓋的構造為

(1)

這里Xn表示流形的1個分片，Kn表示這個分片所包含的數據點的數目，1≤nk≤N，k=1,…,Kn，M≤N表示分片的數目.

(2) 局部同胚.

為流形的每1個分片Xn構造局部同胚映射φn，于是，分片Xn的局部坐標為

(2)

目前，最常用的局部同胚映射的求解方法是PCA方法.

(3) 局部坐標排列.

LTSA建立的局部坐標Θn與全局坐標Yn的關系為

(3)

(4)

‖YWn‖2,

(5)

式(5)只是考慮1個分片的情況，如果考慮所有分片的情況，則有

(6)

2 流形學習中的最小熵排列方法

本文提出一種新的漸進式排列方法.在漸進的過程中，這種方法每次只是把在當前階段交集最大的2個分片的局部坐標融合為1個新的局部坐標，代替原來的2個局部坐標.整個排列的過程與霍夫曼最小熵編碼的過程相似，即每次只是把在當前階段概率最小的二個隨機事件合并為1個隨機事件.因此，稱為最小熵的排列方法.

2.1 兩個局部坐標的排列

提出的最小熵的排列方法是1種漸進式的排列方法，每次只是排列2個分片的局部坐標.文獻[13]的圖2清楚表達了2個分片的局部坐標排列的幾何意義，但是，文獻[13]的數學推導非常繁瑣.本文給出1種實現排列的簡單明快的數學推導.

(1) 確定變換矩陣A.

(7)

(8)

(2) 平移.

(9)

(3) 旋轉和縮放變換.

(10)

(11)

(4) 排列.

(12)

2.2 最小熵排列

最小熵排列(MinimumEntropyAlignment，MEA)的步驟如下.

算法1.MEA1: 初始化.Π=Xm()m=1,…,M{},Ω=Θm()m=1,…,M{}T=m1,m2()1≤m1,m2≤M,Xm1()∩Xm2()≠φ{}2: whileM>1do3:在T中找m1,m2()使得Xm1()∩Xm2()=max 從Ω中取出Θm1()和Θm2()4: 排列Θm1()和Θm2()得到Θm() 合Xm1()和Xm2()成Xm()=Xm1()∪Xm2()5: 更新Ω:Ω=Ω-Θm1(),Θm2(){},Ω=Ω∪Θm(){}6:更新Π:Π=Π-Xm1(),Xm2(){},Π=Π∪Xm(){}7:更新T:T=T-m1,m2(){},對所有m'1,m'2()∈T,Ifm'1=m1,thenT=T-m'1,m'2(){},T=T∪m,m'2(){}Ifm'2=m2,thenT=T-m'1,m'2(){},T=T∪m'1,m(){}8: M=M-19: endwhile10: 輸出Ω

最小熵排列方法具有如下特點：

(1) 最小熵排列的方法，與文獻[13]和[14]的方法一樣，是1種漸進式的排列方法.因此，最小熵排列的方法也具備漸進式排列方法相對于全局式排列方法的全部優(yōu)點，如方法簡單，避免了局部極小值的陷阱，不必求解大型稀疏矩陣的特征值問題等等.

(2) 2個分片的交集是它們局部坐標排列的依據.交集越大，排列的誤差越小.最小熵排列方法每次都是選取在當前階段交集最大的2個分片的局部坐標進行排列，因此，與文獻[13]和[14]提出的方法相比，最小熵排列方法最大限度地減少了排列的誤差.

(3) 減輕誤差的積累和轉播.正如前面所說，本文提出的排列方法與霍夫曼最小熵編碼相似，而霍夫曼編碼過程是1個橫向優(yōu)先的過程，呈現相對扁平化的結構，有助于減輕誤差的積累和轉播，而文獻[13]和[14]提出的排列方法是1個縱向優(yōu)先的方法，呈現1種樹形的結構.樹的每1個節(jié)點代表1個局部坐標，從樹的一個節(jié)點走向另1個節(jié)點代表2個相應的局部坐標的排列，排列的誤差沿著樹干向下積累和傳播.

3 實驗結果

本文分別在人工流形數據和實際圖像數據上，將提出的最小熵排列方法與6種流形學習算法(Isomap[1]、LLE[2]、LE[5]、LTSA[7]、LLI[11]和IAM[12])作比較.其中Isomap、LLE、LE、LTSA是4種經典的流形學習算法，LLI和IAM是兩種基于漸進式排列的算法.需要說明的是，在本文實驗中，將LLI原算法中的歐氏距離測度改為了測地距離以得到更好的結果.因為這里主要是為了比較排列的效果，所以本文的算法是用最小熵排列方法對LLI中得到的分片和局部坐標進行排列.

3.1 人工流形上的實驗

本文用3個人工流形數據集來可視化地說明提出的排列方法的有效性.在以下每個實驗中，對各算法的參數都作了精心選擇以保證最佳的實驗結果.

第1個數據集如圖1(a)所示，是從嵌入在3維歐氏空間中的“Swissrollwithahole”流形上采樣得到的800個數據點.Isomap的降維結果有許多空洞，還出現全局上的變形.這是因為Isomap在1個不準確的測地距離陣上進行MDS算法，導致降維結果不能很好地保持原流形的局部特性.另外，全局上的變形說明了Isomap處理非凸數據集方面的局限性.LLE的降維結果在全局上有較大的扭曲.LLE算法不能保證在原空間相距較遠的兩個點，降到低維空間后仍然相距很遠.LE算法的結果成了曲線，顯然無意義.LTSA結果看似較好，在原3維空間中的數據降到2維空間后，數據點位置的順序關系沒有發(fā)生變化.但是，流形的真實形狀已經被改變了.LTSA在對數據集降維的過程中，都在某個方向上，把數據點壓縮了，數據點間的真實關系沒有得到保持.因為該算法只關注流形的局部幾何結構，忽視了流形全局結構的保持.強加1個單位協(xié)方差矩陣約束，使得數據點之間的測地距離關系無法得到保持.LLI算法結果在中間出現斷裂，這是因為漸進式的排列方法再排列的過程中會導致的排列誤差的積累和傳播.基于同樣原因，IAM算法的結果也出現變形.本文方法的結果要優(yōu)于其他6種算法，這是因為這個流形是等曲率的，這種情況下，漸進式的排列方法往往能取得較滿意的效果.而且本文方法在每次排列的時候都考慮選擇最小熵的2個分片進行，所以有最好的結果.

圖1 Swissroll with a Hole實驗

第2個數據集如圖2(a)所示，采樣自流形S-Curve 的1 240個數據點被分成7類.LLI和IAM的結果都有明顯的斷裂，本文的算法能得到較滿意的結果.多類數據集幾乎對所有流形學習算法來說都是個挑戰(zhàn)[15]，本文的后續(xù)工作會在這方面繼續(xù).

圖2 多類別實驗

圖3是幾種基于排列的流形學習方法對用不同采樣密度采樣自“S-curve”流形的數據點的降維結果.采樣點數N分別為150、300、400、500、800.從圖3可見，隨著采樣密度的變化，最小熵的排列方法具有最好的魯棒性.

圖3 不同采樣密度采樣自S-curve流形的數據點集，用4種基于排列的流形學習方法分別對其進行降維的結果

3.2 圖像數據集上的實驗

為了驗證提出的排列方法在實際圖像數據集上的效果，將該方法和現有的幾種流形學習算法對USPS手寫數字數據集進行降維，然后用K-均值聚類得到聚類結果，從而比較各個算法的性能.

USPS數據集包含“0”到“9”這10個手寫數字，每個數字有1 100張的灰度圖.每張圖的大小是16×16的，看成是在D=256維空間中的1個數據點.聚類算法就是要為每個這樣的數據點生成1個類標.聚類的性能可以由上述產生的類標與真實的類標的重合程度來評估.

分別取不同的聚類數K，即K=2,3,4.對每個K，隨機地選擇數字類別(例如K=2時，隨機地從10個數字類中選擇其中的2類)，并重復10次，最后的結果是取10次的平均.先用各種流形學習算法得到數據集的3維嵌入結果，然后用K-均值聚類算法進行聚類.因為聚類中心是隨機選取的，所以這里運行10次K-均值算法，然后取最好的結果記錄.這里需要說明的是，為了使分片之間有足夠的交疊，本文讓每個數據點屬于4個分片，而不是原LLI中的2個分片.本文的算法也直接用上述得到的分片.表1列出了將USPS數據集用各種流形學習算法降到2維后的聚類準確率.可見3種基于漸進式排列的算法并沒有比其他4種經典的流形學習方法得到更好的結果.這是因為圖像數據流形不是等曲率的，漸進式排列的誤差必然不會小.比較3種漸進式排列方法，本文基于最小熵的排列得到最高的聚類準確率.

表1 USPS數據集經過各算法降到2維的聚類準確率

4 結論

排列就是根據分片在高維歐氏空間中位置的相互關系，在低維歐氏空間中排列分片的局部坐標.全局和漸進式的排列方法各有千秋.漸進式的排列方法把全局排列方法中龐大的特征值問題轉化為一系列簡單的線性方法組求解的問題.另外，漸進式排列方法具有較強的幾何特征，人們可以在漸進式排列的過程中觀察流形全局坐標逐步形成的過程.但是，任何方法都有局限性.漸進式排列方法的局限性在于它主要適合像Swissroll這樣曲率變化為零或曲率變化不大的流形.

現有的漸進式排列方法都是先確定1個基礎局部坐標，然后逐步擴張這個基礎局部坐標.這是1個縱向優(yōu)先的過程，呈現樹形的結構.本文提出的漸進式排列方法沒有基礎局部坐標的概念，每次只是排列當前階段交集最大的2個分片的局部坐標.這是1個橫向優(yōu)先的過程，呈現扁平化的結構.本文提出的漸進式排列方法可以做為現有的漸進式排列方法的改進或補充.

[1] Tenenbaum J B, Silva Vin De ，Langford J C. A global geometric framework for nonlinear dimension reduction [J]. Science, 2000, 290(5500): 2319-2323.

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

[3] Saul L K，Rowels S T. Think globally, fit locally: Unsupervised learning of low dimensional manifolds [J]. Journal of Machine Learning Research, 2004, 4(2): 119-155.

[4] Chen J，Liu Y. Locally linear embedding: a survey[J]. Artificial Intelligence: Review, 2011, 36(1): 29-48.

[5] Sun M, Liu C, Yang J, et al. A two-step framework for highly nonlinear data unfolding [J]. Neurocomputing, 2010, 73(10-12): 1801-1807.

[6] Chen J, Liu Y. Locally Linear Embedding Based on Local Correlation [C]∥ICMV2011. Bellingham, USA: SPIE， 2011: 228-232.

[7] Belkin M，Niyogi P. Laplacian eigenmaps for dimensionality reduction and Laplacian eigenmaps for dimensionality reduction and data representation [J]. Neural Computation, 2003, 15(6): 1373-1396.

[8] Donoho D，Grimes C. Hessian Eigenmaps: new tools for nonlinear dimensionality reduction [C]∥Proceedings of National Academy of Science.Washington D C, USA: National Academy of Science，2003: 5591-5596.

[9] Zhang Z，Zha H. Principal manifolds and nonlinear dimensionality reduction via tangent space alignment [J]. SIAM Journal of Scientific Computing, 2005, 26(1): 313-338.

[10] Weinberger K Q，Saul L K. Unsupervised learning of image manifolds by semidefinite programming [J]. International Journal of Computer Vision, 2006, 70(1): 77-90.

[11] Lafon S, Keller Y，Coifman R. Data fusion and multicue data matching by diffusion maps [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(11): 1784-1797.

[12] Hou C, Zhang C, Wu Y，et al. Stable local dimensionality reduction approaches [J]. Pattern Recognition, 2009, 42(9): 2054-2066.

[13] Hou Y, Zhang P, Xu X，et al. Nonlinear dimensionality reduction by locally linear inlaying [J]. IEEE Transactions on Neural Networks, 2009, 20(2): 300-315.

[14] Zhi H, Deyu M, Zongben X，et al Incremental alignment manifold learning [J]. Journal of Computer Science and Technology, 2011, 26(1): 153-165.

[15] Meng D Y, Leung Y, Xu Z B. Passage method for nonlinear dimensionality reduction of data on multicluster manifolds [J]. Pattern Recognition, 2013, 46(8): 2175-2186.

The Minimum Entropy Alignment in Manifold Learning

Chen Jing1, Liu Yang2

(1. School of Physics and Optoelectronic Engineering; 2. School of Information Engineering, Guangdong University of Technology, Guangzhou 510006, China)

A new progressive alignment method is proposed, while only the local coordinates of the two patches with the largest intersection at the current stage of progressive alignment will be aligned into a larger local coordinate. The method has the following features: without needing to solve a large-scale eigenvalues problem and suffering from the problem of local minima; less accumulation and propagation of alignment errors.

manifold learning; dimensionality reduction; alignment

2014- 05- 13

國家自然科學基金資助項目(61305069)；廣東省自然科學基金資助項目(S2013040016371)

陳 靜(1980-)，女，副教授，博士，主要研究方向為機器學習.

10.3969/j.issn.1007- 7162.2015.03.008

TP 391.4

A

1007-7162(2015)03- 0039- 07