朱恒東,馬盈倉,楊 婷,張 要
(西安工程大學(xué) 理學(xué)院,陜西 西安 710048)
聚類[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)。
譜聚類的原理是首先利用樣本數(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)
使用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是對角矩陣,對角元素為
譜聚類原始目標(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í)的相似矩陣。
將式(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é)果。
根據(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è)連通分支聚類。
為驗(yàn)證算法有效性,將本文ε-RSC算法與K均值(K-means)算法、LRR方法、SR方法以及文獻(xiàn)[22]中CLR-L方法進(jìn)行對比,數(shù)據(jù)集選取人造數(shù)據(jù)集和真實(shí)數(shù)據(jù)集。
以聚類準(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)
人造數(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
真實(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ù)合理切分。
本文提出了一種新的譜聚類方法ε-RSC,在構(gòu)造親和矩陣時(shí),采用ε-鄰域思想,加強(qiáng)了對數(shù)據(jù)局部信息的利用,并且對相似矩陣加上l2,1范數(shù)的約束,使得模型在聚類時(shí)可以更好地處理異常值。在多個(gè)數(shù)據(jù)集上的聚類結(jié)果均很好。后續(xù)將進(jìn)一步探究親和矩陣的構(gòu)造方法以及約束相似矩陣的方法。