蘇揚(yáng)， 胡恩良

(云南師范大學(xué) 數(shù)學(xué)學(xué)院，云南 昆明 650500)

1 引言

譜聚類(lèi)(Spectral Clustering，SPC)是一種基于圖論的聚類(lèi)方法，其本質(zhì)是將聚類(lèi)問(wèn)題轉(zhuǎn)化為求解Laplacian 矩陣或相似矩陣的譜分解問(wèn)題.與傳統(tǒng)聚類(lèi)算法相比，譜聚類(lèi)能夠在任意形狀樣本分布上聚類(lèi)且收斂于全局最優(yōu)解[1].處理數(shù)據(jù)時(shí)，譜聚類(lèi)僅需要構(gòu)建樣本點(diǎn)之間的相似度矩陣，這對(duì)處理高維數(shù)據(jù)聚類(lèi)具有一定優(yōu)勢(shì).近年來(lái)，譜聚類(lèi)算法獲得了持續(xù)改進(jìn)和發(fā)展，例如：針對(duì)譜聚類(lèi)中的相似度測(cè)量問(wèn)題，Tasdemir等人[2]提出了一種基于測(cè)地線距離的混合相似性度量方法，應(yīng)用不同類(lèi)型的信息來(lái)表示數(shù)據(jù)點(diǎn)間的相似度；Wang等人[3]提出了一種譜多流形聚類(lèi)算法(Spectral Multi-Manifold Clustering，SMMC)；Zhang 等人[4]提出了基于隨機(jī)游走來(lái)建立 Gaussian核相似矩陣.但要解決任意形狀樣本分布的數(shù)據(jù)聚類(lèi)問(wèn)題，迄今為止已提出的算法都是不完美的，譜聚類(lèi)也不例外.

傳統(tǒng)譜聚類(lèi)隱含了各簇?cái)?shù)據(jù)點(diǎn)數(shù)量分布較均衡的假設(shè)，即要求所選各簇之間的數(shù)據(jù)點(diǎn)數(shù)量差異不大.因此對(duì)各簇間樣本點(diǎn)數(shù)相差懸殊的類(lèi)不平衡問(wèn)題，傳統(tǒng)譜聚類(lèi)將不再適用.針對(duì)類(lèi)不平衡問(wèn)題，劉富等人[5]提出了一種基于聚類(lèi)體量約束的模糊c-harmonic均值算法，劉歡等人[6]改進(jìn)了EM聚類(lèi)算法，王舒梵等人[7]構(gòu)建了高斯混合模型聚類(lèi)的SMOTE過(guò)采樣算法.然而，這些算法雖然提高了數(shù)據(jù)集類(lèi)不平衡問(wèn)題的聚類(lèi)性能，但在處理高維數(shù)據(jù)集時(shí)容易產(chǎn)生“維數(shù)災(zāi)難”現(xiàn)象，導(dǎo)致聚類(lèi)質(zhì)量降低.為此，本文提出了一種新的平衡化譜聚類(lèi)算法(Balanced Spectral Clustering，BSPC)，該算法考慮譜聚類(lèi)算法的基本特性融入了隸屬度矩陣的近似正交約束，在克服“均勻效應(yīng)”[8]問(wèn)題的同時(shí)保證了結(jié)果的準(zhǔn)確性.

2 平衡化譜聚類(lèi)

2.1 譜聚類(lèi)分析

(1)

2.2 平衡化譜聚類(lèi)

(2)

在模型(2)中：

i)約束“Fi.∈Δk,?i∈[n]={1,…,n}”僅使得數(shù)據(jù)點(diǎn)對(duì)各個(gè)聚類(lèi)中心的隸屬度之和為1，而對(duì)各類(lèi)樣本點(diǎn)的隸屬度總和沒(méi)有限制，由此在處理非平衡數(shù)據(jù)時(shí)，極易使“大類(lèi)”樣本的隸屬度總和過(guò)高，“小類(lèi)”樣本的隸屬度總和過(guò)低，這便導(dǎo)致了“均勻效應(yīng)”.因此需要對(duì)大類(lèi)和小類(lèi)的隸屬度總和施加“平衡”約束；

ii)約束“FTF=I”對(duì)隸屬度矩陣施加正交約束“平衡”大類(lèi)和小類(lèi)的隸屬度總和[9].直觀的，若約束隸屬度矩陣F滿足近似正交(FTF≈I)，記F·p表示F的第P列，則

(3)

(4)

2.3 模型求解

為了求解問(wèn)題(2)，利用文獻(xiàn)[10]中的跡懲罰函數(shù)，將問(wèn)題(2)轉(zhuǎn)化為

(5)

其中μ是罰參數(shù).經(jīng)過(guò)計(jì)算可知，(5)式等價(jià)于

(6)

(7)

由于問(wèn)題(7)中的目標(biāo)函數(shù)是二次函數(shù)，所以可考慮利用Gauss-Newton(GN)法對(duì)其求解[11].記S(Ft)為g(F)在點(diǎn)Ft處的GN方向，則GN迭代格式為

Ft+1=Ft+αtS(Ft).

(8)

根據(jù)文獻(xiàn)[10]， 計(jì)算問(wèn)題(7)的GN方向解析表達(dá)式，即

(9)

至此，平衡化譜聚類(lèi)模型的近似問(wèn)題(5)的求解算法可歸納為如下算法.

算法 平衡化譜聚類(lèi)(BSPC)

輸入：Laplacian矩陣L，期望的聚類(lèi)數(shù)k，罰參數(shù)μ，最大迭代次數(shù)T，終止精度ε.

輸出:聚類(lèi)隸屬度矩陣F*.

step1 :設(shè)置t=0，初始點(diǎn)F0;

step2 :根據(jù)(9)式計(jì)算GN方向

St=S(Ft);

step3 :利用線搜索求St方向的歩長(zhǎng)αt，根據(jù)(8)式更新F為

Ft+1=Ft+αtSt;

輸出F*=Ft+1.

3 實(shí)驗(yàn)與分析

3.1 數(shù)據(jù)集選取

分別在模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上驗(yàn)證BSPC算法的有效性.模擬數(shù)據(jù)集共4個(gè)，分別由具有二維高斯分布的類(lèi)不平衡數(shù)據(jù)點(diǎn)構(gòu)建，每個(gè)數(shù)據(jù)集包含300個(gè)樣本點(diǎn)，其中大尺寸類(lèi)樣本點(diǎn)和小尺寸類(lèi)樣本點(diǎn)的比例依次為9∶1(D1)、8∶2(D2)、7∶3(D3)和 6∶4(D4).真實(shí)數(shù)據(jù)集選用具有不同實(shí)際應(yīng)用背景的UCI數(shù)據(jù)集，從中選取Chessboard、Spiral、Protein、Glass、 Heart、Cancer和CMC共7組數(shù)據(jù)作為測(cè)試集，所有數(shù)據(jù)集均經(jīng)過(guò)類(lèi)不平衡化處理，即各類(lèi)的樣本比例作了設(shè)置(如表1).

表1 實(shí)驗(yàn)所用數(shù)據(jù)集及其相關(guān)信息

3.2 性能評(píng)價(jià)指標(biāo)

在實(shí)驗(yàn)中，設(shè)置期望聚類(lèi)數(shù)等于數(shù)據(jù)集真實(shí)類(lèi)別數(shù).由于所選數(shù)據(jù)集都有真實(shí)的類(lèi)標(biāo)號(hào)，可將其作為聚類(lèi)結(jié)果的基準(zhǔn).采用聚類(lèi)純度(Cluster Purity，CP)[11]來(lái)衡量聚類(lèi)效果，CP定義如下：

(10)

其中，n為樣本總數(shù)，njl為真實(shí)第j類(lèi)中與聚類(lèi)輸出為第l中所含相同樣本數(shù).CP定義是將每個(gè)聚類(lèi)標(biāo)號(hào)對(duì)應(yīng)于與其含有相同樣本數(shù)最多的真實(shí)類(lèi)標(biāo)號(hào)，這k類(lèi)中相同樣本數(shù)之和與樣本總數(shù)的占比，便是聚類(lèi)純度.聚類(lèi)純度越高且越接近1，表明聚類(lèi)效果越好.

圖1 在Chessboard數(shù)據(jù)集上的收斂性Fig.1 Convergence on the Chessboard dataset

3.3 實(shí)驗(yàn)結(jié)果及分析

在Chessboard數(shù)據(jù)集上運(yùn)行BSPC算法，由圖1的算法迭代圖可知，BSPC算法的目標(biāo)函數(shù)值具有迭代收斂性.

為了驗(yàn)證本文算法的聚類(lèi)效果，使用SPC算法[1]與本文算法進(jìn)行比較，在所有測(cè)試數(shù)據(jù)集上，分別以不同的初始點(diǎn)運(yùn)行30次，并在表2中報(bào)告平均聚類(lèi)純度和標(biāo)準(zhǔn)差.可以看出，在多數(shù)情況下BSPC能獲得更大的CP值.這是因?yàn)椋孩?BSPC在SPC的基礎(chǔ)上加入了正交約束項(xiàng)，使得大尺寸類(lèi)的樣本聚類(lèi)隸屬度降低，小尺寸類(lèi)樣本的聚類(lèi)隸屬度升高，從而緩解了聚類(lèi)算法在不平衡數(shù)據(jù)上容易導(dǎo)致的均勻效應(yīng)；②正交約束提高了類(lèi)(簇)間的分離性.

圖2 在Chessboard數(shù)據(jù)集上的聚類(lèi)效果Fig.2 Clustering effect on chessboard dataset

圖2中顯示SPC算法和BSPC算法在Chessboard數(shù)據(jù)集上的聚類(lèi)結(jié)果，可看出BSPC更好地緩解了均勻效應(yīng)，提高了各類(lèi)(簇)間的分離性.

4 結(jié)語(yǔ)

在傳統(tǒng)譜聚類(lèi)的基礎(chǔ)上提出了一種新的平衡化譜聚類(lèi)模型，該模型在譜聚類(lèi)的基礎(chǔ)上加入了對(duì)聚類(lèi)隸屬度矩陣的正交約束，在11個(gè)不平衡數(shù)據(jù)集上的測(cè)試實(shí)驗(yàn)結(jié)果表明，提出的新算法相比于傳統(tǒng)譜聚類(lèi)具有更好的聚類(lèi)效果.