自適應聚類中心策略優(yōu)化的密度峰值聚類算法

徐童童，解 濱，3，張喜梅，張春昊

1.河北師范大學 計算機與網(wǎng)絡空間安全學院，石家莊 050024

2.河北師范大學 河北省網(wǎng)絡與信息安全重點實驗室，石家莊 050024

3.河北師范大學 供應鏈大數(shù)據(jù)分析與數(shù)據(jù)安全河北省工程研究中心，石家莊 050024

聚類是根據(jù)樣本之間的相似性度量，將數(shù)據(jù)集劃分為多個類簇的過程。聚類結(jié)果使相同簇中的樣本具有高度的相似性，不同類簇的樣本具有較大的相異性。聚類是機器學習中一種重要的無監(jiān)督數(shù)據(jù)分析方法[1]，借助聚類可以揭示數(shù)據(jù)中隱藏的規(guī)律，已廣泛應用在社會網(wǎng)絡、統(tǒng)計學、模式識別和信息檢索等領(lǐng)域[2-5]。

在過去的幾十年里，許多學者針對不同的應用開發(fā)了大量的聚類算法。包括基于劃分、基于層次、基于網(wǎng)格、基于密度以及基于圖論的聚類算法[6-9]?；趧澐值腒-means[10]聚類算法在凸球形結(jié)構(gòu)的數(shù)據(jù)集上取得了良好的聚類效果，但其參數(shù)k需要預先指定，且嚴重依賴于初始聚類中心，無法找到任意形狀的簇，聚類容易受到噪聲或離群點的影響?；诿芏鹊腄BSCAN[11]算法對不規(guī)則類簇有很好的聚類結(jié)果，且不容易受到噪聲點和離群點的影響，但處理密度差異較大的聚類和高維數(shù)據(jù)，聚類結(jié)果較差。此外，聚類結(jié)果對半徑Eps和密度閾值MinPts的選擇較為敏感。近鄰傳播算法聚類算法AP（Affinity Propagation）[12]將每個樣本點看作圖的一個頂點，通過反復迭代傳遞近鄰樣本之間的信息，尋找最優(yōu)類簇集合，該算法不需要預先設置中心點數(shù)目，但不能發(fā)現(xiàn)任意形狀的簇且時間復雜度較高。

2014年Rodriguez等人[13]在Science上發(fā)表了基于密度聚類的密度峰值聚類（density peaks clustering，DPC）算法。與傳統(tǒng)聚類算法相比，該算法可識別出任意形狀的簇，能夠直觀地找到聚類中心，并高效進行樣本點分配和離群點剔除，聚類準確率和計算效率均得到明顯提高。此外，該算法參數(shù)唯一，無需迭代，具有很好的魯棒性。然而，DPC 算法也存在一些不足，如對于數(shù)據(jù)集規(guī)模不同，采用的局部密度度量方式不統(tǒng)一；參數(shù)截斷距離dc的選取會在一定程度上影響聚類結(jié)果；利用決策圖選擇聚類中心點具有很強的人為主觀性；單一分配策略也使非聚類中心點分配時容易產(chǎn)生連帶錯誤。

針對DPC 算法的不足之處，近年來有關(guān)于DPC 算法的優(yōu)化算法不斷涌現(xiàn)[14-17]，這些優(yōu)化算法主要表現(xiàn)在局部密度的重新度量、聚類中心的自動確定以及分配策略的優(yōu)化。謝娟英等人[18]提出了一種結(jié)合k近鄰信息的KNN-DPC算法，將DPC算法度量樣本局部密度的兩種準則進行統(tǒng)一，提出新的適應于不同規(guī)模數(shù)據(jù)集的統(tǒng)一的、沒有截斷距離影響的樣本局部密度度量準則，同時在對非聚類中心點進行分配時，引入樣本k近鄰信息，采用兩步分配策略，極大地提高了聚類的準確率。然而在選擇聚類中心時，仍按照決策圖主觀選擇。Liu等人[19]提出了基于k近鄰的自適應密度峰值聚類算法（ADPC-KNN），該算法基于k近鄰的思想重新定義截斷距離dc和局部密度ρ，擴大了每個核心對象的密度與邊界區(qū)域其他對象的差異，實現(xiàn)了初始聚類中心的自動選擇，但對k近鄰引入的參數(shù)k所帶來的不確定性還是不能避免。李濤等人[20]提出了一種自動確定聚類中心的密度峰聚類算法（ADPC）。根據(jù)樣本γ值繪制排序圖，通過確定“拐點”，將大于該點的γ值對應的點作為潛在聚類中心點，最終，從潛在聚類中心中“篩選”出實際聚類中心，但在處理密度不均勻數(shù)據(jù)集時，無密度峰簇內(nèi)聚類中心難以發(fā)現(xiàn)。王萬良等人[21]提出了自動確定聚類中心的快速搜索和發(fā)現(xiàn)密度峰值的聚類算法（CFSFDP），確定密度和距離閾值上限，根據(jù)決策函數(shù)實現(xiàn)中心點的自動選擇。然而該算法沒有考慮截斷距離dc對局部密度度量的影響，以及切比雪夫不等式引入了新的參數(shù)ε，不同的數(shù)據(jù)集ε選取可能會不同，不具有普適性。Liu等人[22]提出了一種基于共享近鄰密度峰值聚類算法（SNN-DPC），該算法基于共享近鄰提高了DPC算法在多尺度、交叉纏繞以及變化密度數(shù)據(jù)集上的優(yōu)越性能，但無法避免選擇聚類中心的人為主觀性。張新元等人[23]在SNN-DPC基礎(chǔ)上引入放大因子重新定義樣本局部密度，提出了共享k近鄰和多分配策略的密度峰值聚類算法（SKM-DPC），改進了分配策略，聚類性能較SNN-DPC 有所提升，但還無法避免選擇聚類中心的人為主觀性。

針對上述DPC 改進算法的不足，本文提出了自適應聚類中心的密度峰值聚類算法（ADPC）。重新定義了局部密度，通過斜率差分和決策函數(shù)確定潛在的聚類中心，根據(jù)DPC 算法中聚類中心點之間距離較大原則進行篩選，最終自動確定真實聚類中心，同時優(yōu)化了非聚類中心點的分配策略，避免非聚類中心點分配時產(chǎn)生連帶錯誤，算法適用于不同分布類型數(shù)據(jù)集。

1 DPC算法

1.1 DPC算法基本思想

DPC 算法的關(guān)鍵是通過決策圖能夠快速識別數(shù)據(jù)集樣本的聚類中心，實現(xiàn)任意形狀數(shù)據(jù)集樣本的高效聚類。理想的聚類中心基于兩個假設：（1）其局部密度大于圍繞它的鄰居的局部密度；（2）不同聚類中心點之間的距離相對較遠。

對于數(shù)據(jù)集中任意樣本點xi，DPC 算法需要計算兩個變量，即樣本點xi的局部密度ρi和相對距離δi。樣本點xi的局部密度ρi，定義如公式（1）所示：

相對距離δi為樣本點xi到比其局部密度更高且距離最近的點的距離，定義如公式（3）所示：

相對距離δi和局部密度ρi的乘積為γi，定義如公式（4）所示：

DPC算法以局部密度ρ為橫坐標，相對距離δ為縱坐標繪制二維決策圖，依據(jù)DPC 算法中理想聚類中心的兩個假設，將具有較高ρi和δi的樣本點標識為聚類中心。在決策圖中，選擇位于決策圖右上方的點作為聚類中心。如圖1 所示，可以直觀得到Jain數(shù)據(jù)集的兩個中心點22 和109，選擇出中心點之后，采用一步分配原則將非聚類中心的點被劃分到距離其最近的高密度鄰居所在簇中。在DPC 算法中，為消除離群點對聚類過程的影響，定義邊界區(qū)域，即屬于該簇但是距離其他簇不超過dc的點的集合，將邊界區(qū)域中密度最高的點定義為ρb。簇中密度小于ρb的對象被視為離群點。

圖1 Jain數(shù)據(jù)集決策圖分布Fig.1 Decision graph distribution of Jain

1.2 DPC算法缺陷分析

利用決策圖選擇聚類中心點人為主觀影響較大，且對于密度分布不均勻以及差異性很大的數(shù)據(jù)集來說，直觀選擇中心點較為困難。如圖2所示，在無監(jiān)督聚類過程中已經(jīng)無法通過在決策圖直觀選擇聚類中心，過多過少地選擇聚類中心都會導致最終聚類準確率降低。

圖2 Aggregation數(shù)據(jù)集決策圖分布Fig.2 Decision graph distribution of Aggregation

另外，DPC算法在分配非聚類中心點時采用的一步分配策略，即直接將非聚類中心點分配到比其密度更大且距離更近的點所在的簇中，這種分配策略易產(chǎn)生連帶錯誤，一個樣本分配錯誤，比其密度低且距離最近的點相繼都會分配錯誤，降低聚類準確率。如圖3 所示，PathBased 數(shù)據(jù)集分為三個簇，兩個密度相對較大的簇被一個密度較小的環(huán)狀簇所包圍，可以看到密度較小的環(huán)狀簇兩邊點的密度也相對較小，一步分配策略導致該簇很多點被錯誤分配到密度較大的兩簇中。

圖3 PathBased數(shù)據(jù)集在DPC算法上聚類結(jié)果Fig.3 Clustering of PathBased on DPC

2 自適應聚類中心策略優(yōu)化的密度峰值聚類算法

為克服DPC 算法與其優(yōu)化算法的不足，本文對樣本點局部密度度量、選擇中心點方式以及分配策略進行改進，重新定義了局部密度度量，通過函數(shù)變換加大了γ分布圖中聚類中心與非聚類中心的區(qū)分度，決策函數(shù)確定潛在聚類中心，利用距離均值定義實現(xiàn)自適應選擇聚類中心，優(yōu)化了非聚類中心點的分配。

2.1 算法思想

采用共享近鄰定義兩點之間的相似性度量，用樣本k個近鄰點之間的相似性和與k個近鄰點的距離之和重新定義了局部密度，在γ分布圖上采用從右向左的方式根據(jù)相鄰兩點之間斜率差分尋找“拐點”，并在“拐點”附近對樣本的γ值進行“拉伸”，采用γ決策函數(shù)盡可能多地選擇出潛在的聚類中心點，通過DPC 算法中聚類中心特點篩選出真實聚類中心，實現(xiàn)聚類中心的自適應確定，并對非聚類中心點逐級分配。

定義1（樣本間相似性）利用共享近鄰來定義樣本點之間的相似性，對其運用指數(shù)核的形式重新定義，如公式（5）所示：

DPC算法在Iris數(shù)據(jù)集上的γ降序分布圖如圖4所示，本文ADPC 算法在Iris 數(shù)據(jù)集上通過Max-Min 歸一化的γ降序分布圖中如圖5所示。從圖中可以看出，具有明顯密度峰的樣本點極少，大多數(shù)樣本點的γ值較小，而且，對于稠密的簇來說，可能會存在多個γ值偏大的點，在圖4中從左向右尋找斜率突變的點容易造成其他聚類中心的漏選，尤其是低密度簇。因此本文引用“拐點”概念，在圖5 中從右向左尋找第一個滿足公式（7）的點作為“拐點”?！肮拯c”位置為圖中ap，由此可見，當從右向左尋找“拐點”時，在此處斜率存在明顯變化，且“拐點”前后樣本點γ值存在差異。

圖4 Iris數(shù)據(jù)集在DPC算法上的γ 分布圖Fig.4 γ graph distribution of Iris on DPC

圖5 Max-Min歸一化后的Iris數(shù)據(jù)集γ 分布圖Fig.5 γ graph distribution of Iris after Max-Min normalization

根據(jù)DPC算法中選擇γ值較大的點作為聚類中心點的思想，為防止漏選，ADPC算法以“拐點”為中心，將“拐點”附近的點“拉伸”變換，使“拐點”前后的γ值區(qū)分更加明顯。結(jié)合數(shù)據(jù)樣本特點，定義變換后的γ如公式（9）所示：

其中，γ為Max-Min 歸一化后每個樣本點的升序排列，γap為“拐點”對應的γ值。以Iris數(shù)據(jù)集為例，每個樣本點Max-Min歸一化后的γ值經(jīng)公式（9）變換后的連續(xù)函數(shù)圖像如圖6（b）所示，每個樣本γ值分布如圖6（c）所示。“拐點”變換后的γ～ap=0.5，相比較于圖4，原來γ值大的點變換后依舊保持優(yōu)勢，相對中間的點通過變換使“拐點”附近的點γ值明顯增大，潛在聚類中心與非聚類中心點之間區(qū)分度也增加?？梢员苊庵苯釉趫D4中尋找突變點選擇中心點造成的漏選問題。比較于Max-Min歸一化后的γ分布，ap附近的點被“拉伸”，ap前后的點存在明顯差異，進一步拉大潛在聚類中心和非聚類中心的差異，也使得γ分布圖中的突變點更加直觀。

圖6 函數(shù)可視化圖像Fig.6 Functional visualization images

圖7和圖8分別為DPC算法和ADPC算法在Aggregation 數(shù)據(jù)集和R15 數(shù)據(jù)集的γ降序分布圖，根據(jù)γ值結(jié)果分析，圖7（a）按γ值降序排列后第7、8樣本點基本重合，即γ值相差不大，造成聚類中心點難于選取。圖8（a）中前14 個樣本點與后邊樣本點γ值存在差異，但選取中心點時造成漏選。通過對比，可以看到ADPC算法的γ圖中γ～ =0.5 處的“拐點”位置前后存在差異。相比較于DPC算法，通過更多點γ值被拉伸，潛在聚類中心點的γ值變換后變大，與非聚類中心點差異增加且避免聚類中心點的漏選。

圖7 Aggregation數(shù)據(jù)集的γ 降序分布圖對比Fig.7 Comparison of γ descending graph distribution on Aggregation

圖8 R15數(shù)據(jù)集的γ 降序分布圖對比Fig.8 Comparison of γ descending graph distribution on R15

定義4γ～ 決策函數(shù)。γ～ 決策函數(shù)定義如公式（10）：

其中，μ(γ～ )為變換后的γ～ 的平均值，σ(γ～)為標準差，公式（10）可以將“拐點”之前的點以及靠下一些的點都選為潛在聚類中心，使之可能多地選擇出潛在聚類中心，可以避免較稀疏密度簇的中心點的漏選。設潛在聚類中心集合為dcenters={c1,c2,…,cs}。

基于DPC 算法關(guān)于聚類中心點的兩個假設，提出自適應聚類中心策略優(yōu)化。首先，將潛在的聚類中心點中密度最大的點作為第一個真實聚類中心cc1，然后按照公式（11）選擇第二個真實中心，即兩個聚類中心點之間的距離要大于等于潛在中心點樣本兩兩之間距離均值的1/2。設最終聚類中心點集合fcenters={cc1,cc2,…,ccm}。

其中，ci,cj∈dcenters，ccp∈fcenters，經(jīng)多次實驗驗證，該篩選公式選取所有距離均值的1/2 時篩選結(jié)果最佳，可以將屬于同一簇中的潛在中心點剔除，確定最終聚類中心。

ADPC 算法依據(jù)公式（6）計算樣本點局部密度，公式（3）計算樣本間相對距離，針對DPC 算法的缺陷，不采用局部密度和相對距離決策圖直觀選擇聚類中心，而是通過確定“拐點”，對樣本γ值進行變換，使聚類中心與非聚類中心γ值差異相對較大，利用決策函數(shù)，選擇出潛在的聚類中心點；根據(jù)DPC算法兩個基本假設，對潛在聚類中心點進行篩選，實現(xiàn)聚類中心的自動確定，無需人工干預。

2.2 ADPC算法詳細描述

輸入：數(shù)據(jù)集X，樣本近鄰數(shù)k。

輸出：聚類結(jié)果Clu。

步驟1 初始化聚類Clu[xi]=－1。

步驟2 計算數(shù)據(jù)集樣本點之間的歐式距離，根據(jù)公式（5）計算樣本間相似性。

步驟3 根據(jù)公式（3）和（6）計算δ、ρ。

步驟4 根據(jù)公式（4）計算樣本γ值，并進行Max-Min歸一化。

步驟5 根據(jù)公式（7）確定歸一化后γ降序分布圖的“拐點”，用公式（9）對歸一化后的γ升序排列進行冪函數(shù)變換。

步驟6 根據(jù)公式（10）得到潛在聚類中心集合dcenters={c1,c2,…,cs}。

步驟7 根據(jù)公式（11）對潛在聚類中心集合中的點進行篩選，自動確定聚類中心集合fcenters={cc1,cc2,…,ccm}。

步驟8 樣本點分配。

（1）給聚類中心分配簇標記；

（2）非聚類中心點的分配：

①分配聚類中心的k個近鄰點，若ccp∈fcenters，b∈KNN(ccp)且ccp∈KNN(b)，則Clu[b] =Clu[ccp]；

②對其他未分配的點，將其分配到其k近鄰點中最多點所在的某簇中；

③若還有未分配點，即Clu[xi]=－1，采用DPC 算法的一步分配，即分配到密度比其大且距離最近的點所在的簇中。

2.3 ADPC算法時間復雜度分析

在本節(jié)中，設置樣本數(shù)n，近鄰個數(shù)k，潛在聚類中心數(shù)s，聚類中心數(shù)m，s＜＜n且m＜＜n，ADPC 算法各部分時間復雜度分析如下：

（1）計算樣本點的距離，時間復雜度為O(n2)。

（2）計算樣本間相似性，時間復雜度為O(n2)。

（3）計算樣本點間相對距離，時間復雜度為O(n2)。

（4）計算樣本點局部密度，時間復雜度為O(kn)。

（5）計算樣本γ值，并進行Max-Min歸一化，時間復雜度為O(n)。

（6）確定“拐點”，時間復雜度為O(n)。

（7）γ值進行冪函數(shù)變換，時間復雜度為O(n)。

（8）計算潛在中心集合，時間復雜度為O(n)。

（9）自動確定真實聚類中心，時間復雜度為O(sm)。

（10）樣本點分配，總時間復雜度O(n)。其中分配聚類中心點，時間復雜度為O(m)，分配聚類中心點的k個近鄰點，時間復雜度為O(mk)，其他未分配點數(shù)量最壞情況下為n，時間復雜度為O(nk)，但實際要小于O(nk)。

綜上所述，ADPC 算法時間復雜度約為O(n2)，與DPC算法時間復雜度量級相同，且都主要來源于計算樣本間的距離、計算所有樣本的局部密度以及計算每對樣本之間的相對距離。

3 實驗結(jié)果與分析

3.1 實驗環(huán)境與數(shù)據(jù)

選用人工數(shù)據(jù)集（Aggregation、Flame、Spiral、Far、G2_2_30、R15）和UCI 數(shù)據(jù)集（Iris、Seeds、Glass、Ionosphere、Knowledge、Planning）對本文提出的ADPC 算法進行性能測試。數(shù)據(jù)集詳細信息見表1和表2。

表1 人工數(shù)據(jù)集Table 1 Synthetic datasets

表2 UCI數(shù)據(jù)集Table 2 UCI datasets

ADPC算法與SNN-DPC算法、DPC算法、SKM-DPC算法、DBSCAN算法、AP算法以及K-means算法進行對比實驗。其中SNN-DPC 和DPC 算法來源于Github 源代碼，SKM-DPC 算法和K-means 算法為自己復現(xiàn)，DBSCAN算法和AP算法直接從Sklearn庫中調(diào)用。實驗環(huán)境為Windows 64 bit操作系統(tǒng)，PyCharm Community Edition 2021.3.1軟件，4 GB內(nèi)存，Intel?Core?i5-6200U CPU@2.30 GHz 2.40 GHz。

3.2 評價指標

本文采用的評價指標為聚類中常見的準確率（Acc）、調(diào)整互信息（AMI）、調(diào)整蘭德指數(shù)（ARI）以及FM指數(shù)（FMI）。

準確率（Accuracy，Acc）是被正確聚類的樣本數(shù)占樣本總數(shù)的比值，準確率越高，算法聚類性能越好。

調(diào)整互信息（AMI）是對互信息（Mutual Information，MI）的一種改進。AMI取值范圍為[-1，1]，值越接近1，聚類性能越好。

調(diào)整蘭德指數(shù)（ARI）由蘭德系數(shù)（Rand Index，RI）轉(zhuǎn)化而來。ARI 在[-1，1]范圍內(nèi)取值，ARI 取值越接近1，表明算法的聚類性能越好。

FM指數(shù)（fowlkes and mallows index，F(xiàn)MI）是成對精度與召回率的集合均值，F(xiàn)MI 取值范圍是[0，1]，值越大，聚類效果越好。

3.3 參數(shù)（Par）設置

本文實驗各算法參數(shù)及設置見表3。ADPC 算法、SNN-DPC 算法以及SKM-DPC 算法的參數(shù)為樣本近鄰數(shù)k，該參數(shù)根據(jù)不同的數(shù)據(jù)集選擇不同，實驗在5～20之間擇優(yōu)選取，DPC 算法參數(shù)為截斷距離選取時的占比，選擇范圍為0.5%～2%，大多數(shù)據(jù)集在取2%時效果最優(yōu)。DBSCAN 算法參數(shù)為鄰域半徑Esp和最少樣本數(shù)MinPts，鄰域半徑Esp一般在0.1～2.0 之間取值，但在G2_2_30 數(shù)據(jù)集取值為18 時較優(yōu)，最少樣本數(shù)MinPts在3～30 之間取值。AP 算法參數(shù)為preference，指樣本xi作為聚類中心的參考度，實驗采用歐式距離平方的相反數(shù)作為相似度。K-means 算法參數(shù)為隨機選取的聚類中心數(shù)k，實驗取20 次重復實驗的最優(yōu)結(jié)果取值。

表3 各算法參數(shù)設置Table 3 Parameter settings of each algorithm

3.4 人工數(shù)據(jù)集實驗結(jié)果分析

類中心的位置與聚類結(jié)果可視化，并與SNN-DPC算法和DPC 算法進行可視化聚類對比。對比結(jié)果如圖9～圖14所示。其中紅色星形為聚類中心位置。

圖9 三種算法在Aggregation數(shù)據(jù)集上的聚類中心位置Fig.9 Cluster centers of three algorithms on Aggregation

圖9～圖14 表明，針對所選六個人工數(shù)據(jù)集，ADPC算法都可以自動確定出聚類中心位置，且可以正確聚類。圖9顯示，Aggregation數(shù)據(jù)集有兩個簇存在輕微連接，ADPC算法可以選出合適的聚類中心，且聚類結(jié)果比SNN-DPC 算法好。圖10，F(xiàn)lame 分為上下兩簇，簇與簇存在小部分連接，ADPC算法、SNN-DPC算法和DPC算法都可以正確選出聚類中心，但是圖10（b）中SNN-DPC算法在簇與簇連接部分存在小部分點分配錯誤的情況。圖10（c）中DPC算法由于采用一步分配，產(chǎn)生了連帶反應，造成下半部分簇的大多數(shù)點分配錯誤，聚類準確率降低。圖11為Spiral環(huán)形簇，三種算法均可以正確選出聚類中心，并能準確聚類。圖12 為具有相對獨立的簇的數(shù)據(jù)集4k2_far，由聚類結(jié)果可以看出，三種算法對4k2_far 數(shù)據(jù)集可以正確選出聚類中心，正確聚類。圖13 為數(shù)據(jù)集G2_2_30 的聚類結(jié)果，該數(shù)據(jù)集樣本數(shù)為2 048，分為兩個比較稠密的簇，三種算法針對相對較大規(guī)模數(shù)據(jù)集均可以正確選出聚類中心。圖14為數(shù)據(jù)集R15 的聚類結(jié)果，該數(shù)據(jù)集樣本數(shù)為600，但分為15個簇，ADPC算法、SNN-DPC算法以及DPC算法均可以正確選出聚類中心。

圖10 三種算法在Flame數(shù)據(jù)集上的聚類中心位置Fig.10 Cluster centers of three algorithms on Flame

圖11 三種算法在Spiral數(shù)據(jù)集上的聚類中心位置Fig.11 Cluster centers of three algorithms on Spiral

圖12 三種算法在4k2_far數(shù)據(jù)集上的聚類中心位置Fig.12 Cluster centers of three algorithms on 4k2_far

圖13 三種算法在G2_2_30數(shù)據(jù)集上的聚類中心位置Fig.13 Cluster centers of three algorithms on G2_2_30

圖14 三種算法在R15數(shù)據(jù)集上的聚類中心位置Fig.14 Cluster centers of three algorithms on R15

表4給出了ADPC算法在人工數(shù)據(jù)集上與SNN-DPC算法、DPC 算法、SKM-DPC 算法、DBSCAN 算法、AP 算法以及K-means算法在Acc、ARI、AMI以及FMI四個評價指標上的性能以及各算法的參數(shù)值，其中加粗字體表示性能較好的實驗結(jié)果。

表4 人工數(shù)據(jù)集上聚類性能比較Table 4 Performance comparison of clustering algorithms on synthetic datasets

由表4 得出，在Aggregation 數(shù)據(jù)集上，ADPC 算法比DPC算法的聚類性能平均低1.4%，只比SKM-DPC算法的Acc 低0.4%，但比也應用了共享近鄰的SNN-DPC算法的聚類性能平均高1.8%，AP 算法因無法找到準確的聚類中心，聚類效果不佳。ADPC 算法在其他5 個人工數(shù)據(jù)集上均可以與其他六個算法抗衡，其中在Flame數(shù)據(jù)集上，ADPC 算法與DPC 算法聚類性能相同，比SKM-DPC 算法與SNN-DPC 聚類性能平均高1.67%和9.2%。在Spiral、4k2_far 和R15 數(shù)據(jù)集上ADPC 算法與其他算法相比保持穩(wěn)定優(yōu)勢，其中在Spiral 數(shù)據(jù)集上，ADPC算法、SNN-DPC算法、DPC算法、SKM-DPC算法以及DBSCAN算法聚類性能保持優(yōu)勢，K-means算法與AP 算法聚類性能較差。在4k2_far 數(shù)據(jù)集上，ADPC 算法、DPC 算法、SKM-DPC 算法以及AP 算法聚類性能存在優(yōu)勢，SNN-DPC算法、DBSCAN算法以及K-means算法聚類性能不佳。在R15 數(shù)據(jù)集上ADPC 算法依舊存在優(yōu)勢，DBSCAN算法與K-means算法的表現(xiàn)不佳。在G2_2_30數(shù)據(jù)集上，ADPC算法具有較好的聚類性能，比DPC算法平均高0.05%，AP算法雖聚類性能良好，但是在參數(shù)最優(yōu)的情況下，一般來說，AP 算法難以參數(shù)尋優(yōu)。由此得出結(jié)論，SNN-DPC 算法與其他算法相比在人工數(shù)據(jù)集上優(yōu)勢保持穩(wěn)定且明顯。

由上述人工數(shù)據(jù)集的實驗表明，ADPC算法在不同規(guī)模、不同形狀和不同簇數(shù)的數(shù)據(jù)集上均可以正確選出聚類中心，且聚類性能也存在穩(wěn)定優(yōu)勢。本文算法避免了DPC 算法在決策圖上選擇聚類中心點的人為主觀性，同時結(jié)合了k近鄰分配策略，也避免了DPC算法一步分配所產(chǎn)生的連帶反應。

3.5 真實數(shù)據(jù)集實驗結(jié)果分析

為進一步測試本文ADPC算法性能，本文選用UCI中六個真實數(shù)據(jù)集進行測試，六個數(shù)據(jù)集具有不同維度、不同簇數(shù)且不同規(guī)模。表5 給出了ADPC 算法在UCI 真實數(shù)據(jù)集上與SNN-DPC 算法、DPC 算法、SKMDPC 算法、DBSCAN 算法、AP 算法以及K-means 算法在Acc、ARI、AMI 以及FMI 四個評價指標上的性能以及各算法的參數(shù)值，其中加粗字體表示性能較好的實驗結(jié)果。

表5 UCI數(shù)據(jù)集上聚類性能比較Table 5 Performance comparison of clustering algorithms on UCI datasets

由表5中得出，在數(shù)據(jù)集Iris上，ADPC算法的Acc、ARI 和AMI 值均為最高，AMI 值比最好的DPC 算法低2%。在數(shù)據(jù)集Seeds上，ADPC算法的Acc、ARI和AMI值均為最高，AMI僅比K-means算法低3%，DBSCAN算法聚類效果最差。在數(shù)據(jù)集Glass、Ionosphere和Knowledge 上，ADPC 算法的四個評價指標優(yōu)勢明顯，均為最高值。在數(shù)據(jù)集Planning上，ADPC算法在AMI、ARI以及FMI 性能最好，在Acc 上僅低于K-means 算法。因此，ADPC算法在UCI真實數(shù)據(jù)集上具有較好表現(xiàn)。

4 總結(jié)與展望

本文提出的ADPC 算法通過樣本點之間的共享近鄰定義樣本的相似性，利用樣本點的k個近鄰點的距離之和與相似性的指數(shù)核函數(shù)定義局部密度，在Max-Min歸一化后γ降序分布圖上采用從右向左的方式利用相鄰兩點之間斜率差分尋找“拐點”，通過對樣本點的值進行變換更好地得到了潛在的聚類中心，避免了聚類中心點的漏選，實現(xiàn)了真實聚類中心點的自動確定，解決了人為選擇聚類中心的主觀性問題。同時，優(yōu)化了非聚類中心點的分配策略，避免非聚類中心點分配時產(chǎn)生連帶錯誤。通過六個人工數(shù)據(jù)集驗證了ADPC 算法自適應選擇聚類中心的準確性。在六個UCI 數(shù)據(jù)集上的實驗表明，ADPC 算法可以準確實現(xiàn)聚類中心的自適應的同時，樣本點分配策略更加合理，聚類性能較DPC、ADPC、SKM-DPC、DBSCAN、AP 以及K-means 算法總體有所提升。然而，ADPC 算法樣本k近鄰中的參數(shù)k是提前給定的，如何實現(xiàn)k值自適應將在未來工作中進一步研究。