基于核密度波動(dòng)的異常檢測(cè)算法

張博文，劉 智，桑國(guó)明

大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院，遼寧 大連116026

異常檢測(cè)的目的是找出那些不同于預(yù)期的數(shù)據(jù)點(diǎn)，并嘗試找出與大多數(shù)數(shù)據(jù)表現(xiàn)模式有顯著差異的異常模式。異常檢測(cè)應(yīng)用的領(lǐng)域包括：欺詐識(shí)別、故障診斷、異?；驒z測(cè)等[1]。

在實(shí)際檢測(cè)任務(wù)中，異常標(biāo)簽的獲取往往需要花費(fèi)極大的成本，異常檢測(cè)任務(wù)面對(duì)的待檢測(cè)數(shù)據(jù)往往是無標(biāo)簽數(shù)據(jù)。因此設(shè)計(jì)科學(xué)有效的無監(jiān)督異常檢測(cè)算法具有重要意義。

基于密度的方法是一類重要的無監(jiān)督異常檢測(cè)算法。它們更注重考慮數(shù)據(jù)分布從緊密到稀疏變化的位置、采用直方圖、k-鄰域等方法完成對(duì)數(shù)據(jù)空間的分割，提高了檢測(cè)結(jié)果的可解釋性。Breunig等人提出的LOF算法[2]，Papadimitriou提出LOCI算法[3]和Kriegel等人提出的LoOP算法[4]通過考察數(shù)據(jù)點(diǎn)局部密度的稀疏程度判斷該點(diǎn)是否為異常點(diǎn)；Tang等人引入鏈?zhǔn)骄嚯x的概念，進(jìn)而提出了COF算法[5]；Jin等人提出的INFLO算法[6]在計(jì)算近鄰密度時(shí)考慮了k近鄰和反近鄰。Goldstein等提出的HBOS[7]方法構(gòu)造基于頻率直方圖的概率密度來計(jì)算異常評(píng)分。趙曉永等人[8]提出基于主動(dòng)學(xué)習(xí)的離群點(diǎn)集成挖掘方法，以基于統(tǒng)計(jì)和相似度的方法為基學(xué)習(xí)器。Lin等人[9]成功運(yùn)用三種基于密度的異常檢測(cè)算法應(yīng)用于卒中數(shù)據(jù)。

核密度估計(jì)是一種常用非參數(shù)統(tǒng)計(jì)模型，是從數(shù)據(jù)本身出發(fā)，對(duì)數(shù)據(jù)特征和分布進(jìn)行描述。Xu等人[10]運(yùn)用核密度估計(jì)方法獲得對(duì)交通流量數(shù)據(jù)最優(yōu)估計(jì)的概率密度函數(shù)，然后建立信念函數(shù)來檢測(cè)數(shù)據(jù)中的異常值。Latecki[11]為克服數(shù)據(jù)點(diǎn)間的歐式距離過小導(dǎo)致的密度估計(jì)值較大的情況，運(yùn)用局部密度估計(jì)代替歐氏距離計(jì)算密度估計(jì)值。這些方法的研究與應(yīng)用足以證明核密度估計(jì)方法在異常檢測(cè)領(lǐng)域的優(yōu)越性。

在基于核密度估計(jì)的異常檢測(cè)算法中，常常認(rèn)為異常點(diǎn)具有相對(duì)較低的核密度，而這一假設(shè)并不總是正確的。正常點(diǎn)的核密度也可能較低。因此近年來有學(xué)者提出有關(guān)密度波動(dòng)的異常檢測(cè)算法，其主要思想是異常點(diǎn)密度變化情況更復(fù)雜，波動(dòng)變化大。Cao等人[12]提出一種基于核鄰域密度變化的異常值檢測(cè)算法，該算法運(yùn)用核函數(shù)將數(shù)據(jù)集中的對(duì)象映射到高維空間內(nèi)，在單位距離內(nèi)點(diǎn)的個(gè)數(shù)定義數(shù)據(jù)對(duì)象的核鄰域密度。比較一點(diǎn)與其鄰域內(nèi)的數(shù)據(jù)點(diǎn)近鄰核密度的平均密度波動(dòng)情況。Waid等人[13]提出了一種KDOF算法，通過計(jì)算比較數(shù)據(jù)點(diǎn)間的相對(duì)核密度值波動(dòng)來確定數(shù)據(jù)集中的異常點(diǎn)。這些算法采用了一種更通用的特征表達(dá)方式，然而同樣只是專注在局部范圍內(nèi)的檢測(cè)，對(duì)全局異常點(diǎn)和集體異常檢測(cè)能力較弱。此外近鄰類算法常常敏感于近鄰參數(shù)k的取值。

針對(duì)上述問題，本文提出一種魯棒的基于核密度波動(dòng)的KDF（Kernel-Density Fluctuation factor）異常檢測(cè)算法。充分利用核密度估計(jì)的優(yōu)勢(shì)，結(jié)合密度波動(dòng)思想，定義了核密度波動(dòng)因子KDF。在此基礎(chǔ)上進(jìn)一步制定了檢測(cè)規(guī)則，在生成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集中均可以提供準(zhǔn)確且穩(wěn)定的異常檢測(cè)性能。

1 KDF異常檢測(cè)算法原理

本文首先運(yùn)用t-SNE算法對(duì)數(shù)據(jù)集進(jìn)行特征提取，降低維數(shù)的同時(shí)保持?jǐn)?shù)據(jù)原有的結(jié)構(gòu)。然后創(chuàng)新性地提出可以綜合考慮鄰域內(nèi)和鄰域外的密度波動(dòng)的核密度波動(dòng)因子KDF，據(jù)此檢測(cè)數(shù)據(jù)集中的異常點(diǎn)。

文中的核密度估計(jì)函數(shù)選取了使用較多的多元高斯核，如公式（1）：

(X1,X2,…,X n)為n個(gè)d維樣本，多元高斯核函數(shù)為：

對(duì)于任意正整數(shù)k，數(shù)據(jù)點(diǎn)P的k-近鄰距離表示為d k(P)。d k(P)必須同時(shí)滿足以下兩個(gè)條件：

（1）數(shù)據(jù)集D中至少存在k個(gè)數(shù)據(jù)點(diǎn)Q∈D{P}滿足d(P,Q)≤d k(P)。

（2）數(shù)據(jù)集D中至多存在k-1個(gè)數(shù)據(jù)點(diǎn)Q∈D{P}滿足d(P,Q)＜d k(P)。

其中{P,Q}∈D,d(P,Q)為數(shù)據(jù)集D中數(shù)據(jù)點(diǎn)P和Q間的直達(dá)距離。這里距離使用Euclidean距離，即有對(duì)于d維空間上的數(shù)據(jù)點(diǎn)P=(p1,p2,…,pd)，數(shù)據(jù)點(diǎn)

數(shù)據(jù)點(diǎn)P的k-近鄰區(qū)域N k(P)={Q|d(P,Q)≤d k(P),Q∈D{P}}。|N k(P)|表示數(shù)據(jù)點(diǎn)P的k-近鄰區(qū)域N k(P)中的元素個(gè)數(shù)。

定義1絕對(duì)核密度波動(dòng)因子AKDF（Absolute Kernel-Density Fluctuation factor），如公式（2）：

對(duì)于數(shù)據(jù)集合N和數(shù)據(jù)點(diǎn)P的k-近鄰內(nèi)的數(shù)據(jù)點(diǎn)集合N k(P)，運(yùn)用集合內(nèi)的點(diǎn)估計(jì)出P點(diǎn)的核密度值ρ(P)：

運(yùn)用k-近鄰以外的數(shù)據(jù)點(diǎn)and，估計(jì)出的P點(diǎn)的核密度值ρ′(P)：

定義的AKDF刻畫了數(shù)據(jù)點(diǎn)的全局特征和集體特征。ρ(P)主要描述了數(shù)據(jù)點(diǎn)P周圍的局部密度特征。核密度估計(jì)過程易受極端值影響，因此在計(jì)算ρ′(P)時(shí)，用內(nèi)的點(diǎn)對(duì)其進(jìn)行估算。

為方便數(shù)據(jù)可視化，本文運(yùn)用二維的生成數(shù)據(jù)，分別對(duì)兩個(gè)變量進(jìn)行一維核密度估計(jì)及可視化，其結(jié)果如圖1所示。以數(shù)據(jù)中一異常點(diǎn)的k-近鄰區(qū)域邊界為分界，將數(shù)據(jù)化分為兩部分，分別對(duì)其進(jìn)行核密度估計(jì)。兩部分的核密度估計(jì)曲線如圖2。

圖1 二維生成數(shù)據(jù)核密度估計(jì)曲線

圖2 數(shù)據(jù)核密度估計(jì)曲線

如圖2異常點(diǎn)N k(P)內(nèi)的數(shù)據(jù)點(diǎn)的核密度估計(jì)曲線和中的數(shù)據(jù)點(diǎn)的核密度估計(jì)曲線存在較大差異。因此(ρ(P)-ρ′(P))2越大，P點(diǎn)越可能是異常點(diǎn)。AKDF考慮了數(shù)據(jù)點(diǎn)所在局部區(qū)域與全局的關(guān)系，所以具有較好的區(qū)分能力。同時(shí)這一計(jì)算方法平衡了近鄰參數(shù)k的選擇問題，保證核密度估計(jì)效果的同時(shí)可以識(shí)別局部異常點(diǎn)，減少調(diào)優(yōu)空間。

目前常用異常檢測(cè)算法都著重于發(fā)現(xiàn)異常類型中的“點(diǎn)異?！?，而當(dāng)異常點(diǎn)聚集成一個(gè)簇時(shí)，這種聚類異常難以被發(fā)現(xiàn)?？紤]到已有算法對(duì)集體異常點(diǎn)發(fā)現(xiàn)能力不足的問題，提出的AKDF可以很好地描述集體異常點(diǎn)的特征。若點(diǎn)P及N k(P)內(nèi)的點(diǎn)均為異常點(diǎn)，即存在集體異常。此時(shí)ρ(P)較大，ρ′(P)較小，同樣有(ρ(P)-ρ′(P))2較大。

定義2相對(duì)核密度波動(dòng)因子RKDF(P)（Relative Kernel-Density Fluctuation factor），見公式（5）：

定義的RKDF主要用來度量數(shù)據(jù)點(diǎn)P與其k-近鄰內(nèi)數(shù)據(jù)點(diǎn)的核密度值的差異情況。RKDF(P)越大，P點(diǎn)越可能是異常點(diǎn)。相對(duì)核密度波動(dòng)因子充分考慮了異常點(diǎn)和正常點(diǎn)之間、正常點(diǎn)和正常點(diǎn)之間的關(guān)系。數(shù)據(jù)集內(nèi)常常具有幾個(gè)集群，不同數(shù)據(jù)集群的核密度曲線可能存在差異，所以運(yùn)用數(shù)據(jù)點(diǎn)的k-近鄰內(nèi)的點(diǎn)而不是全部樣本點(diǎn)進(jìn)行核密度估計(jì)。

定義3核密度波動(dòng)因子KDF(P)，如公式（6）：

KDF綜合考慮數(shù)據(jù)點(diǎn)的局部和全局異常特征、點(diǎn)異常特征和集體異常特征，將RKDF和AKDF進(jìn)行線性組合運(yùn)算。λ1和λ2為相應(yīng)權(quán)重，滿足λ1+λ2=1。在實(shí)際應(yīng)用中，可以根據(jù)數(shù)據(jù)特點(diǎn)設(shè)置相應(yīng)的權(quán)值，平衡局部特征、全局特征和集體特征間的關(guān)系，盡可能從多個(gè)角度發(fā)現(xiàn)潛在異常點(diǎn)。計(jì)算所得的KDF值越大，數(shù)據(jù)點(diǎn)為異常點(diǎn)的可能性越大。

2 KDF算法偽代碼

算法1 KDF算法

輸入：待測(cè)樣本的數(shù)據(jù)集合D，帶寬h，近鄰參數(shù)k

輸出：異常因子得分（KDFS），異常點(diǎn)集合O

1.對(duì)數(shù)據(jù)集D進(jìn)行t-sne降維，D′=t-sne(D)

2.for each pointPinD′,do

5.計(jì)算AKDF(P)；

6.end for

7.for each pointPinD′,do

8.計(jì)算RKDF(P|ρNk)(ρNk={ρ(Qi|N k(Q i))|Qi?N k(P)})；

9.計(jì)算KDF(P)；

10.end for

11.for each pointPinD′,do

13.輸出異常得分KDFS(P)

14.ifKDFS(P)＞1：

15.點(diǎn)P進(jìn)入異常點(diǎn)集合O；

16.end if

17.end for

18.輸出異常點(diǎn)集合O

3 算法分析

3.1 參數(shù)穩(wěn)定性分析

無監(jiān)督異常檢測(cè)算法存在調(diào)優(yōu)困難的問題，因此異常檢測(cè)算法的穩(wěn)定性是算法分析中的一個(gè)重要因素。

3.1.1 近鄰參數(shù)k

近鄰參數(shù)k是近鄰學(xué)習(xí)的重要參數(shù)。近鄰算法常常敏感于k值的選擇。當(dāng)k取值較小時(shí)，近似誤差減小，模型變得復(fù)雜，估計(jì)誤差增大，容易發(fā)生過擬合；選取的k值較大時(shí)，模型變得簡(jiǎn)單，估計(jì)誤差會(huì)減小，近似誤差會(huì)增大，容易發(fā)生欠擬合。KDF算法同時(shí)考慮了數(shù)據(jù)點(diǎn)鄰域內(nèi)外的核密度值差異，在理論上可以減小算法對(duì)近鄰參數(shù)k的敏感性。

3.1.2 核密度估計(jì)帶寬h

核函數(shù)中帶寬參數(shù)h是一個(gè)關(guān)鍵的超參數(shù)，用于控制模型的平滑程度。h值越大，則得到的概率密度曲線就越平滑。當(dāng)樣本數(shù)據(jù)已知時(shí)，f?h(x)的精度如何取決于核函數(shù)和帶寬h的選擇。f?h(x)依概率收斂于f(x)。多數(shù)情況用核密度估計(jì)偏差和核密度估計(jì)方差來衡量其估計(jì)效果。核密度估計(jì)的偏差（記為和核密度估計(jì)的方差（記為）計(jì)算公式如下：

由計(jì)算核密度估計(jì)偏差和核密度估計(jì)方差公式可知若h取值過大，則偏差增大，方差降低，導(dǎo)致f?h(x)過于平滑，密度函數(shù)f(x)的某些特征被掩蓋；若h取值過小，則偏差減小，方差增加，導(dǎo)致f?h(x)出現(xiàn)較大波動(dòng)，無法選擇相應(yīng)的帶寬h值使偏差和方差同時(shí)減小[14]。

在KDF算法中，將數(shù)據(jù)點(diǎn)與其鄰域內(nèi)點(diǎn)的KDF進(jìn)行比較計(jì)算，盡可能弱化不同h值對(duì)最終檢測(cè)結(jié)果帶來的影響。

3.2 算法時(shí)間復(fù)雜度分析

由于涉及對(duì)每個(gè)點(diǎn)k-近鄰區(qū)域的搜索，為提高k-近鄰的搜索效率，可以考慮使用Kd樹的結(jié)構(gòu)存儲(chǔ)訓(xùn)練數(shù)據(jù)，以減少計(jì)算距離的次數(shù)。對(duì)于n個(gè)樣本，建立Kd樹后算法的時(shí)間復(fù)雜度達(dá)到O(2nlbn)。

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

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

為驗(yàn)證KDF算法的性能，在生成數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)。生成數(shù)據(jù)集中正常樣本點(diǎn)服從二維標(biāo)準(zhǔn)正態(tài)分布，異常點(diǎn)數(shù)據(jù)一個(gè)維度服從參數(shù)為（2，0.5）的伽馬分布，另一個(gè)維度為服從參數(shù)為1.5的指數(shù)分布。選取的真實(shí)數(shù)據(jù)集為Wine數(shù)據(jù)集和Banknote數(shù)據(jù)集。Wine數(shù)據(jù)集中，類別3視為異常點(diǎn)類。Banknote數(shù)據(jù)集中，類別1視為異常點(diǎn)類；實(shí)驗(yàn)數(shù)據(jù)集的詳細(xì)信息描述如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集信息表

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

實(shí)驗(yàn)中的對(duì)比算法包括LOF算法[2]、KNN算法[15]、LOCI算法[3]和KDOF算法[13]。算法中權(quán)重設(shè)置為λ1=λ2=0.5。

在與其他算法進(jìn)行結(jié)果的比較時(shí)，確定KDOF算法和KDF算法中計(jì)算核密度估計(jì)的帶寬h，比較不同近鄰參數(shù)k下不同算法的性能。在對(duì)參數(shù)h的敏感性分析中，固定了近鄰參數(shù)k，考慮帶寬h的變化對(duì)最終實(shí)驗(yàn)結(jié)果的影響。

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

本文運(yùn)用了兩個(gè)模型性能評(píng)價(jià)指標(biāo)[16]，從不同角度評(píng)價(jià)算法的性能。

4.3.1 基于異常評(píng)分的排序準(zhǔn)確率

無監(jiān)督異常檢測(cè)算法往往對(duì)最為異常的一部分?jǐn)?shù)據(jù)進(jìn)行報(bào)警。對(duì)數(shù)據(jù)點(diǎn)所得的異常評(píng)分KDFS（Kernel-Density Fluctuation factor Score）進(jìn)行降序排序，選擇前5、10、20個(gè)點(diǎn)計(jì)算其檢測(cè)準(zhǔn)確率。這一指標(biāo)可以度量算法所得異常評(píng)分的合理性，同時(shí)又減少單純計(jì)算準(zhǔn)確率對(duì)判決閾值的依賴。

4.3.2 F1值

在異常檢測(cè)任務(wù)中，既要盡可能檢測(cè)出全部的異常情況，又要盡可能減少“誤檢”產(chǎn)生的多余成本。因此本文運(yùn)用F1值作為異常檢測(cè)算法性能的度量。

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

實(shí)驗(yàn)算法中近鄰參數(shù)k=10，KDF算法和KDOF算法中核密度估計(jì)帶寬h=0.5。

從表2中可以看出，KDF算法在三個(gè)實(shí)驗(yàn)數(shù)據(jù)集均取得了很好的結(jié)果，排序準(zhǔn)確率在大多數(shù)情況下明顯高于其他對(duì)比算法。運(yùn)用定義的KDF來檢測(cè)數(shù)據(jù)集中的異常點(diǎn)具有科學(xué)性。

表2 算法異常得分排序準(zhǔn)確率比較表

如圖3所示，在三個(gè)實(shí)驗(yàn)數(shù)據(jù)集上，KDF算法的F1值均高于其他對(duì)比算法。實(shí)驗(yàn)結(jié)果說明提出的方法可以更全面準(zhǔn)確地檢測(cè)異常點(diǎn)。

圖3 不同算法的F1值比較

4.5 參數(shù)的敏感性分析

4.5.1 近鄰參數(shù)k

對(duì)算法在不同k值下，在三個(gè)數(shù)據(jù)集中得到的F1值取平均值，與對(duì)比算法結(jié)果進(jìn)行比較。

由圖4（a）圖中可以看出在k取值較小時(shí)，不同取值下的KDF算法F1值均高于其他對(duì)比算法。而且KDF算法選擇不同的近鄰參數(shù)k對(duì)算法檢測(cè)結(jié)果影響較小，KDF算法對(duì)于k的選擇表現(xiàn)出了良好的魯棒性。

4.5.2 帶寬h

本文通過設(shè)置不同的帶寬h值，對(duì)比KDF算法與KDOF算法在三個(gè)數(shù)據(jù)集上F1的平均值。

圖4（b）圖中顯示：和KDOF算法相比，KDF算法在數(shù)據(jù)集中計(jì)算得到的F1值未出現(xiàn)明顯波動(dòng)。h值的變動(dòng)并不會(huì)給最終的檢測(cè)結(jié)果帶來較大的影響。因此算法可以提供穩(wěn)定的檢測(cè)結(jié)果。

5 結(jié)束語

圖4 參數(shù)敏感性分析比較圖

本文提出了一種基于核密度波動(dòng)的異常檢測(cè)算法。KDF算法具有很多優(yōu)勢(shì)：首先，運(yùn)用核密度波動(dòng)特征代替密度特征識(shí)別異常點(diǎn)。這一特征考慮異常點(diǎn)之間、異常點(diǎn)與正常點(diǎn)之間的特征關(guān)系，可以更好地描述數(shù)據(jù)中的動(dòng)態(tài)特征。其次，定義了核密度波動(dòng)因子概念，充分考慮數(shù)據(jù)點(diǎn)的局部特征和全局特征。經(jīng)過理論分析和實(shí)驗(yàn)結(jié)果分析表明：KDF算法具有更穩(wěn)定和準(zhǔn)確的檢測(cè)性能。在無監(jiān)督異常檢測(cè)任務(wù)中，有較好的應(yīng)用前景。未來將考慮進(jìn)一步擴(kuò)展KDF算法，使其更適用于高維大規(guī)模數(shù)據(jù)中。