基于壓縮子空間對齊的多核聚類算法 *

歐琦媛,祝 恩

(國防科技大學(xué)計算機(jī)學(xué)院，湖南 長沙 410073)

1 引言

多核聚類MKC(Multiple-Kernel Cluster- ing)[1]巧妙地集成了來自多個基核的異構(gòu)信息，以增強(qiáng)聚類性能，在過去幾年中吸引了研究者的廣泛關(guān)注并實(shí)現(xiàn)了飛躍式的進(jìn)展。盡管已經(jīng)取得了顯著的改進(jìn)，但是基核矩陣的大量內(nèi)存消耗O(n2)和高計算復(fù)雜度O(n3)的相應(yīng)優(yōu)化算法限制了這些算法在實(shí)際中的應(yīng)用[2 - 4]。為了解決這些問題，研究人員已經(jīng)提出了大量算法，這些算法可以大致分為4類。第1類算法將特征從不同的角度投影到共識漢明空間中，并在一個輕量級框架內(nèi)共同學(xué)習(xí)二進(jìn)制代碼和簇結(jié)構(gòu)[5 - 8]。第2類算法[9,10]擯棄同時處理所有數(shù)據(jù)的想法，以低計算量和存儲復(fù)雜度的在線方式解決了相應(yīng)的聚類優(yōu)化問題。第3類算法對子集矩陣的MKC聚類進(jìn)行回歸訓(xùn)練，得到一個深度神經(jīng)網(wǎng)絡(luò)，然后使用訓(xùn)練后的網(wǎng)絡(luò)估計整個數(shù)據(jù)集的矩陣，之后，再對估計得出的矩陣使用k均值算法進(jìn)行聚類。通過這種算法，可以有效地學(xué)習(xí)到聚類指示矩陣。近期，使用采樣策略進(jìn)行有效聚類的第4類算法吸引了眾多研究者的關(guān)注。在這類算法中，假設(shè)僅對一個小的子集進(jìn)行采樣就可以充分代表一個數(shù)據(jù)集。具體來說，在文獻(xiàn)[11,12]中，分別學(xué)習(xí)可記錄所選采樣點(diǎn)集和數(shù)據(jù)點(diǎn)之間相似度的新型二分圖和稀疏關(guān)聯(lián)矩陣進(jìn)行聚類。在高效的多視圖子空間聚類[13]中，通過線性時間復(fù)雜度生成了緊湊的重構(gòu)矩陣，該重構(gòu)矩陣僅使用錨點(diǎn)來重構(gòu)數(shù)據(jù)點(diǎn)。在這些算法中，采樣技術(shù)極大地提高了學(xué)習(xí)速度，而不會明顯降低聚類精度。盡管現(xiàn)有文獻(xiàn)已實(shí)現(xiàn)了各種改進(jìn)，但我們發(fā)現(xiàn)第4類算法存在以下缺陷：首先，這些算法中的錨點(diǎn)是通過k均值聚類或隨機(jī)采樣過程生成的，該方法與多視圖信息融合過程相隔離，從而使學(xué)習(xí)到的錨點(diǎn)不太適合下游任務(wù)，例如譜聚類或子空間聚類。其次，在這些算法中，將生成獨(dú)立的錨點(diǎn)集，而無需在不同視圖之間進(jìn)行信息交換，這將無法適應(yīng)多視圖數(shù)據(jù)的整體結(jié)構(gòu)。這2個因素都會降低學(xué)習(xí)到的鄰接矩陣或重構(gòu)矩陣的判別性，從而導(dǎo)致聚類性能不理想。

本文提出了一種基于壓縮子空間對齊的多核聚類CSA-MKC(Compressed Subspace Alignment based Multiple Kernel Clustering)算法來解決上述問題。具體而言，在該算法中，提出了3種機(jī)制以提高聚類速度和準(zhǔn)確性。 首先，以數(shù)學(xué)方式設(shè)定了采樣過程，并將其巧妙地集成到了多視圖子空間聚類過程中，該設(shè)定允許2個過程進(jìn)行協(xié)作，以便在一個聯(lián)合系統(tǒng)中最佳地相互服務(wù)。在本文公式中，學(xué)習(xí)了一個融合了所有基核信息的共識采樣矩陣。其次，采用后期融合技術(shù)[14,15]來減少本文算法的存儲和計算開銷。最后，將子空間聚類的目標(biāo)重新定義為子空間對齊，以進(jìn)一步降低優(yōu)化的復(fù)雜度。本文的貢獻(xiàn)總結(jié)如下：

(1)本文的MKC算法首次將采樣集成到多視圖聚類中，并在一個統(tǒng)一的框架中迭代地學(xué)習(xí)這2個過程，使得所學(xué)習(xí)的錨點(diǎn)集更適合于聚類需求，大大降低了計算復(fù)雜度，并且極大地提高了聚類性能。

(2)本文提出了一種基于后期融合的多核聚類CSA-MKC算法，具有O(n)的存儲開銷和O(n2)的計算復(fù)雜度。

(3)由于CSA-MKC算法的計算瓶頸是易于并行化的矩陣乘法，因此通過GPU的加速，CSA-MKC算法在性能上優(yōu)于現(xiàn)有的對比算法，并且在二次方復(fù)雜度的基礎(chǔ)上進(jìn)一步得到了加速。

2 相關(guān)工作

2.1 多核k均值聚類

s.t.HTH=Ik,μT1p=1

(1)

2.2 基于后期融合的多核聚類

2.3 子空間聚類

子空間聚類[16]是一種對位于低維聯(lián)合線性子空間附近的高維數(shù)據(jù)進(jìn)行聚類的方法。在這類方法中，研究人員假設(shè)位于同一子空間的樣本可以彼此線性重構(gòu)。給定一個數(shù)據(jù)向量集X=[x1,x2,…,xn]，通過進(jìn)一步考慮存在的噪聲、異常點(diǎn)和缺失信息，該分支中多類方法可以共同表達(dá)為：

s.t.X=XS+E

(2)

2.4 基于采樣的聚類算法

采樣方法在高效多視圖譜聚類任務(wù)[11]以及多視圖子空間聚類任務(wù)[13]中被廣泛使用。在這些方法中，為了避免對n×n鄰接矩陣進(jìn)行高復(fù)雜度的計算和存儲，研究人員選取少數(shù)實(shí)例作為采樣錨點(diǎn)，然后有效地學(xué)習(xí)采樣錨點(diǎn)和數(shù)據(jù)點(diǎn)之間的子圖S∈Rn×m，其中m表示錨點(diǎn)的個數(shù)。正如這些方法所展現(xiàn)的，采樣的過程可以在提供可比性的聚類性能的同時極大地減少存儲和計算開銷。然而，在現(xiàn)有的研究中，采樣過程與多視圖聚類過程相互分離，并且該過程是在各個視圖中獨(dú)立執(zhí)行的，導(dǎo)致采樣點(diǎn)不具有判別性。為了解決這個問題，在下一節(jié)中，本文提出基于壓縮子空間對齊的多核聚類算法。

3 基于壓縮子空間對齊的多核聚類算法CAS-MKC

本節(jié)首先修改子空間聚類目標(biāo)[19,20],以適應(yīng)壓縮多視圖子空間對齊任務(wù),并提出新的優(yōu)化目標(biāo)；之后，更進(jìn)一步提出一個高效的三步迭代優(yōu)化算法并證明其收斂性，進(jìn)而實(shí)現(xiàn)優(yōu)化目標(biāo)。

3.1 優(yōu)化目標(biāo)

為了提高算法效率，本文提出的CSA-MKC算法采用了后期融合機(jī)制和采樣方法，優(yōu)化目標(biāo)如式(3)所示：

s.t. 0≤V(Si)≤1,0≤V(S)≤1,PTP=Im

(3)

其中，Hi∈Rk×n是關(guān)于第i個基核的聚類指示矩陣,P∈Rn×m是通過學(xué)習(xí)m個線性組合產(chǎn)生錨點(diǎn)的采樣矩陣。通過二者相乘得到壓縮后的子空間，m即為子空間的維度，V(·)表示矩陣的所有元素，Im表示m維單位矩陣。本文設(shè)定一個共同的采樣矩陣P被所有視圖共享。Si∈Rn×m是第i個基核的重構(gòu)矩陣，它通過生成的樣本點(diǎn)對原始數(shù)據(jù)進(jìn)行重構(gòu)。S是一個將所有視圖的信息融合的共識矩陣。

盡管在式(3)中，后期融合機(jī)制的引入以及采樣矩陣極大地降低了計算和存儲的開銷，針對公式中矩陣P優(yōu)化的重加權(quán)方法[21]仍然有很高的復(fù)雜度。為了更進(jìn)一步加速運(yùn)算，本文將子空間聚類項轉(zhuǎn)化為子空間對齊項，如式(4)所示：

s.t. 0≤V(Si)≤1,0≤V(S)≤1,PTP=Im

(4)

在式(4)中，使用更便于優(yōu)化的最大化對齊項代替富比尼茨范數(shù)，能大大降低優(yōu)化難度。因為最大化Hi和它的重構(gòu)矩陣的對齊項將在一定程度上減少兩者的差別，式(3)和式(4)將達(dá)到類似的效果。在實(shí)驗部分，實(shí)驗結(jié)果將佐證本文的觀點(diǎn)。

3.2 優(yōu)化算法

為了對式(4)進(jìn)行優(yōu)化，本文提出了三步迭代優(yōu)化算法。在每一步中，固定3個待優(yōu)化變量中的2個，對另一個進(jìn)行優(yōu)化。具體優(yōu)化細(xì)節(jié)如下：

3.2.1 優(yōu)化P

s.t.PTP=Im

(5)

s.t.PTP=Im

(6)

令矩陣A的奇異值分解為UDVT，則式(6)中關(guān)于P的最優(yōu)值有閉式解：P*=U·sign(D)·VT，其中sign( )為取符號函數(shù)：

由于奇異值矩陣D具有非負(fù)性，P的最優(yōu)值為：

P*=U·VT

(7)

定理1式(6)的最優(yōu)解為P*=U·sign (D)·VT。

證明首先，由于滿足正交約束P*TP*=Im，可知P*是式(6)的可行解，接下來證明P*是最優(yōu)解。用奇異值分解的結(jié)果替代矩陣A，將P替換為P*，式(6)可表達(dá)為：

Tr (AP*T)= Tr (UDVT(U·sign (D)·VT)T)

將A的奇異值表示為δ1,δ2,…,δn，得到：

對于?P，由于滿足PTP=Im，則：

Tr (APT) = Tr (UDVTPT) = Tr (VTPTUD)

令G=VTPTU，則GGT=Im，因此：

因此，對于?P，如果P是式(6)的可行解，則一定滿足Tr (APT)≤Tr (AP*T)。

□

3.2.2 優(yōu)化Si

s.t. 0≤V(Si)≤1

(8)

s.t. 0≤V(Si)≤1

(9)

(10)

Proj[0,1]()表示將實(shí)數(shù)矩陣映射到[0，1]的函數(shù)。

3.2.3 優(yōu)化S

s.t. 0≤V(S)≤1

(11)

s.t. 0≤V(S)≤1

(12)

式(12)的最優(yōu)解如式(13)所示:

S*=Proj[0,1](C)

(13)

綜上所述，本文優(yōu)化目標(biāo)式(4)的算法如算法1所示，其中obj(t)表示在第t輪迭代后的目標(biāo)式值。

算法1基于壓縮子空間對齊的多核聚類算法CSA-MKC

輸入：基核{(lán)K(1),…,K(p)},聚類簇數(shù)c,參數(shù)α,錨點(diǎn)數(shù)m。

輸出：共識重構(gòu)矩陣S。

2.repeat

4.通過優(yōu)化式(7)計算P(t);

5.通過優(yōu)化式(13)計算S(t);

6.t=t+1。

7.until ‖P(t)-P(t-1)‖F(xiàn)<10-3×‖P(t)‖F(xiàn)。

8.通過對矩陣S進(jìn)行k均值聚類得到最終聚類結(jié)果。

3.3 CSA-MKC算法分析

下面將從收斂性和計算復(fù)雜性2個方面對算法進(jìn)行分析。

3.3.1 收斂性

在本文提出的三步優(yōu)化算法中，每個子步驟都有一個閉式最優(yōu)解。因此，算法1的目標(biāo)可以保證在每一步迭代中是單調(diào)下降的。同時，目標(biāo)是有下界的，因為P是正交矩陣，并且優(yōu)化式滿足約束0≤V(S,Si)≤1，因此，CSA-MKC算法可以保證收斂到式(4)的局部最優(yōu)。

3.3.2 計算復(fù)雜度

4 實(shí)驗

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

本文在5個流行的數(shù)據(jù)集上評估了CSA-MKC算法的聚類性能。這些數(shù)據(jù)集的詳細(xì)信息如表1所示。

Table 1 Information of datasets

4.2 實(shí)驗設(shè)置與結(jié)果

在本節(jié)中，對CSA-MKC算法與4個MKC算法進(jìn)行比較，以驗證其有效性。平均多核k均值聚類算法(A-MKKM)均勻組合每個核矩陣，并用均核聚類。最佳核k均值算法(SB-MKKM)對各核進(jìn)行核k均值，并取最佳結(jié)果。后期融合對齊最大化算法(MVC-LFA)[15]最大程度地將共識劃分與加權(quán)基核劃分對齊，實(shí)現(xiàn)有效的聚類。在大規(guī)模多視圖子空間聚類(LMVSC)[13]中，采取子空間聚類采樣策略。協(xié)同正則化譜聚類(CRSC)[23]采用協(xié)同正則化學(xué)習(xí)機(jī)制進(jìn)行多視圖譜聚類。矩陣誘導(dǎo)的多核k均值正則化 (MKKM-MR)[24]引入了一個多樣性正則化項，以更好地合并 MKC 中的多源信息。局部核對齊最大化的多核聚類 (MKC-LKA)[25]嘗試通過最大化局部內(nèi)核對齊來更好地保留數(shù)據(jù)之間的內(nèi)在局部幾何結(jié)構(gòu)。

4.2.1 聚類性能比較

聚類結(jié)果如表2和表3所示。本文CSA-MKC算法在5個數(shù)據(jù)集上均取得了最佳性能，并在Flower102和CCV數(shù)據(jù)集上以ACC的標(biāo)準(zhǔn)將次優(yōu)算法性能提高了5%以上，證實(shí)了本文多視圖聯(lián)合采樣學(xué)習(xí)機(jī)制的有效性。表2和表3中加粗的黑體字表示最優(yōu)值，方框中的數(shù)值表示次優(yōu)值。

Table 2 ACC performance

Table 3 Purity performance

4.2.2 聚類效率比較

在圖1中，比較了CSA-MKC算法GPU版本的時間成本。如圖1所示，由于CSA-MKC算法是由矩陣乘法帶來的二次復(fù)雜度且易于并行化，因此本文提出的CSA-MKC算法在計算成本方面更具優(yōu)勢。

Figure 1 Time consumption comparison圖1 計算時間對比

5 結(jié)束語

本文提出了基于壓縮子空間對齊的多核聚類CSA-MKC算法，通過使用線性壓縮矩陣對采樣過程進(jìn)行建模，將采樣和多核聚類任務(wù)合并到一個統(tǒng)一的框架中，迭代優(yōu)化這2個任務(wù)，從而大大提高了計算效率和聚類性能。未來計劃將算法擴(kuò)展到更通用的框架，將其用作一個普適的聚類平臺來重新審視現(xiàn)有的多視圖聚類算法。