自適應多視角子空間聚類

2021-05-10 12:48:38唐啟凡張玉龍何士豪周志豪

西安交通大學學報 2021年5期

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

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

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

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

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

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

1 相關工作

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

1.1 單視角聚類

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

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

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

1.2 多視角聚類

與單視角聚類算法相比,多視角聚類算法通常可以挖掘出多視角數據中的隱藏信息與結構,并可以利用這些信息與結構顯著地提升算法性能。多視角聚類算法通常分為基于圖的多視角聚類、基于矩陣投影的多視角聚類以及多視角子空間聚類3類。

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

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

2.1 損失函數

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

本文提出的損失函數為

(1)

(2)

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

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

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

(3)

(4)

(5)

(6)

式中

(7)

(8)

2.2 優化

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

(9)

(10)

(11)

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

(12)

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

2.3 自適應參數選擇

(13)

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

輸入:具有v個視角的數據矩陣X1,…,Xi,…,Xv

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

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

3 repeat

5 利用式(11)更新Zv

6 根據式(13)更新λ

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

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

3 實驗

3.1 數據集

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

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

BBCSport[22]包含從BBC Sport網站中收集的來自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張河流領域衛星圖片,有GIST、PHOG、LBP共3種特征。

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

Scene-15[27]包含4 485張室內和室外場景圖片。圖片的特征與Caltech101數據集一致。

3.2 評價指標

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

(14)

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

(15)

(16)

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

3.3 實驗設置

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

3.4 實驗結果

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

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

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

表1 MSRCV1數據集對比實驗結果

表2 BBCSport數據集對比實驗結果

表3 ORL數據集對比實驗結果

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

表4 Caltech101數據集對比實驗結果

表5 LandUse-21數據集對比實驗結果

表6 Movies617數據集對比實驗結果

表7 Scene-15數據集對比實驗結果

3.5 時間復雜度分析

在Caltech101數據集上,根據經驗對超參數λ和μ進行人工調參,結果如圖2所示。

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

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

3.6 收斂性分析

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