k最近鄰流序列算法對異常流檢測的優化研究*

劉 云，王梓宇

(昆明理工大學信息工程與自動化學院，云南 昆明 650500)

1 引言

時空數據包含了與時空維度有關的信息[1]，時空異常檢測是時空數據挖掘的一個研究方向[2,3]。隨著網絡和傳感器的普及，時空數據呈現指數級增長，數據流在城市交通數據中較為常見。異常的流值由現實中的某些情況(如過飽和條件[4]和交通擁堵[5])引發，為了發現這些異常值所代表的異常行為，檢測城市交通數據中的異常流受到廣泛關注[6]。

目前研究人員已經提出了一些用于城市交通流數據的異常檢測方法，根據研究內容不同這些方法可以分為統計方法、基于相似度的方法和基于頻繁模式挖掘的方法。統計方法使用統計模型(如高斯聚合模型[7]、狄利克雷過程混合模型[8])或諸如主成分分析[9]、隨機梯度下降[10]等技術假設正常流遵循某種常規統計過程，而偏離該統計機制的流則視為異常。基于相似度的方法使用距離度量和鄰域計算方法或者經典的異常值檢測方法[11]來檢測異常值。通常情況下，正常的流假定構建密集區域而異常流假定構建低密度區域。基于頻繁模式挖掘的方法通過使用諸如Apriori[12]或FP-growth[13]之類的技術來發現異常值之間的關聯關系。

相較于檢測單個的異常流，檢測異常流分布是另一個重要的研究方向[1]。由于基于相似度的方法不考慮流數據之間的相關性而僅適用于檢測單個異常流，因此，統計方法是檢測異常流分布的一種常用方法。Ngan等人[14]使用一個狄利克雷過程混合模型DPMM(Dirichlet Process Mixture Model)來推導城市交通流數據中的異常值。首先將所有流值的集合F={f1,f2,…,f|F|}映射到一個n維協方差信號描述符中，其中第i個對象由流值{fi,…,fi+n-1}定義，隨后通過主成分分析將得到的維度縮小為二維，最后用一個塌陷吉布斯采樣器檢測流數據中的異常值。由于塌陷吉布斯采樣器在大規模數據上的低效率和輸出不穩定，使用DPMM的算法(以下稱為DPMM算法)有一定的局限性。Ye等人[15]提出了一種稱為同時估計流量矩陣并檢測異常SETMADA(Simultaneously Estimate Traffic Matrix And Detect Anomaly)的容錯流量矩陣估計算法。首先利用流量矩陣的先驗低秩屬性和時間特性，將流量矩陣異常估計公式轉化為一個先驗信息引導矩陣完成PigMaC(Prior information guided Matrix Completion)問題，通過采用多塊交替方向乘子法ADMM(Alternating Direction Method of Multipliers)以及隨機近端梯度下降法來解決該問題，從而實現流量矩陣的異常估計。該算法在估計缺失值時需要考慮很多先驗信息，然而在許多領域中先驗參數模型是未知的，因此該算法的應用場景有一定的局限性。

為了提高從流序列中檢測異常流分布的速度和精度，本文提出了k最近鄰流序列算法kNNFS(kNearest Neighbor for Flow Sequence)。算法首先確定每個位置處需要測定的時間區間并計算每個時間區間內的單個流觀測值；隨后每個時間區間的流分布概率FDP(Flow Distribution Probability)庫通過計算單個流的觀測頻率構建得到；最后使用KL散度計算新的流分布概率與其k最近鄰之間的距離，由閾值判定該流分布概率是否異常，如距離值小于閾值則更新入歷史流分布概率庫，否則作為異常的流分布提取出來。仿真結果表明，與DPMM算法和SETMADA算法相比，kNNFS算法在精度和運行時間方面均有優化提升。

2 模型

城市特定位置處的交通流通過計算一個時間區間內的對象(汽車、出租車和公共汽車等)數量得到[16,17]。交通流數據通常基于某一特定位置在時間區間內表現出某種特定的分布，因此，區別于從交通流的時間序列中檢測某一時間區間內的單個異常流，從流序列中檢測出的異常流分布更能代表對某段時間區間內總體交通行為產生影響的異常情況。

為了從大規模的城市交通數據中準確快速檢測出異常流分布，本文構建了流分布概率這一模型。把流分布概率視為對流及其概率的序列，流值為某個位置處確定時間區間內的對象數，通過構建流分布概率庫并使用異常值檢測方法計算流分布概率之間的距離。在面對大規模的城市交通數據時，相較檢測單個異常流的方法，對流分布概率進行異常檢測能極大減少算法的運行時間。同時，通過把檢測到的非異常的流分布概率更新入歷史流數據庫可以不斷提高算法的檢測精度。k最近鄰流序列檢測算法框架如圖1所示，包括如下2個部分：

Figure 1 Framework for flow sequences detection algorithm

(2)異常值的檢測：獨立使用歷史流分布概率從流式傳輸的新的流分布中檢測異常值。如果新數據不是異常數據，將其更新入歷史流分布概率庫中，否則將其提取出以待進一步分析。

3 kNNFS算法

3.1 算法推導

算法輸入為時空交通流TF，包含時間、位置和交通流值等信息。基于交通流中的位置信息把TF依據位置劃分為不同位置處交通流的集合TF={TF1,…,TFn}，上述所有n個位置由位置集合L={L1,…,Ln}表示，TFi是與對應位置Li相關的交通流信息。

(1)

(l-1))),(Tj-1+(TFOi×l))]}

(2)

(3)

(4)

(5)

(6)

將得到的所有時間區間的流分布概率組成集合，從而構成位置Li處的流分布概率庫FDPi：

(7)

(8)

(9)

(10)

最后，用KL散度計算這2個流分布概率之間的距離相似度，如式(11)所示：

(11)

算法1kNNFS算法

1forj=1 tordo

3endfor

4d←kNN(dist);

5ifd≤εthen

6Anomaly←false

7else

8Anomaly←true

9endif

10returnAnomaly

3.2 算法分析

算法1的理論復雜度分為FDP構建復雜度和異常值檢測復雜度2部分：

因此，本文所提算法的理論復雜度為：

(12)

其中n為位置Li的數量。

4 仿真分析

4.1 評價指標

為評估kNNFS算法的精度和運行時間，本文在1個中小型交通數據集和1個大型交通數據集上把該算法與其他基準算法進行仿真對比分析。首先在中小型交通數據集上分析比較kNNFS算法、SETMADA算法和DPMM算法檢測到異常值的百分比，通過百分比的大小初步說明kNNFS算法的可行性與精度；隨后在大型交通數據集上分析比較kNNFS算法與基準算法SETMADA和DPMM的精度和運行時間。本文使用F值來對3種算法進行精度對比分析：

(13)

(14)

(15)

其中，TP表示正確判屬異常流的數量，FP表示錯誤判屬異常流的數量，FN表示錯誤判定為非異常流的數量。

4.2 數據集

其他類似算法所采用的標準數據集一致，本文依據1個中小型數據集和1個大型數據集來評估算法的性能。第1個中小型數據集是于2017年1月1日至2017年9月30日間在丹麥歐登塞市的7個位置處觀測到的真實交通流[20]，數據集概要如表1所示。數據包括在特定位置處檢測的車輛的位置、日期時間和速度等信息。位置由經緯度表示；日期時間由汽車經過指定位置的年、月、日、時、分、秒表示，格式為YYYY-MM-DD hh:mm:ss；速度以km/h計算。

第2個大型數據集是在2009年的2個月時間內于中國北京的同一位置處觀測到的9億多個真實城市交通流數據[21]。觀測到每臺車輛的重要信息包括日期和時間，由汽車經過指定位置的年、月、日、時、分、秒表示，格式為YYYY-MM-DD hh:mm:ss。

Table 1 Feature description of the dataset from Odense Denmark

4.3 歐登塞市數據的仿真結果

從圖2中可以看出，在丹麥歐登塞市的7個位置處,kNNFS算法、SETMADA算法和DPMM算法檢測到的異常值的百分比均高于70%。在非密集型位置L1、L2、L3和L4處,kNNFS算法和SETMADA算法以及DPMM算法檢測到的異常值的百分比均在75%附近；在密集型位置L5、L6和L7處，可以看出kNNFS算法檢測到的異常值的百分比在85%附近，明顯高于SETMADA算法和DPMM算法的。

Figure 2 Percentage of detected outliers at different locations

可見，kNNFS算法、SETMADA算法和DPMM算法均適用于在中小型交通數據集中檢測異常值。對于非密集型位置，kNNFS算法的精度與SETMADA算法和DPMM算法的相當；對于密集型位置，kNNFS算法的精度較SETMADA算法和DPMM算法有明顯提升。上述提升得益于kNNFS算法采用的KL散度距離更適用于計算分布之間的相似度，同時本文提出的算法把新的非異常FDP更新入歷史FDP庫，有利于提高檢測異常值的精度，并且在數據較密集(數據集規模較大)時這種提升效果更為明顯。

4.4 北京市數據的仿真結果

從圖3中可以看出，在大型交通數據集上仿真時，隨著流量值從4億逐漸增加至9億，kNNFS算法的F值逐漸升高，而SETMADA算法和DPMM算法的F值逐漸降低。同時，不論流量值為4億～9億間的何值，除取值4億時3種算法的F值均近似于0.8以外，其余取值時kNNFS算法的F值都明顯高于SETMADA算法和DPMM算法的。其中，當流量值為最大9億時,kNNFS算法的F值高于0.9，明顯優于SETMADA算法和DPMM算法的0.7附近的水平。

Figure 3 F-measure on different numbers of flow data

可見，當流量值大于4億時，kNNFS算法的精度明顯高于SETMADA算法和DPMM算法的。上述差異的原因在于，隨著大型交通數據集中流量值逐漸增大，算法計算的樣本數量逐漸增多，由于kNNFS算法將新的非異常FDP更新入歷史FDP庫，其精度會逐漸升高，而SETMADA算法和DPMM算法由于計算量過于巨大，其精度反而逐漸降低。

從圖4中可以看出，在大型交通數據集上仿真時，隨著流量值從4億逐漸增加至9億，3種算法的運行時間都逐漸增加。不論流量值為4億～9億間的何值，kNNFS算法的運行時間都明顯少于SETMADA算法和DPMM算法的。其中，當流量值為4億時，kNNFS算法的運行時間在1 500 s附近，明顯低于SETMADA算法的1 800 s附近以及DPMM算法的2 000 s附近的水平；當流量值為9億時，kNNFS算法的運行時間在2 000 s附近，明顯低于SETMADA算法的2 500 s附近以及DPMM算法的3 000 s附近的水平。

Figure 4 Runtime on different number of flow data

可見，在大型交通數據集上,kNNFS算法由于使用了FDP庫，其運算速度明顯優于SETMADA算法和DPMM算法的。進一步分析得出，當流量值從4億增加至9億時，流量增加了1.25倍，kNNFS算法的運行時間增加了33%，而SETMADA算法運行時間增加了39%,DPMM算法運行時間增加了50%。因此，隨著流量值逐漸增加，kNNFS算法運行時間的增加幅度也要小于SETMADA算法和DPMM算法的。

5 結束語

為了提高檢測流序列中的異常流分布的速度和精度，本文提出了k最近鄰流序列算法(kNNFS)。劃分時間區間后為每個位置測定每個時間區間內的單個流觀測值，通過計算單個流的觀測次數和頻率構建流分布概率(FDP)庫，隨后由KL散度計算新輸入的流分布概率與其k最近鄰之間的距離，最后由閾值判定新的流分布概率是否異常，距離值小于閾值則更新入歷史流分布概率庫，否則為異常值。仿真結果表明，kNNFS算法在精度和運行時間方面均有優化提升。由于使用了k最近鄰，算法對鄰域數量和挖掘閾值敏感，為這2個參數選擇合適的值對算法的精度至關重要。下一步工作的主要方向是消除參數使用的估計偏差來提高算法的檢測性能。