譚 陽(yáng)，唐德權(quán)，曹守富

1.湖南師范大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，長(zhǎng)沙410081

2.湖南廣播電視大學(xué) 網(wǎng)絡(luò)技術(shù)系，長(zhǎng)沙410004

3.湖南警察學(xué)院 信息技術(shù)系，長(zhǎng)沙410138

1 引言

聚類作為一種重要的數(shù)據(jù)分析方法已在許多領(lǐng)域得到廣泛應(yīng)用，作為機(jī)器自動(dòng)識(shí)別數(shù)據(jù)內(nèi)在結(jié)構(gòu)的研究重點(diǎn)[1]，聚類的任務(wù)是在沒(méi)有訓(xùn)練樣本的情況下，僅利用樣本間的相似性尋找樣本集針對(duì)某個(gè)評(píng)判準(zhǔn)則的最佳類別劃分。隨著聚類分析在金融、商業(yè)和社會(huì)學(xué)等領(lǐng)域的應(yīng)用不斷深入，使用的混合型數(shù)據(jù)進(jìn)行聚類的算法研究備受關(guān)注[2]。在混合型數(shù)據(jù)中，大多數(shù)樣本的特征表述采用連續(xù)型、分類型和順序型屬性[3]，由于三種屬性類型具有不同的特點(diǎn)，為混合型數(shù)據(jù)建立一個(gè)合理可行的相似性度量一直是國(guó)內(nèi)、外學(xué)者們研究的重點(diǎn)[4-5]。

樣本屬性的編碼以及相似性度量是設(shè)計(jì)針對(duì)混合數(shù)據(jù)的聚類算法的關(guān)鍵。對(duì)性質(zhì)簡(jiǎn)單的數(shù)據(jù)聚類多使用源于K-means算法[6]的編碼方式，即每個(gè)樣本只對(duì)K個(gè)聚類中心進(jìn)行編碼，然后利用數(shù)據(jù)樣本與聚類中心的相似程度進(jìn)行簇類劃分。因此，相似性度量對(duì)這類算法的性能具有重要影響。其中，最普遍的相似性度量為歐氏距離法，雖然以歐氏距離作為相似性度量，較經(jīng)典的梯度下降的方式在全局最優(yōu)化的性能上有了較大的提高，但是面對(duì)混合型這種在多重維度空間分布的數(shù)據(jù)，效果卻不夠理想。Huang等在文獻(xiàn)[7]中提出了K-Prototype算法，該算法將樣本屬性劃分為數(shù)值型和分類型，使不同的數(shù)據(jù)對(duì)象集合分別對(duì)應(yīng)不同的屬性維度集合，即將樣本屬性劃分到不同的子空間，再進(jìn)行歐氏距離的相似性度量，最后再將兩者結(jié)合起來(lái)度量樣本個(gè)體間的差異。雖然K-Prototype算法能夠處理混合型數(shù)據(jù)集，但仍然存在與K-means算法相同的缺陷：算法對(duì)空間中分布為球體或超球體的數(shù)據(jù)具有較好的性能，而對(duì)空間分布復(fù)雜的數(shù)據(jù)則效果較差。這是基于歐氏距離相似性度量的缺陷所導(dǎo)致的必然結(jié)果[8]。

為此，國(guó)內(nèi)外的研究者提出了各種改進(jìn)方法。Maulik等在文獻(xiàn)[9]中先通過(guò)遺傳算法來(lái)確定特征空間中的聚類中心，再以這些中心來(lái)優(yōu)化聚類的相似性度量，并以此提出了遺傳聚類算法（Genetic Algorithmbased Clustering technique，GAC）。在文獻(xiàn)[10]中Mei等針對(duì)數(shù)據(jù)的相似性分析提出了一種模糊聚類算法（The Proposed Fuzzy Cluster，PFC），該算法在聚類中采用權(quán)重機(jī)制對(duì)每個(gè)集群賦予權(quán)重值，以區(qū)分樣本的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，為后續(xù)的聚類過(guò)程提供先驗(yàn)知識(shí)。文獻(xiàn)[11]中，Chatzis在模糊C均值聚類算法的基礎(chǔ)上提出了（Fuzzy C-Means-type，F(xiàn)CM-type）算法，采用全概率相異性函數(shù)來(lái)處理混合屬性數(shù)據(jù)，通過(guò)交叉熵使得模糊目標(biāo)函數(shù)正則化，使其可以同時(shí)對(duì)混合型數(shù)據(jù)的數(shù)值型屬性和分類型屬性實(shí)施分類，實(shí)現(xiàn)了提高聚類精度的目的。趙興旺等在文獻(xiàn)[12]中利用類內(nèi)和類間信息熵來(lái)度量各個(gè)屬性在聚類過(guò)程中的作用，提出了基于信息熵的數(shù)據(jù)屬性加權(quán)聚類算法，通過(guò)賦予不同的屬性不同的權(quán)重，使得數(shù)據(jù)樣本可以在較為統(tǒng)一的框架下更為客觀地度量數(shù)據(jù)樣本及樣本與簇原型之間的相似性。目前，處理混合型數(shù)據(jù)的方式是將樣本屬性劃分到不同的子空間中分別進(jìn)行度量后再進(jìn)行整合評(píng)價(jià)。但此舉將分割樣本屬性的統(tǒng)一，導(dǎo)致屬性評(píng)價(jià)的非一致；從而產(chǎn)生對(duì)樣本的識(shí)別偏差，影響類簇劃分的效果。

近年來(lái)，利用數(shù)據(jù)樣本的最小鄰域來(lái)發(fā)現(xiàn)任意形狀的密度聚類方法受到了廣泛的關(guān)注[13-14]，這種基于密度聚類的方法具備在存有噪聲的大數(shù)據(jù)集中找到任意形狀的特性。Rodriguez等[15]提出了一種密度峰值聚類算法（Density Peaks Clustering algorithm，DPC），該算法通過(guò)利用決策圖（decision graph）來(lái)快速選擇聚類中心，不僅運(yùn)行高效且具有能發(fā)現(xiàn)任意形狀數(shù)據(jù)集并自動(dòng)確定簇?cái)?shù)的優(yōu)點(diǎn)，但DPC算法的缺陷是其使用范圍僅限于數(shù)值型數(shù)據(jù)集。為此，本文提出一種能夠有效處理混合型數(shù)據(jù)的密度峰值聚類算法——海明度量的密度峰值聚類算法（Density Peak Clustering algorithm for Hamming metrics，DPCH），算法以二進(jìn)制方式對(duì)樣本的屬性進(jìn)行編碼，再對(duì)屬性編碼施行海明差異評(píng)價(jià)，并依據(jù)不同屬性的性質(zhì)賦予不同的屬性權(quán)重，以此度量樣本間的相似程度。通過(guò)在統(tǒng)一的框架內(nèi)對(duì)混合型數(shù)據(jù)實(shí)施相似性度量，可有效避免對(duì)樣本屬性的切割，算法以海明度量計(jì)算樣本個(gè)體間密度和局部密度，以決策圖的方式來(lái)發(fā)現(xiàn)混合數(shù)據(jù)集的聚類中心。仿真實(shí)驗(yàn)結(jié)果表明，算法可對(duì)混合型數(shù)據(jù)集進(jìn)行有效的類簇識(shí)別。

2 基于海明密度峰值的混合數(shù)據(jù)聚類算法

混合型數(shù)據(jù)由于其度量函數(shù)的復(fù)雜性，使得早期的聚類算法難以對(duì)其進(jìn)行有效的聚類。近年來(lái)，對(duì)混合型數(shù)據(jù)聚類的研究重點(diǎn)在如何度量數(shù)據(jù)樣本之間的相似性；雖然通過(guò)類型劃分屬性的方式可以對(duì)樣本屬性的相似性進(jìn)行分別度量，但始終不能滿足多種數(shù)據(jù)類型在同一體系內(nèi)進(jìn)行評(píng)價(jià)和處理的要求。

2.1 規(guī)一化數(shù)據(jù)集

若存在一數(shù)據(jù)集，其中包含n個(gè)樣本，數(shù)據(jù)集可表示為X={ x1,x2,…,xn}，數(shù)據(jù)集中樣本的屬性數(shù)為d，分別為{ A1,A2,…,Ad}。以二進(jìn)制對(duì)樣本的全部屬性進(jìn)行編碼，若樣本的第R( R =1,2,…,d)個(gè)屬性AR的二進(jìn)制編碼長(zhǎng)度為L(zhǎng)R，則屬性AR的編碼空間為BR={0,1}LR，且屬性AR(AR?BR)為一有限點(diǎn)的集合。那么，對(duì)于第i(i=1,2,…,n)個(gè)樣本xi的第R個(gè)屬性表示為ARi,其編碼長(zhǎng)度為L(zhǎng)Ri；樣本xi的另一屬性J(R≠J)的二進(jìn)制編碼長(zhǎng)度為L(zhǎng)Ji。就樣本xi而言，依據(jù)其自身屬性的性質(zhì)來(lái)確定該屬性的二進(jìn)制編碼長(zhǎng)度，不同屬性間的編碼長(zhǎng)度無(wú)需一致。但數(shù)據(jù)集中樣本的同一屬性AR的編碼長(zhǎng)度LRi,(i=1,2,…,n)一致，如圖1所示（*表示屬性編碼長(zhǎng)度）。

2.2 樣本屬性的海明距離

若樣本xi(i=1,2,…,n)的第R個(gè)屬性為AR，則樣本xi的屬性AR表示為xiR，xiR=r1,r2,…,rl,…,rLR稱

rl(l=1,2,…,LR)，rl∈{0,1}

圖1 樣本屬性2維表

為屬性編碼元。對(duì)于任意兩個(gè)樣本xi與xj(xi,xj∈X)在任一屬性AR下的海明距離度量hR(xi,xj)為：

其中，xiRl表示樣本xi在屬性AR下的第l個(gè)屬性編碼元。由式（1）可知0≤hR(xi,xj)≤LR,hR(xi,xj)=hR(xj,xi)即hR是對(duì)稱的，且只有在xiR=xjR時(shí)hR(xi,xj)=0。由式（1）取得樣本屬性的海明距離后，則任意兩個(gè)樣本之間海明距離為：

由式（1）可知，屬性AR的編碼長(zhǎng)度LR對(duì)應(yīng)該屬性海明距離值hR的取值范圍。顯然，不同屬性的取值范圍并非一致，這必將導(dǎo)致樣本整體評(píng)價(jià)的非一致性。另外，在實(shí)際聚類操作中經(jīng)常需要凸顯樣本中一些重要的屬性[12]，但這些屬性并不一定具有較長(zhǎng)的二進(jìn)制編碼，因此，需要對(duì)不同屬性賦予不同的系數(shù)以調(diào)整屬性的權(quán)重。

2.3 屬性權(quán)重

在實(shí)際數(shù)據(jù)集中樣本的部分屬性會(huì)對(duì)聚類結(jié)果產(chǎn)生很大影響。因此，通常也將屬性的意義看作數(shù)據(jù)集相對(duì)于這個(gè)屬性的不均勻程度[16]。若某一屬性包含信息量較大，就該屬性而言，數(shù)據(jù)集中樣本的不均勻程度越高，該屬性的重要性也就越大。若樣本xi的第R個(gè)屬性AR有2L個(gè)取值，分別為{aR1,aR2,…,aR2L}。在一般情況下，對(duì)于屬性AR的熵值由式（3）進(jìn)行計(jì)算：

此時(shí)，將屬性AR看作一個(gè)離散隨機(jī)型變量，其概率分布如式（4）所示：

其中，P( AR=aRt)表示在整個(gè)數(shù)據(jù)集中屬性AR的屬性值為aRt的樣本所占比例，其計(jì)算公式如式（5）所示：

在完成全部屬性{A1,A2,…,Ad}的評(píng)價(jià)后，屬性AR的權(quán)重值αR由式（6）計(jì)算：

2.4 樣本間的海明度量

混合型數(shù)據(jù)樣本包含數(shù)值和分類兩種屬性，就分類屬性而言其取值范圍通常為一有限集中的離散值。傳統(tǒng)方法是將其視作無(wú)序型數(shù)值，并進(jìn)行簡(jiǎn)單的0-1匹配，忽略了分類屬性值之間的關(guān)聯(lián)性。這也是導(dǎo)致歐式距離和簡(jiǎn)單匹配方法對(duì)混合型數(shù)據(jù)劃分效果不理想的主要原因。為此，通過(guò)忽略混合型數(shù)據(jù)屬性的分類，將所有樣本在統(tǒng)一編碼條件下進(jìn)行編碼和評(píng)價(jià)，則可消除數(shù)值型和分類型屬性之間的編碼差異及評(píng)價(jià)體系差異。

設(shè)數(shù)據(jù)集X={x1,x2,…,xn}是一個(gè)由d個(gè)屬性所描述的數(shù)據(jù)集，若在聚類過(guò)程中被指定劃分為K個(gè)簇類，即C={C1,C2,…,CK},且1,2,…,K;i≠j)。在聚類混合型數(shù)據(jù)的結(jié)果中，簇類的熵值由類內(nèi)樣本屬性的熵所確定，某個(gè)屬性的不確定性程度越小則熵越小，表明該屬性的信息量越大。同理，某一簇類在不同屬性AR,(R=1,2,…,d)下數(shù)據(jù)分布的不確定程度越小，則該屬性在該簇類中的不確定性越小，在聚類過(guò)程中該屬性的作用程度越大。因此，在屬性AR下，任意一個(gè)簇類CK∈C的類內(nèi)熵WEC(CK,AR)

可表示為：

其中，nR表示在屬性AR值域的個(gè)數(shù)， ||Ys表示在屬性AR值域中的第s個(gè)取值Ys在簇類CK中出現(xiàn)的次數(shù)，|CK|表示簇類CK中樣本的個(gè)數(shù)。簇類CK的類內(nèi)熵表示類內(nèi)數(shù)據(jù)分布的不確定程度，類內(nèi)熵越小表明類內(nèi)數(shù)據(jù)的相似程度越高。結(jié)合式（7）和式（2）可知，任意一個(gè)類CK的類內(nèi)熵(CK,AR)與類內(nèi)任意兩樣本間的海明距離有如下關(guān)系：

由式（8）可知，類內(nèi)樣本的差異值只取決于樣本屬性的海明差異，與屬性的性質(zhì)無(wú)關(guān)。以統(tǒng)一的編碼對(duì)混合型數(shù)據(jù)進(jìn)行海明度量，可消除不同屬性表達(dá)類型之間度量量綱的差異性，避免了在多維空間中實(shí)施距離比較的復(fù)雜計(jì)算和評(píng)價(jià)不同屬性類型的非一致性問(wèn)題。

屬性編碼長(zhǎng)度的不統(tǒng)一，會(huì)導(dǎo)致對(duì)樣本整體評(píng)價(jià)的差異。雖然式（6）針對(duì)屬性所含的信息量大小，給出了統(tǒng)一的權(quán)重值計(jì)算方法，免去了不同屬性度量之間復(fù)雜的參數(shù)設(shè)置。但是，仍有必要對(duì)所有屬性海明度量的取值范圍進(jìn)行規(guī)整，使其統(tǒng)一到固定的區(qū)間之內(nèi)。對(duì)屬性AR實(shí)行hR(xi,xj)/LR計(jì)算，將評(píng)價(jià)的取值范圍規(guī)整到[0 ,1]區(qū)間內(nèi)，滿足屬性評(píng)價(jià)的一致性要求。數(shù)據(jù)集X={ x1,x2,…,xn}中任意兩個(gè)樣本xi與xj( i≠j)之間的海明度量H(xi,xj)為：

其中，1-αR表示屬性AR的加權(quán)系數(shù)，屬性AR的權(quán)重值αR越高，樣本間的海明度量越低，樣本間的相似性越高?；旌闲蛿?shù)據(jù)在統(tǒng)一編碼條件下進(jìn)行編碼，以海明差異作為混合型樣本的比較，將不同屬性間的相似性轉(zhuǎn)換成離散空間中編碼的海明差異，能夠更加宏觀地反映混合數(shù)據(jù)中個(gè)體與簇類之間的差異性。

2.5 數(shù)據(jù)集的海明密度峰值聚類中心

Rodriguez等[15]提出的DPC算法是利用數(shù)據(jù)集中樣本的密度信息來(lái)構(gòu)建決策圖，該算法不僅可以避免孤立樣本和噪聲對(duì)基類的影響，還能有效處理具有不規(guī)則形狀的聚類和任意形狀數(shù)據(jù)的特性。

2.5.1 構(gòu)建決策圖

數(shù)據(jù)集X中的樣本xi(i=1,2,…,n)，ρi表示為樣本xi的局部海明密度，即除樣本xi自身以外，與xi的海明度量小于Hc的樣本個(gè)數(shù)。

其中：

參數(shù)Hc( Hc＞0)為截?cái)嗑嚯x（cutoff distance）。

δi是樣本xi到任何比其密度大的其他樣本個(gè)體間的海明度量的最小值，設(shè)的一個(gè)降序排列，即滿足ρq1≥ρq2≥…≥ρqn，則：

若某樣本xi的ρi和δi的取值均較大，則該樣本具有個(gè)體的局部海明密度較周圍樣本更大，且樣本的簇中心離比自身密度更大樣本的距離較遠(yuǎn)，即不同簇中心之間的距離相對(duì)較遠(yuǎn)。因此，利用以ρ為橫軸δ為縱軸的決策圖即可判斷樣本個(gè)體是否可以成為聚類中心。

2.5.2 截?cái)鄥?shù)的選擇

通常DPC算法通過(guò)挑選合適的截?cái)鄥?shù)值，使數(shù)據(jù)集中所有樣本的相鄰平均數(shù)量處于0.01n～0.04n之間。對(duì)不同數(shù)據(jù)集進(jìn)行聚類則需要采用不同的截?cái)鄥?shù)，通常截?cái)鄥?shù)的指定值是以人為經(jīng)驗(yàn)來(lái)確定；這將導(dǎo)致難以確定對(duì)未知數(shù)據(jù)集聚類的截?cái)鄥?shù)[17]。為了解決這一問(wèn)題，這里使用從數(shù)據(jù)集中自動(dòng)提取截?cái)鄥?shù)的方法。文獻(xiàn)[18]中提出了一種基于引力衍生的數(shù)據(jù)場(chǎng)，該數(shù)據(jù)場(chǎng)原理與空間中物體對(duì)其他物體施加引力并同時(shí)被其他物體吸引類似，即數(shù)據(jù)場(chǎng)內(nèi)的數(shù)據(jù)都能獨(dú)立地向外輻射能量并接受其他數(shù)據(jù)所輻射出的能量。基于此，本文采用數(shù)據(jù)空間中描述樣本間共同的交互作用（編碼的相似性）來(lái)計(jì)算截?cái)鄥?shù)。樣本的勢(shì)函數(shù)為：

其中，Hij表示樣本xi與其他樣本xj之間的海明差異值，σ為場(chǎng)影響因子。

當(dāng)數(shù)據(jù)場(chǎng)中的勢(shì)函數(shù)和密度公式都取截?cái)嗪撕瘮?shù)時(shí)，樣本xi在數(shù)據(jù)場(chǎng)中的勢(shì)ψ( )xi和樣本的熵等價(jià)，樣本的勢(shì)越大，熵值越高。則數(shù)據(jù)集的總熵值S為：

在數(shù)據(jù)域中樣本的編碼差異較為均勻，則表明數(shù)據(jù)集分布的不確定性較大，數(shù)據(jù)集的總體熵值較大。若樣本的編碼差異較大，則表明數(shù)據(jù)集分布的不確定性較小，數(shù)據(jù)集的總熵值較小，此時(shí)數(shù)據(jù)集更易于聚類劃分。因此，通過(guò)計(jì)算使數(shù)據(jù)集總熵S達(dá)到最小的影響因子σ，即為對(duì)混合型數(shù)據(jù)集進(jìn)行海明密度峰值聚類的最優(yōu)截?cái)鄥?shù)Hc。

2.6 算法流程

若對(duì)數(shù)據(jù)集X指定K個(gè)簇類的聚類，則基于海明密度峰值的混合數(shù)據(jù)聚類算法（DPCH）的算法流程如下：

步驟1初始化數(shù)據(jù)集，對(duì)數(shù)據(jù)集X中的樣本以二進(jìn)制做規(guī)一化處理并計(jì)算所有屬性的權(quán)重值α，根據(jù)式（7）計(jì)算樣本間的海明度量H( xi,xj)。

步驟2用式（14）計(jì)算截?cái)鄥?shù)Hc，并分別用式（10）和式（12）計(jì)算每個(gè)數(shù)據(jù)樣本xi的局部海明密度ρi和高密度距離δi。

步驟3構(gòu)造以ρ為橫軸，δ為縱軸的決策圖。并選擇前K個(gè)ρ×δ值較大的樣本作為聚類中心點(diǎn)。

步驟4計(jì)算數(shù)據(jù)集中其他樣本與K個(gè)聚類中心點(diǎn)的海明度量，并將與其海明度量最小的聚類中心劃歸一類。

步驟5依據(jù)ρ值的降序過(guò)濾噪聲及離群樣本，其密度不超過(guò)邊界。

步驟6完成聚類并輸出簇類標(biāo)簽。

由樣本間海明密度信息所構(gòu)造的DPCH算法的優(yōu)勢(shì)主要體現(xiàn)為：在統(tǒng)一的環(huán)境下對(duì)混合型數(shù)據(jù)集樣本屬性進(jìn)行編碼，消除了數(shù)值型和分類型屬性之間編碼及評(píng)價(jià)體系的差異；能夠自適應(yīng)混合型數(shù)據(jù)形狀的分布，并且能自動(dòng)確定簇的個(gè)數(shù)。通過(guò)數(shù)據(jù)場(chǎng)勢(shì)函數(shù)自動(dòng)計(jì)算的截?cái)鄥?shù)，避免了人為經(jīng)驗(yàn)造成的差異，提升了聚類的準(zhǔn)確率。

3 實(shí)驗(yàn)與結(jié)果分析

為分析DPCH的性能，本文選取K-Prototypes、GAC、FMC-type三種聚類算法進(jìn)行性能比較。采用的測(cè)試數(shù)據(jù)集包括UCI庫(kù)[19]中的混合型數(shù)據(jù)集和20-News groups庫(kù)[20]中的文本數(shù)據(jù)集。并參照原文獻(xiàn)中的數(shù)據(jù)參數(shù)，使用Python重寫了所有對(duì)比算法。實(shí)驗(yàn)平臺(tái)為：Core i5 3.3 GHz的CPU和8 GB的RAM。采用聚類準(zhǔn)確率以及其穩(wěn)定性（標(biāo)準(zhǔn)差）來(lái)共同評(píng)價(jià)，聚類的正確率（Clustering Accuracy，CA）為：

其中，n為樣本總數(shù)，ai表示第i類中被正確歸類的樣本數(shù)。聚類正確率為聚類樣本個(gè)數(shù)與數(shù)據(jù)集樣本總數(shù)的比值。其結(jié)果為區(qū)間[ ]0,1內(nèi)的正數(shù)，值越大表明聚類效果越好。

3.1 在UCI數(shù)據(jù)集上的比較

選取UCI數(shù)據(jù)庫(kù)中5個(gè)具有代表性的混合型數(shù)據(jù)集（如表1所示）。

表1 實(shí)驗(yàn)中所使用的UCI數(shù)據(jù)集

4種對(duì)比算法分別對(duì)UCI中的5個(gè)混合型數(shù)據(jù)集獨(dú)立運(yùn)行50次，并對(duì)這5種算法在求解不同聚類問(wèn)題時(shí)得到的聚類正確率平均值和標(biāo)準(zhǔn)差進(jìn)行了比較（如表2所示）。

由表1可知，Abalone數(shù)據(jù)集樣本數(shù)量較多且樣本屬性較少，DPCH容易從高密度區(qū)域中發(fā)現(xiàn)聚類中心，取得了與FMC-type算法接近的準(zhǔn)確性。German Credit Data數(shù)據(jù)集是經(jīng)典的混合型數(shù)據(jù)集，對(duì)其研究較為充分，因該數(shù)據(jù)集的簇類數(shù)較少，聚類中心易于確定，各對(duì)比算法均取得了較好的準(zhǔn)確性。Sponge數(shù)據(jù)集的樣本數(shù)量較少且樣本屬性相對(duì)較多，從表2中的結(jié)果來(lái)看，雖然DPCH的準(zhǔn)確率較其他算法占優(yōu)但仍不夠理想。經(jīng)分析，樣本屬性數(shù)量的增加會(huì)導(dǎo)致在二進(jìn)制編碼環(huán)境下樣本個(gè)體的屬性編碼長(zhǎng)度增加，從而在客觀上增加樣本的取值空間，導(dǎo)致各樣本之間的海明差異量相對(duì)降低。同時(shí)，由于數(shù)據(jù)集中樣本數(shù)量較少，DPCH對(duì)數(shù)據(jù)集的局部密度區(qū)分受限，影響算法對(duì)高密度中心的識(shí)別。Poker Hand數(shù)據(jù)集樣本數(shù)量巨大，在測(cè)試中可以看出各對(duì)比算法的準(zhǔn)確率均取得了較好的結(jié)果，這也表明樣本數(shù)量的增加能夠使DPCH更好地識(shí)別高密度中心。KDD Cup 1998 Data為樣本數(shù)和樣本屬性數(shù)均巨大的數(shù)據(jù)集，DPCH相較其他對(duì)比算法準(zhǔn)確率更具優(yōu)勢(shì)，這是因?yàn)槠渌麑?duì)比算法是將數(shù)值型屬性和分類型屬性分別進(jìn)行計(jì)算，并采用降低非占優(yōu)屬性對(duì)數(shù)據(jù)對(duì)象整體相似性的影響來(lái)進(jìn)行相似性計(jì)算，因而會(huì)不斷累積對(duì)不同屬性類型的評(píng)價(jià)偏差。而DPCH能夠針對(duì)混合型數(shù)據(jù)的特點(diǎn)，在統(tǒng)一評(píng)價(jià)體系內(nèi)均衡的評(píng)價(jià)每一維屬性，避免了對(duì)樣本屬性調(diào)整所帶來(lái)的偏差，以此獲得了較好的聚類質(zhì)量。雖然表2中5個(gè)UCI數(shù)據(jù)集的4種對(duì)比算法均沒(méi)有取得完全正確的聚類結(jié)果；但DPCH在聚類正確率這一指標(biāo)上優(yōu)于其他3種對(duì)比算法，表明DPCH能夠有效聚類混合型數(shù)據(jù)且具有占優(yōu)的性能。

聚類的準(zhǔn)確率需要在數(shù)據(jù)類別已知的情況下才能計(jì)算，但實(shí)際情況中數(shù)據(jù)集所包含的類別通常是未知的，因此需要通過(guò)聚類后的類內(nèi)距離和類間距離來(lái)衡量算法聚類的性能[18]。類內(nèi)距離（Average distance Within class，AW）反映的是聚類后同一類別中數(shù)據(jù)關(guān)聯(lián)的緊密程度，距離越小說(shuō)明同類別數(shù)據(jù)的關(guān)聯(lián)度越高。

其中，Ck表示第k個(gè)類，nk表示第k個(gè)類內(nèi)的樣本數(shù)。

類間距離（Average Distance Between classes，AB）反映的是聚類后不同類別數(shù)據(jù)之間的分離程度，距離越大說(shuō)明數(shù)據(jù)類別的分離度越高。

但AW值在不同數(shù)據(jù)集上的變化不一定表明聚類方法性能的改變，也可能是由數(shù)據(jù)樣本本身的平均類內(nèi)距離變化所致，因此文獻(xiàn)[21]中提出一種綜合平均類內(nèi)距離及平均類間距離的聚類判別指數(shù)（Clustering Discriminant Index，CDI）為：

CDI的值由內(nèi)類距離與類間距離的平均比率所決定，因此CDI值越小說(shuō)明聚類算法對(duì)于樣本的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)具有更好的識(shí)別。圖2中為4種對(duì)比算法在5個(gè)UCI數(shù)據(jù)集上的CDI均值。圖中可以看出，DPCH表現(xiàn)出在CDI值上的良好性能。

表2 4種算法在UCI數(shù)據(jù)集上的性能比較

圖2 4種對(duì)比算法CDI值的比較

3.2 對(duì)文本據(jù)集的測(cè)試情況

為進(jìn)一步測(cè)試DPCH在文本型混合數(shù)據(jù)上的性能，本文選擇采用真實(shí)文本數(shù)據(jù)（未做清洗）做為測(cè)試對(duì)象。數(shù)據(jù)來(lái)源于20-News groups庫(kù)中所提供的數(shù)據(jù)集。該數(shù)據(jù)集包含了從20種新聞主題中抽取的20 000篇不同內(nèi)容的消息，平均每個(gè)主題的內(nèi)容為1 000篇新聞。當(dāng)樣本屬性類別沒(méi)有預(yù)先進(jìn)行嚴(yán)格區(qū)分時(shí)，混合型數(shù)據(jù)集中不同的樣本屬性會(huì)對(duì)聚類結(jié)果產(chǎn)生較大影響。本文的測(cè)試中選取了20-News groups語(yǔ)料庫(kù)中3組不同主題的新聞數(shù)據(jù)集，為了更好地測(cè)試聚類算法的性能，每組數(shù)據(jù)所選取的內(nèi)容差異跨度較大。表3中數(shù)據(jù)集A（4）包含了從sci.med等4個(gè)主題獲取的3 795篇新聞；數(shù)據(jù)集B（4）中包含了從comp.graphics等另外4個(gè)主題獲取的3 499篇新聞；數(shù)據(jù)集C（6）中的5 328篇新聞來(lái)源于6個(gè)主題，其中包含了其他數(shù)據(jù)集中已采用過(guò)的數(shù)據(jù)，因此，數(shù)據(jù)集C（6）較其他兩個(gè)數(shù)據(jù)集而言增加了更多的相似內(nèi)容和重疊的語(yǔ)義信息，在數(shù)據(jù)信息一致性更高的情況下，會(huì)導(dǎo)致聚類難度的增加。

表3 實(shí)驗(yàn)中所使用的文本數(shù)據(jù)集

表4～表6分別給出了4種對(duì)比算法在真實(shí)文本數(shù)據(jù)集上的情況，其中包括準(zhǔn)確度（CA）和聚類判別指數(shù)（CDI）的平均值及標(biāo)準(zhǔn)差。

表4 在數(shù)據(jù)集A（4）上的聚類結(jié)果

表5 在數(shù)據(jù)集B（4）上的聚類結(jié)果

表6 在數(shù)據(jù)集C（6）上的聚類結(jié)果

圖3 DPCH在數(shù)據(jù)alt.atheism上的聚類結(jié)果

圖4 DPCH在數(shù)據(jù)comp.graphics上的聚類結(jié)果

文本型混合數(shù)據(jù)集屬于分類型屬性占優(yōu)的數(shù)據(jù)，且對(duì)詞匯和語(yǔ)義的分析不能簡(jiǎn)單地通過(guò)數(shù)值比較或空間距離的方式來(lái)度量差異。表4～表6的結(jié)果表明，DPCH能夠在文本型混合數(shù)據(jù)集上取得良好的聚類結(jié)果，除計(jì)算時(shí)間外，在聚類的準(zhǔn)確率和聚類判別指數(shù)上均明顯優(yōu)于其他對(duì)比算法。在圖3、圖4中，進(jìn)一步給出了DPCH算法在對(duì)文本型混合數(shù)據(jù)集聚類時(shí)，針對(duì)詞匯樣本頻度特征的提取情況。在數(shù)據(jù)集“alt.atheism”及“comp.graphics”中提取了如：islam、muslim、video和pixel等高特征頻度詞匯。由此可見，基于海明度量的聚類算法不但可以有效聚類文本型混合數(shù)據(jù)，也可對(duì)數(shù)據(jù)集中具有較高特征頻度的樣本進(jìn)行分辨，為理解數(shù)據(jù)結(jié)構(gòu)組成及涵義提供支持。

4 結(jié)束語(yǔ)

本文提供了一種能夠處理混合型數(shù)據(jù)的聚類算法。該方法通過(guò)二進(jìn)制的方式對(duì)樣本屬性編碼，數(shù)據(jù)集進(jìn)行規(guī)一化處理。并在此基礎(chǔ)上采用海明度量的方式來(lái)評(píng)價(jià)樣本間相似度，通過(guò)構(gòu)造統(tǒng)一的評(píng)價(jià)體系對(duì)混合型數(shù)據(jù)實(shí)施相似性度量，避免了對(duì)樣本屬性的切割。在聚類過(guò)程中受引力衍生的數(shù)據(jù)場(chǎng)的啟發(fā)，通過(guò)計(jì)算數(shù)據(jù)樣本屬性的熵值，從數(shù)據(jù)集中自動(dòng)提取截?cái)鄥?shù)的方法實(shí)施密度峰值的聚類。UCI數(shù)據(jù)集和文本型混合數(shù)據(jù)集上的對(duì)比測(cè)試結(jié)果表明，DPCH算法可更為準(zhǔn)確地對(duì)混合型數(shù)據(jù)集進(jìn)行類簇識(shí)別。