序列模式规则生成与监督学习技术解析

# 序列模式规则生成与监督学习技术解析 ## 1. 序列模式规则生成 ### 1.1 生成序列模式 给定序列数据库，通过特定算法生成序列模式。例如，对于序列集合 \(S1 = \{〈\{40\}\{30\}\{40, 60\}〉, 〈\{30\}\{20, 40\}\{40, 100\}〉, 〈\{40\}\{30\}\{110\}〉\}\)，运行 \(r - PrefixSpan(30, S1, 3)\) 算法： - 频繁项为 30 和 40，支持度均为 3 个序列。 - 长度为 1 的频繁序列仅为 \(〈\{30\}〉\)，因为要求每个频繁序列必须包含 30，所以 \(〈\{40\}〉\) 不包含在内。 - 以 \(〈\{30\}〉\) 为前缀，投影数据库 \(S1\) 得到 \(〈\{40\}〉\) 和 \(〈\{40\}\{40\}〉\)，移除支持度小于 3 的项 20、60 和 100，得到长度为 2 的频繁序列 \(〈\{30\}\{40\}〉\)。 - 以 \(〈\{40\}〉\) 为前缀，投影 \(S1\) 得到 \(〈\{30\}\{40\}〉\) 和 \(〈\{30\}〉\)，得到另一个长度为 2 的频繁序列 \(〈\{40\}\{30\}〉\)。 经过多次迭代，最终从序列数据库生成的序列模式集合为 \(\{〈\{30\}〉, 〈\{20\}〉, 〈\{40\}〉, 〈\{40\}\{30\}〉, 〈\{30\}\{40\}〉\}\)。 ### 1.2 生成规则类型 经典的序列模式挖掘不生成规则，但可以定义和生成多种类型的规则，主要介绍以下三种： #### 1.2.1 序列规则（Sequential Rules，SR） - 形式为 \(X \to Y\)，其中 \(Y\) 是序列，\(X\) 是 \(Y\) 的真子序列，即 \(X\) 是 \(Y\) 的子序列且 \(Y\) 的长度大于 \(X\) 的长度。 - 规则 \(X \to Y\) 在序列数据库 \(S\) 中的支持度是 \(S\) 中包含 \(Y\) 的序列所占比例；置信度是 \(S\) 中包含 \(X\) 的序列同时包含 \(Y\) 的比例。 例如，给定序列数据库（表 2.6），最小支持度为 30%，最小置信度为 60%，找到的一个序列规则为 \(〈\{1\}\{7\}〉 \to 〈\{1\}\{3\}\{7, 8\}〉\)，支持度为 \(2/5\)，置信度为 \(2/3\)。 | 数据序列 | | --- | | \(〈\{1\}\{3\}\{5\}\{7, 8, 9\}〉\) | | \(〈\{1\}\{3\}\{6\}\{7, 8\}〉\) | | \(〈\{1, 6\}\{7\}〉\) | | \(〈\{1\}\{3\}\{5, 6\}〉\) | | \(〈\{1\}\{3\}\{4\}〉\) | #### 1.2.2 标签序列规则（Label Sequential Rules，LSR） - 形式为 \(X \to Y\)，其中 \(Y\) 是序列，\(X\) 是由 \(Y\) 替换部分项为通配符“*”得到的序列。 - 通配符“*” 可匹配任何项，被替换的项通常是重要的标签。 例如，给定上述序列数据库，最小支持度为 30%，最小置信度为 60%，找到的一个标签序列规则为 \(〈\{1\}\{*\}\{7, *\}〉 \to 〈\{1\}\{3\}\{7, 8\}〉\)，支持度为 \(2/5\)，置信度为 \(2/2\)，其中 3 和 8 是标签。 #### 1.2.3 类序列规则（Class Sequential Rules，CSR） - 形式为 \(X \to y\)，其中 \(X\) 是序列，\(y\) 是类标签。 - 数据实例 \((s_i, y_i)\) 覆盖规则 \(X \to y\) 表示 \(X\) 是 \(s_i\) 的子序列；满足规则表示 \(X\) 是 \(s_i\) 的子序列且 \(y_i = y\)。 例如，给定序列数据库（表 2.7），最小支持度为 30%，最小置信度为 60%，找到的一个类序列规则为