非獨(dú)立同分布下的K-Modes算法

周慧鑫，姜 合，王艷梅

(齊魯工業(yè)大學(xué)(山東省科學(xué)院) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山東 濟(jì)南 250353)

0 引 言

許多學(xué)者根據(jù)K-Modes算法[1,2]存在的問題，對算法進(jìn)行了很多研究和改進(jìn)。針對初始中心點(diǎn)選擇的問題，Liwen Peng[3]提出了一種基于屬性權(quán)重的選擇聚類中心的方法。賈瑞玉等[4]定義了一種新的計(jì)算對象密度的方法，通過殘差分析得到初始聚類中心。針對相異度量的問題，趙亮等[5]提出了一種基于樸素貝葉斯分類器中間運(yùn)算結(jié)果的距離度量。施振佺等[6]提出了一種基于粗糙集和知識粒度的屬性加權(quán)算法，加權(quán)到相異度的計(jì)算中。袁方等[7]提出了一種針對有序分類與無序分類兩種屬性的距離度量。針對其它方面的問題，黃苑華等[8]提出一種基于結(jié)構(gòu)相似性的K-Modes算法。張春英等[9]提出了一種基于集對信息粒的集對K-Modes聚類算法。葉霞等[10]提出了一種將蟻群聚類算法與K-Modes算法相結(jié)合的算法。

到目前為止，相異度量的計(jì)算，大多數(shù)都考慮的是數(shù)據(jù)之間是相互獨(dú)立，沒有關(guān)系的，然而實(shí)際上的數(shù)據(jù)集中屬性之間是存在著一定的耦合關(guān)系，即非獨(dú)立同分布。操龍兵首先提出的非獨(dú)立同分布思想，隨后很多研究學(xué)者運(yùn)用這個(gè)思想，用于許多不同的研究方向。操龍兵提出了基于復(fù)雜相互作用的耦合性學(xué)習(xí)。Jian等為無監(jiān)督學(xué)習(xí)定義了一個(gè)耦合度量相似度(CMS)[11]，它提出了數(shù)據(jù)對象間的異構(gòu)耦合關(guān)系。Wang等提出了在無監(jiān)督學(xué)習(xí)中類別型數(shù)據(jù)的耦合關(guān)系來計(jì)算相似性度量的方法并在K-Modes算法中進(jìn)行了驗(yàn)證。在真實(shí)數(shù)據(jù)中，數(shù)據(jù)對象的屬性之間存在著一定的聯(lián)系，因此，在非獨(dú)立同分布的思想下改進(jìn)K-Modes算法將更加符合實(shí)際。

1 K-modes算法

1.1 算法基本概念

在日常的數(shù)據(jù)中，數(shù)據(jù)類型主要包括數(shù)值型數(shù)據(jù)和類別型數(shù)據(jù)。它們之間有本質(zhì)性的區(qū)別，數(shù)值型數(shù)據(jù)是按數(shù)字尺度測量的觀察值，其結(jié)果表現(xiàn)為具體的數(shù)值，是屬性值的一個(gè)數(shù)值，屬性值之間具有一定的幾何特征，可以進(jìn)行數(shù)值運(yùn)算；而類別型數(shù)據(jù)是一種非數(shù)值型數(shù)據(jù)，表示的是對象的特征屬性，特征的數(shù)值既沒有數(shù)量大小的含義，代表的是屬性的各種狀態(tài)，不能進(jìn)行數(shù)值運(yùn)算，各種分類內(nèi)容都屬于類別型數(shù)據(jù), 如性別分類(男、女)、地區(qū)(省、市)、農(nóng)藥毒性(劇毒、高毒、中毒、低毒)等[12]。K-Means算法是適用于連續(xù)的數(shù)值型數(shù)據(jù)[13]的聚類算法，以效果更好，思想簡單的優(yōu)點(diǎn)在聚類算法中得到了廣泛的應(yīng)用[14]?，F(xiàn)在常用的距離度量方法有很多像歐氏距離、曼哈頓距離、切比雪夫距離、余弦距離，這些方法都是針對對數(shù)值很敏感的數(shù)值型數(shù)據(jù)，而類別型數(shù)據(jù)之間的相似性是對數(shù)據(jù)特征很敏感，所以傳統(tǒng)的K-Means算法中計(jì)算數(shù)據(jù)距離的歐式距離不能計(jì)算離散屬性之間的距離。K-Modes聚類算法通過對K-Means聚類算法的拓展，使其可應(yīng)用于類別型屬性數(shù)據(jù)聚類[15]。

K-Modes算法中采用計(jì)算數(shù)據(jù)間相異度量的方法來表示數(shù)據(jù)間的距離。相異度量越小，則表示距離越小。K-Modes的基本思想是隨機(jī)分配K個(gè)對象作為初始聚類中心，計(jì)算隸屬度矩陣，將剩余的數(shù)據(jù)劃分到離初始類中心最近的子類中，基于頻率更新聚類中心，經(jīng)過多次迭代，聚類函數(shù)收斂，算法劃分結(jié)束。

1.2 算法描述

輸入：數(shù)據(jù)集，聚類類簇個(gè)數(shù)K。

輸出：聚類后劃分好的子類集合。

步驟1 從數(shù)據(jù)集中隨機(jī)選擇K個(gè)對象作為初始類中心，其中K表示聚類過程中簇的個(gè)數(shù)。

步驟2 采用簡單0-1匹配方法計(jì)算每個(gè)對象與各聚類中心之間的相異度量作為距離度量。某一個(gè)對象和另一個(gè)對象的相異度量就是它們各個(gè)屬性不相同的個(gè)數(shù)，相同記為0，不相同則記為1，最后計(jì)算1的總和，這個(gè)和就是兩個(gè)對象間的相異度量。

步驟3 將每個(gè)對象分配到相異度度量最小的子類中。

步驟4 使用基于頻率的方法更新聚類中心。

步驟5 重復(fù)上述的步驟2～步驟4，直到目標(biāo)函數(shù)F收斂，即聚類中心不再發(fā)生變化時(shí)，算法結(jié)束。目標(biāo)函數(shù)見式(1)

(1)

其中，k是聚類類簇的個(gè)數(shù)，n是數(shù)據(jù)對象的個(gè)數(shù)，wli∈{0,1} (1≤l≤k,1≤i≤n,)wli=1表示第i個(gè)對象被劃分到第l類中，ml為第l個(gè)類的聚類中心，xi表示第i個(gè)數(shù)據(jù)對象。

2 NonIID-HDK-Modes算法

2.1 初始聚類中心的選取

傳統(tǒng)的K-Modes算法中，對初始聚類中心點(diǎn)是隨機(jī)選取的，這使得聚類算法的結(jié)果會非常依賴初始聚類中心點(diǎn)的選取。隨機(jī)選取K個(gè)中心點(diǎn)，可能會選取到離群點(diǎn)，而且每次中心點(diǎn)選取的不同也會影響到算法的聚類效果。因此，本文提出一種基于層次聚類對數(shù)據(jù)集進(jìn)行預(yù)聚類的方法，對預(yù)聚類劃分好的類簇進(jìn)一步處理后，取得的每個(gè)類簇中的聚類中心作為K-Modes的初始聚類中心，改變傳統(tǒng)算法隨機(jī)選取中心點(diǎn)的缺點(diǎn)。

層次聚類的相似性指的是任意一個(gè)數(shù)據(jù)對象ux與所有數(shù)據(jù)對象之間的距離，它們的距離越小，相似度就越高。層次聚類的思想就是將相似度高的數(shù)據(jù)對象不斷的進(jìn)行合并，直到合并到設(shè)定的K個(gè)類簇，結(jié)束算法。

基于層次聚類預(yù)聚類的初始聚類中心選取方法的具體步驟是：

(1)對數(shù)據(jù)集的數(shù)據(jù)進(jìn)行歸一化處理

在數(shù)據(jù)集中，不同屬性指標(biāo)往往具有不同的量綱和量綱單位，這樣的情況會影響到數(shù)據(jù)分析的結(jié)果，為了數(shù)據(jù)處理方便，對數(shù)據(jù)進(jìn)行基于均值和標(biāo)準(zhǔn)差的歸一化處理

(2)

其中，μ為所有樣本數(shù)據(jù)集的均值，σ為所有樣本數(shù)據(jù)集的標(biāo)準(zhǔn)差。

(2)對數(shù)據(jù)集進(jìn)行層次聚類預(yù)聚類

計(jì)算類簇之間的距離，常用的方法有：最小連接距離法、最大連接距離法、平均連接距離法。采用適用于類別型數(shù)據(jù)的平均連接距離法計(jì)算距離公式如式(3)所示，將數(shù)據(jù)集中所有數(shù)據(jù)都當(dāng)作是一個(gè)獨(dú)立的類簇，對于給定的聚類簇Ci和Cj，找到距離最小的兩個(gè)類簇C1和C2

dmax(Ci,Cj)=|mi-mj|

(3)

其中，mi是簇Ci的均值，mj是簇Cj的均值。

合并距離最小的C1和C2為一個(gè)類簇，然后不斷合并距離最近的聚類簇，并對合并得到的聚類簇距離矩陣進(jìn)行更新。不斷重復(fù)上述過程，直至達(dá)到K個(gè)聚類簇。

(3)分別計(jì)算K個(gè)類簇中每個(gè)對象的局部密度和高密度點(diǎn)距離。

把每個(gè)聚類簇中的所有數(shù)據(jù)對象作為一個(gè)子集，分別計(jì)算每個(gè)子集中每個(gè)數(shù)據(jù)對象的局部密度，局部密度計(jì)算公式如式(4)所示

(4)

其中，dij表示任意的數(shù)據(jù)對象xi和數(shù)據(jù)對象xj之間的距離，用歐氏距離進(jìn)行計(jì)算，計(jì)算公式如式(5)所示

(6)

dc是一個(gè)截?cái)嗑嚯x參數(shù)，設(shè)置dc為數(shù)據(jù)量的1%，把每個(gè)樣本點(diǎn)和所有樣本點(diǎn)的距離與先前設(shè)定好的截?cái)嗑嚯x相比較，所有小于截?cái)嗑嚯x的點(diǎn)的個(gè)數(shù)就是這個(gè)樣本點(diǎn)的局部密度大小。

接著，計(jì)算高局部密度點(diǎn)距離如式(7)所示

(7)

(4)選取聚類中心

ρi和δi相對較高的數(shù)據(jù)點(diǎn)標(biāo)記為簇的中心，所以計(jì)算每個(gè)子集中ρi和δi的乘積，即γi，取γi的最大值，將每個(gè)類簇中的最大值的數(shù)據(jù)點(diǎn)作為每個(gè)類簇中的聚類中心

γi=ρiδi

(8)

將選取出來的所有K個(gè)類簇的聚類中心作為K-Modes算法的初始聚類中心。

2.2 相異度量的計(jì)算

在傳統(tǒng)的K-modes算法中，相異度量的計(jì)算都是基于距離的度量方法，是以數(shù)據(jù)屬性之間的存在是獨(dú)立同分布為前提的，然而現(xiàn)實(shí)生活中的數(shù)據(jù)的屬性之間都是非獨(dú)立同分布的。在Wang的文章里將非獨(dú)立同分布的思想加入到K-Modes算法的相異度量的計(jì)算中與Ahmad等提出的ADD相異度量的計(jì)算方法進(jìn)行了實(shí)驗(yàn)比較，發(fā)現(xiàn)在數(shù)據(jù)結(jié)構(gòu)分析和聚類質(zhì)量方面，提出的方法優(yōu)于其它類別型數(shù)據(jù)的相異度量的方法。所以將非獨(dú)立同分布的思想加入到K-Modes算法的相異度量的計(jì)算中是可行的。

在Wang改進(jìn)的K-Modes的算法中屬性之間的耦合相似度的權(quán)重參數(shù)認(rèn)為每個(gè)屬性的重要程度是均等的，不能反映屬性間真實(shí)的權(quán)重參數(shù)?；バ畔⒎从车氖侨我鈨蓚€(gè)對象的聯(lián)合分布相對于假定兩個(gè)對象是獨(dú)立情況下的聯(lián)合分布之間的內(nèi)在依賴性，度量兩個(gè)事件集合之間的相關(guān)性，屬性之間的耦合相似性體現(xiàn)的就是某個(gè)屬性值與其它屬性值的共現(xiàn)依賴關(guān)系，所以可以采用計(jì)算互信息的方法來計(jì)算屬性之間的權(quán)重關(guān)系，在本文中計(jì)算屬性之間的互信息后對互信息進(jìn)行標(biāo)準(zhǔn)化，得到屬性的權(quán)重矩陣，更好反映出每個(gè)屬性的重要程度以及更加合理改進(jìn)了計(jì)算對象差異度量的方法。

設(shè)數(shù)據(jù)集集合為U={u1,u2,…,um}， 表示一組非空的m個(gè)數(shù)據(jù)對象組成。A={a1,a2,…,an}， 表示每個(gè)數(shù)據(jù)對象包括n個(gè)屬性，是一組有限的屬性。V=∪j=1nvj表示的是屬性值集，Vj是屬性aj的值的集合。

(9)

IaASV反映的是屬性的屬性值頻率之間的關(guān)系，頻率近似相等的兩個(gè)屬性值具有較大的相似性。

(10)

(11)

(12)

2)αk是屬性ak的權(quán)重參數(shù)，利用標(biāo)準(zhǔn)化互信息求取權(quán)重矩陣對αk賦值，計(jì)算公式如式(13)所示

(13)

I(ai,aj) 是指屬性ai和aj的互信息。計(jì)算公式為式(14)

(14)

其中，p(vi)，p(vj) 分別是屬性值vi和vj在數(shù)據(jù)集U中的概率分布函數(shù)。p(vi,vj) 是屬性值vi和vj在數(shù)據(jù)集U中的聯(lián)合概率分布函數(shù)，計(jì)算公式如式(15)所示

p(vi,vj)=p(vi)·p(vj)

(15)

H(ai) 表示的是屬性ai的信息熵，計(jì)算公式為

(16)

(3)對象的耦合屬性不相似性(CADO)為

(17)

令h1=1/t-1，h2=1-t，h1(t)，h2(t)， 都是關(guān)于t的遞減函數(shù)，滿足相似性和不相似性的互補(bǔ)性。

計(jì)算相異度量的步驟為：

步驟3 求取權(quán)重矩陣對對αk賦值

步驟4 計(jì)算任意兩個(gè)對象ux和uy之間的對象耦合屬性不相似性CADO，得到數(shù)據(jù)對象間的距離矩陣作為數(shù)據(jù)對象之間的相異度量。

本文選取Breast-cancer數(shù)據(jù)集中的一個(gè)片段為例計(jì)算數(shù)據(jù)片段的相異度量矩陣，6個(gè)對象具有8個(gè)屬性，分為兩類，具體信息見表1。

表1 Breast-cancer數(shù)據(jù)片段

將表1 按照相異度量的計(jì)算方法，計(jì)算出表1的相異度量見表2。

表2 數(shù)據(jù)片段的相異度量

2.3 算法描述

輸入：數(shù)據(jù)集，聚類類簇個(gè)數(shù)K。

輸出：聚類后劃分好的子類集合。

步驟1 按照2.1中的思想選取K個(gè)聚類中心。

步驟2 根據(jù)2.2中方法計(jì)算數(shù)據(jù)集中任一數(shù)據(jù)對象ux與選取的聚類中心之間的相異度量。

步驟3 將每個(gè)對象分配到與聚類中心相異度量最小的子類中。

步驟4 分配結(jié)束后，通過基于頻率的方法來重新確定聚類中心。

步驟5 重復(fù)上述的步驟2～步驟4，直到所有數(shù)據(jù)對象所屬的聚類中心不再變化時(shí)，算法結(jié)束。

以上是對K-Modes算法初始聚類中心的選擇和相異度量進(jìn)行了改進(jìn)，考慮到數(shù)據(jù)之間的屬性相似性，更好地處理了類內(nèi)間相似性的問題，解決了傳統(tǒng)K-Modes算法隨機(jī)選取中心點(diǎn)和計(jì)算相異度量時(shí)忽略了類內(nèi)相似性的問題，更好提高了算法的聚類效果。

3 實(shí)驗(yàn)結(jié)果及分析

本文實(shí)驗(yàn)在UCI數(shù)據(jù)集分別是Zoo數(shù)據(jù)集、Breast-cancer數(shù)據(jù)集及Soybean-small數(shù)據(jù)集這3個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)驗(yàn)證。

實(shí)驗(yàn)環(huán)境：MATLAB R2019b，Intel(R) Core(TM) i7-6700CPU、3.40 GHz、8.0 GB，Microsoft Windows 7。

3.1 實(shí)驗(yàn)描述

本文改進(jìn)了傳統(tǒng)隨機(jī)選取中心點(diǎn)的缺點(diǎn)，并改進(jìn)非獨(dú)立同分布的公式引入到計(jì)算K-Modes算法的相異度量中，主要目的是提升K-Modes算法的聚類精度，避免選取初始聚類中心的時(shí)候選到離群點(diǎn)或者同一類別的情況，同時(shí)使屬性的權(quán)重參數(shù)更加合理化，更加準(zhǔn)確的將屬性內(nèi)耦合和屬性之間的耦合的相似性加入到計(jì)算數(shù)據(jù)對象的相異度量中。

本文分別在Zoo數(shù)據(jù)集、Breast-cancer數(shù)據(jù)集和Soybean-small數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)驗(yàn)證。將數(shù)據(jù)集在相同的環(huán)境中分別在傳統(tǒng)的K-Modes算法、Wang改進(jìn)的K-Modes算法(簡稱Wang)、文獻(xiàn)[16]和NonIID-HDK-Modes的算法程序中運(yùn)行20次，分別記錄下每個(gè)算法聚類的正確率。

3.2 實(shí)驗(yàn)結(jié)果

3.2.1 數(shù)據(jù)集描述

3個(gè)數(shù)據(jù)集的描述見表3。

表3 數(shù)據(jù)集信息

3.2.2 實(shí)驗(yàn)對比結(jié)果

下面分別從分類正確率(AC)、類精度(PR)、召回率(RE)這3個(gè)方面來分析算法的聚類質(zhì)量，AC、PR、RE的定義分別如下

其中，U表示的是數(shù)據(jù)集中的對象的數(shù)量，K表示的是聚類類簇的個(gè)數(shù)，xi表示可以正確分到第i類的對象數(shù)量，yi表示錯(cuò)誤分到第i類的對象數(shù)量，zi表示應(yīng)分到卻沒分到第i類的對象數(shù)量。

在Zoo數(shù)據(jù)集、Breast-cancer數(shù)據(jù)集和Soybean-small數(shù)據(jù)集3個(gè)數(shù)據(jù)集中，驗(yàn)證傳統(tǒng)的K-Modes算法、Wang、文獻(xiàn)[16]的算法和NonIID-HDK-Modes算法。4個(gè)算法在相同的環(huán)境中運(yùn)行20次取平均值，具體聚類算法性能比較見表4～表6和圖1。

表4 在Zoo數(shù)據(jù)集下性能比較/%

表5 在Breast-cancer數(shù)據(jù)集下性能比較/%

表6 在Soybean-small數(shù)據(jù)集下性能比較/%

圖1 4種算法的準(zhǔn)確率

通過分析圖1，可以發(fā)現(xiàn)在非獨(dú)立同分布思想下，NonIID-HDK-Modes算法比Wang算法中改進(jìn)K-Modes算法相異度量的聚類效果更好，準(zhǔn)確率更高。

通過分析表4～表6，可以看到在數(shù)據(jù)集Zoo、Breast-cancer和Soybean-small上，經(jīng)過修改非獨(dú)立同分布思想下計(jì)算耦合相似性的權(quán)重參數(shù)和初始聚類中心點(diǎn)選取方法的K-Modes算法與獨(dú)立同分布條件下的K-Modes算法的對比，NonIID-HDK-Modes算法獲取了較好的聚類效果，聚類結(jié)果優(yōu)于文獻(xiàn)[16]，驗(yàn)證NonIID-HDK-Modes算法是有效的。

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

根據(jù)實(shí)驗(yàn)得到的結(jié)果，可以看到Wang的算法在非獨(dú)立同分布的思想下把屬性內(nèi)和屬性之間的相似性一起加入到計(jì)算相異度量時(shí)，聚類效果會相比傳統(tǒng)的K-Modes算法有一定的提高。因此，把非獨(dú)立同分布的思想引入到K-Modes算法中是可以提高算法的聚類效果的，是可行的。

通過圖1我們可以看到，在非獨(dú)立同分布的條件下，在相同的運(yùn)行環(huán)境下3個(gè)數(shù)據(jù)集中NonIID-HDK-Modes算法與Wang對K-Modes算法的改進(jìn)相比，可以更好提高聚類算法的準(zhǔn)確率，說明改進(jìn)耦合權(quán)重和初始聚類中心的選取方法是有效的。

由實(shí)驗(yàn)結(jié)果可以看到，基于非獨(dú)立同分布的思想的NonIID-HDK-Modes算法在Zoo數(shù)據(jù)集中，相比較文獻(xiàn)[16]的方法聚類準(zhǔn)確度提高了8.62%；在Breast-cancer數(shù)據(jù)集中，相比較文獻(xiàn)[16]的方法聚類準(zhǔn)確度提高了4.19%；在Soybean-small數(shù)據(jù)集中，相比較文獻(xiàn)[16]的方法聚類準(zhǔn)確度提高25.85%。在Zoo數(shù)據(jù)集和Soybean-small數(shù)據(jù)集與Breast-cancer數(shù)據(jù)集的準(zhǔn)確率提高的較多，兩個(gè)數(shù)據(jù)集中的數(shù)據(jù)較少，算法準(zhǔn)確率的提高較為明顯，對于數(shù)據(jù)集中數(shù)據(jù)較多的情況，算法的準(zhǔn)確率效果較為不明顯。因此，NonIID-HDK-Modes算法可以更好提高較小數(shù)據(jù)集的聚類準(zhǔn)確率，對于提高較大數(shù)據(jù)集的準(zhǔn)確率存在不足。

通過比較聚類的純度大小，判斷算法聚類效果的好壞，當(dāng)聚類的純度越接近1，說明算法聚類的效果越好。傳統(tǒng)K-Modes算法、文獻(xiàn)[16]和NonIID-HDK-Modes算法在3個(gè)數(shù)據(jù)集上的純度見表7，在Zoo和Soybean-small兩個(gè)數(shù)據(jù)集上，NonIID-HDK-Modes算法表現(xiàn)較好，聚類的效果更好。在Breast-cancer數(shù)據(jù)集上，文獻(xiàn)[16]的聚類效果更好，說明改進(jìn)的算法在整體上還是能夠有效提高算法的聚類純度，提高聚類的效果，這得益于非獨(dú)立同分布的思想。

表7 3種算法的純度比較

4 結(jié)束語

在本文中針對K-Modes算法隨機(jī)選取初始聚類中心的缺點(diǎn)，首先對數(shù)據(jù)集通過層次聚類預(yù)聚類對數(shù)據(jù)集進(jìn)行類別劃分，然后再分別計(jì)算每個(gè)類別中所有對象的局部密度和高密度點(diǎn)距離，選擇兩個(gè)距離乘積的最大值作為每個(gè)類別的一個(gè)聚類中心，逐一選取每個(gè)類別的聚類中心，并將所有類別的聚類中心作為算法的初始聚類中心。同時(shí)傳統(tǒng)的K-Modes算法計(jì)算相異度量時(shí)，忽略了數(shù)據(jù)對象之間的聯(lián)系，在本文中根據(jù)非獨(dú)立同分布的思想計(jì)算相異度量，并且在非獨(dú)立同分布的基礎(chǔ)上繼續(xù)改進(jìn)計(jì)算屬性耦合相似性權(quán)重參數(shù)的方法，計(jì)算兩列間的標(biāo)準(zhǔn)化互信息作為權(quán)重矩陣。實(shí)驗(yàn)結(jié)果表明，本文在非獨(dú)立同分布的思想下提出的NonIID-HDK-Modes算法具有較高的準(zhǔn)確率，可以提高K-Modes算法聚類的效果，更加符合現(xiàn)實(shí)中數(shù)據(jù)的實(shí)際情況。