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

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

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

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

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

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

1 引 言

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

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

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

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

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

2 區域周期模式的形式化描述

2.1 基礎概念

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

定義一個時間序列S中關于模式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 區域周期模式的定義

定義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.區域周期模式

給定長度為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的一個區域，稱Sub所含周期段數量(j-i+ 1)為Sub的區域長度，記為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的一個區域周期模式.

例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的一個區域周期模式.

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

3 區域周期模式挖掘算法

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

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

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

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

輸出:存放所有區域周期模式數據結構的集合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步進行：

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

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

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

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

(3)

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

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

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

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

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

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

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

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

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

算法2.一階區域周期模式求解算法

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

輸出:存放一階區域周期模式數據結構的集合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中出現字符l的時間點

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

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

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

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

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

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

步驟2.推導高階區域周期模式.

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

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

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

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

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

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

(4)

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

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

(5)

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

3.4 三種算法比較與分析

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

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

4 實驗評估

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

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

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

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

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

表2 區域周期模式挖掘結果Table 2 Results of regional periodic pattern mining

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

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

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

5 結 論

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