一種改進(jìn)的K?Modes聚類算法

摘 要： 傳統(tǒng)的K?Modes算法采用0?1簡(jiǎn)單匹配方法計(jì)算對(duì)象與類中心（Modes）之間的距離，并將每個(gè)對(duì)象分配到離它最近的類中去。采用基于頻率方法重新計(jì)算各類的類中心（Modes）、定義目標(biāo)函數(shù)，然而，對(duì)象的歸類方法和目標(biāo)函數(shù)的定義沒(méi)有充分考慮分類數(shù)據(jù)的特點(diǎn)。對(duì)此，提出一種改進(jìn)的K?Modes算法，采用期望熵最小的衡量方法進(jìn)行歸類，并且采用期望熵作為新的目標(biāo)函數(shù)。通過(guò)實(shí)驗(yàn)將該算法與傳統(tǒng)的K?Modes算法進(jìn)行比較，表明該算法是更有效的。

關(guān)鍵詞： 分類型數(shù)據(jù)； 聚類算法； 期望熵； 目標(biāo)函數(shù)； 聚類精度

中圖分類號(hào)： TN911?34； TP181 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2015）04?0039?03

0 引 言

聚類技術(shù)廣泛應(yīng)用于數(shù)據(jù)挖掘、統(tǒng)計(jì)模式識(shí)別、機(jī)器學(xué)習(xí)、信息檢索等領(lǐng)域[1?2]。它是將一個(gè)數(shù)據(jù)集劃分為若干個(gè)子類，使得類內(nèi)對(duì)象盡可能相似，類間對(duì)象盡可能相異[3]。隨著分類型數(shù)據(jù)的出現(xiàn)，分類型數(shù)據(jù)聚類成為亟待解決的問(wèn)題。K?Modes算法[4]是在K?means算法[5]基礎(chǔ)上擴(kuò)展而來(lái)的，其算法簡(jiǎn)單、高效，被廣泛應(yīng)用于各個(gè)領(lǐng)域，但是它采用在每個(gè)屬性域中采用頻率較高的屬性值作為類中心，其他數(shù)據(jù)和類中心進(jìn)行0?1匹配，確定它們所屬的類別，以及目標(biāo)函數(shù)中各數(shù)據(jù)和類中心的距離也是0?1匹配，這些顯然是不合理的。

人們針對(duì)該問(wèn)題進(jìn)行了改進(jìn)，白亮等人提出了基于新的距離度量的K?Modes算法，在選取類中心時(shí)，能夠較精確計(jì)算對(duì)象的距離，從而更精確地選取初始類中心，提高了算法的執(zhí)行效率[6]。文獻(xiàn)[7]提出了基于頻率的加權(quán)度量方法，有效地提高了算法的聚類效果。Ng等人利用基于相對(duì)頻率的相異度度量對(duì)傳統(tǒng)的K?Modes聚類算法進(jìn)行了改進(jìn)，有效地提高了算法效率[8]。文獻(xiàn)[9]采用新的相異度度量方法改進(jìn)K?Modes算法，有效地提高了算法性能。然而這些算法都隱含假定類中各數(shù)據(jù)對(duì)象具有一樣的重要性，沒(méi)有充分考慮分類型數(shù)據(jù)的特點(diǎn)，因而不能準(zhǔn)確計(jì)算數(shù)據(jù)間的距離。文獻(xiàn)[10]采用期望熵來(lái)判斷各種分類方案的好壞，它依序處理數(shù)據(jù)，并對(duì)分得不好的數(shù)據(jù)重新標(biāo)記類別。

本文提出了改進(jìn)的K?Modes算法，將期望熵引入到K?Modes算法中來(lái)，采用期望熵最小的方法對(duì)各數(shù)據(jù)歸類，并且定義了基于期望熵的目標(biāo)函數(shù)，在選擇初始類中心時(shí)，通過(guò)簡(jiǎn)單0?1匹配選取最不相同的數(shù)據(jù)作為類中心。這些改進(jìn)可以將分類型數(shù)據(jù)更有效地歸類，從而提高了算法的效率。

1 傳統(tǒng)K?Modes聚類算法

K?Modes聚類算法是通過(guò)對(duì)K?Means聚類算法的擴(kuò)展，使其應(yīng)用于分類屬性數(shù)據(jù)聚類。它采用簡(jiǎn)單匹配方法度量同一分類屬性下兩個(gè)屬性值之間的距離，用Mode代替K?Means聚類算法中的Means，通過(guò)基于頻率的方法在聚類過(guò)程中不斷更新Modes。

定義1[4]：設(shè)[S=U，A]是一個(gè)分類信息系統(tǒng)，[U={x1，x2，…，xn}]，[A={a1，a2，…，am}]，[xi，xj∈U（1≤i，j≤n）]，[xi，xj]分別被A描述為[xi=（f（xi，a1），f（xi，a2），…，f（xi，am））]和[xj=（f（xj，a1），f（xj，a2），…，f（xj，am））]，[xi]和[xj]的距離定義為：

[d（xi，xj）=l=1mδ（f（xi，al），f（xj，al））]

式中：

[δ（f（xi，al），f（xj，al））=1， f（xi ，al）≠f（xj ，al）0， f（xi ，al）=f（xj ，al）]

Huang為實(shí)現(xiàn)K?Modes聚類算法定義目標(biāo)函數(shù)為[4]：

[FW，Z=l=1ki=1nwild（xi，zl）]

式中：

[wil∈{0，1}， 1≤l≤k，1≤i≤n] （1）

[l=1kwil=1， 1≤i≤n] （2）

[0

[W]是一個(gè)[n×k]的{0，1}矩陣；[n]表示對(duì)象集[U]所包含的對(duì)象個(gè)數(shù)；[k]表示聚類的個(gè)數(shù)，[wil=1]表示第[i]個(gè)對(duì)象被劃分到第[l]類中，[Z={z1，z2，...，zk}，zl（1≤l≤k）]是第[l]類的中心。

為了使目標(biāo)函數(shù)F在滿足約束條件式（1）～式（3）下達(dá)到極小化，K?Modes聚類算法基本步驟如下：

Step1：從數(shù)據(jù)集中隨機(jī)選擇k個(gè)對(duì)象作為初始類中心，其中k表示聚類個(gè)數(shù)；

Step2：應(yīng)用簡(jiǎn)單匹配方法計(jì)算對(duì)象與類中心（Modes）之間的距離，并將每個(gè)對(duì)象分配到離它最近的類中去；

Step3：基于頻率方法重新計(jì)算各類的類中心（Modes）；

Step4：重復(fù)上述Step2，Step3過(guò)程，直到目標(biāo)函數(shù)[F]不再發(fā)生變化為止。

2 改進(jìn)的K?Modes算法

K?Modes聚類算法利用簡(jiǎn)單匹配方法對(duì)每個(gè)對(duì)象分類必然效果較差，因?yàn)橛妙l率來(lái)選取類中心比較粗糙，再用0?1匹配決定所屬類別也不太合理。文獻(xiàn)[9]提出了基于期望熵（Expected Entropy）的分類方法比較適合分類型數(shù)據(jù)，因此，這里將該方法結(jié)合到K?Modes算法中來(lái)，進(jìn)一步提高算法的運(yùn)行效率。期望熵的定義如下：

定義2： 設(shè)[S=U，A]是一個(gè)分類信息系統(tǒng)，[U={x1，…，xi，…，xn}]，[A=Sa1，…，Saj，…，Sam]，[Saj]表示第[j]個(gè)屬性所有屬性值的集合，數(shù)據(jù)對(duì)象[xi]可表示成[xi=xi1，…，xim]，假定分為k類，[C=c1，…，cl，…，ck]， 期望熵的定義如下：

[E=l=1kclnEclEcl=Ea1+Ea2+…+EamEaj=-y∈sajpylogpy]

假定三個(gè)數(shù)據(jù)對(duì)象，[v1=\"red\"，\"heavy\"，][v2=][\"red\"，\"medium\"，][v3=\"blue\"，\"light\"]要分為兩類，有三種分類方案如表1所示。

從表1可以看出，分類方案1的期望熵最小，該分類方案也是最好的分類方式。因此，可以將期望熵作為目標(biāo)函數(shù)。同時(shí)，確定了類中心后，對(duì)每個(gè)對(duì)象分類也可以采用該方法，假定初始類中心為：[\"red\"，\"heavy\"]，[\"blue\"，\"light\"]，向量[\"red\"，\"medium\"]有兩種歸類方式，即方案1和方案3，方案1的期望熵較小，并且該方案是較好的分類方式，因此，可以通過(guò)取最小期望熵對(duì)每個(gè)對(duì)象進(jìn)行分類。

另外，在數(shù)據(jù)集中隨機(jī)選取類中心也不合理，假定選取的類中心在一個(gè)類中，將其他對(duì)象歸到這k個(gè)類中，重新計(jì)算各類中心，再次歸類，可能使得目標(biāo)函數(shù)不再變化，得不到好的聚類效果，如圖1所示。假定數(shù)據(jù)集中有四個(gè)對(duì)象，選取數(shù)據(jù)1，2作為初始類中心，將數(shù)據(jù)3和4歸類后，新的類中心為數(shù)據(jù)5，6，再次對(duì)四個(gè)數(shù)據(jù)歸類，分類結(jié)果可能不變，目標(biāo)函數(shù)不再發(fā)生變化，而該分類結(jié)果并不是理想的分類結(jié)果。因此，初始化時(shí)，應(yīng)找到k個(gè)最不相同的數(shù)據(jù)作為初始類中心。首先找到最不相同的兩個(gè)數(shù)據(jù)[xc1]，[xc2]，使得[dxc1，xc2=][max1≤i≤n，1≤j≤ndxi，xj]，分別作為兩個(gè)類的中心，再依次找到其他類中心，假定已經(jīng)找到了[j-1]個(gè)類中心，第j個(gè)類中心為[xcj]，使得[dxci，xcj=maxmini=1，…，j-1xci，xcj]。當(dāng)數(shù)據(jù)集比較大時(shí)，先取樣再尋找類中心。

改進(jìn)的K?Modes聚類算法基本步驟如下：

Step1：從數(shù)據(jù)集中選擇k個(gè)最不相同對(duì)象作為初始類中心，其中k表示聚類個(gè)數(shù)；

Step2：應(yīng)用期望熵最小方法將每個(gè)對(duì)象分類；

Step3：基于頻率方法重新計(jì)算各類的類中心（Modes）；

Step4：重復(fù)上述Step2，Step3過(guò)程，直到目標(biāo)函數(shù)F不再發(fā)生變化為止。

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

下面分別從分類正確率（Accuracy）、類精度（Precision）和召回率（Recall）三方面來(lái)分析算法的聚類質(zhì)量：Accuracy（AC），Precision（PE），Recal1（RE）分別定義如下：

[AC=i=1kain， PE=i=1kaiai+bik， RE=i=1kaiai+cik]

式中：n表示數(shù)據(jù)集的對(duì)象數(shù)；[ai]表示正確分到第i類的對(duì)象數(shù)；[bi]表示誤分到第i類的對(duì)象數(shù)；[ci]表示應(yīng)該分到第i類卻沒(méi)分到的對(duì)象數(shù)；k表示聚類個(gè)數(shù)。從UCI數(shù)據(jù)集中挑選了2組數(shù)據(jù)Mushroom和Breast Cancer，Mushroom數(shù)據(jù)集有一列屬性中包括不確定屬性，因此，這里分兩種情況處理，即移除該屬性列和將不確定屬性值用特定屬性值取代。3組數(shù)據(jù)描述如表2所示。

通過(guò)分析表3～表5，在數(shù)據(jù)Mushroom和Breast Cancer上，改進(jìn)的K?Modes聚類算法得到了較好的聚類效果，優(yōu)于傳統(tǒng)的K?Modes聚類算法。

4 結(jié) 語(yǔ)

本文提出一種改進(jìn)的K?Modes算法，首先采用簡(jiǎn)單匹配方法依次選取最不相同的k個(gè)類中心，其他數(shù)據(jù)采用期望熵較小的方法進(jìn)行歸類，并且定義了基于期望熵的目標(biāo)函數(shù)。通過(guò)實(shí)驗(yàn)和傳統(tǒng)的K?Modes算法進(jìn)行比較，結(jié)果表明在相同的實(shí)驗(yàn)環(huán)境下，改進(jìn)的K?Modes聚類算法在準(zhǔn)確率、類精度和召回率上都優(yōu)于傳統(tǒng)的K?Modes聚類算法。

參考文獻(xiàn)

[1] CHEN M S， HAN J， YU P S. Data mining： an overview from a database perspective [J]. IEEE Transactions on Knowledge and Data Engineering， 1996， 8（6）： 866?883.

[2] JAIN A K， DUIN R P， MAO J. Statistical pattern recognition： a review. [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2000， 22（1）： 4?37.

[3] BERKHIN P. Survey of clustering data mining techniques [R]. San Jose， CA ： Accrue Software， 2002.

[4] HUANG Zhe?xue.Extensions to the k?means algorithm for clustering large data sets with categorical values [C]// Proceedings of Data Mining and Knowledge Discovery. Netherlands： Kluwer Academic Publishers， 1998： 283?304.

[5] HAN Jia?wei， KAMBER M. Data mining concepts and techniques [M]. San Francisco， USA： Morgan Kaufmann， 2001.

[6] 梁吉業(yè)，白亮，曹付元.基于新的距離度量的K?Modes聚類算法[J].計(jì)算機(jī)研究與發(fā)展，2010，47（10）：1749?1755.

[7] HE Zeng?you， DENG Sheng?chun， XU Xiao?fei. Improving K?modes algorithm considering frequencies of attribute values in mode [C]// Proceedings of the International Conference on Computational Intelligence and Security. Berlin： Springer?Verlag， 2005： 157?162.

[8] NG K N， LI M J， HUANG J Z， et a1. On the impact of dissimilarity measure in k?modes clustering algorithm [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2007， 29（3）： 503?507.

[9] CAO Fu?yuan， LIANG Ji?ye， LI De?yu. A dissimilarity measure for the k?Modes clustering algorithm [J]. Knowledge?Based Systems， 2012， 26： 120?127.

[10] BARBARA D， COUTO J， LI Y. Coolcat： an entropy?based algorithm for categorical clustering [C]// Proceedings of ACM 11th International Conference on Information and Knowledge Management. [S.l.]： ACM， 2002： 582?289.