馬文強(qiáng)，趙旭俊，張繼福，饒?jiān)?/p>

(太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，太原 030024)

E-mail:mwq_93@163.com

1 引 言

離群點(diǎn)挖掘是數(shù)據(jù)挖掘中的一個(gè)重要領(lǐng)域，也被稱(chēng)作離群點(diǎn)檢測(cè).隨著人工智能技術(shù)飛速的發(fā)展，對(duì)離群點(diǎn)檢測(cè)研究的興趣正在大大增加[1].Hawkins[2]將離群點(diǎn)定義如下：離群數(shù)據(jù)是數(shù)據(jù)集中偏離大部分對(duì)象的數(shù)據(jù)，它們的表現(xiàn)與大多數(shù)常規(guī)對(duì)象有著明顯的差異，以至于讓人懷疑它們可能是由另外一種完全不同的機(jī)制所產(chǎn)生的.但是，離群數(shù)據(jù)并不全是錯(cuò)誤數(shù)據(jù)，離群數(shù)據(jù)中可能蘊(yùn)含著極為重要的信息，并已廣泛應(yīng)用在許多領(lǐng)域，例如天文光譜[3]，信用卡欺詐[4]，網(wǎng)絡(luò)異常檢測(cè)[5，6]，道路交通異常[7]等.近年來(lái)，研究者提出了許多離群檢測(cè)算法，其中基于k近鄰(kNN)和逆近鄰(RNN)的離群檢測(cè)是重要算法之一.隨著數(shù)據(jù)維度的增加[8]，一些數(shù)據(jù)對(duì)象(樞紐點(diǎn))會(huì)經(jīng)常出現(xiàn)在其他數(shù)據(jù)對(duì)象的kNN列表中，其逆近鄰集合中包含的數(shù)據(jù)對(duì)象個(gè)數(shù)很多，同時(shí)，一些數(shù)據(jù)對(duì)象(非樞紐點(diǎn))幾乎成為不常見(jiàn)的鄰居，其逆近鄰集合中包含的數(shù)據(jù)對(duì)象個(gè)數(shù)很少或者為零，這種現(xiàn)象稱(chēng)為樞紐現(xiàn)象.

樞紐現(xiàn)象(Hubness)是高維空間學(xué)習(xí)中的一個(gè)普遍問(wèn)題，在許多文獻(xiàn)中將其作為一個(gè)新的研究方向[9，10].樞紐現(xiàn)象是“維度災(zāi)難”中與k近鄰查詢(xún)相關(guān)的概念，它是指數(shù)據(jù)對(duì)象出現(xiàn)在其他數(shù)據(jù)對(duì)象的kNN列表中的次數(shù)Nk(i)(即RNN).其出現(xiàn)的原因是由于隨著數(shù)據(jù)維度的增加，導(dǎo)致數(shù)據(jù)對(duì)象的次數(shù)Nk(i)出現(xiàn)的分布出現(xiàn)向右偏斜，同時(shí)方差也隨之增加.樞紐現(xiàn)象造成的后果是一些數(shù)據(jù)對(duì)象(hubs，稱(chēng)為樞紐點(diǎn))會(huì)經(jīng)常出現(xiàn)在其他數(shù)據(jù)對(duì)象的kNN列表中，同時(shí)，一些數(shù)據(jù)對(duì)象(antihubs，稱(chēng)為非樞紐點(diǎn))會(huì)經(jīng)常不出現(xiàn)或很少出現(xiàn)在其他數(shù)據(jù)對(duì)象的kNN列表中.非樞紐與離群數(shù)據(jù)在高維和低維數(shù)據(jù)上均存在著聯(lián)系.本文針對(duì)離群檢測(cè)中的樞紐現(xiàn)象，結(jié)合k近鄰和逆近鄰互補(bǔ)性能，分析了離群檢測(cè)中的影響空間，并一種面向樞紐現(xiàn)象的雙向近鄰離群檢測(cè)算法，HPOD算法.首先，算法引入并重新定義了對(duì)象的影響空間，在影響空間中，不僅考慮對(duì)象的k近鄰的影響作用同時(shí)還考慮逆近鄰的影響作用；其次，在HPOD算法的基礎(chǔ)上引入了啟發(fā)式信息，提出了改進(jìn)算法HPOD2算法，有效的降低了k的取值，從而減少了算法的計(jì)算量和運(yùn)行時(shí)間；最后，采用真實(shí)數(shù)據(jù)集對(duì)本文提出的改進(jìn)算法進(jìn)行了檢測(cè)并證明了本文提出的算法要優(yōu)于傳統(tǒng)的基于樞紐現(xiàn)象的離群數(shù)據(jù)挖掘算法.

2 相關(guān)工作

傳統(tǒng)的離群點(diǎn)檢測(cè)算法，大致可以分為基于統(tǒng)計(jì)的離群檢測(cè)[11]，基于距離的離群檢測(cè)[12]，基于密度的離群檢測(cè)[13，14]，基于近鄰的離群檢測(cè)[15]，基于角度的離群檢測(cè)[16，17]等.樞紐現(xiàn)象是高維數(shù)據(jù)中普遍存在的現(xiàn)象，而且隨著數(shù)據(jù)集維數(shù)的不斷增加，樞紐現(xiàn)象會(huì)越來(lái)越明顯，被作為“維度災(zāi)難”的新方面和高維空間學(xué)習(xí)的一般問(wèn)題進(jìn)行了研究.

樞紐現(xiàn)象是“維度災(zāi)難”中與k近鄰查詢(xún)相關(guān)的概念，而k近鄰查詢(xún)是一個(gè)理論上比較成熟的方法，也是最簡(jiǎn)單的機(jī)器學(xué)習(xí)算法之一[18].加權(quán)k最近鄰算法[19]是k近鄰查詢(xún)最簡(jiǎn)單、最有效改進(jìn)算法，其主要思想是根據(jù)它們的距離來(lái)分配同一個(gè)權(quán)重的鄰居，權(quán)重隨著距離變化而變化，距離越近，權(quán)重越大，反之，距離越遠(yuǎn)，權(quán)重越??；LOF算法[20]通過(guò)k近鄰查詢(xún)計(jì)算對(duì)象的 k-距離、可達(dá)距離和可達(dá)密度，用數(shù)據(jù)對(duì)象k最近鄰的平均可達(dá)密度與數(shù)據(jù)對(duì)象自身的可達(dá)密度之比表示數(shù)據(jù)對(duì)象的離群程度，但計(jì)算量大，不適合高維數(shù)據(jù)；還有LOCI算法[21]和LoOP算法[22]等很多算法都用到了k近鄰查詢(xún).

逆k近鄰查詢(xún)是在k近鄰查詢(xún)問(wèn)題的基礎(chǔ)上產(chǎn)生的，獲得將查詢(xún)對(duì)象作為kNN的數(shù)據(jù)對(duì)象集合，逆k近鄰可以評(píng)價(jià)查詢(xún)對(duì)象的影響力，同樣在離群數(shù)據(jù)挖掘方面也有廣泛的應(yīng)用.ODIN算法[23]是基于k最近鄰圖的入度(即逆近鄰)來(lái)實(shí)現(xiàn)異常檢測(cè)的算法，如果數(shù)據(jù)的入度小就可以被看做離群數(shù)據(jù)，但是需要人為設(shè)定區(qū)分度，不適用于未知數(shù)據(jù)集；INFLO算法[24]是一種基于密度的技術(shù)，在估計(jì)點(diǎn)的離群值時(shí)，除了直接鄰居之外還考慮反向鄰居的密度，是對(duì)LOF算法的擴(kuò)展，解決了LOF算法對(duì)密度變化不敏感的缺點(diǎn)，但是只適合在低維和中維數(shù)據(jù)集，在高維數(shù)據(jù)集中效果較差.在數(shù)據(jù)聚類(lèi)方面，逆k近鄰查詢(xún)也得到應(yīng)用，RNN-DBSCAN算法[25]用Nk(i)作為對(duì)觀測(cè)密度的估計(jì)，不僅可以處理較大的密度變化，而且將閾值由兩個(gè)降低到一個(gè)，減少了人為因素的干擾，但是k值的選擇對(duì)RNN-DBSCAN算法有較大的影響；Radovanovic等人[26]提出了適用高維數(shù)據(jù)的AntiHub和AntiHub2算法.Antihub算法根據(jù)每個(gè)數(shù)據(jù)對(duì)象i的Nk(i)值來(lái)確定離群點(diǎn)，AntiHub2算法則是在Antihub算法的基礎(chǔ)上同時(shí)考慮每個(gè)數(shù)據(jù)對(duì)象i的值Nk(i)及其k最近鄰Nk(i)值，但是AntiHub算法只有在較大的k值上才能提高正常數(shù)據(jù)與離群數(shù)據(jù)的區(qū)分度，運(yùn)算量代價(jià)昂貴，雖然AntiHub2算法可以在相對(duì)較小的k值獲得較高的區(qū)分度，但是k的取值還是相對(duì)較大.Guo等[27]人在AntiHub2算法的基礎(chǔ)上引入距離加權(quán)提出了WAntiHub算法，雖然提高了算法的準(zhǔn)確性，但是并未解決AntiHub2算法所出現(xiàn)的問(wèn)題，并且隨著k值的逐漸增大，距離加權(quán)的效果逐漸降低.

綜上所述，現(xiàn)有的大部分基于逆k近鄰(RkNN)的離群挖掘算法主要使用逆近鄰來(lái)檢測(cè)離群數(shù)據(jù).但是，這些算法需要較大的k值才能獲得較高的正常數(shù)據(jù)與離群數(shù)據(jù)的區(qū)分度，運(yùn)算量較大，耗費(fèi)時(shí)間較長(zhǎng)，并且未考慮k近鄰等信息.

3 影響空間下的離群數(shù)據(jù)挖掘樞紐算法

現(xiàn)有的基于逆k近鄰(RkNN)的離群挖掘算法均利用數(shù)據(jù)對(duì)象的Nk(i)值來(lái)確定離群值，文獻(xiàn)[11]中算法在較低的k值上對(duì)正常數(shù)據(jù)與離群數(shù)據(jù)的區(qū)分度不高，主要是因?yàn)閿?shù)據(jù)對(duì)象的Nk(i)值本質(zhì)是離散的，要想得到較高的準(zhǔn)確率，往往需要選擇較大的k值，但是計(jì)算量較大，并且從未考慮k近鄰因素.針對(duì)上述問(wèn)題，提出了一種面向樞紐現(xiàn)象的離群數(shù)據(jù)檢測(cè)算法(An Outlier Detection Algorithm for Hubness Phenomenon，HPOD)，算法利用對(duì)象的影響空間進(jìn)行離群數(shù)據(jù)檢測(cè)，同時(shí)考慮數(shù)據(jù)對(duì)象的逆近鄰和近鄰等信息，有效的消除只由逆近鄰帶來(lái)的局限性，提高了算法的準(zhǔn)確率.為了進(jìn)一步提高算法的性能，本文對(duì)HPOD算法進(jìn)行了改進(jìn)，提出了HPOD2算法，HPOD2算法在HPOD算法的基礎(chǔ)上引入了啟發(fā)式信息，可以減小k的取值，從而減少算法的計(jì)算量.

3.1 影響空間

針對(duì)現(xiàn)有的大部分基于逆k近鄰(RkNN)的離群挖掘算法單純只使用逆近鄰來(lái)檢測(cè)離群數(shù)據(jù)且并未考慮k近鄰等原因，本文提出使用對(duì)象的影響空間來(lái)檢測(cè)異常數(shù)據(jù)，同時(shí)考慮數(shù)據(jù)對(duì)象的逆近鄰和近鄰等信息，相關(guān)定義如下：

定義 1.數(shù)據(jù)對(duì)象p的k-距離.對(duì)?p∈數(shù)據(jù)集D，p的k-距離，記作kdist(p)，定義為對(duì)象p和對(duì)象q之間的距離dist(p,q)，且滿(mǎn)足：

1)至少有k個(gè)對(duì)象qi∈D，使得

dist(p,qi)≤dist(p,q)；

2)至多有(k-1)個(gè)對(duì)象qi∈D，使得

dist(p,qi)

定義 2.數(shù)據(jù)對(duì)象p的k最近鄰集合.對(duì)p∈數(shù)據(jù)集D，p的k鄰域點(diǎn)集NNk(p)，定義為數(shù)據(jù)集D的一個(gè)非空子集X，滿(mǎn)足dist(p,X)≤kdist(p)即P的k鄰域點(diǎn)集為

NNk(p)={X?D}dist(p,X)≤kdist(p)}

(1)

由定義1和定義 2可知，雖然數(shù)據(jù)對(duì)象p的k最近鄰集合可能不是唯一的，但數(shù)據(jù)對(duì)象p的kdist(p)是唯一的.而且數(shù)據(jù)對(duì)象p的最近鄰關(guān)系是不對(duì)稱(chēng)的.對(duì)于給定的數(shù)據(jù)對(duì)象p，p的最近鄰可能并沒(méi)有把數(shù)據(jù)對(duì)象p作為自己的最近鄰之一.

定義 3.數(shù)據(jù)對(duì)象p的逆近鄰集合.數(shù)據(jù)對(duì)象p的逆鄰域點(diǎn)集RNNk(p)，定義為

RNNk(p)={q∈D|q∈NNk(p)}

(2)

由定義3可知對(duì)于任意數(shù)據(jù)對(duì)象p的k近鄰數(shù)據(jù)集NNk(p)包含至少k個(gè)數(shù)據(jù)對(duì)象，而數(shù)據(jù)對(duì)象p的RNNk(p)取決于數(shù)據(jù)對(duì)象p作為其他點(diǎn)的k近鄰次數(shù)可能為空，也有可能含有遠(yuǎn)遠(yuǎn)大于k個(gè)數(shù)據(jù)對(duì)象.而同時(shí)考慮數(shù)據(jù)對(duì)象p的RNNk(p)和NNk(p)，形成一個(gè)關(guān)于數(shù)據(jù)對(duì)象p的局部鄰域空間，用來(lái)表示數(shù)據(jù)對(duì)象p的離群程度，定義如下：

定義 4.對(duì)象p的影響空間.數(shù)據(jù)對(duì)象p的影響空間ISk(p)，定義為對(duì)象p的k最近鄰集合和逆近鄰集合的交集，即

ISk(p)=NNk(p)∩RNNk(p)

(3)

由定義4可知離群數(shù)據(jù)都會(huì)較少或不出現(xiàn)在其他數(shù)據(jù)對(duì)象的近鄰列表中，表示逆近鄰集合包含的數(shù)據(jù)對(duì)象數(shù)量較少或者為空，其影響空間中包含的數(shù)據(jù)對(duì)象也會(huì)較少或不存在.采用對(duì)象的影響空間代替逆近鄰進(jìn)行離群數(shù)據(jù)檢測(cè)，同時(shí)考慮數(shù)據(jù)對(duì)象的逆近鄰和近鄰等信息，可以消除只由逆近鄰帶來(lái)的局限性，有效減少誤報(bào)率，除此之外，對(duì)象的影響空間同時(shí)考慮數(shù)據(jù)對(duì)象的逆近鄰和近鄰，對(duì)局部密度的變化有較高的敏感性，要優(yōu)于其他方法.

3.2 HPOD算法

文獻(xiàn)[25]利用數(shù)據(jù)對(duì)象的Nk(i)值來(lái)確定離群值，并選擇全體數(shù)據(jù)對(duì)象中離群分?jǐn)?shù)最小的n個(gè)數(shù)據(jù)對(duì)象作為離群對(duì)象，并未考慮數(shù)據(jù)對(duì)象的k近鄰等因素.因此，根據(jù)定義4來(lái)定義對(duì)象的影響空間，并結(jié)合文獻(xiàn)[25]，計(jì)算數(shù)據(jù)對(duì)象xi離群分?jǐn)?shù)的標(biāo)準(zhǔn)化公式可重新定義為：

(4)

其中：ε為影響因子且ε∈[0,1]，dist(xi)為對(duì)象p的k-距離，sxi為數(shù)據(jù)對(duì)象xi的離群分?jǐn)?shù)，Nk(i)為數(shù)據(jù)對(duì)象xi的逆近鄰數(shù)量.

由公式(4)可得當(dāng)數(shù)據(jù)對(duì)象xi為離群數(shù)據(jù)時(shí)，經(jīng)常不出現(xiàn)或很少出現(xiàn)在其他數(shù)據(jù)對(duì)象的kNN列表中，其N(xiāo)k(i)值較低，該數(shù)據(jù)對(duì)象的逆近鄰所包含的數(shù)據(jù)對(duì)象也就較少，且數(shù)據(jù)對(duì)象的dist(xi)較大，sxi的得分也就越大.當(dāng)數(shù)據(jù)對(duì)象的Nk(i)值較低時(shí)，其數(shù)據(jù)對(duì)象的dist(xi)則對(duì)數(shù)據(jù)對(duì)象的離群得分有較大的影響，從而保證了算法在較小的k值獲得較高的正常數(shù)據(jù)與離群數(shù)據(jù)的區(qū)分度；雖然隨著k值的增加數(shù)據(jù)對(duì)象的dist(xi)對(duì)數(shù)據(jù)對(duì)象的離群得分的影響逐漸降低，但數(shù)據(jù)對(duì)象的Nk(i)值逐漸變大，對(duì)數(shù)據(jù)對(duì)象的離群得分的影響逐漸增加，能保證算法在較高的k值也能獲得較高的區(qū)分度.綜上所述，數(shù)據(jù)對(duì)象的影響空間，可以保證算法無(wú)論在較高或者較低的k值上都能保持一個(gè)理想的正常數(shù)據(jù)與離群數(shù)據(jù)的區(qū)分度.

影響因子ε的給定可以調(diào)節(jié)dist(xi)和Nk(i)所占的比重，使算法適應(yīng)不同的場(chǎng)景應(yīng)用.當(dāng)待檢測(cè)數(shù)據(jù)比較適合逆近鄰檢測(cè)時(shí)，可以將影響因子ε變?。划?dāng)待檢測(cè)數(shù)據(jù)比較適合用距離檢測(cè)時(shí)，可以將影響因子ε變大.在一些極端的情況下，例如，當(dāng)待檢測(cè)數(shù)據(jù)過(guò)度分散時(shí)，采用逆近鄰檢測(cè)，準(zhǔn)確率極低，甚至干擾檢測(cè)結(jié)果，此時(shí)可以將ε設(shè)為1，只靠dist(xi)來(lái)檢測(cè)數(shù)據(jù)；反之，當(dāng)待檢測(cè)數(shù)據(jù)對(duì)距離信息不敏感時(shí)，此時(shí)可以將ε設(shè)為0，只根據(jù)待檢測(cè)數(shù)據(jù)的逆近鄰信息來(lái)檢測(cè)數(shù)據(jù).極端情況下，計(jì)算數(shù)據(jù)對(duì)象xi離群分?jǐn)?shù)的公式(4)則變?yōu)椋?/p>

(5)

3.3 HPOD2算法

為了能夠在相對(duì)較小的k值上獲得較高的正常數(shù)據(jù)與異常數(shù)據(jù)之間的區(qū)分度，減少計(jì)算量與運(yùn)行時(shí)間，本文提出了HPOD算法的改進(jìn)算法，HPOD2算法.

HPOD2算法在HPOD算法的基礎(chǔ)上引入了啟發(fā)式信息，不僅考慮數(shù)據(jù)對(duì)象xi本身的離群分?jǐn)?shù)sxi，同時(shí)還考慮其k近鄰對(duì)象的離群情況.數(shù)據(jù)對(duì)象xi的k近鄰對(duì)象的離群得分之和annxi計(jì)算公式定義如下：

annxi=∑xj∈NN(xi)sxj

(6)

其中：annxi是數(shù)據(jù)對(duì)象xi的k近鄰sxj得分之和，數(shù)據(jù)對(duì)象xj則是xi的k近鄰，sxj為數(shù)據(jù)對(duì)象xj的離群得分.

對(duì)于每個(gè)數(shù)據(jù)對(duì)象xi，HPOD2算法按比列將(1-α)*sxi與數(shù)據(jù)對(duì)象xi的k近鄰的離群分?jǐn)?shù)之和α*annxi相加，其中α為最大區(qū)分度比列，能最大限度的區(qū)分離群數(shù)據(jù)與正常數(shù)據(jù).數(shù)據(jù)對(duì)象xi的離群程度計(jì)算公式為：

ssxi=(1-α)*sxi+α*annxi

(7)

其中：ssxi為數(shù)據(jù)對(duì)象xi的離群總得分，sxi為數(shù)據(jù)對(duì)象xj的離群得分，annxi為數(shù)據(jù)對(duì)象xj的k近鄰sxj得分之和，α是最大區(qū)分比例，α∈[0,1].

4 算法描述

HPOD算法的基本過(guò)程為：第一步，對(duì)數(shù)據(jù)集中的每個(gè)數(shù)據(jù)對(duì)象xi計(jì)算其k近鄰，根據(jù)數(shù)據(jù)對(duì)象的k近鄰得到每個(gè)數(shù)據(jù)對(duì)象xi出現(xiàn)在其他數(shù)據(jù)對(duì)象的kNN列表中的次數(shù)Nk(i)和dist(xi)；第二步，根據(jù)公式(4)，計(jì)算數(shù)據(jù)對(duì)象的離群分?jǐn)?shù)，得到sxi；最后，根據(jù)上一步得到的每個(gè)數(shù)據(jù)對(duì)象的離群分?jǐn)?shù)，從中選取離群分?jǐn)?shù)最高的n個(gè)對(duì)象作為離群對(duì)象.其算法描述如下：

算法：HPOD

輸入：

數(shù)據(jù)集D={x1,x2,…,xn},其中，xi∈D,i∈{1,2,…,n}

近鄰數(shù)量k∈{1,2,…,n}

影響因子ε∈[0,1]

輸出：離群分?jǐn)?shù)最高的n個(gè)數(shù)據(jù)對(duì)象

步驟：

1)For each i∈(1, 2,…, n) in D

2) 計(jì)算數(shù)據(jù)對(duì)象xi的k近鄰，得到數(shù)據(jù)對(duì)象xi的Nk(i)值

3) 和dist(xi)

4)end for；

5)For each i∈(1, 2,…, n) in D

6) 根據(jù)公式(4)，計(jì)算數(shù)據(jù)對(duì)象的離群分?jǐn)?shù)，得到sxi

7)end for；

8)End HPOD

HPOD2算法在HPOD算法的基礎(chǔ)上同時(shí)考慮其k近鄰數(shù)據(jù)，在計(jì)算數(shù)據(jù)對(duì)象xi的sxi得分的同時(shí)，還考慮其k近鄰數(shù)據(jù)對(duì)象的s得分，通過(guò)設(shè)置step參數(shù)進(jìn)行遍歷，找到最大區(qū)分度比例α，區(qū)分度比列α通過(guò)最大限度地區(qū)分離群程度最大異常對(duì)象的異常值得分自動(dòng)確定，并且由兩個(gè)參數(shù)控制：離群值與最大識(shí)別率之比ρ(其中，ρ∈(0,1])和搜索最大區(qū)分度比列α?xí)r的步長(zhǎng)step(step∈(0,1])，并在最大區(qū)分度比例α的基礎(chǔ)上將數(shù)據(jù)對(duì)象xi的sxi得分和其k近鄰對(duì)象的離群得分之和annxi相加，得到最后的數(shù)據(jù)對(duì)象的離群分?jǐn)?shù)，從中選取離群分?jǐn)?shù)最高的n個(gè)對(duì)象作為離群對(duì)象.其算法描述如下：

算法：HPOD2

輸入：

數(shù)據(jù)集D={x1,x2,…,xn},其中，xi∈D,i∈{1,2,…,n}

近鄰數(shù)量k∈{1,2,…,n}

影響因子ε∈[0,1]

離群值與最大識(shí)別率之比ρ∈(0,1]

搜索最大區(qū)分度比列α?xí)r的步長(zhǎng)step∈(0,1]

輸出：離群分?jǐn)?shù)最高的若干對(duì)象

局部函數(shù)：discScore(ssxi,ρ)：對(duì)于ss∈Rn和ρ∈(0，1]，輸出ss中的[nρ]最小成員中唯一項(xiàng)的數(shù)目，并除以「nρ?.

步驟：

1)For each i∈(1, 2,…, n) in D

2) 計(jì)算數(shù)據(jù)對(duì)象xi的k近鄰，得到數(shù)據(jù)對(duì)象xi的Nk(i)值和

dist(xi)

3)end for；

4)For each i∈(1, 2,…, n) in D

5) 根據(jù)公式(4)，計(jì)算數(shù)據(jù)對(duì)象的離群分?jǐn)?shù)，得到sxi

6) 根據(jù)公式(6)，計(jì)算數(shù)據(jù)對(duì)象xi的k近鄰的離群分?jǐn)?shù)之和

annxi

7)end for；

8)disc :=0；

9)For each α∈(0,step,2·step,…, 1)

10) For each i∈(1, 2,…, n)

11) 根據(jù)公式(7)，計(jì)算數(shù)據(jù)對(duì)象xi的離群分?jǐn)?shù)，得到ssxi

12) end for；

13) cdisc :=discScore(ssxi,ρ) //計(jì)算α對(duì)應(yīng)的區(qū)分度

14) If cdisc>disc

15) t:=ssxi；disc:=cdisc；

16) end if；

17)end for；

18)For each i ∈ (1, 2,…, n) in D

19) 根據(jù)得到的最大區(qū)分度α值和公式(7)計(jì)算數(shù)據(jù)對(duì)象的離群

分?jǐn)?shù)

20)end for；

21)End HPOD2

算法的復(fù)雜性分析：

HPOD算法中，計(jì)算每個(gè)數(shù)據(jù)對(duì)象的k近鄰之后，可以同時(shí)得到數(shù)據(jù)對(duì)象xi的Nk(i)值和dist(xi)，因此HPOD算法的時(shí)間復(fù)雜度為O(n2)；HPOD2算法在HPOD算法的基礎(chǔ)上引入了啟發(fā)式信息，還考慮其k近鄰數(shù)據(jù)，除此之外，還需要計(jì)算最大區(qū)分度，因此HPOD2算法的時(shí)間復(fù)雜度為O(n2s)，其中s為計(jì)算最大區(qū)分度α值的時(shí)間復(fù)雜度.

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

為了驗(yàn)證提出的基于數(shù)據(jù)對(duì)象的影響空間算法的有效性，選取真實(shí)數(shù)據(jù)集進(jìn)行性能測(cè)試，并與AntiHub2算法和WAntiHub算法的實(shí)驗(yàn)結(jié)果進(jìn)行了比較.AntiHub2算法和WAntiHub算法是兩種常見(jiàn)基于樞紐現(xiàn)象的離群數(shù)據(jù)檢測(cè)算法，其中AntiHub2算法分析了樞紐現(xiàn)象，并且證明了非樞紐點(diǎn)和離群數(shù)據(jù)存在著聯(lián)系；WAntiHub算法是對(duì)AntiHub2算法的改進(jìn)，在AntiHub2算法的基礎(chǔ)上利用k近鄰中的距離信息作為權(quán)值，對(duì)逆k近鄰中的離群分?jǐn)?shù)進(jìn)行了加權(quán).本文所有的實(shí)驗(yàn)測(cè)試，均在以下環(huán)境進(jìn)行：Inter(R)Core(TM)i5-4200CPU，8GB內(nèi)存，Windows7操作系統(tǒng)，IntelliJ IDEA開(kāi)發(fā)平臺(tái)，采用java語(yǔ)言實(shí)現(xiàn)了所提出的算法以及涉及的相關(guān)算法.

實(shí)驗(yàn)全部采用真實(shí)數(shù)據(jù)集進(jìn)行驗(yàn)證，且真實(shí)數(shù)據(jù)集全部來(lái)源于ELKI庫(kù)(1)https：// elki-project.github.io/datasets/，分別為Ionosphere、SpamBase和PenDigits.數(shù)據(jù)集Ionosphere包含351條數(shù)據(jù)和32個(gè)屬性，其中包括126個(gè)離群數(shù)據(jù)；數(shù)據(jù)集SpamBase包含2588條數(shù)據(jù)和57個(gè)屬性，其中包括50個(gè)離群數(shù)據(jù)；數(shù)據(jù)集PenDigits包含9878條數(shù)據(jù)和16個(gè)屬性，其中包括30個(gè)離群數(shù)據(jù).測(cè)試數(shù)據(jù)集的詳細(xì)信息如表1所示.

表1 測(cè)試數(shù)據(jù)集信息

Table 1 Details of test data

數(shù)據(jù)集數(shù)量n維度d離群點(diǎn)數(shù)量PenDigits98781630Ionosphere35132126SpamBase25885750

5.1 驗(yàn)證對(duì)象影響空間的有效性

為了驗(yàn)證算法采用對(duì)象的影響空間的性能要優(yōu)于其逆近鄰，本文將HPOD算法、HPOD2算法、Antihub2算法和WAntiHub算法在數(shù)據(jù)集SpamBase上進(jìn)行測(cè)試，算法都使用相同的參數(shù)，搜索最大區(qū)分度比列α?xí)r的步長(zhǎng)step=0.001，離群值與最大識(shí)別率之比ρ=0.1，HPOD算法和HPOD2算法中的影響因子ε=0.5，然后將兩者的實(shí)驗(yàn)結(jié)果進(jìn)行比較.

圖1 數(shù)據(jù)集SpamBase上性能對(duì)比

由圖1可知，Antihub2算法和WAntiHub算法的準(zhǔn)確率隨著k值的增加而逐漸變高，在k取值900以后才一直維持較高的區(qū)分度，主要原因是數(shù)據(jù)對(duì)象的逆近鄰數(shù)量是離散的，需要較大的k值才能獲得較高的區(qū)分度；而HPOD算法和HPOD2算法在k取值30到50之間就能獲得較高的區(qū)分度，遠(yuǎn)遠(yuǎn)小于Antihub2算法和WAntiHub算法中的k取值，并且隨著k值的增加，一直具有較高的準(zhǔn)確率，主要原因是HPOD算法和HPOD2算法引入了數(shù)據(jù)對(duì)象的影響空間，同時(shí)考慮數(shù)據(jù)對(duì)象的逆近鄰和近鄰等信息，雖然在k值較小的時(shí)候，只靠數(shù)據(jù)對(duì)象的逆近鄰數(shù)量無(wú)法獲得較高的區(qū)分度，但是數(shù)據(jù)對(duì)象的近鄰因素對(duì)數(shù)據(jù)對(duì)象的影響較大，使得HPOD算法和HPOD2算法能在較低的k值上有較高的準(zhǔn)確率.

由圖2可知，在數(shù)據(jù)集SpamBase上，WAntiHub算法和Antihub2算法和HPOD2算法都隨著k值的增加耗費(fèi)時(shí)間逐漸增加，并且在相同的k值上，效率差別不大，HPOD算法；但是由圖1可知，HPOD算法和HPOD2算法在較低的k值上就可以得到較高的準(zhǔn)確率，而WAntiHub算法和Antihub2算法卻需要較大的k值；從圖4(c)中的數(shù)據(jù)集SpamBase上，可以看出在各自最優(yōu)k值上HPOD算法和HPOD2算法耗費(fèi)的時(shí)間要遠(yuǎn)遠(yuǎn)低于WAntiHub算法和Antihub2算法，主要是由于WAntiHub算法和Antihub2算法的k值較大，計(jì)算量變大，從而導(dǎo)致算法耗費(fèi)時(shí)間變長(zhǎng).

圖2 數(shù)據(jù)集SpamBase上效率對(duì)比

在圖1和圖2中還可以看出，HPOD算法比HPOD2算法的準(zhǔn)確率低，但算法效率明顯高于其他算法，主要有兩方面的原因：一是HOPD2算法中需要設(shè)置步長(zhǎng)，step值越小，在搜索最大區(qū)分度比例時(shí)耗費(fèi)時(shí)間O(s)將越長(zhǎng)(可參見(jiàn)第5節(jié)HPOD算法的時(shí)間復(fù)雜度分析)，而在HPOD算法中不需要這一步驟，因此HPOD2算法的執(zhí)行時(shí)間會(huì)高于HPOD算法，并受到步長(zhǎng)step值的直接影響；二是由于HPOD2算法在HPOD算法的基礎(chǔ)上進(jìn)行了改進(jìn)，引入了啟發(fā)式信息，考慮數(shù)據(jù)對(duì)象的k近鄰對(duì)象的離群情況，提高了算法的準(zhǔn)確率，但增加了算法的執(zhí)行時(shí)間.

如果應(yīng)用場(chǎng)景對(duì)效率要求高的情況下，可以采用HPOD算法，在犧牲一定的精度下保持較高的效率；如果應(yīng)用場(chǎng)景對(duì)準(zhǔn)確率要求較高，可以采用HPOD2算法.

5.2 算法性能對(duì)比

在驗(yàn)證了影響空間的有效性之后，使用真實(shí)數(shù)據(jù)集Ionosphere和真實(shí)數(shù)據(jù)集PenDigits對(duì)算法的性能進(jìn)行實(shí)驗(yàn)測(cè)試，并對(duì)所有算法在效率和準(zhǔn)確率上進(jìn)行比較來(lái)驗(yàn)證改進(jìn)算法的有效性.在這里所有算法使用相同的參數(shù)，對(duì)比的是HPOD算法、HPOD2算法、Antihub2算法和WAntiHub算法在各自選取最優(yōu)的k值時(shí)的準(zhǔn)確率及其效率.

圖3表明，在真實(shí)數(shù)據(jù)集Ionosphere和真實(shí)數(shù)據(jù)集PenDigits上，HPOD算法和HPOD2算法的準(zhǔn)確率都要高于AntiHub2算法和WAntiHub算法，主要原因是HPOD算法和HPOD2算法引入對(duì)象的影響空間進(jìn)行離群數(shù)據(jù)檢測(cè)，同時(shí)考慮數(shù)據(jù)對(duì)象的逆近鄰和近鄰等信息，可以有效的消除逆近鄰帶來(lái)的在較低的k值上區(qū)分度不高的問(wèn)題，提高了算法的準(zhǔn)確率；在k取值較小時(shí)，WAntiHub算法的準(zhǔn)確率要高于AntiHub2算法，主要是因?yàn)閃AntiHub算法在AntiHub2算法的基礎(chǔ)上引入了加權(quán)信息，從而提高了準(zhǔn)確率，但是隨著k值的增加，任意兩個(gè)數(shù)據(jù)對(duì)象之間的k近鄰中相同的數(shù)據(jù)對(duì)象會(huì)越來(lái)越多，兩者距離慢慢地趨于一致，使基于距離信息加權(quán)的效果變差，并且WAntiHub算法同AntiHub2算法一樣往往需要取較大的k值才能獲得較高的準(zhǔn)確率.

圖3 真實(shí)數(shù)據(jù)集上算法準(zhǔn)確率對(duì)比

由圖4(a)和(b)可知，在相同k取值下AntiHub2算法和HPOD2算法的運(yùn)行時(shí)間基本上相同，WAntiHub算法的運(yùn)行時(shí)間略低于AntiHub2算法和HPOD2算法，但是相差不大，而HPOD算法的運(yùn)行時(shí)間要小于其他算法；但是由圖4(c)可以看出，所有算法為了獲得最高的區(qū)分度而選取不同的k值情況，運(yùn)行時(shí)間卻是不同的.在數(shù)據(jù)集Ionosphere中，所有算法運(yùn)行時(shí)間幾乎沒(méi)有差別，主要原因是數(shù)據(jù)集Ionosphere的數(shù)據(jù)量較小，在進(jìn)行k近鄰查詢(xún)時(shí)耗時(shí)極少，差別不大；而在數(shù)據(jù)集PenDigits和SpamBase中HPOD算法和HPOD2算法所耗費(fèi)時(shí)間要明顯少于AntiHub2算法和WAntiHub算法，主要是原因數(shù)據(jù)集PenDigits和SpamBase數(shù)據(jù)量較大，而HPOD算法和HPOD2算法可以在較低的k值上獲得最佳的正常數(shù)據(jù)與離群數(shù)據(jù)的區(qū)分度，而AntiHub2算法和WAntiHub算法則需要較高的k值，計(jì)算量的增加導(dǎo)致了算法運(yùn)行時(shí)間變長(zhǎng)，而且HPOD算法和HPOD2算法獲得的最優(yōu)區(qū)分度要高于其他算法的最優(yōu)區(qū)分度.

6 結(jié)束語(yǔ)

針對(duì)在高維數(shù)據(jù)中進(jìn)行離群數(shù)據(jù)挖掘?qū)е鲁霈F(xiàn)的樞紐現(xiàn)象，提出了一種面向樞紐現(xiàn)象的雙向近鄰離群檢測(cè)算法.該算法同時(shí)考慮影響空間中對(duì)象的k近鄰和逆近鄰對(duì)對(duì)象的影響作用；并且在HPOD算法的基礎(chǔ)引入了啟發(fā)式信息，提出了改進(jìn)算法HPOD2算法，有效的降低了k的取值，從而大大提高了算法的效率；最后，對(duì)于本文提出的改進(jìn)算法采用真實(shí)數(shù)據(jù)集對(duì)其進(jìn)行了檢測(cè)，實(shí)驗(yàn)表明本文提出的改進(jìn)算法要優(yōu)于傳統(tǒng)的基于樞紐現(xiàn)象的離群數(shù)據(jù)挖掘算法.同時(shí)，面對(duì)海量高維數(shù)據(jù)，算法的并行化將是下一步的研究工作.

圖4 真實(shí)數(shù)據(jù)集上算法效率對(duì)比