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

李順勇， 余 曼， 王改變

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

聚類分析［1-3］是常見的多元統(tǒng)計分析方法的一個分支，被廣泛應(yīng)用于多個領(lǐng)域，如電信、保險、銀行和醫(yī)療數(shù)據(jù)庫中. 聚類的主要目的之一是對數(shù)據(jù)進(jìn)行分類，使得在同一個簇中對象間的距離盡可能小，在不同簇中對象間的距離盡可能大. 因此，數(shù)據(jù)聚類可以幫助我們深入了解數(shù)據(jù)的分布.

數(shù)據(jù)一般可以分為數(shù)值型、分類型以及混合型，根據(jù)數(shù)據(jù)類型不同，提出了各種各樣的聚類算法. k-means算法［4-5］是對數(shù)值型數(shù)據(jù)進(jìn)行聚類的算法之一，該算法是對數(shù)據(jù)計算均值然后將其聚類. 與數(shù)值型數(shù)據(jù)不同，由于分類數(shù)據(jù)的無序性和離散性，若還是計算它的均值，就會顯得牽強(qiáng)，因而k-means聚類過程不能直接用于分類數(shù)據(jù). 基于此，諸多研究人員發(fā)展了分類型數(shù)據(jù)聚類的幾種算法. Huang［6］在1998 年提出了k-modes 算法，對分類對象采用簡單匹配不相似度測量，用modes 代替means 來代表聚類的中心，并且提出了一種基于頻率的更新模式的方法. 這樣的處理使得聚類過程能夠?qū)Ψ诸悢?shù)據(jù)進(jìn)行聚類，消除了對于數(shù)值的限制.Cao［7］提出了一類時變數(shù)據(jù)的廣義聚類框架. Bai［8］提出了一種對于分類數(shù)據(jù)能同時找到初始聚類中心和聚類數(shù)的初始化方法. Liang［9］提出了一種用于高維分類數(shù)據(jù)聚類的屬性加權(quán)算法. Liang［10-14］基于多項(xiàng)度量對分類數(shù)據(jù)提出了多種聚類算法. Cao［15］對分類矩陣對象數(shù)據(jù)提出了一種新的算法：k-mw-modes算法.

本文利用簇間信息建立新的目標(biāo)函數(shù)；結(jié)合目標(biāo)函數(shù)提出了一種新的聚類算法；導(dǎo)出了隸屬度矩陣以及聚類原型的更新公式；在真實(shí)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，驗(yàn)證了該算法的有效性.

1 回顧k-modes算法

2 分類矩陣對象數(shù)據(jù)聚類算法（between-cluster k-modes，BC-k-modes）

2.1 簇間信息

2.2 對象間的相異性度量

2.3 BC-k-modes聚類算法

Algorithm：BC-k-modes算法

Input：

1：-n：每個集群中對象的數(shù)量；

2：-k：聚類個數(shù)；

3：-ε：閾值；

4：-X：由m個屬性描述的n個矩陣對象數(shù)據(jù)；

5：-idcenters：k個初始類中心的標(biāo)簽；

6：Output：

7：-cid：聚類后對象標(biāo)簽；

8：-num：迭代次數(shù)；

9：Method：

10：Z按照索引在idcenters中存儲k個初始中心，value=0,num=0；

11：while num ≤100 do

12： newvalue=0；

13： for i=1 to n do

14： for l=1 to k do

15： 通過式（7）計算第l個簇與其他簇之間的相似性度量；

16： 通過式（11）計算第i個對象到第l個聚類中心的距離；

17： 通過式（18）計算第i個對象到第l個聚類中心的隸屬度；

18： end for

19： end for

21： if |newvalue-value |≤ε，break；else value=newvalue 且num=num+1；

22： for l=1 to k do

23： 啟發(fā)式算法更新類中心；

24： end for

25：end while.

3 實(shí)驗(yàn)分析

在本節(jié)中，我們主要在Market Basket data（Data website下載），Market Basket data數(shù)據(jù)包括1001個用戶的交易記錄，Microsoft web data（UCI數(shù)據(jù)集下載），Microsoft web data記錄了1998年2月的一個星期內(nèi)隨機(jī)選擇的32 711個匿名用戶在訪問這些網(wǎng)站的情況，Musk data（UCI數(shù)據(jù)集下載），Musk data記錄由167個屬性描述的92個對象，MovieLens data（MovieLens website 下載），記錄了6040 個用戶對3900 部電影的1 000 209 條評分情況，Alibaba data（competition website 下載）記錄了793名用戶的165 655條的訪問記錄，在五個數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，來評估所提算法的有效性. 首先對五組數(shù)據(jù)進(jìn)行了數(shù)據(jù)預(yù)處理，接著使用文獻(xiàn)［15］中的五個評價指標(biāo)，將該算法與其他算法進(jìn)行比較. 五個真實(shí)數(shù)據(jù)集的預(yù)處理結(jié)果見表1.

表1 預(yù)處理后的數(shù)據(jù)集Tab.1 Preprocessed data sets

3.1 評價指標(biāo)

3.2 BC-k-modes算法與其他算法的比較

表2 在五個實(shí)驗(yàn)數(shù)據(jù)集上三種算法比較Tab.2 Three algorithms compared on five experimental data sets

表2 表明BC-k-modes 算法比SV-k-modes 算法相比在Market Basket data，Microsoft web data 兩個數(shù)據(jù)集AC，PR，RE 的值提高了15%，在ARI，NMI 上的值提高了30%，在Musk data 數(shù)據(jù)集上AC，PR，RE 的值提高了3%，ARI，NMI 上的值也有所提高，在MovieLens data 上AC，RE，ARI 的值提高了12%，最高提高了16%，在PR，NMI 的值提高了3%～5%，與Alibaba data 相比，AC，RE，ARI，NMI 提高了5%～9%，在PR 上也有所提高. 與k-mw-modes 算法相比，BC-k-modes 算法在AC，PR，RE，ARI，NMI 的值提高了2%～3%，說明聚類效果更好.

圖1～圖5分析了五組數(shù)據(jù)在五個評價指標(biāo)的箱線圖. 其中中間的黑線表示均值，上下值波動的幅度表示標(biāo)準(zhǔn)差.

從圖1～圖5可以看出，BC-k-modes算法的均值明顯高于SV-k-modes，k-mw-modes算法，且BC-k-modes算法是在k-mw-modes算法的基礎(chǔ)上增加簇間信息，還可以看出BC-k-modes算法比k-mw-modes算法的波動浮動更小，聚類的效果更穩(wěn)定.

圖1 五組數(shù)據(jù)在AC上的箱線圖Fig.1 Boxplots of five sets of data on AC

圖2 五組數(shù)據(jù)在PR上的箱線圖Fig.2 Boxplots of five sets of data on PR

圖3 五組數(shù)據(jù)在RE上的箱線圖Fig.3 Boxplots of five sets of data on RE

圖4 五組數(shù)據(jù)在ARI上的箱線圖Fig.4 Boxplots of five sets of data on ARI

圖5 五組數(shù)據(jù)在NMI上的箱線圖Fig.5 Boxplots of five sets of data on NMI

4 結(jié)論

本文對于矩陣對象數(shù)據(jù)提出了一種新的聚類算法：BC-k-modes. 在BC-k-modes算法中，首先給出矩陣對象之間的相異性度量，其次引入了簇間信息，提出了新的目標(biāo)函數(shù)，通過目標(biāo)函數(shù)解決了矩陣對象數(shù)據(jù)的聚類問題. 最后在五個真實(shí)數(shù)據(jù)集上驗(yàn)證了BC-k-modes算法的有效性.