一種改進的K-Prototypes聚類算法

孫志冉，蘇 航，梁 毅

北京工業大學 信息學部，北京 100124

1 引言

聚類算法[1]作為數據挖掘領域的重要組成部分，能夠在無標記樣本的條件下，根據各數據對象的相關信息，將相似的對象進行分類，使得同一類中的對象盡可能相似，不同類中的對象差異盡可能大，從而發現數據的潛在結構和組織規律。在現實的應用中，數據集中不僅包含著年齡、身高等定量的數值屬性，還包含如性別、職業等類別屬性，同時包含數值型屬性和類別型屬性的混合型數據集無處不在。為解決混合型數據的聚類問題，Huang 提出了由K-Means[2]和K-Modes[3]算法結合而成的，可處理混合型數據的K-Prototypes[3]聚類算法。該算法具備簡單高效的特點，應用也十分廣泛，但是仍然存在不足，如隨機選擇初始聚類中心導致算法穩定性和準確率較差、需要人為確定類簇個數等。

針對原始K-Prototypes 算法的問題，近年來有不少學者進行了不同程度的優化。針對屬性值距離度量表示不準確的問題，陳韡等[4]改進了分類屬性的距離計算公式，不單單考慮樣本與聚類中心的距離，還加入了樣本與類簇中已有數據之間的差異；Sangam等[5]考慮每個類別的相對頻率和分布，對分類屬性采用加權漢明距離測度；Cui等[6]提出了RS-K-Prototypes算法，將數值數據離散化為分類數據，利用粗糙集刻畫屬性值之間的距離，并進行異常值檢查，但如果不同類的屬性值數據范圍之間存在交叉，則離散化數據難以準確分類，聚類結果很大程度上受離散化情況的影響。針對類簇邊界數據對象歸屬應具有模糊性，而在劃分迭代過程中沒有考慮模糊性的問題，Chen等[7]考慮到樣本在類簇歸屬上的模糊性，根據模糊隸屬度的思想，提出了模糊K-Prototypes（FuzzyK-Prototypes，FKP）算法。針對忽視了各屬性對聚類結果的貢獻可能不同的問題，Ji等提出了IWKM算法和WFK-Prototypes 算法[8]，利用模糊集和模糊質心的思想，考慮了不同屬性對聚類過程的不同影響力，在一定程度上提高了聚類精度；歐陽浩等人[9]根據信息熵對分類屬性賦權值，并利用粗糙集表示對象之間的差異度；Yao 等[10]提出了基于K-Prototypes 的 KLS 算法，改進了距離算法的距離公式，對數值型和分類型屬性的權重進行了統一，可以滿足敏感屬性的多級隱私保護要求，但該算法的權重是由專家預先指定，需要大量人工干預。為改進傳統算法隨機選擇初始中心點的問題，Zheng 等[11]提出了進化K-Prototypes（EvolutionaryKPrototypes，EKP）算法，引入了具有全局搜索能力的進化算法（Evolutionary Algorithm，EA），改進了K-Prototypes聚類結果對初始選點敏感，容易造成局部最優的問題，但未對距離計算方式改進，所以結果仍不太理想；文獻[12]基于先驗信息利用最大最小距離算法確定類簇個數和初始中心，但該算法需要有類標簽信息；文獻[13-15]都能夠根據密度和距離分布[16]選擇初始聚類中心，但DC-MDACC 算法[13]中心點受置信因子參數影響較大，DPCM[14]算法利用拐點進行選擇，對于多個類簇的識別，效果不佳，DP-MD-FN 算法[15]引入了額外的閾值截斷參數來選擇中心點，參數需先驗知識，且可能選出同一類簇的兩個高密度點，造成聚類結果有誤。

以上算法從不同方面改進了原算法的不足，但鮮少有能自動確定類簇個數的改進方法，且大多算法初始選點隨機具有不穩定性。為解決該問題，本文提出基于密度自動確定聚類中心的DACKP 算法，該算法根據數據對象的密度和數據對象間的距離，實現類簇個數的自動識別，并選擇出初始聚類中心，優化初始選點造成的局部最優問題，保證聚類結果的準確性。另外，在聚類過程中還優化了距離公式，考慮各屬性對聚類的不同影響，并保存類簇中重要屬性值，以達到更好的聚類效果。

2 傳統K-Prototypes聚類算法

K-Prototypes 聚類算法是對K-Means 和K-Modes 聚類算法的擴展，用于處理混合型數據的聚類問題。

定義1設S=(U,A,V,f)是一個信息系統，其中U={x1,x2,…,xn}是由n(n≥1)個數據對象組成的有限數據集合，xi(1 ≤i≤n)表示由m(m≥1)個屬性描述的數據對象；A={a1,a2,…,amr,amr+1,amr+2,…,amr+mc}表示m個屬性組成的有限屬性集合，其中a1～amr表示mr個數值型屬性，amr+1～amr+mc表示mc個分類型屬性，即m=mr+mc；V={vj|1 ≤j≤m}表示所有屬性值域的集合，vj表示屬性aj的取值集合，aj∈A，若1 ≤j≤mr，則vj由實數域表示數值屬性取值集合，根據實際需求確定上下界，若mr＜j≤m，則vj={v1j,v2j,…,vnjj}表示分類屬性取值集合，nj表示分類屬性aj的不同取值個數；f:U×A→V表示一個數據對象的映射信息函數，對?xi∈U,aj∈A，有f(xi,aj)∈vj。

定義2數據集U聚類過程中的類簇劃分表示為集合C={C1,C2,…,Ck}，其中k為類簇個數，U，并且Ci?Cj=?(1 ≤i,j≤k,i≠j)，即C是U的一個劃分。

定義3屬性值在類簇Cl中的出現比例表示為并且0 ≤。

定義4數據集U聚類過程中類簇的中心點表示為集合Z={z1,z2,…,zk}，zl表示類簇Cl的中心點，且對每個中心點zl(1 ≤l≤k)都有：

數據對象xi和類中心zl的相異度為：

K-Prototypes算法的目標函數可描述為：

其中，wli∈{0,1} ，1表示數據對象xi被劃分到第l個類簇中，0 表示數據對象xi沒有被劃分到第l個類簇中，每個數據對象被劃分且僅被劃分到一個類簇中。

K-Prototypes 算法的步驟為：輸入為數據集U和類簇個數k；首先從數據集中隨機選擇k個樣本作為初始聚類中心Z；然后根據相異度度量公式（2）把數據集中的樣本x逐一分配到最近的類簇中，并按照公式（1）更新聚類中心Z，迭代劃分和更新聚類中心的過程，直到目標函數F不再發生變化，即每個數據對象不再改變所屬聚類時算法結束，得到聚類結果C。

K-Prototypes 聚類算法達到迭代終止條件，即目標函數F減小到不再變化時，則認為算法收斂，但目標函數可能有多個極值點，而初始聚類中心的選擇，可能導致算法收斂到局部最優，所以K-Prototypes 聚類算法對初始聚類中心敏感。另外算法采用公式（2）來度量數據對象間的相異度，忽略了數值屬性對聚類結果的影響，以及不同屬性對聚類結果的不同影響；由于分類屬性聚類中心單值表示的問題，造成屬性缺失，不能準確刻畫類簇的信息，造成分類屬性的相異度度量忽略了類內對象的總體相異度，并且當相異度相同時，算法不能準確地劃分到相似性更大的類簇中。K-Prototypes 算法還需指定類簇數目，而對于無序的數據集，類簇數目往往很難確定。針對上述問題，本文提出了一種改進K-Prototypes算法。

3 改進的K-Prototypes算法

針對K-Prototypes 算法的不足，本文提出了新的相異度度量方法，并解決隨機選取初始聚類中心的問題，且可自動確定類簇數目，提高算法的準確率和穩定性。

3.1 新相異度度量公式

本文提出的相異度度量方法，使用信息熵來確定各屬性的重要程度，對各屬性進行加權；對于分類屬性相異度度量采用多Modes的聚類中心，不單單保留類簇內出現頻率最高的值，而是保留全部屬性值及其出現頻率，并給出混合屬性的相異度度量公式。

信息熵表示事件發生的概率，對于數值屬性aj(1 ≤表示在屬性aj下對象xi的取值所占的比重；對于分類屬性aj(mr＜j≤m) ，表示在屬性aj下第t個屬性值所占的比重，其中ntj表示屬性值為的對象個數，故各屬性的信息熵表示為：

屬性在聚類過程中的重要程度與其屬性值構成的差異度成正比。熵值越大則屬性值差異度越大，故該屬性的權重值應該更高，反之，熵值越小表明屬性值差異度越小，故該屬性的權重值應該更低。屬性aj權重值表示為0 ≤ωj≤ 1 。

根據定義4可知，傳統算法對分類屬性聚類中心的表示是直接選擇頻率最高的屬性值，這不能準確地刻畫類簇內的信息，在多于一個類簇出現頻率最高的屬性值相同時，數據對象到每個類簇的距離相同，算法不能準確劃分到更相近的類簇中，故本文將聚類中心的分類屬性值表示為該屬性的所有屬性值及其出現頻率組合，則聚類中心的映射函數定義為：

基于權重和聚類中心的優化，本文給出的相異度度量公式定義為：

3.2 初始聚類中心點的選取

為解決隨機或人工干預選擇聚類中心的問題，考慮到數據的實際分布情況，結合文獻[16]提出的數據分布的密度和高密度距離定義，本文使其應用到混合數據集上，并提出了初始聚類中心點的選取方法，能夠有效地確定初始中心點和類簇個數。該方法首先進行聚類中心的預選取，然后進行優化確認最終的中心點集合和類簇個數。

（1）聚類中心預選取：通常情況下，中心點往往分布在數據對象密度較高的區域中，且不同類簇之間的間距較大，根據這兩個假設，文獻[16]定義兩個關鍵參數：①每個數據對象xi的局部密度ρi，常用截斷核和高斯核兩種定義方式，分別如公式（7）和（8）所示，公式（7）取值為離散的整數，往往用于大規模數據集，公式（8）取值為實數；②每個數據對象xi到局部密度高于它且距離最近的數據點xj之間的距離δi，定義如公式（9）：

其中，d(xi,xj)表示數據對象xi和xj之間的距離，dl為截斷距離，由近鄰占比pd來確定，通常pd∈[1%，2%]，即所有d(xi,xj)由小到大排序后第1%到2%的值取作dl；為了能更好適用于混合數據集，結合3.1節中提出相異度度量公式，數據對象之間的距離公式描述為：

其中：

由于聚類中心的局部密度應該大于其周圍數據對象的局部密度，且不同類簇的聚類中心之間的距離應該相對較遠，故聚類中心點應為ρi和δi都較高的數據點，則設定預選初始中心點集合Zp應滿足：

其中，μ(δ)表示所有數據對象δi的均值，μ(ρ)表示ρi的均值。通過均值篩選掉大部分單個類簇中的多余密度較大的點，以及δi值過大但密度較小的噪聲點。

（2）聚類中心優化：預選中心點集合中包含了實際應有的中心點，但也包含了非中心點（高密度類簇內，中心點附近往往存在密度同樣較大的點），如圖1所示，多余的中心點導致紅色框內的原本一個類簇，分為了兩個類簇。為防止這種情況，需要將原本屬于一個類簇的預選中心點進行合并，如圖2 所示，兩個中心點之間的距離應為大于2dl，若小于2dl，則表示兩個中心點屬于同一個類簇。

圖1 R15數據集上的錯誤聚類結果

圖2 中心點距離決策圖

最終中心點選取過程：首先對Zp集合中的數據根據公式（12）計算ηi，ηi綜合考慮了ρi和δi，且忽略了量綱的差異，ηi值越大越可能成為中心點。

然后將數據對象按照ηi從大到小排序，選ηi最大的數據對象作為確認的中心點，添加到最終的初始中心點集合Z0中；其余預選中心點按照排序后的順序，依次計算與排序在它之前的數據對象之間的距離，若皆大于2dl則表示該對象可作為初始中心點，將xi添加入Z0中，初始中心點集合Z0表示為：

最終將集合Z0中元素作為初始中心點，集合Z0大小作為類簇個數。

3.3 DACKP算法

改進后的DACKP 算法主要包括聚類中心點預選取，確定中心點和迭代聚類劃分過程3 個步驟，基本步驟描述如下：

輸入：數據集U和近鄰占比pd

輸出：聚類劃分結果C

步驟1根據公式（10）計算任意兩個數據對象之間的距離d(xi,xj),1 ≤i,j≤n。

步驟2根據pd，確定截斷距離dl，根據公式（8）對每個數據對象xi計算其局部密度ρi。

步驟3根據公式（9）對每個數據對象xi計算其高密度距離δi。

步驟4計算δi和ρi的均值μ(δ)和μ(ρ)，并根據公式（11）得到預選初始中心點集合Zp。

步驟5對 ?xi∈Zp，根據公式（12）計算其ηi值，并進行由大到小排序。

步驟6根據公式（13）確定最終初始中心點集合Z0。

步驟7使用相異度度量公式（6）計算每個數據點到各個聚類中心之間的相異度，并把數據集中的樣本逐一分配到最近的類簇中。

步驟8更新聚類中心Z，數值型屬性類中心為該類簇中所有該屬性值的平均值，分類型屬性類中心為類簇中該屬性各屬性值及其出現的頻率。

步驟9重復上述步驟7 和步驟9 的過程，直到目標函數F不再發生變化，即每個數據對象不再改變所屬聚類時算法結束。

通過分析可知，傳統K-Prototypes 算法的時間復雜度為O(nkT)，其中n表示數據對象個數，k表示類簇個數，T表示迭代次數；本文算法的主要計算開銷有：中心點選取的時間復雜度為O(n2)、迭代計算的時間復雜度為O(nkT′)，一般情況下k∈[2,n][17]，T′為改進后算法的迭代次數，根據實驗結果，準確的聚類中心使其值較小T′?n，所以本文算法的時間復雜度為O(n2)。中心點的選取雖然耗時較多，提高了算法的復雜度，但避免了盲目的隨機選點，提高聚類的有效性。

4 實驗結果

為驗證本文提出的算法的有效性，本文使用了人工合成數據集和UCI 機器學習庫中的數據集進行驗證，如表1 所示，本文分別選取了數值屬性數據集、分類屬性數據集和混合屬性數據集。并根據數據集類型，將DACKP 算法分別和K-Means 算法、DPC 算法[16]、FuzzyK-Means（FCM）算法、K-Modes 算法、K-Prototypes（KP）算法、DPCM算法、FuzzyK-Prototypes（FKP）算法進行比較。實驗環境為Intel?Core? i7-4790K CPU @ 4.00 GHz，16 GB內存，操作系統為Microsoft Windows 10。

表1 驗證數據集描述

為了評估聚類算法效果，本文采用的評價指標包括正確率（AC）、類精度（PE）、召回率（RE）和執行劃分步驟的迭代次數（Iter），評價指標定義如下：

其中，n表示的是數據集中對象的總個數，ni表示的是被正確分配到第i個類簇的對象個數，cni表示的是聚類結果中第i個類簇的對象個數，pni表示的是真實標簽中第i個類簇的對象個數。

在對比實驗中，對于隨機初始選點的K-Means、FCM、K-Modes、KP 和FKP 算法，給出正確的聚類個數參數，并采用了100次隨機初始選點，最終統計平均值；KP算法的重要參數γ=分類屬性個數/數值屬性個數[9]；DPCM算法依照原文參數pd=1.5%，給出正確聚類個數，選擇η值最大的數據對象作為初始中心點；DPC和本文算法同樣取pd=1.5%。

數據集R15和D31為人工合成的二維數據集，其聚類結果如圖3、圖4所示，不同顏色代表不同類簇，“*”表示初始中心點。可直觀看出，本文算法可準確地識別出類簇數和初始中心，得到正確的聚類結果。

圖3 本文算法在R15數據集上的聚類結果

圖4 本文算法在D31數據集上的聚類結果

如表2 給出的各算法在數值屬性和分類數據集上的評價結果，對于數值屬性數據集，K-Means 算法對初始選點敏感、DPC 算法對參數也有依賴性，得到的結果并不能代表其最佳水平，FCM算法引入模糊理論，其結果普遍優于K-means 和DPC 算法。本文算法相較K-Means和DPC表現較好，準確率上和FCM幾乎持平，但本文算法迭代次數有明顯的優勢，收斂速度更優。在分類數據集上的實驗結果，本文算法因改進了分類屬性相異度表示和穩定了中心點的選取，達到了良好的聚類效果。

表2 數值屬性和分類屬性數據集實驗結果比較

本文驗證混合屬性數據集聚類效果，結果如表3所示。KP 和FKP 因中心點選擇不穩定，相似度度量方法過于粗糙，導致在各數據集效果皆不佳；DPCM 算法對于非高密度的點會因一個數據對象劃分錯誤，造成連鎖反應，導致準確率低。本文算法在German Credit Data數據集準確率略差，主要是以為該數據集類簇分布比例差異較大，使用導致初始選點不夠準確，但在精準度和召回率上要優于其他算法。在其他數據集上本文算法聚類指標都高于其他算法均能有效的聚類。根據多個混合屬性數據集實驗結果，與傳統KP算法相比，本文算法平均準確率提高了8.52%，與DPCM算法和FKP算法相比，平均準確率分別提高了4.28%和8.33%，且本文算法能保證聚類的穩定性。

表3 混合屬性數據集實驗結果比較

5 結束語

本文提出的DACKP 算法，結合數據對象的密度分布優化了初始聚類中心的選取問題，且可自動地確定類簇數目，另外通過區分每個屬性對聚類結果的不同影響權重，和優化聚類中心的表示方式，改進了相異度計算公式，強化了屬性間的差異性和類內相似性。本文使用人工數據集和UCI 數據集進行驗證，實驗結果表明，改進后的DACKP 算法與其他算法相比，聚類結果的準確率、精準率和召回率都有所提高。但算法對于類簇分布比例差異較大的數據集提升效果并不明顯，如何改善此類數據集的聚類效果和提升算法的時間復雜度是下一步的主要工作。