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

董紅玉， 陳曉云

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

?

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

董紅玉， 陳曉云

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

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

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

1相關(guān)研究

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

(1)

MTS數(shù)據(jù)廣泛存在于各種應(yīng)用領(lǐng)域， 如視頻監(jiān)控、 金融、 醫(yī)療、 氣象、 動作捕捉等.

異常檢測是指在數(shù)據(jù)集中發(fā)現(xiàn)不符合期望行為的數(shù)據(jù)點， 這些不符合期望行為的數(shù)據(jù)點在不同的應(yīng)用領(lǐng)域被稱為異常， 孤立值， 不和諧的觀察值， 奇異模式等[1]. 異常檢測作為數(shù)據(jù)挖掘領(lǐng)域的重要分支， 在醫(yī)學(xué)診斷、 信用卡欺詐、 網(wǎng)絡(luò)入侵、 生態(tài)系統(tǒng)失調(diào)等領(lǐng)域有著強大的實際應(yīng)用背景， 而這些領(lǐng)域的數(shù)據(jù)類型一般都是或能轉(zhuǎn)化為MTS數(shù)據(jù)， 因此， 針對MTS的異常檢測研究有較強的實踐意義.

根據(jù)異常的表現(xiàn)形式， 異?？煞譃槿蛄挟惓：妥有蛄挟惓?， 當(dāng)子序列的長度為1時， 子序列異常退化為點異常. 本文針對多變量時間序列的全序列異常， 即異常樣本展開研究.

根據(jù)采用技術(shù)的不同， 現(xiàn)有MTS異常檢測方法可分為以下5類：

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

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

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

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

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

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

2PageRank及ADPP算法簡介

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

(2)

ADPP算法[12]則先構(gòu)造一個ε-鄰域圖， 在圖上執(zhí)行改進的PageRank.ε-鄰域圖的構(gòu)造原理如下： 若兩樣本點落在ε-鄰域內(nèi)， 邊的權(quán)值定義如下：

(3)

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

轉(zhuǎn)移矩陣P根據(jù)構(gòu)造的ε-鄰域圖定義：

(4)

傳遞向量C依據(jù)每個樣本點的權(quán)值定義, 其元素

(5)

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

(6)

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

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

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

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

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

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

3IADPP 檢測算法

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

3.1相關(guān)定義

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

(7)

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

給定一個自然數(shù)k和MTS數(shù)據(jù)集D， 樣本X的k-相似度是X和數(shù)據(jù)集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數(shù)據(jù)集D={X1, X2, …, Xd}， 通過樣本的simk(X)構(gòu)造樣本間的k-近鄰圖. 近鄰圖是關(guān)于樣本的加權(quán)圖G=(V, E)， 其中V表示頂點集， E表示邊集， 若樣本Xi與Xj存在邊當(dāng)且僅當(dāng)SSOTPCA(Xi, Xj)≥simk(Xi)， 那么邊的權(quán)值wij≥0. 權(quán)重矩陣W定義如下：

(8)

定義3MTS樣本異常系數(shù).

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

(9)

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

定義4MTS數(shù)據(jù)集的相對異常樣本.

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

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

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

輸出： 前l(fā)個異常樣本.

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

Step 2構(gòu)造關(guān)于數(shù)據(jù)集D的k-近鄰圖， 并計算圖中邊的權(quán)值矩陣W；

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

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

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

Step 6輸出異常系數(shù)最大的前l(fā)個MTS樣本.

4實驗與結(jié)果分析

4.1實驗數(shù)據(jù)集

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

表1　實驗數(shù)據(jù)概述

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

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

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

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

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

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

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

表2　三種異常檢測算法在兩組數(shù)據(jù)集上的檢測準(zhǔn)確率

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

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

4.3參數(shù)對IADPP算法的影響

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

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

5結(jié)語

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

參考文獻：

[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]李權(quán)， 周興社. 基于KPCA的多變量時間序列數(shù)據(jù)異常檢測方法研究[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]. 江西師范大學(xué)學(xué)報(自然科學(xué)版)， 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]. 計算機應(yīng)用研究， 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.

(責(zé)任編輯： 蔣培玉)

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

文獻標(biāo)識碼：A

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

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

收稿日期:2013-09-10

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

DOI:10.7631/issn.1000-2243.2016.02.0164