广义无冗余情节规则抽取方法研究

广义无冗余情节规则抽取方法研究摘要：情节规则挖掘旨在发现频繁情节之间的因果关联，现有无损情节规则挖掘方法没有考虑多规则间的关联关系因素，故而存在大量冗余。利用演绎推导特性对情节规则间的关系进行建模，引入了无冗余情节迹规则的概念，分析了情节迹冗余的原因，基于最大重叠项冗余性检查给出了广义无冗余情节规则抽取算法；证明了广义无冗余情节规则对情节规则的等价表达能力。理论分析和实验评估表明该算法在处理效率基本不变的前提下，提高了情节规则的生成质量。关键词：事件序列，演绎，情节迹，最大重叠项，情节规则中图分类号：TP311文献标识码：AResearchonExtractingGeneralizedNon-RedundantEpisodeRulesAbstract:Aimingattheproblemthatcurrentnondestructiveepisoderuleminingalgorithmsdon’tconsidertherelationshipbetweenepisoderulesandgenerateredundancy,wemodeltherelationshipamongtheepisoderulesbyusingdeductioncharacteristic,andintroducetheconceptofnon-redundantepisodetracerules.Wealsoanalyzereasonsforepisodetraceredundancy,andpresentthegeneralizednon-redundantepisoderulesminingalgorithmbasedontheredundantcheckingonmaximumoverlapitems.Thenweprovethatgeneralizednon-redundantepisoderuleskeeptheequivalentexpressionabilitytoepisoderules.Theoreticalanalysisandexperimentsdemonstratethisalgorithmimprovedthequalityofgeneratedepisoderuleswithalmostthesameefficiency.Keywords:eventsequence,deduction,episodetrace,maximumoverlapitems,episoderule1.引言情节刻画了事件间的紧随关系，而情节规则描述了情节内的因果关联。自Mannila等人[1]引入情节规则的概念以来，情节规则挖掘问题[2,3]一直是数据挖掘领域研究的热点之一。基于情节规则匹配的预测方法被广泛应用在传感器数据处理、网络安全监控、金融证券管理、软件规范挖掘、城市交通管理、事务日志分析等众多领域[4]。在众多预测方法中，无论是Laxman等人[5]提出的生成模型预测方法，还是Cho等人[6]提出ToFel算法、基于后向检索规则前件策略的数据流预测算法CBS-Tree、CBS-Tree改进算法[7]，其核心都是通过查找规则前件的发生来进行预测。而从历史数据中挖掘出的规则数量，直接影响各预测算法的预测效率。因此，自从情节规则挖掘诞生以来，针对规则精简集的挖掘算法研究一直比较活跃。已有情节规则挖掘的各类算法，虽然在数据组织、处理流程等方面各有不同，但主要分为三类，如表1所示。1、产生情节规则全集的典型算法为TASA[8]、WinMiner[9]。TASA算法分为3个步骤：首先，基于广度优先的搜索策略和滑动窗口的情节支持度定义，通过多遍扫描事件序列，以候选、剪枝再测试的处理方式发现频繁情节；其次，由频繁情节集产生情节规则集；最后，使用剪枝技术来筛选冗余的情节规则。WinMiner算法采用了深度优先的搜索策略和最小发生的情节支持度定义，只需单遍扫描事件序列便可完成挖掘，且不会产生任何候选情节。2、产生最小前件情节规则全集的典型算法为GenMiner[10]，算法首先采用深度优先的搜索策略来创建存储所有情节的前缀搜索树PSL，然后通过遍历PSL得到包含所有情节模式生成子的超集，据此可以得到最小前件情节规则。3、产生无冗余情节规则集的典型算法为Extractor[11]，算法采用最小且非重叠发生的支持度定义和深度优先的搜索策略来发现频繁闭情节及其生成子，保证了频繁闭情节及其生成子的挖掘质量和挖掘效率；利用非生成子情节的Apriori性质，避免了冗余的情节生成子判断；直接由频繁闭情节及其生成子产生情节规则，提高了情节规则的生成质量和生成效率。表1典型情节规则挖掘算法分类比较类别产生方式产生规则1频繁情节投影情节规则全集2频繁情节与生成子投影最小前件情节规则全集3频繁闭情节与生成子投影无冗余情节规则集上述情节规则抽取算法的发展不难看出，规则的产生方式经历了频繁情节投影、频繁情节及其生成子投影、频繁闭情节及其生成子投影等阶段；无论是算法的效率、精确程度、精简粒度都在逐步提高；且都保持了情节规则的完备性，属于无损规则挖掘方法。近年来，伴随不同应用的需求变更，诞生了许多对规则集的有损挖掘方法。文献[12]提出了挖掘top-K无冗余情节规则的方法，算法根据规则的支持度大小，选择前K个情节规则。这样既限定了情节规则数量，又可以保证规则代表信息的有用性，达到了对规则进行约减的目的，但却损失了支持度较小的情节规则信息。文献[13]提出信息情节规则的概念，在给定预测目标的前提下，保证参与预测的情节规则数量最少。该算法采用模式倒置树，生成对应预测目标的信息情节规则。算法虽然不会对预测结果产生影响，但是得到的情节规则未包含完整的情节规则集信息。文献[14]为了使挖掘的情节规则更具预测性，提出了严格支持度阈值的概念，同时在挖掘过程中不断调整置信度。算法虽然挖掘到的情节规则蕴含较高的预测信息，但却损失了较低的支持度与置信度的情节规则，在某些情况下会影响到最终预测的效果。综上所述，现有的情节规则挖掘算法存在以下不足：①无损规则挖掘方法仅考虑了两规则间的包含冗余，忽略了多规则间的关联关系，造成了该类方法虽然能够产生完备规则集，但仍存在冗余；②有损规则挖掘方法虽然考虑了多规则间的关联关系（如top-K利用多规则间排序关系、信息情节规则利用多规则的表达关系等），但是方法本身得到的是规则的不完备集。能否得到一种利用多规则关系化简的无损情节规则挖掘方法？众所周知，频繁情节的挖掘是在频繁项挖掘的基础上发展而来的，相对于频繁项的挖掘，情节挖掘带有有序、可重复等特征。基于频繁闭情节及其生成子产生无冗余情节规则的方法也是从频繁闭项集及其生成子产生精简关联规则的思想发展而来的。延续这一思路，从比频繁闭项集更加精简的项集挖掘过程（这些项集挖掘考虑了多项集间的关联）中是否可以发现更加精简的情节规则抽取方法？这正是本文研究的主要动机。在频繁项集的挖掘研究中，频繁闭项集并不是最小的压缩方式。已有研究中，非可导频繁项集[5]被证明是最小的压缩表示方式，不但可以节省大量系统资源，而且能够使用户更好地理解关联规则。非可导频繁项集是在2002年根据多项集间的演绎关系提出来的，文献[15]将非可导项集应用到关联规则挖掘上，取得了良好的效果。但一方面文献[15]的算法没有考虑演绎推导对规则集的约简作用，另一方面它针对的是关联规则挖掘并非情节规则挖掘。为此，我们利用演绎推导特性对情节规则间的关系进行建模，引入了无冗余情节迹规则的概念，提出了广义无冗余情节规则，并在无冗余情节规则抽取的基础上给出了广义无冗余情节规则生成方法（GeneralizedNon-RedundantMiner,GNRMiner）。理论分析和实验评估表明该算法能有效地抽取给定事件序列上的广义无冗余情节规则，与无冗余情节规则相比，规则数量平均降低41%（最差27%，最好67%）。2.广义无冗余情节规则抽取方法2.1相关定义[7]定义1(事件，事件序列)。事件是给定事件类型集12{,,,}nEEEL中的事件E和事件发生时间t的二元组(,)Et。事件序列是由若干中的事件按发生时间先后排列的序列，表示为1122(,),(,),,(,)ssESEtEtEtL。定义2(情节)。一个情节是由若干事件组成的序列，表示为1122(,),(,),,(,)kkEtEtEtL，简记为12kEEEL。定义3(串接，投影)。给定情节12mEEEL和12'''kEEEL，则1212'''mkEEEEEELL称为和的串接，记为(,)concat。设，j是在中首次出现的结束位置，则从中删除第1至第j个事件后剩余的情节称为在上的投影，记为(,)project。定义4(发生)。给定事件序列ES和情节12kEEEL，若ES在时间区间1[,]ktt上按的事件排列顺序出现了所代表的所有事件，则称ES上发生了情节，时间区间1[,]ktt称为在ES上的一次发生。定义5(支持度)。情节在事件序列ES上所有发生的数目称为的支持度，记为.sup。定义6(频繁情节，频繁闭情节，情节生成子)。给定支持度阈值min_sup，若情节的支持度大于等于min_sup，则是一个频繁情节。若情节是频繁的，且的支持度不等于的任何一个真超情节的支持度，则是一个频繁闭情节。设f是一个闭情节，gf，若g的支持度等于f的支持度，且g不存在与其支持度相同的任何一个真子情节，则g称为闭情节f的一个情节生成子。定义7(情节规则)。一个情节规则是一个五元组(,,,,)lrsc。其中的前件、后件、支持度、置信度和窗口宽度分别记为lrsc、、、、。定义8(无冗余情节规则)。给定情节规则(,,,,)lrscw，若不存在情节规则'(,,,,)lrscw，使得'.=.ss，'..cc，'..ll，'..rr，则称是一个无冗余情节规则，否则是一个冗余情节规则。2.2无冗余情节迹规则无冗余情节规则给出了两情节规则间的包含关系，相关算法据此对规则集合进行约简。下面我们应用演绎推理给出情节规则间的演绎关系。定理1规则演绎。如果规则、'、''之间，满足(1).'.ll或者.('.,'.)lconcatlr；(2)(.,.)''.concatlrl或者(.,.)(''.,''.)concatlrconcatlr，则'''。证明：'.l、('.,'.)concatlr的支持度可以由规则'得到，而.l满足条件(1)，即.l的支持度可知；''.l、(''.,''.)concatlr的支持度可以由规则''得到，而(.,.)concatlr满足条件(2)，即(.,.)concatlr的支持度可知；进而可以计算规则的支持度、置信度，确定其窗口宽度。因此'''。定理1得证。由规则间的演绎定理，我们可以得到无冗余情节迹规则的概念描述如下。定义9(无冗余情节迹规则)。给定情节规则(,,,,)lrscw，若不存在情节规则'(,,,,)lrscw、''(,,,,)lrscw，使得(1).'.ll或者.('.,'.)lconcatlr；(2)(.,.)''.concatlrl或者(.,.)(''.,''.)concatlrconcatlr同时成立。即不可以从其他规则的产生轨迹上推导得出，则称是一个无冗余情节迹规则，否则是一个冗余情节迹规则。定理1和定义9分别给出了规则演绎和无冗余情节迹规则的最一般描述，对描述进行展开，可以得到规则演绎的各种情况如表2所示。为了不失一般性，我们对表2所示的各种情况分析如下。表2规则演绎的情况分解表情形规则1提供规则2提供约束条件1整个情节整个情节前件相等2整个情节整个情节前件不相等3前件前件情节相等4前件前件情节不相等5前件整个情节前件不相等、情节不相等对于情