FNOD:基于近鄰差波動(dòng)因子的離群點(diǎn)檢測(cè)算法①

張忠平 鄧禹 劉偉雄 張玉停

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

（??河北省計(jì)算機(jī)虛擬技術(shù)與系統(tǒng)集成重點(diǎn)實(shí)驗(yàn)室 秦皇島066004）

（???河北省軟件工程重點(diǎn)實(shí)驗(yàn)室 秦皇島066004）

0 引言

離群點(diǎn)是數(shù)據(jù)集中偏離大部分?jǐn)?shù)據(jù)的數(shù)據(jù),由于偏離其他數(shù)據(jù)太多,這些數(shù)據(jù)的偏離可能并非由隨機(jī)因素產(chǎn)生,而是產(chǎn)生于完全不同的機(jī)制[1]。離群點(diǎn)檢測(cè)是一個(gè)長(zhǎng)期存在于數(shù)據(jù)挖掘領(lǐng)域的基本主題,其旨在消除噪音和干擾或發(fā)現(xiàn)潛在的、有價(jià)值的信息。離群點(diǎn)檢測(cè)在欺詐檢測(cè)[2]、垃圾郵件檢測(cè)[3]、交通異常檢測(cè)[4]、入侵檢測(cè)[5-6]、醫(yī)療與公共衛(wèi)生安全監(jiān)測(cè)[7]等領(lǐng)域有著廣闊的應(yīng)用前景。

目前,國(guó)內(nèi)外許多學(xué)者在離群點(diǎn)檢測(cè)領(lǐng)域的研究十分活躍,提出了大量?jī)?yōu)秀的離群點(diǎn)檢測(cè)方法,這些方法大致可分為基于分布的、基于距離的、基于密度的、基于聚類的和基于深度的5種[8]。近年來(lái)也有一些新方法被提出,文獻(xiàn)[9]和文獻(xiàn)[10]通過(guò)構(gòu)建k 近鄰（k nearest neighbors,KNN）圖,利用圖的標(biāo)簽傳播和隨機(jī)游走的方法檢測(cè)離群點(diǎn)。

早期基于分布的方法通過(guò)判斷數(shù)據(jù)點(diǎn)偏離正常分布模式的程度判斷離群點(diǎn)[11],但該方法不適用于高維數(shù)據(jù)集,特別是數(shù)據(jù)集數(shù)據(jù)分布未知的情況。

為了改進(jìn)基于分布方法的缺陷,文獻(xiàn)[12]提出了一種基于距離的離群點(diǎn)檢測(cè)方法。該方法通過(guò)計(jì)算數(shù)據(jù)點(diǎn)到其k 近鄰點(diǎn)的平均距離,選取平均距離最大的n個(gè)點(diǎn)作為離群點(diǎn),但由于該方法使用的是全局閾值,未考慮局部環(huán)境的影響,因此難以檢測(cè)局部離群點(diǎn)。

為解決基于距離方法的問(wèn)題,文獻(xiàn)[13]定義了局部離群因子（local outlier factor,LOF）算法,該方法將數(shù)據(jù)點(diǎn)與其k 近鄰點(diǎn)平均距離的倒數(shù)看作局部密度因子,密度因子越小,該點(diǎn)是離群點(diǎn)的概率越高。LOF 算法作為經(jīng)典的局部離群點(diǎn)檢測(cè)算法已被廣泛研究,但存在精確度較低、參數(shù)敏感等問(wèn)題,很多研究學(xué)者都對(duì)此算法提出了改進(jìn)。INFLO（influence outlierness）算法[14]、NOF（natural outlier factor）算法[15]分別在局部密度因子中引入了反向k 近鄰（reverse k nearest neighborhood,RNN）和相互k 近鄰（mutal k neighborhood,MUN）提高了算法的性能。RDOS（reverse shared outlier density）算法[16]將局部密度因子替換為效果更好的核密度,同時(shí)引入反向k 近鄰、相互k 近鄰和共享k 近鄰提高了檢測(cè)精度。文獻(xiàn)[17]提出的DDPOS（density and distance parameters outlier factor scores）算法利用反向k 近鄰來(lái)排除掉部分邊界點(diǎn)的干擾,類似的算法還有RDOF（relative density outlier factor）[18]和LCDO（local correlation dimension outlier）[19]。

文獻(xiàn)[20]引入反向近鄰關(guān)系,提出了一種將k近鄰點(diǎn)和反向k 近鄰點(diǎn)數(shù)的比值作為離群因子的快速離群點(diǎn)檢測(cè)方法。文獻(xiàn)[21]提出了一種基于不穩(wěn)定因子的離群點(diǎn)檢測(cè)方法INS（INStability factor）,通過(guò)計(jì)算虛擬k 近鄰點(diǎn)的穩(wěn)定性判斷離群點(diǎn)。以上方法都需要遍歷數(shù)據(jù)集中所有點(diǎn),然后再對(duì)離群因子進(jìn)行排序來(lái)確定離群點(diǎn),但是此類方法對(duì)計(jì)算位于聚類區(qū)域的正常點(diǎn)是沒(méi)有必要的。

為解決上述問(wèn)題,文獻(xiàn)[22]通過(guò)DBSCAN（density-based spatial clustering of applications with noise）聚類的方法剪枝位于聚類中心的正常點(diǎn),只計(jì)算保留下的可疑點(diǎn),減少了后續(xù)離群點(diǎn)檢測(cè)算法的計(jì)算量。文獻(xiàn)[23]提出了一種基于累積權(quán)熵空間聚類（subspace outlier detection cumulative holoentropy,SODCH）的離群點(diǎn)檢測(cè)算法,利用k-means 對(duì)子空間進(jìn)行聚類,根據(jù)累積權(quán)熵檢測(cè)離群點(diǎn),大幅提高了算法處理數(shù)據(jù)的力度。文獻(xiàn)[24]利用相互k 近鄰關(guān)系提出了一種無(wú)參數(shù)的聚類方法,減少了算法對(duì)參數(shù)k的依賴。文獻(xiàn)[25]提出了一種基于聚類因子和相互密度的離群點(diǎn)檢測(cè)算法,通過(guò)引入相互k 近鄰關(guān)系提高了算法的精確度。

通過(guò)對(duì)上述算法的總結(jié)可以看出,很多改進(jìn)算法都在原有的離群因子中引入了更復(fù)雜的近鄰關(guān)系,但沒(méi)有改變離群因子的計(jì)算方法,且未考慮變化的參數(shù)k對(duì)離群點(diǎn)檢測(cè)的影響。隨著數(shù)據(jù)分布越來(lái)越復(fù)雜,這些離群點(diǎn)檢測(cè)算法效果不夠理想,因此,本文提出一種基于變化參數(shù)k的離群因子,為離群點(diǎn)檢測(cè)提供了新的研究方向?；诰垲惖募糁Ψ椒▽?duì)數(shù)據(jù)聚類程度要求較高,不能適應(yīng)多種數(shù)據(jù)集,因此提出一種新的剪枝方法,也是一個(gè)新的研究方向。綜上所述,本文引入相互k 近鄰關(guān)系,提出了一種基于近鄰差波動(dòng)因子的離群點(diǎn)檢測(cè)算法（outlier detection algorithm based on fluctuation of nearest neighbor difference factor,FNOD）。該算法引入相互k 近鄰關(guān)系,首先提出一種近鄰剪枝算法（neighbor pruning factor algorithm,NPF）剪枝正常點(diǎn),保留離群度較高的可疑點(diǎn),降低運(yùn)算量,提升后續(xù)離群點(diǎn)檢測(cè)算法的精確度;其次設(shè)計(jì)迭代減小的參數(shù)k,隨著k值減小,離群點(diǎn)的相互k 近鄰變化程度要小于正常點(diǎn);最后利用數(shù)據(jù)點(diǎn)相互k 近鄰變化的波動(dòng)程度刻畫(huà)每個(gè)點(diǎn)的離群程度。

本文其余部分安排如下。第1 節(jié)介紹相關(guān)工作,關(guān)于相關(guān)算法的各種定義。第2 節(jié)對(duì)本文提出的算法進(jìn)行闡述。第3 節(jié)通過(guò)實(shí)驗(yàn)對(duì)所提算法的實(shí)效性進(jìn)行驗(yàn)證。第4 節(jié)對(duì)本文做出總結(jié)。

1 相關(guān)工作

下面簡(jiǎn)要介紹相互k 近鄰數(shù)搜索算法。

1.1 相關(guān)定義

定義1k 距離（k_distance）[15]。數(shù)據(jù)點(diǎn)p的k距離表示點(diǎn)p和其第k個(gè)近鄰點(diǎn)o之間的歐氏距離,用k_dist（p）表示。點(diǎn)p至多存在（k-1）個(gè)o′點(diǎn)滿足dist（p,o′）≤dist（p,o）。

定義2k 近鄰[15]。點(diǎn)p把點(diǎn)q看作k近鄰點(diǎn)。數(shù)據(jù)點(diǎn)p的k近鄰集合表示為KNN（p）?D,要求點(diǎn)q滿足dist（p,q）≤k_dist（p）,定義為式（1）。

其中,D表示數(shù)據(jù)集,p、q、o為數(shù)據(jù)集D中的數(shù)據(jù)點(diǎn),dist（p,q）表示點(diǎn)p、q之間的歐式距離,k為正整數(shù)。

定義3反向k 近鄰[15]。數(shù)據(jù)點(diǎn)p被點(diǎn)q看作k 近鄰點(diǎn),數(shù)據(jù)點(diǎn)p的反向k 近鄰集合用RNN（p）?D表示,定義為式（2）。

定義4相互k 近鄰。數(shù)據(jù)點(diǎn)p的相互k 近鄰用MUN（p）?D表示,要求在當(dāng)前k值下,點(diǎn)p是點(diǎn)q的k 近鄰,同時(shí)點(diǎn)p也是點(diǎn)q的反向k 近鄰,定義為式（3）。

相互k 近鄰建立在k 近鄰的基礎(chǔ)上,要求兩點(diǎn)互相將對(duì)方看作k 近鄰,受距離和參數(shù)k的影響,當(dāng)一個(gè)點(diǎn)距離其他點(diǎn)越遠(yuǎn)時(shí),其越不容易被其他點(diǎn)選為k 近鄰點(diǎn),也就很難形成相互k 近鄰關(guān)系。圖1中單向箭頭表示k 近鄰,雙向箭頭表示相互k 近鄰。k=1 時(shí),點(diǎn)q是點(diǎn)p的k 近鄰,由于點(diǎn)q與點(diǎn)o的距離小于點(diǎn)q與點(diǎn)p的距離,所以點(diǎn)q的k 近鄰是點(diǎn)o,同理點(diǎn)o的k 近鄰點(diǎn)是點(diǎn)q,因此點(diǎn)q與點(diǎn)o形成相互近鄰關(guān)系,未與點(diǎn)p形成相互近鄰關(guān)系。若使點(diǎn)p與點(diǎn)o和q形成相互近鄰關(guān)系,只有擴(kuò)大參數(shù)k值,使點(diǎn)p成為點(diǎn)q和o的k 近鄰點(diǎn)。如圖1（b）中k=2 時(shí)所示,點(diǎn)p成為點(diǎn)o和q的第2個(gè)k近鄰點(diǎn),此時(shí)點(diǎn)p形成了相互k近鄰關(guān)系,所以相互k 近鄰關(guān)系受到距離和參數(shù)k的影響。

圖1 相互k 近鄰關(guān)系

圖2 顯示了不同k值下,數(shù)據(jù)點(diǎn)相互k 近鄰的變化情況。圖中虛線單向箭頭代表k 近鄰關(guān)系,雙向箭頭代表相互k 近鄰關(guān)系（點(diǎn)o和r存在一條雙向箭頭）,點(diǎn)p為離群點(diǎn)。

圖2 參數(shù)k 變化對(duì)相互k 近鄰關(guān)系的影響

由于圖中離群點(diǎn)p遠(yuǎn)離其他點(diǎn),且參數(shù)k較小,所以點(diǎn)[o,s,r] 是點(diǎn)p的k 近鄰點(diǎn),但點(diǎn)p不是點(diǎn)[o,s,r] 的k 近鄰點(diǎn),因此點(diǎn)[o,s,r] 不會(huì)與點(diǎn)p形成相互近鄰關(guān)系。k=4 時(shí)點(diǎn)p僅與點(diǎn)q形成了相互近鄰關(guān)系,而其他點(diǎn)均有3 或4 個(gè)相互k 近鄰點(diǎn)。

表1 統(tǒng)計(jì)了圖2 中不同參數(shù)k下,部分?jǐn)?shù)據(jù)點(diǎn)相互k 近鄰點(diǎn)的變化。當(dāng)參數(shù)k遞減時(shí),數(shù)據(jù)點(diǎn)的k 近鄰點(diǎn)減少,所以數(shù)據(jù)點(diǎn)的相互k 近鄰點(diǎn)也會(huì)減少,相互近鄰點(diǎn)開(kāi)始發(fā)生變化。由于離群點(diǎn)p僅有一個(gè)相互k 近鄰點(diǎn),因此隨著參數(shù)k下降,最多發(fā)生一次相互k 近鄰變化。但位于聚類區(qū)域的點(diǎn)[q,o,s],由于其相互k 近鄰點(diǎn)個(gè)數(shù)接近k 近鄰點(diǎn)個(gè)數(shù),伴隨k值下降,這些點(diǎn)會(huì)有多次相互k 近鄰變化。

根據(jù)圖2 和表1 的描述可以總結(jié)出:（1）在某一參數(shù)k下,離群點(diǎn)的相互k 近鄰點(diǎn)個(gè)數(shù)要小于k近鄰點(diǎn)個(gè)數(shù);（2）在變化的近鄰參數(shù)k下,離群點(diǎn)的相互k 近鄰點(diǎn)數(shù)相對(duì)穩(wěn)定,不易發(fā)生變化。本文根據(jù)（1）設(shè)計(jì)一種基于相互k 近鄰關(guān)系的近鄰剪枝方法,排除正常點(diǎn);根據(jù)（2）設(shè)計(jì)一種在變化參數(shù)k下基于數(shù)據(jù)點(diǎn)相互k 近鄰波動(dòng)的離群點(diǎn)檢測(cè)算法。

表1 數(shù)據(jù)點(diǎn)相互k 近鄰點(diǎn)個(gè)數(shù)

1.2 相互k 近鄰數(shù)統(tǒng)計(jì)算法

根據(jù)1.1 節(jié)描述的相關(guān)定義,統(tǒng)計(jì)相互k 近鄰數(shù)量的算法如算法1 所示,首先根據(jù)輸入的近鄰參數(shù)k計(jì)算每個(gè)點(diǎn)的k 近鄰和反k 近鄰;再根據(jù)相互k 近鄰的定義,搜索每個(gè)數(shù)據(jù)點(diǎn)的相互k 近鄰;最后統(tǒng)計(jì)每個(gè)數(shù)據(jù)點(diǎn)的相互k 近鄰的數(shù)量作為輸出。

在相互近鄰數(shù)搜索（MUNn-Searching）算法中,KNN（i）代表數(shù)據(jù)點(diǎn)i的k 近鄰點(diǎn)集合,RNN（i）代表數(shù)據(jù)點(diǎn)i的反向k近鄰集合,MUN（i）代表數(shù)據(jù)點(diǎn)i的相互k近鄰點(diǎn)集合。MUNn-Searching 算法的時(shí)間復(fù)雜度源于利用KD 樹(shù)計(jì)算k 近鄰點(diǎn)的過(guò)程,時(shí)間復(fù)雜度為O（n·logn）,n為數(shù)據(jù)集中數(shù)據(jù)點(diǎn)的個(gè)數(shù)。

2 近鄰差波動(dòng)算法

2.1 近鄰剪枝算法思想

離群點(diǎn)檢測(cè)算法中對(duì)聚類區(qū)域中正常點(diǎn)的計(jì)算是沒(méi)有必要的,為減少此類點(diǎn)的計(jì)算,本文利用相互k 近鄰提出了一種近鄰剪枝算法,能夠剪枝大部分聚類區(qū)域的正常點(diǎn),減少后續(xù)離群點(diǎn)檢測(cè)算法的計(jì)算量。

根據(jù)定義2 k 近鄰、定義4 相互k 近鄰和圖2可知,由于離群的數(shù)據(jù)點(diǎn)距離聚類區(qū)域的數(shù)據(jù)點(diǎn)較遠(yuǎn),難以被聚類區(qū)域的點(diǎn)看作k 近鄰點(diǎn),因此相互k 近鄰點(diǎn)的數(shù)量遠(yuǎn)遠(yuǎn)小于k 近鄰點(diǎn)數(shù)量,反之位于聚類區(qū)域點(diǎn)的相互k 近鄰點(diǎn)數(shù)量接近k 近鄰點(diǎn)數(shù)量。因此,聚類區(qū)域點(diǎn)的k 近鄰點(diǎn)數(shù)與相互k 近鄰點(diǎn)數(shù)的比值接近1,稀疏區(qū)域點(diǎn)的k 近鄰點(diǎn)數(shù)與相互k 近鄰點(diǎn)數(shù)的比值遠(yuǎn)遠(yuǎn)大于1。據(jù)此特點(diǎn)可以使大部分正常點(diǎn)被剪枝。

定義5近鄰剪枝因子（NPF）。NPF（p）是數(shù)據(jù)點(diǎn)p在某一k值下k 近鄰個(gè)數(shù)和相互k 近鄰點(diǎn)個(gè)數(shù)的比值,定義為式（4）。

式中,KNNn（p）表示數(shù)據(jù)點(diǎn)的k 近鄰點(diǎn)個(gè)數(shù),等于近鄰參數(shù)k,MUNn（p）表示數(shù)據(jù)點(diǎn)p的相互k 近鄰點(diǎn)個(gè)數(shù)。將分母MUNn（p）加1 是為了防止出現(xiàn)分母為0,即數(shù)據(jù)點(diǎn)p沒(méi)有相互k 近鄰點(diǎn)的特殊情況,分子KNNn（p）加1 是為了降低MUNn（p）加1 帶來(lái)的影響。

2.2 近鄰剪枝算法

根據(jù)2.1 節(jié)中描述及相關(guān)定義,近鄰剪枝算法如算法2 所示,該算法首先根據(jù)輸入的參數(shù)k統(tǒng)計(jì)數(shù)據(jù)點(diǎn)k 近鄰點(diǎn)和相互k 近鄰點(diǎn)個(gè)數(shù),隨后計(jì)算數(shù)據(jù)點(diǎn)的近鄰剪枝因子NPF,最后對(duì)所有數(shù)據(jù)點(diǎn)按NPF 值降序排序,保留最大的前pt個(gè)數(shù)據(jù)點(diǎn)作為可疑點(diǎn)。

剪枝后保留的可疑點(diǎn)的相互近鄰數(shù)很少,能夠減少相互近鄰隨參數(shù)k變化而變化的次數(shù),有利于提高基于近鄰差波動(dòng)的離群點(diǎn)檢測(cè)算法精度。NPF算法的時(shí)間復(fù)雜度主要來(lái)源于利用KD 樹(shù)計(jì)算k 近鄰點(diǎn)的過(guò)程,時(shí)間復(fù)雜度為O（n·logn）,n為數(shù)據(jù)集中數(shù)據(jù)點(diǎn)的個(gè)數(shù)。相比基于聚類的剪枝算法[22],具有剪枝程度大、速度快的優(yōu)點(diǎn)。

2.3 近鄰差波動(dòng)因子算法思想

本文提出了一種基于近鄰差波動(dòng)因子的離群點(diǎn)檢測(cè)方法FNOD,算法思想源于相互k 近鄰關(guān)系。聚類區(qū)域的點(diǎn)容易形成相互k 近鄰,且相互k 近鄰易隨參數(shù)k減小而減少,相反,由于離群點(diǎn)遠(yuǎn)離聚類區(qū)域,相互k 近鄰點(diǎn)很少,所以相互k 近鄰不易隨k值減小而減少。

圖3 所示的數(shù)據(jù)集中,雙向虛線代表相互k 近鄰關(guān)系,A代表一個(gè)小聚類,點(diǎn)B為局部離群點(diǎn),點(diǎn)C、D、E為全局離群點(diǎn)。虛線表示在當(dāng)前k值下存在的相互k 近鄰關(guān)系。對(duì)比發(fā)現(xiàn)在k=[10,9,…,2]過(guò)程中全局離群點(diǎn)C、D、E的相互k 近鄰點(diǎn)不會(huì)變化;k=[1,2,…,5]過(guò)程中局部離群點(diǎn)B的相互k近鄰點(diǎn)不會(huì)變化;聚類A中的點(diǎn)在k每次變化后都會(huì)發(fā)生變化。離群程度越高的點(diǎn)越不易發(fā)生相互近鄰的變化,本文據(jù)此設(shè)置一個(gè)迭代減小的參數(shù)k,隨著k值減小,數(shù)據(jù)點(diǎn)相互k 近鄰點(diǎn)發(fā)生變化,離群程度越高的點(diǎn),其相互k 近鄰點(diǎn)數(shù)越少,甚至為0,不易變化。本文設(shè)計(jì)用波動(dòng)的方式描述數(shù)據(jù)點(diǎn)相互近鄰變化程度,波動(dòng)越小的點(diǎn)是離群點(diǎn)的概率越大。

圖3 FNOD 算法思想示意圖

2.4 相關(guān)定義

本節(jié)詳細(xì)介紹FNOD 算法及其相關(guān)定義,其中,D表示數(shù)據(jù)集;p代表數(shù)據(jù)集中的數(shù)據(jù)點(diǎn);i代表參數(shù)k的迭代次數(shù);ki代表第i次迭代 時(shí)的k值;MUNi（p）表示數(shù)據(jù)點(diǎn)p在第i次迭代時(shí)的相互k 近鄰點(diǎn)個(gè)數(shù);n為正整數(shù)表示初始k值。

定義6近鄰差d（p）。di（p）是數(shù)據(jù)點(diǎn)p第i次迭代后相互k 近鄰點(diǎn)數(shù)的差,用來(lái)描述相互k 近鄰的變化程度,定義為式（5）。式中MUNi-1（p）和MUNi（p）分別為第i-1 和第i次參數(shù)k變化后,數(shù)據(jù)點(diǎn)p的相互k 近鄰點(diǎn)個(gè)數(shù)。n為數(shù)據(jù)點(diǎn)個(gè)數(shù),本文將一個(gè)di（p）看作一次波動(dòng)。

定義7穩(wěn)態(tài)ST（steady）。穩(wěn)態(tài)表示數(shù)據(jù)點(diǎn)在相鄰兩次k值變化過(guò)程中近鄰波動(dòng)差di（p）=0 的狀態(tài)。

本文定義ST=0,是因離群點(diǎn)的相互k 近鄰點(diǎn)較少,因此在近鄰參數(shù)k下降過(guò)程中,離群點(diǎn)的近鄰差不容易發(fā)生變化,即di（p）=0,相反正常點(diǎn)會(huì)隨著參數(shù)k的變化而變化。統(tǒng)計(jì)數(shù)據(jù)點(diǎn)在整個(gè)參數(shù)k值迭代過(guò)程中di（p）每次的變化情況是否貼近di（p）=0,因此設(shè)置整體穩(wěn)態(tài)ST=0。

定義8近鄰下降率α。參數(shù)k的下降速度定義為近鄰下降率。定義為式（6）。

近鄰下降率α直接決定算法迭代的次數(shù),α值越大,k值減小的速度越快,算法迭代的次數(shù)越少,但會(huì)降低離群點(diǎn)檢測(cè)的精確度。如圖4 所示,k=3時(shí)點(diǎn)p的相互近鄰點(diǎn)數(shù)為1;k=2 時(shí),點(diǎn)p的相互k近鄰點(diǎn)減少到0;k=1 時(shí),點(diǎn)p的相互k 近鄰點(diǎn)仍為0。因此k值從3 到2 形成了一次波動(dòng),從2 到1 是一個(gè)穩(wěn)態(tài)。穩(wěn)態(tài)有利于增加離群程度,而波動(dòng)會(huì)降低離群程度。若參數(shù)k直接從3 降到1,會(huì)丟失一個(gè)穩(wěn)態(tài),降低離群程度,因此本文設(shè)置近鄰下降率α=1。

圖4 近鄰下降率α 對(duì)穩(wěn)態(tài)的影響

此外設(shè)置k=1 時(shí)停止迭代,此時(shí)每個(gè)數(shù)據(jù)點(diǎn)只 有1 個(gè)k 近鄰點(diǎn),每個(gè)數(shù)據(jù)點(diǎn)至多只有1 個(gè)相互k近鄰點(diǎn),減少相互k 近鄰點(diǎn)數(shù)由1 到0 帶來(lái)的必然波動(dòng)。

定義9近鄰差波動(dòng)因子FNOD（p）描述數(shù)據(jù)點(diǎn)p隨k值下降,點(diǎn)p的近鄰波動(dòng)差d（p）的變化情況,參考統(tǒng)計(jì)學(xué)中的標(biāo)準(zhǔn)差,定義為式（7）。

標(biāo)準(zhǔn)差描述的是各個(gè)階段的數(shù)據(jù)相對(duì)均值的波動(dòng)情況,本文中要求統(tǒng)計(jì)數(shù)據(jù)點(diǎn)相對(duì)于穩(wěn)態(tài)的波動(dòng)情況,因此,用穩(wěn)態(tài)ST=0 替換均值。本文設(shè)置初始參數(shù)k,同時(shí)參數(shù)k按近鄰下降率α=1 迭代,直到k=1,共迭代n-1 次。FNOD（p）波動(dòng)值越小,說(shuō)明此點(diǎn)是離群點(diǎn)的概率越高。

在圖5 （a）所示的人工數(shù)據(jù)集中,驗(yàn)證了隨著參數(shù)k減小,不同類型的點(diǎn)的近鄰差波動(dòng)不同。圖中數(shù)據(jù)點(diǎn)A和B為正常點(diǎn)、C為離群點(diǎn),它們的近鄰差波動(dòng)如圖5（b）所示,圖中橫坐標(biāo)軸為參數(shù)k,縱坐標(biāo)軸為近鄰波動(dòng)差,根據(jù)近鄰波動(dòng)因子,定義ST=0 為橫坐標(biāo)軸。計(jì)算圖中折線相對(duì)于橫坐標(biāo)軸的波動(dòng)情況,可得FNOD（A）=0.95、FNOD（B）=1.0、FNOD（C）=0.46。點(diǎn)C的近鄰波動(dòng)因子遠(yuǎn)小于其余兩點(diǎn),因此點(diǎn)C為離群點(diǎn)。通過(guò)觀察圖5（b）也可以看出,離群點(diǎn)C的波動(dòng)程度很小,只有4次d（p）=1 的波動(dòng),相反正常點(diǎn)B有18次d（p）=1,點(diǎn)A擁有多次d（p）=1和d（p）=2 的波動(dòng)。

圖5 正常數(shù)據(jù)和離群數(shù)據(jù)樣本

2.5 FNOD 算法描述

本文提出的一種基于近鄰差波動(dòng)的離群點(diǎn)檢測(cè)算法FNOD,輸入數(shù)據(jù)集D和參數(shù)k,輸出離群點(diǎn)。首先對(duì)數(shù)據(jù)集進(jìn)行剪枝,排除位于聚類區(qū)域的正常點(diǎn),留下可疑點(diǎn);隨后在迭代減小的參數(shù)k下,計(jì)算可疑點(diǎn)的近鄰波動(dòng)因子,按從小到大排序,前n個(gè)點(diǎn)即為離群點(diǎn)。FNOD 算法代碼如算法3 所示。

算法3中Odoubt存放剪枝后保留的可疑點(diǎn),MUN（pk）為當(dāng)前k值下,數(shù)據(jù)點(diǎn)p的相互k 近鄰點(diǎn)數(shù),集合MUN（p）存放點(diǎn)p每次k值變化后的相互近鄰數(shù),集合FNOD（Odoubt）存放所有可疑點(diǎn)的近鄰差波動(dòng)因子,算法最終輸出波動(dòng)最小的前n個(gè)點(diǎn)作為離群點(diǎn)。FNOD 算法的時(shí)間復(fù)雜度主要來(lái)源于兩方面:（1）使用KD 樹(shù)尋找相互k 近鄰點(diǎn)個(gè)數(shù),時(shí)間復(fù)雜度為O（n·logn）,n為剪枝后可疑點(diǎn)個(gè)數(shù);（2）參數(shù)k迭代減小,時(shí)間復(fù)雜度為O（k）。算法總體的時(shí)間復(fù)雜度為O（k·n·logn）。

3 實(shí)驗(yàn)評(píng)估

為檢測(cè)FNOD 算法的性能,在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集下進(jìn)行實(shí)驗(yàn),同時(shí)將FNOD 算法與較為流行的——利用其他近鄰關(guān)系的LOF[13]、INFLO[14]、NOF[20]、NOF2[15]算法和同樣迭代k值的INS[21]算法進(jìn)行對(duì)比。FNOD 算法和INS 算法的k值分別對(duì)應(yīng)初始k值和截止k值。實(shí)驗(yàn)環(huán)境如表2 所示,實(shí)驗(yàn)結(jié)果使用Python 進(jìn)行可視化處理。

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

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

在大多數(shù)實(shí)際應(yīng)用中,相比大量存在的正常數(shù)據(jù),含有異常值的數(shù)據(jù)顯得非常稀有,數(shù)據(jù)分布存在極端不平衡現(xiàn)象。因此,常見(jiàn)的準(zhǔn)確率等指標(biāo)不能客觀評(píng)價(jià)算法性能。為評(píng)估離群點(diǎn)檢測(cè)的性能,針對(duì)人工數(shù)據(jù)集,采用精確率（precision,Pr）指標(biāo)進(jìn)行評(píng)估。精確率定義如式（8）所示。

式中,TP表示算法檢測(cè)到的真實(shí)離群點(diǎn)數(shù)量,FP表示算法錯(cuò)誤地將正常點(diǎn)判斷為離群點(diǎn)的數(shù)量。精確率數(shù)值越大,算法性能越好。

針對(duì)真實(shí)數(shù)據(jù)集,采用F1 曲線和接受者操作特性曲線（receiver operating characteristic curve,ROC）的曲線下面積（area under curve,AUC）進(jìn)行評(píng)估。F1 值是衡量二分類模型的一種常用指標(biāo),其同時(shí)兼顧了精確率和召回率兩個(gè)指標(biāo)。F1 值越接近1,算法性能越好。F1 值定義如式（9）所示。

ROC 是以真陽(yáng)性率（TPR）為縱坐標(biāo),假陽(yáng)性率（FPR）為橫坐標(biāo)繪制的曲線,ROC 曲線描繪了兩者的相對(duì)權(quán)衡。真陽(yáng)性率和假陽(yáng)性率的定義如式（10）、（11）所示。AUC 可以直觀地展現(xiàn)出算法的性能,值取0 到1 之間,越大的AUC 值意味著算法有更大的概率將離群點(diǎn)排在正常點(diǎn)之前,所以AUC 值越大越好,小于0.5 意味著算法不可用。

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

為測(cè)試本文算法在各種復(fù)雜數(shù)據(jù)分布下的性能,實(shí)驗(yàn)在圖6 所示的6 種二維人工數(shù)據(jù)集Data_01～ Data_06 中進(jìn)行,圖6 中“o”代表離群點(diǎn)。每個(gè)數(shù)據(jù)集的屬性特征如表3 所示。

圖6 6 種人工數(shù)據(jù)集分布

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

圖7 展示了本文FNOD 算法和其余5 個(gè)算法在6 個(gè)人工數(shù)據(jù)集上精確率隨k值變化的過(guò)程,橫坐標(biāo)為k值,縱坐標(biāo)為精確率Pr。

圖7 人工數(shù)據(jù)集下不同算法的精確率變化曲線

隨著參數(shù)k不斷增大,FNOD 算法的精準(zhǔn)率不斷上升,最終大于或等于其余算法。特別是在Data_01、Data_05、Data_06 中,FNOD 算法的峰值超出了其余算法的峰值,分別達(dá)到0.95、0.98、0.86。此外FNOD 算法在Data_02、Data_03、Data_06 數(shù)據(jù)集中,曲線變化程度接近且高于同樣使用相互k近鄰關(guān)系的NOF2 算法。隨著k值不斷增大,實(shí)驗(yàn)中所有算法的精確率有所下降,但本文FNOD 算法的下降程度要低于其余算法,特別是在Data_01 數(shù)據(jù)集中初始參數(shù)k從150 增加到300 的過(guò)程中LOF、INFLO、NOF 和NOF2 的下降率分別為0.05、0.11、0.07 和0.10,而FNOD 的下降率為0.04,這是因?yàn)殡S著參數(shù)k增大,利用距離或密度的方法會(huì)不斷獲取一個(gè)較遠(yuǎn)的近鄰點(diǎn),這些方法依賴k 近鄰點(diǎn)的距離計(jì)算離群因子,因此不斷加入距離較大的k 近鄰點(diǎn)不利于算法的精確度,而本文FNOD 算法用數(shù)量計(jì)算離群程度,受到的影響較小。

由于INS 算法相比于其余算法需要更大的k值,所以圖7 中沒(méi)有體現(xiàn)INS 算法的最佳精確率,將INS 算法的最佳精確率放置在表4 中。

表4 人工數(shù)據(jù)集精確率

通過(guò)總結(jié)圖7 和表4 的數(shù)據(jù),FNOD 算法在Data_02、Data_01、Data_03、Data_06 表現(xiàn)最優(yōu),Data_04 和Data_05 數(shù)據(jù)集中數(shù)據(jù)聚類不明顯,所以表現(xiàn)略低于NOF2 算法。由于FNOD 算法需要統(tǒng)計(jì)多次參數(shù)k變化下的數(shù)據(jù),當(dāng)初始k值取到10 和20時(shí),算法只能獲得9 和19 次的波動(dòng)數(shù)據(jù),因此FNOD 算法在初始k值較小的情況下精確率較低。隨著初始k值增加,FNOD 算法獲取波動(dòng)的數(shù)據(jù)增多,算法的精確度提高。

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

為較為全面地檢測(cè)FNOD算法的真實(shí)性能,本文實(shí)驗(yàn)選擇在6 個(gè)真實(shí)數(shù)據(jù)集Ecoli、Lonoshpere、Lymphography、PenDigits、Stamps 和Wdbc 中進(jìn)行,6個(gè)真實(shí)數(shù)據(jù)集均來(lái)自UCI 數(shù)據(jù)庫(kù),表5 展示了真實(shí)數(shù)據(jù)集的數(shù)據(jù)特征。

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

表6 展示了真實(shí)數(shù)據(jù)集下FNOD 算法和其余5個(gè)算法的AUC 值,同時(shí)標(biāo)注出每個(gè)數(shù)據(jù)集中排名前2 的算法。FNOD 算法在每個(gè)真實(shí)數(shù)據(jù)集上的AUC值均屬于表現(xiàn)最優(yōu)的前2 個(gè)算法。特別是在Ecoli和PenDigits 中,FNOD 的AUC 值達(dá)到了0.96,超過(guò)同樣使用相互近鄰關(guān)系的NOF2 算法的0.91 和使用變化k值的INS 算法的0.78。在數(shù)據(jù)量較大的PenDigits 和離群點(diǎn)數(shù)較多的Lonoshpere 中,FNOD算法同樣保持了較好的檢測(cè)效果。面對(duì)維數(shù)較高的數(shù)據(jù)集Lymphography 時(shí),FNOD 算法表現(xiàn)不佳,僅為0.80,但也接近其余幾種算法的最佳值。整體上看FNOD 算法AUC 值大于同樣使用相互k近鄰的NOF2 算法。

表6 真實(shí)數(shù)據(jù)集AUC值

圖8 展示了各個(gè)算法F1 值隨參數(shù)k變化的曲線。通過(guò)觀察圖像可以得到,在各個(gè)數(shù)據(jù)集中,除在PenDigits 和Stamps 下的INS 算法F1 值為0.5,其余每個(gè)算法在各個(gè)數(shù)據(jù)集下的F1 曲線都接近一條逐漸上升的擬合曲線,表明各算法都具備一定的二分類效果。

圖8 真實(shí)數(shù)據(jù)集下不同算法的F1 值變化曲線

真實(shí)數(shù)據(jù)集中,FNOD 算法在初始參數(shù)k較小時(shí)性能要低于其余5 種算法。隨著k值增大,FNOD算法的F1 值逐漸上升,最佳F1 值大于或等于其余算法。由于Ecoli 數(shù)據(jù)集和數(shù)據(jù)集Lymphography 中數(shù)據(jù)數(shù)量較少,較大的初始參數(shù)k會(huì)接近數(shù)據(jù)點(diǎn)數(shù)量,從而導(dǎo)致數(shù)據(jù)集中離群點(diǎn)擁有較多的相互k 近鄰點(diǎn),不利于本文算法,所以FNOD 算法僅接近或略高于其余算法。Stamps 數(shù)據(jù)集中FNOD 算法的F1峰值達(dá)到了1,超出了NOF2 算法的0.91 和LOF 算法的0.92。在Lonoshpere 數(shù)據(jù)集中,FNOD 算法和LOF、INFLO、NOF 的指標(biāo)均在0.82 上下波動(dòng)。FNOD 算法優(yōu)于同樣使用相互近鄰關(guān)系的NOF2 算法和利用參數(shù)k迭代的INS 算法。綜合上述2 個(gè)指標(biāo),相較于其他算法,FNOD 算法在檢測(cè)性能上有不同程度的優(yōu)勢(shì)。實(shí)驗(yàn)驗(yàn)證了本文算法能全面準(zhǔn)確地檢測(cè)到離群點(diǎn)。

3.4 檢測(cè)效率對(duì)比

為對(duì)比FNOD 算法和其余算法的離群點(diǎn)檢測(cè)效率,本節(jié)統(tǒng)計(jì)了各算法在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上達(dá)到最高檢測(cè)精度的時(shí)間消耗,同時(shí)標(biāo)注出每個(gè)數(shù)據(jù)集中排名前2 的算法,如表7 和表8 所示,表中單位為秒。

表7、表8 顯示了各算法在不同數(shù)據(jù)集下的時(shí)間消耗。本文的FNOD 算法在大部分?jǐn)?shù)據(jù)集中都屬于排名前2 的算法,特別是在Data_06 和PenDigits中,算法的時(shí)間消耗為9.36 s 和5.35 s,遠(yuǎn)低于其余算法。本文的FNOD 算法和INS 算法都需要計(jì)算不同k值下的近鄰信息,算法時(shí)間消耗較大,但由于FNOD 算法利用NPF 算法對(duì)數(shù)據(jù)集進(jìn)行了剪枝,很大程度上減少了算法關(guān)于正常點(diǎn)的計(jì)算,從而減少了時(shí)間消耗,所以FNOD 算法的時(shí)間消耗遠(yuǎn)低于INS 算法。此外,由于Data_02 和Ecoli 數(shù)據(jù)集中數(shù)據(jù)分布較為分散,NPF 算法能夠剪枝的正常點(diǎn)較少,導(dǎo)致FNOD 算法的時(shí)間消耗較大。綜上所述,結(jié)合圖7、圖8 的實(shí)驗(yàn)結(jié)果,可以看出FNOD 算法以較低的時(shí)間消耗保持了較高的算法性能。

表7 人工數(shù)據(jù)集時(shí)間消耗

表8 真實(shí)數(shù)據(jù)集時(shí)間消耗

4 結(jié)論

本文分析了基于各種近鄰關(guān)系的離群點(diǎn)檢測(cè)算法和近年來(lái)較為新穎的算法。針對(duì)傳統(tǒng)算法精確度較低且局限于獲取一個(gè)參數(shù)k下的離群信息的問(wèn)題,首先提出了一種基于相互k 近鄰關(guān)系的近鄰剪枝方法,排除大部分位于聚類區(qū)域的正常點(diǎn),減少了關(guān)于正常點(diǎn)的冗余計(jì)算,同時(shí)提高了FNOD 算法的精確度;其次,提出了一種基于相互近鄰波動(dòng)的離群點(diǎn)檢測(cè)算法,統(tǒng)計(jì)不同參數(shù)k下數(shù)據(jù)點(diǎn)的近鄰差,根據(jù)這種差值的波動(dòng)作為離群因子檢測(cè)離群點(diǎn)。在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集下的實(shí)驗(yàn)驗(yàn)證了該算法具有良好的離群點(diǎn)檢測(cè)能力。但算法對(duì)初始參數(shù)k的選取也較為敏感,如何自適應(yīng)獲取初始參數(shù)k、減少算法對(duì)參數(shù)的依賴從而提高精確率,將是未來(lái)的研究方向。