基于核密度波動的異常檢測算法

張博文，劉 智，桑國明

大連海事大學 信息科學技術學院，遼寧 大連116026

異常檢測的目的是找出那些不同于預期的數據點，并嘗試找出與大多數數據表現模式有顯著差異的異常模式。異常檢測應用的領域包括：欺詐識別、故障診斷、異常基因檢測等[1]。

在實際檢測任務中，異常標簽的獲取往往需要花費極大的成本，異常檢測任務面對的待檢測數據往往是無標簽數據。因此設計科學有效的無監督異常檢測算法具有重要意義。

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

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

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

針對上述問題，本文提出一種魯棒的基于核密度波動的KDF（Kernel-Density Fluctuation factor）異常檢測算法。充分利用核密度估計的優勢，結合密度波動思想，定義了核密度波動因子KDF。在此基礎上進一步制定了檢測規則，在生成數據集和真實數據集中均可以提供準確且穩定的異常檢測性能。

1 KDF異常檢測算法原理

本文首先運用t-SNE算法對數據集進行特征提取，降低維數的同時保持數據原有的結構。然后創新性地提出可以綜合考慮鄰域內和鄰域外的密度波動的核密度波動因子KDF，據此檢測數據集中的異常點。

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

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

對于任意正整數k，數據點P的k-近鄰距離表示為d k(P)。d k(P)必須同時滿足以下兩個條件：

（1）數據集D中至少存在k個數據點Q∈D{P}滿足d(P,Q)≤d k(P)。

（2）數據集D中至多存在k-1個數據點Q∈D{P}滿足d(P,Q)＜d k(P)。

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

數據點P的k-近鄰區域N k(P)={Q|d(P,Q)≤d k(P),Q∈D{P}}。|N k(P)|表示數據點P的k-近鄰區域N k(P)中的元素個數。

定義1絕對核密度波動因子AKDF（Absolute Kernel-Density Fluctuation factor），如公式（2）：

對于數據集合N和數據點P的k-近鄰內的數據點集合N k(P)，運用集合內的點估計出P點的核密度值ρ(P)：

運用k-近鄰以外的數據點and，估計出的P點的核密度值ρ′(P)：

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

為方便數據可視化，本文運用二維的生成數據，分別對兩個變量進行一維核密度估計及可視化，其結果如圖1所示。以數據中一異常點的k-近鄰區域邊界為分界，將數據化分為兩部分，分別對其進行核密度估計。兩部分的核密度估計曲線如圖2。

圖1 二維生成數據核密度估計曲線

圖2 數據核密度估計曲線

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

目前常用異常檢測算法都著重于發現異常類型中的“點異常”，而當異常點聚集成一個簇時，這種聚類異常難以被發現。考慮到已有算法對集體異常點發現能力不足的問題，提出的AKDF可以很好地描述集體異常點的特征。若點P及N k(P)內的點均為異常點，即存在集體異常。此時ρ(P)較大，ρ′(P)較小，同樣有(ρ(P)-ρ′(P))2較大。

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

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

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

KDF綜合考慮數據點的局部和全局異常特征、點異常特征和集體異常特征，將RKDF和AKDF進行線性組合運算。λ1和λ2為相應權重，滿足λ1+λ2=1。在實際應用中，可以根據數據特點設置相應的權值，平衡局部特征、全局特征和集體特征間的關系，盡可能從多個角度發現潛在異常點。計算所得的KDF值越大，數據點為異常點的可能性越大。

2 KDF算法偽代碼

算法1 KDF算法

輸入：待測樣本的數據集合D，帶寬h，近鄰參數k

輸出：異常因子得分（KDFS），異常點集合O

1.對數據集D進行t-sne降維，D′=t-sne(D)

2.for each pointPinD′,do

5.計算AKDF(P)；

6.end for

7.for each pointPinD′,do

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

9.計算KDF(P)；

10.end for

11.for each pointPinD′,do

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

14.ifKDFS(P)＞1：

15.點P進入異常點集合O；

16.end if

17.end for

18.輸出異常點集合O

3 算法分析

3.1 參數穩定性分析

無監督異常檢測算法存在調優困難的問題，因此異常檢測算法的穩定性是算法分析中的一個重要因素。

3.1.1 近鄰參數k

近鄰參數k是近鄰學習的重要參數。近鄰算法常常敏感于k值的選擇。當k取值較小時，近似誤差減小，模型變得復雜，估計誤差增大，容易發生過擬合；選取的k值較大時，模型變得簡單，估計誤差會減小，近似誤差會增大，容易發生欠擬合。KDF算法同時考慮了數據點鄰域內外的核密度值差異，在理論上可以減小算法對近鄰參數k的敏感性。

3.1.2 核密度估計帶寬h

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

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

在KDF算法中，將數據點與其鄰域內點的KDF進行比較計算，盡可能弱化不同h值對最終檢測結果帶來的影響。

3.2 算法時間復雜度分析

由于涉及對每個點k-近鄰區域的搜索，為提高k-近鄰的搜索效率，可以考慮使用Kd樹的結構存儲訓練數據，以減少計算距離的次數。對于n個樣本，建立Kd樹后算法的時間復雜度達到O(2nlbn)。

4 實驗結果與結果分析

4.1 實驗數據集

為驗證KDF算法的性能，在生成數據集和真實數據集上進行了實驗。生成數據集中正常樣本點服從二維標準正態分布，異常點數據一個維度服從參數為（2，0.5）的伽馬分布，另一個維度為服從參數為1.5的指數分布。選取的真實數據集為Wine數據集和Banknote數據集。Wine數據集中，類別3視為異常點類。Banknote數據集中，類別1視為異常點類；實驗數據集的詳細信息描述如表1所示。

表1 實驗數據集信息表

4.2 實驗設計

實驗中的對比算法包括LOF算法[2]、KNN算法[15]、LOCI算法[3]和KDOF算法[13]。算法中權重設置為λ1=λ2=0.5。

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

4.3 評價指標

本文運用了兩個模型性能評價指標[16]，從不同角度評價算法的性能。

4.3.1 基于異常評分的排序準確率

無監督異常檢測算法往往對最為異常的一部分數據進行報警。對數據點所得的異常評分KDFS（Kernel-Density Fluctuation factor Score）進行降序排序，選擇前5、10、20個點計算其檢測準確率。這一指標可以度量算法所得異常評分的合理性，同時又減少單純計算準確率對判決閾值的依賴。

4.3.2 F1值

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

4.4 實驗結果

實驗算法中近鄰參數k=10，KDF算法和KDOF算法中核密度估計帶寬h=0.5。

從表2中可以看出，KDF算法在三個實驗數據集均取得了很好的結果，排序準確率在大多數情況下明顯高于其他對比算法。運用定義的KDF來檢測數據集中的異常點具有科學性。

表2 算法異常得分排序準確率比較表

如圖3所示，在三個實驗數據集上，KDF算法的F1值均高于其他對比算法。實驗結果說明提出的方法可以更全面準確地檢測異常點。

圖3 不同算法的F1值比較

4.5 參數的敏感性分析

4.5.1 近鄰參數k

對算法在不同k值下，在三個數據集中得到的F1值取平均值，與對比算法結果進行比較。

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

4.5.2 帶寬h

本文通過設置不同的帶寬h值，對比KDF算法與KDOF算法在三個數據集上F1的平均值。

圖4（b）圖中顯示：和KDOF算法相比，KDF算法在數據集中計算得到的F1值未出現明顯波動。h值的變動并不會給最終的檢測結果帶來較大的影響。因此算法可以提供穩定的檢測結果。

5 結束語

圖4 參數敏感性分析比較圖

本文提出了一種基于核密度波動的異常檢測算法。KDF算法具有很多優勢：首先，運用核密度波動特征代替密度特征識別異常點。這一特征考慮異常點之間、異常點與正常點之間的特征關系，可以更好地描述數據中的動態特征。其次，定義了核密度波動因子概念，充分考慮數據點的局部特征和全局特征。經過理論分析和實驗結果分析表明：KDF算法具有更穩定和準確的檢測性能。在無監督異常檢測任務中，有較好的應用前景。未來將考慮進一步擴展KDF算法，使其更適用于高維大規模數據中。