自適應多密度峰值子簇融合聚類算法

陳 迪，杜 韜，2，周 勁，2，仵勻政，王心耕

1.濟南大學 信息科學與工程學院，濟南 250024

2.山東省網(wǎng)絡環(huán)境智能計算技術重點實驗室，濟南 250024

聚類作為一種無監(jiān)督的學習方法，只需基于數(shù)據(jù)本身特征計算出數(shù)據(jù)對象間的相似度即可實現(xiàn)數(shù)據(jù)集的劃分[1]。通過聚類處理后，同一簇內(nèi)的數(shù)據(jù)應盡可能相似，不同簇間的數(shù)據(jù)應盡可能相異。目前，聚類算法的研究方向包括基于劃分的聚類[2-3]、基于密度的聚類[4-5]、基于網(wǎng)格的聚類[6-7]、基于模型的聚類[8-9]、深度聚類等[10-11]。K-Means是一種經(jīng)典的基于劃分的聚類算法，首先隨機選取K個點作為初始聚類中心，計算其余點到各中心的距離，進而將其劃分給離它最近的中心所屬簇中，之后基于目標函數(shù)調(diào)整聚類中心的位置以及非中心點的分配結果，直到目標函數(shù)最小[12]。這種基于劃分的聚類算法采用歐式距離最近的劃分原則，因此對非球形簇的聚類效果較差?；诿芏鹊木垲惙椒梢蕴幚砣我庑螤畹拇?。DBSCAN 算法是最具代表性的一種基于密度的聚類算法，該算法將樣本空間劃分為高密度區(qū)域與低密度區(qū)域，將密度相連點的最大集合看作簇[13]。在密度聚類的基礎上，Rodriguez和Laio[14]于2014年提出了一種基于密度峰值的聚類算法DPC（density peak cluster），該算法使用局部密度和上級點（局部密度大于它的最近點）距離作為描述數(shù)據(jù)的兩個特征，構建決策圖來快速選取聚類中心。雖然該算法可以快速選取聚類中心點，且非中心點的分配只需進行一次，但是DPC 算法仍存在缺陷，具體表現(xiàn)在以下幾個方面：（1）DPC算法在計算局部密度時所使用的方法對參數(shù)敏感；（2）在DPC算法的分配階段，易出現(xiàn)連鎖效應，即當局部密度較大的樣本出現(xiàn)分配錯誤時，會導致隸屬于它的樣本發(fā)生同樣的分配錯誤；（3）DPC 及其部分改進算法采用手動選取聚類中心點的方式會導致密度稀疏簇的中心點被忽略，從而影響最終的聚類結果。

為改進局部密度的計算方式，一些學者將K近鄰（KNN）思想引入DPC 中。Du 等人[15]提出了DPC-KNN算法，將局部密度的計算空間縮小至樣本的KNN 鄰域中，不僅減少了計算成本，而且更加精確地描述了樣本的局部密度。Jiang等人[16]同樣使用KNN的思想對上級點距離的計算方式進行改進，使中心點和非中心點之間的差異變大，進而方便中心點的選取。然而，這些引入KNN 對DPC 進行改進的算法，其聚類效果仍受K值大小的影響，當K值過小時，原本存在的鄰域關系會被忽略，導致具有相同特征的樣本被錯誤地劃分為不同簇中。當K值過大時，具有不同特征的樣本會被錯誤地分類到同一簇中[17]。為盡量避免連鎖效應產(chǎn)生，Xie 等人[18]提出了FKNN-DPC算法，使用兩種策略對非中心點進行分配。第一種策略是從聚類中心點開始進行最近鄰廣度優(yōu)先搜索來進行分配，第二種策略利用近鄰加權方法分配離群點和尚未分配的數(shù)據(jù)點。Abdulrahman等人[19]提出了一種基于密度主干的改進算法DPC-DBFN。該方法利用模糊鄰域核來提高聚類的可分性，使用基于密度的KNN 圖來標記主干。在分配時首先分配主干，其次利用KNN方法將邊界點分配給相對應的密度主干區(qū)域。Liu等人[20]提出一種基于共享鄰居的密度峰值聚類算法SNN-DPC。該算法使用共享鄰居關系對局部密度與上級點距離進行重新定義，并提出了兩步分配的方法使算法更具魯棒性。上述方法都在一定程度上緩解了連鎖效應對聚類結果產(chǎn)生的影響。為實現(xiàn)聚類中心點的自動選取，Chen等人[21]提出了一種域自適應密度聚類算法DADC。該算法分別為局部密度和上級點距離設置閾值，規(guī)定大于閾值的點為聚類中心點，該算法還提出了一種聚類融合度模型，通過評估相鄰集群之間的融合度，實現(xiàn)碎片簇的合并。趙力衡等人[22]提出一種去中心化加權簇歸并的密度峰值聚類算法，通過劃分高密度區(qū)域選取核心樣本組，以此取代手動選取聚類中心的方式，最后使用近鄰思想分配剩余樣本點。

目前團隊已解決DPC算法對參數(shù)敏感以及分配過程易出現(xiàn)連鎖效應的缺陷。通過引入自然鄰居思想，不斷擴展鄰域范圍，自適應得到每個點的鄰域關系，之后基于自然鄰居計算樣本的局部密度與上級點距離，避免了人工設定參數(shù)對聚類結果的影響。同時，在分配階段，提出一種兩階段分配策略，首先分配聚類中心附近的密集點形成聚類雛形，再使用隸屬上級點的方式分配剩余點[23]。本文在此基礎上，進一步提出了一種自適應多密度峰值子簇融合聚類（adaptive multi-density peak subcluster fusion clustering，AMDFC）算法。為防止稀疏簇的中心點被忽略，算法提出一種自動選擇策略確定子簇中心。同時，為實現(xiàn)子簇的融合，提出一種K近鄰相似度度量準則，合并相似度高的子簇得到最終的聚類結果，使算法更加適合處理密度不均勻的數(shù)據(jù)集。為驗證該算法的有效性，實驗部分使用聚類精度（ACC）、標準化互信息（NMI）和調(diào)整蘭德指數(shù)（ARI）三項聚類評價指標對不同聚類算法在二維合成數(shù)據(jù)集和UCI 真實數(shù)據(jù)集得到的聚類結果進行對比分析。實驗結果表明，AMDFC算法聚類性能優(yōu)于對比算法。

1 相關工作

1.1 密度峰值聚類算法

密度峰值聚類算法基于兩個前提：（1）聚類中心點的局部密度大于其周圍點的局部密度。（2）不同中心點之間的距離相對較遠。DPC 使用局部密度和上級點距離對數(shù)據(jù)點進行詳細描述。對于局部密度，DPC使用截斷距離或高斯核函數(shù)方法來計算。

其中，n表示數(shù)據(jù)規(guī)模，dij表示數(shù)據(jù)點i和j之間的歐氏距離，dc為截斷距離參數(shù)。上級點距離指的是該點到局部密度大于它且離它最近點的距離，其計算公式如下：

在獲取所有數(shù)據(jù)點的局部密度和上級點距離值后，為快速識別中心點，DPC以ρ為X軸，δ為Y軸繪制決策圖進行中心點的選取，中心點即ρ和δ值大的點。同時，DPC 還提出γ-決策圖的概念。γ值是局部密度與上級點距離的乘積，值越大，該點作為聚類中心點的概率越大。

在挑選出中心點之后，為這些中心點分配不同的標簽，對于非中心點，將其分配給上級點所歸屬的簇中，若上級點尚無所屬的簇，則迭代尋找其上級點完成分配，得到最終的聚類結果。

1.2 自然鄰居

自然鄰居是一種自適應鄰居概念，可以有效解決鄰居關系中鄰域大小選擇的問題[24]。下面對自然鄰居的相關概念進行介紹。

定義1（K最近鄰）設數(shù)據(jù)集為X，待處理的數(shù)據(jù)點為a，則a的K最近鄰為一組對象b，定義如下：

定義2（反向K最近鄰）點a的反向K近鄰為一組對象b，這些對象將a作為它們的K近鄰，定義如下：

定義3（自然鄰居）對于點a，若它的自然鄰居為b，則滿足a和b互為鄰居，定義如下：

定義4（穩(wěn)定狀態(tài)與自然特征值）自然鄰居的獲取是一個逐漸擴大搜索范圍的過程，直到除噪聲點之外，所有數(shù)據(jù)點至少有一個自然鄰居時終止，此時認為該數(shù)據(jù)集達到穩(wěn)定狀態(tài)，此時K的取值稱為自然特征值，用λ表示。

自然鄰居的獲取過程是：首先找到樣本空間中每個數(shù)據(jù)點的K近鄰，根據(jù)反向K近鄰關系確定互鄰居關系，之后不斷擴大K值，直到除噪聲點外，所有點都至少有一個自然鄰居時終止。

算法1自然鄰居搜尋算法

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

輸出：自然特征值λ，各點的自然鄰居。

步驟1初始化K=1，為數(shù)據(jù)集X創(chuàng)建KD 樹，為每個樣本點構造近鄰集合；

步驟2使用KD樹搜索樣本的第K近鄰，并加入到該樣本的近鄰集合；

步驟3利用反向鄰居關系判斷兩樣本點是否互為鄰居，若是則二者建立自然鄰居關系；

步驟4擴大K值，重復步驟2與步驟3，直到所有樣本都至少有一個自然鄰居時停止；

步驟5獲取所有樣本點的自然鄰居，以及全局自然特征值λ。

2 AMDFC算法

AMDFC算法依據(jù)流程可分為四部分：（1）基于自然鄰居計算點的局部密度等度量值；（2）基于自動選取策略選取聚類中心點；（3）基于兩階段分配策略實現(xiàn)非中心點的分配；（4）基于K近鄰相似度實現(xiàn)子簇融合。下面對這四部分內(nèi)容進行詳細介紹。表1 為本文所定義的數(shù)據(jù)符號及其含義。

表1 符號及表示含義Table 1 Symbols and their meanings

2.1 自適應計算數(shù)據(jù)點的局部密度等度量值

原始DPC 算法在計算局部密度時，只考慮數(shù)據(jù)的全局結構而缺少局部分析，因此在處理非均勻密度簇的數(shù)據(jù)集時表現(xiàn)不佳。如圖1所示，該數(shù)據(jù)集由三個不同密度分布的心形簇組成。使用DPC算法對該數(shù)據(jù)集進行處理，當截斷距離取2 時，左上和下方兩個簇被劃分為同一個聚類。當截斷距離取20 時，右上和下方的兩個簇被劃分為同一個聚類。在該數(shù)據(jù)集上，DPC無法選取合適的參數(shù)來準確完成聚類任務。除此之外，DPC算法在計算局部密度時需全體樣本參與，因此當數(shù)據(jù)規(guī)模過大或維度過高時，計算成本大?？紤]樣本點的鄰域信息不僅可以縮小局部密度的計算空間，在一定程度上減小計算成本，同時讓算法更適合處理多密度簇數(shù)據(jù)集。

圖1 DPC算法在多密度數(shù)據(jù)集上的聚類結果Fig.1 Clustering results of DPC on dataset with different density

為考慮樣本鄰域信息且解決參數(shù)敏感問題，本文借助自然鄰居思想自適應獲取數(shù)據(jù)點的鄰域信息，進而計算局部密度等相關度量值。首先自適應獲得樣本自然鄰居，之后計算樣本的局部密度，為使算法適應更多的數(shù)據(jù)分布情況，本文使用三種核函數(shù)分別計算樣本局部密度。

上述公式均滿足樣本的鄰居越多且距離該點越近，該點的局部密度越大。在實驗環(huán)節(jié)，針對不同的數(shù)據(jù)集分別使用三種方法進行計算，并以聚類精度為準，從中選出最優(yōu)的方法來處理該數(shù)據(jù)集。

為使聚類中心點的局部密度更加突出，對Chen 等人[21]提出的域密度定義進行改進，將局部密度更新為局部域密度。

定義5（局部域密度）數(shù)據(jù)點i的局部域密度等于點i的局部密度和其自然鄰居局部密度的加權和。

其中，權重系數(shù)ω為自然鄰居到該樣本距離的倒數(shù)，距離越近，自然鄰居的權重越高，反之，權重越低。由于聚類中心點的自然鄰居數(shù)目多于非中心點，因此使用局部域密度代替局部密度可以使聚類中心點更加突出。

對于每個樣本點，計算其上級點距離：

得到每個數(shù)據(jù)點的局部域密度DD和上級點距離δ后，將二者相乘得到γ值，點的γ值越高，被選取為聚類中心的概率越大。

通過引入自然鄰居思想，算法無需設定K值即可自適應獲取樣本鄰域信息，進而計算樣本的局部密度等度量值，解決了參數(shù)敏感問題。

2.2 聚類中心自動選取策略

原始DPC 算法分別以局部密度ρ和上級點距離δ作為X軸和Y軸構建決策圖，并且人工選取決策圖右上角的點，即局部密度與上級點距離大的點作為中心點。除此之外，還可以選取γ值大的數(shù)據(jù)作為聚類中心。這種方式可以快速發(fā)現(xiàn)大部分數(shù)據(jù)集的聚類中心。然而在一些密度不均勻的數(shù)據(jù)集中，密度較為稀疏簇的聚類中心極易被忽視，這時通過人工選取的聚類中心點可能無法反映真實聚類中心點的分布情況。下面以Jain數(shù)據(jù)集為例進行說明。

Jain數(shù)據(jù)集由兩個簇組成，其中上半部分的簇相較下半部分的簇分布更為稀疏，導致該簇中心點的局部密度較小，從而在手動選取中心點時，該簇的中心點容易被忽略。由圖2（c）得，選出的兩個聚類中心點都分布下半部分的簇中，上半部分簇的中心點并沒有被選取。由圖2（f）可得，即使DPC 選取3 個聚類中心點，仍沒有選取到上半部分簇的點，這導致了較差的聚類結果。由此可見，人工選取聚類中心點的方式由于受先驗知識的影響，在中心點的選取數(shù)量上一般接近真實簇的數(shù)量。但在一些密度分布不均勻的數(shù)據(jù)集上，一些密度較稀疏的簇中心因其γ值相對較小，容易被忽略。針對這一問題，提出一種聚類中心點自動選取策略，設定一個參數(shù)c，在得到所有樣本點的γ值后，選取γ值前c%的點作為聚類中心點。該策略的意義在于保證密度稀疏簇的中心點盡可能被選取。以Jain數(shù)據(jù)集為例，圖3 為該數(shù)據(jù)集的γ決策圖，圖中分別標注了降序排列后第1%，第2%，第3%，第4%和第5%的點，可以看到，γ值排在5%后的點分布平穩(wěn)，這些點成為中心的概率極低。經(jīng)大量實驗后確定當c的取值范圍在1%～5%之間時，大部分數(shù)據(jù)集的所有簇中心點都能被選取。下面對局部密度等度量值的計算以及聚類中心的選取流程進行介紹：

圖2 手工選取聚類中心在Jain數(shù)據(jù)集上的聚類結果Fig.2 Clustering results of manually selected cluster centers on Jain dataset

圖3 Jain數(shù)據(jù)集γ 決策圖Fig.3 Jain dataset γ Decision graph

算法2度量值計算及中心點選取

輸入：數(shù)據(jù)集X，聚類中心點比例參數(shù)c，自然鄰居。

輸出：局部域密度DD、上級點距離δ、γ值，中心點。

步驟1計算樣本點之間的歐氏距離；

步驟2根據(jù)式（8）或式（9）或式（10）計算樣本點局部密度ρ；

步驟3根據(jù)式（11）計算樣本局部域密度DD；

步驟4根據(jù)式（12）計算樣本上級點距離δ；

步驟5根據(jù)式（13）計算樣本局部域密度與上級點距離乘積γ；

步驟6選取γ值前c%的數(shù)據(jù)點作為初始聚類中心點。

2.3 兩階段分配策略

在得到聚類中心點后，需要完成非中心點的分配任務。原始DPC算法需要通過迭代查找上級點的方式確定非中心點的歸屬，此時若一個密度較大的上級點出現(xiàn)分配錯誤，則隸屬于它的點也會產(chǎn)生同樣的分配錯誤，這種現(xiàn)象稱為連鎖效應。為了降低連鎖效應出現(xiàn)的概率，需要盡量減少上級點的迭代查找次數(shù)。本文提出一種兩階段的分配策略。提出了稠密點的概念，稠密點指圍繞在中心點周圍且自然鄰居較多的點。在分配時首先將中心點的標簽分配給稠密點得到聚類雛形，聚類雛形的生成意味著非中心點的分配無需多次迭代即可找到對應的上級點，之后再使用尋找上級點的方式完成第二步分配，得到聚類結果。

定義6（稠密點）自然鄰居數(shù)大于等于自然特征值一定比率的點為稠密點。

第一步分配策略采用擴散的方式，首先將中心點的標簽擴散給它自然鄰居中的稠密點，之后若稠密點的自然鄰居也為稠密點，則將標簽進一步擴散。不斷重復此過程直到所有的稠密點都分配完畢后停止。經(jīng)過第一步分配，各簇形成聚類雛形。第二步采用隸屬于上級點所在簇的方法完成剩余數(shù)據(jù)點的分配任務，由于聚類雛形已經(jīng)形成，上級點不需多次迭代即可找到，從而降低連鎖效應出現(xiàn)的概率。下面給出兩步分配策略流程：

算法3兩步分配策略

輸入：比率參數(shù)α。

輸出：聚類結果。

步驟1將所有樣本點置于未分配狀態(tài)；創(chuàng)建一個稠密點隊列Dense，所有聚類中心入隊；

步驟2從稠密點隊列中取一個點，對其自然鄰居進行判斷，若滿足稠密點條件且處于未分配狀態(tài)，則將中心點標簽擴散給它并將它加入隊列；

步驟3重復步驟2，直到所有稠密點分配完畢；

步驟4針對未分配數(shù)據(jù)點，使用隸屬于上級點的方式完成第二步分配；

步驟5得到聚類結果。

圖4 以Aggregation 數(shù)據(jù)集為例展示了兩階段分配過程。Aggregation 數(shù)據(jù)集包含了七個凸狀簇。圖4（a）為數(shù)據(jù)集分布情況。首先找到數(shù)據(jù)集中的稠密點，將聚類中心點的標簽擴散式分配給其稠密點。圖4（b）為經(jīng)第一步分配后得到的結果，可以看到此時每個簇的雛形已經(jīng)生成。第二步分配采用隸屬上級點所在簇的方法分配剩余點，圖4（c）為兩階段分配得到的最終聚類結果。經(jīng)過兩次分配之后數(shù)據(jù)被成功劃分為七個簇，證明該方法提升了分配效果，并且由于減少了上級點迭代查詢次數(shù)，因此在一定程度上減少了運行成本。

圖4 兩階段分配策略在Aggregation數(shù)據(jù)集上的聚類過程Fig.4 Clustering process of two-stage allocation strategy on Aggregation dataset

2.4 基于K近鄰相似度的子簇融合策略

通過上述分配步驟已得到初步聚類結果。此時，若c值較大，則生成簇的數(shù)量大于真實簇的數(shù)量，需要對子簇進行融合。子簇融合的依據(jù)是子簇之間的相似度，目前簇間相似度一般通過簇間平均距離、最大距離、最小距離等方法進行衡量，然而這類方法易受噪聲點的影響。針對該問題，提出一種K近鄰相似度的度量指標來測量子簇之間相似度。這里的K值一般設定為數(shù)據(jù)集的自然特征值λ。通過計算簇之間點的K近鄰相似度得出子簇之間的相似度，若子簇間的相似度大于規(guī)定閾值st（similarity threshold），則將兩子簇融合。之后不斷迭代直到?jīng)]有兩子簇的K近鄰相似度高于閾值時停止，得到最終的聚類結果。

定義7（K近鄰相似度）對于簇A中的點i，若i的K近鄰有一部分落在簇A中，另一部分落在簇B中，則證明簇A與簇B是相鄰的，這種點越多，證明兩個子簇越相似。

上述公式中，s(i,A→B)∈[0,1]，其中|KNN(i,A)|表示點i的K近鄰落入簇A的數(shù)量，|KNN(i,B)|表示點i的K近鄰落入簇B的數(shù)量，二者越接近，公式的值越接近1，二者相差越大，值越接近0。簇A和簇B的K近鄰相似度由下面公式計算，由于K近鄰相似度不具有對稱性，因此簇A和簇B的相似度等于簇A和簇B中所有點的K近鄰相似度之和，值越大表示兩子簇越相似。：

在計算出兩兩子簇的K近鄰相似度后，選出最相似的兩子簇，若其相似度大于規(guī)定閾值，則將兩簇融合得到全新的簇。之后不斷進行迭代融合，直到最大的子簇相似度小于閾值時停止。下面給出子簇融合流程。

算法4基于K近鄰相似度的子簇融合策略

輸入：融合閾值st。

輸出：聚類結果。

步驟1根據(jù)式（15）與式（16）計算兩兩子簇的K近鄰相似度，選出其中的最大值Smax；

步驟2判斷Smax是否大于融合閾值st，若滿足條件，則將子簇融合；

步驟3重復步驟1 和步驟2，直到?jīng)]有滿足融合條件的兩子簇；

步驟4得到聚類結果。

下面以Jain 數(shù)據(jù)集為例展示子簇融合過程。實驗設定c=4，即取γ值前4%的點作為聚類中心點進行分配，得到的初步聚類結果如圖5（a）?？梢钥吹浇?jīng)過兩步分配策略，共生成12 個初始子簇。之后計算子簇間的K近鄰相似度并進行子簇融合，得到最終的兩個簇。圖5（b）～（h）為選取的部分融合過程，圖5（i）表示最終的聚類結果，可以看到，該方法實現(xiàn)了對Jain 數(shù)據(jù)集的準確劃分。

圖5 Jain數(shù)據(jù)集子簇融合過程Fig.5 Sub cluster fusion process of Jain dataset

下面對算法各環(huán)節(jié)的時間復雜度進行分析。假設數(shù)據(jù)集中數(shù)據(jù)對象個數(shù)為n，使用KD樹搜索樣本近鄰所消耗的時間為O()nlbn，因此自然鄰居搜索的時間復雜度為O()nlbn。借助自然鄰居計算局部密度等度量值的時間復雜度為O(n2)，分配階段需遍歷所有數(shù)據(jù)點，因此時間復雜度為O(n2)。在子簇融合階段，需計算每個子簇與其余子簇間的相似度。假設初始聚類數(shù)為m，該環(huán)節(jié)的時間復雜度為O()。綜上，算法整體時間復雜度為O(n2)。

3 實驗結果與分析

實驗部分使用7個二維合成數(shù)據(jù)集與4個UCI真實數(shù)據(jù)集測試算法性能，其中二維合成數(shù)據(jù)集包括不同形狀與不同規(guī)模的數(shù)據(jù)，表2 和表3 對這些數(shù)據(jù)集進行介紹。聚類結果使用聚類精度（ACC），標準化互信息（NMI）以及調(diào)整蘭德系數(shù)（ARI）3 個指標進行對比，ACC 與NMI 指標的取值范圍為[0，1]，ARI 指標的取值范圍為[-1，1]。值越接近1表示算法性能越好。對比算法包括K-Means、DBSCAN、DPC[14]以及近年來對DPC進行改進的算法（FKNN-DPC[16]、SNN-DPC[20]、DBFN[19]、FSDPC[25]），還包括一種深度嵌入式聚類算法IDEC[26]。在參數(shù)設置環(huán)節(jié)，本文提出的算法需要設定聚類中心比例參數(shù)c，稠密系數(shù)a以及簇融合閾值st。對比算法中，K-Means算法需設定聚類個數(shù)，DBSCAN算法需設定鄰域半徑以及最小數(shù)據(jù)點數(shù)，DPC 與FSDPC 算法需給定聚類中心數(shù)量以及截斷距離，F(xiàn)KNN-DPC 與SNN-DPC算法需要給定聚類中心數(shù)量以及鄰域大小，DBFN算法需給定聚類中心數(shù)量、鄰域大小以及邊界點閾值。對于IDEC 算法的訓練過程，采用小批量樣本進行隨機梯度下降和反向傳播，KL 散度聚類系數(shù)設置為1，學習率設置為0.001。

表2 二維合成數(shù)據(jù)集詳細信息Table 2 2D synthetic dataset details

表3 UCI數(shù)據(jù)集詳細信息Table 3 UCI dataset details

3.1 二維合成數(shù)據(jù)集實驗結果

本節(jié)選取7個二維合成數(shù)據(jù)集用于算法性能測試，這些數(shù)據(jù)集由多個任意形狀與非均勻密度簇組成。表4為AMDFC 與對比算法的聚類評價指標對比。其中KMeans算法適合處理球形簇，R15數(shù)據(jù)集由15個球形簇構成，因此K-Means 算法在該數(shù)據(jù)集上表現(xiàn)最優(yōu)，在其余含有非球形簇數(shù)據(jù)集上的聚類效果較差。DBSCAN算法能夠識別任意形狀的簇，但是該算法需設定全局參數(shù)，因此不適合處理變密度數(shù)據(jù)集，在3circles、Smile、Twomoons、R15 這些密度均勻的數(shù)據(jù)集上DBSCAN 聚類效果較好，但在Jain等密度不均勻的數(shù)據(jù)集上效果較差。原始DPC 算法忽視了鄰域信息，且手工選取中心點的方式容易忽略密度稀疏簇的中心，因此在Jain、3circles、Smile、Twomoons 等數(shù)據(jù)集上效果并不理想。FKNN-DPC、DBFN、SNN-DPC以及FSDPC算法雖然考慮樣本的鄰域信息，聚類效果相比DPC算法有所提升，但這些算法沒有實現(xiàn)簇中心自動選取，處理多密度數(shù)據(jù)集的能力較差。IDEC算法除在R15數(shù)據(jù)集上性能最優(yōu)之外，在其余數(shù)據(jù)集上表現(xiàn)均沒有達到最優(yōu)，這是因為神經(jīng)網(wǎng)絡聚類算法常用于處理高維文本及圖片數(shù)據(jù)集，數(shù)據(jù)集的維度越大，相應的優(yōu)化參數(shù)就越多，神經(jīng)網(wǎng)絡的擬合能力就會越強，因此在低維空間中神經(jīng)網(wǎng)絡聚類的性能較差。AMDFC 算法很好地實現(xiàn)了任意形狀及密度數(shù)據(jù)集的聚類任務，由表可得，該算法在Jain、3circles、Smile、Twomoon數(shù)據(jù)集上聚類精度等指標均達到1，在Aggregation 與Pathbased 數(shù)據(jù)集上，算法同樣表現(xiàn)出最優(yōu)性能。在R15數(shù)據(jù)集上雖未表現(xiàn)出最優(yōu)性能，但是與最優(yōu)算法的精度差距不大。圖6～圖9 分別展示了不同算法在Jain、3cirles、Smile 以及Twomoons 數(shù)據(jù)集上的聚類結果。其中（a）～（h）分別表示K-Means、DBSCAN、DPC、FKNN-DPC、SNN-DPC、DBFN、FSDPC以及AMDFC 算法的聚類結果。為避免樣本順序對IDEC 聚類結果產(chǎn)生影響，在每一輪訓練時均打亂原始數(shù)據(jù)順序，隨機打亂后的樣本更接近真實分布。若不打亂樣本順序，使用排序的樣本進行訓練會使神經(jīng)網(wǎng)絡學習樣本順序，從而影響泛化能力。每輪打亂后的順序是未知的，無法使樣本與標簽對齊，有關IDEC的聚類結果在表格中以數(shù)據(jù)形式進行展示。

圖6 Jain數(shù)據(jù)集聚類結果Fig.6 Clustering results of Jain dataset

圖7 3circles數(shù)據(jù)集聚類結果Fig.7 Clustering results of 3circles dataset

圖7 （續(xù)）

圖9 Twomoons數(shù)據(jù)集聚類結果Fig.9 Clustering results of Twomoons dataset

圖9 （續(xù)）

表4 各聚類算法在合成數(shù)據(jù)集上的評價指標對比Table 4 Comparison of evaluation indicators of various clustering algorithms on synthetic datasets

3.2 UCI數(shù)據(jù)集實驗結果

本節(jié)選取4個UCI數(shù)據(jù)集用于算法性能測試。表5為AMDFC與各對比算法的評價指標比較。其中，Iris數(shù)據(jù)集分布相對均勻，因此在該數(shù)據(jù)集上AMDFC 算法性能略低于對比算法，但仍較好地完成了數(shù)據(jù)集的劃分。E-coli 數(shù)據(jù)集密度分布不均勻，適合使用本文提出的算法進行處理，實驗結果表明AMDFC 在E-coil 數(shù)據(jù)集上三項指標均達到最優(yōu)。同樣的，AMDFC 算法在Heart failure clinical數(shù)據(jù)集上聚類精度達到最優(yōu)，在Banknote authentication 數(shù)據(jù)集上聚類精度與標準化互信息最優(yōu)。綜上，AMDFC方法在處理任意形狀與非均勻密度數(shù)據(jù)集時表現(xiàn)出了優(yōu)異的聚類性能。

表5 各聚類算法在UCI數(shù)據(jù)集上的評價指標對比Table 5 Comparison of evaluation indicators of various clustering algorithms on UCI datasets

4 結束語

針對密度峰值聚類算法存在的不足，提出一種自適應多密度峰值子簇融合聚類算法。第一，將自然鄰居的概念引入密度峰值聚類算法中，在計算局部密度時考慮樣本點的鄰域信息，自然鄰居具有的自適應特點解決了參數(shù)敏感的問題。第二，針對密度分布稀疏簇的中心點不易被發(fā)現(xiàn)的問題，提出一種聚類中心點自動選取策略，通過擴大選取范圍來盡量使得所有簇的中心都被選取。第三，在非中心點的分配階段，使用兩階段分配策略，通過對稠密點進行首次分配形成聚類雛形，降低了分配過程中連鎖反應出現(xiàn)的概率。第四，由于聚類中心的選取范圍擴大，生成的簇數(shù)大于真實簇的數(shù)量，因此定義了一種K近鄰相似度計算子簇間的相似度，并將相似度高的子簇進行融合，生成最終聚類結果。實驗結果表明，AMDFC算法可以很好地對任意形狀及非均勻密度數(shù)據(jù)集進行聚類。下一步的工作重點是將該算法應用到高維復雜數(shù)據(jù)以及流數(shù)據(jù)環(huán)境中，適配更多的實際應用環(huán)境。