李 婧,于麗英

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

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

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

1 預備知識

1.1 直覺模糊集

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

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

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

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

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

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

1.2 模糊熵

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

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

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

(2)E(A)=1,當且僅當?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]設X={x1,x2,···,xn}為非空集合,A∈F(X),則有

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

2 改進的FCM聚類算法

2.1 問題描述

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

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

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

2.2 計算加權樣本特征值

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

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

此時,樣本yi所對應的加權后的特征矢量為

2.3 確定初始聚類中心

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

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

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

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

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

在基于直覺模糊集的FCM聚類算法中,需要利用聚類中心計算對應的隸屬度矩陣.

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

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

式中,

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

2.5 算法步驟

改進的FCM聚類算法的具體步驟如下.

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

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

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

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

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

步驟 6 采用式(18)計算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;若不成立,跳轉到步驟4.

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

3 算例驗證

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

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

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

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

表3 聚類中心Table 3 Clustering center

表4 隸屬度矩陣Table 4 Membership matrix

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

4 結束語

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