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

歐琦媛,祝 恩

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

1 引言

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

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

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

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

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

2 相關(guān)工作

2.1 多核k均值聚類

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

(1)

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

2.3 子空間聚類

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

s.t.X=XS+E

(2)

2.4 基于采樣的聚類算法

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

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

本節(jié)首先修改子空間聚類目標(biāo)[19,20],以適應(yīng)壓縮多視圖子空間對(duì)齊任務(wù),并提出新的優(yōu)化目標(biāo)；之后，更進(jìn)一步提出一個(gè)高效的三步迭代優(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個(gè)基核的聚類指示矩陣,P∈Rn×m是通過學(xué)習(xí)m個(gè)線性組合產(chǎn)生錨點(diǎn)的采樣矩陣。通過二者相乘得到壓縮后的子空間，m即為子空間的維度，V(·)表示矩陣的所有元素，Im表示m維單位矩陣。本文設(shè)定一個(gè)共同的采樣矩陣P被所有視圖共享。Si∈Rn×m是第i個(gè)基核的重構(gòu)矩陣，它通過生成的樣本點(diǎn)對(duì)原始數(shù)據(jù)進(jìn)行重構(gòu)。S是一個(gè)將所有視圖的信息融合的共識(shí)矩陣。

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

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

(4)

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

3.2 優(yōu)化算法

為了對(duì)式(4)進(jìn)行優(yōu)化，本文提出了三步迭代優(yōu)化算法。在每一步中，固定3個(gè)待優(yōu)化變量中的2個(gè)，對(duì)另一個(gè)進(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( )為取符號(hào)函數(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，得到：

對(duì)于?P，由于滿足PTP=Im，則：

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

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

因此，對(duì)于?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基于壓縮子空間對(duì)齊的多核聚類算法CSA-MKC

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

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

2.repeat

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

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

6.t=t+1。

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

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

3.3 CSA-MKC算法分析

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

3.3.1 收斂性

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

3.3.2 計(jì)算復(fù)雜度

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

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

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

Table 1 Information of datasets

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

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

4.2.1 聚類性能比較

聚類結(jié)果如表2和表3所示。本文CSA-MKC算法在5個(gè)數(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版本的時(shí)間成本。如圖1所示，由于CSA-MKC算法是由矩陣乘法帶來的二次復(fù)雜度且易于并行化，因此本文提出的CSA-MKC算法在計(jì)算成本方面更具優(yōu)勢。

Figure 1 Time consumption comparison圖1 計(jì)算時(shí)間對(duì)比

5 結(jié)束語

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