自適應(yīng)近鄰的局部線性嵌入算法

張興福，黃少濱

(1.哈爾濱工程大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江哈爾濱150001;2.黑龍江省農(nóng)墾經(jīng)濟(jì)研究所，黑龍江哈爾濱150090)

隨著多媒體技術(shù)的廣泛應(yīng)用，分析圖像及音、視頻文件的算法也越來越受到科研工作者的關(guān)注.圖像等數(shù)據(jù)往往維數(shù)過高，因此出現(xiàn)眾多對(duì)高維數(shù)據(jù)進(jìn)行降維處理算法，優(yōu)秀的降維算法既可以去掉冗余特征，又能夠保留主要特征，這樣既提高后續(xù)算法的性能，還降低了算法的復(fù)雜度.

降維算法分為線性降維及非線性降維，經(jīng)典的線性降維算法有主分量分析(PCA)、線性判別分析(LDA)、獨(dú)立分量分析(ICA)等.線性降維算法通過對(duì)訓(xùn)練樣本的學(xué)習(xí)得到映射矩陣，再通過線性運(yùn)算將高維空間的數(shù)據(jù)映射至低維空間，算法計(jì)算復(fù)雜度低，適合實(shí)時(shí)應(yīng)用，但對(duì)非線性分布數(shù)據(jù)的降維效果不佳，故需要采用對(duì)非線性分布數(shù)據(jù)的降維效果良好的非線性降維算法，如流形學(xué)習(xí).

2000年Science雜志在同一期上連續(xù)發(fā)表了3篇流形學(xué)習(xí)方面的文章[1-3]，奠定了流形學(xué)習(xí)的研究基礎(chǔ).相對(duì)于PCA等線性降維算法，流形學(xué)習(xí)算法能夠更好地發(fā)現(xiàn)非線性分布數(shù)據(jù)的本質(zhì)結(jié)構(gòu)，而且H.Sebastian Seung等[1]又提出人類的感知是基于流形的，眾多國內(nèi)學(xué)者也對(duì)流形學(xué)習(xí)進(jìn)行了深入研究[4-11].流形學(xué)習(xí)分為全局算法與局部算法，等距映射(ISOMAP)[2]是經(jīng)典的全局算法，該算法將多維分析(MDS)推廣到非線性降維領(lǐng)域，能夠更好地保持?jǐn)?shù)據(jù)的整體結(jié)構(gòu)，但計(jì)算復(fù)雜度較高;局部線性嵌入(LLE)[3]與拉普拉斯映射(LM)[12]算法則是經(jīng)典的局部算法，LLE算法將PCA算法推廣到非線性降維領(lǐng)域，LM算法則利用熱核方程計(jì)算加權(quán)邊，然后與數(shù)據(jù)樣本組成拉普拉斯圖后進(jìn)行數(shù)據(jù)降維，LLE與LM算法均只保留局部關(guān)系，這樣雖然數(shù)據(jù)整體分布會(huì)有些“變形”，但計(jì)算復(fù)雜度大大降低，適合實(shí)時(shí)性要求高的系統(tǒng).

目前流形學(xué)習(xí)的局部降維算法普遍存在3方面問題:1)近鄰選取問題，局部算法均需要應(yīng)用K近鄰法或ε近鄰法[12]確定任意樣本的近鄰，并沒有根據(jù)樣本自身特征考慮某一樣本是否適合作為另一個(gè)樣本的近鄰，同時(shí)k或ε值的確定也沒有給出具體方案;2)相似性度量問題，局部算法往往應(yīng)用歐氏距離計(jì)算樣本間相似度，歐氏距離假定高維數(shù)據(jù)的各個(gè)分量間是完全無關(guān)的，而對(duì)諸如圖像等高維數(shù)據(jù)，作為分量的各個(gè)位置的像素值并不是完全無關(guān)的，因此某些具體應(yīng)用中歐氏度量不一定是最恰當(dāng)?shù)南嗨菩远攘?3)新樣本降維問題，一些局部算法沒有提供新樣本的降維方法，這使其很難應(yīng)用于動(dòng)態(tài)系統(tǒng).

針對(duì)LLE算法存在的第1個(gè)問題，Dick de Ridder等[13]提出監(jiān)督的 LLE 算法(SLLE)，Shiqing Zhang等[14]提出增強(qiáng)的監(jiān)督 LLE 算法(ESLLE)，2種算法在近鄰選擇步驟時(shí)都充分考慮樣本的類標(biāo)簽信息，使得樣本的近鄰大部分是同類，少部分是異類，這樣在重構(gòu)時(shí)既能盡量保持?jǐn)?shù)據(jù)分布屬性，還使得算法有較好的泛化能力.Hong Chang等[15]提出魯棒的LLE算法，通過運(yùn)用系數(shù)主分量分析算法評(píng)估每個(gè)樣本噪聲的概率，然后在運(yùn)用LLE算法時(shí)，只選擇是噪聲概率較小的樣本作為近鄰.Shuzhi Sam Ge等[16]提出鄰域線性嵌入算法(NLE)，認(rèn)為如果2個(gè)樣本過于相似，則其中一個(gè)可以由另外一個(gè)表示，即過于相似的2個(gè)樣本有類似的屬性，選擇近鄰時(shí)只選擇過于相似的2個(gè)樣本之一作為某個(gè)樣本的近鄰.A.Hadid等[17]提出多流形局部線性嵌入算法，指出如果數(shù)據(jù)采樣不好會(huì)造成當(dāng)前很多LLE相關(guān)算法性能都會(huì)急劇下降，因此提出另外一種魯棒LLE算法;將訓(xùn)練樣本組成連通分支，如果存在多個(gè)連通分支，則認(rèn)為較小的連通分支是由噪聲點(diǎn)組成，因此只在較大的連通分支上應(yīng)用LLE算法.LLE算法存在的第2個(gè)問題，很多學(xué)者也給出了改進(jìn)方案，針對(duì)于圖像降維應(yīng)用問題，Liwei Wang等[18]提出圖像相似度計(jì)算的方法(IMED)[18]，Lijing Zhang 等[19]將其用于LLE算法中2個(gè)數(shù)據(jù)樣本相似性度量.ChangYin Zhou等[20]還提出了基于凸輪分布的 近鄰算法(camNN)，Yaozhang Pan 等[21]將其用于 LLE算法中2個(gè)數(shù)據(jù)樣本相似性度量.針對(duì)LLE算法存在的第3個(gè)問題，出現(xiàn)了新樣本的線性及非線性降維方法[22-24].

標(biāo)準(zhǔn)LLE算法在應(yīng)用K近鄰法時(shí)還存在如下問題:1)缺乏有效確定K值的方法，試湊法需要大量的時(shí)間;2)對(duì)K值過于敏感，從仿真實(shí)驗(yàn)效果看，不同的取值往往會(huì)造成完全不同的降維效果;3)固定K值不合理，由于數(shù)據(jù)樣本未必是均勻分布，故每個(gè)樣本周圍近鄰分布情況不同，針對(duì)不同的分布卻選擇相同的K值顯然并不合理.針對(duì)上述問題，眾多學(xué)者提出自適應(yīng)LLE算法，自動(dòng)確定每個(gè)樣本的近鄰數(shù)[16，25-30]，但這些算法在自動(dòng)確定K值時(shí)，往往引入新參數(shù)，而對(duì)于新參數(shù)的確定沒有給出具體方法.

本文提出基于自適應(yīng)近鄰的局部線性嵌入算法(ANLLE)，根據(jù)樣本數(shù)據(jù)分布情況不同，自動(dòng)為每個(gè)樣本分配不同數(shù)目的近鄰，解決了標(biāo)準(zhǔn)LLE算法的近鄰選取問題，且不需引入其他參數(shù).

1 局部降維

1.1 標(biāo)準(zhǔn)局部線性嵌入算法(LLE)

假設(shè)一幅圖像由m行n列像素組成，D=m×n表示原始圖像向量空間的維數(shù)，d表示降維后子空間的維數(shù)，K表示使用K近鄰算法時(shí)每個(gè)樣本選取的近鄰個(gè)數(shù)，X1、X2、…、XN表示D維空間的N個(gè)樣本，Y1，Y2，…，YN表示 d 維空間的 N 個(gè)樣本，Yi為Xi在d維空間的表示，一般d?D.

Sam T.Roweis等開創(chuàng)性的提出了標(biāo)準(zhǔn)LLE算法，核心思想是在高維空間的局部鄰域關(guān)系降維后在低維空間得到保持，即保證數(shù)據(jù)的局部結(jié)構(gòu)，算法分為如下 3 步[3，31]:

1)計(jì)算樣本間的歐氏距離，距離越小說明兩者相似度越高，依此原則確定每個(gè)樣本 Xi(i=1，2，…，N)的 K 個(gè)由近到遠(yuǎn)的近鄰 Xi1，Xi2，…，XiK;

2)對(duì)任意Xi，用其近鄰的線性組合重構(gòu)Xi，系數(shù)W(i)j表示在重構(gòu)時(shí)Xi的第j個(gè)近鄰所占的權(quán)重，為使重構(gòu)誤差最小，設(shè)置代價(jià)函數(shù)為

3)保證系數(shù)W(i)j不變，在d維子空間用各個(gè)樣本的近鄰重構(gòu)其本身，即求Y=[Y1Y2… YN]，使得重構(gòu)誤差最小，設(shè)置代價(jià)函數(shù)為

記W為N×N的稀疏矩陣，Wij為矩陣W的第i行第j列對(duì)應(yīng)的元素，如果Yj是Yi的近鄰，則Wij=，否則 Wij=0，設(shè) M=(I-W)T(I-W)，I為單位陣，限制.設(shè)矩陣M按升序排列的最小的d個(gè)非零特征值所對(duì)應(yīng)的特征向量為 q1，q2，…，qd，則最終求得

1.2 標(biāo)準(zhǔn)拉普拉斯映射(LM)算法及自動(dòng)確定近鄰的LM算法

Mikhail Belkin等[12]于2001年提出拉普拉斯映射算法(LM)，其理論基礎(chǔ)是圖譜理論，使用K近鄰法確定任意樣本的近鄰，用熱核方程確定拉普拉斯圖中邊的權(quán)值，即任意樣本Xi與其第j(j≤K)個(gè)近鄰Xij作為頂點(diǎn)的邊的系數(shù)為

LM算法的目標(biāo)是使任意Xi的近鄰在降維后仍然盡可能靠近Xi，即在低維空間所有點(diǎn)與其近鄰的距離和最小，因此有代價(jià)函數(shù):

式中:Yi為Xi在低維空間的表示，維數(shù)為d;Yij為Xi的第j個(gè)近鄰在低維空間的表示，其中是為了體現(xiàn)局部特征，而使得越靠近Xi的近鄰點(diǎn)所占權(quán)重越大;L=D-W稱為拉普拉斯算子，其中W為N×N的稀疏矩陣，Wij為矩陣W的第i行第j列對(duì)應(yīng)的元素，如果Yj是Yi的近鄰，則，否則Wij=0，D 為對(duì)角陣

文獻(xiàn)[12]算法證明了拉普拉斯映射中求L的特征向量近似等同于標(biāo)準(zhǔn)LLE算法中求M的特征向量.

Bo Yang等[32]提出自動(dòng)選擇近鄰 LM算法，算法根據(jù)每個(gè)樣本周圍數(shù)據(jù)分布情況確定該樣本的近鄰數(shù)，優(yōu)點(diǎn)在于解決了標(biāo)準(zhǔn)算法確定近鄰數(shù)的難題，而且不同樣本選用不同近鄰數(shù)，顯然比采用固定近鄰數(shù)的算法更合理.算法核心在于為每個(gè)樣本確定一個(gè)近鄰數(shù)閾值，即利用式(4)作為2個(gè)樣本間的相似性度量，則任意樣本Xi與所有樣本的平均相似度為

2 自適應(yīng)近鄰局部線性嵌入算法理論

同標(biāo)準(zhǔn)LM算法一樣，LLE算法同樣需要確定近鄰數(shù)，因此從 Bo Yang的論文[32]得到啟示，尋找一種適合LLE算法的相似性度量，然后確定合理閾值即可為每個(gè)樣本自動(dòng)尋找合適的近鄰.

分析自動(dòng)選擇近鄰的LM算法的相似性度量函數(shù)可知:1)函數(shù)以樣本間歐氏距離為自變量，且必須是單調(diào)遞減，單調(diào)性保證2個(gè)樣本距離不同則相似性一定不同，遞減則表示樣本距離越大相似度越小，具有現(xiàn)實(shí)意義;2)隨著自變量無限增大，函數(shù)極限為零，保證距離過大的2個(gè)樣本相似度基本為零，這樣如果用相似度均值作為閾值，則可保證閾值更多地取決于樣本附近的數(shù)據(jù).基于以上規(guī)則，針對(duì)LLE算法提出將圖像歐氏距離的倒數(shù)作為相似性度量，以歐氏距離倒數(shù)的均值作為近鄰選擇的閾值.選取此閾值，當(dāng)任意樣本Xi周圍數(shù)據(jù)比較密集時(shí)，閾值會(huì)相對(duì)靠近Xi，則在距離Xi較近處即可取到足夠近鄰;而當(dāng)Xi周圍數(shù)據(jù)比較稀疏時(shí)，閾值則會(huì)相對(duì)遠(yuǎn)離Xi，以便能夠取到足夠的近鄰.基于此種想法提出自適應(yīng)近鄰局部線性嵌入(ANLLE)算法.

2.1 算法描述

2.1.1 樣本近鄰確定

設(shè)存在 N 個(gè)數(shù)據(jù)樣本 X1，X2，…，XN，其中 Xi∈RD，(i=1，2，…，N)，計(jì)算任意 2 個(gè)樣本 Xi與 Xj相似度為

式中:分母表示兩樣本數(shù)據(jù)的2范數(shù)，則Xi與所有其他樣本的平均相似度為

式中:Mi即可作為近鄰選擇的閾值，即任意Xj與Xi的相似度如果大于Mi，則Xj是Xi的近鄰，否則不是.式(7)是雙曲線在第一象限的部分，即靠近Xi的數(shù)據(jù)點(diǎn)Sij值較大，遠(yuǎn)離Xi的數(shù)據(jù)點(diǎn)Sij值迅速減小，因此式(8)中Mi值將較偏向Xi，這樣可保證近鄰數(shù)不會(huì)很大，在一定程度上避免近鄰數(shù)過大導(dǎo)致的回路問題.

可采用二分法確定每個(gè)樣本近鄰數(shù)，具體描述如下:

1)對(duì)于任意Xi，將其他所有樣本按與Xi歐氏距離升序排序，賦初值 λmin=1，λmax=N-1，轉(zhuǎn)入2);

2)設(shè)置 λ =(λmin+ λmax)/2，如果滿足 Si■λ+1」≤Mi≤Si■λ」(■λ」表示對(duì) λ 下取整)則轉(zhuǎn)入 4)，否則轉(zhuǎn)入3);

3)計(jì)算Xi與X■λ」的相似度，如果相似度大于Mi，則設(shè)置λmin=■λ」，否則設(shè)置 λmax=■λ」，轉(zhuǎn)入2);

4)確定λi=■λ」為Xi的近鄰數(shù)，算法結(jié)束.

2.1.2 訓(xùn)練樣本降維

每一個(gè)樣本的近鄰確定完畢后，可據(jù)此對(duì)訓(xùn)練樣本降維，過程可參照標(biāo)準(zhǔn)LLE算法，但有幾點(diǎn)需要說明:

1)求解系數(shù)的代價(jià)函數(shù)為

注意與式(2)比較，式(9)的求和公式中用λi代替K，即針對(duì)每一個(gè)Xi值，用于重構(gòu)的近鄰數(shù)是不同的;

2)求解M=(I-W)T(I-W)的特征向量時(shí)，M中的矩陣W與標(biāo)準(zhǔn)LLE算法中M中的矩陣W有很大不同，標(biāo)準(zhǔn)算法中W的每一列都有且僅有K個(gè)非零元素，但本算法中W的每一列非零元素不同，即W的第i列有且僅有λi個(gè)非零元素.最終求得

2.1.3 待測(cè)樣本分類

首先確定待測(cè)樣本重構(gòu)近鄰數(shù)，然后再對(duì)待測(cè)樣本降維，最后在低維空間使用最近鄰法將待測(cè)樣本分類，具體描述如下.

對(duì)任意待測(cè)樣本Xtest，其與訓(xùn)練樣本中任意樣本 Xi的相似度為 Stesti=1/‖Xtest-Xi‖，Xtest與所有訓(xùn)練樣本的平均相似度為

以 Mtest為閾值，用二分法確定 Xtest的近鄰數(shù)λtest，進(jìn)而確定 Xtest的近鄰，用式(2)計(jì)算出重構(gòu)系數(shù)，設(shè)Xtest的近鄰在d維空間對(duì)應(yīng)向量為 Ytest1、Ytest2、…、Ytestλtest，則 Xtest1在 d 空間的表示為

最后利用最近鄰法，在低維空間尋找距Ytest最近點(diǎn)，其所屬分類即是Ytest所屬分類.注意，測(cè)試樣本的降維過程依賴于樣本分布局部線性的假設(shè)，這也是LLE算法的基礎(chǔ)，因此假設(shè)是合理的，詳細(xì)描述可參考文獻(xiàn)[22].

2.2 ANLLE算法理論分析

ANLLE算法關(guān)鍵在于采用歐氏距離的倒數(shù)作為相似性度量，并據(jù)此利用式(8)計(jì)算每個(gè)樣本的近鄰數(shù)，下面比較此相似性度量對(duì)于直接使用歐氏距離作為相似性度量的優(yōu)勢(shì).

不妨假設(shè)樣本均勻分布并均勻取值，假設(shè)共有n+1個(gè)樣本，樣本X與其余n個(gè)樣本的相似度分別為:1、1/2、1/3、1/4、…、1/n，根據(jù)式(8)計(jì)算平均相似度為

可知，當(dāng)n趨于無窮大時(shí)有

式中:c=0.577 215 664 9為歐拉常數(shù)，則有

因此，用式(8)計(jì)算出來的近鄰數(shù)是有界的，不會(huì)隨著訓(xùn)練樣本的增加而不斷增大，可以有效避免近鄰數(shù)太大出現(xiàn)的回路問題;而如果用歐氏距離作為相似性度量，則隨著樣本的增加，近鄰數(shù)不斷增大，不可避免的會(huì)造成回路問題.

3 仿真實(shí)驗(yàn)及結(jié)果分析

將標(biāo)準(zhǔn)LLE算法、NLE算法及ANLLE算法分別應(yīng)用于ORL人臉數(shù)據(jù)庫及USPS手寫數(shù)字?jǐn)?shù)據(jù)庫，并對(duì)3種算法的性能進(jìn)行比較分析.注意，實(shí)驗(yàn)過程中將 NLE算法的調(diào)節(jié)參數(shù) γ設(shè)置為1，即lnγ=0，則NLE也變?yōu)橥耆赃m應(yīng)算法，這樣易于與ANLLE算法進(jìn)行性能比較.

3.1 ORL人臉數(shù)據(jù)庫上的實(shí)驗(yàn)及性能分析

ORL人臉數(shù)據(jù)庫由40個(gè)人的臉部圖像組成，每個(gè)人提供10幅不同圖像，每幅圖像為112×92像素，包括在不同時(shí)間、光照、人臉表情(睜、閉眼，微笑、不笑)、面部細(xì)節(jié)(是否戴眼鏡)取得的圖片，背景相同，前視圖有輕微傾斜，圖1為其中一人的全部圖像.

將圖像分為10組，每組40幅圖像，由40個(gè)不同人的臉部圖像組成，采用留一法進(jìn)行測(cè)試，即每次選取1組作為測(cè)試樣本，其余9組作為訓(xùn)練樣本，直到所有樣本均已當(dāng)選且僅當(dāng)選過一次測(cè)試樣本.

圖1 ORL數(shù)據(jù)庫示例Fig.1 Samples on ORL

對(duì)標(biāo)準(zhǔn)LLE算法子空間維數(shù)d分別設(shè)置為30、40、50及60，在每個(gè)子空間近鄰數(shù)d分別設(shè)置為5、10、20、30、40、50 及 60 進(jìn)行實(shí)驗(yàn)，對(duì)于 NLE 及 ANLLE算法，由于無需手動(dòng)設(shè)置近鄰數(shù)K，所以只需分別設(shè)置子空間維數(shù)d進(jìn)行實(shí)驗(yàn)即可.實(shí)驗(yàn)結(jié)果如圖2及3所示.

圖2 LLE算法在ORL庫上的識(shí)別率Fig.2 Recognition rate of LLE algorithm on ORL

圖2中描述了不同子空間中選擇不同近鄰數(shù)時(shí)，LLE算法在ORL人臉數(shù)據(jù)庫上的識(shí)別率.從圖2中可以看出，在K=60且d=30及K=60且d=60時(shí)取得最低識(shí)別率84.25%，在K=5且d=60時(shí)取得最高識(shí)別率93.25%.在各個(gè)子空間中不同的K值使得識(shí)別率也不同，但從圖中以看出在不同子空間中均是在K=5時(shí)取得最高識(shí)別率，因此采用K=5時(shí)LLE算法的識(shí)別率與NLE算法及ANLLE算法識(shí)別率進(jìn)行比較，比較結(jié)果如圖3所示.

圖3 3種算法在ORL庫上的識(shí)別率比較Fig.3 The comparison of recognition rates of the three algorithms on ORL

從圖3中可以看出標(biāo)準(zhǔn)LLE算法當(dāng)K=5時(shí)在30、40、50、60 維子空間的識(shí)別率分別為 88.5%、90%、91.25%、93.25%，NLE 算法在相應(yīng)子空間的識(shí)別率為 91%、91.75%、92.25%、92.5%，ANLLE算法在相應(yīng)子空間的識(shí)別率分別為95.5%、96.5%、95.25%、95.5%.由此可以得出，在各個(gè)不同子空間ANLLE算法識(shí)別率均優(yōu)于標(biāo)準(zhǔn)LLE算法及NLE算法.

3.2 USPS手寫數(shù)字?jǐn)?shù)據(jù)庫上的實(shí)驗(yàn)及性能分析

USPS手寫數(shù)字?jǐn)?shù)據(jù)庫由0～9數(shù)字圖像組成，每個(gè)數(shù)字有1 100個(gè)不同手寫圖像，每幅圖像像素為16×16，圖4為其中部分圖像.

圖4 USPS數(shù)據(jù)庫示例Fig.4 Samples on USPS

從0～9中每個(gè)數(shù)字選擇100幅圖像，共計(jì)1 000幅作為訓(xùn)練樣本，然后從剩余圖像中每個(gè)數(shù)字選擇200幅圖像，共計(jì)2 000幅圖像作為測(cè)試樣本進(jìn)行實(shí)驗(yàn).

對(duì)標(biāo)準(zhǔn)LLE算法子空間維數(shù)d分別設(shè)置為30、40、50及60，在每個(gè)子空間近鄰數(shù)K從5～60中每隔5取一次值進(jìn)行實(shí)驗(yàn)，對(duì)于ANLLE算法及NLE算法，同樣只需分別設(shè)置子空間維數(shù)d為30、40、50及60進(jìn)行實(shí)驗(yàn)即可.實(shí)驗(yàn)結(jié)果如圖5及6所示.

圖5 LLE算法在USPS庫上的識(shí)別率Fig.5 Recognition rate of LLE algorithm on USPS

圖5中描述了不同子空間中選擇不同近鄰數(shù)時(shí)LLE算法在USPS手寫數(shù)字?jǐn)?shù)據(jù)庫上的識(shí)別率.可以看出，并沒有出現(xiàn)類似ORL庫中不同子空間均在一個(gè)K值取得最好識(shí)別率現(xiàn)象，當(dāng)子空間維數(shù)為30時(shí)，在K=25處取得最高識(shí)別率75.9%;維數(shù)為40時(shí)，在K=20處取得最高識(shí)別率77.25%;維數(shù)為50時(shí)，K=30處取得最高識(shí)別率77.15%;維數(shù)為60時(shí)，K=30處取得最高識(shí)別率77.5%.選取LLE算法在各個(gè)子空間最高的識(shí)別率與ANLLE算法及NLE算法進(jìn)行比較，結(jié)果如圖6所示.

圖6 3種算法在USPS庫上的識(shí)別率比較Fig.6 The comparison of recognition rates on USPS

從圖6中可以看出，ANLLE算法及NLE算法在不同維數(shù)識(shí)別率均優(yōu)于標(biāo)準(zhǔn)LLE算法，在30、40維子空間，ANLLE算法識(shí)別率高于NLE算法，而40、50維子空間NLE算法識(shí)別率高于ANLLE算法，但對(duì)比實(shí)驗(yàn)在ANLLE算法30維子空間處取得最高識(shí)別率 86.95%，大于 NLE的 83.15% 及 LLE的77.5%.

從與標(biāo)準(zhǔn)LLE算法的對(duì)比實(shí)驗(yàn)可以看出，ANLLE算法不但簡化了手工確定K值的步驟，而且取得更好的識(shí)別率.從與NLE算法的對(duì)比實(shí)驗(yàn)分析，ANLLE算法計(jì)算近鄰過程所需時(shí)間更短，而識(shí)別率卻更高.因此綜上所述，ANLLE算法相對(duì)于其他算法的優(yōu)點(diǎn)主要有:1)正確識(shí)別率高;2)自動(dòng)確定每個(gè)樣本所需近鄰;3)訓(xùn)練時(shí)間較短.

4 結(jié)論

提出ANLLE算法，相比較標(biāo)準(zhǔn)LLE算法有以下2個(gè)優(yōu)點(diǎn):

1)自動(dòng)確定每個(gè)樣本的近鄰數(shù)，效率高于標(biāo)準(zhǔn)LLE算法中常用的試湊法確定近鄰;

2)根據(jù)樣本周圍數(shù)據(jù)分布情況確定其近鄰數(shù)，這比無論分布情況如何一律采用相同近鄰數(shù)的標(biāo)準(zhǔn)LLE算法更合理，在ORL及USPS庫上的實(shí)驗(yàn)證明，ANLLE算法識(shí)別率明顯高于標(biāo)準(zhǔn)LLE算法.

除LLE算法外，局部切空間映射(LTSA)及漢森映射(HLLE)等算法均是較優(yōu)秀的局部流形學(xué)習(xí)方法，同樣可以考慮將自動(dòng)選擇近鄰的方法應(yīng)用于這些算法，這將作為后續(xù)研究內(nèi)容.

[1]SEUNG H S，LEE D D.The manifold ways of perception[J].Science，2000，290(5500):2268-2269.

[2]TENENBAUM J B，DESILVA V，LANGFORD J C.A global geometric framework for nonlinear dimensionality reduction[J].Science，2000，290(5500):2319-2323.

[3]ROWEIS S T，SAUL L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science，2000，290(5500):2323-2326.

[4]徐蓉，姜峰，姚鴻勛.流形學(xué)習(xí)概述[J].智能系統(tǒng)學(xué)報(bào)，2006，1(1):44-51.XU Rong，JIANG Feng，YAO Hongxun.Overview of manifold learning[J].CAAI Transactions on Intelligent Systems，2006，1(1):44-51.

[5]尹峻松，肖健，周宗潭，等.非線性流形學(xué)習(xí)方法的分析與應(yīng)用[J].自然科學(xué)進(jìn)展，2007，17(8):1015-1025.YIN Junsong，XIAO Jian，ZHOU Zongtan，et al.Analysis and application of nonlinear manifold learning method[J].Progress in Natural Science，2007，17(8):1015-1025.

[6]何力，張軍平，周志華.基于放大因子和延伸方向研究流形學(xué)習(xí)算法[J].計(jì)算機(jī)學(xué)報(bào)，2005，28(12):2000-2009.HE Li， ZHANG Junping， ZHOU Zhihua. Investigating manifold learning algorithms based on magnification factors and principal spread directions[J].Chinese Journal of Computers，2005，28(12):2000-2009.

[7]趙連偉，羅四維，趙艷敞，等.高維數(shù)據(jù)流形的低維嵌入及嵌入維數(shù)研究[J].軟件學(xué)報(bào)，2005，16(8):1423-1430.ZHAO Lianwei，LUO Siwei，ZHAO Yanchang，et al.Study on the low-dimensional embedding and the embedding dimensionality of manifold of high-dimensional data[J].Journal of Software，2005，16(8):1423-1430.

[8]詹德川，周志華.基于集成的流形學(xué)習(xí)可視化[J].計(jì)算機(jī)研究與發(fā)展，2005，42(9):1533-1537.ZHANG Dechuan，ZHOU Zhihua.Ensemble-based manifold learning for visualization[J].Journal of Computer Research and Development，2005，42(9):1533-1537.

[9]孟德宇，徐宗本，戴明偉.一種新的有監(jiān)督流形學(xué)習(xí)方法[J].計(jì)算機(jī)研究與發(fā)展，2007，44(12):2072-2077.MENG Deyu，XU Zongben，DAI Mingwei.A new supervised manifold learning method[J].Journal of Computer Research and Development，2007，44(12):2072-2077.

[10]馬瑞，王家廞，宋亦旭.基于局部線性嵌入(LLE)非線性降維的多流形學(xué)習(xí)[J].清華大學(xué)學(xué)報(bào):自然科學(xué)版，2008，48(14):583-586.MA Rui，WANG Jiaxin，SONG Yixue.Multi-manifold learning using locally linear embedding(LLE)nonlinear dimensionality reduction[J].J Tsinghua Univ:Sci＆Tech，2008，48(14):583-586.

[11]馮海亮，李見為，王旭初，等.基于非線性子流形的人臉識(shí)別[J].重慶大學(xué)學(xué)報(bào)，2008，31(3):303-306.FENG Hailiang，LI Jianwei，WANG Xuchu，et al.Face recognition based on nonlinear manifold learning[J].Journal of Chongqing University，2008，31(3):303-306.

[12]MIKHAIL B ，PARTHA N.Laplacian eigenmaps for dimension reduction and data representation[J].Neural Computation，2001，15(6):1373-1396.

[13]RIDDER D D，KOUROPTEVA O，OKUN O，et al.Supervised locally linear embedding[R].Stuttgart:Lecture Notes in Computer Science，2003.

[14]ZHANAG Shiqing.Enhanced supervised locally linear embedding[J].Pattern Recognition Letters，2009，30(13):1208-1218.

[15]CHANG Hong，YEUNG D Y.Robust locally linear embedding[J]. PatternRecognition， 2006，39(6):1053-1065.

[16]SAM G S，F(xiàn)ENG G，PAN Y Z，et al.Neighborhood linear embedding for intrinsic structure discovery[J].Machine Vision and Applications，2008，21(3):391-401.

[17]ABDENOUR H，MATTI P.Efficient locally linear embeddings of imperfect manifolds[C]//Proceedings of the Third International Conference on Machine Learning and Data Mining in Pattern Recognition.Leipzig，Germany，2003:188-201.

[18]WANG Liwei，ZHANG Yan，F(xiàn)ENG Jufu.On the Euclidean distance of images[J].IEEE Transactions on Pattern A-nalysis and Machine Intelligence，2005，27(8):1334-1339.

[19]ZHANG Lijing，WANG Ning.Locally linear embedding based on image Euclidean distance[C]//2007 IEEE International Conference on Automation and Logistics.Jinan，China，2007:1914-1918.

[20]ZHOU Changyin，CHEN Yanqiu.Improving nearest neighbor classification with cam weighted distance[J].Pattern Recognition，2006，39(4):635-645.

[21]PAN Yaozhang，GE S S，MAMUN A A.Weighted locally linear embedding for dimension reduction[J].Pattern Recognition，2009，42(5):798-811.

[22]DICK D R，ROBERT P W.Locally linear embedding for classification.PH-2002-01[R].Delft:Delft University of Technology，2002.

[23]OLGA K，OLEG O，PIETIKAINEN M.Incremental locally linear embedding[J].Pattern Recognition，2005，38(10):1764-1767.

[24]HE Xiaofei，CAI Deng，YAN Shuicheng，et al.Neighborhood preserving embedding[C]//Tenth IEEE International Conference on Computer Vision.Beijing，China，2005:1208-1213.

[25]文貴華，江麗君，文軍.基于鄰域優(yōu)化的局部線性嵌入[J].系統(tǒng)仿真學(xué)報(bào)，2007，19(13):3119-3122.WEN Guihua，JIANG Lijun，WEN Jun.Locally linear embedding based on optimization of neighborhood[J].Journal of System Simulation，2007，19(13):3119-3122.

[26]李博，楊丹，雷明，等.基于近鄰消息傳遞的自適應(yīng)局部線性嵌入[J].光電子·激光，2010，21(5):772-778.LI Bo，YANG Dan，LEI Ming，et al.Adaptive locally linear embedding based on affinity propagation[J].Journal of Optoelectronics·Laser，2010，21(5):772-778.

[27]文貴華，江麗君，文軍.鄰域參數(shù)動(dòng)態(tài)變化的局部線性嵌入[J].軟件學(xué)報(bào)，2008，19(7):1666-1673.WEN Guihua，JIANG Lijun，WEN Jun.Dynamically determining neighborhood parameter for locally linear embedding[J].Journal of Software，2008，19(7):1666-1673.

[28]喻軍，秦如新，鄧乃揚(yáng).基于自適應(yīng)最近鄰的局部線性嵌入算法[J].控制工程，2006，13(5):469-470.YU Jun，QIN Ruxin，DENG Naiyang.Locally linear embedding algorithm based on adaptive nearest neighbor[J].Control Engineering of China，2006，13(5):469-470.

[29]惠康華，肖柏華，王春恒.基于自適應(yīng)近鄰參數(shù)的局部線性嵌入[J].模式識(shí)別與人工智能，2010，23(6):842-846.HUI Kanghua，XIAO Baihu，WANG Chunheng.Self-regulation of neighbourhood parameter for loally linear embedding[J].Pattern Recognition and Artificial Intelligence，2010，23(6):842-846.

[30]張育林，莊健，王娜，等.一種自適應(yīng)局部線性嵌入與譜聚類融合的故障診斷方法[J].西安交通大學(xué)學(xué)報(bào)，2010，44(1):77-82.ZHANG Yulin，ZHUANG Jian，WANG Na，et al.Fusion of adaptive local linear embedding and spectral clustering algorithm with application to fault diagnosis[J].Journal of Xi＇an Jiaotong University，2010，44(1):77-82.

[31]SAUL L K，ROWEIS S T.Think globally，fit locally:unsupervised learning of low dimensional manifolds[J].Journal ofMachineLearningResearch， 2004，4(2):119-155.

[32]YANG B，CHEN S C.Sample-dependent graph construction with application to dimensionality reduction[J].Neurocomputing，2010，74(1):301-314.