李權(quán)，周興社

?

一種新的多變量時(shí)間序列數(shù)據(jù)異常檢測(cè)方法

李權(quán)1,2，周興社1

（1. 西北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，西安 710072；2. 西安衛(wèi)星測(cè)控中心，西安 710043）

介紹了一種通過(guò)建立多變量時(shí)間序列數(shù)據(jù)相似度矩陣，對(duì)相似度矩陣進(jìn)行轉(zhuǎn)換以最大化數(shù)據(jù)之間的相關(guān)性，并采用隨機(jī)游走模型計(jì)算數(shù)據(jù)點(diǎn)之間的連接系數(shù)來(lái)檢測(cè)數(shù)據(jù)點(diǎn)上異常的方法。該方法充分利用了數(shù)據(jù)之間的相關(guān)性，有效減少了數(shù)據(jù)中不同程度噪聲對(duì)異常檢測(cè)的影響，檢測(cè)過(guò)程中的漏報(bào)率和誤報(bào)率明顯減少，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了該方法的有效性。

時(shí)間序列數(shù)據(jù)；異常檢測(cè)；相似性分析

異常檢測(cè)也稱(chēng)為離群點(diǎn)檢測(cè)，是近年來(lái)數(shù)據(jù)挖掘領(lǐng)域的重要研究方向之一[1-5]，其目標(biāo)是在數(shù)據(jù)集中發(fā)現(xiàn)不正常的數(shù)據(jù)點(diǎn)，與之相關(guān)的研究包括：事件檢測(cè)（event detection）[3]、變化點(diǎn)檢測(cè)（change-point detection）[4]、異常行為檢測(cè)（aberrant behavior detection）[5]等。目前，對(duì)時(shí)間序列的異常還沒(méi)有一個(gè)公認(rèn)的定義，普遍采用的是D. M. Hawkins給出的定義[6]：“異常點(diǎn)是那些與其他數(shù)據(jù)點(diǎn)有較大偏差的數(shù)據(jù)點(diǎn)，以至于懷疑這些偏差并非隨機(jī)產(chǎn)生，而是產(chǎn)生于一種完全不同的方式”。異常檢測(cè)技術(shù)已在經(jīng)濟(jì)、科學(xué)、工程等領(lǐng)域取得了廣泛應(yīng)用，如信用卡欺詐[7]、網(wǎng)絡(luò)入侵檢測(cè)[8]、航天器在軌診斷等。

異常檢測(cè)方法主要包括以下幾種：1）基于距離的異常點(diǎn)檢測(cè)方法[9]，其通過(guò)計(jì)算數(shù)據(jù)點(diǎn)之間的距離來(lái)檢測(cè)異常點(diǎn)，該方法具有簡(jiǎn)單高效的優(yōu)點(diǎn)，但當(dāng)數(shù)據(jù)包含多種不同分布的數(shù)據(jù)時(shí)效果不好； 2）基于密度的異常檢測(cè)方法，如局部異常因子（LOF，local outlier factor）[10]，該方法克服了不同密度子集混合而造成的檢測(cè)錯(cuò)誤，檢測(cè)精度較高，但當(dāng)數(shù)據(jù)集較大時(shí)計(jì)算量大，復(fù)雜度過(guò)高，響應(yīng)速度較慢；3）基于模型的異常檢測(cè)方法[11]，該方法通過(guò)構(gòu)建數(shù)據(jù)的概率分布模型，將具有較低概率的數(shù)據(jù)點(diǎn)作為異常點(diǎn)檢出，該方法具有堅(jiān)實(shí)的數(shù)學(xué)理論基礎(chǔ)，其難點(diǎn)在于數(shù)據(jù)分布的識(shí)別和模型參數(shù)的估計(jì)。

目前大多數(shù)時(shí)間序列數(shù)據(jù)異常檢測(cè)方法存在的主要問(wèn)題是對(duì)數(shù)據(jù)之間的相關(guān)性分析利用不夠，對(duì)噪聲比較敏感[1]。本文介紹的異常檢測(cè)方法充分利用了數(shù)據(jù)之間的相關(guān)性，采用高斯徑向基函數(shù)計(jì)算序列之間的相似性，降低了噪聲對(duì)檢測(cè)結(jié)果的影響。該方法適用于數(shù)據(jù)噪聲較大、數(shù)據(jù)量較小的異常檢測(cè)，通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性。

1 異常檢測(cè)算法

1.1 相關(guān)定義

異常檢測(cè)：在數(shù)據(jù)中檢測(cè)那些數(shù)值明顯背離數(shù)據(jù)集合總體分布情況的數(shù)據(jù)，依據(jù)檢測(cè)出的內(nèi)容可以劃分為單數(shù)據(jù)點(diǎn)檢測(cè)和子序列數(shù)據(jù)檢測(cè)，單數(shù)據(jù)點(diǎn)檢測(cè)用于檢測(cè)時(shí)間序列數(shù)據(jù)中某一點(diǎn)的異常情況，子序列檢測(cè)用于檢測(cè)連續(xù)數(shù)據(jù)段（該數(shù)據(jù)段長(zhǎng)度遠(yuǎn)小于整個(gè)數(shù)據(jù)序列長(zhǎng)度）的異常情況。

1.2 相似度的度量

本文介紹的異常檢測(cè)方法采用高斯徑向基函數(shù)計(jì)算數(shù)據(jù)之間的相似性，但沒(méi)有通過(guò)直接比較相似度進(jìn)行異常檢測(cè)，而是由相似度矩陣求解異常檢測(cè)矩陣，通過(guò)計(jì)算檢測(cè)矩陣的節(jié)點(diǎn)連接系數(shù)判斷數(shù)據(jù)的異常，該方法能夠有效降低噪聲影響，最大化地利用數(shù)據(jù)之間的相關(guān)性。

1.3 異常檢測(cè)矩陣構(gòu)造

1.4 節(jié)點(diǎn)連接系數(shù)計(jì)算

1.5 算法流程

以上論述的故障檢測(cè)算法的流程中，輸入的是多變量時(shí)間序列數(shù)據(jù)和判斷門(mén)限，經(jīng)過(guò)一系列計(jì)算后，輸出異常檢測(cè)結(jié)果，從而可知異常時(shí)間點(diǎn)和相應(yīng)的異常數(shù)據(jù)。計(jì)算步驟為：

1）計(jì)算各序列相似度矩陣；

2）由各序列相似度矩陣計(jì)算轉(zhuǎn)換矩陣；

3）計(jì)算整個(gè)序列異常檢測(cè)矩陣；

4）采用基于隨機(jī)游走模型計(jì)算每個(gè)節(jié)點(diǎn)的連接系數(shù)；

5）對(duì)連接系數(shù)進(jìn)行比較，獲取輸出。

2 實(shí)驗(yàn)與結(jié)果分析

圖1 實(shí)驗(yàn)所用的多變量時(shí)間序列數(shù)據(jù)

上述數(shù)據(jù)采用本文介紹的方法進(jìn)行異常檢測(cè)，假設(shè)連接系數(shù)低于0.3的數(shù)據(jù)點(diǎn)視為異常，其檢測(cè)的結(jié)果如圖2所示。由圖2可清晰看出在＝20和＝80這2個(gè)點(diǎn)上出現(xiàn)的數(shù)據(jù)異常，表明即使時(shí)間序列中出現(xiàn)了較強(qiáng)的噪聲污染，本方法依然檢測(cè)出了相應(yīng)的異常點(diǎn)。試驗(yàn)中還比較了采用基于距離的異常檢測(cè)方法的有效性，結(jié)果如圖3所示。由圖3可以看出，由于，對(duì)數(shù)據(jù)的影響，直接采用距離的方法難以檢測(cè)出對(duì)應(yīng)的異常點(diǎn)。

圖2 采用檢測(cè)矩陣的結(jié)果

圖3 基于距離的檢測(cè)結(jié)果

3 結(jié)論

本文介紹的多變量異常檢測(cè)方法采用高斯徑向基函數(shù)計(jì)算時(shí)間序列之間的相似性，通過(guò)建立相似度矩陣和異常檢測(cè)矩陣實(shí)現(xiàn)了多變量時(shí)間序列數(shù)據(jù)的異常檢測(cè)。由于本方法計(jì)算中有效挖掘了數(shù)據(jù)之間的相關(guān)性，降低了相關(guān)數(shù)據(jù)的噪聲影響，因此異常檢測(cè)的誤報(bào)率和漏報(bào)率得到了下降。高斯徑向基函數(shù)參數(shù)選擇對(duì)檢測(cè)結(jié)果的影響以及如何降低計(jì)算的復(fù)雜度將是下一步研究的重點(diǎn)。

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

[2] LAST L, KANDEL A, BUNKE H. Data Mining in Time Series Databases[M]. Singapore: World Scientific Publishing Company, 2004.

[3] YAMANISHI K, TAKEUCHI J I. A unifying framework to detecting outliers and change-points from nonstationary data[C] // Proceedings of the Eighth ACM SIGKDD International Conference on KDD. New York: ACM, 2002: 676-681.

[4] JAGADISH H V, KOUDAS N, MUTHUKRISHNAN S. Mining deviants in a time series database[C] // Proceedings of 25th International Conference on Very Large Data Bases. San Fracisco: Morgan Kanfman Publishers Inc, 1999: 102-113．

[5] KOTSAKIS E, WOLSKI A. MAPS: a method for identifying and predicting aberrant behavior in time series[C] // Proceeding of 14th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems. New York: ACM, 2001: 314-325.

[6] HAWKINS D M. Identification of Outliers[M]. London: Chapman and Hall, 1980．

[7] 吳婷. 數(shù)據(jù)挖掘在信用卡欺詐識(shí)別上的應(yīng)用研究[D]. 南京: 東南大學(xué), 2006.

[8] 范秉琪, 朱曉東, 馬鴻雁, 等．基于數(shù)據(jù)挖掘的網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的設(shè)計(jì)與應(yīng)用[J]．河南理工大學(xué)學(xué)報(bào), 2006, 25 (3): 247-250.

[9] KNORR E M, RAYMOND T N. A unified notion of outliers: properties and computation[C] // KDD-1997 Proceedings. [S.l.]: AAAI Press, 1997: 219-222．

[10] BREUNIG M M, KRIEGEL H P, RAYMOND T N, et al. LOF: identifying density-based local outliers[C] // SIGMOD′ 00 Proceedings of the 2000 ACM SIGMOD International Conference on Management of Date. New York: ACM, 2000: 93-104.

[11] 陳封能, 斯坦巴赫, 庫(kù)瑪爾. 數(shù)據(jù)挖掘?qū)д揫M]. 范明, 范宏建, 譯. 上海: 人民郵電出版社, 2006.

[12] CRISTIANINI N, KANDOLA J, ELISSEEFF A, et al. On kernel-target alignment[C] // In Advances in Neural Information Processing Systems(NIPS2001). Vancouver, Canada: MIT Press, 2001: 367-373.

A new method of detecting anomalies in multivariate time series

LI Quan1,2, ZHOU Xing-she1

(1. School of Computer Science, Northwestern Polytechnic University, Xi′an 710072, China; 2. Xi′an Satellite Control Center, Xi′an 710043, China)

A new method of detecting anomalies in MTS (multivariate time series) is introduced, in which a similarity matrix for MTS is set up and the similarity matrix is transformed to maximize the correlation between the data points and then the anomalous data points are detected by comparing the predefined threshold with the connectivity coefficient calculated through the random walk model. This detection method makes full use of the correlation between the data points and effectively reduces the influence of the noise. The omission rate and false alarms decrease obviously, and the simulation has tested and verified the validity of this method.

MTS(multivariate time series); anomalies detection; similarity analysis

TP39

A

1674-0637(2011)02-0154-05

2011-03-06

李權(quán)，男，博士研究生，研究員，長(zhǎng)期從事測(cè)控軟件規(guī)劃設(shè)計(jì)、數(shù)據(jù)挖掘、人工智能等方面的研究。