文占婷，王红伟，张建辉

（中国电子科技网络信息安全有限公司，四川 成都 610041）

0 引言

随着大数据及云计算的快速发展，越来越多的企业将业务迁移上云，产生了很多现代信息系统，促使流程挖掘技术得到了广泛应用。它能从信息系统中常见的事件日志中获取知识，发现、监测和改进实际系统行为模式。现有数据挖掘技术能够从标签化事件日志中发现流程模型，但实际应用中事件日志多为未标签化的，因此从未标签化的事件日志中提取事件模型，发现和监测系统中的实际行为具有重要意义。本文将基于云上用户行为产生的大量事件日志，通过数学概率方法和迭代的最大期望预估模型，设计了一种从未标签化的事件日志中挖掘出事件流的模型，可以实现对云上用户事件行为的有效审计。

1 流程挖掘面临的问题

现有的工作流的基本原理是由预先定义的流程模型控制，可实现执行一个业务流程的多个实例[1-2]。而流程挖掘[3]的目标是从一系列按运行时间排列的流程实例的行为中发现流程模型。假设这种流程挖掘是可行的，且所有的流程实例的运行都有相应的日志可被记录。这里所有的事件日志均需要包含格式为＜case id,task id＞的条目，其中case id 标识流程实例，task id 指定已执行的任务[3]。此类日志可以从工作流信息系统中获取，但更多的时候很多系统并不支持这种流程感知系统，因此获取相关日志变得相当困难，原因主要可以归纳如下。

（1）通常在记录大量云平台产生的事件产生的日志时未必会记录下它们的流程实例，所以大多数情况下case id 是不存在的，且大多数事件日志均为未标签化的日志。在一系列事件中，由于两个连续的事件可能来自不同的个流程实例，因此不确定两个事件是否有关，且对流程实例的具体数量是未知的。

（2）本文的目标是从未标签化的云日志中挖掘出事件，显然这种情况下发现的流程模型都是不确定的。

（3）云上系统存在大量日志且云上日志的获取相对比较容易，但是日志中的事件都是未知的，难以从云服务商处获得已知事件。

但是，事件流程具有独特的顺序模式[4]，所有的日志均是按照一定的顺序一遍遍重复产生的。基于这个前提，可以从大量未标签化的云平台产生事件日志中提取事件流的概率模型。

2 流程挖掘模型设计

2.1 流程挖掘模型的技术原理

假设K是某流程所生成的代表流程顺序的符号序列所对应的流程实例（以下称之为源）的个数。所有源的输出都记录在一份公共事件日志中。不同源产生的符号序列会彼此交织。假设x={x1,x2,…,xN}是长度为N的符号序列，其中每个符号xn来自K个源中的一个；假设s={s1,s2,…,sN}为未知的源序列，每个元素sn都代表符号xn是由它生成的。

为了仅从符号序列x单独挖掘出事件流程模型，将使用一阶马尔可夫链的概率方法，并用特定的开始（○）和停止（●）状态来增强结果。如图1所示，转移矩阵M展示了任意两个符号之间的转换条件概率。例如，在符号D之后产生符号E的概率由p(E/D)=M(D,E)=0.47 给出。从图1 中可以看出，除了最后一行表示停止状态，其他行中的概率加起来均为1.0。

图1 转移矩阵

特殊的起止符号并不是对应的具体序列符号，仅用于表示某流程以某些符号开始或者结束的概率。图1 中，p(○|…)=p(…|●)=p(●|○)=0，表示无法转换到开始状态，也无法从停止状态开始转换，也没有直接从开始状态直接转换到停止状态。

2.2 流程挖掘模型的核心技术

此部分详细介绍从给定的符号序列x中获得转移矩阵M和源序列s。由于整个计算过程涉及多个步骤，因此该部分分3 部分逐步介绍流程挖掘模型的关键算法。

2.2.1 计算转移矩阵M（给定s 和x）

如果同时给定了符号序列x和源序列s，则可以直接计算出如图1 所示的转换矩阵M。使用x和s，可以将x分离到每个源产生的符号序列。假设其中y(k)表示源K生成的长度为mk的符号序列的集合，●。将每个序列的相应位置都添加上开始状态和停止状态，同时sn=k，然后可以推导出每个序列的y(k)。

x和s的联合概率可以表示为：

对于给定的符号对a和b，采用M的最大似然值得出令p(x；s)的值达到最大的M^ (a,b)的表达式为：

式中，a和b为对应的符号序列中的任意两个不同的符号，η(a,b)(y(k))表示在符号序列y(k)中，出现从a转换成b的次数。

假设云上事件日志的符号序列x为：

如图2 所示，可以看到如下结论：

图2 云平台日志记录

因此，根据式（2）可以计算出：

计算结果和2.1 节给出的结果一样。根据该方法可以计算出转移矩阵M，结果如图1 所示。

2.2.2 计算源序列s（给定x 和M）

如果已知M，可以通过给出的符号序列x计算出源序列s。原则上，应该要找到使x和s的联合概率p(x；s)最大的最优资源序列但是得到最优ŝ 需要根据式（1）计算所有有可能的源序列才能找到使p(x；s)最大的序列符号集合y(k)。因此，实际中用贪婪算法（Greedy Algorithm）[5]找的近似值（用表示）即可。算法核心思想如下。

（1）假设知道每一个源k的前一个符号εk，用k计算能够产生具有最高转移概率的xn，将xn分 配 给 源k，用 此 方 法 得 到即

（2）假设每个源不会多次产生相同的符号（否则将分x配给各个源变得更加困难），然后将εk更新为xn，找出xn+1，最终得到，以此类推，直到x中的所有符号都分配给某个源为止。

另外，无论xn在哪个位置，如果M(○,xn)的值高于所有k源中的M(εk,xn)值，则创建一个新的源序列，再将xn添加到新的源序列中。无论xn在哪个位置，若M(xn,●)的值比所有其他的符号的转移概率都高，那么源sn就被看作已经结束。

输入：符号序列x和转移矩阵M

2.2.3 计算转移矩阵M 和源序列s（给定x）

假设每个源不会多次产生相同的符号，根据式（2）和提到的贪婪算法，可以在仅给定符号序列x时估算出转移矩阵M和源序列s。它的核心算法是最大期望算法，即估算的最大期望算法。

输入：符号序列x

该算法描述如下。

该算法本质上是在源s缺失时用最大期望算法（Expectation-Maximization Algorithm，EM）[6-7]从不完整数据x中估算出M，其中最大的问题是如何初始化最简单的方法是随机初始化只要满足即可。然而，这种随机初始化只能得到次优解，需要一个更好的方法来初始化得到的一个最优解。

假设：

式中，η(a,b)表示在符号序列x中从a转换成b的次数（a、b为相邻符号）。根据式（9），仅需要x即可得到M。

因为序列中一致行为的转移概率更高，即使x是多个互相交错的源序列中的序列符号，依然可以计算出M，因此M+是对M估算最好的算法模型。

2.3 流程挖掘模型

云操作系统中存在大量的可用日志。通过分析日志能够提取出事件日志中的单个操作行为，进而完成对云上用户行为的审计。基于日志流的流程挖掘模型，如图3 所示。

图3 基于日志流的流程挖掘的模型

2.3.1 日志采集模块

日志采集模块负责从云平台中收集原始日志及云平台上的租户、用户、资产、业务信息，并将采集到的数据作为整个流程挖掘过程的输入。

2.3.2 日志聚类

由于日志数据都是未标记的，因此需要使用无人监督的聚类方法（如K-means）。聚类结果除了那些属性值，一般包含一些附加属性值，如实例数和聚类数，本文不做重点介绍。

2.3.3 日志过滤

考虑到云上日志的多样性以及会重复产生大量的无用日志，为了提高流程挖掘的准确性和高效性，需要在流程挖掘前过滤掉大量的无用日志。“日志聚类”模块的输出有大、小两种聚集。大的聚集可能包含大量的云系统日志中的操作噪音；小的聚集大多数是有效日志信息，会保留，因此大的聚集会被过滤掉。

在过滤掉不需要的云系统日志条目后，对上述保留的小聚集的日志进行标记。例如，有5 个小日志聚集，则可分别用A、B、C、D、E 作为其日志聚集的标识。这个聚集标识将作为其聚集内的所有日志的符号序号，将所有日志符号序号按照日志发生的时间进行排序，最终得到可以表示日志序列的符号序列，如“ABEBD”等，并将符号序列作为流程挖掘模型的输入。

2.3.4 流程挖掘

流程挖掘模块主要是从日志符号序列中挖掘出事件流程，具体实现过程如图4 所示。

流程挖掘模型的流程说明如下：

（1）输入日志符号序列x；

（2）根据x计算初始转移矩阵

（3）根据贪婪算法，由日志符号序列x和转移矩阵计算源序列s；

（4）由日志符号序列x和第3 步得出的过程模型s计算转移矩阵M1；

（5）比较M1和如果则s为所得源序列保存下来，否则，跳转到步骤3，直至所有符号序列x都处理完成，结束流程。

根据上述流程计算出s（此处的s是去重之后的结果）：

图4 流程挖掘模块流程

图5 从未标记的符号序列估算转移矩阵

图6 挖掘出的流程估算模型

3 结语

本文主要从对未标签化日志中提取出事件行为的需求出发，描述了以最大期望算法为核心，估算出转移矩阵M。该转移矩阵M表示从未标签化的事件流日志中挖掘出的过程模型。该流程挖掘算法可以从一系列事件日志中分离出多个随机交织的事件流程。本文提到的方法也可用于标签化的事件日志。同时，由于M是一阶马尔可夫模型，因此它可能无法表示某些工作流程模型。如果是标签化的日志，就可利用其完善现有的流程挖掘模型，使其能够适用于其他类型的模型。因此，本文提出的流程挖掘模型对于从海量未标签化的事件日志中提取事件行为具有重要的参考意义。