学位论文 > 优秀研究生学位论文题录展示

支持业务流程建模的块结构流程挖掘技术的研究

作　者: 张立群
导　师: 王海洋
学　校: 山东大学
专　业: 计算机软件与理论
关键词: 业务流程建模流程挖掘流程日志文件块结构挖掘 WF网
分类号: TP311.13
类　型: 博士论文
年　份: 2010年
下　载: 300次
引　用: 4次
阅　读: 论文下载

内容摘要

随着市场经济的发展,企业、机构需要顺应市场需求的变化,随时快速调整业务,提高应对市场变化的快速反应能力。因此企业的信息系统中支持业务运行的业务流程部分需要再造或优化,而流程的再造或优化首先需要理解当前业务流程运行的模式。目前,业务流程运行模式的提炼主要依赖技术人员与业务人员的沟通,其所得结果有很强的主观性,缺乏整体、完善性,且时间成本高、效率低。目前,大多数企业的信息系统管理应用软件,无论提供或不提供显式的流程,这些软件都提供企业实际业务执行的记录,即流程日志。如何分析这些日志数据,从中找出业务流程运行的模式,用于快速的流程再造和柔性管理是迫切需要解决的问题,而流程日志中抽取的业务流程模型,可以真实反映企业业务流程的执行,支持业务流程再造或优化的快速建模。本文研究的基础——简单格式的流程日志并不是仅仅局限于工作流管理系统所提供,目前公司、机构的信息系统,它们的事务系统,如ERP、CRM、B2B、SCM等都提供本文研究所需的简单格式的日志信息。也就是说,只需要收集记录了业务流程中各个任务活动发生的顺序序列,即流程日志。流程日志记录了业务流程执行的真实情况,从中挖掘出业务流程模式更加可信易读。因为流程模型的结构往往比较复杂,存在循环、并行、选择、非自由选择等难以表述清楚的块结构,现有文献的挖掘方法对这些结果的处理不理想,如循环结构、非自由选择结构等,目前没有普适的处理方法解决这些问题。此外,利用流程日志中的时间信息可以挖掘到更精确的活动逻辑关系并计算流程工作的性能,但是大多数的流程挖掘方法并没有充分利用日志中的时间信息。本文主要是深入研究并提炼给出了流程挖掘概念、流程日志的数学表示、流程模型的Petri网表示及结构化工作流网概念,并给出相关的数学描述以及定义。在此基础上的研究工作主要有以下三个方面的贡献：第一,目前,企业应用系统软件没有统一的流程日志规范标准,日志格式分为两类：无时间标志型日志和有时间标志型日志且一般原始日志带有噪音。针对无时间标志型日志,采用多步抽取模型方法,提出了一种基于简单流程日志格式的块结构挖掘方法BRC (Block_Structure Replace Compression:BRC),挖掘任务之间的逻辑关系,用于构建日志所反映的业务流程模型。基本块结构对应于四种结构即顺序、并行、选择和循环结构。方法首先定义了能够被挖掘的流程的基本要求,即结构化流程模型。方法的基本思想是在对四种基本结构进行分析的基础上,从日志中找出具有这些结构的模块,并用结点来替换每个模块。通过循环使用四种模块挖掘算法从日志中挖掘和替换,使得日志不断收缩。如果最后得到的日志是一个点,则只需进行一次逆变换,即将前面得到的模块按照相反的顺序依次代入到流程模型中,这样得到一个容易理解的基于工作流网的WF网模型。同时,证明用该种方法得到的工作流网是合理的,安全的。在对顺序任务和选择任务进行挖掘的过程中,考虑到来自其他并行任务的干扰,BRC提出并采用了并行任务等价类概念,即首先从日志中划分出并行任务等价类,再依次搜索各等价类,挖掘出其中的顺序和选择任务,从而很好地解决了并行任务对结构化挖掘的干扰问题。通过生成和运行一定数量的实验数据,对BRC方法的挖掘质量进行了检验分析,证明该方法在复杂流程的挖掘方面具有明显优势。讨论了带噪音的因果关系挖掘、带噪音的并行关系挖掘、带噪音的选择结构的挖掘,并给出了带噪音处理的改进型结构化挖掘算法。第二,无时间标志型日志中并行关系的挖掘是相对困难且计算量较大,针对有时间标志型日志,提出了一种基于时间间隔的简单流程日志格式的挖掘方法,用于构建日志所反映的业务流程模型。方法的基本思想不同于事件模型类思想,在事件挖掘类中,把一个任务的执行看作是不可分割的,是一个原子性事件。而从基于时间间隔日志的流程挖掘方法解决方案看,每一个任务的执行都具有一个时间间隔,即任务的开始事件和任务的结束事件。可以再拓展这个模型成为捕获更精确的模型视图,在其中,执行活动是一个沿着时间轴的时间间隔,并且两个间隔可以互相交叉。间隔方法分为两大步骤：(1)：产生流程执行图。针对每一执行产生一个DAG图。在单个执行中的间隔交叉使得此DAG图易于对并行关系的挖掘,对具有同样活动集合的执行图进行合并产生单个DAG图；(2)合并流程执行图。对于流程图的一个子图,各个运行于其上的执行覆盖相同的活动集合,也就是业务流程中使用不同的参数来选择合作伙伴的有向边是一样的。因此合并结果所产生的DAG图就是流程的控制流图。方法通过合并各个依赖于日志的DAG图,产生现实意义上的流程模型图。验证对比了两类算法：间隔算法和非间隔算法。得出了有意义的一些结论,如丢失边或多余边与流程日志规模之间的关系等。第三,针对一般情况下,流程日志带有噪音且是不完备的,探讨分析了噪音情况,给出了日志中任务逻辑关系挖掘方法。方法中定义了一个概念：顺序关系。该关系是基于START和COMPLETE这两种事件类型和它们的时间戳的。随后给出顺序关系的度量方法。提出了一个挖掘流程模型图的方法,源流程模型可以包括所有的基本块结构和非自由选择结构。提出的方法使用具有时间戳的任务状态流程日志,利用时间信息,比如活动的平均等待时间、平均执行时间去挖掘流程模型。在挖掘流程模型时,首先通过扫描一次日志,为每一个任务构建平均值表；然后在平均值表的基础上分两步执行：第一步是挖掘基本的结构,比如顺序路由、并行路由、选择和循环路由；第二步是分析流程模型的高级结构,如或连接结构。通过以上两步,能挖掘出预期的流程模型。另外使用算法进行挖掘的时候,去除噪音问题通过观测起始值来决定。最后对提出的挖掘算法和文献中已经提到的算法做了比较,得出的结论是：TWM能挖掘α算法所挖掘的所有流程,然而,α算法不能挖掘TWM能挖掘的所有的流程,TWM和α算法在时间复杂度方面是等同的。另外,提出的算法对解决隐藏任务挖掘提供了有用的信息。此外,研究工作中,实现了一个支持流程挖掘算法的原型系统。设计此系统的目的主要是：(1)验证α算法的有效性；(2)以此和我们所提方法算法进行有意义的比较,获得有效的可信度；(3)验证针对复杂变异结构流程,α算法的局限性；(4)为流程挖掘技术的商业化应用积累相应的经验。本文研究目的是针对支持业务流程建模的流程挖掘技术进行探索性的研究,希望为该领域的问题解决提供一种有效的思路和方法。

全文目录

摘要  11-14
ABSTRACT  14-18
第一章绪论  18-28
  1.1 研究背景和意义  18-22
    1.1.1 研究背景  18-19
    1.1.2 问题的提出  19-20
    1.1.3 研究意义  20-22
  1.2 主要研究内容和创新点  22-24
    1.2.1 主要研究内容  22-23
    1.2.2 主要创新工作  23-24
  1.3 本文组织结构  24-26
  1.4 本章小结  26-28
第二章相关技术及研究现状  28-37
  2.1 业务流程建模技术  28-30
  2.2 软件工程领域中的流程抽取  30
  2.3 单步抽取模型方法  30-31
  2.4 多步抽取模型方法  31-33
  2.5 抽取流程的模型表示  33-34
  2.6 总结与分析  34-35
  2.7 本章小结  35-37
第三章基于无时间标志型日志构建流程模型  37-62
  3.1 流程日志的形式化表示及性质  37-43
  3.2 块结构挖掘  43
  3.3 日志预处理  43-44
  3.4 基本结构挖掘  44-55
    3.4.1 顺序结构的挖掘  45-46
    3.4.2 选择结构的挖掘  46-48
    3.4.3 循环结构的挖掘  48-50
    3.4.4 并行结构的挖掘  50-53
    3.4.5 循环使用结构挖掘算法  53-55
  3.5 模型转化—替换任务并生成流程模型  55
  3.6 结构化挖掘满足合理性要求  55-56
  3.7 算法实例  56-60
  3.8 算法局限性分析  60-61
  3.9 本章小结  61-62
第四章基于时间间隔型日志构建流程模型  62-78
  4.1 时间间隔流程日志  62-64
  4.2 流程模型  64-66
  4.3 间隔模型  66-67
  4.4 产生流程模型图的间隔方法  67-75
    4.4.1 实现步骤1的算法Ⅰ  68-69
    4.4.2 实现步骤2的合并执行图算法Ⅱ  69-75
  4.5 间隔方法验证分析结果  75-77
  4.6 本章小结  77-78
第五章带噪音日志中任务关系挖掘分析  78-110
  5.1 事件日志  78-80
  5.2 顺序关系  80-82
  5.3 一致性关系测量  82-83
  5.4 确认路由  83-84
  5.5 基于带噪音日志构建流程模型  84-94
    5.5.1 构建平均值表AVT  85-86
    5.5.2 任务之间边的判定  86-90
    5.5.3 Timed Workflow Miner(TWM)  90-94
  5.6 对比分析  94-102
    5.6.1 实例1:Log WA  95-96
    5.6.2 实例2:Log WB  96-99
    5.6.3 实例3:Log WC  99-101
    5.6.4 噪音  101-102
    5.6.5 隐含任务  102
  5.7 带噪音处理的块结构挖掘方法  102-109
    5.7.1 带噪音的因果关系挖掘  103
    5.7.2 带噪音的并行关系挖掘  103-104
    5.7.3 带噪音的选择结构挖掘  104-105
    5.7.4 实验方法和实验数据的准备  105-106
    5.7.5 实验结果分析  106-109
  5.8 本章小结  109-110
第六章流程挖掘系统  110-119
  6.1 流程挖掘算法语言模型  110-112
  6.2 流程挖掘系统原型  112-116
    6.2.1 系统结构  112-113
    6.2.2 日志文件  113
    6.2.3 流程日志预处理  113
    6.2.4 任务间依赖关系的计算  113-114
    6.2.5 生成流程模型  114-116
  6.3 WFML(WF-net Markup Language)  116-118
  6.4 结果验证与质量度量  118
  6.5 本章小结  118-119
第七章总结与展望  119-125
  7.1 本文主要工作总结  120-123
  7.2 未来研究工作展望  123-124
  7.3 本章小结  124-125
参考文献  125-136
致谢  136-137
攻读博士学位期间发表的学术论文  137-139
在读期间参与科研项目情况  139-140
学位论文评阅及答辩情况表  140-142
附录英文论文  142-159

支持业务流程建模的块结构流程挖掘技术的研究

内容摘要

全文目录

相似论文