石雋鋒，白妙青

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

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ù)聚類成為亟待解決的問題。K?Modes算法[4]是在K?means算法[5]基礎(chǔ)上擴(kuò)展而來的，其算法簡(jiǎn)單、高效，被廣泛應(yīng)用于各個(gè)領(lǐng)域，但是它采用在每個(gè)屬性域中采用頻率較高的屬性值作為類中心，其他數(shù)據(jù)和類中心進(jìn)行0?1匹配，確定它們所屬的類別，以及目標(biāo)函數(shù)中各數(shù)據(jù)和類中心的距離也是0?1匹配，這些顯然是不合理的。

人們針對(duì)該問題進(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ì)象具有一樣的重要性，沒有充分考慮分類型數(shù)據(jù)的特點(diǎn)，因而不能準(zhǔn)確計(jì)算數(shù)據(jù)間的距離。文獻(xiàn)[10]采用期望熵來判斷各種分類方案的好壞，它依序處理數(shù)據(jù)，并對(duì)分得不好的數(shù)據(jù)重新標(biāo)記類別。

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

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

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

式中：

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

式中：

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過程，直到目標(biāo)函數(shù)F不再發(fā)生變化為止。

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

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

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

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

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

從表1可以看出，分類方案1的期望熵最小，該分類方案也是最好的分類方式。因此，可以將期望熵作為目標(biāo)函數(shù)。同時(shí)，確定了類中心后，對(duì)每個(gè)對(duì)象分類也可以采用該方法，假定初始類中心為：{" red","heavy"}，{"blue","light"}，向量{" red","medium"}有兩種歸類方式，即方案1和方案3，方案1的期望熵較小，并且該方案是較好的分類方式，因此，可以通過取最小期望熵對(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，使得，分別作為兩個(gè)類的中心，再依次找到其他類中心，假定已經(jīng)找到了 j-1個(gè)類中心，第j個(gè)類中心為xcj，使得當(dāng)數(shù)據(jù)集比較大時(shí)，先取樣再尋找類中心。

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

改進(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過程，直到目標(biāo)函數(shù)F不再發(fā)生變化為止。

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

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

式中：n表示數(shù)據(jù)集的對(duì)象數(shù)；ai表示正確分到第i類的對(duì)象數(shù)；bi表示誤分到第i類的對(duì)象數(shù)；ci表示應(yīng)該分到第i類卻沒分到的對(duì)象數(shù)；k表示聚類個(gè)數(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個(gè)數(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é)語(yǔ)

本文提出一種改進(jìn)的K?Modes算法，首先采用簡(jiǎn)單匹配方法依次選取最不相同的k個(gè)類中心，其他數(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.