数据挖掘：周期性分析SMCA算法
原文地址:
算法介绍
以时间顺序挖掘周期性的模式（即周期性分析）是一种重要的数据挖掘方式，在以前的研究中我们假设每个时间点只发生一个事件，然而在这篇文章中我们研究一种更普遍的模式：即在每个时间点可以发生多个事件。
在这个算法中我们需要自己设置三个参数：min_rep, max_dis, global_rep。分别代表“一个有效序列的最小重复次数”、“相邻有效序列最大允许扰动”、“有效序列总的要求重复次数”。其实在算法最后中我们会发现，我们也可以设置另外一个参数Lmaxn,即允许的最大周期。
最后，这个算法原作者似乎认为效果不错，->.->
问题定义
在这个部分中，我们定义一些异步周期挖掘的问题。
E代表所有事件的集合，即一个事件的集合一定是E的一个非空子集。信息库D是一系列的时间记录，每一个记录用一个数组来表示(tid, X)，表示在tid时刻发生了集合X中的事件。同时D的这种表示方法我们定义为水平表达格式(horizontal format)，具体请看下表。同时对于另一个事件集合Y，我们定义Y是被一个时间记录所支持需满足：Y⊆X。一个有k个事件的序列一般称为k-事件序列(k-event set)。
| Time | Event Set | Time | Event Set | Time | Event Set |
|---|---|---|---|---|---|
| 1 | A, B, C | 7 | A, B, C, D | 13 | A, C, D |
| 2 | B, D | 8 | A | 14 | A, C |
| 3 | A, C, D | 9 | A, C, D | 15 | A, D |
| 4 | B | 10 | A, C | 16 | A, C, D |
| 5 | A, C | 11 | D | 17 | A |
| 6 | D | 12 | A, B, C, D | 18 | A, B, C, D |
定义 1：一个以l为周期的模式是一个非空序列P=(p1,p2,...,pl)，其中p1是一个事件序列，其他的或者是一个事件序列，或者是*，即可以理解为任何序列。
一个模式P若包含i个事件则被称作i-模式(i-pattern)。特别的，我们称1-模式为单模式(singular patterns)，当i>1时我们称之为复杂模式(complax patterns)，例如(A, *, *)是一个单模式而(A, B, *)是一个2-模式，也称为复杂模式。如果一个模式不包含任何“*”我们就称之为满模式(full pattern)，否则就称之为部分模式(partial pattern)。
定义 2：设有周期为了的模式P=(p1,p2,...,pl)和一个包含l个事件的集合D'=(d1,d2,...,dl)，我们定义P匹配D'当且仅当对于每个j(1<=j<=l)，或者pj=*，或者pj⊆dj。D'也可以称为P的一个匹配项。
比如现在有一个模式P=(A, B, *)，那么*显然可以和任何事件序列匹配，于是如果我们有D=(A, B, C)就是一个P的一个匹配项。
定义 3：为了方便，我们用一个4元组(P, l, rep, pos)来定义一个模式片段P，它的周期l，开始位置是pos，并重复rep次，一般我们假设这个rep要取最大值(maximum segment)。
定义 4：一个最大片段(maximum segment)是一个有效片段当且仅当其重复次数不小于参数min_rep。
我们再定义一下扰动的概念：连个片段的扰动就是第一个片段的尾部和第二个片段的开始的位置之间的距离。例如在下图中，S1和S3之间的扰动是8(15 - 3)。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| A | C | B | A | E | D | A | A | B | C | A | B | C | A | A | D | A | A | B | C | A | E | C |
| D1 | D1 | D1 | D2 | D2 | D2 | D3 | D3 | D3 | D8 | D8 | D8 | D9 | D9 | D9 | D10 | D10 | D10 | |||||
| S1 | S1 | S1 | S1 | S1 | S1 | S1 | S1 | S1 | S3 | S3 | S3 | S3 | S3 | S3 | S3 | S3 | S3 |
定义 5：假设一个时间的数据库D和一个模式P，序列D是一系列不重合的有效序列，并且其中任意相邻片段的扰动小于一个预定的值，我们称之为最大扰动max_dis。一个序列被称作是有效的当且仅当P的全部的重合的次数大于一个预定的参数global_rep。
对于Fig.1b，如果我们设min_rep = 2, global_rep = 6, max_dis = 8，那么我们将会得到两个有效序列(S1, S2)，和(S1, S3)。而我们的任务找到所有有效的周期序列，其周期在1~Lmax之间，其中Lmax由用户给定。
算法预览
在这个模块中，我们从挖掘单模式的周期序列到复杂模式周期序列，展示一下在时间数据库中异步周期序列挖掘的过程。首先一个称为“SPMiner”被用来找所有的单模式周期序列，它的原理主要是潜在循环试探(Potential Cycle Detection)和基于哈希的表(Hash-Based Validation)。然后，两个算法“MPMiner”和“CPMiner”被用来寻找有效的多重单模式(multievent 1-patterns)和复杂模式序列(complex patterns)。最后，所有的有效片段都可以组合在一起来检测是否满足要求，即最后的"APMiner"。详细见下图：
现在我们分步骤来讲解每一步的具体方法及部分伪代码
SPMiner：Segment Mining for Single Event Pattern
- 首先，我们在前面提过一种叫做水平数据格式(horizontal database layout)的数据结构，现在我们要使用一种和其相对应的垂直数据格式(vertical database format)，具体请见下表，它可以大大提高我们的搜索效率。
| Event | TimeList |
|---|---|
| A | 1, 3, 5, 7, 8, 9, 10, 12, 13, 14, 15, 16, 17, 18 |
| B | 1, 2, 4, 7, 12, 18 |
| C | 1, 3, 5, 7, 9, 10, 12, 13, 14, 16, 18 |
| D | 2, 3, 6, 7, 9, 11, 12, 13, 15, 16, 18 |
PCD算法(Potential Cycle Detection)测探所有在1~Lmax之间的可能周期,具体看伪代码。
HBV算法(Hash-Based Validation)可以对于每个潜在的周期p和一个事件列表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));
最后我们会得到如下的结果
| Pattern | Period | Rep | Start |
|---|---|---|---|
| A | 1 | 7 | 12 |
| A | 2 | 5 | 1 |
| A | 2 | 6 | 8 |
| C | 2 | 5 | 1 |
| C | 2 | 5 | 10 |
| D | 2 | 5 | 7 |
| D | 3 | 6 | 3 |
MPMiner： Multievent Patterns
这里我们直接介绍推荐的SBE算法(Segment-Based Enumeration)。
SBE算法的思路是，对于一个周期p，先在上表中找到周期为p的项。我们假设一个变量off = start % p，这样我们在此步找到的组合内部off则一定相同。如果最后重合部分还大于参数min_rep，那么我们就成功的找到了一组答案了。而对于重合的部分，我们也可以根据上表在O(1)的时间内计算出来。
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; 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
就像我们在定义5中说的那样，一个异步周期模式被定义为有一组序列互不重合。因此我们还需使用深度优先搜索来枚举所有的组合方式。现在假设我们把所有的片段按照开始的时间排序，一个单模式的片段如果重复次数大于global_rep，那么它本身就是一个合法答案，但是每次枚举过程中，我们总要尽力的把新的事件加入到已有的事件序列中。同时，如果新的片段距离的开始位置距离已有片段的距离小于max_dis，那么我们也可以把它加入进去。但是一旦上述条件不符合的话，我们就可以跳出搜索了，因为我们是按照开始的时间顺序有小到大排序的，这样可以达到剪枝的效果。
其他
这个算法总体就是这个样子，如果想看更详细的请参考链接：欢迎大家留言交流。