魯棒譜多流形聚類算法

鄒 鵬，李凡長

1(蘇州大學 計算機科學與技術學院，江蘇 蘇州 215006)

2(蘇州大學 機器習與類腦計算國際合作聯實驗室，江蘇 蘇州 215006)

1 引 言

聚類是機器學習和模式識別領域的一個重要研究方向.傳統的聚類算法，如K-means[1]是通過將所有數據點與少量聚類中心比較相似度得到最終聚類結果.這些方法的主要缺點是不能處理線性不可分的數據.近年來，由于流形學習在非線性數據上有較好的處理能力，大量研究者將流形聚類作為工作重點[2-5].K-manifolds[6]通過估計樣本點間的測地距離對分布于多個混合非線性流形上的數據進行聚類分析.該算法對類間混合度較高的樣本聚類效果較好，但無法處理異類樣本分離度很大的情況.相反地，譜聚類算法[7-10]只能對流形間距離較大的數據進行聚類.Wang等人提出了基于譜聚類的兩種多流形聚類算法mumCluster[11]和SMMC[12].這兩種算法既可以處理流形分開的情況，也可以區分出流形間有交叉數據.譜多流形聚類算法(SMMC)引入流形局部近鄰幾何信息對譜方法的相似度矩陣進行重構，既可以處理流形上的數據點有/無交叉的情況，也可以線性/非線性數據進行聚類.mumCluster算法與傳統聚類算法不同，無需提供初始類別數，根據樣本的局部近鄰維度來確定流形結構.然而，現實中大多原始數據都是含有噪聲或者錯誤信息的，不加處理會影響算法的魯棒性.

對于分布于多流形結構的數據，隨著噪聲點的增多，在估計樣本局部幾何結構時會受到嚴重影響.一些研究者將數據降維與聚類算法結合學習得到一個降維投影矩陣[13,14]，但是噪聲數據同樣會影響數據的降維效果以及最終識別率.Hu等人提出基于非負矩陣分解投影(projective nonnegative matrix factorization，PNMF)的相關算法[15,16].PNMF算法將原始數據投影到非負矩陣子空間中，可提取出更好的局部特征.PNMF相關算法依然存在收斂速度慢、誤差大、重建精度低和魯棒性不足等問題.但是上述提及的聚類算法都是直接使用原始數據進行聚類分析，數據中的噪聲點和異類點很大程度上影響模型的最終結果.

本文提出了魯棒譜多流形聚類算法(RSMMC)來提高數據聚類準確率和魯棒性.本文所提出的方法基于SMMC方法，但是新引入一個噪聲消除項來提高模型的魯棒性.該噪聲消除項由l2，1范數正則化噪聲項和l2，1范數正則化降噪投影矩陣組成，主要原因在于l2，1范數可使矩陣行稀疏并對數據中的噪聲有很好的魯棒性[17].通過對模型的迭代優化學習得到一個降噪投影矩陣，該投影進而可用于提取“干凈”數據進行訓練，大幅度降低直接使用有噪音的原始數據對樣本局部幾何結構估計產生的負面影響，提升算法的聚類精確度和對噪音的魯棒性.

2 相關工作

2.1 譜聚類(SC)

假設X={xi∈D，i=1，…，N} 表示一組無標簽樣本點，其中D表示數據維度，N表示樣本個數.G=(V，E，W)表示由X構成的無向帶權圖.X中的樣本點對應V中的頂點.任意兩點間的權值由相似度矩陣W給出.聚類分析是將這些點分到K個不相交的子集.即不同類的樣本相似度低，同類樣本相似度高.

譜聚類中相似度矩陣W∈N×N可由公式(1)求得

(1)

為得到更好的聚類效果，正則切(Ncut)[18]被引入到譜聚類中.正則化譜聚類目標函數為

(2)

對式(2)的求解可以轉化成一個廣義特征值問題[8]

(E-W)u=λEu

(3)

對(3)求解最小的K個特征值對應的特征向量U=[u1，…，uK]∈N×K.最后將K-means算法應用到矩陣U上即可得到聚類.

2.2 譜多流形聚類(SMMC)

譜聚類僅能處理流形間相對分離的情況，而現實中分布于多流形的數據大多存在交叉區域.針對這一問題，譜多流形算法(SMMC)對譜聚類進行了改進[12].SMMC算法首先用概率主成分分析器(PPCA)確定每個樣本點的局部切空間，即可得到局部線性流形結構.再用樣本局部近鄰的幾何信息重構相似度矩陣W.既可以處理類間分離度高的數據，又能夠劃分出存在交叉的多流形結構.

3 魯棒譜多流形聚類(RSMMC)

大多數現實數據含有許多噪聲，目前的多流形聚類算法都直接對含有噪聲的數據進行處理.噪聲數據會降低算法的聚類準確率，并持續影響后續的應用.魯棒譜多流形聚類算法首先對原始數據進行迭代降噪處理，提取出更“純凈”的數據；再通過各樣本的局部幾何結構信息重構相似度矩陣；最后得出聚類結果.

3.1 算法模型

首先對原數據進行降噪處理，通過求解以下優化問題

(4)

其中P∈N×N表示降噪投影矩陣，PX表示“純凈”數據.通過最小化降噪項求解得到降噪投影.符號T表示矩陣或向量的轉置，Z=X-PX表示噪聲.是l2，1范數正則化降噪投影矩陣，是l2，1范數正則化噪聲項.l2，1范數可使正則化矩陣行稀疏，并且基于l2，1范數的度量對數據噪聲和異常點具有魯棒性[20].因此，投影矩陣P可以降低數據噪聲.

假設所有流形的內嵌維度d(0

(5)

(6)

其中Knn表示樣本點x的K個近鄰點.Θi和Θj分別表示點xi和xj(i，j=1，...，N)處的切空間，θ表示切空間Θi和Θj間的角度，o∈N+是一個調和參數.切空間可由PPCA算法求得.

相似度矩陣W可由式(7)重構得到

(7)

即對于樣本點的近鄰點，其切空間(結構)相似度越大，越有可能分布于同一流形結構.將K-means算法應用于重構得到的相似度W，得到最終聚類結果.

3.2 優化

(8)

(9)

其中V和Λ是對角矩陣，定義為

(10)

Zm和Pn分別對應于Z的第m列和P的第n列.V和Λ初始化為單位矩陣.式(9)對P求導?P/?P=0，即可求P

P=XVXT(λΛ+XVXT)-1

(11)

算法1. RSMMC算法

輸入：數據集X，類別數K，嵌入維數d，線性流形數M，近鄰數k，調和參數o，λ.

輸出：數據劃分為K個不相交聚類

步驟1. 初始化P(0)為隨機正則化矩陣，V(0)和Λ(0)為單位矩陣t=0；

步驟2.Fort= 0：iteration- 1

2.1 用PPCA算法訓練M個d維局部線性流形；

2.2 按式(6)計算任意兩點的局部切空間相似度；

2.3 計算相似度矩陣W∈N×N；

2.5 對(E-W)u=λEu求最小的K個特征值對應的特征向量；

2.6 按等式(11)更新P(t+1)；

2.7 按等式(10)更新對角矩陣V(t+1)和Λ(t+1)；

t=t+1 ；

end

步驟3. K-means算法對U∈N×K進行聚類.

3.3 算法復雜度分析

本文提出的RSMMC算法，基于SMMC算法通過對降噪投影矩陣P進行迭代更新優化，得到最優聚類.這里只計算一次迭代的時間復雜度.主要分為以下4步：

1)計算每個樣本的切空間；

2)計算相似度矩陣W；

3)更新投影矩陣P；

4)譜聚類算法應用于W.

PPCA算法對原數據訓練M個主成分分析器，估計出每個樣本的切空間Θi，i=1，…，N，時間復雜度為O(NDMd)，d表示各流形內嵌維度.相似度矩陣W的計算復雜度為O(N2(Dd2+k))，k表示近鄰數.第三步根據式(10)和(11)對P，V和Λ進行更新，復雜度為O(dN2+d2N+d3).最后將W通過譜聚類投影到K維特征空間，并用K-means算法將數據聚成K類.此部分復雜度為O((N+K)N2+NK2).因此，RSMMC算法最終復雜度為O(N3+N2(Dd2+k+d)+NDMd+d2N+d3).

4 實 驗

本文對RSMMC算法進行魯棒聚類分析.將聚類結果與K-means[1]，譜聚類(SC)[10,18]，K-manifolds[6]，LSC[19]和SMMC[12]等算法進行對比分析.本文進行三組實驗：實驗將各算法在人工數據集、COIL-20數據集[20]和MIT人臉數據集[21]上的聚類結果進行對比分析；并在各實驗數據集上加入隨機高斯噪聲驗證本文算法在帶噪聲的數據集上的魯棒性.

本文將算法得到的聚類標簽與樣本真實標簽進行比對得出聚類評分.采用聚類準確率(AC)和歸一化交互信息(NMI)[22,23]作為評分標準，即AC和NMI取值越大，聚類效果越好.

4.1 數據聚類

本文選取1個人工數據集和2個圖像數據集對RSMMC算法和相關聚類算法進行對比實驗.

為檢驗本文算法對噪聲的魯棒性，我們在各實驗數據集中加入不同系數的高斯噪聲，分別進行聚類分析.所有數據按公式(12)加入噪聲.

(12)

下面分別對實驗數據集和實驗結果進行介紹.

圖1 RSMMC在COIL-20數據集上的收斂性Fig.1 Convergence of RSMMC on the COIL-20 database

1)人工數據集包括3類數據共2500個樣本點，如圖2所示.既包含類間交叉和類間分離的混合非線性數據.將本文提出的RSMMC算法與各算法進行實驗對比，記錄10次實驗的平均聚類結果.RSMMC算法中參數λ=0.005，其他參數按文獻[12]作者的建議設置.本文算法在所有實驗迭代次數為10次.

圖2 人工數據集Fig.2 Synthetic dataset

實驗結果如表1所示.對人工數據增加噪聲，取噪聲系數為0，3和7，從表1可以看出RSMMC算法比其他對比算法聚類準確率更高.K-manifolds算法聚類識別率較低，因為數據集中類別間分離的數據.而在處理類間有交叉的數據時，SC算法聚類效果較差.SMMC和RSMMC在處理類間既存在交叉區域又有分離的數據時效果都很好.

表1 人工數據集上的聚類結果Table 1 Clustering results on synthetic dataset

2)COIL-20數據集包括20個物品的1440張灰度圖像，每個物品72張圖像.這些物品有著復雜的幾何結構，每幅圖像的像素為32×32.為計算簡便本文在實驗中將數據先降到10維.對每個算法取10次實驗的平均值進行記錄.

本實驗中，當K-manifolds算法近鄰數取k= 60時都無法得出整個數據的測地距離.可以看出，COIL-20數據集不同物體類間分離度較高[12].

實驗中設置K-manifolds近鄰數為80，RSMMC算法模型參數λ=0.01.

實驗結果如表2所示.從表2可以看出，由于數據類間的高分離度，K-manifolds算法的聚類準確率很低；基于譜聚類的相關算法SC，LSC和SMMC算法的聚類效果較好.增加噪聲數據后，隨著噪聲系數Variance的增大，各算法聚類準確率都有了不同程度的下降.本文的RSMMC算法聚類效果始終高于其他對比算法.

表2 COIL-20數據集上的聚類結果Table 2 Clustering results on the COIL-20 dataset

表3 MIT人臉數據集上的聚類結果Table 3 Clustering results on the MIT face dataset

3)MIT人臉數據集包括10個人的3240幅人臉圖片.實驗中參數λ=10，其余參數設置與實驗(2)相同.實驗結果如表3所示.可以看出，RSMMC算法比相關對比算法的聚類效果好.圖3和圖4顯示了MIT數據集上各算法隨著噪聲增加聚類效果的變化.可以看出，隨著噪聲數據的增加，RSMMC算法的聚類準確率高于其他對比算法，并且有著很好的魯棒性.

圖3 MIT人臉數據集上AC隨著variance的變化Fig.3 AC with varying variance on MIT face database圖4 MIT人臉數據集上NMI隨著variance的變化Fig.4 NMI with varying variance on MIT face database

4.2 參數分析

本節我們對模型參數敏感性進行分析.由于最優參數選擇是一個開放性問題，本文通過在一定范圍內改變模型參數λ的取值分析參數的敏感性.實驗采用COIL-20數據集，其余設置與3.1節相同.對于每個參數值，記錄10次實驗的平均結果.圖5是RSMMC算法在COIL-20數據集上的實驗結果.可以看出，隨著參數λ取值的不同，實驗結果并沒有發生太大變化.說明本文模型對參數λ不敏感.

圖5 COIL-20數據集上參數λ對實驗的影響Fig.5 Effects of parameter selection of λ on COIL-20

5 總 結

本文提出了一種魯棒譜多流形聚類算法(RSMMC).該算法在迭代優化的過程中引入一個由l2，1范數正則化噪聲項和l2，1范數正則化降噪投影矩陣組成的噪音消除項，旨在對原始數據進行降噪，進而基于“干凈”數據進行聚類分析，引入流形局部近鄰幾何信息對譜方法的相似度矩陣進行重構.該算法既可以處理流形上的數據點有/無交叉的情況，也可以對線性/非線性數據進行聚類.實驗結果表明，該方法在數據類別增大時優于相關對比算法，另外對噪音具有較強的魯棒性.考慮到真實世界中的數據往往會有一部分存在類別標簽，大多數無類別標簽，在未來我們將考慮充分使用這些類別信息將提出的算法拓展到半監督領域.

：

[1] Hartigan J A，Wong M A.A K-means clustering algorithm[J].Applied Statistics，1979，28(1)：100-108.

[2] Tenenbaum J B，De Silva V，Langford J C.A global geometric framework for nonlinear dimensionality reduction[J].Science，2000，290(5500)：2319-2323.

[3] Seung H S，Lee D D.Cognition-the manifold ways of perception[J].Science,2000，290(5500):2268-2269.

[4] Roweis S T，Saul L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science，2000，290(5500)：2323-2326.

[5] Hassanzadeh A，Kauranne T，Kaarna A.A multi-manifold clustering algorithm for hyperspectral remote sensing imagery[C].Geoscience and Remote Sensing Symposium (IGARSS)，IEEE International.，IEEE，2016：3326-3329.

[6] Souvenir R，Pless R.Manifold clustering[C].Proceedings of the 10th IEEE International Conference on Computer Vision，2005：648-653.

[7] Ren P，Wilson R C，Hancock E R.Graph characterization via Ihara coefficients[J].IEEE Transactions on Neural Networks，2011，22(2)：233-245.

[8] von Luxburg U.A tutorial on spectral clustering[J].Statistics and Computing，2007，17(4)：395-416.

[9] Zhang K，Kwok J T.Clustered Nystrom method for large scale manifold learning and dimension reduction[J].IEEE Transactions on Neural Networks，2010，21(10)：1576-1587.

[10] Ng A，Jordan M，Weiss Y.On spectral clustering：analysis and an algorithm[J].Advances in Neural Information Processing Systems，2001，14 ：849-856.

[11] Wang Y，Jiang Y，Wu Y，et al.Multi-manifold clustering[C].Pacific Rim International Conference on Artificial Intelligence，Springer Berlin Heidelberg，2010：280-291.

[12] Wang Y，Jiang Y，Wu Y，et al.Spectral clustering on multiple manifolds[J].IEEE Transactions on Neural Networks，2011，22(7)：1149-1161.

[13] Wang J，Yue S，Yu X，et al.An efficient data reduction method and its application to cluster analysis[J].Neurocomputing，2017，238(C)：234-244.

[14] Kr?mer P，Plato? J.Cluster analysis of data with reduced dimensionality：an empirical study[M].Intelligent Systems for Computer Modelling,Springer International Publishing，2016.

[15] Hu L，Dai L，Wu J.Convergent projective non-negative matrix factorization with kullback-leibler divergence[J].Pattern Recognition Letters，2013，10(1)：15-21.

[16] Hu L，Wu J，Wang L.Linear projective non-negative matrix factorization[J].Research Journal of Applied Sciences Engineering & Technology，2013，6(9)：2285-2291.

[17] Hou Chen-ping，Nie Fei-ping，Li Xue-long，et al.Joint embedding learning and sparse regression：a framework for unsupervised feature selection[J].IEEE Trans.Cybernetics，2014，44(6)：793- 804.

[18] Shi J，Malik J.Normalized cuts and image segmentation[J].IEEE Transactions on Pattern Analysis & Machine Intelligence，2002，22(8)：888-905.

[19] Chen X，Cai D.Large scale spectral clustering with landmark-based representation[C].AAAI Conference on Artificial Intelligence，AAAI Press，2011：313-318.

[20] Yang J，Parikh D，Batra D.Joint unsupervised learning of deep representations and image clusters[C].Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition，2016：5147-5156.

[21] Weyrauch B，Heisele B，Huang J，et al.Component-based face recognition with 3D morphable models[C].International Conference on Audio-and Video-Based Biometric Person Authentication，Springer-Verlag，2004：27-34.

[22] Rafailidis D，Constantinou E，Manolopoulos Y.Landmark selection for spectral clustering based on weighted PageRank[J].Future Generation Computer Systems，2017，68：465-472.

[23] Cai D，He X，Han J.Document clustering using locality preserving indexing[J].Knowledge & Data Engineering IEEE Transactions on，2005，17(12)：1624-1637.