一种基于滑窗的增量式过程挖掘算法1

《一种基于滑窗的增量式过程挖掘算法1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1一种基于滑窗的增量式过程挖掘算法1,221,2查海平王建民孙家广(1.清华大学计算机科学与技术系，北京100084；2.清华大学软件学院，北京100084)摘要演化过程的执行日志包含了不同时刻系列模型的执行轨迹，而传统过程挖掘算法针对静态模型和静态日志进行设计，不能直接用于演化过程的发现。本文提出一种过程挖掘算法，应用滑窗机制实现增量式算法设计，利用日志事件关系模型，并引入日志事件关系计数和阀值机制，实现对事件日志流进行持续挖掘，能够发现模型演化的历史及当前的业务过程模型。最后分析了复杂度等算法性质，以及影响挖掘结果的相关因素，并进行了实验验证。关键词过程挖掘;演化过程;滑

2、窗算法中图分类号TP311文献表示码AAnincrementalalgorithmforprocessminingbased-onslidingwindow1,221,2ZHAHai-ping,WANGJian-ming,SUNJia-guang(1.Dep.ofComputerS&T,TsinghuaUniv.,Beijing100084,China;2.Sch.ofSoftware,TsinghuaUniv.,Beijing100084,China)AbstractMostexistingprocessminingalgorithmsaredesignedforstati

3、cmodelsandstaticeventlogs,notavailableforminingevolutionaryprocessesimmediately.Thispaperproposesanincrementalminingalgorithm,whichappliesaslidingwindowtoeventlogstream,andintroducesevent-relationcountandevent-relationthresholdtechniques.Thealgorithmcangetaseriesofmodelscorrespondingtoevolu

4、tionaryeventlogs,andkeepworkingwithtimeandspaceefficiency.Experimentsaredonetovaluatethediscoverycapacityandpropertiesofthealgorithm.Keywordprocessmining,evolutionprocess,slidingwindowalgorithm1引言业务需求总处于不断变化之中，尽管当初业务过程模型经过了精心设计，但是随着需求的变化，实际业务过程执行会逐渐偏离原有过程模型，其表现如更频繁的异样出现，或是需要更多的人工干预等。如何及时发现业

5、务过程执行偏离，并推荐更符合当前业务需求的过程模型，是适应性工作流系统面临的问题，而过程挖掘技术为解决这一问题提供了一种选择手段。[1]过程挖掘通过系统的事件日志，自动产生过程模型，过程挖掘技术可以用于辅助过程建模、过程模型再发现以及过程执行监控等方面。传统的过程挖掘研究多集中在过程的辅助建模上，文献[2]对事件日志进行事件级的拆分，然后通过对日志中的事件逻辑关系的综合分析，构造符合事件日志的过程模型；文献[3，4，5]先对事件日志进行实例级的聚合操作，然后通过统计分析和推理的办法，得出覆盖所有事件日志的过程模型。以上几种典型过程挖掘算法的共同特点是：（1）假设过程模型是一成

6、不变的，没有考虑日志可能来自不同时期的系列模型；（2）针对静态的日志库进行设计，如果日志更新，则需要对更新后的日志进行重新的扫描。然而，适应性工作流中过程模型会不断演化以适应新的业务需求，其日志可能来自同一业务过程模型的不同版本，因此针对静态模型设计的算法不适合演化过程日志的挖掘。另外，针对静态日志库的算法设计，1基金项目：国家自然科学基金(60373011)；973项目(2002CB312006)也不能实现对演化过程日志的持续挖掘。文献[6]提出了一种增量式过程挖掘算法思想，采用过程代数作为模型的推导手段和展现形式，但对算法只进行了原理上的阐述，没有深入到算法设计和实现层面

7、。针对演化过程日志挖掘，本文提出了一种基于滑动窗口的增量式过程挖掘算法，满足一定的空间和时间复杂度要求下，实现对演化过程日志的持续挖掘。本文内容安排如下：第2节是问题的描述，介绍了演化过程的挖掘问题；第3节是滑窗算法的设计，包括算法基础、算法设计和算法分析；第4节是实验结果，验证了算法的可行性以及相关参数的影响；第5节是全文的结论与未来工作展望。2问题描述我们观察一个演化过程的示例，如图1所示。随着时间的推移，模型从N1，N2，N3到N4逐渐变化。在最初的过程模型N1中，ABCD四个任务按顺序依次执行；