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

石雋鋒，白妙青

（山西大學(xué) 計(jì)算中心，山西 太原 030006）

0 引言

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

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

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

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

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

定 義 1[4]：設(shè) S=( )U,A是一個分類信息系統(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的距離定義為：

式中：

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

式中：

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

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

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

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

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

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

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

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

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

假定三個數(shù)據(jù)對象，v1={" red","heavy"},v2={"red","medium"},v3={" blue","light"}要分為兩類，有三種分類方案如表1所示。

表1 對數(shù)據(jù)集{v1，v2，v3}不同的分類方式及期望熵

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

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

圖1 經(jīng)典K?Modes算法錯誤的分類情況

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

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

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

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

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

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

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

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

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

表3～表5是改進(jìn)的K?Modes算法和Huang的K?Modes聚類算法在3個數(shù)據(jù)集上的性能比較。

表3 在M ushroom（移除）數(shù)據(jù)集上算法的性能比較

表4 在M ushroom（取代）數(shù)據(jù)集上算法的性能比較

表5 在Breast Cancer數(shù)據(jù)集上算法的性能比較

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

4 結(jié)語

本文提出一種改進(jìn)的K?Modes算法，首先采用簡單匹配方法依次選取最不相同的k個類中心，其他數(shù)據(jù)采用期望熵較小的方法進(jìn)行歸類，并且定義了基于期望熵的目標(biāo)函數(shù)。通過實(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聚類算法。

[1]CHEN M S，HAN J，YU P S.Datamining：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 Ma?chine 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]//Pro?ceedings of Data Mining and Knowledge Discovery.Nether?lands：Kluwer Academic Publishers，1998：283?304.

[5]HAN Jia?wei，KAMBER M.Data mining concepts and tech?niques[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 Com?putational Intelligence and Security.Berlin：Springer?Verlag，2005：157?162.

[8]NG K N，LIM J，HUANG JZ，et a1.On the impact of dis?similarity 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，LIDe?yu.A dissimilarity mea?sure for the k?Modes clustering algorithm[J].Knowledge?Based Systems，2012，26：120?127.

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