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

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

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

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

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

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

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

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

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

1 DPC算法

1.1 DPC算法基本思想

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

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

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

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

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

圖1 Jain數據集決策圖分布Fig.1 Decision graph distribution of Jain

1.2 DPC算法缺陷分析

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

圖2 Aggregation數據集決策圖分布Fig.2 Decision graph distribution of Aggregation

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

圖3 PathBased數據集在DPC算法上聚類結果Fig.3 Clustering of PathBased on DPC

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

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

2.1 算法思想

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

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

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

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

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

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

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

圖6 函數可視化圖像Fig.6 Functional visualization images

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

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

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

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

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

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

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

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

2.2 ADPC算法詳細描述

輸入：數據集X，樣本近鄰數k。

輸出：聚類結果Clu。

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

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

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

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

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

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

步驟7 根據公式（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é)中，設置樣本數n，近鄰個數k，潛在聚類中心數s，聚類中心數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）γ值進行冪函數變換，時間復雜度為O(n)。

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

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

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

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

3 實驗結果與分析

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

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

表1 人工數據集Table 1 Synthetic datasets

表2 UCI數據集Table 2 UCI datasets

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

3.2 評價指標

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

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

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

調整蘭德指數（ARI）由蘭德系數（Rand Index，RI）轉化而來。ARI 在[-1，1]范圍內取值，ARI 取值越接近1，表明算法的聚類性能越好。

FM指數（fowlkes and mallows index，FMI）是成對精度與召回率的集合均值，FMI 取值范圍是[0，1]，值越大，聚類效果越好。

3.3 參數（Par）設置

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

表3 各算法參數設置Table 3 Parameter settings of each algorithm

3.4 人工數據集實驗結果分析

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

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

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

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

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

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

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

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

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

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

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

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

3.5 真實數據集實驗結果分析

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

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

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

4 總結與展望

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