一种新的工作流频繁闭合模式挖掘算法研究.pdf

第 39卷 第 11期 计 算 机 科 学 Vo1．39NO．11 2012年 l1月 Computer Science Nov2012 一 种新的工作流频繁闭合模式挖掘算法研究 王丹丹 蒋文娟 (南通大学计算机科学与技术学院 南通226O19) 摘 要 为了提高工作流环境下频繁模式挖掘的准确性，提 出了一种新的频繁闭合模式挖掘算法。首先扩展 了依赖 矩阵的定义，即利用工作流 日志建立包含直接依赖关系和交叠关系的依赖支持度矩阵。然后扩展了CHARM 算法， 以在支持度矩阵的基础上 自动挖掘频繁闭合活动集。最后对频繁 闭合项集进行处理，以形成最终的工作流频繁闭合 模式。该算法对于并行和选择关系的处理能力优于同类算法。 关键词 工作流 ，频繁 闭合模式，依赖矩阵 中图法分类号 TP311 文献标识码 A New Algorithm forM iningW orkflow FrequentClosetPattern WANGDan-dan JIAN GWenjuan (ComputerScience＆ TechnologyInstitute，NantongUniversity，Nantong226019，China) Abstract Toimprovetheaccuracyofworkflow frequentpatterns，weproposedanew algorithm forminingrfequent closedpattern．First。weextendedthedefinitionofthedependenceMatrix，which includesdirectdependencyandover— lappingrelationshipamongactivitiesfrom theworkflow logs．Second，weextendedtheCHAR M algoritmh tomineall closedfrequentpattern soverthedependencematrix．Finally，theworkflow frequentpatternsweregeneratedbydiscar— dingnon-frequentpattern s．Thealgoritmh hasadvantagesindealingwiththeinterleavingrelationsma ongactivitiesand workflow modelswithbothserialorparallelrelations． Keywords W orkflow，Closedfrequentpatterns，Dependencematrix 个活动作为原子事件 ，而没有考虑活动的执行时间间隔，所以 1 引言 只能处理顺序的工作流模式。文献 [7]提出了一种新的工作 自Agrawat等人最早提出利用工作流系统 日志挖掘工作 流频繁模式挖掘算法。该算法将活动间的依赖关系作为 流模型以来，工作流挖掘研究得到越来越多学者的关注l1]。 “项”；然后构建依赖矩阵；最后通过依赖矩阵挖掘频繁项集， 工作流挖掘研究中主要有两个重要问题：工作流模型重构和 得到最终的工作流频繁模式。然而该算法未考虑活动之间存 工作流频繁模式挖掘。工作流模型重构主要通过研究企业已 在的重叠关系，故不能完全处理具有并行关系的工作流模型。 有的日志记录来重构工作流模型。在一系列的工作流模型重 另一方面，该算法以Apriori算法为原型进行扩展 ，因此执行 构算法中，Alast和他的研究小组提出的a算法_2]最为著名。 效率低，很难处理大规模数据。 工作流频繁