FCM聚類算法介紹

1、FCM聚類算法介紹FCM算法是一種基于劃分的聚類算法，它的思想就是使得被劃分到同一簇的對(duì)象之間 相似度最大，而不同簇之間的相似度最小。模糊C均值算法是普通 C均值算法的改進(jìn)，普通C均值算法對(duì)于數(shù)據(jù)的劃分是硬性的， 而FCM則是一種柔性的模糊劃分。在介紹 FCM具體算法之前我們先介紹一些模糊集合的 基本知識(shí)。6.1.1 模糊集基本知識(shí)21首先說明隸屬度函數(shù)的概念。隸屬度函數(shù)是表示一個(gè)對(duì)象x隸屬于集合A的程度的函數(shù)，通常記做H A(x)，其自變量范圍是所有可能屬于集合A的對(duì)象(即集合 A所在空間中的所有點(diǎn))，取值范圍是0,1,即0<=1 , H A(x)<=1。 A(x)=1表示X完全

2、隸屬于集合 A,相 當(dāng)于傳統(tǒng)集合概念上的 x A。一個(gè)定義在空間 X=x上的隸屬度函數(shù)就定義了一個(gè)模糊集 合A ,或者叫定義在論域 X=x上的模糊子集 A。對(duì)于有限個(gè)對(duì)象x1 , 乂2, , xn模糊集合A可以表示為： A=(七3),為)|" X(6.1)有了模糊集合的概念， 一個(gè)元素隸屬于模糊集合就不是硬性的了，在聚類的問題中，可以把聚類生成的簇看成模糊集合，因此，每個(gè)樣本點(diǎn)隸屬于簇的隸屬度就是0, 1區(qū)間里面的值。6.1.2 K均值聚類算法(HCM)介紹K均值聚類，即眾所周知的C均值聚類，已經(jīng)應(yīng)用到各種領(lǐng)域。它的核心思想如下：算法把n個(gè)向量為(1,2,n)分為c個(gè)組Gi(i=1,

3、2,c),并求每組的聚類中心，使得非相似性 (或距離)指標(biāo)的價(jià)值函數(shù)(或目標(biāo)函數(shù))達(dá)到最小。當(dāng)選擇歐幾里德距離為組j中向量xk與相應(yīng)聚類中心q間的非相似性指標(biāo)時(shí)，價(jià)值函數(shù)可定義為： ccJ = ' Ji 八(' |xk-G|2)(6.2)c這里Ji =£ ( £ |xk G |2)是組i內(nèi)的價(jià)值函數(shù)。這樣Ji的值依賴于Gi的幾何特性和g的位置。般來說，可用一個(gè)通用距離函數(shù)d(xk,ci)代替組I中的向量xk, 則相應(yīng)的總價(jià)值函數(shù)可表小為:ccJ = ' Ji = ' ( ' d(xk -g)(6.3)為簡單起見，這里用歐幾里德距離作為

4、向量的非相似性指標(biāo)，且總的價(jià)值函數(shù)表示為 (6.2)式。劃分過的組一般用一個(gè) cx n的二維隸屬矩陣U來定義。如果第j個(gè)數(shù)據(jù)點(diǎn) 為屬于組i,則U中的元素Uj為1;否則，該元素取 0。一旦確定聚類中心 M ,可導(dǎo)出如下使式(6.2)最小Uij :1 對(duì)每個(gè) k , i,如果 |xj - v <| xj - v2,Uk =(6.4)0 其它重申一點(diǎn)，如果 Vi是Xj的最近的聚類中心，那么 Xj屬于組i。由于一個(gè)給定數(shù)據(jù)只能屬于一個(gè)組，所以隸屬矩陣 U具有如下性質(zhì)：c' Uij =1,j=1,.,n(6.5)i A且c n1 .1 Uij = n(6.6)舊j日另一方面，如果固定 Uj

5、則使(6.2)式最小的最佳聚類中心就是分組i中所有向量的均值：vi =£ Xk '(6.7)Gi k,Xk Gi、一 一 一 一 n這里Gi是Gi的規(guī)模或Gi =£ jUij。為便于批模式運(yùn)行，這里給出數(shù)據(jù)集Xi (1, 2，n)的K均值算法；該算法重復(fù)使用下列步驟，確定聚類中心G和隸屬矩陣U:步驟1:初始化聚類中心Ci,i=1,.,c。典型的做法是從所有數(shù)據(jù)點(diǎn)中任取c個(gè)點(diǎn)。步驟2:用式(6.4)確定隸屬矩陣 U。步驟3:根據(jù)式(6.2)計(jì)算價(jià)值函數(shù)。如果它小于某個(gè)確定的閥值，或它相對(duì)上次價(jià)值 函數(shù)質(zhì)的改變量小于某個(gè)閥值，則算法停止。步驟4:根據(jù)式(6.5)修正聚類

6、中心。返回步驟2。該算法本身是迭代的，且不能確保它收斂于最優(yōu)解。K均值算法的性能依賴于聚類中心 的初始位置。所以，為了使它可取，要么用一些前端方法求好的初始聚類中心；要么每次用 不同的初始聚類中心，將該算法運(yùn)行多次。此外，上述算法僅僅是一種具有代表性的方法； 我們還可以先初始化一個(gè)任意的隸屬矩陣，然后再執(zhí)行迭代過程。K均值算法也可以在線方式運(yùn)行。這時(shí)，通過時(shí)間平均，導(dǎo)出相應(yīng)的聚類中心和相應(yīng)的組。即對(duì)于給定的數(shù)據(jù)點(diǎn) X,該算法求最近的聚類中心G,并用下面公式進(jìn)行修正：G = (XG)(6.8)這種在線公式本質(zhì)上嵌入了許多非監(jiān)督學(xué)習(xí)神經(jīng)元網(wǎng)絡(luò)的學(xué)習(xí)法則。6.2.3 模糊C均值聚類模糊C均值聚類(F

7、CM )，即眾所周知的模糊ISODATA ,是用隸屬度確定每個(gè)數(shù)據(jù)點(diǎn)屬于某個(gè)聚類的程度的一種聚類算法。1973年，Bezdek提出了該算法，作為早期硬 C均值聚類(HCM )方法的一種改進(jìn)。FCM把n個(gè)向量Xi (i=1,2，,n)分為c個(gè)模糊組，并求每組的聚類中心，使得非相似 性指標(biāo)的價(jià)值函數(shù)達(dá)到最小。FCM與HCM的主要區(qū)別在于 FCM用模糊劃分，使得每個(gè)給定數(shù)據(jù)點(diǎn)用值在0, 1間的隸屬度來確定其屬于各個(gè)組的程度。與引入模糊劃分相適應(yīng)，隸 屬矩陣U允許有取值在0, 1間的元素。不過，加上歸一化規(guī)定，一個(gè)數(shù)據(jù)集的隸屬度的和 總等于1 :c二：Uij = 1, - j = 1,., n(6.9

8、)i日那么，F(xiàn)CM的價(jià)值函數(shù)(或目標(biāo)函數(shù))就是式(6.2)的一般化形式：cc nJ(U,g,.,Cc) =£ Ji =W £ Ujmdi2 ,(6.10)i=1i=1 j這里Uj介于0, 1間；g為模糊組I的聚類中心，dj=|ci-xj|為第I個(gè)聚類中心與第j個(gè)數(shù)據(jù)點(diǎn) 間的歐幾里德距離；且 m在1,叫)是一個(gè)加權(quán)指數(shù)。構(gòu)造如下新的目標(biāo)函數(shù)，可求得使(6.10)式達(dá)到最小值的必要條件：c n(6.11)(6.12)J(U,C1,.,C"1,.,，n) = J(U,G,.,Cc) "Jj(、Uij -1)c nnc=Uijmdj w jT Uij -1)i

9、A jj W i A這里j(6.10)j=1到n,是(6.9)式的n個(gè)約束式的拉格朗日乘子。對(duì)所有輸入?yún)⒘壳髮?dǎo)，使式 達(dá)到最小的必要條件為：n m Uij Xjj wG = n m Uijj日1Uij =2/(m J)(6.13)c +k m dkj由上述兩個(gè)必要條件，模糊C均值聚類算法是一個(gè)簡單的迭代過程。在批處理方式運(yùn)行時(shí)，F(xiàn)CM用下列步驟確定聚類中心ci和隸屬矩陣U1:步驟1:用值在0, 1間的隨機(jī)數(shù)初始化隸屬矩陣U,使其滿足式(6.9)中的約束條件步驟2：用式(6.12)計(jì)算c個(gè)聚類中心Ci, i=1,c。步驟3:根據(jù)式(6.10)計(jì)算價(jià)值函數(shù)。如果它小于某個(gè)確定的閥值，或它相對(duì)上次價(jià)

10、 值函數(shù)值的改變量小于某個(gè)閥值，則算法停止。步驟4:用(6.13)計(jì)算新的U矩陣。返回步驟 2。上述算法也可以先初始化聚類中心，然后再執(zhí)行迭代過程。由于不能確保 FCM收斂于 一個(gè)最優(yōu)解。算法的性能依賴于初始聚類中心。因此，我們要么用另外的快速算法確定初始聚類中心，要么每次用不同的初始聚類中心啟動(dòng)該算法，多次運(yùn)行FCM。6.2.4 FCM算法的應(yīng)用通過上面的討論，我們不難看出 FCM算法需要兩個(gè)參數(shù)一個(gè)是聚類數(shù)目 C,另一個(gè)是 參數(shù)m。一般來講 C要遠(yuǎn)遠(yuǎn)小于聚類樣本的總個(gè)數(shù)，同時(shí)要保證 C>1。對(duì)于m,它是一個(gè) 控制算法的柔性的參數(shù)，如果m過大，則聚類效果會(huì)很次，而如果m過小則算法會(huì)接近 HCM 聚類算法。算法的輸出是C個(gè)聚類中心點(diǎn)向量和 C*N的一個(gè)