結(jié)合柯西核的分類型數(shù)據(jù)密度峰值聚類算法

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

江蘇師范大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州221100

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

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

圖1 職稱關(guān)系Fig.1 Title relationships

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

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

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

1 基于概率分布的加權(quán)有序距離度量

1.1 相關(guān)定義和特性統(tǒng)一

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

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

圖3 分類型數(shù)據(jù)屬性劃分Fig.3 Categorical data attribute division

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

1.2 距離度量方法

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

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

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

傳統(tǒng)利用L1或L2范式的方法計算條件概率分布會容易損失順序關(guān)系的信息，例如在計算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的結(jié)果，這與有序型屬性的距離關(guān)系不符，顯然第一與第二可能值之間應(yīng)該比第一與第四可能值之間距離更近。本文使用了一種類似推土機(jī)算法[23]的計算方法保留了該關(guān)系，如公式（3）所示：

其中，在計算過程中使用均值完成特性的同質(zhì)計算，與1.1 節(jié)對應(yīng)，同時出于數(shù)據(jù)屬性本身的特性要求，當(dāng)ar∈Ao時再次考慮了順序關(guān)系。

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

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

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

圖5 距離度量結(jié)果Fig.5 Distance measurement results

2 結(jié)合柯西核函數(shù)的聚類算法

2.1 柯西核函數(shù)

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

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

圖6 高斯函數(shù)和柯西函數(shù)Fig.6 Gaussian function and Cauchy function

圖7 數(shù)據(jù)集密度排序圖Fig.7 Density sorting diagram of dataset

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

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

2.2 聚類算法

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

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

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

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

在密度計算上，CDPCD 定義的相似度矩陣在公式（14）的基礎(chǔ)上結(jié)合了柯西核函數(shù)，基于的改進(jìn)思想與2.1節(jié)對應(yīng)，如公式（15）。同時關(guān)于計算數(shù)據(jù)xi密度峰值參數(shù)的和如公式（16）和公式（17）所示，其中在計算的過程中同樣結(jié)合了柯西核函數(shù)。

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

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

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

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

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

算法1 CDPCD

輸入：數(shù)據(jù)集X,參數(shù)K。

輸出：聚類結(jié)果R。

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

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

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

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

步驟5 記錄數(shù)據(jù)分配結(jié)果，返回R。

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

3 實驗部分

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

表1 實驗數(shù)據(jù)集Table 1 Experimental data sets

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

本文參考的聚類評價指標(biāo)[24-25]分別為標(biāo)準(zhǔn)化互信息NMI、調(diào)整蘭德系數(shù)ARI 和?？怂柜R洛斯指數(shù)FMI，其中NMI 和FMI 的取值范圍是[0，1]，ARI 的取值范圍是[-1,1]，三個指標(biāo)的數(shù)值越大，聚類的效果越好。

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

3.1 對比實驗

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

表2 NMI結(jié)果Table 2 NMI result

表3 ARI結(jié)果Table 3 ARI result

表4 FMI結(jié)果Table 4 FMI result

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

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

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

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

3.2 消融實驗

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

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

表5 聚類結(jié)果Table 5 Clustering results

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

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

3.3 其他實驗

3.3.1 時間對比實驗

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

表6 運行時間實驗結(jié)果Table 6 Running time experiment results

3.3.2 參數(shù)實驗

CDPCD算法的執(zhí)行需要參數(shù)K，本小節(jié)通過簡要舉例分析該參數(shù)對聚類結(jié)果的影響。

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

圖11 參數(shù)K 對聚類結(jié)果NMI的影響Fig.11 Effect of parameter K on clustering result NMI

3.3.3 核函數(shù)實驗

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

表7 核函數(shù)對比實驗結(jié)果Table 7 Kernel function comparison experimental results

4 結(jié)束語

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