一种面向概率工作流的相似性度量方法
|
摘要
为了在进行业务过程模型的检索与组合验证时比较两个工作流过程之间的相似度,在传统的工作流结构相似性度量与检索的基础上,针对概率式工作流的相似性度量与检索展开研究,通过定义概率结构树来描述工作流系统,在此基础上提出基于树编辑距离的工作流度量方法,进一步将其转换为概率无环有向图,并给出了基于等价迹的检索方法。给出相关的算法设计,并分析了时间复杂度。对该方法进行了系统性实验,评估了其正确性和有效性。
To compare the similarity between two different workflow models in modern business process management applications,based on measuring the structure similarity of workflows in traditional manner,the process similarity in probabilistic workflows was researched.The workflow system was formulated by defining probabilistic structure tree and the workflow measurement method based on tree editing distance was proposed.Furthermore,the proposed method was translated into the probabilistic acyclic directed graph,and the trance equivalence-based retrieval method was given.The corresponding algorithm was presented and its time complexity was also analyzed.The extensive experiment was conducted to evaluate the effectiveness the proposed method.
To compare the similarity between two different workflow models in modern business process management applications,based on measuring the structure similarity of workflows in traditional manner,the process similarity in probabilistic workflows was researched.The workflow system was formulated by defining probabilistic structure tree and the workflow measurement method based on tree editing distance was proposed.Furthermore,the proposed method was translated into the probabilistic acyclic directed graph,and the trance equivalence-based retrieval method was given.The corresponding algorithm was presented and its time complexity was also analyzed.The extensive experiment was conducted to evaluate the effectiveness the proposed method.
引文
[1]HARRINGTON H J.Business process improvement[M].New York,N.Y.,USA:McGraw-Hill,1991.
[2]FAN Yushun.Foundation of workflow management technology[M].Beijing:Tsinghua University Press,2001(in Chinese).[范玉顺.工作流管理技术基础[M].北京:清华大学出版社,2001.]
[3]VAN DER AALST W M P.Process-oriented architectures for electronic commerce and interorganizational workflow[J].Information Systems,2000,24(8):639-671.
[4]VAN DER AALST W M P.Loosely coupled interorganizational workflows:modeling and analyzing workflows crossing organizational boundaries[J].Information and Management,2000,37(2):67-75.
[5]AALST W M P V D,KUMAR A.A reference model for team-enabled workflow management systems[J].Data&Knowledge Engineering,2001,38(3):335-363.
[6]QIAO Shaojie,TANG Changjie,CHEN Yu,et al.Hierarchical clustering algorithm based on tree edit distance[J].Computer Science and Exploration,2007,1(3):282-292(in Chinese).[乔少杰,唐常杰,陈瑜,等.基于树编辑距离的层次聚类算法[J].计算机科学与探索,2007,1(3):282-292.]
[7]BAE J,LIU L,CAVERLEE J,et al.Development of distance measures for process mining,discovery,and integration[J].International Journal of Web Services Research,2007,4(4):1-17.
[8]KUNZE M,WEIDLICH M,WESKE M.Behavioral similarity-aproper metric[J].Lecture Notes in Computer Science,2011,6896:166-181.
[9]LUO Haibin,FAN Yushun,WU Cheng.Workflow technology overview of[J].Journal of Software,2000,11(7):899-907(in Chinese).[罗海滨,范玉顺,吴澄.工作流技术综述[J].软件学报,2000,11(7):899-907.]
[10]HAN Xiaoan.Discovery and reuse of data mining workflow[D].Tianjin:Tianjin University,2008(in Chinese).[韩小安.数据挖掘工作流的发现和复用[D].天津:天津大学,2008.]
[11]ZENG Z,TUNG A K H,WANG J,et al.Comparing stars:on approximating graph edit distance[J].Proceedings of the VLDB Endowment,2009,2(1):25-36.
[12]FU X,YUE K,ZOU P,et al.A process distance metric based on alignment of process structure trees[J].Lecture Notes in Computer Science,2012,7234:221-232.
[13]SONG L,DENG Y,CAI X.Towards automatic measurement of probabilistic processes[C]//Proceedings of the 7th International Conference on Quality Software.Washington,D.C.,USA:IEEE Computer Society,2007:50-59.
[14]VAN DER AALST W M P,ALVES DE MEDEIROS A K,WEIJTERS A J M M.Process equivalence:comparing two process models based on observed behavior[J].Lecture Notes in Computer Science,2006,4102:129-144.
[15]AALST W V D,WEIJTERS A,MARUSTER L.Workflow mining:discovering process models from event logs[J].IEEE Transactions on Knowledge&Data Engineering,2004,16(9):1128-1142.
[16]VAN DER AALST W M P,BASTEN T.Inheritance of workflows:an approach to tackling problems related to change[J].Theoretical Computer Science,2002,270(1):125-203.
[17]JUNG J,BAE J,LIU L.Hierarchical business process clustering[C]//Proceedings of 2013IEEE International Conference on Services Computing.Washington,D.C.,USA:IEEE,2008:613-616.
[18]LI C,REICHERT M,WOMBACHER A.On measuring process model similarity based on high-level change operations[M].Berlin,Germany:Springer-Verlag,2008:248-264.
[19]XIE Jianen.Workflow model mining based on event log[D].Hangzhou:Hangzhou Dianzi University,2011(in Chinese)[谢建恩.基于事件日志的工作流模型挖掘[D].杭州:杭州电子科技大学,2011.]
[20]KOEHLER J,VANHATALO J,VOLZER H.The refined process structure tree[J].Data&Knowledge Engineering,2009,68(9):793-818.
[21]REIJERS H,MENDLING J.Modularity in process models:review and effects[M]//Business Process Management.Berlin Heidelberg,Germany:Springer-Verlag,2008:20-35.
[22]GUO Xitong.A dataflow perspective for business process integration[D].HongKong:City University of Hong Kong,2010.
[23]ALONSO G,AGRAWAL D,ABBADI A E,et al.Functionality and limitations of current workflow management systems[J].IEEE Expert,1998,12:754-763.
[24]MOHAN C.Recent trends in workflow management products,standards and research[M]//Workflow Management Systems and Interopera Bility.Berlin,Germany:SpringerVerlag,1998:396-409.
[25]HWANG S Y,WANG H,TANG J,et al.A probabilistic approach to modeling and estimating the QoS of Web-services-based workflows[J].Information Sciences,2007,177(23):5484-5503.
[26]KIEPUSZEWSKI B,HOFSTEDE A H M T,BUSSLER C J.On structured workflow modelling[J].Lecture Notes in Computer Science,2000,1789:241-256.
[27]ZHANG K,SHASHA D.Simple fast algorithms for the editing distance between trees and related problems[J].SIAM Journal of Computing,1989,18(6):1245-1262.
[2]FAN Yushun.Foundation of workflow management technology[M].Beijing:Tsinghua University Press,2001(in Chinese).[范玉顺.工作流管理技术基础[M].北京:清华大学出版社,2001.]
[3]VAN DER AALST W M P.Process-oriented architectures for electronic commerce and interorganizational workflow[J].Information Systems,2000,24(8):639-671.
[4]VAN DER AALST W M P.Loosely coupled interorganizational workflows:modeling and analyzing workflows crossing organizational boundaries[J].Information and Management,2000,37(2):67-75.
[5]AALST W M P V D,KUMAR A.A reference model for team-enabled workflow management systems[J].Data&Knowledge Engineering,2001,38(3):335-363.
[6]QIAO Shaojie,TANG Changjie,CHEN Yu,et al.Hierarchical clustering algorithm based on tree edit distance[J].Computer Science and Exploration,2007,1(3):282-292(in Chinese).[乔少杰,唐常杰,陈瑜,等.基于树编辑距离的层次聚类算法[J].计算机科学与探索,2007,1(3):282-292.]
[7]BAE J,LIU L,CAVERLEE J,et al.Development of distance measures for process mining,discovery,and integration[J].International Journal of Web Services Research,2007,4(4):1-17.
[8]KUNZE M,WEIDLICH M,WESKE M.Behavioral similarity-aproper metric[J].Lecture Notes in Computer Science,2011,6896:166-181.
[9]LUO Haibin,FAN Yushun,WU Cheng.Workflow technology overview of[J].Journal of Software,2000,11(7):899-907(in Chinese).[罗海滨,范玉顺,吴澄.工作流技术综述[J].软件学报,2000,11(7):899-907.]
[10]HAN Xiaoan.Discovery and reuse of data mining workflow[D].Tianjin:Tianjin University,2008(in Chinese).[韩小安.数据挖掘工作流的发现和复用[D].天津:天津大学,2008.]
[11]ZENG Z,TUNG A K H,WANG J,et al.Comparing stars:on approximating graph edit distance[J].Proceedings of the VLDB Endowment,2009,2(1):25-36.
[12]FU X,YUE K,ZOU P,et al.A process distance metric based on alignment of process structure trees[J].Lecture Notes in Computer Science,2012,7234:221-232.
[13]SONG L,DENG Y,CAI X.Towards automatic measurement of probabilistic processes[C]//Proceedings of the 7th International Conference on Quality Software.Washington,D.C.,USA:IEEE Computer Society,2007:50-59.
[14]VAN DER AALST W M P,ALVES DE MEDEIROS A K,WEIJTERS A J M M.Process equivalence:comparing two process models based on observed behavior[J].Lecture Notes in Computer Science,2006,4102:129-144.
[15]AALST W V D,WEIJTERS A,MARUSTER L.Workflow mining:discovering process models from event logs[J].IEEE Transactions on Knowledge&Data Engineering,2004,16(9):1128-1142.
[16]VAN DER AALST W M P,BASTEN T.Inheritance of workflows:an approach to tackling problems related to change[J].Theoretical Computer Science,2002,270(1):125-203.
[17]JUNG J,BAE J,LIU L.Hierarchical business process clustering[C]//Proceedings of 2013IEEE International Conference on Services Computing.Washington,D.C.,USA:IEEE,2008:613-616.
[18]LI C,REICHERT M,WOMBACHER A.On measuring process model similarity based on high-level change operations[M].Berlin,Germany:Springer-Verlag,2008:248-264.
[19]XIE Jianen.Workflow model mining based on event log[D].Hangzhou:Hangzhou Dianzi University,2011(in Chinese)[谢建恩.基于事件日志的工作流模型挖掘[D].杭州:杭州电子科技大学,2011.]
[20]KOEHLER J,VANHATALO J,VOLZER H.The refined process structure tree[J].Data&Knowledge Engineering,2009,68(9):793-818.
[21]REIJERS H,MENDLING J.Modularity in process models:review and effects[M]//Business Process Management.Berlin Heidelberg,Germany:Springer-Verlag,2008:20-35.
[22]GUO Xitong.A dataflow perspective for business process integration[D].HongKong:City University of Hong Kong,2010.
[23]ALONSO G,AGRAWAL D,ABBADI A E,et al.Functionality and limitations of current workflow management systems[J].IEEE Expert,1998,12:754-763.
[24]MOHAN C.Recent trends in workflow management products,standards and research[M]//Workflow Management Systems and Interopera Bility.Berlin,Germany:SpringerVerlag,1998:396-409.
[25]HWANG S Y,WANG H,TANG J,et al.A probabilistic approach to modeling and estimating the QoS of Web-services-based workflows[J].Information Sciences,2007,177(23):5484-5503.
[26]KIEPUSZEWSKI B,HOFSTEDE A H M T,BUSSLER C J.On structured workflow modelling[J].Lecture Notes in Computer Science,2000,1789:241-256.
[27]ZHANG K,SHASHA D.Simple fast algorithms for the editing distance between trees and related problems[J].SIAM Journal of Computing,1989,18(6):1245-1262.