基于密度峰值的混合型數(shù)據(jù)聚類算法設(shè)計(jì)

李　曄，陳奕延，張淑芬

(1.中國(guó)市場(chǎng)學(xué)會(huì) 服務(wù)質(zhì)量專業(yè)委員會(huì)，北京 100048；　2.河北省數(shù)據(jù)科學(xué)與應(yīng)用重點(diǎn)實(shí)驗(yàn)室(華北理工大學(xué))，河北 唐山 063210)(*通信作者電子郵箱townjam_sovietnia@163.com)

0　引言

隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，人們采集與獲取信息的能力大大提高。當(dāng)海量信息出現(xiàn)時(shí)，人們希望從繁多復(fù)雜的數(shù)據(jù)中得到有價(jià)值的信息。聚類分析是數(shù)據(jù)挖掘中一個(gè)極其重要的分支。文獻(xiàn)[1]指出聚類是一個(gè)把數(shù)據(jù)對(duì)象劃分成子集的過(guò)程，每個(gè)子集是一個(gè)簇，使得簇中的對(duì)象彼此相似，但與其他簇中的對(duì)象不相似。

根據(jù)數(shù)據(jù)對(duì)象(數(shù)據(jù)點(diǎn))每個(gè)屬性值的數(shù)據(jù)類型，可把數(shù)據(jù)分為數(shù)值型數(shù)據(jù)、分類型數(shù)據(jù)(無(wú)序分類變量構(gòu)成的數(shù)據(jù))及混合型數(shù)據(jù)。很多科研工作者為保證數(shù)據(jù)分析的普適性和全面性，采用的調(diào)查數(shù)據(jù)大多為既含數(shù)值型屬性又含分類型屬性的混合型數(shù)據(jù)。由于面對(duì)的數(shù)據(jù)類型日益多樣化，聚類分析也需要處理不同類型的數(shù)據(jù)，然而目前的聚類算法大多是針對(duì)數(shù)值型數(shù)據(jù)提出的，也有一部分可用來(lái)處理分類型數(shù)據(jù)，但能夠處理混合型數(shù)據(jù)的聚類算法卻相對(duì)較少。文獻(xiàn)[2]指出這兩種屬性在屬性值的取值范圍、分布和特點(diǎn)上差異較大，許多研究人員認(rèn)為針對(duì)單一屬性數(shù)據(jù)的傳統(tǒng)聚類算法已不適用于混合屬性數(shù)據(jù)。因此，設(shè)計(jì)更多針對(duì)混合型數(shù)據(jù)的聚類算法是聚類分析中一項(xiàng)極具意義的工作。

最早用于混合型數(shù)據(jù)的聚類算法是k-prototypes算法[3],該算法結(jié)合了k-means和k-modes兩種方法，故而不像很多傳統(tǒng)的聚類算法一樣只能處理單一屬性的數(shù)據(jù)集。另外，該算法具備了k-means算法高效性的特點(diǎn)，應(yīng)用十分廣泛，尤其是對(duì)于大型數(shù)據(jù)集也十分有效。雖然k-prototypes算法有很多優(yōu)點(diǎn)且被人們廣泛使用，但仍存在以下一些不足：1)無(wú)法實(shí)現(xiàn)對(duì)數(shù)據(jù)分布的適應(yīng)性。對(duì)于簇中的數(shù)值部分，k-prototypes算法同k-means算法一樣只能發(fā)現(xiàn)球狀分布的簇。2)無(wú)法自動(dòng)確定簇的個(gè)數(shù)。3)沒(méi)有考慮聚類過(guò)程中的模糊性問(wèn)題。很多情況下，數(shù)據(jù)對(duì)象很可能同時(shí)分屬多個(gè)簇，有時(shí)簇邊界附近的數(shù)據(jù)對(duì)象的歸屬問(wèn)題會(huì)很模糊，而k-prototypes算法并未考慮這一點(diǎn)。4)對(duì)混合屬性數(shù)據(jù)簇原型(中心)的表示可能造成嚴(yán)重的信息丟失。5)沒(méi)有考慮每個(gè)屬性對(duì)聚類結(jié)果影響的差異性。6)受初始值的影響很大。由于k-prototypes算法是一種迭代算法，只能收斂于局部最優(yōu)解，因此對(duì)初值的選取十分敏感。

近年來(lái)有不少研究者紛紛對(duì)上述缺點(diǎn)進(jìn)行了不同程度的改進(jìn)。針對(duì)缺點(diǎn)3)：文獻(xiàn)[4]在k-prototypes算法的基礎(chǔ)上提出了fuzzyk-prototypes聚類算法，通過(guò)在k-prototypes算法中引入模糊理論的概念，增加了數(shù)據(jù)對(duì)象分配到簇原型時(shí)的不確定性，使改進(jìn)的算法具有分析模糊性和不確定性問(wèn)題的能力；文獻(xiàn)[5]中則認(rèn)為常用于混合型數(shù)據(jù)模糊聚類的fuzzyk-prototypes算法僅僅是在原始的模糊C均值(Fuzzy C-Means, FCM)聚類算法中使用了不同的相異性函數(shù)，從而使其可用于同時(shí)具有數(shù)值型屬性和分類型屬性的混合型數(shù)據(jù)，于是該文中提出了一個(gè)全新的FCM-type算法，采用全概率相異性函數(shù)來(lái)處理混合屬性數(shù)據(jù)，通過(guò)交叉熵使得模糊目標(biāo)函數(shù)正則化，最終達(dá)到提高聚類精度的目的。針對(duì)缺點(diǎn)4)，文獻(xiàn)[6]提出了fuzzyk-prototypes聚類算法的一種改進(jìn)算法，該算法改進(jìn)了簇原型的選取方式，對(duì)每個(gè)有p種不同取值的分類型屬性，將其看成是一個(gè)p維的屬性，迭代過(guò)程中原型的計(jì)算也要將每個(gè)分類型屬性看成一個(gè)p維的屬性，按每個(gè)分類型屬性的可能取值在所屬簇中的比例來(lái)定義簇原型，從而也間接改變了分類型屬性的相異性度量方式。這樣的原型選取方式包含了更多的數(shù)據(jù)信息，從而提高了聚類的精度。針對(duì)缺點(diǎn)5):文獻(xiàn)[7]提出了基于聚類相似性的算法——SBAC算法，它是一個(gè)凝聚層次聚類算法，引入了一個(gè)相似度的度量方式來(lái)計(jì)算數(shù)據(jù)對(duì)象間的相似性；文獻(xiàn)[8]提出了基于熵權(quán)法的針對(duì)混合屬性數(shù)據(jù)的聚類算法，改進(jìn)了數(shù)據(jù)對(duì)象之間距離的度量方式，利用信息熵作為各個(gè)屬性的權(quán)值，從而提高了聚類的精度和穩(wěn)定性；文獻(xiàn)[9]中利用類內(nèi)和類間信息熵來(lái)度量各個(gè)屬性在聚類過(guò)程中的作用，由此給不同的屬性分配不同的權(quán)重，從而使得數(shù)據(jù)對(duì)象可以在統(tǒng)一的框架下更客觀地度量彼此之間以及對(duì)象與簇原型之間的相異性。針對(duì)缺點(diǎn)6)，文獻(xiàn)[10]對(duì)k-prototypes聚類算法初始點(diǎn)選取方法作了改進(jìn)，通過(guò)對(duì)模糊k-prototypes的分析，分別對(duì)數(shù)值型屬性部分和分類型屬性部分進(jìn)行劃分，在每個(gè)劃分中選取初值，最后將兩部分和在一起組成初始的簇原型。該方法降低了數(shù)據(jù)對(duì)初值的敏感度，從而減少了聚類算法的迭代次數(shù)，同時(shí)還能避免選取到相同的初始簇原型。

雖然目前國(guó)內(nèi)外針對(duì)缺點(diǎn)3)～6)有諸多改進(jìn)，但卻鮮有針對(duì)缺點(diǎn)1)和2)的改進(jìn)算法，故本文主要針對(duì)這兩個(gè)不足之處提出一種可用于混合型數(shù)據(jù)的新型聚類算法。2014年，文獻(xiàn)[11]提出一種用于數(shù)值型數(shù)據(jù)的CFSFDP(Clustering by Fast Search and Find of Density Peaks)聚類算法，該算法具有能發(fā)現(xiàn)任意形狀數(shù)據(jù)集且能自動(dòng)確定簇?cái)?shù)的優(yōu)點(diǎn),但使用范圍局限于數(shù)值型數(shù)據(jù)。之后文獻(xiàn)[12]進(jìn)行了基于CFSFDP算法的模糊聚類研究；文獻(xiàn)[13]提出了基于近鄰距離曲線和類合并優(yōu)化CFSFDP的聚類算法；文獻(xiàn)[14]提出一種基于簇中心點(diǎn)自動(dòng)選擇策略的密度峰值聚類算法；文獻(xiàn)[15]提出一種基于粒子群算法的CFSFDP算法。這些改進(jìn)雖然提高了CFSFDP算法的性能，但仍然不能用于混合型數(shù)據(jù)的聚類。

因此，本文首先重新定義了混合型數(shù)據(jù)之間的距離，接著把CFSFDP算法擴(kuò)展到混合型數(shù)據(jù)，這樣可以克服k-prototypes算法相應(yīng)的1)、2)兩個(gè)缺點(diǎn)，使得該算法能夠自動(dòng)確定簇?cái)?shù)，并且對(duì)于任意形狀的簇都有一個(gè)比較滿意的聚類效果。接著對(duì)算法復(fù)雜度進(jìn)行分析，并且研究了算法中的閾值dc及權(quán)值γ的選取問(wèn)題，分別利用數(shù)據(jù)場(chǎng)中的勢(shì)熵和可度量數(shù)值型及分類型數(shù)據(jù)集聚類趨勢(shì)的統(tǒng)計(jì)量來(lái)確定這兩個(gè)參數(shù)。最后用文獻(xiàn)[16]中的三個(gè)混合型數(shù)據(jù)集作為實(shí)驗(yàn)對(duì)象，通過(guò)和k-prototypes算法的比較來(lái)驗(yàn)證針對(duì)混合型數(shù)據(jù)的尋找密度峰值算法的有效性。

1　尋找密度峰值的聚類算法

本文把CFSFDP算法擴(kuò)展到混合型數(shù)據(jù)，提出一種可用于混合型數(shù)據(jù)的尋找密度峰值聚類算法，該算法的基本思想是簇中心應(yīng)該同時(shí)滿足以下兩點(diǎn)：1)簇中心的密度比它周圍的點(diǎn)的密度更大；2)簇中心離比自身密度大的點(diǎn)的距離較遠(yuǎn)，即不同的簇中心之間的距離相對(duì)較遠(yuǎn)。

該想法是整個(gè)聚類過(guò)程的基礎(chǔ)，找到簇中心以后，也就自動(dòng)確定了簇的個(gè)數(shù)。對(duì)于任意一個(gè)非簇中心數(shù)據(jù)點(diǎn)i，認(rèn)為點(diǎn)i跟所有比它密度更大的點(diǎn)中與之距離最近的那個(gè)點(diǎn)屬于同一個(gè)簇。該算法中簇的分配在一步中完成，這與那些通過(guò)迭代來(lái)優(yōu)化目標(biāo)函數(shù)的算法是不同的。

1.1　相關(guān)定義

(1)

1.1.1計(jì)算ρi

計(jì)算密度時(shí)常用的核函數(shù)包括截?cái)嗪?Cut-off kernel)、高斯核(Gaussian kernel)和指數(shù)核(Exponential kernel)，它們的定義分別如下：

(2)

(3)

(4)

式(2)～(4)中的參數(shù)dc>0為閾值(截?cái)嗑嚯x)，需由使用者事先指定。

1.1.2計(jì)算δi

ρq1≥ρq2≥…≥ρqN

(5)

然后定義

(6)

至此，對(duì)于S中的每個(gè)數(shù)據(jù)點(diǎn)xi，可利用式(2)、 (3)或(4)以及式(6)為其計(jì)算(ρi,δi)(i∈IS)。

根據(jù)ρi,δi的定義可知，當(dāng)某個(gè)點(diǎn)的這兩個(gè)量同時(shí)取值較大時(shí)，這個(gè)點(diǎn)就滿足前文提到的成為簇中心的兩個(gè)條件，因此可以利用以ρ為橫軸，δ為縱軸的圖(稱為決策圖)來(lái)判斷哪些點(diǎn)同時(shí)具有較大的ρ值和δ值，即哪些點(diǎn)可以被當(dāng)成是簇中心。

1.2　算法步驟及流程

下面利用上述符號(hào)給出尋找密度峰值聚類算法的具體步驟。

步驟1初始化及預(yù)處理。

1)給定用于確定閾值(截?cái)嗑嚯x)dc的參數(shù)t∈(0,1)。

2)給定權(quán)值γ。

3)計(jì)算距離dij，并令dji=dij(i

4)確定閾值dc。

將上一步計(jì)算的距離dij(i

步驟3對(duì)非簇中心數(shù)據(jù)點(diǎn)進(jìn)行歸類。

注1：當(dāng)處理某個(gè)xqi時(shí)，若所有比xqi密度大的點(diǎn)到xqi的距離都相等，則把xqi隨機(jī)分配到一個(gè)xqj(j

步驟4若nc>1，則將每個(gè)簇中的數(shù)據(jù)點(diǎn)進(jìn)一步分為“簇核心”和“簇光暈”。

1)初始化標(biāo)記hi=0(i∈IS)。

2)確定每個(gè)簇的邊界區(qū)域。這個(gè)區(qū)域中的數(shù)據(jù)點(diǎn)定義如下：它們屬于該簇，且在與其距離不超過(guò)dc的范圍內(nèi)，存在屬于其他簇的數(shù)據(jù)點(diǎn)。

1.3　算法復(fù)雜度分析

在針對(duì)混合型數(shù)據(jù)的尋找密度峰值算法中，給定閾值dc及權(quán)值γ后，該算法的時(shí)間復(fù)雜度主要包括距離矩陣的計(jì)算，本文算法需計(jì)算n(n-1)/2個(gè)距離值，n是數(shù)據(jù)集中的數(shù)據(jù)對(duì)象數(shù)，因此算法時(shí)間復(fù)雜度為O(n2)。k-prototypes算法的時(shí)間復(fù)雜度為O((l+1)kn)，其中k是簇?cái)?shù)，n是數(shù)據(jù)集中的數(shù)據(jù)對(duì)象數(shù)，l是k-prototypes算法收斂所需的迭代次數(shù)。當(dāng)n很大時(shí)，本文算法的時(shí)間復(fù)雜度可能會(huì)遠(yuǎn)高于k-prototypes算法。

2　閾值和權(quán)值的選取

從以上論述可知，新算法中可能影響最終聚類結(jié)果的因素主要有兩個(gè)： 1)密度公式中的閾值(截?cái)嗑嚯x)dc；2)距離公式中的權(quán)值γ。接下來(lái)需進(jìn)一步討論并驗(yàn)證這兩個(gè)因素對(duì)聚類結(jié)果的影響，并給出一個(gè)相對(duì)合理的方式來(lái)選取這兩個(gè)參數(shù)，以達(dá)到最理想的聚類效果。

2.1　閾值dc的選取

對(duì)于dc的選取，文獻(xiàn)[11]給出了一種一般性的方法：選取一個(gè)dc，使每個(gè)數(shù)據(jù)點(diǎn)的平均“鄰居”個(gè)數(shù)大約為數(shù)據(jù)點(diǎn)總數(shù)的1%～4%，這里的“鄰居”是指與其距離不超過(guò)dc的點(diǎn)，具體的比例通常根據(jù)研究人員的經(jīng)驗(yàn)和實(shí)際的數(shù)據(jù)集而定。

以上方法需要根據(jù)個(gè)人實(shí)際經(jīng)驗(yàn)來(lái)確定dc，但通過(guò)下文的實(shí)驗(yàn)(這些實(shí)驗(yàn)的細(xì)節(jié)會(huì)在2.1.3節(jié)中介紹)可以看到，聚類結(jié)果會(huì)受到閾值dc的影響，而根據(jù)經(jīng)驗(yàn)很難估計(jì)出最優(yōu)的閾值dc。對(duì)同一數(shù)據(jù)集，若閾值的經(jīng)驗(yàn)估計(jì)值不同，則聚類的結(jié)果可能也不同。

為了解決這一問(wèn)題，使用數(shù)據(jù)場(chǎng)中的勢(shì)熵從混合型數(shù)據(jù)集中自動(dòng)提取最優(yōu)的閾值dc。文獻(xiàn)[17]提出用數(shù)據(jù)場(chǎng)去描述數(shù)據(jù)空間中對(duì)象之間共同的交互作用，同時(shí)文獻(xiàn)[18-19]指出對(duì)于同樣的參數(shù)，數(shù)據(jù)點(diǎn)在稠密區(qū)域有較高的勢(shì)而在稀疏區(qū)域有較低的勢(shì)。

可用于計(jì)算勢(shì)的勢(shì)函數(shù)有很多種，如高斯核、指數(shù)核、截?cái)嗪说取＝酉聛?lái)介紹如何通過(guò)數(shù)據(jù)場(chǎng)中的勢(shì)熵計(jì)算出在不同勢(shì)函數(shù)和不同數(shù)據(jù)集下的最優(yōu)閾值。

2.1.1數(shù)據(jù)場(chǎng)

假設(shè)在數(shù)據(jù)空間Ω中有一個(gè)混合型數(shù)據(jù)集X={x1,x2, …,xn}。文獻(xiàn)[19]指出受到物理上場(chǎng)論的影響，將X中的一個(gè)數(shù)據(jù)對(duì)象當(dāng)成一個(gè)在給定的任務(wù)中傳播它的數(shù)據(jù)分布的物理對(duì)象，這就形成了數(shù)據(jù)場(chǎng)。對(duì)于一個(gè)任意的點(diǎn)xi∈Ω(1=1,2,…,n)，場(chǎng)函數(shù)按如下公式定義:

(7)

其中：σ是一個(gè)影響因子；mj是xj的質(zhì)量；K(x)是一個(gè)單位勢(shì)函數(shù)，xi-xj是點(diǎn)i和另一個(gè)點(diǎn)j之間的方位距離。σ對(duì)最終的勢(shì)分布有一定的影響。K(x)給出了數(shù)據(jù)對(duì)象把它的數(shù)據(jù)分布擴(kuò)散到數(shù)據(jù)場(chǎng)中的規(guī)則，通常情況下K(x)選擇為高斯核函數(shù)。

2.1.2利用數(shù)據(jù)場(chǎng)提取最優(yōu)的截?cái)嗑嚯x

在式(7)中，如果數(shù)據(jù)場(chǎng)是一個(gè)標(biāo)量場(chǎng)，則mj=1，當(dāng)K(x)選擇高斯核函數(shù)時(shí)，xi-xj變成dij，dij表示點(diǎn)xi和xj之間的某種距離，那么每一個(gè)點(diǎn)的勢(shì)φi由如下公式計(jì)算：

(8)

圖1　原始數(shù)值型數(shù)據(jù)集和加入類標(biāo)號(hào)的數(shù)據(jù)集ⅠFig. 1　Original numeric data set and data set with the class label Ⅰ

圖2　原始數(shù)值型數(shù)據(jù)集和加入類標(biāo)號(hào)的數(shù)據(jù)集ⅡFig. 2　Original numeric dataset and dataset with class label Ⅱ

如果式(8)中的dij和新算法中dij的度量方式相同，并且如果新算法在計(jì)算密度時(shí)也選取高斯核函數(shù)，那么點(diǎn)xi在數(shù)據(jù)場(chǎng)中的勢(shì)φi和在新算法中的密度ρi是等價(jià)的，也就是說(shuō)式(8)與式(3)是等價(jià)的。

同理，當(dāng)數(shù)據(jù)場(chǎng)中的勢(shì)函數(shù)和密度公式都取為截?cái)嗪撕瘮?shù)或指數(shù)核函數(shù)時(shí)，點(diǎn)xi在數(shù)據(jù)場(chǎng)中的勢(shì)φi和在新算法中的密度ρi是也等價(jià)的。因此在尋找密度峰值的聚類算法中，閾值dc的最優(yōu)化問(wèn)題可以轉(zhuǎn)化為數(shù)據(jù)場(chǎng)中影響因子σ的最優(yōu)化問(wèn)題。我們希望找到一個(gè)影響因子σ使得隨機(jī)變量的不確定性達(dá)到最小。

在信息論與概率統(tǒng)計(jì)中，熵[20]是隨機(jī)變量不確定性的度量,熵越大，隨機(jī)變量的不確定性越大。

設(shè)X是一個(gè)取有限個(gè)值的離散隨機(jī)變量，其概率分布為:

P(X=xi)=pi;i=1,2,…,n

(9)

則隨機(jī)變量X的熵定義為:

(10)

因此，可以使用熵來(lái)最優(yōu)化σ。對(duì)于數(shù)據(jù)集X，如果數(shù)據(jù)場(chǎng)中每個(gè)點(diǎn)的勢(shì)為{φ1,φ2,…,φn}，則熵H的定義如式(11)：

(11)

由于取相同的核函數(shù)時(shí)，數(shù)據(jù)場(chǎng)中的影響因子σ與新算法中密度公式里的閾值dc等價(jià),因此通過(guò)計(jì)算使熵H達(dá)到最小的影響因子σ，就可以得到尋找密度峰值聚類算法中的最優(yōu)閾值dc。

2.1.3實(shí)驗(yàn)和分析

為了更加直觀地看到選取不同閾值時(shí)的聚類結(jié)果，且為了驗(yàn)證基于數(shù)據(jù)場(chǎng)的方法提取最優(yōu)閾值的合理性，本節(jié)使用具有兩個(gè)數(shù)值型和一個(gè)分類型屬性的混合型數(shù)據(jù)集進(jìn)行模擬，數(shù)據(jù)的記錄按照如下方法產(chǎn)生。

首先生成四組二維數(shù)據(jù)點(diǎn)。第一組包含四個(gè)正態(tài)分布并且包含300個(gè)點(diǎn)(如圖1(a))；第二組包含七個(gè)正態(tài)分布并且包含840個(gè)點(diǎn)(如圖2(a))；第三組是兩個(gè)環(huán)狀分布并且包含400個(gè)點(diǎn)(如圖3(a))。然后給每個(gè)點(diǎn)加入一個(gè)分類值，從而把這些點(diǎn)擴(kuò)展到3維，分別記這三個(gè)數(shù)據(jù)集為Ⅰ、Ⅱ和Ⅲ(如圖1(b)、2(b)、3(b))(文獻(xiàn)[21]展示了本文所有彩色原圖)。

需要注意的是，一個(gè)點(diǎn)的分類值不能表明它是哪個(gè)類成員。事實(shí)上，這些點(diǎn)完全沒(méi)有類，分類值僅僅代表對(duì)象在第三維既不是連續(xù)的也不是有序的。因此對(duì)每個(gè)數(shù)據(jù)集加入分類值時(shí)，我們使分類型屬性可能的取值個(gè)數(shù)等于僅考慮數(shù)值型屬性時(shí)二維平面中簇的個(gè)數(shù)，這樣做是為了分別利用數(shù)值型屬性和分類型屬性進(jìn)行聚類時(shí)簇的個(gè)數(shù)相等，把兩個(gè)屬性放在一起考慮時(shí)也可以有一個(gè)統(tǒng)一的聚類簇?cái)?shù)(在此先不考慮數(shù)值型屬性和分類型屬性的權(quán)重問(wèn)題)，同時(shí)也可以在模擬實(shí)驗(yàn)中看到該算法自動(dòng)選取的簇?cái)?shù)是否合理。

對(duì)于第一個(gè)數(shù)據(jù)集，把每個(gè)正態(tài)分布看成一部分，并且給每部分的大多數(shù)點(diǎn)分配其中一個(gè)分類型屬性值，使得擁有這個(gè)分類型屬性值的點(diǎn)數(shù)與擁有其余的分類型屬性值的點(diǎn)數(shù)大致相等。例如在圖1(b)左上角的部分中大多數(shù)點(diǎn)被分配屬性值A(chǔ)，并且這部分其余的點(diǎn)被分配屬性值B、C或者D。所有的分配都是隨機(jī)的。剩下兩個(gè)數(shù)據(jù)集的分類值的分配情況類似(如圖2(b)、3(b))。

對(duì)于同樣的數(shù)據(jù)集選擇相同類型的核函數(shù)和相同的距離公式，如果聚類結(jié)果不同，說(shuō)明閾值dc對(duì)該聚類算法的聚類結(jié)果有重要的影響。在本實(shí)驗(yàn)中使用數(shù)據(jù)集Ⅰ，并且度量數(shù)據(jù)集中數(shù)據(jù)點(diǎn)的密度時(shí)選用高斯核函數(shù)。將數(shù)據(jù)集中所有對(duì)象之間的距離dij(i

圖3　原始數(shù)值型數(shù)據(jù)集和加入類標(biāo)號(hào)的數(shù)據(jù)集ⅢFig. 3　Original numeric dataset and dataset with class label Ⅲ

圖4　數(shù)據(jù)集Ⅰ對(duì)于選取不同閾值的聚類結(jié)果Fig. 4　Clustering results with different thresholds for dataset Ⅰ

為了印證利用數(shù)據(jù)場(chǎng)得到閾值dc是一種較合理的方法，接下來(lái)仍繼續(xù)使用數(shù)據(jù)集Ⅰ、Ⅱ和Ⅲ進(jìn)行比較性模擬實(shí)驗(yàn)，實(shí)驗(yàn)中計(jì)算數(shù)據(jù)場(chǎng)中勢(shì)的勢(shì)函數(shù)和計(jì)算數(shù)據(jù)集中點(diǎn)密度的核函數(shù)均選取高斯核函數(shù)，距離度量公式中數(shù)值型和分類型屬性的權(quán)值取為γ=2。對(duì)于利用經(jīng)驗(yàn)選取閾值的方法，將所有的dij(i

由前述可知，尋找密度峰值的聚類算法可識(shí)別出數(shù)據(jù)集中的噪聲點(diǎn)(異常值)，噪聲點(diǎn)會(huì)對(duì)聚類算法產(chǎn)生一定干擾，因此，須盡可能多地識(shí)別出噪聲點(diǎn)從而提高算法的穩(wěn)定性。表1中列出了利用兩種不同方法選取閾值時(shí)，算法移除噪聲點(diǎn)的個(gè)數(shù)。從表1可以看到，對(duì)于這三個(gè)數(shù)據(jù)集，利用數(shù)據(jù)場(chǎng)提取閾值的方法比利用經(jīng)驗(yàn)的方法移除的噪聲點(diǎn)更多。同時(shí)對(duì)于這三個(gè)數(shù)據(jù)集，無(wú)論是用一般性的方法選取閾值還是利用數(shù)據(jù)場(chǎng)自動(dòng)提取閾值都與每個(gè)數(shù)據(jù)集對(duì)應(yīng)的合理簇?cái)?shù)一致(進(jìn)行模擬的數(shù)據(jù)集包含的簇?cái)?shù))，所以至少可以說(shuō)明利用數(shù)據(jù)場(chǎng)來(lái)確定閾值的方法不會(huì)比利用經(jīng)驗(yàn)來(lái)確定的方法表現(xiàn)更差，而且它對(duì)于任何的數(shù)據(jù)集都適用，也就是說(shuō)對(duì)于任意的數(shù)據(jù)集都可以自動(dòng)計(jì)算出一個(gè)閾值，而不需要根據(jù)用戶的經(jīng)驗(yàn)來(lái)指定，因此該方法的適用性更廣。

2.2　權(quán)值γ的選取

對(duì)于混合型數(shù)據(jù)的聚類，距離公式中分類型屬性權(quán)值γ的選取也會(huì)直接影響到最終的聚類效果，通常為了簡(jiǎn)單起見(jiàn)，可以取γ=1，即兩種屬性的權(quán)重相等。文獻(xiàn)[3]指出混合型數(shù)據(jù)距離公式中權(quán)值γ的選取依賴于數(shù)值型屬性的分布，即權(quán)值γ的選取依賴于數(shù)值型屬性的平均標(biāo)準(zhǔn)差σ，但該文獻(xiàn)并未給出具體應(yīng)如何選取以及這樣選取的依據(jù)。因此本節(jié)對(duì)權(quán)值γ的選取提出一個(gè)新的方法。

表1　利用兩種不同方法選取閾值時(shí)移除噪聲點(diǎn)的個(gè)數(shù)Tab. 1　Number of removed noise points with different threshold selected by two different methods

2.2.1聚類趨勢(shì)

對(duì)于給定的數(shù)據(jù)集，幾乎每個(gè)聚類算法都可以為該數(shù)據(jù)集返回簇，然而如果數(shù)據(jù)集中根本不存在自然的簇，那么通過(guò)聚類算法所產(chǎn)生的簇很可能不具有實(shí)際的意義?？紤]一個(gè)完全隨機(jī)結(jié)構(gòu)的數(shù)據(jù)集，如數(shù)據(jù)空間中均勻分布的點(diǎn)，盡管聚類算法仍然可以人工地把這些點(diǎn)劃分成簇，但這些簇是隨機(jī)的，不具有任何意義。所以只有當(dāng)數(shù)據(jù)集有明顯的聚類趨勢(shì)時(shí)，聚類算法返回的簇才有實(shí)際意義。

因此，可以提出這樣的方法來(lái)確定權(quán)值γ：1)分別計(jì)算混合型數(shù)據(jù)集中數(shù)據(jù)對(duì)象的數(shù)值部分和分類部分的聚類趨勢(shì)。數(shù)值部分的聚類趨勢(shì)可以利用霍普金斯(Hopkins)統(tǒng)計(jì)量的變化形式來(lái)計(jì)算，分類部分的聚類趨勢(shì)利用下文2.2.3節(jié)中提出的統(tǒng)計(jì)量來(lái)計(jì)算。2)如果數(shù)值部分的聚類趨勢(shì)更明顯，那么希望γ小一些；如果分類部分的聚類趨勢(shì)更明顯，那么希望γ大一些。

2.2.2數(shù)值型數(shù)據(jù)集的聚類趨勢(shì)

對(duì)于給定的混合型數(shù)據(jù)集，將其中的數(shù)值部分取出構(gòu)成一個(gè)數(shù)值型數(shù)據(jù)集，然后將該數(shù)據(jù)集與其在數(shù)據(jù)空間中的均勻分布進(jìn)行比較，以此評(píng)估該混合型數(shù)據(jù)集中數(shù)值部分的聚類趨勢(shì)?；羝战鹚菇y(tǒng)計(jì)量可用來(lái)度量數(shù)值型數(shù)據(jù)集的聚類趨勢(shì)。

霍普金斯統(tǒng)計(jì)量[1]是一種空間統(tǒng)計(jì)量，檢驗(yàn)空間分布的變量的空間隨機(jī)性。給定混合型數(shù)據(jù)集D，取出其中的數(shù)值型部分組成一個(gè)數(shù)值型數(shù)據(jù)集Dr，它可以看作隨機(jī)變量Z的一個(gè)樣本，想要確定Z在多大程度上不同于數(shù)據(jù)空間中的均勻分布，可以根據(jù)文獻(xiàn)[1]中總結(jié)的步驟來(lái)計(jì)算:

(12)

(13)

3)計(jì)算可度量數(shù)值型數(shù)據(jù)集聚類趨勢(shì)的統(tǒng)計(jì)量Hr(霍普金斯統(tǒng)計(jì)量的變形)。

(14)

2.2.3分類型數(shù)據(jù)集的聚類趨勢(shì)

受到可度量數(shù)值型數(shù)據(jù)集聚類趨勢(shì)的霍普金斯統(tǒng)計(jì)量的啟發(fā)，對(duì)于分類型數(shù)據(jù)集，同樣可以提出一個(gè)用來(lái)度量其聚類趨勢(shì)的統(tǒng)計(jì)量Hc。

Hc是一個(gè)可以評(píng)估分類型數(shù)據(jù)分布隨機(jī)性的統(tǒng)計(jì)量。給定混合型數(shù)據(jù)集D，取出其中的分類型部分組成一個(gè)分類型數(shù)據(jù)集Dc，然后按以下步驟計(jì)算:

(15)

(16)

3)計(jì)算可度量分類型數(shù)據(jù)集聚類趨勢(shì)的統(tǒng)計(jì)量Hc:

(17)

2.2.4權(quán)值γ的計(jì)算

從以上分析可以看到，Hr越小說(shuō)明混合型數(shù)據(jù)中數(shù)值部分的聚類趨勢(shì)越明顯；同理，Hc越小說(shuō)明混合型數(shù)據(jù)中分類部分的聚類趨勢(shì)越明顯。因此，如果混合型數(shù)據(jù)集D的Hr越小，則希望γ的取值越小，即希望聚類時(shí)更多的考慮數(shù)值型屬性；相反，如果混合型數(shù)據(jù)集D的Hc越小，則希望γ的取值越大，即希望聚類時(shí)更多地考慮分類型屬性。因此可以按以下公式定義權(quán)值γ：

γ=Hr/Hc

(18)

2.2.5實(shí)驗(yàn)與分析

為了更加直觀地看到選取不同權(quán)值時(shí)的聚類結(jié)果并且驗(yàn)證利用聚類趨勢(shì)定義權(quán)值的合理性，使用一個(gè)新的僅有三個(gè)屬性的混合型數(shù)據(jù)集Ⅳ進(jìn)行模擬，屬性中有兩個(gè)數(shù)值型和一個(gè)分類型，這些數(shù)據(jù)記錄按如下的方式產(chǎn)生。

首先生成一組二維數(shù)據(jù)點(diǎn)，這組數(shù)據(jù)包含400個(gè)點(diǎn)且是一個(gè)正態(tài)分布(圖5(a))；然后通過(guò)給每個(gè)點(diǎn)加入一個(gè)分類值把這些點(diǎn)擴(kuò)展到三維(圖5(b))。對(duì)于這個(gè)數(shù)據(jù)集我們?nèi)藶榈匕阉殖伤膫€(gè)部分：用以(0,0)為坐標(biāo)原點(diǎn)的坐標(biāo)軸把區(qū)域分成左上、左下、右上、右下，因此給每部分中的大多數(shù)點(diǎn)分配一個(gè)分類值，使得擁有這個(gè)分類值的點(diǎn)數(shù)與擁有其余分類值的點(diǎn)數(shù)大致相等。舉個(gè)例子，在圖5(b)中右上角的部分大多數(shù)點(diǎn)被分配屬性值A(chǔ)并且這部分其余的點(diǎn)被分配B、C或者D。

模擬的主要目的是驗(yàn)證在該算法中數(shù)值型和分類型屬性如何相互影響，如果只考慮數(shù)值型屬性，那么可知這個(gè)二維數(shù)據(jù)只包含一個(gè)自然簇；當(dāng)加入第三維分類型屬性時(shí)，可知那些空間上離得比較近且有相同分類值的點(diǎn)更傾向于分到同一個(gè)簇。圖6為數(shù)據(jù)集Ⅳ對(duì)于不同權(quán)值γ的聚類結(jié)果，其他的參數(shù)完全一樣，其中不同的顏色表示聚類后得到的不同的簇。從圖6可以看到，對(duì)于不同的權(quán)值γ，聚類結(jié)果的差異很大，所以對(duì)權(quán)值選取的討論很有必要。當(dāng)權(quán)值很小(γ=0.1)時(shí)，分類型屬性的貢獻(xiàn)較小，雖然難以解釋此時(shí)的聚類結(jié)果，但可以看到空間上離得比較近的點(diǎn)會(huì)被分到同一個(gè)簇；隨著權(quán)值γ的增加，可以看到第三維上類標(biāo)號(hào)相同的點(diǎn)會(huì)逐漸被分到同一個(gè)簇中。對(duì)于數(shù)據(jù)集Ⅳ，當(dāng)權(quán)值γ=7.5時(shí)，所有類標(biāo)號(hào)相同的點(diǎn)被分到同一個(gè)簇。

圖5　原始數(shù)值型數(shù)據(jù)集和加入類標(biāo)號(hào)的數(shù)據(jù)集ⅣFig. 5　Original numeric dataset and the dataset with class label Ⅳ

接下來(lái)對(duì)數(shù)據(jù)集Ⅳ使用本文提出的方法計(jì)算一個(gè)較為合理的γ。利用式(18)得到γ=0.37，聚類結(jié)果見(jiàn)圖7，其中不同的顏色表示聚類后得到的不同的簇。從圖7可以看到，γ=0.37時(shí)的聚類結(jié)果與之前人為的劃分較為吻合，大致分成左上、左下、右上、右下四個(gè)部分，因此也從另一個(gè)角度說(shuō)明了γ選取的合理性。

3　實(shí)證分析

為了進(jìn)一步對(duì)提出的尋找密度峰值聚類算法進(jìn)行驗(yàn)證，本章使用一些實(shí)際數(shù)據(jù)集進(jìn)行測(cè)試，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。

3.1　數(shù)據(jù)集的選取

為了驗(yàn)證本文算法的有效性，選用UCI機(jī)器學(xué)習(xí)庫(kù)[16]中的Cylinder Bands(以下簡(jiǎn)稱Cylinder)、German Credit Data(以下簡(jiǎn)稱German)和Postoperative Patient Data(以下簡(jiǎn)稱Patient)這三組混合型數(shù)據(jù)集，數(shù)據(jù)描述見(jiàn)表2。分別在這三組數(shù)據(jù)集上對(duì)新算法和原始的k-prototypes算法進(jìn)行測(cè)試，聚類結(jié)果的分析主要依靠聚類的準(zhǔn)確率。

3.2　評(píng)價(jià)指標(biāo)

為了比較不同算法的正確率，引用文獻(xiàn)[22]提出的聚類正確率定義，算法在數(shù)據(jù)集上的聚類正確率如下：

(19)

其中：k為該數(shù)據(jù)集真實(shí)的類的個(gè)數(shù)，corr_ci表示第i個(gè)類中被正確聚類的樣本個(gè)數(shù)，|D|為該數(shù)據(jù)集的樣本個(gè)數(shù)。

由此看出，ac_rate值越大，聚類效果越好。當(dāng)聚類結(jié)果與已知類標(biāo)號(hào)完全一致時(shí)，取得最大值1。

圖6　數(shù)據(jù)集Ⅳ對(duì)于不同的權(quán)值的聚類結(jié)果Fig. 6　Clustering results of different weights in dataset Ⅳ

圖7　數(shù)據(jù)集Ⅳ的一個(gè)合理權(quán)值的聚類結(jié)果Fig. 7　Clustering result of reasonable weight of the dataset Ⅳ

表2　實(shí)際數(shù)據(jù)集描述Tab. 2　Real dataset description

3.3　實(shí)驗(yàn)結(jié)果

對(duì)于k-prototypes算法，使用式(1)作為數(shù)據(jù)對(duì)象之間的相異性度量，γ取為1(使得數(shù)值型屬性和分類型屬性有同等的地位)。對(duì)于新提出的算法，按照常規(guī)參數(shù)選取和本文新提出的參數(shù)選取分別進(jìn)行驗(yàn)證，這樣不僅可以測(cè)試新型算法的有效性，同時(shí)可以測(cè)試新提出的參數(shù)選取方法的有效性。對(duì)于新型算法的常規(guī)參數(shù)選取，γ取為1，閾值dc取為所有的dij(i

表3　不同算法的聚類正確率比較Tab. 3　Comparison of clustering accuracy of different algorithms

4　結(jié)語(yǔ)

本文打破了對(duì)混合型數(shù)據(jù)進(jìn)行聚類時(shí)最常用的k-prototypes算法的框架，把用于數(shù)值型數(shù)據(jù)的CFSFDP算法擴(kuò)展到混合型數(shù)據(jù)，提出了一種新的針對(duì)混合型數(shù)據(jù)的尋找密度峰值聚類算法。該算法不像k-prototypes算法一樣僅僅考慮對(duì)象到簇中心(原型)的距離，而是考慮了對(duì)象之間的某種關(guān)系，認(rèn)為密度高的點(diǎn)“控制”了與它距離最近的低密度點(diǎn)，這樣可以使那些距離較遠(yuǎn)但原本屬于同一個(gè)自然簇的對(duì)象在聚類過(guò)程中能被正確地分配，由此實(shí)現(xiàn)了該算法對(duì)簇分布的適應(yīng)性，而不像k-prototypes算法那樣只能識(shí)別球狀分布的簇。同時(shí)該算法在確定簇中心的同時(shí)也就自動(dòng)確定了簇的個(gè)數(shù)，而不需要像k-prototypes算法根據(jù)經(jīng)驗(yàn)事先指定簇?cái)?shù)。

雖然本文提出的針對(duì)混合型數(shù)據(jù)的聚類算法在很多情況下是很有效的，但仍存在一些不足之處，通過(guò)算法復(fù)雜度分析可以看出尋找密度峰值聚類算法的時(shí)間復(fù)雜度較高，當(dāng)采用本文提出的方法選取閾值和權(quán)值時(shí)會(huì)進(jìn)一步增加其復(fù)雜度，因此對(duì)于超大型數(shù)據(jù)集，其有效性還需進(jìn)一步驗(yàn)證，在未來(lái)的研究中需要針對(duì)該算法的復(fù)雜度問(wèn)題作更深入的討論。

參考文獻(xiàn):

[1]HAN J W, KAMBER M, PEI J. 數(shù)據(jù)挖掘：概念與技術(shù)[M].范明,孟小峰,譯.3版.北京：機(jī)械工業(yè)出版社,2012:288,315-316. (HAN J W, KAMBER M, PEI J. Data Mining: Concept and Techniques [M]. FAN M, MENG X F, translated. 3rd ed. Beijing: China Machine Press, 2012: 288, 315-316.)

[2]冀進(jìn)朝.針對(duì)多維混合屬性數(shù)據(jù)的聚類算法研究[D].長(zhǎng)春:吉林大學(xué),2013:I. (JI J C. Research on clustering algorithms for the data with multidimensional mixed attributes [D]. Changchun: Jilin University, 2013: I.)

[3]HUANG Z. Clustering large data sets with mixed numeric and categorical values [C]// PAKDD 1997: Proceedings of the First Pacific-Asia Knowledge Discovery and Data Mining Conference. Singapore: World Scientific, 1997: 21-34.

[4]CHEN N, CHEN A, ZHOU L. Fuzzyk-prototypes algorithm for clustering mixed numeric and categorical valued data [J]. Journal of Software, 2001, 12(8): 1107-1119.

[5]CHATZIS S P. A fuzzyc-mean-types algorithm for clustering of data with mixed numeric and categorical attributes employing a probabilistic dissimilarity functional [J]. Expert Systems with Application, 2011, 38(7): 8684-8689.

[6]王宇,楊莉.模糊k-prototypes聚類算法的一種改進(jìn)算法[J].大連理工大學(xué)學(xué)報(bào),2003,43(6):849-852. (WANG Y, YANG L. An improved algorithm for fuzzyk-prototypes algorithm [J]. Journal of Dalian University of Technology, 2003, 43(6): 849-852.)

[7]LI C, BISWAS G. Unsupervised learning with mixed numeric and nominal data [J]. IEEE Transactions on Knowledge and Data Engineering, 2002, 14(4): 673-690.

[8]孫浩軍,高玉龍,閃光輝,等.基于熵權(quán)法的混合屬性聚類算法[J].汕頭大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,28(4):58-65. (SUN H J, GAO Y L, SHAN G H, et al. A clustering algorithm based on entropy weight for mixed numeric and categorical data [J]. Journal of Shantou University (Natural Science), 2013, 28(4): 58-65.)

[9]趙興旺,梁吉業(yè).一種基于信息熵的混合型數(shù)據(jù)屬性加權(quán)聚類算法[J].計(jì)算機(jī)研究與發(fā)展,2016,53(5):1018-1028. (ZHAO X W, LIANG J Y. An attribute weighted clustering algorithm for mixed data based on information entropy [J]. Journal of Computer Research and Development, 2013, 53(5): 1018-1028.)

[10]周才英,黃龍軍.模糊K-Prototype聚類算法初始點(diǎn)選取方法的改進(jìn)[J].計(jì)算機(jī)科學(xué),2010,37(7A):69-75. (ZHOU C Y, HUANG L J. Improvement of the method to choosing the initial value of fuzzyK-prototypes clustering algorithm [J]. Computer Science, 2010, 37(7A): 69-75.)

[11]RODRIGUEZ A, LAIO A. Clustering by fast search and find of density peak [J]. Science, 2014, 344(6191): 1492-1496.

[12]BIE R, MEHMOOD R, RUAN S, et al. Adaptive fuzzy clustering by fast search and find of density peaks [J]. Personal and Ubiquitous Computing, 2016, 20(5): 785-793.

[13]蔣禮青,張明新,鄭金龍,等.快速搜索與發(fā)現(xiàn)密度峰值聚類算法的優(yōu)化研究[J].計(jì)算機(jī)應(yīng)用研究,2016,33(11):3251-3254. (JIANG L Q, ZHANG M X, ZHENG J L, et al. Optimization of clustering by fast search and find of density peaks [J]. Application Research of Computers, 2016, 33(11): 3251-3254.)

[14]馬春來(lái),單洪,馬濤.一種基于簇中心點(diǎn)自動(dòng)選擇策略的密度峰值聚類算法[J].計(jì)算機(jī)科學(xué),2016,43(7):255-258,280. (MA C L, SHAN H, MA T. Improved density peaks based clustering algorithm with strategy choosing center automatically [J]. Computer Science, 2016, 43(7): 225-258, 280.)

[15]詹春霞,王榮波,黃孝喜,等.基于改進(jìn)CFSFDP算法的文本聚類方法及其應(yīng)用[J].數(shù)據(jù)分析與知識(shí)發(fā)現(xiàn),2017,1(4):94-99. (ZHAN C X, WANG R B, HUANG X X, et al. Application of text clustering method based on improved CFSFDP algorithm [J]. Data Analysis and Knowledge Discovery, 2017, 1(4): 94-99.)

[16]UCI database [EB/OL]. [2017- 01- 20]. http:// archive.ics.uci.edu/ml/datasets.html.

[17]WANG S, GAN W, LI D, et al. Data field for hierarchical clustering [J]. International Journal of Data Warehousing and Mining, 2011, 7(4): 43-63.

[18]WANG S, CHEN Y. HASTA: a hierarchical-grid clustering algorithm with data field [J]. International Journal of Data Warehousing and Mining, 2014, 10(2): 39-54.

[19]WANG S, WANG D, LI C, et al. Clustering by fast search and find of density peaks with data field [J]. Chinese Journal of Electronics, 2016, 25(3): 397-402.

[20]李航.統(tǒng)計(jì)學(xué)習(xí)方法 [M].北京:清華大學(xué)出版社,2012:60. (LI H. Method of Statistical Learning [M]. Beijing: Qinghua University Press, 2012: 60.)

[21]陳奕延.《基于密度峰值的混合型數(shù)據(jù)聚類算法設(shè)計(jì)》——聚類效果彩色圖[EB/OL]. [2017- 09- 09]. http://blog.csdn.net/dr_chenyiyan/article/details/77914036. (CHEN Y Y. Design of hybrid data clustering algorithm based on density peak: Chromatic effect diagrams in clustering [EB/OL]. [2017- 09- 09]. http://blog.csdn.net/dr_chenyiyan/article/details/77914036.)

[22]AL-SHAMMARY D, KHILI I, TARI Z, et al. Fractal self-similarity measurements based clustering technique for SOAP Web messages [J]. Journal of Parallel and Distributed Computing, 2013, 73(5): 664-676.