基于快速密度峰值聚類(lèi)離群因子的離群點(diǎn)檢測(cè)算法

張忠平，李森，劉偉雄，劉書(shū)霞

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

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

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

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

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

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

2) 使用局部密度與相對(duì)距離的乘積來(lái)自動(dòng)選擇聚類(lèi)中心，避免人為選取聚類(lèi)中心。

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

1 相關(guān)工作

1.1 密度峰值聚類(lèi)DPC 算法

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

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

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

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

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

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

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

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

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

圖2 DPC 決策圖

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

算法1密度峰值聚類(lèi)DPC 算法

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

輸出c個(gè)聚類(lèi)

1) for eachx∈Ddo

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

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 相對(duì)距離

10) end for

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

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

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

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

1.2 k 近鄰

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

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

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

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

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

2 FDPC-OF 算法

2.1 快速密度峰值聚類(lèi)算法

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

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

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

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

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

算法2FDPC 算法

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

輸出c個(gè)聚類(lèi)

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

2) for eachx∈Ddo

3) 根據(jù)KD-Tree 和式(3)計(jì)算數(shù)據(jù)對(duì)象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 相對(duì)距離

10) end for

11) for eachx∈Ddo

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

13) end for

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

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

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

2.2 FDPC-OF 算法描述

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

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

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

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

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

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

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

從密度上看，本文首先根據(jù)數(shù)據(jù)集構(gòu)建KD-Tree，然后根據(jù)該索引結(jié)構(gòu)計(jì)算數(shù)據(jù)對(duì)象的KNN 局部密度。該局部密度能很好地表示數(shù)據(jù)對(duì)象所處區(qū)域的密集程度。一般來(lái)說(shuō)，離群點(diǎn)通常處于局部密度較低的區(qū)域。從距離上看，向心相對(duì)距離利用了聚類(lèi)中心與數(shù)據(jù)對(duì)象之間的關(guān)系，能在一些具有不同密度的數(shù)據(jù)集上有較好的適應(yīng)性，通常離群點(diǎn)的向心相對(duì)距離會(huì)比正常點(diǎn)大得多。因此，快速密度峰值聚類(lèi)離群因子能很好地刻畫(huà)數(shù)據(jù)對(duì)象的離群程度，通常情況下離群因子較大的點(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以及聚類(lèi)數(shù)目c

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

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

2) for eachc∈Cdo

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

4) end for

5) for eachx∈Ddo

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

7) end for

8) for eachx∈Ddo

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

10) end for

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

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

2.3 FDPC-OF 算法正確性

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

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

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

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

為了評(píng)估本文所提FDPC-OF 算法的性能，本節(jié)將在真實(shí)數(shù)據(jù)集和人工數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并選取了幾種不同的離群點(diǎn)檢測(cè)算法進(jìn)行對(duì)比實(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)評(píng)價(jià)指標(biāo)

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

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

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

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

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

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

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

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

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

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

FDPC-OF 算法與對(duì)比算法在人工數(shù)據(jù)集上的F1 值如表4 所示。從表4 可以看出，F(xiàn)DPC-OF 算法在4 個(gè)人工數(shù)據(jù)集上的F1 值的均值在93.5%以上，高于對(duì)比算法。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)于對(duì)比算法，在不同人工數(shù)據(jù)集上有著穩(wěn)定的離群點(diǎn)檢測(cè)效率，因此可以證明本文算法在人工數(shù)據(jù)集上的有效性。

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

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

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

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

本節(jié)采用4 種來(lái)自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)本文算法以及對(duì)比算法在真實(shí)數(shù)據(jù)集上的離群點(diǎn)檢測(cè)能力。真實(shí)數(shù)據(jù)集的數(shù)據(jù)特征如表5 所示。

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

FDPC-OF 算法與對(duì)比算法在真實(shí)數(shù)據(jù)集上的精確率如表6 所示。從表6 可以看出，F(xiàn)DPC-OF算法在4 種真實(shí)數(shù)據(jù)集上的Pr 均值約為80%，高于對(duì)比算法。在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)檢測(cè)效率。

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

FDPC-OF 算法與對(duì)比算法在真實(shí)數(shù)據(jù)集上的F1 值如表7 所示。從表7 可以看出，F(xiàn)DPC-OF 算法在4 種人工數(shù)據(jù)集上的F1 值的均值在78.6%以上，高于對(duì)比算法。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)評(píng)估中有著不錯(cuò)的表現(xiàn)，結(jié)合精確度指標(biāo)，本文提出的FDPC-OF算法在不同的真實(shí)數(shù)據(jù)集上有著穩(wěn)定的離群點(diǎn)檢測(cè)效率，因此可以證明本文FDPC-OF 算法在真實(shí)數(shù)據(jù)集上能穩(wěn)定高效地檢測(cè)出離群點(diǎn)。

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

FDPC-OF 算法與對(duì)比算法在真實(shí)數(shù)據(jù)集上的運(yùn)行時(shí)間如圖6 所示。從圖6 可以看出，F(xiàn)DPC-OF算法在4 種人工數(shù)據(jù)集上的運(yùn)行時(shí)間的均值僅為0.16 s，快于其他對(duì)比算法。在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í)間超過(guò)40 s。本文算法在處理大規(guī)模數(shù)據(jù)集時(shí)，仍然有著十分優(yōu)異的運(yùn)行速率，在真實(shí)數(shù)據(jù)集上的運(yùn)行速率在整體上快于其他對(duì)比算法，因此本文算法的計(jì)算效率優(yōu)異。

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

4 結(jié)束語(yǔ)

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