Fuzzy BC-k-modes：一種分類矩陣對象數(shù)據(jù)的聚類算法

李順勇 余 曼 王改變

(山西大學(xué)數(shù)學(xué)科學(xué)學(xué)院 山西 太原 030006)

0 引 言

對于數(shù)據(jù)進(jìn)行劃分時,目前基本上分為兩種劃分。第一種是硬劃分,考慮其類別歸屬時,一般只考慮0、1這兩個值,也就是只能把數(shù)據(jù)劃分到某一個確定的類別中。數(shù)據(jù)一般可分為三類：數(shù)值型數(shù)據(jù)、分類型數(shù)據(jù)和混合型數(shù)據(jù)。與其相對應(yīng)數(shù)據(jù)的硬劃分的聚類算法具有代表性的是k-means、k-modes和k-prototype算法。對于數(shù)值型數(shù)據(jù),一般采用k-means[1]算法計算均值,然后對其聚類。Zhou等[2]2015年提出一種基于代數(shù)圖論的聚類方法,可用來求解大規(guī)模譜聚類的近似加權(quán)核k-means算法。Li等[3]利用和改進(jìn)k-means聚類技術(shù),提出了一種新的文本聚類算法。對于分類型數(shù)據(jù),由于其數(shù)據(jù)類型是離散并且無序的,故而不能直接用數(shù)值型數(shù)據(jù)的聚類算法去進(jìn)行聚類。很多學(xué)者對此進(jìn)行了研究,主要有以下幾種聚類算法：Huang等[4]1998年提出了k-modes算法對分類數(shù)據(jù)進(jìn)行聚類,主要思想是用modes代替means,是一種簡單的匹配不相似度量的聚類算法；林強(qiáng)等[6]綜合考慮有序型分類數(shù)據(jù)中的屬性值之間順序關(guān)系、無序型分類數(shù)據(jù)中不同屬性值間的相似性以及考慮各屬性間的關(guān)系，提出一種適用于混合型分類數(shù)據(jù)的改進(jìn)的聚類算法；Ng等[7]2007年提出基于屬性的頻率計算相似度的方法；Cao等[19]提出了k多權(quán)重模式算法對分類矩陣對象數(shù)據(jù)進(jìn)行聚類,通過定義兩個分類對象數(shù)據(jù)之間的距離,提出了一種多權(quán)重模式的聚類原型的表示方法。由于不同數(shù)據(jù)在數(shù)據(jù)庫中占有不同的比例,軟劃分由此產(chǎn)生。Huang等[20]1999年提出了模糊集的概念,引入了關(guān)于模糊因子和隸屬度矩陣的概念,進(jìn)一步提出了fuzzy k-modes算法。隨后,李順勇等[21]通過引入模糊因子,定義了矩陣對象之間的相異性度量,提出一種對于矩陣對象數(shù)據(jù)的MD fuzzy k-modes聚類算法。對于混合型數(shù)據(jù)，李順通等[24]提出了一種帶權(quán)的混合數(shù)據(jù)確定算法。

本文的研究思路和內(nèi)容為：1) 引入簇間信息，即不同類中的對象到其他類中心的距離。2) 利用簇間信息及模糊因子構(gòu)建新目標(biāo)函數(shù);導(dǎo)出隸屬度原型以及聚類中心的更新公式。3) 提出Fuzzy BC-k-modes算法。4) 在四個真實數(shù)據(jù)集上進(jìn)行了實驗,驗證所提算法的有效性。

1 Fuzzy BC-k-modes聚類算法

面向1對1對象數(shù)據(jù)之間的度量一般采用0-1匹配來度量它們之間的距離,然而本文所研究的分類矩陣對象數(shù)據(jù)中每一個屬性對應(yīng)著多個分類值,用0-1匹配度量具有局限性,因此,本文引入文獻(xiàn)[19]中所提的差異性度量。

1.1 對象間的相異性度量

定義1x={x1,x2,…,xn}是由m個分類屬性{a1,a2,…,am}所描述的一組n個分類型矩陣對象數(shù)據(jù)集,其中xi={xi1,xi2,…,xim},1≤i≤n。xi和xj之間的不相似度量為：

(1)

其中：

(2)

(3)

基于該距離度量的目標(biāo)函數(shù)為：

(4)

其中：

f(·,·)是一個函數(shù),當(dāng)兩個參數(shù)值相等,取值為1,否則取值為0。|·|表示一個值的絕對值。

要最小化式(4),需要迭代求解兩個子問題：

(5)

式中：1≤i≤n,1≤l≤k。

由文獻(xiàn)[20]可知,Z計算如下：

(6)

上述W和Z的更新公式僅僅依賴于簇內(nèi)信息,然而,一個好的聚類結(jié)果應(yīng)當(dāng)具有簇內(nèi)相似度高以及簇間相似度低。上述更新公式忽略了簇間相似性,導(dǎo)致簇間分離較弱。下面從兩方面分析其重要性。

1) 固定Z計算W若只考慮簇內(nèi)信息,如圖1所示,可以看到d(xi,z1)=d(xi,z2)

圖1 簇間信息固定Z計算W

2) 固定W計算Z若只考慮簇內(nèi)信息基于每一個分類值在聚類中的頻率去表示聚類的中心,將會導(dǎo)致集群中分類值出現(xiàn)的頻率起決定作用,然而分類值出現(xiàn)的頻率很可能被高估,因為分類值在其他簇中也可能會出現(xiàn)較高的頻率。例如：表1展示了三個簇中的屬性分布,由表1可以看出,分類值A(chǔ)在Cluster2中出現(xiàn)的頻率最高,并且在其他簇中出現(xiàn)頻率較低,故可以用分類值A(chǔ)表示Cluster2的中心,但分類值B在Cluster3中出現(xiàn)的頻率最高,但在Cluster1中出現(xiàn)的頻率也相對較高,相比較而言,雖然分類值C在Cluster3的頻率低于分類值B的頻率,但分類值C集中出現(xiàn)在Cluster3中,因此,用分類值C表示Cluster3的中心更好。這表明如果僅僅只考慮頻率最高作為聚類的中心,將產(chǎn)生不太好的結(jié)果。

表1 簇間信息固定W計算Z

從上面的分析可以看出,簇間信息有助于在迭代過程中獲得更好的W和Z。因此,我們將給出簇間信息的定義,并提出新的聚類算法,同時考慮簇間信息及簇內(nèi)信息。

1.2 簇間信息

定義2zl表示第l個簇原型,zh表示第h個簇原型,h和l不相等,則zl和zh之間的相似性度量為：

(7)

定義3zl表示第l個簇原型,由zl表示的第l個簇與其他簇之間的相似性度量為：

(8)

定義4基于簇間分離的目標(biāo)函數(shù)為：

(9)

要最小化式(8),需要迭代求解以下兩個子問題：

(10)

基于此,對簇間分離目標(biāo)函數(shù)進(jìn)行評價：

(11)

(12)

式中：1≤j≤m,1≤l≤k。

1.3 啟發(fā)式更新類中心

定義5如果Zl能使下面的目標(biāo)函數(shù)Fn(W,Zl,γ)達(dá)到最小,則稱Zl是W的類中心。

Fn(W,Zl,γ)=F′(W,Zl)+γB(W,Zl)=

(13)

參數(shù)γ用來調(diào)整簇內(nèi)信息以及簇間信息對于目標(biāo)函數(shù)最小化的影響。

1) 當(dāng)γ>0時,B(W,Z)對Fn(W,Z,γ)的最小化起到重要作用,聚類過程嘗試將這些點分配到離A相對較遠(yuǎn)的一個聚類中,使簇間相似度減少,當(dāng)對象的位置固定時,為了使簇間相似度減少,聚類過程會將聚類原型移動到離A代表點較遠(yuǎn)的位置。然而,γ的值不應(yīng)該太大,這是因為若γ很大時,簇間相似項會占主導(dǎo)地位,聚類原型會被移動到的離群值。

2) 當(dāng)γ=0時,B(W,Z)對Fn(W,Z,γ)的最小化不起任何作用,聚類過程將使簇內(nèi)分離最小。

3) 當(dāng)γ<0時,聚類過程會將聚類原型移動A到代表點位置,這與聚類原始思想矛盾,因此γ不能小于0。

基本算法步驟描述如下：

1) 令Γ={γ1,γ2,…,γo}是這樣一個序列,其中γ1>γ2>…>γo,選擇一個初始點集Ze?R,設(shè)置e=1。

(14)

(15)

1.4 Fuzzy BC-k-modes聚類算法

基于此,提出一種Fuzzy BC-k-modes聚類算法。首先給出了一個新目標(biāo)函數(shù)：

Fn(W,Z,γ)=F′(W,Z)+γB(W,Z)=

(16)

要最小化目標(biāo)函數(shù)式(13),需要迭代求解以下兩個子問題：

(17)

對于1≤i≤n,1≤l≤k。

(18)

(19)

是非負(fù)并且獨立的,令：

(20)

(21)

式中：1≤j≤m,1≤l≤k。

算法1Fuzzy BC-k-modes算法

輸入：n：每個集群中對象的數(shù)量;k：聚類個數(shù);α：模糊因子;ε：閾值;X：由m個屬性描述的n個矩陣對象數(shù)據(jù);idcenters：k個初始類中心的標(biāo)簽。

輸出：cid：聚類后對象標(biāo)簽;num：迭代次數(shù)。

1.Method：

2.Z按照索引在idcenters中存儲k個初始中心,value=0,num=0;

3.whilenum≤100 do

4.newvalue=0;

5.fori=1 tondo

6.forl=1 tondo

7.通過式(1)計算第i個對象到第l個聚類中心的距離;

8.通過式(8)計算第l個簇與其他簇之間的相似性度量;

9.通過式(18)計算第i個對象到第l個聚類中心的隸屬度;

10.end for

11.end for

13.if |newvalue-value|≤ε,break；

elsevalue=newvalue且num=num+1;

14.forl=1 tokdo

15.使用1.3節(jié)啟發(fā)式更新類中心;

16.end for

17.end while

2 真實數(shù)據(jù)實驗

本節(jié)主要在Market basket data(Data website下載),Microsoft web data(UCI數(shù)據(jù)集下載),Movielens data(Movielens website下載),Alibaba data(competition website下載)四個數(shù)據(jù)集上進(jìn)行了實驗。首先對四組數(shù)據(jù)進(jìn)行了數(shù)據(jù)預(yù)處理,接著利用五個評價指標(biāo)進(jìn)行了有效性分析,最后,將該算法與其他算法進(jìn)行比較,并且討論了模糊因子與隸屬度之間的關(guān)系。

2.1 數(shù)據(jù)預(yù)處理

為了獲得給定數(shù)據(jù)集的結(jié)構(gòu),使用了多維縮放技術(shù)來可視化數(shù)據(jù),該技術(shù)主要目標(biāo)是通過n×n的距離矩陣去得到一個n行,p列的結(jié)構(gòu)。從MATLAB傳遞到函數(shù),n個點之間的歐氏距離近似于n×n距離矩陣中對應(yīng)的不相似點的單調(diào)變換,因此,可以可視化n個點來反映數(shù)據(jù)的分布。為了使數(shù)據(jù)可視化,設(shè)置p=2。四個真實數(shù)據(jù)集的預(yù)處理結(jié)果如表2所示。

表2 預(yù)處理后的數(shù)據(jù)集

2.2 評價標(biāo)準(zhǔn)

為了去評價所提出算法的有效性,我們采用了以下的五個外部指標(biāo)：(1)ARI(蘭德指數(shù),衡量兩個數(shù)據(jù)分布的吻合程度);(2)AC(精度,表示正確分類的測試實例的個數(shù)占測試實例總數(shù)的比例);(3)PR(純度,也叫查準(zhǔn)率,表示正確分類的正例個數(shù)占分類為正例的實例個數(shù)的比例);(4)RE(召回率,也叫查全率,表示正確分類的正例個數(shù)占實際正例個數(shù)的比例);(5)NMI(歸一互化信息,衡量兩個數(shù)據(jù)分布的吻合程度)。可以明顯看出,五個評價指標(biāo)值越大,聚類結(jié)果越好。

(22)

(23)

(24)

(25)

(26)

2.3 MD fuzzy k-modes算法與其他算法的比較

選取SV-k-modes、k-mw-modes、fuzzy k-modes、fuzzy SV-k-modes、MD fuzzy k-modes這五種算法與Fuzzy BC-k-modes算法進(jìn)行比較。與SV-k-modes、k-mw-modes比較時,由于這兩種算法里不含有模糊因子,因此將新提出的算法的模糊因子設(shè)為1.1。在與fuzzy k-modes、fuzzy SV-k-modes和MD fuzzy k-modes這三種算法比較時,不同的模糊因子對于聚類結(jié)果存在不同的影響,很多學(xué)者已經(jīng)研究過這一問題,Huang[20]設(shè)置模糊因子的最小值為1.1,Zhou[28]認(rèn)為模糊因子的最優(yōu)區(qū)間[2.5,3],Pal等[29]在fuzzyk-means算法中建議采取[1.5,2.5],Yu等[26]提出了模糊因子的理論上界。在這個實驗中設(shè)置選取序列Γ={γ1,γ2,…，γo}，設(shè)置γ1=1,γ0=0且γe+1=γe-0.1，設(shè)置1≤e

表3 在五個數(shù)據(jù)集上三種算法比較

表3顯示,在不考慮模糊因子的情形下,與SV-k-modes算法相比說明Fuzzy BC-k-modes算法在Market Basket data、Microsoft Web data、Movielens data上的AC、PR、RE值有15%～25%的提高,ARI、NMI的值有20%～40%的提高。在Alibaba data數(shù)據(jù)集上AC、RE、ARI、NMI的值有10%左右的提高。與k-mw-modes算法相比，F(xiàn)uzzy BC-k-modes算法在四個真實數(shù)據(jù)集的五個評價指標(biāo)上的值有約3%的提高,最高提高8%,說明Fuzzy BC-k-modes算法的聚類效果要優(yōu)于k-mw-modes算法。

從表4-表7可以看出,當(dāng)考慮模糊因子時,與fuzzy k-modes算法相比, Fuzzy BC-k-modes算法在Market Basket data上和Microsoft Web data上的AC、PR、RE值有30%～35%的提高,ARI、NMI的值有60%的提高,在Movielens data上和Alibaba data上,雖然RE值有所下降,但AC、PR值有10%的提高,ARI、NMI的值有15%的提高,說明Fuzzy BC-k-modes算法的聚類效果要優(yōu)于fuzzy k-modes算法。與fuzzy SV-k-modes算法相比,Fuzzy BC-k-modes算法在Market Basket和Microsoft Web data上AC、PR、RE值有10%的提高,ARI、NMI的值有20%的提高,在Movielens data和Alibaba data上AC、PR、RE、ARI、NMI的值有約4%的提高,說明Fuzzy BC-k-modes的算法的聚類效果要優(yōu)于fuzzy SV-k-modes。與MD fuzzy k-modes算法相比,Fuzzy BC-k-modes算法在四個真實數(shù)據(jù)集的五個評價指標(biāo)上的值有3%的提高,說明Fuzzy BC-k-modes算法的聚類效果要優(yōu)于MD fuzzy k-modes算法。

表4 在Market Basket data數(shù)據(jù)集上四種算法的對比

續(xù)表4

表5 在Microsoft Web data數(shù)據(jù)集上四種算法的對比

表6 在MovieLens data數(shù)據(jù)集上四種算法的對比

續(xù)表6

表7 在Alilibaba data數(shù)據(jù)集上四種算法的對比

2.4 α與W的關(guān)系

模糊因子的大小影響到對象分配到不同集群的隸屬度,因此研究模糊因子與隸屬度之間的關(guān)系是非常有必要的。實驗分析了四個數(shù)據(jù)集上模糊因子與隸屬度之間的關(guān)系,模糊因子的值從1.1到2.9,步長為0.2,由于所要研究的數(shù)據(jù)集中對象個數(shù)過多,在2.1節(jié)已經(jīng)對數(shù)據(jù)進(jìn)行預(yù)處理,因此只在每個數(shù)據(jù)集可視化前十個對象作為其研究對象,分別在四個數(shù)據(jù)集上進(jìn)行了30次實驗,取其平均值,實驗結(jié)果如圖2-圖5所示。

圖2 在Market Basket數(shù)據(jù)集上α與W的關(guān)系圖

圖3 在Microsoft Web數(shù)據(jù)集上α與W的關(guān)系圖

圖4 在MovieLens數(shù)據(jù)集上α與W的關(guān)系圖

圖5 在Alibaba數(shù)據(jù)集上α與W的關(guān)系圖

圖2-圖5顯示了隸屬度與模糊因子α之間確實存在關(guān)系。隨著模糊因子α的增大,曲線越平緩,即隸屬于同一類的可能性越大。

3 結(jié) 語

本文對于矩陣對象數(shù)據(jù)提出了一種新的聚類算法：Fuzzy BC-k-modes算法。在Fuzzy BC-k-modes算法中,首先給出矩陣對象之間的差異性度量,其次引入了簇間信息,集成了簇內(nèi)信息和簇間信息,提出了新的目標(biāo)函數(shù),通過修改目標(biāo)函數(shù)的方法解決矩陣對象數(shù)據(jù)的聚類問題,然后,提出了一種Fuzzy BC-k-modes算法。最后在四個數(shù)據(jù)集上進(jìn)行了實驗,驗證了Fuzzy BC-k-modes算法的有效性。與此同時，本文提出的算法對未來解決包含各種復(fù)雜簇結(jié)構(gòu)的問題，以及考慮如何融入簇間差距的問題上將會有較好的啟發(fā)作用。