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

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

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

0 引言

高維數(shù)據(jù)聚類是數(shù)據(jù)挖掘、計算機(jī)視覺、機(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é)果。但是，譜聚類算法嚴(yán)重依賴于構(gòu)建關(guān)系圖的質(zhì)量，因此關(guān)系圖的構(gòu)造是該類算法的關(guān)鍵步驟。此外，由于噪聲和離群值的影響，真實環(huán)境的數(shù)據(jù)不嚴(yán)格遵循子空間結(jié)構(gòu)，可能導(dǎo)致不正確的子空間聚類。因此，譜聚類算法面臨著兩個挑戰(zhàn)性的問題：①如何從噪聲數(shù)據(jù)中學(xué)習(xí)高質(zhì)量關(guān)系圖來滿足聚類的目的；②當(dāng)數(shù)據(jù)不是嚴(yán)格來自于線性子空間時，如何處理非線性數(shù)據(jù)。

對于問題①，基于低秩表示（Low-Rank Representation，LRR）［8］和稀疏表示（Sparse Representation，SR）［9］的聚類算法被廣泛研究。其中：LRR用核范數(shù)（又稱跡范數(shù)）約束關(guān)系圖，誘導(dǎo)關(guān)系圖具有低秩性，從而保持?jǐn)?shù)據(jù)的全局流形結(jié)構(gòu)；SR用L1范數(shù)約束關(guān)系圖，誘導(dǎo)關(guān)系圖具備稀疏性，從而保持?jǐ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］，因此有必要擴(kuò)展單核學(xué)習(xí)模型到多核學(xué)習(xí)（Multiple Kernel Learning，MKL）［15］模型。MKL 模型是一種靈活的學(xué)習(xí)模型，該模型的關(guān)鍵在于設(shè)計一個核加權(quán)策略，能夠整合多個候選核來產(chǎn)生一個最佳的共識核，該共識核能充分利用各個候選核的互補(bǔ)信息與冗余信息，還能避免核函數(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 擴(kuò)展到多核模型，RMKKM是MKKM 的魯棒性版本，它可以同時找到多個候選核的最佳組合和最佳類簇標(biāo)簽。由于關(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ù)集自動進(jìn)行核函數(shù)選擇和核參數(shù)調(diào)諧，從而學(xué)習(xí)一個最佳的共識核K；考慮噪聲影響，在核空間中引入噪聲項E，提高模型魯棒性。所提的模型同時學(xué)習(xí)關(guān)系圖S、共識核K、噪聲E，三者相互促進(jìn)達(dá)到最佳狀態(tài)。

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

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ù)中分離出小隨機(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進(jìn)行譜聚類，最終得到聚類結(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的貢獻(xiàn)）。

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

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

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

圖1 JLSMKC流程Fig.1 Flowchart of JLSMKC

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

本文提出利用交替方向乘子法（Alternating Direction Method of Multipliers，ADMM）［22］求解式（9）。因此，首先引入輔助變量J和A，讓式（9）變得可分割，得到以下目標(biāo)函數(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 實驗準(zhǔn)備

為了驗證所提出的JLSMKC的聚類性能，本文采用7種不同類型的數(shù)據(jù)集進(jìn)行實驗，數(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 所示，可以參考文獻(xiàn)［15］更好地了解這7 個數(shù)據(jù)集。

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

本文用聚類精度（ACCuracy，ACC）、標(biāo)準(zhǔn)互信息（Normalized Mutual Information，NMI）、純度（Purity）3 個指標(biāo)來評價所有多核算法的聚類性能，3 個指標(biāo)都與聚類性能呈正相關(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 的均值和標(biāo)準(zhǔn)差，其中用粗體表示的均值和標(biāo)準(zhǔn)差代表其聚類性能最好。因此，從表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ù)集上進(jìn)行測試，用殘差公式記錄20次殘差迭代值，這里殘差沒有明確單位，最終得到如圖3 所示的收斂曲線。從圖3 可知，JLSMKC 在5 次左右逐漸趨于穩(wěn)定并達(dá)到收斂，這表明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 的目標(biāo)函數(shù)涉及三個參數(shù)：系數(shù)λ0用于平衡關(guān)系圖的低秩稀疏程度，λ0→∞時變成稀疏自表示模型，λ0→0 時變成低秩自表示模型；λ1用于平衡噪聲成分；λ2用于平衡多核學(xué)習(xí)項。

為了驗證JLSMKC 的參數(shù)敏感性，本文在ORL 和Yale 數(shù)據(jù)集上進(jìn)行網(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ù)的選擇。最后，用交替方向乘子法求解目標(biāo)函數(shù)，迭代增強(qiáng)關(guān)系圖和核矩陣質(zhì)量，從而有效地提高了譜聚類算法的性能。通過在7 種數(shù)據(jù)集上與5 種流行的同類型聚類算法比較可知，本文算法具有收斂性好、時間成本低、參數(shù)不敏感等優(yōu)點。但是對于大規(guī)模數(shù)據(jù)的處理，該算法還存在一定的局限性，因此，以后將用神經(jīng)網(wǎng)絡(luò)來提高共識核質(zhì)量。