基于網格近鄰優(yōu)化的密度峰值聚類算法

摘 要：密度峰值聚類（DPC）將數(shù)據(jù)樣本點的局部密度和相對距離進行結合，能對任意形狀數(shù)據(jù)集進行聚類處理，但密度峰值聚類算法存在主觀選擇截斷距離、簡單分配策略和較高時間復雜度等問題。為此，提出了一種基于網格近鄰優(yōu)化的密度峰值聚類算法（KG－DPC算法）。首先對數(shù)據(jù)空間進行網格化，減少了樣本數(shù)據(jù)點之間距離的計算量；在計算局部密度時不僅考慮了網格自身的密度值，而且考慮了周圍k個近鄰的網格密度值，降低了主觀選擇截斷距離對聚類結果的影響，提高了聚類準確率，設定網格密度閾值，保證了聚類結果的穩(wěn)定性。通過實驗結果表明，KG－DPC算法比DBSCAN、DPC和SDPC算法在聚類準確率上有很大提升，在聚類平均消耗時間上DPC、SNN－DPC和DPC－NN 算法分別降低38%、44%和44%。在保證基本聚類準確率的基礎上，KG－DPC算法在聚類效率上有特定優(yōu)勢。

關鍵詞：密度峰值聚類； 密度閾值； 網格； 近鄰優(yōu)化

中圖分類號：TP311.13文獻標志碼： A文章編號：1001－3695（2024）04－015－1058－06

doi：10.19734/j.issn.1001－3695.2023.08.0396

Density peak clustering algorithm based on grid neighbor optimization

Liu Ji Yang Jinruia

Abstract：Density peak clustering（DPC） combines the local density and relative distance of data sample points， and can cluster arbitrary shaped datasets. However， DPC algorithm has problems such as subjective selection of truncation distance， simple allocation strategy， and high time complexity. This paper proposed a density peak clustering algorithm based on grid nearest neighbor optimization（KG－DPC algorithm）. Firstly， it gridded the data space to reduce the computational burden of distance between sample data points. When calculating local density， not only the density values of the grid itself were consi－dered， but also the density values of the surrounding k nearest neighbors were considered， reducing the impact of subjective selection of truncation distance on clustering results， improving clustering accuracy， and setting a grid density threshold to ensure the stability of clustering results. The experimental results show that the KG－DPC algorithm has a significant improvement in clustering accuracy compared to DBSCAN， DPC， and SDPC algorithms. Compared to DPC， SNN－DPC， and DPC－NN algorithms，the average consumption time in clustering is reduced by 38%， 44% and 44%， respectively. On the basis of ensuring the accuracy of basic clustering， the KG－DPC algorithm has specific advantages in clustering efficiency.

Key words：density peak clustering; density threshold; grid; nearest neighbor optimization

0 引言

大數(shù)據(jù)時代，如何從數(shù)據(jù)中發(fā)現(xiàn)隱含有價值的信息成為廣泛關注的問題［1］。聚類分析作為常用的統(tǒng)計數(shù)據(jù)分析技術，近年來在許多領域都得到了廣泛應用，如數(shù)據(jù)分析、商業(yè)、生物學、醫(yī)療診斷、市場研究等領域［2，3］。

聚類方法有多種分類，有基于劃分的聚類方法、基于分層的聚類方法等，由于基于密度的聚類方法不需要預先知道聚類簇數(shù)，受到研究者廣泛關注。Rodriguez等人［4］于2014年提出了一種基于密度的聚類方法。該聚類算法相比于其他傳統(tǒng)的聚類算法，算法原理簡單易于實現(xiàn)，需要人為設置的參數(shù)較少，能夠快速發(fā)現(xiàn)噪聲點，能夠根據(jù)決策圖自動發(fā)現(xiàn)類簇中心并實現(xiàn)對任意形狀數(shù)據(jù)集的高效聚類，因此密度峰值聚類算法在圖像處理、社區(qū)劃分、模式識別和文本處理等領域得到了廣泛的應用。但是該算法中截斷距離dc的選取是由人為主觀決定的，而截斷距離在局部密度的計算中占據(jù)重要地位，不同的取值會直接影響到聚類的結果，并且該算法對于非類簇中心樣本點的分配策略也存在不足。如果一個數(shù)據(jù)集中所包含的類簇為半月形，很容易將數(shù)據(jù)點分配到錯誤的類簇中，而一個數(shù)據(jù)樣本點如果被分配到錯誤的類簇中，就會引發(fā)與其相鄰樣本數(shù)據(jù)點的分配錯誤，最終導致聚類結果不盡如人意。

對于密度峰值算法中所存在的不足，部分學者對其進行了綜合剖析。徐曉等人［5］從四個方面總結了如何對密度峰值聚類算法改進，而陳葉旺等人［6］對各種改進算法進行了對比，并且討論了密度峰值聚類算法在不同領域中的應用。

針對密度峰值聚類算法中需要人工選取聚類中心的不足，王萬良等人［7］引入了切比雪夫不等式確定密度閾值，并建立決策函數(shù)自動選取聚類中心。江平平等人［8］使用網格代表點代替整個網格單元，利用網格單元計算局部密度和相對距離，并通過改進的自適應方法選取聚類中心，從而使用提出的網格密度峰值聚類算法（G－DPC算法）進行聚類。Zhao等人［9］提出了一種k值選擇方法來選擇最佳簇數(shù)，該簇數(shù)由簇內誤差平方和決定，并利用K近鄰的思想對異常值進行賦值。馬淑華等人［10］在選取截斷距離時引入了基尼系數(shù)，并根據(jù)局部密度與相對距離定義了一個參數(shù)，綜合衡量了局部密度和相對距離。Yin等人［11］繪制了K近鄰域距離的線圖找到全局分岔點，自動確定聚類中心和聚類中心數(shù)，然后利用聚類融合規(guī)則對聚類結果進行完善和集成。

為了避免簡單分配策略影響聚類的效果，部分專家對分配策略進行了改進。Jiang等人［12］提出了一種基于K近鄰的密度峰值聚類（DPC－KNN），將K近鄰的思想引入到距離計算和分配過程中，提高了聚類的準確度。王艦［13］通過計算類簇內所包含的樣本點到類簇中心的距離統(tǒng)計，使用高斯判別式對類與類之間的樣本點進行分配，并設定了高斯約束值，將高斯判別式計算出來的值與高斯約束值作比較，從而區(qū)分出邊界點和噪聲點。陳蔚昌等人［14］在對非聚類中心點進行分配時引入了共享近鄰，構造相似度矩陣， 使屬于同一類簇樣本之間的聯(lián)系更緊密， 避免錯誤分配樣本，進一步提高了聚類的精度。

由于密度峰值聚類算法中局部密度的數(shù)值直接影響聚類的結果，而局部密度與主觀選擇的截斷距離有關，所以部分學者對該缺陷進行了改進。徐紅艷等人［15］利用了自適應多分辨率網格劃分的思想，對數(shù)據(jù)集進行網格化后，使用密度比估計計算數(shù)據(jù)點的局部密度，然后再進行聚類。文獻［16，17］均對密度峰值聚類算法中局部密度的計算公式進行了新的設定，前者以局部密度的平均值作為密度閾值篩選出離群點并進行剔除，然后使用自適應策略將相似的聚類簇進行合并，而后者對樣本點的權值進行了排序，然后利用權值斜率選擇臨界點，找到數(shù)據(jù)集中類簇的聚類中心點。Li等人［18］為了避免密度峰值聚類算法中兩個用戶指定的參數(shù)對聚類效果產生影響，將其擴展為一種通用的層次結構形式，從而在一定程度上提高了聚類的精確度。

還有部分學者對于密度峰值聚類算法中計算距離矩陣所消耗時間較高的問題進行了改進，減少了算法的運行時間。江婧婷等人［19］通過判斷網格均衡來計算網格間距離并根據(jù)網格相對引力與局部密度的乘積極大值來自動確定閾值，從而得到聚類結果。孫昊等人［20］首先利用網格將數(shù)據(jù)集劃分到不同的區(qū)域得到一個數(shù)據(jù)分區(qū)，對各個數(shù)據(jù)分區(qū)進行局部聚類，然后再進行類簇合并，從而實現(xiàn)聚類。徐曉等人［21］設定了一個篩選比例a，用于篩選出密集網格，然后進行聚類，降低了密度峰值聚類算法的時間復雜度。馬福民等人［22］認為網格的劃分對聚類結果有影響，所以根據(jù)網格密度的分布具有Zipf分布的特點，提出了一種基于Zipf分布的網格密度峰值聚類算法，并引入了邊緣網格處理算法，提高聚類的準確度和網格邊緣的平滑度。Liu等人［23］提出了一種基于共享最近鄰的快速搜索和密度峰值發(fā)現(xiàn)的聚類算法，根據(jù)最近鄰居和共享鄰居的信息，重新定義了局部密度和相對距離。

以上研究者基本上認為密度峰值聚類算法為發(fā)現(xiàn)具有不同形狀和密度的聚類提供了有效的工具，但是該算法存在時間復雜度高、聚類精度容易受到人工參數(shù)調整影響等缺點，因此本文提出了一種基于網格和最近鄰優(yōu)化的密度峰值聚類的算法（KG－DPC算法）。對于原始的密度峰值聚類算法需要計算每個數(shù)據(jù)點與其他所有數(shù)據(jù)點之間的距離，造成算法時間復雜度較高的問題，引入網格化的思想，將數(shù)據(jù)空間劃分為多個網格，然后只需計算每個數(shù)據(jù)點與其相鄰網格中的數(shù)據(jù)點之間的距離，這樣可以大大減少計算量，提高聚類算法的效率；對于密度峰值聚類算法中需要人為選擇截斷距離的問題，引入了K近鄰的思想，優(yōu)化聚類算法的局部密度度量方式，降低了由于主觀選擇截斷距離對聚類的影響，提升了聚類結果的精確度，并設定了密度閾值來過濾低密度區(qū)域中的噪聲影響，提升聚類結果的穩(wěn)定性。

1 密度峰值聚類

Rodrigues等人［4］提出了一種有關密度的聚類算法，即密度峰值聚類算法（density peaks clustering），該算法有兩個基本的假設：自身的密度較大，而周圍都是其他密度較低的數(shù)據(jù)點；與大于自身密度的數(shù)據(jù)點距離相對較遠。在密度峰值聚類算法中，有局部密度ρi和相對距離δi兩個重要的參數(shù)，這兩個參數(shù)的取值關系到整個算法的聚類效果。

對于不同的數(shù)據(jù)集，截斷距離dc計算所消耗的時間及次數(shù)也不同，數(shù)據(jù)集所包含的數(shù)據(jù)樣本量越大，需要計算的樣本點之間的距離就越多，其時間復雜度就越高。而在同一個樣本數(shù)據(jù)集中，不同的截斷距離值會直接影響到局部密度的計算。在密度峰值聚類算法中，聚類結果的質量受聚類中心的影響很大，該算法中聚類中心的選擇由局部密度ρ和相對距離δ這兩個參數(shù)所決定，而在局部密度的計算公式中又包含了參數(shù)截斷距離dc，所以截斷距離dc的大小會直接影響到數(shù)據(jù)集的聚類結果。

aggregation數(shù)據(jù)集有七個類，不同的類中數(shù)據(jù)點的個數(shù)不夠均勻，差異較大，并且不同的類簇會有較多數(shù)據(jù)點連接。本文以該數(shù)據(jù)集為例，研究截斷距離不同的取值對聚類結果的影響。從圖1中可以看出，不同的截斷距離值所產生的聚類結果存在很大的差異。因此，本文提出的KG－DPC算法沒有使用截斷距離dc計算局部密度ρ，而是引入了衰減因子的概念和K近鄰的思想，消減了截斷距離在計算局部密度的負面作用，因此避免了由截斷距離dc對聚類結果所帶來的一系列影響。

在密度峰值聚類算法中，首先，利用樣本集數(shù)據(jù)對距離矩陣 D 進行求取，從而得到局部密度ρi和相對距離δi的值；然后，根據(jù)局部密度ρi與相對距離δi的乘積γi=ρi×δi繪制決策圖選取聚類中心點，聚類中心一般選取的是局部密度較大且相對距離較遠的數(shù)據(jù)樣本點，使用兩者乘積進行選取是為了避免某一項的值過小，使得聚類中心的選取不準確；在選擇正確的聚類中心后，根據(jù)距離原則對非類簇中心樣本數(shù)據(jù)點進行分配；最后，得到聚類的結果圖及各項指標。

從上述算法的步驟中可以看出，密度峰值聚類算法的時間復雜度主要在于對距離矩陣的計算和存儲，但對數(shù)據(jù)進行網格劃分以后，不再是計算數(shù)據(jù)點之間的歐氏距離，而是通過對網格與網格之間的距離進行計算，使得時間復雜度降低。

2 基于網格優(yōu)化的密度峰值聚類算法

2.1 問題描述及算法介紹

大量學者使用聚類分析衡量不同數(shù)據(jù)源之間的相似性，從而找到數(shù)據(jù)之間存在的聯(lián)系和規(guī)律。而密度峰值聚類算法是一種使用密度進行聚類的算法，密度峰值聚類算法在計算局部密度時，計算方式中涉及到了截斷距離，而截斷距離又是根據(jù)樣本數(shù)據(jù)點的距離矩陣計算而來的，所以對于較大數(shù)據(jù)集會消耗較長的時間。本文對樣本數(shù)據(jù)集進行了網格劃分，還定義了密度閾值，對稠密的網格進行了篩選，直接在稠密的網格中選取聚類中心，該過程極大地減少了計算的時間。對于密度峰值聚類算法中分配策略的缺陷，將非類簇中心樣本點根據(jù)最近鄰的思想進行再分配，從而提高了聚類效果。

2.2 數(shù)據(jù)空間網格化

對于數(shù)據(jù)空間網格化，將每一維數(shù)據(jù)都均勻劃分成相同的段數(shù)h，刪除網格內數(shù)據(jù)點個數(shù)為０的空網格，剩下的非空網格的數(shù)量為M。實驗結果表明，當網格對象個數(shù)M在大于數(shù)據(jù)樣本的n/5時，聚類準確率較高［24］。

對于網格劃分段數(shù)h，段數(shù)h的大小會影響聚類的結果。網格劃分的段數(shù)h越小，網格長度就越大，就會導致不屬于同一類簇的數(shù)據(jù)樣本點被劃分到同一類簇中，從而導致聚類精度有所下降；而網格劃分的段數(shù)h越大，網格長度就越小，甚至有的網格中只含有一個數(shù)據(jù)樣本點，這種情況下聚類的精度與未進行網格劃分之前的精確度相差不大，因此網格劃分就失去了它的意義。

均勻劃分對非均勻數(shù)據(jù)集進行聚類，能夠更直接地找出聚類中心并且時間復雜度低；而非均勻劃分可能對不同稀疏程度的數(shù)據(jù)集有一定的正面影響效果，但如何量化數(shù)據(jù)稀疏需要依據(jù)不同數(shù)據(jù)進行分析，另外非均勻劃分會降低算法的通用性且提高計算的復雜度。因此，本文選擇使用均勻劃分網格段數(shù)h的方式進行聚類分析。

2.3 局部密度計算和分配策略

定義3

局部密度。網格i的局部密度計算方式為網格i內的樣本數(shù)據(jù)點個數(shù)gi加上k個近鄰網格j內的樣本數(shù)據(jù)點個數(shù)gj與e函數(shù)之積，其中e-d2ij為衰減因子［24］，dij表示網格i與j之間的距離。

其中：d代表上四分位數(shù)；sort（ρi）表示將每個網格單元的局部密度值按照從大到小的原則進行排序［13］。

分配策略步驟如下：

a）從稀疏網格集合G中任取一個未標記的稀疏網格g；若所有網格均被標記，則跳至步驟d）。

b）對未標記的稀疏網格，識別其網格內的數(shù)據(jù)點。

c）對稀疏網格內的數(shù)據(jù)點與周圍類簇的中心點的歐氏距離進行比較，使用最近鄰的思想對其余數(shù)據(jù)樣本點進行分配。

d）完成分配。

2.4 算法步驟

基于網格優(yōu)化的密度峰值聚類算法（KG－DPC）的偽代碼如下：

輸入：樣本數(shù)據(jù)點X={x1，x2，…，xn}。

輸出：聚類索引的標量y。

a）對樣本數(shù)據(jù)點X={x1，x2，…，xn}進行預處理，并將其映射到所劃分的網格單元中。

b）尋找k個鄰近網格單元的集合。

c）根據(jù)定義3計算出每個網格單元的局部密度ρ，將局部密度ρ按照從大到小的原則進行排序。

d）篩選出稠密網格，將每個網格的局部密度ρ與密度閾值進行比較，如果ρi＞ρt，則網格i為稠密網格；如果ρi＜ρt，則該網格單元為稀疏網格。

e）根據(jù)定義4計算相對距離δ值。

f）根據(jù)步驟c）計算得到的局部密度ρ為橫軸和步驟e）計算得到的相對距離δ為縱軸繪制出決策圖，選擇聚類中心。

g）按照上述分配策略進行分配，其中數(shù)據(jù)點所在的類簇與其網格對象所在的類簇一致。

h）得到聚類結果，輸出聚類索引的標量y。

基于網格優(yōu)化的密度峰值聚類算法的偽代碼如下：

輸入：樣本數(shù)據(jù)點X={x1，x2，…，xn}。

輸出：聚類結果。

a）preprocess the sample data points

X={x1，x2，…，xn} and map them to the divided grid cells

b）find a set of k adjacent grid cells and initialize the index of local density set ρ={φ}

c）for each point xi∈X do

compute ρi by equation（6）

end for

sort ρi in descending order

d）for each point ρi∈ρ do

if ρi＞ρt then

ρi∈Gd //Gd為稠密網格集合

else

ρi∈Gs //Gs為稀疏網格集合

end if

end for

e）for each point ρi∈ρ do

compute δi by equation（7）

end for

f）select cluster centers based on the decision graph

g）for each point gi∈Gs do

if gi is not marked then

find closest center point with higher density for allocation

else

complete allocation

end if

end for

KC－DPC算法流程如圖2所示。

2.5 時間復雜度

假設樣本數(shù)據(jù)量為n，維數(shù)為d，劃分網格后的非空網格的數(shù)量為m，中心網格的數(shù)量為c，簇的數(shù)目為k，段數(shù)為h。密度峰值聚類算法中時間復雜度主要來源于數(shù)據(jù)樣本點間距離的計算，每個數(shù)據(jù)樣本的局部密度ρ和相對距離δ計算的時間復雜度都為O（n2），因此密度峰值聚類算法的時間復雜度為O（n2）［21］。

對樣本數(shù)據(jù)集進行網格劃分并計算網格對象局部密度的時間復雜度為O（ndkh2），使用密度閾值挑選出稠密網格的時間復雜度為O（mlog m），計算網格間相對距離的時間復雜度為O（c2）。在DPC算法中，要將非中心網格分配給聚類中心，其需要的時間復雜度為O（（m-c）2），而在網格優(yōu)化的密度峰值聚類算法中僅需要計算其與聚類中心間的距離，不需要遍歷每一個點計算點與點之間的距離，減少了距離計算的次數(shù)，所以該步驟的時間復雜度小于O（（m-c）2），本文算法總的時間消耗約為O（ndkh2）+O（mlog m）+O（c2）+O（（m-c）2）。根據(jù)上面的表述，本文算法的最終時間復雜度是O（ndkh2），在n較大的情況下，本文算法比密度峰值聚類算法的時間復雜度要小很多。

本文使用隨機生成數(shù)據(jù)樣本量為1 000～10 000，聚類中心為3的數(shù)據(jù)集，對KG－DPC算法的時間復雜度進行驗證，得出的結果如圖3所示。從圖3中可以看出，隨著數(shù)據(jù)樣本量的逐漸增大，DPC與KG－DPC算法之間的計算時間差值越大。

3 實驗分析

為檢驗本文方法的有效性，將KG－DPC與DBSCAN、密度峰值聚類（DPC）、SDPC［21］、SNN－DPC［23］和DPC－NN［14］五種算法所得出的聚類結果進行了比較。本文在Intel CoreTM i5處理器、Windows 11系統(tǒng)、Python 3.7的條件下進行實驗。

3.1 數(shù)據(jù)集

本文使用表1中的五個數(shù)據(jù)集對本文算法進行驗證，其中flame、aggregation、R15和D31數(shù)據(jù)集來源于人工數(shù)據(jù)集［22］，seed、banknote來源于UCI數(shù)據(jù)集，2d_4c_no9數(shù)據(jù)集為人工合成數(shù)據(jù)集，來源于https：//download.csdn.net/ download/ZC496496/16669473。從表1可以看出，數(shù)據(jù)集的維數(shù)都較低，并且樣本量大于1 000的數(shù)據(jù)集有兩個，分別為D31和banknote數(shù)據(jù)集，其余數(shù)據(jù)集的樣本量均小于1 000。

3.2 聚類效果評價指標

本文選擇三項評估指標，即精確度（ACC）、調整蘭德系數(shù)（ARI）和調整互信息（AMI）來評估各個數(shù)據(jù)集的聚類結果。各個評估指標計算方式如下：

其中：I（f，r）表示樣本數(shù)據(jù)的真實標簽r與聚類結果f之間的互信息；E{I（f，r）}表示互信息I（f，r）的期望；H表示信息熵。

3.3 結果分析

為充分體現(xiàn)出密度峰值聚類算法的特點，本文在基本算法對比上，增加了SDPC、SNN－DPC和DPC－NN三個新算法進行對比。SDPC算法通過引入網格提高了聚類算法的效率；SNN－DPC和DPC－NN算法針對原始密度峰值聚類中的缺陷進行了詳細的改進，提高了聚類的效果。因此本文將KG－DPC算法與DBSCAN、DPC、SDPC、SNN－DPC和DPC－NN作對比分析，結果如圖4和5所示。

從圖4中可以看出，樣本數(shù)據(jù)集flame有兩個類簇，而這兩類的數(shù)據(jù)點分布都較為稀疏，六種聚類算法均能識別出該數(shù)據(jù)集的聚類中心。六種聚類算法相比較：DBSCAN算法能夠準確地找到兩個類簇的聚類中心點，但由于存在噪聲點，需要聯(lián)合調節(jié)兩個參數(shù)，所以聚類結果較差；密度峰值聚類算法（DPC算法）和SDPC算法在找到聚類中心后，無法正確地分配非中心數(shù)據(jù)點，導致數(shù)據(jù)集的聚類效果較差；SNN－DPC、DPC－NN和KG－DPC算法不僅能夠準確地找到兩個類簇的聚類中心點，還可以找出非中心數(shù)據(jù)點所屬的類簇。

從圖5中可以看出，aggregation數(shù)據(jù)集有七類，不同的類中數(shù)據(jù)點的個數(shù)不夠均勻，差異較大，并且不同的類簇會有較多數(shù)據(jù)點連接。DBSCAN、DPC和SDPC算法無法準確地識別出數(shù)據(jù)點應該劃分到哪一個類簇；SNN－DPC、DPC－NN和KG－DPC算法能正確識別數(shù)據(jù)集的類簇個數(shù)和聚類中心，從而得到較好的聚類結果；而KG－DPC算法雖然引入網格化會對聚類質量有影響，但通過優(yōu)化聚類算法的局部密度度量方式和設定閾值，改善了算法對數(shù)據(jù)集中噪聲和異常值的處理能力，使得聚類結果能達到較優(yōu)的程度。

由表2評價指標可知，KG－DPC算法與DPC、DBSCAN、SDPC、SNN－DPC和DPC－NN相比較，聚類結果優(yōu)于DBSCAN、DPC和SDPC算法，但與SNN－DPC和DPC－NN算法的結果差異不 大。對于banknote數(shù)據(jù)集，KG－DPC算法的準確率、調整互信息和調整蘭德系數(shù)分別為0.99、0.94、0.97；DBSCAN、DPC和SDPC算法三個評價指標都小于等于0.90；SNN－DPC和DPC－NN算法的準確率與KG－DPC相同，但SNN－DPC算法的調整互信息和調整蘭德系數(shù)均小于KG－DPC，DPC－NN算法的調整互信息和調整蘭德系數(shù)略大于KG－DPC算法。

從表3可知，在數(shù)據(jù)樣本少的數(shù)據(jù)集上，例如flame數(shù)據(jù)集，KG－DPC算法運行所消耗的時間相比DPC、SNN－DPC和DPC－NN所消耗的時間分別減少了67%、38%、65%；在數(shù)據(jù)樣本較大的數(shù)據(jù)集D31上，KG－DPC算法運行所消耗的時間相比DPC、SNN－DPC和DPC－NN分別減少了33%、46%、42%。

通過上述七個數(shù)據(jù)集的比較，KG－DPC算法的運算效率比DPC、SNN－DPC和DPC－NN分別提高了38%、44%、44%，與SDPC算法運行效率差別不大。由于DPC、SNN－DPC和DPC－NN算法計算的是點與點間的距離dij，而SDPC和KG－DPC算法計算的是網格與網格之間的距離，并且引入了密度閾值，對局部密度進行篩選，篩選出密度稀疏的網格，在篩選后的網格中尋找聚類中心，而不是比較了各個數(shù)據(jù)樣本點的局部密度之后尋找聚類中心，所以提高了聚類的效率。但SDPC算法在計算局部密度時，只考慮了網格內樣本數(shù)據(jù)點的個數(shù)，而未考慮周圍網格對其的影響，其算法精度遠低于KG－DPC的聚類精度。

4 結束語

數(shù)據(jù)聚類將消耗大量的計算資源，為了避免密度峰值聚類算法在計算數(shù)據(jù)樣本點之間的歐氏距離消耗大量的時間，本文將數(shù)據(jù)集映射到相應的網格中，減少了運行的時間；針對密度峰值聚類算法中截斷距離dc的選取具有主觀性，根據(jù)K近鄰的思想定義了一種局部密度計算方式。該計算方式獨立于數(shù)據(jù)集規(guī)模，并且與截斷距離dc無關，有效地避免了截斷距離dc對聚類效果產生影響。在設定密度閾值基礎上，進一步減少了選取聚類中心時的工作量。在對非聚類中心網格進行分配時，不僅計算了與距離最近的類簇中心點的歐氏距離，還計算了與距離最近的類簇所包含的數(shù)據(jù)點之間的歐氏距離，從而降低了分配策略造成連帶錯誤的可能。但如何確定不同數(shù)據(jù)集下的有效網格劃分方式，以進一步提高聚類效率，將是以后研究的方向。

參考文獻：

［1］Li Fuxiang， Shu Li， Yang Tianhao， et al.A new density peak clustering algorithm based on cluster fusion strategy［J］.IEEE Access ， 2022， 10 ： 98034－98047.

［2］Duan Baobin， Wei Ping， Ma Weiyuan. An improved density peak clustering algorithm［C］//Proc of International Conference on Computer Graphics， Artificial Intelligence， and Data Processing. 2023：1044－1052.

［3］Chen Hu Zhou Yuan， Mei Kehui，et al.A new density peak clustering algorithm with adaptive clustering center based on differential privacy［J］.IEEE Access ， 2023， 11 ： 1418－1431.

［4］Rodriguez Laio A. Clustering by fast search and find of density peaks［J］.Science ， 2014，344 （6191）：1492－1496.

［5］徐曉， 丁世飛， 丁玲. 密度峰值聚類算法研究進展［J］. 軟件學報， 2022， 33 （5）： 1800－1816. （Xu Xiao， Ding Shifei， Ding Ling. Research progress on density peak clustering algorithms［J］.Journal of Software Science ， 2022， 33 （5）： 1800－1816.）

［6］陳葉旺， 申蓮蓮， 鐘才明， 等. 密度峰值聚類算法綜述［J］. 計算機研究與發(fā)展， 2020，57 （2）： 378－394. （Chen Yewang， Shen Lianlian， Zhong Caiming，et al.Overview of density peak clustering algorithms［J］.Computer Research and Development ， 2020，57 （2）： 378－394.）

［7］王萬良， 吳菲， 呂闖. 自動確定聚類中心的快速搜索和發(fā)現(xiàn)密度峰值的聚類算法［J］. 模式識別與人工智能， 2019，32 （11）： 1032－1041. （Wang Wanliang， Wu Fei， Lyu Chuang. A fast clustering algorithm for automatically determining clustering centers and discovering density peaks［J］.Pattern Recognition and Artificial Intelligence ， 2019， 32 （11）： 1032－1041.）

［8］江平平， 曾慶鵬. 一種基于網格劃分的密度峰值聚類改進算法［J］. 計算機應用與軟件， 2019， 36 （8）： 268－274，280. （Jiang Pingping， Zeng Qingpeng. An improved density peak clustering algorithm based on grid partitioning［J］.Computer Application and Software ， 2019， 36 （8）： 268－274，280.）

［9］Zhao Chao， Yang Junchuang， Wen Kexin，et al.An improved clustering algorithm based on density peak and nearest neighbors［J］.Mathematical Problems in Engineering ， 2022， 2022 ： 1－10.

［10］馬淑華， 尤海榮， 唐亮， 等. 一種自適應的密度峰值聚類算法［J］. 東北大學學報：自然科學版， 2022， 43 （6）： 761－768. （Ma Shuhu You Hairong， Tang Liang，et al.An adaptive density peak clustering algorithm［J］.Journal of Northeast University：Natural Science Edition ， 2022， 43 （6）： 761－768.）

［11］Yin Lifeng， Wang Yingfeng， Chen Huayue， et al. An improved density peak clustering algorithm for multi－density data［J］.Sensors ， 2022，22 （22）： 8814.

［12］Jiang Jianhu Chen Yujun， Meng Xianqiu，et al.A novel density peaks clustering algorithm based on k nearest neighbors for improving assignment process［J］.Physica A： Statistical Mechanics and Its Applications ， 2019，523 ： 702－713.

［13］王艦. 基于高斯核優(yōu)化的密度峰值聚類算法［J］. 電腦知識與技術， 2020， 16 （28）： 192－194，209. （Wang Jian. Density peak clustering algorithm based on gaussian kernel optimization［J］.Compu－ter Knowledge and Technology ， 2020， 16 （28）： 192－194，209.）

［14］陳蔚昌， 趙嘉， 肖人彬，等. 面向密度分布不均數(shù)據(jù)的近鄰優(yōu)化密度峰值聚類算法［J］. 控制與決策， 2024， 39 （3）：919－928. （Chen Weichang， Zhao Ji Xiao Renbin，et al.Nearest neighbor optimization density peak clustering algorithm for uneven density distribution data［J］.Control and Decision ，2024， 39 （3）：919－928.）

［15］徐紅艷， 普蓉， 黃法欣， 等. 基于網格和密度比的DBSCAN聚類算法研究［J］. 計算機與數(shù)字工程， 2020， 48 （6）： 1269－1274，1285. （Xu Hongyan， Pu Rong， Huang Faxin，et al.Research on DBSCAN clustering algorithm based on grid and density ratio［J］.Computer and Digital Engineering，2020， 48 （6）： 1269－1274，1285.）

［16］黃學雨， 程世超. KNN優(yōu)化的密度峰值聚類算法［J］. 通信技術， 202 54 （7）： 1608－1618. （Huang Xueyu， Cheng Shichao. KNN optimized density peak clustering algorithm［J］.Communication Technology ， 202 54 （7）： 1608－1618.）

［17］楊震， 王紅軍. 基于加權K近鄰的改進密度峰值聚類算法［J］. 計算機應用研究， 2020，37 （3）： 667－671. （Yang Zhen， Wang Hongjun. Improved density peak clustering algorithm based on weighted K－nearest neighbors［J］.Application Research of Computers ， 2020，37 （3）： 667－671.）

［18］Li Tianyi， Yue Shihong， Sun Chang. General density－peaks－clustering algorithm［C］//Proc of IEEE International Instrumentation and Measurement Technology Conference. Piscataway， NJ： IEEE Press， 2021： 1－6.

［19］江婧婷， 鄭朝暉. 面向大規(guī)模節(jié)點劃分的網格密度峰值聚類［J］. 小型微型計算機系統(tǒng)， 2022，43 （3）： 498－505. （Jiang Jingting， Zheng Chaohui. Grid density peak clustering for large－scale node partitioning［J］.Journal of Chinese Computer Systems ， 2022， 43 （3）： 498－505.）

［20］孫昊， 張明新， 戴嬌， 等. 基于網格的快速搜尋密度峰值的聚類算法優(yōu)化研究［J］. 計算機工程與科學， 2017， 39 （5）： 964－970. （Sun Hao， Zhang Mingxin， Dai Jiao，et al.Research on optimization of clustering algorithm for fast searching density peak based on grid［J］.Computer Engineering and Science ， 2017， 39 （5）： 964－970.）

［21］徐曉， 丁世飛， 孫統(tǒng)風，等. 基于網格篩選的大規(guī)模密度峰值聚類算法［J］. 計算機研究與發(fā)展， 2018， 55 （11）： 2419－2429. （Xu Xiao， Ding Shifei， Sun Tongfeng，et al.Large scale density peak clustering algorithm based on grid filtering［J］.Computer Research and Development，2018， 55 （11）： 2419－2429.）

［22］馬福民， 宮婷， 楊帆， 等. 基于Zipf分布的網格密度峰值聚類算法［J］. 控制與決策， 2024， 39 （2）：577－587. （Ma Fumin， Gong Ting， Yang Fan，et al.Grid density peak clustering algorithm based on Zipf distribution［J］.Control and Decision ， 2024， 39 （2）：577－587.）

［23］Liu Rui， Wang Hong， Yu Xiaomei. Shared－nearest－neighbor－based clustering by fast search and find of density peaks［J］.Information Sciences，2018， 450 ： 200－226.

［24］李曉光， 邵超. 基于網格數(shù)據(jù)中心的密度峰值聚類算法［J］. 計算機科學， 2019，46 （S1）： 457－460，487. （Li Xiaoguang， Shao Chao. Density peak clustering algorithm based on grid data centers［J］.Computer Science ， 2019， 46 （S1）： 457－460，487.）

收稿日期：2023－08－01；修回日期：2023－09－30基金項目：國家自然社科基金資助項目（72164034）

作者簡介：劉繼（1974—），男，四川達州人，教授，博導，博士，主要研究方向為數(shù)據(jù)智能分析（liuji5000@126.com）；楊金瑞（1999—），女，安徽潁上人，碩士研究生，主要研究方向為數(shù)據(jù)智能分析．