摘  要： 擴(kuò)散映射（Diffusion Maps）是一種基于流形學(xué)習(xí)的非線性降維方法。基于對(duì)擴(kuò)散映射的研究，提出了一種新的非線性降維算法。根據(jù)近鄰點(diǎn)分布的不同和模糊聚類原理，新算法定義了擴(kuò)散映射算法構(gòu)建權(quán)值矩陣的誤差近似系數(shù)，并采用改進(jìn)的距離公式來選取樣本點(diǎn)的近鄰點(diǎn)，很大程度地降低了近鄰點(diǎn)的選取對(duì)降維效果的影響。實(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ù)的曲線、曲面等，是一般的幾何對(duì)象的總稱。流形學(xué)習(xí)[1-3]以流形理論為基礎(chǔ)，把高維空間中的樣本集在低維空間中重新表示出來，并能求出其相應(yīng)的嵌入映射，很好地保持了樣本點(diǎn)的拓?fù)浣Y(jié)構(gòu)，達(dá)到了維數(shù)約簡(jiǎn)的目的。流形學(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)生不同的鄰接圖，對(duì)擴(kuò)散映射的降維效果影響很大，由此本文提出了一種改進(jìn)的算法。由于聚類的中心含有大量的信息，新算法根據(jù)聚類原理，先定義了擴(kuò)散映射構(gòu)建權(quán)值矩陣的誤差近似系數(shù)，然后利用改進(jìn)的距離函數(shù)來選取近鄰點(diǎn)，構(gòu)建鄰接圖。新算法模糊了近鄰點(diǎn)的選取對(duì)實(shí)驗(yàn)結(jié)果的影響，達(dá)到了較為理想的降維效果，并在實(shí)驗(yàn)中得到了證實(shí)。
　　1 Diffusion Maps（DM）算法
　　DM算法主要分為如下4步：
　　（1）構(gòu)建鄰接圖。對(duì)于給定的數(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之間的相似程度，因此滿足：
　　①W是對(duì)稱的：Wij=Wji；
　　②W是非負(fù)的：Wij≥0。
　　一般采用高斯核函數(shù)定義成對(duì)數(shù)據(jù)點(diǎn)之間的相似度矩陣，即：

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

　　其中，Wi表示xi與其他各點(diǎn)的權(quán)值之和。
　　（4）核矩陣K的特征分解。對(duì)內(nèi)積矩陣K進(jìn)行特征分解，求K的特征值和特征向量，K的最大的d個(gè)特征值λ1，λ2，…，λd對(duì)應(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ù)對(duì)象的集合，同一簇中的對(duì)象相似，不同簇中的對(duì)象相異，每個(gè)簇的中心含有豐富的可利用的信息，具有代表性。模糊C均值（Fuzzy C-Means，F(xiàn)CM）算法[11-13]是應(yīng)用最廣泛的聚類分析方法之一。
　　對(duì)于給定的采樣于維流形的高維觀測(cè)數(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ù)
　　對(duì)于分布不均勻的數(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小得多。因此對(duì)于分布不均勻的樣本集，近鄰點(diǎn)k個(gè)數(shù)的選取會(huì)影響實(shí)驗(yàn)結(jié)果。所以要對(duì)近鄰點(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)成立；
　　②對(duì)稱性：dij=dji；
　　③三角不等式性：dis+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)的分布對(duì)算法效果的影響。
　　2.3改進(jìn)的算法（Improved Diffusion Maps，IMDM）
　　IMDM算法的步驟如下：
　　（1）對(duì)樣本集進(jìn)行聚類分類，得出構(gòu)建權(quán)值矩陣的誤差近似系數(shù)：

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

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

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

　　（5）核矩陣K′的特征分解。求K′的特征值和特征向量，K′的最大的d個(gè)特征值λ′1，λ′2，…，λ′d對(duì)應(yīng)的特征向量為U′=[u′1，u′2，…，u′d]，則高維數(shù)據(jù)X降維后的數(shù)據(jù)集為Y=[U′]T=[u′1，u′2，…，u′d]T。
　　新算法首先對(duì)樣本集進(jìn)行聚類分類，利用類別信息得出構(gòu)建權(quán)值矩陣的誤差近似系數(shù)，然后采用新的距離函數(shù)選取近鄰點(diǎn)構(gòu)建鄰接圖，這樣可適當(dāng)降低近鄰點(diǎn)個(gè)數(shù)k的選取對(duì)算法的影響，得到較好的降維效果。
3 實(shí)驗(yàn)結(jié)果及分析
　　3.1人工數(shù)據(jù)
　　用DM和IMDM對(duì)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ù)庫(kù)，共1 000幅圖像，類別為10種，有建筑、風(fēng)景、人物、動(dòng)物、植物等。實(shí)驗(yàn)對(duì)第450號(hào)恐龍圖像進(jìn)行相關(guān)圖像檢索，降至維數(shù)d分別取6、14、20，檢索出的圖像數(shù)目設(shè)為20。實(shí)驗(yàn)一先用DM方法對(duì)圖像數(shù)據(jù)集降維然后進(jìn)行檢索，得出實(shí)驗(yàn)結(jié)果如圖3中的（a）、（c）、（e）所示。實(shí)驗(yàn)二先用IMDM方法對(duì)圖像數(shù)據(jù)集降維再進(jìn)行檢索，得出實(shí)驗(yàn)結(jié)果如圖3中的（b）、（d）、（f）所示。對(duì)比兩次實(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é)論
　　本文對(duì)基于流形學(xué)習(xí)的擴(kuò)散映射非線性降維方法進(jìn)行了分析研究，提出了一種改進(jìn)的擴(kuò)散映射非線性降維方法。此方法以聚類分類原理構(gòu)造權(quán)值矩陣的誤差近似系數(shù)，通過改變樣本點(diǎn)間的距離公式重新構(gòu)建鄰接圖，進(jìn)而實(shí)現(xiàn)降維。新算法有效地降低了近鄰點(diǎn)的選取對(duì)降維效果的影響，并且很好地保留了原始數(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í)算法對(duì)比研究[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.