吳潤秀

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

0 引言

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

本文提出的距離度量方法，其算法復(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)是兩個(gè)對(duì)象，有s個(gè)字符屬性(即categorical data)，則 X1,X2之間的差異性度量為：

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

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

1.2 K-Modes聚類算法

k-modes算法是對(duì)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算法中差異度越小，則表示距離越小。一個(gè)樣本和一個(gè)聚類中心的差異度就是它們各個(gè)屬性不相同的個(gè)數(shù)，不相同則記為1，最后計(jì)算1的總和。這個(gè)和就是某個(gè)樣本到某個(gè)聚類中心的差異度。該樣本屬于差異度最小的聚類中心。具體步聚如下：

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

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

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

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

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

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

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

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

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

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

此時(shí) 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 基于互信息量的對(duì)象之間的距離公式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了測(cè)試該算法的有效性,我們從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兩個(gè)數(shù)據(jù)集上相比較評(píng)價(jià)的結(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ù)雜性低,且該距離公式既考慮了對(duì)象某個(gè)屬性值本身的不同，又考慮了對(duì)象其它屬性對(duì)該屬性值的影響，使之更符合實(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ì)算機(jī)科學(xué),2009,36(1).

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