基于核的低秩子空間聚類算法

馬凱 王偉文 由從哲

摘? ? 要：基于稀疏表示和低秩表示的子空間聚類算法是目前的研究熱點(diǎn)，但大多數(shù)子空間聚類方法只適用于線性子空間或仿射子空間。針對這一問題，研究了一種能處理非線性模型的核子空間聚類方法。提出學(xué)習(xí)一種低秩核映射，通過這種映射，特征空間中的映射數(shù)據(jù)不僅具有低秩性，而且具有自表達(dá)性，從而使得低維子空間結(jié)構(gòu)在高維特征空間中得以呈現(xiàn)。通過運(yùn)動(dòng)分割和人臉圖像聚類問題的實(shí)驗(yàn)，驗(yàn)證了方法的有效性。

關(guān)鍵詞：子空間聚類;低秩表示;核方法;運(yùn)動(dòng)分割;人臉聚類

中圖分類號(hào)：TP391.4? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ?文章編號(hào)：2095-7394（2021）04-0032-06

子空間聚類是指將位于一組低維線性子空間中的數(shù)據(jù)樣本點(diǎn)劃分到不同子空間中的算法。該算法在計(jì)算機(jī)視覺中有多種應(yīng)用，如：運(yùn)動(dòng)分割、圖像聚類?，F(xiàn)有的子空間聚類方法大致可分為三類[1]：代數(shù)算法、統(tǒng)計(jì)方法以及基于譜聚類的方法。目前，對于子空間聚類的研究熱點(diǎn)主要集中在基于表示的譜聚類算法[2-3]，算法主要步驟為：（1）構(gòu)建親和矩陣;（2）應(yīng)用譜聚類對親和圖進(jìn)行劃分，得到聚類結(jié)果。然而，這些方法只能處理線性子空間問題，在實(shí)際應(yīng)用中，數(shù)據(jù)點(diǎn)可能不完全適合線性子空間模型。例如，在運(yùn)動(dòng)分割問題中，相機(jī)通常具有某種程度的透視失真，因此，仿射相機(jī)假設(shè)不成立;在這種情況下，一個(gè)運(yùn)動(dòng)的軌跡就會(huì)位于非線性子空間中。

為了解決這一問題，也有一些方法通過核技巧將線性子空間聚類擴(kuò)展到對應(yīng)的非線性子空間。例如，核稀疏子空間聚類（KSSC）方法[4]采用多項(xiàng)式核或高斯RBF核將數(shù)據(jù)矩陣的內(nèi)積替換為核矩陣。KSSC算法假設(shè)數(shù)據(jù)是從對稱正定（SPD）矩陣中提取的，并將對Log-Euclidean核應(yīng)用于SPD矩陣上，實(shí)現(xiàn)SSC算法的核化。但是，由于這些方法中使用了預(yù)先定義的核，特征空間映射后的數(shù)據(jù)不能保證低秩;因此，很難形成多個(gè)低維子空間結(jié)構(gòu)。

在本文中，我們通過學(xué)習(xí)得到一個(gè)低秩核映射，這樣，通過核映射得到的特征空間中的數(shù)據(jù)都具有低秩性和自表示特性。直觀地說，本文方法強(qiáng)制核特征映射為低秩，從而使得數(shù)據(jù)在特征空間中形成線性子空間結(jié)構(gòu)。

1? ? 相關(guān)工作

子空間聚類算法的核心在于親和矩陣的構(gòu)造，來自同一子空間的數(shù)據(jù)點(diǎn)具有高親和值，而來自不同子空間的數(shù)據(jù)點(diǎn)具有低親和值（理想情況下為零）?；诒硎镜淖涌臻g聚類方法利用子空間自表示特性，即一個(gè)子空間中的數(shù)據(jù)樣本點(diǎn)可以表示為同一子空間中其他數(shù)據(jù)樣本點(diǎn)的線性組合，并利用自表示系數(shù)矩陣作為譜聚類的親和矩陣。

給定數(shù)據(jù)矩陣[X∈RD×N]，子空間自表示特性可以表示為[X=XZ]，其中，[Z]為自表示系數(shù)矩陣。JI等人[5]在子空間獨(dú)立的假設(shè)下，通過最小化[Z]的某些范數(shù)，得到[Z]的最優(yōu)解具有塊對角結(jié)構(gòu)，該優(yōu)化問題可以表示為如下形式：

在實(shí)際應(yīng)用中，數(shù)據(jù)往往含有噪聲，為了處理噪聲污染的數(shù)據(jù)，LRR算法的目標(biāo)函數(shù)可以表示為如下形式：

其中：[λ]為平衡參數(shù);采用[E2，1]來強(qiáng)調(diào)噪聲矩陣[E]的列稀疏性。

LRR的設(shè)計(jì)是為了處理原始輸入空間中子空間并集的數(shù)據(jù);因此，它不能有效地處理從非線性輸入空間采樣的數(shù)據(jù)。此外，我們不能直接對LRR的目標(biāo)函數(shù)進(jìn)行核化，這是因?yàn)楫?dāng)數(shù)據(jù)不以內(nèi)積的形式出現(xiàn)時(shí)，核技巧無法直接使用（即[x′ixj]）。

2? ? 基于核的低秩子空間聚類算法

核方法可以將數(shù)據(jù)點(diǎn)映射到高維特征空間，在該空間中可進(jìn)行線性模式分析，并與輸入數(shù)據(jù)空間中的非線性分析相對應(yīng)[6]。核方法中的常見做法不是顯式計(jì)算高維特征空間中的坐標(biāo)，而是使用“核技巧”，其中，特征映射是隱式的，特征空間中一對數(shù)據(jù)點(diǎn)之間的內(nèi)積作為核值計(jì)算。雖然，“核技巧”在計(jì)算上相對方便，但對于常用的核函數(shù)（如高斯RBF），我們并不清楚數(shù)據(jù)點(diǎn)是如何映射到特征空間的。具體地說，在子空間聚類的背景下，在隱式特征映射下，無法保證在特征空間中具有低維線性子空間結(jié)構(gòu)。

本文目標(biāo)是學(xué)習(xí)一個(gè)低秩核映射，它將數(shù)據(jù)投影到一個(gè)高維Hilbert空間，并具有線性子空間的結(jié)構(gòu)。當(dāng)Hilbert特征空間中存在線性子空間結(jié)構(gòu)時(shí)，特征映射[ΦX]應(yīng)該是低秩的。我們希望得到的Hilbert空間中的數(shù)據(jù)仍然位于多個(gè)線性子空間上，因此，也希望它具有自表示特性。優(yōu)化目標(biāo)函數(shù)可以表示為如下形式：

其中：[K=KX，X=ΦXTΦX]表示未知的核Gram矩陣;[λ]是一個(gè)平衡參數(shù)。在這里，最小化[ΦX?]使得[ΦX]是低秩的。在核方法中，通常不知道[ΦX]的顯式形式，因此，需要應(yīng)用“核技巧”。在實(shí)際應(yīng)用中，數(shù)據(jù)點(diǎn)往往含有噪聲，此時(shí)可以放寬（3）中的等式約束，使之成為目標(biāo)中的正則化項(xiàng)，即[ΦX-ΦXZ2F]。該項(xiàng)可以展開為如下形式：

上述目標(biāo)函數(shù)優(yōu)化的主要障礙在于[ΦX?]，因?yàn)樵擁?xiàng)依賴于[ΦX]。LEE等人[10]通過使用重參數(shù)化可以繞過這一障礙，從而得到特征空間中魯棒秩最小化的閉式解。由于核矩陣[K]是對稱半正定的，可以把它分解為[K=BTB]，其中，[B]是一個(gè)方陣。得到：

利用[B?]來代替[ΦX?]，則目標(biāo)函數(shù)表示如下：

其中：[ΦXTΦX=BTB];[KG]是給定的正定核矩陣。由于假設(shè)數(shù)據(jù)點(diǎn)離線性子空間不太遠(yuǎn)，因此，本文中僅利用簡單的核函數(shù)來定義[KG]，例如多項(xiàng)式核。本算法的主要思想是學(xué)習(xí)一個(gè)核矩陣[K=BTB]，即：（1）學(xué)習(xí)得到的特征映射是低秩的;（2）學(xué)習(xí)得到的核矩陣不是任意的，而是接近于一個(gè)預(yù)定義的核矩陣（如多項(xiàng)式核或高斯RBF核）;（3）特征空間中的數(shù)據(jù)點(diǎn)仍然形成一個(gè)多重線性子空間結(jié)構(gòu)，因此，其在特征空間中具有自表示特性。

3? ?目標(biāo)函數(shù)優(yōu)化

由于目標(biāo)函數(shù)中雙線性項(xiàng)的存在，上述優(yōu)化問題是非凸的。近年來，ADMM算法[7]在求解非凸問題特別是雙線性問題上得到了廣泛的應(yīng)用，本文采用ADMM算法來求解該優(yōu)化問題。

為了求解目標(biāo)函數(shù)，引入了一個(gè)輔助變量[A]，使得[A=Z]。將式（4）代入式（6），得到如下等價(jià)的優(yōu)化目標(biāo)函數(shù)：

為了利用ADMM算法求解優(yōu)化問題（7），首先給出其增廣拉格朗日方程，表示如下：

其中：[Y1∈RN×N]和[y2∈R1×N]分別是（7）中約束所對應(yīng)的拉格朗日乘子;[ρ]是拉格朗日增廣項(xiàng)的懲罰參數(shù)。

通過固定其他參數(shù)，ADMM算法利用迭代的方式來更新某一變量，更新規(guī)則如下：

（1）固定變量[A，B]，求解變量[Z]

通過求解如下子問題，可以得到[Z]的表達(dá)式：

該問題可以利用奇異閾值算子（SVT）進(jìn)行求解。SVT 算子為[DηX=UηVT]，其中：[X=UVT]為SVD分解;[ηX=sgnx];[maxabsx-η，0]為壓縮算子。

（2）固定變量[Z，B]，求解變量[A]

通過求解如下優(yōu)化問題，得到[A]的表達(dá)式：

通過對[A]求導(dǎo)并令其值為零，可以得到[A]的閉式解，表示如下：

其中：[I]是一個(gè)單位矩陣。

（3）固定變量[Z，A]，求解變量[B]

[B]通過求解如下優(yōu)化問題得到：

該優(yōu)化問題有閉式解表示如下：

4? ? 算法復(fù)雜度分析

文中，由于核矩陣[K]是對稱半正定的，因此，可以把它分解為[K=BTB]，其中[，B]是一個(gè)方陣。我們可以基于矩陣[X]的SVD分解直接得到核矩陣[K]的SVD分解。以線性核[K=XTX]為例，計(jì)算[X]的SVD分解[X=UXSXVTX]，時(shí)間復(fù)雜度為[ONDL]，其中[L=minN，D]。由于[SX]是對角陣，[S2X]以單個(gè)元素的方式很容易進(jìn)行求解，從而直接得到核矩陣[K]的SVD分解[K=UXS2XVTX]。

文中優(yōu)化算法采用迭代方式進(jìn)行求解，迭代算法的效率取決于迭代的總次數(shù)以及每次迭代的時(shí)間復(fù)雜度。優(yōu)化方法每次迭代的計(jì)算復(fù)雜度，主要開銷在于更新變量[Z]，[A]，[B]。對于更新[Z]，可通過SVD分解來進(jìn)行奇異值收縮，時(shí)間復(fù)雜度為[OrN2]，其中，[r]是迭代中SVD分解的秩;對于更新[A]，可以預(yù)先計(jì)算[λ2BTB+ρI+11T-1]的Cholesky分解，復(fù)雜度為[O12N3]，則計(jì)算[A]的復(fù)雜度為[ON2];對于[B]的計(jì)算，主要開銷在于對核矩陣的SVD分解，時(shí)間復(fù)雜度為[ONDL]。綜上分析，算法每次迭代的復(fù)雜度為[ON3+NDL]。

5? ? 實(shí)驗(yàn)

通過實(shí)驗(yàn)驗(yàn)證本文算法的有效性。對比算法采用LRR[3]、SSC[2]、LRSC[8]和KSSC[4]算法。實(shí)驗(yàn)數(shù)據(jù)集分別采用Hopkins155[9]數(shù)據(jù)集和擴(kuò)展的YaleB數(shù)據(jù)集。

5.1? 運(yùn)動(dòng)分割實(shí)驗(yàn)

Hopkins155是一個(gè)標(biāo)準(zhǔn)的運(yùn)動(dòng)分割數(shù)據(jù)集，它由155個(gè)具有2個(gè)或3個(gè)運(yùn)動(dòng)的序列組成，如圖1所示。這些序列可分為三類：室內(nèi)棋盤序列（104個(gè)序列）、室外交通序列（38個(gè)序列）和鉸接/非剛性序列（13個(gè)序列）。在仿射攝像機(jī)模型下，一個(gè)運(yùn)動(dòng)的軌跡位于一個(gè)高達(dá)3維的仿射子空間上;因此，可以采用子空間聚類方法來進(jìn)行運(yùn)動(dòng)分割。

實(shí)驗(yàn)中，本文提出的KLRR算法參數(shù)設(shè)置為：[λ1=1];[λ2=10];[λ3=1×105]。另外，使用多項(xiàng)式核[kx1，x2=xT1x2+2.23]來定義[KG]。所有算法獨(dú)立運(yùn)行10次，實(shí)驗(yàn)結(jié)果如表1所示。根據(jù)表1，所有算法都取得了很好的結(jié)果，但本文提出的算法取得了最低的聚類錯(cuò)誤率。需要指出的是：對比SSC算法和KSSC算法，KSSC算法的聚類錯(cuò)誤率要更高，這也表示并不是單純利用核方法就可以提高算法性能。本文提出的基于核的低秩表示KLRR算法，其性能要優(yōu)于傳統(tǒng)LRR算法。

5.2? 人臉聚類實(shí)驗(yàn)

如圖2所示擴(kuò)展的Yale B數(shù)據(jù)集[10]由38個(gè)人的人臉圖像組成，每個(gè)人有64張正面人臉圖像。這些圖像在不同光照條件以及固定姿勢下獲取，為了方便進(jìn)行計(jì)算，首先對圖像進(jìn)行采樣，大小為48×42;然后進(jìn)行矢量化處理，將每一張圖像變?yōu)? 016維向量。

為了充分驗(yàn)證算法的有效性，選擇不同數(shù)目的樣本類別（[K]=10、15、20、25、30、35或38）。將樣本類別從1到38進(jìn)行編號(hào)，先學(xué)習(xí)前[K]個(gè)類別，再學(xué)習(xí)后[K]個(gè)類別，直到考慮所有樣本類別。以[K]=10為例，每次實(shí)驗(yàn)選取1-10，2-11，[…]，或者29-38的樣本類別，來組成測試數(shù)據(jù)集[X∈R2? 016×640]。

實(shí)驗(yàn)中，本文提出的KLRR算法參數(shù)設(shè)置為：[λ1=1.1×103];[λ2=2×10-2];[λ3=1×105];多項(xiàng)式核[kx1，x2=xT1x2+122]。實(shí)驗(yàn)中，將數(shù)據(jù)標(biāo)準(zhǔn)化為[-1，1]，實(shí)驗(yàn)結(jié)果如表2所示。從表2可以看出，本文提出的KLRR算法聚類錯(cuò)誤率最低，取得了很好的聚類效果。

6? ? 結(jié)語

為了更好地處理非線性子空間的聚類問題，本文提出了一種新的低秩核子空間聚類算法。主要思路為：在聚類過程中通過學(xué)習(xí)得到一個(gè)低秩特征映射，以便在特征空間中獲得所需要的線性子空間結(jié)構(gòu)。對于目標(biāo)函數(shù)的優(yōu)化問題，本文給出了有效的基于ADMM算法的求解方案。在運(yùn)動(dòng)分割和人臉識(shí)別數(shù)據(jù)集上的實(shí)驗(yàn)，也驗(yàn)證了本文算法明顯優(yōu)于基于預(yù)定義核子空間聚類方法和線性子空間聚類方法，顯示了算法的有效性。在未來的研究中，將進(jìn)一步探討算法對于缺失數(shù)據(jù)的處理，以及在多視圖子空間聚類問題中的拓展應(yīng)用。

參考文獻(xiàn)：

[1] VIDAL R. Subspace clustering[J]. Signal Processing Magazine IEEE，2011，28（2）：52-68.

[2] ELHAMIFAR E，VIDAL R. Sparse subspace clustering： algorithm， theory， and applications[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence，2012，35（11）：2765-2781.

[3] LIU G，LIN Z，YAN S，et al. Robust recovery of subspace structures by low-rank representation[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence，2013，35（1）：171-184.

[4] PATEL V M，VIDAL R. Kernel sparse subspace clustering[C]// IEEE International Conference on Image Processing，2014：2849-2853.

[5] JI P，SALZMANN M，LI H. Shape interaction matrix revisited and robustified： efficient subspace clustering with corrupted and incomplete data[C]// IEEE International Conference on Computer Vision，2015：4687-4695.

[6] SHAWETAYLOR J. Kernel methods for pattern analysis[M]. Cambridge：Cambridge University Press，2004.

[7] LIN Z，CHEN M，MA Y. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices[J]. Eprint Arxiv，2010：9.DOI：10.1016/j.jsb.2012.10.010.

[8] VIDAL R，F(xiàn)AVARO P. Low rank subspace clustering （LRSC）[J]. Pattern Recognition Letters，2014，43（1）：47-61.

[9] TRON R，VIDAL R. A benchmark for the comparison of 3-D motion segmentation algorithms[C]// IEEE Conference on Computer Vision & Pattern Recognition，2007：1-8.

[10] LEE K，HO J，KRIEGMAN D J. Acquiring linear subspaces for face recognition under variable lighting[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（5）：684-698.

責(zé)任編輯? ? 盛? ? 艷