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

2、集合概念上的x Ao 一個定義在空間X=x上的隸屬度函數就定義了一個模糊集合A，或者叫定義在論域 X=x上的模糊子集A。對于有限個對象 xi, x2,，xn模糊集合A可以表示為： A =(a(*), x) " X(6.1)有了模糊集合的概念，一個元素隸屬于模糊集合就不是硬性的了，在聚類的問題中，可以把聚類生成的簇看成模糊集合，因此，每個樣本點隸屬于簇的隸屬度就是0, 1區間里面的值。6.1.2 K均值聚類算法(HCM)介紹K均值聚類，即眾所周知的C均值聚類，已經應用到各種領域。它的核心思想如下：算法把n個向量 為(1,2,n)分為c個組Gi(i=1,2,c),并求每組的聚類中心，使得

3、非相似性(或距離)指標的價值函數(或目標函數)達到最小。當選擇歐幾里德距離為組j中向量xk與相應聚類中心Ci間的非相似性指標時，價值函數可定義為：CC2J = Ji 二 L ( ' | xk -Ci | )(6.2)C這里Ji =£ ( £ | xk -c |2)是組i內的價值函數。這樣 Ji的值依賴于 Gi的幾何特性和Ci 的位置。一般來說，可用一個通用距離函數 d(xk,Ci)代替組I中的向量xk,則相應的總價值函數可 表小為:CCJ = ' Ji = ' ( ' d(xk -。)(6.3)為簡單起見，這里用歐幾里德距離作為向量的非相似性

4、指標，且總的價值函數表示為 (6.2)式。劃分過的組一般用一個 c x n的二維隸屬矩陣 U來定義。如果第j個數據點xj屬于組i, 則U中的元素Uj為1;否則，該元素取 0。一旦確定聚類中心 ci,可導出如下使式(6.2) 最小Uij :1對每個 k # i,如果 |x j - cxj -ck2Uij = <II J11 j(6.4)1°其它重申一點，如果Ci是Xj的最近的聚類中心，那么 Xj屬于組io由于一個給定數據只能屬 于一個組，所以隸屬矩陣U具有如下性質：C'、'Uij =1,-j =1,.,n©5）i 4且c n' ' Uij

5、 =n（6.6）i 4 j _1另一方面，如果固定 Uij則使（6.2）式最小的最佳聚類中心就是組I中所有向量的均值：Ci =孔 £ Xk ，（6.7）Gi k,Xk Gi這里|Gi|是Gi的規模或Gi =£：_"。為便于批模式運行，這里給出數據集Xi （1, 2，n）的K均值算法；該算法重復使用下列步驟，確定聚類中心Ci和隸屬矩陣U:步驟1:初始化聚類中心 Ci,i=1, ,*典型的做法是從所有數據點中任取c個點。步驟2:用式（6.4）確定隸屬矩陣 U。步驟3:根據式（6.2）計算價值函數。如果它小于某個確定的閥值，或它相對上次價值 函數質的改變量小于某個閥值，

6、則算法停止。步驟4:根據式（6.5）修正聚類中心。返回步驟 2。該算法本身是迭代的，且不能確保它收斂于最優解。K均值算法的性能依賴于聚類中心 的初始位置。所以，為了使它可取，要么用一些前端方法求好的初始聚類中心；要么每次用不同的初始聚類中心，將該算法運行多次。此外，上述算法僅僅是一種具有代表性的方法； 我們還可以先初始化一個任意的隸屬矩陣，然后再執行迭代過程。K均值算法也可以在線方式運行。這時，通過時間平均，導出相應的聚類中心和相應的組。即對于給定的數據點 X,該算法求最近的聚類中心Ci,并用下面公式進行修正：=C = （x - ci）（6.8）這種在線公式本質上嵌入了許多非監督學習神經元網絡

7、的學習法則。6.2.3 模糊C均值聚類模糊C均值聚類（FCM ），即眾所周知的模糊 ISODATA,是用隸屬度確定每個數據點 屬于某個聚類的程度的一種聚類算法。1973年，Bezdek提出了該算法，作為早期硬C均值聚類（HCM ）方法的一種改進。FCM把n個向量Xi （i=1,2，,n）分為c個模糊組，并求每組的聚類中心，使得非相似 性指標的價值函數達到最小。FCM與HCM的主要區別在于 FCM用模糊劃分，使得每個給定數據點用值在 0, 1間的隸屬度來確定其屬于各個組的程度。與引入模糊劃分相適應，隸 屬矩陣U允許有取值在0, 1間的元素。不過，加上歸一化規定，一個數據集的隸屬度的和 總等于1

8、:CUij =1, -j =1,., n（6.9）i ±那么，FCM的價值函數（或目標函數）就是式（6.2）的一般化形式：J（U ,C1,., Cc） =£ Ji =£ Z um" ,（6.10）i _1i _1 j這里uij介于0, 1間；Ci為模糊組I的聚類中心，dij=|c-xj|為第I個聚類中心與第j個數據點 間的歐幾里德距離；且 m在1,叫 廬一個加權指數。c n"二 j4 jC Uij -1)nc.，j (、 Uij -1) j A(6.11)構造如下新的目標函數，可求得使（6.10）式達到最小值的必要條件:J (U ,c1 ,.,

9、 cc, ',., ，n) =J(U ,c1 ,., cc nm 2-u ijd iji皂j這里j(6.10)對所有輸入參量求導，使式(6.12)(6.13)j=1到n,是（6.9）式的n個約束式的拉格朗日乘子。 達到最小的必要條件為：n. mUij Xjcij日nm Uijj i1u =ijc d 2/(m)k i dkj由上述兩個必要條件，模糊 C均值聚類算法是一個簡單的迭代過程。在批處理方式運行時，FCM用下列步驟確定聚類中心ci和隸屬矩陣U1:步驟1:用值在0, 1間的隨機數初始化隸屬矩陣U,使其滿足式（6.9）中的約束條件步驟2：用式（6.12）計算c個聚類中心ci, i=1

10、, -,c。步驟3:根據式（6.10）計算價值函數。如果它小于某個確定的閥值，或它相對上次價 值函數值的改變量小于某個閥值，則算法停止。步驟4:用（6.13）計算新的U矩陣。返回步驟 2。上述算法也可以先初始化聚類中心，然后再執行迭代過程。由于不能確保FCM收斂于一個最優解。算法的性能依賴于初始聚類中心。因此，我們要么用另外的快速算法確定初始聚類中心，要么每次用不同的初始聚類中心啟動該算法，多次運行FCM。6.2.4 FCM算法的應用通過上面的討論，我們不難看出 FCM算法需要兩個參數一個是聚類數目 C,另一個是 參數m。一般來講 C要遠遠小于聚類樣本的總個數，同時要保證C>1。對于m,它是一個控制算法的柔性的參數，如果m過大，則聚類效果會很次，而如果m過小則算法會接近 HCM 聚類算法。算法的輸出是C個聚類中心點向量和 C