基于期望核密度離群因子的離群點檢測算法①

張忠平 孫光旭 姚春辰 劉 碩 齊文旭

(*燕山大學(xué)信息科學(xué)與工程學(xué)院 秦皇島 066004)

(**河北省計算機虛擬技術(shù)與系統(tǒng)集成重點實驗室 秦皇島 066004)

(***信息工程大學(xué)信息系統(tǒng)工程學(xué)院 鄭州 450001)

離群點是指數(shù)據(jù)集中偏離大多數(shù)數(shù)據(jù)的少量數(shù)據(jù)對象,它們與正常數(shù)據(jù)對象存在明顯的差異。離群點檢測技術(shù)致力于消除噪音和干擾或發(fā)現(xiàn)潛在的、有價值的信息[1],是數(shù)據(jù)挖掘的一個重要研究方向。目前,離群點檢測技術(shù)已經(jīng)廣泛應(yīng)用于各大領(lǐng)域中,例如網(wǎng)絡(luò)入侵檢測[2-3]、金融欺詐檢測[4-5]、工業(yè)損傷檢測[6]、垃圾郵件檢測[7]、醫(yī)療與公共衛(wèi)生檢測[8]等領(lǐng)域。

目前離群點檢測大致可分為基于統(tǒng)計的[9-10]、基于距離的[11-12]、基于聚類的[13-14]和基于密度的[15-16]方法。

基于統(tǒng)計的方法采用統(tǒng)計學(xué)中的標(biāo)準(zhǔn)分布模型擬合數(shù)據(jù),若某個數(shù)據(jù)點與假設(shè)的分布模型偏差較大,則視其為離群點。此類方法不適用于高維數(shù)據(jù)集,并且當(dāng)數(shù)據(jù)集不服從任何標(biāo)準(zhǔn)分布或無法判斷分布特征時,離群點檢測效率將會大幅降低。

基于距離的方法通過計算數(shù)據(jù)對象之間的距離遠近,將距離更遠的數(shù)據(jù)對象標(biāo)記為離群點,避免了數(shù)據(jù)分布假設(shè)。然而,此類方法只考慮了全局離群點,沒有顧及到局部離群點。對此,Ramaswamy 等人[17]提出了一種基于距離的改進離群點檢測算法——k 近鄰(k-nearest neighbors,KNN)算法。該算法首先對原始數(shù)據(jù)聚類,計算簇中樣本點的k 近鄰距離的上下界,排除距離過小的簇,將剩余數(shù)據(jù)點中k 近鄰距離較大的點標(biāo)記為離群點。文獻[18]針對KNN 算法對近鄰參數(shù)k值敏感的問題,提出了一種基于自然最近鄰的離群點檢測算法,通過在不同數(shù)據(jù)集上自適應(yīng)獲取近鄰參數(shù),避免了人為設(shè)置。

基于聚類的方法將遠離正常簇的離群聚類中的數(shù)據(jù)點以及不屬于任何聚類的數(shù)據(jù)點視為離群點,此類方法通常會引入新的參數(shù)。文獻[19]提出了一種基于累積全熵的子空間聚類離群點檢測算法(subspace outlier detection based on cumulative holoentropy,SODCH),該算法通過計算子空間的累積全熵值選取最優(yōu)聚類子空間,提高檢測效率。文獻[20]提出了一種基于聚類離群因子和相互密度的離群點檢測算法,算法根據(jù)相互鄰居而非k 鄰域來計算數(shù)據(jù)的相互密度,通過構(gòu)造決策圖完成聚類,進而識別出離群點。

基于密度的方法是當(dāng)下離群點檢測領(lǐng)域的研究熱點。傳統(tǒng)的基于密度的方法大多將密度視作距離的倒數(shù),通過數(shù)據(jù)對象間的距離來計算局部密度,離群點與位于密集區(qū)域的正常對象相比密度更低。局部離群因子(local outlier factor,LOF)算法[21]通過計算每個數(shù)據(jù)對象的局部離群因子來檢測數(shù)據(jù)集中的離群點,作為迄今為止最為經(jīng)典的離群點檢測算法,仍存在精確率低、參數(shù)設(shè)置敏感等問題。Huang等人[22]針對LOF 近鄰參數(shù)k選取困難的問題,提出了無參數(shù)的基于自然鄰居的離群點檢測算法——自然離群因子(natural outlier factor,NOF)算法。該算法合并k 鄰域和反k 鄰域,自適應(yīng)獲取近鄰參數(shù)k,通過定義離群因子NOF 檢測離群點。Li 等人[23]提出了一種基于密度-距離決策圖的離群點檢測算法,將傳統(tǒng)核密度估計(kernel density estimation,KDE)與局部可達距離相結(jié)合檢測局部離群點,根據(jù)密度提升距離的度量標(biāo)準(zhǔn)檢測全局離群點,通過密度比和密度提升距離生成決策圖,同時檢測出局部、全局和聚類離群點。

通過將核密度估計應(yīng)用于離群點檢測算法中,Wahid 等人[24]提出了一種基于相對核密度的離群點檢測(relative kernel-density outlier factor,KDOF)算法。該算法使用核密度估計計算數(shù)據(jù)對象的局部密度,然后計算密度波動及其近鄰點的密度差的平方和,最后通過比較其密度波動與近鄰點的平均密度波動來描述數(shù)據(jù)對象的離群程度?；诖?Wahid 等人[25]又提出了一種基于自然鄰居的離群點檢測(natural neighbor outlier detection,NaNOD)算法,根據(jù)自然鄰居自適應(yīng)獲取近鄰參數(shù)k,并采用加權(quán)核密度估計計算數(shù)據(jù)對象的密度,采用高斯核函數(shù)保證數(shù)據(jù)點之間的平滑度,使用自適應(yīng)核帶寬的思想適應(yīng)數(shù)據(jù)點之間的密度差異,進一步區(qū)分正常點和離群點。上述2 種算法在很多場景下都具有良好的性能,但存在維度災(zāi)難的問題,導(dǎo)致算法運行時間過長,離群點檢測效率顯著下降。

本文針對基于密度的離群點檢測方法在不同分布的數(shù)據(jù)集上檢測精度低的問題,提出一種基于期望核密度離群因子的離群點檢測(outlier detection algorithm based on expected kernel density outlier factor,EKDOF)算法。首先,算法將k 近鄰和反向k 近鄰合并為鄰域空間,充分考慮數(shù)據(jù)對象的局部信息;其次,將核密度估計與多元高斯函數(shù)相結(jié)合估計數(shù)據(jù)對象的局部密度,同時根據(jù)數(shù)據(jù)點的k 鄰域平均距離自適應(yīng)地選取核帶寬,給出了期望距離的概念,進一步區(qū)分局部離群點和低密度區(qū)域的正常點;最后,利用期望距離與核密度估計的比值定義期望核密度離群因子來刻畫數(shù)據(jù)對象的離群程度。

1 相關(guān)工作

下面簡要介紹相互k 近鄰數(shù)搜索算法。其中,D表示數(shù)據(jù)集,p、q、o為數(shù)據(jù)集D中的數(shù)據(jù)點,dist(p,q)表示點p、q之間的歐式距離,k為正整數(shù)。

1.1 擴展鄰域空間

定義1k距離dk(p)。dk(p) 是指在給定的k值下,點p到點m之間的歐氏距離。其中,數(shù)據(jù)點m滿足:至少存在k個數(shù)據(jù)點m′ ∈D{m′},滿足d(p,m′) ≤d(p,m)。

定義2數(shù)據(jù)點xi的k 近鄰kNN(xi)[22]。kNN(xi)是指在數(shù)據(jù)集D={x1,x2,…,xn} 中,到數(shù)據(jù)點xi的距離不大于數(shù)據(jù)點xi的k距離的點的集合,定義為式(1)。

定義3數(shù)據(jù)點xi的反向近RNN(xi)[22]。RNN(xi) 是指在數(shù)據(jù)集D={x1,x2,…,xn} 中,將數(shù)據(jù)點xi看作k 最近鄰居的數(shù)據(jù)點xj所構(gòu)成的點的集合,定義為式(2)。

定義4擴展鄰域空間(extended neighborhood space,ENS)ENS(xi)[26]。ENS(xi) 是指數(shù)據(jù)點xi的k 近鄰kNN(xi) 和反向近鄰RNN(xi) 的并集所組成的集合,定義為式(3)。

1.2 核密度估計

在數(shù)據(jù)分布未知的情況下,使用核密度估計可以估計出每個數(shù)據(jù)對象本身的局部密度,更好地反映出數(shù)據(jù)點本身與其擴展鄰域空間內(nèi)其他數(shù)據(jù)點之間的密度差異。

定義5核密度估計(KDE)[27]。KDE 是指通過估計樣本集中樣本的概率密度函數(shù),得出樣本集的總體分布情況,定義為式(4)。

其中,n表示數(shù)據(jù)集D中數(shù)據(jù)點的個數(shù);h(xj) 表示在數(shù)據(jù)點xj上的帶寬,也稱為平滑函數(shù);d表示數(shù)據(jù)點的維度;‖xi-xj‖表示數(shù)據(jù)點xi到數(shù)據(jù)點xj的歐式距離。K()表示核函數(shù),具有期望值為0、非負性和歸一性的特征,滿足以下條件:

在傳統(tǒng)計算核密度的方法中,通常根據(jù)經(jīng)驗值將帶寬設(shè)置為固定帶寬,難以體現(xiàn)出不同數(shù)據(jù)點之間的局部密度差異。局部密度因子(local density factor,LDF)算法[28],提出一種自適應(yīng)獲取核帶寬的方法,以適應(yīng)在不同數(shù)據(jù)集下數(shù)據(jù)點局部密度的差異,定義為式(8)。

其中,dk(xi) 表示數(shù)據(jù)點xi到第k個近鄰點的距離,但該方法仍然需要用戶事先指定h的取值。

2 EKDOF 算法

2.1 EKDOF 算法相關(guān)定義

定義6自適應(yīng)核帶寬h(xj)。h(xj) 是指在給定近鄰參數(shù)k值時,2 個數(shù)據(jù)對象的度量參數(shù)乘積的擬合值,定義為式(9)。

其中,mi、mj分別表示數(shù)據(jù)點xi、xj的度量參數(shù),且數(shù)據(jù)點xj在數(shù)據(jù)點xi的擴展鄰域空間內(nèi),即xj∈ENS(xi)。自適應(yīng)核帶寬能夠在估計密度時根據(jù)數(shù)據(jù)對象所處區(qū)域疏密程度的不同而發(fā)生改變。

定義7度量參數(shù)mi。mi是指數(shù)據(jù)點的k 鄰域平均距離,定義為式(10)。

其中,kNN(xi) 表示數(shù)據(jù)點xi的k 近鄰點的集合,|kNN(xi) | 表示數(shù)據(jù)點xi的k 鄰域范圍內(nèi)數(shù)據(jù)點的個數(shù),d(xi,xl) 表示數(shù)據(jù)點xi到數(shù)據(jù)點xl的歐式距離。

定義8多元高斯函數(shù)K()。K() 是核密度估計的底層函數(shù),定義為式(11)。

其中,d為數(shù)據(jù)對象的維度,‖x‖ 表示向量x的模。

定義9核密度估計denENS(xi)。denENS(xi) 是指在xi的擴展鄰域空間內(nèi),結(jié)合多元高斯函數(shù)和傳統(tǒng)核密度估計得到的密度,定義為式(12)。

其中,| ENS(xi)| 表示數(shù)據(jù)點xi的擴展鄰域空間內(nèi)數(shù)據(jù)對象的個數(shù)。綜合式(9) 和(12),得到denENS(xi) 的最終計算式定義為式(13)。

定義10期望k 距離Ek_dist(expected k-distance)。Ek_dist 是指所有數(shù)據(jù)點到其各自的第k個近鄰點的距離平均值,定義為式(14)。

其中,Nk-th表示第k個近鄰點,xi為數(shù)據(jù)集D中的數(shù)據(jù)點,n表示數(shù)據(jù)集D中樣本個數(shù)。期望k 距離是數(shù)據(jù)集中的每個數(shù)據(jù)點到第k個近鄰點的期望值,反映了在不同k值下,數(shù)據(jù)點與近鄰點之間的距離偏差。

定義11期望k 距離差(difference of expected k-distance)difEk_dist(xi)。difEk_dist(xi) 指數(shù)據(jù)點xi到第k近鄰的距離與期望k 距離的差,定義為式(15)。

其中,d(xi,Nk-th) 表示數(shù)據(jù)點xi到第k個近鄰點的歐式距離?？梢钥闯?期望k 距離差difEk_dist(xi) 的結(jié)果可取到正值、負值或者零。如果數(shù)據(jù)點到第k個近鄰點的距離大于期望k 距離,則difEk_dist(xi) 的值為正,否則為負;如果數(shù)據(jù)點到第k個近鄰點的距離剛好等于期望k 距離,則difEk_dist(xi) 的值等于0。期望k 距離差的正值越大,代表數(shù)據(jù)點本身與鄰居點之間越疏遠,該點越有可能是離群點;期望k 距離差的負值結(jié)果越小,代表數(shù)據(jù)點本身與鄰居點之間越緊密,該點越有可能是正常點。

圖1 展示了一個二維數(shù)據(jù)集部分數(shù)據(jù)點的分布情況。O1、O2、O3分別表示點p的3 個近鄰點;實線表示數(shù)據(jù)集中所有數(shù)據(jù)點到第k個近鄰點的平均距離,即期望k 距離,分別用E1_dist、E2_dist 和E3_dist 表示;虛線表示數(shù)據(jù)點p到第k個近鄰點的距離與期望k 距離的差,分別用difE1_dist(p)、difE2_dist(p)、difE3_dist(p) 表示。從圖1 可以看出,數(shù)據(jù)點p到第1個近鄰點O1的距離大于E1_dist,因此difE1_dist(p)的值為正;數(shù)據(jù)點p到第2個近鄰點O2的距離小于E2_dist,因此difE2_dist(p) 的值為負;數(shù)據(jù)點p到第3 個近鄰點O3的距離大于E3_dist,因此difE3_dist(p)的值為正。

圖1 k=3 時,期望k 距離和期望k 距離差的簡單示例

定義12期望距離(expected distance)Edist(xi)。Edist(xi)是指在給定k值下,數(shù)據(jù)點xi的期望k 距離差的和,定義為式(16)。

其中,s表示近鄰參數(shù)k的值。位于密集區(qū)域的正常點與其鄰域范圍內(nèi)的數(shù)據(jù)點之間的相互距離較小,則期望距離的值也會較小;位于稀疏區(qū)域的離群點與其鄰域范圍內(nèi)的數(shù)據(jù)點之間的相互距離較大,則期望距離的值也會較大,從而可以進一步區(qū)分離群點和位于低密度區(qū)域的正常點。

定義13期望核密度離群因子EKDOF(xi)。EKDOF(xi) 是指數(shù)據(jù)點xi的期望距離與核密度估計的比值,定義為式(17)。

其中,Edist(xi) 表示數(shù)據(jù)對象的期望距離,denENS(xi) 表示數(shù)據(jù)對象的核密度估計,兩者的比值表明了數(shù)據(jù)對象的離群程度。由于離群點常常偏離正常點,從而離群點到其第k個近鄰點的距離總是大于期望k 距離Ek_dist,其期望k 距離差difEk_dist(xi) 也會更大且總是取到正值,因此離群點的期望距離Edist(xi) 要遠大于正常點,又由于離群點總是位于低密度區(qū)域,其核密度denENS(xi) 一般較小。因為期望距離Edist(xi) 更大、核密度denENS(xi) 更小,所以離群因子EKDOF(xi) 的值也會更大,該點是離群點的概率也就越大。

2.2 EKDOF 算法思想

EKDOF 算法思想如下。首先,擴大數(shù)據(jù)對象的鄰域范圍,引入反向k 近鄰關(guān)系,將k 近鄰和反向k近鄰合并作為數(shù)據(jù)對象的擴展鄰域空間,完善了僅考慮k 鄰域范圍內(nèi)數(shù)據(jù)點分布情況的不足;采用自適應(yīng)核帶寬的思想計算核密度,在帶寬函數(shù)中引入一種度量參數(shù),根據(jù)不同數(shù)據(jù)點之間度量參數(shù)的大小來判斷數(shù)據(jù)點所處區(qū)域的密集或稀疏程度。核帶寬會隨著數(shù)據(jù)點的變化而變化,而不是一個固定值。當(dāng)數(shù)據(jù)點位于密集區(qū)域時,數(shù)據(jù)點之間的k 鄰域平均距離小,度量參數(shù)的值變小,核帶寬也就越小;當(dāng)數(shù)據(jù)點位于稀疏區(qū)域時,數(shù)據(jù)點之間的k 鄰域平均距離大,度量參數(shù)的值變大,核帶寬也就隨之變大。將高斯核函數(shù)應(yīng)用到核密度估計中,在擴展的鄰域空間內(nèi)計算數(shù)據(jù)點的局部密度。由于基于密度的方法存在低密度模式的問題,位于低密度區(qū)域內(nèi)的正常點和位于密集區(qū)域邊界的局部離群點的密度大小較為接近,僅憑密度難以區(qū)分,因此本文提出期望距離的概念。位于低密度區(qū)域內(nèi)的數(shù)據(jù)點的期望距離相對較小,而位于密集區(qū)域邊界的局部離群點的期望距離相對較大,可以進一步區(qū)分正常點和離群點。本文將高斯核密度估計與期望距離相結(jié)合構(gòu)造離群因子,通過比較離群因子值的大小檢測離群點。

2.3 EKDOF 算法描述

根據(jù)相關(guān)定義和算法思想,本節(jié)提出了基于期望核密度離群因子的離群點檢測算法EKDOF,算法描述如算法1 所示。

首先,將數(shù)據(jù)點的k 近鄰與反向k 近鄰合并形成擴展鄰域空間,在擴展的鄰域空間內(nèi),通過將傳統(tǒng)核密度估計與多元高斯函數(shù)相結(jié)合估計每個數(shù)據(jù)點的密度,同時引入度量參數(shù)的概念,根據(jù)數(shù)據(jù)對象的k 鄰域平均距離自適應(yīng)獲取數(shù)據(jù)對象之間的核帶寬;其次,根據(jù)期望k 距離和期望k 距離差的定義計算每個數(shù)據(jù)對象的期望距離;最后,用數(shù)據(jù)對象的期望距離與核密度估計的比值構(gòu)造離群因子,根據(jù)離群因子值進行降序排序,將離群因子值較大的前n個點輸出即為離群點。

算法1 中,EKDOF(xi) 中存放的分別是每個數(shù)據(jù)點xi∈D的期望核密度離群因子的值,算法將EKDOF(xi) 值較大的前n個點輸出作為離群點,Soutlier中存放的是算法最終檢測到的所有離群點。

2.4 EKDOF 算法分析

2.4.1 正確性分析

在EKDOF 算法中,首先將數(shù)據(jù)對象的k 近鄰和反向k 近鄰合并生成擴展鄰域空間,充分考慮數(shù)據(jù)點的鄰域信息;將傳統(tǒng)核密度估計與多元高斯函數(shù)相結(jié)合估計數(shù)據(jù)對象的密度,同時引入自適應(yīng)核帶寬的思想,能夠在不同分布的數(shù)據(jù)集下根據(jù)數(shù)據(jù)對象鄰域范圍的密集或稀疏程度自動進行調(diào)整,平滑了正常點之間的密度差異;通過分析發(fā)現(xiàn),僅憑密度難以辨別出位于低密度區(qū)域的正常點和位于密集簇邊界區(qū)域的局部離群點,因此本算法提出期望距離的概念,能夠進一步區(qū)分正常點和局部離群點。EKDOF 算法采用數(shù)據(jù)對象的期望距離與核密度估計的比值構(gòu)造離群因子,離群因子值越大,該點是離群點的可能性就越大。以上分析說明了所提出的基于期望核密度離群因子的離群點檢測算法在原理上是正確的。

2.4.2 時間復(fù)雜度分析

EKDOF 算法的時間復(fù)雜度主要分為2 部分:(1)在構(gòu)造擴展鄰域空間的過程中,需要計算每個數(shù)據(jù)點的k 近鄰和反向k 近鄰,時間復(fù)雜度為O(n·logn),其中n表示數(shù)據(jù)集中數(shù)據(jù)點的個數(shù);(2)計算數(shù)據(jù)對象的期望核密度離群因子EKDOF(xi),時間復(fù)雜度為O(n)。綜合上述分析,所提算法的時間復(fù)雜度為O(n·logn)+O(n) 兩部分之和,進而得出EKDOF 算法最終的時間復(fù)雜度為O(n·logn)。

3 實驗與分析

3.1 實驗環(huán)境配置

表1 給出了驗證本文算法性能所采用的實驗環(huán)境,主要包括軟硬件環(huán)境以及各配置所對應(yīng)的參數(shù)。

表1 實驗環(huán)境

3.2 實驗評價指標(biāo)

本文采用的實驗評價指標(biāo)為精確率Pr、AUC(area under curve)值和離群點發(fā)現(xiàn)曲線。

精確率Pr是指算法實際檢測到的離群點數(shù)量與離群點總數(shù)之比,定義為式(18)。

其中,FP表示算法把數(shù)據(jù)集中的正常點當(dāng)作離群點進行輸出的數(shù)量,TP表示算法最終檢測到的真實離群點的個數(shù)。精確率Pr的取值在0～1 之間,Pr的值越接近于1,代表算法檢測出的真實離群點的數(shù)量越多,算法的性能就越好。

AUC 值是一個介于0 和1 之間的數(shù),AUC 的值越接近于1,代表算法越接近于離群點檢測的最佳水平,能把更多的離群點排在正常點之前進行輸出,算法的性能就越好。

離群點發(fā)現(xiàn)曲線[29]反映的是算法實際檢測到的離群點個數(shù)隨用戶查詢個數(shù)的變化趨勢。離群點發(fā)現(xiàn)曲線的橫坐標(biāo)是用戶想要查詢的離群點的個數(shù),縱坐標(biāo)是算法真正檢測到的離群點的個數(shù)。離群點發(fā)現(xiàn)曲線的斜率越接近于1,代表算法越能滿足用戶的查詢需求,算法的性能就越好。

3.3 人工數(shù)據(jù)集實驗與分析

本文使用圖2 所示的二維人工數(shù)據(jù)集DS5～DS8進行對比實驗,其中“ ×”代表離群點,其余點代表正常點。DS5～DS8 的數(shù)據(jù)特征如表2 所示。

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

圖2 EKDOF 算法人工數(shù)據(jù)集的數(shù)據(jù)分布圖

結(jié)合圖2 和表2 可以看出,本算法選取的人工數(shù)據(jù)集的數(shù)據(jù)分布復(fù)雜程度不同,既包括離群點和正常點分布較為明顯的數(shù)據(jù)集,也包括離群點交錯地分布在正常點所構(gòu)成的聚類簇的周圍或邊界區(qū)域的數(shù)據(jù)集。因此,在這些數(shù)據(jù)集上進行實驗可以有效地驗證EKDOF 算法的性能,同時有助于與其他對比算法作出區(qū)分。

表3 和圖3 展示了在4 個人工數(shù)據(jù)集下,EKDOF算法和其他4 種對比算法在精確率上的實驗結(jié)果。

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

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

結(jié)合表3 和圖3 可以看出,EKDOF 算法在人工數(shù)據(jù)集上的精確率均為最優(yōu),且在DS8 數(shù)據(jù)集上,EKDOF 算法的精確率為0.97,在所有人工數(shù)據(jù)集中達到了最高。在所有數(shù)據(jù)集中EKDOF 算法的精確率均高于同樣使用了核密度估計方法的LOLED 算法和LDF 算法,特別是在DS5 數(shù)據(jù)集上EKDOF 算法的精確率為0.95,而LOLED 算法的精確率為0.79。這是因為EKDOF 算法同時將k 鄰域和反向k 鄰域作為鄰域空間,更加全面地考慮數(shù)據(jù)對象的局部信息,使用期望距離能夠進一步區(qū)分離群點和位于低密度區(qū)域的正常點,因此提高了本文算法的檢測精度。在DS6 數(shù)據(jù)集上,每種算法的精確率均有所下降,EKDOF 算法的精確率為0.88,仍高于對比算法。在4 個人工數(shù)據(jù)集上,EKDOF 算法的精確率均優(yōu)于同樣使用了擴展鄰域空間的INFLO 算法和NOF算法,特別是在DS7 數(shù)據(jù)集上,EKDOF 算法的精確率為0.91,高于NOF 算法0.54。綜上所述,EKDOF 算法在所有數(shù)據(jù)集上的精確率都是最高的,從而驗證了本文所提出的基于期望核密度離群因子的離群點算法在精確率上的有效性。

表4 和圖4 展示了4 個人工數(shù)據(jù)集上,EKDOF算法和其他4 種對比算法在AUC 值上的實驗結(jié)果。

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

圖4 不同算法在人工數(shù)據(jù)集上的AUC 值對比

結(jié)合表4 和圖4 可以看出,EKDOF 算法在人工數(shù)據(jù)集上的AUC 值均為最優(yōu),其中在DS7 和DS8數(shù)據(jù)集上,其AUC 值均達到了1.00。在DS5 和DS6數(shù)據(jù)集上,EKDOF 算法的AUC 值均為0.97,除NOF算法在DS6 數(shù)據(jù)集上的AUC 值為0.75 之外,其他算法在這2 個數(shù)據(jù)集上的AUC 值均保持在0.80 以上。在DS7 數(shù)據(jù)集上,LOLED 算法、LDF 算法和NOF 算法的AUC 值均有所下降,其中NOF 算法的AUC 值僅為0.30,這是因為DS7 數(shù)據(jù)集分布較為復(fù)雜,通過密度難以區(qū)分出局部離群點和低密度區(qū)域的正常點,難以檢測出更多的離群點,因此造成算法AUC 值減小。綜上,EKDOF 算法在4 個人工數(shù)據(jù)集上的AUC 值都是最高的,證明本文提出的基于期望核密度離群因子的離群點檢測算法在AUC 值上的有效性。

圖5 展示了4 個人工數(shù)據(jù)集上,EKDOF 算法和4 種對比算法的離群點發(fā)現(xiàn)曲線的實驗結(jié)果。

圖5 不同算法在人工數(shù)據(jù)集上的離群點發(fā)現(xiàn)曲線對比

觀察圖5(a)～(d)的曲線變化趨勢可以看出,當(dāng)查詢條件相同時,EKDOF 算法能夠查詢到更多的離群點反饋給用戶,表明EKDOF 算法相比于其他算法具有更優(yōu)秀的檢測能力。NOF 算法在DS8 數(shù)據(jù)集上的表現(xiàn)和其他算法較為相似,但在DS6 和DS7數(shù)據(jù)集上的檢測效果與其他算法相比相差較多。在DS8 數(shù)據(jù)集上,EKDOF 算法的離群點發(fā)現(xiàn)曲線的斜率最接近于1,當(dāng)用戶的查詢數(shù)量從5 依次遞增至40 時,EKDOF 算法查詢到的離群點個數(shù)與用戶設(shè)置的查詢個數(shù)始終相等,說明EKDOF 算法檢測到的前40 個數(shù)據(jù)點都是離群點。綜上所述,EKDOF算法的離群點發(fā)現(xiàn)曲線在4 個人工數(shù)據(jù)集上的表現(xiàn)都是最優(yōu)的,從而驗證了本文所提出的EKDOF 算法在離群點檢測方面的良好性能。

3.4 真實數(shù)據(jù)集實驗與分析

4 個真實數(shù)據(jù)集的數(shù)據(jù)特征如表5 所示,它們均來自于UCI 真實數(shù)據(jù)集[30]。由表5 可知,EKDOF算法所選取的真實數(shù)據(jù)集的樣本數(shù)量從129～1 641,數(shù)據(jù)維度從7～17,離群點數(shù)量從10～25,離群點占比從1.2%～14.8%。由此可知,本算法選取的真實數(shù)據(jù)集的數(shù)據(jù)分布較為復(fù)雜,有包含幾百個數(shù)據(jù)點的小規(guī)模數(shù)據(jù)集,也有包含上千個數(shù)據(jù)點的大規(guī)模數(shù)據(jù)集。因此,在這些數(shù)據(jù)集上進行實驗可以有效地對比各離群點檢測算法的性能。

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

表6 和圖6 展示了在4 個真實數(shù)據(jù)集下,EKDOF 算法和其他4 種對比算法在精確率上的實驗結(jié)果。

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

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

結(jié)合表6 和圖6 可以看出,除了在Ecoli 數(shù)據(jù)集上本文算法和INFLO 算法的精確率相等以外,在其他3 個數(shù)據(jù)EKDOF 算法的精確率都要比另外幾種算法好,特別是在PenDigits 數(shù)據(jù)集上達到了0.95。INFLO 算法在對比算法中的表現(xiàn)相對較好,而另外3 種對比算法的精確率表現(xiàn)較差且波動幅度較大。NOF 算法的穩(wěn)定性最差,雖然在Ecoli 數(shù)據(jù)集上有0.48 的檢測精度,但在WBC 數(shù)據(jù)集上根本沒有檢測出離群點,而本文算法的精確率仍然可以達到0.90。綜上所述,EKDOF 算法在每個真實數(shù)據(jù)集上都能檢測出更多的離群點且穩(wěn)定性也是最好的,從而驗證了本文所提出基于期望核密度離群因子的離群點檢測算法在精確率上的有效性。

表7 和圖7 展示了在4 個真實數(shù)據(jù)集下,EKDOF 算法和其他4 種對比算法在AUC 值上的實驗結(jié)果。

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

圖7 不同算法在真實數(shù)據(jù)集上的AUC 值對比

結(jié)合表7 和圖7 可以看出,EKDOF 算法在每個真實數(shù)據(jù)集上的AUC 值都有著不錯的實驗結(jié)果,在PenDigits、Ecoli 和WBC 這3 個數(shù)據(jù)集上,EKDOF算法的AUC 值均為1.00,說明EKDOF 算法能把檢測出來的所有離群點排在正常點之前進行輸出。在PenDigits 數(shù)據(jù)集上,EKDOF 算法和INFLO 算法的AUC 值相同。NOF 算法在所有真實數(shù)據(jù)集上的AUC 值和穩(wěn)定性表現(xiàn)仍是最差的,由于NOF 算法在WBC 數(shù)據(jù)集上未檢測出離群點,其AUC 值為0.00。INFLO 算法的穩(wěn)定性也一般,在WBC 數(shù)據(jù)集上的AUC 值僅有0.41,但在PenDigits 數(shù)據(jù)集上的AUC值能達到1.00。LDF 算法在4 個對比算法中的表現(xiàn)最為平穩(wěn),其AUC 值一直保持在0.75 以上。綜合上述的分析,EKDOF 算法在每個真實數(shù)據(jù)集上的AUC 值都是最高的,從而驗證了本文所提出的基于期望核密度離群因子的離群點檢測算法在AUC 值上的有效性。

圖8 展示了4 個真實數(shù)據(jù)集下,EKDOF 算法和4 種對比算法離群點發(fā)現(xiàn)曲線的實驗結(jié)果。

觀察圖8(a)～(d),當(dāng)用戶的查詢數(shù)量逐漸增加時,從各算法對應(yīng)的離群點發(fā)現(xiàn)曲線的變化趨勢可以得出,在WBC 數(shù)據(jù)集和wine 數(shù)據(jù)集上,EKDOF算法離群點發(fā)現(xiàn)曲線的線性上升的速度與其他算法相比優(yōu)勢更加明顯,突出了EKDOF 算法在動態(tài)變化的查詢條件下更能滿足用戶的期望。在Ecoli 數(shù)據(jù)集上,除NOF 算法整體表現(xiàn)較差外,本文算法和另外幾種算法具有類似的性能,但整體上仍然優(yōu)于其余對比算法。在PenDigits 數(shù)據(jù)集上,本文所提出的EKDOF 算法和INFLO 算法的離群點發(fā)現(xiàn)曲線基本重合,但整體上本文算法離群點發(fā)現(xiàn)曲線的斜率更接近于1,最終本文算法比INFLO 算法多檢測出1 個離群點。LOLED 算法和LDF 算法在Ecoli 數(shù)據(jù)集上的表現(xiàn)都較為良好,但在其他3 個數(shù)據(jù)集上的表現(xiàn)卻差強人意。綜合上述的分析,EKDOF 算法的離群點發(fā)現(xiàn)曲線在每個真實數(shù)據(jù)集上的表現(xiàn)都是最優(yōu)的,從而驗證了本文所提出的基于期望核密度離群因子的離群點檢測算法具有良好的檢測精度和穩(wěn)定性。

4 結(jié)論

本文分析了近年來較新穎的基于密度的離群點檢測算法和相關(guān)思想,針對基于密度的方法存在的問題進行了深入研究,提出了一種基于期望核密度離群因子的離群點檢測算法。使用k 近鄰和反向k近鄰擴展鄰域空間代替?zhèn)鹘y(tǒng)的k 鄰域空間,充分考慮數(shù)據(jù)點鄰域范圍內(nèi)的數(shù)據(jù)分布;將傳統(tǒng)核密度估計的方法與多元高斯函數(shù)相結(jié)合,引入自適應(yīng)核帶寬的思想,避免了人為設(shè)定核帶寬,更好地適應(yīng)不同數(shù)據(jù)集的數(shù)據(jù)分布。本文提出了期望距離,并定義了期望核密度離群因子刻畫數(shù)據(jù)對象離群程度,從而檢測出離群點。對所提算法的正確性和復(fù)雜性進行分析,在人工數(shù)據(jù)集和真實數(shù)據(jù)集上的實驗證明,EKDOF 算法具有良好的檢測精度和穩(wěn)定性,能夠在各種分布的數(shù)據(jù)集上表現(xiàn)出優(yōu)越的性能。