蘇揚(yáng)， 胡恩良

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

1 引言

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

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

2 平衡化譜聚類

2.1 譜聚類分析

(1)

2.2 平衡化譜聚類

(2)

在模型(2)中：

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

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

(3)

(4)

2.3 模型求解

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

(5)

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

(6)

(7)

由于問題(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ì)算問題(7)的GN方向解析表達(dá)式，即

(9)

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

算法 平衡化譜聚類(BSPC)

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

輸出:聚類隸屬度矩陣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è)，分別由具有二維高斯分布的類不平衡數(shù)據(jù)點(diǎn)構(gòu)建，每個(gè)數(shù)據(jù)集包含300個(gè)樣本點(diǎn)，其中大尺寸類樣本點(diǎn)和小尺寸類樣本點(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ò)類不平衡化處理，即各類的樣本比例作了設(shè)置(如表1).

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

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

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

(10)

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

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

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

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

4 結(jié)語(yǔ)

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