聚類混合型數據的密度峰值改進算法

譚 陽，唐德權，曹守富

1.湖南師范大學 數學與統計學院，長沙410081

2.湖南廣播電視大學 網絡技術系，長沙410004

3.湖南警察學院 信息技術系，長沙410138

1 引言

聚類作為一種重要的數據分析方法已在許多領域得到廣泛應用，作為機器自動識別數據內在結構的研究重點[1]，聚類的任務是在沒有訓練樣本的情況下，僅利用樣本間的相似性尋找樣本集針對某個評判準則的最佳類別劃分。隨著聚類分析在金融、商業和社會學等領域的應用不斷深入，使用的混合型數據進行聚類的算法研究備受關注[2]。在混合型數據中，大多數樣本的特征表述采用連續型、分類型和順序型屬性[3]，由于三種屬性類型具有不同的特點，為混合型數據建立一個合理可行的相似性度量一直是國內、外學者們研究的重點[4-5]。

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

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

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

2 基于海明密度峰值的混合數據聚類算法

混合型數據由于其度量函數的復雜性，使得早期的聚類算法難以對其進行有效的聚類。近年來，對混合型數據聚類的研究重點在如何度量數據樣本之間的相似性；雖然通過類型劃分屬性的方式可以對樣本屬性的相似性進行分別度量，但始終不能滿足多種數據類型在同一體系內進行評價和處理的要求。

2.1 規一化數據集

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

2.2 樣本屬性的海明距離

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

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

圖1 樣本屬性2維表

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

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

由式（1）可知，屬性AR的編碼長度LR對應該屬性海明距離值hR的取值范圍。顯然，不同屬性的取值范圍并非一致，這必將導致樣本整體評價的非一致性。另外，在實際聚類操作中經常需要凸顯樣本中一些重要的屬性[12]，但這些屬性并不一定具有較長的二進制編碼，因此，需要對不同屬性賦予不同的系數以調整屬性的權重。

2.3 屬性權重

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

此時，將屬性AR看作一個離散隨機型變量，其概率分布如式（4）所示：

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

在完成全部屬性{A1,A2,…,Ad}的評價后，屬性AR的權重值αR由式（6）計算：

2.4 樣本間的海明度量

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

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

可表示為：

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

由式（8）可知，類內樣本的差異值只取決于樣本屬性的海明差異，與屬性的性質無關。以統一的編碼對混合型數據進行海明度量，可消除不同屬性表達類型之間度量量綱的差異性，避免了在多維空間中實施距離比較的復雜計算和評價不同屬性類型的非一致性問題。

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

其中，1-αR表示屬性AR的加權系數，屬性AR的權重值αR越高，樣本間的海明度量越低，樣本間的相似性越高?；旌闲蛿祿诮y一編碼條件下進行編碼，以海明差異作為混合型樣本的比較，將不同屬性間的相似性轉換成離散空間中編碼的海明差異，能夠更加宏觀地反映混合數據中個體與簇類之間的差異性。

2.5 數據集的海明密度峰值聚類中心

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

2.5.1 構建決策圖

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

其中：

參數Hc( Hc＞0)為截斷距離（cutoff distance）。

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

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

2.5.2 截斷參數的選擇

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

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

當數據場中的勢函數和密度公式都取截斷核函數時，樣本xi在數據場中的勢ψ( )xi和樣本的熵等價，樣本的勢越大，熵值越高。則數據集的總熵值S為：

在數據域中樣本的編碼差異較為均勻，則表明數據集分布的不確定性較大，數據集的總體熵值較大。若樣本的編碼差異較大，則表明數據集分布的不確定性較小，數據集的總熵值較小，此時數據集更易于聚類劃分。因此，通過計算使數據集總熵S達到最小的影響因子σ，即為對混合型數據集進行海明密度峰值聚類的最優截斷參數Hc。

2.6 算法流程

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

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

步驟2用式（14）計算截斷參數Hc，并分別用式（10）和式（12）計算每個數據樣本xi的局部海明密度ρi和高密度距離δi。

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

步驟4計算數據集中其他樣本與K個聚類中心點的海明度量，并將與其海明度量最小的聚類中心劃歸一類。

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

步驟6完成聚類并輸出簇類標簽。

由樣本間海明密度信息所構造的DPCH算法的優勢主要體現為：在統一的環境下對混合型數據集樣本屬性進行編碼，消除了數值型和分類型屬性之間編碼及評價體系的差異；能夠自適應混合型數據形狀的分布，并且能自動確定簇的個數。通過數據場勢函數自動計算的截斷參數，避免了人為經驗造成的差異，提升了聚類的準確率。

3 實驗與結果分析

為分析DPCH的性能，本文選取K-Prototypes、GAC、FMC-type三種聚類算法進行性能比較。采用的測試數據集包括UCI庫[19]中的混合型數據集和20-News groups庫[20]中的文本數據集。并參照原文獻中的數據參數，使用Python重寫了所有對比算法。實驗平臺為：Core i5 3.3 GHz的CPU和8 GB的RAM。采用聚類準確率以及其穩定性（標準差）來共同評價，聚類的正確率（Clustering Accuracy，CA）為：

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

3.1 在UCI數據集上的比較

選取UCI數據庫中5個具有代表性的混合型數據集（如表1所示）。

表1 實驗中所使用的UCI數據集

4種對比算法分別對UCI中的5個混合型數據集獨立運行50次，并對這5種算法在求解不同聚類問題時得到的聚類正確率平均值和標準差進行了比較（如表2所示）。

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

聚類的準確率需要在數據類別已知的情況下才能計算，但實際情況中數據集所包含的類別通常是未知的，因此需要通過聚類后的類內距離和類間距離來衡量算法聚類的性能[18]。類內距離（Average distance Within class，AW）反映的是聚類后同一類別中數據關聯的緊密程度，距離越小說明同類別數據的關聯度越高。

其中，Ck表示第k個類，nk表示第k個類內的樣本數。

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

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

CDI的值由內類距離與類間距離的平均比率所決定，因此CDI值越小說明聚類算法對于樣本的基礎數據結構具有更好的識別。圖2中為4種對比算法在5個UCI數據集上的CDI均值。圖中可以看出，DPCH表現出在CDI值上的良好性能。

表2 4種算法在UCI數據集上的性能比較

圖2 4種對比算法CDI值的比較

3.2 對文本據集的測試情況

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

表3 實驗中所使用的文本數據集

表4～表6分別給出了4種對比算法在真實文本數據集上的情況，其中包括準確度（CA）和聚類判別指數（CDI）的平均值及標準差。

表4 在數據集A（4）上的聚類結果

表5 在數據集B（4）上的聚類結果

表6 在數據集C（6）上的聚類結果

圖3 DPCH在數據alt.atheism上的聚類結果

圖4 DPCH在數據comp.graphics上的聚類結果

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

4 結束語

本文提供了一種能夠處理混合型數據的聚類算法。該方法通過二進制的方式對樣本屬性編碼，數據集進行規一化處理。并在此基礎上采用海明度量的方式來評價樣本間相似度，通過構造統一的評價體系對混合型數據實施相似性度量，避免了對樣本屬性的切割。在聚類過程中受引力衍生的數據場的啟發，通過計算數據樣本屬性的熵值，從數據集中自動提取截斷參數的方法實施密度峰值的聚類。UCI數據集和文本型混合數據集上的對比測試結果表明，DPCH算法可更為準確地對混合型數據集進行類簇識別。