王穎潔,白鳳波,王金慧

(1.大連大學(xué)信息工程學(xué)院,遼寧大連 116622;2.北京海輝高科軟件有限公司微軟事業(yè)部,北京 100085; 3.北京機(jī)電工程研究所,北京 100074)

關(guān)于模糊C-均值(FCM)聚類算法的改進(jìn)

王穎潔1,白鳳波2,王金慧3

(1.大連大學(xué)信息工程學(xué)院,遼寧大連 116622;2.北京海輝高科軟件有限公司微軟事業(yè)部,北京 100085; 3.北京機(jī)電工程研究所,北京 100074)

對模糊C-均值聚類算法的改進(jìn),即在原有的模糊C-均值算法的基礎(chǔ)上,用一種新的定義距離的方法替代歐氏空間中距離的定義,改進(jìn)模糊聚類算法。并且用數(shù)據(jù)仿真驗(yàn)證這種改進(jìn)的模糊聚類算法與原來算法相比,聚類效果更好,分類更清晰。

模糊C-均值算法,模糊加權(quán)距離,模糊加權(quán)因子

1 引言

模糊聚類分析(FCA)的思想首先是由Bel lman和Zadeh等人在1966年提出的,它是近些年來發(fā)展很快的一種分析方法,其目的是對樣本進(jìn)行合理分配,從而達(dá)到對樣本進(jìn)行判別、分析與預(yù)測的目的。1973年Dunn提出了模糊C-均值聚類法(FCM);1992年Bezdek提出一種"Fuzzy Kohonen Clustering Network"算法(FKCN),Bezdek的FKCN算法是將神經(jīng)網(wǎng)絡(luò)用于求類中心的迭代問題,該算法中沒有考慮模式特征的重要性描述,因此迭代速度慢。目前有關(guān)模糊聚類的許多成果都是對C-均值聚類法進(jìn)行推廣和改進(jìn)。該文討論的是對模糊C -均值聚類算法的改進(jìn),這種改進(jìn)算法的核心部分是引進(jìn)了一種新的定義距離的方法-模糊加權(quán)距離。

2 FCM算法

模糊C-均值聚類問題在數(shù)學(xué)上可以表示為如下的目標(biāo)函數(shù)[1]求極值的問題:

約束條件為:

式中n為樣本數(shù)據(jù)點(diǎn)的數(shù)目,c為類別數(shù)目,通常1＜c＜n;m＞1為一個(gè)標(biāo)量;dij(xj, vi)=‖xj-vi‖示數(shù)據(jù)點(diǎn)xj心之間的歐氏距離;X={x1,x1,Λ,xn}?Rs點(diǎn)的集合,vi∈Rs為聚類的中心;μij表示數(shù)據(jù)點(diǎn)xj屬于類中心vi的隸屬度。U={μij}是一個(gè)n×c的模糊分割矩陣,V={v1,v2,Λ,vc}是一個(gè)s×c的矩陣。

m用來控制分割矩陣U的模糊程度,m越大,分類的模糊程度越高,m→∞時(shí),μ=→1/c,實(shí)際上已不能提供分類信息;當(dāng)m=1時(shí),μij∈[0,1],算法退化為HCM算法,所以FCM實(shí)質(zhì)上是HCM的自然推廣。歐氏距離準(zhǔn)則適合于類內(nèi)數(shù)據(jù)點(diǎn)為超球型分布的情況,dij采用不同的距離定義,可將聚類算法用于不同分布類型數(shù)據(jù)的聚類問題。

3 改進(jìn)的模糊聚類算法

3.1 引入加權(quán)因子的模糊加權(quán)距離

距離是模式識別與分類、聚類分析及現(xiàn)實(shí)社會(huì)中非常重要的概念之一,它反映了事物之間的近似程度。模糊加權(quán)距離[2]是一種新的定義距離的方法。模糊加權(quán)距離的加權(quán)因子是根據(jù)數(shù)據(jù)空間中各數(shù)據(jù)點(diǎn)對同一聚類中心的貢獻(xiàn)(即所起的作用)不同而確定的。

(1)先對模糊子集和隸屬函數(shù)進(jìn)行定義。

設(shè)給定論域?yàn)閁,U上的一個(gè)模糊子集A是指:對任X∈U,都確定了一個(gè)數(shù)μA(x)且μA(x)∈[0,1],稱μA(x)為x對A的隸屬程度.

μ稱為模糊子集A的隸屬函數(shù),模糊子集完全由其隸屬函數(shù)所刻畫。

(2)提出一個(gè)新的概念-模糊加權(quán)因子。模糊加權(quán)因子的性質(zhì)類似于隸屬度,但作用不同于FCM算法中的隸屬度μij,它與隸屬度分別側(cè)重于兩個(gè)不同的方面。每一個(gè)數(shù)據(jù)點(diǎn)xj相對于每一個(gè)聚類中心center(i)都有一個(gè)隸屬度μij(μij是初始化的隸屬度矩陣中第i行j列位置上的元素并且Σci=1μij=1),所以同一個(gè)數(shù)據(jù)點(diǎn)對于不同的聚類中心可以用隸屬度來表示其優(yōu)勢程度。但對于同一個(gè)聚類中心來說,不同的數(shù)據(jù)點(diǎn)之間的隸屬度就沒有任何的聯(lián)系,也就是說每個(gè)數(shù)據(jù)點(diǎn)對同一個(gè)聚類中心來說對于距離的貢獻(xiàn)是無法比較的。舉個(gè)簡單的例子:

圖1 舉例說明模糊加權(quán)因子

如圖1:A,B,C,D是四個(gè)數(shù)據(jù)點(diǎn),x,y,z是三個(gè)聚類中心。數(shù)據(jù)點(diǎn)A對于三個(gè)聚類中心x, y,z的隸屬度分別是0.6,0.3,0.1,三者之間可以比較,數(shù)據(jù)點(diǎn)A屬于聚類中心x的可能性更大一點(diǎn)。但對于同一個(gè)聚類中心x來說,四個(gè)數(shù)據(jù)點(diǎn)A,B,C,D原來的隸屬度已沒有可比性,對于距離沒有任何意義。所以提出一個(gè)模糊加權(quán)因子的概念。

(3)加權(quán)因子的確定[3-5]。定量給出了每個(gè)數(shù)據(jù)點(diǎn)xj隸屬于同一個(gè)聚類中心center(i)時(shí)所具有的優(yōu)勢程度。模糊加權(quán)因子,描述各個(gè)數(shù)據(jù)點(diǎn)對距離的貢獻(xiàn)是不平等的(距離是聚類中心center(i)到數(shù)據(jù)點(diǎn)xj的距離)。

其定義如下:

Wij即為是第j個(gè)數(shù)據(jù)點(diǎn)屬于第i個(gè)聚類中心的模糊加權(quán)因子。在這里,μij是第j個(gè)數(shù)據(jù)點(diǎn)屬于第i個(gè)聚類中心的隸屬度,n是數(shù)據(jù)點(diǎn)的個(gè)數(shù)。

(4)模糊加權(quán)距離的定義

在模式識別與分類中,常常只求距離的平方而不必求出距離本身,這僅僅是為避免開方運(yùn)算(歐式空間中),并不影響討論結(jié)果,因此這里亦以平方形式給出加權(quán)距離的定義:

其中Wij由式(4)確定。可以證明式(5)滿足距離空間中關(guān)于距離的定義。

下面我們討論1/Wij的意義。當(dāng)Wij越大,則表示在各數(shù)據(jù)點(diǎn)到聚類中center(i)的距離中, xj所起的作用越大,即對距離的貢獻(xiàn)越大。xj對距離的貢獻(xiàn)越大就表示它距離聚類中心center(i)越近,1/Wij越小,距離放大的尺度就越小,所以距離值越小。舉個(gè)例子:(參見圖1)假定A,B,C,D四個(gè)數(shù)據(jù)點(diǎn)到聚類中心z的歐式距離分別是10,4,2,8。利用(3)和(4)式可以求出WZA=1/12;WZB=1/4;WZC=1/2;WZD= 1/6。將上述代入到(5)式中得到模糊加權(quán)距離dZA=120;dZB=16;dZC=4;dZD=48。

模糊加權(quán)距離的原理就是將模糊加權(quán)因子引入到歐氏空間距離公式中,模糊加權(quán)因子的倒數(shù)就相當(dāng)于一個(gè)放大鏡的作用,將所有的距離全部放大,但是放大的尺度不同,對于距離遠(yuǎn)的數(shù)據(jù)點(diǎn)放大的尺度要大一些,對于距離近的數(shù)據(jù)點(diǎn)放大的尺度要小一些。這樣就導(dǎo)致了兩極分化,距離遠(yuǎn)的變得更遠(yuǎn),距離近的變得更近,使得更易于聚類,分類清晰,得到很好的聚類效果。

3.2 改進(jìn)的模糊聚類算法

下面將模糊加權(quán)距離引入到模糊C-均值聚類算法中,模糊C-均值聚類算法中的其他的定義沒有變化,只有求極值的目標(biāo)函數(shù)中距

其中Wij為模糊加權(quán)因子,由式(5)確定。

在模糊C-均值算法中引入模糊加權(quán)因子,使得數(shù)據(jù)空間中各個(gè)數(shù)據(jù)點(diǎn)對同一聚類中心所具有的特征優(yōu)勢不同,導(dǎo)致對距離的貢獻(xiàn)也不同,更具合理性,使得聚類效果更好,分類更清晰,改進(jìn)數(shù)據(jù)預(yù)處理的方法。

4 數(shù)據(jù)仿真結(jié)果

將200個(gè)二維數(shù)據(jù)分為三類。使用了兩種方法,本文提出的改進(jìn)的模糊聚類算法(引入了模糊加權(quán)因子),結(jié)果見圖2;經(jīng)典的模糊C-均值聚類算法[6],結(jié)果見圖3。對比聚類效果圖如下:

通過對比兩種算法的效果圖可以看出:圖2是改進(jìn)后的模糊聚類算法(引入了模糊加權(quán)因子)的效果圖,聚類效果比圖3經(jīng)典的模糊C -均值聚類算法更好,數(shù)據(jù)點(diǎn)更集中,有若干點(diǎn)集中在聚類中心上。我們可以看右下角的數(shù)據(jù)點(diǎn),改進(jìn)后的模糊聚類算法將紫色的點(diǎn)和藍(lán)色的點(diǎn)能清楚的分開,兩個(gè)類之間的界限很明顯;而模糊C-均值算法分類的程度就不是很清晰,分別屬于兩個(gè)類的綠色的點(diǎn)和紫色的點(diǎn)幾乎重合,可見類與類之間劃分不清晰。

圖2 改進(jìn)算法后的聚類效果圖

圖3 FCM聚類效果圖

圖4 改進(jìn)算法后的目標(biāo)函數(shù)圖

圖5 FCM目標(biāo)函數(shù)圖

對比目標(biāo)函數(shù)曲線如下:圖4的是改進(jìn)算法后的目標(biāo)函數(shù)圖(引入模糊加權(quán)因子),圖5是經(jīng)典的模糊C-均值算法目標(biāo)函數(shù)圖。可以看出圖4的函數(shù)曲線比圖5的函數(shù)曲線更加平滑,收斂速度快。

5 結(jié)論

本文討論的是對模糊C-均值聚類算法的改進(jìn),在原有的模糊C-均值算法的基礎(chǔ)上,用一種新的定義距離的方法替代歐氏空間中距離的定義,引入了重要參數(shù)-模糊加權(quán)因子,模糊加權(quán)因子的引入,使得數(shù)據(jù)空間中各數(shù)據(jù)點(diǎn)所具有的特征優(yōu)勢不同,導(dǎo)致對距離的貢獻(xiàn)也不同,這是兩種距離定義方法的根本區(qū)別之處。并且用數(shù)據(jù)仿真驗(yàn)證了這種改進(jìn)了的模糊聚類算法比原來的算法聚類更有效,分類更清晰,速度快。

[1]Timothy J.Ross.模糊邏輯及其工程應(yīng)用[M].北京:電子工業(yè)出版社,2003.

[2]魯宇,范希魯.模糊加權(quán)距離及其合理性討論[J].北方交通大學(xué)學(xué)報(bào),1990(2).

[3]王士同.神經(jīng)模糊系統(tǒng)及其應(yīng)用[M].北京:北京航天航空大學(xué)出版社,1998(6).

[4]Kazutaka Umayahara,Sadaaki MiyamotoandYoshiteru Nakamori,Formulations of Fuzzy Clustering for Categorical Data,InternationalJournalofInnovativeComputing, Information and Control(IJICIC),vol.1,no.1,pp.83-94,2005(3).

[5]Hugang Han,InformationSystem withFuzzy Weights, International Journal of Innovative Computing,Information and Control(IJICIC),vol.2,no.3,pp.553-565,2006 (6).

[6]吳曉莉,林哲輝.MATLAB輔助模糊系統(tǒng)設(shè)計(jì)[M].西安:西安電子科技大學(xué)出版社,2002.

Improvement of the Fuzzy C-Means Clustering Algorithm

WANG Ying-jieWang1,BA IFeng-bo2,WANG Jin-hui3

(1.College of Infor mation Engineering,Dalian University,Dalian,116622,China;
2.MSPD,HiSoft Technology InternationalLtd.,Beijing,100074,China;
3.Beijing Electromechanical Engineering Insitute,Beijing,100074,China)

An improvement algorithm about the fuzzy c-means clustering algorithm is discussed in this paper.Based on original fuzzy c-means clustering algorithm,the improvement algorithm uses a new way of defining distance to displace the distance in Euclidean space.Experimental results show that the improvement algorithm is better than original algorithm and the classification is clearer than original algorithm.

Fuzzy c-means algorithm;Fuzzyweighted distance;Fuzzyweighted factor

TP18

A

1008-2395(2010)06-0001-04

2010-11-15

王穎潔(1977-),女,講師,Email:yingjiehappy@hotmail.com