国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

基于自然鄰居鄰域圖的無參數(shù)離群檢測算法

2019-11-09 03:42馮驥冉瑞生魏延
智能系統(tǒng)學(xué)報(bào) 2019年5期
關(guān)鍵詞:離群鄰域局部

馮驥,冉瑞生,魏延

(重慶師范大學(xué) 計(jì)算機(jī)與信息科學(xué)學(xué)院,重慶 401331)

隨著大數(shù)據(jù)技術(shù)和數(shù)據(jù)密集型科學(xué)的發(fā)展,數(shù)據(jù)已經(jīng)滲透到各個行業(yè)和業(yè)務(wù)功能中,成為了生產(chǎn)的一個重要因素。越來越多的國家、政府、行業(yè)、企業(yè)等機(jī)構(gòu)已經(jīng)意識到大數(shù)據(jù)正在成為組織最重要的資產(chǎn),數(shù)據(jù)分析能力也已經(jīng)成為組織的核心競爭力。目前,國家、政府已經(jīng)把大數(shù)據(jù)應(yīng)用推進(jìn)了人們的生活中,大數(shù)據(jù)研究也成為了“十三五”期間的重點(diǎn)發(fā)展項(xiàng)目。

離群檢測也是大數(shù)據(jù)戰(zhàn)略中舉足輕重的核心技術(shù),在大數(shù)據(jù)技術(shù)發(fā)展日新月異之際,包括離群檢測在內(nèi),數(shù)據(jù)挖掘中聚類、分類等技術(shù)也隨之不斷地進(jìn)步與發(fā)展。離群檢測的目的在于檢測出數(shù)據(jù)集中那些被懷疑由異常機(jī)制產(chǎn)生的奇異數(shù)據(jù),廣泛應(yīng)用于欺詐檢測[1]、異常檢測[2]、圖像檢測[3]、醫(yī)學(xué)分析[4]、信號異常檢測[5]等,并取得了眾多令人滿意的結(jié)果。

然而迄今為止,對離群的定義沒有一個統(tǒng)一的認(rèn)識,因離群定義的不同,離群檢測算法的檢測結(jié)果也會有所不同。本文將同時考慮全局離群點(diǎn)和局部離群點(diǎn),提出了基于加權(quán)自然鄰居鄰域圖的離群檢測算法(weighted natural neighborhood graph outlier detection algorithm,WNaNG)。該算法利用加權(quán)自然鄰居鄰域圖計(jì)算局部自然鄰居離群度,找出離群度最高的n個離群點(diǎn),而無需人為地預(yù)設(shè)鄰域參數(shù)k。在此基礎(chǔ)上,本算法可以利用離群度的離散圖輔助挖掘出合理的離群點(diǎn),或利用長尾理論直接根據(jù)離群度的分布找到合理的離群點(diǎn)區(qū)間,進(jìn)而去除參數(shù)n,在無需鄰域參數(shù)k的基礎(chǔ)上將算法完善為完全無參數(shù)的離群檢測算法。

1 傳統(tǒng)離群檢測算法

為了解決局部離群點(diǎn)的問題,基于密度的離群檢測算法被陸續(xù)提出(例如LOF算法)。與距離度量不同的是,基于密度的離群檢測算法通過定義各種不同的局部離群度來檢測局部離群點(diǎn)。局部離群度往往能夠準(zhǔn)確地反映出數(shù)據(jù)點(diǎn)與其周圍點(diǎn)密度特性上的差異,進(jìn)而可以通過局部離群度的大小直觀地找到離群點(diǎn)。這種方法在面對局部離群點(diǎn)時,往往能夠取得更好的檢測效果。

近年來,隨著數(shù)據(jù)挖掘研究領(lǐng)域的不斷深入,針對不同的應(yīng)用領(lǐng)域,研究人員提出了大量的改進(jìn)算法。Kim等[6]利用k-d樹和近似k-最近鄰居方法提出了一種高效的離群檢測算法;Campello等[7]則提出了一種基于層次密度的數(shù)據(jù)挖掘算法,該算法提高了傳統(tǒng)的基于密度的聚類效果,并通過計(jì)算得到層次化的聚類結(jié)果進(jìn)行聚類、離群檢測和數(shù)據(jù)可視化等多項(xiàng)任務(wù)。茍和平等[8]利用DBSCAN(density-based spatial clustering of applications with noise)算法對樣本進(jìn)行去噪和裁剪提出了KNN(k-nearest neighbor)算法的改進(jìn)算法;周芳芳等[9]以體數(shù)據(jù)的標(biāo)量值與梯度模直方圖的密度分布為基礎(chǔ)對傳統(tǒng)算法進(jìn)行了改進(jìn);周國兵等[10]基于算法空間復(fù)雜度的考慮提出了Bit kmeans算法;王習(xí)特等[11]提出了BOD(BDSP-based outlier detection)分布式離群點(diǎn)檢測算法解決了傳統(tǒng)的集中式算法處理效率受限的問題;陸海青等[12]提出的圖像分割算法需根據(jù)圖像噪聲的強(qiáng)度適當(dāng)?shù)剡x取鄰域窗口大小,并根據(jù)鄰域窗口中各像素的灰度差異,利用指數(shù)函數(shù)進(jìn)一步控制鄰域像素的影響權(quán)重,實(shí)現(xiàn)像素灰度的自適應(yīng)加權(quán),從而提高像素灰度計(jì)算的準(zhǔn)確性;趙冠哲等[13]提出的異常檢測方法針對移動數(shù)據(jù)中歷史位置和好友圈信息進(jìn)行高效的檢測,并在檢測方法中探討了針對不同情況時鄰域參數(shù)的選擇策略;張美琴等[14]提出了一種基于加權(quán)聚類集成的標(biāo)簽傳播算法,該算法利用逆鄰居的思想完成了計(jì)算基聚類集,進(jìn)而利用基聚類集的加權(quán)相似性矩陣得到社區(qū)劃分結(jié)果。

上述算法在各自的應(yīng)用領(lǐng)域中均取得了令人滿意的效果,進(jìn)一步推動了相關(guān)技術(shù)的發(fā)展,卻也同時凸顯出了另一個亟待解決的問題——鄰域參數(shù)對算法效率的影響。大多數(shù)基于距離和基于密度的離群檢測算法的核心都架構(gòu)于k-最近鄰居思想,因此鄰域參數(shù)的選擇也就是k值的設(shè)置。k值較大會導(dǎo)致短路,使得算法在離群點(diǎn)檢測中錯誤地將部分局部離群點(diǎn)歸到正常點(diǎn)的范圍中,而k值較小則會導(dǎo)致數(shù)據(jù)簇的不完整,將邊緣點(diǎn)與稀疏點(diǎn)錯誤地歸為局部離群點(diǎn)。更為困難的是,選擇一個恰當(dāng)具有非普適性的k值,在一個數(shù)據(jù)集中合適的k值通常在其他數(shù)據(jù)集中都會成為一個不恰當(dāng)?shù)倪x擇。解決鄰域參數(shù)的選取問題出現(xiàn)了兩種思考的方向:探尋具有普適性的鄰域參數(shù)選擇方法,或降低鄰域參數(shù)的敏感性。

Ha等[15]利用不穩(wěn)定因子提出了一種新的對參數(shù)不敏感的離群檢測算法INS(instability factor)。INS改善了KNN算法中離群檢測算法對參數(shù)敏感的問題,使得離群檢測的準(zhǔn)確率能夠在較大的范圍內(nèi)不會隨著參數(shù)的改變而產(chǎn)生很大的變化,且可以檢測出數(shù)據(jù)集中的全局和局部離群點(diǎn)。但是INS算法對參數(shù)的不敏感性犧牲了一部分離群檢測的準(zhǔn)確率,即INS的離群檢測結(jié)果趨于穩(wěn)定時檢測準(zhǔn)確率往往低于鄰域參數(shù)選擇合理時的其他算法。而且INS算法很難同時檢測出局部離群點(diǎn)和全局離群點(diǎn),檢測局部離群點(diǎn)時需要調(diào)整不穩(wěn)定因子的設(shè)定。

通過以上分析可以得知,現(xiàn)有的離群檢測算法各自有各自的優(yōu)勢。但是,無論是基于距離的還是基于密度的算法都存在一個參數(shù)k值的設(shè)置問題,那就是如何選擇一個合適的鄰居個數(shù)k值。為了解決這一問題,本文選擇結(jié)合自然鄰居的思想提出適用于離群檢測的普適性鄰域參數(shù)選擇方法?;谧匀秽従有纬蛇^程無參的特性,本文提出了一種離群檢測算法,該算法能夠在已知離群點(diǎn)參數(shù)n的情況下無需鄰域參數(shù)k找到數(shù)據(jù)集中的離群點(diǎn)。最后,算法探討了完全無參數(shù)化的離群檢測算法,在挖掘出正確的離群點(diǎn)的同時去除鄰域參數(shù)k和離群點(diǎn)數(shù)量參數(shù)n。

2 基于自然鄰居思想的離群檢測算法

2.1 自然鄰居概述

自然鄰居思想是筆者及課題組成員提出的一種無尺度的概念,與傳統(tǒng)的KNN方法相比,該思想能夠在無需鄰域參數(shù)k的情況下構(gòu)建出合理的鄰居關(guān)系,為后續(xù)的數(shù)據(jù)挖掘方法提供分析基礎(chǔ)[16]。該思想包含以下幾個核心概念。

定義1 搜索穩(wěn)定狀態(tài)(search stable state)

定義2 自然鄰居(natural neighbor)

定義3 自然鄰居特征值(natural neighbor eigenvalue)

定義4 自然鄰居鄰域圖(natural neighborhood graph)

在定義 1~4 中,數(shù)據(jù)集 X={x1, x2, ···, xn},KNNr(xi)代表點(diǎn)xi的r鄰域,即前r個鄰居構(gòu)成的集合,λ是自然鄰居特征值,NN(xi)代表點(diǎn)xi的自然領(lǐng)域。自然鄰居概念的定義在提出時就對該概念的擴(kuò)展性進(jìn)行了展望分析,而本文正是在此基本概念基礎(chǔ)上,提出并構(gòu)造加權(quán)自然鄰居鄰域圖,并以此為基礎(chǔ)完成無參數(shù)的離群點(diǎn)的檢測算法。

2.2 基于加權(quán)自然鄰居鄰域圖的離群檢測算法

定義5 加權(quán)自然鄰居鄰域圖(weighted natural neighborhood graph)。加權(quán)自然鄰居鄰域圖反映了自然穩(wěn)定狀態(tài)時數(shù)據(jù)集中數(shù)據(jù)點(diǎn)之間的鄰居關(guān)系,每一條加權(quán)邊反映了對應(yīng)的兩個數(shù)據(jù)點(diǎn)首次互為鄰居關(guān)系時的最近鄰居搜索狀態(tài)。加權(quán)自然鄰居鄰域圖權(quán)值的形式化描述為

權(quán)值的取值范圍為 [1,λ]。

定義6 自然鄰居離群因子(natural neighbor outlier factor)。數(shù)據(jù)點(diǎn)p的自然鄰居離群因子f (p)滿足:

其中,集合Q ={q|e =(p,q)∈ E},即Q為數(shù)據(jù)點(diǎn)p的所有自然鄰居所構(gòu)成的數(shù)據(jù)子集。

在完善了加權(quán)自然鄰居鄰域圖和自然鄰居離群因子的定義后,本文提出基于加權(quán)自然鄰居鄰域圖的離群檢測算法,算法流程如圖1所示。

圖1 基于加權(quán)自然鄰居鄰域圖的離群檢測算法流程圖Fig. 1 Flowchart of the WNaNG outlier detection algorithm

算法1 基于加權(quán)自然鄰居領(lǐng)域圖的離群檢測

輸入 目標(biāo)數(shù)據(jù)集X,離群點(diǎn)總數(shù)n;

輸出 加權(quán)自然鄰居鄰域圖G,局部離群點(diǎn)個數(shù)nl,全局離群點(diǎn)。

1) 初始化k=0,并創(chuàng)建數(shù)據(jù)集X對應(yīng)的k-d樹T;

2) 令k=k+1,并利用k-d樹T找到數(shù)據(jù)集中每個點(diǎn)的k最近鄰居;

3) 分析當(dāng)前的鄰居關(guān)系,將互為k最近鄰居的兩點(diǎn)構(gòu)成一條邊,并記錄當(dāng)前的k作為該邊的權(quán)值;

4) 重復(fù)執(zhí)行步驟2)~3),直到數(shù)據(jù)集X中所有點(diǎn)都至少具有一個鄰居,或連續(xù)r次未增加新的邊,其中;

5) 將加權(quán)自然鄰居鄰域圖中沒有邊的點(diǎn)標(biāo)記為全局離群點(diǎn),并計(jì)算出剩余的局部離群點(diǎn)個數(shù)nl;

6) 根據(jù)當(dāng)前所有已知邊的信息構(gòu)造加權(quán)自然鄰居鄰域圖。

自然鄰居搜索算法通過自然鄰居搜索過程和自然鄰居鄰域圖的簡單分析,找到了全局離群點(diǎn),同時給出了剩余數(shù)據(jù)的加權(quán)自然鄰居鄰域圖。算法得到的加權(quán)自然鄰居鄰域圖將會被用于局部離群點(diǎn)挖掘過程,找到數(shù)據(jù)集中最終的局部離群點(diǎn)。

算法2 局部離群點(diǎn)挖掘算法

輸入 加權(quán)自然鄰居鄰域圖G=(V, E),局部離群點(diǎn)個數(shù)nl;

輸出 局部離群點(diǎn)。

1) 對鄰域圖進(jìn)行遍歷,找到每個點(diǎn)的所有加權(quán)邊;

2) 根據(jù)定義6計(jì)算所有點(diǎn)的自然離群因子f;

3) 對所有點(diǎn)的自然離群因子進(jìn)行降序排序,前nl個點(diǎn)即為局部離群點(diǎn)。

局部離群點(diǎn)挖掘算法首先計(jì)算加權(quán)自然鄰居鄰域圖中點(diǎn)的自然鄰居離群因子,其次依照離群因子的大小得到局部離群點(diǎn)。

2.3 自然鄰居離群因子離散圖分析

在上述算法的局部離群點(diǎn)挖掘算法中,剩余離群點(diǎn)依然需要人為設(shè)置,如算法中則是用離群點(diǎn)數(shù)量參數(shù)n減去已經(jīng)找到的全局離群點(diǎn)個數(shù)。為了進(jìn)一步完成無參數(shù)的離群點(diǎn)檢測算法,本文嘗試通過對自然鄰居離群因子的離散圖進(jìn)行分析,去除離群點(diǎn)數(shù)量參數(shù)n,使得本文提出的離群檢測算法具有更強(qiáng)的自適應(yīng)性。因此,本文有針對性地構(gòu)造了一個具有多個局部離群點(diǎn)的人工數(shù)據(jù)集,并針對其局部離群點(diǎn)的情況和自然鄰居離群因子的值進(jìn)行分析。

在圖2中可以看到,數(shù)據(jù)點(diǎn)1、2、3、4和162、163、164、165為局部離群點(diǎn)。從圖3中可以看出,圖2中提到的離群點(diǎn)所對應(yīng)的局部離群因子均遠(yuǎn)遠(yuǎn)高于普通數(shù)據(jù)點(diǎn)的局部離群因子,因此如果以自然鄰居離群因子離散圖作為輔助決策,可以直觀地通過其數(shù)據(jù)分布確定自然鄰居離群因子的閾值,并以此閾值作為局部離群點(diǎn)的判定標(biāo)準(zhǔn),達(dá)到去除離群點(diǎn)數(shù)量參數(shù)n的目的。這種結(jié)合圖形化展示的離群點(diǎn)檢測方法使得離群點(diǎn)的度量和檢測能夠進(jìn)行更為直觀地展示。

圖2 自然鄰居鄰域圖和局部離群點(diǎn)示意Fig. 2 Natural neighbor graph and local outliers

圖3 數(shù)據(jù)集中各個數(shù)據(jù)點(diǎn)對應(yīng)的自然鄰居離群因子Fig. 3 Natural neighbor outlier factor of each data point

另外,若希望離群檢測擺脫人為的參數(shù)設(shè)置和圖像化輔助決策,在此選擇對自然鄰居離群因子進(jìn)行降序排序,離群度的分布形態(tài)與長尾分布具有極高的相似度,因此可以嘗試?yán)瞄L尾分布的相關(guān)理論進(jìn)行自然鄰居離群因子的閾值確定,實(shí)現(xiàn)無需人為干涉、無需鄰域參數(shù)k和離群點(diǎn)數(shù)量參數(shù)n的自適應(yīng)離群檢測算法。

2.4 算法復(fù)雜度分析

首先,自然鄰居搜索算法在自然鄰居查找和自然穩(wěn)定狀態(tài)的獲取階段時間復(fù)雜度為。其次,全局集群點(diǎn)和離群簇的挖掘均可以在鄰居搜索的過程中完成,且并不會在數(shù)量級級別增加算法的時間復(fù)雜度。因此當(dāng)前階段的時間復(fù)雜度為。

在算法的第二階段,局部離群點(diǎn)挖掘算法的時間復(fù)雜度要低于上一階段。首先,自然鄰居鄰域圖中的任意點(diǎn)最多具有λ條邊,最少具有一條邊。因此,自然鄰居離群因子階段的時間復(fù)雜度為,其中λ為一個較小的整數(shù),因此該階段實(shí)際復(fù)雜度為。之后的聚類分析具體操作時只需要對上一階段中的數(shù)據(jù)簇結(jié)果進(jìn)行簡單的修改,而該修改操作的時間復(fù)雜度為。

3 實(shí)驗(yàn)結(jié)果

3.1 人工數(shù)據(jù)集實(shí)驗(yàn)

人工數(shù)據(jù)集的實(shí)驗(yàn)分為兩部分。1)著重于展示本算法自適應(yīng)性的優(yōu)勢,即與其他算法選擇多個參數(shù)時能夠獲得的最好檢測結(jié)果相比,本算法能夠獲得與之相似甚至于更好的結(jié)果,且無需選擇鄰域參數(shù)。在這一部分中,同一數(shù)據(jù)集中多個算法均選取相同的離群點(diǎn)數(shù)量n。2)分討論算法在無需離群點(diǎn)數(shù)量參數(shù)n的情況下利用自然鄰居離群因子查找局部離群點(diǎn)的算法結(jié)果。

首先進(jìn)行基于鄰域參數(shù)k的實(shí)驗(yàn)展示。本實(shí)驗(yàn)用到的人工數(shù)據(jù)集如圖4所示。

圖4中的6個數(shù)據(jù)集均包含了多個肉眼可見的離群點(diǎn),其中既有局部離群點(diǎn),又有全局離群點(diǎn),且這6個數(shù)據(jù)集具有不同的數(shù)據(jù)分布特性,因而能更準(zhǔn)確地反映出鄰域參數(shù)對算法的影響,以及本算法的自適應(yīng)性在面對數(shù)據(jù)集的多樣性時的實(shí)際表現(xiàn)。

本文將基于加權(quán)自然鄰居鄰域圖的數(shù)據(jù)挖掘算法與4種離群檢測算法相對比,檢驗(yàn)本算法與當(dāng)前離群檢測算法之間的性能差異,被選取的對比算法為KNN、LOF、INFLO和INS。

圖5用曲線圖展示了5種不同的離群檢測算法在6個數(shù)據(jù)集中的檢測精確率。為了更好地反映準(zhǔn)確率隨著鄰域參數(shù)取值的變化而上下波動的詳細(xì)情況,這里將x軸設(shè)定為鄰域參數(shù)k的不同取值,y軸則是各個算法在選取每一個k值時對應(yīng)的離群檢測準(zhǔn)確率。本算法克服了傳統(tǒng)的鄰域選擇問題,即無需在算法中設(shè)置參數(shù)k,則在圖5的所有子圖中,WNaNG算法的準(zhǔn)確率是確定的,即對固定的數(shù)據(jù)集,WNaNG算法只有一個確定的離群檢測結(jié)果。為了算法對比效果的展示,WNaNG算法的準(zhǔn)確率采用直線進(jìn)行標(biāo)示。

圖4 包含離群點(diǎn)的6個人工數(shù)據(jù)集Fig. 4 Six synthetic data sets of the outliers

圖5 5種離群檢測算法在取不同k值時離群檢測準(zhǔn)確率對比Fig. 5 Outlier detection accuracies of five detection methods over a range of k values

縱觀所有子圖,WNaNG算法的普適性高于其余算法,能夠在6個數(shù)據(jù)集中均取得令人滿意的結(jié)果。若對每一個算法在各個數(shù)據(jù)集中均選擇一個最優(yōu)的參數(shù)k與本算法相比較,在數(shù)據(jù)集1中其余5種算法的最優(yōu)算法略高于本算法,而在其余幾個數(shù)據(jù)集中,其最優(yōu)值基本僅能與本算法取得相似的檢測效果,大部分的鄰域參數(shù)值所對應(yīng)的檢測效果均與本算法有一定的差距。

從算法對鄰域參數(shù)的適應(yīng)性上看,本算法完全擺脫了鄰域參數(shù)的影響,并取得了令人滿意的結(jié)果;INS算法對鄰域參數(shù)的敏感度較低,因此在各個數(shù)據(jù)集中,其檢測結(jié)果不易隨著鄰域參數(shù)的變化產(chǎn)生劇烈波動;其余算法則對鄰域參數(shù)較為敏感,特別是當(dāng)數(shù)據(jù)集分布不規(guī)則時,如最后兩個數(shù)據(jù)集中,鄰域參數(shù)的選取會嚴(yán)重影響其算法結(jié)果。

產(chǎn)生上述情況的原因:為了降低鄰域參數(shù)對算法的影響,增強(qiáng)算法的適應(yīng)性,往往會在某些情況犧牲一部分離群檢測準(zhǔn)確率,如INS算法。而本文提出的WNaNG算法合理地利用了自適應(yīng)的鄰居特性,因而在保證了檢測準(zhǔn)確率的情況下移除了鄰域參數(shù)的影響。本算法在與其余算法進(jìn)行比較時檢測結(jié)果呈現(xiàn)一條直線,并不是代表算法的檢測結(jié)果不會隨著k值的變化而產(chǎn)生變化,而是算法無需人為設(shè)置參數(shù)k。因此可以得到結(jié)論:WNaNG算法不僅解決了鄰域參數(shù)的選取問題,更能在具有不同特性的數(shù)據(jù)集中取得穩(wěn)定且準(zhǔn)確的離群檢測結(jié)果。本文將進(jìn)一步討論WN-aNG算法利用自然鄰居離群因子查找局部離群點(diǎn)的實(shí)驗(yàn)結(jié)果。

圖6展示了5個不同分布特點(diǎn)的數(shù)據(jù)集利用自然鄰居離群因子進(jìn)行局部離群點(diǎn)檢測的檢測結(jié)果。從實(shí)驗(yàn)結(jié)果中可以看到,在前兩個數(shù)據(jù)集中,自然鄰居離群因子的分布相對較為均勻,對應(yīng)的數(shù)據(jù)集中局部離群點(diǎn)的特征也較弱;而在后幾個數(shù)據(jù)集中,自然鄰居離群因子的分布呈現(xiàn)較大的差異,能夠通過分布圖明顯地劃分出一個或者多個自然鄰居離群因子突變界限,而這種情況也與實(shí)際數(shù)據(jù)分布相吻合,其數(shù)據(jù)集中的局部離群點(diǎn)在分布上也呈現(xiàn)出多層級的特點(diǎn),即不同范圍的離群點(diǎn)其局部離群特征也具有較大的差異性。

圖6 局部離群點(diǎn)與自然鄰居離群因子離散圖Fig. 6 Local outliers and NaNOF scatter

3.2 真實(shí)數(shù)據(jù)集實(shí)驗(yàn)

真實(shí)數(shù)據(jù)集中本文采用的對比算法為KNN、LOF、INFLO和INS算法,算法對應(yīng)的兩個數(shù)據(jù)集分別為UCI 網(wǎng)站的CANCER和IRIS,采用的評價指標(biāo)是離群檢測的ROC曲線(receiver operating characteristic curve),其橫、縱坐標(biāo)為離群點(diǎn)檢測率和離群點(diǎn)數(shù)目,通過積分面積驗(yàn)證數(shù)據(jù)集在對應(yīng)的k值選擇中離群檢測的效率。在兩個人工數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果中,基于加權(quán)自然鄰居鄰域圖的數(shù)據(jù)挖掘算法由于不需要鄰域參數(shù),因此圖中所展示的k為算法自適應(yīng)得出的對應(yīng)數(shù)據(jù)集的自然鄰居特征值,其余算法則是其對應(yīng)的鄰域參數(shù)k的取值。

圖7中的實(shí)驗(yàn)結(jié)果分為頂部和底部兩組,頂部的實(shí)驗(yàn)結(jié)果為算法在對應(yīng)的鄰域參數(shù)k值的范圍中選取得到的最差實(shí)驗(yàn)結(jié)果,而底部為該范圍中最好的實(shí)驗(yàn)結(jié)果。從當(dāng)前數(shù)據(jù)集可以看到,以離群點(diǎn)檢測命中率作為檢測結(jié)果時,INS和本算法的表現(xiàn)相對較差。這主要是由于,在CANCER數(shù)據(jù)集中,部分離群點(diǎn)被算法歸為了簇,繼而難以被檢測出來,而其他3個算法能夠更快地隨著參數(shù)n的增加而找到那部分離群點(diǎn)。

圖7 CANCER數(shù)據(jù)集的ROC曲線下面積Fig. 7 Area under the ROC curves of CANCER

圖8 的布局和圖7相同,也是由最差實(shí)驗(yàn)結(jié)果和最佳實(shí)驗(yàn)結(jié)果組成。在IRIS數(shù)據(jù)集中,因?yàn)殡x群點(diǎn)中離群簇的情況比CANCER更少,因此WNaNG算法的結(jié)果有了明顯的好轉(zhuǎn)。特別是當(dāng)n=50時,僅本算法就能夠找到所有的離群點(diǎn)。

圖8 IRIS數(shù)據(jù)集的ROC曲線下面積Fig. 8 Area under the ROC curves of IRIS

總結(jié)上述兩個人工數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn):WNaNG算法的離群檢測結(jié)果不需要鄰域參數(shù),因此不存在鄰域選擇影響算法效率的問題;算法在兩個數(shù)據(jù)集中均表現(xiàn)較為穩(wěn)定,對不同的數(shù)據(jù)集均能獲得較好的效果。INS算法需要鄰域參數(shù),雖然其對參數(shù)的容忍度較高,但從本實(shí)驗(yàn)中依然可以看到參數(shù)取值的最差情況和最好情況所對應(yīng)的檢測結(jié)果差距較大。其余3個算法在不同數(shù)據(jù)集、不同參數(shù)的情況下表現(xiàn)出了較大的波動,且針對不同數(shù)據(jù)集參數(shù)的最優(yōu)取值之間沒有規(guī)律,需要根據(jù)具體問題獨(dú)立嘗試。

4 結(jié)束語

針對離群檢測中鄰域參數(shù)、離群點(diǎn)總數(shù)參數(shù)以及局部離群點(diǎn)等問題,本文結(jié)合自然鄰居思想提出了一種自適應(yīng)的離群檢測算法WN-aNG。該算法在不同的數(shù)據(jù)集中運(yùn)行時無需人為設(shè)置鄰域參數(shù),并能夠根據(jù)數(shù)據(jù)集自身的分布特征獲得令人滿意的檢測結(jié)果。另外,WN-aNG能夠更為準(zhǔn)確地挖掘出局部離群點(diǎn)和全局離群點(diǎn)并予以區(qū)分,這也為離群點(diǎn)解釋、釋義空間的構(gòu)建等數(shù)據(jù)挖掘的后續(xù)步驟提供了強(qiáng)有力的支持。

猜你喜歡
離群鄰域局部
一種基于鄰域粒度熵的離群點(diǎn)檢測算法
基于混合變鄰域的自動化滴灌輪灌分組算法
爨體蘭亭集序(局部)
含例鄰域邏輯的薩奎斯特對應(yīng)理論
超精密車削出現(xiàn)局部振紋的診斷及消除
尖銳特征曲面點(diǎn)云模型各向異性鄰域搜索
一種相似度剪枝的離群點(diǎn)檢測算法
從數(shù)學(xué)的角度初步看離群點(diǎn)檢測算法
丁學(xué)軍作品
候鳥