计算机科学 ›› 2023, Vol. 50 ›› Issue (6): 338-350.doi: 10.11896/jsjkx.220700061
简开宇, 史涯晴, 黄松, 许山山, 杨忠举
JIAN Kaiyu, SHI Yaqing, HUANG Song, XU Shanshan, YANG Zhongju
摘要: 随着业务流程模型管理库规模的增大,传统的模型管理方式在效率和准确度方面已经无法达到预期,研究能够提升业务流程模型管理效率的技术成为人们的迫切需求。其中,业务流程模型相似度技术在模型搜索、模型一致性检测等模型管理的相关应用场景中能够有效提升工作的效率和精度,因此,对业务流程模型相似度技术的研究已经逐渐成为模型分析领域的一个研究热点,并取得了许多有价值的研究成果。业务流程模型相似度技术涉及的领域较多,可以向不同的分支方向发展,虽然不同分支的模型相似度技术会有方法之间的类比,但是缺乏系统性的整理和分析。文中从相似度计算方法和应用场景这两个层面对业务流程模型相似度技术进行了分类讨论,将相似度计算方法分为文本相似度、语义相似度、结构相似度、行为相似度和基于人类评估的相似度,并分析了每种计算方法的特点。较为常见的业务流程模型相似度应用场景包括一致性检测、标准化、流程模型搜索和模型重用,文中对基于以上场景的相关研究进行了梳理。最后分析了业务流程模型相似度研究面临的挑战。
中图分类号:
[1]YAN Z,DIJKMAN R,GREFEN P.Fast business process similarity search with feature-based similarity estimation[C]//OTM Confederated International Conferences on the Move to Mea-ningful Internet Systems.Berlin:Springer,2010:60-77. [2]BECKER M,LAUE R.A comparative survey of businessprocess similarity measures[J].Computers in Industry,2012,63(2):148-167. [3]THALER T,SCHOKNECHT A,FETTKE P,et al.A comparative analysis of business process model similarity measures[C]//International Conference on Business Process Management.Cham:Springer,2016:310-322. [4]MINOR M,TARTAKOVSKI A,BERGMANN R.Representa-tion and structure-based similarity assessment for agile workflows[C]//International Conference on Case-Based Reasoning.Berlin:Springer,2007:224-238. [5]DONGEN B,DIJKMAN R,MENDLING J.Measuring similarity between business process models[M]//Seminal Contributions to Information Systems Engineering.Berlin:Springer,2013:405-419. [6]CORRALES J C,GRIGORI D,BOUZEGHOUB M.BPELprocesses matchmaking for service discovery[C]//OTM Confederated International Conferences “On the Move to Meaningful Internet Systems”.Berlin:Springer,2006:237-254. [7]YAN Z,SUN B,WANG T.Research on Business Process Model Analysis Method Based on UML [J].Computer Engineering and Applications,2004,40(29):226-228. [8]CAO B,WANG J,FAN J.Interprocess Element Mapping Based on Petri Net [J].Journal of Software,26(3):474-490. [9]ZENG Y.Implementation of BPR process based on extended Petri net model [J].Modular Machine Tool & Automatic Manufacturing Technique,2005(9):37-39,48. [10]SMIRNOV S,REIJERS H A,WESKE M,et al.Businessprocess model abstraction:a definition,catalog,and survey[J].Distributed & Parallel Databases,2012,30(1):63-99. [11]SETIAWAN Y,SUNGKONO K R,SARNO R.A new similarity method based on weighted graph models for matching parallel business process models[J].International Journal of Intelligent Engineering and Systems,2020,13(5):267-276. [12]AKKIRAJU R,IVAN A.Discovering business process similarities:An empirical study with SAP best practice business processes[C]//International Conference on Service-Oriented Computing.Berlin:Springer,2010:515-526. [13]AHN H,CHANG T W.Measuring similarity for manufacturing process models[C]//IFIP International Conference on Advances in Production Management Systems.Cham:Springer,2018:223-231. [14]DIJKMAN R,DUMAS M,VAN DONGEN B,et al.Similarityof business process models:Metrics and evaluation[J].Information Systems,2011,36(2):498-516. [15]BUNKE H.On a relation between graph edit distance and maximum common subgraph[J].Pattern Recognition Letters,1997,18(8):689-694. [16]ZHANG H,WANG G,ZHONG Y.Text Similarity Calculation Based on Hamming Distance[J].Computer Engineering and Applications,2001,37(19):2-7. [17]HUANG C H,YIN J,HOU F.A Text Similarity MeasurementMethod Combining Term Semantic Information and TF-IDF Method [J].Chinese Journal of Computers,2011,34(5):856-864. [18]DICE L R.Measures of the amount of ecologic association between species[J].Ecology,1945,26(3):297-302. [19]WANG Y,QIN J,WANG W.Efficient approximate entity ma-tching using jaro-winkler distance[C]//International Conference on Web Information Systems Engineering.Cham:Springer,2017:231-239. [20]NIWATTANAKUL S,SINGTHONGCHAI J,NAENUDORNE,et al.Using of Jaccard Coefficient for Keywords Similarity[C]//Iaeng International Conference on Internet Computing & Web Services.International Association of Engineers,2013:237-245. [21]JACCARD P.The distribution of the flora in the alpine zone.1[J].New Phytologist,1912,11(2):37-50. [22]BERGROTH L,HAKONEN H,RAITA T.A survey of longest common subsequence algorithms[C]//Proceedings Seventh International Symposium on String Processing and Information Retrieval.IEEE,2000:39-48. [23]DUMAS M,GARCÍA-BAÑUELOS L,DIJKMAN R M.Simi-larity search of business process models[J].IEEE Data Engineering Bulletin,2009,32(3):23-28. [24]JARO M A.Advances in record-linkage methodology as applied to matching the 1985 census of Tampa,Florida[J].Journal of the American Statistical Association,1989,84(406):414-420. [25]LEACOCK C,CHODOROW M.Combining local context andWordNet similarity for word sense identification[J].WordNet:An Electronic Lexical Database,1998,49(2):265-283. [26]WU Z,PALMER M.Verb semantics and lexical selection[J].arXiv:cmp-lg/9406033. [27]RESNIK P.Semantic similarity in a taxonomy:An information-based measure and its application to problems of ambiguity in natural language[J].Journal of Artificial Intelligence Research,1999,11:95-130. [28]LIN D.An information-theoretic definition of similarity[C]//International Conference on Machine Learning.1998:296-304. [29]JIANG J J,CONRATH D W.Semantic similarity based on corpus statistics and lexical taxonomy[J].arXiv:cmp-lg/9709008. [30]CILIBRASI R L,VITANYI P M B.The google similarity distance[J].IEEE Transactions on Knowledge and Data Enginee-ring,2007,19(3):370-383. [31]RECCHIA G,JONES M N.More data trumps smarter algo-rithms:Comparing pointwise mutual information with latent semantic analysis[J].Behavior Research Methods,2009,41(3):647-656. [32]LANDAUER T K,FOLTZ P W,LAHAM D.An introduction to latent semantic analysis[J].Discourse processes,1998,25(2/3):259-284. [33]LI Y,MCLEAN D,BANDAR Z A,et al.Sentence similaritybased on semantic nets and corpus statistics[J].IEEE Transactions on Knowledge and Data Engineering,2006,18(8):1138-1150. [34]GACITUA-DECAR V,PAHL C.Automatic Business ProcessPattern Matching for Enterprise Services Design[C]//2009 World Conference on Services-II.2009:313-374. [35]LEOPOLD H,NIEPERT M,WEIDLICH M,et al.Probabilistic optimization of semantic process model matching[C]//International Conference on Business Process Management.Berlin:Springer,2012:319-334. [36]FELLBAUM C.A semantic network of English:the mother of all WordNets[C]//EuroWordNet:A multilingual Database with Lexical Semantic Networks.Dordrecht:Springer,1998:137-148. [37]LI S J.Research on Sentence Relevance Based on Semantic Computing [J].Computer Engineering and Applications,2002,38(7):3-12. [38]ANTUNES G,BAKHSHANDEH M,BORBINHA J,et al.The process model matching contest 2015[M].Geellschaftfür Informatik,2015. [39]CAYOGLU U,DIJKMAN R,DUMAS M,et al.Report:Theprocess model matching contest 2013[C]//International Confe-rence on Business Process Management.Cham:Springer,2013:442-463. [40]LI C,REICHERT M,WOMBACHER A.On measuring process model similarity based on high-level change operations[C]//International Conference on Conceptual Modeling.Berlin:Sprin-ger,2008:248-264. [41]KUNZE M,WEIDLICH M,WESKE M.Behavioral similarity-a proper metric[C]//International Conference on Business Process Management.Berlin:Springer,2011:166-181. [42]VAN DER AALST W M P,MEDEIROS A K,WEIJTERS A.Process equivalence:Comparing two process models based on observed behavior[C]//International Conference on Business Process Management.Berlin:Springer,2006:129-144. [43]XU Z,KUN Z,NING L,et al.Overview of graph editing distance [J].Computer Science,2018,45(4):11-18. [44]MELCHER J,SEESE D.Visualization and clustering of busi-ness process collections based on process metric values[C]//2008 10th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing.IEEE,2008:572-575. [45]GERKE K,CARDOSO J,CLAUS A.Measuring the complianceof processes with reference models[C]//OTM Confederated International Conferences on the Move to Meaningful Internet Systems.Berlin:Springer, 2009:76-93. [46]ZHA H,WANG J,WEN L,et al.A workflow net similarity measure based on transition adjacency relations[J].Computers in Industry,2010,61(5):463-471. [47]XING J,ZHANG X,SONG W,et al.BPEL Similarity-a metric based on activity constraint graphs[C]//Asia-Pacific Conference on Business Process Management.Cham:Springer,2013:39-55. [48]LI H,GUO C,QIU W.Computing Method of Similarity of Normal Cloud Model [J].Acta Electronica Sinica,2011,39(11):25-61. [49]WEIDLICH M,DIJKMAN R,MENDLING J.The ICoP framework:Identification of correspondences between process models[C]//International Conference on Advanced Information Systems Engineering.Berlin:Springer,2010:483-498. [50]KLINKMÜLLER C,LEOPOLD H,WEBER I,et al.Listen to me:Improving process model matching through user feedback[C]//International Conference on Business Process Management.Cham:Springer,2014:84-100. [51]RODRÍGUEZ C,KLINKMÜLLER C,WEBER I,et al.Activity matching with human intelligence[C]//International Conference on Business Process Management.Cham:Springer,2016:124-140. [52]LAUE R,BECKER M.Evaluating social tagging for business process models[C]//International Conference on Business Process Management.Springer,2012:280-291. [53]SHAHMIRZADI O,LUGOWSKI A,YOUNGE K.Text simi-larity in vector space models:a comparative study[C]//2019 18th IEEE International Conference on Machine Learning and Applications(ICMLA).IEEE,2019:659-666. [54]JI C,WANG J,GENG R.Weak selection backtracking matching tracking algorithm based on Dice coefficient[J].Journal of Northeastern University(Natural Science),201,42(02):189-195. [55]SCHOKNECHT A,FISCHER N,OBERWEIS A.Process mo-del search using latent semantic analysis[C]//International Conference on Business Process Management.Cham:Springer,2016:283-295. [56]TANG H G.Research and Implementation of Data Migration Based on Business Process Model Similarity [D].Shanghai:Shanghai Institute of Computing Technology,2020. [57]MERKX D,FRANK S L,ERNESTUS M.Semantic sentencesimilarity:size does not always matter[J].arXiv:2106.08648. [58]EHRIG M,KOSCHMIDER A,OBERWEIS A.Measuring similarity between semantic business process models[C]//APCCM.2007:71-80. [59]HUANG G,ZHOU Z.Research on Semantic Similarity Calculation of Concept Based on Domain Ontology[J].Computer Engineering and Design,2007,28(10):2460-2463. [60]ZHANG P.Computational Model of Sentence Similarity based on Multi-Feature Fusion [J].Computer Engineering and Applications,2010,46(26):136-137. [61]VAN GLABBEEK R J,WEIJLAND W P.Branching time and abstraction in bisimulation semantics[J].Journal of the ACM(JACM),1996,43(3):555-600. [62]LOPEZ-GAZPIO I,MARITXALAR M,LAPATA M,et al.Word n-gram attention models for sentence similarity and infe-rence[J].Expert Systems with Applications,2019,132:1-11. [63]QU R,FANG Y,BAI W.Computing semantic similarity based on novel models of semantic representation using Wikipedia[J].Information Processing & Management,2018,54(6):1002-1021. [64]KRISSINEL E B,HENRICK K.Common subgraph isomor-phism detection by backtracking search[J].Software:Practice and Experience,2004,34(6):591-607. [65]RAYMOND J W,GARDINER E J,WILLETT P.Rascal:Calculation of graph similarity using maximum common edge subgraphs[J].The Computer Journal,2002,45(6):631-644. [66]DIJKMAN R,DUMAS M,GARCÍA-BAÑUELOS L.Graphmatching algorithms for business process model similarity search[C]//International Conference on Business Process Mana-gement.Berlin:Springer,2009:48-63. [67]YU H.Research on Business Process Similarity Measurement Based on Internal Structure [D].Shenzhen:Shenzhen University,2016. [68]LA ROSA M,DUMAS M,UBA R,et al.Business process model merging:An approach to business process consolidation[J].ACM Transactions on Software Engineering and Methodology(TOSEM),2013,22(2):1-42. [69]SCHOKNECHT A,THALER T,FETTKE P,et al.Similarity of business process models-a state-of-the-art analysis[J].ACM Computing Surveys(CSUR),2017,50(4):1-33. [70]ZHOU C,LIU C,ZENG Q,et al.A comprehensive process similarity measure based on models and logs[J].IEEE Access,2019,7:69257-69273. [71]MENDLING J,VAN DONGEN B F,VAN DER AALST W M P.On the Degree of Behavioral Similarity between Business Process Models[C]//EPK.2007:39-58. [72]VAN DER AALST W,WEIJTERS T,MARUSTER L.Workflow mining:Discovering process models from event logs[J].IEEE Transactions on Knowledge and Data Engineering,2004,16(9):1128-1142. [73]SONG W,JACOBSEN H A.Static and dynamic process change[J].IEEE Transactions on Services Computing,2016,11(1):215-231. [74]ZHANG X,SONG W,WANG J,et al.Measuring businessprocess consistency across different abstraction levels[J].IEEE Transactions on Network and Service Management,2018,16(1):294-307. [75]WEIDLICH M,MENDLING J,WESKE M.Efficient consistency measurement based on behavioral profiles of process models[J].IEEE Transactions on Software Engineering,2010,37(3):410-429. [76]AYORA C,TORRES V,DE LA VARA J L,et al.Variability management in process families through change patterns[J].Information and Software Technology,2016,74:86-104. [77]POURMASOUMI A,BAGHERI E.Business process mining[J].Encyclopedia with Semantic Computing and Robotic Intelligence,2017,1(1):1-32. [78]KOSCHMIDER A,FELLMANN M,SCHOKNECHT A,et al.Analysis of process model reuse:Where are we now,where should we go from here?[J].Decision Support Systems,2014,66:9-19. [79]LIU H,XU D.A survey of Semantic Similarity and Relevance Computing Based on Ontology [J].Computer Science,2012,39(2):8-13. [80]GÜNTHER C W,RINDERLE S,REICHERT M,et al.Change mining in adaptive process management systems[C]//14th International Conference on Cooperative Information Systems,2006:309-326. |
|