結合柯西核的分類型數據密度峰值聚類算法

盛錦超，杜明晶，李宇蕊，孫嘉睿

江蘇師范大學 計算機科學與技術學院，江蘇 徐州221100

聚類[1]是一種利用數據自身屬性進行歸類的數據挖掘方法，可以有效處理大量無標注的數據集。聚類過程依賴數據間的距離度量，由于歐式空間的量化性質較好，因此數值型數據一般采用歐氏距離作為度量方法，但這對分類型數據并不適用。分類型數據作為一種常見的離散型數據，數值空間較為復雜。傳統基于劃分的聚類方法[2]在處理分類型數據過程中往往無法得到良好的劃分效果，一方面考慮的距離度量相對簡單，比如K-modes（KM）[3]算法所采用的漢明距離度量（Hamming distance measure，HDM）[4]只計算數據對應屬性的差異程度，忽視了數據屬性的相關性、權重等重要信息；另一方面，基于劃分的聚類方法并不能有效捕捉復雜數據的數值分布，例如在屬性加權K-modes（weightedK-modes，WKM）[5]、混合屬性加權K-modes（mixed weightedKmodes，MWKM）[6]等算法上盡管采用了量化性質更好的距離度量方式，但其聚類效果依然有限。

目前分類型數據距離度量的方法中，一般使用條件概率分布計算數據屬性間的關聯信息，利用信息熵計算屬性的權重，比如OF[7]、Goodall[8]等，但是當前研究很少考慮到分類型數據存在的一個重要特性——有序特性[9]。事實上，分類型數據的屬性可以進一步劃分為有序型屬性和名義型屬性，其中有序是指該屬性的屬性值之間存在順序關系。例如圖1所示，現實情況下講師與副教授的差距應該小于講師與教授之間的差距，假如對這個屬性進行度量，那么其對應關系的信息也應該得到保留，相反，名義型屬性并沒有這種順序關系。EBDM-KM[10]是一種使用信息熵對有序特性進行度量的分類型數據聚類算法，該算法從一定程度上提高了聚類效果。HDNDW[11]同樣考慮了數據屬性的有序特性，并且該算法將名義型屬性轉換為有序型屬性，統一了分類型數據的內在特性，盡管該算法的聚類表現較好，但是其內部參數計算非常復雜且算法的收斂性較差，很難應用在實際社會生產中。UDMKM[12]進一步提出了利用熵整合屬性關聯、權重和有序的距離度量方法，但其聚類手段仍局限于傳統劃分方法，聚類性能提升有限。

圖1 職稱關系Fig.1 Title relationships

密度峰值聚類（density peaks clustering，DPC）[13]算法是一種有效應對復雜數據分布的密度聚類算法[14]，已經廣泛運用在工業領域。DPC 根據密度峰值點確定類中心，并將未分配數據分配給比其密度更高且距離其最近的數據所在類中，因而算法執行快速高效，但是其容易受到鏈式錯誤的影響且不能很好處理密度分布不均問題。共享最近鄰密度峰值聚類算法（shared nearest neighbor density peaks clustering，SNNDPC）[15]通過共享最近鄰和二次分配方式解決了數值型數據的鏈式錯誤和密度不均問題，王大剛等人[16]則利用二階K近鄰及多步驟的分配策略緩解了數據的不規則、密度不均勻問題，此外，丁世飛等人[17]基于度量優化，柏鍔湘[18]使用自然最近鄰，趙嘉等人[19]采用相互鄰近度都從一定角度出發緩解甚至解決了上述問題，但是這些方法都只針對數值型數據，因而簡單地將現有的分類型距離度量引入該算法中，依然無法很好地解決分類型數據的聚類問題。其中最主要的原因為在距離度量方面，現有的距離計算大多會產生“距離值的重疊問題”，例如圖2（a）所示在擁有24 個數據的Lenses 數據集上使用HDM 計算數據之間的距離，結果產生了大量相同距離結果值，這往往不利于距離遠近的比較。在密度計算方面，上述提出的重疊問題會進一步導致“密度值的聚集問題”，即較多數據有相同密度值的情況，例如圖2（b）所示的數據在最終分配過程中其周圍數據的密度值相同，最終結果很有可能將該數據分配給一個密度更高但實際距離較遠的類中，導致最終的聚類結果變差。

圖2 分類型數據在DPC上存在的問題Fig.2 Problems of categorical data on DPC algorithm

考慮到這些問題，本文提出一種改進的結合柯西核的分類型數據密度峰值聚類算法（Cauchy kernel-based density peaks clustering algorithm for categorical data，CDPCD）。算法首先提出了一種新的基于概率分布的加權有序距離度量方法，該方法充分考慮了分類型數據的屬性相關性、屬性權重和有序特性，并將有序型屬性和名義型屬性進行了同質計算統一，從而保證了距離值的高區分度和高信息量。其次通過結合柯西核函數[20-21]重新評估密度值，改進了SNNDPC 算法中的數據密度計算和二次分配方式，使得算法不僅能夠作用于分類型數據，還能有效緩解重疊和聚集問題，提高聚類性能。通過大量的對比實驗和消融實驗證明了CDPCD算法的有效性，CDPCD 也成為了當前鮮有的面向分類型數據的密度峰值聚類算法。

1 基于概率分布的加權有序距離度量

1.1 相關定義和特性統一

本節首先給出相關定義：設xij為數據集合X中數據點xi關于屬性aj的屬性值，其中1 ≤i≤n,1 ≤j≤m。設Ao為有序型屬性集合，An為名義型屬性集合，則Ao?An=A。為了方便后續公式說明，設O為數據的屬性值集合，O={o1,o2,…,om}，每個oj代表aj中數值的取值集合，oj={oj1,oj2,…,ojc(j)}，其中C(j)表示該屬性中可能取值個數，比如“性別”屬性中共有“男”和“女”兩個可能的屬性取值，C(j)=2。

觀察圖3的分類型數據屬性劃分，從信息量層面可以認為有序型屬性所提供的信息是同一內容的不同程度，而名義型屬性則更側重不同內容的信息，因此考慮屬性的關聯計算時難免會產生非同質的錯誤，為了避免這個問題，有必要將特性進行統一。有序型屬性轉變為名義型屬性時會損失順序信息，因此本文選擇將名義型屬性轉換為有序型屬性。轉化方法的基本思想如圖4所示，通過集合變換將名義型屬性的每個可能取值轉換為一個具有兩個邏輯值的有序集合，兩個邏輯值分別代表是否為當前可能取值的兩種極端情況，例如“寵物”屬性值中存在“貓”“狗”和“其他”三個取值，這三個取值被轉換為三個“新”集合，“貓”“狗”“其他”，其中“貓”集合包含了兩個極端值：是（用1 表示）、否（用0 表示），同理“狗”和“其他”也包含這兩個極端值。通過集合變換，名義型屬性所產生的屬性集合可以被視為由多個有序型屬性所組成，如上述“寵物”屬性可視為由三個有序型屬性組成的集合，于是可以將這個集合利用平均值等統計特征與原有的有序型屬性進行計算。基于這種思想，有序型屬性和名義型屬性完成了同質計算統一，下節將利用這種方式輔助距離計算。

圖3 分類型數據屬性劃分Fig.3 Categorical data attribute division

圖4 名義特性變換Fig.4 Nominal feature transformation

1.2 距離度量方法

本節將提出一個全新且完整的分類型數據距離度量，包括屬性關聯、權重及有序特性所反映的順序關系。其中屬性關聯利用條件概率分布[22]實現，屬性加權使用信息熵[10，12]，而順序關系則考慮屬性值之間轉換的最小移動花費代價[23]。

在屬性ar的屬性值為orm條件下屬性as的屬性值為osp的條件概率如公式（1）所示：

其中{xi|xir=orm}和{xi|xis=osp}分別代表了數據點xi的ar和as的屬性值為orm和osp的數據集合，count()函數用于統計數據集合中數據的個數。通過公式（1），ar關于as所有屬性值取值的條件概率分布可以用公式（2）所示的列表表示：

傳統利用L1或L2范式的方法計算條件概率分布會容易損失順序關系的信息，例如在計算U1=[1,0,0,0],U2=[0,1,0,0],U3=[0,0,0,1]三個分布的過程中，最終得到了‖U1-U2‖1=‖U1-U3‖1=‖U1-U2‖2=‖U1-U3‖2的結果，這與有序型屬性的距離關系不符，顯然第一與第二可能值之間應該比第一與第四可能值之間距離更近。本文使用了一種類似推土機算法[23]的計算方法保留了該關系，如公式（3）所示：

其中，在計算過程中使用均值完成特性的同質計算，與1.1 節對應，同時出于數據屬性本身的特性要求，當ar∈Ao時再次考慮了順序關系。

上述討論假設數據屬性的權重一致，但實際情況中由于不同屬性值的分布不同，每個屬性對距離的貢獻是不同的，因此有必要對屬性進行加權。信息熵是一種度量權重的方法，使用信息熵對屬性進行加權能夠很好地衡量隨機變量的不確定度，尤其是離散型隨機變量，因而適合分類型數據的離散分布特征[12]。信息熵的公式如式（6）、（7）所示：

容易驗證公式（8）符合以下距離性質，是一種距離度量方法。

圖5 展示了使用HDM、OF、Goodall 和本文提出的距離度量在Lenses數據集上的距離值集合，可以看到本文方法得到了更多的距離差異，保證了距離值的高區分度和高信息量，有效降低了重疊問題。

圖5 距離度量結果Fig.5 Distance measurement results

2 結合柯西核函數的聚類算法

2.1 柯西核函數

盡管提出的距離度量增加了距離差異，但是分類型數據的密度計算仍然會產生聚集問題，需要一種考慮密度差異的評估方法。

核函數方法[21]能在密度計算的過程中考慮到更多數據對待評估數據的影響，比如常見的高斯核，但是高斯核的密度計算快速衰減特性使其容易忽視某些較遠鄰居的貢獻。根據分類型數據相對分散的分布特點，這樣的結果反而不利于區分密集區域的密度峰值點。相反如圖6 所示，柯西核函數擁有更長的函數尾特征，因而空間中處于不同方向的密度峰值點會擴大考慮不同的較遠數據的影響，從而更有利于數據密度計算結果的多樣性。與此同時，柯西核函數的特性使其沒有降低原先密集區域對密度計算的貢獻，例如圖7（a）、（b）所示經過排序后的Lenses數據集和Post數據集密度值圖中，更平滑的藍色點表示用柯西核計算出的密度值，而綠色點則使用了高斯核，可以看到綠色點區域中的密度值仍較為聚集，而藍色點區分度較好，呈現出一個良好的上升趨勢，有助于緩解聚集問題。

圖6 高斯函數和柯西函數Fig.6 Gaussian function and Cauchy function

圖7 數據集密度排序圖Fig.7 Density sorting diagram of dataset

柯西核函數的另一個優勢是運算方法簡單，計算速度快。綜上選擇柯西核函數作為密度評估方法具有合理性和有效性。

兩個數據結合柯西核函數的計算公式如式（13）所示，其中υi是關于n的超參數，本文使用xi與距離xi第K近的數據之間的距離作為υi。

2.2 聚類算法

本節將介紹提出的CDPCD 算法，出于算法描述考慮，首先簡要介紹原始算法（SNNDPC）的共享最近鄰、相似度矩陣和二次分配方式[15]。

共享最近鄰是指兩個數據最近K個數據點中相同數據點的集合，記為SNN(xi,xj)=Γ(xi)?Γ(xj),其中Γ(xi)表示距離xi最近的K個數據點集合。

相似度矩陣是一個n維方陣，方陣中的值表示對應數據之間的局部相似度，計算過程如公式（14）所示：

二次分配方式將數據按照密度比例劃分為不可避免從屬點和可能從屬點兩類，并在劃分過程中對數據進行相應的二輪分配，其中第一輪分配通過劃分依據將不可避免從屬點進行歸類，第二輪分配則通過循環統計可能從屬點最近鄰中已分配數據的歸屬進行歸類。

在密度計算上，CDPCD 定義的相似度矩陣在公式（14）的基礎上結合了柯西核函數，基于的改進思想與2.1節對應，如公式（15）。同時關于計算數據xi密度峰值參數的和如公式（16）和公式（17）所示，其中在計算的過程中同樣結合了柯西核函數。

在分配方式上，CDPCD 保留了從屬點的命名及二次分配基本流程，但是劃分依據和分配過程不同。其中劃分依據方面，原始算法僅考慮數據之間共享一半數據點就劃分為不可避免從屬點，因此算法容易受到參數K的影響，過少或過多的K都會降低算法性能。此外分類型數據的數值分布在多數情況下會出現部分數據點集中但又與其他同類數據點分散的問題，如圖8 所示，同一個類中出現了兩個集中的數據組，甚至有些數據是重疊的（圖中放大部分），因此重疊部分的數據點很可能由于共享最近鄰重合導致無法被劃分為不可避免從屬點，最終產生兩個后果，其一是在第二輪分配過程中被分配，從而產生一定的花費，其二是最終因為遺漏進而降低算法性能。CDPCD 考慮K與柯西核函數結合計算出的距離值并根據已分配數據點的最近鄰平均距離值將數據進行劃分，如定義1所示。這種劃分依據會依靠數據本身最近鄰點分布產生的均值作為閾值，這種閾值會保留相近點和重疊點，同時過濾遠處的數據點，因而會盡可能將數據組合并，到達預期效果。與此同時CDPCD的劃分依據會因為柯西核函數的加入而降低對K的敏感度，有利于算法的穩定。

圖8 分類型數據存在的分布問題Fig.8 Distribution problems with categorical data

分配過程方面，原始算法在第二輪分配過程中會出現兩個問題，即重復統計某一個已分配數據點和可能從屬點出現多次統計最近鄰數據點所屬類卻未被分配的情況，為了避免這兩個問題，CDPCD在第二輪分配過程中通過考慮柯西核函數計算出的密度值影響，將可能從屬點依照公式（13）計算出的距離值升序排序，并使用循環依次將可能從屬點xi分配到Γ(xi)中距離最近的數據所在類中，在最近鄰數據都未分配情況下將搜索空間變為整個數據集。這種分配過程使得每個可能從屬點只計算一次就進行分配，從而能夠有效解決重復統計卻未被分配問題，加快第二輪的分配速度，同時基于出現就分配的原則，改進的分配方式也不會出現重復統計已分配數據點的情況。3.3.1 小節將通過實驗證明分配過程在有效提速的同時并沒有損失聚類效果的結論。

圖9 給出了CDPCD 算法的流程示意圖，其算法步驟如下所示：

圖9 算法流程示意圖Fig.9 Algorithm flow diagram

算法1 CDPCD

輸入：數據集X,參數K。

輸出：聚類結果R。

步驟1 根據公式（8）計算X中任意兩個數據之間的距離。

步驟2 根據公式（16）與公式（17）計算數據的ρxi和δxi。

步驟3 通過決策圖選取密度峰值點，對數據進行第一輪分配，根據定義1將不同密度峰值點的不可避免從屬點歸類。

步驟4 對標記的可能從屬點進行第二輪分配，計算可能從屬點結合柯西核函數的距離值，并升序排列；從隊列中選取每個數據，按照最近鄰原則分配，如果最近鄰集合中數據均未分配，則分配到距離最近的當前已經分配的數據所在類中。

步驟5 記錄數據分配結果，返回R。

算法1的時間復雜度主要在步驟1和步驟2上。步驟1中的距離度量主要取決C(j)的最大值，如果假設為q，則計算兩個數據距離的時間復雜度為O(mq2)，整個數據集的距離計算復雜度為O(mq2n2)。步驟2 中柯西核函數產生的計算為線性運算，故不存在多余運算代價，因此時間復雜度僅與K、m和n三個參數有關，為O((K+m)n2)。步驟3 和步驟4 的計算依賴步驟1 和步驟2，因此復雜度為O(1)，故算法1 的總時間復雜度為O((mq2+K+m)n2)。與SNNDPC的O((K+m)n2)時間復雜度相比較，算法1中的mq2絕大部分情況下會遠小于n2即屬性值取值個數遠小于數據量，因此算法1 和SNNDPC 的時間復雜度在數量級上是一致的，由于二次分配的優化，算法1在處理分類型數據集上會有額外增速優勢。與K-modes 的O(E(kmn)) 時間復雜度和HDNDW 的O(E(kmqn+mn+mq2k))時間復雜度（注意這里的E為迭代次數，k為真實標簽值）等劃分聚類方法相比，算法1 不會受到隨機結果影響，并且可以將距離計算和聚類過程分離，具有更好的靈活性。

3 實驗部分

本文選用了表1 所示的15 組UCI 公開真實數據[11]作為進行各種實驗的基本數據集，其中表1 的Attribute列定義為有序型屬性列+名義型屬性列。

表1 實驗數據集Table 1 Experimental data sets

實驗使用KM[3]、WKM[5]、MWKM[6]、EBDM-KM[10]、HDNDW[11]、UDMKM[12]與DPC[13]作為對比算法進行對比。按照文獻及對比實驗要求，KM、WKM、MWKM 和DPC使用HDM作為距離度量。此外，為了驗證提出的距離度量以及柯西核函數方法在聚類上的有效性和重要性，在SNNDPC[15]和CDPCD 算法基礎上增加了相應的消融實驗。最后就CDPCD算法在劃分依據和分配過程的時間提速方面進行了驗證，并針對參數K對算法的影響和柯西函數相較于其他核函數的優勢進行了實驗。

本文參考的聚類評價指標[24-25]分別為標準化互信息NMI、調整蘭德系數ARI 和福克斯馬洛斯指數FMI，其中NMI 和FMI 的取值范圍是[0，1]，ARI 的取值范圍是[-1,1]，三個指標的數值越大，聚類的效果越好。

本文使用的編程環境為Matlab2021b 和Python3.6。算法的參數設置方面，KM、WKM、MWKM、EBDM-KM、UDMKM和HDNDW使用數據集的真實類別數目，由于這些方法具有隨機性，因此會隨機實驗50 次取平均值作為最終結果；DPC算法的閾值參數設置為2%；其余算法存在最近鄰參數K，本文選擇重復實驗并取NMI 最優結果值，K的最終設置范圍在2～40。

3.1 對比實驗

表2、表3和表4給出了各個算法在數據集上取得的聚類效果。

表2 NMI結果Table 2 NMI result

表3 ARI結果Table 3 ARI result

表4 FMI結果Table 4 FMI result

從表中可見在有序和名義特性都存在的數據集上（例如Lym、Flare等），進一步考慮有序特性的EBDM-KM、HDNDW 和UDMKM 算法比傳統基于劃分的MWKM、WKM 和KM 算法的聚類表現要好，這說明數據屬性的進一步劃分確實可以增加數據的信息量，提高聚類效果。CDPCD 算法不僅考慮了有序特性，而且統一了特性的同質計算，因此使其在Flare、Dermatology有序特征比例較高的數據集上比HDNDW、UDMKM等先進的分類型數據聚類算法更有競爭力。

在Soybean、Zoo等純名義型屬性的數據集上，CDPCD通過將名義特性轉化為有序特性的手段，增加了距離信息量，緩解了距離度量的重疊問題，因而同樣取得了較好的聚類結果。在純有序型屬性的數據集上，CDPCD通過密度值計算結果的多樣性有效降低了聚集問題并減少了錯誤分配，從而更好地處理了基于劃分算法不能有效捕捉復雜分布的問題，使得算法的性能更強。

與DPC 的對比結果中CDPCD 展示了其作為密度聚類算法卻能夠克服數據的距離值重疊問題和密度值聚集問題從而對分類型數據進行聚類的可能性和有效

性，CDPCD 通過新的距離度量和結合柯西核函數的方法讓密度值的計算更符合分類型數據的需要，比如具有較高區分度的密度多樣性等特征，這也為分類型數據的密度聚類方法提供了全新的解決思路。

3.2 消融實驗

本節將通過消融實驗進一步驗證提出的基于概率分布的加權有序距離度量和結合柯西核函數方法計算密度值的重要性和有效性。實驗使用SNNDPC和CDPCD作為兩個基礎算法，通過“控制變量”手段令SNNDPC 算法的距離度量使用本文提出的方法，并將方法記作CSNNDPC；CDPCD 算法的距離度量改為使用HDM、OF 和Goodall，分別記作CDPCD（HDM）、CDPCD（OF）和CDPCD（Goodall）。

表5給出了最終的聚類指標結果，其中每條數據集的指標結果的下一行Δ（%）表示CDPCD 與每個通過“控制變量”驗證的算法在該數據集上對應指標的提高比，例如CDPCD 在Primary 數據集上相較于CSNNDPC的NMI 提高0.567 即56.7%。表5 的最后兩行Avg 和AvgΔ（%）分別表示各個驗證算法在所有數據集上的單一指標平均值和CDPCD相較于所有驗證算法的單一指標在所有數據集上的平均提高比，例如CDPCD 在所有的數據集上相較于CSNNDPC的NMI平均提高0.642即64.2%。

表5 聚類結果Table 5 Clustering results

圖10給出了三個聚類評價指標在各個驗證算法和CDPCD算法上所有數據集上平均值的可視化結果。結果可見各個驗證算法均沒有達到CDPCD的平均聚類效果，CSNNDPC在缺少了柯西核函數增強密度多樣性的效果后，其聚類效果明顯降低。正如2.1節所述，柯西核函數提供的平滑、有差別的密度值計算結果能夠很好地區分不同數據對所屬類的貢獻差別。此外這種密度多樣性的特征不僅僅體現在解決密度計算聚集問題的柯西核函數上，由于密度計算依賴距離度量，三個控制距離度量方法的算法得到的聚類結果較差，說明了提出的距離度量方法在后續計算數據密度值和進行聚類的過程中起到了關鍵作用，尤其在純有序型的數據集上NMI和ARI的結果平均下降非常大，證明缺少了有序特性的距離度量方法后，聚類算法會在運行過程中損失許多有用的順序信息，導致性能變差。

圖10 驗證算法和CDPCD在數據集上的平均聚類效果Fig.10 Average clustering effect of validation algorithm and CDPCD on dataset

3.3 其他實驗

3.3.1 時間對比實驗

本小節將對2.2節中算法1的分配過程加速且不損失算法性能的結論進行實驗驗證，為了更好對比實驗結果，選擇Wisconsin、Tic、Lecturer、Social 和Car 五個較大的數據集進行實驗，并將兩個算法的參數K設置為相同值，最后統計聚類指標NMI和運行時間Time。表6給出了最終的結果，其中每個數據集分別對原始算法（Mode 列標為original）和改進的算法（Mode 列標為now）進行實驗。從表中可見，相較于原始算法，CDPDC在基本不損失聚類性能的前提下均有一定的提速，說明該分配方式更加符合分類型數據的特點，能夠提高運行速度，同時在大多數數據集上NMI 指標得到了提高也側面說明了算法改進能夠提高一定的聚類性能。

表6 運行時間實驗結果Table 6 Running time experiment results

3.3.2 參數實驗

CDPCD算法的執行需要參數K，本小節通過簡要舉例分析該參數對聚類結果的影響。

如圖11，在Zoo 和Dermatology 數據集上設置參數K的范圍為[5，40]并運行算法統計其NMI，可以發現指標隨著K的增加而上升，并逐步達到最大值，隨后下降。同時在最大值參數K附近的指標差值較小，說明該參數還具有一定的魯棒性。

圖11 參數K 對聚類結果NMI的影響Fig.11 Effect of parameter K on clustering result NMI

3.3.3 核函數實驗

本小節對柯西核函數的有效性進行驗證，實驗選取有序型+名義型、純有序型和純名義型的若干數據集并使用目前常見考慮數據之間距離的高斯核（GK）、二次有理核（RQK）和冪指數核（EK）進行比較。表7給出了最終結果，其中表中的最后列為柯西核（CK），可以看到由于缺乏重尾核函數提供的平滑密度值過渡特性，這些對比核函數不能夠為分類型數據提供符合其數值分布的良好空間特點，因此聚類性能較差。

表7 核函數對比實驗結果Table 7 Kernel function comparison experimental results

4 結束語

本文提出了結合柯西核的分類型數據密度峰值聚類算法。算法首先針對密度聚類中距離計算產生的重疊問題，提出了一種全新的基于概率分布的加權有序距離度量來增強距離計算的高區分度和高信息量。然后針對密度計算產生的聚集問題，使用了一種結合柯西核函數的密度估計方法重新計算數據局部密度值，同時改進了SNNDPC 算法的劃分依據和二次分配過程。實驗證明本算法顯著提高了分類型數據的聚類效果，但是本算法在處理高維分類型數據集下存在計算量較大的問題，如何有效降低計算消耗將是下一步研究的重點方向。