加权Petri网的字符串序列相似性度量

doi:10.12052/gdutxb.220178

摘要/Abstract

摘要： 由于现有的流程相似性度量方法大多只关注流程的单一维度，缺乏对流程信息的综合考虑，使得流程检索的准确率还有待提高。在综合考虑结构信息和行为信息下，提出了一种高效率、多维度的加权Petri网的字符串序列的相似性度量方法。该方法首先将事件日志信息加权至Petri网，然后使用广度优先遍历将加权Petri网模型转换为字符串序列，再将该序列分为一个带权重的紧邻变迁对集和一个结构序列并分别计算相似度值，最后加权得到流程之间的相似度值。实验结果表明，该度量方法准确率达到99.51%。另外，该方法在时间复杂度上也有着不错的优势。

关键词: 广度优先遍历, 流程, 相似性, Petri网, 序列

Abstract: Due to the fact that most existing process similarity metrics focus on a single dimension of the process and lack comprehensive consideration of process information, the accuracy of process retrieval needs to be improved and the application focuses on a single scenario. In this paper, an efficient and multidimensional similarity measure of string sequences of weighted Petri nets is proposed based on the structural and behavioral information. First, the proposed method weights the event log information to Petri nets. Then, the proposed method converts the weighted Petri net model into a string sequence using breadth-first traversal, and further divides the sequence into a set of immediately adjacent variation pairs with weights and a structural sequence and calculates the similarity value separately. Finally, the similarity value between processes is obtained by weighting. The experimental results show that the metric has a high accuracy rate of metric is 99.51% with a low time complexity.

Key words: breadth-first traversal, process, similarity, Petri net, sequence

中图分类号:

TP301

胡迎城, 邢玛丽, 吴元清. 加权Petri网的字符串序列相似性度量[J]. 广东工业大学学报, 2024, 41(01): 110-118.

Hu Ying-cheng, Xing Ma-li, Wu Yuan-qing. Similarity Measure for String Sequences in Weighted Petri Net[J]. Journal of Guangdong University of Technology, 2024, 41(01): 110-118.

参考文献

[1] KOPP A M, ORLOVSKYI D L. An approach to measure similarity of business process models[D]. Kharkiv Ukraine: National Technical University, 2018: 198-199.
[2] 殷明, 闻立杰, 王建民, 等. 基于变迁紧邻关系重要性的流程相似性算法[J]. 计算机集成制造系统, 2015, 22(2): 344-358.
YIN M, WEN L J, WANG J M, et al. Process similarity algorithm based on importance of transient adjacent relationships [J]. Computer Integrated Manufacturing System, 2015, 22(2): 344-358.
[3] CAHYAPRATAMA A, SARNO R. Gap analysis of business processes using behavioral, structural, and semantic similarity calculations [C]// 2018 2nd East Indonesia Conference on Computer and Information Technology (EIConCIT) . Makassar, Indonesia: IEEE, 2018: 192-196.
[4] GUO W, ZENG Q, DUAN H, et al. Process-extraction-based text similarity measure for emergency response plans [J]. Expert Systems with Applications, 2021(1): 115301.
[5] TORKANFAR N, AZAR E R. Quantitative similarity assessment of construction projects using WBS-based metrics [J]. Advanced Engineering Informatics, 2020, 46: 101179.
[6] 李东月, 方欢. 基于活动发生关系的流程相似性度量方法[J]. 控制理论与应用, 2020, 37(9): 2011-2019.
LI D Y, FANG H. An approach of process similarity measurement based on activity occurrence relationship [J]. Control Theory and Application, 2020, 37(9): 2011-2019.
[7] 董子禾, 闻立杰, 黄浩未, 等. 基于触发序列集合的过程模型行为相似性算法[J]. 软件学报, 2015, 26(3): 449-459.
DONG Z H, WEN L J, HUANG H W, et al. Behavioral similarity algorithm for process models based on firing sequence collection [J]. Journal of Software, 2015, 26(3): 449-459.
[8] 段瑞, 方欢, 方贤文, 等. 基于变迁图编辑距离的流程相似性算法[J]. 计算机应用研究, 2020, 37(4): 1049-1053.
DUAN R, FANG H, FANG X W, et al. Process similarity algorithm based on editing distance of transition graph [J]. Computer Application Research, 2020, 37(4): 1049-1053.
[9] 吴亚锋, 谭文安. 基于邻接矩阵的业务流程间距离计算方法[J]. 计算机工程, 2018, 44(4): 52-58.
WU Y F, TAN W A. Method for calculating distance between business processes based on adjacency matrix [J]. Computer Engineering, 2018, 44(4): 52-58.
[10] 宋金凤, 闻立杰, 王建民. 基于任务发生关系的流程模型相似性度量[J]. 计算机研究与发展, 2017, 54(4): 832-843.
SONG J F, WEN L J, WANG J M. A similarity measure for process models based on task occurrence relations [J]. Computer Research and Development, 2017, 54(4): 832-843.
[11] 周长红, 曾庆田, 刘聪, 等. 基于模型结构与日志行为的流程相似度计算[J]. 计算机集成制造系统, 2018, 24(7): 1793-1805.
ZHOU C H, ZENG Q T, LIU C, et al. Business process similarity computing method based on process model structure and log behavior [J]. Computer Integrated Manufacturing Systems, 2018, 24(7): 1793-1805.
[12] LIU C, ZENG Q, CHENG L, et al. Measuring similarity for data-aware business processes [J]. IEEE Transactions on Automation Science and Engineering, 2021, 19(2): 1070-1082.
[13] ABID S, AMMAR H, MOBASHAR R, et al. An intelligent graph edit distance-based approach for finding business process similarities [J]. Computers, Materials & Continua, 2021(12): 3603-3618.
[14] 蔡启明, 张磊, 许宸豪. 基于单层神经网络的流程相似性的研究[J]. 计算机工程与应用, 2022, 58(7): 295-302.
CAI Q M, ZHANG L, XU C H. Research of process similarity based on single-layer neural network [J]. Computer Engineering and Applications, 2022, 58(7): 295-302.
[15] CHEN X SHAN M. A recommendation method for process modeling based on clustering and graph neural network[C]//2021 8th International Conference on Dependable Systems and Their Applications (DSA) . Yinchuan, China: IEEE, 2021: 195-201.
[16] TRABELSI F Z, KHTIRA A, ASRI B E. Towards an approach of recommendation in business processes using decision trees[C]//2021 International Symposium on Computer Science and Intelligent Controls (ISCSIC) . Rome, Italy: IEEE, 2021: 341-347.
[17] 吴亚锋, 谭文安. 基于Petri网关联矩阵的流程模型间距离计算方法[J]. 计算机与数字工程, 2018, 46(3): 429-436.
WU Y F, TAN W A. Method for calculating the distance between process models based on the correlation matrix of Petri net [J]. Computer and Digital Engineering, 2018, 46(3): 429-436.
[18] 崔亮. 基于机器学习的业务流程系统的预测[D]. 北京: 北京邮电大学, 2019.
[19] TAN W, XIE N, ZHAO L, et al. A new method for business process retrieval using breadth-first traversal [J]. Enterprise Information Systems, 2020, 14(1): 83-109.
[20] 曹斌, 王佳星, 安卫士, 等. ProBench: 一种评估流程相似性查询算法的基准数据集[J]. 计算机集成制造系统, 2017, 23(5): 1069-1079.
CAO B, WANG J X, AN W S, et al. ProBench: a benchmark dataset for evaluating the process similarity search methods [J]. Computer Integrated Manufacturing Systems, 2017, 23(5): 1069-1079.

相关文章 15

[1]	杨小鸽, 王华, 柏俊, 吴希文, 李廷俊, 柏玉超, 皮廷亮. 基于四叉树滤波的InSAR矿区形变监测与分析[J]. 广东工业大学学报, 2023, 40(03): 99-104.
[2]	危由兴, 罗向龙, 胡凌锋, 陈健勇, 梁颖宗, 杨智, 陈颖. 基于时间序列聚合的有机朗肯循环系统优化方法[J]. 广东工业大学学报, 2022, 39(06): 98-106.
[3]	郑博文, 杜向峰, 詹松辉, 吴希文, 王华. 中国大陆GPS连续站时间序列噪声分析[J]. 广东工业大学学报, 2022, 39(03): 70-76,82.
[4]	梁志颖, 陈健勇, 陈颖, 罗向龙, 杨智, 梁颖宗. 多流程分液板式冷凝器的变工况性能研究[J]. 广东工业大学学报, 2022, 39(01): 99-106.
[5]	滕少华, 董谱, 张巍. 融合语义结构的注意力文本摘要模型[J]. 广东工业大学学报, 2021, 38(03): 1-8.
[6]	李振福, 段伟, 李肇坤, 邓昭. 基于“21世纪海上丝绸之路”AIS数据的船舶交通流预测[J]. 广东工业大学学报, 2020, 37(06): 1-8.
[7]	陈鹤峰, 伍乃骐. 基于Petri网可达性和结构的最大许可控制器设计[J]. 广东工业大学学报, 2019, 36(04): 1-9.
[8]	张巍, 麦志深. 核模糊谱聚类LOF降噪方法研究[J]. 广东工业大学学报, 2018, 35(06): 77-82.
[9]	苏晋, 牛晓东, 袁小燕. 传播子矩阵方法推导IR-EPI序列下的磁共振信号[J]. 广东工业大学学报, 2018, 35(01): 6-8,28.
[10]	陈璟华, 邱明晋, 郭经韬, 唐俊杰. 模糊熵权法和CCPSO算法的含风电场电力系统多目标无功优化[J]. 广东工业大学学报, 2018, 35(01): 35-40.
[11]	魏威，胡正发，夏智锋，蓝秀娟. 大光圈微型高清照相物镜的设计和性能分析[J]. 广东工业大学学报, 2016, 33(06): 67-71.
[12]	苗晴, 唐颂, 凌永权. 一种关于序列二次规划和l_p罚函数的推论与证明[J]. 广东工业大学学报, 2016, 33(05): 1-4.
[13]	林非凡, 韩雅莉. 人CYP2E1基因编码蛋白主要特性与结构的生物信息学分析[J]. 广东工业大学学报, 2015, 32(1): 16-19.
[14]	郭经韬, 陈璟华, 周俊, 许伟龙. 基于组合混沌序列动态粒子群算法的电力系统无功优化[J]. 广东工业大学学报, 2014, 31(2): 85-89.
[15]	张巍, 刘峰, 滕少华. 改进的PrefixSpan算法及其在序列模式挖掘中的应用[J]. 广东工业大学学报, 2013, 30(4): 49-54.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed