算法介紹

以時(shí)間順序挖掘周期性的模式（即周期性分析）是一種重要的數(shù)據(jù)挖掘方式，在以前的研究中我們假設(shè)每個(gè)時(shí)間點(diǎn)只發(fā)生一個(gè)事件，然而在這篇文章中我們研究一種更普遍的模式：即在每個(gè)時(shí)間點(diǎn)可以發(fā)生多個(gè)事件。

在這個(gè)算法中我們需要自己設(shè)置三個(gè)參數(shù)：min_rep, max_dis, global_rep。分別代表“一個(gè)有效序列的最小重復(fù)次數(shù)”、“相鄰有效序列最大允許擾動(dòng)”、“有效序列總的要求重復(fù)次數(shù)”。其實(shí)在算法最后中我們會(huì)發(fā)現(xiàn)，我們也可以設(shè)置另外一個(gè)參數(shù)Lmaxn,即允許的最大周期。

最后，這個(gè)算法原作者似乎認(rèn)為效果不錯(cuò)，->.->

問題定義

在這個(gè)部分中，我們定義一些異步周期挖掘的問題。

E代表所有事件的集合，即一個(gè)事件的集合一定是E的一個(gè)非空子集。信息庫D是一系列的時(shí)間記錄，每一個(gè)記錄用一個(gè)數(shù)組來表示(tid, X)，表示在tid時(shí)刻發(fā)生了集合X中的事件。同時(shí)D的這種表示方法我們定義為水平表達(dá)格式(horizontal format)，具體請(qǐng)看下表。同時(shí)對(duì)于另一個(gè)事件集合Y，我們定義Y是被一個(gè)時(shí)間記錄所支持需滿足：Y?X。一個(gè)有k個(gè)事件的序列一般稱為k-事件序列(k-event set)。

定義 1：一個(gè)以l為周期的模式是一個(gè)非空序列P=(p1,p2,…,pl)，其中p1是一個(gè)事件序列，其他的或者是一個(gè)事件序列，或者是*，即可以理解為任何序列。

一個(gè)模式P若包含i個(gè)事件則被稱作i-模式(i-pattern)。特別的，我們稱1-模式為單模式(singular patterns)，當(dāng)i>1時(shí)我們稱之為復(fù)雜模式(complax patterns)，例如(A, *, *)是一個(gè)單模式而(A, B, *)是一個(gè)2-模式，也稱為復(fù)雜模式。如果一個(gè)模式不包含任何“*”我們就稱之為滿模式(full pattern)，否則就稱之為部分模式(partial pattern)。

定義 2：設(shè)有周期為了的模式P=(p1,p2,…,pl)和一個(gè)包含l個(gè)事件的集合D’=(d1,d2,…,dl)，我們定義P匹配D’當(dāng)且僅當(dāng)對(duì)于每個(gè)j(1<=j<=l)，或者pj=*，或者pj?dj。D’也可以稱為P的一個(gè)匹配項(xiàng)。

比如現(xiàn)在有一個(gè)模式P=(A, B, *)，那么*顯然可以和任何事件序列匹配，于是如果我們有D=(A, B, C)就是一個(gè)P的一個(gè)匹配項(xiàng)。

定義 3：為了方便，我們用一個(gè)4元組(P, l, rep, pos)來定義一個(gè)模式片段P，它的周期l，開始位置是pos，并重復(fù)rep次，一般我們假設(shè)這個(gè)rep要取最大值(maximum segment)。

定義 4：一個(gè)最大片段(maximum segment)是一個(gè)有效片段當(dāng)且僅當(dāng)其重復(fù)次數(shù)不小于參數(shù)min_rep。

我們?cè)俣x一下擾動(dòng)的概念：連個(gè)片段的擾動(dòng)就是第一個(gè)片段的尾部和第二個(gè)片段的開始的位置之間的距離。例如在下圖中，S1和S3之間的擾動(dòng)是8(15 – 3)。

定義 5：假設(shè)一個(gè)時(shí)間的數(shù)據(jù)庫D和一個(gè)模式P，序列D是一系列不重合的有效序列，并且其中任意相鄰片段的擾動(dòng)小于一個(gè)預(yù)定的值，我們稱之為最大擾動(dòng)max_dis。一個(gè)序列被稱作是有效的當(dāng)且僅當(dāng)P的全部的重合的次數(shù)大于一個(gè)預(yù)定的參數(shù)global_rep。

對(duì)于Fig.1b，如果我們?cè)O(shè)min_rep = 2, global_rep = 6, max_dis = 8，那么我們將會(huì)得到兩個(gè)有效序列(S1, S2)，和(S1, S3)。而我們的任務(wù)找到所有有效的周期序列，其周期在1~Lmax之間，其中Lmax由用戶給定。

算法預(yù)覽

在這個(gè)模塊中，我們從挖掘單模式的周期序列到復(fù)雜模式周期序列，展示一下在時(shí)間數(shù)據(jù)庫中異步周期序列挖掘的過程。首先一個(gè)稱為“SPMiner”被用來找所有的單模式周期序列，它的原理主要是潛在循環(huán)試探(Potential Cycle Detection)和基于哈希的表(Hash-Based Validation)。然后，兩個(gè)算法“MPMiner”和“CPMiner”被用來尋找有效的多重單模式(multievent 1-patterns)和復(fù)雜模式序列(complex patterns)。最后，所有的有效片段都可以組合在一起來檢測(cè)是否滿足要求，即最后的”APMiner”。詳細(xì)見下圖：

現(xiàn)在我們分步驟來講解每一步的具體方法及部分偽代碼

SPMiner：Segment Mining for Single Event Pattern

首先，我們?cè)谇懊嫣徇^一種叫做水平數(shù)據(jù)格式(horizontal database layout)的數(shù)據(jù)結(jié)構(gòu)，現(xiàn)在我們要使用一種和其相對(duì)應(yīng)的垂直數(shù)據(jù)格式(vertical database format)，具體請(qǐng)見下表，它可以大大提高我們的搜索效率。

PCD算法(Potential Cycle Detection)測(cè)探所有在1~Lmax之間的可能周期,具體看偽代碼。

HBV算法(Hash-Based Validation)可以對(duì)于每個(gè)潛在的周期p和一個(gè)事件列表e，通過遍歷一遍事件表來找出所有的單模式序列。具體看偽代碼。

Procedure of SPMiner(D, Lmax)
    for each event Ei ∈ VD do:
        PCD(Ei, TimeList);
        for p = 1 to Lmax do
            if(CheckSet[p] >= min_rep)
                then HBV(Ei, Ei.TimeList, p); 

Procedure of PCD(TimeList)
    for i = 1 to i <= Lmax do CheckSet[i] = 1;
    for each time instant Ti ∈ TimeList do
        for each time instant Tj ∈ TimeList, i < j do
            if((Tj - Ti) <= Lmax) then
                CheckSet[Tj - Ti]++;
            else break; 

Procedure of HBV(EvtSet, TimeList, p)
    Allocate data structure Cseg[p];
    for i = 0 to p - 1 do /* Initilization */
        Cseg[i].last = -Max; Cseg[i].rep = 1;
    /* Validation */
    for each time instant Ti ∈ TimeList do
        pos = Ti % p;
        if(Ti - Cseg[pos].last == p) then
            Cseg[pos].rep++; Cseg[pos].last = Ti; continue;
        if(Cseg[pos].rep >= min_rep) then
            Output(EvtSet, p, Cseg[pos].rep, Cseg[pos].last - p * (Cseg[pos].rep - 1));
        Cseg[pos].rep = 1; Cseg[pos].last = Ti;
     for i = 0 to p - 1 do /* Rechecking */
        if(Cseg[i].rep >= min_rep) then
            Output(EvtSet, p, Cseg[i].rep, Cseg[i].last - p * (Cseg[i].rep - 1)); 

最后我們會(huì)得到如下的結(jié)果

MPMiner： Multievent Patterns

這里我們直接介紹推薦的SBE算法(Segment-Based Enumeration)。

SBE算法的思路是，對(duì)于一個(gè)周期p，先在上表中找到周期為p的項(xiàng)。我們假設(shè)一個(gè)變量off = start % p，這樣我們?cè)诖瞬秸业降慕M合內(nèi)部off則一定相同。如果最后重合部分還大于參數(shù)min_rep，那么我們就成功的找到了一組答案了。而對(duì)于重合的部分，我們也可以根據(jù)上表在O(1)的時(shí)間內(nèi)計(jì)算出來。

CPMiner：Complex Patterns

這一步的做法和上一步的SBE算法十分相似。

不過在上一步中我們要求off相同才能放在一組，而在這一步中我們要求off必須不同才能在一組，偽代碼如下

Procedure of CPMiner(p, SegListp, w.r.t period p)
    for each segment Si ∈ SegListp; do
        Node.Head = Si;
        Node.Tail = all segment Sj ∈ SegList with j > i;
        Node.start = Si.start;
        Node.end = Si.start + (Si.rep - 1) * p;
        CP(Node, p); 

Subprocedure of CP_DFS(Node, p)
    if(|Node.Head| == p) then return ;
    for each segment Si ∈ Node.Tail do
        Valid = True;
        for each setment Sj ∈ Node.Head do
            if((Si.start - Sj.start) % p == 0) then
                Valid = false; break;
            if(Valid == false) then continue;
            newC.start = Si.start;
            newC.end = Min{Node.end, Si.start + (Si.rep - 1) * p};  //take care
            rep = ?(newC.end - newC.start) / p? + 1;        //take care
            if(rep >= min_rep)
                newC.Head = Node.Head ∪ Si;
                newC.Tail = all Sk ∈ Node.Tail with k > i;
                PatternOutput(newC, p, rep)
                CP_DFS(newC, p);
            else if(Node.end - Node.start + 1 < p * min_rep) break; 

Subprocedure of PatternOutput(Node, p, rep)
    Shift = Node.end % p        //take care not Node.start!
    for i = 1 to p do Pattern[i] = *;
    for each segment Si ∈ Node.Head do
        Pattern[(Si.start - Shift) % p] = Si.EvtSet;
    Output(Pattern, rep, p, Node.end - (rep - 1) * p); 

APMiner：Asynchronous Pattern

就像我們?cè)诙x5中說的那樣，一個(gè)異步周期模式被定義為有一組序列互不重合。因此我們還需使用深度優(yōu)先搜索來枚舉所有的組合方式?，F(xiàn)在假設(shè)我們把所有的片段按照開始的時(shí)間排序，一個(gè)單模式的片段如果重復(fù)次數(shù)大于global_rep，那么它本身就是一個(gè)合法答案，但是每次枚舉過程中，我們總要盡力的把新的事件加入到已有的事件序列中。同時(shí)，如果新的片段距離的開始位置距離已有片段的距離小于max_dis，那么我們也可以把它加入進(jìn)去。但是一旦上述條件不符合的話，我們就可以跳出搜索了，因?yàn)槲覀兪前凑臻_始的時(shí)間順序有小到大排序的，這樣可以達(dá)到剪枝的效果。