论文部分内容阅读
摘要：本文阐述了基于结构化流程树模型来度量两个服务流程距离的算法，该算法可以层次化的对服务流程进行比较，以便对流程进行层次化的归类和检索。
关键词：服务流程 差别 层次
一、背景
服务流程在企业中得到了大规模的应用，服务流程模型被存储在模型数据库中，另外企业业务流程的修改，服务流程也被修改或重建。服务流程数据库中的流程越来越多，完成相同任务的服务流程的版本也不断增加，面对庞大的服务流程模型库，对服务流程进行分类存储势在必行。如何对服务流程进行精确查找，如何清除重复的服务流程模型以及如何融合相似的服务流程都是服务流程领域新的挑战。面临这些新的挑战，必须具备的基本技术就是如何度量两个服务流程间的距离。在此基础上，服务流程可以按照距离的大小进行分类，有条理的存储起来，便于管理；在检索服务流程的时候，能提供一个可靠的标准，此外众多服务流程模型中基于服务流程的距离进行数据挖掘能为服务流程模型定义专家提供企业或者用户的需求变化动态，定制更加合理的服务流程。好的衡量服务流程模型的差别的算法在服务流程走向大规模应用的历程上有着深远的意义。
本文将基于结构化的流程树，提供在不同颗粒度下比较服务流程的算法。能够在不同颗粒度上计算出从一个服务流程到另一个服务流程的修改路径，计算出来的修改路径就是我们衡量两个服务流程的差别的依据。
二、结构化的流程树模型
为了使本文定义的距离是在一个层次化的高度，并具有宏观的语义操作，本章要引入结构化的流程树。
任何一个正确的流程可以唯一的被分解成一颗结构化的流程树(Process Structured Tree,简称PST)[1]。在PST中，任何两个节点不会存在相互重叠的关系，只可能有属于或者隶属于的关系，它很好的将流程模型分解成结构化的块，对于流程相同部分的查找和比较提供了很好的视角。
定义一 结构块
结构块分成四种类型：
(A)顺序块：若干个块按照一定的顺序链接而成的块，一般来说，这些块在服务流程图中是以AND_AND节点1连接起来的，通常一个单独的活动是一个最简单的顺序块。
(B)并行块：由多个需要同时执行的块组成的块。一般这些块都是从同一个-AND节点开始并且从同一个AND-节点结束的（表示可以是AND，也可以是OR）。
(C)多选块：由多个块组成，但是在执行的时候只会选择某个满足特定条件的块执行。一般这些块都是从同一个-OR节点开始并且从同一个OR-节点结束的（表示可以是AND，也可以是OR）。
(D)循环块：循环执行，直到满足某个条件的时候才终止的块。一般这个块由OR-AND节点开始并且在一个AND-OR节点处结束，在这个块中既有从第一个节点到第二个节点的有向通路，又有从第二个节点到底一个节点的有向通路。
三、相关节点
本文希望能根据不同的颗粒度计算两个服务流程的差别，故将根据PST树一层一层的发现两个流程的不同。在每一层都有一些相关的节点，也就是说从这一层的角度看，这两节点是相同的，但子节点并不是完全相同的，故从更小的颗粒度来看，这两个节点是不一样的。本章先给出如何查找两个流程模型中的相关节点。由于流程与结构树转换是唯一的，故可通过匹配结构块来匹配流程。
寻找相同节点通过递归算法，可找出服务流程模型中完全相同的部分，但有些部分在修改时做了一些改变，它们在修改前后大多数的活动还是一样的，但在上面的算法中并不能将它们匹配，有些活动在修改前属于同一个结构块，但在修改后分布到了多个结构块，也有可能将修改前几个结构块的活动合并，或选择性合并到一个结构块中，这样修改前后有关系的结构块就成一个多对多关系，对这些块做完全的删除再插入所有的节点，没有变动的节点就经历两次操作：先删除再插入，显然不能得到最短的路径，为了得到最短的路径，应该将最相似的两个结构块进行匹配，再修改它们不同的地方。在这用相似度来衡量两个结构块的相关程度。
定义二 相似度
根据上面的定义，我们容易得到相似度的两个性质：
S(P1, P2) = S(P2, P1);
S(P1, P1) = 1;
前两种情况是很容易处理的，关键是第三种情况。规定同一个父节点下两个相似度最大的节点是匹配的，首先应计算出所有结构块对的相似度，然后找出相似度最大的一对，再从队列中去除含有这两个节点的结构块对，再找出剩下的里面相似度最大的，以此类推，直到队列为空或队列中的结构块对的相似度都为零为止。P1,P2子节点并集的个数就是P1，P2子节点的个数之和减去匹配的子节点对数。对根节点实行相似度的算法，就可找出两棵树中可认为前后相同节点和其相似度了。
四、修改路径
通过流程间修改路径来描述两个流程的不同。所谓修改路径就是指一个流程是通过另一个流程修改得到的。本章将具体介绍如何根据相关节点的标记来计算修改路径。
经过上面的匹配，能得到这样的几种结果：
在P1中的块在P2中没有与之匹配的，定义删除操作Parent. Delete(block name)。
在P2中的块在P1中没有与之匹配的，定义插入操作：Parent. Insert(block type/activity name, activity before, activity after)。
在P1中的块在P2中有与之匹配并且相似度为1的，无任何操作。
在P1中的块在P2中有与之匹配但是相似度小于1的，定义修改操作：
Parent. update(child)表示需要对他的子孙节点进行操作。
除了这些还应考虑到在顺序块中，串行块的执行顺序是很重要的，对于一个顺序块的节点，还需要检查它的子节点的顺序是不是一样，需要定义移动操作，Parent. Move(to be moved block, before, after)这里假设移动操作只能在同一个父节点下进行。在Chen Li等已经找出了如何寻找最少的move动作的方法[4]，在这使用他们提出的方法来完成move操作的查找。
有时并行的功能模块可能都变成并行的，类似的修改，需要改变节点的类型，于是定义操作：Self.changetype (block type).
最后对于选择块和循环块，有时选择分支的条件需要改变，故还需要定义操作：Parent.setCondition(child name, condition),表示在parent块下到child分支的条件变为condition。
五、差别的定义和证明
定义两个流程的差别为他们修改路径中的有效操作步数。修改路径中update操作并无实际的进行，在计算距离的时不计入。由于修改路径也是一个树，且节点与服务流程的结构树有相同的层次，因此可在不同的颗粒度上对两个服务流程进行比较。当从较高层次比较时，忽略底层的改动，这样他们的差别就比较小，如果更深层次的比较，就可能得到更细微的差别。
对于两个相同的流程，无论深度是多少，他们的差别应该是0，也就是D(P, P, n)=0。通过上面的查找步骤，对于两颗相同的树来说，他们所有节点都是匹配的，而且相似度都是1，所以在查找的时候不需要对任何一个节点采取任何操作。这样得到的最短路径的操作步数是0（无论比较深度是多少），也就是说D(P, P, n)=0成立。
距离的交换性；也就是说D(P1, P2, n)=D(P2, P1, n)。插入和删除是互为你动作的，从P1到P2进行插入一个块的操作（可插入多个子块），从P2到P1就执行删除相应块的操作；而如果在P1到P2执行了move，那么在P2到P1时顺序也是不同，这时执行相反的move操作，move步数是相同的；如果在P1到P2执行改变类型或者设置条件的操作，那么在P2到P1的时就要把类型或条件改变回来，也执行相反的操作，故在从P1到P2、和P2到P1的过程中，所需要执行的操作步数是相同的，因此D(P1, P2, n)=D(P2, P1, n)成立。
D(P1, P2, n)+D(P2, P3, n) ≥ D(P1, P3, n)；在上面的算法中得到的修改操作树中，每一个动作的执行都会产生一颗新的树，这些树是在从P1到P3的过程中必须的。在不等式中，如果P2是P1到P3变换的时候产生的这些中间树种的一颗，那么D(P1, P2, n)+D(P2, P3, n)=D(P1, P3, n)，这是显而易见的。如果P2不是P1到P3的过程中产生的任何一颗中间树，那么P2必然含有这样的节点p，在变化的过程中，从P1到P2的时候需要插入这个节点，然后在P2到P3的时候需要删除这个节点，显然是大于直接从P1到P3的变化的，故上面的不等式成立。
六、应用与前景
本文提供的算法可实现服务流程管理和检索。
任意两个服务流程进行0深度的比较，是无差别的，所有的服务流程都可被归结成一类，再进行更深层次的比较，不同的服务流程将渐渐被发现，将在某一个深度比较没有区别的服务流程归为一类，这样越往深层次比较，将会发现越来越多的子树，当把数据库中的所有服务流程进行了不同层次的分类后，所有流程便构成一颗树，这颗树只有一个根节点(服务流程)，每一个非叶子节点的子节点间都因在这个深度所表现出来的不同而被分到两个类别中去，根据每一类别下流程的共同点，可为此节点进行标注，数据库中的服务流程就更加有条理得被管理起来。
基于服务流程分类，服务流程的检索将会变得更加迅速和精确，根据用户的需求，可迅速的定位到某一类流程，再把这一类流程返回给用户。在整个检索过程中仅仅只需进行一次树的查找，提高了用户体验。
在一个新的服务流程被创建并加入到分类树中的时，系统可提供被添加的服务流程通过与他相似的流程修改得到的修改路径，这样可清晰的看见用户对服务流程需求的变化，以了解市场和需求的动态。
参考文献：
[1]. Jussi Vanhatalo, Hagen Volzer and Jana Koehler. The Refined Process Structure Tree.
[2]. Jochen M. Küster, et al., et al. Detecting and Resolving Process Model Differences in the absence of a change log.
[3]. Boudewijn van Dongen, Remco Dijkman and Jan Mendling. Measuring Similarity between Business Process Models.
[4]. Chen Li, Manfred Reichert and Andreas Wombacher. On Measuring Process Model Similarity based on High-level Change Operations. 2008.
[5]. W.M.P. van der Aalst, A.K. Alves de Medeiros and A.J.M.M. Weijters. Process Equivalence: Comparing Two Process. 2008
关键词：服务流程 差别 层次
一、背景
服务流程在企业中得到了大规模的应用，服务流程模型被存储在模型数据库中，另外企业业务流程的修改，服务流程也被修改或重建。服务流程数据库中的流程越来越多，完成相同任务的服务流程的版本也不断增加，面对庞大的服务流程模型库，对服务流程进行分类存储势在必行。如何对服务流程进行精确查找，如何清除重复的服务流程模型以及如何融合相似的服务流程都是服务流程领域新的挑战。面临这些新的挑战，必须具备的基本技术就是如何度量两个服务流程间的距离。在此基础上，服务流程可以按照距离的大小进行分类，有条理的存储起来，便于管理；在检索服务流程的时候，能提供一个可靠的标准，此外众多服务流程模型中基于服务流程的距离进行数据挖掘能为服务流程模型定义专家提供企业或者用户的需求变化动态，定制更加合理的服务流程。好的衡量服务流程模型的差别的算法在服务流程走向大规模应用的历程上有着深远的意义。
本文将基于结构化的流程树，提供在不同颗粒度下比较服务流程的算法。能够在不同颗粒度上计算出从一个服务流程到另一个服务流程的修改路径，计算出来的修改路径就是我们衡量两个服务流程的差别的依据。
二、结构化的流程树模型
为了使本文定义的距离是在一个层次化的高度，并具有宏观的语义操作，本章要引入结构化的流程树。
任何一个正确的流程可以唯一的被分解成一颗结构化的流程树(Process Structured Tree,简称PST)[1]。在PST中，任何两个节点不会存在相互重叠的关系，只可能有属于或者隶属于的关系，它很好的将流程模型分解成结构化的块，对于流程相同部分的查找和比较提供了很好的视角。
定义一 结构块
结构块分成四种类型：
(A)顺序块：若干个块按照一定的顺序链接而成的块，一般来说，这些块在服务流程图中是以AND_AND节点1连接起来的，通常一个单独的活动是一个最简单的顺序块。
(B)并行块：由多个需要同时执行的块组成的块。一般这些块都是从同一个-AND节点开始并且从同一个AND-节点结束的（表示可以是AND，也可以是OR）。
(C)多选块：由多个块组成，但是在执行的时候只会选择某个满足特定条件的块执行。一般这些块都是从同一个-OR节点开始并且从同一个OR-节点结束的（表示可以是AND，也可以是OR）。
(D)循环块：循环执行，直到满足某个条件的时候才终止的块。一般这个块由OR-AND节点开始并且在一个AND-OR节点处结束，在这个块中既有从第一个节点到第二个节点的有向通路，又有从第二个节点到底一个节点的有向通路。
三、相关节点
本文希望能根据不同的颗粒度计算两个服务流程的差别，故将根据PST树一层一层的发现两个流程的不同。在每一层都有一些相关的节点，也就是说从这一层的角度看，这两节点是相同的，但子节点并不是完全相同的，故从更小的颗粒度来看，这两个节点是不一样的。本章先给出如何查找两个流程模型中的相关节点。由于流程与结构树转换是唯一的，故可通过匹配结构块来匹配流程。
寻找相同节点通过递归算法，可找出服务流程模型中完全相同的部分，但有些部分在修改时做了一些改变，它们在修改前后大多数的活动还是一样的，但在上面的算法中并不能将它们匹配，有些活动在修改前属于同一个结构块，但在修改后分布到了多个结构块，也有可能将修改前几个结构块的活动合并，或选择性合并到一个结构块中，这样修改前后有关系的结构块就成一个多对多关系，对这些块做完全的删除再插入所有的节点，没有变动的节点就经历两次操作：先删除再插入，显然不能得到最短的路径，为了得到最短的路径，应该将最相似的两个结构块进行匹配，再修改它们不同的地方。在这用相似度来衡量两个结构块的相关程度。
定义二 相似度
根据上面的定义，我们容易得到相似度的两个性质：
S(P1, P2) = S(P2, P1);
S(P1, P1) = 1;
前两种情况是很容易处理的，关键是第三种情况。规定同一个父节点下两个相似度最大的节点是匹配的，首先应计算出所有结构块对的相似度，然后找出相似度最大的一对，再从队列中去除含有这两个节点的结构块对，再找出剩下的里面相似度最大的，以此类推，直到队列为空或队列中的结构块对的相似度都为零为止。P1,P2子节点并集的个数就是P1，P2子节点的个数之和减去匹配的子节点对数。对根节点实行相似度的算法，就可找出两棵树中可认为前后相同节点和其相似度了。
四、修改路径
通过流程间修改路径来描述两个流程的不同。所谓修改路径就是指一个流程是通过另一个流程修改得到的。本章将具体介绍如何根据相关节点的标记来计算修改路径。
经过上面的匹配，能得到这样的几种结果：
在P1中的块在P2中没有与之匹配的，定义删除操作Parent. Delete(block name)。
在P2中的块在P1中没有与之匹配的，定义插入操作：Parent. Insert(block type/activity name, activity before, activity after)。
在P1中的块在P2中有与之匹配并且相似度为1的，无任何操作。
在P1中的块在P2中有与之匹配但是相似度小于1的，定义修改操作：
Parent. update(child)表示需要对他的子孙节点进行操作。
除了这些还应考虑到在顺序块中，串行块的执行顺序是很重要的，对于一个顺序块的节点，还需要检查它的子节点的顺序是不是一样，需要定义移动操作，Parent. Move(to be moved block, before, after)这里假设移动操作只能在同一个父节点下进行。在Chen Li等已经找出了如何寻找最少的move动作的方法[4]，在这使用他们提出的方法来完成move操作的查找。
有时并行的功能模块可能都变成并行的，类似的修改，需要改变节点的类型，于是定义操作：Self.changetype (block type).
最后对于选择块和循环块，有时选择分支的条件需要改变，故还需要定义操作：Parent.setCondition(child name, condition),表示在parent块下到child分支的条件变为condition。
五、差别的定义和证明
定义两个流程的差别为他们修改路径中的有效操作步数。修改路径中update操作并无实际的进行，在计算距离的时不计入。由于修改路径也是一个树，且节点与服务流程的结构树有相同的层次，因此可在不同的颗粒度上对两个服务流程进行比较。当从较高层次比较时，忽略底层的改动，这样他们的差别就比较小，如果更深层次的比较，就可能得到更细微的差别。
对于两个相同的流程，无论深度是多少，他们的差别应该是0，也就是D(P, P, n)=0。通过上面的查找步骤，对于两颗相同的树来说，他们所有节点都是匹配的，而且相似度都是1，所以在查找的时候不需要对任何一个节点采取任何操作。这样得到的最短路径的操作步数是0（无论比较深度是多少），也就是说D(P, P, n)=0成立。
距离的交换性；也就是说D(P1, P2, n)=D(P2, P1, n)。插入和删除是互为你动作的，从P1到P2进行插入一个块的操作（可插入多个子块），从P2到P1就执行删除相应块的操作；而如果在P1到P2执行了move，那么在P2到P1时顺序也是不同，这时执行相反的move操作，move步数是相同的；如果在P1到P2执行改变类型或者设置条件的操作，那么在P2到P1的时就要把类型或条件改变回来，也执行相反的操作，故在从P1到P2、和P2到P1的过程中，所需要执行的操作步数是相同的，因此D(P1, P2, n)=D(P2, P1, n)成立。
D(P1, P2, n)+D(P2, P3, n) ≥ D(P1, P3, n)；在上面的算法中得到的修改操作树中，每一个动作的执行都会产生一颗新的树，这些树是在从P1到P3的过程中必须的。在不等式中，如果P2是P1到P3变换的时候产生的这些中间树种的一颗，那么D(P1, P2, n)+D(P2, P3, n)=D(P1, P3, n)，这是显而易见的。如果P2不是P1到P3的过程中产生的任何一颗中间树，那么P2必然含有这样的节点p，在变化的过程中，从P1到P2的时候需要插入这个节点，然后在P2到P3的时候需要删除这个节点，显然是大于直接从P1到P3的变化的，故上面的不等式成立。
六、应用与前景
本文提供的算法可实现服务流程管理和检索。
任意两个服务流程进行0深度的比较，是无差别的，所有的服务流程都可被归结成一类，再进行更深层次的比较，不同的服务流程将渐渐被发现，将在某一个深度比较没有区别的服务流程归为一类，这样越往深层次比较，将会发现越来越多的子树，当把数据库中的所有服务流程进行了不同层次的分类后，所有流程便构成一颗树，这颗树只有一个根节点(服务流程)，每一个非叶子节点的子节点间都因在这个深度所表现出来的不同而被分到两个类别中去，根据每一类别下流程的共同点，可为此节点进行标注，数据库中的服务流程就更加有条理得被管理起来。
基于服务流程分类，服务流程的检索将会变得更加迅速和精确，根据用户的需求，可迅速的定位到某一类流程，再把这一类流程返回给用户。在整个检索过程中仅仅只需进行一次树的查找，提高了用户体验。
在一个新的服务流程被创建并加入到分类树中的时，系统可提供被添加的服务流程通过与他相似的流程修改得到的修改路径，这样可清晰的看见用户对服务流程需求的变化，以了解市场和需求的动态。
参考文献：
[1]. Jussi Vanhatalo, Hagen Volzer and Jana Koehler. The Refined Process Structure Tree.
[2]. Jochen M. Küster, et al., et al. Detecting and Resolving Process Model Differences in the absence of a change log.
[3]. Boudewijn van Dongen, Remco Dijkman and Jan Mendling. Measuring Similarity between Business Process Models.
[4]. Chen Li, Manfred Reichert and Andreas Wombacher. On Measuring Process Model Similarity based on High-level Change Operations. 2008.
[5]. W.M.P. van der Aalst, A.K. Alves de Medeiros and A.J.M.M. Weijters. Process Equivalence: Comparing Two Process. 2008