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

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

关键词：结构化工作流；结构树；工作流距离；树编辑距离；相似度

中图分类号： TP311

文献标志码：A

Workflow distance metric based on tree edit distance

JIA Nan1， FU Xiao-dong1，2*， HUANG Yuan1， LIU Xiao-yan1，DAI Zhi-hua1

1.Faculty of Information Engineering and Automation， Kunming University of Science and Technology， Kunming Yunnan 650500， China；

2.Yunnan Provincial Key Laboratory of Computer Application， Kunming Yunnan 650500， China

Abstract：

For various applications such as workflow discovering and clustering， it is necessary to measure the distance between two process models. In this paper， a quantitative measure was proposed to calculate the distance or similarity between different structured processes. The authors firstly introduced a structured workflow model and transformed each process into a process structure tree， and then calculated the process distance and its similarity based on the tree edit distance of two structure trees. The proposed distance metric satisfied three distance measure properties， i.e.， identity of indiscernibility， symmetry and triangle inequality. These properties enabled the distance metric to be a quantitative tool in effective process model management activities. The experimental studies show that the method is feasible. Compared to the adjacency matrix method， the proposed method is more reasonable since it takes the semantic distance between different structures into consideration.

英文关键词　Key words：

structured workflow； structure tree； workflow distance； tree edit distance； similarity

0 引言

工作流是一类能够完全或部分自动执行的业务过程，根据一系列过程规则使文档、信息或任务能够在不同的执行者之间传递、执行。该过程包括一系列的活动，涉及相互协作执行的多个任务以及各组织之间的信息流和控制流[1]。

在当今动态的业务环境下，一个企业能否取得成功，在很大程度上取决于其能否根据环境的变化作出快速、灵活、有效的反应。伴随着这一发展趋势，出现了大量的工作流模型库，库中的工作流模型随着现实需求的变动而不断地被更新，并且新的工作流模型在不断加入，因此一个能系统的分析和改进工作流的方法就变得十分重要[2]。近年来，许多学者开始关注工作流的发现和聚类[3]。在这些研究过程中，需要一个计算工作流距离或工作流相似度的有效方法以支持工作流发现和聚类的模型管理活动：比如，根据所得的相似度值，可以对相似的工作流模型及其对应的业务操作进行整合，为工作流的重构提供参考。或者跨国企业可以根据工作流距离或相似度数值识别出与公司定义的参考流程不匹配的特定流程。

近年来，已有学者对工作流距离和相似度问题进行了研究并获得了一些成果，现有的研究主要有基于工作流执行日志的距离度量、基于工作流活动间的依赖关系的距离度量以及基于工作流结构的距离度量等，这些研究要么针对已执行过的工作流，或者针对工作流的结构信息进行距离度量，没有将工作流的结构及其语义统一考虑[2-7]。为此，本文提出一种基于树编辑距离的工作流模型距离和相似度度量方法，解决了工作流距离度量中结构及其语义的统一问题，证明了该方法满足3个距离度量的属性，即同实体不可区分性、对称性和三角不等式性质。这些性质确保该方法在工作流发现和聚类等工作流管理活动中的使用是正确和可行的。

1 相关工作

文献[2]给出一种通过记录在执行日志中的可观察行为获取工作流相似度的方法，该方法利用痕迹等价概念判断两个流程模型相似或相同，因此，这种方法只能应用于流程已经被执行的场合。

基于工作流结构进行工作流相似度度量的技术还较少。文献[4]利用Petri网和自动机理论，以流程行为继承规则度量工作流相似度。但是其只能对两个模型相同与否或者一个模型是否为另一个模型的子模型给出二元的答案。文献[5]通过决定活动之间依赖关系的区别来对两个工作流之间的距离进行度量，这种方法并没有将工作流的结构信息加以考虑。一个流程模型中，除了节点和边，还包括其他一些丰富的信息（比如split和join的语义）。文献[3]给出一种基于邻接矩阵的度量方法，其并未考虑工作流的语义信息。文献[6]则利用高级变化操作（如增加、删除或移动）对工作流距离和相似度进行度量，这些操作可以将相似度度量为一个值，但该方法没有考虑到工作流控制结构的嵌套性。

本文提出的方法对工作流的结构及其语义进行了统一考虑。通过将工作流转换为一棵结构树，一方面可以通过树之间结构差异来体现工作流的结构差异；另一方面，也能通过结构树节点之间的语义差异来体现工作流活动间的语义差异。