基于互信息量的改進(jìn)K-Modes聚類方法

吳潤秀

（南昌工程學(xué)院計算 機(jī)系，南昌 330099）

0 引言

聚類算法常被稱為一種無監(jiān)督的學(xué)習(xí)方法，聚類分析是數(shù)據(jù)挖掘中的主要技術(shù)之一，聚類分析是根據(jù)組內(nèi)相似度高，組間相似度低的原則將數(shù)據(jù)對象進(jìn)行分類。在聚類過程中一個關(guān)鍵問題就是相似性度量的定義,當(dāng)數(shù)據(jù)對象的每個特征均是數(shù)值型(實(shí)數(shù),整數(shù))時,相似性度量的定義有諸多選擇,因?yàn)榇朔N情形每個數(shù)據(jù)對象可用n維空間中的向量來表示(n為特征個數(shù)),則n維空間的距離(如歐氏距離,馬氏距離,范數(shù)距離等)可用來定義對象之間的相似度,且這些度量只僅僅依賴特征向量之間的差值.然而在數(shù)據(jù)挖掘的應(yīng)用中,有諸多數(shù)據(jù)對象是用類型數(shù)據(jù)來描述的,這使得我們不能通過計算兩個特征向量值之差來表示對象之間的距離,最簡單的辦法是overlap,即若兩個對象的屬性值相等則為1，不相等則為0，這種簡單匹配方法沒有把整個數(shù)據(jù)集考慮進(jìn)來，Boriah等[2]對類型數(shù)據(jù)的相似性度量做了較詳細(xì)的綜述和分析，分析了14種相似性度量及其在聚類中的優(yōu)缺點(diǎn)，這14種相似性度量方法都只考慮了用同一屬性值的分布特征來修正屬性值之間的相似度，沒有考慮數(shù)據(jù)對象屬性之間的相互關(guān)系對相似度的影響，白亮等[6]通過用粗糙集中的上下近似集來定義兩個屬性值之間的距離,張小宇等[7]通過連接度來定義兩個屬性值之間的距離,Dino Ienco等[1]應(yīng)用條件概率差來定義兩個屬性值之間的距離,他們的實(shí)驗(yàn)結(jié)果表明均能提高類型數(shù)據(jù)的聚類效果,但這些方法都涉及到一個計算復(fù)雜度高的問題.我們在本文中提出一種用樣本互信息來刻畫數(shù)據(jù)對象屬性之間的相互關(guān)系,每兩個數(shù)據(jù)對象之間的距離是由其各個屬性值之間的距離決定,每兩個數(shù)據(jù)對象屬性值之間的距離又是由其他屬性值之間的距離來確定,一個屬性對另一個之間的距離影響程度是由互信息來決定的。由此我們可定義綜合整個數(shù)據(jù)對象的信息和每個數(shù)據(jù)對象個體信息的類型數(shù)據(jù)對象之間距離的度量方法(由此也可定義相似度)。

本文提出的距離度量方法，其算法復(fù)雜性低,在UCI數(shù)據(jù)集上的實(shí)驗(yàn)表明,與傳統(tǒng)k-modes方法比較,有效地提高了聚類精度。

1 K-modes聚類方法[3-4]

1.1 K-modes聚類方法概述

令 X1=(x11,x12,…,x1s),X2=(x21,x22,…,x2s)是兩個對象，有s個字符屬性(即categorical data)，則 X1,X2之間的差異性度量為：

假設(shè)有p個對象的類C={X1,X2,…Xp}，Xi=(xi1,xi2,…,xis),(1≤i≤p)，它的Modes（眾數(shù)）Q={q1,q2,…qs}，其中qj是{X1j,X2j,…,Xpj}的眾數(shù)。

則n個對象分成k類的最優(yōu)化問題為：

1.2 K-Modes聚類算法

k-modes算法是對k-means算法的擴(kuò)展。k-means算法是在數(shù)據(jù)挖掘領(lǐng)域中普遍應(yīng)用的聚類算法，它只能處理數(shù)值型數(shù)據(jù)，而不能處理分類屬性型數(shù)據(jù)。例如表示人的屬性有：姓名、性別、年齡、家庭住址等屬性。而k-modes算法就能夠處理分類屬性型數(shù)據(jù)。k-modes算法采用差異度來代替k-means算法中的距離。k-modes算法中差異度越小，則表示距離越小。一個樣本和一個聚類中心的差異度就是它們各個屬性不相同的個數(shù)，不相同則記為1，最后計算1的總和。這個和就是某個樣本到某個聚類中心的差異度。該樣本屬于差異度最小的聚類中心。具體步聚如下：

第一步:給定含有n個對象的數(shù)據(jù)集T和聚類數(shù)k。

第二步：隨機(jī)選擇k個對象Xi(1≤i≤n)作為初始眾數(shù)Q1,Q2,…,Qk，每一個成為一類。

第三步：利用公式（1）計算所有對象與上述k個初始眾數(shù)的差異性度量d(Xi,Qj)(1≤i≤n,1≤j≤k)，然后將每個對象分配到與其差異性度量最小的那個類當(dāng)中，得到k個分類C1,C2,…,Ck。

第四步：重新計算每個類的眾數(shù)Q1,Q2,…,Qk。即在每個類中，對每個屬性選取在該類中所占比例最大的屬性值作為該類的眾數(shù)的屬性值。從而得到每個類的眾數(shù)Q1,Q2,…,Qk。

第五步：返回到第三步，直到每個類的眾數(shù)不再發(fā)生改變?yōu)橹埂?/p>

2 互信息的相關(guān)概念

在信息論中,熵是隨機(jī)變量的不確定性度量或自信息的平均值。一個隨機(jī)變量X的熵是該隨機(jī)變量X所含信息量的度量。設(shè)隨機(jī)變量X=[x1,x2,…,xs],p(xi)(1≤i≤s)是隨機(jī)變量X的分布列，則隨機(jī)變量X的信息熵可定義為:

聯(lián)合熵是指一對變量X和Y的不確定度,即兩個隨機(jī)變量X和Y的聯(lián)合熵(Joint Entropy)定義為:

互信息(Mutual Information)是另一有用的信息度量，它是指兩個隨機(jī)變量之間的相關(guān)性。兩個隨機(jī)變量X和Y的互信息定義為：

其中當(dāng)X和Y是離散型隨機(jī)變量時,p(x,y)表示的是X,Y的聯(lián)合分布列,p1(x),p2(y)分別是X,Y的邊緣分布列,當(dāng)X和Y是連續(xù)型隨機(jī)變量時,X和Y的互信息為：

此時 p(x,y)是X,Y的聯(lián)合密度函數(shù),p1(x),p2(y)分別是X,Y的邊緣密度函數(shù)。

性質(zhì)1:I(X,Y)=H(X)+H(Y)-H(X,Y)

性質(zhì)2:I(X,X)=H(X)

性質(zhì)3：I(X,Y)=I(Y,X)

性質(zhì)4：I(X,Y)≥0

性質(zhì)5：如果X與Y互相獨(dú)立，則I(x,y)=0

3 基于樣本互信息量的改進(jìn)K-Modes聚類算法

3.1 基于互信息量的對象之間的距離公式

定義S=(U,A)為一個信息系統(tǒng)，U={x1,x2,…xn}為對象全體，A={A1,A2,…Am}為屬性集，數(shù)據(jù)如表1所示：

表1 數(shù)據(jù)表

I(Ai,Aj)(i,j∈{1,2,…,m}）表示屬性 Ai與 Aj的互信息，當(dāng)i=j時，I(Ai,Ai)=H(Ai)就是屬性 Ai的信息熵，定義對象xi和xj的第k個屬性之間的差異性度量為：

性質(zhì)6:兩個對象 xi和 xj的屬性值完全相同時,則d(xi,xj)=0

性質(zhì)7:兩個對象 xi和 xj的屬性值完全不相同時,則d(xi,xj)=1

3.2 基于樣本互信息的改進(jìn)K-Modes聚類算法

在基于互信息量的對象之間的距離公式的基礎(chǔ)上，我們得到基于樣本互信息的改進(jìn)K-Modes聚類算法如下：

第一步:給定含有n個對象的數(shù)據(jù)集T和聚類數(shù)k;

第二步:任意給出T的k個非空子集C1,C2,…Ck(C1?C2…?Ck=T)作為初始的聚類劃分；

第三步：計算目前劃分C1,C2,…Ck的眾數(shù)Ql={ql1,ql2,…qls}(l=1,2,…,k)。即在每個Ci(1≤i≤k)類中，對每個屬性選取在該類中所占比例最大的屬性值作為該類的眾數(shù)的屬性值,從而得到每個類的眾數(shù)Q1,Q2,…,Qk。

第四步：對每一個對象xi(1≤i≤n)，利用公式8計算到k個眾數(shù)Ql（1≤l≤k）的距離d(xi,Ql)，并將 xi分配到距離最小的眾數(shù)所在的類。得到新的劃分C1,C2,…Ck;

第五步：返回第三步,直到每個對象所屬類不再改變?yōu)橹埂?/p>

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

為了評價一種聚類算法質(zhì)量，通常是一件很難又帶有主觀性的工作。因此我們引入了兩個客觀標(biāo)準(zhǔn)來評價聚類的結(jié)果：精度（Accuracy）和標(biāo)準(zhǔn)互信息（Normalized Mutual Information）。

聚類的標(biāo)準(zhǔn)互信息定義為：

其中nij是既出現(xiàn)在聚類i中，同時又出現(xiàn)在分類j中的對象集合的關(guān)聯(lián)基數(shù)；ni是在聚類i中的對象數(shù)；nj是在分類j中的對象數(shù)；n是數(shù)據(jù)集中總的對象數(shù)。C和P分別表示聚類數(shù)和分類數(shù)。NMI可用來計算任意一對聚類與分類之間的平均互信息，NMI的值越高，聚類結(jié)果越好。

為了測試該算法的有效性,我們從UCI數(shù)據(jù)集中挑選了2組數(shù)據(jù)進(jìn)行實(shí)驗(yàn),分別為vote和mushroom,2組數(shù)據(jù)描述如表2所示。

表2 數(shù)據(jù)描述

表3 在2種不同數(shù)據(jù)集下算法精度和NMI的比較

在表3中，我們列出了基于互信息量的改進(jìn)K-Modes聚類算法與傳統(tǒng)的K-Modes聚類算法分別運(yùn)行在Vote和mushroom兩個數(shù)據(jù)集上相比較評價的結(jié)果。通過表3可知，幾乎在所有的實(shí)驗(yàn)中，不管是在Vote數(shù)據(jù)集上，還是在mushroom數(shù)據(jù)集上，基于互信息量的改進(jìn)K-Modes聚類算法不僅在聚類精度上比傳統(tǒng)的K-Modes聚類算法結(jié)果更好，而且在聚類的平均標(biāo)準(zhǔn)互信息上也比傳統(tǒng)的K-Modes聚類算法結(jié)果更好，表明基于互信息量的改進(jìn)K-Modes聚類算法有效地提高了聚類效果。

5 結(jié)束語

本文引入樣本互信息的方法，提出了一種新的距離度量，該距離度量方法算法復(fù)雜性低,且該距離公式既考慮了對象某個屬性值本身的不同，又考慮了對象其它屬性對該屬性值的影響，使之更符合實(shí)際問題情況。通過在UCI數(shù)據(jù)集上的實(shí)驗(yàn)，與傳統(tǒng)的K-Mode聚類算法進(jìn)行了比較，實(shí)驗(yàn)結(jié)果表明，基于互信息量的改進(jìn)K-Modes聚類算法有效地提高了聚類精度。

[1]Dino Ienco,Ruggero G.Pensa,Rosa Meo.Context-Based Distance Learning for Categorical Data Clustering[Z].IDA 2009,LNCS 5772,2009.

[2]Shyam Boriah,Varun Chandola,Vipin Kumar.Similarity Measures for Categorical Data:A Comparative Evaluation[EB/OL]＜Sboriah,Chando?la,Kumar＞@cs.umu.edu,1999.

[3]Amir Ahmad,Lipika Dey.A K-mean Clustering Algorithm for Mixed Numeric and Categorical Data[J].Data&Knowledge Engineering,2007,（63）.

[4]Michael K.Ng,Mark Junjie Li,Joshua Zhexue Huang,Zengyou He.On the Impact of Dissimilarity Measure in k-Modes Clustering Algorithm[J].Ieee Transactions on Pattern Analysis and Machine Intelligence,2007,29(3).

[5]Amir Ahmad，Lipika Dey.A Method to Compute Distance between Two Categorical Values of Same Attribute in Unsupervised Learning for Categorical Data Set[J].Pattern Recognition Letters，2007，（28）.

[6]白亮,梁吉業(yè),曹付元.基于粗糙集的改進(jìn)K-Modes聚類算法[J].計算機(jī)科學(xué),2009,36(1).

[7]張小宇,梁吉業(yè),曹付元,于慧娟.基于加權(quán)連接度的改進(jìn)K-Modes聚類算法[J].廣西師范大學(xué)學(xué)報自然科學(xué)版,2008,26(3).