在过去的20年中，国内外学者已经提出各种流程发现方法，如AI- pha Miner8,Heuristics MinerInductive Min erTsinghua-AlphaSplitMinerl等，然而由于1/0和内存等硬件限制，大多数发现方法不再适用于使用一台机器处理整个大型数据集的模型发现，著依靠当期的个布式平台重新家现现有的流程发现算法，如著名的MapReduce框架1-4,则流程将非常耗时，而目这些方法不且有普适化，需要开发人员对底层发现方法有广沙的了解，因此迫切需要一种新方法来解决这些问题。

事件日志采样技术为上述问题提供了一种可行性方案，其将原始事件日志作为输人，返回一个样本日志。

事件日志采样技术不是要求重新实现现有发理方法,而是希想能够提供一种提高发现效率的费代方法。

目前已经提出许多事件日志采样技术，以 LogRank甘志采样技术4为例，该技术实现了一个基干图的排序算法，所得样本日志比原始日志小得多,处理效率也更高，在此基础上提出的一种基于轨迹相似度的事件日志采样技术LogRank+1门]虽然能够确保采样质量，缩短采样时间，提高采样效率，但是其性能仍然不能满足实际应用的需求，例如得到的模刑质量不够理想，而且随着原始日志规模的增大，原始日志采样时间与样本日志挖据时间之和与原始日志按据时间之间的差异食发明显。

受传统集合覆盖等相关问题的启发，借助传统算法如动态规划、贪心算法、排序算法等，本文提出面向日志完备性的事件日志采样方法，包括完全追历采样法(BF-Sampling)集合覆盖采样法(SC Sampling)基于轨迹长度的采样方法(TL-Sam- pling)和基于轨迹频次的采样方法(TF-Sampling)4种，该方法保留了原始日志更多的信息，能够更有效地支持日志采样，而且与已有采样方法相比，4种采样方法可以得到更简单，更高质量的流程模刑，为了验证这种保证日志完备性的事件日志采样方法的可行性与高效性，从模型质量评估和时间性能分析两方面进行实验，比较4种采样方法得到的样本日志与原始日志的质量，最终说明本文所提4种新的采样方法可以在保证模型挖掘质量的前提下，大幅提高模型挖掘效率，具备可行性与高效性。

1 基础知识

本章介绍后期研究4种事件日志采样方法和两种实验评估方法需要用到的基本知识。

假设S为一个集合，表示空集，B(S)为集合S所有多集的集合;f:X→Y是一个函数，其中dom(f)为其定义域，cod(f)={f(x)

rEdom(f))为函数的值域:在集合S上长度为n的序列为一个函数σ{1.2，…，n}→S。若σ1)=a1，(2)=z，…=a，则σ=<a， a2…a>;S”为定义在集合S上所有任意长度有限序列的集合。

定义1事件、轨迹、事件日志。

给定A是一个活动的集合，一个轨迹σ∈A”是一系列的活动。对于1≤iso，表示轨迹。中的第i个事件，LEB(A”)是一个事件日志。一个事件日志记录了某个潜在业务流程的执行情况，该业务流程对应的业务流程模型即为流程挖掘的任务目标，因此并未在事件日志的定义中显式地出现。业务流程实例的执行情况由相应的轨迹表示，轨迹中的事件记录在事件日志中。

定义2流程发现。

设UM是所有流程模型的集合，一个流程发现方法指从一个事件日志LEB(A*)映射到一个流程模型pmEUM的函数r即r(L)=pm。一般来说，流程发现方法能够将事件日志转换为有标记的Petri网、业务流程建模标注(Business Process Modeling NotationBPMN)流程树等表示的流程模型。无论流程模型采用什么表示方法，输人事件日志中的每个轨迹都对应发现的流程模型中的一个可能的执行序列。

定义3 直接跟随活动关系。

假设事件日志L中的一条轨迹为 <ab.cef>.则 <a.b.c.e·f> 是σ的5个活动，如果活动b紧紧跟随在活动a之后，则称在轨迹o中从a到6存在直接跟随活动关系，记作<ab>。因此轨迹σ的直接跟随活动关系有4对，分别为<a，b>，<c,e>,<e,f>.

2 方法概述

本意提出两个研究目标:①寻找一种事件日志采样方法，使样本日志不仅具有足够的代表性，还能覆盖原始事件日志中的所有行为，而且相比已有采样方法更加高效

:2)分别从时间性能分析和模型质量评估两方面衡量样本日志相对于原始事件日志的质量。

目标①的解决方案提供了一种方法，即相比已有事件日志采样方法，将大规模事件日志更快更准确地采样为较小的样本日志，以便更高效地进行分析:目标②的答案用于验证事件日志采样方法的有效性和评估样本日志的质量，以证明事件日志采样方法的可行性。为了实现这些研究目标，图1展示了所用方法的概述，包括以下两个阶段:

(1)阶段1–事件日志采样

事件日志采样技术将一个事件日志LEB(A*)映射到另一个事件日志LEB(A·)中，其中LC L.L为原始事件日志，”“为L的一个样本日志，与原始事件日志L相比，L小得多，而且可以准确地代表 L。

本文提出的面向日志完备性的4种事件日志采样方法分别为完全遍历采样法、集合覆盖采样法、基于轨迹长度的采样方法、基于轨迹频次的采样方法。

(2)阶段2–采样技术的有效性评估

为验证4种事件日志采样方法的有效性，提出两种评估方法:

1)模型质量评估首先通过比较原始日志和样本日志的有向图是否相同。

间接地说明样本日志中的行为与原始事件日志中的代表性行为是否相同，若比较结果相同，则将原始日志与从样本日志中挖掘的模型进行拟合度计算[，拟合度值为1表示样本模型可以重新生成原始日志中的所有轨迹，低拟合度表明原始日志中的大部分行为不能被样本模型重演。此外，通过准确度20指标量化样本日志相对干原始日志的质量，准确度值为1表示样本模型生成的所有轨迹都包含在原始日志中，低精确度则表明样本模型允许原始日志外更多的行为。

最后，通过拟合度和准确度的调和平均值F-measure18来评价模型的优劣。

2)时间性能分析首先计算原始日志采样时间与样本日志挖掘时间之和，再将其与原始日志挖掘时间进行比较，原始日志采样时间与样本日志挖掘时间之和越短，采样效率越高，事件日志采样方法越高效，

3 业务流程事件日志采样

本章首先给出4种事件日志采样方法的具体思路，其次介绍两种实验评估方法。

下面给出一个示例日志(表示为L),用于介绍面向事件日志完备性的采样方法。

3.1 日志完备性采样方法

3.1.1 完全遍历采样法

完全遍历采样法的思路如下，从原始事件日志第一条轨迹开始依次遍历，若轨迹的直接跟随关系集合与日志直接跟随关系集合有交集，且满足轨迹的开始点与开始点集合有交集或轨迹的结束点与结束点集合有交集，则将该条轨迹加入样本日志，并删除以下3部分:日志直接跟随关系集合与新轨迹的直接跟随关系集合的交集:②开始点集合与新轨迹开始点的交集:3结束点集合与新轨迹结束点的交集。

直到日志直接跟随关系集合、开始点集合、结束点集合均为空，停止轨迹遍历。

完全遍历采样法的伪代码如算法l所示。

3.1.2 集合覆盖采样法

本文给出集合覆盖采样法的伪代码，如算法2所示。

集合覆盖采样法主要借助集合覆盖问题的贪婪算法求解思想，具体思路如下:首先遍历所有轨迹的直接跟随活动关系，选择一条覆盖了最多未覆盖直接跟随活动关系的轨迹(即与日志直接跟随活动关系集合拥有最大交集的轨迹);然后将所选轨迹加人样本日志，删除其覆盖的日志直接跟随活动关系、开始点与开始点集合的交集、结束点与结束点集合的交集;最后重复前两步，直到日志直接跟随活动关系集合、开始点集合结束点集合3个集合均为空集时结束遍历。

3.1.3基于轨迹长度的采样方法

定义4轨迹长度，轨迹σ的长度记为σ。日志中的所有事件是全序的，即整个日志可以看作为一个事件序列，然而整个日志的长度通常并不是该序列的长度，而是日志中所包含的轨迹数，因为轨迹是一个相对完整的逻辑单位。

假设一条轨迹a=<a,b,c,e,f>.a.b.c.e，f 是o的5个事件，则称L中 o的轨迹长度为5即σ=5日志L中第i条轨迹长度表示为 L。

根据定义4,基于轨迹长度的采样方法思想如下，首先统计原始事件日志中每条轨迹的长度，将轨迹和其对应的长度存储到一个集合中;然后按照轨迹长度降序排列，从最长的轨迹开始依次向下遍历，筛选样本日志轨迹的方法与完全遍历采样法相同。基于轨迹长度的采样方法伪代码如算法3所示。

3.1.4 基于轨迹频次的采样方法

定义5轨迹频次。轨迹频次L定义为在遍历事件日志L中所有轨迹时轨迹i出现的频次，即第几次出现。假设事件日志L=[00)，(2)0(30(2]1)，0(2)()为日志的3条轨迹，0+)的轨迹频次均为102)在日志L中出现两次，第1条因为是第1次出现，所以L2=1:第2条a2)是第2次出现，因此 L)=2。根据定义5.基于轨迹频次的采样方法思想如下:从原始事件日志的第1条轨迹开始，依次统计每条轨迹出现的次数，同时将轨迹和其对应的频次存储到一个集合中:统计完成后进行去重操作，只保留相同轨迹的频次最大值:最后按照轨迹频次降序排列，从频次最大的轨迹开始依次向下遍历，筛选样本日志轨迹的方法与完全遍历采样法相同。基干轨迹频次的采样方法伪代码如算法4所示。算法4基于轨迹频次的采样方法。

总结

怎么样做到采样降低样本率，同时又保证数据不少呢？

开源地址

为了便于大家学习，项目已开源。

Github: https://github.com/houbb/auto-log

Gitee: https://gitee.com/houbinbin/auto-log

小结

dubbo filter 模式非常的优雅，以前一直只是学习，没有将其应用到自己的项目中。

提供的便利性是非常强大的，值得学习运用。

参考资料

auto-log

https://mp.weixin.qq.com/s/rxyuxScPUYML-f5FhgNBpw

如何保证日志完备性？

LogRank 采样技术

日志采样和存储

https://mp.weixin.qq.com/s/cgDzA0cvUQJETL_fa8gGSQ

6个开源日志工具

https://mp.weixin.qq.com/s/6KVzR3JQzTnXNNUwwcZIPw

日志演尽之旅

https://mp.weixin.qq.com/s/D9dUPQk4ghz86yL5BTcIUw

日志收集器

https://mp.weixin.qq.com/s/8mCVk3gvXPOijTlcRjUR_w

业务背景
- 拓展阅读
摘要
引言
1 基础知识
2 方法概述
3 业务流程事件日志采样
- 3.1 日志完备性采样方法
- 总结
开源地址
小结
参考资料

autoLog-07-面向日志完备性的事件日志采集方法

业务背景

拓展阅读

摘要

引言