FCM聚類算法介紹

《FCM聚類算法介紹》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在工程資料-天天文庫。

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

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

3、距離）指標的價值函數(shù)（或目標函數(shù)）達到最小。當選擇歐幾里德距離為組j中向量xk與相應聚類中心ci間的非相似性指標時，價值函數(shù)可定義為：(6.2)這里是組i內(nèi)的價值函數(shù)。這樣Ji的值依賴于Gi的幾何特性和ci的位置。一般來說，可用一個通用距離函數(shù)d(xk,ci)代替組I中的向量xk，則相應的總價值函數(shù)可表示為：(6.3)為簡單起見，這里用歐幾里德距離作為向量的非相似性指標，且總的價值函數(shù)表示為（6.2）式。劃分過的組一般用一個c×n的二維隸屬矩陣U來定義。如果第j個數(shù)據(jù)點屬于組i，則U中的元素為1；否則，該元素取0。一旦確定聚類中心，可導出如下使式（6.2）最?。?6.4)重申一點

4、，如果是的最近的聚類中心，那么屬于組。由于一個給定數(shù)據(jù)只能屬于一個組，所以隸屬矩陣U具有如下性質(zhì)：(6.5)且(6.6)另一方面，如果固定則使（6.2）式最小的最佳聚類中心就是分組中所有向量的均值：，(6.7)這里是的規(guī)模或。為便于批模式運行，這里給出數(shù)據(jù)集xi（1，2…，n）的K均值算法；該算法重復使用下列步驟，確定聚類中心ci和隸屬矩陣U：步驟1：初始化聚類中心ci,i=1,…,c。典型的做法是從所有數(shù)據(jù)點中任取c個點。步驟2：用式（6.4）確定隸屬矩陣U。步驟3：根據(jù)式（6.2）計算價值函數(shù)。如果它小于某個確定的閥值，或它相對上次價值函數(shù)質(zhì)的改變量小于某個閥值，則算法停止。

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

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

7、數(shù)）就是式（6.2）的一般化形式：，(6.10)這里uij介于0，1間；ci為模糊組I的聚類中心，dij=

8、

9、ci-xj

10、

11、為第I個聚類中心與第j個數(shù)據(jù)點間的歐幾里德距離；且是一個加權指數(shù)。構造如下新的目標函數(shù)，可求得使（6.10）式達到最小值的必要條件：(6.11)這里lj，j=1到n，是（6.9）式的n個約束式的拉格朗日乘子。對所有輸入?yún)⒘壳髮В故剑?.10）達到最小的必要條件為：(6.12)和(6.13)由上述兩個必要條件，模糊C均值聚類算法是一個簡單的迭代過程。在批處理