基于密度峰值和近鄰優化的聚類算法*

何云斌，董 恒，萬 靜，李 松

哈爾濱理工大學 計算機科學與技術學院，哈爾濱 150080

1 引言

在數據挖掘領域，聚類分析是一個十分活躍的研究方向。聚類分析無需具有先驗知識，根據數據之間內在的關系，就可以進行分類或者劃分，因此得到了廣大科研工作者的青睞。其中基于密度的聚類方法具有可以識別出任意類型的簇，對噪聲不敏感等優點。

文獻[1]提出了基于密度的典型代表算法DBSCAN（density-based spatial clustering of applications with noise），可以識別出任意形狀的數據，并對噪聲不敏感，但時間復雜度略高，并且對鄰域參數(ε,MinPts)比較敏感，不同的參數可能會得到不同結果。因此文獻[2]對DBSCAN 算法改進，提出了OPTICS（ordering points to identify the clustering structure）算法，使得基于密度的算法得到了更廣泛的適用。文獻[3]提出“分而治之”和并行方法對DBSCAN 算法改進，通過對數據進行劃分，利用“分而治之”思想減少全局變量Eps值的影響，以及采用并行處理方法和降維技術提高聚類效率，降低了DBSCAN 算法對內存的較高要求。Huang等提出了一種基于網格和密度的混合聚類算法GRPDBSCAN（grid-based DBSCAN algorithm with referential parameters），該算法可以有效處理噪聲點，且運算效率較高，自動生成鄰域參數(ε,MinPts)[4]。這些對聚類算法的討論，使聚類研究得到了更深入和廣泛的應用。

Rodriguez 等[5]在2014 年提出了DPC（clustering by fast search and find of density peaks）算法。該算法簡單高效，不需要迭代運算，性能不受數據空間維度的影響，對于聚類過程采取的是基于密度的方法，核心思想是對聚類中心的描述：

（1）聚類中心被不高于它的密度點所包圍；

（2）與其他聚類中心的相對距離更大。

根據上述對聚類中心的描述篩選聚類中心，然后將非聚類中心點進行分配到距離其最近的聚類中心，算法結束。

密度峰值算法有一些局限性，比如截斷距離由用戶根據經驗選取，若選取的不合適，則聚類結果較差。此外，在度量數據點的密度時，只有一個恒定不變的截斷距離參數，這在同一簇內同時擁有多個高密度點的情況下，無法取得良好的聚類效果。針對這些問題，文獻[6]提出信息熵來計算截斷距離的方法。文獻[7-8]都提出使用網格的方法進行改進。其中文獻[7]的主要思想是通過自適應多分辨率的網格劃分思想把數據劃分到多個網格空間中，然后在每個網格空間中進行密度峰值聚類，進而利用網格邊界合并聚類結果。文獻[8]則是引入稀疏網格篩選的方法，去除一部分不可能成為聚類中心的點，只保留稠密網格單元中的點進行聚類中心的選擇，其余步驟則與原DPC 算法相同。文獻[9]提出利用Voronoi圖對數據進行處理，并結合MapReduce 模型實現了DPC算法在大規模數據下的應用。文獻[10]則指出算法EDDPC[9]（efficient distributed density peaks clustering algorithm）存在大量的冗余數據復制和計算開銷，進而提出基于z值的分布式DPC 算法，該算法的設計也是結合了MapReduce模型。

文獻[11]提出了基于共享最近鄰的密度峰值算法，該算法有效改善了DPC 算法對于一些類簇不能有效識別的缺點。文獻[12]結合半監督約束、密度聚類和層次聚類等思想，提出了一種基于約束的DPC算法。文獻[13]從兩方面來對DPC 算法進行改進：一是從聚類中心開始對數據點的K-最近鄰居進行廣度優先搜索來指定非異常值；二是使用模糊加權K最近鄰居技術分配異常值和第一次分配過程未分配的數據點。文獻[14]提出基于自然最近鄰優化的方法優化密度峰聚類。文獻[15]針對DPC 算法的dc值不能自適應，導致不能夠有效應對復雜數據集的問題，提出利用基尼不純度找到最優的dc值。文獻[16]則在局部密度的計算上使用KNN（K-nearest neighbor）的方法改進，在后續數據點的分配時，提出了兩種分配策略。文獻[17]在利用高斯函數計算局部密度時，將考慮范圍限制在dc范圍內并在判斷相似類簇合并時提出了相應的標準。這些算法從不同角度對DPC算法進行改進，并經過實驗驗證取得了良好的聚類效果和準確性，但時間復雜度卻居高不下。

針對密度峰值算法，本文從以下幾個方面進行改進：首先，提出基于K最近鄰方法計算局部密度，以改進密度峰值算法不能準確衡量數據點的真實局部密度的不足，根據聚類中心的特點，對聚類中心進行兩步篩選，從而準確篩選出聚類中心。然后，依據離群點的特征，結合Voronoi 圖，去除離群點的影響。最后，結合層次聚類的思想解決簇之間的合并分裂問題，以改進密度峰值聚類算法不能適應復雜環境數據如流形數據的不足。

2 IDPC（improved density peak cluster）算法

2.1 聚類中心的篩選

在密度峰值聚類算法中，選擇聚類中心，需要計算所有數據點之間的距離，并作出決策圖。這種方法雖然簡單明了，但是時間復雜度達到O(n2)，并且dc值選取不恰當的話，將無法選擇出正確的聚類中心，造成多米諾骨牌效應，使聚類結果較差。

如圖1 所示，實線圓的半徑都為dc，直虛線的長度相同。根據文獻[5]的計算局部密度的方法，A中②的局部密度為7，而B中⑥的局部密度為5。但是如果通過選取第k個近鄰內的數據點的個數，來算②和⑥的密度，則結果就不一樣。假設k為7，則A中②的密度為7，B中⑥的密度為10，⑥的密度大于②的密度。直觀上來看，使用K近鄰的方法，更符合各數據點的真實局部密度。

Fig.1 Schematic diagram of cluster center圖1 聚類中心示意圖

為更好地衡量數據點局部密度，將目標數據點與K近鄰內的數據點之間的距離也作為一個考慮因素。如圖1 所示，若選擇前5 個數據點，A中的②相對于B中的⑥，處于更為緊湊的地方，②的局部密度理應大于⑥。因此可以得出，目標數據點周圍數據點距離與目標數據點的局部密度成反相關關系。

綜合以上分析，給定數據點o，參數k，數據點o的局部密度ρ的計算公式如式（1）所示。

其中，numk是指數據點o和第k近的數據點ok之間的距離內包含的數據點個數。dist(o,oi)是指數據點oi與數據點o之間的歐式距離。

在上述計算局部密度時，采用了KNN 方法，該方法的局限性是需要事先指定k值，但是相對于原DPC算法事先指定dc值，指定k值要相對容易一些。雖然在指定k值之后，k值也像原DPC 算法指定dc值之后一樣不再發生變化，但是每個數據點的k個近鄰點的分布卻是不一樣的，結合式（1）的具體計算局部密度方法可知，本文所采用的KNN 方法計算局部密度更為符合數據點的真實情況。KNN 算法另一個局限性是無法考慮樣本之間的相關性，由于本文探討和處理的數據，不涉及高維數據，因此不構成影響。本文選擇采用KNN 方法計算局部密度。

成正態分布的數據集的聚類中心的另一個特征是，大于整個數據集的平均密度。利用這個特征，可以對聚類中心進行過濾篩選。

本文通過兩步篩選的策略來選擇聚類中心。第一步：基于K最近鄰的思想，進行初步篩選聚類中心，首先尋找數據點o的K最近鄰，根據式（1）計算數據集O中所有的數據點的局部密度，然后計算數據集O的平均密度，將平均密度作為一條分界線，高于平均密度的數據點作為候選聚類中心，并將這些候選聚類中心從高到低進行排序，存入到集合preC中。第二步：根據密度峰值算法對聚類中心的描述，提出規則1 對候選聚類中心進行篩選。

規則1 在候選聚類中心集合preC中，首先選擇擁有局部密度最大的數據點oi，將數據點oi加入到候選聚類中心集合realC中，然后從集合preC中判斷所有低于其局部密度的數據點是否在oi的dok內，dok是指數據點oi與距離其第k近的數據點之間的距離。將所有局部密度低于oi并且在oi的dok內的數據點及數據點oi，從候選聚類中心集合preC中刪除。循環上述過程，直至候選聚類中心集合preC為空。

依據以上分析和規則，給出算法FliterC的主要思想：首先計算數據點oi的局部密度，求出所有數據點的平均密度，然后進行第一步過濾篩選操作，即將那些局部密度低于平均密度的數據點過濾掉，只留下高于平均密度的數據點，并采用快速排序的方法將這些高密度點進行遞減排序。接下來，根據規則1，進行第二步精煉篩選操作，直至得到聚類中心。基于以上分析，下面給出篩選聚類中心具體算法FilterC，如算法1 所示。

算法1FliterC(O,k)

算法時間復雜度分析：假設數據集中數據點的個數為n，篩選過后的preC集合大小為m。步驟1～步驟3，只有一個for 循環，可得時間復雜度為O(n)，同樣步驟5～步驟9，時間復雜度也是O(n)，步驟10 采用快速排序，時間復雜度為O(nlbn)，在步驟11～步驟19 中有一層for 循環，因為這個for 循環遍歷的是preC集合，因此最壞情況下的時間復雜度為O(m)。綜上所述，時間復雜度為O(nlbn)。

2.2 離群點的篩選和剪枝

本節討論數據集中的離群點處理。在密度峰值聚類算法中，對于離群點采用了如下方法處理：首先定義邊界區域，邊界區域的數據點特征是，它們屬于某一個類簇，即在截斷距離dc內，但在這些數據點中存在屬于其他類簇的數據點。將這些數據點的局部密度計算出一個平均密度，這個平均密度用于區分這些數據點是離群點還是類簇內的點。

上述篩選離群點的方法，依賴于截斷距離dc，而截斷距離dc的計算代價較高，因此本文采用其他的方法進行處理。本文在計算局部密度時，考慮到目標數據點與周圍數據點之間的距離對局部密度的影響。本文基于這樣一個直觀認知，如果周圍數據點距離目標數據點緊湊，那么目標數據點則處于一個相對密集區域，如果周圍數據點距離目標數據點松散，那么目標數據點處于相對稀疏的區域。因此本文選擇局部密度衡量一個數據點所處于稀疏區域還是密集區域。

在2.1 節中討論了聚類中心在一個成正態分布的數據集中應該處于平均密度之上，而對于離群點的局部密度應該是處于平均密度之下，因此從這個角度出發，如果一個數據點低于整個數據集的平均密度，那么它就可能成為離群點。因此本文從那些處于平均密度以下的數據點中，進行離群點的篩選和剪枝操作。為了便于查找離群點，本文提出基于Voronoi 圖的方法進行查找，首先給出Voronoi 的相關定義：

定義1（Voronoi 圖[18]）給定一組生成點O={o1,o2,…,on}?R2，其中2 ＜n＜∞，且當(i≠j)時，oi≠oj。其中i,j∈{1,2,…,n}。由oi所決定的區域稱為Voronoi單元VO，Voronoi 圖構成為VD(O)={VO(o1),VO(o2),…,VO(on)}，其中VO(oi)表示的是oi所在的Voronoi單元。

定義2（鄰接多邊形[19]）共享相同邊的Voronoi多邊形稱為鄰接多邊形，它們的生成點被稱為鄰接生成點。Voronoi 單元存在幾條邊，就會有幾個鄰接多邊形。

定義3（Voronoi 圖的t級鄰接生成點[18]）給定一組生成點O={o1,o2,…,on}?R2。oi的t級鄰接生成點定義如下：

（1）一級鄰接生成點AG1(oi)={oj|VO(oi) 和VO(oj)有公共邊}；

（2）t(t≥2)級鄰接生成點AGt(oi)={oj|VO(o)和VO(oj)有公共邊，o∈AGt-1(oi)}。

定理1 如果一個數據點有反向最近鄰，那么其反向最近鄰一定在其一級鄰接生成點中。證明見文獻[20]。

下面給出離群點的判斷規則：

規則2 如果一個低于平均密度的數據點的反向最近鄰是0，那么該數據點是一個離群點。

規則3 如果一個數據點的一級鄰接生成點均為離群點，那么這個數據點是一個離群點。

根據規則2、規則3 和定理1，本文提出判斷一個數據點是否為離群點的規則4。

規則4 對于一個低于平均密度的數據點o，首先找其一級鄰接生成點，依次判斷其一級鄰接生成點的最近鄰是否為數據點o，如果都不是，則數據點o為離群點；如果是，則判斷其一級鄰接生成點是否均為離群點，如果均為離群點，那么數據點o也為離群點，進行剪枝處理。

定理2 給定兩個低于平均密度的數據點a、b，假設數據點a的局部密度大于數據點b的局部密度。如果數據點a是離群點的話，數據點b也一定是離群點。

證明 假設數據點a的局部密度高于數據點b的局部密度，根據對局部密度的定義可知，數據點的局部密度與其周圍的數據點分布有關，如果一個數據點是離群點，那么該數據點則處于一個稀疏區域。由此可知，如果數據點a是離群點，那么數據點a處于稀疏區域，既然數據點b的局部密度小于數據點a，那么數據點b也必然處于更為稀疏的區域，那么b肯定是離群點。 □

Fig.2 Schematic diagram of outliers圖2 離群點示意圖

如圖2 所示，根據定理1 得到，如果一個數據點具有反向最近鄰，則必然在其一級鄰接點內。假設數據點v17沒有反向最近鄰，也就意味著，數據點v17不是任何數據點的近鄰點，處于密度稀疏區，那么就將數據點v17視為離群點，即規則2。

假設數據點{v16,v17,v18,v19,v20}為離群點，那么這些點必然處于密度稀疏點，而v21在這些點中間，也處在密度稀疏區域，也將v21視為離群點，即規則3。

通過以上論述和分析以及提出的定理1、定理2，規則2、規則3、規則4，下面給出關于離群點篩選剪枝算法outlierO的主要思想：給定數據集O，首先計算數據集O中數據點的局部密度，進而算出平均密度并篩選出所有低于平均密度的數據點，按遞減順序進行排序，并存入集合outO中。然后，將所有數據點作為生成點，生成Voronoi 圖，將集合outO中的數據點根據局部密度大小，從大到小進行逐個判斷是否為離群點，如果是離群點，則從數據集O中刪除該點及后續所有數據點，并停止判斷，離群點篩選剪枝算法過程結束。下面給出具體的離群點篩選剪枝算法outlierO，如算法2 所示。

算法2outlierO(O,k)

算法時間復雜度分析：假設數據集的大小為n，篩選過后的數據集outO的大小為m。算法有三個循環：步驟1～步驟3 為第一個循環，時間復雜度為O(n)；步驟5～步驟9 為第二個循環，由于遍歷的數據是整個數據集O，因此時間復雜度為O(n)；步驟12～步驟17 為第三個循環，當遇到數據點是離群點時，停止遍歷，由于遍歷的數據集為篩選過后outO，因此時間復雜度肯定是不大于O(n)。步驟10 使用快速排序的方法對數據集outO進行遞減排序，時間復雜度為O(mlbm)，步驟11 生成Voronoi 圖的時間復雜度為O(nlbn)。綜上所述，該算法的時間復雜度為O(nlbn)。

2.3 數據點的分配

本節討論非聚類中心點、非離群點，即普通數據點如何進行聚類劃分的問題。在密度峰值聚類算法中，針對數據點分配問題的算法是在選擇聚類中心時，計算了所有數據點到其最近密度更高的數據點的距離，因此在篩選出聚類中心后，將剩余的數據點根據先前計算出的信息，直接進行分配即可，該算法分配數據點步驟的高效是建立在前期計算出的信息上面。由于本文提出的聚類中心篩選算法，沒有獲取數據集中數據點兩兩之間的距離信息以及數據點距離密度比其高的最近數據點的距離，因此無法利用密度峰值聚類算法對數據點分配的方法，如果繼續采用原方法的話，則需重新進行計算，這將造成巨大的計算代價，會導致整個聚類算法時間復雜度提高。

本文借鑒密度峰值算法對于數據點的分配思想，通過對以上問題的分析，利用Voronoi 圖的性質，提出基于Voronoi圖的分配策略。該策略無需利用兩兩數據點之間的距離信息，就可以完成數據點的分配操作。

Voronoi圖的相關定義在2.2 節已經介紹過，下面給出Voronoi圖的性質[18]。

性質1 任意兩個多邊形不存在公共區域。Voronoi圖將數據集中數據按照其最近屬性將空間進行劃分，生成互不重疊的區域。

性質2 在Voronoi 圖區域內的數據點，距離其Voronoi圖區域內的生成點的距離最近。

性質3 處于兩個鄰接生成點的生成區域的Voronoi 圖公共邊上的數據點，與兩個鄰接生成點之間的距離相等。

性質4 處于m個鄰接生成點的生成區域的在Voronoi 圖公共邊交點處的數據點，與這m個鄰接生成點的距離相等。

首先根據算法FliterC對數據點的預處理操作后生成的聚類中心，作為Voronoi 圖的生成點，生成Voronoi 圖，根據Voronoi 圖的性質，可以得到在某一個Voronoi區域內的數據點距離其所在區域的生成點最近，那么可以將其劃分到對應的生成點所代表的類簇中。這時會出現對于分布在鄰接多邊形的共享邊，共享交點處的數據點怎樣進行劃分的問題，如圖3 所示。針對這個問題，本文根據性質2、性質3、性質4，對于分布在共享邊、共享交點處的數據點，提出規則5 進行解決。

規則5 當數據點分布在m個鄰接多邊形的共享邊或者共享交點時，采取隨機分配的方法將數據點分配到m個鄰接生成點中的一個代表的類簇上。

如圖3 所示，數據點o1、o2在被映射到Voronoi圖中時，分布到了{v17,v18,v7,v8}的共享交點和{v7,v8}的共享邊處，因此這時可根據規則5 進行判斷o1、o2的歸屬。

Fig.3 Schematic diagram of partial data points distribution圖3 部分數據點分布示意圖

基于以上論述和分析，結合Voronoi圖的性質，本文提出基于Voronoi 圖的分配方法，首先將一些初始聚類中心作為Voronoi圖生成點生成Voronoi圖，這些點將整個區域劃分成一個個鄰接多邊形，將那些不是離群點的數據點映射到整個區域中，根據這些數據點在Voronoi 圖哪個鄰接多邊形區域中，就將其劃分歸屬于哪個類簇，對于在共享邊、共享交點處的數據點則按照規則5 進行判斷歸于哪個類簇，進而可以得到初始的類簇劃分。在2.1 節篩選出的聚類中心，只是一個初始聚類中心，因此基于這個聚類中心劃分的數據點形成的類簇，也只是一個初始的類簇，并非最終的類簇劃分結果。

此外基于Voronoi圖的劃分方法的不足是無法正確識別出流形數據。比如：圖4 所示是一個流形數據的部分，其中三角形數據點為聚類中心點，取k=2時，根據基于Voronoi圖的劃分方法，則會將其分裂成3 個簇o1、o2、o3，這顯然是不對的。

Fig.4 Schematic diagram of core point data圖4 核心點數據示意圖

針對上述問題，采用層次聚類的思想，使用式（2）計算這些候選聚類中心集合C中的兩兩之間的jaccard 相似系數，若其jaaccrd 系數≥距離閾值α，則視為同一組元素，進行合并，直至得出最后的聚類結果，其中距離閾值α由人工設定。

其中，|ci∩cj|是指以ci或cj為中心，第k近鄰的數據點距離兩個聚類中心的距離為半徑的范圍內相交的數據點個數。|ci∪cj|為兩個集合并集的數據點的個數。雖然以半徑為范圍，但是實際以兩個Voronoi 區域內的數據點個數計算jaccard 系數。

如圖3 所示，在Voronoi 區域{v19,v18,v21}3 個區域中，雖然由Voronoi 圖的性質2 可知在各自的Voronoi區域內的數據點距離其生成點最近，將這些數據點都劃分到生成點所代表的類簇中。但經過觀察可以發現，各自數據點互相之間的分布極為接近，如果此時將其分成3 個類簇，則是一種錯誤的分類，根據實際情況理應劃分為一類，這時可以通過給定的k值和閾值α，找到k距離內數據點，然后利用式（2）判斷是否超過閾值α，比較各個初始類簇的相似程度，進而判斷是否可以進行類簇的合并。

基于以上分析以及2.1 節、2.2 節的討論，下面給出算法IDPC 的主要思想：首先將數據集O中的數據點作為鄰接生成點，生成Voronoi 圖。其次利用outlierO算法篩選和剪枝離群點，得到新的數據集O，然后利用FliterC算法進行聚類中心的篩選，將篩選出的聚類中心作為生成點生成新的Voronoi 圖，并將其余的數據點映射進Voronoi圖中。最后隨機選擇一個生成點采用廣度優先遍歷的方法，逐級掃描其鄰接區域，使用式（2）判斷兩者jaccard 系數是否超過閾值α，進而判斷是否進行合并，直至得到最后的結果簇。下面給出聚類算法IDPC，如算法3 所示。

算法3 IDPC

算法時間復雜度分析：假設數據集O的大小為n，篩選過后的preC集合大小為m。步驟1 的時間復雜度為O(nlbn)，步驟2 的時間復雜度已經在2.1 節分析得到的是O(nlbn)。步驟3～步驟5 主要是生成Voronoi 圖需要耗費時間，生成Voronoi 圖的時間復雜度為O(mlbm)。步驟6～步驟18 時間主要消耗在候選區域的兩兩比較上面，但并不是一個數據點需要與所有的數據點進行比較，而只是與其一級鄰接點比較。根據文獻[18]可知，平均情況下，每個數據點的一級鄰接點的個數為[1,6]個，因此時間復雜度不會達到O(m2)，在最壞情況下的時間復雜度為O(6m) 。綜上所述，總時間復雜度為O(nlbn)。

3 實驗結果與分析

實驗設備系統環境采用Windows 7 的64 位操作系統，計算機的硬件配置16 GB RAM，256 GB ROM，處理器Intel?CoreTMi7 處理器（主頻為2.60 GHz）。所有程序使用Java語言進行實現。

本文所提算法IDPC 將在人工數據集與真實數據集上驗證可行性，與DPC[5]算法、DBSCAN[1]算法、對DPC 算法進行改進的FKNN-DPC[13]（fuzzy weightedK-nearest neighbors density peak clustering）算法、基于反向最近鄰的RNN-DBSCAN[21]（reverse nearest neighbor density-based spatial clustering of applications with noise）算法進行比較與分析。

UCI 數據集是公認、公開的機器學習/數據挖掘數據集，許多聚類算法都會使用其驗證聚類算法準確率和有效性。因此本文選擇UCI 中的數據作為本文實驗的真實數據集，本文所采用的數據信息如表1所示。

Table 1 Data information of UCI data set表1 UCI數據集的數據信息

在對一個聚類算法進行評價時，一般用F-measure熵作為評價聚類外部的標準，簡寫為F值。用輪廓系數（silhouette coefficient），簡寫為S值，作為評價聚類內部有效性的指標。另一個聚類評價指標是聚類精度Accuracy，簡寫為Acc值。

在F值、S值和Acc值中，值的取值范圍為[0,1]，并且越接近1，說明效果越好。對上述算法進行100次聚類，取各算法的各指標值的平均值作為其最終的結果值，如表2 所示。從表2 中可以得到，在這些密度聚類算法中，IDPC 算法不論是在F值還是在S值的表現上，都比DPC 和DBSCAN 算法要好一些，而與FKNN-DPC 與RNN-DBSCAN 等算法表現出相近的效果。

Table 2 Comparison of evaluation criteria of each algorithm表2 各算法評價標準對比

在表3 的算法運行時間對比中，因為Iris、Heart、Wine 數據集的樣本量較少，因此各個算法運行時間較少，而Waveform 的樣本數量較多，因此運行時間較慢。從單獨的各個樣本的運行時間來看，DBSCAN算法相對較慢。在上述分析中，IDPC算法聚類評價指標，與改進DPC 的算法FKNN-DPC、RNN-DBSCAN性能相近，但在時間對比上，本文算法處理相對較快，表現出更高的效率。

上述是在真實數據集上的實驗結果與分析，下面進行人工數據集的實驗。第一組人工數據集稱為Zigzag，由1 002 個數據點生成，包含3 個類簇，1 個如鋸齒形狀的流形簇，2 個球狀簇，如圖5 所示。第二組人工數據集稱為Parabolic，由1 000 個數據點生成兩條對繞拋物線形狀的類簇，如圖6 所示。

Table 3 Comparison of running time of each algorithm表3 各算法的運行時間對比圖

Fig.5 Zigzag data set圖5 Zigzag 數據集

對于這兩組人工數據集，同樣使用F值和S值進行比較，實驗進行500 次，取最好結果作為結果值，如表4 所示。從表4 可以得到DPC 算法處理流形數據Parabolic 和Zigzag 的聚類效果和準確率，不如其他幾個算法，這正是DPC 的一個缺點，就是對于流形數據，會產生一些誤差。縱觀整個算法指標信息對比，本文所提IDPC 算法的F值和輪廓系數S值都表現出比其他算法較好的效果。

Fig.6 Parabolic data set圖6 Parabolic 數據集

Table 4 Comparison of experimental results of artificial data表4 人工數據實驗結果對比

Fig.7 Histogram of artificial data experiment running time圖7 人工數據實驗運行時間直方圖

圖7 是各算法的運行時間對比的直方圖，從圖中可以看出，DBSCAN 算法相對DPC 算法來說較為耗費時間，但是各項聚類指標要優于DPC 算法。這與真實數據集上得到的結果、表現出的特征略有不同，從這里可以看出在處理流形數據時，DBSCAN 算法要略優于DPC 算法。結合表4 來看，FKNN-DPC 算法比其他算法時間消耗要多，主要是在考慮共享近鄰時花費的時間代價較大，但是帶來好處是F值和S值要好一些。本文所提的IDPC 算法，在時間代價上面要優于其他算法，但是在聚類指標F值和S值上和FKNN-DPC 算法相近，比RNN-DBSCAN 算法要好一些。

表5 展示了各個算法在不同數據集上的聚類精度，其中加粗部分為多次實驗取得的最優值，“—”表示沒有對應值。在UCI 的4 個數據集上，本文所提算法要優于其他算法的聚類精度。此外，在人工數據集Zigzag 和Parabolic 方面，從圖5 和圖6 可知這兩 個數據集是較為復雜的數據集，既包含流形數據，也包含了流形數據與普通形狀數據混合的數據，但從表5 展示的聚類精度可得，相比于其他算法，本文所提算法在處理這類復雜數據時可以取得更高的聚類精度。

Table 5 Comparison of clustering accuracy of different algorithms in different data sets表5 各算法在不同數據集聚類精度對比

Fig.8 Clustering accuracy of different distance thresholds α圖8 不同距離閾值α的聚類精度

IDPC 算法中包含一個距離閾值α，下面討論分析距離閾值α對IDPC 算法的影響。本文選擇通過在復雜數據集Zigzag 和Parabolic 下，不同距離閾值α對IDPC 算法產生的聚類精度影響進行實驗，并給出距離閾值α的選取原則。從圖5 和圖6 可知，Zigzag數據集是一個鋸齒形數據加兩個圓形數據的數據集，Parabolic 數據集是兩個對繞的條形數據。圖8 展示了不同距離閾值α，IDPC 算法處理Zigzag 數據集和Parabolic 數據集獲得的聚類精度。對于Zigzag 數據集，距離閾值α從1 增長到5，獲得的聚類精度也跟著從62.1%增長到93.3%，繼續增加距離閾值α到16，可以發現，聚類精度從距離閾值α為5 時的93.3%開始一直呈現下降趨勢。觀察整個變化情況，在距離閾值α為5 時，IDPC 算法處理Zigzag 數據集可以獲得最高的聚類精度。對于Parabolic 數據集，距離閾值α從1 增長到4，聚類精度從60.2%增長到95.1%，然后聚類精度開始隨著距離閾值α的增長呈現下降趨勢。通過觀察圖8 可知，IDPC 算法在距離閾值α為4 時取得最高的聚類精度95.1%。

通過上述實驗過程和結果的分析，可以得出距離閾值α在不斷增長的情況下，IDPC 算法處理數據集得到的聚類效果（本文選擇聚類精度指標進行衡量）是呈現先升后降的趨勢，并且只需在選取一定范圍的距離閾值α進行少量數次實驗，進行統計，當出現明顯的下降趨勢時，即可停止實驗，就可以確定出最佳的距離閾值α參數。結合表5 可知，只要距離閾值α選取適當，IDPC 算法相比其他實驗算法處理復雜數據集可以取得更高的聚類精度，而距離閾值α的選取也相對原DPC 算法的dc值要相對容易一些，對人的經驗依賴性也較小。

綜上所述，在聚類效果相近的情況下，本文所提算法更加節約時間，具有更高的效率。在處理復雜數據時，本文所提算法相比其他算法，具有更為良好的聚類效果。

4 結束語

在聚類算法中，基于密度的聚類算法，具有一個顯著的優勢，就是可以識別出任意形狀的類簇，密度峰值算法是近年來基于密度的聚類算法新星，其對聚類中心的描述，是其聚類算法的核心所在，但其缺陷是時間復雜度較高，本文提出基于K近鄰的方法遴選初始聚類中心并結合Voronoi圖進行了聚類的優化處理，提出了基于密度峰值和近鄰優化的IDPC 聚類算法。通過實驗證明，本文所提聚類算法具有較好的聚類效果和準確率。

下一步將探討在障礙環境和移動環境下的聚類算法。