邱益維+鐘海偉

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

關(guān)鍵詞：SMMC模型；流形學(xué)習(xí)；子空間聚類；多流形建模

DOIDOI：10.11907/rjdk.171193

中圖分類號(hào)：TP303

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2017）007-0029-04

0 引言

隨著大數(shù)據(jù)時(shí)代的到來(lái)，數(shù)據(jù)量呈爆發(fā)式增長(zhǎng)。如何對(duì)數(shù)據(jù)進(jìn)行有效分析和處理已成為成功解決諸多問(wèn)題的關(guān)鍵，由此涌現(xiàn)出大量的數(shù)據(jù)分析方法。在實(shí)際問(wèn)題分析中可發(fā)現(xiàn)，大部分?jǐn)?shù)據(jù)集實(shí)質(zhì)上是由許多集合結(jié)構(gòu)組合而成的。幾何結(jié)構(gòu)分析現(xiàn)已被廣泛應(yīng)用于對(duì)象識(shí)別、圖像分類等模式識(shí)別和分類問(wèn)題，同時(shí)也是對(duì)高維數(shù)據(jù)進(jìn)行相關(guān)性分析、聚類分析等的有效方法。其中流形學(xué)習(xí)是幾何結(jié)構(gòu)分析方法中的重要組成部分[1-2]。流形學(xué)習(xí)的目的在于把高維數(shù)據(jù)在低維流形中表示出來(lái)，從而便于數(shù)據(jù)分析與存儲(chǔ)，近年來(lái)流形學(xué)習(xí)的研究特別是多流形的研究逐漸增多[3]。

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

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

1 理論基礎(chǔ)

1.1 多流形譜聚類模型

SMMC模型的基本思想是從相似性矩陣的角度出發(fā)，充分利用流形采樣點(diǎn)所包含的自然的局部幾何結(jié)構(gòu)信息，輔助構(gòu)造更適合的相似性矩陣，進(jìn)而發(fā)現(xiàn)正確的流形聚類[5-6]。

根據(jù)數(shù)據(jù)點(diǎn)內(nèi)包含的局部幾何結(jié)構(gòu)信息輔助構(gòu)造相似性矩陣W[5]。當(dāng)兩個(gè)數(shù)據(jù)點(diǎn)滿足條件相互靠近同時(shí)具有相似的局部切空間時(shí)，才能斷定它們是來(lái)自同一個(gè)流形聚類。因此結(jié)合數(shù)據(jù)點(diǎn)之間的歐氏距離關(guān)系qij=q（xi-xj）和局部切空間之間的相似性pij來(lái)決定最后的相似性權(quán)值：

其中，f表示融合函數(shù)。結(jié)合理論與實(shí)際可知，兩點(diǎn)劃分為同類的概率與結(jié)構(gòu)相似性成正比，與兩者之間的歐式距離成反比。為使相似矩陣具有預(yù)期性質(zhì)，融合函數(shù)f關(guān)于pij單調(diào)遞增，關(guān)于qij單調(diào)遞減。

假設(shè)數(shù)據(jù)點(diǎn)xi和xj（i，j=1，…N）處的局部切空間為Θi和Θj，則兩數(shù)據(jù)點(diǎn)的局部切空間之間結(jié)構(gòu)相似性可定義為：

1.2 流形距離

對(duì)于流形分類問(wèn)題，其距離測(cè)度需要滿足條件：在相同流形上的點(diǎn)的距離大于在不同流形上點(diǎn)的距離，而歐式距離不能體現(xiàn)該性質(zhì)。為了滿足聚類全局一致性的目的，使同一流形結(jié)構(gòu)中的數(shù)據(jù)點(diǎn)的相似度高，而不同流形結(jié)構(gòu)中的數(shù)據(jù)點(diǎn)的相似度低，使用一種能夠體現(xiàn)全局一致性的測(cè)度—流形距離核測(cè)度。

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

此流形距離測(cè)度可以度量流形上的最短路徑，反映樣本集內(nèi)的流行結(jié)構(gòu)。具體表現(xiàn)為用較短邊連接同一流形上的兩個(gè)樣本點(diǎn)，較長(zhǎng)邊連接位于不同流形上的兩個(gè)樣本點(diǎn)，最終達(dá)到縮短同一流形上樣本點(diǎn)間距離，放大不同流形上樣本點(diǎn)間距離的目的。

2 SMMC模型改進(jìn)

在利用坐標(biāo)表示圖像信息時(shí)，不同樣本為流形上一點(diǎn)的空間坐標(biāo)位置，此時(shí)樣本不能很好地體現(xiàn)流形結(jié)構(gòu)。對(duì)于SSC模型或SMMC模型，都先將圖像信息從一種表示方式映射到另一種表示方式：SSC模型利用稀疏性要求，得到圖像的稀疏表示；SMMC模型針對(duì)流形曲面，對(duì)局部進(jìn)行線性重構(gòu)，利用重構(gòu)的空間基向量表示原始圖像。

一定程度上講，映射方式的選擇決定了聚類的效果，對(duì)于SSC模型，因?yàn)椴捎玫氖亲陨硐蛄吭俦硎荆撍惴ㄔ谙蛄孔陨硐嚓P(guān)性較大的場(chǎng)合有效，特別是在高維，小樣本的情況下進(jìn)行聚類。而SMMC算法是流形結(jié)果，對(duì)曲面采樣稠密，稠密的條件保證了局部切空間的準(zhǔn)確性，在抽樣不夠稠密和流形邊界位置時(shí)，局部切空間的法線方向穩(wěn)定性較差。本文針對(duì)SMMC在流形的局部表示上進(jìn)行改進(jìn)。

不同于SMMC模型中對(duì)局部點(diǎn)構(gòu)成的矩陣進(jìn)行奇異值分解，改進(jìn)模型采用了奇異值向量來(lái)重構(gòu)局部切平面，這樣構(gòu)成的切空間性質(zhì)連續(xù)性不夠明顯，對(duì)于連續(xù)的曲面，設(shè){h1，h2，……h(huán)k}∈δ（x，ε，k）為數(shù)據(jù)點(diǎn)x的流形鄰域類中最近的k個(gè)數(shù)據(jù)點(diǎn)，令H=[h1，h2……h(huán)k]T，求解如下最小化問(wèn)題：

參數(shù)β即為求解得到的數(shù)據(jù)點(diǎn)x重新表示。對(duì)于連續(xù)變化的流形結(jié)構(gòu)，其切線構(gòu)成新的流形。特別地，如果原始圖像中的直線在局部法線的表示下為一個(gè)稠密點(diǎn)，若沒(méi)有誤差項(xiàng)，則新的表示下，直線變成點(diǎn)；對(duì)于曲線來(lái)說(shuō)，在新的表示下為一連續(xù)的曲線。分離稠密點(diǎn)即可得到原始空間的直線。在高維空間中，切平面參數(shù)化以后，原始圖像則表示成新的流形，平面表示為稠密點(diǎn)，曲面構(gòu)成新的流形，然后利用重新參數(shù)化的數(shù)據(jù)根據(jù)SMMC模型算法求解。

根據(jù)以上論述，改進(jìn)后的SMMC模型算法步驟可歸納為：

（1）計(jì)算各點(diǎn)之間的歐式距離。

（2）利用Floyd算法求解任意點(diǎn)的流形距離。

（3）重構(gòu)局部切平面并估計(jì)參數(shù)β，組成的新數(shù)據(jù)樣本，利用MPPCA訓(xùn)練M個(gè)d維的局部線性模型來(lái)近似潛在的流形數(shù)據(jù)。

（4）由式（10）確定每一個(gè)數(shù)據(jù)樣本點(diǎn)的局部切空間。

（5）由式（2）計(jì)算兩個(gè)局部切空間之間的結(jié)構(gòu)相似性。

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

（7）計(jì)算特征矩陣D-Wu=λDu最小的k個(gè)特征值對(duì)應(yīng)的特征向量u1，u2，…uk。

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

3 改進(jìn)SMMC模型的子空間聚類驗(yàn)證

為了驗(yàn)證本文所提出的改進(jìn)SMMC模型的有效性，將其應(yīng)用于獨(dú)立線性子空間的流形、良分離曲線的流形以及交疊曲線的流形這三類問(wèn)題的子空間的聚類中，并與根據(jù)SSC模型、SMMC模型得到的聚類結(jié)果進(jìn)行對(duì)比，仿真結(jié)果如下文所示。

由圖1可知，對(duì)于獨(dú)立線性子空間的流形，SSC模型不能很好地將兩條直線分成兩類，尤其是直線的交叉處無(wú)法得到好的聚類效果。SMMC模型對(duì)其聚類，直線的交叉處數(shù)據(jù)的聚類已經(jīng)比SSC模型的結(jié)果好很多，但是沒(méi)能完整地將兩條直線聚成兩類，說(shuō)明模型還需改進(jìn)。改進(jìn)的SMMC模型可以很好地將同一直線上的點(diǎn)聚到同一類中，效果顯著。

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

由圖3可知，對(duì)于相交的兩條螺旋線，用SSC模型分兩類的結(jié)果沒(méi)有規(guī)律性，每條螺旋線上的點(diǎn)都被聚到不同的兩類當(dāng)中去，效果不理想。采用SMMC模型聚類時(shí)，雖然沒(méi)有將兩條螺旋線完全分開(kāi)，但是其中一條螺旋線的一半已經(jīng)完全與另一條螺旋線區(qū)分開(kāi)，說(shuō)明相比SSC模型，用SMMC模型有更好地聚類效果。通過(guò)本文提出的改進(jìn)SMMC模型聚類，發(fā)現(xiàn)可以將兩條螺旋線可以進(jìn)行區(qū)分且效果很好。

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1]易思，左小雷，黃小明，等.基于SMMC模型的數(shù)據(jù)多流形結(jié)構(gòu)分析研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2016，46（14）：163-172.

[2]胡一帆，胡友彬，李紹輝，等.多流形結(jié)構(gòu)數(shù)據(jù)建模與應(yīng)用研究[J].現(xiàn)代計(jì)算機(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]劉向陽(yáng).多流形數(shù)據(jù)建模及其應(yīng)用[D].上海：上海交通大學(xué)，2011.

[5]王勇.基于流形學(xué)習(xí)的分類與聚類方法及其應(yīng)用研究[D].長(zhǎng)沙：國(guó)防科技大學(xué)，2011.

[6]王夢(mèng)瑩，鄭雄風(fēng)，葛余超.混合流形結(jié)構(gòu)的子空間聚類研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2016，46（14）：189-199.

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