荊雪純，趙 鵬，崔志華

(太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024)

E-mail：cuizhihua@tyust.edu.cn

1 引 言

聚類作為一種重要的無(wú)監(jiān)督學(xué)習(xí)算法，被廣泛應(yīng)用于不同領(lǐng)域，例如聲學(xué)場(chǎng)景[1-3]，物聯(lián)網(wǎng)場(chǎng)景[4， 5]，云計(jì)算[6]和智能優(yōu)化算法[7-9].隨著數(shù)據(jù)復(fù)雜性的增加，傳統(tǒng)的聚類方法已不能滿足需求，因此針對(duì)高維數(shù)據(jù)的子空間聚類算法應(yīng)運(yùn)而生[10， 11].事實(shí)上，高維數(shù)據(jù)是低維線性子空間的并集.子空間聚類算法的實(shí)質(zhì)是找到低維線性子空間結(jié)構(gòu)，并將同一子空間中的數(shù)據(jù)點(diǎn)歸為一類.如今，子空間聚類算法已在許多領(lǐng)域得到廣泛的應(yīng)用，例如機(jī)器學(xué)習(xí)[12]，計(jì)算機(jī)視覺(jué)[13]，圖像處理[14， 15]和系統(tǒng)識(shí)別[16， 17].子空間聚類算法大約包括五類：矩陣分解方法[18， 19]，代數(shù)方法[20-22]，迭代方法[23， 24]，統(tǒng)計(jì)方法[25]和譜聚類方法[26-28].

基于譜聚類的子空間聚類算法可以根據(jù)樣本之間的關(guān)系獲取表示系數(shù)矩陣，然后將矩陣傳入譜聚類獲得聚類結(jié)果.但是，對(duì)于構(gòu)建表示系數(shù)矩陣，數(shù)據(jù)規(guī)模是一個(gè)非常重要的影響因素，算法的時(shí)間復(fù)雜度隨著數(shù)據(jù)規(guī)模的增長(zhǎng)呈指數(shù)增長(zhǎng).因此，不少研究人員開(kāi)始研究基于抽樣的聚類算法.雖然采樣降低了時(shí)間成本，但是聚簇質(zhì)量也不可避免隨之降低.

為了解決這個(gè)問(wèn)題，我們提出了一個(gè)基于信息傳遞的稀疏子空間聚類(SSC)算法框架[29].在此框架中，抽取樣本的表示系數(shù)通過(guò)傳統(tǒng)方法計(jì)算獲得，其余數(shù)據(jù)的系數(shù)通過(guò)已知信息的傳遞獲得.該框架的最大優(yōu)點(diǎn)是靈活且通用，一是它抽取樣本時(shí)可以采用不同的抽樣方法，本文采用隨機(jī)抽樣和K-means聚類抽樣.二是該方法在提高經(jīng)典算法SSC效率的同時(shí)，還可以應(yīng)用于其他子空間聚類算法.這種新的子空間聚類方法不僅減少了時(shí)間，而且在一定程度上保證了聚類質(zhì)量.總體而言，這項(xiàng)工作的主要貢獻(xiàn)包括以下3個(gè)方面：

1)為了提高SSC算法的效率，本文提出了一個(gè)基于抽樣的子空間聚類算法框架，該框架靈活可擴(kuò)展.它不僅可以選擇不同的采樣方法，而且可以擴(kuò)展到其他子空間聚類算法.

2)本文提出了一種信息傳遞機(jī)制并應(yīng)用于算法框架中.在計(jì)算表示系數(shù)矩陣的過(guò)程中，首先計(jì)算抽取樣本表示系數(shù)，其余系數(shù)通過(guò)信息傳遞的方式得到.在保證聚類精度的前提下，它降低了時(shí)間成本.

3)本算法框架在兩個(gè)數(shù)據(jù)集上進(jìn)行試驗(yàn)驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，與其他算法相比，本算法時(shí)間成本低，聚類質(zhì)量高.

本文的結(jié)構(gòu)如下.相關(guān)工作在第二節(jié)中介紹.第三節(jié)詳細(xì)介紹了稀疏子空間聚類算法.在第四節(jié)中，我們提出了一個(gè)基于信息傳遞的聚類算法框架.其中我們定義了信息傳遞以及介紹了其如何被應(yīng)用于框架中.在第五節(jié)中，本文方法的有效性被驗(yàn)證.最后第六節(jié)總結(jié)本文.

2 相關(guān)工作

在譜聚類中，需要一個(gè)相似度矩陣才可獲得聚類結(jié)果，而一個(gè)相似度矩陣就對(duì)應(yīng)一個(gè)鄰接圖.在圖中，一個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)數(shù)據(jù)點(diǎn)，兩個(gè)數(shù)據(jù)點(diǎn)之間的關(guān)系表示為一條邊，邊的權(quán)重與兩個(gè)數(shù)據(jù)點(diǎn)的相似度呈正相關(guān).因此，譜聚類的關(guān)鍵在于構(gòu)建一個(gè)好的鄰接圖.

構(gòu)建鄰接圖的傳統(tǒng)方法是利用成對(duì)距離.其中任意兩個(gè)數(shù)據(jù)點(diǎn)的相似度都是通過(guò)歐氏距離來(lái)計(jì)算的，包括拉普拉斯特征圖[30]，局部線性嵌入(LLE)[31]，K近鄰(K-NN)[32]等.但是，成對(duì)距離過(guò)于關(guān)注局部結(jié)構(gòu)而忽略了整體結(jié)構(gòu)，因此受噪聲的影響很大.與成對(duì)距離不同，表示系數(shù)將每個(gè)數(shù)據(jù)點(diǎn)作為其他數(shù)據(jù)點(diǎn)的線性表示.為了獲得更好的聚類結(jié)果，學(xué)者基于不同的正則化項(xiàng)提出了不同的算法.例如，稀疏子空間聚類(SSC)[29]，低秩表示(LRR)[33]，低秩稀疏子空間聚類(LRSSC)[34]等.

盡管表示系數(shù)與成對(duì)距離相比具有更好的有效性，但是面對(duì)大規(guī)模數(shù)據(jù)時(shí)，需要逐個(gè)計(jì)算每個(gè)數(shù)據(jù)點(diǎn)和其他數(shù)據(jù)點(diǎn)之間的關(guān)系系數(shù)，時(shí)間成本將會(huì)很高.以n個(gè)數(shù)據(jù)點(diǎn)為例，算法時(shí)間復(fù)雜度為O(mn3)，其中m代表數(shù)據(jù)維度.因此，ShenJie等人[35]提出對(duì)大規(guī)模問(wèn)題進(jìn)行隨機(jī)優(yōu)化.但是由于抽樣數(shù)目小，該方法的性能較差.與此不同的是，PengXi等人[36]隨機(jī)選擇小部分的數(shù)據(jù)點(diǎn)并定義為樣本內(nèi)數(shù)據(jù)，其余數(shù)據(jù)點(diǎn)被視為樣本外數(shù)據(jù).他們采用SSC將樣本內(nèi)數(shù)據(jù)聚類，并將樣本外數(shù)據(jù)分類到最近的進(jìn)行歸類.然后，他們開(kāi)發(fā)了3種算法：可伸縮稀疏子空間聚類(SSSC)，可伸縮低秩表示子空間聚類(SLRR)和可伸縮最小二乘回歸子空間聚類(SLSR).但是，樣本外數(shù)據(jù)分類時(shí)不是基于整個(gè)數(shù)據(jù)的本質(zhì)特征，因此對(duì)噪聲更敏感.為了解決這個(gè)問(wèn)題，Libo等人[37]提出了一種新穎的在線LRR子空間學(xué)習(xí)方法.該方法包括兩個(gè)階段：第1階段是先計(jì)算一小部分的數(shù)據(jù)點(diǎn)的子空間結(jié)構(gòu)，稱為靜態(tài)學(xué)習(xí).第2步是計(jì)算整個(gè)數(shù)據(jù)集的內(nèi)部關(guān)鍵組成部分.但是，當(dāng)數(shù)據(jù)點(diǎn)不足時(shí)，LRR模型可能會(huì)失效，那么在靜態(tài)學(xué)習(xí)時(shí)如果選擇數(shù)據(jù)點(diǎn)太少就無(wú)法產(chǎn)生可靠的結(jié)果.

為了解決這些問(wèn)題，我們提出了一個(gè)基于信息傳遞的稀疏子空間聚類算法框架.在此框架中，需要采用兩階段方法來(lái)構(gòu)建表示系數(shù)矩陣.首先，我們抽取出一部分?jǐn)?shù)據(jù)點(diǎn)利用傳統(tǒng)方式計(jì)算得到其表示系數(shù).在第2階段，表示系數(shù)矩陣的剩余數(shù)值通過(guò)信息傳遞完成，信息傳遞依賴于第1階段的已知信息.與PengXi等人[36]的子空間聚類算法相比，該方法抓住了整個(gè)數(shù)據(jù)的特征.另外，信息傳遞的思想可以擴(kuò)展到其他子空間聚類算法.

3 稀疏子空間聚類算法

譜聚類需要一個(gè)相似度矩陣才可獲得聚類結(jié)果.因此，基于譜聚類的子空間聚類算法的關(guān)鍵是如何構(gòu)造表示系數(shù)矩陣，表示系數(shù)矩陣將直接決定相似度矩陣.

稀疏表示(SR)是構(gòu)造表示系數(shù)矩陣最流行的方法之一.近年來(lái)，SR成為某些領(lǐng)域研究的重點(diǎn).SR的目的是有效表示數(shù)據(jù)并且通過(guò)特定空間中數(shù)據(jù)的稀疏性來(lái)挖掘數(shù)據(jù)的本質(zhì)特征.稀疏性是指數(shù)據(jù)可被視作其他數(shù)據(jù)的線性組合，要求包括盡可能少的非零系數(shù).因此，SR可以表征數(shù)據(jù)的子空間特征.

假設(shè)給定一個(gè)數(shù)據(jù)集X∈RD×n是K個(gè)子空間的并集{S}Ki=1，其中D表示數(shù)據(jù)的維數(shù)，n表示數(shù)據(jù)的數(shù)量.X的每一列代表一個(gè)數(shù)據(jù)點(diǎn)，每個(gè)子空間i包含ni個(gè)數(shù)據(jù)點(diǎn)，即∑ki=1ni=n.稀疏子空間聚類的理念是每一個(gè)數(shù)據(jù)點(diǎn)都可以由同一子空間中其他數(shù)據(jù)點(diǎn)線性表示：

xi=∑j≠izijxj

(1)

其中xi表示第i個(gè)數(shù)據(jù)點(diǎn).zij表示第i個(gè)數(shù)據(jù)點(diǎn)和第j個(gè)數(shù)據(jù)點(diǎn)之間的表示系數(shù)，表示系數(shù)反映的是它們的相似度.

對(duì)于公式(1)的計(jì)算過(guò)程，矩陣表示為公式(2)：

X=XZ

(2)

其中Z∈Rn×n是表示系數(shù)矩陣，當(dāng)xi和xj不在同一子空間時(shí)zij=0，不同于一組基或字典，公式(2)的含義是用自己本身來(lái)表示數(shù)據(jù)，因此也叫做自表示矩陣.如果已知子空間結(jié)構(gòu)并按分類順序依次排列數(shù)據(jù)，表示系數(shù)矩陣Z在理想狀態(tài)下將具有塊對(duì)角結(jié)構(gòu)，如公式(3)所示：

Z=Z10…0
0Z2…0
????
00…Zk

(3)

其中Zα(α=1，…，K)是子空間Sα的表示系數(shù)矩陣.矩陣的塊對(duì)角結(jié)構(gòu)揭示了數(shù)據(jù)的子空間結(jié)構(gòu).而稀疏子空間聚類的目的正是利用不同的正則化約束項(xiàng)在公式(2)的基礎(chǔ)上使表示系數(shù)矩陣達(dá)到理想的結(jié)構(gòu)，之后通過(guò)W=(|Z|+|ZT|)/2將表示系數(shù)矩陣轉(zhuǎn)化為相似度矩陣，最終通過(guò)譜聚類得到聚類結(jié)果.

為了提高聚類精度，通常增加正則化項(xiàng)來(lái)改善表示系數(shù)矩陣的結(jié)構(gòu).因此，Elhamifar提出了基于向量稀疏的稀疏子空間聚類算法.該算法利用公式(4)來(lái)計(jì)算數(shù)據(jù)點(diǎn)之間的相似度，得到表示系數(shù)矩陣：

minz‖Z‖1,s.t.X=XZ,diag(Z)=0

(4)

稀疏子空間聚類算法對(duì)于高維數(shù)據(jù)是一種非常有效的算法.然而，隨著數(shù)據(jù)的數(shù)量和維數(shù)的增加，構(gòu)造表示系數(shù)矩陣的時(shí)間復(fù)雜度也急劇增加.因此，本文我們利用信息傳遞技術(shù)，提出了一種基于采樣的新型聚類框架來(lái)構(gòu)建表示系數(shù)矩陣.

4 基于信息傳遞的子空間聚類算法框架

4.1 信息傳遞

一個(gè)關(guān)系網(wǎng)絡(luò)中包括不同的頂點(diǎn)以及他們的關(guān)系.在一個(gè)不完整的關(guān)系網(wǎng)絡(luò)中，如何計(jì)算兩個(gè)頂點(diǎn)之間的未知關(guān)系是一個(gè)難點(diǎn).因此，我們提出信息傳遞理論，信息傳遞可以通過(guò)中介點(diǎn)獲得未知的關(guān)系.兩個(gè)頂點(diǎn)的中介點(diǎn)的定義如定義1所示.利用信息傳遞計(jì)算未知關(guān)系的方法如定理1所示.

定義1. 假設(shè)頂點(diǎn)A與頂點(diǎn)B、C直接相關(guān)，并已知A與B和A與C的關(guān)系，則A被稱為B和C之間的中介點(diǎn).

定理1. 假設(shè)xi和xj的關(guān)系是未知的，并且在xi和xj之間存在η個(gè)中介點(diǎn){xk,k=1,2,…,η}，則zij可由公式(5)計(jì)算得到.

zij=∑ηk=1zikW×zkj

(5)

W=∑ηk=1zik

(6)

其中zij表示xi和xj的關(guān)系.同樣的，zki和zkj也代表兩點(diǎn)之間的關(guān)系.W是樣本xi與所有中介點(diǎn)之間的關(guān)系之和(如公式(6)所示).因此，zik/W表示xi到xj所有路徑中選擇包含第k個(gè)中介點(diǎn)路徑的概率.因此，zik/W×zkj表示選擇包含第k個(gè)中介點(diǎn)路徑時(shí)xi和xj之間的關(guān)系.

4.2 信息傳遞的應(yīng)用

在基于抽樣的子空間聚類算法中，一些數(shù)據(jù)點(diǎn)會(huì)被率先抽取出來(lái).因此，從n個(gè)數(shù)據(jù)點(diǎn)中選擇η個(gè)樣本點(diǎn)是首要任務(wù).然后可以通過(guò)傳統(tǒng)方式即公式(7)獲得部分系數(shù)矩陣Zelite∈Rn×1.需要強(qiáng)調(diào)的是，這種傳統(tǒng)計(jì)算方式的本質(zhì)是依次計(jì)算每個(gè)數(shù)據(jù)點(diǎn)與其他數(shù)據(jù)點(diǎn)之間的關(guān)系作為矩陣的一列.因此，公式(4)與公式(7)等價(jià).

由表1中數(shù)據(jù)可知，“煙氣中溶水性固體氣溶膠的排放量”是“煙氣中非溶水性固體氣溶膠的排放量（PM）”的75倍以上，此表的計(jì)算數(shù)據(jù)可以說(shuō)明，解決濕法煙氣脫硫工藝形成的氣溶膠問(wèn)題遠(yuǎn)比將燃煤煙氣中的含塵排放標(biāo)準(zhǔn)從50mg/Nm3降到10mg/Nm3更為重要，由于氣溶膠是“霧霾”的凝結(jié)核，因此，濕法煙氣脫硫產(chǎn)生的氣溶膠對(duì)“霧霾”的影響不可低估。但由于污染物監(jiān)測(cè)技術(shù)的局限和粉塵監(jiān)測(cè)位置僅在電除塵出口，使對(duì)煙囪出口煙氣氣溶膠的監(jiān)控出現(xiàn)盲區(qū)，隨意排放而失去控制。由于燃煤超凈排放采用的技術(shù)未考慮上述情況，即使采用濕式電除塵器，顯然也不能徹底解決該問(wèn)題[2]。

minzi‖Zi‖1,s.t.xi=XZi,zi(i)=0

(7)

其中Zi∈Rn×1表示Z的第i列，xi是第i個(gè)數(shù)據(jù)點(diǎn)，zi(i)表示Zi的第i個(gè)系數(shù).

與矩陣Z不同，Zelite只包含樣本點(diǎn)與其他所有數(shù)據(jù)點(diǎn)之間的關(guān)系，因此Zelite不是方陣，它對(duì)應(yīng)的是一個(gè)不完整的關(guān)系圖.但是，譜聚類需要一個(gè)完整的關(guān)系圖，該圖與系數(shù)矩陣Z相對(duì)應(yīng).因此需要計(jì)算圖中未知關(guān)系所對(duì)應(yīng)的表示系數(shù).這些缺失的表示系數(shù)是剩余數(shù)據(jù)點(diǎn)之間的關(guān)系.此時(shí)需采用定理1來(lái)解決問(wèn)題.

根據(jù)定理1，還需已知剩余數(shù)據(jù)點(diǎn)與樣本點(diǎn)之間的關(guān)系，用Znon-elite∈Rη×(n-η)表示，其每一列為剩余數(shù)據(jù)點(diǎn)和樣本點(diǎn)之間的表示系數(shù).Znon-elite同樣可以由公式(7)得到.

為了更加清晰地描述表示系數(shù)矩陣的計(jì)算過(guò)程，我們以圖1為例說(shuō)明.

圖1 信息傳遞圖Fig.1 A diagram of information transfer

圖1中有五個(gè)數(shù)據(jù)點(diǎn)，包括三個(gè)樣本點(diǎn)(實(shí)心)和兩個(gè)剩余數(shù)據(jù)點(diǎn)(空心).首先，Zelite，Znon-elite由傳統(tǒng)方式計(jì)算，即z25，z35，z45，z12，z13和z14被計(jì)算得出.根據(jù)定理1，z15=∑4k=2z1k/(z12+z13+z14)×zk5.從矩陣的角度來(lái)看，z15是將Zelite的第5行(歸一化后)與Znon-elite相乘得到.因此，將歸一化的Zelite和Znon-elite相乘則可計(jì)算得到缺失的部分系數(shù)矩陣Z′.Z′的每一列代表剩余數(shù)據(jù)點(diǎn)與剩余數(shù)據(jù)點(diǎn)之間的表示系數(shù).最后，Z矩陣由Zelite和Z′拼接而成.

4.3 整體結(jié)構(gòu)

圖2展示了基于信息傳遞的子空間聚類的基本框架.首先，通過(guò)一些采樣策略選擇出樣本點(diǎn)，如圖中步驟(a)所示.接下來(lái)，在步驟(b)和步驟(c)中，通過(guò)公式(7)獲得Zelite和Znon-elite.步驟(d)是將歸一化的Zelite和Znon-elite相乘得到Z′.最后，(e)將矩陣Zelite和Z′拼接后作為表示系數(shù)矩陣Z.Z將被傳入譜聚類算法得到最終聚類結(jié)構(gòu).其中步驟(f)的目的是將矩陣Z對(duì)稱化.

圖2 基于信息傳遞的子空間聚類框架Fig.2 Framework based on information transfer for subspace clustering

可以看出，新算法與傳統(tǒng)的算法的主要區(qū)別在于減少了計(jì)算量.計(jì)算Z矩陣一列的時(shí)間復(fù)雜度為O(n).因此，傳統(tǒng)方法的時(shí)間復(fù)雜度為O(n2).但是，新算法的時(shí)間復(fù)雜度僅為O(n×η+η×(n-η))，這是計(jì)算Zelite和Zmon-elite的時(shí)間復(fù)雜度之和.而O(n2)總是高于O(n×η+η×(n-η))，證明過(guò)程如公式(8)所示.因此，當(dāng)面對(duì)大規(guī)模數(shù)據(jù)時(shí)，所提出的方法更加有效.

=n2-2nη+η2=(n-η)2>0s.t.y

(8)

算法1為所提框架的偽代碼.其中K,ε,λ是需要傳入的參數(shù).K表示要聚類的類別數(shù).ε表示剪枝的閾值.λ表示樣本點(diǎn)所占整個(gè)數(shù)據(jù)的比例，即η=n×λ.首先，數(shù)據(jù)將被分為兩類：樣本點(diǎn)和剩余數(shù)據(jù)點(diǎn).在此框架中，樣本點(diǎn)的采樣方式是靈活的，這也是算法框架靈活性的體現(xiàn).在本文中，我們以K-means抽樣和隨機(jī)抽樣為例進(jìn)行實(shí)驗(yàn).接下來(lái)，由公式(7)獲得Zelite和Znon-elite.步驟8-10是根據(jù)定理1將Znon-elite歸一化，而Z是由步驟11-12獲得的.為了提高聚類質(zhì)量，將低于閾值的表示系數(shù)置為0，即剪枝操作，如步驟13-15所示.最終的聚類結(jié)果在步驟11-13中得到.

算法1.基于信息傳遞的子空間聚類算法

輸入：數(shù)據(jù)X∈RD×n，K，ε，λ∈[0，1]

1.初始化0矩陣Zelite∈RD×n，Znon-elite∈Rη×(n-η)，Z∈Rn×n

2.η=n×λ， 利用抽樣策略進(jìn)行抽樣，生成一個(gè)長(zhǎng)度為η，包含所抽樣本的編號(hào)的列表

3.Forcol=1：η：

4.X[：,L[col]]，作為xi被用于公式(7)計(jì)算得到Zelite[：,col]

5.N=[1,2,3,…,n],non=N-L

6. Forcol=1∶n-η：

7.X[：,non[col]]作為xi被用于公式(7)計(jì)算得到Znon-elite[：,col]

8.Forrow=1∶η：

9. Forcol=1∶n-η：

10.Znon-elite[row,col]=

Znon-elite[row,col]/sum(Znon-elite[row,：])

11.Z′=Zelite×Znon-elite

12.Zelite和Z′拼接得到Z

13. Forrow=1：n：

14. Forcol=1：n：

15.Z[row,col]=0 ifZ[row,col]<ε

16.W=1/2(Z+ZT),W和K傳到譜聚類中得到聚類結(jié)果

輸出：聚類結(jié)果

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

5.1 數(shù)據(jù)集和評(píng)價(jià)指標(biāo)

在實(shí)驗(yàn)中，我們使用兩個(gè)數(shù)據(jù)集COIL-20，YaleBCrop025來(lái)表明算法的有效性.COIL-20包含20個(gè)物體72個(gè)不同角度的圖片，其像素大小統(tǒng)一控制為128×128.因此，COIL-20共有1440張圖片.而YaleBCrop025是一個(gè)人臉數(shù)據(jù)集，包括38個(gè)人在不同照明條件和不同姿勢(shì)下的照片，每個(gè)人64張照片，整個(gè)數(shù)據(jù)集共有2432張圖片.表1展示了數(shù)據(jù)集的具體說(shuō)明.

表1 數(shù)據(jù)集的數(shù)值說(shuō)明Table 1 Numerical statement of the datasets

為了評(píng)估效果，采用聚類準(zhǔn)確度(ACC)[38]，歸一化互信息(NMI)[39]和時(shí)間(TIME)作為評(píng)價(jià)指標(biāo).聚類質(zhì)量正是通過(guò)ACC和NMI來(lái)體現(xiàn)的，他們都是通過(guò)比較聚類結(jié)果和真實(shí)標(biāo)簽得到的結(jié)果.它們的范圍是從0到1，越接近1，算法性能越好.同時(shí)，TIME表示程序的執(zhí)行時(shí)間，執(zhí)行時(shí)間越短，算法越高效.

5.2 參數(shù)的影響

在本文提出的算法1中，需要預(yù)先確定超參數(shù)ε和λ. 為了得到更好的聚類效果，我們首先測(cè)試了不同的ε和λ對(duì)聚類的影響，選擇最佳效果對(duì)應(yīng)的參數(shù)值用于后續(xù)實(shí)驗(yàn).

在確定ε的實(shí)驗(yàn)中，隨機(jī)抽取YaleBCrop025中2類數(shù)據(jù)為數(shù)據(jù)集，測(cè)試了ε的6個(gè)不同值.同時(shí)，為了降低λ的影響，將λ設(shè)置為1.也就是說(shuō)，沒(méi)有采樣操作，所有數(shù)據(jù)均按照傳統(tǒng)稀疏子空間聚類進(jìn)行聚類，這么做的原因是采樣與否對(duì)表示系數(shù)矩陣的剪枝閾值并沒(méi)有影響.不同的ε得到的ACC和NMI如圖3所示.很顯然，當(dāng)ε=10-1時(shí)，算法具有最佳性能.因此，在后續(xù)實(shí)驗(yàn)中均采用ε=10-1.

另一方面，采樣率λ對(duì)聚類質(zhì)量和計(jì)算時(shí)間中都有著重要影響.根據(jù)格里文科定理，λ太低將無(wú)法達(dá)到優(yōu)秀的聚類質(zhì)量.因?yàn)闃颖玖亢苄o(wú)法確保采樣數(shù)據(jù)與其余數(shù)據(jù)具有相同的分布.相反，如果λ設(shè)置得太高，該算法將會(huì)失去采樣的意義，退化為傳統(tǒng)的子空間聚類算法，效率依舊無(wú)法提高.因此，λ∈[0，0.5]是一個(gè)合適的區(qū)間，該實(shí)驗(yàn)測(cè)試λ在這個(gè)區(qū)間范圍內(nèi)的變化.所使用得數(shù)據(jù)集與測(cè)試ε的實(shí)驗(yàn)數(shù)據(jù)相同.實(shí)驗(yàn)結(jié)果如圖4所示.很明顯，計(jì)算時(shí)間和聚類質(zhì)量隨著λ的增大而提高.最終我們確定λ的值為0.4，以平衡時(shí)間成本和聚類質(zhì)量.

圖3 參數(shù)ε對(duì)聚類質(zhì)量的影響Fig.3 Iimpact of ε on clustering qualities

圖4 參數(shù)λ對(duì)聚類質(zhì)量的影響Fig.4 Impact of λ on clustering qualities

5.3 不同采樣方法的對(duì)比實(shí)驗(yàn)

該算法的第一步就是從整個(gè)數(shù)據(jù)中挑選出樣本點(diǎn).在所提框架中，采樣方法不受限制，但不同的采樣方法會(huì)對(duì)聚類質(zhì)量有不同程度的影響.在這項(xiàng)工作中，我們選擇兩種抽樣方法K-means抽樣和隨機(jī)抽樣進(jìn)行測(cè)試.K-means抽樣就是將聚類后的聚類中心抽取出來(lái).K-means是一種基礎(chǔ)的聚類算法，其主要特征是簡(jiǎn)單，運(yùn)算速度快.但是，K-means不適合用于直接圖片這種高維數(shù)據(jù)，但可以將其用作預(yù)聚類方式以獲得聚類中心，將聚類中心抽取出來(lái)作為樣本點(diǎn).因此，K-means可以成為獲取樣本點(diǎn)的一種采樣方法.而隨機(jī)抽樣是隨機(jī)選擇η個(gè)數(shù)據(jù)作為樣本點(diǎn).

我們從COIL-20中隨機(jī)選擇了不同數(shù)量的類別，每類均包括72張圖片.在這項(xiàng)工作中，由于譜聚類和采樣方法具有隨機(jī)性，每個(gè)實(shí)驗(yàn)都進(jìn)行10次重復(fù)試驗(yàn).表2列出了ACC的平均值(mean)，中位數(shù)(median)，標(biāo)準(zhǔn)方差(std)和最優(yōu)值(optimum).平均值，中位數(shù)和最優(yōu)值從不同的角度反映算法的性能，而標(biāo)準(zhǔn)方差可以反映算法的穩(wěn)定性.表3為NMI的結(jié)果.不同采樣方法的計(jì)算花費(fèi)如表4所示.

分析實(shí)驗(yàn)結(jié)果可以得出以下結(jié)論：

1)從結(jié)果中可看出所提算法的聚類質(zhì)量，ACC和NMI，均優(yōu)于SSC算法.因此，無(wú)論采用哪種抽樣方式，所提算法均比傳統(tǒng)SSC有更好的效果.不可否認(rèn)，有時(shí)由于隨機(jī)性，SSC-Random比SSC-K-means具有更好的效果.例如，如表2所示，當(dāng)類別為15時(shí)，SSC-K-means的均值，中值，標(biāo)準(zhǔn)差均優(yōu)于SSC-Random，但SSC-random的最佳值66.20優(yōu)卻于SSC-K-means，這正是由于隨機(jī)性導(dǎo)致的結(jié)果.另外，當(dāng)類別數(shù)較少時(shí)，隨機(jī)抽樣的表現(xiàn)也會(huì)更好.隨著類別數(shù)的增加，性能會(huì)變差.因此，在對(duì)3類進(jìn)行測(cè)試時(shí)，隨機(jī)采樣的均值，中值高于K-means采樣.原因是隨著數(shù)據(jù)的增加，隨機(jī)采樣不能確保樣本數(shù)據(jù)與總體數(shù)據(jù)具有相同的分布.相比之下，K-means預(yù)聚類抽取聚類中心，更好地保證分布，因此采樣也會(huì)具有更好的性能.此外，盡管15類時(shí)隨機(jī)抽樣比K-means抽樣更好，但結(jié)果沒(méi)有太大差異.這也是由于隨機(jī)性而引發(fā)的.總而言之，SSC-K-means總是比SSC-Random聚類效果更好.

表2 不同采樣方式在數(shù)據(jù)集COIL-20上的ACC(%)結(jié)果Table 2 ACC (%) of different sampling methods on COIL-20 database

表3 不同采樣方式在數(shù)據(jù)集COIL-20上的NMI (%)結(jié)果Table 3 NMI (%) of different sampling methods on COIL-20 database

表4 不同算法在數(shù)據(jù)集COIL-20上的執(zhí)行時(shí)間Table 4 Computational times(s) of different algorithms on COIL-20

2)如表4所示，所提算法大大減少了運(yùn)行時(shí)間成本.隨著數(shù)據(jù)量的增加，效果更加明顯.這表明所提方法更適合處理海量數(shù)據(jù)，節(jié)省時(shí)間，效率更高.例如，當(dāng)類別數(shù)為3時(shí)，SSC-K-means節(jié)省4s，而當(dāng)類別數(shù)為10時(shí)，SSC-K-means節(jié)省459s.此外，由于隨機(jī)采樣更直接，SSC-Random總是比SSC-K-means花費(fèi)更少的時(shí)間.

表5 不同算法在數(shù)據(jù)集YaleBCrop025的ACC (%)結(jié)果Table 5 ACC (%) of different algorithms on YaleBCrop025

5.4 YaleBCrop025數(shù)據(jù)集性能測(cè)試

我們?cè)赮aleBCrop025數(shù)據(jù)集中測(cè)試了所提算法SSC-K-means和SSC-Random，并與最新的3種抽樣子空間聚類方法進(jìn)行了比較：SLRR，SLSR和SSSC.本實(shí)驗(yàn)從38個(gè)類別中隨機(jī)選擇不同數(shù)量的對(duì)象進(jìn)行實(shí)驗(yàn).每一類包括64張圖片.同樣，我們將每個(gè)實(shí)驗(yàn)重復(fù)10次以確保結(jié)果可靠.在YaleBCrop025測(cè)試后不同算法的ACC，NMI和TIME的結(jié)果如表5-表6及圖5所示.

分析上述實(shí)驗(yàn)結(jié)果可以得出以下幾個(gè)結(jié)論：

1)表5和表6的實(shí)驗(yàn)結(jié)果表明，無(wú)論類別數(shù)是多少，所提出的算法均優(yōu)于其他算法.其原因是所提出的算法聚類時(shí)仍是對(duì)整個(gè)數(shù)據(jù)進(jìn)行聚類.并且，剩余數(shù)據(jù)點(diǎn)之間的表示系數(shù)是通過(guò)信息傳遞來(lái)獲取的，沒(méi)有拋棄樣本的基本特征.相反，其他算法只是對(duì)樣本點(diǎn)進(jìn)行聚類，然后根據(jù)樣本點(diǎn)的聚類結(jié)果將剩余數(shù)據(jù)歸類，這樣的方法對(duì)噪聲更敏感.

表6 不同算法在數(shù)據(jù)集YaleBCrop025的NMI(%)結(jié)果Table 6 NMI (%) of different algorithms on YaleBCrop025

2)從ACC和NMI的標(biāo)準(zhǔn)差可以看出，所提出的算法在大多數(shù)情況下具有更好的穩(wěn)定性.有時(shí)，盡管所提出算法的穩(wěn)定性不如SLRR，但SLLR的聚類質(zhì)量明顯低于SSC-K-means和SSC-random.

圖5 不同采樣方式在數(shù)據(jù)集COIL-20上的時(shí)間花費(fèi)Fig.5 Computational times of different sampling methods on COIL-20 database

3)圖5的結(jié)果表明，與傳統(tǒng)的SSC相比，所提出的算法大大減少了運(yùn)行時(shí)間，SSC-K-means和SSC-Random減少了約40%的計(jì)算時(shí)間.另外，盡管其他算法比所提算法花費(fèi)的時(shí)間短，但是聚類質(zhì)量大大低于所提算法.毫無(wú)疑問(wèn)，聚類質(zhì)量比運(yùn)行時(shí)間更重要.

6 結(jié) 論

在本文中我們提出了一種基于信息傳遞的稀疏子空間聚類框架.該框架的關(guān)鍵是采用信息傳遞來(lái)預(yù)測(cè)數(shù)據(jù)之間的關(guān)系，而不是直接計(jì)算，從而節(jié)省時(shí)間.本文最重要的貢獻(xiàn)是，所提出的框架具有通用性：框架內(nèi)可以采用任何抽樣方法來(lái)選擇樣本點(diǎn)，并且該框架可以應(yīng)用于除SSC之外的其他稀疏子空間聚類算法.在COIL-20數(shù)據(jù)庫(kù)上的實(shí)驗(yàn)結(jié)果表明，與傳統(tǒng)的SSC相比，該算法大大減少了計(jì)算時(shí)間，提高了聚類質(zhì)量.此外，在YaleBCrop025上的實(shí)驗(yàn)證明，所提出的方法比其他方法具有更高的準(zhǔn)確性.