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

江蘇師范大學(xué) 計(jì)算機(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]只計(jì)算數(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ù)距離度量的方法中，一般使用條件概率分布計(jì)算數(shù)據(jù)屬性間的關(guān)聯(lián)信息，利用信息熵計(jì)算屬性的權(quán)重，比如OF[7]、Goodall[8]等，但是當(dāng)前研究很少考慮到分類型數(shù)據(jù)存在的一個(gè)重要特性——有序特性[9]。事實(shí)上，分類型數(shù)據(jù)的屬性可以進(jìn)一步劃分為有序型屬性和名義型屬性，其中有序是指該屬性的屬性值之間存在順序關(guān)系。例如圖1所示，現(xiàn)實(shí)情況下講師與副教授的差距應(yīng)該小于講師與教授之間的差距，假如對這個(gè)屬性進(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ù)計(jì)算非常復(fù)雜且算法的收斂性較差，很難應(yīng)用在實(shí)際社會(huì)生產(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ùn)用在工業(yè)領(lǐng)域。DPC 根據(jù)密度峰值點(diǎn)確定類中心，并將未分配數(shù)據(jù)分配給比其密度更高且距離其最近的數(shù)據(jù)所在類中，因而算法執(zhí)行快速高效，但是其容易受到鏈?zhǔn)藉e(cuò)誤的影響且不能很好處理密度分布不均問題。共享最近鄰密度峰值聚類算法（shared nearest neighbor density peaks clustering，SNNDPC）[15]通過共享最近鄰和二次分配方式解決了數(shù)值型數(shù)據(jù)的鏈?zhǔn)藉e(cuò)誤和密度不均問題，王大剛等人[16]則利用二階K近鄰及多步驟的分配策略緩解了數(shù)據(jù)的不規(guī)則、密度不均勻問題，此外，丁世飛等人[17]基于度量優(yōu)化，柏鍔湘[18]使用自然最近鄰，趙嘉等人[19]采用相互鄰近度都從一定角度出發(fā)緩解甚至解決了上述問題，但是這些方法都只針對數(shù)值型數(shù)據(jù)，因而簡單地將現(xiàn)有的分類型距離度量引入該算法中，依然無法很好地解決分類型數(shù)據(jù)的聚類問題。其中最主要的原因?yàn)樵诰嚯x度量方面，現(xiàn)有的距離計(jì)算大多會(huì)產(chǎn)生“距離值的重疊問題”，例如圖2（a）所示在擁有24 個(gè)數(shù)據(jù)的Lenses 數(shù)據(jù)集上使用HDM 計(jì)算數(shù)據(jù)之間的距離，結(jié)果產(chǎn)生了大量相同距離結(jié)果值，這往往不利于距離遠(yuǎn)近的比較。在密度計(jì)算方面，上述提出的重疊問題會(huì)進(jìn)一步導(dǎo)致“密度值的聚集問題”，即較多數(shù)據(jù)有相同密度值的情況，例如圖2（b）所示的數(shù)據(jù)在最終分配過程中其周圍數(shù)據(jù)的密度值相同，最終結(jié)果很有可能將該數(shù)據(jù)分配給一個(gè)密度更高但實(shí)際距離較遠(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ì)計(jì)算統(tǒng)一，從而保證了距離值的高區(qū)分度和高信息量。其次通過結(jié)合柯西核函數(shù)[20-21]重新評估密度值，改進(jìn)了SNNDPC 算法中的數(shù)據(jù)密度計(jì)算和二次分配方式，使得算法不僅能夠作用于分類型數(shù)據(jù)，還能有效緩解重疊和聚集問題，提高聚類性能。通過大量的對比實(shí)驗(yàn)和消融實(shí)驗(yàn)證明了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ù)點(diǎn)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}，每個(gè)oj代表aj中數(shù)值的取值集合，oj={oj1,oj2,…,ojc(j)}，其中C(j)表示該屬性中可能取值個(gè)數(shù)，比如“性別”屬性中共有“男”和“女”兩個(gè)可能的屬性取值，C(j)=2。

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

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

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

1.2 距離度量方法

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

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

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

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

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

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

容易驗(yàn)證公式（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ù)的密度計(jì)算仍然會(huì)產(chǎn)生聚集問題，需要一種考慮密度差異的評估方法。

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

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

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

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

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

2.2 聚類算法

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

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

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

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

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

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

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

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

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

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

算法1 CDPCD

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)部分

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

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

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

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

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

3.1 對比實(shí)驗(yàn)

表2、表3和表4給出了各個(gè)算法在數(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í)可以增加數(shù)據(jù)的信息量，提高聚類效果。CDPCD 算法不僅考慮了有序特性，而且統(tǒng)一了特性的同質(zhì)計(jì)算，因此使其在Flare、Dermatology有序特征比例較高的數(shù)據(jù)集上比HDNDW、UDMKM等先進(jìn)的分類型數(shù)據(jù)聚類算法更有競爭力。

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

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

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

3.2 消融實(shí)驗(yàn)

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

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

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

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

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

3.3 其他實(shí)驗(yàn)

3.3.1 時(shí)間對比實(shí)驗(yàn)

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

表6 運(yùn)行時(shí)間實(shí)驗(yàn)結(jié)果Table 6 Running time experiment results

3.3.2 參數(shù)實(shí)驗(yàn)

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

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

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

3.3.3 核函數(shù)實(shí)驗(yàn)

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

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

4 結(jié)束語

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