计算机科学 ›› 2019, Vol. 46 ›› Issue (8): 71-77.doi: 10.11896/j.issn.1002-137X.2019.08.011

• 大数据与数据科学* • 上一篇    下一篇

日志诱导下的形态学片段流程聚类方法

孙书亚, 方欢, 方贤文   

  1. (安徽理工大学数学与大数据学院 安徽 淮南232001)
  • 收稿日期:2018-08-15 出版日期:2019-08-15 发布日期:2019-08-15
  • 通讯作者: 方欢(1982-),女,博士,副教授,主要研究方向为Petri网理论与应用、业务过程管理方法与应用,E-mail:fanghuan0307@163.com
  • 作者简介:孙书亚(1994-),女,硕士,主要研究方向为Petri网理论与应用,E-mail:2351982104@qq.com;方贤文(1975-),男,博士,教授,主要研究方向为Petri网和可信软件
  • 基金资助:
    国家自然科学基金项目(61472003,61272153,61340003,61402011,61572035),安徽省自然科学基金项目(1608085QF149),安徽省高校优秀青年人才基金项目(gxyqZD2018038),安徽省博士后基金项目(2018B288)

Log-induced Morphological Fragments Process Clustering Method

SUN Shu-ya, FANG Huan, FANG Xian-wen   

  1. (School of Mathematics and Big Data,Anhui University of Science & Technology,Huainan,Anhui 232001,China)
  • Received:2018-08-15 Online:2019-08-15 Published:2019-08-15

摘要: 在业务流程管理系统中,执行同一目的的任务流可能存在若干事件集的多种不同排列方式,对应在日志上则表现为很多日志存在着诸多变化,同时具有很多业务的共性特征。因此,如何提取日志行为的共性,将多个相似日志的流程进行聚类,实现提取流程簇业务系统的共性,对相似流程的业务融合具有积极意义。文中提出了一种基于日志的流程聚类方法,首先对日志中的低频事件进行过滤,利用日志形态学片段提取公共的高频片段,进而通过形式自动机将提取的公共高频片段转换为相似日志的聚类中心;然后,提出基于形态学片段的业务组合方法产生流程模型共性的频繁执行路径,将相似的等价类形态学片段进行业务组合,得到组合后的Petri网模型,即为流程簇的聚类中心;最后,通过一个实际的案例验证了所提方法的可行性和有效性。

关键词: 形态学片段, 流程聚类, 流程组合, Petri网

Abstract: In the business process management system,there may be many different arrangements of several event sets in the task flow for performing the same purpose.Corresponding to the logs,it shows that many logs have many changes,but also have some common characteristics of many services.Therefore,extracting the commonality of the logs behavior and clustering multiple similar logs of the similar type of business system have positive significance for the business integration of similar processes.This paper proposed an approach of process clustering method.Firstly,low-frequency events are filtered out,and common high-frequency fragments from the morphological fragments in the log are extracted by automata.And then the extracted public high-frequency fragments are converted into clusters of similar logs through automation formal method.Then,a morphological fragment-based approach is proposed.A business combination algorithm is generated for those frequent execution paths of the commonality of the process model.By combining similar equivalent morphological fragments for business combination,a fused Petri net model is obtained.Finally,a practical case is proposed to verify the feasibility and validity of the proposed method

Key words: Morphological fragments, Process clustering, Process combination, Petri net

中图分类号: 

  • TP391.9
[1] AALST W M P V D.Process Mining - Data Science in Action(2nd edn)[M]. Springer,Heidelberg,2016.
[2] LIU X,DING C.Learning Workflow Models from Event Logs Using Co-clustering[J].International Journal of Web Services Research,2013,10(3):42-59.
[3] LEONI M D,AALST W M P V D,DEES M.A general process mining framework for correlating,predicting and clustering dynamic behavior based on event logs[J].Information Systems,2016,56(C):235-257.
[4] MILANI F,DUMAS M,AHMED N,et al.Modelling families of business process variants:A decomposition driven method[J].Information Systems,2016,56:55-72.
[5] LI C,REICHERT M,WOMBACHER A.Discovering process reference models from process variants using clustering techniques[J].Centre for Telematics & Information Technology University of Twente,2018,16(5):1-30.
[6] WESKE M.Business Process Management:Concepts,Langua- ges,Architectures[M].Springer-Verlag New York,Inc.2007.
[7] POURMASOUMI A,KAHANI M,BAGHERI E.Mining variable fragments from process event logs[J].Information Systems Frontiers,2017,19(6):1-21.
[8] MA H,TANG Y,WU L K.Model update method in process in- cremental mining[J].Computer Science,2009,36(5):154-157.
[9] BOLT A,LEONI M D,AALST W M P V D.Process Variant Comparison:Using Event Logs to Detect Differences in Behavior and Business Rules[J].Information Systems Frontiers,2018,74(1):53-66.
[10] DÖHRING M,REIJERS H A,SMIRNOV S.Configuration vs.adaptation for business process variant maintenance:An empirical study[J].Information Systems,2014,39(1):108-133.
[11] BUIJS J C A M,REIJERS H A.Comparing Business Process Variants Using Models and Event Logs[M]∥Enterprise,Business-Process and Information Systems Modeling.Springer Berlin Heidelberg,2014:154-168.
[12] BUIJS J,DONGEN B,AALST W.Mining Configurable Process Models from Collections of Event Logs[C]∥International Conference on Business Process Management.Springer-Verlag,2013:33-48.
[13] ASSY N,GAALOUL W,DEFUDE B.Mining Configurable Process Fragments for Business Process Design[M]∥Advancing the Impact of Design Science:Moving from Theory to Practice.Springer International Publishing,2014:209-224.
[14] HASANKIYADEH A,KAHANI M,BAGHERI E,et al.Mining common morphological fragments from process event logs[C]∥International Conference on Computer Science and Software Engineering.IBM Corp,2014:179-191.
[15] ASSY N,CHAN N,GAALOUL W,et al.Deriving configurable fragments for process design[J].International Journal of Business Process Integration & Management,2014,7(1):2-21.
[16] LU X X,FAHLAND D D,WIL V D A W.Interactively exploring logs and mining models with clustering,filtering,and relabeling[C]∥Proceedings of the BPM 2016 Tool Demonstration TRACK.2016.
[17] ASSY N,CHAN N,GAALOUL W.Assisting Business Process Design with Configurable Process Fragments[C]∥IEEE International Conference on Services Computing.IEEE Computer Society,2013:535-542.
[18] DERGUECH W,BHIRI S.Merging Business Process Variants [C]∥Business Information Systems,International Conference(Bis 2011).Poznan,Poland,DBLP,2011:86-97.
[19] 方贤文.Petri网行为轮廓理论及其应用[M].上海:上海交通大学出版社,2017:39-40.
[20] ZEMNI M A,HADJ-ALOUANE N B,MAMMAR A.Business Process Fragments Behavioral Merge[M]∥On the Move to Meaningful Internet Systems:OTM 2014 Conference.Berlin:Springer,2014:112-129.
[21] 蒋宗礼,姜守旭.形式语言与自动机理论[M].北京:清华大学出版社,2003:71-73.
[1] 杨皓然, 方贤文. 基于概率和时间因素的Petri网业务流程一致性分析[J]. 计算机科学, 2020, 47(5): 59-63.
[2] 李娟,方贤文,王丽丽,刘祥伟. 基于日志自动机的业务流程混沌活动过滤方法[J]. 计算机科学, 2020, 47(1): 66-71.
[3] 苏庆,林昊,黄剑锋,何凡,林志毅. 基于Petri网编码的动态图水印技术研究[J]. 计算机科学, 2019, 46(7): 120-125.
[4] 宋健,方贤文,王丽丽. 基于流程切的过程模型挖掘方法[J]. 计算机科学, 2019, 46(7): 315-321.
[5] 宋健, 方贤文, 王丽丽, 刘祥伟. 基于行为轮廓的业务流程隐变迁挖掘方法[J]. 计算机科学, 2019, 46(12): 334-340.
[6] 曹蕊, 方贤文, 王丽丽. 基于通讯行为轮廓挖掘条件非频繁行为的方法[J]. 计算机科学, 2018, 45(8): 310-314.
[7] 何路路, 方欢. 带数据流的面向服务的业务流程模型变化传播Petri网方法[J]. 计算机科学, 2018, 45(6A): 545-548.
[8] 赵培海, 王咪咪. 基于三维行为关系图的模型一致性检测方法[J]. 计算机科学, 2018, 45(6): 156-160.
[9] 高雅楠,方贤文,王丽丽. 基于Petri网行为紧密度的业务流程配置优化分析[J]. 计算机科学, 2017, 44(Z6): 539-542.
[10] 周杰,李文敬. 基于三层混合编程模型的Petri网并行算法研究[J]. 计算机科学, 2017, 44(Z11): 586-591.
[11] 林雷蕾,周华,代飞,何臻力,沈勇,康洪炜. 一种基于代数语义的软件体系结构求精方法[J]. 计算机科学, 2017, 44(7): 141-146.
[12] 宋振华,张广泉. 基于AOP的时空Petri网的CPS建模[J]. 计算机科学, 2017, 44(7): 38-41.
[13] 宋相君,张广泉. 基于扩展混成Petri网的CPS无人车系统建模与分析[J]. 计算机科学, 2017, 44(7): 21-24.
[14] 赵娜,王剑,李彤,郁涌,李鹏,谢仲文. 面向对象的可信构件网的组装研究[J]. 计算机科学, 2017, 44(11): 104-108.
[15] 李响,李彤,谢仲文,何云,成蕾,韩煦. 一种面向SaaS多租户的多层模型[J]. 计算机科学, 2017, 44(11): 56-63.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[2] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[3] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[4] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[5] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[6] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[7] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[8] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[9] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .
[10] 王振朝,侯欢欢,连蕊. 抑制CMT中乱序程度的路径优化方案[J]. 计算机科学, 2018, 45(4): 122 -125 .