張曉宇，孫海霞，黃天民

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

?

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

張曉宇，孫海霞，黃天民

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

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

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

1　局部線性嵌入法(LLE)

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

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

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

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

第二步，計(jì)算局部權(quán)值矩陣W={wij}，對(duì)每個(gè)樣本點(diǎn)用它的k個(gè)鄰域來近似重構(gòu)，即計(jì)算該點(diǎn)和每個(gè)近鄰點(diǎn)的權(quán)重wij使得構(gòu)建誤差最小，解最小化目標(biāo)函數(shù)

第三步，用局部權(quán)值矩陣W計(jì)算低維嵌入空間中的Y。由于wij代表著局部信息，低維空間要盡量保持高維空間的局部線性結(jié)構(gòu)，所以固定wij，最小化目標(biāo)函數(shù)

(1)

得到Y(jié)，LLE通過兩個(gè)條件來約束優(yōu)化問題使f(Y)對(duì)旋轉(zhuǎn)、平移、伸縮變化具有不變性：樣本點(diǎn)映射后的坐標(biāo)以原點(diǎn)為中心；嵌入之后的向量有單位協(xié)方差，即

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

要解決的優(yōu)化問題此時(shí)成為

這個(gè)問題的解為M=(I-WT)(I-W)的最小m個(gè)特征值對(duì)應(yīng)的特征向量，即

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

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

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

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

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

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

第三步，計(jì)算局部權(quán)值矩陣W={wij}，對(duì)每個(gè)樣本點(diǎn)用它的k個(gè)鄰域來近似重構(gòu)，即計(jì)算該點(diǎn)和每個(gè)近鄰點(diǎn)的權(quán)重wij使得構(gòu)建誤差最小，解最小化目標(biāo)函數(shù)

(2)

式(2)中的I表示n維單位矩陣，對(duì)應(yīng)的優(yōu)化問題轉(zhuǎn)化為以下的約束優(yōu)化問題

令M=(I-WT)(I-W)，取M的第2～m+1個(gè)特征值所對(duì)應(yīng)的特征向量當(dāng)作低維嵌入的坐標(biāo)。

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

3　實(shí)驗(yàn)

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

表1　兩種方法降維時(shí)間的比較

由實(shí)驗(yàn)結(jié)果可知，利用模糊C均值聚類方法聚類后，重構(gòu)權(quán)值矩陣的階數(shù)與近鄰點(diǎn)的個(gè)數(shù)只是和聚類的個(gè)數(shù)有關(guān)，大大縮減了求M矩陣和近鄰點(diǎn)的計(jì)算量，因而計(jì)算速度較快些。

對(duì)LLE和基于模糊C均值聚類和測地距離的LLE算法在樣本點(diǎn)個(gè)數(shù)變化時(shí)查準(zhǔn)率進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖1所示：

圖1　樣本點(diǎn)個(gè)數(shù)變化時(shí)兩種方法的查準(zhǔn)率比較

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

針對(duì)LLE算法對(duì)樣本點(diǎn)的計(jì)算量問題，提出了一種基于模糊C均值聚類和測地距離的LLE算法，該方法有效的縮減了求M矩陣階數(shù)和近鄰點(diǎn)的計(jì)算量，實(shí)驗(yàn)結(jié)果表明，改進(jìn)的方法具有一定的優(yōu)越性。

[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]鄒艷.高維數(shù)據(jù)降維方法的研究[D].成都：西南交通大學(xué)，2012年.

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

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

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

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

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

[15]許麗利.聚類分析的算法及應(yīng)用[D].吉林：吉林大學(xué)，2010年.

責(zé)任編輯王菊平

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

張曉宇，女，山西霍州人，碩士研究生，主要研究方向?yàn)檫\(yùn)籌與優(yōu)化；孫海霞，女，山西呂梁人，碩士研究生，主要研究方向?yàn)槲⒎址匠?；黃天民，男，河北邯鄲人，教授，主要研究方向?yàn)閮?yōu)化與決策、模糊控制與智能控制。

國家自然科學(xué)基金項(xiàng)目(61473239)。