基于直覺模糊集的模糊C均值聚類改進(jìn)算法

李 婧,于麗英

(上海大學(xué)管理學(xué)院,上海200444)

在科學(xué)研究中,人們常常需要把研究對(duì)象按照它們的自身性質(zhì)和用途等進(jìn)行分類,以便進(jìn)一步研究.聚類分析是指對(duì)具體或抽象事物進(jìn)行分類,使得同類事物之間具有極高的相似度,而不同類事物之間高度相異.模糊C均值(fuzzy C-means,FCM)算法是一種常用的聚類分析方法,最早由Dunn[1]提出.之后,Bezdek[2]對(duì)FCM聚類算法進(jìn)行了推廣.目前,FCM聚類算法已在醫(yī)療圖像分割[3]、環(huán)境污染狀況分類[4]、水下目標(biāo)識(shí)別[5]和電力客戶分類[6]等領(lǐng)域得到了廣泛應(yīng)用.

傳統(tǒng)的FCM算法中聚類對(duì)象的特征值通常是精確值,而在許多實(shí)際問題中,聚類對(duì)象的信息是模糊的,因此模糊環(huán)境下的FCM聚類算法被很多學(xué)者關(guān)注.于春海等[7]提出了聚類對(duì)象具有不確定性區(qū)間數(shù)多指標(biāo)信息的聚類分析問題的算法.張洪美等[8]提出了基于直覺模糊集的聚類方法,但當(dāng)樣本數(shù)量較大且實(shí)時(shí)性要求較高時(shí),該方法無法滿足需要.吳成茂[9]提出了基于直覺模糊集的FCM聚類算法,但該算法隨機(jī)選擇初始聚類中心,魯棒性較差.申曉勇等[10]和昌燕等[11]分別研究了基于直覺模糊集的FCM聚類算法初始聚類中心的選擇問題,但均未考慮聚類樣本的特征權(quán)重對(duì)聚類結(jié)果的影響.目前,已有很多學(xué)者將基于直覺模糊集的FCM聚類方法應(yīng)用現(xiàn)實(shí)問題中.王昭等[12]提出了一種融入局部信息的直覺模糊C均值聚類算法,并應(yīng)用于圖像分割領(lǐng)域.耿秀麗等[13]將直覺模糊C均值聚類方法應(yīng)用于客戶聚類和識(shí)別中.針對(duì)上述研究中未同時(shí)考慮特征權(quán)重和初始聚類中心的問題,本工作提出了一種改進(jìn)的基于直覺模糊集的FCM聚類算法.

1 預(yù)備知識(shí)

1.1 直覺模糊集

Atanassov[14]首次提出了直覺模糊集的概念,并利用隸屬度與非隸屬度兩個(gè)標(biāo)度刻畫數(shù)據(jù)的模糊性.

定義1[14]令集合X={x1,x2,···,xn},X上的一個(gè)直覺模糊集可表示為

式中,μA(xi)∈[0,1],νA(xi)∈[0,1]分別表示元素xi對(duì)A的隸屬度與非隸屬度,且對(duì)于?xi∈X,都有0≤ μA(xi)+νA(xi)≤ 1.記πA(xi)=1?μA(xi)?νA(xi)為猶豫度,則πA(xi)∈[0,1].

定義2[15]設(shè)A={〈xi,μA(xi),νA(xi)〉|xi∈ X}和B={〈xi,μB(xi),νB(xi)〉|xi∈ X}為兩個(gè)直覺模糊集,則直覺模糊集A與B的歐氏距離為

由X中的元素xi對(duì)A的隸屬度和非隸屬度所組成的有序?qū)Α处藺(xi),νA(xi)〉稱為直覺模糊數(shù)[16].為方便起見,直覺模糊數(shù)記為〈μi,νi〉,猶豫度記為πi.

定義3[16]設(shè)為直覺模糊數(shù),則有

1.2 模糊熵

直覺模糊熵是直覺模糊集理論中的一個(gè)重要概念,由Burillo等[17]最先給出定義.直覺模糊熵是一種反映直覺模糊集模糊程度的量化指標(biāo).

定義4[18]設(shè)F(X)表示非空集合X上的所有直覺模糊集的集合,直覺模糊集A∈F(X),稱函數(shù)E:F(X)→[0,1]為直覺模糊集A的直覺模糊熵E(A),則有

(1)E(A)=0,當(dāng)且僅當(dāng)?x ∈ X,〈μA(x),νA(x)〉= 〈1,0〉或〈0,1〉;

(2)E(A)=1,當(dāng)且僅當(dāng)?x ∈ X,〈μA(x),νA(x)〉= 〈0,0〉;

(3)E(A)=E(Ac);

(4)?A,B ∈F(X),若A?B,則E(A)≤E(B).

定義5[19]設(shè)X={x1,x2,···,xn}為非空集合,A∈F(X),則有

式中,E(A)為A的直覺模糊熵.

2 改進(jìn)的FCM聚類算法

2.1 問題描述

設(shè)有限集Y={y1,y2,···,yn}是n個(gè)待聚類樣本組成的集合,G={g1,g2,···,gs}為樣本的s個(gè)特征組成的特征集.P=(P1,P2,···,Pn)T為樣本的特征值矩陣,Pi=(pi1,pi2,···,pis),i=1,2,···,n是樣本yi的特征矢量,pij(i=1,2,···,n,j=1,2,···,s)是樣本yi關(guān)于特征gj的特征值.c(c＜ n)為聚類類別數(shù),Z={Z1,Z2,···,Zc}是聚類中心集,Zk=(zk1,zk2,···,zks),k=1,2,···,c是聚類中心.U=[uik]n×c是劃分的隸屬度矩陣,uik∈ R是樣本yi關(guān)于聚類中心Zk的隸屬度.d(Pi,Zk)是yi的特征矢量Pi和聚類中心Zk間的歐式距離.m為模糊度參數(shù),表示聚類效果的模糊程度,其值越大,聚類結(jié)果越模糊.由于目前尚無被廣泛接受的模糊度參數(shù),在FCM算法中常取m=2[20].定義樣本集Y對(duì)于聚類中心集Z的廣義歐氏距離平方和為

傳統(tǒng)的FCM聚類算法有3點(diǎn)不足:①聚類樣本yi(i=1,2,···,n)關(guān)于特征gj(j=1,2,···,s)的特征值pij都是精確數(shù)值,而現(xiàn)實(shí)中聚類問題的復(fù)雜性、多樣性使得決策者很難給出精確數(shù)值;②未考慮樣本特征權(quán)重對(duì)聚類結(jié)果的影響;③對(duì)初始聚類中心敏感.

因此,本工作提出一種改進(jìn)的FCM聚類算法,對(duì)一個(gè)待聚類的樣本集Y={y1,y2,···,yn}合理分類,其中樣本Y的s個(gè)特征組成的特征集為G={g1,g2,···,gs}. 樣本yi關(guān)于特征gj的特征值為直覺模糊數(shù)形式pij= 〈μij,νij〉,i=1,2,···,n,j=1,2,···,s, 其中μij,νij∈R+.樣本的直覺模糊數(shù)特征值已知,而樣本特征權(quán)重未知.

2.2 計(jì)算加權(quán)樣本特征值

模糊熵描述了模糊集合的模糊程度和不確定程度.如果集合越模糊,它的模糊熵就越大,權(quán)重就越小;反之亦然.樣本的特征權(quán)重必須反映各特征的相對(duì)重要程度.為避免賦權(quán)過程中的主觀隨意性,本工作采用直覺模糊熵確定特征gj的權(quán)重wj,有

式中,猶豫度πij=1?μij?νij.Egj反映了樣本集Y在特征gj下的特征值的模糊性和不確定性.Egj的值越大,模糊程度越高,說明聚類結(jié)果對(duì)特征gj的依賴程度越小.

此時(shí),樣本yi所對(duì)應(yīng)的加權(quán)后的特征矢量為

2.3 確定初始聚類中心

由于傳統(tǒng)的FCM算法對(duì)初始聚類中心敏感,不同的初始聚類中心往往對(duì)應(yīng)不同的聚類結(jié)果.若利用歐氏距離作為距離度量工具,選擇待聚類樣本集中相互距離最遠(yuǎn)的c個(gè)樣本的特征值為初始聚類中心,則有時(shí)會(huì)取到噪聲點(diǎn),從而影響聚類結(jié)果.袁方等[21]為消除傳統(tǒng)的FCM算法對(duì)初始聚類中心的敏感性,定義了聚類對(duì)象的密度參數(shù),有效地避開噪聲點(diǎn).賴玉霞等[22]提出采取對(duì)象分布密度方法確定初始聚類中心.本工作認(rèn)為,在直覺模糊的大環(huán)境下,可以將初始聚類中心的選擇區(qū)域進(jìn)行密度細(xì)分,有效避開低密度區(qū)域的噪聲點(diǎn),取高密度區(qū)域中相互距離最遠(yuǎn)的c個(gè)點(diǎn).

式中,0＜C＜n且為整數(shù),具體數(shù)值視情況而定.ρi越大,說明的區(qū)域密度越大;反之,ρi越小,說明的區(qū)域密度越小.

的特征矢量為第三個(gè)聚類中心Z3;最后,計(jì)算H中所有特征矢量到Z1,Z2,···,Zk?1的距離,在H中取出滿足

的特征矢量為第k個(gè)聚類中心Zk(k=1,2,···,c).依此求得聚類中心Z={Z1,Z2,···,Zc},其中c個(gè)聚類中心取自特征矢量集H中的C個(gè)特征矢量.在確定初始聚類中心時(shí),要避免過于集中,且H中的特征矢量的選取要避開噪聲點(diǎn).本工作中取C∈((n+c)/2,n)且為整數(shù).

2.4 更新聚類中心和隸屬度矩陣

在基于直覺模糊集的FCM聚類算法中,需要利用聚類中心計(jì)算對(duì)應(yīng)的隸屬度矩陣.

式中,m為模糊度參數(shù).

利用隸屬度矩陣更新聚類中心[9],其中第k個(gè)聚類中心記為Zk,

式中,

此時(shí),樣本集Y對(duì)于聚類中心Z的廣義歐氏距離平方和[9]為

2.5 算法步驟

改進(jìn)的FCM聚類算法的具體步驟如下.

步驟1 輸入樣本特征值矩陣P,聚類數(shù)目c,模糊度參數(shù)m,停止迭代的閾值ε,迭代次數(shù)δ.

步驟2 采用式(5)和(6)計(jì)算特征權(quán)重,再采用式(7)計(jì)算加權(quán)特征值矩陣P′.

步驟3 令t=0,確定初始聚類中心Z(t),并采用式(13)和(14)計(jì)算出隸屬度矩陣U(t).

步驟4 判斷t是否小于δ.若是,繼續(xù)步驟5;若不是,跳轉(zhuǎn)到步驟7.

步驟5 令t=t+1,采用式(12)更新聚類中心Z(t),再采用式(13)和(14)更新隸屬度矩陣U(t).

步驟 6 采用式(18)計(jì)算J?U(t?1),Z(t?1)?和J?U(t),Z(t)?, 判斷J?U(t?1),Z(t?1)? ?J?U(t),Z(t)?＜ε是否成立.若成立,繼續(xù)步驟7;若不成立,跳轉(zhuǎn)到步驟4.

步驟7 輸出隸屬度矩陣U和聚類中心Z.

3 算例驗(yàn)證

文獻(xiàn)[8]最早研究了基于直覺模糊集的聚類問題,因此本工作選取其中的算例進(jìn)行驗(yàn)證.某汽車市場(chǎng)欲對(duì)5款不同的汽車Y={y1,y2,···,y5}進(jìn)行分類,每款汽車有6個(gè)可供評(píng)價(jià)的特征G={g1,g2,···,g6},其中g(shù)1為燃料消耗量,g2為摩擦系數(shù),g3為價(jià)格,g4為舒適度,g5為設(shè)計(jì),g6為安全系數(shù).每種汽車在各特征下的特征值用直覺模糊數(shù)表示,那么該聚類樣本的特征值矩陣如表1所示.

表1 聚類樣本特征值矩陣Table 1 Characteristic value matrix of clustering samples

假設(shè)c=3,m=2,ε=10?6,δ=100.通過表1計(jì)算各特征權(quán)重,進(jìn)而得到加權(quán)后的樣本特征值矩陣,如表2所示.根據(jù)本工作提出的計(jì)算方法確定初始聚類中心,得到的3個(gè)聚類中心初始值分別為和再由隸屬度計(jì)算公式計(jì)算初始聚類中心相應(yīng)的隸屬度矩陣?迭代結(jié)束?后得到?的聚類中?心為和具體如表3所示.經(jīng)過2次迭代后,得到JU(1),Z(1)?JU(2),Z(2)=6.971 0×10?7＜ ε,隸屬度迭代結(jié)果如表4所示.從表4可以看出,若根據(jù)最大隸屬原則對(duì)樣本分類,第一類為{y1,y2,y3},第二類為{y4},第三類為{y5},該結(jié)果與文獻(xiàn)[8]和[23]中的聚類結(jié)果相同.表5為在同樣考慮特征權(quán)重的前提下,本工作提出的改進(jìn)算法與文獻(xiàn)[8]和[23]中算法的比較.由表5可以看出,文獻(xiàn)[8]和[23]中的基于直覺模糊集的聚類算法目標(biāo)函數(shù)的初始值較大,迭代次數(shù)多.由以上分析可見,采用本工作提出的方法,可以極大地提高聚類性能.由于初始聚類中心有效地避開了噪聲點(diǎn),獲得了較小的目標(biāo)函數(shù)初始值,因此大大減少了迭代次數(shù),克服了目標(biāo)函數(shù)在尋優(yōu)過程中易陷入局部最優(yōu)值的缺陷,同時(shí)加快了收斂速度.綜上可知,本工作提出的聚類算法在聚類樣本數(shù)較多、樣本特征權(quán)重之間差異明顯的實(shí)例中,可取得更好的聚類效果.

表2 加權(quán)后的樣本特征值矩陣Table 2 Weighted characteristic value matrix of clustering samples

表3 聚類中心Table 3 Clustering center

表4 隸屬度矩陣Table 4 Membership matrix

表5 聚類算法結(jié)果的比較Table 5 Comparison of clustering results

4 結(jié)束語

本工作給出了一種改進(jìn)的基于直覺模糊集的FCM聚類算法,該算法考慮到樣本的特征權(quán)重對(duì)聚類效果的影響,利用直覺模糊熵對(duì)特征值進(jìn)行加權(quán);考慮到傳統(tǒng)FCM聚類算法中隨機(jī)選取初始聚類中心的不合理性,定義了區(qū)域密度,通過比較每個(gè)樣本的區(qū)域密度,在高密度區(qū)域中選取初始聚類中心.最后通過算例驗(yàn)證了該聚類方法的正確性和有效性.由于算法在計(jì)算機(jī)上易于實(shí)現(xiàn),可用于解決大數(shù)量以及實(shí)時(shí)性要求較高的聚類問題.需要指出的是,樣本的聚類數(shù)目和加權(quán)指數(shù)的確定等還需要進(jìn)一步探討,這些問題的解決直接關(guān)系到最終聚類結(jié)果的有效性.