GFExtractor：事件序列上有效挖掘无冗余情节规则的算法

袁红娟

泰州学院 数理信息学院，江苏 泰州 225300

GFExtractor：事件序列上有效挖掘无冗余情节规则的算法

袁红娟

泰州学院 数理信息学院，江苏 泰州 225300

1 引言

情节规则的概念首先由Mannila等人[1]提出，用于描述情节之间的因果关系。事件序列上挖掘情节规则，目前主要有Mannila提出的MINEPI算法，Hatonen等人提出的TASA算法[2]、Meger等人提出的WinMiner[3]算法等，主要应用于网络安全监控[4]、事务日志分析[5]、传感器数据分析处理[6]、交通流预测等方面。

现有的挖掘情节规则的算法，大多数基于滑动窗口或最小发生来计算情节的支持度，对支持度的“过计数”导致挖掘质量不高，且从频繁情节集产生的情节规则存在冗余，导致挖掘效率不高。而直接从频繁闭情节集产生情节规则，同样存在冗余。假设有事件序列ES如图1所示。

图1 事件序列ES

当支持度阈值min_sup=2，置信度阈值min_conf=0.4时，该序列有34个频繁情节，7个频繁闭情节，直接从频繁闭情节挖掘得到46个情节规则，存在冗余。

为有效地在事件序列上挖掘无冗余的情节规则，定义了情节生成子概念，结合频繁闭情节，提出挖掘无冗余情节规则的算法GFExtractor（Generator&Frequent Closed Episode Extractor）。该算法基于非重叠的最小发生的支持度定义[7]和深度优先搜索策略，产生情节生成子集与频繁闭情节集，在两者之间抽取无冗余的情节规则。在挖掘过程中，利用非生成子剪枝策略淘汰非生成子情节，利用向前、向后双向扩展检查淘汰非闭情节，避免维护频繁情节集，节省存储空间，提高运行效率。

双向扩展检查挖掘频繁闭情节的BIDEFCE算法，可参考作者的另一篇文章《BIDEFCE：一种基于双向扩展的频繁闭情节挖掘算法》。

2 相关工作

在研究情节规则挖掘之前，关联规则挖掘和序列模式挖掘的研究由来已久。

（1）关联规则挖掘

关联规则挖掘的对象是一个事务数据库，将包含在相同交易集的项集的集合称为等价类[8]。为控制由频繁项集产生的关联规则的数量，Pasquier等人引入了项集生成子[9]的概念：在同一等价类中，最小的元素称为项集生成子，最大的元素称为闭项集。根据MDL（最小描述长度）原理[10]，项集生成子比闭项集具有更小的描述长度。从项集生成子和频繁闭项集产生无冗余的关联规则，主要的算法有Gen，DPMiner等。Gen[11]算法采用广度优先搜索策略，定义了精确关联规则基和近似关联规则基的概念，精确关联规则基由具有最小前件与最大后件的精确关联规则（置信度等于100%）组成，近似关联规则基由具有最小前件与最大后件的近似关联规则（置信度小于100%）组成。DPMiner[12]算法则采用了深度优先搜索策略，利用FP树挖掘频繁闭项集及其生成子，生成等价类。

（2）序列模式挖掘

序列模式挖掘的对象是一个序列数据库，由相同序列集支持的序列模式的集合称为等价类。同一等价类中，不存在等支持度真子序列的序列模式称为序列生成子[13]，不存在等支持度超序列的序列模式称为闭序列。同样，根据MDL原理，序列生成子比闭序列具有更小的描述长度。主要算法有GenMiner。GenMiner[13]算法采用深度优先搜索策略，创建并存储所有序列模式的前缀搜索树PSL，遍历PSL，得到序列模式生成子超集并进行过滤，得到最后的序列模式生成子集合。

（3）情节规则挖掘

情节规则挖掘与前两者不同，挖掘的对象是一个事件序列。

Mannila等人提出的MINEPI算法中，情节规则形如且 β是α的子情节，情节规则表示α、 β发生的起始时间相同，若 β在win1宽度的时间区间内发生，紧接着α将会在win2宽度的时间区间内发生，算法基于频繁情节集抽取情节规则。

由Hatonen等人提出的TASA算法，基于滑动窗口的支持度定义及广度优先搜索策略，多次扫描事件序列挖掘频繁情节，再基于频繁情节集抽取情节规则，最后再通过剪枝、排序、分组等技术来筛选冗余的情节规则。

由Meger等人提出的WinMiner算法，基于最小发生的支持度定义和深度优先搜索策略，单遍扫描事件序列，挖掘频繁情节的过程中无需生成候选情节，再基于频繁情节集抽取情节规则。

上述算法均是从频繁情节集中抽取所有的情节规则，存在大量冗余。由朱辉生[14]等人提出的Extractor算法，基于最小且非重叠的支持度定义和深度优先搜索策略来发现频繁闭情节及其生成子，生成无冗余的情节规则。但在生成规则时需双重遍历并维护频繁情节集。

针对以上不足，本文提出了GFExtractor算法。算法基于非重叠的最小发生的支持度定义和深度优先搜索策略，在挖掘频繁情节的同时，及时淘汰非生成子情节及非闭情节，产生情节生成子集Gen和频繁闭情节集FCE，再在Gen和FCE之间抽取无冗余的情节规则。算法避免了遍历和维护频繁情节集，节省存储空间，提高了情节规则挖掘的效率和质量。

3 相关概念

定义1（事件序列event sequence）设E是一组事件类型，事件＜e，t＞，e∈E，t是事件发生的时间，则事件序列ES=(s，Ts，Te)，其中s=＜(t1)，(e2，t2)，…，(en，tn)＞，ei∈E，ti＜ti+1(1≤i＜n)，Ts表示事件序列的起始时间，Te表示事件序列的结束时间。

定义2（情节episode/子情节subepisode）情节是事件发生的偏序集合，情节α=＜e2，…，ek＞，ei∈E(1≤i≤k)，其中ei出现在ej之前(1≤i＜j≤k)，情节长度=k。设情节α=＜e1，e2，…，ek＞，情节 β=＜e1'，e2'，…，ej'＞(j≤k)，其中存在整型序列1≤l1＜l2＜…≤lj，且ei'=eli(1≤i≤j)，则称 β是α的子情节，α是 β的超情节。

定义3（前缀prefix/投影project/增长growth）给定情节α=＜e1，e2，…，ek＞，情节 β=＜e1'，e2'，…，ej'＞(j≤k)，其中情节β是α的子情节，设m是β在α中首次出现的结束位置，其中对于所有的i(1≤i≤m≤k)，满足ei=ei''，则情节γ=＜e1''，e2''，…，em''＞称为β在α上的前缀，表示为 prefix(α，β)。如情节α=ABACBC，子情节β=BC，则 prefix(α，β)=ABAC。β在α上的投影则是从情节α中删除 β在α上的前缀之后剩余的部分，表示为project(α，β)。如情节α=ABACBC，子情节 β=AB，project(α，β)=ACBC。设情节α=＜e2，…，ek＞，1-情节e=＜e'＞，对 α和e连接形成超情节 β=＜e1，e2，…，ek，e'＞，称作对α进行增长，表示为 β=growth(α，e)，主要用于深度优先搜索时，增长形成新情节。

定义4（向前扩展检查forcheck/向后扩展检查backcheck）

定义4参考BIDEFCE算法的定义，借鉴BIDE[15]算法思想，用于在深度优先搜索生成新情节的时候，对当前情节进行向前、向后扩展检查，判断当前情节是否存在向前或向后扩展项。若存在，则当前情节非闭，直接淘汰；若均为空，则情节待定，加入频繁闭情节超集FCE中，供进一步辨别是否为闭情节。对当前情节α进行向前、向后扩展检查分别表示为 forcheck(α)、backcheck(α)。

定义5（非重叠的最小发生non-overlapping minmal occurrence/支持度support）设情节α在事件序列上的最小发生集合表示为α.mo，若情节α的两次最小发生则称这两次发生是非重叠的最小发生[16]。从事件序列上第一个最小发生开始计算，情节α在事件序列上非重叠的最小发生的最大集合表示为α.nomo，最大集合中元素的数量是情节的支持度，即

如图1中的事件序列ES，情节β=ABA的最小且非重叠的发生情节 β在事件序列上的支持度本文的支持度均采用绝对支持度。

定义6（频繁情节/频繁闭情节/情节生成子episode generator）设支持度阈值min_sup，若情节α在事件序列上非重叠的最小发生的支持度α.sup≥min_sup，则称情节α是频繁情节。设情节α是频繁情节，且在事件序列上不存在等支持度的超情节，则称情节α是频繁闭情节。设 β是频繁情节，f是频繁闭情节，其中 β⊂f，且在事件序列上β不存在等支持度的真子情节，则称情节 β是 f的一个情节生成子。

定义7（情节规则/情节规则的支持度/情节规则的置信度）设情节α和 β，其中 β⊂α，以 β为前件，β在α上的投影 project(α，β)为后件，则在α和 β之间产生情节规则，记作 β⇒project(α，β)。

由情节 α和 β生成的情节规则，其支持度定义为support(β⇒project(α，β))=support(α)，即规则的支持度等于情节α在事件序列上的支持度。

由情节α和β生成的情节规则，其置信度定义为：

若情节规则置信度等于1，称为精确情节规则；置信度小于1，称为近似情节规则。

设情节规则的最小支持度阈值min_sup和最小置信度阈值min_conf，若support(β⇒project(α，β))≥min_sup，则称该情节规则是频繁的；若confidence(β⇒project(α，β))≥min_conf，则称该情节规则是可信的。

定义8（无冗余情节规则）一个情节规则γ:g→r是无冗余情节规则，当且仅当不存在情节规则γ':g'→r'，有supprot(γ)=support(γ')及 confidence(γ)=confidence(γ')，且g'⊆g和r⊆r'。

本文情节规则由一个四元组构成γ=(g，r，sup，conf)，分别表示情节规则的前件、后件、支持度和置信度。

4 挖掘无冗余情节规则的GFExtractor算法

GFExtractor算法分为如下3步：

（1）搜索阶段：深度优先搜索，淘汰非生成子情节及非闭情节，得到情节生成子超集和频繁闭情节超集。

（2）过滤阶段：删除非生成子情节及非闭情节，得到最后的情节生成子集Gen及频繁闭情节集FCE。

（3）生成规则阶段：根据情节生成子集Gen及频繁闭情节集FCE，分别产生精确情节规则和近似情节规则，其中对近似情节规则进行消除冗余后件的处理，最后得到无冗余情节规则集R。

4.1 主要算法

因为频繁1-情节长度为1，不存在等支持度的真子情节，则频繁1-情节都是情节生成子，直接加入情节生成子超集Gen中。

GFExtractor（ES，min_sup，min_conf）

输入：事件序列ES，最小支持度阈值min_sup，最小置信度阈值min_conf

输出：无冗余情节规则集合R

GFExtractor（）算法1～2行，首先初始化情节生成子超集Gen和频繁闭情节超集FCE为空。第3行单遍扫描事件序列并生成频繁1-情节集合F1。4～7行遍历频繁1-情节集合F1，将各1-情节加入情节生成子集合Gen中；若当前1-情节向前、向后扩展检查均为空，情节待定，加入频繁闭情节超集FCE中（参考BIDEFCE算法）。第8行，调用MINE（）子算法，深度优先搜索，挖掘所有的频繁情节。9～11行，对频繁闭情节超集FCE进行过滤，删除闭合性检查为假的情节（参考BIDEFCE算法）。12～14行，对情节生成子超集Gen进行过滤，删除生成子检查为假的情节。15～16行，在情节生成子集合Gen和频繁闭情节FCE之间产生情节规则，并输出。

MINE（）算法17～20行，遍历频繁1-情节集合F1，增长当前情节α和1-情节e得到新情节β；根据α和e的最小发生计算β的最小发生，进而计算出β非重叠的最小发生；21～25行，如果情节β是频繁情节，且β的支持度与其真子情节α和e的支持度均不等，β是待定生成子情节，加入情节生成子超集Gen中；若情节β的向前、向后扩展检查均为空，β是待定闭情节，加入频繁闭情节超集FCE中（参考BIDEFCE算法）；第26行，递归调用MINE（）算法。

MINE（）算法递归调用，深度优先遍历并生成新情节，通过非生成子情节剪枝和非闭情节淘汰策略，尽快产生情节生成子超集Gen和频繁闭情节超集FCE，避免维护频繁情节集合，压缩搜索空间。GFExtractor（）算法通过生成子检查和闭情节检查对Gen和FCE进行过滤，并在两者之间产生情节规则。

4.2 非生成子情节的剪枝

MINE（）算法中，新情节β=growth(α，e)，由真子情节α和频繁1-情节e增长得到。若情节β的支持度等于真子情节α或1-情节e的支持度，根据定义6可以得出情节β必定是非生成子情节，尽快淘汰。即

若情节β是频繁的，且它的支持度不等于真子情节α及e的支持度，则情节β是否生成子情节待定，加入情节生成子超集Gen中。

说明在事件序列上，对于新情节β，若存在支持度相同的真子情节，则情节β为非生成子情节。因此MINE（）算法的第22～23行，对非生成子情节进行剪枝淘汰，只保留生成子待定情节到Gen中，缩小搜索范围。

4.3 生成子情节检查

在情节生成子超集Gen中，若某情节不存在具有相同支持度的真子情节，则该情节为生成子情节。

GeneratorCheck（g）算法中，遍历生成子超集Gen，判断当前情节g是否存在等支持度的真子情节f，若存在，则返回假，表示g是非生成子情节。遍历完生成子超集Gen，若不存在等支持度的真子情节f，则返回真，表示g是生成子情节。

生成子情节检查只需遍历生成子超集Gen，避免扫描频繁情节集合，降低搜索空间。

情节的闭合性检查，参考BIDEFCE算法。

4.4 生成情节规则

情节规则在情节生成子集Gen及频繁闭情节集FCE之间生成，要求置信度大于等于阈值min_conf。

CreateRule（Gen，FCE，min_conf，R）

输入：情节生成子集合Gen，频繁闭情节集合FCE，最小置信度阈值min_conf

CreateRule（）算法第1行，初始化情节规则集合R为空。第2行，外层遍历情节生成子集合Gen。第3行内层遍历频繁闭情节集合FCE。4～10行，若当前生成子情节g是闭情节f的真子序列，则可在两者之间生成情节规则；SUCC集合保存情节规则的后件，初始化为空；r=project(f，g)计算g在f上的投影，作为情节规则的后件；若生成子情节g与闭情节f等支持度，则置信度为1，生成精确情节规则，加入集合R中；否则将后件r加入到SUCC集合中。11～14行，针对当前生成子g，遍历其后件集合SUCC；若后件s不是冗余的后件，即在SUCC中不存在与s等支持度的超情节，且置信度大于等于min_conf，则生成近似情节规则，并加入到集合R中。第15行，返回情节规则集合R。

CreateRule（）算法针对近似情节规则作了消除冗余后件的处理，保证情节规则有着最小前件和最大后件。如图1所示的事件序列ES上，有情节生成子B∶3与频繁闭情节ABACE∶2及ACBE∶2，它们之间可以产生情节规则，如表1所示。

表1 情节规则示例

此时，两个近似情节规则前件相同且等支持度、等置信度，存在冗余。CreateRule（）算法的第11～14行，对冗余后件E进行了删除，避免生成冗余情节规则B->E。

5 运行实例

以图1所示的事件序列ES为例，支持度阈值min_sup= 2，置信度阈值min_conf=0.4，运行GFExtractor算法，共生成8个情节生成子，7个频繁闭情节，在情节生成子与频繁闭情节之间，经过消除冗余后件处理，最后产生14个无冗余的情节规则。

由表4可知，相对于通过闭情节与频繁情节集挖掘出的所有46个情节规则，GFExtractor算法基于情节生成子和频繁闭情节挖掘出14个情节规则，数量大大减少，同时也没有丢失信息。

表2 ES上的情节生成子集合Gen

表3 ES上的频繁闭情节集合FCE

表4 ES上的情节规则集合R

6 算法性能分析

假设事件序列ES，长度为L，频繁1-情节集合F1，频繁情节集合FE，情节生成子超集Gen，频繁闭情节超集FCE，频繁情节的最大长度max_len，则算法GFExtractor的复杂度分析如下：

6.1 时空复杂度分析

GFExtractor算法的主要时间代价是搜索阶段的非闭情节判断、过滤阶段的生成子检查和闭合性检查，以及情节规则的生成。

参考BIDEFCE算法，搜索阶段的非闭情节判断的时间复杂度为O(|FE|•L•max_len)。过滤阶段，生成子检查时间复杂度为O(|Gen|2•max_len)，闭合性检查时间复杂度为O(|FCE|2•max_len)。情节规则生成，时间复杂度为O(|Gen|•|FCE|)。由于通过非生成子情节剪枝和非闭情节判断后，情节生成子超集Gen和频繁闭情节超集FCE中的元素数量大大减少，因此GFExtractor算法的时间复杂度为O(|FE|•L•max_len)。

GFExtractor算法在挖掘无冗余情节规则过程中，无需维护频繁情节集，只需维护情节生成子超集Gen和频繁闭情节超集FCE及情节规则集R，而情节规则集R是由Gen和FCE计算得来，因此空间复杂度为O(|Gen|•|FCE|)，远小于TASA和WinMiner算法。

6.2 实验评估

基于非重叠的最小发生的支持度定义，对经典算法TASA和WinMiner算法进行了调整，然后与本文的GFExtractor算法进行了时空性能的比较。实验的硬件环境：2 GHz Intel®CoreTM2 Duo CPU，内存2 GB，操作系统Windows XP，程序采用VC实现。实验数据集基于中国知网CNKI平台的文献资源，选用知网的一个WEB服务器上2010-09-01至2010-09-30之间的日志数据，内容包括232 438条读者阅读文献的事件序列，提取阅读文献的标题为事件类型，阅读时间为事件发生的时间，挖掘文献之间的引用关系。

6.2.1 运行时间和支持度阈值、置信度阈值的关系

图2、图3显示，随着支持度阈值或置信度阈值的减小，3种算法运行时间均在增加，其中GFExtractor算法要优于其他两种算法，原因是该算法采用了深度优先搜索策略，并应用非生成子剪枝策略加快挖掘生成子情节的进程。

图2 置信度阈值为60%时运行时间

图3 支持度阈值为7时运行时间

6.2.2 内存开销和支持度阈值、置信度阈值的关系

图4、图5显示，随着支持度阈值或置信度阈值的减小，3种算法的内存开销均在增加，GFExtractor算法要优于其他两种算法。原因是GFExtractor算法是从情节生成子集和频繁闭情节集中抽取情节规则，不需要维护频繁情节集合。

图4 置信度阈值为60%时内存开销

图5 支持度阈值为7时内存开销

6.2.3 规则数量和支持度阈值、置信度阈值的关系

图6、图7显示，随着支持度阈值或置信度阈值的减小，3种算法均产生了更多的情节规则，GFExtractor算法产生的规则数量要小于其他两种算法，原因是GFExtractor算法是基于情节生成子集和频繁闭情节集产生的无冗余情节规则，而其他算法是基于频繁情节集产生的所有情节规则，存在冗余。

图6 置信度阈值为60%时规则数量

图7 支持度阈值为7时规则数量

7 结论

本文提出的GFExtractor算法基于非重叠的最小发生的支持度定义及深度优先搜索策略，采用非生成子情节剪枝策略，及时淘汰非生成子情节，加快情节生成子的挖掘过程；采用双向扩展检查判断并淘汰非闭情节，加快频繁闭情节的挖掘过程；在情节生成子集与频繁闭情节集之间，有效删除近似情节规则的冗余后件，最后产生无冗余的情节规则。理论分析和实验性能研究证明GFExtractor算法能有效地挖掘事件序列上的无冗余情节规则。

[1]Mannila H，Toivonen H，Verkamo A I.Discovering frequent episodes in sequences[C]//Proceedings of the 1stACM SICKDD ConferenceonKnowledgeDiscoveryandData Mining，Montreal，Canada，1995：210-215.

[2]Hatonen K，Klemettinen M，Mannila H，et al.Knowledge discovery from telecommunication network alarm databases[C]// Proceedings of the 12th IEEE International Conference on Data Engineering，New Orleans，Louisiana，1996：115-122.

[3]Meger N，Rigotti C.Constraint-based mining of episode rules and optimal window sizes[C]//Proceedings of the 8th European Conference on Principles and Practice of Knowledge Discovery in Database，Pisa，Italy，2004：313-324.

[4]Hwang K，Cai M，Chen Y，et al.Hybrid intrusion detection with weighted signature generation over anomalous internet episodes[J].IEEE Transactionson Dependable and Secure Computing，2007，4（1）：41-55.

[5]Wang P，Wang H，Liu M，et al.An algorithmic approach to event summarization[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data，Indianapolis，Indiana，USA，2010：183-194.

[6]Patnaik D，Marwah M，Sharma R，et al.Sustainable operation and management of data center chillers using temporaldatamining[C]//Proceedingsofthe15thACM SIGKDD Conference on Knowledge Discovery and Data Mining，Paris，France，2009：1305-1313.

[7]Zhu H，Wang P，He X，et al.Efficient episode mining with minimal and non-overlapping occurrences[C]//Proceedings of the 10th IEEE International Conference on Data Mining，Sydney，Australia，2010：1211-1216.

[8]Bastide Y，Taouil R，Pasquier N，et al.Mining frequent patterns with counting inference[J].SIGKDD Explorations，2000，2（2）：66-75.

[9]Pasquier N，Bastide Y，Taouil R，et al.Discovering frequent closed itemsets for association rules[C]//Proceedings of the 7th International Conference on Database Theory，Jerusalem，Israel，1999：398-416.

[10]Li J，Li H，Wong L，et al.Minimum description length principle：generators are preferable to closed patterns[C]//Proceedings of the 21st National Conference on Artificial Intelligence Conference，Boston，Massachusetts，USA，2006：409-414.

[11]Bastide Y，Pasquier N，Taouil R，et al.Mining minimal non-redundant association rules using frequent closed itemsets[C]//Proceedings of the 1stInternationalConference on Computational Logic，London，UK，2000：972-986.

[12]Li J，Liu G，Wong L.Mining statistically important equivalence classes and delta-discriminative emerging patterns[C]// Proceedingsofthe13th ACM SICKDD Conferenceon Knowledge Discovery and Data Mining，San Jose，California，USA，2007：430-439.

[13]Lo D，Khoo S C，Li J.Mining and ranking generators of sequentialpatterns[C]//ProceedingsoftheSIAM International Conference on Data Mining，Atlanta，Georgia，USA，2008：553-564.

[14]朱辉生，汪卫，施伯乐.基于频繁闭情节及其生成子的无冗余情节规则抽取[J].计算机学报，2012（1）：53-63.

[15]Wang J，Han J.BIDE：efficient mining of frequent closed sequences[C]//Proceedings of the 20th International Conference on Data Engineering.Boston：IEEE，2004：79-90.

[16]朱辉生，汪卫，施伯乐.基于最小且非重叠发生的频繁闭情节挖掘[J].计算机研究与发展，2013（4）：852-860.

YUAN Hongjuan

School of Mathematics and Information,Taizhou University,Taizhou,Jiangsu 225300,China

Mining episode rules in event sequence aims to discover the causal relationship between the episodes.To mine non-redundant episode rules in event sequence,the algorithm of GFExtractor is proposed in this paper,based on the support definition of non-overlapping minimal occurrences and the depth-first search strategy.GFExtractor uses the pruning technology to eliminate non-generator episodes,and uses the forward and backward extension check to eliminate non-closed episodes.Nonredundant episode rules are generated between a superset of Gen and FCE.Experimental results confirm the validity of algorithm in mining non-redundant episode rules in event sequence.

episode generator;frequent closed episode;episode rules

事件序列上挖掘情节规则，旨在发现情节之间的因果关系。基于非重叠的最小发生的支持度定义及深度优先搜索策略，提出在事件序列上挖掘无冗余情节规则的GFExtractor算法。利用非生成子情节的剪枝策略，淘汰非生成子情节；利用向前、向后扩展检查，淘汰非闭情节；最终在情节生成子集Gen与频繁闭情节集FCE之间产生无冗余的情节规则。实验结果证实了算法在事件序列上挖掘无冗余情节规则的有效性。

情节生成子；频繁闭情节；情节规则

A

TP311

10.3778/j.issn.1002-8331.1306-0271

YUAN Hongjuan.GFExtractor：algorithm of mining non-redundant episode rules effectively in event sequence.Computer Engineering and Applications,2013,49（23）：106-111.

袁红娟（1979—），女，讲师，研究领域为数据挖掘。E-mail：yhj_blue@126.com

2013-06-24

2013-09-04

1002-8331（2013）23-0106-06