自適應多視角子空間聚類

唐啟凡,張玉龍,何士豪,周志豪

(西安交通大學軟件學院,710049,西安)

近年來,隨著計算機性能的大幅度提升和互聯(lián)網(wǎng)通信速度與用戶的大規(guī)模增長,海量的數(shù)據(jù)被提取出來。人們希望從這些海量的數(shù)據(jù)中找出有意義的結構信息,其中以多視角數(shù)據(jù)最為突出。舉例說明多視角數(shù)據(jù):①新聞既有視頻形式也有音頻形式;②網(wǎng)頁既可以被URL地址所表示也可以被其中內(nèi)容所表示;③雕像可以從不同側面表示;④同一種語義有多種語言的表達方式。聚類算法作為一種行之有效的手段受到了研究人員廣泛的關注,聚類的目的是將具有潛在相似結構的數(shù)據(jù)歸為一類,從而為后續(xù)其他針對于數(shù)據(jù)的處理做準備。傳統(tǒng)的單視角聚類算法在對待多視角數(shù)據(jù)時,會將每一個視角上的特征簡單地連接在同一個矩陣中,并在該特征矩陣上直接運行聚類算法,例如k-means、譜聚類等算法。但是,這樣做有極大的缺點和限制:對于樣本數(shù)較小的數(shù)據(jù),如果將所有視角的特征簡單連接起來會造成維度災難,而且在連接時沒有考慮不同視角數(shù)據(jù)之間的互補性和異構性,會造成多視角數(shù)據(jù)大量信息的缺失。由此,多視角聚類算法憑借其對于多視角數(shù)據(jù)獨特的處理能力、良好的魯棒性及泛化能力得到了研究人員越來越多的關注和研究。

從21世紀開始,有許多科研人員在多視角聚類領域內(nèi)取得了不錯的成果。為了挖掘數(shù)據(jù)的潛在結構,Elhamifar等提出稀疏子空間聚類算法,該聚類算法的主要思想是高維數(shù)據(jù)通常能被低維的子空間數(shù)據(jù)所表示,可由公式X=DC來表示,其中矩陣D為字典矩陣,矩陣C為權重矩陣[1]。通過對權重矩陣添加稀疏性約束,從而發(fā)掘出數(shù)據(jù)矩陣的低維表示。對學習出的權重矩陣應用傳統(tǒng)的聚類算法,便可得到最終的結果。在Elhamifar等[1]的基礎上,Liu等提出了對權重矩陣添加低秩性約束,并在損失中加入噪聲矩陣E,從而在挖掘出數(shù)據(jù)隱藏結構的同時去除數(shù)據(jù)矩陣中夾雜的噪聲點、離群點以及損壞點[2]。通過對噪聲矩陣約束不同的范數(shù),從而達到對不同噪點的良好處理效果。在Elhamifar等[1]和Liu等[2]的研究中可以發(fā)現(xiàn),現(xiàn)實中為了簡化問題的處理,通常所使用的字典矩陣D都是原始數(shù)據(jù)矩陣X,這一做法的原理是數(shù)據(jù)的自表達性質(zhì),即類內(nèi)數(shù)據(jù)點可以被類中其他所有數(shù)據(jù)點線性表示。Ji等在傳統(tǒng)深度學習網(wǎng)絡Auto-Encoder的基礎之上,通過利用數(shù)據(jù)的自表達性質(zhì),設計了神經(jīng)網(wǎng)絡的一個卷積層,使其夾在編碼網(wǎng)絡層和解碼網(wǎng)絡層中間[3],開創(chuàng)了多視角聚類深度學習的先河。

這些算法取得了矚目的成績,但絕大多數(shù)受制于參數(shù)選擇。為了選擇更好的參數(shù),這些算法都會利用歸一化互信息評價指標來評價算法的性能,這又要求數(shù)據(jù)必須包含標簽。但是,現(xiàn)實中的數(shù)據(jù)由于數(shù)據(jù)量過大,絕大多數(shù)情況下都很難對數(shù)據(jù)做出標注,例如道路視頻監(jiān)控數(shù)據(jù)、互聯(lián)網(wǎng)輿情文本數(shù)據(jù)等。為此,許多免除參數(shù)選擇的算法被提出[4-8]。這些算法利用計算得到的權重矩陣、相似度矩陣、指示矩陣來直接計算參數(shù),在算法運行過程中不斷更新參數(shù),從而免除了人工選擇參數(shù)。但是,這類算法依然存在缺陷,例如:在Peng等提出的算法中,由于數(shù)據(jù)表示矩陣Z和相似度矩陣S僅考慮了單個視角內(nèi)的相關性,缺失了對于表示矩陣和相似度矩陣在多視角范圍內(nèi)的相關性約束,造成了算法在特定多視角數(shù)據(jù)集上的性能失效[8];在Nie等提出的算法中,使用RatioCut切圖算法,通過指示矩陣迭代更新各個聚類的權重,該切圖算法使聚類之間相似性最小,但在考慮類內(nèi)相似度時,僅將最大化類內(nèi)數(shù)據(jù)點數(shù)作為目標,缺乏對于類內(nèi)數(shù)據(jù)點之間相似度的深入挖掘,導致在大規(guī)模數(shù)據(jù)集上應用效果欠佳[4]。

為此,本文提出自適應多視角子空間聚類算法ASC,基于不同視角數(shù)據(jù)點對之間的相似度近似的原理,在多視角范圍內(nèi)約束表示矩陣和相似度矩陣間的相關性,構建了全新的損失函數(shù),并使用塊坐標下降法來優(yōu)化,從而徹底解決了這類算法在部分數(shù)據(jù)集中失效的問題,提高了算法的性能。

1 相關工作

近幾十年來,聚類算法的研究大致可以分為單視角聚類和多視角聚類兩大類。本節(jié)挑選了其中最具代表性的算法進行簡單總結,基本上概括了聚類算法的發(fā)展歷程。

1.1 單視角聚類

在早期數(shù)據(jù)結構不復雜且數(shù)據(jù)量不龐大的背景下,聚類算法研究的普遍共識是同一類別的數(shù)據(jù)會圍繞在一些標志性點的附近。所以,只要找出幾個標志性的數(shù)據(jù)點,并根據(jù)其他數(shù)據(jù)點與標志點的相似度,便可以得到數(shù)據(jù)的分類情況。最具代表性的以這種思想為核心的算法為k-means算法。該算法首先根據(jù)聚類數(shù)來隨機初始化標志性點,再將數(shù)據(jù)點分配到離它們最近的標志性點,最后根據(jù)每個聚類的重心更新標志點,循環(huán)往復直到標志點不再變化。與k-means不同,研究者基于概率密度函數(shù)和高斯混合模型,提出了最大期望算法。該算法將每一個類別都看作一個單高斯分布模型,在E步用高斯概率密度函數(shù)計算每個數(shù)據(jù)點所屬的類別,在M步計算每個聚類的聯(lián)合概率分布,優(yōu)化聚類參數(shù)。這兩種算法都是在原始數(shù)據(jù)矩陣上直接應用聚類算法,算法性能往往會受限于原始數(shù)據(jù)結構,而譜聚類算法首先對原始數(shù)據(jù)矩陣進行處理,挖掘出數(shù)據(jù)矩陣潛藏的結構,處理完成后再使用k-means等基礎算法聚類。相比于k-means算法,譜聚類算法性能提高顯著,尤其對于處理稀疏矩陣效果良好。

k-means、最大期望、譜聚類這3種算法假定所有數(shù)據(jù)點都處于同一維空間,對于高維數(shù)據(jù),性能往往下降嚴重。為此,研究者提出了子空間聚類算法,將數(shù)據(jù)矩陣視為由多個維度子空間構成的公共空間,處于同一子空間中的數(shù)據(jù)點劃分為一類?？臻g聚類算法中最具代表性的算法為Elhamifar等提出的稀疏子空間聚類[1]以及Liu等提出的低秩子空間聚類[2],這兩種子空間聚類算法分別對學習出的系數(shù)矩陣約束L1范數(shù)和核范數(shù)的正則化項,最終所學習出的系數(shù)矩陣具有良好的塊對角性質(zhì)。文獻[9]采用L2范數(shù)作為正則化項,同樣取得了不錯的成果。在Elhamifar等[1]和Liu等[2]的基礎上,Wang等將低秩和稀疏的性質(zhì)結合起來,使得學習出的系數(shù)矩陣同時具有稀疏與低秩兩種特性[10],從而提升了算法性能。

單視角聚類算法雖取得了長足發(fā)展,但隨著其他各學科的發(fā)展,數(shù)據(jù)視角數(shù)越來越多,數(shù)據(jù)量也越來越大。因此,對聚類算法的要求也逐步提高,聚類結果既要保持多視角數(shù)據(jù)的一致性,也要挖掘出多視角數(shù)據(jù)的互補性。此外,單視角聚類算法還要面對包含大量噪聲的數(shù)據(jù),已逐步無法滿足性能要求。

1.2 多視角聚類

與單視角聚類算法相比,多視角聚類算法通?？梢酝诰虺龆嘁暯菙?shù)據(jù)中的隱藏信息與結構,并可以利用這些信息與結構顯著地提升算法性能。多視角聚類算法通常分為基于圖的多視角聚類、基于矩陣投影的多視角聚類以及多視角子空間聚類3類。

基于圖的多視角聚類算法將數(shù)據(jù)點看作圖中的結點,圖中邊上的數(shù)據(jù)為結點之間的相似度,常用的相似度度量算法有高斯核函數(shù)、knn算法等。構建好圖之后再采用切分圖的算法將圖分為幾類,最后應用單視角聚類算法即可[11-13]。Kumar等將協(xié)同正則化算法與基于圖的多視角聚類算法相結合,將成對視角的數(shù)據(jù)矩陣投影到嵌入空間中,使它們在該空間中的相關性達到最大[14],但僅限于成對的視角,算法的性能隨著視角數(shù)的提升而下降。基于矩陣投影的算法是將不同視角的數(shù)據(jù)投影到公共低維特征空間中,再進一步優(yōu)化它們之間的相關性,最典型的算法為Chaudhuri等提出的算法,他們通過結合CCA算法來達到這一目的[15]。多視角子空間聚類算法與單視角子空間聚類算法本質(zhì)相同,但加入了更多的正則化項來挖掘多視角數(shù)據(jù)潛在的互補信息與數(shù)據(jù)結構。Cao等引入了希爾伯特施密特準則來衡量視角之間的多樣性,從而挖掘出更多的互補性信息[16]。Zhang等在子空間聚類的基礎上引入了張量,基于張量對矩陣進行分解,并加入矩陣低秩約束,得到了較好的效果[17]。本文算法歸屬于多視角子空間聚類算法,在子空間聚類基本原理的基礎上加入了多個行之有效的正則化項,同時根據(jù)數(shù)據(jù)結構尋找自適應超參數(shù),既保持了多視角數(shù)據(jù)的一致性,也挖掘出了多視角數(shù)據(jù)之間的互補信息。

2 自適應多視角子空間聚類

2.1 損失函數(shù)

設矩陣X1,…,Xi,…,Xv表示輸入的多視角數(shù)據(jù)矩陣,Xi∈Rn×d,符號v、n、d分別表示視角數(shù)、樣本數(shù)和特征數(shù)。數(shù)據(jù)矩陣Xi既可以來自于人工數(shù)據(jù)集,也可以來自于真實數(shù)據(jù)集,例如,圖像數(shù)據(jù)、文字媒體數(shù)據(jù)等。

本文提出的損失函數(shù)為

(1)

(2)

圖1 ASC算法基本原理Fig.1 Basic principle of ASC algorithm

為了挖掘數(shù)據(jù)矩陣X的潛在結構,本文重構矩陣X為新的表示矩陣Z,因此矩陣X與Z之間具有天然的相關性,本文在式(2)中的第一項對數(shù)據(jù)點xi與zi之間的歐幾里得距離進行約束。針對式(2)第2項,本文采用文獻[2,18-19]的思想,在迭代的過程中,屬于同一類別數(shù)據(jù)點的表示點zi會逐漸靠近,并最終坍縮為少數(shù)幾個標志性點。ASC算法基本原理如圖1所示。首先,對原始圖片分別提取局部二值模式(LBP)、方向梯度直方圖(HOG)等多種特征,代表多個視角的數(shù)據(jù)。在得到視角數(shù)據(jù)后,將其輸入到ASC算法當中。這里對數(shù)據(jù)做了簡化處理,圖1中僅假設包含三角和圓兩種類別。迭代一開始,表示矩陣Z與原始數(shù)據(jù)矩陣X一致,當算法迭代100次后,相同類別的表示數(shù)據(jù)點zi會逐漸靠近。同時,處于不同視角相同類別的數(shù)據(jù)點,它們之間的表示點zi也在逐漸靠近,反之逐漸變遠,即不同視角中相同數(shù)據(jù)點對之間的相關性應該相同。

為了實現(xiàn)這一過程,本文在式(2)第二項針對一對表示點zi與zj的歐幾里得距離添加懲罰函數(shù)δ(·)。理想狀態(tài)下,δ(·)應為l0范數(shù),但由于l0范數(shù)是非凸的,造成問題無解,因此通常都松弛到l1范數(shù)。然而,來自于真實數(shù)據(jù)集的矩陣會包含大量的噪點,通過這種數(shù)據(jù)矩陣計算出的最近鄰數(shù)據(jù)點集合ε會包含虛假的數(shù)據(jù)點,也就是并無相關性的點對。l1范數(shù)是數(shù)據(jù)絕對值的和,在優(yōu)化的過程中,噪點并不會隨著迭代而被排除,從而造成算法性能的下降。所以,本文中選擇使用l2范數(shù)來進行約束,式(2)轉(zhuǎn)換為

(3)

(4)

(5)

(6)

式中

(7)

(8)

2.2 優(yōu)化

當Zv固定時,去掉式(8)中的無關項,并求導為0,可得

(9)

(10)

(11)

將式(11)改寫為X=ZM,可以看出,式(11)的解法與線性最小二乘法問題解法相同。將式(11)中的一部分提取出來設為Θ

(12)

易得Θ為拉普拉斯矩陣,根據(jù)拉普拉斯矩陣性質(zhì),可得到M為對稱半正定矩陣,因此在Xv已知的情況下,便可根據(jù)式(11)對Zv進行求解。

2.3 自適應參數(shù)選擇

(13)

通過施加數(shù)據(jù)矩陣X與Θ之間最大奇異值的比例系數(shù),達到前后兩項之間的平衡。每一次迭代都僅改變Θ,數(shù)據(jù)矩陣X不變,因此本文只需在預訓練中計算好‖X‖2即可。對于參數(shù)μ,本文初始化μ為θ2,其中θ為矩陣W中最大邊的長度。ASC算法偽代碼如下。

輸入:具有v個視角的數(shù)據(jù)矩陣X1,…,Xi,…,Xv

1 預訓練權重矩陣W以及‖X‖2

2 初始化連接矩陣C為單位矩陣,表示矩陣Z為數(shù)據(jù)矩陣X,根據(jù)2.3節(jié)對參數(shù)λ和μ進行計算

3 repeat

5 利用式(11)更新Zv

6 根據(jù)式(13)更新λ

7 until滿足收斂條件或達到最大迭代數(shù)

輸出:通過在得到的連接矩陣C上應用譜聚類算法,得到最終聚類分配結果

3 實 驗

3.1 數(shù)據(jù)集

為了驗證算法的魯棒性及有效性,本文實驗所采用的7種數(shù)據(jù)及均來自于現(xiàn)實世界,并對個別數(shù)據(jù)集做了相應的調(diào)整。

MSRCV1[21]包含8種類別的240張圖片。本文挑選了7種類別,分別為樹、建筑、飛機、牛、人臉、汽車和自行車。同時,對這些圖片采用6種特征進行描述,即有CENT、CMT、GIST、HOG、LBP、SIFT共6個視角。

BBCSport[22]包含從BBC Sport網(wǎng)站中收集的來自5個頂尖領域的544篇體育新聞,由兩種視角構成。

ORL[23]包含40種不同的對象,每種對象包含10張不同的特征圖像,有Intensity、BP、Gabor共3種類型的特征被選取。

Caltech101[24]包含從20種類別中挑選出的2 386張圖片,每張圖片由Gabor、WM、CENT、HOG、GIST、LBP共6種不同的特征構成。

LandUse-21[25]包含21種類別的100張河流領域衛(wèi)星圖片,有GIST、PHOG、LBP共3種特征。

Movies617[26]包含從IMDb網(wǎng)站收集的17種類別共617場電影數(shù)據(jù)。由兩種視角構成,這兩種視角分別為1 878個關鍵字及1 398個演員,每個關鍵字至少用于2部電影,一個演員至少出演3部電影。

Scene-15[27]包含4 485張室內(nèi)和室外場景圖片。圖片的特征與Caltech101數(shù)據(jù)集一致。

3.2 評價指標

本文采用歸一化互信息指標(N)、聚類性能評估指標(V)、預測精確度指標(A)從聚類劃分的準確度、聚類性能以及預測精度3個方面對算法進行評價,這3種評價指標都是值越大越好。N的計算公式為

(14)

式中:I為互信息;H為熵。V的計算公式為

(15)

(16)

式中ncorrect表示聚類劃分結果中符合預期的樣本數(shù)。

3.3 實驗設置

對比算法均來自本領域非常經(jīng)典且具有代表性的算法,其中單視角聚類算法2種,多視角聚類算法5種,自適應多視角聚類算法1種。對于單視角聚類算法,取它們在多個視角中表現(xiàn)最好的那個視角,給k-means算法設置對應的聚類數(shù),LRR算法的超參數(shù)根據(jù)Liu等[2]的設置,在[3,5]內(nèi)使用最小二乘法逼近10次,取最好的結果。對于有參數(shù)的多視角聚類算法,首先根據(jù)它們各自對應文獻中推薦的超參數(shù)進行取值,再根據(jù)經(jīng)驗對超參數(shù)逼近10次,取結果最好的那個參數(shù)。對于自適應的多視角聚類方法COMIC,使用文獻[8]中推薦的超參數(shù)。

3.4 實驗結果

每種算法在每個數(shù)據(jù)集上均運行30次,指標采用“平均值±標準差”的格式進行展示。綜合排名是本文算法與其他算法在同一數(shù)據(jù)集上相同評價指標下的排序,1表示效果最好。實驗結果如表1～7所示,其中ASC為本文算法。

由表1～7可知:相比于無參數(shù)多視角聚類算法COMIC,本文算法在數(shù)據(jù)集BBCSport、ORL、Movies617數(shù)據(jù)集中不會失效,在MSRCV1數(shù)據(jù)集中綜合性能提升9.3%(N、V、A這3個指標提升百分比的平均值),在Caltech101數(shù)據(jù)集中綜合性能提升6.8%,在LandUse-21數(shù)據(jù)集中綜合性能提升55.8%,在Scene-15數(shù)據(jù)集中綜合性能提升15.39%;相比有參數(shù)多視角聚類算法,本文算法在MSRCV1、Caltech 101、LandUse-21、Movies617數(shù)據(jù)集中均取得了前2名的成績,在其他數(shù)據(jù)集中平均排名2.15。

在BBCSport、ORL和Scene-15這3個小規(guī)模數(shù)據(jù)集中,本文算法性能與手動調(diào)參聚類算法性能有差距,原因主要有兩點:①在小規(guī)模數(shù)據(jù)集中,手動調(diào)參聚類算法可以在較短時間內(nèi)找到準確的超參數(shù),而在大規(guī)模數(shù)據(jù)集中,由于可選參數(shù)范圍很大,即使經(jīng)過較長時間的調(diào)參,也很難達到較好的性能;②在小規(guī)模數(shù)據(jù)集中,超參數(shù)需要更多輪算法迭代才能獲得性能更優(yōu)的值,而本文算法收斂過快,導致超參數(shù)計算不夠精準。

表1 MSRCV1數(shù)據(jù)集對比實驗結果

表2 BBCSport數(shù)據(jù)集對比實驗結果

表3 ORL數(shù)據(jù)集對比實驗結果

綜合來看,本文算法在大規(guī)模數(shù)據(jù)集Caltech 101、LandUse-21以及噪聲數(shù)據(jù)集Movies617表現(xiàn)突出,取得了首位排名的好成績,并在全部7個數(shù)據(jù)集中相對于無參數(shù)算法性能均有提升。由此可見,本文算法性能優(yōu)異。

表4 Caltech101數(shù)據(jù)集對比實驗結果

表5 LandUse-21數(shù)據(jù)集對比實驗結果

表6 Movies617數(shù)據(jù)集對比實驗結果

表7 Scene-15數(shù)據(jù)集對比實驗結果

3.5 時間復雜度分析

在Caltech101數(shù)據(jù)集上,根據(jù)經(jīng)驗對超參數(shù)λ和μ進行人工調(diào)參,結果如圖2所示。

圖2 時間復雜度分析實驗結果Fig.2 Time complexity analysis of experimental results

共進行80次手動調(diào)參,耗時14 h 18 min,超參數(shù)λ和μ最終收斂在3.8和0.2附近,并得到歸一化互信息評價指標最大值為0.751 3。本文自適應超參數(shù)算法耗時11 min 54 s,與手動調(diào)參相比性能差值僅為1.18%。由此可知,本文算法所得超參數(shù)基本發(fā)揮出算法的最大性能,且在時間和人力成本上有著明顯優(yōu)勢。

3.6 收斂性分析

在Caltech101、LandUse-21這兩個大規(guī)模數(shù)據(jù)集上進行收斂性分析實驗,結果如圖3和圖4所示?？梢钥闯?即使是在大規(guī)模數(shù)據(jù)集中,本文算法依然能夠快速收斂,在Caltech101數(shù)據(jù)集中,迭代38次后基本收斂,在LandUse-21數(shù)據(jù)集中,迭代26次后基本收斂。這一實驗結果證明了本文算法為塊坐標下降法屬類的基本判斷,具有優(yōu)良的收斂性能。

圖3 Caltech101數(shù)據(jù)集上的收斂性分析Fig.3 Convergence analysis on Caltech101 dataset

圖4 LandUse-21數(shù)據(jù)集上的收斂性分析Fig.4 Convergence analysis on LandUse-21 dataset

4 總 結

高維數(shù)據(jù)矩陣通常包含多個低維度子空間,本文認為處于同一子空間中的數(shù)據(jù)是屬于同一類的數(shù)據(jù)。基于此,本文利用子空間進行聚類,提出了自適應多視角子空間聚類算法,結論如下。

(1)來自于現(xiàn)實世界的數(shù)據(jù)通常都是無標簽數(shù)據(jù),超參數(shù)調(diào)優(yōu)往往是聚類算法難以應用于現(xiàn)實的障礙。本文算法將超參數(shù)自適應算法與子空間聚類算法相結合,在保證算法性能的同時極大地降低了通常算法調(diào)優(yōu)過程中所耗費的人力物力成本,使子空間聚類算法應用于現(xiàn)實無標簽數(shù)據(jù)成為可能。

(2)相比于多視角聚類領域中已經(jīng)提出的無參數(shù)聚類算法,本文在前人的基礎上進行改進,成功解決了其在特定數(shù)據(jù)集上算法性能失效的問題,并在多個大規(guī)模數(shù)據(jù)集中取得了良好的性能提升。

(3)本文算法在小規(guī)模數(shù)據(jù)集中與有參數(shù)聚類算法存在性能差距,這也是無參數(shù)聚類算法的普遍缺陷,后續(xù)研究可考慮在小規(guī)模數(shù)據(jù)集的性能上做出提升。