基于Petri网可达图的业务对齐方法

为提高过程挖掘中计算最优对齐的效率,提出一种基于Petri网可达图的业务对齐方法。首先,根据给定事件日志,提取其包含的活动子集;然后,将子集中包含的活动映射到变迁,构建花型日志模型;进一步,计算花型日志模型与过程模型之间的乘积模型及其可达图;最后,给出算法在可达图中查找出事件日志中全部迹与过程模型之间基于给定代价函数的一个最优对齐和所有最优对齐。从理论上证明了该方法的适用性与有效性。通过仿真实验,验证了该方法的可行性与优越性。     

基于Artifact生命周期的业务流程一致性检查

为检查业务流程日志中对关键业务数据的操作和预定义模型中的操作是否存在偏差,提出一种基于Artifact生命周期的业务流程一致性检查方法。基于Petri网建立了业务流程关键数据Artifact的生命周期模型。给出Artifact实例日志,采用A*算法查找日志中的Artifact实例轨迹与模型中活动序列的最佳对齐,计算活动—属性关联拟合度。最后,实现了一个原型系统,结果表明以数据为中心进行一致性检查为流程分析和改进提供了有效的方法。     

基于Petri网的事件日志与过程模型对齐方法

为了提高过程挖掘中计算最优对齐的效率,提出一种基于Petri网的事件日志与过程模型之间的快速对齐方法——RapidAlign方法。该方法在观察日志的同时运行模型,比对日志活动与模型活动,从而得到日志移动、模型移动和同步移动;根据移动类型计算代价值,并记录日志和模型的当前状态;选取代价值最小的状态继续日志的观察和模型的运行,直到日志和模型均到达结束状态。最终生成一个最优对齐图,其源节点到终节点之间的路径包含了基于标准似然代价函数的事件日志与业务过程模型之间的所有最优对齐。对RapidAlign方法的适用性进行了详细且严格的描述,从理论上证明了该方法的正确性与有效性。通过仿真实验,验证了RapidAlign方法的优越性。     

基于对齐处理与偏差检测的业务流程适合度分析

由于业务流程在实际应用中的多变性及动态性,需要对日志与给定模型之间的服从性进行校验与分析。目前的服从性校验方法主要将日志与模型进行对齐处理以检测整体偏差,但这种全局观测所获得的偏差会影响服从性校验的准确性,因此提出一种新方法对日志和给定模型间的最优对齐进行搜索来分析服从性。首先设定选择子序列划分对齐的种类,并通过对齐搜索算法在不断排除的过程中寻找最小偏差对齐;然后分析同一偏差以不同形式回放于模型子模块中的精度及行为关系确定最优对齐。该方法通过实际业务流程的研究案例及比较实验进行评估,其结果表明准确检测偏差能够明显提高适合度的测量值,并通过分析适合度测量的详细数据得出缩小对齐比较范围可减少计算量的结论。     

基于关系矩阵的工作流日志重复任务识别算法

针对传统工作流模型挖掘算法不考虑模型中重复任务的存在,导致挖掘出的模型精确度不高的问题,提出一种基于关系矩阵的重复任务识别方法。通过分析工作流执行日志得到所有事件的前驱后继关系,根据不同的模型结构进行事件重命名,再基于同类别重复事件之间的相似度对重复事件进行聚类得到最优识别结果。实验表明,该方法能正确有效地识别工作流日志中的重复任务,减少模型中的不可见任务,最终提高工作流模型挖掘方法的精确度和可理解性。     

基于行为校验与偏差组合的过程模型修复

模型修复通过对偏差行为的合理调整,改善事件日志与业务流程之间的一致性性能.采用自循环插入方式对日志中可观测的偏差活动进行模型修复,将优先考虑适合度的提升而忽视精度.为获得事件日志与过程模型之间不可回放的行为模式,根据行为关系将其可达活动图表划分为若干个片段并进行服从性校验.利用回放过程中行为模式所产生的最优对齐检测偏差的发生、位置以及潜在行为关系,将具有直接跟随关系的偏差元素构建为可修复的子结构,从而通过减少事件日志中的偏差个数而改善精度.通过实验使用M-repair插件在不同数据集上进行评估,结果表明该方法相较于现存方法在保证适合度的前提下可显著提升精度.     

支持复杂结构的混成过程挖掘方法

为解决传统过程挖掘算法在处理蕴含复杂结构的海量日志时的低效低质问题,提出一种支持复杂结构的混成过程挖掘方法。该方法首先将事件日志转化为具有发生次数的直接后继图,以支持活动间基本关系的判定;通过过程树对已发现的两两活动间的基本关系进行抽象与合并,进而对日志进行更新,反复迭代直到整个日志中的所有具有基本关系的活动被全部发现。若待发现模型由基本块组成,则挖掘结果为基于块的过程模型;若待发现模型包含复杂结构,则通过混成使用基于区域的方法对复杂结构进行发现。最终利用活动重构操作对挖掘结果中已抽象为过程树的部分进行细化,从而获得最终结果。为了进一步提升挖掘效率,还提出并行化的发现与重构方法。大量基于真实数据的实验结果表明,该方法的挖掘效率和挖掘精确度达到了较好的水平。     

基于可扩展活动关系的过程概念漂移检测

为了发现过程模型漂移的时间点,提出一种基于活动关系频繁度的日志分割方法。事件日志可以用活动关系抽象表示。通过关系抽取将事件日志转化为活动关系矩阵,然后分析每个活动关系的变化趋势并检测出候选变更点将所有候选变更点通过密度聚类的方式进行合并,得到模型漂移的时间点。在人工生成日志上的实验结果表明,算法具有良好的准确率、较小的误差和较低的时间消耗。     

基于日志的流程相似度计算方法适用性分析

针对现有业务流程相似度计算方法的不足,从流程日志出发计算流程相似度,并根据以流程日志为输入的特点对现有方法进行了改进,提出两种改进方法。一种方法是通过日志重构流程模型,基于模型结构计算流程相似度,但是为体现流程日志中对流程结构某些执行路径或分支的倾向性,在流程模型上重演日志轨迹,利用A*算法寻找匹配日志轨迹的最佳重演方式,识别最佳重演方式下被执行的流关系,以对流关系加权生成加权BPMN模型计算流程相似度;另一种方法不需重构模型,基于任务序列计算流程相似度,为支持任务相似度计算,定义了任务间的距离,由此得到支持任务距离度量的轨迹距离,进一步利用轨迹多集计算流程相似度。通过在不同的真实数据集上的实验,分析了两种方法在相似度计算结果的异同之处,并总结了两种方法的适用范围。     

基于轨迹聚类种群的遗传过程混成挖掘算法

遗传过程挖掘算法以模型质量引导模型的发现,在挖掘模型的同时不断修正挖掘算法的执行,因此相比于其他挖掘算法,更容易生成高质量的过程模型。但由于其迭代发现的特性,对于大型日志,挖掘效率往往较低且生成模型质量不高。针对以上问题,提出一种基于轨迹聚类种群的遗传过程混成挖掘算法(GMTC)。该算法一方面通过轨迹聚类划分事件日志,简化挖掘环境,再使用归纳挖掘算法对事件日志进行预挖掘,为遗传挖掘算法准备高质初始种群;另一方面优化遗传算子,使用对齐日志得到的模型偏差信息指导突变操作,使得突变操作由随机变为有向,从而有效地提高种群的综合质量,使遗传挖掘算法加快收敛。基于过程日志生成器生成模拟日志、某市政府建筑许可申请过程的真实日志以及6个公开数据集的实验结果表明:基于轨迹聚类种群的遗传过程混成挖掘算法相较于其他挖掘算法不但在挖掘效率方面有较大提升,而且挖掘得到的模型质量也能够达到较高的水平。     

基于Petri网基本结构的相似最优校准计算方法

为了提高事件日志与过程模型之间一致性检查的效率,提出一种基于Petri网基本结构的相似最优校准计算方法。根据网上购物流程建立Petri网模型,计算给定迹与模型之间的所有最优校准。分析发现有些最优校准包含的移动集合完全相同,只是移动出现顺序不同,定义为相似最优校准。通过对相似最优校准的性质进行分析得出定理与推论。定义最优校准相似关系和等价关系,给出了最优校准集合的划分方法,该方法可选取代表项,体现迹与过程模型之间的所有偏差。通过分析四种工作流模式提出多阶段校准算法,用于求解Petri网模型与约束迹之间相似最优校准代表项。仿真实验例证了该相似最优校准方法的正确性和有效性。     

基于逻辑Petri网的模型修正方法

为了解决现有模型修正方法仅考虑拟合度,而忽略精确度以及简洁度等指标的问题,提出一种基于逻辑Petri网的模型修正技术。利用已有的一致性检测技术计算最优校准,并通过标识所在库所定位偏差位置。给出了逻辑校准和逻辑最优校准的定义,并提出一种基于最优校准的计算拟合度的方法。将本文所提方法与Fahland方法进行对比分析,表明本文修正方法的拟合度和精确度更高,能够更好的修正带有复杂循环结构的流程。最后,通过仿真实验证明了方法的有效性。     

基于Petri网的业务流程低频行为挖掘与优化分析

低频行为的挖掘是业务流程管理的重要内容之一,区分有效低频和噪音在业务流程优化中显得尤为重要。已有挖掘方法多是从数据属性研究低频行为,较少根据不同模块间的行为属性来分析低频行为,由此提出基于Petri网的业务流程低频行为的挖掘与优化方法。首先,通过用流程树切的直接流图表示日志的行为关系,并与初始模型做匹配,发现所有的低频序列;然后,计算日志与模型的行为距离向量,基于行为紧密度区分有效低频日志和噪音日志,优化事件日志;其次,利用不包含噪音序列的事件日志通过融合交互模块网与特征网,挖掘得到一个优化的业务流程模型;最后,通过具体的实例分析和仿真实验验证了该方法的有效性。     

基于最优匹配的三维CAD模型相似性评价算法

提出一种基于最优匹配的三维计算机辅助设计模型相似性评价算法.根据三维计算机辅助设计模型的边界表示,将相比较的两个计算机辅助设计模型拆分成面,并分别对面进行分类.将两模型中同种类型的面两两匹配,运用相应的准则计算出每对面的相似性系数δij,从而使同种类型的面形成了一个二分图.利用图论中二分图的最优匹配算法,计算出两个模型同类型面中各面的最优匹配方案,并计算出加权最优匹配值,最后将各种类型面的最优匹配值相加得到模型的相似系数,以此作为评价模型相似性的依据.为恰当地评价两个类型相同面的相似性,给出了能够综合反映面几何特征和拓扑特征的评价准则.试验表明本方法能够客观地反映两计算机辅助设计模型的相似程度,并较好地反映人视觉上的相似经验.     

一种基于排队论的关键流路由调整算法

在分析现有路由调整算法的基础上,提出一种基于排队论的关键流路由调整新算法(KFRA)。首先,应用排队论建立最优流分配模型,模型既给出最优流分配的计算方法,也给出路径的最优流分配与各路径最大可用带宽之间的关系。然后基于模型实现KFRA算法,其计算复杂度为O(nlogn),低于大部分路由调整算法。理论分析和仿真实验结果表明在不同的网络环境下,提出的算法能在保证时延的基础上对待调整的流进行全局最优分配,最小化流传输的端到端时延,提高流传输的质量,与同类算法相比有更好的性能。     

基于后继关系的行为块过程挖掘方法

鉴于已有的过程挖掘方法在发现循环结构和隐藏行为上具有一定的局限性,提出一种基于后继关系的行为块挖掘算法。依据日志建立后继关系矩阵,分析了矩阵中变迁间对应的值,从而可以发现所有最小行为块和隐藏的行为关系,包括循环行为块;利用组合原理对带有重复变迁的最小行为块进行组合,得到结构行为块;组合所有行为块得到初始模型,利用已发现的隐藏行为关系修正初始模型得到更加精确的过程模型。通过实例分析和ProM的仿真实验验证了所提方法的可行性。     

一种新的空间曲线匹配算法

提出一种新的空间曲线匹配算法。该算法对离散的曲线进行光顺、拟合和采样，使用空间曲线微分几何性质计算各采样点的曲率和弗朗内特标架。通过曲率计算匹配点对列表，通过对齐匹配点对的弗朗内特标架进行曲线匹配，得到一个匹配矩阵集。从匹配矩阵集中选出一个最优匹配的匹配矩阵，使得空间曲线的对应点匹配窗口内的距离平方和最小。实验结果证明，算法效率高、鲁棒性好。     

基于行为特征网的流程模型分解挖掘

为了使包含活动数目较多的事件日志有效挖掘流程模型,提出基于行为特征网的流程模型分解挖掘方法,基于活动日志确定各活动间的行为足迹关系,推得相应的行为矩阵;结合行为矩阵计算行为关系图,从而产生活动聚类;通过现存挖掘算法过滤子日志挖掘子网,并对子网添加接口库所形成子网行为特征网;在行为特征网的基础上,运用合成网的观点合成整网,以此挖掘流程模型。最后通过仿真分析验证了该分解挖掘方法的有效性。     

基于Spark的并行分布式过程挖掘算法

针对传统的过程发现算法对大规模事件日志挖掘效率低的问题,提出一种利用Spark集群进行加速过程挖掘的方法。该方法主要针对基于日志活动关系的过程挖掘算法,对抽取活动关系阶段进行加速。通过并行分布式抽取活动关系,将事件日志转化为活动关系矩阵。然后利用关系矩阵,按算法原本的后续步骤,挖掘出过程模型。利用Spark实现分布式α-Mine算法和分布式Flexible Heuristic Miner算法,结果表明:所提方法在时间消耗上优于目前最好的算法,挖掘效率明显提升。     

面向模型局部搜索的最短路径集最优匹配方法

为实现边界表示模型的局部搜索,提出一种将模型属性图局部结构比较问题转化为属性图最短路径集最优匹配问题的方法。为获得属性图的最短路径集,给出一种可以生成两两节点间所有最短路径的算法;为实现查询模型与备选模型对应的最短路径集之间的最优匹配,将离散粒子群优化算法引入模型搜索领域,提出面向最短路径集最优匹配的算法,定义了相应的基本运算规则、适应度函数、终止条件和算法步骤。模型搜索实验结果表明,所提算法可以解决如何获取模型局部结构对应关系和计算局部结构间距离的问题,从而有效地支持模型的局部搜索。