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

劉 云，王梓宇

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

1 引言

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

目前研究人員已經(jīng)提出了一些用于城市交通流數(shù)據(jù)的異常檢測方法，根據(jù)研究內(nèi)容不同這些方法可以分為統(tǒng)計方法、基于相似度的方法和基于頻繁模式挖掘的方法。統(tǒng)計方法使用統(tǒng)計模型(如高斯聚合模型[7]、狄利克雷過程混合模型[8])或諸如主成分分析[9]、隨機(jī)梯度下降[10]等技術(shù)假設(shè)正常流遵循某種常規(guī)統(tǒng)計過程，而偏離該統(tǒng)計機(jī)制的流則視為異常?；谙嗨贫鹊姆椒ㄊ褂镁嚯x度量和鄰域計算方法或者經(jīng)典的異常值檢測方法[11]來檢測異常值。通常情況下，正常的流假定構(gòu)建密集區(qū)域而異常流假定構(gòu)建低密度區(qū)域。基于頻繁模式挖掘的方法通過使用諸如Apriori[12]或FP-growth[13]之類的技術(shù)來發(fā)現(xiàn)異常值之間的關(guān)聯(lián)關(guān)系。

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

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

2 模型

城市特定位置處的交通流通過計算一個時間區(qū)間內(nèi)的對象(汽車、出租車和公共汽車等)數(shù)量得到[16,17]。交通流數(shù)據(jù)通?；谀骋惶囟ㄎ恢迷跁r間區(qū)間內(nèi)表現(xiàn)出某種特定的分布，因此，區(qū)別于從交通流的時間序列中檢測某一時間區(qū)間內(nèi)的單個異常流，從流序列中檢測出的異常流分布更能代表對某段時間區(qū)間內(nèi)總體交通行為產(chǎn)生影響的異常情況。

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

Figure 1 Framework for flow sequences detection algorithm

(2)異常值的檢測：獨(dú)立使用歷史流分布概率從流式傳輸?shù)男碌牧鞣植贾袡z測異常值。如果新數(shù)據(jù)不是異常數(shù)據(jù)，將其更新入歷史流分布概率庫中，否則將其提取出以待進(jìn)一步分析。

3 kNNFS算法

3.1 算法推導(dǎo)

算法輸入為時空交通流TF，包含時間、位置和交通流值等信息?；诮煌髦械奈恢眯畔裈F依據(jù)位置劃分為不同位置處交通流的集合TF={TF1,…,TFn}，上述所有n個位置由位置集合L={L1,…,Ln}表示，TFi是與對應(yīng)位置Li相關(guān)的交通流信息。

(1)

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

(2)

(3)

(4)

(5)

(6)

將得到的所有時間區(qū)間的流分布概率組成集合，從而構(gòu)成位置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的理論復(fù)雜度分為FDP構(gòu)建復(fù)雜度和異常值檢測復(fù)雜度2部分：

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

(12)

其中n為位置Li的數(shù)量。

4 仿真分析

4.1 評價指標(biāo)

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

(13)

(14)

(15)

其中，TP表示正確判屬異常流的數(shù)量，F(xiàn)P表示錯誤判屬異常流的數(shù)量，F(xiàn)N表示錯誤判定為非異常流的數(shù)量。

4.2 數(shù)據(jù)集

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

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

Table 1 Feature description of the dataset from Odense Denmark

4.3 歐登塞市數(shù)據(jù)的仿真結(jié)果

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

4.4 北京市數(shù)據(jù)的仿真結(jié)果

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

Figure 3 F-measure on different numbers of flow data

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

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

Figure 4 Runtime on different number of flow data

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

5 結(jié)束語

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