多局部約束自表示的譜聚類算法

蔣憶睿，裴 洋，陳 磊，王文樂(lè)，代江艷，易玉根

1.江西師范大學(xué) 軟件學(xué)院，南昌330022

2.濰坊學(xué)院 計(jì)算機(jī)工程學(xué)院，山東 濰坊261061

1 引言

子空間聚類（Subspace Clustering，SC）是機(jī)器學(xué)習(xí)、模式識(shí)別和計(jì)算機(jī)視覺(jué)等眾多領(lǐng)域中研究熱點(diǎn)之一[1-3]。近些年，子空間聚類受到研究者的廣泛關(guān)注，并提出了大量算法用于挖掘高維數(shù)據(jù)的低維結(jié)構(gòu)[4-7]。根據(jù)采用方法的不同，大致可以將子空間聚類方法分為五類：基于代數(shù)方法、基于統(tǒng)計(jì)方法、基于迭代方法、基于矩陣分解方法和基于譜聚類的方法[8]。在上述方法中，由于基于譜聚類（Spectral Clustering）的方法具有較強(qiáng)的理論基礎(chǔ)，并且在圖像表示、圖像聚類等實(shí)際應(yīng)用領(lǐng)域中取得優(yōu)越的性能，因此，它已成為目前子空間聚類的主流技術(shù)之一[9-10]。

譜聚類方法首先通過(guò)計(jì)算樣本間的相似關(guān)系構(gòu)建圖，然后對(duì)圖的拉普拉斯矩陣進(jìn)行特征值分解得到相應(yīng)的低維表示，最后利用k-mean 算法對(duì)其進(jìn)行聚類[11-12]。因此，基于譜聚類方法的核心問(wèn)題是如何有效地構(gòu)建圖。傳統(tǒng)的圖構(gòu)建方法，一類是基于數(shù)據(jù)的距離（如余弦距離或熱核距離），主要包括k-近鄰和ε-球方法[12]。而另一類方法則是通過(guò)最小化局部樣本重構(gòu)誤差的方式實(shí)現(xiàn)圖的構(gòu)建[13]。由于上述兩類方法具有直觀且易實(shí)現(xiàn)等特點(diǎn)，因此它們被廣泛用于譜聚類和基于圖的維數(shù)約簡(jiǎn)等方法中，并取得較好的性能。然而，這些方法所涉及的鄰域參數(shù)和熱核參數(shù)在實(shí)際問(wèn)題中難以選擇。參數(shù)一旦選取不恰當(dāng)，將會(huì)導(dǎo)致聚類算法無(wú)法很好地挖掘數(shù)據(jù)的內(nèi)在結(jié)構(gòu)。另外，這些方法為所有樣本設(shè)置相同的參數(shù)，這也將導(dǎo)致算法不能很好地反映非均勻分布樣本的局部結(jié)構(gòu)。

為了解決上述問(wèn)題，相繼提出了大量基于數(shù)據(jù)驅(qū)動(dòng)的自適應(yīng)圖構(gòu)建方法[14-15]。例如：Yang 等人[14]提出了樣本依賴圖（SG-graph）的方法，該方法根據(jù)計(jì)算每個(gè)樣本與所有樣本之間的平均相似性的差異尋找樣本近鄰。因此，它可以自適應(yīng)地確定圖中每個(gè)樣本的近鄰數(shù)。隨著基于稀疏表示的方法在眾多領(lǐng)域中的成功應(yīng)用，基于稀疏表示的構(gòu)圖方法也相繼被提出[15]，也被稱為L(zhǎng)1圖。如Elhamifar 等人[15]提出稀疏子空間聚類（Sparse Subspace Clustering，SSC）方法，該方法首先假設(shè)每個(gè)樣本可以用其他樣本線性表示，并對(duì)其表示系數(shù)加以基于l1-范數(shù)的稀疏約束。盡管基于稀疏表示的方法可以自適應(yīng)選擇樣本的鄰域和計(jì)算樣本的權(quán)值，但該類方法需要分別求解每個(gè)樣本的稀疏表示，從而增加了算法時(shí)間代價(jià)。另外，由于單獨(dú)對(duì)每個(gè)樣本進(jìn)行求解將導(dǎo)致所構(gòu)建的圖不能很好地刻畫(huà)數(shù)據(jù)全局結(jié)構(gòu)信息。

于是，為了解決上述方法存在的問(wèn)題，Liu等人[16]提出基于低秩表示（Low-Rank Representation，LRR）的譜聚類方法，該方法通過(guò)求解數(shù)據(jù)的低秩表示獲取數(shù)據(jù)的全局結(jié)構(gòu)。然而，由于LRR 方法在每次迭代求解過(guò)程中都需要進(jìn)行奇異值分解并且收斂較慢，因此，該方法不適應(yīng)于處理大規(guī)模高維數(shù)據(jù)。為了提高算法的效率，Lu等人[17]提出了一種基于最小二乘回歸（Least Squares Regression，LSR）的譜聚類方法，該方法充分利用數(shù)據(jù)的相關(guān)性將高度相關(guān)的數(shù)據(jù)聚集在一起。與LRR算法相比，LSR方法的求解簡(jiǎn)單且高效。盡管通過(guò)LSR方法所構(gòu)建的圖可以獲取樣本的全局結(jié)構(gòu)，但其樣本的局部結(jié)構(gòu)卻被忽略。換句話說(shuō)，LSR方法并沒(méi)有考慮樣本點(diǎn)之間的距離關(guān)系，將導(dǎo)致在線性重構(gòu)時(shí)選擇距離較遠(yuǎn)的樣本進(jìn)行重構(gòu)，形成的圖并不能很好地反映數(shù)據(jù)的局部結(jié)構(gòu)。然而，大量研究表明，數(shù)據(jù)的局部性在數(shù)據(jù)聚類和分類等任務(wù)中起著非常重要的作用。因此，Chen 等人[18]結(jié)合局部約束和LSR 方法提出一種局部約束最小二乘回歸（Locality-Constrained LSR，LCLSR）方法，充分繼承LSR 方法和局部約束的優(yōu)點(diǎn)。文獻(xiàn)[18]中的實(shí)驗(yàn)結(jié)果驗(yàn)證LCLSR 方法的聚類性能要優(yōu)于LSR 方法，但局部約束的選擇將會(huì)影響LCLSR方法的性能。

目前，提出了大量的距離度量方法，如基于指數(shù)函數(shù)的方法[19]、基于歐式距離的方法[20]、基于內(nèi)積的方法[21]等。這些不同的距離度量方法都是基于不同的假設(shè)或準(zhǔn)則提出的，它們可能僅適用于表征特定類型數(shù)據(jù)的結(jié)構(gòu)。因此，如何有效選擇哪一種距離度量方法更適合特定任務(wù)和數(shù)據(jù)仍然是一個(gè)有待研究的問(wèn)題。

本文為了解決上述方法存在的局限性，提出了一種多局部約束自身表示（Multiple Locality Constrained Self Representation，MLCSR）圖構(gòu)建方法用于譜聚類，MLCSR 算法具有如下優(yōu)點(diǎn)：（1）MLCSR 方法繼承了樣本的自表示能力和局部約束的優(yōu)點(diǎn)，并將數(shù)據(jù)的自表示和局部性集成到一個(gè)統(tǒng)一的框架中。（2）MLCSR方法能夠自適應(yīng)地將不同的距離度量函數(shù)組合到局部約束中，從而保證算法更具有靈活性和實(shí)用性。本文提出了一種基于迭代更新的優(yōu)化策略來(lái)優(yōu)化MLCSR 算法。另外，通過(guò)大量實(shí)驗(yàn)驗(yàn)證了MLCSR方法的有效性。

2 多局部約束自表示圖構(gòu)建方法

2.1 目標(biāo)函數(shù)

假設(shè)矩陣X=[x1,x2,…,xN]∈RD×N表示樣本集合，其中，包括N 個(gè)樣本，每個(gè)樣本的維度為D。

首先，假設(shè)集合中的任意樣本都可以由其他樣本線性表示。不同于LCLSR 方法，本文對(duì)表示系數(shù)加以非負(fù)約束使之更具有線性表示的物理意義，目標(biāo)函數(shù)可定義為公式（1）：

其中，W=[w1,w2,…,wN]∈RN×N表示系數(shù)矩陣。

其次，為了在樣本重構(gòu)時(shí)考慮數(shù)據(jù)的局部結(jié)構(gòu)性，本文定義局部約束項(xiàng)如公式（2）所示：

其中，D=[dist(xi,xj)]N×N表示樣本間的距離矩陣，其元素dist(xi,xj)表示樣本xi和xj之間距離，dist(?)表示距離度量函數(shù)，||?||1則表示矩陣的l1范數(shù)，符號(hào)⊙表示矩陣元素的點(diǎn)乘操作運(yùn)算。通過(guò)最小化公式（2）可以盡可能選擇距離與重構(gòu)樣本較近的樣本進(jìn)行重構(gòu)。

同時(shí)，為了考慮不同距離度量函數(shù)對(duì)局部約束的影響，本文采用五種常用的距離度量函數(shù)[19-23]。如文獻(xiàn)[20]定義的一種基于歐式距離的函數(shù)，如公式（3）所示：

文獻(xiàn)[19]定義了一種基于指數(shù)的距離度量函數(shù)，如公式（4）所示：

其中，σ 是非零參數(shù)。在實(shí)驗(yàn)中，本文將其設(shè)置為所有樣本歐式距離的均值。

文獻(xiàn)[21]定義了一種基于內(nèi)積的距離度量函數(shù)，如公式（5）所示：

文獻(xiàn)[22]結(jié)合指數(shù)距離和內(nèi)積距離函數(shù)定義為公式（6）：

其中，θ 是非零參數(shù)。實(shí)驗(yàn)中本文將其設(shè)置為所有樣本內(nèi)積的均值。

文獻(xiàn)[23]定義了一種基于l1范數(shù)的距離度量函數(shù)，如公式（7）所示：

其中，max(||xi-xj||1)i,j=1,2,…,N表示所有樣本的l1范數(shù)距離最大值。

然后，為了充分考慮不同距離度量函數(shù)之間互補(bǔ)性，本文將局部約束項(xiàng)重新定義為公式（8）：

其中，M 表示采用距離度量函數(shù)的數(shù)量（本文M=5），μ=[μ1,μ2,…,μM]為權(quán)值向量，α ＞0 為平衡參數(shù)。

最后，結(jié)合公式（1）和公式（8），MLCSR方法的最終目標(biāo)函數(shù)如公式（9）所示：

其中，參數(shù)α 和β 平衡各項(xiàng)在目標(biāo)函數(shù)中的貢獻(xiàn)。

2.2 優(yōu)化求解

從目標(biāo)函數(shù)公式（9）可以看出，有兩個(gè)變量（W 和μ）需要優(yōu)化，然而對(duì)于這兩個(gè)變量而言，目標(biāo)函數(shù)公式（9）為一個(gè)非凸函數(shù)，因此，無(wú)法給出目標(biāo)函數(shù)的全局最優(yōu)解。但對(duì)于單個(gè)變量而言，目標(biāo)函數(shù)是一個(gè)凸函數(shù)，因此，本文給出一種基于迭代的優(yōu)化算法對(duì)目標(biāo)函數(shù)進(jìn)行求解，即，固定其中一個(gè)變量，更新另一個(gè)變量。

2.2.1 固定μ，求解W

從目標(biāo)函數(shù)中移除無(wú)關(guān)項(xiàng)，有關(guān)W 的優(yōu)化問(wèn)題可轉(zhuǎn)化為公式（10）：

對(duì)公式（10）進(jìn)行運(yùn)算，可簡(jiǎn)化為：

求解公式（11），需引入拉格朗日乘子矩陣Λ，則公式（11）的拉格朗日函數(shù)定義為公式（12）：

對(duì)公式（12）求導(dǎo)并令其導(dǎo)數(shù)等于零，則有：

根據(jù)KKT條件ΛijWij=0[24]，則有：

根據(jù)公式（14），W 更新如公式（15）所示：

2.2.2 固定W，求解μ

從目標(biāo)函數(shù)中移除無(wú)關(guān)項(xiàng)，有關(guān)μ 的優(yōu)化問(wèn)題可以轉(zhuǎn)換為公式（16）：

其中，qm=||Dm⊙W||1和。公式（16）是標(biāo)準(zhǔn)的凸二次規(guī)劃問(wèn)題，本文采用文獻(xiàn)[25]的坐標(biāo)梯度下降（Coordinate Descent Algorithm，CDA）方法求解。具體求解過(guò)程如下：考慮約束條件μm≥0 和，在每次迭代過(guò)程中僅更新權(quán)值向量μ 中的任意兩個(gè)成對(duì)的元素，而固定其他元素。首先，假設(shè)需要更新的成對(duì)元素為μk和μl(k ≠l)，固定其他元素μm(m ≠k,l)，根據(jù)上述約束條件，則有：

令ρ(μk)為目標(biāo)函數(shù)，表示如下：

對(duì)公式（18）求導(dǎo)數(shù)，并令其等于零，則有：

根據(jù)公式（19），則有：

（3）否則有：

通過(guò)公式（22）至公式（24），成對(duì)更新μ 中的所有成對(duì)元素，直到目標(biāo)函數(shù)達(dá)到收斂。

2.3 算法流程

本文提出的基于多局部約束的自表示圖構(gòu)建算法如算法1所示。

算法1 基于多局部約束的自表示圖構(gòu)建算法

輸入：樣本集X=[x1,x2,…,xN]∈RD×N，參數(shù)α 和β

1.通過(guò)公式（3）至（7）計(jì)算距離矩陣

2.循環(huán)迭代執(zhí)行步驟3和4直到達(dá)到收斂條件

3. 通過(guò)公式（15）更新W 矩陣

4. 通過(guò)CDA方法求解權(quán)值向量μ

輸出：矩陣W ，權(quán)值向量μ

2.4 計(jì)算復(fù)雜度分析

本節(jié)主要對(duì)算法1 的計(jì)算復(fù)雜性進(jìn)行分析。假設(shè)M 為本文所采用距離度量的數(shù)量，則其計(jì)算復(fù)雜度為O(MDN2)。根據(jù)文獻(xiàn)[25]，更新權(quán)值向量的計(jì)算復(fù)雜度為O(M2)，更新W 矩陣的計(jì)算復(fù)雜度為O(DN2)。因此，算法的總體計(jì)算復(fù)雜度為O(MDN2+T(M2+DN2))，其中T 表示算法的迭代次數(shù)。表1 給出不同圖構(gòu)建算法的計(jì)算復(fù)雜度的對(duì)比結(jié)果。從表中可以看出，KNN算法的計(jì)算復(fù)雜度最小，L1、LRR 和MLCSR 三個(gè)算法的計(jì)算復(fù)雜度要高于其他方法。

表1 不同算法的計(jì)算復(fù)雜度

2.5 參數(shù)設(shè)置

從目標(biāo)函數(shù)公式（9）中可知，本文方法包括兩個(gè)參數(shù)，分別為α 和β。參數(shù)α 主要用于控制局部約束項(xiàng)重要性，而參數(shù)β 用于控制不同拉普拉斯矩陣的權(quán)值。因此，參數(shù)的取值應(yīng)根據(jù)數(shù)據(jù)庫(kù)特征進(jìn)行設(shè)置。更為詳細(xì)的說(shuō)，當(dāng)來(lái)自同類的樣本具有較高的相似性，并與其他類樣本可以較容易分開(kāi)，此時(shí)應(yīng)該將參數(shù)α 設(shè)置較大的值使之能夠很好地保持?jǐn)?shù)據(jù)的局部結(jié)構(gòu)信息。相反，當(dāng)樣本的鄰域樣本來(lái)自于不同類的樣本，此時(shí)將參數(shù)α 設(shè)置為較小值。對(duì)于參數(shù)β 而言，當(dāng)β →∞，所有拉普拉斯矩陣的權(quán)值相同，此時(shí)，忽略了不同拉普拉斯矩陣的差異。當(dāng)β 設(shè)置為零，權(quán)值向量μ 中僅有一個(gè)元素有值，也是說(shuō)僅僅一個(gè)拉普拉斯矩陣被利用。因此，參數(shù)β 應(yīng)該設(shè)置為適中的值。

2.6 算法收斂分析

本節(jié)主要對(duì)算法收斂性進(jìn)行分析。首先，將目標(biāo)函數(shù)公式（9）標(biāo)記為φ(W,μ)，則有如下理論：

理論1 目標(biāo)函數(shù)φ(W,μ)其函數(shù)值是遞減的。

證明 令φ(Wt,μt)表示目標(biāo)函數(shù)在第t 次迭代時(shí)的目標(biāo)函數(shù)值。首先，在第t+1 迭代時(shí)，固定μt，再求解子優(yōu)化問(wèn)題。對(duì)于該子優(yōu)化問(wèn)題的收斂性證明可以參閱文獻(xiàn)[26]。因此在每次迭代W 時(shí)，目標(biāo)函數(shù)值隨著降低，故有如下不等式成立：

然后，固定Wt，繼續(xù)求解子優(yōu)化問(wèn)題對(duì)于求解此優(yōu)化問(wèn)題，本文采用CDA算法求解，可以獲得最優(yōu)的μt+1。由于該優(yōu)化問(wèn)題屬于一個(gè)凸優(yōu)化問(wèn)題，故有如下不等式：

最后，結(jié)合不等式（25）和（26），可得到如下不等式：

綜上所述，理論1 已被證明。而且，由于目標(biāo)函數(shù)公式（9）中的所有項(xiàng)都是大于等于零，因此，目標(biāo)函數(shù)具有最小值。因此，根據(jù)柯西收斂準(zhǔn)則[27]，本文提出方法的目標(biāo)函數(shù)是收斂的。并且在數(shù)值實(shí)驗(yàn)中也驗(yàn)證了目標(biāo)函數(shù)值隨著迭代次數(shù)的增加能夠快速趨于收斂。

3 實(shí)驗(yàn)及分析

為了測(cè)試本文提出的MLCSR 算法的有效性，在3個(gè)標(biāo)準(zhǔn)的人臉圖像數(shù)據(jù)庫(kù)進(jìn)行實(shí)驗(yàn)（如Yale[28]、AR[29]和CMU PIE[30]）。三個(gè)圖像數(shù)據(jù)庫(kù)的具體信息如表2 所示，以及每個(gè)數(shù)據(jù)庫(kù)中的部分實(shí)例圖像如圖1所示。

表2 數(shù)據(jù)庫(kù)詳細(xì)信息

圖1 數(shù)據(jù)庫(kù)中部分實(shí)例圖

本實(shí)驗(yàn)中將MLCSR方法與不同的圖構(gòu)建方法比較，如KNN[12]、LLE[13]、L1[15]、LRR[16]、LSR[17]和LCLSR[18]。本文提出的方法和所有對(duì)比方法都是基于Matlab2016 編程實(shí)現(xiàn)的。實(shí)驗(yàn)平臺(tái)為Intel?Core?i7-4790，雙核GPU，頻率為3.60 GHz，內(nèi)存為8 GB，系統(tǒng)為64 位Windows 10 系統(tǒng)。此外，MLCSR 方法采用公式（3）至公式（7）的五個(gè)距離度量函數(shù)。在實(shí)驗(yàn)中采用網(wǎng)格式搜索方式尋找各個(gè)方法中參數(shù)的最優(yōu)取值。由于譜聚類中的kmeans 聚類算法的性能依賴于初始化，因此，實(shí)驗(yàn)中將隨機(jī)執(zhí)行50 次不同的初始化，然后統(tǒng)計(jì)其平均值和標(biāo)準(zhǔn)差作為最終結(jié)果。本文采用三個(gè)常用的度量準(zhǔn)則：聚類準(zhǔn)確率（ACC）、歸一化互信息（NMI）和純度（Purity）評(píng)價(jià)聚類算法的性能。不同方法在三個(gè)人臉數(shù)據(jù)庫(kù)上的實(shí)驗(yàn)結(jié)果，如表3至表5所示。

表3 不同方法在Yale數(shù)據(jù)庫(kù)上聚類結(jié)果 %

表4 不同方法在AR數(shù)據(jù)庫(kù)上聚類結(jié)果 %

表5 不同方法在CMU PIE數(shù)據(jù)庫(kù)上聚類結(jié)果%

從表3至表5的實(shí)驗(yàn)結(jié)果中可得到如下結(jié)論：

（1）基于KNN 和LLE 圖的聚類性能要低于其他構(gòu)圖方法，其主要原因是基于歐式距離的KNN 和LLE 圖對(duì)數(shù)據(jù)中的噪聲點(diǎn)、局外點(diǎn)以及參數(shù)取值非常敏感。

（2）因?yàn)榛贚RR 和LSR 的方法在構(gòu)圖過(guò)程中考慮數(shù)據(jù)的全局結(jié)構(gòu)，所以，它們的性能要優(yōu)于L1 圖的方法。

（3）由于基于LRR和LSR的圖構(gòu)建方法忽略了數(shù)據(jù)的局部結(jié)構(gòu)，因此，它們聚類效果要低于LCLSR方法。

（4）由于本文提出的MLCSR 方法融合了多個(gè)距離度量準(zhǔn)則，可以充分挖掘數(shù)據(jù)的局部結(jié)構(gòu)特性，所以它的性能要優(yōu)于所有對(duì)比方法。

其次，為了驗(yàn)證采用不同距離度量的必要性。實(shí)驗(yàn)中將測(cè)試單獨(dú)采用一種距離度量函數(shù)的算法聚類性能，其結(jié)果如表6所示。從表中可觀察到，僅僅用單一的距離度量函數(shù)的聚類正確率要低于融合使用多個(gè)距離度量函數(shù)的。因此，實(shí)驗(yàn)結(jié)果說(shuō)明了本文采用多個(gè)距離準(zhǔn)則是有必要的。為了進(jìn)一步驗(yàn)證不同距離函數(shù)的權(quán)值對(duì)算法性能的影響，在實(shí)驗(yàn)中將所有距離函數(shù)的權(quán)值設(shè)置為等同值，其結(jié)果如表7 所示，實(shí)驗(yàn)結(jié)果驗(yàn)證了權(quán)值分配對(duì)算法性能也有一定的影響。

表6 不同度量函數(shù)在數(shù)據(jù)庫(kù)上聚類準(zhǔn)確率ACC %

表7 不同權(quán)值本文方法在數(shù)據(jù)庫(kù)上聚類準(zhǔn)確率ACC %

接著，為了驗(yàn)證算法收斂性，圖2 給出MLCSR 算法在3 個(gè)人臉圖像數(shù)據(jù)庫(kù)上的目標(biāo)曲線圖。從圖中可以看出，MLCSR 算法在較少的迭代次數(shù)下就能達(dá)到收斂。

圖2 不同數(shù)據(jù)庫(kù)上的目標(biāo)曲線圖

最后，表8給出不同算法在各個(gè)數(shù)據(jù)庫(kù)上的運(yùn)行時(shí)間。從表8中看出，基于KNN、LLE和LSR和LCLSR的圖構(gòu)建方法的運(yùn)行時(shí)間總體要低于其他方法，但本文提出的構(gòu)圖方法的運(yùn)行時(shí)間要低于基于L1和LRR的構(gòu)圖方法。

表8 不同方法在三個(gè)數(shù)據(jù)庫(kù)上運(yùn)行時(shí)間 s

4 結(jié)論

通過(guò)融入多個(gè)距離度量準(zhǔn)則，本文提出一種基于多局部約束的自表示圖構(gòu)建方法用于譜聚類。不同于現(xiàn)有的方法，該方法不僅繼承了樣本間的自表示特性，同時(shí)還能充分挖掘數(shù)據(jù)的局部性。為了有效地求解目標(biāo)函數(shù)，本文基于迭代思想提出一種優(yōu)化算法，并在理論方法和數(shù)值實(shí)驗(yàn)中驗(yàn)證該優(yōu)化算法的收斂性。最后，在三個(gè)數(shù)據(jù)庫(kù)上的實(shí)驗(yàn)驗(yàn)證了本文方法有效性。