ERDOF：基于相對熵權密度離群因子的離群點檢測算法

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

（1.燕山大學信息科學與工程學院，河北 秦皇島 066004；2.河北省計算機虛擬技術與系統集成重點實驗室，河北 秦皇島 066004；3.河北省軟件工程重點實驗室，河北 秦皇島 066004）

1 引言

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

基于統計的檢測方法是根據現有的數據集結合統計學的方法生成模型，這類方法根據數據對象在模型中是否處于低概率區域來判斷離群點。這類檢測方法需要充分的數據先驗知識，并且對于高維數據集的檢測效果較差。

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

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

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

近年來，基于核的方法在離群點檢測和聚類等領域得到了廣泛的應用，基于核的方法利用核函數及其參數建立算法模型。文獻[18]提出了一種基于密度的離群點檢測算法，該算法將核密度估計（KDE,kernel density estimation）納入LOF 框架中，并將一個數據對象的KDE 標準化成S分數，與其鄰域的KDE 進行比較。

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

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

2 相關工作

2.1 自然鄰居

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

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

算法1自然鄰居搜索算法

輸入初始數據集D

輸出自然近鄰值NV

18) 輸出自然近鄰值NV

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

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

2.2 熵權距離

本文在計算數據對象之間的距離的時候，使用熵權距離取代傳統算法中的歐氏距離，下面，給出信息熵加權距離的定義和信息熵加權算法[17]的流程描述。

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

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

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

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

在數據集中，并非所有屬性對離群點檢測都是有作用的，因此，在計算距離時，為離群屬性提供更大的權值能更好地突顯離群點的離群程度，從而提高離群點和內部點的區分能力，其中參數l在本文中默認設定為1.5。

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

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

2.3 高斯核密度估計

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

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

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

本文選用的GKDE 方法[22]只通過數據對象的鄰域去估計對象xi的局部密度，而不是通過整個數據集去估計。因為如果通過整個數據集去估計，有可能無法檢測到局部的離群點。

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

圖1 局部離群點

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

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

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

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

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

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

2.4 自適應核帶寬

本文選用了高斯核密度估計方法[22]對數據對象進行密度估計，在傳統的核密度估計方法里，核帶寬都是預先設置好且固定的。但在使用的過程中會發現，在一些高密度區域里，使用過高的核帶寬會使密度估計結果過于平滑，影響實驗結果；此外，在一些低密度區域里，使用過低的核帶寬會導致產生噪聲估計。

圖2(a)表示在高密度區域設置不同核帶寬對數據點密度估計的影響。當設置合適的核帶寬時，各個數據點的密度為虛線所對應的曲線，能較準確地表示數據點的密度分布。當設置過高的核帶寬時，各個數據點的密度為實線所對應的曲線，過高的核帶寬會導致高密度區域的密度分布過于平滑，掩蓋了數據大部分的基礎結構，從而影響實驗結果。

圖2(b)表示在低密度區域設置不同核帶寬對數據點密度估計的影響。當設置合適的核帶寬時，各個數據點的密度為虛線所對應的曲線，能較準確地表示數據點的密度分布。當設置過低的核帶寬時，各個數據點的密度為實線所對應的曲線，過低的核帶寬會導致低密度區域數據點的密度分布波動較劇烈，會產生大量噪聲估計，從而影響實驗結果。

圖2 核帶寬對密度估計影響

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

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

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

3 ERDOF 算法

3.1 相對距離

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

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

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

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

3.2 相對熵權密度離群因子

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

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

算法2ERDOF 離群點檢測算法

輸入初始數據集D和Ball-Tree

輸出數據集D中前o個離群點

3.3 ERDOF 算法正確性

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

3.4 ERDOF 算法復雜性

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

4 實驗與分析

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

表2 實驗環境

4.1 算法有效性檢測指標

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

其中，TP 表示預測為離群點且實際上也是離群點的個數；FP 表示預測為離群點但實際上是正常點的個數；TN 表示預測為正常點且實際上也是正常點的個數；FN 表示預測為正常點但實際上是離群點的個數。

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

F1 分數（F1-Score）是統計學中用來衡量二分類模型精確度的一種指標，它同時兼顧了分類模型的準確率和查全率。F1 分數可以看作模型準確率和查全率的一種加權平均，它的取值為0～1。

在參數的選擇上，本文選用各算法在相應文獻中的默認值進行后續實驗。在本文算法中，自適應核帶寬的平滑參數θ設置為0.015，為了防止核帶寬為0，將極小正數δ設置為10-4；在信息熵權距離中，離群屬性的權值l設置為1.5。

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

圖3 是本文算法在人工數據集D2和真實數據集Ionosphere 上采用不同自適應核帶寬的平滑參數θ的準確度的實驗結果。從圖3 可以看出，在人工數據集上，參數θ在0.01～0.06 保持高效穩定；在真實數據集上，當參數θ大于0.03 時準確率大幅度下降，因此選取0.015 作為參數θ在本文算法上的默認取值。

圖3 不同參數θ 的準確度的實驗結果

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

圖4 不同參數l 的準確度的實驗結果

4.2 人工數據集

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

表3 人工數據集數據特征

圖5 數據集D1～D6的數據分布

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

表4 各算法在人工數據集上的AUC 得分

4.3 真實數據集

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

表5 真實數據集數據特征

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

表6 各算法在真實數據集上的F1 得分

圖6 各算法在真實數據集上的離群點檢測準確率

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

圖7 各算法在真實數據集上的運行時間

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

5 結束語

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