吳金娥， 王若愚， 段倩倩， 李國強, ， 琚長江

(1. 上海工程技術大學 電子電氣工程學院， 上海 201600； 2. 上海交通大學 軟件學院， 上海 200240)

異常檢測技術通過對事物產生的數據進行分析和挖掘，能有效及時地發(fā)現事物中的異常數據，有利于預防和制止損失的產生.隨著該技術的發(fā)展與成熟，已被廣泛應用于網絡安全、金融、醫(yī)療健康、國防軍事等多個領域[1].根據待檢測數據有無標簽可將異常檢測算法分為監(jiān)督[2]、半監(jiān)督[3]和無監(jiān)督[4]；依據異常類型的不同又可分為點異常、上下文異常和群異常[5].現有的技術大多是在有數據標簽的情況下研究單個點的異常，而現實生活中的部分異常只能從無數據標簽的群數據中挖掘出來.

監(jiān)督或半監(jiān)督的異常檢測技術依賴于數據集所提供的帶數據標簽的正常和異常數據，該方法利用已知正常和異常數據訓練模型[6]，通過觀察待測數據的數據模型與帶標簽數據訓練出的模型之間的符合程度判別是否異常.而當待檢測的數據集無已知正?；虍惓祿?，如網絡新型攻擊發(fā)生時，使用監(jiān)督式方法并不能檢測出該異常.而在異常檢測技術領域中，高檢測率是該領域追求的最終目標，漏報和誤報作為影響算法效率的根本原因，也是目前異常檢測算法中普遍存在的問題.減少漏報和誤報可以提升算法性能，對現實領域的應用具有重大意義.

異常或離群值指的是與正常數據有顯著差異的數據點.早在19世紀，關于離群值問題就被統(tǒng)計學界提出并研究[7].直至2000年，Knorr等[8]提出基于距離的異常檢測方法，掀起了異常檢測技術的發(fā)展高潮.在關于群數據的異常檢測中，Lee等[9]提出的基于分段檢測的軌跡離群點檢測 (TRAOD)框架可有效檢測出異常的子軌跡.Luan等[10]在傳統(tǒng)TRAOD算法的基礎上，結合文獻[9]中提出的分割檢測框架提出一種基于局部密度的軌跡離群算法.Djenouri等[11]提出在給定時間間隔中同時考慮時間和空間因素建立的流量分布概率數據庫，結合基于距離的k近鄰(kNN)算法檢測交通流數據的異常.毛江云等[12]提出通過Markov決策過程實現異常車輛的軌跡檢測，該算法分為預處理、離線訓練模型和在線檢測異常3個階段.Wang等[13]提出一套基于統(tǒng)計距離的群數據異常檢測技術，該技術以已知的正常群數據和異常群數據作為參照系，使用動態(tài)更新閾值法對待檢測群數據進行異常判別.通過淘寶交易刷信譽的真實數據集進行大量實驗，實驗結果證明該監(jiān)督式方法可有效識別出異常.

本文的主要創(chuàng)新點在于：① 為解決無數據標簽的群數據異常檢測問題，提出一種基于k近鄰算法的無監(jiān)督式異常檢測算法；② 為減少算法的漏報、誤報率，提出使用反向k近鄰(RkNN)算法過濾異常值，優(yōu)化算法性能；③ 相比于文獻[13]，本文解決了在無監(jiān)督模式下對異常群數據的檢測問題，并優(yōu)化了kNN算法的檢測質量.

1 相關技術

1.1 相似性度量

相似性度量指的是兩個事物間相似程度的一種度量方式.使用統(tǒng)計距離作為不同集群數據間的相似性度量.統(tǒng)計距離度量的是兩個群數據在數據分布上的差異，常見的統(tǒng)計距離有相對熵，又被稱為Kullback-Leibler散度(KLD)或信息散度[14]，該距離度量方式不具有對稱性，而Jensen-Shannon散度(JSD)[15]作為相對熵的優(yōu)化計算方式具有對稱性.在實驗中選用具有對稱性的JSD作為衡量兩個群數據間差異的相似性度量.但當出現兩個數據分布完全不重疊的極端情況時，JSD不再適用.為此，考慮將集群數據以特定形式引入歐式空間中進行異常檢測.對本文中使用到的距離度量方式進行如下定義.

g、l分別表示待檢測數據集C中的任意兩個群數據，g、l間的距離可記為d(g,l).當相似性度量為JSD距離度量方式時，g、l間的距離表達式如下：

d(g,l)=JSD(G‖L)

(1)

式中：G、L分別為g和l的概率分布.KLD的距離表達方式如下：

(2)

式中：G(z)、L(z)為離散變量.G、L間JSD值的計算方式為

(3)

當使用歐式距離作為相似性度量時，g、l間的距離表達式則為

d(g,l)=E(X,Y)

(4)

式中：X、Y分別為g、l各自在24 h中每小時銷售統(tǒng)計量構成的24維向量；E(X,Y)為X、Y間的歐式距離.具體定義如下：

(5)

1.2 k近鄰與反向k近鄰

k近鄰算法[16]是最簡單的機器學習算法之一，最開始被用于求解分類問題[17].隨著異常檢測技術的發(fā)展，該算法被應用于異常檢測中，其判別異常的步驟如下：對每個待測樣本求得其k個最近鄰的集合，再求得每個樣本到各自k個最近鄰的平均距離，將平均距離表示為該樣本的異常得分，異常得分越高表示該樣本越異常[18].本文使用該算法求得每個群數據的異常得分后，為了更好地反映不同集群間的差異，使用每個集群到各自k個最近鄰的距離總和作為異常得分.g的k個最近鄰集合可記作Nk(g)，則有：

Nk(g)={l|d(g,l)≤dk(g),

l∈{C-{g}}}

(6)

式中：dk(g)為g的k個最近鄰.綜合以上定義，待測集群g的異常得分定義如下：

(7)

由于在計算k個最近鄰時，不可避免地會受到異常值之間的相互干擾，提出使用反向k近鄰法[19]過濾互相干擾的情況.關于反向k近鄰的定義如下：

Qk(g)={l|g∈Nk(l),l∈C}

(8)

式中：Qk(g)為g的k個反向最近鄰的集合；Nk(l)為l的k個最近鄰的集合.

2 反向k近鄰過濾異常的群數據異常檢測

2.1 模型建立

無監(jiān)督方式下的數據異常檢測對數據集的要求較低.當待檢測的異常為新發(fā)生的異常時，由于缺少先驗知識，有監(jiān)督的算法并不能實現檢測，而無監(jiān)督方式可直接對數據集進行建模，從而檢測出異常.針對k近鄰算法在檢測異常時存在的誤報和漏報問題，提出使用反向k近鄰法對該算法進行優(yōu)化，以提升算法的檢測效果.模型包括3個部分：① 數據預處理模塊；② 初步異常檢測模塊；③ 算法優(yōu)化模塊.各模塊部分的功能簡述如下：

(1) 數據預處理模塊.將待測數據集劃分成多個集群數據，以方便算法的實施.

(2) 初步異常檢測模塊.對輸入的多個集群數據使用k近鄰算法實現無監(jiān)督式的群數據異常檢測，獲得初步異常群數據.

該模塊首先計算兩兩集群之間的距離，建立起距離權圖；再計算每個集群的k個最近鄰的距離之和作為該集群的異常得分；最后將異常得分最高的前m個集群Sm作為初始異常輸出到算法優(yōu)化模塊.

(3) 算法優(yōu)化模塊.對輸入的異常群數據，使用反向k近鄰法進行過濾，獲得優(yōu)化后的異常群數據.

由于k近鄰算法在計算集群的k個最近鄰時存在異常集群和正常集群之間相互干擾的問題，導致檢測結果存在漏報和誤報.為解決這個問題，該模塊提出使用反向k近鄰算法對初始異常集群進行反向過濾.首先查找每個異常集群的反向k近鄰；再對其中的正常集群更新k近鄰，使異常集群不包含在其k近鄰中；最后重新計算異常得分，更新異常集群.重復該操作直至最終輸出的異常集群的反向k近鄰中不再包含正常集群.

根據以上3個模塊的功能簡述，所建立的算法模型如圖1所示.

圖1 模型建立流程圖Fig.1 Flow chart of model establishment

2.2 基于k近鄰的群數據異常檢測

2.2.1JSD相似性度量下的群數據異常檢測 在處理無數據標簽的數據集時，無法從數據集本身的建模判別異常集群，而建立全局的距離權圖有助于解決異常集群的識別問題.利用所建立的距離權圖，使用k近鄰算法求得每個集群的異常得分，根據異常得分識別異常數據.集群數據之間的差異可以很好地體現在數據分布的差異性上，而統(tǒng)計距離能較好地捕捉不同群數據間的分布差異，因此使用JSD距離度量方式計算兩兩集群間的距離.為更好地反映集群間的差異性，將待測集群與其k個最近鄰集群間的距離之和作為該集群的異常得分，最后輸出異常得分排序列表的前m個集群作為異常值，即輸出Sm.根據以上分析，基于k近鄰算法的統(tǒng)計分布檢測(SDD-kNN)算法的偽代碼如算法1所示.

算法1SDD-kNN

輸入數據集C={c1,c2,…,cn}，近鄰的數量為k

輸出Sm

(1)M←n×n空矩陣

(2) fori←1 tondo

(3)Gi←ci的概率分布

(4) end for

(5) fori←1 tondo

(6) forj←1 tondo

(7)Mij←JSD(Gi‖Gj)

(8) end for

(9) end for

(10) fori←1 tondo

(11)α(ci)←M的第i行前k+1個最小元素和

(12) end for

(13)S←對所有集群按α(ci)值進行降序排列

(14)Sm←S中前m個集群

(15) returnSm

2.2.2歐式距離的應用 當兩個集群的概率分布G和L完全沒有重疊的極端情況發(fā)生時，JSD不再適用.通過比較式(3)和(5)可以發(fā)現，歐式距離對數據的變化更為敏感，因此可將待檢測數據集映射到歐式空間中，使用歐式距離作為兩兩集群間的相似性度量.由于實驗數據是淘寶交易數據，所以將待檢測數據集按天劃分為不同的集群數據，將每天24 h的交易量作為歐式距離的24維向量，由此來計算不同集群間的差異.統(tǒng)計日交易數據分布直方圖如圖2所示.其中：H為不同時間點；V為銷售量.

圖2 日交易數據分布直方圖(第156天)Fig.2 Distribution histogram of daily trading data (156th day )

2.3 基于反向k近鄰的過濾法

漏報和誤報是異常檢測算法普遍存在的問題，產生漏報和誤報的情況有兩種，一種是算法本身存在局限性，不能準確識別出部分異常集群；另一個原因是在計算k近鄰時產生的誤差.在SDD-kNN算法中，造成誤差的原因是異常值與正常值之間的相互干擾，導致異常集群被誤判為正常集群.

SDD-kNN算法之所以能有效檢測出異常，這依賴于異常集群與正常集群之間的距離較大，而正常集群之間的距離則相對較小，所以異常集群相對于正常集群而言有更高的異常得分.假設集群g的Nk(g)中包含另一個甚至幾個其他異常集群，此時α(g)將會變低，當該值小于噪聲點或處于異常邊緣的正常集群的異常得分時，g則被誤判為正常，而噪聲點或處于異常邊緣的正常集群被宣布為異常，由此導致算法的誤報和漏報率上升.

為解決由上述原因產生的誤報和漏報問題，對算法初步輸出的異常值使用反向k近鄰法進行過濾，從而提升算法的性能.反向分析上述問題產生的原因，如果算法判別為正常集群的k個最近鄰中包含判別為異常的集群，那么該正常集群很有可能是受其他異常集群的干擾而被誤判的.所以在該方法中應首先找到初步輸出的異常集群的反向k近鄰，對反向k近鄰中被初步識別為正常的集群重新計算k近鄰，且該k近鄰不再包含已知的異常集群.然后再重新計算異常得分，更新Sm，并重復上述步驟.直至Sm中集群的反向k近鄰中不再包含正常集群.根據上述分析，反向k近鄰過濾異常算法的偽代碼如算法2所示.

算法2反向k近鄰過濾異常法

輸入數據集C={c1,c2,…,cn}，初步輸出的異常集合θ，近鄰的數量為k

輸出Sm

(1) forci∈θdo

(2) forcj∈Qk(ci)do

(3) ifcj?θ

(4)Nk(cj)={cb|d(cj,cb)≤dk(cj),cb∈{C-{ci,cj}}}

(6) end for

(7) end for

(8)S←對所有集群按α(ci)值進行降序排列

(9)Sm←S中前m個集群

(10) returnSm

3 實驗及其結果分析

3.1 數據集介紹

選取文獻[13]在實驗中使用的數據集，該數據集的正常交易數據來自于阿里巴巴天池大數據競賽.提取編號為 1 629 的賣家交易史，記錄時間為2015-11-11～2016-10-31，以天為單位將數據集劃分成325個集群.關于該數據集的詳細描述如圖3所示.

圖3 數據集介紹Fig.3 Data set introduction

由圖3可見，口碑數據集中描述了集中式刷信譽和均衡式刷信譽兩種不同的刷信譽模式，這兩種模式下的數據是模擬不同刷信譽行為生成的.由于原始數據集只記錄了交易成交時間點的小時記錄數，所以引入了增強數據集，該數據集添加了時分秒的時間戳.在檢測算法性能時，待測數據集由異常群數據中的異常集群替換正常數據中的正常集群，從而組成待測數據集.

3.2 實驗結果評價指標介紹

在異常檢測問題中，正確率作為直觀的評價指標之一，通常被用于度量算法的性能.然而，當異常數據較少時，盡管算法未檢測出任何異常，該算法表現出的正確率仍然會很高.因此，除了正確率A之外，還引入假陽率η、精度P、召回率R、綜合評價指標F以及運行時間t作為衡量算法有效性的指標.

(1) 正確率：指預測正確的集群個數在待測數據集中的占比， 該值越大，則代表算法性能越好，

(9)

式中：FP為將正常集群誤判為異常的數量；TN為正常集群被正確判斷的數量；TP為異常集群被正確判別為異常的數量；FN為異常集群被錯判為正常的數量.

(2) 假陽率：指正常集群中被預測為異常的比例，該值越小，則代表算法性能越好，

(10)

(3) 精度：指在預測為異常的集群中真實異常的占比，即

(11)

(4) 召回率：指預測為異常的集群占總真實異常的比例，即

(12)

(5) 綜合評價指標：該指標是P和R的加權調和平均，其計算公式如下：

(13)

式中：β為參數，此處取β=1，此時將綜合評價指標記作F1值，即上式變?yōu)?/p>

(14)

隨著F1值的升高，算法性能也越來越好.

(6) 運行時間：該項指標記錄的是算法完成檢測所需的時間，該指標越小，則代表算法性能越好.

3.3 實驗分析

實驗1k值的選擇.由于kNN算法的檢測結果在很大程度上受到k值的影響，所以合理地選擇k值是保證實驗檢測效率的條件之一.實驗數據集由正常交易數據混合不同數目的集中式刷信譽數據構成.采用單變量控制法，檢測在不同異常概率下k值對最終決策的影響，檢測結果如圖4所示，其中U為異常概率.

由圖4可見，k值對算法的檢測結果有較大的影響.隨著k值的增大，F1值呈上升趨勢并逐漸趨于平穩(wěn).當k值較小時，噪聲點不易與異常值區(qū)分，導致較低的檢測率.因此，當k逐漸增大時，可以獲得與待測集群數據更多的相關信息，使噪聲點與異常值的異常得分差距增大，算法性能得到提升.

圖4 k值對檢測結果的影響Fig.4 Influence of k values on test results

比較圖4(a)和(b)可見，在歐式距離相似性度量方式下算法性能比JSD距離度量方式下提升得更快.這是由于歐式距離對微小的變化更敏感，在k值較小的情況下也能有效區(qū)別噪聲和異常.

實驗2反向過濾干擾值的有效性驗證.由于kNN算法在檢測異常時存在一定的漏報和誤報，為減少由于數據間相互干擾帶來的誤報和漏報率，使用RkNN算法對kNN算法進行優(yōu)化.在該組實驗中，對反向過濾干擾值方法的有效性進行驗證，對兩種不同距離度量方式下的算法分別應用該方法.實驗數據集由兩種不同刷信譽行為下的數據隨機替換正常交易數據集中20%的正常數據組成.使用反向k近鄰過濾方法下的統(tǒng)計檢測方法記作SDD-RkNN；歐式距離度量方式下的基于距離的檢測方式記為DBD-kNN；歐式距離度量方式下的基于反向k近鄰過濾法的檢測方式記為DBD-RkNN；W為各項評價指標的百分比.

由圖5可見，A與F1值在SDD-RkNN和DBD-RkNN方法下分別比SDD-kNN和DBD-kNN方法下具有更高的值，同時具有更低的η值.由此可見，無論是在集中式還是在均衡式刷信譽方式下，反向過濾異常干擾方法均能有效提升算法的檢測性能，評價指標η、A和F1值均得到了約1%的提升.

由圖6(a)可見，使用了反向k近鄰法優(yōu)化算法的SDD-RkNN和DBD-RkNN方法在增強數據集

下集中式刷信譽模式的檢測性能評測指標η、A和F1值相比于直接使用k近鄰算法有所提升.由圖6(b)可知，DBD-RkNN方法下的3項性能評價指標均無提升，因此當相似性度量為歐式距離時，對均衡式刷信譽模式應用反向k近鄰法并不能提升算法性能，甚至會對原始算法的性能有微小的降低，增強數據集中隨機生成的時間戳是導致該情況發(fā)生的原因之一.

綜合而言，使用RkNN算法對異常值之間互相干擾的情況進行優(yōu)化的算法能有效提高SDD-kNN和DBD-kNN算法的檢測效果.

實驗3算法性能對比.綜合上述實驗，基于反向k近鄰的優(yōu)化算法能夠對kNN算法的檢測結果進行優(yōu)化，為進一步驗證算法的優(yōu)越性，將SDD-RkNN、DBD-RkNN算法與帶證據集的動態(tài)統(tǒng)計檢測(DSDD-E)算法[13]進行性能比較.為更好地檢測均衡式刷信譽的方式引入二階直方圖技術，實驗結果如表1和2所示.

圖5 反向過濾干擾值法在原始數據集下實驗結果Fig.5 Experimental results of reverse filtering interference value method in original data set

圖6 反向過濾干擾值法在增強數據集下實驗結果Fig.6 Experimental results of reverse filtering interference value method in enhanced data set

表1 原始數據集下的算法性能對比Tab.1 Comparison of algorithm performance in raw data set

表2 增強數據集下的算法性能對比Tab.2 Comparison of algorithm performance in enhanced data set

由表1可知，集中式刷信譽模式下最好的F1值可達到99.69%，而均衡式刷信譽模式下最高的F1值為80.92%.由表2可知，集中式刷信譽模式下的最優(yōu)F1值可達到96.30%，而均衡式刷信譽模式下最高的F1值為81.85%.因此，集中式刷信譽模式比均衡式刷信譽模式更易于檢測.這是由于集中式刷信譽模式下異常集群的數據分布明顯區(qū)別于正常集群，所以異常集群具有較高的異常得分.均衡式刷信譽模式由于異常集群與正常集群的數據分布比較相似而較難檢測.盡管如此，在一階直方圖下，從表1和2的均衡式刷信譽模式中可見，SDD-RkNN方法下的F1值分別從20.92%、16.92%提升至DBD-RkNN方法下的79.38%與81.85%.可見，對微小變化敏感的歐式距離仍然可以較好地識別均衡式刷信譽模式下的異常集體.均衡式刷信譽模式中，SDD-RkNN方法在一階和二階直方圖下的F1值分別從20.92%、16.92%提升至80.92%以及79.69%.由此可見，二階直方圖技術的應用有利于發(fā)現均衡式異常.這是由于二階直方圖的技術通過改變數據分布放大了異常集體與正常集體的分布差異導致的.

對明顯區(qū)別于正常集群的集中式異常的檢測，由表1的集中式刷信譽模式可見，使用DSDD-E算法時F1值為87.99%，使用DBD-RkNN算法后F1值可達到99.69%.同時，由表1其余內容可見，所提算法的P、R和F1值均優(yōu)于DSDD-E算法.這是由于DSDD-E算法計算的是局部差異，而SDD-RkNN和DBD-RkNN算法是與待測數據集進行全局數據的差異比較，能夠獲得更準確的信息.所以與DSDD-E算法相比，所提算法的性能更優(yōu).所提算法在建立全局距離權圖時，需要計算每兩個集群之間的距離，時間復雜度為O(n2)，算法的時間資源消耗較高.SDD-RkNN算法性能與DBD-RkNN算法性能幾乎一樣優(yōu)秀，但歐式距離的度量方式比JSD方式節(jié)省了一半的時間資源，這是由兩種不同相似性度量計算方式帶來的差異.

實驗4算法穩(wěn)定性分析.穩(wěn)定性是評價算法性能的重要指標之一，為更好地觀察算法的穩(wěn)定性，取不同的U對算法的穩(wěn)定性進行分析.實驗數據集由正常交易數據集依次替換不同數目、不同刷信譽模式的異常集群構成.考慮到實際生活中異常出現的概率一般不會超過數據集的總量一半，因此分別取U=10%、20%、30%、40%、50%進行不同衡量指標的檢測.對于不能很好地識別出均衡式刷信譽的算法使用二階技術進行檢測.實驗結果如圖7所示.

圖7 不同異常概率下，3種算法的穩(wěn)定性對比Fig.7 Comparison of stability of three algorithms under different anomaly probabilities

由圖7可知，對于A和F1值這兩項評價指標，越平穩(wěn)的接近圖正上方，則算法性能越穩(wěn)定.SDD-RkNN算法和DBD-RkNN算法的性能評價指標折線圖比DSDD-E算法的性能評價指標折線圖更接近圖的正上方，故所提算法具有更高的穩(wěn)定性和更好的性能.由圖7(d)可知，DSDD-E算法的F1值在不同異常概率下明顯偏離SDD-RkNN算法和DBD-RkNN算法的F1值，這是由于SDD-RkNN算法和DBD-RkNN算法總是通過全局比較獲得異常得分，因此異常比例對該算法的影響較小.而DSDD-E算法依賴于數據分布估計的準確性，在使用二階技術時，直方圖變得粗糙，因此該算法的檢測性能明顯較差.

4 結語

本文提出一種無監(jiān)督式的基于反向k近鄰法的群數據異常檢測算法.對無數據標簽的數據集進行集體數據的劃分，直接建立模型檢測異常.根據集群數據的分布相似性，使用JSD作為k近鄰算法在求取異常得分時的距離度量，針對異常值之間相互干擾的問題提出使用反向k近鄰對異常值進行過濾，優(yōu)化算法性能.

通過大量對比實驗可見，基于反向k近鄰過濾異常值的方法能有效提高kNN算法的檢測質量.歐式距離對微小變化足夠敏感，因此在不使用二階直方圖的技術下也能較好地識別出均衡式刷信譽模式.在二階技術的使用下，SDD-RkNN算法能較好地識別出此異常，同時該算法具有較強的穩(wěn)定性.通過與引入的DSDD-E算法的對比，所提的SDD-RkNN算法能更好地識別出異常，可應用于相關數據資源的檢測和篩選中.