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

賈彬 梁毅 蘇航

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

關(guān)鍵詞：聚類算法;相異度度量;初始中心點(diǎn);多屬性值Modes;K-Modes

DOI：10. 11907/rjdk. 182651

中圖分類號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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 引言

近年來(lái)隨著互聯(lián)網(wǎng)的快速發(fā)展，信息量以前所未有的速度迅猛增長(zhǎng)。聚類算法[1]作為一種有效的數(shù)據(jù)挖掘工具，其應(yīng)用十分廣泛，目前已成為國(guó)內(nèi)外學(xué)者的研究熱點(diǎn)。聚類算法的核心是將一個(gè)數(shù)據(jù)集劃分成幾個(gè)子集，并使同一子集中的元素盡可能相似，且不同子集中的元素盡可能相異。聚類算法用來(lái)訓(xùn)練的樣本標(biāo)記信息是未知的，因而也被稱作無(wú)監(jiān)督學(xué)習(xí)方法[2]，需要通過學(xué)習(xí)探究數(shù)據(jù)內(nèi)在性質(zhì)及規(guī)律。

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

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

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