一種面向混合型數據聚類的k-prototypes聚類算法

賈子琪，宋 玲

1(廣西大學 計算機與電子信息學院,南寧 530004)2(廣西多媒體通信與網絡技術重點實驗室,南寧 530004)

E-mail:jqian@gxu.edu.cn

1 引 言

聚類旨在找出數據集內子簇之間的相關性，并評估這些子簇內數據對象之間的相似性[1].假設數據集中的每個數據對象都由m個特征描述，聚類算法的目的可以表述為“將數據集D劃分為k(k∈N+)個不同的子簇，使得每個子簇內的成員彼此之間盡可能相似，不同的子簇之間的成員彼此之間盡可能相異”.

在數值型數據聚類領域中，經典的k-means算法[2]以每個特征值的平均值表示簇中心.只能處理數值型數據.k-means算法依據待聚類數據對象和簇之間的距離進行聚類劃分.在分類型數據聚類領域中，經典的k-modes算法[3]用mode向量表示簇中心，mode向量是子簇中每個特征中出現頻率最大的特征值組合而來的.k-modes算法通過簡單漢明距離計算待聚類數據對象和簇之間的相似性，以進行聚類劃分.但是，簡單漢明距離不能有效的計算高維數據的相異度.不管是k-means算法還是k-modes算法都只能處理單一類型的數據.在一些實際應用中，人們不僅要處理數值型數據還必須處理諸如性別、顏色和疾病類型等的分類型數據.換句話說，包含數值型和分類型的混合型數據集在實際任務中無處不在.但是，在聚類分析中處理混合類型數據是很復雜的，因為數值型數據和和分類型數據之間存在很大的差異.為此，論文提出了一種混合型相異度系數，以計算待聚類數據對象和簇之間的相異度.隨后，論文基于混合型相異度系數提出了一種混合型數據聚類算法“一種面向混合型數據聚類的k-prototypes聚類算法(KPMD)”，為每個待聚類數據對象劃分合適的簇.使用KPMD算法的優點是不需要人為的設置各種參數，并且對待聚類數據的類型沒有限制，可以同時處理數值型數據、分類型數據和混合型數據.

論文的其余部分安排如下：第2節，相關工作敘述；第3節，問題陳述、相關符號描述和經典k-prototypes算法描述；第4節，論文提出的算法(KPMD)；第5節，實驗及結果分析；最后，第6節，論文得出的結論.

2 相關工作

本節闡述當前一些與基于相異度系數的混合型數據聚類最相關的重要聚類算法.

在實際的聚類劃分中，需要處理大量的高維數據集以及由分類型數據和數值型數據組成的混合型數據集.處理混合類型數據的一種簡單方法是預處理，直接將分類型特征轉換為數值型特征.例如將分類型特征轉換為二進制字符串，然后用基于數值型數據的聚類算法進行進一步的聚類劃分.然而，用二進制編碼進行預處理有四個缺點：第一，破壞了分類型數據的原始結構，導致轉換后的二進制特征沒有意義；第二，忽略了隱含的相異度信息，不能真實地反映數據集的結構；第三，如果特征值的值域很大，那么轉換后的二進制特征值將具有更大的維數；最后一個缺點是維護困難，如果為分類型特征添加新的特征值，那么所有的數據對象都將發生更改[4].為了更好地解決這些問題，許多研究人員對基于相異度系數的聚類算法進行了研究，尋找能直接處理混合型數據的有效方法.k-prototypes算法[5]及其變形算法是基于同時考慮數值型特征和分類型特征的相異度系數的混合型數據聚類算法，此類算法可以同時處理分類型和數值型數據，但是需要人為設置聚類參數.Li[6]提出了一種基于相異度系數的聚焦聚類(SBAC)算法，該算法基于Goodall相異度[7].在不預先知道特征值基本分布的情況下，對相異度系數中出現的不尋常特征值賦予較大的權重.該方法對混合型特征的處理能力較好，并且可以避免分類型數據和數值型數據之間的參數調整，但是該算法具有很高的時間復雜度.COOLCAT算法[8]是一種基于熵的分類型數據聚類算法，使用熵初始化簇中心，旨在最小化期望熵，但在處理分類型數據時不能體現特征之間的簇內相異度.OCIL算法[9]是基于無參數的混合型聚類算法，基于熵給出了統一的相異度系數.和k-prototypes及其變體一樣，OCIL算法使用k-means范例來處理混合類型數據，是一種迭代聚類算法，對初始化敏感，更適合于球形分布數據.Sangam[10]提出了一種基于相異度系數的EKACMD算法.EKACMD算法是k-prototypes的變體算法，通過對相異度系數進行改進來提高混合型數據聚類的準確率.EKACMD算法在一些情況下能較充分的考慮數據的結構特點，但在分類型數據各特征值出現頻率相等的情況下不再適用.

針對上述問題，首先，論文基于簇內簇間相異度、信息熵和最大最小值標準化提出了新的混合型相異度系數.該混合型相異度系數具有統一的標準，能夠自動設置分類型和數值型數據之間的權重參數，消除了分類型數據和數值型數據之間的計算差距，避免了分類型和數值型數據之間的特征變換和參數調整.接著，提出了一種面向混合型數據聚類的k-prototypes聚類算法(KPMD)，KPMD算法可以進行無參數聚類分析，適用于分類型，數值型和混合行數據聚類.實驗結果表明，與經典的k-prototypes算法等算法相比，KPMD可以獲得更好的聚類結果，且不需要人為手動的設置各種參數.

3 經典prototypes聚類算法及問題描述

3.1 相關符號說明

為了便于表示和更好地理解問題，論文使用的一些相關符號及其含義說明如表1所示.

3.2 k-prototypes聚類算法

Huang[5]將k-means算法和k-modes算法結合起來，提出了針對混合型數據聚類的k-prototypes算法.具體方法是，將數值型部分的“means”和分類型部分“modes”組合起來，構建了一個新的混合型簇中心“prototype”，并以prototype為基礎構建了一個適用于混合型數據的相異度系數公式和目標函數；引入權重γ來控制數值型特征和分類型特征對聚類過程的影響；采用k-means算法的基本思想，直接對混合型數據進行聚類.

假設使用k-prototypes算法對數據集D={xi,1≤i≤n}進行聚類.根據每個數據對象的m維特征的相異度，將數據集D劃分為k個子簇，對應k個prototypes.1≤s≤p為分類型數據的維度數，p+1≤s≤m為數值型數據的維度數.k-prototypes算法是將混合型數據的相異度系數分成兩個部分單獨計算的，其中數值型部分采用歐氏距離的平方，分類型部分采用簡單漢明距離[11].兩種類型數據之間的權重采用權重系數γ來進行調節[12]，如公式(1)所示.

(1)

γ是用來調節兩種類型數據在相異度系數中的比重，避免聚類結果值偏向分類型特征或者數值型特征，是k-prototypes算法的一個重要的可調節參數.k-prototypes算法的基本步驟描述如下

算法 1.k-prototypes聚類算法

輸入：聚類個數k；包含n個對象的混合型數據集D；

輸出：完成聚類的k個簇C={C1,…,Cl,…,Ck}；

Step 1.在數據集D中隨機選取k個數據對象作為初始簇中心；

Step 2.根據公式(1)計算數據集中的所有數據對象xi與簇中心ql之間的距離，根據最近原則將這些數據對象分配到離它最近的簇中去；

Step 3.更新簇中心.重新計算每個對象與當前簇中心之間的相異度；分類部分采用出現頻率最高的值，數值部分采用求平均值的方法來確定；將xi重新分配到距離它最近的簇中去；

Step 4.確定每個簇中的簇中心不再發生變化，即目標函數的值不再發生變化；如果達到，則算法結束；否則跳至Step 2繼續執行，直到目標函數值不再發生變化為止；

表1 符號說明Table 1 Symbolic description

3.3 問題描述

k-prototypes算法由于其原理簡單，易復現已經在混合型數據聚類中得到了廣泛的應用.但是，其相異度系數中的參數γ需要人為確定，對聚類結果影響很大；對分類型和數值型特征的相異度計算也存在缺陷，沒有充分的考慮兩種類型數據的結構特點和數據集整體的分布.

借助表2所示的人工數據集D1來討論用戶指定權重γ在聚類過程中的缺點.人工數據集D1包含27個數據對象，每個數據象由兩個數值型特征和一個分類型特征描述.分類型特征A3具有三個特征值DOM(A3)={A,B,C}.數值型特征A1和A2的取值均在0-80的范圍內.

表2 人工數據集D1Table 2 Artificial data set D1

關于特征A3，規定特征值為A,B,C的數據對象分別用實心三角形、實心圓、實心正方形表示.當權重γ=0時，人工數據集D4的聚類結果只取決于A1,A2兩個特征.其聚類結果如圖1所示，該數據集有三個簇.為了方便觀察，用虛線將三個簇分隔開.當γ>0，則數據對象x7可以移動到C2，因為對象x7和簇C2中大多數數據對象的特征A3是相同的.類似地，基于上述原因，數據對象x10可以移動到簇C1.權重γ的不確定，導致數據對象x7和x10是偏向數值型部分還是分類型部分也是不確定的.數據對象x1和x20可能仍然保留在原來的簇中，因為它們距離臨近的其它簇太遠了，即使它們與臨近的其它簇中的數據對象有相同的特征值.綜上所述，在相同尺度上定義數據特征和分類型特征的權重是很重要的.

4 一種面向混合型數據聚類的k-prototypes聚類算法(KPMD)

論文提出算法的動機主要有兩個方面：是為了給混合型數據聚類提供有效的相異度系數表示方法；另一方面是考慮不同特征對聚類的重要性.基于上述動機，首先，本節基于熵理論提出了基于熵權的分類型相異度系數；然后，基于最大-最小值標準化理論提出了量化的數值型相異度系數；此外，經過綜合討論提出了適用于混合型數據聚類的混合型相異度系數；最后，將提出的混合型相異度系數應用到經典k-prototypes算法上，提出了一種面向混合型數據聚類的k-prototypes聚類算法(KPMD).

圖1 人工數據集Di的聚類結果Fig.1 Clustering results of artificial data set Di

4.1 基于熵權的分類型相異度系數

為解決對信息的量化計算問題，1948年Shannon引用熱力學中熱熵的概念提出了“信息熵”的概念[13，14].信息熵可以用于計算數據的離散程度，可以為各維特征分配合適的權重提高聚類效果.熵與聚類的關系可以理解為，由相似數據對象組成的簇比由不相似數據對象組成的簇的總熵值要小.相反，如果相似的數據對象被分在不同的簇中,它們的熵值會更大.數據集越復雜，不同特征數據越多，數據集的信息熵就越大.將信息熵的概念引入到權重的計算中，可以定量的計算特征值構成的差異程度.Shannon的信息熵公式[15]定義如公式(2)所示.

(2)

性質 1.非負性.En(x)=-∑x∈Dp(xi)log(p(xi))≥0，公式(2)包含負號，這是為了確保信息量的值恒大于等于0.

性質 2.對稱性.函數的所有變量可以互換，而不影響函數值.En(X)=En(p(x1),p(x2),p(x3),…,p(xn))=En(p(x2),p(x1),p(x3),…,p(xn))=En(p(x3),p(x1),p(x2),…,p(xn))，其中i=1,2,…,s.

在聚類過程中，某分類型特征的重要程度與該它的差異程度成反比[15].在一定程度上，每維分類型特征的信息熵反映了每維分類型特征的權重ws.因此，論文根據各維分類型特征取值的不確定性，利用信息熵來計算各維分類型特征在聚類過程中的重要程度，為相異度系數分配權重.

定義 1.特征值的簇內相對頻率

(3)

定義 2.特征值的簇間分布頻率

(4)

定義 3.分類型相異度系數

令dC(xi,ql)表示混合型數據集分類型數據部分的相異度，滿足公式(5).

(5)

其中，δ(xi,s,ql,s)定義如公式(6)所示.此定義的前提是，每維分類型特征占有相同的權重.

(6)

(7)

(8)

定義 6.分類型數據第s維特征上的權重ws

(9)

(10)

定義 7.基于熵權的分類型相異度系數

對于任意xi,ql∈D，它們之間基于熵權的分類型相異度系數定義如公式(11)所示.

(11)

使用k-prototypes算法的相異度計算結果為：

d(x16,q1)=d(x16,q2)=0+0+0=0；

d(x16,q3)=1+0+1=2；

使用EKACMD算法的相異度計算結果為：

表3 人工數據集D2Table 3 Artificial data set D2

d(x16,q2)=1.896392；d(x16,q3)=2.836363

使用KPMD算法的相異度計算結果為：

d(x16,q2)=0.632130；d(x16,q3)=0.946240；

由上述計算可知，KPMD算法的相異度系數可以對x16進行正確的劃分.

4.2 量化的數值型相異度系數

定義 8.數值型相異度系數dN(xi,ql)

令dN(xi,ql)表示混合型數據集數值型數據部分的相異度，定義如公式(12)所示.

(12)

(13)

定義 9.量化的數值型相異度系數dN(xi,ql)

(14)

4.3 加權的混合型相異度系數

定義 10.加權的混合型相異度系數dw(xi,ql)

設D={xi,1≤i≤n}是待聚類的混合型數據集，該數據集有n個數對象，每個對數據象有m維特征(前p維為分類型特征，后m-p維為數值型特征)，將數值型特征看作一個整體(一個向量)進行處理；將分類型特征看成p維向量處理.拿一個有p維分類型特征m-p維數值型特征的數據對象xi舉例，在計算相異度的過程中，使用1個數值向量和p個分類型特征來計算，即在相異度系數過程中一共有1+p維向量參與計算.因此，對于數據集中的任意數據對象xi和xj，它們之間的相異度系數定義如公式(15)所示.

(15)

定義 11.考慮權重的目標函數Fw(U,Q)

將公式(15)中定義的相異度系數應用到k-prototypes算法的目標函數中.得到加權的目標函數Fw(U,Q)，其定義如公式(16)所示.

(16)

其中，

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

(17)

(18)

(19)

當目標函數Fw(U,Q)的值在滿足約束條件公式(17)-公式(19)的情況下，達到極小值，此時聚類過程結束.

4.4 KPMD算法流程

KPMD算法步驟如下：

算法2.一種面向混合型數據聚類的k-prototypes聚類算法(KPMD)

輸入：聚類個數k；包含n個對象的混合型數據集D；

輸出：聚類完成的k個簇C={C1,…,Cl,…,Ck}

Step 1.在數據集D中隨機選取k個對象作為初始簇中心Q(0)=q1,…,ql,…,qk；

Step 2.初始化過程.根據公式(1)計算數據集中的每個數據對象xi與簇中心ql之間的相異度，根據最近原則將這些數據對象分配到離它最近的簇中；

Step 3.計算數值型特征的最大最小值；

Step 4.計算每維分類型特征的權重；

Step 5.迭代過程.根據公式(15)重新計算每個數據對象xi與簇中心ql之間的相異度，根據最近原則，將xi重新分配到離它最近的簇中；

Step 6.更新簇中心，確定每個子簇中的簇中心不再發生變化，即目標函數Fw(U,Q)的值不再發生變化；如果不再變化，則算法結束，否則重復Step 3-Step 5，直到目標函數值不再發生變化為止.

KPMD算法流程圖如圖2所示.

KPMD算法的時間復雜度主要包括初始化階段和迭代階段中每次計算相異度和更新簇中心.在初始化過程中將所有數據對象劃分到合適的簇所需的時間復雜度是O(nkm).根據公式(16)，計算待聚類分類型數據對象與簇之間的相異度的時間復雜度是O(nsp)，計算待聚類數值型數據對象與簇之間的相異度的時間復雜度是O(m-p)，因此計算混合型數據的總相異度的時間復雜度是O(nsp+(m-p)).假設為所有待聚類數據對象劃分合適的簇需要的迭代次數為t，n是數據集中的數據對象數，m是數據集的總特征維數,k是簇數，p是分類型特征的維數，m-p是數值型特征的維數.在通常情況下

圖2 KPMD算法流程圖Fig.2 Flow chart of KPMD algorithm

n?k,t,m,p,ns.則迭代過程需要的總時間復雜度是O(nkt(nsp+(m-p))).因此，KPMD算法的時間復雜度為O(nkm)+O(nkt(nsp+(m-p))).

5 實驗及結果分析

5.1 性能指標

為了評估論文提出算法的有效性，論文采用指標聚類精度(accuracy，AC)對聚類結果進行評價，如公式(20)所示.NUM+表示正確分到簇Cl的對象數.聚類精度AC表示正確分到簇Cl中的對象數占總對象個數的比值.聚類正確率越高，聚類劃分的正確性越高.

(20)

如果聚類結果與數據集的真實類劃分越接近，AC值就越大，算法效果就越好.在下面的實驗中，將論文提出的KPMD算法與Huang提出的k-prototypes算法和Sangam提出EKACMD算法進行對比實驗.

5.2 實驗環境

算法用Python語言實現，所有實驗均在intel(R)Core(TM)處理器i7-8700K CPU@3.70GHz，Windows 10操作系統上運行.使用數據集均來自UC機器學習數據庫.UCI1是加州大學歐文分校提供的專門用于機器學習的真實數據集.為了驗證提出算法的有效性和可行性，論文從UCI數據集中選取Bank Marking(簡稱Bank)，Zoo兩個混合型數據集進行實驗驗證.選取這兩個數據集作為實驗數據集主要是因為混合型數據集有比純分類型數據集和純數值型數據集更高的復雜性.因此不可以單一的、隨機的選取數據集以驗證算法的有效性.選取Bank數據集做為實驗數據集主要原因是為了驗證在分類型和數值型特征分布均勻的情況下KPMD算法的有效性.Bank數據集的特征分布比較特殊，其分類型和數值型數據特征的個數完全一樣；選取Zoo數據集做為實驗數據集主要原因是為了驗證在分類型和數值型特征分布不均勻的情況下KPMD算法的有效性.Zoo數據集的特征分布比較特殊，其分類型和數值型數據特征的個數差別非常大.此外，選取這兩個數據集作為實驗數據集的另一個原因是為了驗證在數據集簇數較少和較多的情況下，KPMD算法的有效性.所選數據集的詳細信息如表4所示.

表4 混合型數據集描述Table 4 Description of mixed type data set

5.3 實驗結果分析

5.3.1 算法的精確度分析

實驗比較了KPMD與k-prototypes，EKACMD在混合型數據集Bank和Zoo上的性能.每個算法在每個數據集上分別執行30次取平均值，聚類結果統計匯總在表5～表6中.對于k-prototypes，EKACMD和KPMD，論文分別設置k=2，k=4，k=6，k=8，k=10五種不同的聚類參數進行實驗.由于EKACMD和KPMD都不需要設置聚類參數γ，因此論文只單獨設置k-prototypes的聚類參數γ.

表5 銀行數據集的聚類精度比較Table 5 Comparison of cluster accuracy on data set Bank

表6 動物園數據集的聚類精度比較Table 6 Comparison of cluster accuracy on data set Zoo

銀行數據集有41188個數據對象，10個分類型特征，10個數值型特征，2個簇.論文對Bank數據集以4.8%的采樣率進行采樣.表5顯示，當k=2時，KPMD的AC值分別比k-prototypes和EKACMD高9.43%，5%.

動物園數據集有101個數據對象，15個分類型特征，1個數值型特征，7個簇.表6顯示，當k=7時，KPMD的AC值分別比k-prototypes和EKACMD高11.88%，4.95%.

表5和表6中的實驗結果表明，就聚類精度而言，論文的算法比其他算法獲得了更好的聚類結果.因為在論文算法中，簇中心的表示包含了分類型和數值型特征的分布信息.此外，論文的混合型相異度系數考慮了每個特征在聚類過程中的重要性，可以自動的計算不同特征的權重.上述原因使論文的算法可以獲得更好的聚類結果.

5.3.2 提出算法與對比算法的聚類效果的直觀對比

圖3顯示了KPMD和k-prototypes、EKACMD在不同參數k的銀行數據集上的聚類精度.從圖3中可以明顯看到KPMD在整體上產生了良好的聚類結果，在k=4處取得最差值0.858.

圖3 銀行據集的聚類精度比較Fig.3 Comparison of cluster accuracy on data set Bank

圖4顯示了KPMD和k-prototypes、EKACMD在不同參數k的動物園數據集上的聚類精度.可以看到KPMD的曲線高于k-prototypes和EKACMD.

圖4 動物園據集的聚類精度比較Fig.4 Comparison of cluster accuracy on data set Zoo

從圖3和圖4可以看出，在隨機初始化的情況下，所提出的無參數算法KPMD在聚類精度方面優于k-prototypes算法和EKACMD算法.從表4所示的數據集詳細信息可以看出，所選取的Zoo數據集中的分類型特征與數值型特征的個數差別很大，僅有1個數值型特征和15個分類型特征.盡管該數據集兩種類型的特征分布差距很大，KPMD算法還是取得了令人滿意的聚類結果.這表明所提出的混合型相異度系數適用于各種復合類型的數據集，并且不需要手動設置任何參數來調整分類型特征和數值型特征的權重.

6 結 論

k-prototypes算法是混合數據聚類中廣泛使用的一種聚類算法，但聚類精度較低，聚類結果不穩定.因此論文提出了一種基于對象相異度的通用聚類框架，并通過該框架給出了統一的混合型相異度系數.對數值型數據，論文使用量化的數值型相異度系數來標準化不同的數值；對分類型數據，論文使用基于熵權的分類型相異度系數；對混合型數據，論文使用加權的混合型相異度系數.提出的混合型相異度系數不僅保留了不同類型數據的特征，還為分類型數據和數值型數據設置了合適的權重，并且基于熵理論為分類型數據內部的各個特征分配了不同的熵權，最后，論文提出了一種迭代算法(KPMD)來實現混合型數據聚類.與現有算法相比，UCI真實數據集的實驗證明論文提出的相異度系數是一種更合理的混合數據聚類分析方法.總的來說，論文提出的KPMD算法不僅可以準確地找到聚類個數而且提高了聚類精度.