李順勇， 顧嘉成

(山西大學 數(shù)學科學學院, 山西 太原 030006)

0 引言

聚類分析是數(shù)據(jù)挖掘過程中一個不可或缺的環(huán)節(jié)[1,2]，聚類的目標是將相似的對象歸到同一類中，不相似的歸到不同的類中[3].聚類方法多種多樣，大致可以從基于層次、密度、劃分、網(wǎng)格、模型幾個方面進行分類，如圖1所示.

文獻[4]首次提出K-means算法，但由于該算法中的代價函數(shù)是面向數(shù)值型數(shù)據(jù)的，所以此算法應用到其他類型的數(shù)據(jù)上時存在一些不足.文獻[5]中提出的方法結(jié)合了UKF思想，提升了估計收斂速度，但是在處理分類型數(shù)據(jù)時該算法效果并不顯著.基于此，文獻[6]提出了K-modes算法，該算法用modes代替means，采用簡單匹配差異度來度量距離，在處理分類型數(shù)據(jù)時有較好的效果.文獻[7]中提出的算法將聚類算法與Autoencoder算法結(jié)合，提高了推薦質(zhì)量.文獻[8]提出了K-prototypes算法，該方法引入了參數(shù)控制兩種屬性數(shù)據(jù)在計算距離時所占的權(quán)重從而實現(xiàn)對混合型數(shù)據(jù)的聚類.之后又有類似算法被提出，例如EKP[9]、DP-MD-FN[10]、FKP-MD[11]等算法.陳韡等[12]考慮到樣本與類的差異，對相異度公式進行改進，得到了較好的實驗結(jié)果.文獻[13]將信息熵與混合數(shù)據(jù)加權(quán)算法結(jié)合，解決了聚類算法過度依賴數(shù)據(jù)集總體分布的不足.當然，雖然很多學者提出了一些不同的新算法，但是仍然沒有徹底解決K-prototypes存在的一些局限性.

K-prototypes由于其算法較為簡單并且容易實現(xiàn)，在得到廣泛應用的同時也凸顯出了一些不足之處，主要體現(xiàn)在以下三點：(1)該方法的聚類效果易受初始原型選擇影響；(2)計算分類型數(shù)據(jù)距離時采用的是0-1匹配原則，不能較好的體現(xiàn)數(shù)據(jù)之間的差異；(3)該方法只能得到局部最優(yōu)，無法做到對所有樣本信息進行覆蓋.針對以上不足，本文定義了新的距離公式，并選取較多初始原型來覆蓋數(shù)據(jù)整體信息，隨后迭代消去多余原型.

1 K-prototypes算法[8]

設數(shù)據(jù)集X={X1,X2,X3,…,Xn}，一共有n個數(shù)據(jù)，并且數(shù)據(jù)集中的各個數(shù)據(jù)均有m個屬性，即Xi={xi1,xi2,xi3,…,xip,xi(p+1),…,xim}，數(shù)值型數(shù)據(jù)在前并且一共有p個屬性，分類型數(shù)據(jù)在后一共有m-p個屬性.設初始原型集合為V={V1,V2,V3,…,Vk}，中間過程中得到的集合為C={C1,C2,C3,…,Ck}，距離公式如定義1所示.

定義1[8]樣本Xi到原型Vi距離為：

(1)

其中,η為分類屬性權(quán)重.

定義2[8]求解聚類分析中的準則函數(shù)為：

(2)

K-prototypes算法是基于劃分將樣本集X分為k個互不相交的類，并使得目標函數(shù)值最小，其具體算法如下：

算法1[8]K-prototypes算法

輸入：原型k，數(shù)據(jù)集X；

輸出：劃分結(jié)果.

Step1:選擇k個原型V；

Step2:根據(jù)公式(1)得到n-k個樣本到k個原型的d(Xi,Vl)，并根據(jù)計算結(jié)果把n-k個樣本分到距離自身最近的原型中，更新簇中心；

Step3:重新計算并得出新的簇劃分結(jié)果；

Step4:重復上述步驟，直到類中的樣本不再改變即迭代準則函數(shù)最小.

2 EKPCA算法

針對以上K-prototypes算法存在的局限性，本文提出了一種增強的K-prototypes混合數(shù)據(jù)聚類算法(An EnhancedK-prototypes Mixed Data Clustering Algorithm，EKPCA).本文還定義了一種新距離公式，并選取較多初始原型來覆蓋數(shù)據(jù)整體信息，隨后再迭代消去多余原型.新距離公式如下.

定義3樣本Xi到原型Vi距離為：

(3)

指數(shù)函數(shù)ex隨著x的增大其斜率也在增大，故本文利用指數(shù)函數(shù)性質(zhì)定義了距離計算公式，擴大了數(shù)據(jù)之間的差異性，這樣有助于對簇邊緣的點進行歸類.

通過一個例子來驗證公式(3)滿足距離的三條性質(zhì)，可以度量混合數(shù)據(jù)距離.

例假設X1={1,a,b,c,d},X2={3,d,c,b,a},V={2,a,c,d,b},經(jīng)過計算可得：d(V,X1)=1+3e-0.25,d(V,X2)=1+3e-0.25,d(X1,X2)=4

非負性：由上述結(jié)果可知：

d(V,X1)>0,d(V,X2)>0,d(X1,X2)>0

故滿足非負性；

對稱性：由上述結(jié)果可知：

d(V,X1)=d(X1,V)

d(V,X2)=d(X2,V)

d(X1,X2)=d(X2,X1)

故滿足對稱性；

三角不等式性:由上述結(jié)果可知：

d(V,X1)+d(V,X2)>d(X1,X2)

d(V,X1)+d(X1,X2)>d(V,X2)

d(V,X2)+d(X1,X2)>d(V,X1)

即滿足三角不等式.

綜上，公式(3)滿足距離的三條性質(zhì)，可以用來度量距離.

公式(3)利用指數(shù)函數(shù)的性質(zhì)，當分類型樣本數(shù)據(jù)兩兩之間相似度較小時，β取值較大，相似度較大時，取值較小.指數(shù)函數(shù)是非線性變化的，這樣可以滿足在分類數(shù)據(jù)差異性較大時較大增大分類型數(shù)據(jù)距離權(quán)重，兩個樣本分類數(shù)據(jù)部分差異性小的時候較大減小分類型數(shù)據(jù)距離權(quán)重，從而使各個數(shù)據(jù)的差異性更加顯著.

EKPCA算法在選擇初始點時，選擇大于目標原型k的數(shù)目，選取μk個原型，μ通常為k的倍數(shù)，隨后在聚類過程中計算μk個簇中已有數(shù)據(jù)到其余μk-1個簇中心的距離，合并距離最小的簇中的數(shù)據(jù).接著計算μk-1個簇中已有數(shù)據(jù)到其余μk-2個簇中心的距離，合并距離最小的簇中的數(shù)據(jù)，按照這個過程一直合并直到剩余k個簇.μ具體取值需要在實驗中進行確定，本文會在后面實驗分析中對其進行確定，算法步驟如下：

算法2EKPCA算法

輸入：原型μk，數(shù)據(jù)集X；

輸出：分類結(jié)果.

Step1:選取μk個原型；

Step2:根據(jù)公式(3)計算n-μk個樣本到μk個原型的距離，根據(jù)計算結(jié)果將n-μk個樣本依次歸到距離最近的原型中，計算得出聚類中心；

Step3:計算μk個簇中已有樣本到其余μk-1個簇中心的距離，合并距離最小的簇中的樣本，重新計算得到新的聚類中心；

Step4:重復上述步驟，直到剩余k個原型即可.

3 仿真實驗

3.1 數(shù)據(jù)集的選擇及評價標準

選取UCI數(shù)據(jù)庫中8個數(shù)據(jù)集對算法性能進行評測，數(shù)據(jù)集形式如表1所示.其中，h表示總屬性數(shù)；h1表示數(shù)值型數(shù)據(jù)屬性數(shù)；h2表示分類型數(shù)據(jù)屬性數(shù)；Class表示分類個數(shù)，即模k，instance表示樣本個數(shù).從表1可以看出，Wine和Seeds兩個數(shù)據(jù)集h1=0，為數(shù)值型數(shù)據(jù)集；Tia-tac-toe和Congressional Voting兩個數(shù)據(jù)集h2=0，為分類型數(shù)據(jù)集；其余四個數(shù)據(jù)集中h1和h2均不為0，為混合型數(shù)據(jù)集.數(shù)據(jù)中存在的缺失數(shù)據(jù)采用文獻[14]中直接刪除的方法進行清洗.

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

評價標準選取JC(Jaccard Coefficient)、RI(Rand index)、FMI(Fowlkes-Mallows scores)作為評價指標.

上述定義的4個值表示樣本對個數(shù)，a表示在C和C′中均屬于相同類別的樣本對，b、c、d定義與a類似.通過計算可得上述四個值的和為n(n-1)/2.

基于上述4個值，計算出JC(Jaccard Coefficient)、FMI(Fowlkes-Mallows scores)以及RI(Rand index).

JC指數(shù)(Jaccard Coefficient)[15]，用來比較C和C′的差異性，計算公式如下：

(4)

RI指數(shù) (Rand index)[15]，用來計算正確率，計算公式如下：

(5)

FMI指數(shù) (Fowlkes-Mallows scores)[15]，通過a、b、c、d求得的查全率和查準率可以計算得出，計算公式如下：

(6)

JC、RI以及FMI的取值范圍均為0～1之間，且相應指標值越接近1，劃分效果越好.

3.2 參數(shù)μ的確定

新算法EKPCA中，對μ從1開始取值，一直到10結(jié)束.利用表1中Wine和Heart disease兩個數(shù)據(jù)集進行實驗分析，同時選用JC和FMI[14]兩個指標進行評測，其結(jié)果如圖2、圖3所示.

由圖2可知，水平軸表示的是初始選取原型k的值，縱軸表示的是JC和FMI兩個指標的值，由以上評價指標定義可知指標的值越高越好，當k=18即μ=6時JC和FMI值在Wine數(shù)據(jù)集上較高且初始模較少.μ具體取值情況還需分析其他數(shù)據(jù)集的比較結(jié)果.

由圖3可知，水平軸表示的是初始選取原型k的值，縱軸表示的是JC和FMI兩個指標的值，k=12也即μ=6時JC和FMI值在Heart disease數(shù)據(jù)集上較高且初始模較少，算法迭代次數(shù)也較少.綜合圖2和圖3分析，選取μ=6為初始迭代原型參數(shù).

圖2 wine數(shù)據(jù)集上不同k值 下結(jié)果比較

圖3 Heart disease數(shù)據(jù)集上不同k值 下結(jié)果比較

3.3 算法比較

選取表1中8個數(shù)據(jù)集對算法性能進行評測，分別在數(shù)值型、分類型以及混合型數(shù)據(jù)集上的聚類結(jié)果進行對比.

3.3.1 數(shù)值型數(shù)據(jù)聚類結(jié)果對比

選取表1中的Wine和Seeds兩個數(shù)值型數(shù)據(jù)集，將EKPCA算法與K-means、DBSCAN[16]、FCM[17]算法的聚類結(jié)果進行對比，選取JC、RI和FMI為評價標準，其結(jié)果如表2以及圖4、圖5所示.

表2 數(shù)值型數(shù)據(jù)聚類結(jié)果比較

由表2可知，EKPCA算法在Wine和Seeds數(shù)據(jù)集上JC、RI、FMI三個指標均高于其他算法，在Wine數(shù)據(jù)集上EKPCA算法的RI值為0.943 3，F(xiàn)MI值為0.922 9，第二高的FCM算法RI值為0.903 4，F(xiàn)MI值為0.820 6，兩者相比EKPCA算法在兩個指標上均高出不少.說明EKPCA算法相較于其他算法性能有明顯的提升，優(yōu)勢明顯.

圖4 Wine數(shù)據(jù)集聚類結(jié)果比較

圖5 Seeds數(shù)據(jù)集聚類結(jié)果比較

圖4以及圖5中的柱體越高，表示在各項指標上對應算法的效果越顯著.從圖4及圖5可以看出，EKPCA算法在Wine和Seeds數(shù)據(jù)集上JC、RI和FMI三個指標柱體高度均高于其他算法，并且從圖4中可以直觀的看出EKPCA算法在三個指標上柱體高度高出其他算法一大截，說明EKPCA算法明顯優(yōu)于其他算法.

3.3.2 分類型數(shù)據(jù)聚類結(jié)果對比

選取表1數(shù)據(jù)集中的Tia-tac-toe和Congressional Voting兩個分類型數(shù)據(jù)集，將EKPCA算法與K-means、DBSCAN、FCM算法的聚類結(jié)果進行對比，選取JC、RI和FMI為評價標準，其結(jié)果如表3及圖6、圖7所示.

表3 分類型數(shù)據(jù)聚類結(jié)果比較

從表3可以看出，DBSCAN、FCM算法在Tia-tac-toe和Congressional Voting數(shù)據(jù)集上相比K-means算法性能提升較小，甚至部分指標略低于K-modes.相較起來，本文提出的EKPCA算法在JC、RI和FMI三個指標上均高于其他算法，并且在FMI值以及RI值上相比其他三個算法提升比較明顯，尤其是在Tia-tac-toe數(shù)據(jù)集上由EKPCA算法計算出的JC值高出K-means算法0.223 3.綜合比較起來EKPCA算法性能卓越.

圖6 CV數(shù)據(jù)集聚類結(jié)果比較

圖7 Tia-tac-toe數(shù)據(jù)集聚類結(jié)果比較

圖6、圖7中的柱體越高，表示在各項指標上對應算法的效果越好.從圖6、7可得， EKPCA算法在Congressional Voting數(shù)據(jù)集和Tia-tac-toe數(shù)據(jù)集上JC、RI和FMI三個指標柱體高度均高于其他算法，并且柱體高出部分較為明顯，說明EKPCA算法有明顯優(yōu)勢.

3.3.3 混合型數(shù)據(jù)聚類結(jié)果對比

選取表1數(shù)據(jù)集中的Heart Disease、Australian Credit Approval、German Credit、Hepatitis四個混合型數(shù)據(jù)集，將EKPCA算法與K-prototypes[8]、EKP[9]、DP-MD-FN[10]、FKP-MD[11]算法結(jié)果進行對比，結(jié)果如表4以及圖8所示.

圖8 混合型數(shù)據(jù)聚類結(jié)果比較

圖8中的堆積面積越大，表示在各項指標上對應算法越好.從圖8可以看出，代表EKPCA算法的顏色部分堆積面積最大，說明EKPCA算法在四個混合型數(shù)據(jù)集上JC、RI和FMI三個指標均高于其他算法，說明EKPCA算法優(yōu)勢較為明顯.

表4 混合型數(shù)據(jù)聚類結(jié)果比較

從表4可以看出，EKPCA算法在Heart Disease、Australian Credit Approval、German Credit這三個數(shù)據(jù)集上JC、RIF、MI三個指標均取得了最高值，并且三個評價指標提升幅度較大.在Heart Disease數(shù)據(jù)集上提升最為明顯，RI值達到了0.818 2,高出K-prototypes算法0.308 1.雖然在Hepatitis數(shù)據(jù)集上EKPCA算法FMI值比EKP算法小，但是相差較小.綜合比較起來，EKPCA算法可以達到預期的效能.

4 結(jié)論

數(shù)據(jù)的復雜多變導致生活中出現(xiàn)的數(shù)據(jù)大多是混合型的，這使得對混合型數(shù)據(jù)聚類的關(guān)注度越來越高，本文提出了一種增強的K-prototypes混合數(shù)據(jù)聚類算法，算法首先提出了新的距離計算公式，然后通過選取較多的初始原型再進行迭代消去多余原型從而達到覆蓋數(shù)據(jù)整體信息的效果.實驗結(jié)果表明EKPCA算法聚類性能較優(yōu).