張忠平，劉偉雄，張玉停，鄧禹，魏棉鑫

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

1 引言

離群點(diǎn)是數(shù)據(jù)集中偏離大部分?jǐn)?shù)據(jù)對象的數(shù)據(jù)，它們的表現(xiàn)和大多數(shù)數(shù)據(jù)對象有著明顯的差異。離群點(diǎn)并不等同于錯誤數(shù)據(jù)，反而可能蘊(yùn)含著極其重要的信息。離群點(diǎn)檢測就是從海量數(shù)據(jù)中發(fā)現(xiàn)異常數(shù)據(jù)對象，是數(shù)據(jù)挖掘中的熱門研究方向。目前，離群點(diǎn)檢測廣泛運(yùn)用于工業(yè)無線傳感器網(wǎng)絡(luò)[1]、醫(yī)療處理[2]、欺詐檢測[3]、垃圾郵件檢測[4]、入侵檢測[5-6]等領(lǐng)域，且有很多種分類，包括基于統(tǒng)計(jì)的[7-8]、基于距離的[9-10]、基于聚類的[11-13]和基于密度的[14-19]等方法。

基于統(tǒng)計(jì)的檢測方法是根據(jù)現(xiàn)有的數(shù)據(jù)集結(jié)合統(tǒng)計(jì)學(xué)的方法生成模型，這類方法根據(jù)數(shù)據(jù)對象在模型中是否處于低概率區(qū)域來判斷離群點(diǎn)。這類檢測方法需要充分的數(shù)據(jù)先驗(yàn)知識，并且對于高維數(shù)據(jù)集的檢測效果較差。

基于距離的檢測方法主要通過計(jì)算數(shù)據(jù)集中每個數(shù)據(jù)對象和鄰居點(diǎn)的距離來檢測離群點(diǎn)，其中k 最近鄰（KNN,k nearest neighbor）算法[9]是基于距離的方法中較常用的算法，基本原理是通過計(jì)算數(shù)據(jù)對象與其k個最近鄰居的平均距離，通常離群點(diǎn)會遠(yuǎn)離正常點(diǎn)，因此平均距離越大，越有可能是離群點(diǎn)。由于KNN 算法通過全局距離來檢測離群點(diǎn)，因此無法檢測出局部離群點(diǎn)。

基于聚類的檢測方法是一種無監(jiān)督的學(xué)習(xí)方法，用作聚類的數(shù)據(jù)集不需要類標(biāo)簽，基本思想是將數(shù)據(jù)集通過聚類算法得到簇，并將數(shù)據(jù)對象與簇進(jìn)行比較，通常離群點(diǎn)不屬于任何密集簇。常用的算法有DBSCAN[12]和CHAMELEON[13]。然而此類方法需要根據(jù)不同的應(yīng)用場景和數(shù)據(jù)本身特征采用不同的聚類方法，因此檢測的有效性依賴于聚類方法的選用。

在基于密度的檢測方法中，如果一個數(shù)據(jù)對象為離群點(diǎn)，那它的密度與其周圍鄰居的密度會有很大的差異。這類密度檢測方法主要通過數(shù)據(jù)對象的局部密度和其鄰域密度的差異來判斷離群點(diǎn)。為了實(shí)現(xiàn)這個想法，研究人員提出了很多基于密度的離群點(diǎn)檢測算法。其中局部離群因子（LOF,local outlier factor）算法[14]是最常用的一種離群點(diǎn)檢測算法。LOF 代表一個數(shù)據(jù)對象的離群得分，用于表示該對象與其局部可達(dá)鄰域之間的差異。該方法利用2 個數(shù)據(jù)對象之間可達(dá)距離來估計(jì)該對象的密度，該對象的離群得分是根據(jù)數(shù)據(jù)對象相對于其鄰域?qū)ο蟮南鄬γ芏鹊贸鰜淼?。文獻(xiàn)[14]表明，離群得分更高的數(shù)據(jù)對象更有可能是離群點(diǎn)。之后，研究人員提出了很多基于LOF 的改進(jìn)算法。Zhang 等[16]提出了一種基于局部距離的離群因子（LDOF,local distance-based outlier factor）算法來度量離群得分。文獻(xiàn)[17]在LDOF 算法的基礎(chǔ)上，增加了熵權(quán)距離的定義，改進(jìn)并提出了一種基于熵權(quán)距離和局部密度的離群點(diǎn)檢測（ELDOF,local entropy weight distance-based outlier factor）算法。

近年來，基于核的方法在離群點(diǎn)檢測和聚類等領(lǐng)域得到了廣泛的應(yīng)用，基于核的方法利用核函數(shù)及其參數(shù)建立算法模型。文獻(xiàn)[18]提出了一種基于密度的離群點(diǎn)檢測算法，該算法將核密度估計(jì)（KDE,kernel density estimation）納入LOF 框架中，并將一個數(shù)據(jù)對象的KDE 標(biāo)準(zhǔn)化成S分?jǐn)?shù)，與其鄰域的KDE 進(jìn)行比較。

與本文算法最相似的算法是基于自然鄰居的離群點(diǎn)檢測（NaNOD,natural neighbour-based outlier detection）算法[19]，該算法是一種非監(jiān)督的基于密度的離群點(diǎn)檢測算法，使用自然鄰居概念，自適應(yīng)地獲取一個自然值（NV,natural value）的參數(shù)，并使用加權(quán)核密度估計(jì)（WKDE,weighted kernel density estimation）方法來估計(jì)數(shù)據(jù)對象的密度。另外，該算法采用了KNN 以及反向k 最近鄰（RNN,reverse k-nearest neighbor），使系統(tǒng)可以靈活地對不同數(shù)據(jù)模式進(jìn)行建模，并采用高斯核函數(shù)來實(shí)現(xiàn)度量的平滑性。此外，該算法使用自適應(yīng)核寬度概念來增強(qiáng)正常樣本與離群樣本之間的區(qū)分能力。

分析近年來較新穎的基于密度的離群點(diǎn)檢測算法和相關(guān)算法思想可以發(fā)現(xiàn)，大多數(shù)基于密度的檢測算法在一些低密度的區(qū)域內(nèi)和在高維數(shù)據(jù)集上的檢測效果會有所下降。因此，本文在已有算法的基礎(chǔ)上，考慮到在低密度區(qū)域內(nèi)局部離群點(diǎn)與內(nèi)部點(diǎn)密度相近的問題，提出相對距離的概念，可以有效地將其區(qū)分開來，從而提高算法在低密度區(qū)域處理局部離群點(diǎn)的能力。此外，本文還考慮到高維度對于離群點(diǎn)檢測的影響，并不是所有屬性對離群點(diǎn)檢測都是有作用的，因此本文引用了信息熵加權(quán)距離（EWdist,entropy-weighted distance）的概念，取代傳統(tǒng)算法中的歐氏距離，為數(shù)據(jù)對象的不同屬性分配不同的權(quán)重，給離群屬性分配更高的權(quán)重，能放大離群點(diǎn)的離群程度，從而提高算法在一些高維數(shù)據(jù)集中的檢測能力。針對上述問題，本文提出了一種基于相對熵權(quán)密度離群因子的離群點(diǎn)檢測（ERDOF,outlier detection based on entropy weight distance and relative density outlier factor）算法來檢測離群點(diǎn)。

2 相關(guān)工作

2.1 自然鄰居

Zhu 等[20]提出了一個新的無參數(shù)鄰居的概念，稱為自然鄰居。如果數(shù)據(jù)對象x把數(shù)據(jù)對象y看作自己的鄰居，同時y也把x看作自己的鄰居，那么就把x看作y的自然鄰居。一般地，在稀疏區(qū)域內(nèi)的數(shù)據(jù)對象擁有較少的鄰居，而在稠密區(qū)域內(nèi)的數(shù)據(jù)對象則擁有更多的鄰居。

更重要的是，自然鄰居可以在不使用任何參數(shù)的情況下有效地計(jì)算鄰域。其主要思路是不斷擴(kuò)展鄰居的搜索范圍，每次搜索時記錄每個數(shù)據(jù)對象被看作其他對象的鄰居的次數(shù)，直到不被其他數(shù)據(jù)對象看作鄰居的對象個數(shù)不變。由于數(shù)據(jù)對象在數(shù)據(jù)集中的KNN以及RNN的搜索代價較高，因此本文在自然鄰居搜索算法[20]中使用Ball-Tree[21]。Ball-Tree是一個輕量級的二叉樹，在高維數(shù)據(jù)集上性能良好且查詢效率高。自然鄰居搜索算法[20]流程如算法1所示。

算法1自然鄰居搜索算法

輸入初始數(shù)據(jù)集D

輸出自然近鄰值NV

18) 輸出自然近鄰值NV

在算法1 中，r表示鄰域搜索范圍，NaN(x)表示對象x被其他對象看作鄰居的次數(shù)，KNNr(x)表示對象x的r最近鄰域，RNNr(y)表示對象y的反向r最近鄰域。本文在算法1 中應(yīng)用了Ball-Tree 來提高鄰域的搜索效率，時間復(fù)雜度為O(nlogn)，其中n表示數(shù)據(jù)集中對象的數(shù)量。

定義1自然鄰域。KNNk(xi)和RNNk(xi)合并生成對象xi的擴(kuò)展鄰域空間稱為自然鄰域，定義為IS(xi)=KNNk(xi) ∪RNNk(xi)。其中，鄰域的k值不是人為設(shè)定的，而是通過算法1 自適應(yīng)得出的自然近鄰值NV。

2.2 熵權(quán)距離

本文在計(jì)算數(shù)據(jù)對象之間的距離的時候，使用熵權(quán)距離取代傳統(tǒng)算法中的歐氏距離，下面，給出信息熵加權(quán)距離的定義和信息熵加權(quán)算法[17]的流程描述。

設(shè)數(shù)據(jù)集D={x1,x2,…,xn]，其中n為數(shù)據(jù)樣本大小。設(shè)屬性集A={A1,A2,…,Ad}，其中d為數(shù)據(jù)樣本維度數(shù)量。信息熵表示信息的不確定程度。熵值越大，信息的不確定程度越大，信息熵計(jì)算方法如式(1)所示。

其中，S(Ai)是屬性Ai(i=1,2,…,d)所有可能的取值的集合。

定義2離群屬性。在數(shù)據(jù)集D中，若屬性Ai的信息熵大于或等于數(shù)據(jù)集的平均信息熵，則稱之為離群屬性。

通過式(2)的判斷，符合條件的屬性Ai看作離群屬性。根據(jù)條件判斷公式分類屬性后，各屬性的權(quán)重wi取值如式(3)所示，其中l(wèi)＞ 1。

在數(shù)據(jù)集中，并非所有屬性對離群點(diǎn)檢測都是有作用的，因此，在計(jì)算距離時，為離群屬性提供更大的權(quán)值能更好地突顯離群點(diǎn)的離群程度，從而提高離群點(diǎn)和內(nèi)部點(diǎn)的區(qū)分能力，其中參數(shù)l在本文中默認(rèn)設(shè)定為1.5。

定義3熵權(quán)距離。熵權(quán)距離是具有信息熵加權(quán)的歐氏距離。對象o與對象p的熵權(quán)距離定義如式(4)所示。

其中，fAi(o) 為對象o在屬性Ai上的取值，wi(i=1,2,…,d)為屬性Ai相應(yīng)的權(quán)值。

2.3 高斯核密度估計(jì)

設(shè)數(shù)據(jù)集D={x1,x2,…,xn}，其中n為數(shù)據(jù)樣本大小。為了計(jì)算數(shù)據(jù)對象不同于其自然鄰域的偏差程度，首先進(jìn)行局部密度的估計(jì)。由于不確定數(shù)據(jù)集的分布情況，本文選用無參數(shù)的高斯核密度估計(jì)（GKDE,Gaussian kernel density estimation）方法[22]來估計(jì)數(shù)據(jù)對象的密度，該方法使用自適應(yīng)核寬度概念來提高離群點(diǎn)和內(nèi)部點(diǎn)之間的區(qū)分能力和平滑正常樣本點(diǎn)（內(nèi)部點(diǎn)）之間的差異。

使用GKDE 在隨機(jī)樣本x1,x2,…,xn(xi∈Dd)上進(jìn)行局部密度估計(jì)，計(jì)算方法如式(5)所示。

其中，K(·)表示核函數(shù)；hj表示對應(yīng)數(shù)據(jù)對象j自適應(yīng)得出的核帶寬，用于控制密度估計(jì)的平滑度。本文選用零均值、單位標(biāo)準(zhǔn)差的多變量d維的高斯核函數(shù)，計(jì)算方法如式(6)所示。

本文選用的GKDE 方法[22]只通過數(shù)據(jù)對象的鄰域去估計(jì)對象xi的局部密度，而不是通過整個數(shù)據(jù)集去估計(jì)。因?yàn)槿绻ㄟ^整個數(shù)據(jù)集去估計(jì)，有可能無法檢測到局部的離群點(diǎn)。

局部離群點(diǎn)如圖1 所示。從圖1 可以看出，C2集合的點(diǎn)整體間距、密度和分散情況較一致，可以認(rèn)為是同一個簇；雖然相較于C2集合的點(diǎn)，C1集合的點(diǎn)較分散，但不難看出，C1集合的點(diǎn)也屬于同一個簇。o1、o2相對孤立，可以視作離群點(diǎn)或異常點(diǎn)。如果通過整個數(shù)據(jù)集去估計(jì)對象的密度，全局離群點(diǎn)o1可以較容易地分離出來，但局部離群點(diǎn)o2的密度與C1簇中的點(diǎn)的密度相近，有可能無法檢測到局部離群點(diǎn)o2，導(dǎo)致算法的準(zhǔn)確率下降。

圖1 局部離群點(diǎn)

在基于全局的離群點(diǎn)檢測算法中，KNN 算法[9]是較常用的算法，為了驗(yàn)證KNN 算法在此類數(shù)據(jù)分布中的不足，本文使用KNN 算法在圖1 數(shù)據(jù)集上進(jìn)行離群得分的計(jì)算，結(jié)果如表1 所示。KNN 算法中離群得分越大的點(diǎn)越有可能是離群點(diǎn)，而局部離群點(diǎn)o2的離群得分比C1簇的最大離群得分低，因此KNN 算法無法檢測出局部離群點(diǎn)o2。

表1 KNN 算法在圖1 上的離群得分

此外，通過整個數(shù)據(jù)集進(jìn)行密度估計(jì)的計(jì)算成本較高（O(n2)）。

為了更好地估計(jì)數(shù)據(jù)對象在鄰居中的密度，本文使用數(shù)據(jù)對象xi的 k 最近鄰（ρIS(xi)=和反向k 最近鄰（RNNk）的并集作為數(shù)據(jù)對象的鄰域。其中數(shù)據(jù)對象xi的RNNk表示把xi看作自己的k 最近鄰的集合，實(shí)驗(yàn)表明RNNk可以更好地提供局部分布信息，將其用于檢測離群點(diǎn)有較好的效果[23]。

因此，式(5)對于對象xi的密度估計(jì)的計(jì)算如式(7)所示。

綜合式(6)和式(7)，對象xi的密度估計(jì)的計(jì)算如式(8)所示。

2.4 自適應(yīng)核帶寬

本文選用了高斯核密度估計(jì)方法[22]對數(shù)據(jù)對象進(jìn)行密度估計(jì)，在傳統(tǒng)的核密度估計(jì)方法里，核帶寬都是預(yù)先設(shè)置好且固定的。但在使用的過程中會發(fā)現(xiàn)，在一些高密度區(qū)域里，使用過高的核帶寬會使密度估計(jì)結(jié)果過于平滑，影響實(shí)驗(yàn)結(jié)果；此外，在一些低密度區(qū)域里，使用過低的核帶寬會導(dǎo)致產(chǎn)生噪聲估計(jì)。

圖2(a)表示在高密度區(qū)域設(shè)置不同核帶寬對數(shù)據(jù)點(diǎn)密度估計(jì)的影響。當(dāng)設(shè)置合適的核帶寬時，各個數(shù)據(jù)點(diǎn)的密度為虛線所對應(yīng)的曲線，能較準(zhǔn)確地表示數(shù)據(jù)點(diǎn)的密度分布。當(dāng)設(shè)置過高的核帶寬時，各個數(shù)據(jù)點(diǎn)的密度為實(shí)線所對應(yīng)的曲線，過高的核帶寬會導(dǎo)致高密度區(qū)域的密度分布過于平滑，掩蓋了數(shù)據(jù)大部分的基礎(chǔ)結(jié)構(gòu)，從而影響實(shí)驗(yàn)結(jié)果。

圖2(b)表示在低密度區(qū)域設(shè)置不同核帶寬對數(shù)據(jù)點(diǎn)密度估計(jì)的影響。當(dāng)設(shè)置合適的核帶寬時，各個數(shù)據(jù)點(diǎn)的密度為虛線所對應(yīng)的曲線，能較準(zhǔn)確地表示數(shù)據(jù)點(diǎn)的密度分布。當(dāng)設(shè)置過低的核帶寬時，各個數(shù)據(jù)點(diǎn)的密度為實(shí)線所對應(yīng)的曲線，過低的核帶寬會導(dǎo)致低密度區(qū)域數(shù)據(jù)點(diǎn)的密度分布波動較劇烈，會產(chǎn)生大量噪聲估計(jì)，從而影響實(shí)驗(yàn)結(jié)果。

圖2 核帶寬對密度估計(jì)影響

因此本文需要為數(shù)據(jù)對象設(shè)置一個相對較優(yōu)的核帶寬，這一般取決于數(shù)據(jù)對象在數(shù)據(jù)集中所處的特定位置。為了獲取這樣的核帶寬，本文引入自適應(yīng)核帶寬的概念[22]，目的是提高離群點(diǎn)和內(nèi)部點(diǎn)的區(qū)分能力和平滑正常樣本點(diǎn)（內(nèi)部點(diǎn)）之間的差異。對于數(shù)據(jù)對象xi，取其KNNk鄰域內(nèi)平均距離，記為davg(xi)，如式(9)所示。

此外，取數(shù)據(jù)集{davg(xi)|i=1,2,3,…,n}中的最大值和最小值，分別記為dmax和dmin。自適應(yīng)核帶寬hi的計(jì)算方法如式(10)所示。

其中，θ(θ＞ 0)是密度估計(jì)中用于控制平滑度的參數(shù)；δ是一個非常小的正數(shù)，是為了防止核帶寬取值為0。

3 ERDOF 算法

3.1 相對距離

本文提出了一種相對距離的概念，記為σi?？紤]到在低密度區(qū)域內(nèi)局部離群點(diǎn)與內(nèi)部點(diǎn)的密度相近的問題，因此在計(jì)算數(shù)據(jù)對象的離群程度時，除了考慮數(shù)據(jù)對象的密度外，增加對數(shù)據(jù)對象相對距離的計(jì)算，進(jìn)一步刻畫數(shù)據(jù)對象的離群程度，能有效地把局部離群點(diǎn)和內(nèi)部點(diǎn)、邊界點(diǎn)區(qū)分開，從而提高算法在低密度區(qū)域處理局部離群點(diǎn)的能力。

定義4相對距離。相對距離是指數(shù)據(jù)對象到相對于密度比它大的數(shù)據(jù)對象的距離中的最小值。

對于密度最大的數(shù)據(jù)對象，本文通常給它取一個很小的正數(shù)作為該數(shù)據(jù)對象的相對距離。通常情況下，內(nèi)部點(diǎn)處于一個密度較相近的區(qū)域內(nèi)，相對距離的取值較小，而離群點(diǎn)常處于稀疏區(qū)域，密度比其大的點(diǎn)通常處于相對較遠(yuǎn)的位置，所以離群點(diǎn)的相對距離的值會比較大。通過該方法得出的相對距離，能夠有效地提高ERDOF 算法區(qū)分內(nèi)部點(diǎn)和離群點(diǎn)的能力。

在完成對所有數(shù)據(jù)對象的密度估計(jì)以及相對距離的計(jì)算后，為了更好地刻畫數(shù)據(jù)對象的離群程度，本文提出了相對熵權(quán)密度離群因子的概念，進(jìn)一步刻畫數(shù)據(jù)對象的離群程度，進(jìn)而提出了一種基于相對熵權(quán)密度離群因子的離群點(diǎn)檢測算法ERDOF 來檢測數(shù)據(jù)集中的離群點(diǎn)。

3.2 相對熵權(quán)密度離群因子

定義5相對熵權(quán)密度離群因子。相對熵權(quán)密度離群因子是由相對距離和核密度的比值所構(gòu)成的，計(jì)算方法如式(12)所示。

該離群因子由相對距離和核密度的比值構(gòu)成。從密度上看，本文首先通過計(jì)算自然鄰居自適應(yīng)獲取k值，然后對數(shù)據(jù)集上的屬性進(jìn)行信息熵的計(jì)算，劃分離群屬性和非離群屬性，為離群屬性在計(jì)算距離時提供更大的權(quán)值。運(yùn)用高斯核密度估計(jì)[22]結(jié)合自然鄰居和熵權(quán)距離的概念計(jì)算每個數(shù)據(jù)對象的密度，為了在不同數(shù)據(jù)分布都能得到較優(yōu)的密度估計(jì)，本文引用了自適應(yīng)核帶寬的概念自適應(yīng)獲取相對較優(yōu)的核帶寬。其中密度相對較高的對象通常處于簇的內(nèi)部，而密度相對較低的對象則有可能為離群點(diǎn)。同時考慮到在一些低密度區(qū)域和邊界上的數(shù)據(jù)對象難以僅憑密度的大小進(jìn)行判斷。因此，本文提出了相對距離的概念，在低密度區(qū)域的簇中的內(nèi)部對象和邊界上對象的相對距離會相對較小，而離群點(diǎn)的相對距離通常相對較大，可以有效地提高內(nèi)部點(diǎn)和離群點(diǎn)的區(qū)分能力。本文通過距離和密度的比值的形式構(gòu)成相對熵權(quán)密度離群因子，通常情況下相對熵權(quán)密度離群因子較大的點(diǎn)更有可能為離群點(diǎn)，因此算法選取排序后的離群因子中前o個點(diǎn)作為離群點(diǎn)輸出，在算法實(shí)際應(yīng)用中，o的取值是根據(jù)實(shí)際數(shù)據(jù)集的情況人為設(shè)定的。在本文實(shí)驗(yàn)中，為了驗(yàn)證算法在各數(shù)據(jù)集上的有效性，o的取值根據(jù)數(shù)據(jù)集已有的離群點(diǎn)標(biāo)簽個數(shù)設(shè)定。

算法2ERDOF 離群點(diǎn)檢測算法

輸入初始數(shù)據(jù)集D和Ball-Tree

輸出數(shù)據(jù)集D中前o個離群點(diǎn)

3.3 ERDOF 算法正確性

算法2 詳細(xì)描述了所提算法。其中熵權(quán)距離是基于信息熵計(jì)算得出的，在多維數(shù)據(jù)集中，并不是每個屬性對檢測離群點(diǎn)都是有幫助的，通過給屬性分配權(quán)重能有效地提高檢測精度。生成的擴(kuò)展局部鄰域 ISk(x)是由KNNk(x)和RNNk(x)合并而成的，其中RNNk(x)能有效地提高對于局部離群點(diǎn)的檢測精度?；?ISk(x)對每個數(shù)據(jù)對象進(jìn)行密度估計(jì)，然后根據(jù)密度分別計(jì)算每個數(shù)據(jù)對象的相對距離。最后通過計(jì)算相對熵權(quán)密度離群因子，對其進(jìn)行降序排列，輸出前o個離群點(diǎn)。

3.4 ERDOF 算法復(fù)雜性

ERDOF 算法的時間復(fù)雜度主要由以下2 個部分組成：1) 為得到自適應(yīng)的NV 和自然鄰域而構(gòu)建的Ball-Tree，時間復(fù)雜度為O(nlogn)，其中n為數(shù)據(jù)集的數(shù)據(jù)對象的個數(shù)；2) 計(jì)算數(shù)據(jù)對象的相對熵權(quán)密度離群因子ERDOFk(x)，時間復(fù)雜度為O(nk)，其中k為NV，因此ERDOF 算法總的時間復(fù)雜度為O(nlogn)。

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

為驗(yàn)證本文所提算法ERDOF 在各種復(fù)雜數(shù)據(jù)分布上的性能，本節(jié)在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)驗(yàn)證。在實(shí)驗(yàn)中，將本文算法與常用的6 種離群點(diǎn)檢測算法（NaNOD[19]、IForest[24]、LDF[25]、RDOS[26]、NOF[27]、COPOD[28]）進(jìn)行對比實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境如表2 所示。

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

4.1 算法有效性檢測指標(biāo)

在離群點(diǎn)檢測實(shí)驗(yàn)中，大多數(shù)的數(shù)據(jù)集是高度不平衡的，即正常數(shù)據(jù)大量存在，而異常數(shù)據(jù)則十分稀有，這使準(zhǔn)確率可能不適合作為離群點(diǎn)檢測的性能指標(biāo)。因此，本文使用接收器工作特性（ROC,receiver operating characteristics）曲線下方的面積（AUC,area under curve）作為實(shí)驗(yàn)結(jié)果的評價指標(biāo)，AUC 在離群點(diǎn)檢測領(lǐng)域是最常見且有效的評價指標(biāo)。ROC 曲線是真陽性率隨假陽性率變化的曲線，其中真陽性率和假陽性率的定義分別如式(13)和式(14)所示。

其中，TP 表示預(yù)測為離群點(diǎn)且實(shí)際上也是離群點(diǎn)的個數(shù)；FP 表示預(yù)測為離群點(diǎn)但實(shí)際上是正常點(diǎn)的個數(shù)；TN 表示預(yù)測為正常點(diǎn)且實(shí)際上也是正常點(diǎn)的個數(shù)；FN 表示預(yù)測為正常點(diǎn)但實(shí)際上是離群點(diǎn)的個數(shù)。

AUC 的取值范圍為0～1，一個隨機(jī)算法會產(chǎn)生一條近似于對角線的曲線（AUC=0.5），AUC 的取值越大，意味著在該算法里離群點(diǎn)的離群得分有更大的概率排在正常點(diǎn)之前[29]，因此AUC 的取值越大，離群點(diǎn)檢測算法效果越好。

F1 分?jǐn)?shù)（F1-Score）是統(tǒng)計(jì)學(xué)中用來衡量二分類模型精確度的一種指標(biāo)，它同時兼顧了分類模型的準(zhǔn)確率和查全率。F1 分?jǐn)?shù)可以看作模型準(zhǔn)確率和查全率的一種加權(quán)平均，它的取值為0～1。

在參數(shù)的選擇上，本文選用各算法在相應(yīng)文獻(xiàn)中的默認(rèn)值進(jìn)行后續(xù)實(shí)驗(yàn)。在本文算法中，自適應(yīng)核帶寬的平滑參數(shù)θ設(shè)置為0.015，為了防止核帶寬為0，將極小正數(shù)δ設(shè)置為10-4；在信息熵權(quán)距離中，離群屬性的權(quán)值l設(shè)置為1.5。

為了驗(yàn)證參數(shù)θ和參數(shù)l取值的有效性，本文選取了人工數(shù)據(jù)集D2和真實(shí)數(shù)據(jù)集Ionosphere 進(jìn)行實(shí)驗(yàn)。其中人工數(shù)據(jù)集是二維數(shù)據(jù)集，數(shù)據(jù)集特征較相似，故選用樣本個數(shù)和離群點(diǎn)比例均適中的D2數(shù)據(jù)集；真實(shí)數(shù)據(jù)集Ionosphere 的離群點(diǎn)占比較大，因此該數(shù)據(jù)集能更好地檢測出參數(shù)的變化對實(shí)驗(yàn)結(jié)果的影響。

圖3 是本文算法在人工數(shù)據(jù)集D2和真實(shí)數(shù)據(jù)集Ionosphere 上采用不同自適應(yīng)核帶寬的平滑參數(shù)θ的準(zhǔn)確度的實(shí)驗(yàn)結(jié)果。從圖3 可以看出，在人工數(shù)據(jù)集上，參數(shù)θ在0.01～0.06 保持高效穩(wěn)定；在真實(shí)數(shù)據(jù)集上，當(dāng)參數(shù)θ大于0.03 時準(zhǔn)確率大幅度下降，因此選取0.015 作為參數(shù)θ在本文算法上的默認(rèn)取值。

圖3 不同參數(shù)θ 的準(zhǔn)確度的實(shí)驗(yàn)結(jié)果

圖4 是本文算法在人工數(shù)據(jù)集D2和真實(shí)數(shù)據(jù)集Ionosphere 上采用不同的離群屬性的權(quán)值參數(shù)l的準(zhǔn)確度的實(shí)驗(yàn)結(jié)果。從圖4 可以看出，當(dāng)離群屬性的權(quán)重大于1 時，在真實(shí)數(shù)據(jù)集上，準(zhǔn)確率有了大幅提高，并且在1.4～2.0 保持穩(wěn)定，而信息熵加權(quán)距離主要適用于維度較高的數(shù)據(jù)集，人工數(shù)據(jù)集對參數(shù)l的設(shè)置并不敏感，因此選取1.5 作為參數(shù)l在本文算法上的默認(rèn)取值。

圖4 不同參數(shù)l 的準(zhǔn)確度的實(shí)驗(yàn)結(jié)果

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

為了驗(yàn)證本文算法在各種復(fù)雜數(shù)據(jù)分布下的性能，本文使用圖5 所示的6 種二維人工數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，其中離群點(diǎn)為“o”代表的點(diǎn)，人工數(shù)據(jù)集的數(shù)據(jù)特征如表3 所示。

表3 人工數(shù)據(jù)集數(shù)據(jù)特征

圖5 數(shù)據(jù)集D1～D6的數(shù)據(jù)分布

表4 展示了在6 種人工數(shù)據(jù)集上各算法的AUC得分結(jié)果，加黑字體表示每個數(shù)據(jù)集中表現(xiàn)最優(yōu)的算法。在D4中，本文ERDOF 算法的AUC 得分為0.99，在所有對比算法中為最高得分。從表4 中可以看出，本文ERDOF 算法在所有數(shù)據(jù)集上的AUC得分基本都是最優(yōu)的，與近年來較熱門的算法相比，實(shí)驗(yàn)效果突出。雖然本文ERDOF 算法并不在所有數(shù)據(jù)集上都表現(xiàn)最優(yōu)，但整體性能遠(yuǎn)超其他對比算法。因此，該實(shí)驗(yàn)證明ERDOF 算法可以適應(yīng)各種復(fù)雜形狀的數(shù)據(jù)分布且有較好的性能表現(xiàn)。

表4 各算法在人工數(shù)據(jù)集上的AUC 得分

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

本文采用的6 種真實(shí)數(shù)據(jù)集均來自UCI 數(shù)據(jù)集，數(shù)據(jù)集的維度為4～166，離群點(diǎn)所占比例為4.1%～35.8%，從維度和離群點(diǎn)占比上全面檢測ERDOF 算法的真實(shí)有效性，其中真實(shí)數(shù)據(jù)集的數(shù)據(jù)特征如表5 所示。

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

圖6 是各算法在真實(shí)數(shù)據(jù)集上的離群點(diǎn)檢測準(zhǔn)確率。為了提高實(shí)驗(yàn)結(jié)果的可靠性，引入F1 得分的概念對算法效果進(jìn)行評測，結(jié)果如表6 所示。從圖6可以看出，ERDOF 算法在各個真實(shí)數(shù)據(jù)集上的準(zhǔn)確率均不低于0.8，ERDOF 算法與所有對比算法相比，在真實(shí)數(shù)據(jù)集上的準(zhǔn)確率整體上達(dá)到最高。ERDOF 算法在真實(shí)數(shù)據(jù)集Wbc 上的準(zhǔn)確率和F1值均略低于IForest 算法，但均高于與NaNOD 算法和NOF 算法。通過分析發(fā)現(xiàn)，真實(shí)數(shù)據(jù)集Wbc屬性列密度分布都較均勻，使各個屬性列的信息熵都較接近，進(jìn)而導(dǎo)致熵權(quán)距離效果不佳，但由于本文使用相對距離去刻畫密度分布均勻或低密度區(qū)域的密度分布，使ERDOF 算法依舊保持較好的檢測效果。其中在Wdbc 和Ionosphere 這2 個高維數(shù)據(jù)集上，ERDOF 算法保持了較高的準(zhǔn)確率，其余算法受維度災(zāi)難的影響，效果相對較差。ERDOF 算法在Wdbc 數(shù)據(jù)集上的F1 得分為0.92，在所有對比算法中為最高得分。從表6 中可以看出，ERDOF 算法在各個真實(shí)數(shù)據(jù)集上整體性能遠(yuǎn)超其他對比算法。實(shí)驗(yàn)驗(yàn)證了本文算法能全面準(zhǔn)確地檢測出離群點(diǎn)。

表6 各算法在真實(shí)數(shù)據(jù)集上的F1 得分

圖6 各算法在真實(shí)數(shù)據(jù)集上的離群點(diǎn)檢測準(zhǔn)確率

各算法在真實(shí)數(shù)據(jù)集上的運(yùn)行時間如圖7 所示。從圖7 可以看出，在中低維度的數(shù)據(jù)集中各算法的運(yùn)行時間基本持平，而在高維數(shù)據(jù)集中除了COPOD 和IForest 算法的運(yùn)行時間保持平穩(wěn)外，其余算法均大幅度增大。但綜合準(zhǔn)確率來看，除了ERDOF 算法和LDF 算法在高維數(shù)據(jù)集上保持了較高的準(zhǔn)確率，其余算法的準(zhǔn)確率均大幅降低。ERDOF 算法在時間效率上對比其余算法沒有太大的優(yōu)化，但在可接受的時間差范圍內(nèi)，為了提高離群點(diǎn)的檢測精度，本文選用檢測性能更好的熵權(quán)距離和相對距離，因此犧牲了一些時間效率，但準(zhǔn)確率有較大提高。

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

從圖6 和圖7 中可以看出，本文算法在維度4～34時，時間效率和準(zhǔn)確率都保持較高的水平，而隨著維度的增大，準(zhǔn)確率依舊保持較高的水平，且時間效率的優(yōu)勢大幅度增加，因此本文算法考慮時間效率和準(zhǔn)確率，在可接受的時間差范圍內(nèi)，本文算法可以應(yīng)對的維度的大致范圍在2～100。

5 結(jié)束語

本文分析了近年來較新穎的基于密度的離群點(diǎn)檢測算法和相關(guān)算法思想，針對基于密度的方法存在的問題，提出了相對熵權(quán)密度離群因子來刻畫數(shù)據(jù)對象的離群程度，進(jìn)而提出了一種基于相對熵權(quán)密度離群因子的離群點(diǎn)檢測算法，其中用熵權(quán)距離取代傳統(tǒng)的歐氏距離，提高離群屬性在計(jì)算距離中的權(quán)重。本文首先提出相對距離的概念，提高算法在低密度區(qū)域處理局部離群點(diǎn)的能力；然后對算法進(jìn)行了正確性、復(fù)雜性的分析；最后在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上對ERDOF 算法進(jìn)行實(shí)驗(yàn)驗(yàn)證，通過對實(shí)驗(yàn)結(jié)果的比較分析，驗(yàn)證了ERDOF 算法能有效且全面地檢測離群點(diǎn)。