基于改進ADPP的多變量時間序列異常檢測

董紅玉， 陳曉云

(福州大學數學與計算機科學學院， 福建 福州　350116)

?

基于改進ADPP的多變量時間序列異常檢測

董紅玉， 陳曉云

(福州大學數學與計算機科學學院， 福建 福州350116)

摘要：針對多變量時間序列異常檢測問題進行研究， 提出基于改進ADPP的多變量時間序列異常檢測算法IADPP. IADPP算法引入適用于多變量時間序列的張量相似性度量SSOTPCA， 并以此相似性度量構造序列集的k-近鄰圖， 在構造的k-近鄰圖上計算多變量時間序列的異常系數. 研究結果表明， IADPP算法克服了原有ADPP算法不支持多變量時間序列和要求密度均勻的缺陷， 取得了較好的檢測結果.

關鍵詞：多變量時間序列； 異常檢測； 張量相似性度量； k-近鄰圖

1相關研究

多變量時間序列MTS(multivariate time series)是指多個變量依照時間先后順序得到的一系列觀察值的集合， 記為Xi(t)， (i=1, 2, …m; t=1, 2, …n). 其中i表示變量個數(m≥2)， t表示序列長度. 它可用一個n×m的矩陣表示如下：

(1)

MTS數據廣泛存在于各種應用領域， 如視頻監控、 金融、 醫療、 氣象、 動作捕捉等.

異常檢測是指在數據集中發現不符合期望行為的數據點， 這些不符合期望行為的數據點在不同的應用領域被稱為異常， 孤立值， 不和諧的觀察值， 奇異模式等[1]. 異常檢測作為數據挖掘領域的重要分支， 在醫學診斷、 信用卡欺詐、 網絡入侵、 生態系統失調等領域有著強大的實際應用背景， 而這些領域的數據類型一般都是或能轉化為MTS數據， 因此， 針對MTS的異常檢測研究有較強的實踐意義.

根據異常的表現形式， 異常可分為全序列異常和子序列異常， 當子序列的長度為1時， 子序列異常退化為點異常. 本文針對多變量時間序列的全序列異常， 即異常樣本展開研究.

根據采用技術的不同， 現有MTS異常檢測方法可分為以下5類：

1) 基于統計的異常檢測. 指為數據建立一個模型， 與模型參數擬合概率較低的對象判為異常. 文獻[2]提出的基于核主成分分析KPCA(kernel principal component analysis)的異常檢測算法， 通過KPCA獲取MTS的主方向矢量并估計訓練樣本vMF(von miser-fisher)分布模型的參數， 將小概率的測試樣本歸為異常. 該算法預先設定數據滿足vMF分布， 但真實數據的分布一般較為復雜且不一定滿足vMF分布. 文獻[3]和文獻[4]分別采用投影尋蹤和獨立成分分析確定序列的峰度系數， 樣本的峰度系數和模型預定的系數范圍比較廣. 但這兩種方法均單獨處理每個變量， 忽視了變量間的相關性.

2) 基于距離的異常檢測. 是指若一個對象遠離其它大部分數據點， 就認為該對象是異常的， 其中遠離程度通過距離度量. 文獻[5]提出基于解決集的子序列異常檢測算法， 通過滑動窗口獲得MTS子序列并用擴展的Frobenius范數(Eros)[6]計算子序列間的距離， 根據距離的大小采用基于解決集的方法檢測異常. 雖然該類方法簡便易行， 但它對距離的選擇異常敏感， 且不適用密度分布不均的數據集.

3) 基于密度的異常檢測. 是指若一個對象的密度相對于其它對象較低， 那它就被判定為異常， 對象的密度(局部異常系數)表明了該對象與其它對象的相似程度. 該類方法是對基于距離異常檢測方法的改進， 能較好地處理具有不同密度的數據集. 文獻[7]和[8]都是基于此思想， 不同的是文獻[7]采用Eros計算樣本間的相似性， 而文獻[8]采用SPCA[9]計算相似性， 但這兩種相似性度量均不滿足三角不等式.

4) 基于聚類的異常檢測. 是將規模較小的簇內對象或簇隸屬度較低的對象判定為異常. 文獻[10]提出兩階段的異常檢測算法， 通過有界坐標系統計算樣本相似性， 采用K-means算法對數據聚類并由一個啟發式規則對其排序， 最后在簇上采用循環嵌套算法進行異常檢測， 該算法嚴重依賴簇個數， 而且時間復雜度較高.

5) 基于圖的異常檢測. 先構造一個樣本連接圖， 之后將連接圖中與其它樣本連接較少的對象定義為異常. 如文獻[11]提出的基于隨機游走的MTS異常檢測算法， 先采用高斯徑向基函數獲得數據集每個變量的相似度矩陣， 并把相似度矩陣轉化為樣本連接圖， 之后通過隨機游走算法計算各樣本的連接系數， 以此判斷樣本的異常程度. 但該算法將MTS的變量分別處理， 忽視了變量間的相關性.

目前， 基于圖的異常檢測方法也成為目前異常檢測領域的研究熱點. 文獻[12]提出基于鄰近圖和PageRank的異常檢測算法—ADPP(anomalydetectionusingproximitygraphandPageRank)， 該算法先構造了樣本的ε-鄰域圖， 之后利用PageRank算法[11]發現圖中的異常樣本. 經實驗驗證， 該方法提高了異常檢測的準確率， 但ADPP算法僅適用向量型數據， 不適用于矩陣型的MTS數據. 本文擬對ADPP算法進行適當改進， 使其能成功應用于MTS數據.

2PageRank及ADPP算法簡介

PageRank算法[13]最早由Page和Brin提出， 被Google用于網頁排名， 可看做在定向圖上的馬爾可夫隨機游走模型：

(2)

ADPP算法[12]則先構造一個ε-鄰域圖， 在圖上執行改進的PageRank.ε-鄰域圖的構造原理如下： 若兩樣本點落在ε-鄰域內， 邊的權值定義如下：

(3)

式中：dist(xi, xj)表示樣本點xi和xj的歐氏距離； 反之， wij=0.

轉移矩陣P根據構造的ε-鄰域圖定義：

(4)

傳遞向量C依據每個樣本點的權值定義, 其元素

(5)

此外，ADPP算法通過下式計算J

(6)

由上述可知， ADPP算法主要包括以下四個步驟：

Step 1計算數據集內各數據點間的歐式距離dist(xi, xj)并儲存；

Step2給定閾值ε， 若dist(xi, xj)≤ε， 根據式(3)計算數據點間邊的權值， 記為權值矩陣W；

Step 3分別由式(4)和(5)計算數據集的轉移矩陣P和傳遞向量C；

Step 4由式(6)計算連接度J， 并對J值升序排列， 將J值較小的數據點判定為異常.

ADPP算法的不足在于： ①構造ε-鄰域圖時使用全局閾值， 因此ADPP算法對數據集密度分布情況依賴程度高. ②由式(6)可知， 求解J的過程兩次用到逆矩陣， 計算一個d×d矩陣的逆矩陣的時間復雜度高達O(d3)， 這導致了ADPP算法的時間開銷較大.

3IADPP 檢測算法

針對ADPP算法不適用MTS數據及要求數據集密度分布均勻， 提出基于改進ADPP的多變量時間序列異常檢測方法—IADPP. IADPP算法引入支持多變量時間序列的張量相似性度量SSOTPCA， 構造時間序列集的k-近鄰圖， 新的k-近鄰圖可以有效避免原有ADPP算法ε-鄰域圖對數據集密度敏感的問題.

3.1相關定義

定義1張量相似性度量SSOTPCA.

(7)

定義2樣本X的k-相似度(simk(X)).

給定一個自然數k和MTS數據集D， 樣本X的k-相似度是X和數據集D中的某個樣本Z之間的相似度， 記為simk(X). 樣本Z滿足以下兩個條件：

1) 至少存在k個樣本Z′∈D{X}， 使得SSOTPCA(X, Z′)≥SSOTPCA(X, Z′)；

2) 至多存在k-1個樣本Z′∈D{X}， 使得SSOTPCA(X, Z′)≥SSOTPCA(X, Z′).

對于MTS數據集D={X1, X2, …, Xd}， 通過樣本的simk(X)構造樣本間的k-近鄰圖. 近鄰圖是關于樣本的加權圖G=(V, E)， 其中V表示頂點集， E表示邊集， 若樣本Xi與Xj存在邊當且僅當SSOTPCA(Xi, Xj)≥simk(Xi)， 那么邊的權值wij≥0. 權重矩陣W定義如下：

(8)

定義3MTS樣本異常系數.

MTS樣本的異常系數ODi(i=1, …, d)定義為對應連接度的倒數：

(9)

如果樣本的異常系數較大， 就意味著樣本與其它樣本的連接度較小， 從而樣本為異常的概率就較大.

定義4MTS數據集的相對異常樣本.

3.2基于改進ADPP的異常檢測算法描述

算法名稱： 基于改進ADPP的異常檢測算法.

輸入： MTS樣本的數據集D， 近鄰數k， 輸出樣本數l， 阻尼系數α， 閾值β， 最大迭代次數t.

輸出： 前l個異常樣本.

Step 1利用張量相似性度量SSOTPCA計算MTS樣本的k-相似度simk(X)；

Step 2構造關于數據集D的k-近鄰圖， 并計算圖中邊的權值矩陣W；

Step 3分別由式(4)和(5)計算樣本轉移矩陣P和傳遞向量C；

Step 4由式(2)采用循環迭代算法計算MTS樣本的連接度Ji(i=1, …,d)；

Step 5由式(9)計算樣本的異常系數ODi(i=1, …,d)， 對所有樣本的異常系數降序排列；

Step 6輸出異常系數最大的前l個MTS樣本.

4實驗與結果分析

4.1實驗數據集

選取兩組MTS數據集進行實驗， 分別為JV2和Wafer2， 表1概要描述了這兩組實驗數據.

表1　實驗數據概述

JV2數據集選取了JV 數據集[13]中第三個測試者的118個樣本作為正常類， 第五個測試者的前10個樣本作為異常類. Wafer2數據集隨機選擇Wafer數據集[14]中normal類的190個樣本， abnormal類的10 個樣本作為測試集.

4.2三種異常檢測算法性能比較

實驗比較以下3種算法的檢測準確率及時間開銷：

1) IADPP算法： 基于張量相似性度量SSOTPCA構造k-近鄰圖.

3) T_ADPP算法： 基于張量相似性度量SSOTPCA構造ε-鄰域圖.

當傳遞向量C取均值時， 由經驗定義阻尼系數α=0.85. 為了實驗的可比較性， 三種算法均取阻尼系數α=0.85， 輸出樣本數l=10. IADPP算法設閾值β=0.001， 最大迭代數t=20. 分別在JV2和Wafer2數據集上實驗， 實驗結果見表2.

由表2可知： 對于JV2和Wafer2數據集， IADPP算法的檢測準確率明顯高于IADPP_M和T_ADPP算法. 這是因為IADPP_M算法的傳遞向量沒有考慮到序列集的權值， 平等看待每個樣本； 而T_ADPP算法的ε-鄰域圖依賴數據集的密度分布. 此外， 在JV2數據集上， 若T_ADPP算法取鄰域ε=1.5時， 求解過程出現奇異情況， 無法得到正確的結果.

表2　三種異常檢測算法在兩組數據集上的檢測準確率

下面比較在以上參數條件下這三種算法的時間開銷. 實驗結果如圖1所示. 由圖1可知， 時間開銷從小到大排列依次是 IADPP_M、 IADPP、 T_ADPP算法. 從理論上講， 由于IADPP_M算法的傳遞向量直接定義為均值向量， 不需要計算， 而IADPP和T_ADPP算法的傳遞向量都是根據權值矩陣計算， 故IADPP算法時間開銷要比IADPP_M算法大； T_ADPP算法求解逆矩陣的時間復雜度為O(d3)，d為樣本數， IADPP算法采用迭代算法的時間復雜度O(t)，t為迭代次數， 因此IADPP算法的時間開銷低于T_ADPP算法.

綜合比較IADPP、 IADPP_M和T_ADPP三種算法在兩組數據集上的檢測準確率和時間開銷可知， IADPP算法不僅有較高的檢測準確率， 其時間開銷也比T_ADPP算法小.

4.3參數對IADPP算法的影響

IADPP算法閾值β和最大迭代數t影響算法的時間開銷， 而樣本近鄰圖的近鄰數k和阻尼系數α影響算法的檢測準確率. 本文只討論近鄰數k和阻尼參數α對算法準確率的影響， 實驗分別在JV2和Wafer2數據集上進行， 結果如圖2所示.

由圖2(a)可知： 隨著近鄰數的增加， IADPP算法的準確率逐漸提高， 當近鄰數增加到一定程度后， 準確率保持不變. 由此可知， 在構造k-近鄰圖時， 直接取較大的近鄰數k， 能在一定程度上保證IADPP算法的準確率. 選擇上述實驗準確率最高時所對應的最小近鄰數， 即JV2數據集取k=20， Wafer2數據集取k=10. 由圖2(b)可知： 隨著阻尼系數α的增加， IADPP算法的準確率始終保持不變. 這說明IADPP算法對阻尼系數α不敏感.

5結語

針對ADPP異常檢測算法不適用MTS數據及要求數據密度分布均勻， 提出基于改進ADPP的多變量時間序列異常檢測算法IADPP. 該算法基于逆向挖掘思想， 即異常樣本肯定是與其它樣本連接度最低的樣本， 引入支持MTS的張量相似性度量， 并以此度量構造樣本的k-近鄰圖， 在新的k-近鄰圖上計算MTS的異常系數. 在真實數據集上的實驗結果表明算法能取得較好的檢測結果.

參考文獻：

[1]VARUN C, ARINDAM B, KUMAR V. Anomaly detection for discrete sequences: a survey[J]. IEEE Transactions on Knowledge and Data Engineering, 2012, 24(5), 823-839.

[2]李權， 周興社. 基于KPCA的多變量時間序列數據異常檢測方法研究[J]. 計算機測量與控制， 2011, 19(4)： 822-825.

[3]GALEANO D, PENA R, TSAY R S. Outlier detection in multivariate time series by projection pursuit[J]. Journal of the American Statistical Association, 2006, 101(474), 654-669.

[4]BARAGONA R, BATTAGLIA F. Outlier detection in multivariate time series by independent component analysis[J]. Neural Computation, 2007, 19(7): 1 962-1 984.

[5]WENG X, SHEN J. Finding discordant subsequence in multivariate time series[C]//2007 IEEE International Conference on Automation and Logistics. Piscataway:IEEE, 2007： 1 731-1 735. DOI:10.1109/ICA L.27.4338852.

[6]YaNG K, SHAHABI C. A PCA-based similarity measure for multivariate time series[C]//Proceedings of the Second ACM International Workshop on Multimedia Databases. Washington:ACM, 2004： 65-74. DOI:10.1145/1032604.1032616.

[7]翁小清, 沈鈞毅. 多變量時間序列異常樣本的識別[J]. 模式識別與人工智能， 2007, 20(4): 463-468.

[8]郭小芳， 李鋒， 宋曉寧. 一種基于PCA的時間序列異常檢測方法[J]. 江西師范大學學報(自然科學版)， 2012, 36(3): 280-283.

[9] SINGHA A , SEBORG D E. Pattern matching in historical batch data using PCA[J]. IEEE Control Systems Magazine， 2002, 22(5): 53-63.

[10]王欣.兩階段的多元時間異常檢測算法[J]. 計算機應用研究， 2011, 28(7): 2 466-2 469.

[11]CHENG H B, TAN P N, POTTER C,etal. A robust graph-based algorithm for detection and characterization of anomalies in noisy multivariate time series[C]// Workshops Proceedings of the 8th IEEE International Conference on Data Mining.Pisa:IEEE, 2008： 349-358. DOI:10.1109/ICDMW.2008.48.

[12]YAO Z, MARK P, RABBAT M. Anomaly detection using proximity graph and PageRank algorithm[J]. IEEE Transactions on Information Forensics and Security， 2012, 7(4): 1 288-1 300.

[13]PAGE L, BRIN S, MOTWANI R,etal. The PageRank citation ranking: bring order to the web[R].Stanford: Stanford University, 1998.

[14]PageRank[EB/O L].[2013-04-23]. http://en.wikipedia.org/wiki/PageRank.

(責任編輯： 蔣培玉)

Outlier detection based on improved ADPP for multivariate time series

DONG Hongyu, CHEN Xiaoyun

(College of Mathematics and Computer Science, Fuzhou University, Fuzhou, Fujian 350116, China)

Abstract:We study the outlier detection for multivariate time series, and an approach of outlier detection for multivariate time series based on improved ADPP-IADPP is proposed. IADPP algorithm introduces tensor similarity measure SSOTPCAsupporting for multivariate time series, and constructs the k-neighbor graph about the sequence set. Then, we calculate the outlier coefficient of multivariate time series on k-neighbor graph .The research results show that the proposed method overcomes the disadvantages that original ADPP does not support multivariate time series and requests uniform density, IADPP algorithm achieves a better detection results.

Keywords:multivariate time series; outlier detection; tensor similarity measure; k-neighbor graph

中圖分類號：TP311

文獻標識碼：A

基金項目:福建省新世紀優秀人才資助項目(XSJRC2007-11)

通訊作者：陳曉云(1970-)， 教授， 主要從事數據挖掘、 機器學習、 模式識別等研究， c_xiaoyun@21cn.com

收稿日期:2013-09-10

文章編號：1000-2243(2016)02-0164-06

DOI:10.7631/issn.1000-2243.2016.02.0164