隱子空間聚類算法的改進及其增量式算法*

董 琪，王士同

江南大學 數(shù)字媒體學院，江蘇 無錫 214122

隱子空間聚類算法的改進及其增量式算法*

董 琪+，王士同

江南大學 數(shù)字媒體學院，江蘇 無錫 214122

基于稀疏表示的隱子空間聚類（latent subspace clustering，LSC）算法，相對于傳統(tǒng)的子空間聚類算法，具有更快的聚類速度，使其適用于更大的數(shù)據(jù)集，但是其存在字典訓練具有隨機性，占用內(nèi)存過多等缺陷。參照LC-KSVD字典訓練算法的思想，通過將一部分信號的標簽信息添加進字典訓練階段，以此提高了字典的判別性，進而提出了聚類精度更好的ILSC（improved LSC）算法。但相比于LSC算法，ILSC算法在字典訓練階段的耗時卻大幅增加，針對此缺陷，參照增量字典訓練的思想，提出了ILSC算法的增量式聚類算法I2LSC（incremental ILSC），在確保聚類精度、NMI（normalized mutual information）、RI（Rand index）值高于LSC且與ILSC相當?shù)耐瑫r，較之ILSC具有更快的運行速度。

子空間聚類；隱子空間聚類（LSC）；判別式字典訓練；增量式字典訓練

1 引言

聚類分析是數(shù)據(jù)挖掘、模式識別領(lǐng)域的重要內(nèi)容。隨著數(shù)據(jù)維度的增大，高維數(shù)據(jù)的聚類成為聚類分析技術(shù)的重點和難點，子空間聚類是實現(xiàn)高維數(shù)據(jù)集聚類的一種有效途徑，它是根據(jù)一簇信號集的子空間跨越情況來進行聚類的算法，是對傳統(tǒng)聚類算法的一種擴展。根據(jù)文獻[1]，子空間聚類算法可以根據(jù)實現(xiàn)方法分為4類，即基于統(tǒng)計的方法、代數(shù)的方法、迭代的方法和基于譜聚類的方法?，F(xiàn)階段最流行的算法包括：Elhamifar等人基于一維稀疏性提出的稀疏子空間聚類算法（sparse subspace clustering，SSC）[2]，Liu等人進一步利用二維稀疏性提出的基于低秩表示的子空間聚類算法（low-rank representation，LRR）[3]，F(xiàn)avaro等人提出的基于低秩表示的閉合解子空間聚類算法（closed form solutions of low-rank representation，LRR-CFS）[4]，這些算法都基于譜聚類，并擁有優(yōu)秀的聚類性能。LRR和SSC是相似的算法，都是通過構(gòu)建自表示系數(shù)矩陣來展現(xiàn)初始信號間的相關(guān)性，并利用系數(shù)矩陣構(gòu)建相似度矩陣，最后利用譜聚類算法如Ncut[5]得到最終的聚類結(jié)果。但是由于系數(shù)矩陣計算的多項式復雜度和聚類時的復雜度，限制了它們只能處理中小規(guī)模數(shù)據(jù)集。文獻[6]提出了一種基于稀疏表示的隱子空間聚類（latent subspace clustering，LSC）算法，其稀疏表示系數(shù)矩陣是通過OMP（orthogonal matching pursuit）[7]算法構(gòu)建而來，有效降低了系數(shù)矩陣計算和聚類時的復雜度。LSC算法中使用K-SVD[8]算法訓練出一個所有類共享的字典。該字典雖然具有優(yōu)秀的重構(gòu)能力，但是缺乏足夠的判別信息，導致系數(shù)矩陣表示的數(shù)據(jù)與原始信號之間存在較大的誤差，故會影響LSC算法的聚類精度。

針對以上問題，人們改進了LSC算法的字典訓練過程，Zhang等人[9]基于K-SVD算法引入監(jiān)督學習的思想，提出了一種判別式字典訓練算法D-KSVD（discriminative K-SVD），通過同時訓練字典和線性分類器，獲得了兼具重構(gòu)性和判別性的字典。同樣基于K-SVD算法，Jiang等人[10]提出了具有標簽一致性的K-SVD算法（label consistent K-SVD，LC-KSVD），在訓練字典的同時，添加了對訓練信號具有判別性的稀疏編碼誤差項，此項約束使得屬于同一類的信號具有十分相似的稀疏表示形式，從而突出了不同類別的差異性，故相比于D-SVD算法而言，LC-KSVD算法能進一步構(gòu)建出更加優(yōu)秀的字典。本文在LSC算法的基礎(chǔ)上，通過引入LC-KSVD算法來改進原字典訓練方法，以提高LSC算法的聚類精度，進而提出了聚類精度更好的改進算法ILSC（improved latent subspace clustering）。進一步地，雖然ILSC算法相對于LSC算法較好地提升了聚類精度，但在字典訓練階段的耗時也成倍增加。針對此缺陷，結(jié)合增量式字典訓練的思想，提出了ILSC算法的增量式聚類算法I2LSC（incremental improved latent subspace clustering）。它在保證聚類精度的同時，進一步提高了運行速度。

本文組織結(jié)構(gòu)如下：第2章介紹了基于稀疏表示的隱子空間聚類算法LSC；第3章介紹了LSC的改進型聚類算法ILSC；第4章介紹了ILSC的增量式聚類算法I2LSC；第5章為實驗驗證，采用聚類精度、歸一化互信息（normalized mutual information，NMI）、芮氏指標（Rand index，RI）、運行時間等來評估算法性能；第6章總結(jié)全文。

2 相關(guān)知識

2.1 稀疏表示模型

稀疏表示提供了一種高維數(shù)據(jù)在低維子空間中表示的自然模型。模型假設信號y∈?K（即樣本數(shù)據(jù)）可以表示為y?Dx，其中字典矩陣D∈?K×M，稀疏表示向量x∈?M×N。即信號y可由字典D的原子（即字典D的列向量）線性表示，此時x的求取可以轉(zhuǎn)換為如下問題的最優(yōu)化：

其中，ε為近似誤差的閾值；?0范數(shù)||c||0為稀疏表示向量x中的非零元素個數(shù)。最優(yōu)化上式的問題是NP難的，但可以通過OMP算法[7]求得稀疏表示系數(shù)的近似解，如下式：

其中，Tmax為最大稀疏度。字典D可以預先設置或由信號y訓練得到，具體參見文獻[11]。例如，通過K-SVD算法[8]求解如下最優(yōu)化問題可以得到字典D：

其中，Y∈?K×N是信號矩陣，其第i列為信號 yi；X∈?M×N是稀疏表示系數(shù)矩陣，其第i列為稀疏表示向量xi；Tmax是最大稀疏度。此時，每一個信號就可以由一些原子（即字典D的列向量）線性表示。

若使用?1范數(shù)正則化代替?0范數(shù)來加強稀疏性，x的求取就可以轉(zhuǎn)換為如下問題的最優(yōu)化：

文獻[12-13]中提供了多種針對?1范數(shù)稀疏約束的最優(yōu)化解法。

2.2 基于稀疏表示的隱子空間聚類算法

LSC算法是一種基于子空間聚類算法的改進算法，其利用系數(shù)矩陣提供的信號與原子間的關(guān)系信息來量化信號間潛在的聯(lián)系。系數(shù)矩陣中非零系數(shù)的位置確定稀疏表示時所用的原子，系數(shù)的絕對值代表相應原子在稀疏表示時的權(quán)值大小。

Fig.1 Sparse representation relation and partition result圖1 稀疏表示關(guān)系及劃分結(jié)果

圖1（a）中，4個方形代表原子，8個圓形代表信號，原子與信號之間的連線表示信號在稀疏表示后與該原子的聯(lián)系，可以根據(jù)這種潛在的聯(lián)系對頂點集合進行劃分。但在某些情況下，由于子空間的部分重疊，稀疏表示階段的誤差或噪聲等原因，導致產(chǎn)生了不可分割的組，進而無法將集合完全地分割成不相交的子集。一種可行的辦法是利用信號稀疏表示時最重要的一些原子作為特征來劃分，相應的信號與原子間不重要的一些連線將被忽略（例如圖1（b）中的虛線）。利用上述方法進行劃分的結(jié)果如圖1（b）所示，加粗的直線表示劃分結(jié)果：第一組的頂點包括{1,2,5,6,7,8,9}，第二組的頂點包括{3,4,10,11,12}。

參照圖1的方法，假定將樣本信號Y={y1,y2,…, yN}看作其中的圓形，字典中的原子D={d1,d2,…,dM}看作其中的方形，在使用OMP算法求解信號Y的稀疏編碼系數(shù)矩陣X時，一個信號yi可以由多個原子線性表示，則說明原子表示的圓形與信號表示的方形間存在一條連線，即相應信號與原子間有潛在聯(lián)系。例如：圖1（a）中的頂點6（即信號y6）與頂點1（即原子d1）和頂點2（即原子d2）間存在連線，則表示信號y6可以由原子d1、d2線性表示。信號與原子間的連線用集合E表示，此時兩個不相交的頂點集合Y與D構(gòu)成了無向圖G=(Y,D,E)，為每條連線e∈E賦予一個權(quán)值wij，則非負鄰接矩陣W={wij}的定義如下：

其中，Α=|X|（X為稀疏編碼系數(shù)矩陣）。W的結(jié)構(gòu)表明只有當原子與信號間存在稀疏表示關(guān)系時，才被賦予一個正數(shù)的權(quán)值，在原子與原子，信號與信號等其余情況中權(quán)值都為0。此時可以將信號Y的聚類問題轉(zhuǎn)化為圖G上的圖劃分問題，基于圖論的最優(yōu)劃分準則是劃分后使子圖內(nèi)部的相似度最大，子圖之間的相似度最小。

本文使用規(guī)范割集準則（normalized-cut criterion）來劃分圖，其不僅能衡量同類別樣本的相似度，同時考慮不同類別之間樣本的差異性，并在尋求最優(yōu)化分割的同時平衡每組樣本的大小。文獻[14]提供了一種求解規(guī)范割集準則問題的方法，此方法需要求解廣義特征值問題：Lz=λDz。其中L=D-W是拉普拉斯矩陣，D是對角矩陣且，稱為度矩陣，且拉普拉斯矩陣和度矩陣的定義如下：

其中，D1∈?M×M和 D2=?N×N是對角矩陣，表示第i個原子與所有信號相連邊上的權(quán)值之和，表示第 j個信號與所有原子相連邊上的權(quán)值之和。此時，等式Lz=λDz可以轉(zhuǎn)化為如下形式：

假設一個原子至少與一個信號相連（每個原子都至少在一次信號的稀疏表示中起作用），一個信號也至少與一個原子相連（每一個信號都至少由一個原子稀疏表示），故D1和D2都是非奇異的，將式（7）改寫為：

上式準確定義了矩陣An的奇異值分解（singular value decomposition，SVD）形式。其中μ和ν分別是相應的左右奇異向量，1-λ是相匹配的特征值。不同于傳統(tǒng)譜聚類算法中計算相似度矩陣的第二小特征向量（即第二個最小特征值對應的特征向量），由于式（9）中特征值的形式為1-λ，故此時應計算矩陣An的第二大特征值對應的左右奇異向量 μ和ν，μ和ν分別包含圖的最佳劃分信息和原子的特征信息。此外與傳統(tǒng)譜聚類算法相比，因為An是大小為M×N的矩陣，而傳統(tǒng)譜聚類算法中的拉普拉斯相似度矩陣的大小為(M+N)×(M+N)，所以從計算時間的角度上講，相似度矩陣An更有優(yōu)勢。

3 改進的隱子空間聚類算法ILSC

3.1 判別式字典訓練算法

字典訓練就是從數(shù)據(jù)中學習稀疏表示下的最優(yōu)表示，同時訓練初始字典使得字典中的原子特性更接近于所需表示的原始信號，以此獲得性能優(yōu)良并且規(guī)模更加緊湊的新字典。LSC算法中使用K-SVD算法構(gòu)建字典，如式（3）所示，其目標函數(shù)只包含重構(gòu)誤差項，在構(gòu)造字典的過程中具有一定的隨機性，使得訓練出的字典缺少足夠的重構(gòu)能力和判別能力。為了改進這一缺陷，本文利用訓練信號中包含的類別信息，在式（3）的基礎(chǔ)上添加了分類誤差項，其中W是分類器參數(shù)，H= [h1h2…h(huán)N]∈?m×T是信號Y的類標簽矩陣，m為類別數(shù)，hi=[0,0…1…0,0]T∈?m是對應于輸入信號yi的標簽向量，其中非零值的位置代表信號yi所屬的類別。為了進一步增強字典的判別性，又添加了判別式稀疏編碼誤差項使系數(shù)矩陣X的形式接近于判別式稀疏編碼矩陣Q，使得屬于同一類別的信號具有十分相似的稀疏表示形式，并突出不同類別信號的差異性。綜合考慮重構(gòu)誤差、判別能力以及線性分類性能這三方面因素提出如下的學習模型：

其中，α和 β是平衡因子；Q=[q1q2...qN]∈?K×T是關(guān)于信號Y的判別式稀疏編碼矩陣；是對應于信號yi∈Y的判別式稀疏編碼向量，如果信號yi和字典原子dk屬于同一類，則向量qi中相應位置為1，否則為0。例如：假設有字典D=[d1d2…d6]和信號Y=[y1y2…y6]，其中y1、y2、d1、d2屬于第一類，y3、y4、d3、d4屬于第二類，y5、y6、d5、d6屬于第三類，則矩陣Q定義如下：

每一列對應著一個信號的判別式稀疏編碼。

A是一個線性變換矩陣，采用線性變換函數(shù)g(x;A)=Ax將原始稀疏表示系數(shù)x轉(zhuǎn)換到更具判別性的稀疏特征空間RM中。為了計算方便，將式（11）改寫為如下形式：

此時式（13）與式（3）的模型是相同的，因此可以用KSVD算法求得最優(yōu)解，訓練得到字典D。

3.2 初始化參數(shù)的推導

使用K-SVD算法求解字典學習模型式（13）時，需要具備初始化的字典Dnew，即需要對參數(shù)D、A、W進行初始化，具體方法如下。

對于字典D的初始化，針對每一類別的信號用K-SVD算法訓練得到各自類別的字典，再將訓練得到的字典合并為一個完整的初始字典D0，即所有類共享的字典。

對于參數(shù)A的初始化，使用多元嶺回歸正則化模型[15]來求解其初始值，相應的目標函數(shù)如下：

其解為：

參數(shù)W的初始化與參數(shù)A類似，利用上述模型求得如下的解：

其中，參數(shù)X是在已知初始字典D0的情況下，使用K-SVD算法所求得的信號Y的稀疏表示系數(shù)矩陣。

3.3 ILSC算法的步驟

輸入：Y,m。

輸出：測試信號Y2的聚類標簽。

步驟1將信號Y分為Y1∈?K×T和Y2∈?K×N兩部分，Y1為訓練信號，帶有標簽信息，用于訓練字典，Y2為測試信號，不帶標簽信息，用于測試聚類算法，即Y1∈Y,Y2∈Y,Y1?Y2=Y。

步驟2求得訓練信號Y1的判別式稀疏編碼矩陣Q∈?M×T和類標矩陣H∈?m×T（參照2.1節(jié)）。

步驟3使用K-SVD算法求解式（13）得到字典D，其中Dnew的初始化參照3.2節(jié)。

步驟4使用OMP算法，利用字典D構(gòu)建測試信號Y2的稀疏表示矩陣C∈?M×N，使得Y?DC。

步驟5構(gòu)建矩陣A=|C|，計算度矩陣D1和D2，求得矩陣（參照2.2節(jié)）。

步驟6使用奇異值分解算法計算矩陣An的前?=[lbm]個左右奇異向量 μ2,μ3,…,μ?+1和ν2,ν3,…, ν?+1。

步驟7構(gòu)建矩陣，其中U=[μ2,μ3,…,μ?+1]，V=[ν2,ν3,…,ν?+1]。

步驟8對?維數(shù)據(jù)集Ζ進行k-means聚類，聚類標簽的最后N行是測試信號Y2的聚類結(jié)果。

在ILSC算法中，字典訓練階段需要使用部分信號的標簽信息，因此與LSC算法不同，ILSC算法需要從原始信號中抽取一部分帶標簽的信號用于訓練字典，而LSC算法則是用所有的信號去隨機地訓練一個字典。此外在字典訓練階段，ILSC算法和LSC算法雖然都是使用K-SVD算法求解字典，但Dnew相比于LSC中的D包含更多的判別信息，因此在ILSC算法中可以訓練出更具判別性的優(yōu)秀字典。與此同時，由于Dnew規(guī)模的增大，也使得字典訓練的耗時大幅增加。

4 ILSC算法的增量式聚類算法I2LSC

4.1 增量式字典訓練算法

在ILSC聚類算法中，使用LC-KSVD算法訓練字典，相比于原先的K-SVD算法，可以訓練得到判別性更好的字典，因此提高了算法的聚類精度。但是字典訓練階段的耗時也隨之大幅增加，為了改進這一問題，引入增量式字典訓練的思想來求解字典。為了保證訓練所得的字典具有足夠的判別性，同樣采用式（11）的學習模型，通過最優(yōu)化如下?1范數(shù)約束的目標函數(shù)求解字典D：

首先采用鏈式規(guī)則計算Li關(guān)于字典D的梯度得：

接著，參考文獻[16-18]，利用不動點方程的隱函數(shù)微分來構(gòu)建式（4）的不動點方程 DT(Dx-y)= -γsign(x)，并計算方程關(guān)于字典D的梯度得：

其中，Λ表示稀疏編碼系數(shù)xi中非零值的索引集合；表示系數(shù)中零值的索引集合。

最后求解Li關(guān)于D、A、W的梯度，定義輔助變量?μ,μ∈{1,2}，使得，其中。此時可以求得故Li關(guān)于字典D的梯度如下：

此外，對Li直接求解關(guān)于A和W的梯度，其結(jié)果如下：

4.2 I2LSC算法的步驟

輸入：Y,m,D1,A1,W1,ρ,n,M,μ,ν1,ν2,b。

輸出：測試信號Y2的聚類標簽。

步驟1將信號Y分為Y1∈?K×T和Y2∈?K×N兩部分，Y1為帶有標簽信息的訓練信號，用于訓練字典，Y2為不帶標簽信息的測試信號，用于聚類算法，即Y1∈Y,Y2∈Y,Y1?Y2=Y。

步驟2求得訓練信號Y1的判別式稀疏編碼矩陣Q∈?M×T和類標矩陣H∈?m×T（參照2.1節(jié)）。

步驟3增量式訓練字典D（參照3.1節(jié)）：

for i=1…n

（1）依次從信號Y1中隨機抽取一批信號，計算其對應的qi∈Q和hi∈H；

for j=1…T/b

（2）根據(jù)式（4）計算y(i)的稀疏表示xi

（3）根據(jù)xi中非零值的位置，得到索引集合Λi，并計算輔助變量?1和?2

（4）選擇學習率ρi=min(ρ,ρi0/i)

（5）通過式（20）、（21）更新參數(shù)D、A、W

D、A、W的初始化參照3.2節(jié)

步驟4其余步驟與ILSC算法相同。

在I2LSC算法中，使用與ILSC類似的字典訓練模型，但求解最優(yōu)化的方式不同，I2LSC中使用增量式算法每次讀取一小批信號來訓練字典，并用梯度下降算法更新最優(yōu)參數(shù)。梯度下降算法擁有較快的尋優(yōu)速度，因此I2LSC中的增量式字典訓練算法在保證字典判別性的同時，減少了字典訓練的耗時。

5 實驗結(jié)果與分析

實驗平臺：Intel?CoreTMi3-3240 CPU；主頻：3.40 GHz；內(nèi)存：4 GB；系統(tǒng)類型：Win7 64位操作系統(tǒng)；編程環(huán)境：Matlab R2014a（8.3.0.532）。

為了對本文算法的性能進行有效評價，本文選取如下4種指標：

（1）聚類精度（clustering accuracy assessment）[6]

（2）歸一化互信息（NMI）[19-20]

（3）芮氏指標（RI）[19-21]

（4）算法耗時

聚類精度是類別被正確標記的信號占總信號數(shù)的百分比；NMI、RI兩種指標，其取值范圍均為[0,1]，值越靠近1說明聚類效果越好，反之值越靠近0說明聚類效果越差。

5.1 實驗數(shù)據(jù)

本文采用ExtendedYale B(B+)、Scene-15、Caltech-101、手寫數(shù)字數(shù)據(jù)集MNIST等4個數(shù)據(jù)集驗證本文算法的有效性。

Extended Yale B[22]人臉庫是一個包含28個人在9種不同姿態(tài)和64種不同光照條件下共16 128張人臉圖片的數(shù)據(jù)庫，為了實驗的可操作性，將每張圖像的尺寸都調(diào)整為48×42像素大小，構(gòu)成一列信號yi∈?2016。因為對數(shù)據(jù)歸一化后可以加快梯度下降求最優(yōu)解的速度，且可能提高精度，所以用式（22）對信號yi做歸一化處理。

Caltech101[23]圖像數(shù)據(jù)集包含花、車輛、動物等101個類別共計9 146幅圖像。每類包含的圖像數(shù)目從31～800不等，圖像尺寸約為300×300像素。實驗中，將圖像庫中的圖片都轉(zhuǎn)化為灰度圖，采用稠密SIFT（scale-invariant feature transform）[24]特征提取算法進行圖像局部特征描述，提取SIFT特征的圖像塊大小為16×16像素，步長為6像素。同時基于提取的SIFT特征利用空間金字塔匹配（spatial pyramid matching，SPM）特征對其進行提取，金字塔總層數(shù)為3層，大小分別為1×1、2×2、4×4。最后采用k-means算法對空間金字塔進行聚類得到視覺編碼表，并用PCA（principal component analysis）算法將維度降至3 000維。

Scene-15[24]圖像數(shù)據(jù)集包含臥室、廚房、城市場景等15個類別共計4 485幅自然場景圖。每類包含的圖像數(shù)目從200～400不等，圖像尺寸約為250×300像素。實驗中，利用一個四層金字塔的SIFT描述子編碼本計算空間金字塔特征，并用PCA算法將維度降至3 000維。

MNIST手寫數(shù)字數(shù)據(jù)集包含10類共計70 000個手寫數(shù)字的圖像樣本，樣本維數(shù)為784。同樣對MNIST數(shù)據(jù)集用式（22）做歸一化處理。

5.2 實驗設置

為了驗證本文算法的有效性，對SSC算法、LRR算法、LSC算法、ILSC算法及I2LSC算法在聚類精度、NMI值、RI值三方面的表現(xiàn)進行比較。同時為了進一步說明I2LSC算法相較于ILSC算法在運行時間上的優(yōu)勢，對比LSC、ILSC、I2LSC算法完整的運行時間，這3種算法在聚類階段的步驟完全一致，同時也對3種算法在字典學習階段的耗時進行比較。

在聚類精度、NMI值、RI值的對比實驗中，對數(shù)據(jù)集Extended Yale B和Scene-15，為了保證實驗的隨機性，實驗中隨機選取m=2…8類，即m個尺度劃分，每個類別選取T=60個信號構(gòu)成包含T×m列的訓練數(shù)據(jù)集，用于字典訓練，剩余的信號構(gòu)成測試數(shù)據(jù)集，用于測試聚類精度、NMI、RI值。對數(shù)據(jù)集Caltech101，由于其每類包含的信號數(shù)從31～800不等，為了保證足夠的信號數(shù)，需要從信號數(shù)足夠的類別中抽取信號，其余同上。參考文獻[6]，當測試信號數(shù)與字典大小的比率N/M＞10時，LSC聚類算法可以獲得較好的聚類效果，故字典的大小M設置如表1所示。

Table 1 Dictionary sizeMcorresponding to different scales m表1 不同劃分尺度m對應的字典大小M

在增量式字典訓練中，學習率ρ取0.01，迭代次數(shù)n取20，平衡系數(shù) μ取0.6，ν1、ν2取10-6。增量式字典訓練算法的步驟3中，每批數(shù)據(jù)塊的大小為總訓練信號數(shù)的10%，即b=T×10%。平衡因子的取值也可以由用戶根據(jù)實際樣本進行調(diào)整，但必須在經(jīng)驗值范圍內(nèi)取值。計算以上5種算法在各個數(shù)據(jù)集上的聚類精度、NMI和RI的均值以及標準差，其中均值反映了算法的平均聚類性能，標準差反映了算法的穩(wěn)定魯棒性。

在算法耗時的對比實驗中，對Extended Yale B、 Caltech101、Scene15數(shù)據(jù)集，劃分尺度m取8，每個劃分尺度中訓練信號的個數(shù)T取100。對MNIST數(shù)據(jù)集，m取6，T取5 000。其余同上。最后統(tǒng)計3種聚類算法的整體耗時情況和聚類算法在字典訓練階段的耗時。以上所有實驗均重復40次，并且每次隨機選取不同的樣本集合。

5.3 實驗結(jié)果

各算法在3個數(shù)據(jù)集Extended Yale B、Scene-15、Caltech101上的聚類精度、NMI、RI值如表2～表10所示。其中最優(yōu)均值都已用黑體標出。對比各表的實驗結(jié)果可以發(fā)現(xiàn)，隨著劃分尺度的增大，即類別m的增大，5種聚類算法SSC、LRR、LSC、ILSC、I2LSC的聚類精度、NMI、RI值在大多數(shù)情況下都逐漸下降，并且以SSC、LRR、LSC算法下降幅度最大，而ILSC和I2LSC算法的下降速度都較慢。這是因為判別式字典的訓練過程中使用到訓練信號的標簽信息，當類別數(shù)增加時，相應類別的標簽信息也會被添加進字典訓練階段。因此，在類別數(shù)增大時，相比于SSC、LRR、LSC算法，ILSC和I2LSC算法具有更穩(wěn)定的聚類精度、NMI、RI值。此外，在所有聚類精度、NMI、RI值的對比實驗中，ILSC和I2LSC算法的聚類精度、NMI、RI值均遠優(yōu)于LSC算法，在某些情況下具備良好的魯棒性，且在大多數(shù)情況下，I2LSC算法的聚類精度、NMI、RI值均優(yōu)于ILSC算法。以上說明也驗證了由于在字典訓練階段合理使用了部分標簽信息，使得訓練得到的字典更具判別性，進而使信號稀疏表示的結(jié)果更加準確，最終提升了算法的聚類精度、NMI、RI值。

Table 2 Clustering accuracy assessment of 5 clustering algorithms on Extended Yale B dataset表2 5種聚類算法在Extended Yale B數(shù)據(jù)集上的聚類精度

Table 3 NMI of 5 clustering algorithms on Extended Yale B dataset表3 5種聚類算法在Extended Yale B數(shù)據(jù)集上的NMI值

Table 4 RI of 5 clustering algorithms on Extended Yale B dataset表4 5種聚類算法在Extended Yale B數(shù)據(jù)集上的RI值

Table 5 Clustering accuracy assessment of 5 clustering algorithms on Caltech101 dataset表5 5種聚類算法在Caltech101數(shù)據(jù)集上的聚類精度

Table 6 NMI of 5 clustering algorithms on Caltech101 dataset表6 5種聚類算法在Caltech101數(shù)據(jù)集上的NMI值

Table 7 RI of 5 clustering algorithms on Caltech101 dataset表7 5種聚類算法在Caltech101數(shù)據(jù)集上的RI值

在不同數(shù)據(jù)集上，LSC、ILSC、I2LSC聚類算法的整體耗時及算法在字典訓練階段的耗時情況如表11和表12所示。

Table 8 Clustering accuracy assessment of 5 clustering algorithms on Scene-15 dataset表8 5種聚類算法在Scene-15數(shù)據(jù)集上的聚類精度

Table 9 NMI of 5 clustering algorithms on Scene-15 dataset表9 5種聚類算法在Scene-15數(shù)據(jù)集上的NMI值

Table 10 RI of 5 clustering algorithms on Scene-15 dataset表10 5種聚類算法在Scene-15數(shù)據(jù)集上的RI值

Table 11 Elapse of 3 algorithms in dictionary training phase表11 3種算法在字典訓練階段的耗時 s

Table 12 Elapse of 3 algorithms in entire clustering phase表12 3種算法完整的耗時 s

對比3種聚類算法LSC、ILSC、I2LSC在不同數(shù)據(jù)集上訓練字典所需的時間，參照表11可以看出LSC算法最快，ILSC算法最慢。這是因為LSC和ILSC算法最優(yōu)化求解字典的方式類似。但由于ILSC算法在求解字典的過程中除了原有的重構(gòu)誤差項外，還添加了分類誤差項和稀疏編碼誤差項，使得初始字典Dnew的規(guī)模遠大于LSC算法中的初始字典D，致使最優(yōu)化時的耗時大幅增加。此外，I2LSC算法在字典訓練階段的耗時遠低于ILSC算法，只比LSC算法的耗時多一點，這也驗證了之前的猜測，同等規(guī)模下使用梯度下降方式最優(yōu)化的速度遠快于使用K-SVD算法進行最優(yōu)化。同時，對比表5和表6可以看出，在Extended Yale B、Caltech101、Scene15這些小樣本數(shù)據(jù)集上，字典訓練階段的耗時基本等同于聚類算法的完整耗時；在MNIST這樣的大樣本數(shù)據(jù)集上，字典訓練階段的耗時也占聚類算法完整耗時的80%左右。因此，減少字典訓練階段的耗時對提高聚類算法的整體運行效率有顯著效果。

綜合以上所有實驗可以看出，ILSC算法相比于LSC算法擁有更優(yōu)的聚類精度，更進一步，I2LSC算法在擁有優(yōu)秀聚類精度的前提下還能保證較快的運行速度。

6 結(jié)束語

基于稀疏表示的隱子空間聚類算法LSC由于字典訓練算法過于簡單，導致訓練得到的字典缺少足夠的表示能力和判別能力，影響到數(shù)據(jù)的稀疏表示，進而降低了算法的聚類精度。針對以上問題，本文改進其字典訓練方法，利用已有的樣本類別信息，從多尺度字典中訓練得到具有優(yōu)秀重構(gòu)性和判別性的過完備字典，提出了ILSC算法。此外，為了提高字典訓練算法的效率，改進了字典訓練模型的最優(yōu)化過程，提出了增量式判別字典訓練算法，使得ILSC算法的增量式算法I2LSC在擁有優(yōu)秀聚類精度的同時，具有較好的運行速度。

目前，ILSC和I2LSC算法仍存在一些不足，以上實驗中字典的大小是根據(jù)經(jīng)驗設定的，一般來說字典中原子數(shù)目越多其包含的信息也越多，對聚類精度的影響也越大，但字典過大會導致冗余，并且會大幅增加字典訓練階段的耗時。另外，在驗證增量式字典訓練算法的實驗中，每批數(shù)據(jù)塊大小被設定為10%，數(shù)據(jù)塊的大小對每次訓練樣本包含的特征信息量以及算法的迭代次數(shù)都有影響，最終將影響算法的運行時間和訓練所得字典的判別性。因此，如何科學有效地設定字典大小和數(shù)據(jù)塊大小將是下一步的研究方向。

[1]Vidal R.Subspace clustering[J].IEEE Signal Processing Magazine,2011,28(2):52-68.

[2]Elhamifar E,Vidal R.Sparse subspace clustering[C]//Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition,Miami,USA,Jun 20-25,2009. Piscataway,USA:IEEE,2009:2790-2797.

[3]Liu Guangcan,Lin Zhouchen,Yu Yong.Robust subspace segmentation by low-rank representation[C]//Proceedings of the 27th International Conference on Machine Learning, Haifa,Israel,Jun 21-24,2010.Red Hook,USA:Curran Associates,2014:663-670.

[4]Favaro P,Vidal R,Ravichandran A.A closed form solution to robust subspace estimation and clustering[C]//Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition,Colorado Springs,USA,Jun 20-25,2011. Washington:IEEE Computer Society,2011:1801-1807.

[5]Shi J,Malik J.Normalized cuts and image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2000,22(8):888-905.

[6]Adler A,Elad M,Hel-Or Y.Fast subspace clustering via sparse representations[R].Department of Computer Science, Technion,Tech,2011.

[7]Pati Y C,Rezaiifar R,Krishnaprasad P S.Orthogonal matching pursuit:recursive function approximation with applications to wavelet decomposition[C]//Proceedings of the 27th Asilomar Conference on Signals,Systems and Computers,Pacific Grove,USA,Nov 1-3,1993.Piscataway,USA:IEEE, 1993:40-44.

[8]Aharon M,Elad M,Bruckstein A.K-SVD:an algorithm for designing overcomplete dictionaries for sparse representation[J].IEEE Transactions on Signal Processing,2006,54 (11):4311-4322.

[9]Zhang Qiang,Li Baoxin.Discriminative K-SVD for dictionary learning in face recognition[C]//Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition,San Francisco,USA,Jun 13-18,2010.Piscataway,USA:IEEE,2010:2691-2698.

[10]Jiang Zhuolin,Lin Zhe,Davis L S.Learning a discriminative dictionary for sparse coding via label consistent K-SVD [C]//Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition,Colorado Springs,USA, Jun 20-25,2011.Washington:IEEE Computer Society,2011: 1697-1704.

[11]Rubinstein R,Bruckstein A M,Elad M.Dictionaries for sparse representation modeling[J].Proceedings of the IEEE,2010,98(6):1045-1057.

[12]Lee H,Battle A,Raina R,et al.Efficient sparse coding algorithms[C]//Proceedings of the 20th Annual Conference on Neural Information Processing Systems,Vancouver,Canada, Dec 4-7,2006.Red Hook,USA:Curran Associates,2012: 801-808.

[13]Gregor K,Lecun Y.Learning fast approximations of sparse coding[C]//Proceedings of the 27th International Conference on Machine Learning,Haifa,Israel,Jun 21-24,2010. Red Hook,USA:CurranAssociates,2014:399-406.

[14]Dhillon I S.Co-clustering documents and words using bipartite spectral graph partitioning[C]//Proceedings of the 7th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,San Francisco,USA, Aug 26-29,2001.New York:ACM,2001:269-274.

[15]Golub G H,Hansen P C,O'Leary D P.Tikhonov regularization and total least squares[J].SIAM Journal on Matrix Analysis andApplications,1999,21(1):185-194.

[16]Bagnell J A,Bradley D M.Differentiable sparse coding[C]// Proceedings of the 22nd Annual Conference on Neural Information Processing Systems,Vancouver,Canada,Dec 8-10,2008.Red Hook,USA:CurranAssociates,2009:113-120.

[17]Mairal J,Bach F,Ponce J.Task-driven dictionary learning[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(4):791-804.

[18]Yang Jianchao,Yu Kai,Huang T.Supervised translation invariant sparse coding[C]//Proceedings of the 2010 IEEE Conference on Computer Vision and Pattern Recognition, San Francisco,USA,Jun 13-18,2010.Piscataway,USA: IEEE,2010:3517-3524.

[19]Liu Jun,Mohammed J,Carter J,et al.Distance-based clustering of CGH data[J].Bioinformatics,2006,22(16):1971-1978.

[20]Deng Zhaohong,Choi K S,Chung F L,et al.Enhanced soft subspace clustering integrating within-cluster and betweencluster information[J].Pattern Recognition,2010,43(3): 767-781.

[21]Rand W M.Objective criteria for the evaluation of clustering methods[J].Journal of the American Statistical Association, 1971,66(336):846-850.

[22]Georghiades A S,Belhumeur P N,Kriegman D J.From few to many:illumination cone models for face recognition under variable lighting and pose[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2001,23(6):643-660.

[23]Li Feifei,Fergus R,Perona P.Learning generative visual models from few training examples:an incremental Bayesian approach tested on 101 object categories[J].Computer Vision and Image Understanding,2007,106(1):59-70.

[24]Lazebnik S,Schmid C,Ponce J.Beyond bags of features: spatial pyramid matching for recognizing natural scene categories[C]//Proceedings of the 2006 IEEE Conference on Computer Vision and Pattern Recognition,New York,Jun 17-22,2006.Washington:IEEE Computer Society,2006: 2169-2178.

DONG Qi was born in 1990.He is an M.S.candidate at School of Digital Media,Jiangnan University.His research interests include artificial intelligence,pattern recognition,dictionary learning and subspace clustering algorithm.

董琪（1990—），男，江南大學數(shù)字媒體學院碩士研究生，主要研究領(lǐng)域為人工智能，模式識別，字典學習，子空間聚類算法。

WANG Shitong was born in 1964.He is a professor at School of Digital Media,Jiangnan University.His research interests include artificial intelligence,pattern recognition and bioinformatics.

王士同（1964—），男，江南大學數(shù)字媒體學院教授，主要研究領(lǐng)域為人工智能，模式識別，生物信息。

Improved Latent Subspace ClusteringAlgorithm and Its Incremental Version*

DONG Qi+,WANG Shitong
School of Digital Media,Jiangnan University,Wuxi,Jiangsu 214122,China

+Corresponding author:E-mail:dq_nyr@163.com

DONG Qi,WANG Shitong.Improved latent subspace clustering algorithm and its incremental version.Journal of Frontiers of Computer Science and Technology,2017,11(5)：802-813.

Compared with the traditional subspace clustering algorithms,the latent subspace clustering(LSC)algorithm based on sparse representation has faster clustering speed,thereby it can be applied into larger data sets.However it still has two shortcomings.One is the randomness and slowness in dictionary training phase and the other is its occupying too much memory.On the basis of the LC-KSVD algorithm,this paper proposes the ILSC(improved LSC)algorithm to obtain its enhanced clustering accuracy by adding some labels into the dictionary training phase to improve its discrimination.However,compared with the LSC algorithm,ILSC algorithm consumes more time in dictionary training phase.In order to circumvent this drawback,based on the idea of incremental training,this paper develops the I2LSC(incremental ILSC)algorithm to achieve comparable clustering performance to ILSC algorithm in the sense of clustering accuracy,NMI(normalized mutual information)and RI(Rand index),but faster speed than ILSC.

subspace clustering;latent subspace clustering(LSC);discriminant dictionary training;incremental dictionary training

10.3778/j.issn.1673-9418.1601005

A

TP391

*The National Natural Science Foundation of China under Grant No.61170122(國家自然科學基金);the New Century Excellent Talent Foundation from MOE of China under Grant No.NCET-12-0882(教育部新世紀優(yōu)秀人才支持計劃).

Received 2016-01,Accepted 2016-03.

CNKI網(wǎng)絡優(yōu)先出版:2016-03-07,http://www.cnki.net/kcms/detail/11.5602.TP.20160307.1710.018.html