董 琪，王士同

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

隱子空間聚類(lèi)算法的改進(jìn)及其增量式算法*

董 琪+，王士同

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

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

子空間聚類(lèi)；隱子空間聚類(lèi)（LSC）；判別式字典訓(xùn)練；增量式字典訓(xùn)練

1 引言

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

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

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

2 相關(guān)知識(shí)

2.1 稀疏表示模型

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

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

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

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

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

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

2.2 基于稀疏表示的隱子空間聚類(lèi)算法

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

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

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

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

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

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

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

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

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

3 改進(jìn)的隱子空間聚類(lèi)算法ILSC

3.1 判別式字典訓(xùn)練算法

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

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

每一列對(duì)應(yīng)著一個(gè)信號(hào)的判別式稀疏編碼。

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

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

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

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

對(duì)于字典D的初始化，針對(duì)每一類(lèi)別的信號(hào)用K-SVD算法訓(xùn)練得到各自類(lèi)別的字典，再將訓(xùn)練得到的字典合并為一個(gè)完整的初始字典D0，即所有類(lèi)共享的字典。

對(duì)于參數(shù)A的初始化，使用多元嶺回歸正則化模型[15]來(lái)求解其初始值，相應(yīng)的目標(biāo)函數(shù)如下：

其解為：

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

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

3.3 ILSC算法的步驟

輸入：Y,m。

輸出：測(cè)試信號(hào)Y2的聚類(lèi)標(biāo)簽。

步驟1將信號(hào)Y分為Y1∈?K×T和Y2∈?K×N兩部分，Y1為訓(xùn)練信號(hào)，帶有標(biāo)簽信息，用于訓(xùn)練字典，Y2為測(cè)試信號(hào)，不帶標(biāo)簽信息，用于測(cè)試聚類(lèi)算法，即Y1∈Y,Y2∈Y,Y1?Y2=Y。

步驟2求得訓(xùn)練信號(hào)Y1的判別式稀疏編碼矩陣Q∈?M×T和類(lèi)標(biāo)矩陣H∈?m×T（參照2.1節(jié)）。

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

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

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

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

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

步驟8對(duì)?維數(shù)據(jù)集Ζ進(jìn)行k-means聚類(lèi)，聚類(lèi)標(biāo)簽的最后N行是測(cè)試信號(hào)Y2的聚類(lèi)結(jié)果。

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

4 ILSC算法的增量式聚類(lèi)算法I2LSC

4.1 增量式字典訓(xùn)練算法

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

首先采用鏈?zhǔn)揭?guī)則計(jì)算Li關(guān)于字典D的梯度得：

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

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

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

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

4.2 I2LSC算法的步驟

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

輸出：測(cè)試信號(hào)Y2的聚類(lèi)標(biāo)簽。

步驟1將信號(hào)Y分為Y1∈?K×T和Y2∈?K×N兩部分，Y1為帶有標(biāo)簽信息的訓(xùn)練信號(hào)，用于訓(xùn)練字典，Y2為不帶標(biāo)簽信息的測(cè)試信號(hào)，用于聚類(lèi)算法，即Y1∈Y,Y2∈Y,Y1?Y2=Y。

步驟2求得訓(xùn)練信號(hào)Y1的判別式稀疏編碼矩陣Q∈?M×T和類(lèi)標(biāo)矩陣H∈?m×T（參照2.1節(jié)）。

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

for i=1…n

（1）依次從信號(hào)Y1中隨機(jī)抽取一批信號(hào)，計(jì)算其對(duì)應(yīng)的qi∈Q和hi∈H；

for j=1…T/b

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

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

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

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

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

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

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

5 實(shí)驗(yàn)結(jié)果與分析

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

為了對(duì)本文算法的性能進(jìn)行有效評(píng)價(jià)，本文選取如下4種指標(biāo)：

（1）聚類(lèi)精度（clustering accuracy assessment）[6]

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

（3）芮氏指標(biāo)（RI）[19-21]

（4）算法耗時(shí)

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

5.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

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

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

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

5.2 實(shí)驗(yàn)設(shè)置

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

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

Table 1 Dictionary sizeMcorresponding to different scales m表1 不同劃分尺度m對(duì)應(yīng)的字典大小M

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

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

5.3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

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

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

Table 11 Elapse of 3 algorithms in dictionary training phase表11 3種算法在字典訓(xùn)練階段的耗時(shí) s

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

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

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

6 結(jié)束語(yǔ)

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

目前，ILSC和I2LSC算法仍存在一些不足，以上實(shí)驗(yàn)中字典的大小是根據(jù)經(jīng)驗(yàn)設(shè)定的，一般來(lái)說(shuō)字典中原子數(shù)目越多其包含的信息也越多，對(duì)聚類(lèi)精度的影響也越大，但字典過(guò)大會(huì)導(dǎo)致冗余，并且會(huì)大幅增加字典訓(xùn)練階段的耗時(shí)。另外，在驗(yàn)證增量式字典訓(xùn)練算法的實(shí)驗(yàn)中，每批數(shù)據(jù)塊大小被設(shè)定為10%，數(shù)據(jù)塊的大小對(duì)每次訓(xùn)練樣本包含的特征信息量以及算法的迭代次數(shù)都有影響，最終將影響算法的運(yùn)行時(shí)間和訓(xùn)練所得字典的判別性。因此，如何科學(xué)有效地設(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—），男，江南大學(xué)數(shù)字媒體學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)槿斯ぶ悄埽Ｊ阶R(shí)別，字典學(xué)習(xí)，子空間聚類(lèi)算法。

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—），男，江南大學(xué)數(shù)字媒體學(xué)院教授，主要研究領(lǐng)域?yàn)槿斯ぶ悄?，模式識(shí)別，生物信息。

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(國(guó)家自然科學(xué)基金);the New Century Excellent Talent Foundation from MOE of China under Grant No.NCET-12-0882(教育部新世紀(jì)優(yōu)秀人才支持計(jì)劃).

Received 2016-01,Accepted 2016-03.

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