聯(lián)合低秩稀疏的多核子空間聚類算法

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中λ0＞0和λ1＞0是平衡參數(shù)。

但是，模型式（6）只適用于線性數(shù)據(jù)，而實際應(yīng)用中往往更多面臨的是非線性數(shù)據(jù)。因此，通常的做法是把原始空間中的非線性數(shù)據(jù)通過核函數(shù)φ(X)映射到可再生空間RKHS中。給定一組數(shù)據(jù)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），得到魯棒的核稀疏與低秩約束自表示學(xué)習(xí)模型為：

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

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

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

綜上，將多核學(xué)習(xí)與魯棒的核低秩稀疏自表示學(xué)習(xí)相結(jié)合，得到最終的目標函數(shù)：

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

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

圖1 JLSMKC流程Fig.1 Flowchart of JLSMKC

2 算法優(yōu)化求解

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

其增廣拉格朗日函數(shù)如下：

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

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

令式（12）的一階導(dǎo)數(shù)為零，得閉式解為：

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

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

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

式中，gi為G的第i列。

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

令式（20）的一階導(dǎo)數(shù)為零，得到K的閉式解為：

學(xué)習(xí)得到K*后，核Ki與共識核K的相似程度與wi呈正相關(guān)，即K和Ki越相似則權(quán)重wi越大；反之亦然。故wi的更新式為：

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

3 實驗與結(jié)果分析

3.1 實驗準備

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

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

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

圖2 5個圖像數(shù)據(jù)集示例樣本Fig.2 Samples of five image datasets

表1 數(shù)據(jù)集樣本信息Tab.1 Information of dataset samples

3.2 聚類性能比較

表2 給出了本文算法與5 個流行算法20 次獨立實驗得到的ACC、NMI 和Purity 的均值和標準差，其中用粗體表示的均值和標準差代表其聚類性能最好。因此，從表2 可知，本文提出的算法JLSMKC 的聚類性能優(yōu)于目前最流行的5 種多核聚類算法。在Yale、Jaffe、ORL、BA、TR11、TR45、COIL20 數(shù)據(jù)集上，與對比算法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 數(shù)據(jù)集上，本文算法的Purity 分別提升了5.79、10.63、5.05、0.68、5.39 個百分點；另外兩個數(shù)據(jù)集其Purity精度有所下降，但是并不影響算法整體性能。

3.3 算法收斂性

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

3.4 關(guān)系圖比較

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

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

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

圖4 學(xué)習(xí)得到的關(guān)系矩陣Fig.4 Learned relation matrices

3.5 參數(shù)敏感性

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

為了驗證JLSMKC 的參數(shù)敏感性，本文在ORL 和Yale 數(shù)據(jù)集上進行網(wǎng)格參數(shù)搜索實驗，令λ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 數(shù)據(jù)集上，當(dāng)λ1≤10-2且λ2≥1 時，JLSMKC 能獲得最好的聚類精度。在Yale 數(shù)據(jù)集上，當(dāng)λ1≤10-1且0.5 ≤λ2≤1 時，JLSMKC 能獲得最好的聚類精度。實驗結(jié)果表明，JLSMKC的參數(shù)容易調(diào)節(jié)，且對參數(shù)變化不敏感。

圖5 參數(shù)敏感性Fig.5 Parameter sensitivity

3.6 時間消耗比較

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

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

4 結(jié)語

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