融入無監(jiān)督度量學習的稀疏子空間聚類模型

江雨燕,邵 金,李 平

1(安徽工業(yè)大學 管理科學與工程學院,安徽 馬鞍山 243032) 2(南京郵電大學 計算機學院,南京 210023)

1 引 言

子空間聚類是目前實現(xiàn)高維數(shù)據(jù)聚類的有效方法之一,涉及到運動分割[1]、圖像識別[2]等各方面應用,如在一個視頻序列中可能會包含多個運動對象,通過多個子空間將描述不同對象的運動過程.近年來,已有許多子空間聚類算法被提出,現(xiàn)有方法包括:代數(shù)方法[3]、迭代方法[4]、統(tǒng)計方法[5]、譜聚類方法[6,7].子空間聚類的主要思想是將高維數(shù)據(jù)通過多個低維子空間表達,在子空間的并集中選擇一組數(shù)據(jù)對其進行分割、聚類.但是,類別劃分并不明確的特征空間對聚類任務無太大幫助,甚至是負作用[8],這凸顯了數(shù)據(jù)預處理的重要性.

基于低秩表示的子空間聚類[9-11]揭示了數(shù)據(jù)的相關結構,尋找每個數(shù)據(jù)的低秩表示,通過低秩表示恢復子空間結構,但缺點是當獲得數(shù)據(jù)不足或數(shù)據(jù)損壞時性能會明顯降低.稀疏子空間聚類(Sparse Subspace Clustering,SSC)[12]一定程度上保證存在損壞數(shù)據(jù)時正常進行子空間恢復,但缺乏對數(shù)據(jù)全局結構的描述,僅考慮每個數(shù)據(jù)的稀疏表示.文獻[13]將對抗性或隨機噪聲添加到無標簽的數(shù)據(jù)中,學習到噪聲字典后正確識別底層子空間.文獻[14,15]針對數(shù)據(jù)缺失問題優(yōu)化模型,通過計算稀疏系數(shù)矩陣恢復數(shù)據(jù)的缺失項.這些方法的優(yōu)點是有效解決缺失項的稀疏表示問題,但當數(shù)據(jù)維度很高時尋找稀疏表示或低秩表示的計算是非常困難的.這些文獻研究重點在低秩或稀疏約束下考慮子空間聚類的數(shù)據(jù)缺失、噪聲等問題.然而,缺點是大多采用主成分分析(Principal Component Analysis,PCA)[16]、局部線性嵌入(Local Linear Embedding,LLE)[17]等方法作為一個單獨的聚類前的預處理步驟,這些經(jīng)典的無監(jiān)督方法對數(shù)據(jù)采集質(zhì)量要求低,無需數(shù)據(jù)的標簽,能夠降低數(shù)據(jù)維度.但是,這些方法僅能尋找數(shù)據(jù)之間的相似關系,不能對數(shù)據(jù)聚類起到關鍵作用.因此,數(shù)據(jù)預處理方法也是影響聚類性能的關鍵因素.

對輸入樣本的預處理,現(xiàn)有的子空間聚類模型往往使用優(yōu)秀的特征選擇方法[18]選擇感興趣的特征作為輸入特征,并大多使用歐氏距離來度量樣本之間的相似性,不完全適用于子空間分割過程.目前在度量學習方面,相關研究主要側(cè)重于有監(jiān)督的度量學習,但此類度量學習方法通常無法直接應用于無監(jiān)督(未觀測到樣本的類別信息的)子空間聚類任務中.文獻[19]提出面向聚類的自適應度量學習,對輸入數(shù)據(jù)同時進行降維和聚類,使數(shù)據(jù)可分性最大化,可以有效對高維數(shù)據(jù)進行聚類.文獻[20]將近鄰成分分析擴展到無監(jiān)督場景,對無標簽數(shù)據(jù)點同時進行聚類和距離度量學習.基于上述分析,可以使用度量學習方法將數(shù)據(jù)間的相似性最大化,同時為了能夠提升子空間聚類模型的性能,必須對樣本間的距離度量進行詳細的設計與驗證.

因此,本文提出了一種融入無監(jiān)督度量學習的稀疏子空間聚類模型(Unsupervised Metric Learning for Sparse Subspace Clustering,UML-SSC).將度量學習與子空間聚類集成在一個統(tǒng)一優(yōu)化框架中,而不再是聚類前的一個單獨的步驟,數(shù)據(jù)結構的先驗可以通過對類別指標的正則化嵌入到子空間聚類模型中.實驗結果表明,模型通過針對化的預處理得以提升子空間聚類能力.

本文的主要貢獻如下:

1)將無監(jiān)督度量學習引入作為數(shù)據(jù)預處理過程,生成偽類標簽指導后續(xù)子空間聚類工作,提升原始數(shù)據(jù)的可分性.

2)重構了稀疏子空間聚類模型,將度量學習融入到子空間聚類中,對于數(shù)據(jù)的預處理不再是一個單獨的步驟.

3)為解決所提出優(yōu)化模型,更新了迭代優(yōu)化過程.

2 相關工作

2.1 度量學習

假設輸入X=[x1,x2,…,xN]∈D×N,其中N為輸入數(shù)據(jù)的數(shù)目,D為輸入數(shù)據(jù)的維度,大多度量學習方法使用馬氏距離進行度量,一般來說,馬氏距離的度量表現(xiàn)優(yōu)于歐氏距離的度量.

(1)

(2)

其中,d(xi,xj)是表示兩點之間的馬氏距離,為了確保滿足非負性和三角不等式的度量,其中M必須是半正定的[21]且M=ATA,M≥0.因為本文主要研究的是正交變換,即ATA=Il,其中Il是大小為l的單位矩陣.對線性變換后的數(shù)據(jù)進行歐氏距離的計算等于在輸入空間進行馬氏距離的計算,這表明了度量學習和數(shù)據(jù)投影問題被視為一個統(tǒng)一的概念[22,23].

2.2 稀疏子空間聚類

(3)

其中,Z的第i列對應的是X的第i個稀疏解,diag(Z)=0是為了避免數(shù)據(jù)點對自身用線性組合表示的平凡解,上式的解Z是塊對角結構,塊的個數(shù)代表子空間的個數(shù),塊的大小代表子空間的維度.令W=|Z|+|Z|T,其中W為數(shù)據(jù)的相似度矩陣,最終使用譜聚類中Ncut或Ratio Cut方法得到聚類結果[24].

3 算法及提出的模型

3.1 無監(jiān)督度量學習

令A∈D×l作為初始投影矩陣,通過矩陣A對輸入數(shù)據(jù)進行線性變換,即yi=ATxi,從D維空間中轉(zhuǎn)換到l維空間中.在無監(jiān)督模型中,由于沒有任何標簽信息指導我們模型的學習過程,使用K-means方法初始化K個聚類中心[25],給予輸入點偽標簽,然后通過最小化目標函數(shù)J對輸入數(shù)據(jù)點進行進一步優(yōu)化A.

(4)

其中C=[c1,c2,…,cK]指的是在新投影空間中的K類的中心,yi=ATxi,A∈D×l是投影矩陣.這里引入表示數(shù)據(jù)點標簽的聚類指示矩陣H,H=[H1,H2,…,HK],令hij為聚類指示向量,如式(5)所示:

(5)

再定義一個加權聚類指示矩陣F,F=[F1,F2,…,FK],如下[26]:

(6)

其中,Fi表示F的第i列,Ni表示F中第i列的值.當yi對應的項是非零項時,則表示yi是屬于該偽標簽中的數(shù)據(jù)點,對目標函數(shù)J最小化問題則可以轉(zhuǎn)化為式(7):

(7)

然而,由于該優(yōu)化問題是非線性并且很難求解的,使用交替最小化方法(Alternating Minimization,AM)計算.

1)固定F,優(yōu)化A:當F是已知的情況下,通過拉格朗日乘子法解決式(7)中的優(yōu)化問題,對于F中的每一列,優(yōu)化問題可以轉(zhuǎn)化為廣義特征值問題.

PA=ηA

(8)

其中η為拉格朗日乘子(在這里也是特征值),且P=XXT-FTXTXF,根據(jù)特征值計算出A,從而更新A.

2)固定A,優(yōu)化F:C是在新投影空間中對數(shù)據(jù)點進行K-Means算法計算后的偽類別中心,加權指示向量F與數(shù)據(jù)點的偽類別中心C直接相關,根據(jù)固定的A,直接計算出F.

3.2 提出的模型

首先采用無監(jiān)督度量學習對原始數(shù)據(jù)進行預處理,給予數(shù)據(jù)偽類標簽以指導后續(xù)工作,再將譜聚類損失、度量損失加入到模型中,我們的目標函數(shù)如式(9)所示:

(9)

其中,X為N個輸入數(shù)據(jù)點,X=[X1,X2,…,XN].A為投影矩陣,M=ATA.F∈N×K為加權聚類指示矩陣,F=[F1,F2,…,FK],其中K是對數(shù)據(jù)點進行分類的類別數(shù)量,L為拉普拉斯矩陣,L=R-W,R為對角矩陣,Rii=∑Wij,W為相似度矩陣,W=|Z|T+|Z|.

目標函數(shù)的第1項在投影空間的自表示模型的損失,第2項是譜聚類的非負正交約束,第3項是稀疏表示的約束,第4項是投影空間上的度量損失.α是非負權衡的參數(shù),λ是平衡稀疏解的參數(shù).約束項ATA=I是為了得到防止得到平凡解;約束項diag(Z)=0要求數(shù)據(jù)不能使用線性組合表示自身;約束項ZT1=1要求數(shù)據(jù)分布在仿射子空間上;約束FTF=I是必須對F進行非負正交的約束.因此,式(9)可以重寫為式(10):

(10)

UML-SSC模型的核心思想是在保證局部數(shù)據(jù)幾何結構不變的前提下先將數(shù)據(jù)在低維流形空間中通過度量學習將數(shù)據(jù)可分性最大化;然后將預處理后的數(shù)據(jù)在稀疏約束下進行自表達并執(zhí)行子空間選擇過程,通過改進模型使預處理不再是單獨的步驟,然后迭代地更新稀疏表示矩陣Z,加權偽類標簽矩陣F,投影矩陣A,隨著迭代次數(shù)增加,獲得的結果會更加精確.

3.3 優(yōu)化與算法

1)固定A、F,更新Z

去掉不相關的項,優(yōu)化目標函數(shù)可以轉(zhuǎn)化為式(11):

(11)

引入拉格朗日乘子η,刪去上式等式約束,則有:

(12)

根據(jù)文獻[27],將X替換為[XT,η×1]T,其中η是一個接近無窮的量,則式(12)可以更新為式(13):

(13)

同時,這里引入定理1結論重構該優(yōu)化問題.

定理1.對于拉普拉斯矩陣L∈N×N,其加權類標簽矩陣為F∈N×K,存在:

由于A是固定的,Y=AX根據(jù)輸入數(shù)據(jù)點X而改變.根據(jù)定理1的結論,式(13)可以改寫為:

(14)

上式可以使用迭代的方式求解,固定Z除了第i行以外的所有行,僅對第i行進行求解:

(15)

(16)

(17)

其中zk、vk、pk指的是z、v、p中第k個元素.

2)固定Z、A,更新F去掉不相關的項,優(yōu)化問題可以轉(zhuǎn)化為:

(18)

對上式中加入拉格朗日乘子Φ,同時消去上式等式、不等式約束,則轉(zhuǎn)化為:

(19)

(20)

根據(jù)Karush-Kuhn-Tucker(KKT)條件[29]ΦijFij=0,計算得到下式以更新F.

(22)

3)固定Z、F,更新A去掉不相關的項,優(yōu)化問題為:

(23)

求解式(23)最小化問題,對A進行求導:

(24)

由于上式?jīng)]有閉合解,令求導后的梯度為Q.

Q=2(XTAX-XTAXZ-ZTXTAX+ZTXTAXZ)
+2(XTAX-FTXTAXF)+4δA(ATA-I)

(25)

根據(jù)梯度Q利用隨機梯度下降法進行迭代,直至目標函數(shù)收斂.

A(t+1)=A(t)-ξQ

(26)

其中ξ為學習率,取值范圍為ξ∈{10-1,…,10-4},A(t)指的是第t次迭代的值.

通過固定二者,更新另一者,交替地更新A,F,Z,直到目標函數(shù)收斂.設置最大迭代次數(shù)iter為100次,每迭代1次,都獲得更有判別能力的投影矩陣A、更優(yōu)的加權類標簽矩陣F、更優(yōu)的稀疏系數(shù)矩陣Z.根據(jù)得到的最終結果構建相似度矩陣進行譜聚類,最終得到聚類結果,算法流程見算法1.

算法1.UML-SSC

輸入:數(shù)據(jù)矩陣X=[X1,X2,…,XN]∈D;超參數(shù)α,λ.學習率ξ

輸出:數(shù)據(jù)X的所屬類別

1.初始化投影矩陣A,FandZ

2.根據(jù)式(8)、式(9)計算出投影矩陣A,偽類別矩陣F;

3.For循環(huán)iter=1,2,….

4.固定A和F,更新Z通過式(17);

5.固定A和Z,更新F通過式(22);

6.固定F和Z,更新A通過式(26);

7.直到目標函數(shù)收斂;

8.End for

9.構建相似度矩陣W=|Z|T+|Z|;

10.使用譜聚類得到聚類結果.

4 實 驗

4.1 實驗設置

在本節(jié)中,為驗證所提出模型的有效性,我們選取兩個公開真實的標準數(shù)據(jù)集:The Extend YaleB數(shù)據(jù)集、COIL-20數(shù)據(jù)集,具體描述見表1.

表1 實驗中兩個數(shù)據(jù)集的描述Tabel 1 Descriptions of two datasets

1)The Extend YaleB數(shù)據(jù)集是38個人正面人臉圖像,每一個人在不同光照下的64張圖像.原始的每張人臉圖像分辨率為192×168,根據(jù)文獻[12]的實驗設置,將圖像降至48×42像素,為保證實驗精確性,選取前m1={5,10,20,30,38}個對象進行聚類.

2)COIL-20是20個物體的1440副灰度圖像構成,物體包括鴨子玩具、汽車模型等,每副圖像的像素大小為32×32,擁有1024個特征.為更好地分析實驗精確性,選取前m2={5,10,15,20}個對象進行聚類.

在以上數(shù)據(jù)集中將我們的算法與以下幾種先進的聚類算法進行對比:局部子空間分析[30](Local Subspace Analysis,LSA),曲率譜聚類[31](Spectral Curvature Clustering,SCC),最小二乘回歸[32](Least Squares Regression,LSR),低秩表示[11](Low Rank Representation,LRR),低秩子空間聚類[33](Low Rank Subspace Clustering,LRSC),SSC[12],基于正交追蹤的稀疏子空間聚類[34](SSC by Orthogonal Matching Pursuit,SSC-OMP),l0稀疏子空間聚類[35](l0Sparse Su-bspace Clustering,l0-SSC).

算法中涉及到的輸入?yún)?shù)包括α,λ,設置取值范圍α∈{10-6,10-5,…,105,106},λ∈{10-6,10-5,…,105,106},令超參數(shù)δ=106,γ=106,K根據(jù)不同數(shù)據(jù)集實驗目標數(shù)設置.由于實驗結果對參數(shù)值非常敏感,在不同數(shù)據(jù)集中根據(jù)實驗結果調(diào)整相對應合適的參數(shù)值.

4.2 時間復雜度分析

由于提出的模型更新包括3個子步驟,需要通過對每個子步驟的復雜度進行分析來計算模型的總時間復雜度,假設迭代次數(shù)為t.更新投影矩陣A,由于d

4.3 實驗結果

為了評估所提出模型的性能,與幾類常見聚類算法進行對比,均使用作者提供的代碼進行測試,并將參數(shù)設置到最優(yōu)的聚類性能.實驗報告了包括UML-SSC在內(nèi)的9種算法在不同數(shù)據(jù)集中不同數(shù)量的對象的聚類性能,如表2～表5所示,并分別以ACC和NMI對不同算法進行評價,對比結果如圖1、圖2所示.由于所選取的參數(shù)不同,其ACC、NMI值會有變化,因此需要分析不同參數(shù)下不同的聚類結果,以直觀地看出最佳參數(shù)選擇,如圖3、圖4所示.實驗結果均為重復20次實驗的均值.

表2 9種算法在Extend YaleB數(shù)據(jù)集上的ACC值Table 2 ACC of nine algorithms on Extend YaleB

表3 9種算法在COIL-20數(shù)據(jù)集上的ACC值Table 3 ACC of nine algorithms on COIL-20

表4 9種算法在Extend YaleB數(shù)據(jù)集上的NMI值Table 4 NMI of nine algorithms on Extend YaleB

表5 9種算法在COIL-20數(shù)據(jù)集上的NMI值Table 5 NMI of nine algorithms on COIL-20

圖1 不同算法在兩個數(shù)據(jù)集上的ACC對比Fig.1 ACC of different algorithms on two data sets

圖2 不同算法在兩個數(shù)據(jù)集上的NMI對比Fig.2 NMI of different algorithms on two data sets

由于算法的聚類結果對參數(shù)很敏感,聚類性能很大程度取決于參數(shù)組合.這里將不同的參數(shù)α,λ的實驗結果進行記錄并展示.通過對圖3的分析,我們的方法在Extend YaleB數(shù)據(jù)集中設置α=10-6,λ=106可以得到較好的聚類表現(xiàn),其ACC達到82.2%.在COIL-20數(shù)據(jù)集上設置α=106,λ=106,其聚類準確率ACC達到最高值89.3%.從圖4中可以看出在Extend YaleB數(shù)據(jù)集中取值α∈{10-3,10-6},λ∈{103,106}時NMI值普遍較高,在α=10-6,λ=106時NMI達到最高值85.8%.不同的數(shù)據(jù)集需要不同的參數(shù)組合才能達到最佳性能,在COIL-20數(shù)據(jù)集上設置α=106,λ=106時,NMI得到最優(yōu)值95.0%.

圖3 UML-SSC算法在不同數(shù)據(jù)集上不同參數(shù)的ACC值Fig 3 ACC values of different parameters of UML-SSC on different data sets

圖4 UML-SSC算法在不同數(shù)據(jù)集上不同參數(shù)的NMI值Fig.4 NMI values of different parameters of UML-SSC on different data sets

5 結束語

本文主要研究了將度量學習融入到子空間聚類過程,重構了稀疏子空間聚類模型.為了克服子空間聚類模型精度提升受限、大多使用傳統(tǒng)PCA方法進行預處理等問題,針對輸入數(shù)據(jù)的預處理進行詳細設計.本文優(yōu)點如下:1.通過使用無監(jiān)督度量學習的方法可以在保留局部數(shù)據(jù)結構的情況下,自適應地學習數(shù)據(jù)間的相似度將數(shù)據(jù)的可分性最大化;2.將稀疏子空間聚類與度量學習結合,提出聯(lián)合框架模型同時執(zhí)行子空間選擇與聚類,將度量學習與子空間聚類過程融合.通過迭代求解的方式,學習到更精確的數(shù)據(jù)分布及更優(yōu)的相似度矩陣,實驗證明模型有效提高了子空間聚類效果,提升了泛化能力.

雖然提出的模型提升了聚類的準確率,但仍然存在改進的空間.例如,可以考慮加入深度神經(jīng)網(wǎng)絡來處理非線性高維數(shù)據(jù),未來將進一步進行研究.