基于頻繁模式發(fā)現(xiàn)的時(shí)間序列異常檢測(cè)方法

李海林，鄔先利

(華僑大學(xué) 信息管理系，福建 泉州 362021)(*通信作者電子郵箱1519998683@qq.com)

0 引言

近幾年，時(shí)間序列的異常研究漸漸興起，成為時(shí)間序列數(shù)據(jù)挖掘的一個(gè)新熱點(diǎn)，并被廣泛地應(yīng)用于航天、醫(yī)療、網(wǎng)絡(luò)監(jiān)測(cè)等領(lǐng)域。航路飛行目標(biāo)的屬性異常檢測(cè)是確保及時(shí)發(fā)現(xiàn)飛行異常的關(guān)鍵問(wèn)題，對(duì)此，王曉華等[1]通過(guò)在時(shí)間序列上的指派融合，對(duì)比預(yù)測(cè)值和觀測(cè)值差異，檢測(cè)航路目標(biāo)異常變化。在時(shí)間序列的異常檢測(cè)實(shí)際應(yīng)用中，劉煒等[2]從時(shí)間序列角度出發(fā)，提出一種基于結(jié)構(gòu)相似度準(zhǔn)則的輸油管道泄漏檢測(cè)定位方法。

在時(shí)間序列異常研究中，相對(duì)于單個(gè)序列點(diǎn)的異常，大家更多關(guān)心的是序列在一段時(shí)間內(nèi)的異常變化情況[3]。現(xiàn)有的方法有基于擴(kuò)展符號(hào)聚集近似的水文時(shí)間序列異常檢測(cè)方法(Extended Symbolic Aggregate Approximation based anomaly mining of hydrological time series, ESAA)[4]。首先通過(guò)基于擴(kuò)展符號(hào)聚集近似(Extended Symbolic Aggregate Approximation, ESAX)方法對(duì)時(shí)間序列進(jìn)行重新描述，然后計(jì)算某序列與時(shí)間序列數(shù)據(jù)集中其他序列之間的累積距離，以此來(lái)衡量其異常程度。時(shí)間序列的累積距離越小，其為異常的可能性也就越小。該方法能較好地壓縮數(shù)據(jù)并發(fā)現(xiàn)異常，但對(duì)于時(shí)間序列的異常檢測(cè)，每增加一條新的序列就需要該序列與數(shù)據(jù)集中每一條序列作距離測(cè)量，如果數(shù)據(jù)集中的序列過(guò)少則不能較好地發(fā)現(xiàn)異常；然而，如果數(shù)據(jù)集中的序列過(guò)多則會(huì)耗時(shí)耗力，特別是對(duì)增量式數(shù)據(jù)，更是不適用。后續(xù)研究在此問(wèn)題上提出基于層級(jí)實(shí)時(shí)記憶算法的時(shí)間序列異常檢測(cè)方法[5]、基于滑動(dòng)窗口預(yù)測(cè)的水文時(shí)間序列異常檢測(cè)方法(Time Series Outlier Detection based on sliding window prediction, TSOD)[6]等，通過(guò)對(duì)時(shí)間序列內(nèi)在模式關(guān)系進(jìn)行學(xué)習(xí)，建立預(yù)測(cè)模型，通過(guò)比較預(yù)測(cè)值和真實(shí)值的偏離程度來(lái)判斷數(shù)據(jù)是否異常。這類方法對(duì)含有噪聲的數(shù)據(jù)檢測(cè)率較低，對(duì)數(shù)據(jù)干擾較為敏感。鑒于傳統(tǒng)方法對(duì)增量式數(shù)據(jù)挖掘效率較低等問(wèn)題，提出基于頻繁模式的時(shí)間序列異常檢測(cè)方法。

1 相關(guān)理論基礎(chǔ)

1.1 符號(hào)集合近似

符號(hào)集合近似(Symbolic Aggregate Approximation, SAX)[7-8]是由Keogh在分段累積近似(Piecewise Aggregate Approximation, PAA)的基礎(chǔ)上提出的一種有效的時(shí)間序列數(shù)據(jù)離散化降維方法,通過(guò)將數(shù)值轉(zhuǎn)換為離散的符號(hào)來(lái)對(duì)時(shí)間序列重新描述，因其簡(jiǎn)單易用、不依賴于具體實(shí)驗(yàn)數(shù)據(jù)等特點(diǎn)而得到越來(lái)越多的關(guān)注。

SAX可分為3個(gè)步驟。

首先,用Z-score標(biāo)準(zhǔn)化方法對(duì)時(shí)間序列L={l1,l2,…,li,…,lm}(例如t=(0∶0.001∶2),L=sint)進(jìn)行預(yù)處理，得到均值為0、標(biāo)準(zhǔn)差為1的序列C={c1,c2,…,ci,…,cm}。

(1)

然后,選擇合適的壓縮閾值w(例：w=1 000),對(duì)C進(jìn)行 PAA表示，得到U={u1,u2,…,un}(例如U={0.65，1.35，0.82，-0.47，-1.33，-0.96，-0.20})其中m是序列L的長(zhǎng)度，n為時(shí)間序列的PAA表示的長(zhǎng)度。

最后,離散化，選定字母集大小即基大小a(例如a=3),根據(jù)字母集大小在高斯分布表(如表1)中查找區(qū)間的系列分裂點(diǎn)。

表1 基從3到7的分裂點(diǎn)

將PAA表示的均值映射為對(duì)應(yīng)的字母，最終離散化為字符串H={h1,h2,…,hn}(例如H={a,a,a,c,c,c,b})。其主要實(shí)現(xiàn)過(guò)程如圖1所示。

圖1 SAX方法實(shí)現(xiàn)過(guò)程示意圖

1.2 頻繁模式

頻繁模式是頻繁地出現(xiàn)在數(shù)據(jù)集中的模式。如首先購(gòu)買PC，然后是數(shù)碼相機(jī)，再后是內(nèi)存卡，如果它頻繁地出現(xiàn)在購(gòu)物歷史數(shù)據(jù)庫(kù)中，則稱它為一個(gè)(頻繁的)序列模式。頻繁模式挖掘是一項(xiàng)數(shù)據(jù)挖掘任務(wù)，它發(fā)現(xiàn)頻繁出現(xiàn)并且具有某些突出性質(zhì)的模式，這些性質(zhì)使它們有別于其他模式，常常揭示某些固有的和有價(jià)值的規(guī)律。

序列模式挖掘算法[9-10]就是找出序列支持度大于或等于min_sup的所有頻繁序列, 其中，min_sup是用戶預(yù)先指定的最小支持度閾值。假設(shè)有序列數(shù)據(jù)集D={I1,I2,…,Ia}，一般的序列I={k1,k2,…,kp},序列I的支持度support(I)是包含I的所有數(shù)據(jù)序列所占數(shù)據(jù)集D的比例。如果序列I的支持度大于或等于用戶指定閾值min_sup，則稱I是一個(gè)頻繁序列。

support(I)=P(I∪D)

(2)

設(shè)n維序列P={p1,p2,…,pn},m維序列Q={q1,q2,…,qm}，其中m>n，若序列P中每個(gè)元素都在序列Q中相同位置出現(xiàn)，即pi=qi(i

頻繁序列挖掘和頻繁項(xiàng)集挖掘一樣，首先遍歷一次序列數(shù)據(jù)集D，得到所有的頻繁1-序列, 按照頻繁1-序列把數(shù)據(jù)集D劃分為各個(gè)頻繁 1-序列作為前綴的投影數(shù)據(jù)集; 在生成得到的各個(gè)投影數(shù)據(jù)集中繼續(xù)遞歸挖掘子頻繁序列; 將投影數(shù)據(jù)集中的序列當(dāng)作新的序列數(shù)據(jù)集，按照上述步驟重新掃描并形成頻繁序列項(xiàng)，然后挖掘各個(gè)頻繁項(xiàng)的投影數(shù)據(jù)集，直到?jīng)]有新的投影數(shù)據(jù)集產(chǎn)生，即獲得所有的頻繁序列。

2 異常序列檢測(cè)

2.1 頻繁模式挖掘

頻繁模式的挖掘是本文提出的新方法中的重點(diǎn)，也是比較傳統(tǒng)方法的優(yōu)勢(shì)所在，因?yàn)槔碚撋系玫降念l繁模式看作正常序列的標(biāo)準(zhǔn)，省去了待測(cè)序列與所有序列都作相似性度量的繁雜，只需與該模式作相似性度量即可初步判斷其是否為異常序列。

在尋找頻繁模式前需對(duì)所有序列進(jìn)行預(yù)處理，用SAX方法對(duì)時(shí)間序列進(jìn)行重新描述可以在壓縮數(shù)據(jù)的同時(shí)保留較多的局部信息，而且分段過(guò)程能實(shí)現(xiàn)數(shù)據(jù)的噪聲消除，重新描述的數(shù)據(jù)結(jié)果在視覺(jué)上表現(xiàn)得簡(jiǎn)潔直觀。

對(duì)頻繁模式挖掘，主要算法步驟如下。

輸入 訓(xùn)練序列，最小支持度min_sup;

輸出 頻繁序列p。

步驟1 用SAX方法將序列符號(hào)化，得到字符序列。

步驟2 首先遍歷一次字符序列S，提取序列中每個(gè)長(zhǎng)度為1的字符存入候選集U(相同字符只提取一次)。

步驟3 查找序列中U中每個(gè)序列的個(gè)數(shù)，計(jì)算其支持度。

步驟4 將支持度大于min_sup的1-序列表示為候選頻繁序列q，若q為空，則跳到步驟7)；反之，p=q。

步驟5 將p進(jìn)行自連接得到新的候選集并讓其替代U。

步驟6 檢測(cè)U是否為空，若U為空，則繼續(xù)步驟7；否則跳到步驟3。

步驟7 輸出最終的頻繁序列p。

該方法結(jié)合了時(shí)間序列的頻繁序列挖掘和數(shù)據(jù)挖掘中頻繁項(xiàng)集的挖掘思想，不同于這兩種思想的是該方法對(duì)時(shí)間序列不需要進(jìn)行分段，沒(méi)有數(shù)據(jù)項(xiàng)，僅僅用字符序列進(jìn)行挖掘，省去了序列劃分的繁雜過(guò)程，也避免了因序列劃分不當(dāng)而引起的某些模式被忽略的情況。方法過(guò)程中的支持度是序列模式的個(gè)數(shù)。該方法至少要遍歷序列S一遍，但時(shí)間復(fù)雜度不高，當(dāng)min_sup為1且S中所有字符不同時(shí)，時(shí)間復(fù)雜度最高為n2，但這樣的挖掘是沒(méi)有意義的，所以在一般情況下，時(shí)間復(fù)雜度都會(huì)比這個(gè)小很多。

2.2 異常檢測(cè)

目前，時(shí)間序列的異常還沒(méi)有一個(gè)公認(rèn)的定義，普遍采用Hawkin給出的定義[11]：異常是在數(shù)據(jù)集中偏離大部分?jǐn)?shù)據(jù)的數(shù)據(jù)，使人懷疑這些數(shù)據(jù)是由不同的機(jī)制產(chǎn)生的，而非隨機(jī)偏差。由此可以想到異常所偏離的大部分?jǐn)?shù)據(jù)一定存在一個(gè)共同的模式，所以本文要用挖掘出的這一模式作異常檢測(cè)，便會(huì)省去許多繁雜的過(guò)程。

同時(shí)，為了檢測(cè)出所測(cè)序列的片段異常，本文需要對(duì)序列進(jìn)行分段。滑動(dòng)窗口分段壓縮算法[12]是通過(guò)不斷利用最小二乘法去擬合當(dāng)前窗口所有樣本點(diǎn)組成的子序列，若擬合誤差沒(méi)有超過(guò)預(yù)先設(shè)置好的閾值，則擴(kuò)大窗口加入新的樣本點(diǎn)到子序列直到窗口到達(dá)終點(diǎn)。若子序列的擬合誤差超過(guò)閾值，則從下一個(gè)樣本點(diǎn)開始重新劃分窗口繼續(xù)擬合直線。

結(jié)合上述方法思想，本文提出的異常檢測(cè)方法步驟如下：

輸入 需檢測(cè)的時(shí)間序列L，滑動(dòng)窗口分段的擬合誤差maxError，頻繁模式序列p；

輸出 序列L的異常片段G。

步驟1 用滑動(dòng)窗口對(duì)序列L進(jìn)行分段：

1)初始化第一段子序列的分段點(diǎn)index=1；

2)i=index,判斷滑動(dòng)窗口是否到達(dá)終點(diǎn)，如果到達(dá)終點(diǎn)，則跳到5)；

3)往滑動(dòng)窗口中加入新的序列點(diǎn)Li，利用最小二乘法去擬合當(dāng)前窗口所有樣本點(diǎn)組成的子序列；

4)判斷擬合誤差是否大于閾值maxError，如果小于maxError，則令i=i+1跳到3)；

5)合并該子序列到F，如果滑動(dòng)窗口沒(méi)有到達(dá)終點(diǎn)，則跳到2)，反之執(zhí)行步驟2。

步驟2 用SAX將子序列集F符號(hào)化，生成符號(hào)表示的子序列集H。

步驟3 用最長(zhǎng)公共子序列對(duì)頻繁模式序列p與H作相似性度量，找出H中相似度低的子序列，并將其存入異常序列候選集G。

步驟4 計(jì)算異常序列候選集G占序列L的比例，如果比例超過(guò)0.5，提示頻繁序列已經(jīng)過(guò)期，需挖掘新的頻繁模式；否則輸出G。

待測(cè)序列L的長(zhǎng)度為m時(shí)，該方法中滑動(dòng)窗口分段的時(shí)間復(fù)雜度為m。當(dāng)maxError最小，即分段結(jié)果為每個(gè)數(shù)據(jù)自成一段時(shí)，相似性度量的時(shí)間復(fù)雜度為m，所以該方法的時(shí)間復(fù)雜度最大為2m。

3 數(shù)值實(shí)驗(yàn)

3.1 仿真實(shí)驗(yàn)

3.1.1 實(shí)驗(yàn)數(shù)據(jù)

對(duì)心電圖時(shí)間序列的異常檢測(cè)具有重要的醫(yī)學(xué)價(jià)值，對(duì)于重癥患者實(shí)行實(shí)時(shí)的心臟監(jiān)控也是必要的。本文實(shí)驗(yàn)所采用的數(shù)據(jù)集從 MIT-BIH ECG 數(shù)據(jù)庫(kù)[13]中下載。 MIT-BIH 數(shù)據(jù)庫(kù)共包含 48 條超過(guò)30 min的心電圖數(shù)據(jù)。 圖3實(shí)驗(yàn)結(jié)果所使用的數(shù)據(jù)是編號(hào)為104的時(shí)間序列，該序列為一個(gè)66歲女性30 min的心電圖數(shù)據(jù)，實(shí)驗(yàn)選取了前5 000個(gè)數(shù)據(jù)點(diǎn)做實(shí)驗(yàn)。表2給出了該序列的特征點(diǎn)以及相應(yīng)發(fā)生時(shí)刻, 其中室性早搏(Premature Ventricular Contractions, PVC)是多樣的，幾次爆發(fā)的肌肉噪聲。

表2 實(shí)驗(yàn)數(shù)據(jù)基本信息

3.1.2 實(shí)驗(yàn)準(zhǔn)備

參數(shù)maxError,選擇該參數(shù)時(shí)可觀察序列的波形，盡可能地使分段能包含一個(gè)周期序列(如圖2)，該實(shí)驗(yàn)選擇的maxError=170；參數(shù)min_sup,選擇該參數(shù)時(shí)觀察訓(xùn)練序列的波形，大概有幾個(gè)完整的正常周期就擬訂為幾，該示例實(shí)驗(yàn)選擇的min_sup=5(如圖2)；w主要是符號(hào)化時(shí)對(duì)序列的壓縮，該參數(shù)的選擇表現(xiàn)的是序列的走向，所以可根據(jù)時(shí)間序列的具體情況而定，如果序列驟變性較強(qiáng)則不應(yīng)該選擇過(guò)大，視具體序列而定，該實(shí)驗(yàn)示例選擇的w=50；a為字母集大小，該實(shí)驗(yàn)示例選擇的a=3。

圖2 訓(xùn)練數(shù)據(jù)集

3.1.3 實(shí)驗(yàn)過(guò)程

用SAX方法把序列R進(jìn)行符號(hào)化得到S={acaabbbcbabbbcabbbcbabbbcbabba}，用時(shí)間序列的頻繁模式挖掘算法尋找符號(hào)序列S中的頻繁序列，獲得頻繁序列p={ab,bb}，用滑動(dòng)窗口分段對(duì)序列L進(jìn)行分段，得到的子序列在L中的位置為F={1～232,233～539,540～805,806～1 118, 1 119～1 442,1 443～1 645,1 646～2 067,2 068～2 361,2 362～2 651,2 652～2 941,2 942～3 231,3 232～3 513,3 514～3 715,3 716～4 142,4 143～4 423,4 424～4 708,4 709～4 997,4 998～5 000}，再次用SAX方法將子序列集F符號(hào)化，生成符號(hào)表示的子序列集H={cbaaba}{a} {acaab}{bacbabb}{bbcaab}{bbcbabb}{bbcaabb}{accbb}

{bbbbaabba}{cbabbb}{cbabbb}{ccabcb}{ccabbb}{ccabbb}

{accbb}{babbabbab}{caabba}{caabba}，再用p與H進(jìn)行相似性度量，找出相似度低的子序列，并將其存入異常序列候選集G={1 442～1 645,3 513～3 715,4 997～5 000}，最后計(jì)算異常序列候選集G占序列L的比例為0.166 7，小于0.5，所以輸出G。

3.1.4 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)結(jié)果如圖3所示，結(jié)合表1對(duì)數(shù)據(jù)的描述可發(fā)現(xiàn)，該異常片段為該數(shù)據(jù)產(chǎn)生者爆發(fā)的肌肉噪聲，實(shí)驗(yàn)結(jié)果與數(shù)據(jù)的描述相符。

圖3 異常檢測(cè)實(shí)驗(yàn)結(jié)果

3.2 對(duì)比實(shí)驗(yàn)

為檢驗(yàn)基于頻繁模式的時(shí)間序列異常檢測(cè)方法的可行性和優(yōu)越性，在此選擇3種性質(zhì)不同的數(shù)據(jù)進(jìn)行異常檢測(cè)實(shí)驗(yàn)，采用余宇峰等[6]提出的基于滑動(dòng)窗口預(yù)測(cè)的水文時(shí)間序列異

常檢測(cè)(TSOD)和劉千等[4]提出的基于擴(kuò)展符號(hào)聚集近似的水文時(shí)間序列異常挖掘(ESAA)兩種方法與本文方法作比較。

3種數(shù)據(jù)各具代表性:第1種數(shù)據(jù)MRN_measles數(shù)據(jù)是真實(shí)數(shù)據(jù)，其中異常的數(shù)據(jù)明顯高于其他數(shù)據(jù)點(diǎn); 第2種數(shù)據(jù)Keogh_Data是仿真數(shù)據(jù)，其中加入了較多干擾; 第3種數(shù)據(jù)Aritificial_Data是比較規(guī)則的周期數(shù)據(jù)異常。下面是三種數(shù)據(jù)的實(shí)驗(yàn)結(jié)果及分析。

3.2.1 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)1 真實(shí)數(shù)據(jù)MRN_measles[14]。該數(shù)據(jù)是長(zhǎng)度為534的時(shí)間序列，在區(qū)間[150，170]和[420，534]存在異常情況，如圖4(a)所示。通過(guò)TSAD方法對(duì)該序列進(jìn)行異常檢測(cè)，實(shí)驗(yàn)的相關(guān)參數(shù)分別設(shè)置為滑動(dòng)窗口最大誤差maxError=25，符號(hào)化壓縮閾值w=10，最小支持度min_sup=15。檢測(cè)出的異常片段為[152,166]、[417,534]，實(shí)驗(yàn)結(jié)果如圖4(b)所示；通過(guò)ESAA方法對(duì)該序列進(jìn)行異常檢測(cè)，檢測(cè)出的異常片段為 [151,165]、[181,195],實(shí)驗(yàn)結(jié)果如圖4(c)所示。通過(guò)TSOD方法對(duì)該序列進(jìn)行異常檢測(cè)，檢測(cè)出的異常片段為[158,162]、[195,196]，實(shí)驗(yàn)結(jié)果如圖4(d)所示。

圖4 三種方法對(duì)MRN_measles數(shù)據(jù)實(shí)驗(yàn)結(jié)果

圖4中虛線畫出的序列為檢測(cè)出的異常片段，可以看出，TSAD能很好地檢測(cè)出原序列的兩個(gè)異常片段；ESAA只能較好的檢測(cè)原序列中凸起的一個(gè)片段異常，而未能檢測(cè)出序列中平滑的片段異常，同時(shí)還誤將片段[181,195]認(rèn)為異常；TSOD方法雖然也檢測(cè)出來(lái)凸起的片段異常，但沒(méi)能準(zhǔn)確地測(cè)出該段的所有異常，同時(shí)也誤將一個(gè)正常片段當(dāng)作異常。比較三種方法對(duì)數(shù)據(jù)MRN_measles的檢測(cè)效果可以看出，TSAD方法檢測(cè)效果最好，其次是ESAA方法，TSOD方法檢測(cè)效果最差。

實(shí)驗(yàn)2 Keogh_Data數(shù)據(jù)是Keogh等[15]進(jìn)行時(shí)間序列異常檢測(cè)時(shí)使用的仿真數(shù)據(jù)，由以下隨機(jī)過(guò)程產(chǎn)生:

(3)

(4)

其中:t=1,2，…，N, 實(shí)驗(yàn)取值為N=800，即實(shí)驗(yàn)仿真得到長(zhǎng)度為800的序列；自定義n(t)是均值為0，標(biāo)準(zhǔn)差為1的加性高斯噪聲；e(t)為自定義的異常事件，具體如下:

(5)

通過(guò)TSAD對(duì)序列L2(t)進(jìn)行異常檢測(cè)，實(shí)驗(yàn)的相關(guān)參數(shù)分別設(shè)置為滑動(dòng)窗口最大誤差maxError=27，符號(hào)化壓縮閾值w=3，最小支持度min_sup=35。檢測(cè)出的異常片段為[402,448]，實(shí)驗(yàn)結(jié)果如圖5(b)所示。通過(guò)ESAA方法對(duì)該序列進(jìn)行異常檢測(cè)，檢測(cè)出的異常片段為[601, 650]、[701,750]，實(shí)驗(yàn)結(jié)果如圖5(c)所示。通過(guò)TSOD方法對(duì)該序列進(jìn)行異常檢測(cè),檢測(cè)出的異常片段為[55,56]、[68,69]、[91,92]、[115,116]、[129,139]、[140,141]、[232,233]、[235,236]、[246,247]、[255,256]、[269,270]、[290,291]、[320,321]、[344,345]、[393,394]、[396,397]、[419,420]、[472,473]、[485,486]、[498,499]、[504,505]、[519,522]、[597,598]、[614,615]、[630,631]、[640,641]、[650,651]、[679,680]、[695,696]、[727,728]、[743,744]、[746,747]、[793,794]，實(shí)驗(yàn)結(jié)果圖5(d)所示。

由圖5可以看出：TSAD方法正確地檢測(cè)出了原序列中的大部分異常，僅僅漏掉少有的個(gè)別異常點(diǎn)；而ESAA方法檢測(cè)到兩段異常片段，但沒(méi)能檢測(cè)出真正的異常片段，該方法對(duì)這種數(shù)據(jù)的檢測(cè)效果非常不理想；TSOD方法雖然檢測(cè)出了真正異常片段中的幾個(gè)小片段，但也將一些正常片段看作異常測(cè)出，誤報(bào)率也是較大，由此可以看出TSOD和ESAA兩種方法對(duì)Keogh_Data數(shù)據(jù)的檢測(cè)效果非常差。

實(shí)驗(yàn)3 Aritificial_Data數(shù)據(jù)[16]，時(shí)間序列由如下隨機(jī)過(guò)程產(chǎn)生：

(6)

(7)

其中t=1,2,…,N,實(shí)驗(yàn)取值為N=1 200，即實(shí)驗(yàn)仿真得到長(zhǎng)度為1 200的序列。序列L1(t)沒(méi)有異常，將時(shí)間序列L1(t)加上異常事件e(t),即變形為包含異常序列的時(shí)間序列L2(t)。異常事件e(t)定義如下：

e(t)=

(8)

通過(guò)TSAD方法對(duì)序列L2(t)進(jìn)行異常檢測(cè)，實(shí)驗(yàn)的相關(guān)參數(shù)分別設(shè)置為滑動(dòng)窗口最大誤差maxError=48，符號(hào)化壓縮閾值w=7，最小支持度min_sup=20。檢測(cè)出的異常片段為[94,203]、[499,609]、[807,923]，實(shí)驗(yàn)結(jié)果如圖6(b)所示。通過(guò)ESAA方法對(duì)該序列進(jìn)行異常檢測(cè)，檢測(cè)出的異常片段為[101,200]、[501,600]、 [801,900]，實(shí)驗(yàn)結(jié)果如圖6(c)所示。通過(guò)TSOD方法對(duì)該序列進(jìn)行異常檢測(cè)，檢測(cè)出的異常片段為[100,102]、[115,127]、[139,151]、[161,177]、[185,200]、[500,557]、[569,581]、[594,600]、[800,846]、[857,869]、[881,893]，實(shí)驗(yàn)結(jié)果如圖6(d)所示。

由圖6(a)和圖6(b)對(duì)比可以看出，TSAD方法能較好地測(cè)出原序列中存在的異常；對(duì)比圖6(a)和圖6(c)可以看出，ESAA方法能非常準(zhǔn)確地檢測(cè)出異常；對(duì)比圖6(a)和圖6(d)可以看出，TSOD方法只能檢測(cè)出原序列的部分異常，且這部分?jǐn)?shù)據(jù)是凸出正常模式的序列點(diǎn)，而將異常模式中與正常模式序列點(diǎn)數(shù)值相近的點(diǎn)看作正常數(shù)據(jù)，由此可以看出TSAD方法和ESAA方法對(duì)Aritificial_Data數(shù)據(jù)的檢測(cè)效果最好，TSOD方法的檢測(cè)效果最差。

圖5 三種方法對(duì)Keogh_Data數(shù)據(jù)實(shí)驗(yàn)結(jié)果

圖6 三種方法對(duì)Aritificial_Data數(shù)據(jù)實(shí)驗(yàn)結(jié)果

3.2.2 實(shí)驗(yàn)評(píng)估

為評(píng)價(jià)所提出的時(shí)間序列異常檢測(cè)方法的實(shí)驗(yàn)結(jié)果，采用檢測(cè)率(Detecton Rate, DR)、誤報(bào)率(False Positive Rate, FPR)和漏報(bào)率(False Negative Rate, FNR)作為算法檢測(cè)性能的度量指標(biāo)[16]。檢測(cè)率是指異常行為被正確檢測(cè)出來(lái)的比率，如果檢測(cè)算法不能精確地描述正常行為，那么就必然會(huì)出現(xiàn)各種誤報(bào)的情況，如果把正常行為誤報(bào)為異常行為，此情況稱為誤報(bào)；把這種錯(cuò)誤情況所占正常行為的比率，稱為誤報(bào)率。如果有異常行為不能被識(shí)別，無(wú)法被檢測(cè)出，這種情況被稱為漏報(bào)；把漏報(bào)的異常行為所占所有異常行為的比率，稱為漏報(bào)率[17]：

DR=(Y∩Y′)/Y

(9)

FPR=[Y-(Y∩Y′)]/(X-Y)

(10)

FNR=[Y-(Y∩Y′)]/Y

(11)

其中:X代表數(shù)據(jù)集，Y代表X中的異常數(shù)據(jù)集，Y′代表算法檢測(cè)出的異常數(shù)據(jù)集。

表3中給出了基于頻繁模式的時(shí)間序列異常檢測(cè)方法(TSAD)、基于擴(kuò)展符號(hào)聚集近似的水文時(shí)間序列異常挖掘方法(ESAA)和基于滑動(dòng)窗口預(yù)測(cè)的水文時(shí)間序列異常檢測(cè)方法(TSOD)對(duì)MRN_measles、Keogh_Data和Aritificial 三種數(shù)據(jù)的檢測(cè)實(shí)驗(yàn)結(jié)果。

由實(shí)驗(yàn)結(jié)果可以看出， MRN_measles和Keogh_Data兩種數(shù)據(jù)用TSAD方法的檢測(cè)效果最好，Aritificial_Data數(shù)據(jù)用ESAA方法的檢測(cè)效果最好，用TSAD方法的檢測(cè)效果也很好，對(duì)于這三種不同類型的數(shù)據(jù)，TSAD方法的平均檢測(cè)效果是最好的，并且比另外兩種方法好很多。同時(shí)由表3度量結(jié)果中的方差可以看出, TSAD方法的偏好性最小，對(duì)三種數(shù)據(jù)的檢測(cè)效果都非常好，ESAA方法對(duì)數(shù)據(jù)的偏好性最大，對(duì)Aritificial_Data數(shù)據(jù)的檢測(cè)率高達(dá)0.99，且誤報(bào)率為0，但對(duì)Keogh_Data數(shù)據(jù)的檢測(cè)率為0，分析其原因可以看出該算法對(duì)序列的噪聲非常敏感，會(huì)將一些噪聲誤認(rèn)為異常, 導(dǎo)致其受噪聲干擾性很嚴(yán)重， TSOD方法是三種方法中檢測(cè)效果最差，對(duì)三種數(shù)據(jù)的檢測(cè)率都很低，對(duì)Aritificial_Data數(shù)據(jù)的檢測(cè)相對(duì)于另外兩種數(shù)據(jù)較好，對(duì)數(shù)據(jù)的偏好性較嚴(yán)重，該方法也是受噪聲干擾大，但相對(duì)于ESAA方法較好一點(diǎn)。

表3 三種方法對(duì)比實(shí)驗(yàn)結(jié)果

由結(jié)果對(duì)三種方法進(jìn)行分析可看出，本文方法主要考慮的是序列整體的趨勢(shì)，在符號(hào)序列化中平滑了一些噪聲的干擾能很好地檢測(cè)出異常。相對(duì)于序列整體的異常，而對(duì)比方法TSOD更多考慮的是局部特征，該方法的主要思路是通過(guò)序列中任意一點(diǎn)的k近鄰點(diǎn)對(duì)該點(diǎn)進(jìn)行預(yù)測(cè)，如果預(yù)測(cè)值與該點(diǎn)實(shí)際值不超過(guò)預(yù)設(shè)閾值則可判定該點(diǎn)為正常點(diǎn)，反之為異常，該方法更多受到序列局部特征的影響，而且對(duì)序列所有元素值沒(méi)有進(jìn)行其他提取效果，所以受噪聲干擾大；而ESAA太注重最值的影響，因此噪聲干擾性更強(qiáng)?？傮w來(lái)說(shuō)，三種方法中TSAD最好，其次為ESAA，TSOD最差。

3.2.3 時(shí)間復(fù)雜度分析

在此假設(shè)需檢測(cè)序列的長(zhǎng)度為m，TSAD方法截取前n(n

3.2.4 實(shí)驗(yàn)總結(jié)

比較三種方法對(duì)三種不同數(shù)據(jù)的檢測(cè)效果和時(shí)間復(fù)雜度可以看出，TSAD方法的時(shí)間復(fù)雜度比TSOD方法稍大一點(diǎn)，但檢測(cè)效果明顯好很多，尤其是對(duì)于增量式數(shù)據(jù)，當(dāng)增加的數(shù)據(jù) 趨于無(wú)窮大時(shí)，TSAD方法和TSOD方法的時(shí)間復(fù)雜度近似相同，但檢測(cè)效果好很多?？偟膩?lái)說(shuō)，TSAD方法是最好的。

4 結(jié)語(yǔ)

針對(duì)傳統(tǒng)方法的復(fù)雜性和高消耗性，本文提出的基于頻繁模式的時(shí)間序列異常檢測(cè)方法能較好改善這一問(wèn)題，該方法同時(shí)從序列整體形態(tài)和局部特征的角度研究，能較準(zhǔn)確地發(fā)現(xiàn)序列中的異常片段，并且該方法使用的是對(duì)同種序列的一次性挖掘，在找出一種序列的頻繁模式后該序列新增加的數(shù)據(jù)便不再作頻繁模式的挖掘，只需執(zhí)行簡(jiǎn)單的相似性度量就可以檢測(cè)其中的異常片段。 本文方法的優(yōu)點(diǎn)在于能基于正常數(shù)據(jù)的頻繁模式檢測(cè)新加入數(shù)據(jù)的異常，實(shí)現(xiàn)動(dòng)態(tài)數(shù)據(jù)的異常檢測(cè)，并且對(duì)于新加入的數(shù)據(jù)只需與先挖掘的頻繁序列進(jìn)行簡(jiǎn)單的比較實(shí)驗(yàn)，不用耗費(fèi)太多資源； 但該方法也存在一些缺點(diǎn)，如參數(shù)太多，導(dǎo)致在運(yùn)行時(shí)調(diào)整參數(shù)太過(guò)復(fù)雜。進(jìn)一步的改進(jìn)方案需對(duì)參數(shù)進(jìn)行優(yōu)化，盡量地減少參數(shù)復(fù)雜性，同時(shí)對(duì)符號(hào)化表示方法進(jìn)行優(yōu)化，使其能更好地表示序列的形態(tài)，對(duì)頻繁模式的挖掘起到更普遍的作用，能夠更好地去發(fā)現(xiàn)現(xiàn)實(shí)生活中的動(dòng)態(tài)數(shù)據(jù)異常，免受噪聲數(shù)據(jù)的干擾。