時間序列的區(qū)域周期模式及挖掘算法

郭 靜，陳 欣，何 杰，譚志國

1(重慶工程學院 軟件與計算機學院，重慶 400056)

2(國防科技大學 計算機學院， 長沙 410073)

3(國防科技大學 電子科學與工程學院， 長沙 410073)

4(武警警官學院 信息通信系， 成都 610213)

1 引 言

挖掘周期性行為是理解時間序列特征的一個重要方面，在很多科學領(lǐng)域和社會領(lǐng)域都有重要的研究價值.如在生物信息學領(lǐng)域中，挖掘DNA序列中核酸和氨基酸的周期分布情況等[1]；在天文學領(lǐng)域，研究行星的周期性運行規(guī)律等[2]；在經(jīng)濟學領(lǐng)域，探測股票周期性波動趨勢等[3]；在網(wǎng)絡(luò)安全領(lǐng)域，檢測惡意軟件周期性行為等[4].

當前研究的周期模式主要包括全周期模式和部分周期模式[5-8]，其中全周期模式中周期段中的每一個位置都要參與周期變化，如物理學中鐘擺的運動趨勢等；而部分周期模式中只有部分位置參與周期變化，如某人的一日生活規(guī)律可能只有上、下班時間具有周期性，而飲食地點、工作地點并不一定具有周期性.其他類似研究如模糊周期性[9]、移動目標的周期性[10]以及事務(wù)數(shù)據(jù)庫的周期性[11]等雖然名稱有區(qū)別，但本質(zhì)上都屬于全周期模式和部分周期模式范疇.

但是在科學研究中經(jīng)常出現(xiàn)另外一種情況，即某一個時間序列在整體趨勢上可能并沒有明顯的周期性，但在時間序列的某一部分上隱含著短暫的周期性行為.由于出現(xiàn)的概率并不固定以及延續(xù)時間不能估計，因此在基于整體的挖掘分析上這種周期行為常常會被遺漏.

針對這種只在區(qū)域部分出現(xiàn)的周期性，本文形式化的提出了一種新型的周期模式，稱之為區(qū)域周期模式.區(qū)域周期模式的研究有利于挖掘時間序列中隱藏的周期性行為，從而為揭示時間序列特征提供了更好的工具和支撐.文獻[12]提出的密集型周期模式雖然也定義在部分時間序列上，但其只是區(qū)域周期模式的一種個例，與本文提出的概念并不一致.

全周期模式和部分周期模式的活躍期貫穿于整個時間序列，而區(qū)域周期模式只在時間序列的部分區(qū)域上存在.由于其存在位置、存在數(shù)量和周期性強度都沒有特點規(guī)律，因此傳統(tǒng)用于全周期模式或者部分周期模式的挖掘算法[5,7]，不能直接移植用來進行區(qū)域周期模式挖掘.本文首先對提出的區(qū)域周期模式進行了形式化的描述和分析，然后分別提出了基于迭代、基于類Apriori、基于一階區(qū)域周期模式密集度推薦區(qū)間的三種區(qū)域周期模式挖掘算法，最后在網(wǎng)絡(luò)安全領(lǐng)域公開數(shù)據(jù)集的基礎(chǔ)上，對三種挖掘算法進行了實驗測試，驗證了算法的可行性和有效性.

2 區(qū)域周期模式的形式化描述

2.1 基礎(chǔ)概念

假定S是一個等時間采樣的事件時間序列，S=e1,e2,…,en，ei∈L(i=1,2,…,n).其中n是時間序列的長度，L是事件集合，指代所有事件類型對應(yīng)的字符集.定義p為S的周期，則S可以劃分為至多C=?n/p」個等長周期區(qū)間(留下部分被丟棄).這些周期區(qū)間被稱為周期段，可以表示為：Ei=[eip+1,…,eip+p],i∈[0,C).

定義一個時間序列S中關(guān)于模式s的支持度supp和置信度conf為：

(1)

(2)

公式1中周期段Ei匹配模式s定義為，當且僅當，對于每一個位置j∈[1,p]，s中ej等于*或者與Ei中位置j的字符相同.同時，如果一個模式s′是s的子模式，可推理知，Ei匹配模式s′.

例1.S=abcdabccabcdabcdabddac，定義周期p=4，則S可以劃分為5個周期段：E1=abcd，E2=abcc，E3=abcd，E4=abcd，E5=abdd.如果定義模式s=abcd，則有：supp(s,S) = 3,conf(s,S) = 0.6.如果模式s=ab*d，則有：supp(s,S)=4，conf(s,S)=4/5=0.8.

2.2 區(qū)域周期模式的定義

定義1.全周期模式和部分周期模式.

給定長度為n的事件時間序列S，L為S的事件集合.指定min-conf為最小置信度，min-supp為最小支持度，p為周期.則有，如果一個模式s=e1,…,ei,…,ep(i∈[1,p],ei∈L)滿足：conf(s,S)≥min-conf，supp(s,S)≥min-supp.則稱s為S的一個全周期模式.如果一個模式s=e1,…,ei,…,ep(i∈[1,p],ei∈L∪{*})滿足：conf(s,S)≥min-conf，supp(s,S)≥min-supp，則稱s為S的一個部分周期模式.

例2.假定一個事件時間序列S=abcdabccabcdabcdabddac，周期p=4.定義min-conf=0.6,min-supp=3.可得事件集合L={a,b,c,d}.如果一個模式s=abcd，則有：conf(s,S)=0.6≥min-conf且supp(s,S) = 3 ≥min-supp.在這種情況下，稱s為S的一個全周期模式.如果定義min-conf=0.8，由于conf(s,S)=0.6≤min-conf，則s不是S的全周期模式.同時，如果修改模式s為s=ab*d，則有：conf(s,S)=0.8≥min-conf且supp(s,S) = 4 ≥min-supp.所以，模式s=ab*d是S的一個部分周期模式，但不是一個全周期模式，因為s中含有*字符.

定義2.區(qū)域周期模式

給定長度為n的事件時間序列S，L為S的事件集合.指定min-conf為最小置信度，min-supp為最小支持度，p為周期，則有C=?n/p」，周期段Ei=[eip+1,…,eip+p],i∈[0,C).如果Sub為S的一個子序列且Sub=[Ei,Ei+1,…,Ej]，(i≥0,j≤p),稱Sub為S的一個區(qū)域，稱Sub所含周期段數(shù)量(j-i+ 1)為Sub的區(qū)域長度，記為l.若存在一個模式s=e1,…,ei,…,ep(i∈[1,p],ei∈L∪{*})滿足：conf(s,Sub)≥min-conf，supp(s,Sub)≥min-supp，則基于定義1，s為Sub的一個部分周期模式.同時，稱s為S的一個區(qū)域周期模式.

例3.假定一個事件時間序列S=abcabcabcabcabdccdadaaaaccbccbccbccac且周期p=3，min-conf=0.6，min-supp=4. 如果一個模式s=ab*,有C=?37/3」=12，supp(s,S)=5, 則conf(s,S)=5/12min-conf，supp(s,Sub-S)=5>min-supp.基于定義1和定義2, 模式s=ab*是序列Sub-S的一個部分周期模式，是序列S的一個區(qū)域周期模式.

基于定義1可知，全周期模式和部分周期模式的區(qū)別僅在于全周期模式中的字符不能為*，即全周期模式的事件必須全部來自事件集合L，模式的階數(shù)等于周期p.而部分周期模式放松了這一要求，不必完全匹配，可以包含階數(shù)從1到p的所有滿足條件的模式.此外，相對于全周期模式和部分周期模式需要在所有周期段中滿足最小支持度和最小置信度這兩項條件，區(qū)域周期模式只需要在區(qū)域周期段(即總序列的部分子集)中滿足以上條件即可.

3 區(qū)域周期模式挖掘算法

3.1 基于迭代的區(qū)域周期模式挖掘算法

從基于區(qū)域周期模式的定義可以看出，如果能夠提供該周期模式在當前時間序列中的"區(qū)域"所在位置，則區(qū)域周期模式挖掘?qū)嶋H上等價于部分周期模式挖掘.所以區(qū)域周期模式挖掘的關(guān)鍵問題就在于定位待分析區(qū)域的策略.據(jù)此分析，本文提出了基于迭代的區(qū)域周期模式挖掘算法，本算法偽代碼如下所示.

算法1.基于迭代的區(qū)域周期模式挖掘算法

輸入:事件時間序列S=e1,e2,…,en，周期p，最小支持度m，最小置信度c

輸出:存放所有區(qū)域周期模式數(shù)據(jù)結(jié)構(gòu)的集合RPP

1.C=?n/p」

2.劃分S為C個周期段，得到SE=E1,E2,…,EC,Ei=[eip+1,…,eip+p],i∈[0,C)

3.For head in [1 :C-m+ 1]

4. For tail in [head+m-1:C]

5.Sub=[Ehead,…,Etail]

6. For everysdug by Hit(Sub,m,c)

7.rpp={S,

sup(s,Sub)

conf(s,Sub)

reg(head,tail)}

8.RPP←rpp

9. End

10. End

11.End

12.Forrppi,rppjinRPP

13. Ifrppi.s=rppj.s且rppi.reg?rppj.reg

14. DeleterppifromRPP

15.End

16.OutputRPP

本算法主要分以下3步進行：

首先，基于迭代定位當前時間序列中所有可能的區(qū)域；

然后，采用部分周期模式經(jīng)典挖掘算法對上一步所得每一個區(qū)域進行部分周期模式挖掘，得出所有存在的區(qū)域周期模式；

最后，剔除冗余的區(qū)域周期模式，得到該時間序列最終的區(qū)域周期模式集合.

在算法第1步中，若該時間序列的周期段數(shù)為C，所求模式的最小支持度min-supp為m，則所求區(qū)域的長度l的最小值即為m，最大值為C.由于區(qū)域在時間序列中具有連續(xù)性，因此該時間序列中長度為m的區(qū)域數(shù)量為C-m+1，長度為m+ 1的區(qū)域數(shù)量則為C-(m+1)+1，以此類推.綜上，該時間序列中可能存在的區(qū)域數(shù)量N即為：

(3)

在第2步中，本文利用Han等人提出的最大子模式Hit算法[7]對每一個待分析區(qū)域進行部分周期模式求解.全部求解完成后，得到所有待分析區(qū)域的部分周期模式集合，也就是該時間序列內(nèi)存在的所有區(qū)域周期模式集合.

最后，根據(jù)定義2，區(qū)域周期模式只需要在總時間序列的一段子集(區(qū)域)上滿足支持度和置信度大于一定閾值的條件即可，因此，同一個區(qū)域周期模式可能在多個區(qū)域中滿足條件.本文對算法第2步中所得區(qū)域周期模式集合進行去冗，即：如果一個區(qū)域周期模式在兩個區(qū)域都滿足條件且兩個區(qū)域存在包含與被包含關(guān)系，則只保留較大的區(qū)域.

本算法采用迭代方式遍歷時間序列上的所有可能區(qū)域，從中挖掘存在的區(qū)域周期模式，其優(yōu)點在于能得到完整的挖掘結(jié)果，求解精度高，但存在運算效率較低的缺點.

3.2 基于類Apriori的區(qū)域周期模式挖掘算法

在(全或部分)周期模式挖掘中，基于Apriori原則[11]可以有效地降低計算代價.其可以描述為："每一個周期為p的(全/部分)周期模式的子模式也是一個周期為p的頻繁模式"[7].這就使得我們可以通過i-1(i∈[2,p)) 階周期模式結(jié)合1階周期模式來推導所有可能的i階周期模式.在區(qū)域周期模式挖掘中，Apriori原則同樣適用，可以描述為："所有周期為p的區(qū)域周期模式的所有子模式同樣是周期為p的區(qū)域周期模式".可基于區(qū)域周期模式的定義證明如下：

證明：假設(shè)一個模式s是時間序列S的一個區(qū)域周期模式，則存在S的某一個區(qū)域Sub，使得：supp(s,Sub)≥min-supp且conf(s,Sub)≥min-supp.假定s′是模式s的一個子模式，不失一般性，根據(jù)子模式的含義可知:supp(s′,Sub)≥supp(s,Sub)≥min-supp且conf(s′,Sub)≥conf(s,Sub)≥min-conf由此可知，s′同樣為Sub的部分周期模式，即為S的區(qū)域周期模式.得證.

在此本文提出一種基于類Apriori原則的區(qū)域周期模式挖掘算法.同常規(guī)Apriori算法類似，主要分為獲取一階區(qū)域周期模式和推導高階區(qū)域周期模式兩大步驟.

步驟1.獲取一階區(qū)域周期模式集合F1.

在全(部分)周期模式中，由于每一個模式的活躍期都定義在時間序列的完整時間段上，所以當最小置信度min-conf大于0.5時，每一個周期段位置上的一階周期模式都只有1個.但在區(qū)域周期模式中，由于一階區(qū)域周期模式可以活躍在時間序列的多個區(qū)域內(nèi)，因此滿足條件的一階區(qū)域周期模式不僅可以有多個，而且可以在多個區(qū)域范圍上.對于每一個一階區(qū)域周期模式，本文都只記錄其滿足條件的最大區(qū)域.求解一階區(qū)域周期模式過程見算法2.主要過程為：首先初始化一個數(shù)據(jù)結(jié)構(gòu)F1，用來記錄所有一階區(qū)域周期模式及其最大區(qū)域和置信度.然后對于每一個周期段上的位置j和每一個L中的字符l(對應(yīng)這里的一階模式)，檢查所有可能的區(qū)域并且判斷在每一個區(qū)域上l是否滿足最小置信度和最小支持度條件.同時，本文提出了三種剪枝策略用來降低計算代價.

算法2.一階區(qū)域周期模式求解算法

輸入:事件時間序列S=e1,e2,…,en，周期p，最小支持度m，最小置信度c

輸出:存放一階區(qū)域周期模式數(shù)據(jù)結(jié)構(gòu)的集合F1

1.C=?n/p」

2.劃分S為C個周期段，得到SE=E1,E2,…,EC,Ei=[eip+1,…,eip+p],i∈[0,C)

3.Forjin [1 :p]

4.J=[E0j,E1j,…,E(C-1)j] //周期段位置為j的所有事件集合

5. LJ=distinct(J) //J中獨立的事件類型

6. Forlin LJ

7. TP=J(l) //TP記錄J中出現(xiàn)字符l的時間點

8. TS←TP //轉(zhuǎn)換TP到多個時間段(把連續(xù)的時間點作為一個時間段)

9. For start in [1 : |TS|]

10. For end in [|TS| : start]

11.R=TS[start : end]

12. Ifsupp(l,R)≥m且conf(l,R)≥c

13. IfR?FLJ.R

14.FLJ←{R.conf(l,R)}

15. Goto line 9 for next start

16. End

17. End

18.FJ←FLJ

19. End

20.F1←FJ

21.End

22.OutputF1

1) 本文將連續(xù)的周期段序號作為一個分組來處理，如算法第8行.這樣的處理將有效降低遍歷的數(shù)目.舉例來講，如在位置j上，字符a活躍在E1,E2,E4,E5,E6,E7,E10等7個周期段上.如果按周期段序號來遍歷區(qū)域，則共有{E1}、{E1,E2}、{E1,E2,E4}…{E7,E10}、{E10}共7×(7+1)/2=28個區(qū)域，如果將連續(xù)的周期段序號作為一個分組，得新組E1-new={E1,E2}、E2-new={E4,E5,E6,E7}、E3-new={E10}，則只需遍歷3×(3+1)/2 = 6個區(qū)域.之所以能夠這么做，是因為在本算法中對于每一個模式都計算其能夠活躍的最大區(qū)域，對于任意模式，連續(xù)的活躍周期段都會增加其支持度和置信度，因此連續(xù)的活躍周期段是不可分隔的.這里的活躍周期段是指所有在當前位置出現(xiàn)當前字符的周期段.

2)當遍歷區(qū)域時，設(shè)置結(jié)束邊界從遠周期段到近周期段，如算法第10行.如前文中的E1-new作為開始邊界時，本文首先判斷E3-new作為結(jié)束邊界時當前模式是否滿足約束條件.如果滿足，則記錄當前區(qū)域和模式(算法第14行)，并且直接跳轉(zhuǎn)到下一開始邊界(算法第15行)，而不再繼續(xù)判斷更近的E2-new作為結(jié)束邊界.這同樣是因為對于每一個模式，算法都試圖獲取其滿足條件的最大區(qū)域.如果在某一個區(qū)域內(nèi)滿足條件，則不必判斷其區(qū)域內(nèi)的子區(qū)域.這樣的策略可以進一步有效降低所遍歷區(qū)域的個數(shù).

3) 在循環(huán)過程中，當發(fā)現(xiàn)一個滿足條件的模式時，在記錄該模式和區(qū)域之前，需判斷當前區(qū)域是否已經(jīng)包含于已記錄的某一個區(qū)域，如果被包含，則不記錄當前區(qū)域，直接跳轉(zhuǎn)到下一開始邊界(算法第13行).原理同上.

圖1 一階區(qū)域周期模式分布Fig.1 Distribution of regional periodic 1-patterns

基于以上3個原則，本算法能夠快速且完整地發(fā)現(xiàn)所有一階區(qū)域周期模式及其最大活躍區(qū)域.圖1給出了某一時間序列在周期為13時，所有一階區(qū)域周期模式及其最大活躍范圍的示意.

步驟2.推導高階區(qū)域周期模式.

在獲取F1之后，就可以基于Apriori原則，通過結(jié)合F1與i-1(i∈[2,p))階周期模式來推導可能的i階周期模式，直到某階模式為空.同時，需要注意的是，由于每一個周期段位置上的一階周期模式可能有多個，并且分布在多個不同區(qū)域.如果簡單將其與其他模式結(jié)合來推導高階模式，可能產(chǎn)生巨大的組合數(shù)和運算代價.在最差情況下，L中的每一個字符在每一個位置上都可能是一個周期模式，并且對于同一個位置上的同一個模式，還可能有多個區(qū)域.如圖1，周期段位置1上面對應(yīng)的一階周期模式(b************)就有兩個活躍區(qū)域.所以不能簡單的計算所有的模式組合.這里本文提出了交叉組合概念，即在組合可能的高階模式時，只有i-1階周期模式與F1中的模式在活動區(qū)域上交叉時，才進行組合操作，并且組合后的大區(qū)域范圍也只定義在交叉區(qū)域上.如圖1中，當模式(***d*********)與(****d********)試圖組合出二階模式(***dd********)時，首先判斷兩者活動區(qū)域是否有交叉，若交叉，則進一步獲取新的檢測范圍，即圖1上兩條水平線之間的周期段范圍.之后，在此交叉范圍內(nèi)遍歷可能的區(qū)域，進而判斷是否有當前組合模式所滿足條件的區(qū)域.其中遍歷可能子區(qū)域時，同樣采用如步驟一所示的三種剪枝方法.

通過以上兩個步驟，本算法就可以較快的遍歷出所有可能的區(qū)域周期模式及對應(yīng)的最大活躍區(qū)域.

3.3 算法3：基于一階區(qū)域周期模式密集度推薦區(qū)間的區(qū)域周期模式挖掘算法

盡管算法2能夠有效降低區(qū)域周期模式挖掘的運算開銷，但在實際應(yīng)用中，時間序列的特征更多體現(xiàn)在具備高階數(shù)的周期模式上，階數(shù)越高的周期模式更能表現(xiàn)當前時間序列的變化特征和周期性行為.在這種情況下，并不需要挖掘所有的區(qū)域周期模式.因此，本文提出了一種基于一階區(qū)域周期模式密集度來推薦挖掘區(qū)域的算法.本算法通過給出一種表達一階區(qū)域周期模式密集度的方法，來判斷時間序列中最可能出現(xiàn)高階區(qū)域周期模式的區(qū)域范圍.將區(qū)域周期模式挖掘限定到更小的周期段范圍上，從而大幅度降低運算開銷.其主要包含以下3個步驟：

步驟1.同算法2的第1步，計算F1.但需注意的是，在當前算法中，要記錄所有一階區(qū)域周期模式所在區(qū)域的置信度.

步驟2.在此步中我們提出了一個稱為周期性密集度的函數(shù)IFP(IntensityFunctionofPeriodicity).如公式(4)所示，該函數(shù)計算經(jīng)過每一個周期段e的所有一階區(qū)域周期模式s置信度之和，將其作為該周期段的周期性標度.其中函數(shù)Reg(s)表示模式s的活躍區(qū)域.

(4)

計算IFP函數(shù)之后，掃描整個函數(shù)的值域，獲取離散函數(shù)IFP的極大值ps(可能有多個)及其所屬周期段序號Segs(ps)，定義擴展邊界為BJ=minsupp/mincon，給出新的挖掘范圍CR，如公式(5)所示.圖2給出了圖1對應(yīng)的一階區(qū)域周期模式的IFP值及推薦區(qū)域的示意.

CR=[Segs(ps)-BJ,Segs(ps)+BJ]

(5)

步驟3.在得到推薦挖掘范圍CR后，使用算法2計算該范圍下的區(qū)域周期模式.

3.4 三種算法比較與分析

在以上3種用于時間序列中區(qū)域周期模式挖掘的算法中，算法1采用暴力方法遍歷所有可能區(qū)域，然后采用傳統(tǒng)部分周期模式挖掘算法來發(fā)現(xiàn)區(qū)域周期模式，運算效率最為低下，只具有理論分析價值，不具備實際應(yīng)用條件.算法2基于類Apriori原則，結(jié)合3種有效的剪枝策略，能夠有效降低區(qū)域周期模式挖掘的運算代價，并提供完整的挖掘結(jié)果，是3種算法中最為推薦的算法.算法3通過定義一階區(qū)域周期模式的密集度，推薦局部區(qū)域來進行周期模式挖掘，進一步壓縮了運算代價，但算法3不能提供完整的區(qū)域周期模式集，其設(shè)計目的主要在于在實際應(yīng)用中快速發(fā)現(xiàn)時間序列的重要周期性行為.

圖2 一階區(qū)域周期模式密集度Fig.2 Intensity of regional periodic 1-patterns

4 實驗評估

實驗的數(shù)據(jù)集來自某網(wǎng)絡(luò)安全實驗室中的一個P2P僵尸網(wǎng)絡(luò)流量數(shù)據(jù)集ISOT[13].為了挖掘其中的P2P僵尸網(wǎng)絡(luò)所呈現(xiàn)的區(qū)域周期性行為，本實驗僅關(guān)注該數(shù)據(jù)集中報文大小在60字節(jié)到120字節(jié)之間的本地請求報文，并且忽略其中的DNS類型或者PING類型報文.本文定義該數(shù)據(jù)集中的事件為某本地IP地址每秒發(fā)送上述特定類型報文的數(shù)量，并將所有事件分為5類，分別用a,b,c,d,e五個字符來表示從高到低的發(fā)送頻率.由此，則可為每一個本地IP地址提取出一個用字符集{a,b,c,d,e}表示的事件時間序列.

表1 各個IP地址的推薦周期Table 1 Recommendation periods of IP addresses

本文隨機選取了該數(shù)據(jù)集中的4個本地IP地址，并對它們的區(qū)域周期行為進行了分析.為確定各IP地址對應(yīng)時間序列的周期，本文采用自相關(guān)函數(shù)分析來為其推薦周期取值[8]，結(jié)果如表1所示.基于表1的推薦周期，本文利用上文所述3個區(qū)域周期模式挖掘算法，分別對表中4個IP地址對應(yīng)的事件時間序列進行了區(qū)域周期模式挖掘運算.實驗環(huán)境位于同一臺PC主機，基于MATLAB 7.2完成.

實驗結(jié)果如表2所示.表中第1行為IP地址172.16.0.11周期取10時挖掘結(jié)果，第2行為IP地址172.16.0.11周期取4時挖掘結(jié)果.表中第2、3列的括號內(nèi)第1個數(shù)值表示模式的階數(shù)，第2個數(shù)值表示該階數(shù)模式的個數(shù).也就是說，(x,y)即表示該IP地址的事件時間序列中有y個階數(shù)為x的區(qū)域周期模式.

由于算法1是暴力迭代方式，故其結(jié)果可以認定是完整解.而算法2與算法1結(jié)果一致，由此驗證了基于類Apriori原則的算法2同樣可以獲得完整解.算法3得到了一部分的模式集，但在每個時間序列上，都沒有遺漏表達重要區(qū)域周期行為的高階區(qū)域周期模式，驗證了算法3的設(shè)計效果.

表2 區(qū)域周期模式挖掘結(jié)果Table 2 Results of regional periodic pattern mining

本次實驗中5次執(zhí)行3種區(qū)域模式挖掘算法的時間開銷如圖3所示.其中172.16.0.11(1)表示該IP地址的時間序列周期取10時的運算時間，172.16.0.11(2)為該IP地址的時間序列周期取4時的運算時間.如圖可知，在5次運算過程中，算法1的運算時間總是最長的，而且要比算法2和算法3多出較大比例，這與我們前文的算法分析是一致的，即算法1只能做理論分析和性能比較對象，不具備滿足實踐應(yīng)用的高效處理能力.算法2在5次運算中4次都能做到快速求解，體現(xiàn)了算法2較為良好的計算效率.但在處理IP地址172.16.2.2對應(yīng)的時間序列時，消耗了過多時間.經(jīng)檢驗，這是因為該時間序列對應(yīng)的周期過短(p=3)，導致時間序列所劃分的周期段數(shù)目過于龐大，從而給計算帶來了較大時間消耗.算法3在5次運算中均保持了較低的運算時間，是3種運算中最為快速的算法.

圖3 算法運行時間開銷Fig.3 Time overhead of algorithm

以上實驗分析和驗證了本文所提出的區(qū)域周期模式挖掘算法的有效性和差異性.

5 結(jié) 論

本文提出了一種區(qū)別于全周期模式和部分周期模式的區(qū)域周期模式，為進一步挖掘時間序列的周期性行為提供了一種新型的分析工具.并分別介紹了三種差異化的擁有不同求解目標的區(qū)域周期模式挖掘算法.文章最后利用網(wǎng)絡(luò)安全領(lǐng)域的公開數(shù)據(jù)集測試和評估了3種算法的解完整性和計算性能，驗證了算法的有效性.但我們也看到，算法在特殊情況下并不能總是保證快速求解，因此在下一步工作中，我們將著眼于改進當前算法或者提出新的更快、更穩(wěn)定的區(qū)域周期模式挖掘算法.