?

? FCM 算法是一種基于劃分的聚類算法，它的思想就是使得被劃分到同一簇的對象之間相似度最大，而不同簇之間的相似度最小。模糊 C 均值算法是普通 C 均值算法的改進(jìn)，普通 C 均值算法對于數(shù)據(jù)的劃分是硬性的，而 FCM 則是一種柔性的模糊劃分。在介紹 FCM 具體算法之前我們先介紹一些模糊集合的基本知識。

1?模糊集基本知識

? 首先說明 隸屬度函數(shù) 的概念。隸屬度函數(shù)是表示一個對象 x 隸屬于集合 A 的程度的函數(shù)，通常記做 μA(x) ，其自變量范圍是所有可能屬于集合 A 的對象（即集合 A 所在空間中的所有點），取值范圍是 [0,1] ，即 0<=μ _A (x)<=1 。 μA(x)=1 表示 x 完全隸屬于集合 A ，相當(dāng)于傳統(tǒng)集合概念上的 x ∈A 。一個定義在空間 X={x} 上的隸屬度函數(shù)就定義了一個模糊集合 A ，或者叫定義在論域 X={x} 上的模糊子集 。對于有限個對象 x 1， x 2， …… ， x n模糊集合可以表示為：

??????????????

?? ? ?（6.1)

? 有了模糊集合的概念，一個元素隸屬于模糊集合就不是硬性的了，在聚類的問題中，可以把聚類生成的簇看成模糊集合，因此，每個樣本點隸屬于簇的隸屬度就是 [0 ， 1] 區(qū)間里面的值。

2?K 均值聚類算法 (HCM，K-Means) 介紹

? K 均值聚類（K-Means），即眾所周知的 C 均值聚類，已經(jīng)應(yīng)用到各種領(lǐng)域。它的核心思想如下：算法把 n 個向量 x j(1,2…,n) 分為 c 個組 G i(i=1,2,…,c) ，并求每組的聚類中心，使得非相似性（或距離）指標(biāo)的價值函數(shù)（或目標(biāo)函數(shù)）達(dá)到最小。當(dāng)選擇歐幾里德距離為組 j 中向量 x k與相應(yīng)聚類中心 c i間的非相似性指標(biāo)時，價值函數(shù)可定義為：

??????

?? ? ? ? ?(6.2)

? 這里是組 i 內(nèi)的價值函數(shù)。這樣 J i的值依賴于 G i的幾何特性和 c i的位置。

? 一般來說，可用一個通用距離函數(shù) d(x k,ci) 代替組 I中的向量 x k，則相應(yīng)的總價值函數(shù)可表示為：

???????

?? ? ? ? ? (6.3)

? 為簡單起見，這里用歐幾里德距離作為向量的非相似性指標(biāo)，且總的價值函數(shù)表示為（ 6.2 ）式。

? 劃分過的組一般用一個 c×n 的二維隸屬矩陣 U 來定義。如果第 j 個數(shù)據(jù)點 x j屬于組 i ，則 U 中的元素 u ij為 1 ；否則，該元素取 0 。一旦確定聚類中心 ci ，可導(dǎo)出如下使式（ 6.2 ）最小 u ij：

?

?? ? ? ?(6.4)

? 重申一點，如果 c i是 x j的最近的聚類中心，那么 x j屬于組 i 。由于一個給定數(shù)據(jù)只能屬于一個組，所以隸屬矩陣 U 具有如下性質(zhì)：

???????

?? ? ? ? ?(6.5)

且? ? ? ? ?

?? ? ? ? ? ? ? ? ? ?(6.6)

? 另一方面，如果固定 u ij則使（ 6.2 ）式最小的最佳聚類中心就是組 I中所有向量的均值：? ? ? ??

?? ? ? ? ? ? ? ? ? (6.7)

? 這里 |G i| 是 G i的規(guī)模或。

? 為便于批模式運行，這里給出數(shù)據(jù)集 x i（ 1 ， 2… ， n ）的 K 均值算法；該算法重復(fù)使用下列步驟，確定聚類中心 c i和隸屬矩陣 U ：

? 步驟 1 ：初始化聚類中心 c i,i=1,…,c 。典型的做法是從所有數(shù)據(jù)點中任取 c 個點。

? 步驟 2 ：用式（ 6.4 ）確定隸屬矩陣 U 。

? 步驟 3 ：根據(jù)式（ 6.2 ）計算價值函數(shù)。如果它小于某個確定的閥值，或它相對上次價值函數(shù)質(zhì)的改變量小于某個閥值，則算法停止。

? 步驟 4 ：根據(jù)式（ 6.5 ）修正聚類中心。返回步驟 2 。

? 該算法本身是迭代的，且不能確保它收斂于最優(yōu)解。 K 均值算法的性能依賴于聚類中心的初始位置。所以，為了使它可取，要么用一些前端方法求好的初始聚類中心；要么每次用不同的初始聚類中心，將該算法運行多次。此外，上述算法僅僅是一種具有代表性的方法；我們還可以先初始化一個任意的隸屬矩陣，然后再執(zhí)行迭代過程。

? K 均值算法也可以在線方式運行。這時，通過時間平均，導(dǎo)出相應(yīng)的聚類中心和相應(yīng)的組。即對于給定的數(shù)據(jù)點 x ，該算法求最近的聚類中心 c i，并用下面公式進(jìn)行修正：

?????????

?? ? ? ? ? ? ? ?(6.8)

? 這種在線公式本質(zhì)上嵌入了許多非監(jiān)督學(xué)習(xí)神經(jīng)元網(wǎng)絡(luò)的學(xué)習(xí)法則。

3??? 模糊 C 均值聚類

? 模糊 C 均值聚類 （ FCM ），即眾所周知的模糊 ISODATA ，是用隸屬度確定每個數(shù)據(jù)點屬于某個聚類的程度的一種聚類算法。 1973 年， Bezdek 提出了該算法，作為早期硬 C 均值聚類（ HCM ）方法的一種改進(jìn)。

? FCM 把 n 個向量 x i（i=1,2,…,n ）分為 c 個模糊組，并求每組的聚類中心，使得非相似性指標(biāo)的價值函數(shù)達(dá)到最小。 FCM 與 HCM 的主要區(qū)別在于 FCM 用模糊劃分，使得每個給定數(shù)據(jù)點用值在 0 ， 1 間的隸屬度來確定其屬于各個組的程度。與引入模糊劃分相適應(yīng)，隸屬矩陣 U 允許有取值在 0 ， 1 間的元素。不過，加上歸一化規(guī)定，一個數(shù)據(jù)集的隸屬度的和總等于 1 ： ? ? ? ? ?

? ? ? ? ? ? ?(6.9)

? 那么， FCM 的價值函數(shù)（或目標(biāo)函數(shù)）就是式（ 6.2 ）的一般化形式： ? ?

? ? ? ? ?? (6.10)

? 這里 u ij介于 0 ， 1 間； c i為模糊組I的聚類中心， d ij=||ci-xj|| 為第 I個聚類中心與第 j 個數(shù)據(jù)點間的歐幾里德距離；且 是一個加權(quán)指數(shù)。

? 構(gòu)造如下新的目標(biāo)函數(shù)，可求得使（ 6.10 ）式達(dá)到最小值的必要條件：

???

?? ? ? ? (6.11)

? 這里lj， j=1 到 n ，是（ 6.9 ）式的 n 個約束式的拉格朗日乘子。對所有輸入?yún)⒘壳髮?dǎo)，使式（ 6.10 ）達(dá)到最小的必要條件為：

? ? ? ???? ? ? ? ? ? ? ? (6.12)

和? ? ? ? ? ??

?? ? ? ? ?(6.13)

? 由上述兩個必要條件，模糊 C 均值聚類算法是一個簡單的迭代過程。在批處理方式運行時， FCM 用下列步驟確定聚類中心 c i和隸屬矩陣 U[1] ：

? 步驟 1 ：用值在 0 ， 1 間的隨機(jī)數(shù)初始化隸屬矩陣 U ，使其滿足式（ 6.9 ）中的約束條件

? 步驟 2 ：用式（ 6.12 ）計算 c 個聚類中心 c i， i=1, …,c 。

? 步驟 3 ：根據(jù)式（ 6.10 ）計算價值函數(shù)。如果它小于某個確定的閥值，或它相對上次價值函數(shù)值的改變量小于某個閥值，則算法停止。

? 步驟 4 ：用（ 6.13 ）計算新的 U 矩陣。返回步驟 2 。

? 上述算法也可以先初始化聚類中心，然后再執(zhí)行迭代過程。由于不能確保 FCM 收斂于一個最優(yōu)解。算法的性能依賴于初始聚類中心。因此，我們要么用另外的快速算法確定初始聚類中心，要么每次用不同的初始聚類中心啟動該算法，多次運行 FCM 。

4?FCM 算法的應(yīng)用

? 通過上面的討論，我們不難看出 FCM 算法需要兩個參數(shù)一個是聚類數(shù)目 C ，另一個是參數(shù) m 。一般來講 C 要遠(yuǎn)遠(yuǎn)小于聚類樣本的總個數(shù)，同時要保證 C>1 。對于 m ，它是一個控制算法的柔性的參數(shù)，如果 m 過大，則聚類效果會很次，而如果 m 過小則算法會接近 HCM 聚類算法。

? 算法的輸出是 C 個聚類中心點向量和 C*N 的一個模糊劃分矩陣，這個矩陣表示的是每個樣本點屬于每個類的隸屬度。根據(jù)這個劃分矩陣按照模糊集合中的最大隸屬原則就能夠確定每個樣本點歸為哪個類。聚類中心表示的是每個類的平均特征，可以認(rèn)為是這個類的代表點。

? 從算法的推導(dǎo)過程中我們不難看出，算法對于滿足正態(tài)分布的數(shù)據(jù)聚類效果會很好，另外，算法對孤立點是敏感的。