一种基于关联关系的双粒度噪声日志过滤方法

摘要

本发明公开了一种基于关联关系的双粒度噪声日志过滤方法。该方法基于局部依赖度和全局依赖度计算得到混合依赖度，通过本发明方法能够同时实现日志中噪声事件的细粒度过滤和噪声轨迹的粗粒度过滤。相比于传统的日志过滤方法，本发明具有如下收益：1、采用了双粒度过滤机制，对于不同的噪声情景使用不同的过滤机制，从而在尽可能保留原始日志数据的情况下实现了优秀的过滤效果；2、使用过滤后的日志文件用于流程挖掘能极大提高流程发现模型的精度，增强了模型的可理解性。

说明书

技术领域

本发明涉及流程挖掘领域，尤其涉及一种基于关联关系的双粒度噪声日志过滤方法。

背景技术

流程挖掘旨在从过程感知信息系统记录的事件日志中提取有用的信息来帮助利益相关者了解流程的实际执行情况。流程发现作为流程挖掘的重要部分，其作用在于构建可以重现事件日志记录行为的流程模型。高精度模型可以直观地展现出业务流程的实际执行情况。

在业务流程管理系统中，业务流程的活动是依照精心设计的流程模型执行的，这些活动的执行将被记录在日志中，来帮助利益相关者分析和监控流程的执行。在现实生活中，大多数业务流程的都没有标准化的流程模型，或者是随着业务流程的不断演进流程模型与当前的业务流程存在较大的差异，因此人们需要依靠流程发现技术从流程产生的日志中提取流程的实际执行行为。但是，日志中存在的噪声会对流程发现模型的质量产生负面影响。如果使用流程发现技术对包含噪声的日志进行流程发现会导致其发现模型产生不可见任务和非自由选择结构，从而增加了挖掘模型的复杂性与可理解性。常见的日志噪声有如下几类：缺失型噪声事件(流程中的某些事件由于某些原因未被记录在日志中)，冗余型噪声事件(流程中某些事件被多次重复记录)，错位型噪声事件(某些事件在流程轨迹中发生的顺序位置被记录错误)。

噪声过滤算法可以有效的过滤掉日志中的噪声事件，大大提高流程发现模型的精度。目前的日志噪声过滤算法根据其过滤粒度可大致分为两类，粗粒度过滤和细粒度过滤。其中粗粒度过滤将包含噪声事件的轨迹直接移除原始日志，但是对于规模较小的日志数据来说移除整条轨迹可能会对挖掘的模型结构产生较大的改变。细粒度过滤则只将噪声事件移除，保留该轨迹上的其他事件，但是在移除噪声事件的同时不能保证该行为不会为轨迹带来新的噪声，同时该类算法也无法解决缺失型噪声事件产生的问题。

发明内容

为了克服上述现有技术的不足，本发明提供一种基于关联关系的双粒度噪声日志过滤方法，可有效解决上述问题。本发明具体采用的技术方案如下：

一种基于关联关系的双粒度噪声日志过滤方法，包括以下步骤：

(1)输入原始日志文件，对其进行数据预处理后生成由多条流程轨迹σ组成的一个日志集合每条流程轨迹由多个流程事件e_i组成σ＝<e₁,…,e_n>，记所有流程轨迹中所有流程事件e的集合为ε，即e∈ε；

(2)统计日志集合中所有流程轨迹中两两流程事件之间的频次依赖度DFD(e_i,e_j)；

(3)进一步计算出两两事件之间的局部依赖度Dep_local(e_i,e_j)，全局依赖度Dep_global(e_i,e_j)以及混合依赖度Dep_mixed(e_i,e_j)；

所述局部依赖度Dep_local(e_i,e_j)计算公式如下：

其中C₁、C₂为常数，D_suc(e_i)表示后继密度，即事件e_i的所有后继事件发生的平均频次；D_pre(e_j)表示前驱密度，用于表示事件e_j的所有前驱事件发生的平均频次；后继密度和前驱密度的计算公式如下：

D_pre(e_k)＝N_pre(e_k)/|U_pre(e_k)|

D_suc(e_k)＝N_suc(e_k)/|U_suc(e_k)

其中D_pre(e_k)为事件e_k的前驱密度，D_suc(e_k)为事件e_k的后继密度，N_pre(e_k)为以事件e_k为后继事件的跟随关系的数量，N_suc(e_k)为事件e_k为前趋事件的跟随关系的数量，U_pre(e_k)为事件e_k的前驱集合，|U_pre(e_k)|为事件e_k的前驱集合中的事件种类数，U_suc(e_k)为事件e_k的后继集合，|U_suc(e_k)|事件e_k的后继集合中的事件种类数；

所述全局依赖度Dep_global(e_i,e_j)计算公式如下：

θ＝Max{DFD(e_x,e_y)}

其中ζ为全局噪声因子，用于划分全局噪声事件。

所述混合依赖度Dep_mixed(e_i,e_j)计算公式如下：

Dep_mixed(e_i,e_j)＝α*Dep_local(e_i,e_j)+(1-α)*Dep_global(e_i,e_j)

其中α权衡因子，用于平衡全局依赖度和局部依赖度的占有比例。

(4)依据上一步中计算的混合依赖度构建日志集合中所有流程事件的混合依赖矩阵

(5)开展日志噪声过滤，具体包含以下步骤：

51)构建一个空的日志集用于存放过滤后的轨迹；

52)取出日志集的一条轨迹σ，将σ的遗弃值初始化为1；

53)获取σ的开始事件e_start并将开始事件e_start添加到一个空的事件序列σ_filter中；

54)依照σ中的事件序列取出当前事件e_i；

55)取出轨迹中当前事件的下一事件e_i+1；

56)在中搜寻到e_i和e_i+1的混合依赖度Dep_mixed(e_i,e_i+1)，首先执行事件的细粒度过滤操作，如果Dep_mixed(e_i,e_i+1)的值不小于混合度阈值β，事件e_i+1被判定为正常事件，将其添加到轨迹σ_filter，e_i+1成为当前事件，下标i＝i+1，并返回步骤55)；如果Dep_mixed(e_i,e_i+1)的值小于混合度阈值β，事件e_i+1被判定为噪声事件，使用惩罚函数修改轨迹σ的遗弃值惩罚函数公式如下：

其中为惩罚因子，决定惩罚函数的惩罚力度；

若修正后的遗弃值不低于设定的遗弃阈值则返回步骤55)；若修正后的遗弃值低于遗弃阈值则执行轨迹的粗粒度过滤操作，轨迹σ被判定为噪声轨迹，返回步骤52)；

57)如果事件e_i+1为当前轨迹σ的结束事件e_end，则将过滤轨迹σ_filter添加到过滤日志集中；

58)重复步骤52)～步骤57)，直到原始日志集中的所有轨迹均被取出；

59)输出过滤日志集

(6)根据输出的过滤日志集重新生成日志文件。

作为优选，步骤(1)中所述的日志集合包含了业务流程的全部执行实例，即其中的每条流程轨迹σ都与业务流程的一次执行实例相对应，所述流程轨迹σ是由多个流程事件e组成的有序序列，所述流程事件e是业务流程执行活动的一次记录。

作为优选，步骤(2)中所述的频次依赖度DFD(e_i,e_j)表示直接跟随度，即在全部流程实例中事件e_j紧随事件e_i发生的总频次。

作为优选，步骤(3)中所述的全局噪声因子ζ取0.02。

作为优选，步骤(5)中所述的混合度阈值β取0.5。

作为优选，步骤(5)中所述的权衡因子取值α取0.5。

作为优选，步骤(5)中所述的惩罚因子取0.8。

作为优选，步骤(5)中所述的遗弃阈值取0.7。

本发明提出的过滤方法从全局和局部两个角度来考虑事件间的依赖关系，并以此判断事件是否是噪声事件。相比于传统的日志过滤方法，本发明具有如下收益：1、采用了双粒度过滤机制，对于不同的噪声情景使用不同的过滤机制，从而在尽可能保留原始日志数据的情况下实现了优秀的过滤效果；2、使用过滤后的日志文件用于流程挖掘能极大提高流程发现模型的精度，增强了模型的可理解性。

附图说明

图1为本发明基于关联关系的双粒度噪声日志过滤方法的流程图；

图2为本发明噪声过滤的实例示意图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

相反，本发明涵盖任何由权利要求定义的在本发明的精髓和范围上做的替代、修改、等效方法以及方案。进一步，为了使公众对本发明有更好的了解，在下文对本发明的细节描述中，详尽描述了一些特定的细节部分。对本领域技术人员来说没有这些细节部分的描述也可以完全理解本发明。

如图1所示，本发明的一种基于关联关系的双粒度噪声日志过滤方法，包括以下步骤：

(1)输入原始日志文件，对其进行数据预处理后生成由多条流程轨迹σ组成的一个日志集合每条流程轨迹由多个流程事件e_i组成σ＝<e₁,…,e_n>，记所有流程轨迹中所有流程事件e的集合为ε，即e∈ε；

日志集合包含了业务流程的全部执行实例，即其中的每条流程轨迹σ都与业务流程的一次执行实例相对应，每条流程轨迹σ是由多个流程事件e组成的有序序列，流程事件e是业务流程执行活动的一次记录。

(2)统计日志集合中所有流程轨迹中两两流程事件之间的频次依赖度DFD(e_i,e_j)。

频次依赖度DFD(e_i,e_j)表示直接跟随度，即在全部流程实例中事件e_j紧随事件e_i发生的总频次。

(3)进一步计算出两两事件之间的局部依赖度Dep_local(e_i,e_j)，全局依赖度Dep_global(e_i,e_j)以及混合依赖度Dep_mixed(e_i,e_j)；

所述局部依赖度Dep_local(e_i,e_j)计算公式如下：

其中C₁、C₂为常数，D_suc(e_i)表示后继密度，即事件e_i的所有后继事件发生的平均频次；D_pre(e_j)表示前驱密度，用于表示事件e_j的所有前驱事件发生的平均频次；后继密度和前驱密度的计算公式如下：

D_pre(e_k)＝N_pre(e_k)/|U_pre(e_k)|

D_suc(e_k)＝N_suc(e_k)/|U_suc(e_k)|

其中D_pre(e_k)为事件e_k的前驱密度，D_suc(e_k)为事件e_k的后继密度，N_pre(e_k)为以事件e_k为后继事件的跟随关系的数量，N_suc(e_k)为事件e_k为前趋事件的跟随关系的数量，U_pre(e_k)为事件e_k的前驱集合，|U_pre(e_k)|为事件e_k的前驱集合中的事件种类数，U_suc(e_k)为事件e_k的后继集合，|U_suc(e_k)|事件e_k的后继集合中的事件种类数；

所述全局依赖度Dep_global(e_i,e_j)计算公式如下：

θ＝Max{DFD(e_x,e_y)}

其中ζ为全局噪声因子，用于划分全局噪声事件，取0.02。

所述混合依赖度Dep_mixed(e_i,e_j)计算公式如下：

Dep_mixed(e_i,e_j)＝α*Dep_local(e_i,e_j)+(1-α)*Dep_global(e_i,e_j)

其中α权衡因子，用于平衡全局依赖度和局部依赖度的占有比例，取0.5。

(4)依据上一步中计算的混合依赖度构建日志集合中所有流程事件的混合依赖矩阵

(5)开展日志噪声过滤，具体包含以下步骤：

51)构建一个空的日志集用于存放过滤后的轨迹；

52)取出日志集的一条轨迹σ，将σ的遗弃值初始化为1；

53)获取σ的开始事件e_start并将开始事件e_start添加到一个空的事件序列σ_filter中；

54)依照σ中的事件序列取出当前事件e_i；

55)取出轨迹中当前事件的下一事件e_i+1；

56)在中搜寻到e_i和e_i+1的混合依赖度Dep_mixed(e_i,e_i+1)，首先执行事件的细粒度过滤操作，如果Dep_mixed(e_i,e_i+1)的值不小于混合度阈值β(取0.5)，事件e_i+1被判定为正常事件，将其添加到轨迹σ_filter，e_i+1成为当前事件，下标i＝i+1，并返回步骤55)；如果Dep_mixed(e_i,e_i+1)的值小于混合度阈值β，事件e_i+1被判定为噪声事件，使用惩罚函数修改轨迹σ的遗弃值惩罚函数公式如下：

其中为惩罚因子，决定惩罚函数的惩罚力度，取0.8；

若修正后的遗弃值不低于设定的遗弃阈值则返回步骤55)；若修正后的遗弃值低于遗弃阈值则执行轨迹的粗粒度过滤操作，轨迹σ被判定为噪声轨迹，返回步骤52)。遗弃阈值取0.7。

57)如果事件e_i+1为当前轨迹σ的结束事件e_end，则将过滤轨迹σ_filter添加到过滤日志集中；

58)重复步骤52)～步骤57)，直到原始日志集中的所有轨迹均被取出；

59)输出过滤日志集

(6)根据输出的过滤日志集重新生成日志文件。

下面基于上述方法流程，通过实施例进一步展示其技术效果。

实施例

本实施例步骤与具体实施方式前述步骤相同，在此不再进行赘述。下面就部分实施过程和实施结果进行展示：

数据源获取：本实施例所用的原始日志文件使用java工具包JDOM读取日志文件，取得日志文档的根节点root，获取root节点下名为Process的子节点元素，进一步再获取Process节点下名为ProcessInstance的全部子节点元素。一个ProcessInstance节点包含了流程一次执行实例的全部信息，它通常拥有多个名为AuditTrailEntry的节点元素，流程实例中发生的每一个事件的详细信息都被记录在一个AuditTrailEntry节点元素中，这些AuditTrailEntry节点包含了很多事件属性，如时间戳属性，事件名属性，资源属性等。对这些事件信息进行筛选并剔除其中的冗余信息后保留了事件的事件名属性，并将同一实例的事件按照开始时间戳属性排序，最后保存为一条流程轨迹σ＝<e₁,…,e_n>，并将该轨迹相对应的ProcessInstance节点元素的id属性赋予该轨迹作为其轨迹id，将日志中全部的轨迹构成的多集即原始日志集保存。

图2详细展示了运用本发明方法对两条轨迹(实例1和实例2)进行基于关联关系的双粒度噪声日志过滤的具体过程：

实例1轨迹σ₁＝<ABCDEFGH>

1)获取σ₁的开始事件A并将其添加至空轨迹序列σ_f中；

2)取出事件A的下一事件B，计算事件AB的混合关联度Dep_mixed(A,B)＝0.80，大于混合度阈值0.5，因此事件B为正常事件(非噪声事件)，将其添加至序列σ_f中；

3)取出事件B的下一事件C，计算事件BC的混合关联度Dep_mixed(B,C)＝0.75，大于混合度阈值0.5，因此事件C为正常事件(非噪声事件)，将其添加至序列σ_f中；

4)取出事件C的下一事件D，计算事件CD的混合关联度Dep_mixed(C,D)＝0.85，大于混合度阈值0.5，因此事件D为正常事件(非噪声事件)，将其添加至序列σ_f中；

5)取出事件D的下一事件E，计算事件DE的混合关联度Dep_mixed(D,E)＝0.87，大于混合度阈值0.5，因此事件E为正常事件(非噪声事件)，将其添加至序列σ_f中；

6)取出事件E的下一事件F，计算事件EF的混合关联度Dep_mixed(E,F)＝0.26，小混合度阈值0.5，因此事件F为噪声事件，不将其添加至序列σ_f中；使用惩罚函数修改轨迹σ₁的遗弃值计算得到为0.9，大于遗弃阈值0.7，因此σ₁为正常轨迹(非噪声轨迹)；

7)取出事件F的下一事件G，计算事件EG的混合关联度Dep_mixed(E,G)＝0.87，大于混合度阈值0.5，因此事件G为正常事件(非噪声事件)，将其添加至序列σ_f中；

8)取出事件G的下一事件H，计算事件GH的混合关联度Dep_mixed(G,H)＝0.85，大于混合度阈值0.5，因此事件H为正常事件(非噪声事件)，将其添加至序列σ_f中；

9)事件H为当前轨迹σ₁的结束事件，则使用本方法进行过滤后的轨迹为σ_f＝<ABCDEGH>，将其添加至过滤日志集中。

实例2轨迹σ₂＝<ABCEGH>

1)获取σ₂的开始事件A并将其添加至空轨迹序列σ_f中；

2)取出事件A的下一事件B，计算事件AB的混合关联度Dep_mixed(A,B)＝0.80，大于混合度阈值0.5，因此事件B为正常事件(非噪声事件)，将其添加至序列σ_f中；

3)取出事件B的下一事件C，计算事件BC的混合关联度Dep_mixed(B,C)＝0.75，大于混合度阈值0.5，因此事件C为正常事件(非噪声事件)，将其添加至序列σ_f中；

4)取出事件C的下一事件E，计算事件CE的混合关联度Dep_mixed(C,E)＝0.26，小于混合度阈值0.5，因此事件E为噪声事件，不将其添加至序列σ_f中；使用惩罚函数修改轨迹σ₂的遗弃值计算得到为0.9，大于遗弃阈值0.7，因此σ₂为正常轨迹(非噪声轨迹)；

5)取出事件E的下一事件G，计算事件CG的混合关联度Dep_mixed(C,G)＝0.01，小于混合度阈值0.5，因此事件G为噪声事件，不将其添加至序列σ_f中；使用惩罚函数修改轨迹σ₂的遗弃值计算得到为0.72，大于遗弃阈值0.7，因此σ₂为正常轨迹(非噪声轨迹)；

取出事件G的下一事件H，计算事件CH的混合关联度Dep_mixed(C,H)＝0.01，小于混合度阈值0.5，因此事件H为噪声事件，不将其添加至序列σ_f中；

使用惩罚函数修改轨迹σ₂的遗弃值计算得到为0.58，小于遗弃阈值0.7，因此σ₂为噪声轨迹，不将其添加至噪声日志集中。