局部線性嵌入算法中參數的選取

摘 要：局部線性嵌入（LLE）算法是有效的非線性降維方法，時間復雜度低并具有強的流形表達能力。與其他降維方法相比，局部線性嵌入算法的優勢在于只定義唯一的參數，即鄰域數。因此算法的性能主要依靠此鄰域參數的選取，這就產生問題：怎樣選取鄰域參數的最佳值。通過對兩種自動選取最佳參數值的方法，即簡單方法和分層方法進行試驗比較與分析，歸納出在實踐中確定鄰域參數的啟發式策略。

關鍵詞：線性嵌入; 最佳參數值; 降維; 重構誤差

中圖法分類號：TP391文獻標識碼：A

文章編號：1001—3695(2007)02—0060—03

高維數據中包含大量的冗余并掩藏了重要關系的相關性，降維的目的就是消除冗余，減少被處理數據的數量， 因而廣泛用于數據分類和模式識別等領域。

降維方法可分為線性與非線性兩類。由于大量的數據是高維非線性的，因此非線性方法是目前的研究熱點， 它能分析更復雜的情況（特別在可視化非線性流形時）。非線性方法的關鍵目標就是保持距離不變，也就是說，當映射數據到低維空間時，在輸入空間里接近的點，在輸出空間里也必須是接近的。目前此類具有代表性的方法有Isomap[1]和LLE[2]及其改進算法，如拉普拉斯算子特征映射[3]。Isomap試圖保持流形的全局幾何距離不變， 而LLE則以保持局部幾何距離不變為目標。

LLE方法是2000年由Sam T.Roweis和Lawrence K.Saul提出的一種新的非線性降維方法，具有時間復雜度低、參數少(僅有一個預先確定的參數)等優點。但是還需要深入研究，基于它的實際應用仍然很少[4]。我們的目的是應用LLE實現專利文本數據的可視化[8]， LLE的參數設置對降維性能有很大的影響， 本文側重研究LLE最佳參數值的選取問題。

1 局部線性嵌入（Locally Linear Embedding，LLE）

2 最近鄰域最佳值的自動選取

為什么需要關注這個問題呢？原因就是大量的最近鄰域可以促成流形小規模結構的消除及整個流形的平滑。相反，太少鄰域可能誤將連續的流形劃分成脫節的子流形。

一般地，最優化有不同的定義。為了避免很多情況下常常碰到的，由人們的視覺判斷而產生的主觀評估，我們依據下面介紹的數量測度來表現最優化的特色。

2.1 簡單方法

確定Kopt的簡單方法就是用每個可能的K（K∈[1，Kmax]，這里Kmax是Kopt的最大可能值）去運行LLE，根據式（3）選取Kopt，然而，這種方法過分苛求計算。

2.2 分層方法

還有一種稱為分層的方法[5]。該方法不需要處理完LLE的所有步驟，而在第一步時，選擇一系列可能成為Kopt的候選，接著為每個候選計算剩余方差，挑選對于這種判別標準值最小的候選。與剩余方差法相比，LLE最耗時的操作，即特征向量計算的運行只要極少的時間。分層方法的本質由下面內容組成：

3 試驗分析

試驗采用三組數據驗證簡單方法和分等級法兩種方法。有效性評價指標包括：①類之間的距離和結構要盡可能地保持而不重疊，有利于類之間的結構和相關性的可視化分析；②類內的樣本距離和結構要盡可能地保持而不重疊，有利于類內數據的結構和相關性的可視化分析；③使用要方便，如參數設置、結果對參數的敏感性，以及方法的穩定性等，這對數據挖掘等實踐應用是十分重要的；④時間和空間復雜度要盡可能地低。試驗的目的是為了評價在二維空間中可視化高維數據時，Kopt自動選取的兩種方法。試驗利用了在Windows的MATLAB中執行的LLE代碼[6]。

試驗1：IRIS數據

Fisher的IRIS數據廣泛用于聚類分析和可視化研究，是一個標準的測試集，它由三類四維數據共150個點構成。類別Setosa數據與另外兩個類，即Versicolour和Virginica分離得很開，而Versicolour和Virginica兩類則靠得很近。利用式（1）求得使ε最小的一系列K候選。對候選的K計算剩余方差，得到Kopt=144。利用簡單方法找到的Kopt=145。造成最佳K值不一致的原因是：使重構誤差最小的K候選中不一定含有使剩余方差最小的K，從而產生了誤差。

考查ε(K)函數，當K＜9時， 全局最小值的存在是由以下的事實引起的：對于每個數據點，首批少數鄰域都確實離它很近，每增加一個新的鄰點就大大減少了重構錯誤，然而，隨著K的增長，這個錯誤開始改變（它交替上升或下降），因而歐幾里得距離變成用于近似而又不可靠的指示器。

在IRIS上，最佳鄰域的降維效果良好，但是最佳鄰域覆蓋近似整個數據集。試驗3中Wordtest上也有相同的情形。試驗2:SwissRoll數據

SwissRoll是LLE和Isomap兩種方法都采用的測試數據[1，2]，目的是將三維數據降為兩維數據。在SwissRoll數據集上，簡單方法的耗時特征表現明顯。隨機采用10個測試樣本，用簡單方法計算鄰域最佳值，得到不同的Kopt值，LLE方法聚類不穩定便會出現這樣的現象。樣本降維效果表明，K取較大值時，降維效果顯著變差，這是因為測試數據是比較彎曲的流形，容易發生短路現象。

圖1是SwissRoll數據集10次隨機采樣800點，分別用分層方法和簡單方法得到的Kopt分布。由可視化的降維效果可得出：分層方法是優于簡單方法的，LLE降維SwissRoll（N=800），效果良好的參數值在8—14之間，分層法找到的Kopt在此區間比較集中；而簡單方法的集中區間在16—20之間。

試驗3:數據Wordtest

由我們研制的基于專利的產品創新支持系統產生[8]。產生過程以專利“Teething Aid for Infants”為聯想的靶在試驗用的英文專利數據庫中展開聯想，并利用文本向量空間模型將專利文本向量化[9]，構造了135個專利文本向量的數據集合，向量空間的維數為1 162，四個IPC部級類別。用分層方法找到Kopt=133，用簡單方法找到的Kopt=134。實際降維效果顯示最佳的取值不在兩者之中。由可視化降維效果判斷可知，當K=120時，降維效果略優于自動選取的最佳鄰域，表現在類內數據點之間的重疊更少。其重構誤差實驗結果如圖2所

4 計算復雜度估計

當D>>N（樣本點為少量的高維數據點）時，分層方法不會優于簡單方法。原因就是特征向量計算是對N×N矩陣進行操作，對于N小的矩陣，花費在這項操作上的時間相對而言很少，因此如果D很大，簡單方法后面兩步的時間估計與分層方法相應步驟的時間估計就處在同一個數量級。

當D比N小或者差不多時，情況就改變了。在這種情形下，分層方法中計算重構加權系數的時間代價增加，但是由于實際NS<

5 總結

與線性降維方法相比，LLE處理高維大規模數據的低維嵌入具有更強的能力，它不僅具有較低的時間和空間復雜度，而且得到全局的低維系統，有利于數據的結構和相關分析，特別適合于在線數據聚類分類等數據分析領域。但有一個問題就是怎樣定義流形的最佳分割。在LLE中，分割是由參數K來決定。LLE的前提是流形是平的，對極度彎曲的數據流形難以得到正確的結果。其原因是線性化的局部區域包含很多彎曲而不是真正的超平面，因此造成了在低維彎曲和高維數據流形上，自動選取最佳鄰域的結果與實際情況有不相符的情況發生。

我們對分層方法和簡單方法作了比較：重構誤差和剩余方差都可以用來測度降維的質量，但只能在一定范圍內有效，存在著有的測量結果與主觀評價不一致（如文中的SwissRoll和Wordtest）。兩種參數選擇方法中， 分層方法主要是提高了獲取參數的時間效率。兩種參數選擇方法選擇的K是比較好的參數，但都不一定是最好的參數， 存在有的測量結果與主觀評價不一致（如文中的IRIS），因此我們得到確定參數的策略是用兩種參數選擇方法選擇比較好的參數K，然后在K的附近，采用人工調試主觀評價確定最后的K_opt。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。