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

朱樂為,胡恩良

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

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

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

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

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

1 平衡化模糊C-means聚類

1.1 模糊C-means聚類分析

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

(1)

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

(2)

(3)

1.2 模糊C-means聚類中的“均勻效應”

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

(4)

(5)

(6)

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

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

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

(7)

(8)

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

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

(9)

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

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

2.1 模型建立

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

(10)

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

2.2 SBFCM模型求解

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

令

化簡可得vj的閉式解為

(11)

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

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

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

算法1SBFCM求解算法

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

repeat

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

.

Step 2 更新聚類中心：

Step 3t=t+1

until

輸出U=U(t).

3 實驗與分析

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

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

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

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

(12)

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

聚類實驗將FCM、BFCM和SBFCM 3種方法進行對比，利用各自輸出的聚類純度來比較各個方法的聚類性能，聚類純度越高，對應的方法越好.

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

3.2 聚類效果分析

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

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

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

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

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

4 結語

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