1種魯棒的模糊聚類方法

湯 歡,胡恩良

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

聚類分析按照“物以類聚”的思想將無(wú)標(biāo)簽數(shù)據(jù)聚成不同的簇,實(shí)質(zhì)是發(fā)掘出數(shù)據(jù)間的聯(lián)系.隨著眾多學(xué)者的研究,許多聚類算法被相繼提出,FCM[1](fuzzy C-means clustering)就是最具代表的聚類算法.將C-means聚類[2]結(jié)合模糊集合理論,是C-means的完善,且被廣泛應(yīng)用.然而FCM聚類算法也有不足,例如：FCM缺乏魯棒機(jī)制,對(duì)噪聲點(diǎn)或野值點(diǎn)很敏感.其本質(zhì)原因在于：FCM聚類模型中的度量距離是歐氏距離的平方,故由噪音點(diǎn)或野值點(diǎn)導(dǎo)致的偏差會(huì)按“平方”幅度被放大,從而使得FCM缺乏魯棒性.為了增加魯棒性,文中采用“不帶平方”的距離來(lái)代替“平方”距離,以此來(lái)抑制由噪音點(diǎn)或野值點(diǎn)導(dǎo)致的偏差被放大.“不帶平方”的距離導(dǎo)致了非光滑的FCM,不能用原有的EM(expectation maximization)算法進(jìn)行求解,為此采用了MM(majorization minimization)優(yōu)化方法.實(shí)驗(yàn)結(jié)果表明,與傳統(tǒng)FCM算法相比,RFCM具有更好的聚類性能.

1 FCM及魯棒性分析

1.1 FCM算法

FCM聚類是硬聚類C-means的1種改進(jìn)和推廣.通過(guò)引入模糊集合理論[3],將HCM算法中隸屬度矩陣推廣到模糊隸屬度矩陣.FCM算法根據(jù)模糊隸屬度矩陣U,計(jì)算每個(gè)樣本點(diǎn)隸屬于某個(gè)類的隸屬度uij∈[0,1].從而進(jìn)行聚類.該算法最早由Bezdek[1]提出,將數(shù)據(jù)集X分成c個(gè)模糊類.采用“類內(nèi)加權(quán)平方和最小化”的準(zhǔn)則確定目標(biāo)函數(shù),形式如下：

(1)

在(1)式中,V={v1,v2,…,vc}為聚類中心,U=[uij]n×cFCM隸屬度矩陣.uij表示樣本xi對(duì)類vj的隸屬度,m表示模糊指數(shù)(m越大模糊程度越高).特別地,若在(1)式中定義隸屬度uij：

(2)

則式(1)就退變成C-means的目標(biāo)函數(shù).

(3)

(4)

1.2 魯棒性分析

FCM聚類模型中的度量距離是歐氏距離的平方,故由噪音點(diǎn)或野值點(diǎn)[7]導(dǎo)致的偏差會(huì)按“平方”幅度被放大,從而使得FCM缺乏魯棒性.在模型(1)中,若xi是1個(gè)野值點(diǎn),則它到聚類中心vj的偏差按平方“‖xi-vj2‖”增長(zhǎng)得很大,從而統(tǒng)治了非野值點(diǎn)對(duì)應(yīng)的項(xiàng).雖然“距離平方”帶來(lái)FCM的光滑性,方便了后續(xù)的求導(dǎo)運(yùn)算,但這也將造成FCM對(duì)野值點(diǎn)很敏感,缺乏魯棒性.

2 RFCM:1種魯棒的FCM模型

2.1 模型建立

(5)

對(duì)比問(wèn)題(5)和(1)的2個(gè)模型,很容易看出：

2.2 MM優(yōu)化方法[5](majorization-minimization)

MM算法是1種迭代優(yōu)化方法,它利用函數(shù)的凸性來(lái)找到原函數(shù)最小值.且EM算法是MM算法的1個(gè)特例.當(dāng)目標(biāo)函數(shù)較難優(yōu)化時(shí),MM算法找到易于優(yōu)化的上界函數(shù)逼近于原目標(biāo)函數(shù).即每一次迭代找到1個(gè)原目標(biāo)函數(shù)的上界函數(shù),再求上界函數(shù)的最小值.

若滿足：(i)g(θ|θ(t))≥f(θ) ?θ; (ii)g(θ(t)|θ(t))=f(θ(t)),則g(θ|θ(t))就可作為f(θ)在θt處的代理函數(shù)或上界函數(shù).在MM算法中,通過(guò)最小化g(θ|θ(t))而不是實(shí)際函數(shù)f(θ)來(lái)尋求下1個(gè)迭代點(diǎn).MM算法是1種單調(diào)下降算法,即如果θ(t+1)為g(θ|θ(t))的最小值,則有：

f(θ(t+1))=g(θ(t+1)|θ(t))+f(θ(t+1))-g(θ(t+1)|θ(t))≤g(θ(t)|θ(t))+0=f(θ(t)).

2.3 RFCM模型的求解

定理1：(i)S(V,U|U(t))≥JRFCM(V,U)；(ii)S(V,U(t)|U(t))≥JRFCM(V,U(t)),其中

(6)

基于上界函數(shù)S(V,U),利用EM算法進(jìn)行交替優(yōu)化求解U和V.模糊聚類的隸屬度矩陣U與聚類中心V更新公式都可求出封閉解.迭代序列如下：

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

該求解過(guò)程可整理成如下算法1.

算法1： RFCM求解

輸入：數(shù)據(jù)集X,聚類別數(shù)c,聚類中心V(0),模糊指數(shù)m,最大迭代次數(shù)tmax,閾值ε,t=0.

輸出：隸屬度矩陣U*.

Step 1 更新模糊劃分矩陣:

(7)

Step 2 更新聚類中心向量:

(8)

3 實(shí)驗(yàn)結(jié)果與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)描述及信息

本文選取12個(gè)數(shù)據(jù)集(具體信息如表1)進(jìn)行實(shí)驗(yàn).它們分別是Blood,chessboard,CMC,Bupa, cancer, seed, Vechicle, WDBC, heart, iris, sonar和wine,均來(lái)自UCI數(shù)據(jù)集[6].

3.2 聚類純度對(duì)比及分析

表2中,我們?cè)?2組數(shù)據(jù)集上對(duì)FCM和RFCM的聚類純度[7]進(jìn)行了對(duì)比.從表中可看出：除了在數(shù)據(jù)seed上RFCM聚類純度比FCM稍微低點(diǎn),在大部分?jǐn)?shù)據(jù)上RFCM的聚類純度都比FCM的聚類純度高或者相等.而在數(shù)據(jù)集chessboard、iris上RFCM比FCM優(yōu)勢(shì)明顯突出.

表1 RFCM數(shù)據(jù)集及相關(guān)信息

表2 RFCM與FCM在數(shù)據(jù)集上聚類純度對(duì)比

表2中的結(jié)果分析：

2) 在seed數(shù)據(jù)集上,聚類純度RFCM沒有FCM方法高,其原因可能是該樣本不同類(簇)上數(shù)據(jù)分布相對(duì)集中,或者受到模糊指數(shù)m的影響.

3.3 模糊指數(shù)m的選擇

圖3中,在4組數(shù)據(jù)集(wine、WDBC、chessboard、iris)上,通過(guò)選取不同的模糊指數(shù)m,對(duì)FCM和RFCM聚類純度進(jìn)行了對(duì)比.從表中可看出：FCM和RFCM聚類算法在m≥2時(shí),聚類純度都得到大幅度提高,且聚類純度RFCM都要比FCM高,表現(xiàn)相對(duì)穩(wěn)定.特別的,m=2,2.5時(shí),RFCM總體效果較好.

4 結(jié)語(yǔ)

為了提高聚類效果,本文提出了1種魯棒的FCM聚類算法RFCM.在RFCM中,我們將FCM的目標(biāo)函數(shù)中度量樣本到類(簇)中心的“平方”距離,替換成一般的“非平方”距離.其作用很大程度縮短了樣本中噪音或野值點(diǎn)到類中心的距離,從而降低了野值點(diǎn)對(duì)類中心的影響,有更好的魯棒性.通過(guò)實(shí)驗(yàn)結(jié)果可得出,RFCM方法比FCM具有更高的聚類純度.未來(lái)工作中,可以進(jìn)一步引入圖論的知識(shí)來(lái)提高聚類性能.