基于模糊聚類和測地距離的LLE算法

張曉宇，孫海霞，黃天民

(西南交通大學 數學學院，四川 成都 611756)

?

基于模糊聚類和測地距離的LLE算法

張曉宇，孫海霞，黃天民

(西南交通大學 數學學院，四川 成都 611756)

局部線性嵌入算法(LLE)是一種解決降維問題的方法，針對權值矩陣的計算及近鄰點個數選取，提出了基于模糊聚類和測地距離的LLE算法，模糊C均值聚類可以減少計算權值矩陣的計算量，縮減計算時間；使用測地距離的LLE算法可以在選取近鄰點個數較小的情況下獲得良好的效果。實驗結果表明，基于模糊C均值聚類和測地距離的LLE算法大大縮減了計算M矩陣和近鄰點的計算量，具有一定的優越性。

降維；局部線性嵌入法(LLE)；測地距離；模糊C均值聚類

1　局部線性嵌入法(LLE)

高維數據通常含有大量的冗余數據，維數縮減是模式識別的一項重要內容，通過對高維數據降維可以消除冗余性，提高圖像的識別速度。傳統的降維方法一般指線性降維方法，例如主元分析法(PCA)[1]、Fisher判別法[2]局部線性嵌入法(LLE)[3]、多維尺度法(MDS)[4]和等距離映射法(ISOMAP)[5]等，是非線性降維方法，介紹類似方法的文獻也有很多[6-11]。其中LLE算法具有待定參數少、幾何意義直觀和有整體解析最優解等眾多優點，因此受到很多學者的關注。

LLE是由Saul和Roweis在2000年提出的一種非線性降維方法，其主要思想是用局部線性逼近全局的非線性[3]，即通過彼此互相重疊的局部鄰域提供整體信息，來保持整體的幾何性質。

LLE算法將高維數據X=(x1,x2,…,xn)xi∈Rd映射到低維數據Y=(y1,y2,…,yn)，yi∈Rm(m

第一步，計算每個樣本點xi與其它n-1個樣本點之間的距離dij=|xi-xj|，(其中i,j=1,2,…,n)，選擇與xi最近的前k個點作為其近鄰點。

第二步，計算局部權值矩陣W={wij}，對每個樣本點用它的k個鄰域來近似重構，即計算該點和每個近鄰點的權重wij使得構建誤差最小，解最小化目標函數

第三步，用局部權值矩陣W計算低維嵌入空間中的Y。由于wij代表著局部信息，低維空間要盡量保持高維空間的局部線性結構，所以固定wij，最小化目標函數

(1)

得到Y，LLE通過兩個條件來約束優化問題使f(Y)對旋轉、平移、伸縮變化具有不變性：樣本點映射后的坐標以原點為中心；嵌入之后的向量有單位協方差，即

記f(Y)=‖Y-YWT‖2，則式(1)寫成跡的形式

要解決的優化問題此時成為

這個問題的解為M=(I-WT)(I-W)的最小m個特征值對應的特征向量，即

由于M的最小特征值一般接近于0，因此取2～m+1個特征值所對應的特征向量作為Y，矩陣M=(I-WT)(I-W)通常被稱為LLE矩陣。

2　基于模糊聚類和測地距離的LLE算法

從LLE的計算過程可以看出，當樣本點個數比較大時，求近鄰點和權重矩陣W的計算量也會隨之增大。若樣本集不均勻，近鄰點個數k的選取對結果的影響比較大，而使用測地距離的LLE算法會降低樣本分布對計算結果的影響(證明過程見文獻[9])，因此本文在改進距離的LLE的基礎上使用模糊C均值聚類的方法來縮減求近鄰點及M矩陣的計算量，具體步驟如下：

第一步，采用模糊C均值聚類的方法[12-15]將樣本集X={x1,x2,…,xn}分為c類，由于聚類的均值向量包含大量的信息，因此可以用聚類的均值向量(也稱聚類中心向量)代表該類，再用所有的聚類中心{v1,v2,…,vc}作為新的樣本集。

第二步，對新的樣本集中的每個點vi計算它與其它c-1個樣本點之間的測地距離G(vi,vj)，通過公式

求得樣本點之間的調和距離，其中M(i)，M(j)分別表示vi，vj和其余各點之間距離的平均值，即

第三步，計算局部權值矩陣W={wij}，對每個樣本點用它的k個鄰域來近似重構，即計算該點和每個近鄰點的權重wij使得構建誤差最小，解最小化目標函數

(2)

式(2)中的I表示n維單位矩陣，對應的優化問題轉化為以下的約束優化問題

令M=(I-WT)(I-W)，取M的第2～m+1個特征值所對應的特征向量當作低維嵌入的坐標。

采用測地距離的LLE算法可以使分布比較密集的區域的樣本點距離增大，使得分布比較稀疏的區域的樣本點之間的距離縮小，從而使樣本點整體的分布均勻化，緩解用歐氏距離重構對流行結構造成的扭曲。其次，采用模糊C均值聚類的方法對樣本點進行分類，可以使樣本點個數增多時求近鄰點及矩陣的計算量大大降低。因此，采用兩者相結合的方法理論上較全面的對LLE算法進行了改進，下面用實驗結果驗證新算法的有效性。

3　實驗

采用Matlab R2009a對新算法的有效性進行驗證，本實驗的數據集采樣自Swiss Hole，N=2000，k分別取9,11,13，分別采用測地距離LLE和基于模糊C均值聚類和測地距離的LLE算法將數據降維至二維平面，兩種降維方法所需時間如表1所示：

表1　兩種方法降維時間的比較

由實驗結果可知，利用模糊C均值聚類方法聚類后，重構權值矩陣的階數與近鄰點的個數只是和聚類的個數有關，大大縮減了求M矩陣和近鄰點的計算量，因而計算速度較快些。

對LLE和基于模糊C均值聚類和測地距離的LLE算法在樣本點個數變化時查準率進行實驗，實驗結果如圖1所示：

圖1　樣本點個數變化時兩種方法的查準率比較

從圖1可以看出，隨著樣本點個數的增多，LLE算法與基于模糊C均值聚類和測地距離的LLE算法的檢索精度均有所下降，但是兩種算法卻保持了一致的查準率，也就是說，隨著樣本點個數的增多，基于模糊C均值聚類和測地距離的LLE算法幾乎不影響原來的檢索精度。

針對LLE算法對樣本點的計算量問題，提出了一種基于模糊C均值聚類和測地距離的LLE算法，該方法有效的縮減了求M矩陣階數和近鄰點的計算量，實驗結果表明，改進的方法具有一定的優越性。

[1]Jolliffe I T. Principle Component Analysis[M]. Berlin: Springer, 1986.

[2]Mika S, Ratsch G, Weston J,etal. Fisher discriminant analysis with kernels[J]. Neural Networks for Signal Processing,1999, 8(9):41-48.

[3]Roweis S T, Saul L K. Nonlinear dimensionality reduction by locally linear embedding[J]. Scinece, 2000,290:2323-2326.

[4]Borg I, Groenen P. Mordern Multidimentional Scaling: Theory and Application[M]. New York: Springer Verlag, 1997.

[5]Tenenbaum J B, Silva Vin de, Langford John C. A global geometric framework for nonlinear dimensionality reduction[J]. Science,2000,290:2319-2323.

[6]Orsenigo C, Vercellis C. Kernel ridge regression for out-of sample mapping in supervised manifold learning[J]. Expert System with Application,2012,39(9):7757-7762.

[7]Min R, Stanley D A, Yuan Z,etal. A deep non-linear feature mapping for large-margin kNN classification[C]. The 9th IEEE International Conference on Date Mining.2009:357-366.

[8]Strange H, Zwiggelaar R Z. Parallel projections for manifold learning[C]. The 9th International Conference on Machine Learning and Application, 2010:266-271.

[9]鄒艷.高維數據降維方法的研究[D].成都：西南交通大學，2012年.

[10]余肖生，周寧.高維數據降維方法研究[J].情報科學，2007,25(8):1248-1251.

[11]王和勇，鄭杰，姚正安,等.基于聚類和改進距離的LLE方法在數據降維中的應用[J]. 計算機研究與發展，2006，43(8)：1485-1490.

[12]張小紅，裴道武,代建華.模糊數學與Rough集理論[M]. 北京：清華大學出版社，2013:135-145.

[13]蘇錦旗，張文宇.基于模糊聚類的改進LLE算法[J].計算機與現代化，2014，(5):10-13.

[14]鮑正益.模糊聚類算法及其有效性研究[D].廈門，廈門大學，2006年.

[15]許麗利.聚類分析的算法及應用[D].吉林：吉林大學，2010年.

責任編輯王菊平

The LLE algorithm based on fuzzy clustering and geodesic distance

ZHANG Xiao-yu, SUN Hai-xia， HUANG Tian-min

(Department of Mathematics, Southwest Jiaotong University, Chengdu 611756, China)

Locally linear embedding (LLE) algorithm is a method to solve the problem of dimension reduction. To calculate weight matrix and determine the quantity of neighboring points, this paper proposes LLE algorithm which is based on fuzzy clustering and geodesic distance. Fuzzy C means clustering can reduce the amount of calculation of the weight value matrix and computing time. The application of the LLE algorithm works very well when a small number of neighboring points are chosen. Experimental results show certain advantages of the LLE algorithm as it greatly reduces the calculation M matrix and neighboring point calculation.

dimension reduction; locally linear embedding; geodesic distance; fuzzy C means clustering

TP391.9

A

1003-8078(2016)03-0008-04

2016-04-05

10.3969/j.issn.1003-8078.2016.03.03

張曉宇，女，山西霍州人，碩士研究生，主要研究方向為運籌與優化；孫海霞，女，山西呂梁人，碩士研究生，主要研究方向為微分方程；黃天民，男，河北邯鄲人，教授，主要研究方向為優化與決策、模糊控制與智能控制。

國家自然科學基金項目(61473239)。