欢迎访问一起赢论文辅导网
SCI期刊论文
当前位置:首页 > SCI期刊论文
一种评估流程相似性查询算法的基准数据集
来源:一起赢论文网     日期:2017-08-05     浏览数:2724     【 字体:

 计算机集成制造系统 第23卷程,并参考该流程对现有流程进行设计,则将大大加快流程再造的过程。在将一个新流程添加到流程库之前,管理人员首先需要确认流程库中是否存在与该新流程相似的流程,以避免重复。为了满足上述任务,需要检索流程库,即给定一个流程模型,在流程库中查询出与其相关的流程(称为相似流程)[2]。事实上,一个流程相似性查询算法会返回给用户包含多个相关流程的查询结果,而用户则希望查询结果中的相关流程是按相关程度排序的。基于不同的相似性衡量标准,现有的流程相似性查询算法可以被分成以下3类:①文本相似性衡量标准,主要衡量两个流程模型中任务节点标签间的相似程度[3-5];②结构相似性衡量标准,计算两个流程模型对应图结构间的相似性[6-11];③ 行为相似性衡量标准,主要衡量任务节点对应的执行序列之间的相似性[12-15]。然而,目前尚未发现针对流程相似性算法进行评估的基准数据集,即以上算法的实验结果都是在不同数据集和不 同参数设定下得到的,因此不能对其进行直接比较。总之,缺少一个统一的基准数据集会引起以下几个问题[16-17]:(1)现有的大多数流程相似性查询算法都是基于特定场景提出的。例如,算法 A 的提出是为了计算流程模型间的结构相似性,它不一定适合计算行为相似的场景。(2)不同的研究者使用他们自己的数据集(不公开)得到的实验结果与其他算法进行比较,这种做法很有可能存在问题。(3)同一个算法的实验结果会因人而异,因为不同研究团队会选择不同的数据集进行实验。为了解决 以 上 问 题,本 文 建 立 了 一 个 用 Petri网建模流程的基准数据集,来评估不同流程相似性查询算法的性能。该数据集包括100个流程模型,本文标记出了其中的10个检索流程和每个检索流程对应的9个相关流程,以及9个相关流程的排序结果。由用户调查的结果确定相关流程的排序,通过访问23个领域专家来对每一组相关流程进行排序,将最终的排序结果作为基准排序结果,用来评估算法的准确性。1 数据集本文的数据集由100个 Petri网建模的流程模型组成,将其分成10组,每组流程包括1个检索流程及其对应的9个相关流程,其中的9个相关流程按与该检索流程的相关程度由高到低排序,排序结果根据用户调查得到。数据集中的流程来源于现有的一个真实数据集———IBM 数据集[18],其包括 5 个流 程 库 共3 000多个流程模型。这些流程模型被完全匿名化处理,即流程模型的名字和流程中的节点名称是未知的。IBM 数据集不能直接使用,因为数据集中没有标记出哪些流程是检索流程、哪些流程是检索流程对应的相关流程。基于IBM 数据集,按照以下4个步骤建立基准数据集:①选择检索流程。从IBM 数据集中选出10个检索流程模型,主要考虑顺序、选择、并行和循环4种流程控制流结构。②创建混淆流程。混淆流程的引入是为了迷惑算法,使其将不相关的流程模型作为其相关流程,从而将优秀的算法区分出来(优秀的算法不会将不相关的流程作为其相关流程)。③改造相关流程。人为地给每个检索流程改造了其对应的9个相关流程,包括检索流程本身,每个检索流程包括10个相关流程。④对相关流程进行排序。通过10个用户调查对每组流程内的相关流程进行排序。1.1 选择检索流程从IBM 数据集中选择10个检索流程时,主要考虑流程的复杂度和控制流结构。10 个检索流程的细节如表1所示,从中可以看出每个检索流程的流程编号为1~10(表中第1行),以及每个检索流程的库所数、变迁数、边数及包含的结构。在结构中,S(Sequence)表示顺序结构,E(Exclusive)表示选择结构,P(Parallel)表示并行结构,L(Loop)表示循环结构,EP和 EPL表示复合结构,分别是 E 和 P的复合以及 E,P和 L结构的复合,如图1所示。由表1可知,每两个检索流程(如流程1和流程2)包含相同的结构。7010 曹 斌 等:ProBench:一种评估流程相似性查询算法的基准数据集表1 10个检索流程的细节流程 1  2  3  4  5  6  7  8  9  10库所 14  112  42  42  73  39  101  91  46  48变迁 10  10  46  48  45  32  99  84  36  36边 26  222  92  96  144  76  220 198  96  100结构 S  S  E  E  P  P  EP  EP EPL EPL在每个检索流程的基础上添加或删除边/节点,从而在原有的检索流程上添加或删除控制流结构。例如,表1中的1号检索流程只包含顺序结构,但通过对1号检索流程添加或删除边/节点,可以得到包含选择、并行、循环结构或各个结构的不同组合的相关流程。因此,数据集中的流程基本涵盖了所有可能出现的控制流结构。1.2 创建混淆流程若每组流程(1个检索流程及其9个相关流程)包含的节点标签都不同,则任意的流程相似性查询算法都能为检索流程找到其相关流程,即所有算法的准确率都为100%。为了避免这类情况发生,对包含相同结构的两组流程模型中的节点标签进行修改,使这两组流程模型中的部分节点标签相同。事实上,一旦将一个检索流程 S1改造成另一个检索流程 S2的混淆流程,则S2对应的相关流程也为S1所在组流程的混淆流程,这是因为S2的相关流程是在S2的基础上修改的,包含大部分与 S2相同的节点标签。这种做法可以使两组中的一组流程模型成为另一组流程模型的混淆流程,这是因为在查询一组流程中检索流程的相关流程时,有可能查询到另一组流程中的流程模型,以此区分好的算法和差的算法。在本文实现的待评估算法中,两个库所节点间的相似度是用它们的上下文环境(流入、流出库所的变迁)来 衡 量 的[11],因 此 仅 考 虑 任 务 节 点 的 标 签。如图2所示,图2a和图2b是两个检索流程,它们包含相同的选择结构。图2a和图2b共享了部分节点标签 A 和B,如虚线框中所示,其他节点的标签都不同。因为图2b的相关流程也都包含虚线框中的节点,所以图2b及其相关流程都是图2a所在流程组的混淆流程。1.3 改造相关流程给定一个流程模型,下面介绍改造相关流程的不同策略,主要从结构和行为两个方面来考虑。为了得到一个给定流程模型的相关流程,采用以下 4个策略:①添加子结构或子行为,即将额外的节点、边或执行序列加到给定的流程模型上,使改造后的相关流程模型包含原流程模型的结构或行为;②删除子结构或子行为,即删除给定流程中的部分结构或部分执行序列,使原流程包含改造后流程的结构或行为;③重命名任务节点标签或者打乱任务节点顺序;④组合上述2种以上策略。1.3.1 添加子结构或子行为一个流程模型 S是另一个流程模型 M 的父流程,因此S除了包含 M 的结构或者行为外还包含额外的节点、边或者执行序列。给定一个流程模型,采用以下几种策略得到其父流程:(1)添加额外的顺序节点将一系列顺序节点添加到头部、中间、尾部3个位置。如图3(1)所示,a是检索流程,将一系列顺序节点(库所 P4和变迁C)分别加在a的头部、中间和尾部,可以得到b~d。这种改造没有影响原流程模型的整体结构,但是改变了其执行序列。7011计算机集成制造系统 第23卷(2)添加选择分支将额外的选择分支添加到给定流程模型上,从行为上考虑,改造后的流程模型会在执行序列上多一个选择。如图3(2)所示,a是一个检索流程,包括2个选择分支。将一条额外的选择分支 P2→F→P6→G→P5 加在a后,得到 b。b与a相比,整体结构发生了变化,但是行为有可能相同。例如:若a和 b都执行 A,B,D 或者A,C,E,则它们的执行序列就是相同的。(3)添加并行分支并行分支的添加会使改造后的流程和原流程的结构与行为都发生变化。如图3(3)所示,b在a上添加了一个并行分支 A→P7→E→P8→D。(4)添加循环分支添加了循环分支后,流程模型在结构上是原流程模型的父流程模型,两 者的 行 为也有可能相同。如图3(4)所示,a添加了一个循环分支 P3→D→P5→E→P1 后变成了 b,该循环分支是从 P3开始、P1结束。若b不执行它的循环分支,则 b与a的行为就是相同的。1.3.2 删除子结构或子行为若一个流程模型 M 与另一个流程模型S相比,除了包含S的结构或行为外还包含额外的节点、边或者执行序列,则S是 M 的子模型。给定一个流程模型,有以下3种策略可以改造成其子模型:①删除选择分支、并行分支、循环分支中的一种分支;②删除一个子执行序列;③删除选择片段、并行片段、循环片段中的一个片段。(1)删除分支给定一个流程模型,删除一个选择、并行或循环分支后可以得到改造后的流程模型。分支是指控制流结构(选择、并行、循环结构)中一系列顺序节点组成的一条支路。如图4(1)所示,a是一个检索流程,b~d分别为在a的基础上删除一个选择分支 P1→E→P7→H→P8→G→P4、一个并行分支 A→P5→F→P6→C 和一个循环分支P3→D→P2 后的结果。(2)删除子执行序列给定一个流程模型,它有多个执行序列,删除其中的部分执行序列,得到其基于行为的子流程模型。如图4(2)所示,a可以是一个检索流程,其包含的子序列集合为{A→B→C→D,A→C→B→D},删除其中的 一 条 子 执 行 序 列 A→C→B→D 后,可 以 得到b。(3)删除片段一个片段是指整个控制流程结构,包括从控制流结构的入口节点到出口节点间的所有节点和边。如图4(3)所示,b删除了a中的一个顺序片段 P1→A→P5→F。在图4(4)中,a删除了一个选择片段,该片段包括节点{P2,P3,P4,P5,B,C,D,E}及这些节点间的边,得到b,但是为了保持流程模型的连通性,保留了库所节点 P2,使其与变迁 A 连接起来。相似地,图4(5)和图4(6)分别是a删除了一个并行片段和一个循环片段之后的结果。1.3.3 重命名任务节点标签或者打乱任务节点顺序对流程模型中的任务节点进行以下两种操作,可以将一个给定流程改造成其相关流程:①重命名任务节点标签,即将任务节点的原有标签替换成新的标签,且新的标 签在该流 程 模型中没 有 出现过。②打乱任务节点顺序,即对任务节点的顺序进行重新排序,使其与原有的顺序不同。如图5所示,a是一个检索流程,b,c和a具有相同的结构,b将a中任务节点 A,B,C,D 的标签分别重命名为E,F,G,H;a中的任务节点顺序为 A→B→C→D,c将其顺序打乱为 D→C→A→B。1.3.4 组合结合以上2种或2种以上策略,也可以将一个给定的流程模型改造成其相关流程。如图6所示,通过使用以下2种策略可将a变成 b:①重命名任务节点标签,将任务节点 A,B 的标签重命名为G,H;②添加循环分支 P4→E→P6→F→P2。1.4 对相关流程进行排序为了获得每个检索流程对应相关流程的排序结果,设计了10个用户调查[19]。图 7 所示为第 1 个用户调查的例子,图中列出了检索流程1及其对应的9个相关流程(编号为2~10)。通过采访23位领域专家完成这10个用户调查,让他们对每组流程模型中的相关流程进行排序。23位受访者包括在读硕士研究生和博士研究生,专业涉及数据挖掘、图像处理、工作流管理、服务计算等领域。每个受访者根据自己的专业知识对每个检索流程的相关流程按与其相似性从大到小排序并将排序结果写在用户调查表的“排序”这一行(如图7最后一行),例如对于检索流程1,{2,3,6,4,10,5,7,9,8}可能是某个受访者得到的一种排序结果。整合23位领域专家的结果,得到该组中的检索流程对应相关流程的一个基准排序结果。70126-08-25;修订日期:2016-09-10。Received 25Aug.2016;accepted 10Sep.2016.基金项目:国家自然科学基金资助项目(61602411,61272308);浙江省自然科学基金资助项目(LY15F020030);浙江省重大科技专项重点工业资助项目(2015C01034,2015C01029);杭州市重大科技创新资助项目(20152011A03)。Foundation items:Project supported by theNational Natural Science Foundation,China(No.61602411,61272308),the Natural Science Foundation of Zhejiang Province,China(No.LY15F020030),the Key Research and Development Project of Zhejiang Province,China(No.2015C01034,2015C01029),andthe Major Science and Technology Innovation Project of Hangzhou City,China(No.20152011A03).ProBench:一种评估流程相似性查询算法的基准数据集曹 斌,王佳星,安卫士,范 菁+,程时伟(浙江工业大学 计算机科学与技术学院,浙江 杭州 310023)摘 要:针对目前缺乏评估现有流程相似性算法性能的基准数据集问题,在IBM 公开的数据集基础上,用 Pe-tri网建模流程模型,提出一种评估流程相似性查询算法的基准数据集。该数据集由100个流程模型组成,其中标记出了10个检索流程与其各自的9个相关流程,以及相关流程的排序顺序。对于每个检索流程,其9个相关流程与该检索流程的相关性排序顺序由一个用户调查的结果确定,将该结果作为一个基准对算法的结果进行评估。选取3个基于结构的和1个基于行为的流程相似性查询算法,对它们在准确率和效率两个方面进行了评估,实验结果展示了这些算法各自的适用场景。所提出的基准数据集和相关的算法代码已经公开发布在网上,可供研究人员下载使用。关键词:基准数据集;业务流程;相似性;Petri网中图分类号:TP311   文献标识码:AProBench:a benchmark dataset for evaluating the process similarity search methodsCAO Bin,WANG Jiaxing,AN Weishi,FAN Jing+,CHENG Shiwei(Computer Science and Technology College,Zhejiang University of Technology,Hangzhou 310023,China)Abstract:A Benchmark dataset is presented to evaluate the performance of different process similarity search meth-ods.This dataset is built based on the existing public IBM dataset,where the search models,their correspondingrelevant models and the order of these relevant models are manually labeled by using the business domain knowl-edge.The relevant models are manually synthetized by adding,deleting,or combining the relevant nodes and frag-ments.Based on this dataset,the precision and efficiency of some process similarity search similarity methods interms of structure and behavior are evaluated.The dataset and corresponding similarity search algorithm codes areavailable to the public on a website1.Keywords:benchmark dataset;business process;similarity;Petri-net0 引言近几 年,随 着 业 务 流 程 管 理 (Business ProcessManagement,BPM)技术的快速发展,大量业务流程模型应运而生。例如,中国海尔集团拥有3 000多个流程模型,其中大多数流程模型都涉及家用电器的开发[1]。这些流程模型都是公司宝贵的资产,需要有效地管理起来,由此产生了不同的流程管理技术。业务流程再造(Business Process Re-engineering,BPR)便是其中的一种流程管理技术,该技术旨在对现有的流程模型进行重新设计。在该过程中,若设计人员能够在流程库中找到一个与该待重新设计流程相似的流 曹 斌 等:ProBench:一种评估流程相似性查询算法的基准数据集不同的受 访 者 有 不 同 的 排 序 结 果,先 对 排 序结果进行 简 单 的 人 工 复 审,即 检 查 受 访 者 给 出 的排序顺序 是 否 包 含 了 所 有 的 待 排 序 流 程 编 号、是否出现了 重 复 的 流 程 编 号、是 否 遗 漏 了 某 个 流 程的编号。若出现以上错误,则该排序顺序作废,再使用下 面 的 策 略 整 合 同 一 个 用 户 调 查 的 不 同 结果。如表2所示,首先将排在第1名的流程模型赋权 重 0.9,第 2 名 赋 权 重 0.8,…,第 9 名 赋 权 重0.1;然后对 于 每 一 个 编 号 对 应 的 流 程 模 型,将 所有受访者 对 其 排 序 得 到 的 权 重 进 行 相 加,得 到 一个总权重。以表2中的例子进行说明,表中数据来自3个7013计算机集成制造系统 第23卷受访者对同一个检索流程的相关流程进行排序的结果。2号 流 程 得 到 的 总 权 重 为 0.9+0.8+0.9=2.6,3号流程的总权重为0.8+0.9+0.6=2.3。同样地,剩余7个相关流程的总权重如下:4号2.0、5号1.1、6 号 1.2、7 号 1.7、8 号 0.7、9 号 1、10 号0.9。因此该检索流程的相关流程最后的排序结果为{2,3,4,7,6,5,9,10,8}。表2 排序例子位置 1  2  3  4  5  6  7  8  9权重 0.9  0.8  0.7  0.6  0.5  0.4  0.3  0.2  0.1受访者1  2  3  5  4  10  9  7  6  8受访者2  3  2  4  7  6  8  5  9  10受访者3  2  7  4  3  6  9  10  8  5事实上,不同的受访者会根据自己的专业知识对相关流程与检索流程之间的相似程度作出不同的判断。因此,为了使本文的数据集更适合工作流领域,可以请一些工作流领域的专家接受用户调查,因为他们更了解流程图,其排序结果会更具代表性,从而使数据集更有效、更加令人信服。2 算法已有的计算结构和行为相似度的4个流程相似性查询算法主要有:①基于贪心算法的结构相似性查询算法(Greedy)[7]。②基于 A 星的结构相似性查询算法(A* )[7]。③基于匈牙利算法的结构相似性查询算法(Hungarian)[11]。④基于变迁紧邻关系(Transition Adjacency Relation,TAR)的行为相似性查询算法[13]。现有大多流程相似性研究都关注结构相似性,少部分关注行为相似性,因此本文选择3个结构相似 性 算 法 和 1 个 行 为 相 似 性 算 法 进 行描述。2.1 结构相似性查询算法2.1.1 基于贪心(Greedy)算法实现Greedy算 法 在 计 算 两 个 流 程 模 型 的 相 似 度时,会在每 一 轮 迭 代 地 寻 找 当 前 最 佳 映 射 的 节 点对,即原来的结构加上当前选出的节点对后,其图编辑距离(Graph Edit Distance,GED)[20]最小。给定两个用 Petri网建模的 流 程模型,Greedy算法首先将所有可能映射的节点对组合都加到一 个集合openpairs中,需要注意的是,只有相同类 型的节点之间才能进行映射,即库所只能与库所映 射,变迁只能与变迁映射。于是一个空的映射集合 M 建立起来,用以 存 储 最 终 映 射 起 来 的 节 点 对。 在 每 一轮迭代过程 中,算 法 会 在 openpairs中 挑 选 出 一 个映射的节 点 对,该 节 点 对 能 最 大 程 度 地 增 加 两 个流程 模 型 的 相 似 度。 接 着,映 射 的 节 点 对 会 从openpairs中删 除。算 法 如 此 不 断 迭 代 地 构 建 M,直到没 有 节 点 对 可 以 再 增 加 两 个 流 程 模 型 的 相似度。Greedy算法的时间复杂度为 O(n3)、空间复杂度为O(n2),其中n 表示两个流程模型中包含的最大节点数目。Greedy算法属于一种启发式算法,其得到的解是局部最优解,并不是真正的全局最优解。2.1.2 基于 A*算法实现A*算法的目标是构建一个使两个流程模型相似度最高的节点映射集合,用 GED 的思想 来说就是每一轮都寻找使两个流程模型 GED 最小的一对映射节点。在每一轮中,A* 将在原来映射节点对的基础上构建一个更大的节点映射集合,在未映射的节点对集合中选择当前能最大程度增加两个流程模型相似度的节点对,然后开始下一轮新的计算。算法迭代地构建部分最佳映射节点对,直至不能找到一个更大的映射节点对集合来增 加两个流程的相似度。A*算法至少需要执行 O(n2 m)步,最差的情况是O(nm),其中 m 和n 分别表示两个流程模型中的节点数目。有研究已经证明 A* 算法能找出全局最优的节点映射集合[7,21]。2.1.3 基于匈牙利(Hungarian)算法实现Greedy和 A*算法耗时多,这是由于它们在每一轮寻 找 映 射 节 点 对 时 都 需 要 多 次 计 算 GED。Hungarian算法在计算两个流程模型的相似度时只需计算一次 GED,从而节省了大量的时间。Hungarian算法与 Greedy和 A*算法不同,它7014 曹 斌 等:ProBench:一种评估流程相似性查询算法的基准数据集不是一边计算 GED 一边寻 找映 射的节点对,而 是在找完映射的节点对后计算一次 GED。首先,算法创建一个节点相似度矩阵,该矩阵记录了两个流程模型中所有可能映射的节点对之间的节点相似度。在该矩阵中,用 Hungarian算法[22]找出使总的节点相似度(即所有映射节点对的节点相似度的总和)最高的映射节点对集合。最后基于该节点映射集合得到两个流程间的相似度。2.2 行为相似性查询算法一个流程模型的行为指其任务节点的执行顺序组成的执行序列,包括哪些任务节点已被执行以及以怎样的顺序被执行[1]。当前计算流程间行为相似度的算法很多,本文选择基于 TAR 的行为相似性查询算法。TAR 指两个相邻变迁的触发顺序,即哪一个变迁先被触发,哪一个被后触发。之所以采用TAR,是因为用 TAR 计算流程模型间行为相似度时的限制更小,若用全序列来计算相似度则过于严格[13],只有全序列完全相同的两个流程的行为才是一致的。由此,两个流程模型的行为相似度是基于对应的两个 TAR 集合的相似程度来衡量。在得到一个流程模型的变迁紧邻关系集合时,用前缀展开的方法可以避免状态爆炸的问题,比用可达图的方法更好[23]。分别得到两个流程模型的TAR 集合后,其相似度可以通过其 TAR 集合的交集和并集的比率得到[12]。3 实验评估下面从以下几方面对本文所提数据集的有效性或可用性进行评估:①数据集中选取和改造流程的正确性。用 Petri网 对工作流进行建模,并保证其建模的正确性,使结构和行为相似性算法都能对每个 Petri网 建 模 的 流 程 进 行 解 析。② 使 用 者 的 反馈。使用者使用本文所提基准数据集进行实验后会有一个反馈,根据反馈可知该数据集是否有效、是否可行,并通过反馈及时对数据集进行改进,使数据集更有效、更具有可用性。本节从准确率和效率两个方面使用本文提出的基准数据集考察第 2 章流程相似性查询算法的性能。准确率的评估主要是将数据集中标记出来的相关流程及其排序顺序与算法查询出来的结果进行比较,算法的效率通过评估一个流程查询一个流程库的时间来确定。所有实验都在以下配置机器上进行:Intel(R)Xeon(R)CPU E5-2637,3.50GHz处理器,8GB RAM,JDK7,Windows 7。3.1 准确率评估3.1.1 衡量标准现有的一些 评 估 准 确 率 的 衡 量 标 准,如 P@n和 MAP都没有对相关流程的位置进行评估,因此不能准确 描 述 流 程 相 似 性 查 询 算 法 的 准 确 率,它们不能反 映 出 这 种 信 息,即 排 在 前 面 的 相 关 流 程比排在后 面 的 相 关 流 程 重 要[24]。因 此,本 文 对 算法准确率 的 评 估 使 用 归 一 化 折 损 累 积 增 益 (Nor-malized Discount Cumulative Gain,NDCG)[25],ND-CG 按式 (1)给 相 关 流 程 的 排 序 结 果 计 算 出 一 个得分:N(n)=r(n), n=1;r(1)+∑Nn=2r(n)log2n, n>1烅烄烆;(1)precision =N(n)I(n)×|前n个流程中相关流程|n。 (2)式中:N(n)表示某个给定流程模型和其n 个相关流程的 NDCG 值;r(n)是排在第n 个位置的相关流程的权重,由用户自定义决定;I(n)表示某个给定流程模型和与其n 个相关流程的归一化 折 损累积增益(Ideal Discount Cumulative Gain,IDCG)值。在查询一个检索流程模型的相关流程时,不同的流程相似性查询算法查询到的相关流程可能不同,即使查询到的相关流程相同,其排序顺序也有可能不同,为了比较不同算法的准确率,通过用户调查获得一个检索流程模型相关流程的基准排序,即标准的ID-CG,该基准排序结果通过式(1)计算得到。然后,计算不同算法为一个检索流程查询其前n个相关流程对应的 NDCG 值,用式(2)将 NDCG 与IDCG 进行比较得到算法的准确率。在实验中考察查询10个检索流程的相关流程及其排序的平均准确率,即平均归一化折损累 积 增益(Average Normalized Dis-count Cumulative Gain,ANDCG)。3.1.2 结果对于数据集中标记出来的10个检索流程,通过计算查询每个检索流程对应的相关流程及其排序顺序的 NDCG,比较 Greedy,A*,TAR 和 Hungarian4个算法的查询准确率。如图8所示,每个检索流程都采用4个算法进行查询。表3所示为每个算法查询10个检索流程的 ANDCG,即对图8的平均结7015计算机集成制造系统 第23卷果。从表中可以看出,所有算法查询1号和2号检索流程的准确率都很高,这是由于这两个检索流程包含的是最简单的顺序结构,所有算法都能处理得很好。对于包含比较复杂结构的检索流程,如4,6,7,8,9号检索流程,TAR 算法的准确率最高,Hun-garian和 Greedy算法展现了相似的准确率,A*的准确率最低。随着控制流结构变得复杂,TAR 算法在准确率方面比其他3种算法表现得更优秀,其中的一个原因是,在受访者进行相关流程排序时,相比于流程结构,他们更看重流程行为。表3 ANDCG算法 ANDCG/%Greedy  90.46A*84.35TAR  92.34Hungarian  90.653.2 效率评估下面比较 Greedy,A*,TAR 和 Hungarian 4个算法的查询时间。一方面,考察各算法计算两个流程(单个流程和单个流程)的相似度执行时间;另一方面,考察不同算法为一个检索流程查询一个流程库(单个流程与多个流程)的查询时间。3.2.1 单个流程与单个流程对于包含复杂并行结构的流程模型,TAR 不能很快对其进行相似度计算,由此设计一个实验来考察并行结构中所包含的任务节点数对 TAR 算法执行时间的影响。给定一个基准流程模型,它包含 3个并行分支,每个并行分支中有5个任务节点。与该基准流程模型进行相似度计算的5个待比较流程模型分别包含2,3,4,5,6个分支,如图9a横坐标所示。由实验结果可知,当待比较流程模型包含的并行分支数较少时(2或者3),流程模型中对应的执行序列长度也较短,因此 TAR 算法能快速地对其进行处理。当待比较流程的分支数大于3时,TAR 处理这些流程的时间呈指数增长,因为分支数增多后任务节点之间的执行顺序排列方式也呈指数增多。图9b~图9d是固定基准流程,分别改变另一个流程的库所数、变迁数、边数3个因素后,查看计算两个流程相似度的执行时间。图9b中使用的基准流程包括 53 个库所节点、55 个变迁节点和 200条边;图9c和图9d使用的是同一个基准流程,包括97个库所节点、55个变迁节点和200条边。从图中可以看到,库所数和边数的变化对算法执行时间的影响不大,即随着库所数和边数的增大,两个流程间的相似度计算时间没有明显变化。然而随着变迁数的增大,Greedy算法的执行时间有明显的增加,A*算法有轻微的增加趋势,如图9c所示。总之,在计算单个 流 程 模 型 与 单 个 流 程 模 型 间 的 相 似 度 时,Greedy算法耗时最多,其次是 A*,Hungarian算法的效率最高。Greedy和 A*算法耗时高的原因是计算两个流程相似度时,寻找两个流程模型间的映射节点对中会涉及大量的 GED 计算。在每一轮迭代中,Greed-y算法会选择能够最大程度增加当前两个流程模型相似度的一对映射节点对,由此每一对未映射的节点对都会被计算一次 GED,因此 Greedy算法的效7016第5期 曹 斌 等:ProBench:一种评估流程相似性查询算法的基准数据集率会比 A* 低。Hungarian只计算一次 GED,且寻找映射节点对的时间很快,因此耗时非常少。在本节单个流程与单个流程比较的实验数据中,流程模型中的并行结构包含的任务节点数很少,因此 TAR能很快对其进行相似度计算。任务节点数对算法的执行时间有显著的影响,这是因为在算法实现过程中,计算两个用 Petri网流程 建模的流程模型间的相似度时,库所节点间的相似度由其上下文环境(流入、流出该 库 所 的 变 迁)[11]决 定,当 任 务 节 点 数 少时,映射的库所节点对数目随之变少,因此 Greedy和 A* 算法的执行时间也比较短。3.2.2 单个流程与多个流程选择100个流程模型创建一个新的流程库,流程库中包含的流程模型详情如表4所示。图10a所示为固定检索流程模型(库所数为97,变迁数为55,边数为200),查看改变流程库中流程的数量(如横坐标)对算法执行时间的影响。从图中可以观察到,随着流程库中流程模型数的增加,每个算法的查询总时间都明显增加,其中 Greedy算法耗时最多,其次是 A* ,TAR 和 Hungarian算法。Greedy算法的耗时比 Hungarian算法多了两个数量级,这是由于多次计算 GED 的结果。表4 新流程库的流程详情元素数 最小值 最大值 平均值库所数 7  90  55.05变迁数 5  96  50.30边数 12  192  115.10图10b~图10d的实验结果分别展示了固定流程库大小为100时,改变检索流程的库所数、变迁数和边数对算法执行时间的影响。可以看出,库所数和边数变化对时间的影响不明显。需要注意的是,在图10c中,当变迁数少于37时,Greedy算法耗时比 A* 少;当 变 迁 数 多 于 37 时,Greedy 算 法 慢 于A*算法。这是由于当检索流程中包含的变迁数量较少时,映射的变迁比率会随之变少,导致映射的库所对数减少,从而使总的节点映射对数变少,Greed-y算法可以快速遍历所有可能映射的节点对,并从中找出当前最佳的节点映射对。然而随着变迁数的增 加,潜 在 的 变 迁 映 射 对 数 随 之 增 加,从 而 使Greedy算法花费大量时间来遍历它们。最后,对4种算法进行对比,考虑在何种情况下使用哪种算法比较合适。Greedy,A*,TAR,Hun-garian 4种算法在算法性质(算法计算的是两个流程间的结构相似度还是行为相似度)、流程库大小、流程库中流程是否复杂和并行任务多等情况下的适用情况如表 5 所示。其中 Greedy,A*,Hungarian算法均为结构相似性查询算法,TAR 算法则是行为相似性查询算法。从表中可知,Hungarian算法对流程库大小、流程库的复杂度不敏感,适用于任何情况;TAR 只在并行任务多的情况下不适合,在并行任务少的情况下能较快地提取出一个流程模型中的变迁紧邻关系,并进行行为相似度计算。当流程库比较小但流程结构复杂时,Greedy和 A*是不适合的;当流 程 库小但流 程简单时,4 种算法均 适 合 使用;当流程库大且简单时,Greedy和 A*可以考虑使用;当流程库大且复杂时,这两种算法都不适用。表5 算法的对比结果算法结构算法行为算法流程库小流程库大流程库简单流程库复杂并行任务多Greedy √ × 乄 乄 乄 乄 乄A*√ × 乄 乄 乄 乄 乄TAR × √ 乄 乄 乄 乄 ×Hungarian √ × √ √ √ √ √注:√为适合,×为不合适,乄为有些情况适合。4 结束语本文提出一个基准数据集,在该数据集中标记7017

[返回]
上一篇:安全与成本感知的实例密集型云工作流调度方法
下一篇:O2O服务推荐策略的计算实验比较