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

　（2）構建權值矩陣W。權值矩陣的元素Wij（W（xi，xj））反映樣本點xi與xj之間的相似程度，因此滿足：
　　①W是對稱的：Wij=Wji；
　　②W是非負的：Wij≥0。
　　一般采用高斯核函數定義成對數據點之間的相似度矩陣，即：

　　其中，為高斯核的方差，越大，權值越大，數據點間的相似程度越大。
　　（3）構建擴散核矩陣K。利用加權的圖Laplacian歸一化方法。

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

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

　　其中，‖‖表示歐式距離。由此，定義樣本點構建權值矩陣的誤差近似系數為：

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

　　其中，Gi、Gj分別表示xi、xj和其他點之間距離的平均值。
　　因為新的距離的分子是歐氏距離，分母是數值，則有：
　　①非負性：dij≥0，當且僅當xi=xj，即i=j時等號成立；
　　②對稱性：dij=dji；
　　③三角不等式性：dis+dsj≥dij。
　　由泛函分析知識可知，新的距離滿足距離空間的定義。在DM的第一步構建鄰接圖時，采用新的距離公式取代歐氏距離來選取樣本點的k個近鄰點。新的距離使分布較密集區域的樣本點間的距離增大，而使分布較稀疏區域的樣本點間的距離縮小，這樣區域SP和SO區域的差異性減小，樣本點的整體分布趨于均勻化，從而降低樣本點的分布對算法效果的影響。
　　2.3改進的算法（Improved Diffusion Maps，IMDM）
　　IMDM算法的步驟如下：
　　（1）對樣本集進行聚類分類，得出構建權值矩陣的誤差近似系數：

　　（2）構建鄰接圖。距離公式為：

　　（3）構建權值矩陣W′。

　　（4）構建擴散核矩陣K′。

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

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

　　查準率是衡量圖像檢索算法有效性的常用指標，查準率越高，表示圖像檢索方法越好，反之越差。

　　圖4為在維數不同時，DM和IMDM查準率的變化情況。可以看出，多數情況下IMDM降維后圖像檢索的查準率高于DM的。特別地，當維數為20時，應用IMDM方法，查準率達到了100%。

4 結論
　　本文對基于流形學習的擴散映射非線性降維方法進行了分析研究，提出了一種改進的擴散映射非線性降維方法。此方法以聚類分類原理構造權值矩陣的誤差近似系數，通過改變樣本點間的距離公式重新構建鄰接圖，進而實現降維。新算法有效地降低了近鄰點的選取對降維效果的影響，并且很好地保留了原始數據的拓撲結構。將改進的擴散映射方法用于Scurve數據集和基于內容的圖像檢索實驗，都得到了很好的效果，具有很好的實際應用價值。
　　參考文獻
　　[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] 曹林林.基于流形學習的分類技術[D].濟南：山東師范大學，2013.
　　[3] 王自強，錢旭，孔敏.流形學習算法綜述[J].計算機工程與應用，2008，44（35）：9-12.
　　[4] 曾憲華，羅四維.全局保持的流形學習算法對比研究[J].計算機工程與應用，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.模式識別（第4版）[M].李晶皎，王愛俠，王驕，等譯.北京：電子工業出版社，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] 姜倫，丁華福.關于模糊C-均值（FCM）聚類算法的改進[J].計算機與數字工程，2010，38（2）：4-6.
　　[12] 蘇錦旗，張文宇.基于模糊聚類的改進LLE算法[J]，計算機與現代化，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] 王和勇，鄭杰，姚正安.基于聚類和改進距離的LLE方法在數據降維中的應用[J]，計算機研究與發展，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.