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

賈彬 梁毅 蘇航

摘 要：為了改善傳統K-Modes聚類算法相異度度量公式弱化了類內相似性，忽略了屬性間差異，以及單一屬性值的Modes忽視了某一屬性可能存在多屬性值組合，且算法受初始中心點影響很大的缺點，基于多屬性值Modes的相異度度量方法提出MAV-K-Modes算法，并采用一種基于預聚類的初始中心選取方法。使用UCI數據集進行實驗，結果表明，MAV-K-Modes算法相比于傳統K-Modes算法，其正確率、類精度和召回率都有明顯提升，且MAV-K-Modes算法適合于并行化改造。

關鍵詞：聚類算法;相異度度量;初始中心點;多屬性值Modes;K-Modes

DOI：10. 11907/rjdk. 182651

中圖分類號：TP312

文獻標識碼：A文章編號：1672-7800（2019）006-0060-05

Abstract：The dissimilarity measure method of traditional K-Modes clustering algorithm suffers from some shortcomings， such as weakening the similarity within a class， ignoring the difference between attributes， and the Modes with single attribute value neglects that a property may have multiple attribute value combinations， and the algorithm is greatly affected by the initial center points. A MAV-K-Modes algorithm is proposed based on the dissimilarity measure method of multi-attribute value Modes， and an initial center selection method based on pre-clustering is adopted. The results of experiments using UCI datasets show that the MAV-K-Modes algorithm has a significant improvement in accuracy rate， precision rate and recall rate compared with the traditional K-Modes algorithms， and the MAV-K-Modes algorithm is suitable for parallel transformation.

Key Words： clustering algorithm; dissimilarity measure; initial center points; multi-attribute value Modes; K-Modes

0 引言

近年來隨著互聯網的快速發展，信息量以前所未有的速度迅猛增長。聚類算法[1]作為一種有效的數據挖掘工具，其應用十分廣泛，目前已成為國內外學者的研究熱點。聚類算法的核心是將一個數據集劃分成幾個子集，并使同一子集中的元素盡可能相似，且不同子集中的元素盡可能相異。聚類算法用來訓練的樣本標記信息是未知的，因而也被稱作無監督學習方法[2]，需要通過學習探究數據內在性質及規律。

基于劃分的K-Means算法[3]是一種用于處理大數據集的有效且應用廣泛的聚類算法，但該算法只能處理數值型數據，而大多數實際數據集不僅包括數值型數據，還包括大量分類屬性數據（Categorical Data）。Huang[4]提出一種K-Modes算法，對K-Means算法進行拓展，使其可以處理分類屬性數據。算法采用簡單0-1匹配機制度量兩數據點在某一屬性下的距離，目標函數定義為所有數據點與所屬聚類中心Modes相異度量總和。該相異度度量方法弱化了類中相似性，也忽略了屬性之間權重的差異性。傳統算法在聚類過程中使用基于頻度的方法修正聚類中心Modes在每個屬性中的取值，但每個屬性只保留最高頻率屬性值的聚類中心Modes，會造成其它較高頻率的重要屬性值丟失，導致準確率降低。K-Modes算法受初始中心點選取的影響也很大，容易使目標函數陷入局部最優，導致整體聚類效果下降。

針對傳統K-Modes算法的不足，很多學者都提出了改進方法。針對相異度度量公式問題，Ng[5]、Goodall[6]、趙亮[7]、DinoIenco[8]提出新的類內屬性距離計算公式，但只強化了類內相似性，而未考慮屬性間的差異性;HongJia[9]、Ahamad[10]、Hsu[11-12]、李仁侃[13]、Jayabal[14]提出的方法只考慮了不同屬性的權重計算;石雋鋒[15]定義一種基于期望熵的新目標函數;黃苑華[16]提出基于結構相似性的方法，但計算代價較大，且不易于進行數據并行處理;梁吉業、白亮[17]在提出基于粗糙集的相異度量方法的同時，也考慮了類內相似性與屬性權重的差異，但當屬性具有很多值時，粗糙隸屬度的計算量很大。針對初始選點問題，Huang[4]提出將最頻繁的屬性值均勻分配到初始Modes中;Sun[18]將Bradley的迭代初始點優化算法應用到算法中;Cao[19]結合距離和密度提出一種初始中心選擇方法。但這些選點方法只適用于單屬性值Modes的初始化。

由于以上改進方法均未考慮聚類中心Modes每個屬性只能取單屬性值的問題，且K-Modes算法受初始中心點選取影響很大，容易陷入局部最優，導致整體聚類效果下降，因此本文提出一種MAV-K-Modes算法。使用基于多屬性值Modes的相異度度量方法，可有效防止重要屬性值丟失，并強化同一屬性內屬性值的相似性，突出不同屬性的差異性，使相異度度量更加準確。新的多屬性值Modes相異度度量方法使用信息熵[20]計算屬性權重，以強化屬性間的差異，而新的類內屬性距離計算公式強化了類內相似性。同時，針對多屬性值聚類中心Modes提出一種基于預聚類的初始選點方法，通過統計分析預聚類結果，得到各類的多屬性值聚類中心Modes作為初始中心點，以減少局部最優情況的發生。實驗結果表明，MAV-K-Modes算法在正確率、類精度和召回率方面相比傳統算法都有較大提升，因而有效提升了聚類效果，且該算法可滿足數據并行要求，經過并行化改造后可大幅提升算法執行效率。