基于相似性分析的時間序列異常檢測方法

孫 焱,林 意

江南大學 數字媒體學院,江蘇 無錫 214000

基于相似性分析的時間序列異常檢測方法

孫 焱,林 意

江南大學 數字媒體學院,江蘇 無錫 214000

時間序列數據是按照時間順序在不同的時間點采集的數據，反映了某一對象隨時間的變化狀態和程度。由于時間序列的海量性及復雜性，我們采用頻域表示時間序列，并以此為基礎提出了基于相似性分析的時間序列異常檢測方法。將動態模式匹配距離作為衡量相似性的指標，計算每一個模式同其余各模式之間的相似性，據此確定異常狀態。該方法大大降低了數據搜索復雜度，提高了系統效率與準確度。

時間序列;相似性分析;動態模式匹配;異常檢測

近年來伴隨著社會經濟的高速發展以及科學技術的巨大進步，計算機技術也獲得了巨大的進步。隨著信息時代的到來，人類社會對于外界信息的依賴變得越來越重要同時也產生了海量的信息數據。另一方面這些數據的產生速度可以用驚人來形容，只需要短短一年甚至幾個月整個人類社會的信息量就可以增長一倍。而采用哪種有效手段管理并挖掘出這些海量數據中所隱藏的規律與知識則成為了當代研究者們所關注的熱點話題，因此數據挖掘技術在當代社得越來越重要。

時間序列作為一種廣泛存在于醫學、工程、商業以及自然科學等領域數據庫中的常見數據形式，近年來得到了研究人員越來越多的關注[1]。對其進行相關性分析并在此基礎上進一步進行數據搜索匹配成為了數據挖掘的重要步驟。時間序列異常是指在數據集中某一數據偏離大部分數據，其數值特性已經超出了隨機偏差的范圍，而更有可能是由不同機制產生的[2-4]。為了能夠有效檢測出時間序列數據中的異常數據，本文提出了基于相似性分析的時間序列異常檢測方法。首先通過建立合適的時間序列模型來抽象化數據，降低搜索復雜度，便于檢索；隨后通過一個滑動的窗口平滑處理時間序列，計算其和其他模式的相似度以確定其是否異常。

本文的結構安排如下：首先給出了時間序列模型對數據進行抽象化處理，隨后介紹對時間序列進行相似性度量的各類方案，緊接著提出了時間序列異常檢測的方案，最后通過仿真實驗來驗證分析該方案的可行性。

1 時間序列的模型

因為時間序列一般都是高維數的，假如直接要在原始的數據中進行數據挖掘需要付出高昂的代價，其復雜性高效率低下，也會降低算法的準確性和可靠性。針對這個問題，必須采用合適的抽象方法對時間序列進行抽象建模，以達到簡化數據模型，去除冗余，搭建出符合要求的數據庫索引的目的[5-7]。雖然直接采用傳統時間序列分析方法理論上同樣可以解決相似性分析的問題，但是實際運用時間復雜度。因此，必須能夠建立一個合適的數據模型，以同時具有 高魯棒性和低復雜度的優中效果差，因為相似性度量的計算依賴于時間序列的表示方式，這會大大影響計算過程的點，這會大大提高數據索引的效率。

在這里我們采用頻域表示法，由于離散傅里葉變換DFT開頭的幾個系數表現突出，能夠保留信號的絕大部分能量，因此可以只留存DFT頭幾個系數而直接刪除其余系數同時保留下了數據的大部分特征來達到數據壓縮的目的，這樣做也保留了原始時間序列的基本特性[8]。

DFT變換同時對原始時間序列中的局部極大值與局部極小值都進行了數據平滑，這樣做使得數據的部分重要信息丟失。除此之外DFT還對序列的平穩性有著較高的要求，其對于非平穩的序列并不適用。而且DFT變換以相同長度的系數來度量所有長度的時間序列，降低了方法的合理性。因此，在此基礎上我們提出使用滑動窗口的簡單平滑方法，不但可以去除噪聲，也較為真實地反映出數據的實際特性。具體操作如下：

2 時間序列的相似性度量

2.1 Minkowski距離

歐幾里得距離是平時最常用的一種距離計算方式。假定長度為n的時間序列看作是一個n維歐式空間中的點，它的坐標點則對應著時間序列在各個時間點的取值，則兩條長度為n的時間序列之間的歐氏距離就是這個n維空間中兩點的距離[9-11]。其可以作如下描述：

Minkowski距離作為相似性度量距離，其是歐氏距離的推廣，如下定義：

當p=2時，Minkowski距離就成為了歐式距離，而在p=1時則變成了曼哈頓距離；當p趨于無窮大時則稱為最大距離。由于Minkowski距離同樣滿足非負性即所有值不小于零、對稱性以及距離三角不等式，所以該距離也能夠作為一種度量距離。

正是由于Minkowski距離具有滿足三角不等式的特性，所以在基于索引進行數據查詢時，能夠根據這一特性將其作為索引距離，快速過濾某些不符合索引條件的節點，從而提高索引速度。

Minkowski距離應用于數據索引的相似性度量時具有諸多優點，其簡單直觀，計算簡便，具有非常高的可擴展性，同樣可以應用于數據地查詢以及聚類等方面。然而Minkowski距離應用在時間序列數據挖掘時卻不具備很好的可靠性，其對于時間序列自身的噪聲以及波動不具備很好的魯棒性，相似的時間序列也會存在著多種變形，例如振幅平移與伸縮、線性飄逸、不連續、時間軸伸縮等等。

2.2 動態模式匹配距離

雖然Minkowski距離計算簡便，在索引查詢以及聚類領域有很優秀大表現，但是其對于時間序列的時間軸彎曲以及伸縮并不友好。所以為了能夠更好的進行時間序列的相似性分析，這一節提出使用動態模式匹配距離，同傳統距離所不同的是，動態模式匹配距離并不是根據兩個目標點之間的距離進行計算，而是通過模式匹配進行。這樣做一方面是因為模式的定義較為靈活，同時因為時間序列的模式一般遠遠小于序列的長度，這樣可以降低計算的數據量，提高算法效率。模式之間的距離使用加權歐氏距離進行定義：

假定給定兩個模式p1=(l1,k1)和p2=(l2,k2)，其中l和k分別表示模式的長度與斜率，則兩個模式之間的距離可以如下定義：

在以上定義中，分母的作用是將長度和斜率這兩個不同的量綱進行統一，而取最小值則是為了能夠突出短模式的重要性。

公式中d(px1,py1)表示的是px1與py1之間的模式距離，而P(X)-px1和P(Y)-py1分別表示P(X)和P(Y)去除了第一個元素后的序列。

從上述公式可以看出，模式是由他的長度和斜率這兩個特征表示。由于模式的長度與時間序列的振幅大小無關，而其斜率則體現了時間序列振幅的相對大小，所以所提的動態模式匹配距離可以克服時間序列的振幅平移與伸縮變換。除此以外，因為采用了模式的動態匹配方法，可以實現時間序列在時間軸上的伸縮和彎曲。

動態模式匹配距離可以使用累積距離矩陣的方法進行計算，這樣的話其時間復雜度就為O(mn/uv)，這其中的m和n分別表示兩個時間序列的長度，而u和v則表示模式的平均長度。由此可見，如果模式的平均長度越長的話，動態模式匹配的時間復雜度就越低。進一步可以看出，采用動態模式匹配距離的計算方法要遠遠優于Minkowski距離計算。

3 時間序列的異常檢測

3.1 時間序列的異常模式

異常可以簡單理解為在一個時間序列數據集中，其某一個數據點的值與其他數據點值存在非常明顯的差別，超出了隨機產生的可能，有可能是因為不同的機制而產生的，這一類數據就稱為異常。如圖中就是一種直觀的異常模式。其中的點3,4,5,6,7單獨來看時，其值與整體數據而言并沒有什么差異，然而當這些數據在時間上連續出現時就形成了整個時間序列中的異常數據。

圖1 時間序列異常Fig.1 The abnormal time series

3.2 K-近鄰原理

某一點p的k-近鄰距離（k-dist（p））可以如下定義[12-14]：假定k是一個正整數，D則是一個數據點的集合，而p為改數據集中的一個點，p點的k-近鄰距離應當滿足以下兩個條件：

（1）數據集D中至少有k個數據點（p點除外），這些數據點到p點距離不大于k-dist（p）。

（2）數據集D中至多有k-1個數據點（p點除外），這些點到p點的距離小于k-dist（p）。

如圖所示，當k=4時，點p的k-近鄰距離k-dist(p)=d(p,u),d(p,u)即表示點p到u的距離。

在數據集D中，點p到點t的k-近鄰可達距離r-dist(p,t)可以定義為：

點q的k-局部可達密度l rd(q)可以定義為：

以上公式中，k(q)表示q點的近鄰范圍，由局部密度的定義方式，可以看出該密度反應的是點q周圍的數據點分布情況，如果密度越高表示在數據集中類似于點q的點越多，同時也表明點q是異常數據的概率也越小。

數據集D中，點q的局部異常系數LOF(q)可以如下定義：

如上公式所示，如果局部異常系數越大則表明q點的局部范圍內數據點較為稀疏，則其為異常點的可能性也就越大[15,16]。

3.3 基于相似性分析的異常檢測算法

基于相似性分析的異常檢測算法不是直接對比目標兩個點，而是采用2.2節中提出的動態模式匹配距離，將兩個模式進行比較。由于模式的數據量遠遠小于原始數據量，這樣就極大地降低了需要檢測的數據量，降低了算法的復雜度。同時也對噪聲進行了過濾。并且使用這種方式計算出的異常是一個目標范圍而不再是單單的某一個數據點，這極大地提高了算法的魯棒性與合理性而且也更加符合實際。

該方法的流程圖如圖所示，第一步將目標時間序列進行頻域抽象化表示，形成模式化后的序列數據；第二步計算每一個模式同其余模式之間的模式距離分析其相似性，計算k-近鄰距離，緊接著根據公式6和公式7計算出每一個模式的局部密度以及局部異常因子；最后選取具有較大局部異常因子的模式判定為異常模式。

圖2 時間序列異常檢測流程Fig.2 The detection process of abnormal time series

4 實驗結果與分析

4.1 方法驗證

這部分我們對所設計的方法進行仿真驗證，采用dell便攜機作為仿真主機，頻率2.27 GHz，內存4 G，基于MATLAB進行仿真分析。驗證分為兩個部分，分別是對該方法的可行性以及可靠性進行測試。可行性測試的方法是通過MATLAB仿真對一系列隨機產生的數據進行模式距離計算后計算出每一個點的局部異常系數，并輸出異常數據。

圖3 可行性驗證結果圖Fig.3 The verification results for feasibility

如圖所示，對產生的一系列時間序列模式化后計算出了每一個數據點的拒不異常系數，并將其直觀地用圓的半徑表示，半徑越大則該點的異常系數越大，其為異常模式的可能性也就越大。設置合適的閾值之后就可以通過比較判別出異常模式，如圖中黑色圓所示。

隨后我們對該方法的可靠性進行驗證，探討其在不同數據量下的檢測準確性與時間消耗。

圖4 不同數據量下準確度（%）Fig.4 The detection accuracy on different data

圖5 不同數據量下檢測時間Fig.5 The detection time on different data

如圖4所示為改方法在不同數據量下的準確度，可以看出隨著檢測數據量的不斷增加，該方法雖然準確度有所下降但是依然保持著非常高的準確性。從圖5中可以看出，隨著數據量的增多，方案的檢測時間迅速增加，表明該方法對于算法的復雜度優化方面還存在著缺陷。綜上所述，該方法可以有效對于時間序列的異常進行檢測，并且在大數據量下依然具有非常高的準確性，但是其時間消耗方面需要進一步優化。

4.2 方案不足

該方法基于相似性的分析設計了時間序列異常檢測的方法，雖然可以有效完成異常檢測的目標，但是也存在著一些不足之處：

（1）對于時間序列的模式化還有著其他許多更優秀的方法，而不單單是頻域表示，如分段線性表示法等，可以采用其他抽象方法進行對比仿真。

（2）雖然動態模式匹配距離獲得了很高的準確性，但是其算法的速度依然有待提高，可以對其進行進一步的優化。

5 結論

本文基于相似性分析，結合局部密度計算數據點的數據密度設計了基于相似性分析的時間序列異常檢測方法。提出了動態模式匹配距離，使用模式而不是空間中的兩個點進行距離計算，模式的距離就直觀反映了每一個模式與其余模式之間的相似性，該距離很好的克服了時間序列振幅平移、時間伸縮等困難，采用頻域表示法模式化時間序列極大地降低了數據量，提高了算法效率。同時結合局部密度計算算法有效檢測了每一個目標數據的異常情況。總結而言，該方法不但可以有效檢測出異常數據，而且極大地降低了數據量提高了算法效率，同時可以克服時間序列的伸縮等缺陷，具有很好的擴展性。

[1]陳海燕,劉晨暉,孫 博.時間序列數據挖掘的相似性度量綜述[J].控制與決策,2017,2(1):1-11

[2]陳 然.基于相似性分析的時間序列異常檢測研究[D].重慶:西南交通大學,2011:30-33

[3]肖 輝.時間序列的相似性查詢與異常檢測[D].上海:復旦大學,2005:33-40

[4]曹文平,熊啟軍,羅 穎,等.基于相關性分析的時間序列異常檢測方法[J].信息系統工程,2012,22(10):131-132

[5]閆明月.時間序列相似性與預測算法研究及其應用[D].北京:北京交通大學,2014:18-30

[6]李 權,周興社.一種新的多變量時間序列數據異常檢測方法[J].時間頻率學報,2011,34(2):154-158

[7]唐 亮.時間序列挖掘和相似性查找技術的研究[D].上海:上海師范大學,2004:18-20

[8]方加果.基于相似性分析的時間序列數據挖掘算法研究[D].杭州:浙江大學,2011:33-35

[9]楊永強.基于相似性分析的時間序列數據挖掘研究[D].重慶:西南交通大學,2007:22-25

[10]曾海泉.時間序列挖掘與相似性查找技術研究[D].上海:復旦大學,2003:20-30

[11]馮 鈞,陳煥霖,唐志賢,等.一種基于 DTW 的新型股市時間序列相似性度量方法[J].數據采集與處理,2015,30(1):99-105

[12]張 軍.基于時間序列相似性的數據挖掘方法研究[D].南京:東南大學,2006:33-39

[13]邱均平,王菲菲.時間序列相似性查詢與索引方法研究[C].中國索引學會年會暨學術研討會,2009:4-8

[14]門連生,衛婧菲,李 中.基于形態相似距離的時間序列相似性度量[J].計算機工程與應用,2015,51(4):120-122

[15]劉 杰.時間序列相似性查詢的研究與應用[D].北京:北方工業大學,2016

[16]劉永志.基于兩點的時間序列相似性研究[J].鹽城工學院學報:自然科學版,2014,27(4):1-4

The Detection Method onAbnormal Time Series on account of Similarity Analysis

SUN Yan,LIN Yi
School of Digital Media/Jiangnan University,Wuxi 214000,China

Time series data are collected at different time points according to the time order to reflect an objective variation states and contents with time.This paper took frequency domain to express the time series in consideration of the magnanimity and complexity of time series and propose the detection method on abnormal time series on account of similarity analysis to take a dynamic pattern matching distance as a index to calculate the similarity between every model and others hereby to ensure the abnormal state.This method could greatly reduce the complexity in data search and improve the efficiency and accuracy of the system.

Time series;similarity analysis;dynamic pattern matching;abnormal detection

TP39

:A

:1000-2324(2017)02-0287-06

10.3969/j.issn.1000-2324.2017.02.026

2016-08-23

:2016-10-02

孫 焱(1992-),男,研究生.研究方向:時間序列數據挖掘.E-mail:thierry14henry12@163.com