張忠平 鄧禹 劉偉雄 張玉停

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

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

（???河北省軟件工程重點實驗室 秦皇島066004）

0 引言

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

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

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

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

為解決基于距離方法的問題,文獻[13]定義了局部離群因子（local outlier factor,LOF）算法,該方法將數(shù)據(jù)點與其k 近鄰點平均距離的倒數(shù)看作局部密度因子,密度因子越小,該點是離群點的概率越高。LOF 算法作為經(jīng)典的局部離群點檢測算法已被廣泛研究,但存在精確度較低、參數(shù)敏感等問題,很多研究學(xué)者都對此算法提出了改進。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]將局部密度因子替換為效果更好的核密度,同時引入反向k 近鄰、相互k 近鄰和共享k 近鄰提高了檢測精度。文獻[17]提出的DDPOS（density and distance parameters outlier factor scores）算法利用反向k 近鄰來排除掉部分邊界點的干擾,類似的算法還有RDOF（relative density outlier factor）[18]和LCDO（local correlation dimension outlier）[19]。

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

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

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

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

1 相關(guān)工作

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

1.1 相關(guān)定義

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

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

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

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

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

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

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

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

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

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

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

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

表1 數(shù)據(jù)點相互k 近鄰點個數(shù)

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

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

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

2 近鄰差波動算法

2.1 近鄰剪枝算法思想

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

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

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

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

2.2 近鄰剪枝算法

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

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

2.3 近鄰差波動因子算法思想

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

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

圖3 FNOD 算法思想示意圖

2.4 相關(guān)定義

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

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

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

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

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

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

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

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

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

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

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

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

2.5 FNOD 算法描述

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

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

3 實驗評估

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

表2 實驗環(huán)境

3.1 實驗指標(biāo)

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

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

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

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

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

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

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

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

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

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

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

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

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

通過總結(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)計多次參數(shù)k變化下的數(shù)據(jù),當(dāng)初始k值取到10 和20時,算法只能獲得9 和19 次的波動數(shù)據(jù),因此FNOD 算法在初始k值較小的情況下精確率較低。隨著初始k值增加,FNOD 算法獲取波動的數(shù)據(jù)增多,算法的精確度提高。

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

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

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

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

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

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

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

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

3.4 檢測效率對比

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

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

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

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

4 結(jié)論

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