張忠平，李森，劉偉雄，劉書霞

（1.燕山大學(xué)信息科學(xué)與工程學(xué)院，河北 秦皇島 066004；2.河北省計(jì)算機(jī)虛擬技術(shù)與系統(tǒng)集成重點(diǎn)實(shí)驗(yàn)室，河北 秦皇島 066004；3.河北省軟件工程重點(diǎn)實(shí)驗(yàn)室，河北 秦皇島 066004；4.河北科技師范學(xué)院，河北 秦皇島 066004）

0 引言

離群點(diǎn)指的是數(shù)據(jù)集中偏離正常數(shù)據(jù)分布的數(shù)據(jù)，它們的觀測值與其他觀測值有著顯著的不同。離群點(diǎn)檢測就是在數(shù)據(jù)集中發(fā)現(xiàn)離群點(diǎn)的過程，是數(shù)據(jù)挖掘中重要的研究方向。目前，離群點(diǎn)檢測已應(yīng)用在很多領(lǐng)域，如工業(yè)無線傳感器網(wǎng)絡(luò)[1]、欺詐檢測[2-3]、入侵檢測[4]、心電圖異常檢測[5]等。研究者對離群點(diǎn)檢測也提出了很多算法，主要有基于統(tǒng)計(jì)的算法[6-7]、基于距離的算法[8-9]、基于聚類的算法[10-12]和基于密度的算法[13-18]等。

自 Breunig 等[13]提出局部離群因子（LOF,local outlier factor）算法后，基于密度的離群點(diǎn)檢測算法已成為離群點(diǎn)檢測研究領(lǐng)域最熱門的方向之一。該類算法的核心思想是通過密度估計(jì)算法來計(jì)算各數(shù)據(jù)對象的密度，根據(jù)數(shù)據(jù)對象所處的區(qū)域來判斷離群點(diǎn)，離群點(diǎn)通常處于稀疏區(qū)域，離群點(diǎn)的密度相較于正常數(shù)據(jù)對象而言有明顯差異。近年來，隨著聚類方法的發(fā)展，基于聚類的離群點(diǎn)檢測算法已成為離群點(diǎn)檢測研究領(lǐng)域不可或缺的一部分。其核心思想是對數(shù)據(jù)集進(jìn)行聚類，離群點(diǎn)通常處于那些僅包含極少數(shù)據(jù)對象的小規(guī)模集群中。從核心思想上可以看出，上述2 類算法具有一定的相似性，小規(guī)模的集群往往也是稀疏區(qū)域。這2 類算法有各自的優(yōu)缺點(diǎn)，近幾年研究者開始把研究重心放在如何結(jié)合兩者的優(yōu)點(diǎn)上，從而提出一種具有更強(qiáng)穩(wěn)健性的離群點(diǎn)檢測算法。

Rodriguez 等[19]提出了一種具有重要價(jià)值的新型聚類算法——密度峰值聚類（DPC,density peak clustering）算法。DPC 算法是一種簡單高效的聚類算法，可以通過計(jì)算局部密度以及相對距離，將任意維度的數(shù)據(jù)集映射成一個(gè)二維的決策圖，決策圖可以清晰地反映數(shù)據(jù)集的層次關(guān)系；然后選取數(shù)據(jù)集中密度高且距離其他高密度數(shù)據(jù)對象較遠(yuǎn)的數(shù)據(jù)對象作為數(shù)據(jù)集的聚類中心，這些數(shù)據(jù)對象稱為密度峰值點(diǎn)；最后將剩余的數(shù)據(jù)對象分配到距離其最近的聚類中心。相較于其他傳統(tǒng)聚類算法，DPC算法受離群點(diǎn)和噪聲的影響較小，另外，DPC 算法在聚類的過程中不需要多次迭代，因此，不管是從檢測精度還是從時(shí)間效率層面考慮，DPC 算法更適合與離群點(diǎn)檢測算法相結(jié)合。

盡管DPC 算法可以簡單高效地完成聚類，但仍存在一些問題。首先，由于DPC 算法需要計(jì)算各數(shù)據(jù)對象密度，計(jì)算過程中會產(chǎn)生距離矩陣，在增加空間復(fù)雜度的同時(shí)也增大了時(shí)間復(fù)雜度，DPC算法的時(shí)間復(fù)雜度為O(n2)，對于一些大規(guī)模數(shù)據(jù)集，其時(shí)間效率會嚴(yán)重下降。文獻(xiàn)[20]提出了基于網(wǎng)格的密度峰值聚類（DPCG,density peak clustering based on grid)算法，在計(jì)算數(shù)據(jù)對象的局部密度時(shí)采用網(wǎng)格思想計(jì)算距離的方法來代替DPC 算法中計(jì)算數(shù)據(jù)對象之間距離的方法，從而提高了算法計(jì)算速度。其次，DPC 算法在初始時(shí)需要設(shè)置截?cái)嗑嚯xdc且需要人工選擇聚類中心，由于算法對于截?cái)嗑嚯xdc非常敏感，人工設(shè)置容易導(dǎo)致算法精度下降。Huang 等[21]提出自適應(yīng)密度峰值檢測的快速聚類算法，該算法采用非參數(shù)的高斯核密度估計(jì)代替DPC 算法中的密度估計(jì)，不需要設(shè)定截?cái)嗑嚯xdc，還提出了一種基于輪廓優(yōu)化算法的聚類中心選擇方法來自動選擇聚類中心，但該方法在面對一些稀疏且小規(guī)模的簇類數(shù)據(jù)集時(shí)，難以保持正常的精度。

本文針對DPC 算法時(shí)間復(fù)雜度高、截?cái)嗑嚯x的設(shè)定和聚類中心選取的問題進(jìn)行了改進(jìn)，并將改進(jìn)的DPC 算法與離群點(diǎn)檢測相結(jié)合，提出了基于快速密度峰值聚類離群因子（FDPC-OF,fast density peak clustering outlier factor）的離群點(diǎn)檢測算法，簡稱FDPC-OF 算法。本文算法主要分為2 個(gè)階段進(jìn)行工作。第一階段，使用改進(jìn)的DPC 算法計(jì)算聚類中心；第二階段，基于聚類中心定義了向心相對距離，從而提出基于快速密度峰值聚類離群因子（簡稱FOF）來刻畫數(shù)據(jù)對象的離群程度。本文的主要貢獻(xiàn)總結(jié)如下。

1) 本文算法采用 k 近鄰（KNN,k-nearest neighbour）算法代替DPC 算法中密度估計(jì)的部分，避免了設(shè)定截?cái)嗑嚯xdc，并使用k 維樹（KD-Tree,k-dimensional tree）索引數(shù)據(jù)結(jié)構(gòu)計(jì)算各數(shù)據(jù)對象的k 近鄰，降低算法的時(shí)間復(fù)雜度。

2) 使用局部密度與相對距離的乘積來自動選擇聚類中心，避免人為選取聚類中心。

3) 對DPC 算法中的相對距離進(jìn)行改進(jìn)，定義了平均向心距離，并結(jié)合數(shù)據(jù)對象的相對距離以及平均向心距離定義了向心相對距離，結(jié)合向心相對距離和局部密度這2 個(gè)指標(biāo)，提出了基于快速密度峰值聚類離群因子來刻畫數(shù)據(jù)對象的離群程度。

1 相關(guān)工作

1.1 密度峰值聚類DPC 算法

經(jīng)典的聚類算法K-means[22]通過指定初步聚類中心再進(jìn)行迭代更新找到最終聚類中心，由于每個(gè)點(diǎn)都被分配到距離最近的聚類中心，導(dǎo)致其不能檢測非球面類別的數(shù)據(jù)分布。Ester 等[23]提出了DBSCAN（density-based spatial clustering of application with noise）算法，可以對任意形狀分布的數(shù)據(jù)進(jìn)行聚類，但是必須指定一個(gè)密度閾值，從而去除低于此密度閾值的噪聲點(diǎn)。Comaniciu 等[24]提出了MeanShift 算法，采用均值偏移的方式使數(shù)據(jù)點(diǎn)向密度較大的方向延伸，直至收斂到簇中心。但是均值偏移是一個(gè)不斷迭代的過程，時(shí)間復(fù)雜度較高。DPC 算法解決了以上不足，其原理簡單，要求參數(shù)少，不需要迭代，并且能夠識別不同形狀大小的簇。

DPC 算法的核心思想是基于一種假設(shè)，即在任意數(shù)據(jù)分布的數(shù)據(jù)集中，聚類中心通常會被具有較低局部密度的數(shù)據(jù)對象所包圍，并且這些聚類中心與其他具有較高局部密度的數(shù)據(jù)對象之間的距離都相對較大。在這個(gè)假設(shè)的基礎(chǔ)上，DPC 算法需要計(jì)算2 個(gè)指標(biāo)，一個(gè)是數(shù)據(jù)對象的局部密度，另一個(gè)是數(shù)據(jù)對象的相對距離，這2 個(gè)指標(biāo)都需要通過數(shù)據(jù)對象之間的距離dij計(jì)算得出；然后，根據(jù)局部密度和相對距離來構(gòu)建聚類中心決策圖，以此選擇聚類中心；最后，將數(shù)據(jù)集中剩余的數(shù)據(jù)對象分配到距離其最近的聚類中心，完成聚類。

定義1密度峰值聚類局部密度ρi[19]。ρi指數(shù)據(jù)對象xi在截?cái)嗑嚯x內(nèi)包含的其他數(shù)據(jù)對象的個(gè)數(shù)。其計(jì)算式如下

其中，n為數(shù)據(jù)集中數(shù)據(jù)對象的個(gè)數(shù)；dij為數(shù)據(jù)對象xi和xj之間的歐氏距離；截?cái)嗑嚯xdc需要在算法開始時(shí)進(jìn)行初始化設(shè)置；χ(·)為指示函數(shù)，若x＜0，χ(x)=1，若x≥ 0，則χ(x)=0。簡單來說，截?cái)嗑嚯xdc類似于半徑，ρi則是通過指示函數(shù)計(jì)算在半徑范圍內(nèi)其他數(shù)據(jù)對象的個(gè)數(shù)。

定義2密度峰值聚類相對距離δi[19]。δi指數(shù)據(jù)對象xi與其他局部密度比它大的數(shù)據(jù)對象的最短距離。其計(jì)算式如下

對于ρi最大的數(shù)據(jù)對象，通常將它的δi設(shè)置為其與最遠(yuǎn)的對象之間的距離，即δi=maxj(dij)。值得注意的是，當(dāng)xi為DPC 局部或者全局密度最大值時(shí)，DPC 相對距離會大于傳統(tǒng)的k 近鄰距離，因此聚類中心的DPC 相對距離會是非常大的值。

計(jì)算局部密度和相對距離后，DPC 算法根據(jù)這2 個(gè)指標(biāo)構(gòu)建聚類中心決策圖，以此選擇聚類中心，該決策圖的觀測過程是DPC 算法的核心。由28 個(gè)數(shù)據(jù)對象生成的DPC 二維數(shù)據(jù)分布如圖1 所示。從圖1 可以發(fā)現(xiàn)，1 號和10 號數(shù)據(jù)對象分別位于各自簇內(nèi)的密度峰值區(qū)域，因此將其作為聚類中心。

圖1 DPC 二維數(shù)據(jù)分布

由DPC 局部密度和DPC 相對距離所構(gòu)建的DPC 決策圖如圖2 所示，從圖2 可以發(fā)現(xiàn)，首先，雖然9 號和10 號數(shù)據(jù)對象的DPC 局部密度非常接近，但它們在決策圖中所處的位置有非常大的區(qū)別，這是由于10 號數(shù)據(jù)對象在其所在簇中的DPC局部密度為最大值，DPC 局部密度比其大的數(shù)據(jù)對象位于另一個(gè)簇中，而9 號數(shù)據(jù)對象并非其所在簇中DPC 局部密度的最大值，因此10 號數(shù)據(jù)對象的DPC 相對距離比9 號要大得多，更加符合DPC 算法對聚類中心的假設(shè)；其次，由于1 號數(shù)據(jù)對象為DPC 局部密度的最大值，因此通過該決策圖可以輕松選擇出1 號和10 號這2 個(gè)聚類中心；最后，26～28 號數(shù)據(jù)對象具有較高的相對距離和較小的DPC局部密度，此類型的數(shù)據(jù)對象通常作為離群點(diǎn)單獨(dú)成簇。

圖2 DPC 決策圖

通過決策圖完成聚類中心的選定后，DPC 算法將數(shù)據(jù)集中剩余的數(shù)據(jù)對象分配到距離其最近的聚類中心所在的簇中完成聚類。DPC 算法如算法1所示。需要特別注意的是，聚類數(shù)目c和聚類中心需要通過決策圖來人工選定。

算法1密度峰值聚類DPC 算法

輸入初始數(shù)據(jù)集D和截?cái)嗑嚯xdc

輸出c個(gè)聚類

1) for eachx∈Ddo

2) 計(jì)算x與其他數(shù)據(jù)對象之間的歐氏距離

3) end for

4) for eachx∈Ddo

5) 采用式(1)和截?cái)嗑嚯xdc計(jì)算x的DPC 局部密度

6) end for

7) for eachx∈Ddo

8) 遍歷數(shù)據(jù)集D

9) 采用式(2)計(jì)算x的DPC 相對距離

10) end for

11) 根據(jù)計(jì)算得出的DPC 局部密度和DPC 相對距離構(gòu)建二維決策圖

12) 根據(jù)決策圖人工選取聚類中心以及聚類數(shù)目c

13) 將數(shù)據(jù)集中剩余的數(shù)據(jù)對象分配至距離其最近的聚類中心

14) 完成聚類并輸出c個(gè)聚類

1.2 k 近鄰

定義 3k 近鄰距離（KNN-dist,k-nearest neighbours distance）di。di是指xi到其KNN 內(nèi)所有數(shù)據(jù)對象的平均距離。其計(jì)算式如下

其中，KNNi為數(shù)據(jù)對象xi的k 近鄰的集合；dist(xi，xj)為數(shù)據(jù)對象xi和xj之間的距離，通常采用歐氏距離。

定義4KNN 局部密度deni[25]。deni是根據(jù)xi的KNN 距離構(gòu)造的局部密度估計(jì)度量指標(biāo)。其計(jì)算式如下

簡單而言，數(shù)據(jù)對象xi的KNN 局部密度deni等于其KNN 距離di的倒數(shù)。

計(jì)算數(shù)據(jù)對象的KNN 距離時(shí)，需要先計(jì)算各數(shù)據(jù)對象之間的歐氏距離，時(shí)間復(fù)雜度高達(dá)O(n2)。當(dāng)面對大規(guī)模數(shù)據(jù)集時(shí)，算法的時(shí)間效率會隨著數(shù)據(jù)集的增大而快速下降。為了提高算法在大規(guī)模數(shù)據(jù)集上的適用性，本文采用KD-Tree 索引數(shù)據(jù)結(jié)構(gòu)來優(yōu)化KNN 距離的計(jì)算過程，首先對數(shù)據(jù)集進(jìn)行建模，構(gòu)建KD-Tree；然后，根據(jù)該KD-Tree 獲取近鄰樣本數(shù)據(jù)。通過采用KD-Tree 索引結(jié)構(gòu)來計(jì)算數(shù)據(jù)對象的KNN 距離，能將算法的時(shí)間復(fù)雜度優(yōu)化至O(nlogn)。

2 FDPC-OF 算法

2.1 快速密度峰值聚類算法

針對DPC 算法中需要初始化設(shè)置截?cái)嗑嚯x參數(shù)以及需要人工選定聚類中心的問題，本文提出采用KNN 局部密度代替DPC 算法中局部密度估計(jì)，從而避免了人工設(shè)置截?cái)嗑嚯x參數(shù)，解決了DPC算法對于截?cái)嗑嚯x參數(shù)敏感的問題；并且使用局部密度與相對距離的乘積這一指標(biāo)來選定聚類中心，避免了人為選取聚類中心可能出現(xiàn)的問題。另外，為了解決DPC 算法時(shí)間復(fù)雜度高的問題，本文在計(jì)算KNN 局部密度的過程中，采用KD-Tree 索引數(shù)據(jù)結(jié)構(gòu)來幫助計(jì)算各數(shù)據(jù)對象的k 近鄰，降低算法的時(shí)間復(fù)雜度，并且在計(jì)算相對距離的時(shí)候，只考慮數(shù)據(jù)對象的k 近鄰，避免在計(jì)算相對距離時(shí)進(jìn)行全局搜索。

定義5KNN 相對距離ωi。ωi是指數(shù)據(jù)對象xi與k 近鄰內(nèi)其他KNN 局部密度比它大的數(shù)據(jù)對象中的最短距離。其計(jì)算式如下

當(dāng)數(shù)據(jù)對象xi是KNNi內(nèi)的局部密度最大值時(shí)，將其放入鄰居密度最大值集合maxden 中，然后將xi與maxden 中其他數(shù)據(jù)對象之間距離的最小值作為xi的KNN 相對距離ωi，即

定義6聚類中心決策指標(biāo)ceni。ceni指數(shù)據(jù)對象xi的KNN 局部密度和KNN 相對距離的乘積。其計(jì)算式如下

得到KNN 局部密度deni、KNN 相對距離ωi以及聚類中心決策指標(biāo)ceni后，根據(jù)用戶初始化輸入的聚類參數(shù)c選擇ceni最大的前c個(gè)數(shù)據(jù)對象作為聚類中心。最后將數(shù)據(jù)集中剩余的數(shù)據(jù)對象依次分配到距離其距離最近的聚類中心完成聚類?？焖倜芏确逯稻垲悾‵DPC,fast density peak clustering）算法如算法2 所示。

算法2FDPC 算法

輸入初始數(shù)據(jù)集D、參數(shù)k以及聚類數(shù)目c

輸出c個(gè)聚類

1) 根據(jù)數(shù)據(jù)集D構(gòu)建KD-Tree

2) for eachx∈Ddo

3) 根據(jù)KD-Tree 和式(3)計(jì)算數(shù)據(jù)對象x的KNN 距離

4) end for

5) for eachx∈Ddo

6) 采用式(4)計(jì)算x的KNN 局部密度

7) end for

8) for eachx∈Ddo

9) 采用式(5)和式(6)計(jì)算x的KNN 相對距離

10) end for

11) for eachx∈Ddo

12) 采用式(7)計(jì)算x的聚類中心決策指標(biāo)

13) end for

14) 將聚類中心決策指標(biāo)cen 前c大的數(shù)據(jù)對象作為聚類中心

15) 將數(shù)據(jù)集中剩余的數(shù)據(jù)對象分配至距離其最近的聚類中心

16) 完成聚類并輸出c個(gè)聚類

2.2 FDPC-OF 算法描述

本文結(jié)合快速密度峰值聚類的度量指標(biāo)提出FDPC-OF 算法。在完成聚類算法后，為了更好地刻畫離群點(diǎn)在一些具有不同密度的數(shù)據(jù)集上的離群程度，將進(jìn)一步對快速密度峰值聚類中的KNN 相對距離進(jìn)行改進(jìn)。

定義7平均向心距離davgi。davgi指聚類Ci中所有數(shù)據(jù)對象與聚類中心的平均距離。其計(jì)算式如下

其中，m表示聚類Ci的數(shù)據(jù)對象個(gè)數(shù)；dist(xc,xj)表示數(shù)據(jù)對象xj和其所屬聚類的聚類中心xc之間的距離。

定義8向心相對距離disceni。disceni指數(shù)據(jù)對象xi的KNN 相對距離ωi和其所屬聚類的平均向心距離davgi的比值。其計(jì)算式如下

向心相對距離很好地刻畫了離群點(diǎn)在一些不同密度的數(shù)據(jù)集上的離群程度。FDPC 二維數(shù)據(jù)分布如圖3 所示。從圖3 可以看出，24 號數(shù)據(jù)對象為全局離群點(diǎn)，其相對距離為最大值；25 號數(shù)據(jù)對象為局部離群點(diǎn)，其相對距離比稀疏聚類中的正常數(shù)據(jù)對象小，若把KNN 相對距離作為離群指標(biāo)，局部離群點(diǎn)容易被稀疏區(qū)域的正常數(shù)據(jù)對象淹沒。因此，本文在KNN 相對距離的基礎(chǔ)上提出了平均向心距離。由于25 號數(shù)據(jù)對象屬于左側(cè)聚類，KNN相對距離與左側(cè)聚類的平均向心距離的比值放大了該局部離群點(diǎn)的離群特征，更好地刻畫了離群點(diǎn)的離群程度。

圖3 FDPC 二維數(shù)據(jù)分布

定義9快速密度峰值聚類離群因子FOFi。FOFi指數(shù)據(jù)對象xi的向心相對距離disceni和KNN局部密度deni的比值。其計(jì)算式如下

從密度上看，本文首先根據(jù)數(shù)據(jù)集構(gòu)建KD-Tree，然后根據(jù)該索引結(jié)構(gòu)計(jì)算數(shù)據(jù)對象的KNN 局部密度。該局部密度能很好地表示數(shù)據(jù)對象所處區(qū)域的密集程度。一般來說，離群點(diǎn)通常處于局部密度較低的區(qū)域。從距離上看，向心相對距離利用了聚類中心與數(shù)據(jù)對象之間的關(guān)系，能在一些具有不同密度的數(shù)據(jù)集上有較好的適應(yīng)性，通常離群點(diǎn)的向心相對距離會比正常點(diǎn)大得多。因此，快速密度峰值聚類離群因子能很好地刻畫數(shù)據(jù)對象的離群程度，通常情況下離群因子較大的點(diǎn)更有可能為離群點(diǎn)，因此算法選取排序后的離群因子中前o個(gè)點(diǎn)作為離群點(diǎn)輸出，在算法實(shí)際應(yīng)用中，o的取值是根據(jù)實(shí)際數(shù)據(jù)集的情況人為設(shè)定的。在本文實(shí)驗(yàn)中，為了驗(yàn)證所提FDPC-OF 算法在不同數(shù)據(jù)集上的有效性，o的取值根據(jù)數(shù)據(jù)集已有的離群點(diǎn)標(biāo)簽個(gè)數(shù)設(shè)定。FDPC-OF 算法如算法3 所示。

算法3FDPC-OF 算法

輸入初始數(shù)據(jù)集D、參數(shù)k以及聚類數(shù)目c

輸出o個(gè)離群點(diǎn)

1) 調(diào)用算法2 對數(shù)據(jù)集D進(jìn)行聚類，輸出c個(gè)聚類

2) for eachc∈Cdo

3) 采用式(8)計(jì)算c的平均向心距離

4) end for

5) for eachx∈Ddo

6) 采用式(9)計(jì)算x的向心相對距離

7) end for

8) for eachx∈Ddo

9) 采用式(10)計(jì)算x的快速密度峰值聚類的離群因子

10) end for

11) 降序排列快速密度峰值聚類的離群因子

12) 輸出前o個(gè)點(diǎn)作為離群點(diǎn)

2.3 FDPC-OF 算法正確性

FDPC-OF 算法中，KD-Tree 索引數(shù)據(jù)結(jié)構(gòu)能有效降低算法時(shí)間復(fù)雜度，從而提高算法的計(jì)算速率，基于KNN 對每個(gè)數(shù)據(jù)對象進(jìn)行密度估計(jì)能很好地表示數(shù)據(jù)對象所處區(qū)域的疏密程度。根據(jù)算法2進(jìn)行聚類，對每個(gè)聚類計(jì)算平均向心距離，將KNN相對距離與平均向心距離的比值作為向心相對距離能更好地在一些具有不同密度分布的數(shù)據(jù)集上放大離群點(diǎn)的離群特征。通過計(jì)算快速密度峰值聚類離群因子來刻畫數(shù)據(jù)對象的離群程度，并對其進(jìn)行降序排列，輸出前o個(gè)離群點(diǎn)。

2.4 FDPC-OF 算法復(fù)雜性

FDPC-OF 算法的時(shí)間復(fù)雜度主要由以下2 個(gè)部分組成。1) 為計(jì)算數(shù)據(jù)對象的KNN 局部密度構(gòu)建KD-Tree，時(shí)間復(fù)雜度為O(nlogn)，其中n為數(shù)據(jù)集的數(shù)據(jù)對象的個(gè)數(shù)。2) 計(jì)算數(shù)據(jù)對象的快速密度峰值聚類離群因子FOF(x)，時(shí)間復(fù)雜度為O(n) 。因此，F(xiàn)DPC-OF 算法總的時(shí)間復(fù)雜度為O(nlogn)+O(n) ≈O(nlogn)。

3 實(shí)驗(yàn)與分析

為了評估本文所提FDPC-OF 算法的性能，本節(jié)將在真實(shí)數(shù)據(jù)集和人工數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并選取了幾種不同的離群點(diǎn)檢測算法進(jìn)行對比實(shí)驗(yàn)，包括COF（connectivity-based outlier factor）算法[26]、NOF（natural outlier factor）算法[21]、RDOS（relative density-based outlier score）算法[27]、LDF（local density factor）算法[28]、IForest（isolation forest）算法[29]、NANOD（natural neighbour-based outlier detection）算法[30]和MOD（mean-shift outlier detector）算法[31]。實(shí)驗(yàn)環(huán)境如表1 所示。

表1 實(shí)驗(yàn)環(huán)境

3.1 實(shí)驗(yàn)評價(jià)指標(biāo)

本文針對算法有效性的實(shí)驗(yàn)將選取3種性能評估指標(biāo)，分別為：精確率Pr，計(jì)算方法如式(11)所示；加權(quán)評價(jià)指標(biāo)F1 值，計(jì)算方法如式(13)所示；運(yùn)行時(shí)間。其中，精確率也被稱為查準(zhǔn)率，F(xiàn)1 值結(jié)合了精確率和召回率Re 的表現(xiàn)。以上Pr 和F1 值的取值為0～1，其值越大表示離群點(diǎn)檢測算法的檢測效果越好。

其中，TP 為真陽性，表示算法正確檢測為離群點(diǎn)的個(gè)數(shù)；FP 為假陽性，表示算法錯(cuò)誤檢測為離群點(diǎn)的個(gè)數(shù)；FN 為假陰性，表示算法將離群點(diǎn)檢測為正常點(diǎn)的個(gè)數(shù)。

FDPC-OF 算法的相關(guān)參數(shù)設(shè)置如下：k 近鄰中設(shè)置k=5，自動選取聚類中心時(shí)，設(shè)置聚類數(shù)量參數(shù)c=2。

對比算法的相關(guān)參數(shù)設(shè)置如下：RDOS 算法和COF 算法中，k=5；LDF 算法中，θ=0.5，k=5；NOF 算法和NANOD 算法為無參算法；IForest 算法和MOD 算法均采用原文獻(xiàn)中的默認(rèn)設(shè)置。

3.2 人工數(shù)據(jù)集

為了驗(yàn)證本文算法在各種不同的數(shù)據(jù)分布下離群點(diǎn)的檢測能力，本文使用圖4 所示的二維人工數(shù)據(jù)集D1～D4進(jìn)行對比實(shí)驗(yàn)，其中，○表示離群點(diǎn)。D1～D4的數(shù)據(jù)特征如表2 所示。

圖4 二維人工數(shù)據(jù)集

表2 D1～D4 的數(shù)據(jù)特征

FDPC-OF 算法與對比算法在人工數(shù)據(jù)集上的精確率如表3 所示。從表3 可以看出，F(xiàn)DPC-OF算法在4 種人工數(shù)據(jù)集上的Pr 均值在95%以上，顯著優(yōu)于對比算法，在數(shù)據(jù)集D1上的Pr 高達(dá)100%；在數(shù)據(jù)集D2上的Pr 與LDF 算法相等，均在97%以上。FDPC-OF 算法在4 種人工數(shù)據(jù)集上的離群點(diǎn)檢測穩(wěn)定性優(yōu)于對比算法，這是由于FDPC-OF 算法結(jié)合聚類中心的概念提出了向心相對距離，提高了算法在不同密度的數(shù)據(jù)集上的適用性。

表3 不同算法在人工數(shù)據(jù)集上的精確率

FDPC-OF 算法與對比算法在人工數(shù)據(jù)集上的F1 值如表4 所示。從表4 可以看出，F(xiàn)DPC-OF 算法在4 個(gè)人工數(shù)據(jù)集上的F1 值的均值在93.5%以上，高于對比算法。LDF 算法在數(shù)據(jù)集D2上的F1值與FDPC-OF 算法相等，均在95%以上；RDOS算法的在數(shù)據(jù)集D1和D4上的F1 值表現(xiàn)較好，在D1上F1 值高達(dá)96.6%，但在數(shù)據(jù)集D2和D3上表現(xiàn)不佳；NANOD 算法在4 個(gè)人工數(shù)據(jù)集上整體表現(xiàn)不理想；MOD 算法在4 個(gè)人工數(shù)據(jù)集上表現(xiàn)穩(wěn)定。從總體上看，F(xiàn)DPC-OF 算法的F1 值優(yōu)于對比算法，在不同人工數(shù)據(jù)集上有著穩(wěn)定的離群點(diǎn)檢測效率，因此可以證明本文算法在人工數(shù)據(jù)集上的有效性。

表4 不同算法在人工數(shù)據(jù)集上的F1 值

FDPC-OF 算法與對比算法在人工數(shù)據(jù)集上的運(yùn)行時(shí)間如圖5 所示。從圖5 可以看出，F(xiàn)DPC-OF算法在4 種人工數(shù)據(jù)集上的運(yùn)行時(shí)間的均值僅為0.29 s，快于對比算法。IForest 算法由于不需要計(jì)算各數(shù)據(jù)對象之間的距離，因此時(shí)間復(fù)雜度為線性，在人工數(shù)據(jù)集上運(yùn)行時(shí)間略長于FDPC-OF 算法；COF 算法、NOF 算法、RDOS 算法以及LDF算法需要計(jì)算各數(shù)據(jù)對象之間的距離，因此時(shí)間復(fù)雜度至少為O(n2)，與FPDC-OF 算法和IForest 算法有較大差距；MOD 算法在尋找KNN 鄰域質(zhì)心的過程中需要迭代計(jì)算，當(dāng)數(shù)據(jù)量和維度增加時(shí)，該算法的時(shí)間復(fù)雜度會極大增加。FDPC-OF 算法在人工數(shù)據(jù)集上的運(yùn)行時(shí)間在整體上優(yōu)于對比算法，這是由于FDPC-OF 算法在計(jì)算k 近鄰時(shí)使用了索引結(jié)構(gòu)，從而降低了算法的時(shí)間復(fù)雜度，同時(shí)FDPC-OF算法計(jì)算過程簡單。

圖5 不同算法在人工數(shù)據(jù)集上的運(yùn)行時(shí)間

3.3 真實(shí)數(shù)據(jù)集

本節(jié)采用4 種來自UCI的真實(shí)數(shù)據(jù)集[32]進(jìn)行實(shí)驗(yàn)，分別是Ionosphere、Iris、Wdbc 和Vowels。真實(shí)數(shù)據(jù)集選取的離群點(diǎn)比例為3.4%～35.9%，屬性個(gè)數(shù)為4～34 個(gè)，保證了離群點(diǎn)比例以及數(shù)據(jù)集的屬性個(gè)數(shù)的多樣性和復(fù)雜性，能更好地檢驗(yàn)本文算法以及對比算法在真實(shí)數(shù)據(jù)集上的離群點(diǎn)檢測能力。真實(shí)數(shù)據(jù)集的數(shù)據(jù)特征如表5 所示。

表5 真實(shí)數(shù)據(jù)集的數(shù)據(jù)特征

FDPC-OF 算法與對比算法在真實(shí)數(shù)據(jù)集上的精確率如表6 所示。從表6 可以看出，F(xiàn)DPC-OF算法在4 種真實(shí)數(shù)據(jù)集上的Pr 均值約為80%，高于對比算法。在Iris 數(shù)據(jù)集上，NANOD 算法表現(xiàn)最好，Pr 達(dá)到80%；在Wdbc 數(shù)據(jù)集上，F(xiàn)DPC-OF算法的Pr 與NANOD 算法和MOD 算法相等，為最高值。FDPC-OF 算法在不同規(guī)模、不同屬性個(gè)數(shù)以及不同離群點(diǎn)比例的真實(shí)數(shù)據(jù)集上有著穩(wěn)定的離群點(diǎn)檢測效率。

表6 不同算法在真實(shí)數(shù)據(jù)集上的精確率

FDPC-OF 算法與對比算法在真實(shí)數(shù)據(jù)集上的F1 值如表7 所示。從表7 可以看出，F(xiàn)DPC-OF 算法在4 種人工數(shù)據(jù)集上的F1 值的均值在78.6%以上，高于對比算法。LDF 算法在Ionosphere 以及Iris數(shù)據(jù)集上的F1 值表現(xiàn)優(yōu)異，均值在75%以上，但在其余數(shù)據(jù)集上表現(xiàn)一般；NANOD 算法和MOD算法的F1 值接近，在4 個(gè)真實(shí)數(shù)據(jù)集上都有著不錯(cuò)的表現(xiàn)，NANOD 算法在Iris 數(shù)據(jù)集上的F1 值表現(xiàn)最優(yōu)，達(dá)到80%，MOD 算法在Wdbc 數(shù)據(jù)集上的表現(xiàn)與FDPC-OF 算法相等，為最高值。從總體上看，F(xiàn)DPC-OF 算法在F1 值的指標(biāo)評估中有著不錯(cuò)的表現(xiàn)，結(jié)合精確度指標(biāo)，本文提出的FDPC-OF算法在不同的真實(shí)數(shù)據(jù)集上有著穩(wěn)定的離群點(diǎn)檢測效率，因此可以證明本文FDPC-OF 算法在真實(shí)數(shù)據(jù)集上能穩(wěn)定高效地檢測出離群點(diǎn)。

表7 不同算法在真實(shí)數(shù)據(jù)集上的F1 值

FDPC-OF 算法與對比算法在真實(shí)數(shù)據(jù)集上的運(yùn)行時(shí)間如圖6 所示。從圖6 可以看出，F(xiàn)DPC-OF算法在4 種人工數(shù)據(jù)集上的運(yùn)行時(shí)間的均值僅為0.16 s，快于其他對比算法。在Ionosphere 以及Wdbc數(shù)據(jù)集上，F(xiàn)DPC-OF 算法、COF 算法以及IForest算法有著優(yōu)異的運(yùn)行速率，運(yùn)行時(shí)間均少于1 s；在Iris 數(shù)據(jù)集上，各數(shù)據(jù)集的運(yùn)行速率均有著不錯(cuò)的運(yùn)行速率，運(yùn)行時(shí)間均少于1 s；而在Vowels 數(shù)據(jù)集上除了本文FDPC-OF 算法以及IForest 算法的運(yùn)行時(shí)間少于1 s 以外，其他算法的運(yùn)行速率表現(xiàn)不佳，其中NOF 算法、RDOS 算法以及LDF 算法的運(yùn)行時(shí)間超過40 s。本文算法在處理大規(guī)模數(shù)據(jù)集時(shí)，仍然有著十分優(yōu)異的運(yùn)行速率，在真實(shí)數(shù)據(jù)集上的運(yùn)行速率在整體上快于其他對比算法，因此本文算法的計(jì)算效率優(yōu)異。

圖6 不同算法在真實(shí)數(shù)據(jù)集上的運(yùn)行時(shí)間

4 結(jié)束語

本文首先分析了密度峰值聚類DPC 算法和其算法思想，針對密度峰值聚類算法時(shí)間復(fù)雜度高以及需要人工設(shè)置參數(shù)的問題進(jìn)行了深入的研究，給出了一種快速密度峰值聚類算法，使用k 近鄰算法代替密度峰值聚類中的密度估計(jì)，使用索引數(shù)據(jù)結(jié)構(gòu)對距離計(jì)算進(jìn)行優(yōu)化，極大地減少了聚類的時(shí)間復(fù)雜度，并避免了設(shè)置截?cái)嗑嚯xdc。本文定義了向心相對距離，給出了基于快速密度峰值聚類離群因子來刻畫數(shù)據(jù)對象的離群程度，從而提出了基于快速密度峰值聚類離群因子的離群點(diǎn)檢測算法。對所提算法的正確性和復(fù)雜性進(jìn)行分析，在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)證明，F(xiàn)DPC-OF 算法能夠高效全面地檢測出離群點(diǎn)。