基于密度峰值的混合型數據聚類算法設計

李　曄，陳奕延，張淑芬

(1.中國市場學會 服務質量專業委員會，北京 100048；　2.河北省數據科學與應用重點實驗室(華北理工大學)，河北 唐山 063210)(*通信作者電子郵箱townjam_sovietnia@163.com)

0　引言

隨著互聯網技術的迅速發展，人們采集與獲取信息的能力大大提高。當海量信息出現時，人們希望從繁多復雜的數據中得到有價值的信息。聚類分析是數據挖掘中一個極其重要的分支。文獻[1]指出聚類是一個把數據對象劃分成子集的過程，每個子集是一個簇，使得簇中的對象彼此相似，但與其他簇中的對象不相似。

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

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

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

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

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

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

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

該想法是整個聚類過程的基礎，找到簇中心以后，也就自動確定了簇的個數。對于任意一個非簇中心數據點i，認為點i跟所有比它密度更大的點中與之距離最近的那個點屬于同一個簇。該算法中簇的分配在一步中完成，這與那些通過迭代來優化目標函數的算法是不同的。

1.1　相關定義

(1)

1.1.1計算ρi

計算密度時常用的核函數包括截斷核(Cut-off kernel)、高斯核(Gaussian kernel)和指數核(Exponential kernel)，它們的定義分別如下：

(2)

(3)

(4)

式(2)～(4)中的參數dc>0為閾值(截斷距離)，需由使用者事先指定。

1.1.2計算δi

ρq1≥ρq2≥…≥ρqN

(5)

然后定義

(6)

至此，對于S中的每個數據點xi，可利用式(2)、 (3)或(4)以及式(6)為其計算(ρi,δi)(i∈IS)。

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

1.2　算法步驟及流程

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

步驟1初始化及預處理。

1)給定用于確定閾值(截斷距離)dc的參數t∈(0,1)。

2)給定權值γ。

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

4)確定閾值dc。

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

步驟3對非簇中心數據點進行歸類。

注1：當處理某個xqi時，若所有比xqi密度大的點到xqi的距離都相等，則把xqi隨機分配到一個xqj(j

步驟4若nc>1，則將每個簇中的數據點進一步分為“簇核心”和“簇光暈”。

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

2)確定每個簇的邊界區域。這個區域中的數據點定義如下：它們屬于該簇，且在與其距離不超過dc的范圍內，存在屬于其他簇的數據點。

1.3　算法復雜度分析

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

2　閾值和權值的選取

從以上論述可知，新算法中可能影響最終聚類結果的因素主要有兩個： 1)密度公式中的閾值(截斷距離)dc；2)距離公式中的權值γ。接下來需進一步討論并驗證這兩個因素對聚類結果的影響，并給出一個相對合理的方式來選取這兩個參數，以達到最理想的聚類效果。

2.1　閾值dc的選取

對于dc的選取，文獻[11]給出了一種一般性的方法：選取一個dc，使每個數據點的平均“鄰居”個數大約為數據點總數的1%～4%，這里的“鄰居”是指與其距離不超過dc的點，具體的比例通常根據研究人員的經驗和實際的數據集而定。

以上方法需要根據個人實際經驗來確定dc，但通過下文的實驗(這些實驗的細節會在2.1.3節中介紹)可以看到，聚類結果會受到閾值dc的影響，而根據經驗很難估計出最優的閾值dc。對同一數據集，若閾值的經驗估計值不同，則聚類的結果可能也不同。

為了解決這一問題，使用數據場中的勢熵從混合型數據集中自動提取最優的閾值dc。文獻[17]提出用數據場去描述數據空間中對象之間共同的交互作用，同時文獻[18-19]指出對于同樣的參數，數據點在稠密區域有較高的勢而在稀疏區域有較低的勢。

可用于計算勢的勢函數有很多種，如高斯核、指數核、截斷核等。接下來介紹如何通過數據場中的勢熵計算出在不同勢函數和不同數據集下的最優閾值。

2.1.1數據場

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

(7)

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

2.1.2利用數據場提取最優的截斷距離

在式(7)中，如果數據場是一個標量場，則mj=1，當K(x)選擇高斯核函數時，xi-xj變成dij，dij表示點xi和xj之間的某種距離，那么每一個點的勢φi由如下公式計算：

(8)

圖1　原始數值型數據集和加入類標號的數據集ⅠFig. 1　Original numeric data set and data set with the class label Ⅰ

圖2　原始數值型數據集和加入類標號的數據集ⅡFig. 2　Original numeric dataset and dataset with class label Ⅱ

如果式(8)中的dij和新算法中dij的度量方式相同，并且如果新算法在計算密度時也選取高斯核函數，那么點xi在數據場中的勢φi和在新算法中的密度ρi是等價的，也就是說式(8)與式(3)是等價的。

同理，當數據場中的勢函數和密度公式都取為截斷核函數或指數核函數時，點xi在數據場中的勢φi和在新算法中的密度ρi是也等價的。因此在尋找密度峰值的聚類算法中，閾值dc的最優化問題可以轉化為數據場中影響因子σ的最優化問題。我們希望找到一個影響因子σ使得隨機變量的不確定性達到最小。

在信息論與概率統計中，熵[20]是隨機變量不確定性的度量,熵越大，隨機變量的不確定性越大。

設X是一個取有限個值的離散隨機變量，其概率分布為:

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

(9)

則隨機變量X的熵定義為:

(10)

因此，可以使用熵來最優化σ。對于數據集X，如果數據場中每個點的勢為{φ1,φ2,…,φn}，則熵H的定義如式(11)：

(11)

由于取相同的核函數時，數據場中的影響因子σ與新算法中密度公式里的閾值dc等價,因此通過計算使熵H達到最小的影響因子σ，就可以得到尋找密度峰值聚類算法中的最優閾值dc。

2.1.3實驗和分析

為了更加直觀地看到選取不同閾值時的聚類結果，且為了驗證基于數據場的方法提取最優閾值的合理性，本節使用具有兩個數值型和一個分類型屬性的混合型數據集進行模擬，數據的記錄按照如下方法產生。

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

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

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

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

圖3　原始數值型數據集和加入類標號的數據集ⅢFig. 3　Original numeric dataset and dataset with class label Ⅲ

圖4　數據集Ⅰ對于選取不同閾值的聚類結果Fig. 4　Clustering results with different thresholds for dataset Ⅰ

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

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

2.2　權值γ的選取

對于混合型數據的聚類，距離公式中分類型屬性權值γ的選取也會直接影響到最終的聚類效果，通常為了簡單起見，可以取γ=1，即兩種屬性的權重相等。文獻[3]指出混合型數據距離公式中權值γ的選取依賴于數值型屬性的分布，即權值γ的選取依賴于數值型屬性的平均標準差σ，但該文獻并未給出具體應如何選取以及這樣選取的依據。因此本節對權值γ的選取提出一個新的方法。

表1　利用兩種不同方法選取閾值時移除噪聲點的個數Tab. 1　Number of removed noise points with different threshold selected by two different methods

2.2.1聚類趨勢

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

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

2.2.2數值型數據集的聚類趨勢

對于給定的混合型數據集，將其中的數值部分取出構成一個數值型數據集，然后將該數據集與其在數據空間中的均勻分布進行比較，以此評估該混合型數據集中數值部分的聚類趨勢?；羝战鹚菇y計量可用來度量數值型數據集的聚類趨勢。

霍普金斯統計量[1]是一種空間統計量，檢驗空間分布的變量的空間隨機性。給定混合型數據集D，取出其中的數值型部分組成一個數值型數據集Dr，它可以看作隨機變量Z的一個樣本，想要確定Z在多大程度上不同于數據空間中的均勻分布，可以根據文獻[1]中總結的步驟來計算:

(12)

(13)

3)計算可度量數值型數據集聚類趨勢的統計量Hr(霍普金斯統計量的變形)。

(14)

2.2.3分類型數據集的聚類趨勢

受到可度量數值型數據集聚類趨勢的霍普金斯統計量的啟發，對于分類型數據集，同樣可以提出一個用來度量其聚類趨勢的統計量Hc。

Hc是一個可以評估分類型數據分布隨機性的統計量。給定混合型數據集D，取出其中的分類型部分組成一個分類型數據集Dc，然后按以下步驟計算:

(15)

(16)

3)計算可度量分類型數據集聚類趨勢的統計量Hc:

(17)

2.2.4權值γ的計算

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

γ=Hr/Hc

(18)

2.2.5實驗與分析

為了更加直觀地看到選取不同權值時的聚類結果并且驗證利用聚類趨勢定義權值的合理性，使用一個新的僅有三個屬性的混合型數據集Ⅳ進行模擬，屬性中有兩個數值型和一個分類型，這些數據記錄按如下的方式產生。

首先生成一組二維數據點，這組數據包含400個點且是一個正態分布(圖5(a))；然后通過給每個點加入一個分類值把這些點擴展到三維(圖5(b))。對于這個數據集我們人為地把它分成四個部分：用以(0,0)為坐標原點的坐標軸把區域分成左上、左下、右上、右下，因此給每部分中的大多數點分配一個分類值，使得擁有這個分類值的點數與擁有其余分類值的點數大致相等。舉個例子，在圖5(b)中右上角的部分大多數點被分配屬性值A并且這部分其余的點被分配B、C或者D。

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

圖5　原始數值型數據集和加入類標號的數據集ⅣFig. 5　Original numeric dataset and the dataset with class label Ⅳ

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

3　實證分析

為了進一步對提出的尋找密度峰值聚類算法進行驗證，本章使用一些實際數據集進行測試，并對實驗結果進行分析。

3.1　數據集的選取

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

3.2　評價指標

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

(19)

其中：k為該數據集真實的類的個數，corr_ci表示第i個類中被正確聚類的樣本個數，|D|為該數據集的樣本個數。

由此看出，ac_rate值越大，聚類效果越好。當聚類結果與已知類標號完全一致時，取得最大值1。

圖6　數據集Ⅳ對于不同的權值的聚類結果Fig. 6　Clustering results of different weights in dataset Ⅳ

圖7　數據集Ⅳ的一個合理權值的聚類結果Fig. 7　Clustering result of reasonable weight of the dataset Ⅳ

表2　實際數據集描述Tab. 2　Real dataset description

3.3　實驗結果

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

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

4　結語

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

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

參考文獻:

[1]HAN J W, KAMBER M, PEI J. 數據挖掘：概念與技術[M].范明,孟小峰,譯.3版.北京：機械工業出版社,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]冀進朝.針對多維混合屬性數據的聚類算法研究[D].長春:吉林大學,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].大連理工大學學報,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]孫浩軍,高玉龍,閃光輝,等.基于熵權法的混合屬性聚類算法[J].汕頭大學學報(自然科學版),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]趙興旺,梁吉業.一種基于信息熵的混合型數據屬性加權聚類算法[J].計算機研究與發展,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聚類算法初始點選取方法的改進[J].計算機科學,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]蔣禮青,張明新,鄭金龍,等.快速搜索與發現密度峰值聚類算法的優化研究[J].計算機應用研究,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]馬春來,單洪,馬濤.一種基于簇中心點自動選擇策略的密度峰值聚類算法[J].計算機科學,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]詹春霞,王榮波,黃孝喜,等.基于改進CFSFDP算法的文本聚類方法及其應用[J].數據分析與知識發現,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]李航.統計學習方法 [M].北京:清華大學出版社,2012:60. (LI H. Method of Statistical Learning [M]. Beijing: Qinghua University Press, 2012: 60.)

[21]陳奕延.《基于密度峰值的混合型數據聚類算法設計》——聚類效果彩色圖[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.