孫 焱,林 意

江南大學(xué) 數(shù)字媒體學(xué)院,江蘇 無錫 214000

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

孫 焱,林 意

江南大學(xué) 數(shù)字媒體學(xué)院,江蘇 無錫 214000

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

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

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

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

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

1 時間序列的模型

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

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

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

2 時間序列的相似性度量

2.1 Minkowski距離

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

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

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

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

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

2.2 動態(tài)模式匹配距離

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

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

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

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

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

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

3 時間序列的異常檢測

3.1 時間序列的異常模式

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

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

3.2 K-近鄰原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1 方法驗證

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

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

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

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

圖4 不同數(shù)據(jù)量下準(zhǔn)確度（%）Fig.4 The detection accuracy on different data

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

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

4.2 方案不足

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

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

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

5 結(jié)論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[16]劉永志.基于兩點的時間序列相似性研究[J].鹽城工學(xué)院學(xué)報:自然科學(xué)版,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-),男,研究生.研究方向:時間序列數(shù)據(jù)挖掘.E-mail:thierry14henry12@163.com