朱樂為,胡恩良

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

聚類的目的是發(fā)掘樣本的類別標(biāo)記，進(jìn)而根據(jù)類標(biāo)記揭示數(shù)據(jù)的內(nèi)在結(jié)構(gòu)和規(guī)律.在聚類分析中，樣本的類別標(biāo)記信息未知，故聚類分析屬于“無監(jiān)督”學(xué)習(xí)方法.隨著聚類分析的發(fā)展，涌現(xiàn)出了多種優(yōu)秀的聚類算法，其中FCM[1](fuzzy C-means clustering)是一種被廣泛應(yīng)用的聚類算法.FCM作為K-means[2]的變體，在硬聚類的基礎(chǔ)上引入了模糊理論，在實(shí)際運(yùn)用中獲得了極大成功.

然而，對于非平衡數(shù)據(jù)，F(xiàn)CM的聚類效果并不理想.非平衡數(shù)據(jù)是指不同簇(類)所含樣本點(diǎn)數(shù)相差較大的數(shù)據(jù)集.其中，樣本數(shù)少的類稱為小類，樣本數(shù)多的類稱為大類.對于不平衡數(shù)據(jù)的研究首先源于有監(jiān)督機(jī)器學(xué)習(xí)分類，目前為止已產(chǎn)生了大量的研究成果，提出了許多富有成效的處理方法.主要包括：① 數(shù)據(jù)集的重構(gòu)，即通過欠采樣[3]或過采樣[4]將不平衡數(shù)據(jù)集轉(zhuǎn)換為平衡數(shù)據(jù)集；② 分類器算法[5]的修正，即對分類器權(quán)重進(jìn)行調(diào)整，使之對少數(shù)類敏感.在模糊聚類領(lǐng)域(無監(jiān)督分類)也存在著非平衡數(shù)據(jù)聚類問題，但是到目前為止，僅有少量研究對非平衡數(shù)據(jù)問題進(jìn)行探討.Noordam等[6]提出一種對聚類尺寸不敏感的模糊C-means算法，其方法是對于小類與大類設(shè)置不同的條件值；Wen等[7]提出廣義均衡FCM聚類算法，改進(jìn)了原FCM屬度表達(dá)式以抵消相異簇大小差異對聚類結(jié)果的影響.

上述方法可以在一定程度上解決非平衡問題，但也存在著一定的缺點(diǎn)：① 條件值為人為設(shè)定，不一定有利于聚類任務(wù)，在處理類較多的不平衡數(shù)據(jù)集時(shí)，該方法使得樣本對各個(gè)類的隸屬度都較小，減弱了算法的聚類能力；② 廣義均衡FCM算法在模糊指數(shù)m=1時(shí)無法判斷隸屬度系數(shù)迭代方程可解，不能保證通過交替迭代收斂到穩(wěn)定點(diǎn).除以上2點(diǎn)外，傳統(tǒng)的聚類算法屬于無監(jiān)督學(xué)習(xí)方法，沒有利用監(jiān)督信息，可能會(huì)產(chǎn)生聚類偏差.而在現(xiàn)實(shí)的聚類任務(wù)中，通常能獲得一些額外的先驗(yàn)信息，如部分樣本已帶類標(biāo)記.充分利用已知的部分標(biāo)記來協(xié)助聚類，能得到更好的聚類效果.

基于以上分析，本文提出一種半監(jiān)督的平衡化FCM聚類算法(簡記為SBFCM)，該算法在原FCM目標(biāo)函數(shù)的基礎(chǔ)上引入對聚類模糊隸屬度矩陣的近似正交約束和半監(jiān)督約束，其作用是：① 近似正交約束項(xiàng)迫使隸屬度矩陣近似正交，由此可根據(jù)簇的大小自動(dòng)調(diào)整數(shù)據(jù)點(diǎn)權(quán)重，這將增強(qiáng)聚類效果；② 半監(jiān)督約束則能夠利用已知的部分標(biāo)記信息來引導(dǎo)聚類.實(shí)驗(yàn)表明，SBFCM能夠較好地解決數(shù)據(jù)的類不平衡問題和有效利用部分標(biāo)記問題，可提高聚類精度.

1 平衡化模糊C-means聚類

1.1 模糊C-means聚類分析

FCM聚類 (fuzzy C-means clustering)方法作為C-means聚類的一種變體，它基于模糊劃分理論，通過優(yōu)化求解模糊隸屬度矩陣來獲得數(shù)據(jù)點(diǎn)的類別標(biāo)簽.對于FCM，其目標(biāo)函數(shù)形式如下：

(1)

則式(1)退化為C-means的目標(biāo)函數(shù).由此可知，F(xiàn)CM是對C-means的“軟化”.

(2)

(3)

1.2 模糊C-means聚類中的“均勻效應(yīng)”

FCM聚類方法在處理不平衡數(shù)據(jù)集時(shí)會(huì)傾向于產(chǎn)生大小相同的類(簇)，極易導(dǎo)致錯(cuò)誤的類(簇)劃分，該現(xiàn)象稱為“均勻效應(yīng)”.2012年，Xiong等[9]對“均勻效應(yīng)”的成因進(jìn)行了系統(tǒng)地分析：若假定數(shù)據(jù)集僅含2個(gè)類(簇)，則式(1)可改寫為：

(4)

(5)

(6)

這意味著若初始值差異較小，則v1,v2會(huì)隨著迭代次數(shù)增加趨向于重合，“均勻效應(yīng)”愈發(fā)明顯.

1.3 平衡化模糊C-means聚類算法

在FCM中，隸屬度系數(shù)的單純形約束條件為

(7)

(8)

在式(7)中，每個(gè)類(簇)所含樣本的隸屬度平方總和近似相等，這保證了各類間隸屬度總和的平衡.例如，設(shè)W=[wij]為原始隸屬度矩陣，考慮第p和q兩個(gè)類(簇)，設(shè)第p類(簇)所含樣本數(shù)遠(yuǎn)大于第q類(簇)所含樣本數(shù).若將W近似正交化變?yōu)閁，即W→U且UTU≈I，則第i個(gè)樣本點(diǎn)屬于類(簇)p的隸屬度變?yōu)椋?/p>

基于以上分析，將隸屬度矩陣的近似正交約束項(xiàng)融合到FCM目標(biāo)函數(shù)中，得到了平衡化模糊C-means聚類模型(BFCM)如下：

(9)

其中γ≥0為正交約束參數(shù).對比式(1)和式(9)可知，BFCM在FCM的基礎(chǔ)上要求隸屬度矩陣近似正交，在FCM目標(biāo)函數(shù)與隸屬度正交約束之間達(dá)到折中，以此解決非平衡數(shù)據(jù)上的聚類問題.

2 半監(jiān)督平衡化模糊C-means聚類

2.1 模型建立

傳統(tǒng)的聚類屬于無監(jiān)督學(xué)習(xí)，未能利用已有的先驗(yàn)信息(也稱為半監(jiān)督信息).但在現(xiàn)實(shí)中，通常能事先獲得部分類標(biāo)號(hào)信息，利用該信息可改善聚類效果.受文獻(xiàn)[12]啟發(fā)，我們在模型(9)的基礎(chǔ)上進(jìn)一步引入少量類標(biāo)記數(shù)據(jù)作為先驗(yàn)信息，即對隸屬度矩陣融入了半監(jiān)督約束項(xiàng)，得到半監(jiān)督平衡化模糊C-means聚類(SBFCM)模型如下：

(10)

其中，yij為樣本xi屬于第j類的類標(biāo)號(hào)，若該標(biāo)號(hào)已知，則yij=1，否則yij=0.特別地，若yij=0,?i，即表示沒有任何先驗(yàn)類標(biāo)號(hào)可用，此時(shí)SBFCM退化為BFCM.

2.2 SBFCM模型求解

由式(10)可知，SBFCM的目標(biāo)函數(shù)為雙變量非凸函數(shù)，適合利用EM算法進(jìn)行交替優(yōu)化求解.求解SBFCM中心更新公式，對vj求偏導(dǎo)可得：

令

化簡可得vj的閉式解為

(11)

另一方面，式(10)關(guān)于U的表達(dá)式較為復(fù)雜，不易求出uij的閉式解，故本文在EM迭代中采用投影梯度下降法求解隸屬度矩陣U.EM交替求解V和U可產(chǎn)生如下迭代序列：

V(0)→U(1)→V(1)…→U(t)→V(t)→…

該求解過程可整理成算法1.

算法1SBFCM求解算法

輸入部分類標(biāo)號(hào)yij，類別數(shù)c，平滑指數(shù)m，正交約束項(xiàng)系數(shù)γ，最大迭代次數(shù)T,終止閾值ε；

repeat

Step 1 利用投影梯度下降法求解隸屬度矩陣

.

Step 2 更新聚類中心：

Step 3t=t+1

until

輸出U=U(t).

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

3.1 數(shù)據(jù)集與聚類評價(jià)

本文共采用了9個(gè)數(shù)據(jù)集進(jìn)行試驗(yàn)，它們分別是sonar，chessboard，spiral，heart，iris，wine，soybean，glass和protein，均來自于UCI數(shù)據(jù)集，其信息詳細(xì)見表1.其中，soybean，glass，protein為非平衡數(shù)據(jù)集，其余為平衡數(shù)據(jù)集.

表1 數(shù)據(jù)集及其信息

聚類性能評價(jià)指標(biāo)通常分為2類：一類是將最終的聚類結(jié)果與某個(gè)給定的參考模型進(jìn)行比較，稱為“外部指標(biāo)”，例如聚類純度[13](cp，cluster purity)，jaccard系數(shù)[14]等；另一類是不利用任何參考模型而直接考察聚類結(jié)果，稱為“內(nèi)部指標(biāo)”，例如DB指數(shù)[14](davies-bouldin index)，Dunn指數(shù)[14](dunn index)等.由于本文所采用表1中數(shù)據(jù)集的真實(shí)類標(biāo)記已知，故我們將真實(shí)類標(biāo)記作為標(biāo)準(zhǔn)參考模型，然后將聚類純度作為評價(jià)指標(biāo)，其定義如下：

(12)

其中n為數(shù)據(jù)集中的樣本總數(shù)，njl為在參考模型中屬于第j類的樣本但被算法聚類為第l類的樣本數(shù)量.聚類純度指標(biāo)的設(shè)計(jì)思想是：對于參考模型中的每一類，選擇聚類后含該類標(biāo)記樣本數(shù)最多的簇作為該標(biāo)記對應(yīng)的聚類，每個(gè)聚類中與類標(biāo)記相同的樣本點(diǎn)數(shù)相加，除以總樣本數(shù)，即為聚類純度.

聚類實(shí)驗(yàn)將FCM、BFCM和SBFCM 3種方法進(jìn)行對比，利用各自輸出的聚類純度來比較各個(gè)方法的聚類性能，聚類純度越高，對應(yīng)的方法越好.

表2 FCM、BFCM和SBFCM獲得的聚類純度對比

3.2 聚類效果分析

表2的第2列、第3列和第4列分別給出了FCM、BFCM和SBFCM方法輸出的聚類純度，對SBFCM算法，在實(shí)驗(yàn)中隨機(jī)抽取10%的真實(shí)類標(biāo)記作為監(jiān)督信息.3者對比聚類純度最大者用粗體字顯示，從中可看出.

1) BFCM在9個(gè)數(shù)據(jù)集上的聚類純度均高于FCM，在數(shù)據(jù)集chessboard, iris和protein上的優(yōu)勢尤其顯著，其原因是：BFCM在FCM的基礎(chǔ)上加入了近似正交約束項(xiàng)，這使得大類的樣本隸屬度降低，小類樣本的隸屬度升高，從而抑制不同類(簇)中心點(diǎn)相互靠近，緩解了“均勻效應(yīng)”.此外，近似正交約束能使不同類(簇)樣本的隸屬度成近似正交關(guān)系，提高了類(簇)間的分離性.

2) SBFCM在9個(gè)數(shù)據(jù)集上的聚類純度均高于BFCM，在數(shù)據(jù)集chessboard, soybean和protein上的優(yōu)勢尤其明顯，其原因是：SBFCM在BFCM基礎(chǔ)上加入了半監(jiān)督約束項(xiàng)，利用少量已知的先驗(yàn)類標(biāo)記信息來引導(dǎo)聚類，從而提高了聚類效果.

3.3 監(jiān)督信息量對聚類效果的影響

為了考察不同監(jiān)督規(guī)模對SBFCM的影響，在數(shù)據(jù)集protein, heart, soybean和sonar上，圖1給出了SBFCM隨監(jiān)督信息量變化的聚類純度圖.在圖1的各子圖中，橫軸表示給定的類標(biāo)記數(shù)相對于總樣本數(shù)的比重，縱軸表示獲得的聚類純度.從4個(gè)子圖可以看出，隨著監(jiān)督標(biāo)記量的增加，SBFCM獲得的聚類純度也相應(yīng)提高.特別地，對soybean數(shù)據(jù)集，當(dāng)監(jiān)督標(biāo)記量為60%時(shí)，獲得的聚類純度已達(dá)100%.

4 結(jié)語

為探討在非平衡數(shù)據(jù)上的聚類問題，本文在FCM的基礎(chǔ)上提出了平衡化模糊聚類模型BFCM；為了進(jìn)一步利用已知類標(biāo)號(hào)更好地引導(dǎo)聚類，本文進(jìn)而提出了半監(jiān)督的平衡化模糊聚類模型SBFCM.SBFCM在FCM目標(biāo)函數(shù)的基礎(chǔ)上加入了對聚類模糊隸屬度矩陣的近似正交約束和半監(jiān)督約束，從而得到了新的聚類目標(biāo)函數(shù).在9個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，相比于FCM和BFCM，SBFCM具有更好的聚類效果.在未來的研究中，我們將進(jìn)一步探討如何更優(yōu)地選取SBFCM中的模型參數(shù).