魯棒自適應圖正則化聚類算法

董 昊，李玲慧

魯棒自適應圖正則化聚類算法

董 昊，李玲慧

基于L2,1范數及圖正則化項思想，提出了魯棒自適應圖正則化聚類算法.此算法不僅使數據矩陣行稀疏，而且增強了魯棒性，從而提高聚類算法的性能，得到更優質的聚類結果.合成數據集驗證了文中提出的聚類算法的有效性.

魯棒；圖正則；聚類

近年來，聚類分析技術在機器學習領域得到深入研究及廣泛應用.傳統的聚類方法如：kmeans聚類算法［1］、譜聚類算法［2］等已經被應用到各個領域.然而，傳統的基于圖的聚類方法通常是基于一個給定的數據圖與其鄰接矩陣，聚類時需要對數據圖進行處理才可以提取聚類指標.此外，聚類的過程對于數據圖的初始結構的質量要求是非常嚴格的.為了解決上述問題，Nie等提出了CLR聚類算法［3］.其算法是在給定的數據圖的基礎上，構建一個新的數據相似性矩陣，使聚類結果可以立即得到.

本文根據CLR聚類算法，基于L2,1范數及圖正則化項思想，提出了魯棒自適應圖正則化聚類算法（RAGR）.此算法利用L2,1范數，既使數據行稀疏，又確保數據在幾何結構上具有魯棒性，同時保持矩陣的旋轉不變性，從而提高聚類算法的性能，得到更優質的聚類結果.

1 魯棒自適應圖正則化聚類算法

1.1 模型的建立

給定一個具有鄰接矩陣的結構圖，矩陣M為其鄰接矩陣，M∈Rn×n.構建矩陣M的一個相似矩陣U∈Rn×n，其對應的拉普拉斯矩陣為從而得到rank(LU)=n-k，因此U具有可置換的塊對角矩陣.根據Nie、Wang和Huang的理論［4］可將基于U的數據點直接劃分為k個類別.為了避免U的某些行的元素全是零的情況，給出約束∑juij=1，其中uij≥1.進而建立目標函數如式（1）所示.

1.2 模型的優化

假定αi(LU)表示LU的第i個最小特征值.因為LU半正定，因此αi(LU)≥0.當τ足夠大時，式

根據Ky-Fan的極大極小值定理［5］，得出，由 此 給 出RAGR聚類算法的目標函數為

與原目標函數（1）相比，目標函數（2）增加了拉普拉斯正則化項，提高了聚類性能，而且更容易求解.

1.3 目標函數的求解

本文將用交替更新算法對目標函數（2）進行求解.

1）F的迭代更新.固定U，目標函數（2）將被轉化為的最優解由LU的最小二乘值的最小特征向量決定［6］.

2）U的迭代更新.固定F，目標函數（2）被轉化為

目標函數（3）中對于每一個i是獨立的，因此可以單獨地解決以下問題

目標函數（5）可以通過迭代法對以下問題進行求解.

其中，R為對角矩陣，第j個對角元素為，uij為當前的解，此方法在每一次迭代中收斂到目標函數（5）的最優解中.

下面用增廣拉格朗日函數對目標函數（7）進行求解.

其中，ξ,β≥0是拉格朗日乘子.

其中，(ω)+=max(0,ω).

定義關于ξ的目標函數

1.4 RAGR算法的實現

Algorithm：魯棒自適應圖正則化聚類算法.

輸入：矩陣M∈Rn×n，聚類數目k，正則化參數τ．

輸出：矩陣M的相似性矩陣U∈Rn×n，其中U有k個連通分量初始化的F∈Rn×n.

While not converge do

2.根據目標函數（7）和（9）更新U.

End while

2 初始圖的建立

本文旨在得到一個分塊化的相似矩陣U∈Rn×n，因此，必須先得到初始圖的鄰接矩陣M∈Rn×n.由于矩陣U需要是非負和歸一化的，所以矩陣U的每行元素的和應該等于1.因此需要對矩陣M引入相同的約束，即與mij≥0.

給定一組數據集X=[ ]x1,x2,x3,…,xn，定義為數據點xi與xj的距離，每一個最小距離對應一個鄰接權mij.另外規定mii=0.下面給出目標函數.

為了確保數據圖的稀疏性，限制mi的非零元的個數為q，即‖ ‖mi0=q，需要解決問題，其中為目標函數（11）的最優解.

3 實驗結果與分析

首先選取一個100×100的塊對角矩陣，其中有五塊數據，每一塊為20×20維.其中的數據表示一族數據集兩個對應點的鄰接值，其余所有部分為噪聲.每一塊內的鄰接數據是在0到1之間隨機產生的；噪聲是在0到m間隨機產生的，其中m分別取0.65、0.75、0.85進行試驗，此外隨機挑選20個噪聲數據點，將他們的值設置成1.

參數的設置為：聚類數目k=5.對于正則化參數τ首先令τ=0.1.在每一次迭代中，如果LU的特征值數目大于k，則取τ的如果LU的特征值數目小于k，則取τ的2倍；當LU的特征值數目等于k時，停止迭代.隨機產生的矩陣以及文中所述方法在不同設置下的聚類結果，如圖1所示.

圖1 隨機產生的矩陣以及不同設置下的聚類結果

本文所提到的聚類算法（RAGR）與比例分割（Ratio Cut）、歸一化分割（Normalized Cut）在合成數據中不同噪聲環境下標準聚類精度（ACC）和歸一化互信息（NMI）的比對結果，如表1所示.

表1 RAGR、Ratio Cut、Normalized Cut在合成數據中不同噪聲環境下的ACC和NMI的比對結果

4 結論

在相同的初始化條件下，用不同的聚類方法，重復超過60次試驗.實驗結果表明當噪聲逐漸增大時，本文所述聚類算法的精確度明顯高于其他傳統聚類算法的精確度，從而體現了本文所述聚類算法的魯棒性.合成數據集實驗結果證明了本文所述聚類算法的可行性及有效性.

O29

A

1008-7974（2018）01-0035-04

10.13877/j.cnki.cn22-1284.2018.02.010

2017-05-22

遼寧省自然科學基金項目（60875029）.

董昊，女，遼寧鳳城人，遼寧師范大學數學學院碩士研究生（遼寧 大連 116029）.

［1］周愛武，于亞飛.K-Means聚類算法的研究［J］.計算機技術與發展，2011，21（2）：62-65.

［2］U Luxburg.A tutorial on spectral clustering［J］.Statistics and Computing，2007，17（4）：395-416.

［3］Nie F，Wang X，Jordan M，et al.The Constrained Laplacian Rank Algorithm forGraph-Based Clustering［J］.Artificial Intelligence，Phoenix，2016，34（5）：1012-1016.

［4］Nie F，Wang X，Huang H.Clustering and projected clustering with adaptive neighbors［J］.Knowledge Discovery and Data Mining，2014，42（6）：977-986.

［5］Fan K.On a theorem of Weyl concerning eigenvalues of linear transformations［J］.Natl Acad Sci，1949，35（11）：652-655.

［6］Nie F，Huang H，Cai X C.Efficient and robust feature selection via joint 2，1-norms minimization［J］.Neural Information Processing Systems，2010，37（12）：