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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2 優(yōu)化求解

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

2.2.1 固定μ，求解W

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

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

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

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

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

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

2.2.2 固定W，求解μ

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

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

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

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

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

（3）否則有：

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

2.3 算法流程

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

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

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

1.通過公式（3）至（7）計算距離矩陣

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

3. 通過公式（15）更新W 矩陣

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

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

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

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

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

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

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

2.6 算法收斂分析

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

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

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

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

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

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

3 實驗及分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表8 不同方法在三個數(shù)據(jù)庫上運行時間 s

4 結(jié)論

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