聯合低秩稀疏的多核子空間聚類算法

李杏峰，黃玉清*，任珍文

（1.西南科技大學信息工程學院，四川綿陽 621010；2.西南科技大學國防科技學院，四川綿陽 621010）

（?通信作者電子郵箱hyq_851@163.com）

0 引言

高維數據聚類是數據挖掘、計算機視覺、機器學習、生物信息學等諸多領域中研究的熱點問題［1］。以子空間角度來看，高維數據通常可以由其對應的潛在低維子空間來表示。子空間聚類的目的就是將來自不同子空間的高維數據分割到本質上所屬的低維子空間，子空間聚類是高維數據聚類的一種新方法［2-3］。通常子空間聚類算法可以粗略地分為5 類，即基于矩陣分解的方法、代數方法、迭代方法、統計方法和譜聚類方法［4-5］。

在子空間聚類算法中，譜聚類方法由于理論完備性與性能優越引起學者們極大的研究興趣，該方法主要包括兩個步驟［6-7］：1）根據輸入數據構造關系圖（也稱為關系矩陣），關系圖的每個元素反映兩個數據點之間的相似性；2）應用譜聚類算法將數據聚類到各自的子空間中，得到聚類結果。但是，譜聚類算法嚴重依賴于構建關系圖的質量，因此關系圖的構造是該類算法的關鍵步驟。此外，由于噪聲和離群值的影響，真實環境的數據不嚴格遵循子空間結構，可能導致不正確的子空間聚類。因此，譜聚類算法面臨著兩個挑戰性的問題：①如何從噪聲數據中學習高質量關系圖來滿足聚類的目的；②當數據不是嚴格來自于線性子空間時，如何處理非線性數據。

對于問題①，基于低秩表示（Low-Rank Representation，LRR）［8］和稀疏表示（Sparse Representation，SR）［9］的聚類算法被廣泛研究。其中：LRR用核范數（又稱跡范數）約束關系圖，誘導關系圖具有低秩性，從而保持數據的全局流形結構；SR用L1范數約束關系圖，誘導關系圖具備稀疏性，從而保持數據的局部流形結構。因此，理論上結合二者，則能同時保留關系圖的全局和局部的流形結構信息，也能讓關系圖同時具有低秩性和稀疏性，這將有利于學習更好的關系圖。

對于問題②，為克服線性子空間聚類方法不能處理非線性數據的缺點，將原始空間中的非線性數據映射到可再生希爾伯特空間（Reproducing Kernel Hilbert Space，RKHS）［10］中，在RKHS 中數據呈線性分布，這就使原始空間中的算法可以應用于RKHS 中。目前單核子空間聚類算法主要有：核K均值（KernelK-means，KKM）算法［11］、魯棒核K均值（Robust KernelK-Means，RKKM）算法［12］、單純形稀疏表示（Simplex Sparse Representation，SSR）算法［13］等。但是，單核方法目前也面臨核函數選擇、核參數調諧兩大難題［14］，因此有必要擴展單核學習模型到多核學習（Multiple Kernel Learning，MKL）［15］模型。MKL 模型是一種靈活的學習模型，該模型的關鍵在于設計一個核加權策略，能夠整合多個候選核來產生一個最佳的共識核，該共識核能充分利用各個候選核的互補信息與冗余信息，還能避免核函數的選擇。目前主要的多核方法有：多核K均值（Multiple KernelK-Means，MKKM）算法［16］、魯棒多核K均值（Robust Multiple KernelK-Means，RMKKM）算法［17］、自加權多核學習（Self-weighted Multiple Kernel Learning，SMKL）算法［18］、多核譜聚類（Spectral Clustering with Multiple Kernels，SCMK）算法［19］、基于圖的低秩核學習聚類（Low-rank Kernel learning Graph-based clustering，LKGr）算法［20］、基于圖的稀疏核學習聚類（sparse Kernel Learning Graph-based clustering，LKGs）算法［21］等。MKKM 將KKM 擴展到多核模型，RMKKM是MKKM 的魯棒性版本，它可以同時找到多個候選核的最佳組合和最佳類簇標簽。由于關系圖與核矩陣之間的相似性，AASC（Affinity Aggregation for Spectral Clustering）將譜聚類中的單個關系圖替換為多個核矩陣以提高關系圖質量。SCMK考慮在學習關系圖的同時，增加塊對角約束來提高關系圖的質量。利用最佳核是候選基核的線性組合，LKGr 和LKGs 分別學習低秩核矩陣和稀疏核矩陣來提高共識核與關系圖的質量。雖然上述多核方法能得到最佳的共識核、提高關系圖質量，但是上述多核方法很少考慮噪聲對模型的影響，而實際應用中數據一般都包含噪聲，這將會直接影響關系圖的質量，最終影響聚類性能。在沒有噪聲的情況下，假設有來自c個類的n個樣本，理想的關系圖是n×n的方陣，該方陣具有兩個特征：1）它同時遵循塊對角屬性和具備精確的c個連通部件，并且每個連通部件都有致密而清晰的結構；2）類間關系值均為零，類內關系值為非零，其關系值反映了兩個樣本間的相似性。

為了解決改善核函數選擇與核參數調諧的難題、提高關系圖質量和提高模型魯棒性，本文提出了一種新的聯合低秩稀疏的多核子空間聚類算法（Joint Low-rank and Sparse Multiple Kernel subspace Clustering algorithm，JLSMKC）。JLSMKC 利用核技巧將原始空間中帶噪聲的非線性原始數據映射到一個高維（甚至無限維度）的核特征空間中；在核空間中對關系圖S同時施加低秩與稀疏約束來保留數據在核空間的全局與局部結構信息，提高關系圖質量；引入MKL 學習框架，MKL 可以根據不同數據集自動進行核函數選擇和核參數調諧，從而學習一個最佳的共識核K；考慮噪聲影響，在核空間中引入噪聲項E，提高模型魯棒性。所提的模型同時學習關系圖S、共識核K、噪聲E，三者相互促進達到最佳狀態。

總體來講，本文研究的主要工作如下：1）同時保留關系圖的全局和局部的流形結構信息，顯著增強了關系圖質量；2）將高維非線性結構數據映射到核空間，再進行線性子空間聚類，有效解決了高維非線性數據聚類問題；3）提出了一個多核學習模型，通過學習一個最佳的共識核K，避免了核函數選擇、核參數調諧問題，提高了核Gram 矩陣的質量；4）引入L2，1范數約束的噪聲項E來分離誤差，增強對離群值的魯棒性。

1 基于多核低秩稀疏的約束模型

自表示學習框架（Self-Expressiveness learning Framework，SEF）［6］是目前主要的自動學習關系圖的方法之一。通常，給一個數據矩陣X∈Rd×n，X的每一列代表一個樣本，這些數據分別來自于c個子空間。每個子空間Si包含ni個數據樣本，樣本總數。每個數據點xi可近似地表示為同一空間中其他數據點的線性組合（即xi=，sij表示xi與xj之間的相似度，xi與xj越相似，sij就越大，反之亦然。當數據中不存在噪聲時，自表示圖學習框架定義為：

其中，S∈Rn×n是自表示關系圖。該框架的優點是結構簡潔、有閉式解，并且能夠充分捕獲原始數據結構以及互表示信息。通常，為了獲得不同需求的S，需要對S增加約束。

通過對S的低秩約束，可得低秩自表示模型［8，20］如下：

通過對S的稀疏約束，可得稀疏自表示模型［21］如下：

其中，λ0是平衡系數。顯然，當λ→∞時，變成稀疏自表示模型；λ0→0時，變成低秩自表示模型。

實際應用場景中的數據往往包含噪聲，為了提高模型魯棒性，在式（4）引入噪聲項E以及噪聲正則項R(E)，得到魯棒的低秩稀疏約束模型。該模型能夠同時抑制噪聲和提取干凈的低秩稀疏關系圖，具體如下：

其中：當R(E)為時，能夠從數據中分離出高斯噪聲；當R(E)為時，能夠從數據中分離出小隨機噪聲；當R(E)為時，能夠從數據中分離出較大噪聲以及離群值。本文采用，提出魯棒的稀疏與低秩約束自表示學習模型如下：

其中λ0＞0和λ1＞0是平衡參數。

但是，模型式（6）只適用于線性數據，而實際應用中往往更多面臨的是非線性數據。因此，通常的做法是把原始空間中的非線性數據通過核函數φ(X)映射到可再生空間RKHS中。給定一組數據X=[x1，x2，…，xn]∈Rd×n，映射到核空間后為φ(X)=[φ(x1)，φ(x2)，…，φ(xn)]。因此，將式（6）的約束項X=XS+E映射到核空間后得到φ(X)=φ(X)S+E，等式兩邊同時乘上φ(X)T，得到φ(X)Tφ(X)=φ(X)Tφ(X)S+E。由核技巧（kernel tricks），得到魯棒的核稀疏與低秩約束自表示學習模型為：

其中：K為核矩陣；S為關系圖。在得到S后，通過構造對稱關系圖W=(|S|T+|S|)/2 來消除不平衡性，然后利用W進行譜聚類，最終得到聚類結果。

盡管式（7）能夠解決非線性數據的聚類問題，但是它的性能在很大程度上取決于核函數及其參數的選擇。此外，從預先設定的基核池中搜索最合適的核函數非常耗時。基于此，本文提出一種MKL 模型。利用核加權策略學習一個最佳的共識核，有效地避免了核函數及其參數的選擇問題。MKL 模型如下：

其中：r為候選核數量；K為共識核，Ki為預定義候選核池中的第i個候選核；w=[w1，w2，…，wr]是候選核的權重（權值wi表示第i個候選核Ki對共識核K的貢獻）。

綜上，將多核學習與魯棒的核低秩稀疏自表示學習相結合，得到最終的目標函數：

其中，λ0、λ1、λ2為非負平衡參數。

JLSMKC的具體步驟如圖1所示。

圖1 JLSMKC流程Fig.1 Flowchart of JLSMKC

2 算法優化求解

本文提出利用交替方向乘子法（Alternating Direction Method of Multipliers，ADMM）［22］求解式（9）。因此，首先引入輔助變量J和A，讓式（9）變得可分割，得到以下目標函數：

其增廣拉格朗日函數如下：

其中：μ＞0是懲罰參數；Y1、Y2和Y3是拉格朗日乘子。

式（11）中求解S的子問題變成：

令式（12）的一階導數為零，得閉式解為：

式（11）中求解J的子問題變成：

式（11）中求解A的子問題變成：

式（11）中求解E的子問題變成：

式中，gi為G的第i列。

式（11）中求解K的子問題變成：

令式（20）的一階導數為零，得到K的閉式解為：

學習得到K*后，核Ki與共識核K的相似程度與wi呈正相關，即K和Ki越相似則權重wi越大；反之亦然。故wi的更新式為：

Y1、Y2、Y3和μ的更新式分別為：

3 實驗與結果分析

3.1 實驗準備

為了驗證所提出的JLSMKC的聚類性能，本文采用7種不同類型的數據集進行實驗，數據集分別是Yale、Jaffe、ORL、COIL20、Binary Alphadigits（BA）、TR11、TR45。其中：Yale、Jaffe、ORL是人臉數據集；COIL20是物像數據集；BA是手寫數據集；TR11、TR45 是文本數據集。這7 種不同的數據集被廣泛用于評估聚類算法的性能。通過這7 種數據集，將本文算法與5 種目前流行的多核算法對比分析。用5 個圖像數據集樣本生成的原始圖片如圖2 所示。數據集總的類數、樣本數、特征數如表1 所示，可以參考文獻［15］更好地了解這7 個數據集。

用于對比的5 種多核聚類算法分別為：MKKM、AASC、RMKKM、LKGr、SCMK。為了公平，這些對比算法的實驗參數都按照原文章內推薦的實驗參數設置。JLSMKC 使用的參數設置為：ρ=2，μ=0.5。

本文用聚類精度（ACCuracy，ACC）、標準互信息（Normalized Mutual Information，NMI）、純度（Purity）3 個指標來評價所有多核算法的聚類性能，3 個指標都與聚類性能呈正相關，值越大表明聚類性能越好［12］。

圖2 5個圖像數據集示例樣本Fig.2 Samples of five image datasets

表1 數據集樣本信息Tab.1 Information of dataset samples

3.2 聚類性能比較

表2 給出了本文算法與5 個流行算法20 次獨立實驗得到的ACC、NMI 和Purity 的均值和標準差，其中用粗體表示的均值和標準差代表其聚類性能最好。因此，從表2 可知，本文提出的算法JLSMKC 的聚類性能優于目前最流行的5 種多核聚類算法。在Yale、Jaffe、ORL、BA、TR11、TR45、COIL20 數據集上，與對比算法MKKM、AASC、RMKKM、SCMK、LKGr 中獲得的最高精度相比，本文算法的ACC 分別提升了3.35、12.46、3.83、5.87、10.55、3.11、2.66 個百分點，其NMI 分別提升了3.94、9.8、3.2、3.76、5.39、0.15、1.67 個百分點。在Yale、Jaffe、ORL、TR11、COIL20 數據集上，本文算法的Purity 分別提升了5.79、10.63、5.05、0.68、5.39 個百分點；另外兩個數據集其Purity精度有所下降，但是并不影響算法整體性能。

3.3 算法收斂性

為了驗證本文提出的算法JLSMKC 的收斂性，在COIL20與ORL 數據集上進行測試，用殘差公式記錄20次殘差迭代值，這里殘差沒有明確單位，最終得到如圖3 所示的收斂曲線。從圖3 可知，JLSMKC 在5 次左右逐漸趨于穩定并達到收斂，這表明JLSMKC具有很好的收斂特性。

3.4 關系圖比較

為了驗證本文提出的JLSMKC 具有良好的塊對角特性，在圖4 中給出了JLSMKC 在Yale 和Jaffe 數據集上學習得到的關系圖S。如圖4所示，從兩個數據集上學習到的關系圖具有塊對角特性，并且Jaffe 關系圖包含10 個對角塊（Jaffe 有10 個塊，故有10個類），由此可知JLSMKC具有較好的聚類性能。

表2 不同算法聚類實驗結果對比 單位：%Tab.2 Comparison of clustering results of different algorithms unit：%

圖3 JLSMKC的收斂曲線Fig.3 Convergence curve of JLSMKC

圖4 學習得到的關系矩陣Fig.4 Learned relation matrices

3.5 參數敏感性

JLSMKC 的目標函數涉及三個參數：系數λ0用于平衡關系圖的低秩稀疏程度，λ0→∞時變成稀疏自表示模型，λ0→0 時變成低秩自表示模型；λ1用于平衡噪聲成分；λ2用于平衡多核學習項。

為了驗證JLSMKC 的參數敏感性，本文在ORL 和Yale 數據集上進行網格參數搜索實驗，令λ0=1，λ1∈{0.000 1，0.001，0.01，0.1，1，10，100}，λ2∈{0.1，0.5，10，10，50，100}，測試在不同λ1和λ2下的聚類精度。由圖5 可知：在ORL 數據集上，當λ1≤10-2且λ2≥1 時，JLSMKC 能獲得最好的聚類精度。在Yale 數據集上，當λ1≤10-1且0.5 ≤λ2≤1 時，JLSMKC 能獲得最好的聚類精度。實驗結果表明，JLSMKC的參數容易調節，且對參數變化不敏感。

圖5 參數敏感性Fig.5 Parameter sensitivity

3.6 時間消耗比較

本文對比了RMKKM、AASC、SCMK、LKGr 與JLSMKC 在Yale、ORL、TR11 和TR45 數據集上的聚類時間，如表3 所示。由表3 可知，在4 種數據集上，本文提出的算法JLSMKC 聚類時間消耗最少，并且由表3可知，其聚類性能也最好。

表3 不同算法時間消耗對比單位：sTab.3 Comparison of computational time of different algorithms unit：s

4 結語

針對多核子空間譜聚類算法沒有考慮噪聲和關系圖結構的問題，本文提出了一種新的聯合低秩稀疏的多核子空間聚類算法（JLSMKC）。該算法既解決了高維非線性噪聲數據的聚類問題，又能提高多核聚類算法的魯棒性，同時還避免了核函數與和參數的選擇。最后，用交替方向乘子法求解目標函數，迭代增強關系圖和核矩陣質量，從而有效地提高了譜聚類算法的性能。通過在7 種數據集上與5 種流行的同類型聚類算法比較可知，本文算法具有收斂性好、時間成本低、參數不敏感等優點。但是對于大規模數據的處理，該算法還存在一定的局限性，因此，以后將用神經網絡來提高共識核質量。