聶飛平，王成龍，王 榕

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

聚類是模式識別和統(tǒng)計(jì)機(jī)器學(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)常會(huì)有更好的表現(xiàn)．一般來說，譜聚類算法可以分為3個(gè)步驟：① 相似圖構(gòu)建；② 譜分析；③ 應(yīng)用k-means等離散化程序獲得最終聚類結(jié)果．譜聚類的實(shí)現(xiàn)非常簡單，可以通過標(biāo)準(zhǔn)的線性代數(shù)方法求解[3]．近幾十年來，人們提出了各種各樣的譜聚類算法[3]，如ratio cut算法[4]和normalized cut算法[5]將數(shù)據(jù)轉(zhuǎn)換為基于相似性的加權(quán)無向圖，然后通過圖優(yōu)化算法進(jìn)行求解．NG 等[6]將數(shù)據(jù)投影到一個(gè)低維空間，在這些空間中有很多方法可以將它們分離，比如使用k-means算法．然而譜聚類由于涉及大圖構(gòu)建，特征分解等高計(jì)算復(fù)雜度操作[4-6]，難以直接應(yīng)用于大規(guī)模聚類．

1 目標(biāo)函數(shù)設(shè)計(jì)

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

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

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

(1)

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

進(jìn)一步，可得到二部圖的相似矩陣為

(2)

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

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

(3)

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

(4)

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

2 理論分析

2.1 算法優(yōu)化

如前所述，聚類問題被描述為一個(gè)具有離散約束的目標(biāo)函數(shù)，但由于離散約束難以求解，本研究先對離散約束進(jìn)行松弛，再采用交替優(yōu)化的方法對目標(biāo)函數(shù)進(jìn)行優(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)可進(jìn)一步寫為

(10)

當(dāng)F固定時(shí)，式(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是獨(dú)立的，所以對于每個(gè)i可分別求解式(15)．

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

(15)

(16)

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

優(yōu)化完畢．

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

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

FCBG算法的詳細(xì)流程見圖1．

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

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

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

1) 錨點(diǎn)生成．通過隨機(jī)選擇生成m個(gè)錨點(diǎn)的時(shí)間復(fù)雜度可忽略不計(jì)．

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

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

3.1.1 評價(jià)指標(biāo)

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

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

(17)

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

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

(18)

3.1.2 實(shí)驗(yàn)數(shù)據(jù)集

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

結(jié) 語

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