基于類內(nèi)類間距離量級平衡的FCM聚類算法設(shè)計

江文奇, 牟華偉

(南京理工大學(xué) 經(jīng)濟(jì)管理學(xué)院,江蘇 南京 210094)

0 引言

網(wǎng)絡(luò)環(huán)境下數(shù)據(jù)與數(shù)據(jù)處理能力已經(jīng)成為互聯(lián)網(wǎng)企業(yè)的重要競爭力。近年來，第三方電子商務(wù)平臺收集并存儲了大量的客戶購物和評價信息，通過實(shí)施客戶聚類有效表征了不同類別客戶的特征偏好，為精準(zhǔn)營銷提供了有力支撐。

聚類本質(zhì)是將大量數(shù)據(jù)從空間上進(jìn)行一種無監(jiān)督無標(biāo)號的劃分，目的是挖掘數(shù)據(jù)的內(nèi)在聯(lián)系和潛在價值，已經(jīng)廣泛應(yīng)用于模式識別、機(jī)器學(xué)習(xí)等領(lǐng)域[1]。模糊C均值(Fuzzy C-means, FCM)算法是一種常見且廣泛應(yīng)用的聚類算法，魯棒性好且收斂性強(qiáng)。其中，初始聚類中心點(diǎn)、每個數(shù)據(jù)點(diǎn)與聚類中心點(diǎn)的隸屬度、聚類模型設(shè)計等是FCM算法的核心內(nèi)容[2]。

現(xiàn)有FCM聚類算法研究均突出了聚類穩(wěn)定性特征。如文獻(xiàn)[3]引入多維數(shù)據(jù)的鄰域信息改進(jìn)聚類算法，增加異常值和噪聲點(diǎn)的穩(wěn)健性。文獻(xiàn)[4]根據(jù)數(shù)據(jù)之間互為K近鄰關(guān)系來確定數(shù)據(jù)中的自然簇，減少算法對聚類參數(shù)的依賴程度。文獻(xiàn)[5]提出基于全部最小連通支配集的聚類算法解決了算法易于陷入局部最小值的缺陷。多維大數(shù)據(jù)環(huán)境下，文獻(xiàn)[6]結(jié)合灰狼算法和最大熵理論刪減屬性；文獻(xiàn)[7]采用折線模糊數(shù)描述待聚類對象的指標(biāo)信息并設(shè)計聚類算法；文獻(xiàn)[8]提出了一種自適應(yīng)特征熵權(quán)的FCM算法分析屬性權(quán)重對聚類算法的影響程度；文獻(xiàn)[9]將偏好矢量相聚度作為鄰域相似度，構(gòu)建啟發(fā)式聚類算法解決多屬性復(fù)雜大群體聚類與決策問題。

上述文獻(xiàn)注重FCM算法的穩(wěn)定性問題，但忽視了FCM目標(biāo)函數(shù)對于聚類績效的影響。通常，聚類模型與算法設(shè)計的有效性部分受制于目標(biāo)函數(shù)，而目標(biāo)函數(shù)中類內(nèi)類間距離合成形式是關(guān)鍵點(diǎn)。于是，本文擬深入分析類內(nèi)距離和類間距離之間的關(guān)系，基于兩類距離數(shù)值量級的差異性，設(shè)計兩類距離平衡方法，進(jìn)而提出一種新的FCM聚類目標(biāo)函數(shù)設(shè)計和聚類算法，提高多維大數(shù)據(jù)環(huán)境下FCM算法的聚類績效。

1 FCM聚類算法概述

FCM聚類算法是一種應(yīng)用廣泛的聚類算法，其原理是基于數(shù)據(jù)屬性的相似性以及數(shù)據(jù)屬性的差異性，通過自動迭代算法實(shí)現(xiàn)對大量數(shù)據(jù)的聚類劃分。假定聚類數(shù)據(jù)量為n(X=(x1,x2,…,xn)∈RS)，數(shù)據(jù)集維度為s，聚類中心點(diǎn)數(shù)為c，vi為第個聚類中心點(diǎn)，uij為樣本點(diǎn)j對第i個類的隸屬度(隸屬度矩陣為U)，dij為樣本點(diǎn)j對第i個聚類中心點(diǎn)的距離，模糊加權(quán)數(shù)m∈[1,∞)。經(jīng)典FCM算法的優(yōu)化模型為:

(1)

運(yùn)用Lagrange乘子法求解，有:

(2)

其中，1≤i≤c,1≤j≤n。

FCM算法具體步驟描述為:

首先：確定聚類中心點(diǎn)個數(shù)c，模糊權(quán)重值m，初始聚類中心點(diǎn)vi。給定判斷兩次目標(biāo)函數(shù)值大小之差或者目標(biāo)函數(shù)迭代終止閾值β。

其次：依據(jù)式(2)求隸屬度矩陣和新的聚類中心點(diǎn)，由式(1)求得目標(biāo)函數(shù)值。

最后：計算前后兩次目標(biāo)函數(shù)值之差與β的大小關(guān)系(或目標(biāo)函數(shù)值與β的大小關(guān)系)。若兩次目標(biāo)函數(shù)之值小于β值，則輸出聚類中心點(diǎn)和隸屬度矩陣，否則，重復(fù)步驟(2)。

2 FCM中類內(nèi)與類間距離關(guān)系研究

針對經(jīng)典的FCM聚類模型，以SFA和SFE跡表示類內(nèi)和類間距離，有:

tr(SFT)=tr(SFA)+tr(SFE)

其中：tr(SFA)是經(jīng)典FCM目標(biāo)函數(shù)JFCM，tr(SFE)可作為具有隸屬度加權(quán)類間距離測度，tr(SFF)為僅依賴于隸屬度的不確定值。

為了平衡FCM聚類算法的類內(nèi)類間距離，實(shí)現(xiàn)聚類過程中類內(nèi)類間距離的有效融合，當(dāng)前FCM聚類算法模型優(yōu)化主要有以下幾種方式：(1)添加懲罰函數(shù)項，動態(tài)調(diào)整類內(nèi)類間距離差距；(2)增加權(quán)重系數(shù)平衡類類內(nèi)類間距離；(3)結(jié)合熵函數(shù)表征類間離散程度、(4)基于核函數(shù)改變類內(nèi)類間距離度量方式。結(jié)合tr(SFT)表達(dá)式，分析FCM聚類目標(biāo)函數(shù)的類內(nèi)類間距離關(guān)系。

(1)文獻(xiàn)[10]結(jié)合競爭學(xué)習(xí)思想，在目標(biāo)函數(shù)中添加懲罰函數(shù)項，目標(biāo)函數(shù)表示為:

懲罰函數(shù)項為:

在tr(SFT)=tr(SFA)+tr(SFE)兩側(cè)添加加懲罰函數(shù)項可得:

等式右端為文獻(xiàn)[10]類內(nèi)距離目標(biāo)函數(shù)值和類間距離之和，左側(cè)值:

J(U,V)+tr(SFE)受到隸屬度函數(shù)以及ai影響，不能確定min(tr(SFA))與max(tr(SFE))變化的一致性，即在確定類內(nèi)距離最小化的同時不能保證類間距離最大化。

(2)文獻(xiàn)[11]基于群體排斥思路添加懲罰項改進(jìn)FCM聚類算法，目標(biāo)函數(shù)為:

tr(SFT)=tr(SFA)+tr(SFE)左右加懲罰項，有:

等式右端為類內(nèi)距離優(yōu)化與類間分離度的和，左側(cè)值：

因此算法沒能有效實(shí)現(xiàn)類內(nèi)距離最小化與類間距離最大化的融合。

文獻(xiàn)[10,11]設(shè)置隸屬度函數(shù)作為懲罰項，雖然降低了總體離差tr(SFT)對uij依賴程度，但沒有實(shí)現(xiàn)JFCM最小化時tr(SFE)最大化有效融合。

(3)文獻(xiàn)[12]基于高斯函數(shù)設(shè)置距離測度，并增加懲罰項以解決類內(nèi)類間距離的融合問題。

目標(biāo)函數(shù)改進(jìn)了tr(SFE)，對某樣本點(diǎn)有:

若保證0≤uij≤1，則必有:

使得類間距離收縮到(0,1)范圍內(nèi)，在量級上與類內(nèi)距離差距較大，不利于實(shí)現(xiàn)不同類的劃分。

(4)文獻(xiàn)[6]在兼顧類內(nèi)距離與類間距離的基礎(chǔ)上，提出改進(jìn)型距離測度，其目標(biāo)函數(shù)為:

文獻(xiàn)[12,6]基于min(tr(SFA)-tr(SFE))思想，融合類內(nèi)類間距離，理論上能夠?qū)崿F(xiàn)類內(nèi)緊湊度與類間分離度同步最優(yōu)化，但不同量級的類內(nèi)類間距離差異大，會導(dǎo)致聚類效果不佳。

(5)文獻(xiàn)[13]在目標(biāo)函數(shù)中引入了聚類中心距離懲罰項，將類間距離分離度融合到目標(biāo)函數(shù)，有:

(6)文獻(xiàn)[14]在目標(biāo)函數(shù)中增添了最大中心間隔項與縮放因子η，避免了聚類中心趨于一致性。

雖然文獻(xiàn)[13,14]在類內(nèi)類間融合上提出了創(chuàng)新算法，但沒有有效解決類內(nèi)類間距離的差異性對FCM聚類的影響。

上述類內(nèi)與類間距離融合優(yōu)化并不能有效實(shí)現(xiàn)類內(nèi)距離最小化與類間距離最大化一致性變化，即聚類算法實(shí)現(xiàn)類內(nèi)距離最小化的迭代過程，類間距離不能同步實(shí)現(xiàn)最大化。

3 FCM改進(jìn)聚類算法設(shè)計

為了解決FCM聚類目標(biāo)函數(shù)中類內(nèi)距離和類間距離合成難的問題，實(shí)現(xiàn)類內(nèi)距離最小化且類間距離最大化的聚類目標(biāo)，本文將基于min(tr(SFA)-tr(SFE))的思想來設(shè)計FCM目標(biāo)函數(shù)，借助高斯核函數(shù)距離測度改進(jìn)目標(biāo)函數(shù)相似性函數(shù)，統(tǒng)一類內(nèi)類間距離的合成基礎(chǔ)。

類內(nèi)距離和類間距離的差異可以表示為:

tr(SFA)-tr(SFE)=JFCM-tr(SFE)

采用高斯核函數(shù)將特征空間X映射到H來替代歐式距離，又K(x,x)=1，映射過程為:

d(x,y)=‖Φ(x)-Φ(y)‖2

=(K(x,x)+K(y,y)-2gK(x,y))

=2(1-K(x,y))

高斯核函數(shù)對類內(nèi)類間距離進(jìn)行改進(jìn):

為了更好體現(xiàn)類內(nèi)距離與類間距離在目標(biāo)函數(shù)中的影響，實(shí)現(xiàn)類內(nèi)類間距離的有效比較，K(x,y)為exp(-‖x-y‖2)/σ2)，0≤K(x,y)≤1。基于高斯核函數(shù)的距離測度，d(xi,vj)∈(0,2)，d(vj,vk)∈(0,2)，保證了類內(nèi)與類間距離在距離范圍上的一致性，提供了類內(nèi)與類間距離融合的基礎(chǔ)。

對類內(nèi)與類間距離融合作如下設(shè)計：

改進(jìn)的類內(nèi)類間融合公式保證了類內(nèi)與類間距離非負(fù)性且值在區(qū)間(-2+2θ,2+2θ)內(nèi)，θ∈(0,1)為調(diào)控因子，平衡了類內(nèi)與類間距離的量級，確保了算法收斂性，區(qū)間上限提高了聚類算法的精確度。

令m控制分類的模糊程度，值越大表明模糊程度越高，σ2是給定數(shù)據(jù)方差。改進(jìn)型FCM聚類模型表示為:

(3)

利用拉格朗日乘子法建立無約束優(yōu)化目標(biāo)函數(shù):

(4)

(5)

(6)

(7)

(8)

于是，改進(jìn)的FCM聚類算法步驟表示為：

步驟1設(shè)定聚類個數(shù)、選取合適初始聚類中心點(diǎn)、模糊參數(shù)m、核函數(shù)參數(shù)σ、收斂精度ε、調(diào)控因子初始化為1/c、初始化迭代次數(shù)k=0；

步驟2依據(jù)式(5)計算各代表點(diǎn)隸屬度uij；

步驟3根據(jù)式(8)計算vj，令k=k+1；

步驟4若‖Uk+1-Uk‖≤ε，停止迭代，否則轉(zhuǎn)到步驟2；

步驟5輸出隸屬度矩陣U，聚類中心矩陣V。

4 算例研究

某企業(yè)為了設(shè)計針對學(xué)生人群的產(chǎn)品營銷計劃，選取了價格滿意度、服務(wù)水平、物流速度三個評價指標(biāo)，隨機(jī)調(diào)查了南京地區(qū)600名學(xué)生客戶(通過問卷星發(fā)放并收集問卷，本文作者負(fù)責(zé)設(shè)計與分析問卷)，通過實(shí)施客戶聚類實(shí)現(xiàn)精準(zhǔn)營銷。取m=2，θ=0.02，σ2=6，迭代終止條件cpsm=10-6。聚類中心點(diǎn)矩陣為:

圖1展示了本文提出的改進(jìn)型FCM聚類算法的收斂過程，算法在5次迭代計算后開始收斂。圖2為算法收斂后所有樣本點(diǎn)的隸屬度值，表現(xiàn)了樣本數(shù)據(jù)點(diǎn)對每一類的歸屬程度。

表1 改進(jìn)型FCM類間距離變化

采用經(jīng)典FCM算法進(jìn)行樣本點(diǎn)聚類時，取模糊參數(shù)m=2，epsm=10-6，聚類中心點(diǎn)矩陣為:

經(jīng)典FCM算法9次迭代后開始收斂，收斂曲線如圖3所示。圖4為經(jīng)典算法迭代收斂后所有樣本點(diǎn)的隸屬度值。

經(jīng)典FCM聚類目標(biāo)函數(shù)與類間距離變化值如表2。

比較圖1和圖4收斂曲線：改進(jìn)型FCM聚類算法5次迭代計算便開始收斂，經(jīng)典的FCM算法在第8次迭代計算才開始收斂，改進(jìn)型FCM算法能夠以更少的迭代次數(shù)實(shí)現(xiàn)算法的收斂，同時改進(jìn)型FCM聚類算法的收斂曲線更加平滑，算法的穩(wěn)定度更高。

通過對表1數(shù)據(jù)分析，隨著改進(jìn)型FCM聚類算法目標(biāo)函數(shù)值的減小，類間距離di,j不斷地增大，在目標(biāo)函數(shù)值最小時類間距離達(dá)到最大。表2數(shù)據(jù)顯示，經(jīng)典FCM聚類算法在前5次迭代過程中，類間距離di,j不斷增大，第5次迭代后，di,j隨著目標(biāo)函數(shù)值的變小呈現(xiàn)出先增大后減小的趨勢，第8次迭代類間距離達(dá)到最大值，而目標(biāo)函數(shù)值并未達(dá)到最小值，說明改進(jìn)型聚類算法能夠有效的實(shí)現(xiàn)類內(nèi)距離最小化與類間距離最大化的一致性變化。

表2 經(jīng)典FCM類間距離變化

為了進(jìn)一步驗(yàn)證本文提出的改進(jìn)算法可行性和有效性，采用國際上的標(biāo)準(zhǔn)測試數(shù)據(jù)UCI標(biāo)準(zhǔn)數(shù)據(jù)集Iris、Wine、Glass樣本數(shù)據(jù)。

由表3可知，在維度方面Wine>Glass>Iris，分類方面則Glass>Wine=Iris。綜合分類以及量級差異性程度，Glass>Wine>Iris。

表3 實(shí)驗(yàn)數(shù)據(jù)集

采用Windows7，Matlab編程環(huán)境，分別以經(jīng)典FCM聚類算法、KFCM聚類算法、本文提出改進(jìn)FCM算法流程對三類數(shù)據(jù)進(jìn)行聚類效果統(tǒng)計。得到表4。

表4 聚類算法迭代效果

Compactness(緊密性)(CP):

Separation(間隔性)(SP)：

由上表可知在Iris數(shù)據(jù)集中，本文提出算法較其他算法處于平均水平，沒有較為明顯的優(yōu)勢；分類數(shù)不變，量級出現(xiàn)偏差的高維數(shù)據(jù)集中，改進(jìn)算法在除聚類時間外的聚類效果表現(xiàn)中有一定的優(yōu)勢；而在量級差異較大且類簇更多的Glass數(shù)據(jù)總體來看，本文提出的改進(jìn)算法平均迭代次數(shù)相比于其他的算法在逐漸減小，說明隨著數(shù)據(jù)量級的差異變大以及類內(nèi)類間距離的差異性增加，本文改進(jìn)算法能夠提高聚類效率。

算法計算時間方面，改進(jìn)型聚類算法的時間復(fù)雜度為o(nkc)，與KFCM以及經(jīng)典FCM算法相同。實(shí)際耗費(fèi)時間上，對量級差異性不大的數(shù)據(jù)集，改進(jìn)型FCM的算法復(fù)雜導(dǎo)致效率不高，耗時較長，但是對量級差異較大的數(shù)據(jù)集，改進(jìn)行算法的迭代次數(shù)減少，時間降低。

結(jié)合改進(jìn)型算法的聚類結(jié)果，類與類間的區(qū)別更為明顯，可將調(diào)查學(xué)生群體劃分為四類，即高消費(fèi)人群、中等消費(fèi)人群、服務(wù)主導(dǎo)型人群、普通型消費(fèi)人群。針對不同的消費(fèi)人群制定針對性的營銷策略，例如，可以對高消費(fèi)人群推送奢侈商品廣告，對服務(wù)主導(dǎo)型人群可以推送服務(wù)型、提高生活質(zhì)量的商品廣告。

5 結(jié)論

不同量級數(shù)據(jù)聚類中聚類數(shù)據(jù)點(diǎn)的數(shù)量巨大，易造成聚類過程類內(nèi)與類間距離的影響差異較大的缺陷，從而導(dǎo)致FCM聚類算法不敏感。針對聚類過程中目標(biāo)函數(shù)沒有有效地平衡類內(nèi)與類間距離的問題，本文首先基于矩陣分解方式對類內(nèi)與類間距離的關(guān)系進(jìn)行分析，基于高斯核函數(shù)對類內(nèi)與類間距離進(jìn)行了融合，平衡類內(nèi)與類間的影響。算例表明，改進(jìn)的FCM聚類算法在處理大數(shù)據(jù)集的聚類過程中具有很好的收斂性以及魯棒性，但在處理小數(shù)據(jù)量以及類間距離效果不明顯，適用于處理類內(nèi)與類間距離差較大的情況。