摘  要： 擴(kuò)散映射（Diffusion Maps）是一種基于流形學(xué)習(xí)的非線性降維方法,?；趯U(kuò)散映射的研究，提出了一種新的非線性降維算法,。根據(jù)近鄰點(diǎn)分布的不同和模糊聚類原理,，新算法定義了擴(kuò)散映射算法構(gòu)建權(quán)值矩陣的誤差近似系數(shù)，并采用改進(jìn)的距離公式來選取樣本點(diǎn)的近鄰點(diǎn),，很大程度地降低了近鄰點(diǎn)的選取對降維效果的影響,。實(shí)驗(yàn)結(jié)果表明，新算法有效地保持了高維數(shù)據(jù)中的流形結(jié)構(gòu),，具有更好的降維效果,，并在基于內(nèi)容的圖像檢索中達(dá)到很高的查準(zhǔn)率，新算法的有效性和優(yōu)越性得到了證實(shí),。
　　關(guān)鍵詞： 擴(kuò)散映射,；降維；流形學(xué)習(xí),；聚類
0 引言
　　流形是局部具有歐幾里得空間性質(zhì)的空間,，包括各種維數(shù)的曲線、曲面等,，是一般的幾何對象的總稱,。流形學(xué)習(xí)[1-3]以流形理論為基礎(chǔ)，把高維空間中的樣本集在低維空間中重新表示出來,，并能求出其相應(yīng)的嵌入映射,，很好地保持了樣本點(diǎn)的拓?fù)浣Y(jié)構(gòu)，達(dá)到了維數(shù)約簡的目的,。流形學(xué)習(xí)方法減少了高維數(shù)據(jù)的冗余性,，解決了維數(shù)災(zāi)難的問題，因此,，流形學(xué)習(xí)具有非常重要的研究意義,。目前，流形學(xué)習(xí)的方法主要分為兩類：一類是線性降維方法,，主要有主成分分析（Principal Component Analysis,，PCA）[4]、獨(dú)立分量分析（Independent Component Analysis,，ICA）[5],、多維尺度分析（Multidimensional Scaling,，MDS）[6]等；另一類是非線性降維方法,，主要有核主成分分析（Kernel Principal Component Analysis,，KPCA）[7]、等度規(guī)映射（Isometric Mapping,，Isomap）[8],、局部線性嵌入（Locally Linear Embedding，LLE）[9]等,。
　　擴(kuò)散映射（Diffusion Maps,，DM）[10]是COIFMAN R等人在2006年提出的一種基于流形學(xué)習(xí)的非線性降維方法，其主要思想來自于動(dòng)力系統(tǒng),。作為一種新的流形學(xué)習(xí)框架,，擴(kuò)散映射通過在擴(kuò)散過程中盡可能地保持?jǐn)U散距離來進(jìn)行降維，即保持樣本點(diǎn)的局部結(jié)構(gòu)不變,，通過局部關(guān)系定義全局關(guān)系,，使樣本點(diǎn)在低維空間中仍保持這種穩(wěn)定的全局關(guān)系。近鄰點(diǎn)選取和分布的不同可產(chǎn)生不同的鄰接圖,，對擴(kuò)散映射的降維效果影響很大,，由此本文提出了一種改進(jìn)的算法。由于聚類的中心含有大量的信息,，新算法根據(jù)聚類原理,，先定義了擴(kuò)散映射構(gòu)建權(quán)值矩陣的誤差近似系數(shù)，然后利用改進(jìn)的距離函數(shù)來選取近鄰點(diǎn),，構(gòu)建鄰接圖,。新算法模糊了近鄰點(diǎn)的選取對實(shí)驗(yàn)結(jié)果的影響，達(dá)到了較為理想的降維效果,，并在實(shí)驗(yàn)中得到了證實(shí)。
　　1 Diffusion Maps（DM）算法
　　DM算法主要分為如下4步：
　?。?）構(gòu)建鄰接圖,。對于給定的數(shù)據(jù)集X={x1，x2,，…,，xN}，xi∈RD,，i=1,，2，…,，N,，若xi是xj的近鄰點(diǎn)，則將xi與xj之間賦一個(gè)邊，邊反映了樣本點(diǎn)之間的局部關(guān)系,，近鄰點(diǎn)一般用歐氏距離來度量,，距離公式為：
　

　（2）構(gòu)建權(quán)值矩陣W,。權(quán)值矩陣的元素Wij（W（xi,，xj））反映樣本點(diǎn)xi與xj之間的相似程度，因此滿足：
　?、賅是對稱的：Wij=Wji,；
　　②W是非負(fù)的：Wij≥0,。
　　一般采用高斯核函數(shù)定義成對數(shù)據(jù)點(diǎn)之間的相似度矩陣,，即：

　　其中，為高斯核的方差,，越大,，權(quán)值越大，數(shù)據(jù)點(diǎn)間的相似程度越大,。
　?。?）構(gòu)建擴(kuò)散核矩陣K。利用加權(quán)的圖Laplacian歸一化方法,。

　　其中,，Wi表示xi與其他各點(diǎn)的權(quán)值之和。
　?。?）核矩陣K的特征分解,。對內(nèi)積矩陣K進(jìn)行特征分解，求K的特征值和特征向量,，K的最大的d個(gè)特征值λ1,，λ2，…,，λd對應(yīng)的特征向量為U=[u1,，u2，…,，ud],，則高維數(shù)據(jù)X降維后的數(shù)據(jù)集為Y=UT=[u1，u2,，…,，ud]T。
2 新算法的提出
　　2.1聚類原理
　　聚類是解決高維數(shù)據(jù)問題的常用方法,。聚類分類產(chǎn)生一些簇,，簇是一組數(shù)據(jù)對象的集合,，同一簇中的對象相似，不同簇中的對象相異,，每個(gè)簇的中心含有豐富的可利用的信息,，具有代表性。模糊C均值（Fuzzy C-Means,，F(xiàn)CM）算法[11-13]是應(yīng)用最廣泛的聚類分析方法之一,。
　　對于給定的采樣于維流形的高維觀測數(shù)據(jù)集X={x1，x2,，…,，xN}，xi∈RD,，i=1,，2，…,，D,。設(shè)樣本點(diǎn)聚類分類的類別個(gè)數(shù)為M，第j類樣本的中心為cj,，第j類樣本的個(gè)數(shù)為rj,，總體樣本的中心為c。則定義第j類樣本點(diǎn)的類內(nèi)平均距離為：

　　第j類樣本中心與總體樣本中心的距離為：

　　其中,，‖‖表示歐式距離,。由此，定義樣本點(diǎn)構(gòu)建權(quán)值矩陣的誤差近似系數(shù)為：

　　其中,，j為樣本點(diǎn)xi所屬的類,。
　　用誤差近似系數(shù)重新構(gòu)建樣本點(diǎn)在低維空間上嵌入的權(quán)值矩陣，從而提高樣本點(diǎn)之間的相似程度,，獲得更好的實(shí)驗(yàn)結(jié)果,。
　　2.2 改進(jìn)的距離函數(shù)
　　對于分布不均勻的數(shù)據(jù)集，假設(shè)P為分布密集的區(qū)域上的點(diǎn),，其k個(gè)近鄰點(diǎn)所占的區(qū)域?yàn)镾P,，O為分布稀疏的區(qū)域上的點(diǎn)，其k個(gè)近鄰點(diǎn)所占的區(qū)域?yàn)镾O,，顯然SP要比SO小得多,。因此對于分布不均勻的樣本集,，近鄰點(diǎn)k個(gè)數(shù)的選取會(huì)影響實(shí)驗(yàn)結(jié)果,。所以要對近鄰點(diǎn)間的距離進(jìn)行改進(jìn)，降低樣本點(diǎn)分布的影響,。下面定義一種新的距離[14-15],。

　　其中,，Gi、Gj分別表示xi,、xj和其他點(diǎn)之間距離的平均值,。
　　因?yàn)樾碌木嚯x的分子是歐氏距離，分母是數(shù)值,，則有：
　?、俜秦?fù)性：dij≥0，當(dāng)且僅當(dāng)xi=xj,，即i=j時(shí)等號(hào)成立,；
　　②對稱性：dij=dji,；
　?、廴遣坏仁叫裕篸is+dsj≥dij。
　　由泛函分析知識(shí)可知,，新的距離滿足距離空間的定義,。在DM的第一步構(gòu)建鄰接圖時(shí)，采用新的距離公式取代歐氏距離來選取樣本點(diǎn)的k個(gè)近鄰點(diǎn),。新的距離使分布較密集區(qū)域的樣本點(diǎn)間的距離增大,，而使分布較稀疏區(qū)域的樣本點(diǎn)間的距離縮小，這樣區(qū)域SP和SO區(qū)域的差異性減小,，樣本點(diǎn)的整體分布趨于均勻化,，從而降低樣本點(diǎn)的分布對算法效果的影響。
　　2.3改進(jìn)的算法（Improved Diffusion Maps,，IMDM）
　　IMDM算法的步驟如下：
　?。?）對樣本集進(jìn)行聚類分類，得出構(gòu)建權(quán)值矩陣的誤差近似系數(shù)：

　?。?）構(gòu)建鄰接圖,。距離公式為：

　　（3）構(gòu)建權(quán)值矩陣W′,。

　?。?）構(gòu)建擴(kuò)散核矩陣K′。

　?。?）核矩陣K′的特征分解,。求K′的特征值和特征向量，K′的最大的d個(gè)特征值λ′1,，λ′2,，…，λ′d對應(yīng)的特征向量為U′=[u′1,，u′2,，…,，u′d]，則高維數(shù)據(jù)X降維后的數(shù)據(jù)集為Y=[U′]T=[u′1,，u′2,，…，u′d]T,。
　　新算法首先對樣本集進(jìn)行聚類分類,，利用類別信息得出構(gòu)建權(quán)值矩陣的誤差近似系數(shù)，然后采用新的距離函數(shù)選取近鄰點(diǎn)構(gòu)建鄰接圖,，這樣可適當(dāng)降低近鄰點(diǎn)個(gè)數(shù)k的選取對算法的影響,，得到較好的降維效果。
3 實(shí)驗(yàn)結(jié)果及分析
　　3.1人工數(shù)據(jù)
　　用DM和IMDM對Scurve人工數(shù)據(jù)集（如圖1所示）進(jìn)行降維,，實(shí)驗(yàn)選取2 000個(gè)樣本點(diǎn),，近鄰點(diǎn)的個(gè)數(shù)分別取8、12,，將數(shù)據(jù)集降至2維,，實(shí)驗(yàn)結(jié)果如圖2所示。從圖2中可以看出,，IMDM比DM具有更好的降維效果,，模糊了近鄰點(diǎn)個(gè)數(shù)的選取，降維效果比較理想,，具有更好的可視化效果,。

　　3.2 圖像檢索
　　在基于內(nèi)容的圖像檢索實(shí)驗(yàn)中，圖像選自Corel數(shù)據(jù)庫,，共1 000幅圖像,，類別為10種，有建筑,、風(fēng)景,、人物、動(dòng)物,、植物等,。實(shí)驗(yàn)對第450號(hào)恐龍圖像進(jìn)行相關(guān)圖像檢索，降至維數(shù)d分別取6,、14,、20，檢索出的圖像數(shù)目設(shè)為20,。實(shí)驗(yàn)一先用DM方法對圖像數(shù)據(jù)集降維然后進(jìn)行檢索,，得出實(shí)驗(yàn)結(jié)果如圖3中的（a）、（c）、（e）所示,。實(shí)驗(yàn)二先用IMDM方法對圖像數(shù)據(jù)集降維再進(jìn)行檢索，得出實(shí)驗(yàn)結(jié)果如圖3中的（b）,、（d）,、（f）所示。對比兩次實(shí)驗(yàn)結(jié)果,，可以清晰地看出,，IMDM降維后進(jìn)行基于內(nèi)容的圖像檢索的準(zhǔn)確率明顯高于DM的。

　　查準(zhǔn)率是衡量圖像檢索算法有效性的常用指標(biāo),，查準(zhǔn)率越高,，表示圖像檢索方法越好，反之越差,。

　　圖4為在維數(shù)不同時(shí),，DM和IMDM查準(zhǔn)率的變化情況?？梢钥闯?，多數(shù)情況下IMDM降維后圖像檢索的查準(zhǔn)率高于DM的。特別地,，當(dāng)維數(shù)為20時(shí),，應(yīng)用IMDM方法，查準(zhǔn)率達(dá)到了100%,。

4 結(jié)論
　　本文對基于流形學(xué)習(xí)的擴(kuò)散映射非線性降維方法進(jìn)行了分析研究,，提出了一種改進(jìn)的擴(kuò)散映射非線性降維方法。此方法以聚類分類原理構(gòu)造權(quán)值矩陣的誤差近似系數(shù),，通過改變樣本點(diǎn)間的距離公式重新構(gòu)建鄰接圖,，進(jìn)而實(shí)現(xiàn)降維。新算法有效地降低了近鄰點(diǎn)的選取對降維效果的影響,，并且很好地保留了原始數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu),。將改進(jìn)的擴(kuò)散映射方法用于Scurve數(shù)據(jù)集和基于內(nèi)容的圖像檢索實(shí)驗(yàn)，都得到了很好的效果,，具有很好的實(shí)際應(yīng)用價(jià)值,。
　　參考文獻(xiàn)
　　[1] ORSENIGO C， VERCELLISN C. Kernel ridge regres-sion for out-of-sample mapping in supervised manifold learning[J]. Expert Systems with Application,， 2012,，39（9）：7757-7762.
　　[2] 曹林林.基于流形學(xué)習(xí)的分類技術(shù)[D].濟(jì)南：山東師范大學(xué)，2013.
　　[3] 王自強(qiáng),，錢旭,，孔敏.流形學(xué)習(xí)算法綜述[J].計(jì)算機(jī)工程與應(yīng)用，2008,，44（35）：9-12.
　　[4] 曾憲華,，羅四維.全局保持的流形學(xué)習(xí)算法對比研究[J].計(jì)算機(jī)工程與應(yīng)用,，2010，46（15）：1-6.
　　[5] HYVARINEN A,， OJA E. Independent component analysis：algorithms and applications[J]. Neural Networks,， 2000，13（45）： 411-430.
　　[6] COX T,， COX M. Multidimensional scaling[M]. London：Chapman&Hall,， 1994.
　　[7] SCHOLKOPF B， SMOLA A,， MULLER K R. Nonliner co- mponent analysis as a kernel eigenvalue problem[J]. Neural Computation,，1998，10（5）：1299-1319
　　[8] THEODORIDIS S,，KOUTROUMBAS K.模式識(shí)別（第4版）[M].李晶皎,，王愛俠，王驕,，等譯.北京：電子工業(yè)出版社,，2010.
　　[9] Zhang Zhenyue， Zha Hongyuan. Principal manifold and nonlinear dimensionality reduction via local tangent space alignment[J]. SIAM Journal of Scientific Computing,， 2004,，26（1）：313-338.
　　[10] COIFMAN R， LAFON S. Diffusion maps. Applied and computational harmonic analysis[EB/OL]. [2006-05-30].http： www.elsevier.com/locate/acha.
　　[11] 姜倫,，丁華福.關(guān)于模糊C-均值（FCM）聚類算法的改進(jìn)[J].計(jì)算機(jī)與數(shù)字工程,，2010，38（2）：4-6.
　　[12] 蘇錦旗,，張文宇.基于模糊聚類的改進(jìn)LLE算法[J],，計(jì)算機(jī)與現(xiàn)代化，2014,，225（5）：9-13.
　　[13] BEZDEK J C,， EHRLICH R. Full W. FCM： the fuzzy c-means clustering algorithm[J]. Computers & Geosciences，1984,，10（2）：191-203.
　　[14] 王和勇,，鄭杰，姚正安.基于聚類和改進(jìn)距離的LLE方法在數(shù)據(jù)降維中的應(yīng)用[J],，計(jì)算機(jī)研究與發(fā)展,，2006，43（8）：1485-1490.
　　[15] JOSHUA B T,， VIN.DE S,， LANGFORD J C. A global geometric framework for nonliner dimensionality reduction[J]. Science， 2000，290：2319-2323.