李 威 吴志刚 李健俊 陆海龙

1(浙江中烟工业有限责任公司 杭州 310001)2(杭州世平信息科技有限公司 杭州 310012) (lwei@zjtobacco.com)

考虑事件的发生顺序，面向序列数据的挖掘算法主要分为频繁序列挖掘和频繁情节挖掘2类，但其面向的数据类型仍存在差异.频繁序列挖掘是在一组序列的集合上进行挖掘，找出众多序列中频繁出现的子序列，如获取多个用户的网络行为信息，从中挖掘他们浏览网页的共同操作行为.该领域的经典算法包括GSP算法、Prefix Span算法、SPADE算法、SPAM算法等[1-3].

频繁情节挖掘算法其数据类型为一长串带有发生时间的有序信号事件序列，其工作目标是从中找出事件序列中频繁出现的子序列，从而揭示相邻信号事件的关联关系和发生规律.如何发现频繁情节已成为数据挖掘领域的热点问题之一，学者们先后研究了许多算法[4-6]，如WINEPI，MINEPI，EpiBF，NONEPI，MANEPI等.这些基于最小发生、窗口发生的算法，或因为情节发生之间可能会产生重叠，导致情节发生的“过计数”问题，或将情节设置为发生时间完全独立的无交叠设定，存在情节漏记.此外，上述算法都是基于静态数据的，在进行情节挖掘时，基于事件的统计特性使用广度优先的搜索策略，生成候选情节，然后进行情节发生计数，满足最小支持度阈值的情节即为频繁情节.

这类方法以事件出现频率为基准，按照支持度阈值，首先将事件划分为频繁项与非频繁项，进而根据情节的向下闭合特性生成候选情节.但是动态数据流环境下，事件的出现频度时刻发生变化，原本频繁的事件可能会变得不频繁，而不频繁的事件可能在某些时刻转变为频繁事件.因此，以上所描述的方法无法直接应用到数据变化的动态频繁情节挖掘中.

据了解，现有的能够应对动态数据频繁挖掘的算法极少，与一组序列数据相比，长串数据不易分割的特点更加剧了动态频繁情节挖掘的难度.为了解决长串序列数据不易进行分割的问题，现有的情节定义方法通常采用窗口计数、最小发生计数、无交叠发生计数等方式.

1 相关工作

1) MESELO算法.

MESELO算法是由Ao等人[7]提出的，该算法处理的序列是一个完整信号序列，给出了一种基于最后一次出现的最小情节发生定义，将信号序列按照固定长度进行窗口切割划分，且每个窗口起始时刻相差为1，这使得对于长度为L的序列数据，需要建立(L-|w|+1)个窗口，其中|w|表示窗口大小.然而在现实的场景中：其一，该算法很难保证数据间隔的稳定性；其二，算法需要对每个时间间隔内的挖掘结果进行存储，冗余数据多，占用大量内存.而且，在各时刻点统计情节出现频率时，需要对各时段内挖掘到的情节进行统计并去除重复计数的情节.

2) ONCE算法.

有限状态自动机[8]通过状态转移，实现对特定情节的计数工作.其工作原理是按照情节顺序建立状态机.在捕获到当前等待事件后进行状态转移，转为等待情节的下一事件.当情节的最后一个事件到达时，状态机跳转到结束态，意味着一个完整情节的发生.但有限状态机所捕获的情节发生没有时间跨度的约束，存在一次情节发生开始事件与结束事件时间跨度较长的情况，这类情节发生不再具备较强的现实意义，而且对于交叉发生的情节不具备识别能力.

ONCE算法主要是利用状态转移的思想，是一种对带时间约束的无交叉最小发生情节进行计数的计数算法：它构建了一种名为OccMap的数据结构，该结构可以用来存储事件信号的时间戳.当最后一行为激活态，且有对应信号事件到达时，表明存在一次完整的情节发生，之后通过自底向上对OccMap表进行信号事件选取，得到最小情节发生，然后检验情节发生的时间跨度是否满足约束.如果满足时间跨度约束，则表明捕获到一次符合条件约束的情节发生，可以进行情节计数+1的操作.该算法和OccMap结构详细见Li等人[9]以及李健等人[10]的研究.

ONCE算法按照无交叠的情节最小发生进行扫描计数，不适用于交叉互异的最小情节发生.某些交叉发生的互异情节不能被挖掘捕获.

现有情节定义方法通常为保证情节发生计数的方便性，以牺牲准确性为代价，采用窗口计数、最小发生计数、无交叠发生计数等方式.这些计数方式或事件被重复使用，存在重复计数问题，或由于情节的无交叉性某些情节被漏记.在此，我们定义一种更为通用的情节计数方式——可交叉的带时间约束的互异最小发生，基于这种情节定义方式实现高效的情节计数.我们复用了ONCE算法采用的OccMap结构，通过设计该结构的初始化过程，实现带时间约束的可交叉最小发生情节进行计数，在我们提出的情节定义下完成情节发生的准确计数.

2 实现方案

参考李健等人[10]的计数方案提出的OccMap数据结构，本文对OccMap结构的情节判定和初始化步骤进行了改进，实现单遍扫描序列数据，完成对可交叉的带时间约束的互异最小情节计数的工作，该算法命名为ONCE-TDM.具体操作过程如下：

1) OccMap表建立.

如图1所示，以序列情节α4=〈A,B,B〉为例(α的上标“4”，表示时间跨度最大为4)，按顺序建立存储事件时间戳的对应行，目标情节和各行共同构成1张OccMap表，记作OM(αδ)=[l1,l2,…,lk].将第1行事件A设置为激活状态，表示OccMap表正等待事件A的到达，其他行设置未激活状态.之后随着序列S中每个事件的产生和到达，OccMap不断保存和更新.

图1 α4=〈A,B,B〉在序列S中的计数过程

2) OccMap表更新.

随着长序列S中事件的到达，需要比较OccMap中处于激活状态的各行事件与到达事件是否相同，若相同，则将该事件时间戳加入已激活的事件对应行中，将OccMap表中第1个无数据的行设置为激活状态，表示等待该行类型的信号事件到达.

3) OccMap最后数据到达.

最后一行到达表示找到一个完整的情节发生，因为按照我们的激活规则，OccMap表中的数据必定满足l1[1]<l2[1]<…<lk[1]，下面将判断形成的情节发生是否满足约束条件.

4) 情节约束条件判定.

一种多层小型化5G毫米波功率分配器设计…………………………………………… 姬晓春，姬五胜，王林年，张志悦，童荥贇，涅佛达夫.E.I（6）

考虑到本文所要寻找的是情节的最小发生，所以当最后一行激活且有事件匹配时，先在OccMap中自底向上选中每行能构成情节最小发生的事件时间戳.

最后一行的选中事件即为刚到达的唯一的时间戳所表示的事件，之后向上确定每行选中事件时寻找发生时间早于下一行选中事件时间戳，且最靠近下一事件发生时刻的时间，即小于下一事件时间戳的本行时间戳的最大值，从而保证选中事件构成的发生为最小情节发生.得到情节最小发生的时间跨度[ts,te]，若te-ts≤δ，则存在1次情节发生，满足最小时间跨度约束；相反，则情节发生不能满足时间约束.

如图1(5)所示，α4=〈A,B,B〉的一次最小发生ts=1,te=5，满足时间约束δ(δ=4).

5) OccMap表初始化.

在完成1组选中事件的条件约束判定之后，需要对OccMap进行初始化操作，以便对后续序列进行情节计数.

本文所定义的情节发生其事件必须满足互异性，但发生时间的时间跨度可以有重叠.在此，我们对OccMap初始化步骤进行重新设计，使得它能胜任带时间约束可交叉的互异最小情节的计数工作.

由于满足和不满足时间跨度约束的情节发生在OccMap初始化时操作情况是不同的，在此对2种情况进行分类讨论.

1) 满足约束条件发生的OccMap初始化.

按照之前描述的步骤，在情节最后事件到达后，按要求自底向上按层查找，可得到最小发生的时间跨度[ts,te].考虑到最大化的捕获序列S中满足要求的情节发生，我们增加1次自上而下确定情节发生时间戳的步骤，如图2所示:

不同的学生有着不同的学习层次，不同的学生学习能力也不尽相同，因此，在进行分层异步教学时，要进行合理的分层，保证学生学习能力与知识的匹配，学习上不产生很大的压力，导致学习兴趣的丧失。在分层异步教学中实现对学生进行合理的分配，需对每一个学生进行充分了解，根据学生的理解水平和学习能力进行合理分组，再对每一个组的教学方式和授课方法进行调整，使每一个学生都能够从不一样的程度进行学习，以学生为主体地位，对每一个组进行不一样的指导，充分调动学生学习的积极性，渐渐使理解能力差的学生也能够熟练地掌握知识。

图2 α6=〈A,B,A,C〉在序列S中的计数过程

图3 α4=〈A,B,A〉在序列S中的计数过程

以图2(5)中的序列数据而言，如果以Occ1(α6,S)=〈1,2,4,5〉作为本次情节的发生，则为了保证互异性，事件(A,4)不能被2次使用.

而如果增加1次自上而下确定情节发生时间戳的步骤，则在保证最小发生时间跨度不变的同时，可以选择较为靠前的事件时间戳(A,3).此时，由于情节发生可交叉的设定，(A,4)将可以用于下一次情节发生Occ2(α6,S)=〈4,6,7,8〉，这使得情节发生计数更加准确.

在确定情节发生的时间戳之后，将OccMap表中选中事件及各行选中事件之前的数据删除，同时，由于选中事件已经被使用，删除与选中事件相同的时间戳，如图2(5+)中第1行数据(A,3).

最后，对表中剩余数据进行检查操作，确保每行数据符合OccMap表的要求，即l1[1]<l2[1]<…，并将表中第1个空行及之前行设置为激活态.如图2(5++)，剩余数据(A,4)的第1行数据为激活态，第2行为首个空行，也设置为激活态，代表等待第2行数据的到达.

2) 不满足约束条件发生的OccMap初始化.

根据之前的讨论，OccMap在各层有数据的情况下才能激活下一层事件，所以当情节最后1个事件到达，必可以构成至少1个按顺序的序列情节.我们从最后一行开始，自底向上逐层查找，找到目标情节的最小发生及情节时间跨度[t1,tk]，因此如果该组序列情节不满足约束条件，存在的问题当且仅当是选定的情节发生超出其时间跨度约束.

如图3(6)所示，已知选中的这组情节的发生已经是最小发生，时间跨度达到最小值，若该组时间戳数据不能满足要求，则说明当前状态下无法找到满足时间约束的情节，该组数据作废.作废情况下，选中事件并没有被使用，与后续事件构成情节发生时，不存在事件被重复利用的情况，如图3(6+)中事件(A,6).所以表中与选中事件相同的事件不必进行删除操作.

又知，当前选中情节发生已经为最小发生，且超过时间跨度约束.则此时自下而上选中的各行较为靠后的数据(如图3(6+)中事件B选中时间戳为5的数据)，若能与后续到达的事件再次构成情节发生，其时间跨度只可能大于本次发生，所以不必再自上而下找发生较靠前的等价发生，可直接判定选中数据及各行选中数据之前的数据失效，对其进行删除操作.

接下来与按照满足约束条件发生OccMap初始化的流程一致，对剩余数据进行整理，保证剩余事件能满足情节中事件的顺序约束(l1[1]<l2[1]<…).并将有数据的行和第1个无数据的行设置为激活状态，表示OccMap正等待这些数据的到达.

至此，利用OccMap数据结构，按照以上5个步骤，实现对长串序列数据S中带时间约束的特定情节αδ的计数工作.

3 结 论

本文综合考虑情节发生的时间跨度问题、信号事件的互异性、情节的可交叉性，提出一种更具普适性的情节定义方式.文中提出的情节定义满足情节反单调性，参照ONCE算法提出的情节计数方案，利用算法构建的OccMap数据，通过修改OccMap的情节判定和初始化过程，实现对序列数据1遍扫描，完成对有交叉带时间约束的最小情节发生精确计数的工作.