基于改進SMMC模型的多流形結構數據分析

邱益維+鐘海偉

摘 要：提出一種改進的多流形譜聚類（SMMC）模型，提高復雜流形結構中的聚類精度。改進模型的核心在于首先對原始數據進行空間映射，得到能體現原始數據流形結構的數據；其次，根據流形距離的定義，利用局部點鄰域構造各點的切平面，將切平面參數作為新流形的數據樣本；最后用SMMC模型求解，得到聚類結果。實驗結果表明，改進的SMMC模型對獨立子空間、非線性良分離以及非線性交叉流形這三類數據的子空間聚類效果良好，且具有強魯棒性和通用性。

關鍵詞：SMMC模型；流形學習；子空間聚類；多流形建模

DOIDOI：10.11907/rjdk.171193

中圖分類號：TP303

文獻標識碼：A 文章編號：1672-7800（2017）007-0029-04

0 引言

隨著大數據時代的到來，數據量呈爆發式增長。如何對數據進行有效分析和處理已成為成功解決諸多問題的關鍵，由此涌現出大量的數據分析方法。在實際問題分析中可發現，大部分數據集實質上是由許多集合結構組合而成的。幾何結構分析現已被廣泛應用于對象識別、圖像分類等模式識別和分類問題，同時也是對高維數據進行相關性分析、聚類分析等的有效方法。其中流形學習是幾何結構分析方法中的重要組成部分[1-2]。流形學習的目的在于把高維數據在低維流形中表示出來，從而便于數據分析與存儲，近年來流形學習的研究特別是多流形的研究逐漸增多[3]。

子空間聚類、混合線性模型、流形聚類等是目前主流的多流形模型方法。盡管目前對流形學習的研究較多，但仍面臨巨大的挑戰[4-5]。基于譜聚類的多流形聚類方法是眾多流形聚類方法中的一類，它克服了傳統稀疏子空間聚類（Sparse Subspace Clustering，SSC）算法不能很好地解決非線性子空間聚類的缺陷，能將線性或非線性、良分離或交疊的流形等多流形問題進行聚類，具有強大功能[1]。

本文在深入分析多流形譜聚類（Spectral Multi-manifold Clustering，SMMC）模型的基礎上提出一種改進方法，對獨立線性子空間、良分離曲線以及交疊曲線流形聚類中的3種典型數據進行聚類，并與其它流形聚類方法進行比較，實驗結果表明，改進模型具有更好的聚類效果。

1 理論基礎

1.1 多流形譜聚類模型

SMMC模型的基本思想是從相似性矩陣的角度出發，充分利用流形采樣點所包含的自然的局部幾何結構信息，輔助構造更適合的相似性矩陣，進而發現正確的流形聚類[5-6]。

根據數據點內包含的局部幾何結構信息輔助構造相似性矩陣W[5]。當兩個數據點滿足條件相互靠近同時具有相似的局部切空間時，才能斷定它們是來自同一個流形聚類。因此結合數據點之間的歐氏距離關系qij=q（xi-xj）和局部切空間之間的相似性pij來決定最后的相似性權值：

其中，f表示融合函數。結合理論與實際可知，兩點劃分為同類的概率與結構相似性成正比，與兩者之間的歐式距離成反比。為使相似矩陣具有預期性質，融合函數f關于pij單調遞增，關于qij單調遞減。

假設數據點xi和xj（i，j=1，…N）處的局部切空間為Θi和Θj，則兩數據點的局部切空間之間結構相似性可定義為：

1.2 流形距離

對于流形分類問題，其距離測度需要滿足條件：在相同流形上的點的距離大于在不同流形上點的距離，而歐式距離不能體現該性質。為了滿足聚類全局一致性的目的，使同一流形結構中的數據點的相似度高，而不同流形結構中的數據點的相似度低，使用一種能夠體現全局一致性的測度—流形距離核測度。

所有樣本點看作是圖G=（V，E）的頂點，其中p∈Vl表示圖上一個長度為l=p-1的連接點p1與pp的路徑，邊（pk，pk+1）E，1≤k

此流形距離測度可以度量流形上的最短路徑，反映樣本集內的流行結構。具體表現為用較短邊連接同一流形上的兩個樣本點，較長邊連接位于不同流形上的兩個樣本點，最終達到縮短同一流形上樣本點間距離，放大不同流形上樣本點間距離的目的。

2 SMMC模型改進

在利用坐標表示圖像信息時，不同樣本為流形上一點的空間坐標位置，此時樣本不能很好地體現流形結構。對于SSC模型或SMMC模型，都先將圖像信息從一種表示方式映射到另一種表示方式：SSC模型利用稀疏性要求，得到圖像的稀疏表示；SMMC模型針對流形曲面，對局部進行線性重構，利用重構的空間基向量表示原始圖像。

一定程度上講，映射方式的選擇決定了聚類的效果，對于SSC模型，因為采用的是自身向量再表示，該算法在向量自身相關性較大的場合有效，特別是在高維，小樣本的情況下進行聚類。而SMMC算法是流形結果，對曲面采樣稠密，稠密的條件保證了局部切空間的準確性，在抽樣不夠稠密和流形邊界位置時，局部切空間的法線方向穩定性較差。本文針對SMMC在流形的局部表示上進行改進。

不同于SMMC模型中對局部點構成的矩陣進行奇異值分解，改進模型采用了奇異值向量來重構局部切平面，這樣構成的切空間性質連續性不夠明顯，對于連續的曲面，設{h1，h2，……hk}∈δ（x，ε，k）為數據點x的流形鄰域類中最近的k個數據點，令H=[h1，h2……hk]T，求解如下最小化問題：

參數β即為求解得到的數據點x重新表示。對于連續變化的流形結構，其切線構成新的流形。特別地，如果原始圖像中的直線在局部法線的表示下為一個稠密點，若沒有誤差項，則新的表示下，直線變成點；對于曲線來說，在新的表示下為一連續的曲線。分離稠密點即可得到原始空間的直線。在高維空間中，切平面參數化以后，原始圖像則表示成新的流形，平面表示為稠密點，曲面構成新的流形，然后利用重新參數化的數據根據SMMC模型算法求解。

根據以上論述，改進后的SMMC模型算法步驟可歸納為：

（1）計算各點之間的歐式距離。

（2）利用Floyd算法求解任意點的流形距離。

（3）重構局部切平面并估計參數β，組成的新數據樣本，利用MPPCA訓練M個d維的局部線性模型來近似潛在的流形數據。

（4）由式（10）確定每一個數據樣本點的局部切空間。

（5）由式（2）計算兩個局部切空間之間的結構相似性。

（6）由式（6）計算相似性矩陣W∈RN×N和對角矩陣D，其中dii=∑jwij。

（7）計算特征矩陣D-Wu=λDu最小的k個特征值對應的特征向量u1，u2，…uk。

（8）利用K-means算法將U=[u1，u2…uk]∈RN×k的行向量分組成k個聚類。

3 改進SMMC模型的子空間聚類驗證

為了驗證本文所提出的改進SMMC模型的有效性，將其應用于獨立線性子空間的流形、良分離曲線的流形以及交疊曲線的流形這三類問題的子空間的聚類中，并與根據SSC模型、SMMC模型得到的聚類結果進行對比，仿真結果如下文所示。

由圖1可知，對于獨立線性子空間的流形，SSC模型不能很好地將兩條直線分成兩類，尤其是直線的交叉處無法得到好的聚類效果。SMMC模型對其聚類，直線的交叉處數據的聚類已經比SSC模型的結果好很多，但是沒能完整地將兩條直線聚成兩類，說明模型還需改進。改進的SMMC模型可以很好地將同一直線上的點聚到同一類中，效果顯著。

由圖2可知，對于良分離曲線的流形，SSC模型的聚類效果很差，用SMMC模型和改進的SMMC模型均能很完美地將兩條不相交的二次曲線聚成兩類。因為這種類型的流形聚類正屬于多流形聚類問題，用SSC模型難以解決多流形聚類問題，而SMMC模型正是針對這類問題的。

由圖3可知，對于相交的兩條螺旋線，用SSC模型分兩類的結果沒有規律性，每條螺旋線上的點都被聚到不同的兩類當中去，效果不理想。采用SMMC模型聚類時，雖然沒有將兩條螺旋線完全分開，但是其中一條螺旋線的一半已經完全與另一條螺旋線區分開，說明相比SSC模型，用SMMC模型有更好地聚類效果。通過本文提出的改進SMMC模型聚類，發現可以將兩條螺旋線可以進行區分且效果很好。

綜上所述，SSC模型對獨立線性子空間的兩條平面直線具有較好的聚類效果，但不能很好解決非線性子空間聚類問題。對于非線性子空間，需建立二維坐標的多流形模型進行聚類。實驗結果表明，SMMC模型應用到良分離曲線的流形聚類中，分類效果顯著，但針對交疊曲線的流形聚類還存在一定的缺陷。本文提出的改進SMMC模型改善了SSC和SMMC模型在低維空間中的聚類效果，很好完成了實驗中的三類圖形數據的聚類，分類效果良好，且更具通用性。

4 結語

本文針對多流形聚類問題進行建模，在分析數據幾何結構的理論基礎上，提出了改進的SMMC模型。首先對原始數據進行一次空間映射，使映射后的數據能體現原始數據的流形結構。其次，根據流形距離的定義，利用局部點鄰域構造各點的切平面，對于光滑的流形，各點的切平面法線方向緩慢變化，從而組成新的流形。最后利用重新構造流形得到的參數用SMMC模型算法求解。實驗結果表明，相較于原始SMMC模型，結合切平面與法線方向的改進SMMC模型提高了低維子空間的聚類效果，且更具有一般性和通用性。

參考文獻：

[1]易思，左小雷，黃小明，等.基于SMMC模型的數據多流形結構分析研究[J].數學的實踐與認識，2016，46（14）：163-172.

[2]胡一帆，胡友彬，李紹輝，等.多流形結構數據建模與應用研究[J].現代計算機：普及版，2015，（12）：8-13.

[3]CHEN G，LERMAN G.Spectral curvature clustering（SCC）[J].International Journal of Computer Vision，2009，81（3）：317-330.

[4]劉向陽.多流形數據建模及其應用[D].上海：上海交通大學，2011.

[5]王勇.基于流形學習的分類與聚類方法及其應用研究[D].長沙：國防科技大學，2011.

[6]王夢瑩，鄭雄風，葛余超.混合流形結構的子空間聚類研究[J].數學的實踐與認識，2016，46（14）：189-199.

[7]宋少宇.基于流形距離核的譜聚類算法研究及其應用[D].哈爾濱：哈爾濱工程大學，2012.