一種個(gè)性化k近鄰的離群點(diǎn)檢測算法

樊瑞宣，姜高霞，王文劍

1(山西大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，太原 030006)2(山西大學(xué) 計(jì)算智能與中文信息處理教育部重點(diǎn)實(shí)驗(yàn)室，太原 030006)

1 引 言

在實(shí)際應(yīng)用中，由于數(shù)據(jù)來源和構(gòu)成的多樣性，使得存在這樣一類數(shù)據(jù)點(diǎn)，它們與大部分?jǐn)?shù)據(jù)的一般行為或者模型不一致，這樣的數(shù)據(jù)對(duì)象稱為離群點(diǎn).對(duì)于離群點(diǎn)的定義，目前最廣為人接受的是Hawkins[1]給出的描述：“離群點(diǎn)是在數(shù)據(jù)集中偏離大部分?jǐn)?shù)據(jù)的數(shù)據(jù)，使人懷疑這些數(shù)據(jù)的偏離并非由隨機(jī)因數(shù)產(chǎn)生，而是產(chǎn)生于完全不同的機(jī)制”.離群點(diǎn)檢測是數(shù)據(jù)挖掘的一個(gè)重要分支，被廣泛應(yīng)用在各種領(lǐng)域，如欺詐檢測[2，3]、圖像檢測[4，5]、醫(yī)學(xué)分析[6-8]、信號(hào)異常檢測[9]等.離群點(diǎn)可能包含潛在的信息，而這些信息對(duì)于識(shí)別系統(tǒng)中的異常行為具有重要的作用.

離群點(diǎn)檢測的目的是要找出數(shù)據(jù)集中與其他數(shù)據(jù)相比顯著異常的數(shù)據(jù)對(duì)象，然后幫助我們更好地理解和處理數(shù)據(jù).現(xiàn)有的離群點(diǎn)檢測算法大致可以分為基于統(tǒng)計(jì)、基于距離、基于密度及基于聚類等四類方法.

基于統(tǒng)計(jì)(又稱為基于模型)的方法，其思想來源于統(tǒng)計(jì)學(xué).先對(duì)數(shù)據(jù)集的分布作出假設(shè)，然后建立數(shù)據(jù)集的統(tǒng)計(jì)模型，根據(jù)模型采用不一致檢驗(yàn)識(shí)別離群點(diǎn)[10].當(dāng)數(shù)據(jù)的分布符合前提假設(shè)時(shí)，效果是非常好的.但是，對(duì)于實(shí)際的數(shù)據(jù)集來講，我們并不知道它的分布是怎樣的，而且一般來講，也很難用標(biāo)準(zhǔn)的數(shù)據(jù)模型去擬合它，所以這類方法的離群點(diǎn)檢測效果無法保證，因此，這類方法應(yīng)用不多.

基于距離的方法是該領(lǐng)域內(nèi)應(yīng)用最多的算法，在不同的場景中，選取合適的距離度量方式(歐氏距離、馬氏距離等)，作為離群的判斷準(zhǔn)則，其中使用最為廣泛的算法是k近鄰(k-Nearest Neighbor，KNN)[11]方法.在此基礎(chǔ)上，反向k近鄰(Reversek-Nearest Neighbor，RKNN)[12]的方法被提出.目前有很多離群點(diǎn)檢測算法都是基于KNN或者RKNN，如文獻(xiàn)[13]提出的LDOF(Local Distance-based Outlier Factor)算法，該算法把點(diǎn)的k近鄰平均距離與該點(diǎn)的k近鄰內(nèi)部平均距離之比作為該點(diǎn)的局部距離離群因子，以此判別數(shù)據(jù)對(duì)象是否為離群點(diǎn).基于近鄰的離群點(diǎn)檢測算法與統(tǒng)計(jì)方法相比，計(jì)算比較簡單，減少了在統(tǒng)計(jì)學(xué)方法中需要進(jìn)行的學(xué)習(xí)模型和選擇不一致檢驗(yàn)相關(guān)的過多的計(jì)算，而且此類算法都是依據(jù)周圍有限的近鄰樣本而不需要與整個(gè)的數(shù)據(jù)點(diǎn)進(jìn)行判斷，所以近鄰方法被廣泛運(yùn)用在各種算法中.

基于密度的方法主要針對(duì)局部離群點(diǎn)檢測，由于數(shù)據(jù)集的分布并非總是均勻的，所以會(huì)產(chǎn)生局部離群點(diǎn).最具代表性的算法是Breunig等提出的局部離群因子(Local Outlier Factor，LOF)算法[14].該算法把點(diǎn)的密度與其鄰域的平均密度比值作為局部離群因子，離群因子的值越大，代表該點(diǎn)的離群程度越高.這類方法假定非離群點(diǎn)對(duì)象周圍的密度與其鄰域周圍的密度相似；而離群點(diǎn)對(duì)象周圍的密度顯著不同于其鄰域周圍的密度.在LOF算法的基礎(chǔ)上，Jin等人又提出了INFLO(INFLuenced Outlierness)算法[15]，該算法在計(jì)算離群因子時(shí)，不但考慮了k近鄰，還同時(shí)考慮了反向k近鄰對(duì)于該數(shù)據(jù)點(diǎn)的影響，此方法計(jì)算出的離群因子比LOF包含了更多的信息.

基于聚類的方法是通過觀察數(shù)據(jù)對(duì)象和簇之間的關(guān)系，來尋找離群點(diǎn).直觀地，離群點(diǎn)是一個(gè)對(duì)象，它屬于規(guī)模小的偏遠(yuǎn)簇，或者不屬于任何一個(gè)簇.基于聚類的方法對(duì)無標(biāo)簽數(shù)據(jù)的離群點(diǎn)檢測有效，另外，簇可以看做數(shù)據(jù)的概括，在得到簇以后，只需把檢測對(duì)象和簇進(jìn)行比較，就可以確定該數(shù)據(jù)對(duì)象是否是離群點(diǎn).這個(gè)過程通常比較快，因?yàn)榇氐膫€(gè)數(shù)通常遠(yuǎn)小于數(shù)據(jù)點(diǎn)的總數(shù).目前已經(jīng)出現(xiàn)了很多代表性算法，如DBSCAN[16]，CLARANS[17]，CHAMELEON[18]，BIRCH[19]和CURE[20]，但是這類算法在聚類過程中存在較多參數(shù)，而離群檢測非常依賴于聚類結(jié)果，只有在聚類結(jié)果好的情況下，才能保證離群點(diǎn)檢測效果.

在基于距離和基于密度的算法中，經(jīng)常需要使用k近鄰概念，因此，近鄰參數(shù)k的選取無法避免，而k值的大小將會(huì)直接影響到算法的實(shí)際性能和檢測效果.一般情況下，近鄰參數(shù)k是人為設(shè)定的，為了設(shè)置合理的參數(shù)值，需要對(duì)數(shù)據(jù)集有一定的了解，并具有一定的先驗(yàn)知識(shí).但是在實(shí)際操作中，這些先驗(yàn)知識(shí)往往很難得到.即使是對(duì)不同的數(shù)據(jù)集采用相同的算法，由于不同的數(shù)據(jù)集具有不同的特征，所以在設(shè)定k值時(shí)也沒有太大的借鑒意義.

針對(duì)近鄰參數(shù)k的敏感問題，基于不穩(wěn)定因子的健壯離群點(diǎn)檢測算法(Robust Outlier Detection Using the Instability Factor，INS)[21]被提出.INS算法首先是要找到每個(gè)點(diǎn)的鄰居，確定鄰域重心，然后不斷擴(kuò)大被檢測點(diǎn)的鄰域，根據(jù)鄰域重心的位置變化確定每個(gè)點(diǎn)的不穩(wěn)定因子，以此判斷該點(diǎn)的離群程度.INS算法對(duì)近鄰參數(shù)具有魯棒性，但是該算法容易將處于稀疏區(qū)域與稠密區(qū)域交界處的正常點(diǎn)誤判為離群點(diǎn).文獻(xiàn)[22]提出了自然鄰居(Natural Neighbor，NaN)算法，通過這個(gè)算法可以計(jì)算得出自然鄰居特征值(Natural Neighbor Eigenvalue，NaNE)，然后將NaNE作為數(shù)據(jù)集中所有點(diǎn)的近鄰參數(shù)，為k的自適應(yīng)選擇提供了新的思路.NaN算法雖然給出了一種不需要人為設(shè)定近鄰參數(shù)k的方式，但依然對(duì)所有的數(shù)據(jù)點(diǎn)采用相同的k值，會(huì)讓原本處于稀疏區(qū)域的數(shù)據(jù)點(diǎn)，由于近鄰參數(shù)過大而增加計(jì)算時(shí)間.

本文提出一種個(gè)性化k近鄰(PKNN)的離群點(diǎn)檢測算法，數(shù)據(jù)集中的每個(gè)數(shù)據(jù)點(diǎn)可以采用不同的近鄰數(shù)，而這個(gè)近鄰數(shù)是通過算法自動(dòng)確定的，不但可以避免人為設(shè)定參數(shù)問題，而且可以反應(yīng)出數(shù)據(jù)集本身的分布特征，同時(shí)保留KNN的優(yōu)勢(shì).

2 個(gè)性化k近鄰的離群點(diǎn)檢測方法

在現(xiàn)有的基于近鄰的離群點(diǎn)檢測算法中，都是由用戶根據(jù)經(jīng)驗(yàn)為數(shù)據(jù)集中的所有點(diǎn)統(tǒng)一設(shè)定一個(gè)k值，k值是否合適一般要經(jīng)過實(shí)驗(yàn)驗(yàn)證.另外，由于數(shù)據(jù)分布不同，對(duì)于一個(gè)數(shù)據(jù)來說，采用相同的k值，可能會(huì)把離這個(gè)數(shù)據(jù)較遠(yuǎn)的點(diǎn)作為k近鄰考慮，實(shí)際上對(duì)該點(diǎn)影響較小；也有可能會(huì)把離這個(gè)數(shù)據(jù)較近的近鄰沒有作為k近鄰考慮，實(shí)際上對(duì)該點(diǎn)影響較大，所以檢測效果不能保證.圖1是傳統(tǒng)KNN與PKNN中近鄰分布示意圖，p和q分別表示兩個(gè)三角形點(diǎn).對(duì)于傳統(tǒng)KNN方法(如圖1(a)所示)，假設(shè)采取固定近鄰數(shù)k=5，即p和q的近鄰數(shù)Num(p)=Num(q)=5，兩個(gè)圓圈分別表示p和q的5近鄰.對(duì)于q來說，k取5符合q的分布特征，但是對(duì)點(diǎn)p本身的分布而言，k取5并不適合，會(huì)因?yàn)榘演^遠(yuǎn)的鄰居考慮進(jìn)來，降低計(jì)算效率，而且可能會(huì)干擾檢測結(jié)果.而PKNN對(duì)每個(gè)數(shù)據(jù)點(diǎn)可以采用不同的近鄰數(shù).圖1(b)中，點(diǎn)p和點(diǎn)q的近鄰數(shù)并不相同，Num(p)=2，Num(q)=5.從分布來看，這個(gè)近鄰參數(shù)更能體現(xiàn)出數(shù)據(jù)本身的特征：處于稠密區(qū)域的點(diǎn)具有更多的鄰居，而處于稀疏區(qū)域的點(diǎn)具有更少的鄰居.

圖1 KNN與PKNN近鄰分布示意圖Fig.1 Distribution of nearest neighbors in KNN and PKNN

2.1 確定個(gè)性化近鄰參數(shù)

在PKNN算法中，數(shù)據(jù)集中每個(gè)點(diǎn)都有一個(gè)自己專屬的近鄰個(gè)數(shù)，且這個(gè)近鄰個(gè)數(shù)是由算法自動(dòng)確定，不需要人為指定.

(1)

令Sk(xi)表示xi的k近鄰集合，PK(xi)表示xi的個(gè)性化近鄰集合，即

PK(xi)={xj│xj∈Sk(xi)且xi∈Sk(xj) }

(2)

在個(gè)性化近鄰參數(shù)計(jì)算結(jié)束后，會(huì)存在極少數(shù)點(diǎn)的近鄰參數(shù)為0，這些點(diǎn)一般是孤立點(diǎn)，因此直接將其作為離群點(diǎn).

本文確定近鄰參數(shù)的方法與自然鄰居(NaN)方法過程相同，但輸出結(jié)果不同.NaN算法在迭代結(jié)束時(shí)輸出最大k值，并且將它作為所有點(diǎn)的近鄰參數(shù)，而PKNN則在迭代計(jì)算近鄰過程中，記錄并輸出每個(gè)點(diǎn)的個(gè)性化k值.

2.2 計(jì)算離群度

得到每個(gè)點(diǎn)的個(gè)性化近鄰參數(shù)以后，就可以判斷每個(gè)點(diǎn)與其他點(diǎn)的不一致性，這里用離群度來度量這種不一致性.令D(xi)表示xi的原始k近鄰平均距離，即

(3)

傳統(tǒng)KNN采用原始k近鄰平均距離D(xi)作為離群判別準(zhǔn)則，D(xi)越大，xi的離群程度越高.在PKNN算法中，若采用D(xi)作為離群判別準(zhǔn)則，由于每個(gè)點(diǎn)的近鄰個(gè)數(shù)不同，有可能會(huì)導(dǎo)致稀疏區(qū)域的點(diǎn)的近鄰平均距離小于稠密區(qū)域的點(diǎn)的近鄰平均距離，即稠密區(qū)域的點(diǎn)容易被判別為離群點(diǎn).圖2是一個(gè)簡單的例子，圖中p和q分別表示兩個(gè)三角形點(diǎn)，Num(p)=1，Num(q)=3，圓圈分別表示p和q的近鄰范圍，圖中數(shù)值表示每個(gè)點(diǎn)的近鄰距離.由圖2可以看出：D(p)=1，D(q)=1.5，故D(p)

(4)

圖2 近鄰平均距離示意圖Fig.2 Mean distance of nearest neighbors

對(duì)于圖2中的例子，使用修正后的離群準(zhǔn)則，可得出D′(p)>D′(q)，表明p的離群程度更大，因此，與數(shù)據(jù)的實(shí)際分布相符.PKNN算法中，Num(xi)=0的點(diǎn)在第一階段已被判別為離群點(diǎn)，所以不會(huì)出現(xiàn)D′(xi)不可計(jì)算的情況.

2.3 PKNN算法

PKNN算法的主要步驟總結(jié)如下：

算法1.PKNN算法

輸出：Top-n離群點(diǎn)

Step1.初始化搜索輪數(shù)k=1；?xi∈X，PK(xi)=?，Num(xi)=0.

Step2.?xi∈X，重復(fù)執(zhí)行以下步驟：

Step 2.2.計(jì)算cnt，并使用變量rep保存cnt保持不變的次數(shù).

Step3.得到離群點(diǎn)集合M={xi│Num(xi)=0，i=1，2，…，n}，若‖M‖≥Top-n，則順序取M中前Top-n個(gè)點(diǎn)作為離群點(diǎn)，算法結(jié)束，否則進(jìn)行下一步驟.

Step4.?xi∈X-M，計(jì)算離群度D′(xi).

Step5.選取D′(xi)中值最大的Top-n-‖M‖個(gè)數(shù)據(jù)點(diǎn)，并與M中的點(diǎn)一起作為Top-n離群點(diǎn).

Step6.算法結(jié)束.

本算法主要分為確定個(gè)性化近鄰個(gè)數(shù)和計(jì)算離群度兩個(gè)階段.其中，Step 2的循環(huán)部分是自適應(yīng)確定每個(gè)點(diǎn)的近鄰數(shù)的過程，Step 3是在近鄰數(shù)為0的點(diǎn)中選取一定數(shù)量的點(diǎn)作為離群點(diǎn)，Step 4和Step 5是對(duì)其余點(diǎn)計(jì)算離群度，然后確定離群點(diǎn).第一階段的時(shí)間復(fù)雜度為O(n2)，第二階段的時(shí)間復(fù)雜度為O(n)，因此，本算法的時(shí)間復(fù)雜度為O(n2).

2.4 PKNN算法示例

為了進(jìn)一步說明PKNN算法的計(jì)算過程，本節(jié)給出一個(gè)示例.圖3是含有16個(gè)樣本的原始分布，其中編號(hào)為8和16的是離群點(diǎn)，樣本信息及實(shí)驗(yàn)結(jié)果如表1所示.

圖3 示例數(shù)據(jù)分布Fig.3 Distribution of samples

方法首先確定每個(gè)樣本的個(gè)性化近鄰數(shù).在本示例中，根據(jù)算法1可得實(shí)驗(yàn)在第6輪搜索結(jié)束后，即可滿足終止條件，循環(huán)停止，選取編號(hào)為3、8、16的樣本來說明自適應(yīng)確定近鄰數(shù)以及計(jì)算離群度的過程.

1)對(duì)于樣本3，根據(jù)公式(2)，尋找個(gè)性化近鄰的迭代過程如下：

k=1時(shí)：PK1(3)={5}，Num1(3)=1.

k=2時(shí)：PK2(3)={6}，Num2(3)=1.

k=3時(shí)：PK3(3)={1}，Num3(3)=1.

k=4時(shí)：PK4(3)=?，Num4(3)=0.

k=5時(shí)：PK5(3)={2，7}，Num5(3)=2.

k=6時(shí)：PK6(3)={4}，Num6(3)=1.

迭代結(jié)束，可得：PK(3)={5，6，1，2，7，4}，Num(3)=6，根據(jù)公式(4)計(jì)算樣本3的離群度：D′(3)=2.41.

2)對(duì)于樣本8，根據(jù)公式(2)，尋找個(gè)性化近鄰的迭代過程如下：

k=1時(shí)：PK1(8)=?，Num1(8)=0.

k=2時(shí)：PK2(8)=?，Num2(8)=0.

k=3時(shí)：PK3(8)=?，Num3(8)=0.

k=4時(shí)：PK4(8)={9}，Num4(8)=1.

k=5時(shí)：PK5(8)=?，Num5(8)=0.

k=6時(shí)：PK6(8)={10}，Num6(8)=1.

迭代結(jié)束，可得：PK(8)={9，10}，Num(8)=2，根據(jù)公式(4)計(jì)算樣本8的離群度：D′(8)=3.65.

3)對(duì)于樣本16，根據(jù)公式(2)，尋找個(gè)性化近鄰的迭代過程如下：

k=1時(shí)：PK1(16)=?，Num1(16)=0.

k=2時(shí)：PK2(16)=?，Num2(16)=0.

k=3時(shí)：PK3(16)=?，Num3(16)=0.

k=4時(shí)：PK4(16)=?，Num4(16)=0.

k=5時(shí)：PK5(16)=?，Num5(16)=0.

k=6時(shí)：PK6(16)=?，Num6(16)=0.

迭代結(jié)束，可得：PK(16)=?，Num(16)=0，由于樣本16的個(gè)性化近鄰數(shù)為0，直接被作為離群點(diǎn).

表1 示例數(shù)據(jù)信息及其實(shí)驗(yàn)結(jié)果Table 1 Samples and experimental results

在本例中，離群點(diǎn)個(gè)數(shù)為2.由表1可知，個(gè)性化近鄰數(shù)為0的只有樣本16，已經(jīng)被作為離群點(diǎn).計(jì)算并比較其他15個(gè)樣本的離群度，可得樣本8的離群度最大，因此樣本8也是離群點(diǎn).PKNN算法最終得到的離群點(diǎn)是樣本16和樣本8，與數(shù)據(jù)集中的真實(shí)離群點(diǎn)保持一致.

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

3.1 實(shí)驗(yàn)設(shè)計(jì)

為了驗(yàn)證所提出的算法的有效性，本文在人工數(shù)據(jù)集上進(jìn)行了仿真實(shí)驗(yàn)，數(shù)據(jù)集的說明如表2所示.

8組數(shù)據(jù)集的分布如圖4所示，其中圓形點(diǎn)代表正常數(shù)據(jù)點(diǎn)，三角形點(diǎn)是離群點(diǎn).

表2 實(shí)驗(yàn)數(shù)據(jù)集Table 2 Experimental data sets

PKNN與NaN算法的近鄰參數(shù)k均為自動(dòng)確定，實(shí)驗(yàn)首先將PKNN算法得到的個(gè)性化近鄰參數(shù)與NaN算法的NaNE進(jìn)行比較.然后選取五種代表性離群點(diǎn)檢測算法(KNN、LOF、INFLO、LDOF、INS)與PKNN進(jìn)行離群點(diǎn)檢測效果對(duì)比.評(píng)價(jià)指標(biāo)采用離群點(diǎn)檢測準(zhǔn)確率，即：

Acc=(a/b)×100%

(5)

其中，a是檢測出的真實(shí)離群點(diǎn)的數(shù)量，b是離群點(diǎn)的數(shù)量.

圖4 數(shù)據(jù)集分布Fig.4 Distribution of data set

3.2 實(shí)驗(yàn)結(jié)果與分析

3.2.1 近鄰參數(shù)k的比較

實(shí)驗(yàn)首先確定不同點(diǎn)的個(gè)性化k值.PKNN算法在8個(gè)數(shù)據(jù)集上得出的k值分布如圖5所示，其中，橫軸表示k值大小，縱軸表示在近鄰個(gè)數(shù)等于k值時(shí)對(duì)應(yīng)的數(shù)據(jù)點(diǎn)個(gè)數(shù)占整個(gè)數(shù)據(jù)集的比例.當(dāng)k取最大值時(shí)，即為NaNE.

從圖5可以看出，數(shù)據(jù)點(diǎn)的k值主要分布在后半部分，且隨著k值的增大，近鄰為k的數(shù)據(jù)點(diǎn)所占的比例呈上升趨勢(shì).說明大部分?jǐn)?shù)據(jù)點(diǎn)都分布在稠密區(qū)域，且這些點(diǎn)的近鄰個(gè)數(shù)在迭代過程中不斷增加，與本文所使用的數(shù)據(jù)集的分布一致.PKNN在8個(gè)數(shù)據(jù)集上取NaNE的點(diǎn)的個(gè)數(shù)占整個(gè)數(shù)據(jù)集的比例，除了D5是43.11%，其他數(shù)據(jù)集上均小于40%.在NaN算法中，對(duì)所有數(shù)據(jù)點(diǎn)均采用NaNE作為近鄰參數(shù).從圖中可以看出，存在一些近鄰個(gè)數(shù)很小甚至為0的數(shù)據(jù)點(diǎn)，對(duì)于這些點(diǎn)，如果采用NaNE作為近鄰參數(shù)，可能會(huì)將一些類別模式不同的點(diǎn)作為鄰居，影響檢測結(jié)果，同時(shí)因?yàn)榭紤]了更多的近鄰而降低了計(jì)算效率.

圖5 k值分布Fig.5 Distribution of k values

3.2.2 離群點(diǎn)檢測準(zhǔn)確率的比較

由于對(duì)比算法的檢測結(jié)果均依賴于參數(shù)k的設(shè)置，所以實(shí)驗(yàn)中比較了不同k值下的檢測準(zhǔn)確率，如圖6所示.圖中橫軸表示近鄰參數(shù)k值，縱軸表示準(zhǔn)確率.橫線表示PKNN計(jì)算出的準(zhǔn)確率(這里每個(gè)點(diǎn)的k值不完全相同，所以只給出準(zhǔn)確率，與k的變化無關(guān)).

圖6 不同檢測算法在取不同k值時(shí)的準(zhǔn)確率Fig.6 Accuracies of different detection methods over a range of k values

從圖6中可以看出，在個(gè)別數(shù)據(jù)集(D1，D3，D6，D8)上，其他算法僅在少數(shù)特定的k值下的準(zhǔn)確率超過PKNN，從整體來講，其他算法的準(zhǔn)確率由于受到近鄰參數(shù)k的影響，上下波動(dòng)范圍較大，在大部分k值下的準(zhǔn)確率均小于PKNN算法準(zhǔn)確率.對(duì)于比較算法，LOF在D1上的準(zhǔn)確率相對(duì)較高，說明LOF對(duì)于D1這種分布密度明顯不同的數(shù)據(jù)集具有較好的檢測效果；INS在近鄰參數(shù)不斷變大的過程中，準(zhǔn)確率變化不明顯，表現(xiàn)了INS對(duì)近鄰參數(shù)的魯棒性；其他算法檢測效果受近鄰參數(shù)影響較大.

為了更加直觀地比較不同算法的優(yōu)劣，圖7給出了PKNN算法和其他算法在不同k值下的準(zhǔn)確率比較結(jié)果排名，其中橫軸表示近鄰參數(shù)k值，縱軸表示排名.PKNN算法中每個(gè)點(diǎn)的k值是唯一確定的，且不完全相同，所以圖7只給出PKNN的準(zhǔn)確率排名，與k的變化無關(guān).

圖7 不同算法準(zhǔn)確率排名Fig.7 Accuracies ranking of methods

從圖6可知，PKNN算法在每個(gè)數(shù)據(jù)集上的準(zhǔn)確率是不變的，而其他算法均受參數(shù)k的影響，所以準(zhǔn)確率是變化的，會(huì)在極少數(shù)特定的k值下的準(zhǔn)確率超過PKNN，導(dǎo)致圖7中PKNN算法的排名出現(xiàn)了微小的波動(dòng)，盡管如此，其排名始終最高，而其他對(duì)比算法的排名波動(dòng)較大.

表3 不同算法準(zhǔn)確率高于其他算法的次數(shù)Table 3 Number of wins in accuracy

表3給出了每種算法的準(zhǔn)確率高于其他算法的次數(shù)比較(結(jié)果相同的次數(shù)不包括在內(nèi))，對(duì)于每一個(gè)數(shù)據(jù)集，表中數(shù)值為每種算法k從2到50上的次數(shù)累加結(jié)果.

從表3可以看出，PKNN算法在8組數(shù)據(jù)集上準(zhǔn)確率高于其他算法的次數(shù)均為最高，且總次數(shù)遠(yuǎn)高于其他算法，表現(xiàn)出PKNN在不同數(shù)據(jù)集上具有很好的自適應(yīng)性.對(duì)于其他方法，在不同數(shù)據(jù)集上表現(xiàn)不同，整體來看，KNN在3個(gè)數(shù)據(jù)集(D2，D4，D5)上較好，LOF和LDOF分別在2個(gè)數(shù)據(jù)集(D1，D6；D7，D8)上較好，INS在數(shù)據(jù)集D3上較好，INFLO表現(xiàn)最差.

以上實(shí)驗(yàn)結(jié)果表明，PKNN算法在面對(duì)不同的數(shù)據(jù)集時(shí)，可以根據(jù)數(shù)據(jù)集本身的特征自動(dòng)確定每個(gè)點(diǎn)的近鄰參數(shù)，相比于其他算法來說，不但避免了參數(shù)選擇的問題，還可以達(dá)到很高的準(zhǔn)確率，算法的結(jié)果與人工情況下對(duì)數(shù)據(jù)的基本判斷相符合.

4 結(jié) 論

近鄰思想被廣泛應(yīng)用在離群點(diǎn)檢測方法中，而近鄰參數(shù)k的取值對(duì)檢測結(jié)果會(huì)產(chǎn)生很大影響.現(xiàn)有的方法大多都是人為設(shè)定參數(shù)k，且所有點(diǎn)都采用相同的k值.為了避免k的選擇問題，本文提出了PKNN算法，在不需要提前指定近鄰參數(shù)k的情況下，可以根據(jù)數(shù)據(jù)集自身的分布，自適應(yīng)地選擇近鄰并確定每個(gè)點(diǎn)的k值，然后去尋找離群點(diǎn).PKNN不但避免了參數(shù)k的選擇問題，與其他較為主流的離群點(diǎn)檢測算法相比，也具有更好的檢測效果和性能.然而由于PKNN需要對(duì)每個(gè)點(diǎn)尋找近鄰，所以時(shí)間復(fù)雜度相對(duì)較高，如何提高其效率值得進(jìn)一步研究.