写在前面：episode pattern挖掘不同于itemset pattern挖掘，其复杂程度是远远超过itemset，首先“情节”意味着一系列事件的发生，在一段时间内有多个itemset产生，这些itemset之间可能先后发生，也可能同时发生。也就是说episode挖掘不仅要考虑横向的事件序列，而且还要结合纵向事件集。

Mining High Utility Episodes in Complex Event Sequences

定义

情节（episode）挖掘是从频度（Frequent）计算开始研究，所以这里介绍一些基础定义

Frequent 类

• 简单事件序列（Simple event sequence）：设 $\varepsilon = \lbrace E_1, E_2, \dots, E_{\rm m}\rbrace$ 是有限个事件的集合，简单事件序列 $SS = <(E_1, T_1), (E_2, T_2), \dots, (E_{\rm m}, T_{\rm m})>$ 是一组事件的有序序列，其中每一个事件 $E_{\rm i} \in \varepsilon$ 都与一个时间点 $T_{\rm i} \in N^+$ 相关联。例如下图（Figure 1.）中：

  

• 简单情节（Simple episode）：简单情节 $\alpha$ 是一组非空有序事件集合。例如在图（FIgure 1.）中 $<(A), \, (C)>$ 就是一个简单情节

• 同时事件集（Simultaneous event set）：同时事件集 $SE = (E_1, E_2, \dots, E_{\rm m})$ 是指在同一个时间点 $T_{\rm i}$ 上发生的一组事件。

• 复杂事件序列（Complex event sequence）：复杂事件序列 $CS = <(SE_1, T_1), (SE_2, T_2), \dots,$ $(SE_{\rm n}, T_{\rm n})>$ 是一系列有序事件集合，里面有多个同时事件集，各个同时事件集又组成一个事件序列 。例如下图（Figure 2.）中所示：

  

• 长度和大小（Length and Size）：事件情节 $\alpha$ 的长度定义为 (其实就是该集合里事件的个数)，称为 $k$-episode；而事件情节 $\alpha$ 的大小等于该情节中同时事件集合的个数。例如：$<(AB), (C)>$ 就是大小为2的3-episode

• 发生（Occurrence）：给定一个情节 ，当1）情节 $\alpha = <(SE_1), (SE_2), \dots, (SE_{\rm m})>$ 发生在时间段 [$T_{\rm s}, T_{\rm e}$]；2）情节 $\alpha$ 的第一个同时事件集 $SE_1$ 发生在 $T_{\rm s}$ 时间点，最后一个同时事件集 $SE_{\rm m}$ 发生在 $T_{\rm e}$ 时间点，那么称情节 $\alpha$ 的发生在时间间隔 [$T_{\rm s}, T_{\rm e}$] 上。其中，情节 $\alpha$ 的所有发生时间段组成集合 $occSet(\alpha)$ 。例如：在图（Figure 2.）中 $occSet(<(AB), (C)>) = \lbrace [1,2], [1,3], [1,6], [1,7], [5,6], [5,7]\rbrace$

• 最短发生时间段（Minimal occurrence）：给定情节 $\alpha$ 的两个时间间隔 [$T_{\rm s}, T_{\rm e}$], [$T_{\rm s}’, T_{\rm e}’$]，[$T_{\rm s}’, T_{\rm e}’$] 是 [$T_{\rm s}, T_{\rm e}$] 的子集：当1）情节 $\alpha$ 的发生在[$T_{\rm s}, T_{\rm e}$]时间段上；2）[$T_{\rm s}’, T_{\rm e}’$] 不存在子集。最短发生时间段记为 $mo(\alpha)$。其中，情节 $\alpha$ 的所有最短发生时间段组成集合 $moSet(\alpha)$。例如：情节 $<(AB), (C)>$ 的最短发生时间段 [1,2]，且 $moSet(<(AB), (C)>) = \lbrace [1,2], [5,6]\rbrace$

• 情节支持度（Support of an episode）：情节 $\alpha$ 的支持度 $SC(\alpha)$ 定义为在最短发生时间段集 $moSet(\alpha)$ 中最短发生时间段的个数（Ps. 也就是在这个时间段发生了一次），支持率的定义为在CS中 $SC(\alpha)$ 与时间点的比值

• 频繁情节（Frequent episode）：当一个情节的支持度不低于用户设置的支持度阈值（$minSup$），那么该情节称为频繁情节。

论文中也提到为什么要设计新的效用（Utility）挖掘来替代频度挖掘：一是频度表达的意义太过狭隘（比如钻石和面包案例），二是基于频度很难讨论事件并行（同时）发生（Simultaneous occurrence）的这种情况（定义在同一个时间点上只有一个事件发生一次）

Utility 类

设 $CS = <(t_{SE_1}, T_1), (t_{SE_2}, T_2), \dots, (t_{SE_{\rm n}}, T_{\rm n})>$，其中 $T_{\rm i} \in N^+$，每个事件 $E_{\rm i} \in \varepsilon$ 都关联利润 $p(E_{\rm i}, CS)$（外部效用）和数量 $q(E_{\rm i}, T_{\rm i})$（内部效用）。如下表 （Table 1.）和图（Figure 3.）分别表示各事件的外部效用和内部效用

• 某个时间点的事件效用（Utility of an event at a time point）：在某个时间点 $T_{\rm i} \in N^+$ 下某个事件 $E_{\rm i}$ 的效用定义为 $u(E_{\rm i}, T_{\rm i}) = p(E_{\rm i}, CS) \times q(E_{\rm i}, T_{\rm i})$ （利润 $\times$ 数量）

• 某个时间点并行发生事件集的效用（Utility of a simultaneous event set at a time point）：在某个时间点 $T_{\rm i} \in N^+$ 下并行（同时）发生事件集 $SE = (E_1, E_2, \dots, E_{\rm n})$ 的效用定义为 $u(SE, T_{\rm i}) = \sum_{j = 1}^{n}u(E_{\rm j}, T_{\rm i})$

• 基于复杂事件序列数据集的总效用（Total utility of database complex event sequence）：基于复杂事件序列 $CS$ 的总效用定义为 $u(CS) = \sum_{i = 1}^{n}u(SE_{\rm i}, T_{\rm i})$

• 关于最短发生时间段的情节效用（Utility value of an episode w.r.t its minimal occurrence）：设 $mo(\alpha) = [T_{\rm s}, T_{\rm e}]$ 是情节 $\alpha = <(SE_1, SE_2, \dots, SE_{\rm n})>$ 的最短发生时间段，其中每一个并行发生事件集 $SE_{\rm i} \in \alpha$ 都与某一个时间点 $T_{\rm i} \in N^+$ 相关联。关于最短发生时间段的情节效用定义为 $u(\alpha, mo(\alpha)) = \sum_{i = 1}^{n}u(SE_{\rm i}, T_{\rm i})$

• 基于复杂事件序列情节的效用（Utility of an episode in a complex event sequence）：设 $moSet(\alpha) = [T_{\rm I_1}, T_{\rm I_2}, \dots, T_{\rm I_n}]$ 是关于情节 $\alpha$ 的最小发生集。而基于复杂时间序列 $CS$ 的情节效用定义为 $uv(\alpha, CS) = \sum_{i = 1}^{n}u(\alpha, T_{\rm I_n})$，并且有 $u(\alpha) = uv(\alpha) / u(CS)$

• 最长持续时间（Maximum time duration）：设 $MTD$ 是用户预先设定的最长持续时间, $mo(\alpha) = [T_{\rm s}, T_{\rm e}]$ 是情节 $\alpha$ 的最短发生时间段。当 $(T_{\rm e} - T_{\rm s} + 1) \le MTD$，称 $mo(\alpha)$ 受 $MTD$ 的约束（或者是满足）（Ps. MTD起着时间窗口的作用，因为我们要计算就必须划定好一个范围，否则无穷大时间段或无穷小都不利于我们研究）

• 并行和串行连接（Simultaneous and serial concatenations）：设 $\alpha = <(SE_1), (SE_2), \dots, (SE_{\rm x})>$, $\beta = <(SE_1’), (SE_2’), \dots, (SE_{\rm y}’)>$ $\alpha$ 和 $\beta$ 的并行连结定义为 $simul$-$concat(\alpha, \beta) = <(SE_1),(SE_2)$, $\dots, (SE_{\rm x} \cup SE_1’), (SE_2’), (SE_{\rm y}’)>$，$\alpha$ 和 $\beta$ 的串行连接定义为 $serial$-$concat(\alpha, \beta) = <(SE_1), (SE_2) \dots, (SE_{\rm x}), (SE_1’), (SE_2’), \dots, (SE_{\rm y}’)>$ （Ps. 两种都是扩展项集，只是结合形式不一样）

• 高效用情节（High Utility Episode）：当情节 $E_{\rm i}$ 的效用值 $u(E_{\rm i}) \ge minUtil$，则被视作是我们要的pattern（HUE），否则不是

• 情节效用权重（Episode-Weighted Utilization of an episode）：设 $moSet(\alpha) = [T_{\rm I_1}, T_{\rm I_2}, \dots, T_{\rm I_n}]$ ，且$T_{\rm I_i} \in moSet(\alpha)$ 满足 $MTD$ 约束。那么基于复杂事件序列 $CS$ 的情节 $\alpha$ 效用权重 $EWU(\alpha) = \sum_{i = 1}^{n}EWU(\alpha, T_{\rm I_i}) / u(CS)$。例如：设 $MTD = 3, \alpha = <(A), (C)>$，那么 $EWU(<(A), (C)>) = [u((AB), T_1) + u((BC), T_2) + u((C), T_3)] + [u((AB), T_5) + u((CD), T_6) + u((C), T_7)] / u(CS) = 40 / 40$

  

• 关于最短发生时间段的情节权重效用（Episode-Weighted Utilization of an episode w.r.t a minimal occurrence）：设 $mo(\alpha) = [T_{\rm s}, T_{\rm e}]$ 是情节 $\alpha = <(SE_1), (SE_2), \dots, (SE_{\rm n})>$ 最短发生时间段，其中 $mo(\alpha)$ 受 $MTD$ 的约束。那么在 [$T_{\rm s}, T_{\rm e}$] 下情节 $\alpha$ 的情节权重效用 $EWU(\alpha, mo(\alpha)) =$ $\sum_{i = 1}^{n}u(SE_{\rm i}, T_{\rm i}) + \sum_{i = e}^{(s + MTD - 1)}u(t_{SE_{\rm i}}, T_{\rm i})$，其中 $t_{SE_{\rm i}}$ 是在 $CS$ 中同时事件集的时间点 $T_{\rm i}$ 。例如：设 $MTD = 4, \alpha = <(C), (A)>, mo(<(C), (A)>) = [3,5]$，那么 $EWU(<(C), (A)>, [3, 5]) = [u((C), T_3)] + [u((AB), T_5) + u((CD), T_6)] = 25$

• 高权重效用情节（High Weighted Utilization Episode）：当一个情节 $\alpha$ 的 $EWU(\alpha) \ge minUtil$ 时，该情节称为高权重效用情节（HWUE），也就是下一条定义的候选事件

• 候选事件（Promising event）：当 $EWU(e) \ge minUtil$ 时，该事件 $e$ 是候选事件，需要进一步计算其epsiode utility来准确判断。否则是 unpromising event，当 $\alpha$ 是非候选事件时，对任意情节 $\beta$，它们的超集 $\gamma$ 都是低效用的。

• 情节权重的向下闭合性（Episode-Weighted Downward Closure property (EWDC)）：设 $\alpha$ 和 $\beta$ 都是情节，且 $\gamma = simul$-$concat(\alpha, \beta)$ 或 $serial$-$concat(\alpha, \beta)$，当 $EWU(\alpha) < minUtil$ 时，$\gamma$ 是低效用情节

策略

Discarding Global unpromising Events(DGE)

利用情节权重的向下闭合性，在最开始移除掉那些非有效事件，以达到优化算法的目的。

Discarding Local unpromising Events(DLE)

利用情节权重的向下闭合性，在运算过程中（比如在剪枝、排序后的数据集）移除掉那些非有效事件，以达到优化算法的目的

算法

主体算法的思想是老规矩：找到一个长度为1的情节，然后把这个事件作为前缀再添加其它事件检查能否成为HEWU，需要注意的是每次扩展一个事件，这个事件的时间不能与前缀时间相差超过MTD

UP-Span：

MiningSimultHUE：

主要负责挖掘当前事件集的并发事件

MiningSerialHUE：

主要负责挖掘当前事件集的连续事件

个人总结

在学习了High-Utility Pattern Mining类算法后理解上并不是很难，大多定义加上了时间这个维度。从伪代码上来看该算法整体也不是很复杂，思路与HUI-Miner算法的思路大致一样，只是在这方面目前的研究比较少，还有很大的扩展空间。 该文献是第一个提出基于情节的高效用项挖掘概念，并成功实现。缺陷在于仅仅把提出的EWU作为边界值，难免太过模糊，会产生许多原本不需要的候选集。还需要使用更好的剪枝算法如FHM中使用的或更改数据存储结构，提高检索效率