張忠平，張玉停，劉偉雄，鄧 禹

(1.燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004；2.河北省計(jì)算機(jī)虛擬技術(shù)與系統(tǒng)集成重點(diǎn)實(shí)驗(yàn)室，河北 秦皇島 066004；3.河北省軟件工程重點(diǎn)實(shí)驗(yàn)室，河北 秦皇島 066004)

0 引言

離群點(diǎn)檢測(cè)旨在發(fā)現(xiàn)數(shù)據(jù)集上的特殊數(shù)據(jù)對(duì)象或模式，是數(shù)據(jù)挖掘的一項(xiàng)重要挑戰(zhàn)。離群值檢測(cè)技術(shù)已廣泛應(yīng)用于許多領(lǐng)域，如工業(yè)無(wú)線傳感器網(wǎng)絡(luò)[1]，欺詐檢測(cè)[2-3]，入侵檢測(cè)[4]，心電圖異常檢測(cè)[5]等。離群點(diǎn)檢測(cè)又稱異常點(diǎn)檢測(cè)，其目的是檢測(cè)出與絕大多數(shù)對(duì)象存在差異的對(duì)象。一般離群點(diǎn)檢測(cè)方法分包括基于統(tǒng)計(jì)的方法、基于分類(lèi)的方法、基于近鄰的方法等。其中基于近鄰的方法主要分為基于距離的方法和基于密度的方法?；诰嚯x的方法以距離體現(xiàn)“近鄰性”，基于密度的方法則以密度體現(xiàn)“近鄰性”[6]。

KNORR等[7-8]是最早提出使用基于距離的離群點(diǎn)檢測(cè)算法，該算法克服了基于統(tǒng)計(jì)的方法需要提前選定模型和參數(shù)的問(wèn)題。該方法利用每個(gè)數(shù)據(jù)對(duì)象到鄰居點(diǎn)的距離作為度量數(shù)據(jù)對(duì)象的離群程度，使其適用于各種高維數(shù)據(jù)集，但也存在算法時(shí)間復(fù)雜度高，對(duì)參數(shù)選取較為敏感的問(wèn)題。同時(shí)，由于使用全局閾值，難以檢測(cè)不同密度區(qū)域處的局部離群點(diǎn)。BORIAH等[9]使用k近鄰思想提出一種可以處理大數(shù)據(jù)集的離群點(diǎn)檢測(cè)算法，但該算法在計(jì)算每個(gè)數(shù)據(jù)對(duì)象的鄰域時(shí)需要重新檢索整個(gè)數(shù)據(jù)集，使得算法的時(shí)空開(kāi)銷(xiāo)較大。

在基于密度的離群點(diǎn)檢測(cè)方法中，其假設(shè)離群點(diǎn)的密度與鄰居點(diǎn)的密度區(qū)別很大，即一個(gè)點(diǎn)的局部密度明顯不同于其鄰居點(diǎn)，則該點(diǎn)被檢測(cè)為離群點(diǎn)?；谏鲜鱿敕?，近年來(lái)提出眾多離群點(diǎn)檢測(cè)算法，此類(lèi)算法因計(jì)算數(shù)據(jù)對(duì)象的密度方法而不同。文獻(xiàn)[10]使用LOF(local outlier factor)值作為衡量一個(gè)點(diǎn)的離群程度，提出了LOF算法，該方法通過(guò)數(shù)據(jù)點(diǎn)的鄰域可達(dá)密度與該點(diǎn)的局部密度的比值得出對(duì)應(yīng)的LOF值，該值越大，表示該點(diǎn)越可能是離群點(diǎn)。該方法通過(guò)LOF值表示一個(gè)點(diǎn)的離群程度，改變了以往算法對(duì)離群點(diǎn)直接給出判定結(jié)果的做法。由于現(xiàn)實(shí)世界數(shù)據(jù)的復(fù)雜多樣，文獻(xiàn)[10]中的算法存在很多不足。文獻(xiàn)[11]提出反向k近鄰“RNN”的概念，并構(gòu)造了局部離群因子INFLO以提高算法對(duì)離群點(diǎn)的檢測(cè)性能。該方法在計(jì)算每個(gè)點(diǎn)的局部密度時(shí)，不僅考慮k近鄰集合，還考慮反向k近鄰集合。因此，能夠減少在數(shù)據(jù)分布復(fù)雜情況下基于k近鄰的算法可能出現(xiàn)的誤判。TANG[12]提出一種基于連接的COF算法,該方法提出鏈距離的概念以有效地確定數(shù)據(jù)對(duì)象的個(gè)性化局部空間，進(jìn)而克服了LOF算法對(duì)低密度區(qū)域的數(shù)據(jù)對(duì)象不能有效度量的缺陷。除此之外，在LOF算法基礎(chǔ)上，還產(chǎn)生了自然鄰居因子(Natural Outlier Factor, NOF)算法[13]、局部稀疏系數(shù)(Local Sparsity Coefficient, LSC)算法[14]、多粒度偏差系數(shù)(Multi-granularity Deviation Factor, MDEF)算法[15]等?；诿芏鹊碾x群點(diǎn)檢測(cè)方法可以檢測(cè)各種復(fù)雜的數(shù)據(jù)形式。但大多數(shù)算法對(duì)近鄰參數(shù)k的選取較為敏感且在高維數(shù)據(jù)集應(yīng)用時(shí)需要很大的時(shí)空開(kāi)銷(xiāo)。

近年來(lái)在離群點(diǎn)檢測(cè)領(lǐng)域不斷提出新穎的方法。文獻(xiàn)[16]利用累計(jì)全熵挖掘最佳聚類(lèi)子空間，并在最佳聚類(lèi)子空間中檢測(cè)離群點(diǎn)，大大提高了算法處理的效率;文獻(xiàn)[17]將自然鄰居搜索算法和密度峰值聚類(lèi)算法結(jié)合，提出一種基于聚類(lèi)離群因子和相互密度的離群點(diǎn)檢測(cè)算法，該算法不需要人為指定參數(shù)，且有較好的離群點(diǎn)檢測(cè)性能;JIANG等[18]提出一種基于重力的概念用于離群點(diǎn)檢測(cè),該方法首先為數(shù)據(jù)對(duì)象賦予質(zhì)量定義，利用變形后的萬(wàn)有引力公式計(jì)算每個(gè)數(shù)據(jù)對(duì)象在其鄰域內(nèi)受到的合力LRF，最后通過(guò)不同類(lèi)型的數(shù)據(jù)對(duì)象合力變化率的差異來(lái)識(shí)別數(shù)據(jù)集中的異常點(diǎn);文獻(xiàn)[19]利用自然鄰居的概念自適應(yīng)的獲取鄰域k值，通過(guò)加權(quán)核密度估計(jì)方法獲取數(shù)據(jù)對(duì)象的局部密度。最后利用鄰域平均密度與數(shù)據(jù)對(duì)象的局部密度之比獲取該點(diǎn)離群程度，進(jìn)而提高了離群點(diǎn)的檢測(cè)性能。針對(duì)k鄰域關(guān)系存在的檢測(cè)效果差，k值選取較為敏感的問(wèn)題，文獻(xiàn)[20]提出一種近鄰樹(shù)(Nearest Neighbors Tree, NNT)的鄰域關(guān)系用于離群點(diǎn)檢測(cè)，利用每個(gè)數(shù)據(jù)對(duì)象近鄰樹(shù)結(jié)構(gòu)最長(zhǎng)邊和剩余邊均值的比值表示該數(shù)據(jù)對(duì)象的離群程度。該算法相比于基于k鄰域關(guān)系的算法有更高的準(zhǔn)確率且對(duì)k值不敏感。

隨著數(shù)據(jù)類(lèi)型越來(lái)越復(fù)雜以及數(shù)據(jù)維度不斷增加，基于k近鄰關(guān)系的離群點(diǎn)檢測(cè)算法檢測(cè)效果不夠理想。引入新的鄰域關(guān)系可以為離群點(diǎn)檢測(cè)提供新的研究方向。針對(duì)上述問(wèn)題引入近鄰樹(shù)(NNT)的鄰域關(guān)系，提出一種基于質(zhì)心投影波動(dòng)的離群點(diǎn)檢測(cè)算法(Outlier Detection algorithm based on Fluctuation of Centroid Projection, FCPOD)。該算法引入近鄰樹(shù)關(guān)系，為每個(gè)數(shù)據(jù)對(duì)象提供一個(gè)質(zhì)心投影。質(zhì)心投影既能考慮樣本點(diǎn)到鄰居點(diǎn)的距離，也能考慮樣本點(diǎn)與其鄰域集合的分布特征。隨著k值的增加，離群點(diǎn)區(qū)域的質(zhì)心投影波動(dòng)要遠(yuǎn)高于內(nèi)部正常點(diǎn)。最后，利用數(shù)據(jù)對(duì)象的質(zhì)心投影波動(dòng)刻畫(huà)每個(gè)點(diǎn)的離群程度。

1 相關(guān)工作

1.1 相關(guān)定義

給定數(shù)據(jù)集D={xi},i=1,…,n,xi∈Rd，其中d為數(shù)據(jù)對(duì)象xi的維度個(gè)數(shù)，算法涉及的概念和定義如下。

定義1點(diǎn)p的近鄰樹(shù)。給定數(shù)據(jù)集D，頂點(diǎn)集N，邊集E和參數(shù)k，則以點(diǎn)p為起始點(diǎn)的近鄰樹(shù)NNTk(p)定義為式(1)所示：

NNTm(p)=

(1)

式中：k表示近鄰樹(shù)邊的個(gè)數(shù)，1NN(·)表示距離第一個(gè)最近的鄰居點(diǎn)；Nm-1表示第m-1次迭代后近鄰樹(shù)的頂點(diǎn)集。為避免NNT樹(shù)形成環(huán)，式(1)中1NN(q)?Nm-1。

近鄰樹(shù)構(gòu)造：點(diǎn)p的NNT樹(shù)構(gòu)造過(guò)程和最小生成樹(shù)類(lèi)似，首先將數(shù)據(jù)對(duì)象p放入頂點(diǎn)集N中，尋求距離頂點(diǎn)集N中數(shù)據(jù)對(duì)象最近的鄰居點(diǎn)，且該鄰居點(diǎn)不在頂點(diǎn)集N中。然后將該點(diǎn)和對(duì)應(yīng)的邊分別加入頂點(diǎn)集和邊集中。不斷迭代該過(guò)程直到NNT中邊的個(gè)數(shù)達(dá)到k，則點(diǎn)p的近鄰樹(shù)構(gòu)造結(jié)束。

如圖1所示為點(diǎn)1，6，10的近鄰樹(shù)結(jié)構(gòu)。其中：k=4，點(diǎn)1，6，7為離群點(diǎn)，其他點(diǎn)為正常點(diǎn)。點(diǎn)1的近鄰樹(shù)結(jié)構(gòu)為NNT4(1)={1,2,2,3,3,4,3,5}，點(diǎn)6的近鄰樹(shù)結(jié)構(gòu)為NNT4(6)={6,7,6,8,8,9,9,3}，點(diǎn)10的近鄰樹(shù)結(jié)構(gòu)為NNT4(10)={10,11,10,12,10,13,11,14}，從圖1中可以看出以1，6，7為代表的離群點(diǎn)近鄰樹(shù)關(guān)系可以快速擴(kuò)展到高密度區(qū)域。且由于近鄰樹(shù)鄰域關(guān)系的特殊性，相比傳統(tǒng)的k近鄰鄰域關(guān)系，離群點(diǎn)的鄰居點(diǎn)有更高概率出現(xiàn)在的離群點(diǎn)的一側(cè)。當(dāng)面對(duì)不同類(lèi)簇的影響時(shí)，離群點(diǎn)的鄰居點(diǎn)更傾向出現(xiàn)在第一個(gè)最近點(diǎn)所在的類(lèi)簇。這種特性可用于下文離群點(diǎn)的檢測(cè)。

定義2點(diǎn)p的鄰域。給定數(shù)據(jù)集D，點(diǎn)p近鄰樹(shù)頂點(diǎn)集N中數(shù)據(jù)對(duì)象的集合稱為點(diǎn)p的鄰域，記作NN(p)。

定義3點(diǎn)p的質(zhì)心(鄰域質(zhì)心)。給定數(shù)據(jù)集D，點(diǎn)p的鄰域集合中數(shù)據(jù)對(duì)象的重心稱為點(diǎn)p的質(zhì)心，記作c(p)，

(2)

式中：k為鄰域集合數(shù)據(jù)對(duì)象的個(gè)數(shù);q為包含d個(gè)維度的向量。不包括數(shù)據(jù)點(diǎn)本身的鄰域質(zhì)心更能刻畫(huà)出數(shù)據(jù)點(diǎn)到鄰域質(zhì)心的距離和鄰居分布。

定義4點(diǎn)p的質(zhì)心向量。點(diǎn)p指向其質(zhì)心c的向量稱為點(diǎn)p的質(zhì)心向量，記作pc。

定義5點(diǎn)p的質(zhì)心投影。點(diǎn)p指向其鄰域集合中數(shù)據(jù)對(duì)象形成的向量沿著pc方向的投影稱為點(diǎn)p的質(zhì)心投影，記作CenV(p,k)，

(3)

在圖3中，P1為離群點(diǎn)，P2為內(nèi)部點(diǎn)。其中，P1到P4的距離比P1到P3的距離稍大。使用傳統(tǒng)的k近鄰關(guān)系選定P1的鄰居點(diǎn)會(huì)依次包含P3和P4，使得P1在左右兩個(gè)類(lèi)簇中都存在鄰居點(diǎn)，因此可能難以檢測(cè)出P1為離群點(diǎn)。為解決上述問(wèn)題，本文使用近鄰樹(shù)鄰域關(guān)系刻畫(huà)數(shù)據(jù)對(duì)象的鄰域點(diǎn)，由于P1到P3的距離比P1到P4的距離稍近，P1會(huì)首先選中P3為第一個(gè)鄰居點(diǎn)，然后由于近鄰樹(shù)的特性，P3所在類(lèi)簇中的部分點(diǎn)會(huì)被依次選為P1點(diǎn)的鄰居點(diǎn)，使用近鄰樹(shù)鄰域關(guān)系可以使離群點(diǎn)P1的鄰居點(diǎn)集中在最靠近離群點(diǎn)的類(lèi)簇中，減少了不同類(lèi)簇對(duì)離群點(diǎn)判定的影響。離群點(diǎn)P1隨著鄰居點(diǎn)的增加，質(zhì)心投影的值不斷增大且方向大致相同。內(nèi)部點(diǎn)P2隨著鄰居的增加，質(zhì)心投影基本保持不變且由于鄰居點(diǎn)分散在P2點(diǎn)周?chē)?，投影方向也較為均勻地指向其周?chē)Ｒ虼?，可以看出隨著k值的增加離群點(diǎn)和內(nèi)部點(diǎn)質(zhì)心投影變化不同。

為進(jìn)一步驗(yàn)證隨著k值增大不同類(lèi)型點(diǎn)質(zhì)心投影變化不同這一特征，在人工數(shù)據(jù)集A1上進(jìn)一步進(jìn)行驗(yàn)證。圖4表現(xiàn)的是在不同k值下，離群點(diǎn)和內(nèi)部點(diǎn)質(zhì)心投影的變化?？梢郧宄乜闯觯S著k值的增大，離群點(diǎn)的質(zhì)心投影不斷增大，波動(dòng)較為劇烈。內(nèi)部點(diǎn)的質(zhì)心投影雖有波動(dòng)但較為平穩(wěn)且一直維持在較低的水平。由圖3和圖4可以看出隨著數(shù)據(jù)對(duì)象使用近鄰樹(shù)關(guān)系得到的鄰居點(diǎn)不斷增多，離群點(diǎn)的質(zhì)心投影波動(dòng)要遠(yuǎn)大于內(nèi)部點(diǎn)的質(zhì)心投影波動(dòng)。因此，通過(guò)質(zhì)心投影變化波動(dòng)可以很好地刻畫(huà)數(shù)據(jù)對(duì)象的離群程度，數(shù)據(jù)點(diǎn)質(zhì)心投影波動(dòng)越大，表示該數(shù)據(jù)點(diǎn)越有可能是離群點(diǎn)。

2 基于質(zhì)心投影波動(dòng)的離群點(diǎn)檢測(cè)算法

由于傳統(tǒng)使用k近鄰關(guān)系算法中離群點(diǎn)易受不同類(lèi)簇影響而導(dǎo)致檢測(cè)效果不佳，本文引入近鄰樹(shù)鄰域關(guān)系，使得離群點(diǎn)通過(guò)近鄰樹(shù)鄰域關(guān)系可以快速得到高密度區(qū)域的鄰居點(diǎn)。同時(shí)，由于近鄰樹(shù)鄰域關(guān)系的特性，離群點(diǎn)鄰居點(diǎn)的更傾向出現(xiàn)在距離離群點(diǎn)最近的一個(gè)類(lèi)簇中，因此可以避免傳統(tǒng)使用k近鄰關(guān)系算法離群點(diǎn)檢測(cè)存在的問(wèn)題。由于離群點(diǎn)的質(zhì)心投影波動(dòng)要遠(yuǎn)遠(yuǎn)大于內(nèi)部點(diǎn)的質(zhì)心投影波動(dòng)，本文使用質(zhì)心投影波動(dòng)來(lái)刻畫(huà)數(shù)據(jù)對(duì)象的離群程度。數(shù)據(jù)對(duì)象的質(zhì)心投影波動(dòng)越大，表明該數(shù)據(jù)對(duì)象越有可能是離群點(diǎn)。

2.1 算法思想

從定義5的分析可以看出，由于離群點(diǎn)和內(nèi)部點(diǎn)的鄰居分布不同，隨著鄰居點(diǎn)的增加，離群點(diǎn)的質(zhì)心投影不斷增大，內(nèi)部點(diǎn)的質(zhì)心投影基本保持不變。因此，可使用不同k值下，質(zhì)心投影波動(dòng)進(jìn)行刻畫(huà)數(shù)據(jù)對(duì)象的離群程度。

定義6點(diǎn)p的質(zhì)心投影變化。給定數(shù)據(jù)集D，參數(shù)k，點(diǎn)p在k和k+1下質(zhì)心投影的差值稱為點(diǎn)p在k值下的質(zhì)心投影變化，記作ΔCenV(p,k)，

ΔCenV(p,k)=|CenV(p,k+1)-

CenV(p,k)|,

k=2,…,K。

(4)

定義7點(diǎn)p的質(zhì)心投影波動(dòng)。給定數(shù)據(jù)D，點(diǎn)p在不同k值下質(zhì)心投影變化的總和稱為點(diǎn)p的質(zhì)心投影波動(dòng)，記作ΘCenV(p,K)，

(5)

式中K為算法設(shè)定的最大k值。

由于不同類(lèi)型的數(shù)據(jù)對(duì)象使用近鄰樹(shù)鄰域關(guān)系得到的鄰域集合的分布不同，利用質(zhì)心向量投影波動(dòng)可以很好地刻畫(huà)出數(shù)據(jù)對(duì)象的離群程度。如圖5所示為人工數(shù)據(jù)集A5中離群點(diǎn)和內(nèi)部點(diǎn)的質(zhì)心投影波動(dòng)，其中箭頭長(zhǎng)度為數(shù)據(jù)對(duì)象質(zhì)心投影波動(dòng)值，箭頭方向?yàn)镵值下的質(zhì)心向量方向。數(shù)據(jù)點(diǎn)“”代表離群點(diǎn)，其質(zhì)心投影波動(dòng)要遠(yuǎn)遠(yuǎn)大于內(nèi)部點(diǎn)，因此使用數(shù)據(jù)對(duì)象的質(zhì)心投影波動(dòng)能很好地區(qū)分離群點(diǎn)和內(nèi)部點(diǎn)。

基于上述分析，本文提出FCPOD算法。首先，引入近鄰樹(shù)鄰域關(guān)系來(lái)代替?zhèn)鹘y(tǒng)基于k近鄰的鄰域關(guān)系，使得數(shù)據(jù)對(duì)象的鄰居點(diǎn)可以快速擴(kuò)展到高密度區(qū)域，也減少了因獲取不同類(lèi)簇的鄰居點(diǎn)對(duì)離群點(diǎn)檢測(cè)造成的影響。同時(shí)，不同類(lèi)型點(diǎn)使用近鄰樹(shù)獲取的鄰居點(diǎn)分布不同，離群點(diǎn)的鄰居點(diǎn)主要分布在其一側(cè)，內(nèi)部點(diǎn)的鄰居點(diǎn)一般分布在其四周。然后利用該特性，使用數(shù)據(jù)對(duì)象的質(zhì)心投影刻畫(huà)不同類(lèi)型點(diǎn)的鄰居分布特性。隨著k值的增大，離群點(diǎn)的質(zhì)心投影變化要遠(yuǎn)大于內(nèi)部點(diǎn)的質(zhì)心投影變化。因此，本文最后使用質(zhì)心投影波動(dòng)衡量數(shù)據(jù)點(diǎn)的離群程度，數(shù)據(jù)點(diǎn)的質(zhì)心投影波動(dòng)越大，該數(shù)據(jù)點(diǎn)越有可能是離群點(diǎn)。

2.2 FCPOD算法描述

本節(jié)主要描述FCPOD算法的執(zhí)行過(guò)程。FCPOD算法需要輸入數(shù)據(jù)集D和鄰居點(diǎn)個(gè)數(shù)K，其輸出為top-n個(gè)數(shù)據(jù)對(duì)象的索引值。該算法利用質(zhì)心投影波動(dòng)值衡量數(shù)據(jù)對(duì)象的離群程度。首先構(gòu)建每個(gè)數(shù)據(jù)的近鄰樹(shù)結(jié)構(gòu)獲取其鄰居點(diǎn)，每指定一個(gè)k值可得到對(duì)應(yīng)的質(zhì)心投影。然后，將數(shù)據(jù)對(duì)象質(zhì)心投影的變化進(jìn)行加和以獲取最終的質(zhì)心投影波動(dòng)。最后，利用該質(zhì)心投影波動(dòng)對(duì)數(shù)據(jù)對(duì)象進(jìn)行排序，將排序結(jié)果得分最高的top-n個(gè)點(diǎn)視為離群點(diǎn)。

根據(jù)2.1節(jié)算法思想及相關(guān)定義，F(xiàn)CPOD描述如下：

算法1FCPOD算法。

輸入:DatasetD，K;

輸出:top-noutlier inD。

1.初始化：index=?，k=1

2.創(chuàng)建數(shù)據(jù)集D的KD樹(shù) //用于加快鄰居檢索

3.For each p∈D do

4. For k in 2 to K

5. Create NNT(p); //創(chuàng)建p點(diǎn)的NNT樹(shù)

6. Get NN(p); //獲取p點(diǎn)的鄰域集合

7. Get c of p //獲取p點(diǎn)的質(zhì)心

8. Get CenV(p,k) //獲取p點(diǎn)的質(zhì)心投影

9. IF k>2

10. Get ΔCenV(p,k) //獲取p點(diǎn)的質(zhì)心投影變化

11. End IF

12. End For

13. Compute ΘCenV(p,K) //獲取p點(diǎn)的質(zhì)心投影波動(dòng)

14.End For

15.Sort ΘCenV(p,K)in descending order //降序排序離群因子

16.Output top-n outlier

FCPOD算法的時(shí)間復(fù)雜度主要來(lái)源于以下兩部分：①為得到每個(gè)數(shù)據(jù)對(duì)象的K個(gè)最近鄰居而構(gòu)建的KD-tree，時(shí)間復(fù)雜度為O(n·logn)，n為數(shù)據(jù)集的數(shù)據(jù)對(duì)象個(gè)數(shù)；②計(jì)算數(shù)據(jù)對(duì)象質(zhì)心投影波動(dòng)ΘCenV(p,K)，時(shí)間復(fù)雜度為O(n·K)，K?logn

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

為評(píng)估FCPOD算法的性能，使用局部離群因子(Local Outlier Factor, LOF)[10]連接異常因子(Connective Outlier Factor, COF)[12]、孤立森林(Isolation forest, IForest)[21]、直方圖的異常因子(Histogram-based Outlier Score, HBOS)[22]和局部結(jié)構(gòu)異常因子(local structure outlier factor, LSOF)[19]算法在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)驗(yàn)證，比較分析本文算法的性能。本文FCPOD算法和上述選定的5個(gè)對(duì)比算法一樣，不再二元化地判斷每個(gè)數(shù)據(jù)對(duì)象是否是離群點(diǎn)，而是為每個(gè)數(shù)據(jù)對(duì)象賦予一個(gè)離群程度，然后利用該離群程度對(duì)數(shù)據(jù)對(duì)象進(jìn)行排序，選取前n個(gè)點(diǎn)為檢測(cè)出的離群點(diǎn)。同時(shí)，選定上述5個(gè)對(duì)比算法也是為了方便繪制下文中算法的離群點(diǎn)發(fā)現(xiàn)曲線[23-24]。

其中，LOF算法是基于密度的離群點(diǎn)檢測(cè)算法中最為經(jīng)典的算法，多用于算法性能比較的基準(zhǔn)算法。COF算法在LOF算法基礎(chǔ)上進(jìn)行改進(jìn)，LOF和COF算法能基本代表基于密度的離群點(diǎn)檢測(cè)算法，由于LOF算法和COF均未使用特殊的鄰居檢索策略，其時(shí)間復(fù)雜度均為O(n2)。HBOS算法是一種基于直方圖估計(jì)密度的無(wú)監(jiān)督異常檢測(cè)算法，本質(zhì)上是一種基于統(tǒng)計(jì)的離群點(diǎn)檢測(cè)算法，其時(shí)間復(fù)雜度為O(n·logn)。IForest算法由于具有線性的時(shí)間復(fù)雜度和很好的檢測(cè)性能，一直是離群點(diǎn)檢測(cè)算法最為經(jīng)典的代表之一。LSOF算法是第一個(gè)將近鄰樹(shù)鄰域關(guān)系引入離群點(diǎn)檢測(cè)的算法，在使用如KD-Tree這類(lèi)的結(jié)構(gòu)用于檢索鄰居點(diǎn)后，其時(shí)間復(fù)雜度為O(n·logn)。本文選用基于密度的離群點(diǎn)檢測(cè)算法、基于統(tǒng)計(jì)的離群點(diǎn)檢測(cè)算法、IForest和LSOF算法與本文算法進(jìn)行對(duì)比分析，能較為全面且有效地比較分析FCPOD算法的性能。實(shí)驗(yàn)環(huán)境如表1所示。

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

3.1 評(píng)價(jià)指標(biāo)

在大多數(shù)實(shí)際應(yīng)用中，相比大量存在的正常數(shù)據(jù)，含異常值的數(shù)據(jù)顯得很稀有，使得在離群點(diǎn)檢測(cè)過(guò)程中出現(xiàn)數(shù)據(jù)不平衡現(xiàn)象。因此，在離群點(diǎn)檢測(cè)領(lǐng)域很少有研究者直接使用傳統(tǒng)度量指標(biāo)如準(zhǔn)確率、精確率等來(lái)衡量離群點(diǎn)檢測(cè)性能。ROC曲線(receiver operating characteristics curve)即受試者工作特征曲線，可以綜合考慮敏感性和特異性的影響，使得其被廣泛用于度量非平衡數(shù)據(jù)集。ROC曲線是指真陽(yáng)性率隨著假陽(yáng)性率變化的曲線，其中真陽(yáng)性率和假陽(yáng)性率定義分別如式(6)和式(7)所示。

(6)

(7)

其中：TP表示判斷為離群點(diǎn)實(shí)際也為離群點(diǎn)的個(gè)數(shù)；FP表示判斷為離群點(diǎn)實(shí)際卻是內(nèi)部點(diǎn)的個(gè)數(shù)；TN表示判斷為內(nèi)部點(diǎn)實(shí)際也為內(nèi)部點(diǎn)的個(gè)數(shù)；FN表示判斷為內(nèi)部點(diǎn)實(shí)際卻是離群點(diǎn)的個(gè)數(shù)。

AUC(area under curve)值描述的是在ROC曲線下方的面積，其值范圍為0～1。AUC值大的離群點(diǎn)檢測(cè)算法意味著有更大的概率將離群點(diǎn)排在內(nèi)部點(diǎn)之前[25]。因此，AUC值越大算法表現(xiàn)越好。

離群點(diǎn)發(fā)現(xiàn)曲線(outlier discovery curve)[23-24]用于描述算法檢測(cè)出離群點(diǎn)個(gè)數(shù)與查詢個(gè)數(shù)之間的關(guān)系。離群點(diǎn)發(fā)現(xiàn)曲線中橫坐標(biāo)為離群點(diǎn)檢測(cè)算法查詢前n個(gè)點(diǎn)中真實(shí)的離群點(diǎn)個(gè)數(shù)，縱坐標(biāo)為查詢的個(gè)數(shù)n。離群點(diǎn)檢測(cè)算法對(duì)應(yīng)的離群點(diǎn)發(fā)現(xiàn)曲線爬升越快，表明它比同類(lèi)算法能更加準(zhǔn)確有效地檢測(cè)離群點(diǎn)。

本文主要使用ROC曲線中的AUC值和離群點(diǎn)發(fā)現(xiàn)曲線衡量離群點(diǎn)檢測(cè)算法的性能。LOF、COF、LSOF和本文FCPOD算法都需要指定一個(gè)k值以確定鄰居點(diǎn)的個(gè)數(shù)。實(shí)驗(yàn)使用的k值為2～100。IForest算法是基于樹(shù)結(jié)構(gòu)的經(jīng)典算法，為避免不平衡的隔離樹(shù)對(duì)算法性能造成影響。實(shí)驗(yàn)中為IForest算法在每個(gè)數(shù)據(jù)集上進(jìn)行100次實(shí)驗(yàn)取其平均值來(lái)衡量算法性能。實(shí)驗(yàn)各個(gè)算法均取其最優(yōu)表現(xiàn)。

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

為測(cè)試本文算法在各種復(fù)雜數(shù)據(jù)分布下的性能。本文使用圖6所示的6種二維的人工數(shù)據(jù)集A1～A6進(jìn)行實(shí)驗(yàn)，其中離群點(diǎn)為“o”代表的點(diǎn)。人工數(shù)據(jù)集的屬性特征如表2所示。其中A1和A3數(shù)據(jù)集為包含若干類(lèi)簇且類(lèi)簇之間的密度有差異的人工數(shù)據(jù)集，A2,A4,A5,A6為包含各種復(fù)雜數(shù)據(jù)分布的非球狀類(lèi)簇的數(shù)據(jù)集，選用圖6所示的6種數(shù)據(jù)集能較為全面地檢測(cè)本文算法在各種復(fù)雜數(shù)據(jù)分布下的離群點(diǎn)檢測(cè)效果。

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

圖7展示了本文FCPOD算法和對(duì)比算法在人工數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果。由圖7中可以看出，在人工數(shù)據(jù)集A2，A3，A4，A6中，隨著查詢數(shù)據(jù)點(diǎn)個(gè)數(shù)的增加，本文FCPOD算法查詢出的真實(shí)離群點(diǎn)個(gè)數(shù)一直是最多的，而且離群點(diǎn)發(fā)現(xiàn)曲線基本維持在一條在直線上。FCPOD算法在人工數(shù)據(jù)集A1和A5上表現(xiàn)分別和IForest算法，LOF算法性能接近。FCPOD算法雖不在各個(gè)數(shù)據(jù)集都表現(xiàn)最優(yōu)，但整體性能遠(yuǎn)遠(yuǎn)好于其他算法。因此，該實(shí)驗(yàn)驗(yàn)證了FCPOD算法可以適應(yīng)各種復(fù)雜形狀的數(shù)據(jù)分布且有較好的性能表現(xiàn)。

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

本文采用的6個(gè)真實(shí)數(shù)據(jù)集均來(lái)自UCI數(shù)據(jù)集，數(shù)據(jù)集的維度在4～60之間，離群點(diǎn)所占比例在4.4%～35.8%之間，以較為全面的檢測(cè)FCPOD算法的真實(shí)性能，表3展示了真實(shí)數(shù)據(jù)集的數(shù)據(jù)特征。在數(shù)據(jù)預(yù)處理階段使用式(8)進(jìn)行歸一化處理：

Xnorm=(X-Xmin)/(Xmax-Xmin)。

(8)

其中：Xnorm表示歸一化后的數(shù)據(jù)對(duì)象，Xmax和Xmin分別為各個(gè)維度上最大和最小的值。對(duì)于缺失的空值屬性使用數(shù)據(jù)集對(duì)應(yīng)屬性的均值代替。

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

如表4所示為真實(shí)數(shù)據(jù)集下各個(gè)算法的AUC值，同時(shí)標(biāo)注出每個(gè)真實(shí)數(shù)據(jù)集下表現(xiàn)最優(yōu)的前兩個(gè)算法。FCPOD算法在所有真實(shí)數(shù)據(jù)集上AUC值均屬于表現(xiàn)最優(yōu)的前兩個(gè)算法。尤其在Iris，Sonar數(shù)據(jù)集上離群點(diǎn)檢測(cè)性能遠(yuǎn)遠(yuǎn)好于表現(xiàn)次優(yōu)的其他算法。在包含離群點(diǎn)數(shù)量多的Lonosphere數(shù)據(jù)集中，本文FCPOD算法也能保存較好的檢測(cè)效果。Sonar數(shù)據(jù)有60個(gè)維度，隨著數(shù)據(jù)集維度的增多，一般基于近鄰性的算法檢測(cè)效果較差，F(xiàn)CPOD算法不僅考慮數(shù)據(jù)對(duì)象到鄰居點(diǎn)的距離，還考慮了數(shù)據(jù)對(duì)象與鄰居點(diǎn)的分布關(guān)系，因此檢測(cè)效果較好。

如圖8所示為各算法在真實(shí)數(shù)據(jù)集上的離群點(diǎn)發(fā)現(xiàn)曲線。在Lonosphere，Iris，Sonar數(shù)據(jù)集的實(shí)驗(yàn)中，F(xiàn)CPOD算法在每次查詢過(guò)程中檢測(cè)出的離群點(diǎn)都是最多的。特別在Lonosphere數(shù)據(jù)集上，F(xiàn)CPOD算法檢測(cè)出的離群點(diǎn)數(shù)量是HBOS算法的兩倍左右。在Wbc數(shù)據(jù)集上LSOF，LOF和COF算法檢測(cè)效果較差，而FCPOD算法和IForest算法表現(xiàn)較好。HBOS算法在Sonar數(shù)據(jù)集表現(xiàn)最差?？傮w上看，本文FCPOD算法能在各個(gè)數(shù)據(jù)集上都有較為出色的離群點(diǎn)檢測(cè)效果，從而驗(yàn)證了本文算法能全面準(zhǔn)確的檢測(cè)到離群點(diǎn)。

表4 真實(shí)數(shù)據(jù)集各算法AUC值

從上述實(shí)驗(yàn)分析可知，本文FCPOD算法在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上都表現(xiàn)良好而且性能穩(wěn)定。其中，本文算法選定數(shù)據(jù)集中數(shù)據(jù)分布較為復(fù)雜，而在集成制造領(lǐng)域中，工業(yè)數(shù)據(jù)集種類(lèi)繁多且數(shù)據(jù)分布復(fù)雜，使用傳統(tǒng)的k近鄰關(guān)系的離群點(diǎn)檢測(cè)算法由于數(shù)據(jù)集中不同類(lèi)簇的相互影響導(dǎo)致算法難以快速有效地檢測(cè)離群點(diǎn)。因此，本文算法比傳統(tǒng)基于k近鄰關(guān)系的離群點(diǎn)檢測(cè)算法能更有效地處理工業(yè)數(shù)據(jù)集的離群點(diǎn)檢測(cè)，而且算法性能較為穩(wěn)定。

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

本文首先分析了傳統(tǒng)基于近鄰性的離群點(diǎn)檢測(cè)相關(guān)算法思想和近年來(lái)較為新穎的算法。針對(duì)傳統(tǒng)近鄰關(guān)系檢測(cè)離群點(diǎn)存在的問(wèn)題，引入一種稱為近鄰樹(shù)的鄰域關(guān)系，采用質(zhì)心投影刻畫(huà)數(shù)據(jù)對(duì)象和其鄰居點(diǎn)的關(guān)系，并利用離群點(diǎn)和內(nèi)部點(diǎn)質(zhì)心投影波動(dòng)不同提出一種基于質(zhì)心投影波動(dòng)的離群點(diǎn)檢測(cè)算法(FCPOD)。對(duì)FCPOD算法進(jìn)行了詳細(xì)闡述，并進(jìn)行了時(shí)間復(fù)雜度的分析，同時(shí)也給出了對(duì)比算法的時(shí)間復(fù)雜度分析。最后對(duì)本文提出的FCPOD算法在人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)驗(yàn)證，通過(guò)對(duì)實(shí)驗(yàn)結(jié)果的比較分析，驗(yàn)證了本文算法能有效且全面的檢測(cè)離群點(diǎn)。雖然FCPOD算法在AUC值和離群點(diǎn)發(fā)現(xiàn)曲線上表現(xiàn)較好，但隨著數(shù)據(jù)集的規(guī)模和數(shù)據(jù)維度越來(lái)越大，在不斷出現(xiàn)的繁雜多變的數(shù)據(jù)集中，算法的檢測(cè)精度和效率需要進(jìn)一步的提高。因此，針對(duì)有數(shù)量龐大的、數(shù)據(jù)維度高的數(shù)據(jù)集，研究出檢測(cè)精度高、耗時(shí)少的離群點(diǎn)檢測(cè)算法是今后的主要研究方向。