基于ε-鄰域和拉普拉斯矩陣秩約束的譜聚類算法

朱恒東,馬盈倉,楊 婷,張 要

(西安工程大學(xué) 理學(xué)院,陜西 西安 710048)

0 引 言

聚類[1]是將一群不相關(guān)的對象劃分為相似對象的過程。其中建立在譜圖理論基礎(chǔ)上的譜聚類算法是目前研究較多、理論基礎(chǔ)深厚、應(yīng)用廣泛的聚類方法[2],其本質(zhì)是將聚類問題轉(zhuǎn)化為圖形最優(yōu)切分問題,相較于傳統(tǒng)的聚類算法,可以更好地處理非凸分布等復(fù)雜數(shù)據(jù)。在過去幾十年中,譜聚類在機(jī)器學(xué)習(xí)[3]、圖像處理[4]、計(jì)算機(jī)視覺[5]以及系統(tǒng)辨識(shí)[6]等領(lǐng)域都有著廣泛的應(yīng)用。譜聚類算法作為近年來熱門聚類方法之一[7],很多學(xué)者們提出了不同的譜聚類[8],如傳統(tǒng)的N-cut算法[9]和R-cut算法,也有最新的基于二部圖的快速聚類算法[10]等。

譜聚類算法可以簡單分為3 個(gè)步驟:①構(gòu)建相似矩陣;②譜分析;③應(yīng)用k-means等算法聚類。其中至少存在2個(gè)問題。首先,相似矩陣的構(gòu)造方法很多,不同方法直接影響聚類結(jié)果,構(gòu)造合適的相似矩陣成為了一個(gè)問題[11]。Ng等[12]提出了NJW算法,考慮采用高斯核函數(shù)來構(gòu)造相似矩陣。采用全連接構(gòu)造方法，數(shù)據(jù)點(diǎn)之間的相似度保留過多影響聚類效果，為了滿足稀疏性,文獻(xiàn)[13]引入了K-近鄰思想。為了避免δ參數(shù)的不確定性對聚類結(jié)果的影響,Tulin等[14]提出了NC算法,以自適應(yīng)的方式自行調(diào)整參數(shù)。文獻(xiàn)[15]引入深度學(xué)習(xí)中的S型函數(shù)來構(gòu)造相似矩陣。雖然取得了一定效果,但也容易被“錯(cuò)誤”的數(shù)據(jù)影響[16]。其次,在譜聚類過程中,一般先是求解特征矩陣,然后對特征矩陣進(jìn)行K-means得到聚類結(jié)果。對于大規(guī)模數(shù)據(jù)聚類問題,譜聚類在譜分析處理中由于涉及大圖構(gòu)建、特征分解等高計(jì)算度復(fù)雜操作[9,12,17],使得求解難度增加,并且即使求解出特征矩陣,也并不能直接得到聚類結(jié)果,而是要進(jìn)行離散化處理得到結(jié)果,使得運(yùn)行效率不高。導(dǎo)致難以直接使用譜聚類算法解決大規(guī)模數(shù)據(jù)聚類問題。文獻(xiàn)[18]不通過求解特征矩陣來聚類,而是采用對拉普拉斯矩陣進(jìn)行秩約束,保證圖有K個(gè)連通分支數(shù)目,進(jìn)而選擇對最后學(xué)習(xí)到的相似矩陣直接聚類。近年來關(guān)于譜聚類的研究雖然取得了一定進(jìn)展,但總體上仍處于初級(jí)探索階段,該算法仍然有很大的深入研究空間。

基于以上情況,本文提出新的譜聚類方法。首先,在采用傳統(tǒng)高斯核函數(shù)構(gòu)建相似矩陣過程中,引入ε-鄰域思想,對親和矩陣進(jìn)行稀疏化處理,可以有效利用數(shù)據(jù)點(diǎn)的局部信息[19],剔除大量不相關(guān)點(diǎn)的信息,還可以降低譜分析過程中的計(jì)算量;其次,在譜分析過程中,對相似矩陣的拉普拉斯矩陣加上秩約束[20],并且對相似矩陣加上l2,1范數(shù)作為正則項(xiàng)來修正模型,保證圖的結(jié)構(gòu)性；然后利用學(xué)習(xí)到的相似矩陣來直接聚類。建立基于ε-鄰域和拉普拉斯矩陣秩約束的譜聚類算法(spectral clustering algorithmε-nearest neighbors based on and Laplace matrix rank constraint,簡寫為ε-RSC)。

1 預(yù)備知識(shí)

1.1 譜聚類

譜聚類的原理是首先利用樣本數(shù)據(jù)X={x1,x2,…,xn},X∈Rn×k,得到鄰接矩陣,然后根據(jù)鄰接矩陣求得拉普拉斯矩陣,再對拉普拉斯矩陣進(jìn)行特征分解得到特征向量,最后對特征矩陣進(jìn)行聚類。常采用高斯核函數(shù)[21]構(gòu)造鄰接矩陣A,即

(1)

(2)

進(jìn)而得到新的函數(shù)

(3)

1.2 l2,1范數(shù)

使用l2范數(shù)的平方作為損失函數(shù)對較小的異常值不敏感，但對較大的異常值敏感；使用l1范數(shù)作為損失函數(shù)對較大的異常值不敏感，對較小的異常值敏感。由文獻(xiàn)[22]可知l2,1范數(shù)綜合了l2范數(shù)和l1范數(shù)的優(yōu)點(diǎn),既無論異常值的大小，l2和l1范數(shù)的魯棒性均可被利用。

性質(zhì)1[23]對于矩陣X,其中有

‖X‖2,1=tr(XTDX)

(4)

式中：D是對角矩陣,對角元素為

2 模型的建立及求解

2.1 模型建立

譜聚類原始目標(biāo)函數(shù)為

min tr(FTLSF)
st.FTF=1

(5)

(6)

為了不求解特征矩陣F,采用對相似矩陣S聚類。對拉普拉斯矩陣加上秩約束,即rank(LS)=n-K,通過保證圖有K個(gè)連通分支,保證圖的結(jié)構(gòu)性,最終迭代得到聚類結(jié)果。式(6)轉(zhuǎn)化為

(7)

式中:λ為常數(shù);A為采用1.1節(jié)方法構(gòu)造的相似矩陣;S為最終學(xué)習(xí)的相似矩陣。

2.2 模型求解

將式(7)變化為如下模型:

(8)

式中:A為親和矩陣;S為要學(xué)習(xí)的相似矩陣。對于S,存在一個(gè)函數(shù)fi∈Rc×1[20],使得

(9)

此時(shí)采用交替迭代優(yōu)化算法求解,具體步驟為

1) 當(dāng)S固定時(shí),式(8)變?yōu)?/p>

min tr(FTLSF)
st.FTF=1,F∈Rn×k

(10)

對拉普拉斯矩陣LS進(jìn)行特征分解,求解K個(gè)最小特征值對應(yīng)的特征向量,得到F。

2) 當(dāng)F固定時(shí),結(jié)合式(9),式(8)變?yōu)?/p>

(11)

(12)

根據(jù)1.2中l(wèi)2,1范數(shù)的性質(zhì)1,得

(13)

(14)

(15)

再根據(jù)拉格朗日乘子法,得

(16)

對si求偏導(dǎo),并令其偏導(dǎo)數(shù)等于0,得

Dsi-pi-η1-αi=0

(17)

對其中每個(gè)數(shù)據(jù),有

dijsij-pij-η-αij=0

(18)

令dijsij=0,根據(jù)KKT條件,得

(19)

其中(v)+=max(0,v),根據(jù)η定義函數(shù)

(20)

gi(η)=0

(21)

式中：gi(η)為分段單調(diào)遞增函數(shù),可用牛頓法迭代求解。值得說明的是,由于在算法過程中借用牛頓迭代法,因此是收斂的。

經(jīng)過以上交替迭代優(yōu)化算法計(jì)算后,得到最終學(xué)習(xí)到的相似矩陣。在迭代過程中,因?yàn)榧尤肓死绽咕仃囍燃s束,通過保證特征矩陣的秩為K個(gè),從而保證圖有K個(gè)連通分支數(shù)目,進(jìn)而可以直接對相似矩陣直接聚類,得到聚類結(jié)果。

2.3 算法流程

根據(jù)2.2模型求解,總結(jié)梳理ε-RSC算法流程如下:

輸入 親和矩陣A∈Rn×n,聚類數(shù)K,常數(shù)λ

1) 計(jì)算親和矩陣A;

3) for iter=1,2,…,最大迭代次數(shù) do;

4) while不收斂do;

5) 固定F,由F求解vi,初始化S;

6) fori=1,2,…,n;

8) end for;

9) 固定S,由S求解拉普拉斯矩陣,求解F,完成更新F;

10) end while;

11) end for;

12) 解出S,利用圖的K個(gè)連通分支聚類。

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

為驗(yàn)證算法有效性,將本文ε-RSC算法與K均值(K-means)算法、LRR方法、SR方法以及文獻(xiàn)[22]中CLR-L方法進(jìn)行對比,數(shù)據(jù)集選取人造數(shù)據(jù)集和真實(shí)數(shù)據(jù)集。

3.1 評(píng)價(jià)指標(biāo)

以聚類準(zhǔn)確率和標(biāo)準(zhǔn)化互信息評(píng)價(jià)算法聚類性能。聚類準(zhǔn)確率

(22)

式中:ri和si分別為聚類算法得到的類標(biāo)簽和數(shù)據(jù)集真實(shí)的類標(biāo)簽;n為樣本個(gè)數(shù);函數(shù)δ(x,y)在當(dāng)x=y時(shí)為1,否則為0;map(ri)是一個(gè)排列匹配函數(shù),將ri標(biāo)簽映射成與si匹配的等效標(biāo)簽。A值在[0,1]之間,值越大越好。

標(biāo)準(zhǔn)化互信息用于確定聚類的質(zhì)量,其公式為

(23)

3.2 人造數(shù)據(jù)集

人造數(shù)據(jù)集選取Cdata04數(shù)據(jù)集和雙月數(shù)據(jù)集。Cdata04數(shù)據(jù)集由4個(gè)環(huán)型簇組成,形狀如四葉草,如圖1所示。葉子交匯的地方,由于數(shù)據(jù)間聯(lián)系緊密,給聚類分析帶來一定難度。雙月型數(shù)據(jù)集是一類典型的非線性數(shù)據(jù)集,形狀如兩輪彎月,如圖2所示。由于雙月型數(shù)據(jù)的特殊分布,很多聚類算法容易將中間嵌入的地方混聚一類。

圖 1 Cdata04數(shù)據(jù)集Fig.1 Cdata04 data set

圖3～4分別為Cdata04權(quán)重連接圖和雙月權(quán)重連接圖,均以初始親和矩陣為原始權(quán)重,將數(shù)據(jù)重新連接整理,將數(shù)據(jù)聚類問題轉(zhuǎn)變?yōu)樽V聚類圖形最優(yōu)切分問題?？梢园l(fā)現(xiàn),整個(gè)權(quán)重圖連線緊密,所有的點(diǎn)被劃為一塊。

圖 3 Cdata04權(quán)重連接圖Fig.3 Weight connection diagram of Cdata04

圖 4 雙月權(quán)重連接圖Fig.4 Bimonthly weight connection diagram

圖5～6分別為ε-RSC算法對2種數(shù)據(jù)集的聚類結(jié)果圖?？梢园l(fā)現(xiàn),Cdata04數(shù)據(jù)集和雙月型數(shù)據(jù)集被很好地切分。這說明ε-RSC算法得到的相似矩陣是合理的。

圖 5 Cdata04數(shù)據(jù)集的切分結(jié)果Fig.5 Segmentation result of Cdata04 data sets

圖 6 雙月數(shù)據(jù)集的切分結(jié)果Fig.6 Segmentation results of bi-monthly data sets

3.3 真實(shí)數(shù)據(jù)集

真實(shí)數(shù)據(jù)集選取zoo-uni, blanlance, solar-uni以及ecoli-uni等4個(gè)常用UCI真實(shí)數(shù)據(jù)集,見表1。用A，I評(píng)價(jià)不同算法在4個(gè)數(shù)據(jù)集上的聚類結(jié)果,見表2～3。數(shù)據(jù)加粗代表算法性能最優(yōu),數(shù)據(jù)加下劃線代表算法性能次優(yōu)。

表 1 真實(shí)數(shù)據(jù)集Tab.1 Real datasets

表 2 不同算法在多個(gè)數(shù)據(jù)集下的A值比較Tab.2 Comparison of A value of different algorithms in multiple data sets

表 3 不同算法在多個(gè)數(shù)據(jù)集下的I值比較Tab.3 Comparison fo I value of different algorithms in multiple data set

從表2～3可看出,本文ε-RSC算法對S直接聚類,有著良好的聚類效果。在實(shí)驗(yàn)的4個(gè)數(shù)據(jù)集以及2個(gè)評(píng)價(jià)指標(biāo)上,ε-RSC算法基本都比其他4種算法性能更優(yōu)。這主要是因?yàn)棣?RSC算法在構(gòu)造親和矩陣時(shí)很合理,且加上l2,1范數(shù)的約束,使得譜分析過程中,能夠從整體和局部綜合考慮,對數(shù)據(jù)合理切分。

4 結(jié) 語

本文提出了一種新的譜聚類方法ε-RSC,在構(gòu)造親和矩陣時(shí),采用ε-鄰域思想,加強(qiáng)了對數(shù)據(jù)局部信息的利用,并且對相似矩陣加上l2,1范數(shù)的約束,使得模型在聚類時(shí)可以更好地處理異常值。在多個(gè)數(shù)據(jù)集上的聚類結(jié)果均很好。后續(xù)將進(jìn)一步探究親和矩陣的構(gòu)造方法以及約束相似矩陣的方法。