关联规则：序列模式挖掘

可视化演示

展示系统处理流水线、实时性能指标曲线及多方案对比分析，包含数据流转、吞吐延迟监控与方案评估。

序列模式：侦探的行动轨迹

老周把 30 天的目击报告摊在桌上，每条记录都是一串地名：钟楼、酒馆、钱庄、马厩。他起初只统计每个地点单独出现的次数，但钟楼出现得频繁，酒馆也出现得频繁，两者都解释不了钱庄为何每次都在特定顺序后失窃。直到他把记录当作“一晚上走过的路线”来看，规律才浮出水面：夜行者并不是随机游走，而是反复上演同一套行动剧本。这套剧本的关键不是单个地点，而是地点之间的先后关系。

这里的“行动剧本”，就是计算机领域的序列（sequence）。序列由事件（item）按时间顺序排列而成，比如 <钟楼, 酒馆, 钱庄>。序列模式挖掘的任务，就是从大量序列组成的数据库里，找出反复出现的子序列（subsequence）。子序列不要求事件在原序列中连续相邻，只要求相对顺序一致：<钟楼, 钱庄> 可以对应真实轨迹 <钟楼, 酒馆, 钱庄>，中间多了一个酒馆，但仍然是一个合格的子序列。一个事件内部还可以同时发生多个动作，例如“买啤酒＋买尿布”作为一个元素，内部项之间没有先后，只有元素之间才有先后。

对老周来说，子序列就是“作案习惯的骨架”：他想知道夜行者是否习惯先经过钟楼再摸进钱庄，至于中间是否绕路去酒馆、马厩，都不影响这个骨架成立。序列模式挖掘本质上，就是在无数条路线记录中自动找出这类骨架，并且判断哪些骨架真的稳定。

序列数据库与支持度：卷宗里的概率

老周的桌上有 100 条行动路线，每条路线都来自一位巡夜人的记录，构成一个“卷宗集合”。他现在要问：<钟楼, 酒馆, 钱庄> 这套顺序到底有多常见？如果只是偶尔出现，那可能只是巧合；如果 100 条里出现 60 次，那就是习惯。这里“路线集合”就是序列数据库 D，其中每一条完整记录叫一条序列。

为了量化“多常见”，需要支持度（support）这个概念，它表示一个候选模式 α 在序列数据库中被多少条序列包含。

老周把阈值定为 0.3：只有超过三成路线都出现过的行动顺序，才值得继续调查。低于阈值的路线组合，他会直接从嫌疑名单里划掉。这个“划掉”的动作看着简单，却是整个挖掘算法效率的关键——频繁的才有资格继续生长，冷门的直接淘汰。

GSP 算法：逐层候选的审讯法

老周的第一套办法很实在：既然要确认长路线是否常见，那就从短路线开始试错。他先在 100 条路线里统计所有“两步路线”的频率，比如钟楼→酒馆、酒馆→钱庄、钟楼→钱庄，留下超过阈值的；然后把这些幸存路线分别延长一步，变成“三步路线”，再重新去路线堆里核验；如此反复，直到无法再延长。这个方法就像办案人员逐层审讯嫌疑人：先锁定一批可疑的两步组合，再追问第三步去向。

这就是 GSP（Generalized Sequential Pattern）算法的基本思路。它把候选模式按长度分层：首先由所有单事件生成 1-序列，扫描数据库得到频繁 1-序列；再用频繁 k-序列通过连接操作生成 k+1-序列候选，逐层向下推进。每一层新候选都必须重新扫描整个数据库统计支持度，所以 GSP 的扫描次数与模式长度成正比。

GSP 真正聪明的地方在于 Apriori 剪枝，也叫反单调性：一个序列如果不是频繁的，那么任何包含它的更长序列也一定不频繁。因为支持度只会随着模式变长而下降——老周如果发现“钟楼→钱庄”只在 10 条路线里出现，那么“钟楼→酒馆→钱庄”最多也只能在这 10 条路线里出现，绝不可能更多。于是，每次生成候选时都可以提前砍掉大量不可能频繁的长路线，避免无意义的扫描。

老周把这套方法称为“地毯式搜查”：每一步都老老实实把全城卷宗翻一遍，但每翻一轮，嫌疑路线都会少一大半。GSP 的优势是思想简单、实现直接，适合序列长度不长、模式相对稀疏的数据；代价则是当候选路线很多、序列很长时，反复扫描全库会变得非常耗时。

PrefixSpan 算法：前缀投影追查法

卷宗越堆越高，老周决定换个策略。他发现每次为了确认一条长路线，都要把整摞卷宗重头翻一遍，太浪费了。于是他想：既然已经锁定了“钟楼→酒馆”这个前缀，那之后第三步只会出现在“钟楼→酒馆”之后的记录片段里，为什么不先把这些后续片段单独抽出来，只看这一小摞？

这正是 PrefixSpan（Prefix-projected Sequential Pattern mining）的核心思想。它不再像 GSP 那样先生成大量候选再逐一验证，而是固定一个前缀，把所有包含该前缀的序列截取成“后缀片段”，构成一个更小的数据库，在这个小数据库里继续寻找能接在前缀后面的频繁事件。这个被截取出来的后缀片段集合，就叫投影数据库（projected database）。

假设老周已经确认前缀 α 频繁，现在想扩展一个新事件 β，把 α 和 β 拼成新前缀 α′。那么 α′ 的投影数据库，等价于先在原库上按 α 投影，再在这个投影库中按 β 截取后续部分。这个递归关系可以写成：

老周沿着“钟楼”出发，把所有钟楼之后的内容抽出来；再沿着“钟楼→酒馆”出发，把酒馆之后的内容抽出来；每深入一层，卷宗就越薄，调查范围就越聚焦。PrefixSpan 不用像 GSP 那样枚举海量候选，而是沿着前缀不断生长。代价是，每个频繁前缀都要额外维护一份投影数据库，内存开销会相应增加。

时间约束：步伐里的窗口规则

老周又发现一个细节：有些路线虽然顺序对得上，但夜行者从钟楼到酒馆足足隔了三个小时，跟“踩点后立刻销赃”的手法令人生疑。反过来，如果钟楼和酒馆几乎同一时刻出现，也可能是同一事件被重复记录。于是他给路线分析加上了两条纪律：第一步到第二步之间不能超过 28 分钟，也不能少于 8 分钟。

这就是序列模式挖掘中的时间约束。仅有先后顺序还不够，两个事件之间的跨度、间隔，往往才是业务上真正有意义的信号。最大间隔（max gap）约束限制了模式中相邻两个事件的最大时间跨度，避免把相隔太久的偶然事件强行串成模式；最小间隔（min gap）约束则规定相邻事件至少间隔多久，防止同一时刻发生的并列事件被误读为先后关系。

滑动窗口（sliding window）则是另一类常用约束：它把时间轴切成一个个固定长度的窗口，在窗口内允许事件顺序略有松动，或者把窗口内的事件当作一个整体来计算支持度。比如老周把一晚按 30 分钟切窗，只要钟楼和酒馆落在同一个窗口里，就算一次有效匹配，哪怕中间隔了一两个次要地点。

加了时间约束后，那条“钟楼→酒馆→钱庄”才真正从“顺序碰巧对”变成“节奏紧凑的作案流程”。在实际数据中，时间约束能显著降低无意义的偶然共现，让挖出的模式更贴近真实业务因果。

应用场景：从侦察卷宗到业务现场

老周的方法很快被商业界请去当了顾问。大型超市的运营者发现，只看“哪些商品经常一起买”还不够，顾客的真实决策是一个动作接一个动作的过程：从货架 A 走到货架 B，再到收银台。于是他们把购物路径、浏览点击按时序整理成序列数据库，用序列模式挖掘找出高转化路径。比如发现频繁子序列 <搜索冰箱 → 对比价格 → 加入购物车>，就把它作为推荐策略的触发条件。这对应“购物路径分析”场景。

手机 App 产品经理也遇到了类似问题：用户是否激活，往往不取决于“打开了哪几个页面”，而取决于“先打开哪个、再打开哪个”。把用户首次会话的事件流挖成序列后，团队发现 <导入数据 → 创建报表 → 邀请同事> 是留存用户的频繁子序列，于是把新手引导流程改造成这条路径，让新用户顺着高留存用户的习惯走。这就是“用户行为建模”。

工业领域同样如此。风力发电机的 SCADA 日志会记录一条条状态事件：叶片转速波动、齿轮箱温度升高、报警触发。序列模式挖掘能从海量日志中自动发现故障前的习惯性事件顺序，比如频繁子序列 <转速异常 → 温度升高 → 报警>，实现提前预警。工业 AI 工程师把这些模式嵌入监控系统，替代原来靠老师傅经验的规则库，这就是“工业应用”。

算法对比与选型：挑选合适的老侦探

老周手下的 GSP 和 PrefixSpan 两位侦探各有脾气。GSP 是地毯式搜查型：它逐层生成候选，每层都要扫描整个数据库，候选数量可能指数膨胀，但思路直白，对短序列和稀疏数据表现稳定。PrefixSpan 是目标追踪型：它通过前缀投影不断缩小卷宗范围，避免了大批候选的生成，但每一层投影都要额外保存后缀子库，内存消耗更高。

选择建议可以概括为三条：第一，如果序列库规模不大、模式长度较短，GSP 的实现简单、迭代清晰，是优先选择。第二，如果序列很长、模式稠密，PrefixSpan 的投影机制能大幅减少无效扫描，通常更划算。第三，如果硬件内存紧张且数据稀疏，GSP 类广度优先方法更省内存；如果希望单条长路径挖掘得更深，PrefixSpan 的深度优先递归更有优势。此外，真实工程中常常对两种算法做时间约束剪枝和抽样预估，再决定最终方案。

老周最后在总结报告里写道：没有绝对最好的侦探，只有最合适对手的办案方法。扫描次数少不代表零代价，内存换时间也不一定永远划算；把数据特征、支持度阈值和时间约束放在一起权衡，才能选出真正高效的模式挖掘方案。

AI 应用场景

Python 演示

# -*- coding: utf-8 -*-"""简化版 GSP：逐层生成候选序列并统计支持度。"""  def is_subsequence(sub, seq):    """判断 sub 是否为 seq 的子序列（保持相对顺序）。"""    it = iter(seq)    return all(x in it for x in sub)  def build_candidates(frequent, sequences):    """由长度为 k 的频繁序列扩展单个事件，生成长度为 k+1 的候选。"""    items = sorted({item for seq in sequences for item in seq})    cands = set()    for seq in frequent:        for item in items:            cands.add(seq + (item,))    return cands  def gsp(sequences, min_sup):    """GSP：从 1-序列开始逐层扫描数据库。"""    items = sorted({item for seq in sequences for item in seq})    results = []    candidates = {(item,) for item in items}    max_len = max(len(seq) for seq in sequences)     while candidates:        frequent = []        for cand in sorted(candidates):            sup = sum(1 for seq in sequences if is_subsequence(cand, seq))            if sup >= min_sup:                frequent.append(cand)        if not frequent:            break        results.extend(frequent)        candidates = build_candidates(frequent, sequences)        if len(frequent[0]) + 1 > max_len:            break    results.sort(key=lambda x: (len(x), x))    return results  if __name__ == "__main__":    db = [        ['A', 'B', 'C', 'D'],        ['B', 'C', 'E'],        ['A', 'B', 'D', 'E'],        ['A', 'C', 'D', 'E'],    ]    for pattern in gsp(db, min_sup=2):        print('<' + ','.join(pattern) + '>')

1. def is_subsequence(sub, seq):判断候选模式是否是某条序列的子序列，这里用迭代器的“剩余部分继续查找”保证顺序。
2. return all(x in it for x in sub)对模式里的每个事件，在序列中按顺序寻找，一旦全部找到就返回真。
3. items = sorted({item for seq in sequences for item in seq})收集数据库中出现的所有不同事件，作为候选扩展的单元素集合。
4. sup = sum(1 for seq in sequences if is_subsequence(cand, seq))逐条统计包含该候选模式的序列数，得到支持度。
5. frequent.append(cand)只有当支持度不小于阈值时，才把候选模式保留为频繁序列。
6. candidates = build_candidates(frequent, sequences)由本层频繁序列扩展单个事件，构造下一层更长的候选序列集合。
7. if len(frequent[0]) + 1 > max_len:当下一层候选长度已经超过数据库中最长序列长度，再验证不可能有意义，直接结束循环。

常见误区

面试题