（管理科学与工程专业论文）面向过程挖掘的一致性分析方法研究.pdf

国防科学技术人学研究生院硕十学位论文 摘要 当今社会越来越多的企业使用过程管理系统为其商务处理过程提供支持。过 程挖掘技术就是以过程管理系统为基础的数据挖掘技术，又称工作流挖掘，是工 作流再设计与分析方法的项关键技术，该技术根据同志记录文件中记录的过程 实例的执行信息，能够重构出一个工作流过程模型，能够计算日志中记录与过程 模型的匹配程度，以及能够对模型进行扩展或再造，使之更加符合现实生产过程。 一致性分析，旨在检测某过程模型和与该模型有关的日志记录文件之间的一 致性问题，以及定量的测量方法。一致性分析的过程是：存在预先定义的过程模 型，基于执行日志可以检验实际环境中运行的工作过程是否遵循该模型，同时可 以检验它们之间的偏差以及权衡其严重性。 本文从两个角度来检测目标模型和日志记录文件之间的一致性。首先，度量 了模型和日志之间的适合性维度，适合性维度描述日志记录文件与模型的匹配度， 即日志记录文件中所记录到的过程轨迹是否在过程模型中可以顺利执行。然后， 分析了模型的适当性维度，适当性维度又分为行为适当性维度与结构适当性维度， 行为适当性维度是用来评价过程模型中所有的可能通路在日志记录文件中的利用 率，结构适当性维度描述了模型结构的合理程度。文章最后使用了开源p r o m f r a m e w o r k 框架中自主开发的一致性分析插件来计算适合性维度与适当性维度，最 后综合两种维度，提出了过程模型与日志记录文件的一致性指标，并用一致性分 析插件进行算法时间复杂度分析。 本文提出的综合两种维度的一致性指标，完善过程挖掘技术中一致性分析方 面的研究，对构筑完整的过程挖掘理论体系有积极作用，同时为过程挖掘技术中 的流程扩展与再造技术提供理论依据。通过一致性分析技术，可以定量计算出实 际生产中的活动与过程模型的匹配情况，可以分析出模型结构的优劣，为标准化 建模提供理论支持，通过检验过程管理系统的过程模型与企业实际生产过程中流 程的匹配情况，从而改进过程模型以提高过程模型的效率，使得过程模型能够更 好地为生产服务。 主题词：一致性分析过程挖掘适合性维度适当性维度 第i 页 国防科学技术人学研究生院硕十学位论文 a b s t r a c t m a n yc o m p a n i e sh a v ea d o p t e dp r o c e s s a w a r e i n f o r m a t i o ns y s t e m s ( p 越s ) t o s u p p o r tt h e i r b u s i n e s s p r o c e s s e st o s o m ee x t e n t p r o c e s sm i n i n g 。a l s on a m e da s w o r k f l o wm i n i n g i sak e yt e c h n ol o g yb a s e do np st or e c o n s t r u c tt h ew o r k f l o w m o d e lf i o mt h er u n n i n gl o g so f t h ea l lt h ep r o c e s si n s t a n c e s w ec a nu s et h i st e c h n o l o g y t or e c o n s t r u c taw o r k f l o wp r o c e s sm o d e la n dt od oc o n f o r m a n c ec h e c k i n ga n da l s ot o e x t e n da n dr e f o r g et h ep r o c e s sm o d e l c o n f o r m a n c ec h e c k i n g ，a i m sa tt h ed e t e c t i o no fi n c o n s i s t e n c i e sb e t w e e nap r o c e s s m o d e la n di t sc o r r e s p o n d i n ge x e c u t i o nl o g ，a n dt h e i rq u a n t i f i c a t i o nb yt h ef o r m a t i o no f m e t r i c s t h ep r o c e s so ft h ec o n f o r m a n c ec h e c k i n gi st h a tw ec a nc h e c kw h e t h e rt h e p r o c e s si nt h er e a lc o n d i t i o ni sc o n f o r m t h ep r e - d e f i n e dp r o c e s sm o d e lb a s e do nr u n n i n g e v e n tl o g s ，a n da l s ow ec a l lc h e c kt h ed e v i a t i o na n dt h ec o n s e q u e n c eb e t w e e nt h e m t h i sp a p e rp r o p o s e sa ni n c r e m e n t a la p p r o a c hf r o mt w oa n g l e st oc h e c kt h e c o n f o r m a n c eo fp r o c e s sm o d e l sa n dt h e i rc o r r e s p o n d i n ge v e n tl o g s f i r s to fa l l ，t h e f i t n e s sb e t w e e nt h el o ga n dt h em o d e li sm e a s u r e d ( i e ，t h ee x t e n tt ow h i c ht h el o g t r a c e sc a nb ea s s o c i a t e dw i t hv a l i de x e c u t i o np a t h ss p e c i f i e db yt h ep r o c e s sm o d e l ) s e c o n d ，t h ea p p r o p r i a t e n e s so ft h em o d e l si sa n a l y z e dw i t hr e s p e c t t ot h e l o g a p p r o p r i a t e n e s sc a l lh ee v a l u a t e df r o mb c i t has t r u c t u r a l ( i e ，e v a l u a t e sh o w m u c h b e h a v i o ri sa l l o w e db yt h em o d e l w h i c hw a sa c t u a l l yn e v e ru s e di nt h eo b s e r v e dp r o c e s s e x e c u t i o n si nt h el o g ) a n dab e h a v i o r a l ( i e ，d e s c r i b e st h er e a s o n a b l ed e g r e eo ft h e m o d e ls t r u c t u r e ) p e r s p e c t i v e t oa c c o u n tt h ef i t n e s sm e t r i ca n dt h ea p p r o p r i a t e n e s s m e t r i c ，ac o n f o r m a n c ep l u gh a sb e e ni m p l e m e n t e dw i t h i nt h ep r o mf r a m e w o r k f i n a l l y w ec a ni n t e g r a t et w om e t r i c si n t oc o n f o r m a n c em e t r i ca n du s et h i sp l u gt oa n a l y z et h e e f f i c i e n c yo f t h ea l g o r i t h m s t h ei n t e g r a t i n gc o n f o r m a n c em e t r i c sp r e s e n t e di nt h i sp a p e rw i l lp e r f e c tt h e c o n f o r m a n c ec h e c k i n ga n a l y t i c a lr e s e a r c ho fp r o c e s sm i n i n gt e c h n o l o g y m e a n w h i l e ，i t w i l le x e r tap o s i t i v ee f f e c to nb u i l d i n gac o m p l e t et h e o r e t i c a ls y s t e mo fp r o c e s sm i n i n g a sw e l la sp r o v i d i n gt h e o r ye v i d e n c eo nt h ef l o we x p a n s i o na n dr e c y c l i n go fp r o c e s s m i n i n gt e c h n o l o g i e s w ec a nq u a n t i t a t i v e l yc a l c u l a t et h ec o n f o r m a n c eb e t w e e na c t u a l p r o d u c t i o na c t i v i t i e s a n dp r o c e s sm o d e lt h r o u g hc o n f o r m a n c ec h e c k i n gt e c h n i q u e s m o r e o v e r ，t h ea p p l i c a t i o no ft h et e c h n i q u e sc a nh e l pt oc o m p a r et h ea d v a n t a g e sa n d d i s a d v a n t a g e so fm o d e ls t r u c t u r e p r o v i d et h e o r e t i c a ls u p p o r t i n gf o rt h es t a n d a r d i z a t i o n o fm o d e l i n ga n dc h e c kt h ec o n f o r m a n c eb e t w e e nt h ep r o c e s sm o d e li nt h em a n a g e m e n t s y s t e m sa n dt h er e a lb u s i n e s sp r o c e s st oi m p r o v et h ep r o c e s sm o d e le 衔c i e n c ya n dt h e p r o d u c t i o ns e r v i c e s k e yw o r d s ：c o n f o r m a n c ec h e c k i n g p r o c e s s m i n i n g f i t n e s s a p p r o p r i a t e n e s s 第i i 页 国防科学技术人学研究生院硕十学何论文 表目录 表1 1 几种常见过程挖掘工具的比较3 表1 2 当今主流过程挖掘算法的比较8 表2 1 日志记录文件实例2 l 表2 2 抽取出的记录轨迹以及轨迹频率2 2 表3 1 适合性维度指标算法3 3 表4 1 行为适当性维度指标算法4 1 表4 2 结构适当性维度指标算法4 6 表5 1 日志回放过程中通过隐藏任务发现最短路径的递归方法5 2 表5 2 日志回放过程中在重复任务中选择最佳路径的递归方法5 3 表5 3 各模型适合性维度、行为适当性维度、结构适当性维度5 8 表5 4 各模型与日志记录文件的一致性指标5 9 第1 i i 页 国防科学技术火学研究生院硕十学何论文 图1 1 图1 2 图1 3 图2 1 图2 2 图2 3 图2 4 图2 5 图2 6 图2 7 图3 1 图3 2 图3 3 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图5 1 图5 2 图5 3 图5 4 图5 5 图5 6 图5 7 图5 8 图5 9 图5 1 0 图5 1 1 图目录 一致性分析技术在过程挖掘技术中的地位2 进行过程挖掘的一般步骤2 文章组织结构图1 4 串行模块1 7 并行模块l8 选择模块18 循环模块1 9 过程模型m 1 19 “花 状过程模型m 2 2 4 过程模型m 3 2 4 日志记录文件l 2 第一条轨迹在模型m 1 上的回放过程3 0 日志记录文件l 2 第四条轨迹在模型m 1 上的回放过程3 2 回放完成后提供的模型改进信息3 4 过程模型m 4 3 8 过程模型m 5 3 9 过程模型m 5 中变迁、日志记录文件m 2 中标签的关系4 0 根据事件同志文件l 2 改进过程模型m 5 4 2 可能激发变迁平均数计算原理4 3 过程模型m 6 4 4 模型m 6 与m 3 的改进图4 7 p r o m 框架4 9 打开f t 志记录文件l 2 5 5 过程模型m 4 与日志记录文件l 2 建立映射5 5 显示建立好映射关系的模型图5 6 选择一致性分析插件5 6 选择算法5 7 同志记录文件l 2 与模型m 4 的执行结果5 7 总结分析本文中所有过程模型与同志记录文件6 0 算法耗时统计6 1 模型包含隐藏任务数与重复任务数为2 时根据同志轨迹种类统计耗时6 l 同志轨迹种类为1 5 时，根据重复任务与隐藏任务数量变化统计耗时6 2 第1 v 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目： 学位论文作者签名： 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 学位论文作者签名：兰盔 作者指导教师签名： 日期1 年i 1 月2 如 日期：2 吵年，月目一臼 国防科学技术人学研究生院硕+ 学何论文 第一章绪论 1 1 研究背景和问题 随着企业间竞争日益激烈，提高企业工作效率，优化企业工作过程无疑是至 关重要的，而过程管理系统正是在这种形势下应运而生。过程管理技术作为一项 被业界广泛应用并迅速发展的技术，其主要特点是处理过程自动化、智能化。如 今过程管理系统在各种行业( 如保险业、金融业、制造业、服务业等) 已经得到 了广泛的应用。在指挥控制、信息整编、运行管理等军事领域也存在很高的应用 价值。 过程挖掘技术就是以过程管理系统为基础的数据挖掘技术。c o o k 和w o l f 在 研究中发现过程日志的记录是基于一个一个完整的事件，那么只要找到一种对日 志分析的算法，在软件设计时就可以直接利用过程运行的真实记录，客观地重现 过程，从而避免由于业务顾问和管理者的主观原因导致过程模型建立失败。因此 他们提出了从纯理论、纯算法到理论和算法相结合的三种过程发现的方法，利用 记录的活动属性来自动发现活动之间的关联，以此分析软件的运行过程。 过程挖掘技术是基于日志记录文件而工作的。记录在日志记录文件中的过程 中发生的事件是有序的，即是基于时间戳的，每一个事件都代表一个特定的过程 实例或一个特定的活动。然而在大多数日志记录文件中，还记录更多的信息，例 如事件执行的操作者等等。本文中的日志记录文件使用m x m l 来描述过程的事件 信息【2 】。m x m l 是基于x m l 的格式化文本，它可以很好的存储和表达日志记录文 件，并且m x m l 能够被过程挖掘平台p r o m 很好的支持。利用工具p r o m i n p o r t 很 容易把各种系统中得到的日志数据转换为m x m l 格式【3 】。 在过程管理信息系统中，日志记录文件将记录事件的发生或任务的执行。过 程挖掘技术则是通过后验的分析技术和挖掘算法，提取日志记录文件中的信息， 将实际执行的过程的不同方面( 控制流，数据流，资源分配，时序关系等) 反馈 给原模型。 现存的过程挖掘技术与算法主要致力于以下三个方面的研究【4 1 ： ( 1 ) 过程模型发现1 5 l ：就是在预先未知过程模型的情况下挖掘同志记录文件 构建过程模型，如利用a l p h a 算法可以构建过程模型。 ( 2 ) 一致性分析( d e l t a 分析) 1 6 】：存在预先定义的过程模型，基于执行同 志可以检查实际环境中运行的工作过程是否遵循预先定义的模型。一致性分析可 以检查预先定义模型和实际运行的现实过程之问的偏差以及权衡其严重性。 ( 3 ) 对原模型的扩展或再造i7 】：存在预先定义的模型，但是不进行检查，而 第1 页 9 芸坦 ?i 肇 i，； 9 譬警固 图l2 进行过程挖掘的一般步骤 第2 页 国防科学技术人学研究生院硕十学位论文 为了辅助用户实现过程挖掘一致性分析技术，目前已经丌发了许多过程挖掘 工具，比较著名的过程挖掘工具主要有e m i t t 引，l i t t l e t h u m b l 9 1 ，i n w o l v e 【1 0 ，i l 和 p r o c e s sm i n e r l l 2 1 等。对于这些工具，功能不尽相同，各有不同的优点。表1 1 从模 型表示、时间因素、基本并行结构、非自由选择结构、基本回路、任意回路、隐 含任务、重复任务以及噪声处理等九个方面对e m i t ，l i t t l et h u m b ，i n w o l v e 和 p r o c e s sm i n e 四个工具进行了比较。 表1 1 几种常见过程挖掘工具的比较 功能 e m 汀l i t t l e t h u m b i n w o l v ep r o c e s s m i n e r 模型表示 p e t r i 网p e t r i 网 图形块状 时间冈素 y e sn on on o 基本的并行结构 y e sy e sy e sy e s 非自由选择结构 y e sn on 0n o 基本回路 y e sy e sy e sy e s 任意回路 y e sy e sn on 0 隐含任务 n on on on 0 重复任务 n on oy e sn o 噪声处理 n oy e s y e sn o 通过表1 1 的对比，我们可以看出： ( 1 ) 模型表示方面：e m i t 和l i t t l et h u m b 是基于p e t r i 网建模，所以都是图 形结构，i n w o l v e 也是图形结构，而p r o c e s s m i n e r 是唯一块状语言结构。 ( 2 ) 时间因素：很多日志数据都记录示例的时间信息。然而只有e m i t 可以 挖掘包含时间信息的模型。 ( 3 ) 基本并行结构：所有工具都可以检测并处理并行路径，但是这四个工 具对过程的要求不一样。 ( 4 ) 非自由选择结构：非自由选择结构很难挖掘，上述四个工具都不能处 理非自由选择结构。 ( 5 ) 基本回路：上述四个工具都能处理基本回路，但是它们都对基本回路 有一些特定的要求，只能挖掘某一类型的基本回路。 ( 6 ) 任意回路：e m i t 和l i t t l et h u m b 可以挖掘任意回路，但是需要一个预 处理的步骤。 ( 7 ) 隐含任务：如果存在隐含任务，将会导致同：基数掘不完整。上述四个 工具都不能挖掘出隐含任。 ( 8 ) 重复任务：上述四个工具都假定每个任务在过程中只出现次，即相 同任务不能出现在同一过程的不同部分。i n w o l v e 是唯一能处理重复任务的工具。 ( 9 ) 噪声处理：e m 汀和p r o c e s sm i n e r 不能消除噪卢的影响。l i t t l et h u m b 能 第3 页 国防科学技术火学研究生院硕十学位论文 够处理噪声，它使用启发式算法末消除特定类型的噪声，i n w o l v e 使用随机模型， 能够将正常过程与异常过程区分开。 当然除了成熟的商业软件和工具外，丌源产品也由于研究实验的需要而产生， 其中最具代表性的是过程挖掘框架p r o m 的出现，所有的挖掘算法都可以以插件的 形式集成到该框架中。p r o m 框架支持多种过程模型以及日志记录文件形式。v a n d o n g e n 等人也在文献 2 】中提出了p r o m 框架开创了过程挖掘工具支持的一个新时 代。本文使用p r o m 框架下的自主开发的一致性分析插件进行算法的实现，将在第 五章有详细介绍。 1 2 研究现状和发展趋势 过程挖掘一致性分析技术，是过程挖掘技术中最重要的应用之一，是工作流 再设计与分析方法的一项关键技术，最早是由a a l s t 在2 0 0 4 年提出的【6 】6 ，一致性分 析的概念是：存在预先定义的过程模型，基于执行日志可以检查实际环境中运行 的工作过程是否遵循预先定义的模型。虽然一致性分析技术的概念于2 0 0 4 年提出， 但是之前的许多过程挖掘算法已经解决了一致性分析中的某些关键问题。本节总 结了当今主流的过程挖掘技术算法，以及这些算法在一致性分析中的作用，把过 程挖掘算法按照在一致性分析中的应用分成了三类，并对其进行比较研究。对过 程挖掘技术在一致性分析中的应用目前存在的问题从日志数据、挖掘技术和挖掘 结果等三个方面进行了分析和讨论。 1 2 1 研究现状 由于外部环境的急剧变化，现代工作过程充满了不确定性和多变性，为了提 高过程管理系统应对过程变化的能力，需要持续的对模型进行改进，过程挖掘一 致性分析技术应运而生。 近几年，工作过程管理技术在管理软件的设计中起到举足轻重的作用。但是 专家们逐渐发现上述几个方面正成为过程管理技术发展的瓶颈【1 3 】。早期的建模技 术算法和早期的软件设计一样，存在模型设计和实际业务的分离，并且缺乏柔性。 随着研究的深入，一致性分析的方法变得越来越细致合理，a a l s t 提出了基于p e t r i 网的工作流网进行建模，更加规范了过程模型的格式【1 4 巧】，不但需要分析同志与 模型的匹配程度【6 ，i4 1 ，还要针对模型本身的结构进行分析【1 6 】。进行一致性分析之后， 能够根据同志记录文件中记录的过程实例的执行信息，来改进现有的过程模型， 使得日志记录文件中记录的所有轨迹符合这个过程模型，并使得模型具有良好的 结构，模型中的每条路径都得剑充分的利用。 本章介绍了十三种现阶段七流过程挖掘算法，根掘每个算法在一致性分析技 第4 页 国防科学技术大学研究生院硕十学位论文 术中的应用，将算法分成三类，每一类对应于一致性分析技术中的一项关键技术， 即：解决致性分析技术中分析模型结构找寻最优路径的过程挖掘算法，模型改 进的过程挖掘算法以及提取并处理日志记录文件信息的过程挖掘算法。 ( 1 ) 解决一致性分析技术中分析模型结构找寻最优路径的过程挖掘算法。随 着研究的深入，这类算法从仅能处理串行结构到可以处理并行、选择、循环等多 种复杂结构发展。算法分为五种，即基于窗口序列挖掘方法的过程挖掘算法，基 于活动问依赖图的挖掘算法，基于活动间依赖图的挖掘算法的扩展，基于a d o n i s 模型的挖掘算法，基于遗传算法的挖掘算法。 基于窗口序列挖掘方法的过程挖掘算法：a g r a w a l 等人最早提出了串行模式挖 掘方法，该方法事先定义阀值，利用a p i r o i r 算法挖掘串行实例中不小于阀值的极 大串行序列作为串行模式，并且对算法进行了优化【l7 ，1 8 】。m a n n i l a 等人利用窗口方 法，最终目的是找到序列的集合，集合中的每个序列都被足够多的窗口所包含到 u 9 1 。但是文献【1 7 ，1 8 】中挖掘方法只将每个活动作为一个原子事件，没有考虑每个活 动从开始事件到结束事件之间的时间问隔，所以只能处理串行的过程模式序列。 基于活动问依赖图的挖掘算法：1 9 9 8 年a g r a w a l 第一次把过程挖掘用于过程 管理中，他通过判断活动之间的先后关系，来构造活动的依赖性，从而构造出有 向无循环图来表示流程中不同活动之间的关联【2 0 1 。 基于活动间依赖图的挖掘算法的扩展：进入2 l 世纪，过程挖掘得到了迅速的 发展，a a l s t 、w e i j t e r 、s c h i m m 、h e r b s t 等人提出了不同的算法来解决过程挖掘早 期发展中存在的问题。他们通过建立数据仓库来保存和分析流程只志，以建立完 整的工作过程网为目标，实现了挖掘模型的可视化表示和过程运行的及时监控， 使得过程挖掘与过程管理紧密结合，实现挖掘模型在过程管理系统的直接应用【1 4 】， 当然，用过程挖掘来建模仍然处于发展阶段，难免存在一些问题，但是过程挖掘 可以对不断增加的运行日志进行监控，用反复迭代( 递增) 的手段来提高模型的 柔性变化。p i n t e r 等人在此基础上对算法进行了扩展，考虑了活动的时间周期，但 算法只能处理活动间逻辑串行和并行关系，并不能处理活动之间的选择结构关系 1 2 。h w a n g 等人也提出一种通过考查活动间的依赖交迭关系来挖掘模型的方法， 该方法可以处理活动问的串行、并行和循环关系，但该算法同样不能处理活动间 的逻辑或关系，并且该方法在处理活动问并行关系时忽略了两个活动在不同的实 例中存在不同的时序关系的情况，使并行关系存在缺吲2 2 1 。 基于a d o n i s 模型的挖掘算法：h e r b s t 等人的挖掘算法则采用随机活动图 ( s t o c h a s t i ca c t i v i t yg r a p h ，s a g ) 表示模型【2 3 j ，能很好地处理流程中含有相同活 动名的结构，即能够很好的处理重复任务。与早期的a g r a w a l 提出的算法类似， 它也是在挖掘算法的开始先把有相同名字的活动易名，然后在挖掘出来的模型中 第5 页 国防科学技术人学硼f 究生院硕十学位论文 做相应的处理。二者的不问点在于对活动l 日j 依赖性的确定方式不同；另外，a g r a w a l 的算法只能用有向图来简单表示。这种算法在随机行为图的基础上，通过a d o n i s 模型把并行、选择结构清晰地呈现在使用者面前。它对噪音数据也作了处理，就 是用随机模型来区分，如果出现次数少的就作为噪音数据从同志中删去。但它对 隐藏结构的发现还没能实现，而且也只能发现简单的循环结构。 基于遗传算法的挖掘算法：a k a d em e d e i r o s 等人提出了利用遗传算法来解 决一致性分析问题中处理模型结构的问题。遗传算法不仅能够在一定程度上处理 信息的噪声，而且能够处理重复任务、隐藏任务、以及非自由选择的结构 1 0 , 2 4 , 2 5 】。 ( 2 ) 解决一致性分析技术中模型改进的过程挖掘算法。通过该种算法可以反 馈改进模型的依据，为决策者进行模型改进提供依据和支持。这类算法分为四种， 即基于隐m a r k o v 链的过程挖掘算法，基于p e t r i 网模型的挖掘算法，基于决策的 挖掘算法，多阶段过程挖掘算法。 基于隐m a r k o v 链的过程挖掘算法：h e r b s t 和k a r a g i a n n i s 在过程管理系统中提 出了一种隐藏的m a r k o v 方法来构造活动间的并行和串行操作。这些算法的提出为 建立完整的工作过程网奠定了基础，为模型的改进提供了依据，但它们都只涉及 活动之间关联的发现，没有进一步考虑是否可以构造出一个可以直接操作的可视 化模型【2 6 。0 1 。 基于p e t r i 网模型的挖掘算法：a a l s t 等人采用了p e t r i 网的一个子类一工作流 网络( w o r k f l o w - n e t ，w f n ) 来表示过程模型，提出了g t 算法【1 5 1 ，该算法将日志 中活动之间的时序关系分为四类，在此基础上改进并得到最终的过程模型，“算 法将每个活动作为一个原子事件”，同时p e t r i 网中的一些经典的问题也出现在了 w f n 中。在此基础上a k a d em e d e i r o s 等人开发出了能处理重复任务的a l p h a 抖 算法【3 l 】，有效的解决了上述问题。 多阶段过程挖掘算法：b f v a nd o n g e n 和w m p v a nd e ra a l s t 利用偏序关系 的特点提出了多阶段挖掘算法，它的主要特点是利用偏序关系得到活动实例图， 然后对活动实例图进行投影和标注，在此基础上把多个活动实例图进行集成得到 反映过程模型全局信息的集成实例图，最后把它转化为人们容易理解的e p c 或者 p e t r i - n e t 。多阶段挖掘算法不但能够表达并行，选择等多种逻辑关系，能够处理重 复任务，它的挖掘结果可视化效果也比较好，更容易理解 3 2 - 3 4 】。 基于决策的挖掘算法：r o z i n a t ，a 等人基于决策分析的思想，给出了一种决策 挖掘方法，该方法通过决策树来反映过程活动的再次发生的可能性，并用于之后 的模型改进，使挖掘结果能够被更好的应用【35 1 。 ( 3 ) 解决一致性分析技术中提取并处理r 志记录文件信息的过程挖掘算法。 可以利用这类算法，挖掘同志记录文件中的其他有用信息，为精确进行一致性分 第6 页 国防科学技术入学矽f 究生院硕十学何论文 析提供数据支持。这类过程挖掘算法包括面向块结构模型的挖掘算法，启发式网 络挖掘算法，基于模糊理论的挖掘算法，基于聚类的过程挖掘算法，基于语义的 过程挖掘算法五种。 面向块结构模型的挖掘算法：s c h i m m 则采用块状结构图表示过程模型，重点 分析了模型挖掘的过程，以及该过程中所遇到的其他相关问题，如日志数据处理、 噪音、活动名不唯一及模型中活动与资源的关系等【3 6 。 启发式网络挖掘算法：a j m m w e i j t e r s 等人利用启发式网络的方法和理论， 提出了一种基于启发式算法的过程挖掘算法，该算法对包含大量的过程活动的日 志表现出很好的性能。它能比较有效的处理日志中的噪声，并挖掘出某个过程日 志的主要行为【j7 。 基于模糊理论的挖掘算法：c h r i s t i a nw 等人利用模糊数学的方法，提出了一 种模糊挖掘的方法。因为通常的过程挖掘方法只挖掘过程模型，但并没有深入过 程模式的任务活动的细节，即区分哪些任务是重要的，哪些是不重要的。该方法 有力的解决了这个问题，能更加真实的反映了原过程模式的信息【3 8 1 。 基于聚类的过程挖掘算法：d i o g of e r r e i r a 等人研究的基于聚类的过程挖掘算 法【3 9 j 。在过程挖掘中，最重要的是提取事件日志文件的顺序问题，在通常情况下， 预先已经知道每个事件隶属于某个过程实例；当日志文件与过程实例中缺失隶属 关系时，基于聚类的过程挖掘算法就会显示其价值，它能够处理次序混乱、隶属 关系不明确的事件日志文件。对于流程再造、处理复杂流程、处理不确定流程以 及事件日志文件过于繁杂时具有很好的效果。其缺点是要预先界定过程实例的范 围，然后才能进行聚类算法，如何准确高效的界定过程实例成为该算法的一大技 术难关。 基于语义的过程挖掘：a ka l v e sd em e d e i r o s 等人提出基于语义的过程挖掘 算法【4 们，其关键点是利用过程挖掘软件p r o m 寻找事件日志文件中的语义信息的反 馈，( 如每个过程模型中最频繁发生的事件是什么，每件任务的平均时间是多少， 谁处理相同的任务等等) ，根据这些事件日志文件中的反馈信息，挖决过程中的 语义信息( 如任务信息，角色信息，人员信息等) ，定义具体的语义r 志格式 s a - m x m l 格式，使得挖掘日志文件中有用信息从基于标签向基于概念迈进，在 事件模型与同志文件之间架构语义r 志，有利于从日志文件中提取不同层次的信 息，分门别类，有利于进行一致。陀检验，进行流程再造。 通过回顾过程挖掘技术与算法发展历程，可以让我们更直观的了解过程挖掘 技术本身的特点以及利用过程挖掘的各种算法实现一致性分析，总结规律，有助 于寻找算法之间的联系，完善与发展各算法。表1 2 进行了当今主流过程成挖掘算 法的比较研究，系统地总结分析了过程挖掘算法在一致性分析中的作用。 第7 页 国防科学技术人学研究生院硕十学位论文 表1 2 当今主流过程挖掘算法的比较 提出使川l ： 名称特点及解决问题优点缺点 时间 凡 只将每个活动作 基于窗 利用窗口方法，最终 对于串行过程模为一个原子事件， 口序列 1 9 9 5目的是找到序列的集 式序列效率较没有考虑每个活 挖掘方 至 合，集合中的每个序无 高，为一致性分动从开始事件到 1 9 9 6 列都被足够多的窗口 析技术在模型结结束事件之间的 致 法 所包含到 构处理的算法的时间间隔，所以只 性 发展打下基础能处理串行的过 分程模式序列 析利用过程管理系 算法将每个活动 技 通过判断活动之间的统日志挖掘过程 作为一个原子事 术先后关系，来构造活模型的结构，利 件，没有考虑每个 中 基于活动的依赖性，从而构 用有向非循环图 活动从开始事件 分 动间依1 9 9 8 造出有向无循环图来 无表示过程模型， 到结束事件之间 析 赖图 表示流程中不同活动 并提出了模型挖 的时间间隔，导致 模 之间的关联，从而分掘的目标：满足 活动间的并行关 型析模型结构完整性、正确性 系不完整 结以及最小性 构逐步完善基于活动间 找基于活依赖图的挖掘算法， 开始支持并行、不能处理活动之 寻动间依 2 0 0 2 支持更多类型的活动 最赖图扩 至 无串行关系，对噪间的选择结构关 2 0 0 5 图，并在可视化表示 声进行了处理 系 优展和过程运行监控方面 路 有所提高 径 在随机行为图的基础 该算法能很好地 的 基于 上，通过a d o n i s 模对隐藏结构的发 a d o n处理流程中的重 过 l s 模2 0 0 4 型把并行、选择结构i n w 0 复任务，并且能 现还没能实现，只 程 型的挖 清晰地呈现在使用者 l v e 能发现简单的循 挖 掘算法 面前，并对噪声进行 够处理模型中的 环结构 掘了处理 选择结构关系 算 可处理信息的噪 法 基丁遗 利刚遗传算法的思 2 0 0 4想，设定初始值，设 声，能够往过科 噪声可能造成停 传算法 至 定停- i ：条件，遗传过 p r o m 挖掘中处理重复止条件发生斤但 的挖掘 框架 任务、隐藏任务、计算仍不能停i 卜 2 0 0 6 程( 变异和交换) 等 算法以及非自由选择的情况发生 进行一致性分析 的结构 第8 页 国防科学技术大学研究生院硕十学位论文 表1 2 当今i 流过程挖掘算法的比较( 续表) 提出使用i ： 名称 特点及解决问题优点缺点 时间具 通过该算法，可 该算法只涉及活 可有效的构造活动间以改造过程模 动之间关联的发 基于隐1 9 9 9 的并行和串行操作，型，使之与现实 现，没有进一步考 m a r k o至无 虑是否可以构造 v 链 2 0 0 l 对原模型进行扩展和过程之间提高契 _ 再造 合度，使模型效 出一个可以直接 操作的可视化模 致率更高 型 性 提出了a 算法，该算噪声以及不完整 分 基于 法将日志中活动之间 基于p e t r i 网可 析 p e t r i 以直观的展现出 的日志文件( 如过 技 网模型2 0 0 4 的时序关系分为四i n w o 过程模型的结 程未完成时的日 术 的挖掘 类，在此基础上改进 l v e 志文件) 会对a 中 算法 并得到最终的过程模 构，有利于模型 模 型 的再造与改进 算法造成很人影 响 型 利用偏序关系得到活 改 动实例图，然后对活 进 动实例图进行投影和 能够表达并行， 标注，在此基础上把 选择等多种逻辑 的 多阶段2 0 0 4 多个活动实例图进行 关系，能够处理 不能构造过程实 过 过程挖 至e m i t 重复任务，其挖 例图，只能从现有 程掘算法 2 0 0 6 集成得到反映过程模的过程实例图出 挖 型全局信息的集成实 掘结果可视化效 发 掘 例图，最后把它转化 果也比较好，更 算 为人们容易理解的 容易理解 e p c 或者p e t r i n e t 法 通过决策树来反映过 运用机器学习技 对于隐藏结构、重 基于决程活动的再次发生的术，通过已经发 p r o m 复结构、循环结构 策的挖 2 0 0 6 可能性，从而找到模 框架 生的活动，自动 掘算法 型改进与再造的可能改进p e t r i 网过程 支持不够理想，需 进一步研究 点 模型 第9 页 国防科学技术人学研究生院硕十学位论文 表1 2 当今土流过程挖掘算法的比较( 续表) 提出 使用一l ： 名称特点及解决问题优点缺点 时间具 对输入的过程日 该算法根据逻辑定义 志文件数据的准 面向块( 如j ：作组，角色等) 可处理串行、并确度要求很高，不 致 结构模把整个过程模型分成p r o c e s s 2 0 0 4行、选择、循环能消除噪声的影 性 型的挖若干个块，然后挖掘 m i n e r 分 掘算法各块之间的关系并提 结构响，不能挖掘活动 名不唯一的日志 析 取其中的有用信息 文件 技利用启发式网络的方 术 启发式 法和理论，对大量的对噪声的处理行 中 网络挖 2 0 0 6 过程日志文件数据处 l i t t l e 之有效，可以挖需要大量的过程 提 掘算法 理，可还原出与该日 刀m b 掘出某个日志文 日志文件支持 取志文件匹配的原过程件的主要行为 并模型 处不支持结构过于 理 加强了对信息噪 复杂的过程模型， 日 基于模深入过程模式的任务 声的处理，通过 士 糊理论活动的细节，区分哪 p r o m 把不重要的信息 需要大量的过程 j t 生 的挖掘 2 0 0 6 些任务是重要的，哪 框架 过滤掉，处理过 日志文件支持，由 记于丢弃了不重要 录 算法些是不重要的程日志文件来还 的任务，所还原出 文 原、发现原模型 的模型不够精确 件 对丁流程再造、 信 基于聚利用聚类算法，可以处理复杂流程、 预先准确界定过 息 类的过找寻日志文件与过程处理不确定流程 的 程挖掘 2 0 0 7无程实例的范围较 实例中缺失的隶属关以及事件日志文 困难 过 算法系件过于繁杂时具 程 有很好的效果 挖 利刚过程挖掘软件 挖掘日志文件中对噪声处理较弱， 掘 基于语 p r o m 寻找事件日志 有用信息从基于对于现实过程中 算 义的过文件中的语义信息的 p r o m 2 0 0 8标签向基于概念从事什日志文件 法 样挖掘 反馈，定义具体的语 框架 算法义日，基格式 迈进，有利丁进界定语义信息较 行流程再造 难 s a m x m l 格式 纵观过程挖掘算法的发展过程，以及解决一致性分析中关键技术问题的效果， 可以看出，过程挖掘算法紧紧围绕同志记录文件与现实过程本身的特点，对同志 记录文件的各种信息进行深入分析，支持模型从刚性到柔性，模型结构从简单的 第l o 页 国防科学技术大学研究生院硕十学位论文