一種改進的K?Modes聚類算法

摘 要： 傳統的K?Modes算法采用0?1簡單匹配方法計算對象與類中心（Modes）之間的距離，并將每個對象分配到離它最近的類中去。采用基于頻率方法重新計算各類的類中心（Modes）、定義目標函數，然而，對象的歸類方法和目標函數的定義沒有充分考慮分類數據的特點。對此，提出一種改進的K?Modes算法，采用期望熵最小的衡量方法進行歸類，并且采用期望熵作為新的目標函數。通過實驗將該算法與傳統的K?Modes算法進行比較，表明該算法是更有效的。

關鍵詞： 分類型數據； 聚類算法； 期望熵； 目標函數； 聚類精度

中圖分類號： TN911?34； TP181 文獻標識碼： A 文章編號： 1004?373X（2015）04?0039?03

0 引 言

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

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

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

1 傳統K?Modes聚類算法

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

定義1[4]：設[S=U，A]是一個分類信息系統，[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為實現K?Modes聚類算法定義目標函數為[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]是一個[n×k]的{0，1}矩陣；[n]表示對象集[U]所包含的對象個數；[k]表示聚類的個數，[wil=1]表示第[i]個對象被劃分到第[l]類中，[Z={z1，z2，...，zk}，zl（1≤l≤k）]是第[l]類的中心。

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

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

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

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

Step4：重復上述Step2，Step3過程，直到目標函數[F]不再發生變化為止。

2 改進的K?Modes算法

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

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

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

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

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

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

改進的K?Modes聚類算法基本步驟如下：

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

Step2：應用期望熵最小方法將每個對象分類；

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

Step4：重復上述Step2，Step3過程，直到目標函數F不再發生變化為止。

3 實驗分析

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

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

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

通過分析表3～表5，在數據Mushroom和Breast Cancer上，改進的K?Modes聚類算法得到了較好的聚類效果，優于傳統的K?Modes聚類算法。

4 結 語

本文提出一種改進的K?Modes算法，首先采用簡單匹配方法依次選取最不相同的k個類中心，其他數據采用期望熵較小的方法進行歸類，并且定義了基于期望熵的目標函數。通過實驗和傳統的K?Modes算法進行比較，結果表明在相同的實驗環境下，改進的K?Modes聚類算法在準確率、類精度和召回率上都優于傳統的K?Modes聚類算法。

參考文獻

[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] 梁吉業，白亮，曹付元.基于新的距離度量的K?Modes聚類算法[J].計算機研究與發展，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.