賈子琪，宋 玲

(1.南陽理工學(xué)院 計(jì)算機(jī)與軟件學(xué)院，河南 南陽 473004；2.廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004)

0 引 言

經(jīng)典k-means算法[1]在計(jì)算簇的均值以及數(shù)據(jù)對(duì)象之間的相異度時(shí)使用的是歐式距離，僅適用于連續(xù)特征的數(shù)值型數(shù)據(jù)集，對(duì)于離散特征的分類型數(shù)據(jù)集，k-means算法不再適用。Huang對(duì)k-means算法[1]進(jìn)行擴(kuò)展，使用“modes”代替“means”，提出適用于分類型數(shù)據(jù)聚類的k-modes算法[2]。k-modes算法采用簡單漢明距離計(jì)算相異度，忽略了數(shù)據(jù)對(duì)象間同一分類特征的差異性，弱化了簇內(nèi)相似性，沒有充分反映同一分類特征下兩個(gè)特征值之間的相異度；采用隨機(jī)選擇的方法確定初始簇中心和k值，采用基于頻率的方法重新計(jì)算和更新簇中心，給聚類結(jié)果帶來很大的不確定性。

1 相關(guān)工作

Ahmad等[3]通過共現(xiàn)分析來反映同一特征下特征值之間的距離，如果特征值之間的共現(xiàn)程度高，則將該特征作為新的簇中心。該方法反映了特征之間的潛在關(guān)系，改善了同一特征下特征值相異度系數(shù)的計(jì)算，但忽略了數(shù)據(jù)對(duì)象本身的異同。Hus等[4]提出了一種基于概念層次的相異度系數(shù)。該方法過于依賴用戶的經(jīng)驗(yàn)以及對(duì)待聚類數(shù)據(jù)集專業(yè)知識(shí)的了解，不利于一般用戶的使用，聚類范圍有局限性。Ng等[5]擴(kuò)展了簡單漢明距離，考慮當(dāng)前聚類中modes的影響，基于特征值在簇內(nèi)出現(xiàn)的頻率提出了新的相異度系數(shù)。該方法最小化了目標(biāo)函數(shù)，提高了聚類精度，但其相異度系數(shù)的計(jì)算仍然存在問題。IDMKCA算法只反映了相同特征之間的內(nèi)在關(guān)系，沒有考慮不同特征值之間的相似性。如果兩個(gè)數(shù)據(jù)對(duì)象的特征值不匹配，那么這兩個(gè)特征值的相異度系數(shù)計(jì)算結(jié)果始終為“1”。Cao等[6]提出基于新相異度系數(shù)的IMCDC算法。在新相異度系數(shù)下k-modes算法的性能得到了提高，但由于假定數(shù)據(jù)對(duì)象的重要性相同，導(dǎo)致不能充分考慮分類型數(shù)據(jù)的特點(diǎn)，不能準(zhǔn)確地計(jì)算數(shù)據(jù)對(duì)象間的相異度。Sangam等[7]在IDMKCA算法基礎(chǔ)上提出了基于新的相異度系數(shù)的EKACMD算法。該算法在一些情況下確實(shí)能夠解決IDMKCA算法的部分不足，但是在簇內(nèi)簇間特征值出現(xiàn)頻率相等的情況下，EKACMD算法和IDMKCA算法都存在問題。

2 經(jīng)典k-modes聚類算法及相關(guān)符號(hào)說明

2.1 相關(guān)符號(hào)說明

本文使用的相關(guān)符號(hào)及含義說明見表1。

表1 符號(hào)說明

2.2 k-modes聚類算法

以數(shù)據(jù)對(duì)象xi和簇中心ql為例，定義經(jīng)典k-modes算法的簡單漢明距離，如式(1)所示，此計(jì)算賦予各特征相同的權(quán)重[8]

(1)

k-modes算法通過簡單漢明距離來最小化的目標(biāo)函數(shù)。如式(2)所示[9]

(2)

3 基于簇內(nèi)簇間相異度的k-modes算法(IKMCA)

3.1 IKMCA算法的基本思想

如果選用的相異度系數(shù)可以發(fā)現(xiàn)數(shù)據(jù)集內(nèi)全部或部分潛在的modes，那么對(duì)基于劃分的k-modes算法來說事半功倍。使k-modes算法產(chǎn)生高效的聚類結(jié)果需滿足簇內(nèi)數(shù)據(jù)對(duì)象之間的相異度最?。淮亻g數(shù)據(jù)對(duì)象之間的相異度最大的條件。因此，本節(jié)基于簇內(nèi)簇間相似性提出一種相異度系數(shù)“簇內(nèi)簇間相異度系數(shù)”。IKMCA算法使用基于改進(jìn)的密度峰值算法確定初始簇中心，使用簇內(nèi)簇間相異度系數(shù)計(jì)算各數(shù)據(jù)對(duì)象與簇中心之間的相異度，并更新簇中心。

3.2 經(jīng)典k-modes算法及其變體算法存在的問題

3.2.1 在相異度系數(shù)上存在的問題

經(jīng)典k-modes算法的相異度系數(shù)沒有考慮簇內(nèi)特征值出現(xiàn)的相對(duì)頻率，也沒有考慮各特征的簇內(nèi)簇間結(jié)構(gòu)。導(dǎo)致新數(shù)據(jù)對(duì)象劃分過程中，一些簇分配了較少的相似數(shù)據(jù)。為方便說明，采用表2所示的人工數(shù)據(jù)集D1對(duì)相異度系數(shù)進(jìn)行論證。D1由3個(gè)特征描述A={A1,A2,A3}。其中，DOM(A1)={A,B}, DOM(A2)={E,F}, DOM(A3)={H,I}。D1有兩個(gè)聚類簇C1和C2分別對(duì)應(yīng)的簇中心q1(A,E,H)和q2(A,E,H)。

表2 人工數(shù)據(jù)集D1

假設(shè)需要對(duì)x7=(A,E,H)進(jìn)行聚類劃分。使用簡單滿名距離可得d(x7,q1)=d(x7,q2)=0+0+0=0。但以簇內(nèi)相似性而言，應(yīng)該將x7劃分給簇C1。

3.2.2 在初始簇中心選擇上存在的問題

經(jīng)典k-modes算法對(duì)初始簇中心非常敏感，初始簇中心的選擇采用隨機(jī)初始化法或者人工設(shè)置法，這兩種方法都在一定程度上導(dǎo)致了聚類結(jié)果不穩(wěn)定。選擇不同位置和k值的初始簇中心，會(huì)產(chǎn)生不同的聚類結(jié)果。如圖1所示，該數(shù)據(jù)集的真實(shí)簇?cái)?shù)是3。選擇不同初始簇中心，設(shè)置不同的k值，可能產(chǎn)生不同聚類結(jié)果，圖1內(nèi)容從左到右依次為：隨機(jī)選取初始簇中心、聚類迭代過程、最終聚類結(jié)果?？梢妼ふ液线m的初始簇中心非常重要。

圖1 k-modes算法對(duì)初始簇中心選取的敏感性

3.3 考慮簇內(nèi)相似性的相異度系數(shù)

簇內(nèi)簇間相異度系數(shù)考慮特征值在同一簇內(nèi)分布的相對(duì)頻率。屬于同簇的數(shù)據(jù)對(duì)象，其相同的特征值出現(xiàn)的頻率較高，簇內(nèi)相似性也較高。簇內(nèi)相異度定義如式(3)所示[10]

1≤i≤n, 1≤s≤m

(3)

使用數(shù)據(jù)集D1，根據(jù)式(3)可得d(x10,q1)=(1-2/3)+(1-2/3)+(1-1)=2/3，d(x10,q2)=(1-2/3)+(1-2/3)+(1-2/3)=1。由計(jì)算結(jié)果可知，x7與簇C1具有最小相異度，因此x7應(yīng)該被劃分到簇C1內(nèi)。式(3)雖然考慮了簇內(nèi)特征值的相對(duì)頻率，但沒有考慮簇間特征值的分布。使用表3所示人工數(shù)據(jù)集D2討論不考慮簇間相似度的缺陷。D2由3個(gè)分類型特征描述A={A1,A2,A3}。

表3 人工數(shù)據(jù)集D2

其中，DOM=(A1)={A,B,C}, DOM(A2)={E,F},DOM(A3)={H,I,J}。D2有3個(gè)聚類簇C1,C2和C3分別對(duì)應(yīng)簇中心q1=(A,E,H)，q2=(A,E,H)和q3=(B,E,I)。

假設(shè)需要對(duì)x10=(A,E,H)進(jìn)行聚類劃分。使用簡單漢明距離可得d(x10,q1)=d(x10,q2)=d(x10,q3)=0+0+0=0。使用式(3)可得d(x10,q1)=(1-2/3)+(1-2/3)+(1-3/3)=2/3，d(x10,q2)=(1-2/3)+(1-3/3)+(1-2/3)=2/3，d(x10,q3)=1+0+1=2。由上述計(jì)算結(jié)果可知，簡單漢明距離不能對(duì)x10進(jìn)行聚類劃分；式(3)可以將x10劃分給簇C1或簇C2，即式(3)無法準(zhǔn)確地確定x10的正確聚類劃分。從“低簇內(nèi)相異度高簇間相異度”角度觀察數(shù)據(jù)集D2，可知將x10分配給簇C1更合適。因?yàn)閷10分配給簇C1后，會(huì)讓簇C1和簇C2之間的相異度最大化。

3.4 考慮簇內(nèi)簇間相似性的相異度系數(shù)

簇間相異度考慮特征值相對(duì)于所有簇分布的總頻率。假設(shè)特征值僅在一個(gè)簇內(nèi)頻繁分布，意味該特征值和其它簇之間的差異性很大。簇內(nèi)簇間相異度系數(shù)定義如式(4)所示[11]

1≤i≤n, 1≤s≤m

(4)

使用式(4)數(shù)據(jù)集D2進(jìn)行計(jì)算d(x10,q1)=(1-2/3×2/4)+(1-2/3×2/8)+(1-3/3×3/5)=1.9；d(x10,q2)=(1-2/3×2/4)+(1-3/3×3/8)+(1-2/3×2/5)=2.025；d(x10,q3)=(1-0×1)+(1-3/3×3/8)+(1-0×1)=2.625。根據(jù)式(4)的計(jì)算結(jié)果可知，x10與簇C1之間的相異度更小，這個(gè)結(jié)果與之前的分析一致，成功的對(duì)x10進(jìn)行了聚類劃分。下面使用式(4)驗(yàn)證更為特殊的人工數(shù)據(jù)集D3。如表4所示，D3由3個(gè)特征描述A={A1,A2,A3}。其中，DOM=(A1)={A,B},DOM(A2)={E,F}，DOM(A3)={H,I}，3個(gè)聚類簇C1,C2和C3分別對(duì)應(yīng)簇中心q1=(A,E,H),q2=(A,E,H)和q3=(A,E,H)，A,E和H在D3中均勻分布，均出現(xiàn)6次。

表4 人工數(shù)據(jù)集D3

分別使用簡單漢明距離、式(3)和式(4)對(duì)x10(A,E,H)進(jìn)行聚類劃分。使用簡單漢明距離可得d(x10,q1)=d(x10,q2)=d(x10,q3)=0+0+0=0；使用式(3)可得d(x10,q1)=d(x10,q2)=d(x10,q3)=(1-2/3)+(1-2/3)+(1-2/3)=1；使用式(4)可得d(x10,q1)=d(x10,q2)=d(x10,q3)=(1-2/3×2/6)+(1-2/3×2/6)+(1-2/3×2/6)=21/9。由上述計(jì)算結(jié)果可知，當(dāng)特征值均勻分布時(shí)，上述3種相異度系數(shù)都無法正確對(duì)x10進(jìn)行聚類劃分。因此再一次考慮完善簇內(nèi)簇間相異度系數(shù)。

3.5 完善的簇內(nèi)簇間相異度系數(shù)

取數(shù)據(jù)對(duì)象xi的特征值分布與所在簇的整體特征值分布進(jìn)行比較，完善算子ζl的定義如式(5)所示

(5)

xi是待劃分?jǐn)?shù)據(jù)對(duì)象，xj是簇Cl內(nèi)的數(shù)據(jù)對(duì)象。重新定義的簇內(nèi)簇間相異度系數(shù)如式(6)所示

(6)

對(duì)任意xi，xj∈D，d均有以下性質(zhì)：

自身距離：對(duì)所有xi，每個(gè)對(duì)象與自身的距離等于零d(xi,xi)=0。

對(duì)稱性：對(duì)所有xi和xj，xi到xj的距離等于xj到xi的距離，即d(xi,xj)=d(xj,xi)。

非負(fù)性：對(duì)所有xi和xj，距離d是個(gè)非負(fù)值，當(dāng)且僅當(dāng)xi=xj時(shí)，d(xi,xj)=0。

滿足三角不等式：對(duì)所有xi和xj，存在d(xi,xj)≤d(xi,xh)+d(xh,xj)。

3.6 分類型數(shù)據(jù)初始化方法

2014年，Rodriguez等提出密度峰值(DP)算法[12]。DP算法是一種基于相對(duì)距離和局部鄰域密度的新型聚類算法，處理的是數(shù)值型數(shù)據(jù)，其輸入是數(shù)據(jù)對(duì)象間的相異度矩陣，因此通過合適的相異度系數(shù)計(jì)算出分類型數(shù)據(jù)之間的相異度，就可將DP算法應(yīng)用到分類型數(shù)據(jù)聚類上。本節(jié)利用DP算法可以自動(dòng)確定聚類簇?cái)?shù)的優(yōu)點(diǎn)去確定初始簇中心。

3.6.1 數(shù)據(jù)對(duì)象xi的局部鄰域密度ρi

局部鄰域密度ρi的值等價(jià)于以數(shù)據(jù)對(duì)象xi為圓心，以截?cái)嗑嚯xdc為半徑區(qū)域內(nèi)的數(shù)據(jù)對(duì)象個(gè)數(shù)。xi的局部鄰域密度有方波內(nèi)核函數(shù)法和高斯核函數(shù)法兩種定義方法。方波內(nèi)核函數(shù)法適用于大規(guī)模數(shù)據(jù)集，高斯核函數(shù)法適用于小規(guī)模數(shù)據(jù)集。方波內(nèi)核函數(shù)法求ρi的定義如式(7)所示

(7)

K(x)=exp{-x2}

(8)

從式(7)和式(8)可知，dc的取值會(huì)直接影響ρi的大小，進(jìn)而影響簇中心的選擇和整個(gè)聚類結(jié)果。因此，確定合適的dc值對(duì)算法來說很重要。

3.6.2 數(shù)據(jù)對(duì)象xi和xj之間的相對(duì)距離Li

xi和xj之間的相對(duì)距離Li的定義如式(9)所示

(9)

當(dāng)xi的ρi不是最大密度時(shí)，Li定義為在所有局部鄰域密度比xi大的數(shù)據(jù)對(duì)象中，與xi距離最近的數(shù)據(jù)對(duì)象與xi之間的距離，如式(10)和圖2所示

圖2 xi的局部鄰域密度不是最大密度時(shí)的情況

(10)

當(dāng)xi的ρi是最大密度時(shí)，Li定義為在所有局部鄰域密度比xi大的數(shù)據(jù)對(duì)象中，距xi最遠(yuǎn)的數(shù)據(jù)對(duì)象與xi之間的距離，如式(11)和圖3所示。同時(shí)具備高Li和高ρi的數(shù)據(jù)對(duì)象即為簇中心

圖3 xi的局部鄰域密度是最大密度時(shí)的情況

(11)

3.6.3 截?cái)嗑嚯x

截?cái)嗑嚯xdc是一個(gè)限定距離搜索范圍的臨界值。DP算法的dc值需要人為確定，將數(shù)據(jù)集中兩兩數(shù)據(jù)對(duì)象間的距離升序排列，取前1%至2%位置處的值即為dc值，是一個(gè)大概范圍。在實(shí)際聚類問題中dc值設(shè)置過大，會(huì)導(dǎo)致求得的ρi重疊，dc值設(shè)置過小，會(huì)導(dǎo)致聚類簇分布稀疏。受文獻(xiàn)[13]啟發(fā)本節(jié)給出詳細(xì)的dc值確定方法。設(shè)定di,j=[di,1,di,2,…,di,n]為數(shù)據(jù)對(duì)象xi與xj的相異度。用式(1)計(jì)算di,j值，然后對(duì)di,j升序排序得到d′i,j=[d′i,1,d′i,2,…,d′i,n]。xi的截?cái)嗑嚯xdc,i定義如式(12)所示

(12)

max(d′i,j+1-d′i,j)是d′i,j中相鄰相異度的最大差值，設(shè)定d′i,j=da，d′i,j+1=db。如圖4所示，數(shù)據(jù)對(duì)象xi與和它同簇的數(shù)據(jù)對(duì)象相異度較小，與和它不同簇的數(shù)據(jù)對(duì)象相異度較大。因此，在d′i,j=[d′i,1,d′i,2,…,d′i,j,d′i,j+1,…,d′i,n]內(nèi)一定存在一個(gè)臨界位置使得d′i,j+1與d′i,j的差值最大，認(rèn)為數(shù)據(jù)對(duì)象xi和數(shù)據(jù)對(duì)象a屬于同一簇，與數(shù)據(jù)對(duì)象b屬于不同簇。數(shù)據(jù)對(duì)象xi的dc,i值定義如式(13)所示

圖4 dc,i值的確定

(13)

dc值定義為集合dc,i的最小值如式(14)所示

dc=min(dc,i)

(14)

3.6.4 簇中心的確定

IKMCA基于以下兩個(gè)假設(shè)確定初始簇中心：①簇中心的局部鄰域密度高于周圍非簇中心點(diǎn)；②各簇中心之間的相對(duì)距離較大?；谏鲜黾僭O(shè)，本節(jié)給出初始簇中心自動(dòng)確定的方法。如圖5所示是一個(gè)二維示例數(shù)據(jù)集，共有93個(gè)數(shù)據(jù)對(duì)象，2個(gè)聚類簇，對(duì)應(yīng)2個(gè)簇中心。

圖5 二維數(shù)據(jù)集

DP算法簇中心的選擇是通過決策圖確定的。如圖6所示決策圖的橫軸為數(shù)據(jù)對(duì)象xi的局部鄰域密度ρi，縱軸為相對(duì)距離Li。ρi和Li的值同時(shí)大的值即為數(shù)據(jù)集的簇中心。圖6右上角的兩個(gè)點(diǎn)即為圖6中兩個(gè)簇對(duì)應(yīng)的簇中心。簇中心周圍包圍著大量的數(shù)據(jù)對(duì)象，其局部鄰域密度ρi和相對(duì)距離Li都較大。

圖6 決策圖

為了更加直觀觀察和確定簇中心，考慮使用Zi決策圖來選擇簇中心。通過式(8)和式(9)得到每個(gè)數(shù)據(jù)對(duì)象的局部鄰域密度和相對(duì)距離。根據(jù)公式Zi=ρi×Li計(jì)算出所有數(shù)據(jù)對(duì)象的Zi值，將Zi值降序排序得到排序序列Z(1)>Z(2)>…Z(n)，其中Z(1)>Z(2)>…Z(k)，(k

圖7 Zi決策圖

3.7 IKMCA描述

新的簇內(nèi)簇間相異度系數(shù)使分類型數(shù)據(jù)相異度計(jì)算更加準(zhǔn)確。初始簇中心的自主選取避免了經(jīng)典k-modes算法隨機(jī)選取或者人為手動(dòng)設(shè)置帶來的聚類結(jié)果不確定。DP算法只給出dc的大致范圍，本文在DP算法的基礎(chǔ)上給出了dc的明確確定方法。將簇內(nèi)簇間相異度系數(shù)應(yīng)用到經(jīng)典k-modes 算法中，其目標(biāo)函數(shù)定義如式(15)所示。定理1展示了如何最小化目標(biāo)函數(shù)F(U,Q)

(15)

uil∈{0,1}, 1≤i≤n, 1≤l≤k

(16)

(17)

(18)

Un×k是滿足約束條件(16)～(18)的隸屬度矩陣，uil=1表示xi屬于簇Cl。在滿足約束條件(16)～(18)的情況下，目標(biāo)函數(shù)F(U,Q)達(dá)到極小值，此時(shí)可以判斷聚類算法結(jié)束。

定理1 IKMCA的簇中心選取應(yīng)使得函數(shù)F(U,Q)被最小化，當(dāng)且僅當(dāng)fs,ts(xi)≥fs,th(xi)，ts≠th(1≤s≤m)。文字描述為，簇中心的各特征值應(yīng)選取數(shù)據(jù)集中各特征上出現(xiàn)頻率最大的特征值。fs,t(xi)(1≤s≤m, 1≤t≤ns)表示xi在第s個(gè)特征下取值為As,t的個(gè)數(shù)，如式(19)所示

fs,t(xi)=|{xi∈D,xi,s=As,t}|

(19)

當(dāng)且僅當(dāng)ql=DOM(As), 1≤s≤m并且滿足式(20)

fs,ts(xi)≥fs,th(xi)，且ts≠th(1≤s≤m)

(20)

時(shí)，函數(shù)F(U,Q)被最小化。為了使目標(biāo)函數(shù)F(U,Q)達(dá)到極小值，改進(jìn)后的算法步驟描述如下：

基于簇內(nèi)簇間相異度的k-modes算法(IKMCA)

輸入：包含有n個(gè)對(duì)象，m個(gè)分類型特征的分類型數(shù)據(jù)集D；

(1)通過式(1)計(jì)算相異度di,j，并得到相異矩陣dn×n;

(2)根據(jù)式(14)計(jì)算截?cái)嗑嚯xdc；

(3)利用式(7)或式(8)計(jì)算局部鄰域密度ρi；

(4)利用式(9)計(jì)算相對(duì)距離Li；

(5)根據(jù)公式Zi=ρi×Li，計(jì)算得到Zi={Z1,Z2,…,Zn}；

(6)將Zi降序排序，得到排序序列Z(1)>Z(2)>…>Z(n)。以數(shù)據(jù)對(duì)象xi的下標(biāo)為橫坐標(biāo)，以Zi為縱坐標(biāo)繪制Zi決策圖，確定圖中的拐點(diǎn)，拐點(diǎn)處的值即為最佳k值。

(7)確定k值和初始簇中心集合q(0)={q1,q2,…,qk}；

(8)根據(jù)式(6)計(jì)算數(shù)據(jù)集中n-k個(gè)數(shù)據(jù)對(duì)象與k個(gè)簇中心之間的相異度d(xi,ql)；

(9)根據(jù)就近原則將數(shù)據(jù)對(duì)象分配到離它最近的初始簇中去，分配完成后，得到k個(gè)聚類簇C(1)={C1,C2,…,Ck}，標(biāo)記這(n-k)個(gè)數(shù)據(jù)對(duì)象的簇標(biāo)簽；

(10)在新形成的聚類簇上根據(jù)定理1更新簇中心q(1)={q1,q2,…,qk}；

(11)重復(fù)上述步驟(8)～步驟(10)，直到目標(biāo)函數(shù)不再發(fā)生變化。如果不再發(fā)生變化，則算法結(jié)束；否則，跳至步驟(8)繼續(xù)執(zhí)行。

(12)算法結(jié)束，完成聚類。

輸出：聚類完成的簇集合C={C1,C2,…,Ck}；

IKMCA流程如圖8所示。

圖8 IKMCA流程

假設(shè)l是算法收斂所需的迭代次數(shù)，通常情況下n>>m,k,l。IKMAC算法的時(shí)間復(fù)雜度主要是在每次迭代中更新簇中心和相異度。初始化簇中心需要人工觀察決策圖決定，因此此階段的時(shí)間復(fù)雜度暫不考慮進(jìn)總體算法中。使用簇內(nèi)簇間相異度在每次迭代中更新簇中心和相異度計(jì)算的時(shí)間復(fù)雜度是l(O(nmk)+O(nmk))=O(nmkl)，所以IKMCA的總時(shí)間復(fù)雜度是O(nmkl)。從上述分析可以發(fā)現(xiàn)，使簇內(nèi)簇間相異度的IKMCA算法的時(shí)間復(fù)雜度相對(duì)數(shù)據(jù)對(duì)象的數(shù)量、聚類個(gè)數(shù)和特征個(gè)數(shù)是線性可縮放的。

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

3.8.1 性能指標(biāo)

為評(píng)估提出算法的有效性，下面分別從聚類精度AC[14]、純度PR[15]、召回率RE[2]這3個(gè)指標(biāo)對(duì)聚類結(jié)果進(jìn)行評(píng)價(jià)，分別如式(21)～式(23)所示。NUM+表示被正確劃分到簇Cl的數(shù)據(jù)對(duì)象個(gè)數(shù)；NUM-表示沒有被正確劃分到簇Cl的數(shù)據(jù)對(duì)象個(gè)數(shù)；NUM*表示應(yīng)該被劃分到簇Cl但實(shí)際上沒有被劃分到簇Cl的數(shù)據(jù)對(duì)象個(gè)數(shù)。聚類結(jié)果與數(shù)據(jù)集的真實(shí)劃分越接近，AC、PE和RE的值就越大，算法越有效

(21)

(22)

(23)

3.8.2 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集描述

算法用Python語言實(shí)現(xiàn)，所有實(shí)驗(yàn)均在intel(R)Core(TM)處理器i7-8700K CPU@3.70 GHz，Windows 10操作系統(tǒng)上運(yùn)行。使用數(shù)據(jù)集來自真實(shí)數(shù)據(jù)集。UCI[16]是加州大學(xué)歐文分校提供的專門用于機(jī)器學(xué)習(xí)的真實(shí)數(shù)據(jù)集。為了測試算法的有效性，從UCI數(shù)據(jù)集中選取Mushroom(簡稱Mus)，Breast-cancer(簡稱Bre)，Car和Soybean-small(簡稱Soy)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證。表5列出了這些數(shù)據(jù)集詳細(xì)信息。

表5 數(shù)據(jù)集描述

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

將本文提出的IKMCA算法與Huang提出的k-modes算法、Ng等提出IDMKCA算法和Ravi等提出EKACMD算法分別運(yùn)行30次取平均值。AC、PE和RE的計(jì)算結(jié)果見表6～表9。

表6 4種算法在Mus數(shù)據(jù)集下的實(shí)驗(yàn)結(jié)果

表7 4種算法在Bre數(shù)據(jù)集下的實(shí)驗(yàn)結(jié)果

表8 4種算法在Car數(shù)據(jù)集下的實(shí)驗(yàn)結(jié)果

表9 4種算法在Soy數(shù)據(jù)集下的實(shí)驗(yàn)結(jié)果

從上述實(shí)驗(yàn)結(jié)果可以看出，對(duì)于Mus、Bre、Car和Soy數(shù)據(jù)集而言，大多數(shù)情況下IKMCA在AC、PR和RE上優(yōu)于k-modes算法、IDMKCA算法和EKACMD算法。IMKCA算法優(yōu)于經(jīng)典k-modes算法的原因是，k-modes算法的預(yù)處理破壞了分類型特征的原始結(jié)構(gòu)。轉(zhuǎn)換后的分類特征值使用簡單漢明距離計(jì)算相異度系數(shù)并不能揭示分類型數(shù)據(jù)之間的相異度。當(dāng)數(shù)據(jù)集的特征非常多時(shí)，簡單的0-1對(duì)比可能產(chǎn)生非常大的相異度，也可能產(chǎn)生非常小的相異度甚至是相異差異度。跟經(jīng)典k-modes算法和IDMKCA、EKACMD算法相比，提出的簇內(nèi)簇間相異度可以更好地揭示數(shù)據(jù)集的結(jié)構(gòu)。

4 結(jié)束語

經(jīng)典k-modes算法使用簡單漢明距離進(jìn)行相異度計(jì)算，弱化了類內(nèi)相似性，忽略了簇間相似性。針對(duì)這些問題，本文基于簇內(nèi)簇間相似性提出相異度計(jì)算方法。該方法可以防止聚類過程中的重要特征值的丟失，強(qiáng)化了簇內(nèi)特征值之間的相似性，弱化了簇間特征值之間的相似性。提出的簇中心自動(dòng)選擇方法大大減少了隨機(jī)選取簇中心或者手動(dòng)選擇選取簇中心給聚類帶來的誤差。本文用一些說明性例子討論了k-modes算法中使用簡單漢明距離等其它幾種相異度系數(shù)的局限性，并提出了一種相異度系數(shù)?；诒疚奶岢鱿喈惗认禂?shù)改進(jìn)的分類型數(shù)據(jù)聚類算法與基于其它相異度系數(shù)的k-modes算法在UCI數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，本文提出的相異度系數(shù)計(jì)算方法保留了數(shù)據(jù)的特征，做到了低簇內(nèi)相異度高簇間相異性的標(biāo)準(zhǔn)，在聚類精度、純度和召回率方面均有提高，有效提高了分類型數(shù)據(jù)的聚類效果。