孫 焱,林 意

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

基于相似性分析的時(shí)間序列異常檢測(cè)方法

孫 焱,林 意

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

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

時(shí)間序列;相似性分析;動(dòng)態(tài)模式匹配;異常檢測(cè)

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

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

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

1 時(shí)間序列的模型

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

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

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

2 時(shí)間序列的相似性度量

2.1 Minkowski距離

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

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

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

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

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

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

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

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

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

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

從上述公式可以看出，模式是由他的長(zhǎng)度和斜率這兩個(gè)特征表示。由于模式的長(zhǎng)度與時(shí)間序列的振幅大小無(wú)關(guān)，而其斜率則體現(xiàn)了時(shí)間序列振幅的相對(duì)大小，所以所提的動(dòng)態(tài)模式匹配距離可以克服時(shí)間序列的振幅平移與伸縮變換。除此以外，因?yàn)椴捎昧四Ｊ降膭?dòng)態(tài)匹配方法，可以實(shí)現(xiàn)時(shí)間序列在時(shí)間軸上的伸縮和彎曲。

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

3 時(shí)間序列的異常檢測(cè)

3.1 時(shí)間序列的異常模式

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

圖1 時(shí)間序列異常Fig.1 The abnormal time series

3.2 K-近鄰原理

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

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

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

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

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

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

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

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

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

3.3 基于相似性分析的異常檢測(cè)算法

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

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

圖2 時(shí)間序列異常檢測(cè)流程Fig.2 The detection process of abnormal time series

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

4.1 方法驗(yàn)證

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

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

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

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

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

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

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

4.2 方案不足

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

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

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

5 結(jié)論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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