基于分類型矩陣對象數(shù)據(jù)的MD fuzzy k-modes聚類算法

2019-06-26 10:18:06李順勇張苗苗曹付元

計算機研究與發(fā)展 2019年6期

李順勇張苗苗曹付元

1(山西大學(xué)數(shù)學(xué)科學(xué)學(xué)院太原 030006)2(山西大學(xué)計算機與信息技術(shù)學(xué)院太原 030006)

聚類算法中最具代表性的是k-means，k-modes，k-prototype算法，其中，k-means[1]主要用于對數(shù)值型數(shù)據(jù)進行聚類.現(xiàn)實中，分類型屬性數(shù)據(jù)也常見.1998年Huang[2]提出了k-modes算法，該算法用簡單匹配計算2個對象間的距離，用modes代替means，基于頻率來更新類中心.2001年Chaturvedi等人[3]改進了k-modes算法，提出了k-modes-CGC算法，有效地運用非參數(shù)方法對分類型數(shù)據(jù)進行聚類.隨后，Huang等人[4]證明了二者的等價性.此外，在初始類中心的選取上，Ying等人[5]考慮將迭代求精法與k-modes算法結(jié)合；在相異性度量的選取上，Ng等人[6]和San等人[7]基于屬性頻率計算相似度，Li等人[8]基于生物特征計算距離.Liang等人[9-14]也基于不同度量提出了多種k-modes的改進算法.

以上種種算法在考慮類別歸屬時，其隸屬度只考慮了0，1這2個值，即只能劃分到確定的某一類中，屬于硬劃分.而數(shù)據(jù)的不同屬性重要度會給部分數(shù)據(jù)的真實類別歸屬帶來模糊性.粗糙集[15]和模糊集[16]理論的提出為數(shù)據(jù)在數(shù)據(jù)集中的位置提供了有利的基礎(chǔ)，軟劃分應(yīng)運而生.Bezdek提出的fuzzyc-means(FCM)算法[17]是軟劃分聚類的典例.1999年Huang等人[18]在FCM算法的基礎(chǔ)上引進模糊因子、隸屬度矩陣等，進一步提出fuzzyk-modes算法.2004年Kim等人[19]用模糊集對類中心的模糊化刻畫分類數(shù)據(jù)中類的不確定性，提出了具有模糊類中心的Fuzzyk-modes算法.2005年Li等人[20]提出了基于特征加權(quán)的模糊聚類新算法(novel feature weighted clustering algorithm, NFWFCA).2007年Cai等人[21]結(jié)合局部空間和灰度信息，提出了快速通用的聚類算法(fast generalized fuzzyc-means, FGFCM).2016年Zhou等人[22]結(jié)合多目標(biāo)優(yōu)化算法與模糊中心點聚類，提出一種新穎的多目標(biāo)模糊聚類算法.總之，k-modes算法對后續(xù)眾多的拓展算法起到了積極的鋪墊作用.

已有的聚類算法普遍使用X={X1,X2,…,Xn}的數(shù)據(jù)表示模式，X表示由n個對象組成的對象集，Xi=(Xi1,Xi2,…,Xim)表示每個對象由m個屬性特征描述，每個屬性特征有且僅有唯一的取值.然而實際應(yīng)用中，對象的每個屬性特征可能有不同的取值.例如顧客購物時，可能同時購買多個產(chǎn)品，這就容易產(chǎn)生矩陣對象數(shù)據(jù)[23].若利用已有的聚類算法處理該類數(shù)據(jù)，需用先驗知識來選取其中一條記錄，這會嚴重損失信息并破壞數(shù)據(jù)的原始性，且違背了以數(shù)據(jù)總體來做數(shù)據(jù)分析的初衷.因此，為了利用多條消費記錄發(fā)現(xiàn)客戶的消費喜好，從而做出更具針對性的推薦[23]，有必要研究基于矩陣對象數(shù)據(jù)的聚類算法.Cao等人[24]首先提出基于集值對象的Set-Valuek-modes (SV-k-modes)算法和fuzzy Set-Valuek-modes(fuzzy SV-k-modes)算法[25].之后，Cao等人又提出基于矩陣對象的k-multi-weighted-modes(k-mw-modes)聚類算法[23].該算法在考慮類別歸屬的同時，其隸屬度也僅僅考慮了0，1這2個值.由于數(shù)據(jù)集中屬性重要度的不同，常常會給部分數(shù)據(jù)的真實類別歸屬帶來模糊性.本文兼顧模糊集引入模糊因子，提出一種基于矩陣對象數(shù)據(jù)的模糊聚類算法(matrix-object data fuzzyk-modes, MD fuzzyk-modes).本文的主要貢獻有4個方面：

1) 結(jié)合模糊集的概念提出了一種更新類中心啟發(fā)式算法；

2) 提出了基于分類型矩陣對象數(shù)據(jù)的MD fuzzyk-modes聚類算法；

3) 實驗驗證了MD fuzzyk-modes算法的有效性；

4) 分析了模糊因子β與隸屬度w的關(guān)系.

1 回顧fuzzy k-modes算法

設(shè)X={X1,X2,…,Xn}是由n個對象、m個屬性描述的分類型數(shù)據(jù)集，則Xi與Xj間的相異性度量定義為

(1)

Q是X的類中心，如果Q能最小化

(2)

fuzzyk-modes算法用迭代方式將數(shù)據(jù)分為k類，此算法的目的是最小化目標(biāo)函數(shù)：

(3)

其中，W為隸屬度矩陣.

2 MD fuzzy k-modes聚類算法

經(jīng)典的k-type算法[1-2]主要由3部分組成：相異性度量的定義、類中心的表示和類中心的更新過程.本文提出的MD fuzzyk-modes算法也從這3方面考慮.

2.1 矩陣對象間的相異性度量

用簡單0-1匹配、屬性頻率等相異性度量來計算數(shù)據(jù)間的距離適用于1對1對象數(shù)據(jù)，而矩陣對象數(shù)據(jù)每個屬性有多于一個的屬性值，這些相異性度量對矩陣對象數(shù)據(jù)有一定的局限性，由于k-mw-modes算法[23]中定義了2個矩陣對象間的相異性度量，本文直接引用此相異性度量.

定義1.相異性度量.給定矩陣對象Xi,Xj，每個對象由m個分類型屬性{A1,A2,…,Am}來描述，則Xi與Xj的相異性度量定義為

(4)

其中：

δ(Xis,Xjs)=

(5)

(6)

可以驗證該相異性度量滿足非負性、對稱性和三角不等式性，的確是一個距離.

例1.表1是某一矩陣對象數(shù)據(jù)集的描述，其中X={X1,X2}，A={A1,A2}，計算X1,X2間的距離.

Table 1 A Matrix-Object Data Set表1 某一矩陣對象數(shù)據(jù)集

2.2 類中心的定義及啟發(fā)式更新過程

定義2.類中心.如果Ql能使目標(biāo)函數(shù)達到最小:

(7)

則Ql是X的類中心.

這種全局性更新類中心算法的時間復(fù)雜度為O(nmtk×2|V′|)，n表示對象數(shù)，m表示屬性個數(shù)，k表示分類個數(shù)，t表示迭代次數(shù)，|V′|=max{|Vs|,1≤s≤m}.由此可知，全局性更新類中心的算法時間復(fù)雜度隨著對象個數(shù)、屬性個數(shù)、分類數(shù)及迭代次數(shù)的增多呈線性增長，屬性值的個數(shù)呈指數(shù)增長.

當(dāng)矩陣對象數(shù)據(jù)中屬性值個數(shù)過多時，全局更新類中心的算法計算量過大，耗時增強，故本文提出了啟發(fā)式更新類中心算法.首先分析

(8)

2.3 MD fuzzy k-modes聚類算法

本文在k-mw-modes算法的基礎(chǔ)上，引入模糊因子并改進了類中心的表示及更新過程，提出了MD fuzzyk-modes算法.

定義3.最小化目標(biāo)函數(shù).將一矩陣對象數(shù)據(jù)集X={X1,X2,…,Xn}劃分為k類，則需最小化目標(biāo)函數(shù):

(9)

且滿足:

wli∈[0,1], 1≤l≤k, 1≤i≤n,

(10)

(11)

(12)

其中，Q=(Q1,Q2,…,Qk)中的元素Ql表示第l類的中心，Ql=(Ql1,Ql2,…,Qlm);W=(wli)是一個k×n維的隸屬度矩陣，wli=1表示Xi被分到l類.

為使F′(W,Q)達到最小，要通過多次迭代過程使其收斂：1) 初始化類中心Qt；2) 固定Qt，找出使F′(W,Q)最小的Wt；3) 固定Wt，用啟發(fā)式更新算法找出Qt+1使F′(W,Q)達到最小；4) 重復(fù)步驟1)2)3)，直到類中心不變或目標(biāo)函數(shù)小于閾值為止.

其中，隸屬度矩陣W由定理1計算而來，類中心Q的更新由啟發(fā)式更新算法而來.

定理1.固定Q，在式(10)～(12)的限制下使F′(W,Q)最小，則W的更新為

(13)

MD fuzzyk-modes算法的基本步驟：

1) 隨機選取k個對象作為初始類中心；

2) 根據(jù)2.1節(jié)，計算每個對象到k個中心的距離，將對象分配到與其距離最小的類中；

3) 根據(jù)2.2節(jié)，計算每個對象到k個中心的隸屬度，并更新k個類的類中心；

4) 重復(fù)步驟2)3)，直到類中心或目標(biāo)函數(shù)不變?yōu)橹?

算法1.MD fuzzyk-modes算法.

輸入：X為由m個屬性描述的n維矩陣對象數(shù)據(jù),k為需要聚類個數(shù),ε為閾值,idCenters為k個初始類中心的標(biāo)簽,β為模糊因子；

輸出：cid是聚類后所有對象的標(biāo)簽,num是迭代次數(shù).

①Q(mào)是初始類中心，value=0，num=0；

② whilenum<100 do

③newvalue=0;

④ fori=1 tondo

⑤ forl=1 tokdo

⑥ 計算第i個對象到第l個中心的距離d(Xi,Ql)(用式(4))；

⑦ end for

⑧ end for

⑨ fori=1 tondo

⑩ forl=1 tokdo

3 實驗分析

為了評價MD fuzzyk-modes算法的有效性，本文考慮了5個真實數(shù)據(jù)集：Market Basket，Micro-soft Web，Musk，MovieLens，Alibaba.Market Basket記錄了1 001個顧客的交易記錄，每條記錄由用戶ID、交易時間、產(chǎn)品名稱和產(chǎn)品ID這4個屬性描述；Microsoft Web來自UCI數(shù)據(jù)集，記錄了1998年1月份某周內(nèi)32 711個匿名用戶的網(wǎng)頁瀏覽情況，每個用戶由用戶ID和網(wǎng)頁ID這2個屬性描述；Musk也來自UCI數(shù)據(jù)集，包括92個對象，每個對象由167個屬性描述；MovieLens從MovieLens網(wǎng)站上下載，本文只使用其中的ratings數(shù)據(jù)，它記錄了6 040個觀眾對3 900部電影的1 000 209條評分情況，每條記錄由用戶ID、電影ID、用戶評分和提交評價的時間這4個屬性描述;Alibaba是884個用戶瀏覽某些品牌的182 880條記錄，也由4個屬性描述.這5個數(shù)據(jù)集均為矩陣對象數(shù)據(jù)集.為了增強聚類效果，本文對各數(shù)據(jù)集的屬性做了相應(yīng)的預(yù)處理,預(yù)處理后的數(shù)據(jù)形式如表2所示：

Table 2 Data Set after Preprocessing表2 預(yù)處理后的數(shù)據(jù)集

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

本文采用精度(AC)、純度(PR)、召回率(RE)、蘭德指數(shù)(ARI)、歸一化互信息(NMI)這5個評價指標(biāo)對所提算法進行了有效性評價.AC表示分類正確的比例;PR表示預(yù)測為正的樣本中有多少是對的;RE表示樣本中的正例有多少被預(yù)測正確;ARI和NMI用來衡量2個數(shù)據(jù)分布的吻合程度.AC，PR，RE，ARI，NMI的值越大，聚類結(jié)果越接近于數(shù)據(jù)集的真實劃分，聚類效果越好.

設(shè)X是一矩陣對象數(shù)據(jù)集，C={C1,C2,…,Ck}是X的聚類結(jié)果，P={P1,P2,…,Pk′}是真實標(biāo)簽，聚類個數(shù)為k，真實類別數(shù)為k′.假定k=k′，5種評價指標(biāo)定義為

(14)

(15)

(16)

(17)

(18)

3.2 啟發(fā)式與全局性更新類中心算法的比較

為了評價啟發(fā)式更新類中心算法的有效性，本節(jié)在用MD fuzzyk-modes算法聚類的過程中，分別采用啟發(fā)式(HAMF)和全局性算法(GAMF)更新類中心，對比了實驗結(jié)果與運行時間.以Market Basket為例，運行10次，結(jié)果如表3和表4所示.其中,表3的“±”前后分別表示均值和標(biāo)準(zhǔn)差.

Table 3 Comparison Results of the MD fuzzy k-modes Algorithms with GAMF and HAMF表3 在MD fuzzy k-modes算法中用GAMF和HAMF更新類中心的結(jié)果比較

Table 4Running Time of the MD fuzzyk-modes Algorithms

with GAMF and HAMF

表4 MD fuzzyk-modes算法中用GAMF和HAMF更新

類中心的運行時間

AlgorithmsRunning Time∕sMD fuzzy k-modes+GAMF3.46725×105 MD fuzzy k-modes+HAMF160.313812

Notes: The bold value represents that the running time of the MD fuzzyk-modes algorithm with HAMF is much shorter than GAMF.

從表3和表4可以看出，用全局性算法更新類中心的聚類效果要好于啟發(fā)式更新算法，但耗時長達96 h.而啟發(fā)式更新算法在聚類效果相似的情況下只需耗時160 s.因此，在用MD fuzzyk-modes算法進行聚類時，選用本文提出的啟發(fā)式更新算法更有效.

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

本文選SV-k-modes，k-mw-modes，fuzzyk-modes，fuzzy SV-k-modes這4種算法與MD fuzzyk-modes算法進行比較，其中，fuzzyk-modes算法必須把矩陣數(shù)據(jù)轉(zhuǎn)換為單值屬性值形式，SV-k-modes，fuzzy SV-k-modes算法需把矩陣數(shù)據(jù)轉(zhuǎn)換為集值數(shù)據(jù)形式.在與SV-k-modes，k-mw-modes算法比較時，由于這2種算法不含模糊因子β，本文假定MD fuzzyk-modes算法中的β=1.1.在與fuzzyk-modes，fuzzy SV-k-modes算法進行比較時，由于在fuzzyk-type聚類算法[17-21]中，初始類中心的選取和模糊因子β對聚類結(jié)果有重要的影響，不同的初始化類中心和不同的β取值會導(dǎo)致聚類結(jié)果不同.本文從這2方面驗證MD fuzzyk-modes算法的有效性.在β的取值上，目前很多學(xué)者研究這一問題.Pal和Bezdek[26]在fuzzyk-means算法中設(shè)置β∈[1.5,2.5]，Zhou等人[27]認為β的最優(yōu)區(qū)間是[2.5,3]，Huang等人[18]設(shè)置最小值β=1.1.由于β的取值沒有公認的準(zhǔn)則，目前研究的最小值為1.1，最大值為3.本文設(shè)置β∈[1.1,2.9]，步長為0.2.在初始類中心的選擇上，本文隨機初始化類中心30次，即2種算法在不同的β取值下分別運行30次，通過計算平均聚類質(zhì)量來驗證MD fuzzyk-modes算法的有效性.數(shù)據(jù)集Market Basket，Microsoft Web，Musk，MovieLens，Alibaba在這5種評價標(biāo)準(zhǔn)上的實驗結(jié)果如表5～9所示.其中，“±”前后分別表示30次實驗結(jié)果的均值和標(biāo)準(zhǔn)差.

從表5可以看出，在不考慮模糊因子β的情況下，新提出的MD fuzzyk-modes算法比SV-k-modes算法、k-mw-modes算法在5種評價標(biāo)準(zhǔn)上的值高，說明聚類效果更好.

表6～9顯示，考慮模糊因子β時， MD fuzzyk-modes算法相較fuzzyk-modes算法在5種評價標(biāo)準(zhǔn)上的值有明顯提高.尤其是Market Basket和Microsoft Web數(shù)據(jù)集上，AC，PR，RE，ARI，NMI值有30%～60%的提高，這說明MD fuzzyk-modes算法要比fuzzyk-modes算法的聚類效果好得多.在MovieLens數(shù)據(jù)集上RE值雖有所下降，但在其他評價標(biāo)準(zhǔn)上有20%左右的提高；Musk數(shù)據(jù)集的實驗結(jié)果雖然沒有前3個數(shù)據(jù)集的效果明顯，但仍比fuzzyk-modes算法的值高.再者，相較fuzzy SV-k-modes算法，5種評價標(biāo)準(zhǔn)上的值也有所提高.在Market Basket和Microsoft Web數(shù)據(jù)集上，AC，PR，RE，ARI，NMI值有10%～20%的提高，在Musk，MovieLens數(shù)據(jù)集上的值相近，但比fuzzy SV-k-modes算法的值高，也說明聚類效果好.

上述實驗結(jié)果充分驗證了MD fuzzyk-modes算法對矩陣對象數(shù)據(jù)進行聚類具有較好的可行性與有效性.