基于树编辑距离的工作流距离度量方法

在工作流的发现和聚类等应用中，需要对两个工作流模型的距离进行度量。因此，提出一种计算两个不同结构化工作流的距离定量度量方法。首先介绍了结构化工作流，并将每一个结构化工作流转换为流程结构树；然后基于两个结构树之间的树编辑距离来计算工作流之间的距离及相应相似度。该距离度量方法满足距离度量的3个属性，即同实体不可区分性、对称性和三角不等式性质。这些属性使得该距离度量方法可以在工作流模型管理活动中作为定量分析工具。实验结果表明，基于树编辑距离的工作流度量方法是可行的。同时，与基于邻接矩阵的距离度量方法相比，该方法考虑了不同结构之间的语义距离，有效验证了此方法的合理性。

Workflow distance metric based on tree edit distance

For various applications in today’s service-oriented enterprise computing systems, such as process-oriented service discovering or clustering, it is necessary to measure the distance between two process models. In this paper, we propose a quantitative measure to calculate the distance or similarity between different structured processes. We first introduce a structured workflow model and transform each process into a process structure tree, and then calculate the process distance and its similarity based on the tree edit distance of two structure trees. The proposed distance metric satisfies three distance measure properties, i.e., identity of indiscernible, symmetry and triangle inequality. These properties make the distance metric can be used as a quantitative tool in effective process model management activities. Experiment studies show that the method is feasible. Compared to the adjacency matrix method, the proposed method is more reasonable due to the semantic distance between different structures is considered.