基于二部圖的快速聚類算法

聶飛平，王成龍，王 榕

西北工業(yè)大學(xué)計算機學(xué)院，西北工業(yè)大學(xué)光學(xué)影像分析與學(xué)習(xí)中心，陜西西安 710072

聚類是模式識別和統(tǒng)計機器學(xué)習(xí)等領(lǐng)域最基本的問題之一．大多數(shù)聚類算法基于歐式幾何描述數(shù)據(jù)相似性[1-2]，但難以有效刻畫非凸數(shù)據(jù)集分布．基于拉普拉斯矩陣特征分解的譜聚類算法由于可有效利用數(shù)據(jù)的圖和流形信息，可學(xué)習(xí)更多類型的數(shù)據(jù)結(jié)構(gòu)分布，在非凸分布等復(fù)雜數(shù)據(jù)分布上與其他算法(如k-means)相比經(jīng)常會有更好的表現(xiàn)．一般來說，譜聚類算法可以分為3個步驟：① 相似圖構(gòu)建；② 譜分析；③ 應(yīng)用k-means等離散化程序獲得最終聚類結(jié)果．譜聚類的實現(xiàn)非常簡單，可以通過標準的線性代數(shù)方法求解[3]．近幾十年來，人們提出了各種各樣的譜聚類算法[3]，如ratio cut算法[4]和normalized cut算法[5]將數(shù)據(jù)轉(zhuǎn)換為基于相似性的加權(quán)無向圖，然后通過圖優(yōu)化算法進行求解．NG 等[6]將數(shù)據(jù)投影到一個低維空間，在這些空間中有很多方法可以將它們分離，比如使用k-means算法．然而譜聚類由于涉及大圖構(gòu)建，特征分解等高計算復(fù)雜度操作[4-6]，難以直接應(yīng)用于大規(guī)模聚類．

1 目標函數(shù)設(shè)計

譜聚類算法用無向加權(quán)圖表示數(shù)據(jù)關(guān)系，通過對圖中的邊進行分割，將數(shù)據(jù)圖劃分為不同的連通分量完成對數(shù)據(jù)的聚類．因此，在數(shù)據(jù)圖中表示數(shù)據(jù)點間關(guān)系的邊的連接對于類簇結(jié)構(gòu)發(fā)現(xiàn)至關(guān)重要．對于大規(guī)模的高維數(shù)據(jù)，稀疏性和冗余往往同時存在．冗余數(shù)據(jù)帶來不必要的連接，這增加了計算復(fù)雜度．然而，考慮到數(shù)據(jù)的稀疏性和流形假設(shè)，少量的采樣數(shù)據(jù)點往往就足以覆蓋整個點云，本研究將這些采樣數(shù)據(jù)點簡稱為錨點．利用原始數(shù)據(jù)和錨點的耦合結(jié)構(gòu)，可以快速學(xué)習(xí)到聚類結(jié)果．LIU等[7]在半監(jiān)督學(xué)習(xí)中首先應(yīng)用了這種選擇錨點的策略，并基于二部圖給出了一種快速構(gòu)圖方法．CAI等[8]將通過k-means方法選擇錨點的策略看作是對原始數(shù)據(jù)的稀疏編碼，求解稀疏編碼矩陣的過程其實是求解一個有稀疏約束的線性回歸問題的過程．

本算法致力于學(xué)習(xí)一個數(shù)據(jù)-錨點二部圖(其中邊的權(quán)重表示對應(yīng)的數(shù)據(jù)與錨點的相似度)，并基于二部圖完成快速聚類．令zij表示第i個數(shù)據(jù)點與第j個錨點之間的相似度，即對應(yīng)數(shù)據(jù)點和錨點的連接關(guān)系．在理想的類簇結(jié)構(gòu)中，不同類的錨點和數(shù)據(jù)之間沒有連接，屬于同一類的錨點和數(shù)據(jù)點相互連接，且連接概率越大，相似度分配越高．

令X=[x1,x2, …,xn]T∈Rn×d表示數(shù)據(jù)矩陣，U=[u1,u2, …,um]T∈Rm×d表示錨點，則錨點uj可以以zij的概率連接到xi． 數(shù)據(jù)點和錨點之間的距離越近，連接的概率就越大．本算法將使用一種自適應(yīng)近鄰構(gòu)圖方法[9]來構(gòu)造初始相似矩陣．其中，第i個點的近鄰分配可以被描述為

(1)

其中， 加粗的1表示矢量1;α為正則化參數(shù)．如果沒有正則化項， 則式(1)會很容易得到平凡解，即最接近xi的錨點被分配為xi近鄰點的概率為1，而其他所有點被分配為xi的近鄰點的概率都將為0．α的值可以通過文獻[9]算法求解．然后，代入α的值求解問題(1)，從而獲得數(shù)據(jù)和錨點的關(guān)系矩陣Z∈Rn×m．

進一步，可得到二部圖的相似矩陣為

(2)

其中，S∈R(n+m) ×(n+m)．

通常情況下，式(1)無法在任意α值的情況下實現(xiàn)理想的近鄰分配，所有的數(shù)據(jù)點和錨點會被連接在一起，成為一個全連通圖．在這種情況下，經(jīng)典譜聚類算法[8]會通過求解式(3)來解決此問題．

(3)

s.t.zTi1=1, 0≤zij≤1,

(4)

簡言之，本研究提出的算法通過自適應(yīng)近鄰策略來構(gòu)造二部圖， 并且對這個圖的拉普拉斯矩陣施加了秩約束，從而可以直接從圖的劃分上得到清晰的類簇結(jié)構(gòu)．下面將對該目標函數(shù)的優(yōu)化進行理論推導(dǎo)，同時分析該算法的計算復(fù)雜度．

2 理論分析

2.1 算法優(yōu)化

如前所述，聚類問題被描述為一個具有離散約束的目標函數(shù)，但由于離散約束難以求解，本研究先對離散約束進行松弛，再采用交替優(yōu)化的方法對目標函數(shù)進行優(yōu)化．

根據(jù) Ky Fan 定理[15]，可得

(5)

s.t.zTi1=1, 0≤zij≤1,

F∈R(n+m)×c,FTF=I

(6)

同式(4)相比，式(6)更容易求解．本研究使用交替優(yōu)化的算法求解式(6)．

(7)

將F和DS分別寫為如式(8)和式(9)的塊矩陣形式

(8)

(9)

其中，U∈Rn×c；V∈Rm×c；DSu∈Rn×n；DSu∈Rm×m．

根據(jù)式(2)，式(7)可進一步寫為

(10)

當(dāng)F固定時，式(6)變型為

s.t.zTi1=1, 0≤zij≤1

(11)

根據(jù)歸一化拉普拉斯矩陣的性質(zhì)， 可得

(12)

其中，sij為S的元素.根據(jù)式(2)可將式(12)寫為

(13)

s.t.zTi1=1, 0≤zij≤1

(14)

需要注意的是，式(14)對于不同的i是獨立的，所以對于每個i可分別求解式(15)．

s.t.zTi1=1, 0≤zij≤1

(15)

(16)

式(16)可根據(jù)文獻[9]求得閉式解．

優(yōu)化完畢．

本研究提出的FCBG算法，在每次迭代中只需要更新連接數(shù)據(jù)點和該數(shù)據(jù)點最相似的k個錨點間的邊的權(quán)重，再在一個n×m的矩陣上進行奇異值分解(singular value decomposition, SVD)，因此更新Z和F的計算復(fù)雜度非常低(只計算一個非常稀疏的矩陣的前c個特征向量)．所以，F(xiàn)CBG算法可有效處理大規(guī)模數(shù)據(jù)．

在實際運行時，為加速程序，需在迭代時調(diào)整λ． 將λ的初始值設(shè)為α， 然后在每次迭代中，若S的連接分量小于c， 就將λ增加一倍；反之，若比c大就將λ減小為λ/2．

FCBG算法的詳細流程見圖1．

圖1 FCBG算法流程圖 Fig.1 The flow chart of FCBG algorithm

2.2 時間復(fù)雜度分析

給定X∈Rn×d， FCBG算法由4個階段組成：

1) 錨點生成．通過隨機選擇生成m個錨點的時間復(fù)雜度可忽略不計．

2) 初始化矩陣Z∈Rn×m． 這需要根據(jù)問題(1)的最優(yōu)解從m個錨點中找到k個最近鄰點，并且計算相似性．該步驟的計算復(fù)雜度為O(nmd+nmlog(m))．

4) 直接根據(jù)二部圖的連通性得到聚類結(jié)果．該步驟時間復(fù)雜度為O(n+m+nk)．

考慮到m遠小于n， 且t通常都非常小，F(xiàn)CBG算法的時間復(fù)雜度與樣本數(shù)目n呈線性關(guān)系

3 實驗結(jié)果與分析

為說明FCBG算法的有效性，將該算法與其他大規(guī)模譜聚類算法在真實數(shù)據(jù)集上進行對比．本實驗通過隨機采樣為FCBG算法選擇錨點，當(dāng)然也可以基于這一框架，使用其他選擇代表性錨點的方法，如隨機投影樹方法等．

3.1 實驗設(shè)計

我們將原始的譜聚類(spectral clustering，SC)作為基準算法．

對比算法采用文獻[8]提出了一種用于大規(guī)模聚類問題的基于地標點的譜聚類算法．該算法選擇p個代表性數(shù)據(jù)點作為地標，并將原始數(shù)據(jù)點表示為這些地標的線性組合．然后利用基于地標的表示來有效地計算數(shù)據(jù)相似矩陣的譜嵌入．基于不同的代表點選擇策略，該算法可分為使用隨機采樣的大規(guī)模譜聚類(large spectral clustering based on random selection，LSC-R)算法和使用k-means的大規(guī)模譜聚類(large spectral clustering based onk-means selection，LSC-k)算法．LSC-R算法時間復(fù)雜度為O(nmd+m3+m2n+nmdt1)， LSC-k算法的時間復(fù)雜度為O(nmdt+nmd+m3+m2n+nmdt1)． 其中，t為選擇錨點時k-means的迭代次數(shù)；m為代表點數(shù)量；n為樣本點個數(shù)；d為數(shù)據(jù)維度；t1為離散化步驟時k-means的迭代次數(shù)．

實驗中所有代碼的運行環(huán)境都是Matlab R2018a，硬件系統(tǒng)配置為3.30 GHz，i5-4590 CPU，16 Gbyte 運行內(nèi)存，Windows 10．

3.1.1 評價指標

為評估聚類結(jié)果，采用聚類準確率(ACC)、歸一化互信息熵(normalized mutual information, NMI)這兩種被廣泛使用的聚類性能指標．

ACC指標可以發(fā)現(xiàn)聚類結(jié)果和真實類標簽之間的一對一關(guān)系，且測量每個聚類所包含的來自對應(yīng)類別的數(shù)據(jù)點的多少，其計算式為

(17)

其中，ri為xi聚類結(jié)果給出的類標簽；li為真實的類標簽；n為樣本數(shù)量；δ(x,y)是德爾塔函數(shù)， 當(dāng)x=y時，函數(shù)值為1，否則，函數(shù)值為0； map(ri)是置換映射函數(shù)，可將每個聚類標簽映射到數(shù)據(jù)集的真實對應(yīng)類標簽．

NMI指標用于確定聚類的質(zhì)量．給定一個聚類結(jié)果，則

(18)

3.1.2 實驗數(shù)據(jù)集

將FCBG算法在基準數(shù)據(jù)集Palm25、 Clave-Vectors和Aloi上分別進行實驗．Palm25數(shù)據(jù)集是掌紋數(shù)據(jù)集，包含了100類物體的總共2 000張灰度圖，每張樣本包含圖片像素值對應(yīng)的256個維度．ClaveVectors數(shù)據(jù)集由16維二進制特征組成，表示在 4/4 拍的音樂中鼓點敲擊的記錄，用于打擊樂的分類．Aloi數(shù)據(jù)集是由1 000個小物體組成的彩色圖像集合．每個樣本由128個特征組成．這3個基準數(shù)據(jù)集的統(tǒng)計信息見表1．

表1 三個基準數(shù)據(jù)集統(tǒng)計信息Table 1 The statistics of three benchmark datasets

3.2 實驗結(jié)果

考慮到每種數(shù)據(jù)集樣本數(shù)規(guī)模不一致，且不同的錨點數(shù)量對聚類結(jié)果存在影響(需要注意的是，錨點數(shù)量必須大于類別數(shù)，否則算法不滿足秩約束)，選擇使算法聚類結(jié)果最好的錨點數(shù)，即為ClaveVectors、Palm25、和Aloi數(shù)據(jù)集設(shè)置的錨點數(shù)量m分別為16、128和1 024．在實驗時，每種算法都進行了20次測試并取平均值，表2和表3分別記錄了FCBG算法與對比算法在真實數(shù)據(jù)集上的聚類準確度、NMI的均值．表4記錄了所有算法在數(shù)據(jù)集上運行20次時所需要的平均時間．

在表2至表4中將參與對比的算法最好的結(jié)果進行標記．結(jié)果可見，就聚類準確率和NMI而言，F(xiàn)CBG 算法在3個數(shù)據(jù)集上均保持了顯著的優(yōu)勢，優(yōu)于對比算法的結(jié)果．

表2 三個數(shù)據(jù)集上的聚類準確率Table 2 Cluster accuracy on three data sets %

表3 三個數(shù)據(jù)集上的歸一化互信息熵Table 3 NMI on three data sets %

表4 三個數(shù)據(jù)集上的聚類時間Table 4 Clustering time on three data sets s

表4記錄了算法總的運行時間．從表4可見，F(xiàn)CBG算法在3個數(shù)據(jù)集上進行聚類時，保持了和對比算法相近的運行時間．值得注意的是，F(xiàn)CBG算法在理論上時間復(fù)雜度要略大于LSC-R和LSC-k算法的時間復(fù)雜度，但在運行時出現(xiàn)了FCBG算法運行時間大于LSC-R和LSC-k算法運行時間的情況．這是因為在完成譜分析后進行離散化時，F(xiàn)CBG算法直接根據(jù)圖的連通性得到聚類結(jié)果，時間復(fù)雜度可忽略不計，而LSC-R和LSC-k算法均需要通過在類似性矩陣F上執(zhí)行k-means算法得到聚類結(jié)果．實驗使用LSC-R和LSC-k算法的默認設(shè)置，k-means算法需重復(fù)10次，故所需時間極長．在不計算離散化步驟時間的情況下，LSC-R算法和LSC-k算法運行時間均短于FCBG算法所需時間．總體上來說，F(xiàn)CBG算法運行時間和對比算法相近，但更穩(wěn)定．

結(jié) 語

本研究針對大規(guī)模譜聚類問題提出了一種基于二部圖的快速聚類算法FCBG．初始階段，F(xiàn)CBG算法采用隨機采樣從n個原始數(shù)據(jù)點中選擇m個錨點；構(gòu)圖階段，F(xiàn)CBG算法首先為原始數(shù)據(jù)點和錨點構(gòu)建初始相似矩陣，然后對相似矩陣的歸一化拉普拉斯矩陣施加秩約束，利用約束結(jié)果對相似矩陣進行更新，最后迭代得到聚類結(jié)果．對歸一化拉普拉斯矩陣施加秩約束，可保證相似矩陣中連通分量數(shù)量恰好等于類簇數(shù)量．最終得到的二部圖是稀疏的，且保持了清晰的聚類結(jié)構(gòu)；FCBG算法計算復(fù)雜度與樣本數(shù)目呈線性關(guān)系．真實數(shù)據(jù)集上的實驗結(jié)果表明，F(xiàn)CBG算法性能優(yōu)越、速度快，且圖學(xué)習(xí)思想可應(yīng)用于其他基于圖的機器學(xué)習(xí)算法．