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

哈爾濱理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，哈爾濱 150080

1 引言

在數(shù)據(jù)挖掘領(lǐng)域，聚類分析是一個(gè)十分活躍的研究方向。聚類分析無需具有先驗(yàn)知識，根據(jù)數(shù)據(jù)之間內(nèi)在的關(guān)系，就可以進(jìn)行分類或者劃分，因此得到了廣大科研工作者的青睞。其中基于密度的聚類方法具有可以識別出任意類型的簇，對噪聲不敏感等優(yōu)點(diǎn)。

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

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

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

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

根據(jù)上述對聚類中心的描述篩選聚類中心，然后將非聚類中心點(diǎn)進(jìn)行分配到距離其最近的聚類中心，算法結(jié)束。

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

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

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

2 IDPC（improved density peak cluster）算法

2.1 聚類中心的篩選

在密度峰值聚類算法中，選擇聚類中心，需要計(jì)算所有數(shù)據(jù)點(diǎn)之間的距離，并作出決策圖。這種方法雖然簡單明了，但是時(shí)間復(fù)雜度達(dá)到O(n2)，并且dc值選取不恰當(dāng)?shù)脑?，將無法選擇出正確的聚類中心，造成多米諾骨牌效應(yīng)，使聚類結(jié)果較差。

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

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

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

綜合以上分析，給定數(shù)據(jù)點(diǎn)o，參數(shù)k，數(shù)據(jù)點(diǎn)o的局部密度ρ的計(jì)算公式如式（1）所示。

其中，numk是指數(shù)據(jù)點(diǎn)o和第k近的數(shù)據(jù)點(diǎn)ok之間的距離內(nèi)包含的數(shù)據(jù)點(diǎn)個(gè)數(shù)。dist(o,oi)是指數(shù)據(jù)點(diǎn)oi與數(shù)據(jù)點(diǎn)o之間的歐式距離。

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

成正態(tài)分布的數(shù)據(jù)集的聚類中心的另一個(gè)特征是，大于整個(gè)數(shù)據(jù)集的平均密度。利用這個(gè)特征，可以對聚類中心進(jìn)行過濾篩選。

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

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

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

算法1FliterC(O,k)

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

2.2 離群點(diǎn)的篩選和剪枝

本節(jié)討論數(shù)據(jù)集中的離群點(diǎn)處理。在密度峰值聚類算法中，對于離群點(diǎn)采用了如下方法處理：首先定義邊界區(qū)域，邊界區(qū)域的數(shù)據(jù)點(diǎn)特征是，它們屬于某一個(gè)類簇，即在截?cái)嗑嚯xdc內(nèi)，但在這些數(shù)據(jù)點(diǎn)中存在屬于其他類簇的數(shù)據(jù)點(diǎn)。將這些數(shù)據(jù)點(diǎn)的局部密度計(jì)算出一個(gè)平均密度，這個(gè)平均密度用于區(qū)分這些數(shù)據(jù)點(diǎn)是離群點(diǎn)還是類簇內(nèi)的點(diǎn)。

上述篩選離群點(diǎn)的方法，依賴于截?cái)嗑嚯xdc，而截?cái)嗑嚯xdc的計(jì)算代價(jià)較高，因此本文采用其他的方法進(jìn)行處理。本文在計(jì)算局部密度時(shí)，考慮到目標(biāo)數(shù)據(jù)點(diǎn)與周圍數(shù)據(jù)點(diǎn)之間的距離對局部密度的影響。本文基于這樣一個(gè)直觀認(rèn)知，如果周圍數(shù)據(jù)點(diǎn)距離目標(biāo)數(shù)據(jù)點(diǎn)緊湊，那么目標(biāo)數(shù)據(jù)點(diǎn)則處于一個(gè)相對密集區(qū)域，如果周圍數(shù)據(jù)點(diǎn)距離目標(biāo)數(shù)據(jù)點(diǎn)松散，那么目標(biāo)數(shù)據(jù)點(diǎn)處于相對稀疏的區(qū)域。因此本文選擇局部密度衡量一個(gè)數(shù)據(jù)點(diǎn)所處于稀疏區(qū)域還是密集區(qū)域。

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

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

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

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

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

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

定理1 如果一個(gè)數(shù)據(jù)點(diǎn)有反向最近鄰，那么其反向最近鄰一定在其一級鄰接生成點(diǎn)中。證明見文獻(xiàn)[20]。

下面給出離群點(diǎn)的判斷規(guī)則：

規(guī)則2 如果一個(gè)低于平均密度的數(shù)據(jù)點(diǎn)的反向最近鄰是0，那么該數(shù)據(jù)點(diǎn)是一個(gè)離群點(diǎn)。

規(guī)則3 如果一個(gè)數(shù)據(jù)點(diǎn)的一級鄰接生成點(diǎn)均為離群點(diǎn)，那么這個(gè)數(shù)據(jù)點(diǎn)是一個(gè)離群點(diǎn)。

根據(jù)規(guī)則2、規(guī)則3 和定理1，本文提出判斷一個(gè)數(shù)據(jù)點(diǎn)是否為離群點(diǎn)的規(guī)則4。

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

定理2 給定兩個(gè)低于平均密度的數(shù)據(jù)點(diǎn)a、b，假設(shè)數(shù)據(jù)點(diǎn)a的局部密度大于數(shù)據(jù)點(diǎn)b的局部密度。如果數(shù)據(jù)點(diǎn)a是離群點(diǎn)的話，數(shù)據(jù)點(diǎn)b也一定是離群點(diǎn)。

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

Fig.2 Schematic diagram of outliers圖2 離群點(diǎn)示意圖

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

假設(shè)數(shù)據(jù)點(diǎn){v16,v17,v18,v19,v20}為離群點(diǎn)，那么這些點(diǎn)必然處于密度稀疏點(diǎn)，而v21在這些點(diǎn)中間，也處在密度稀疏區(qū)域，也將v21視為離群點(diǎn)，即規(guī)則3。

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

算法2outlierO(O,k)

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

2.3 數(shù)據(jù)點(diǎn)的分配

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

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

Voronoi圖的相關(guān)定義在2.2 節(jié)已經(jīng)介紹過，下面給出Voronoi圖的性質(zhì)[18]。

性質(zhì)1 任意兩個(gè)多邊形不存在公共區(qū)域。Voronoi圖將數(shù)據(jù)集中數(shù)據(jù)按照其最近屬性將空間進(jìn)行劃分，生成互不重疊的區(qū)域。

性質(zhì)2 在Voronoi 圖區(qū)域內(nèi)的數(shù)據(jù)點(diǎn)，距離其Voronoi圖區(qū)域內(nèi)的生成點(diǎn)的距離最近。

性質(zhì)3 處于兩個(gè)鄰接生成點(diǎn)的生成區(qū)域的Voronoi 圖公共邊上的數(shù)據(jù)點(diǎn)，與兩個(gè)鄰接生成點(diǎn)之間的距離相等。

性質(zhì)4 處于m個(gè)鄰接生成點(diǎn)的生成區(qū)域的在Voronoi 圖公共邊交點(diǎn)處的數(shù)據(jù)點(diǎn)，與這m個(gè)鄰接生成點(diǎn)的距離相等。

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

規(guī)則5 當(dāng)數(shù)據(jù)點(diǎn)分布在m個(gè)鄰接多邊形的共享邊或者共享交點(diǎn)時(shí)，采取隨機(jī)分配的方法將數(shù)據(jù)點(diǎn)分配到m個(gè)鄰接生成點(diǎn)中的一個(gè)代表的類簇上。

如圖3 所示，數(shù)據(jù)點(diǎn)o1、o2在被映射到Voronoi圖中時(shí)，分布到了{(lán)v17,v18,v7,v8}的共享交點(diǎn)和{v7,v8}的共享邊處，因此這時(shí)可根據(jù)規(guī)則5 進(jìn)行判斷o1、o2的歸屬。

Fig.3 Schematic diagram of partial data points distribution圖3 部分?jǐn)?shù)據(jù)點(diǎn)分布示意圖

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

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

Fig.4 Schematic diagram of core point data圖4 核心點(diǎn)數(shù)據(jù)示意圖

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

其中，|ci∩cj|是指以ci或cj為中心，第k近鄰的數(shù)據(jù)點(diǎn)距離兩個(gè)聚類中心的距離為半徑的范圍內(nèi)相交的數(shù)據(jù)點(diǎn)個(gè)數(shù)。|ci∪cj|為兩個(gè)集合并集的數(shù)據(jù)點(diǎn)的個(gè)數(shù)。雖然以半徑為范圍，但是實(shí)際以兩個(gè)Voronoi 區(qū)域內(nèi)的數(shù)據(jù)點(diǎn)個(gè)數(shù)計(jì)算jaccard 系數(shù)。

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

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

算法3 IDPC

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

3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)設(shè)備系統(tǒng)環(huán)境采用Windows 7 的64 位操作系統(tǒng)，計(jì)算機(jī)的硬件配置16 GB RAM，256 GB ROM，處理器Intel?CoreTMi7 處理器（主頻為2.60 GHz）。所有程序使用Java語言進(jìn)行實(shí)現(xiàn)。

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

UCI 數(shù)據(jù)集是公認(rèn)、公開的機(jī)器學(xué)習(xí)/數(shù)據(jù)挖掘數(shù)據(jù)集，許多聚類算法都會使用其驗(yàn)證聚類算法準(zhǔn)確率和有效性。因此本文選擇UCI 中的數(shù)據(jù)作為本文實(shí)驗(yàn)的真實(shí)數(shù)據(jù)集，本文所采用的數(shù)據(jù)信息如表1所示。

Table 1 Data information of UCI data set表1 UCI數(shù)據(jù)集的數(shù)據(jù)信息

在對一個(gè)聚類算法進(jìn)行評價(jià)時(shí)，一般用F-measure熵作為評價(jià)聚類外部的標(biāo)準(zhǔn)，簡寫為F值。用輪廓系數(shù)（silhouette coefficient），簡寫為S值，作為評價(jià)聚類內(nèi)部有效性的指標(biāo)。另一個(gè)聚類評價(jià)指標(biāo)是聚類精度Accuracy，簡寫為Acc值。

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

Table 2 Comparison of evaluation criteria of each algorithm表2 各算法評價(jià)標(biāo)準(zhǔn)對比

在表3 的算法運(yùn)行時(shí)間對比中，因?yàn)镮ris、Heart、Wine 數(shù)據(jù)集的樣本量較少，因此各個(gè)算法運(yùn)行時(shí)間較少，而Waveform 的樣本數(shù)量較多，因此運(yùn)行時(shí)間較慢。從單獨(dú)的各個(gè)樣本的運(yùn)行時(shí)間來看，DBSCAN算法相對較慢。在上述分析中，IDPC算法聚類評價(jià)指標(biāo)，與改進(jìn)DPC 的算法FKNN-DPC、RNN-DBSCAN性能相近，但在時(shí)間對比上，本文算法處理相對較快，表現(xiàn)出更高的效率。

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

Table 3 Comparison of running time of each algorithm表3 各算法的運(yùn)行時(shí)間對比圖

Fig.5 Zigzag data set圖5 Zigzag 數(shù)據(jù)集

對于這兩組人工數(shù)據(jù)集，同樣使用F值和S值進(jìn)行比較，實(shí)驗(yàn)進(jìn)行500 次，取最好結(jié)果作為結(jié)果值，如表4 所示。從表4 可以得到DPC 算法處理流形數(shù)據(jù)Parabolic 和Zigzag 的聚類效果和準(zhǔn)確率，不如其他幾個(gè)算法，這正是DPC 的一個(gè)缺點(diǎn)，就是對于流形數(shù)據(jù)，會產(chǎn)生一些誤差?？v觀整個(gè)算法指標(biāo)信息對比，本文所提IDPC 算法的F值和輪廓系數(shù)S值都表現(xiàn)出比其他算法較好的效果。

Fig.6 Parabolic data set圖6 Parabolic 數(shù)據(jù)集

Table 4 Comparison of experimental results of artificial data表4 人工數(shù)據(jù)實(shí)驗(yàn)結(jié)果對比

Fig.7 Histogram of artificial data experiment running time圖7 人工數(shù)據(jù)實(shí)驗(yàn)運(yùn)行時(shí)間直方圖

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

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

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

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

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

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

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

4 結(jié)束語

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

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