基于简单petri网及gspan算法业务流程频繁结构挖掘

《基于简单petri网及gspan算法业务流程频繁结构挖掘》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、于简单Petri网及gSpan算法业务流程频繁结构挖掘［摘要］针对业务流程的结构特性，提出了将图结构数据挖掘算法应用于业务流程模型的思想，具体将gSpan算法应用于简单Petri网模型，提出筒单Petri网有向图化和d-gSpan算法的可实践方法，实现了业务流程频繁子结构授掘。论文最后以某列车入段检修业务流程进行实验。［关键词］业务流程结构特性；图结构数据挖掘；频繁结构挖掘；简单Petri网；gSpan算法doi：10.3969/j.issn.1673-0194.2013.02.036［中图分类号］TP3

2、91［文献标识码］A［文章编号］1673-0194(2013)02-0076-051引言业务流程的结构化特征，描述了业务规则、文档、信息、资源和任务在业务流程的结构框架中传输、流动。［1］传统数据挖掘方法面向特定分析而专门建立的主题数据，不涉及业务流程的结构特性。近年兴起的“工作流挖掘”(WorkflowMining)也只是基于工作流日志挖掘工作流模型，而不考虑已有业务流程结构特性。［2］文献表明，至今鲜有针对业务流程结构化特性的数据挖掘研究。于简单Petri网及gSpan算法业务流程频繁结构挖掘［摘要］

3、针对业务流程的结构特性，提出了将图结构数据挖掘算法应用于业务流程模型的思想，具体将gSpan算法应用于简单Petri网模型，提出筒单Petri网有向图化和d-gSpan算法的可实践方法，实现了业务流程频繁子结构授掘。论文最后以某列车入段检修业务流程进行实验。［关键词］业务流程结构特性；图结构数据挖掘；频繁结构挖掘；简单Petri网；gSpan算法doi：10.3969/j.issn.1673-0194.2013.02.036［中图分类号］TP391［文献标识码］A［文章编号］1673-0194(2013)

4、02-0076-051引言业务流程的结构化特征，描述了业务规则、文档、信息、资源和任务在业务流程的结构框架中传输、流动。［1］传统数据挖掘方法面向特定分析而专门建立的主题数据，不涉及业务流程的结构特性。近年兴起的“工作流挖掘”(WorkflowMining)也只是基于工作流日志挖掘工作流模型，而不考虑已有业务流程结构特性。［2］文献表明，至今鲜有针对业务流程结构化特性的数据挖掘研究。为挖掘业务流程的结构化特性，需要引入针对结构数据的挖掘方法（结构数据挖掘算法）。由于业务流程的结构特性多被表示为具备特定性质

5、的图结构模型，因此将图结构数据挖掘方法应用于业务流程结构模型是非常自然的思路。近年来，图结构数据挖掘方面的研究有了突出成就，大量频繁子图模式挖掘算法涌现出来。如基于Apriori算法思想的AGM算法［3］和FSG算法［4］、基于FP—Growth算法思想的gSpan算法［5］、基于子图“交”和“扩展”两种操作的FFSM算法［6］等。本文将gSpan（Graph—basedSubstrueturePatternMining,基于图的子结构模式挖掘）算法应用于简单Petri网模型，从而实现业务流程的频繁结构挖

6、掘，即从独立或多个相互关联的业务流程模型中挖掘得到频繁出现的子结构。本研究工作的实践意义在于：在获得业务流程频繁结构后，决策者即可从模块划分、流程设计、资源分配、组织机构等多方面优化频繁子结构，从而把握庞大业务流程中的核心环节，以提高整体业务流程效率。本研究的理论意义在于：业务流程频繁结构可以用来刻画业务流程的结构特性，依据结构特性区分不同的业务流程集合，是依据结构特性对业务流程进行分类和聚类的基础。2频繁子图模式挖掘算法gSpan算法分析设S为库所集，T为变迁集，F为有向弧，F是由一个库所和一个变迁组成

7、有序偶集合。三元组N=(S，T，F)称为一个简单Petri网，[7]当且仅当：①SUT关？准(网非空)；②SC1T=?准(二元性)；③F?舒(SXT)U(TXS)(有向弧仅存在于S与T元素之间)；④dom(F)Ucod(F)=SUT(没有孤立元素)。其中dom(F)是所有有向弧中起点的集合，cod(F)是所有有向弧中终点的集合，即，?祸y:(x，y)eFcod^)=｛乂

8、?祸又：库所、变迁和有向弧在图中分别用圆、矩形和箭头表示。在使用简单Petri网表示业务流程时，库所表示业务案例所处的状态，变迁则表示对

9、某案例所执行的操作，有向弧没有实际意义简单Petri网表达的业务规则，可以由顺序、并行、选择、循环4种基本结构组成(图1)。频繁子图模式挖掘算法gSpan算法[5-8]采用了FP—Growth算法思想，其基本步骤如下：Step1：编码：利用编码标识图结构；Step2:产生初始子图：计算所有边的支持度，得出所有频繁1边子Step3：子图扩展：将频繁k边子图扩展得到k+库所和一个变迁组成有序偶集合。三元组N=(S，T，F)称为一个