★ FEATURED ARTICLE 先说个真实感受很多人第一次看到“序列模式挖掘”这几个字第一反应是“这不就是关联规则换个名字嘛”。等真上手跑了一轮 GSP 算法才发现完全不是一回事。序列模式挖的不只是“哪些东西常一起出现”而是“哪些行为在时间轴上反复出现”。这个区别直接决定了算法的输入格式、处理逻辑、结果解读方式全都变了。我最初是在一个用户行为分析项目里接触 GSP 的。当时要回答一个业务问题用户在三个月内的操作路径里是否存在高频的“搜索-比较-下单”模式。关联规则给不了答案因为它的核心是“共现”对顺序不敏感。而 GSP 这种基于 Apriori 思想扩展出来的序列挖掘算法处理的就是这种带次序、带时间上下文的模式发现任务。这篇文章我不打算堆公式也不搞“从入门到精通”那种教科书式铺开。我就按自己从一个只会跑 Apriori 的菜鸟到能完整实现并调优 GSP 的真实过程来写核心概念怎么理解、候选生成为什么这么设计、支持度计数有哪些坑、手工推演和 Python 实现怎么对得上、以及实际业务里哪些场景真正需要它。1. 为什么要用 GSP序列模式挖掘到底解决了什么问题1.1 从“购物篮”到“购物序列”GSP 与关联规则的本质区别关联规则大家很熟了经典的“啤酒-尿布”故事。它的输入是一条条交易记录每条记录内部是一组商品算法去统计“啤酒”和“尿布”在多少条交易里共同出现。注意一条交易内部是不分先后的买了啤酒再买尿布和买了尿布再买啤酒在关联规则看来没有任何区别。但很多现实业务问题天生就是分先后的。举几个例子用户登录网站后先看了首页推荐然后进入详情页最后提交了订单。这是个有时间顺序的行为序列。病人入院后先是发热然后是咳嗽再是肺部影像异常。这也是一个时序序列。再比如用户在搜索引擎上先输入 A 关键词过了 5 分钟又输入 B 关键词两个关键词在时间上是有先后顺序的。GSP 全称是 Generalized Sequential Pattern通用序列模式算法它哥哥是 Apriori父亲是同一个思想体系。GSP 解决的核心问题就是给定一堆“带顺序的序列数据”找出在所有序列中出现次数足够多的“子序列模式”。比如在上面那个用户行为例子里如果能挖出“搜索某手机型号 → 点击首条搜索结果 → 加入购物车”这个模式在很多用户身上出现了足够多次那这就是一个稳定的高频路径。区别我再往深里说一层关联规则里一个项集出现的“支持度”是统计包含该项集的交易数GSP 里一个序列的“支持度”是统计包含该序列的数据序列数。前者是“哪些东西在篮子里共现”后者是“哪些行为在时间轴上按顺序出现”。由于序列天然携带顺序信息GSP 的搜索空间比 Apriori 大得多所以它才需要专门设计候选生成和剪枝策略而不是简单套用 Apriori 的项集合并逻辑。1.2 核心概念速查序列、项集、支持度这些名词到底在说什么建个模型先不然后面推演全是乱的。一条“数据序列”data sequence就是一条完整的行为记录通常对应一个用户、一个病人或其他主体在一段时间内的行为轨迹。每个数据序列由若干“事件”按时间排序组成。每个事件内部又可以包含多个“项”。比如某用户的行为序列第一天搜索了“数码相机”同一天又搜索了“存储卡”第二天点击了某商品详情页。那这条序列可以记作{数码相机, 存储卡} {商品详情页}尖括号表示整个序列里面每一对大括号表示一个时间点上的事件同一个事件内部的多个项用逗号分隔。这里有个关键约定同一事件内部的项在逻辑上视为同时发生排列不分先后通常按字典序排好不同事件之间严格按时间先后排列。“子序列”的定义也跟字符串子串不一样。序列s a (b c) d的一个子序列不需要连续只需要按顺序“嵌”在里面就行。比如a d是它的子序列a c也是但d a不是。这个“允许跳步”的设计非常重要后面手工推演你会看到。“支持度”就是包含某个候选序列的数据序列条数。注意一条数据序列即使里面出现多次同一模式也只能计 1 次。这个细节我在实际实现时踩过坑后面专门说。再有一个容易混淆的概念是“频繁序列”和“序列模式”。频繁序列是指支持度不低于阈值的序列而很多时候我们还要给这些序列附加一个“占比”概念即它出现在多少比例的数据序列里。这个比例就是常说的“支持率”或“相对支持度”阈值一般就叫 min_sup。GSP 算法最终输出的就是所有支持度达到 min_sup 的频繁子序列。1.3 GSP 算法的定位基于 Apriori 思想的序列模式挖掘框架GSP 的算法骨架和 Apriori 是同一个模子刻出来的迭代搜索逐层扩展。从长度为 1 的候选序列开始扫描数据库数出支持度留下频繁的然后用频繁的生成下一轮长度为 2 的候选再扫库计数再留下频繁的……直到某轮没有新的频繁序列产生算法终止。这个过程每一步都建立在同一个核心性质上也就是 Apriori 性质如果一个序列是频繁的那它的所有子序列也一定是频繁的。反过来说如果一个序列存在某个子序列不频繁那这个序列本身也不可能频繁。这个性质给了 GSP 一把锋利的剪刀能在候选生成阶段把大量注定没出路的候选序列提前剪掉否则序列搜索空间爆炸到根本没法算。不过 GSP 不是 Apriori 的无脑照搬。最大的改动在于候选生成方式。Apriori 生成 k1 项集时只需要做简单的项集拼接因为项集内部是无序的而 GSP 生成 k1 序列时序列内部是有严格顺序的同一个序列还可能有多个时间点、每个时间点多个项怎么把两个 k 序列拼成一个 k1 序列还要保证不重不漏就需要专门的连接规则也就是“删除第一项/删除最后一项后剩余部分相同”的那个经典做法。这个我在下一节展开讲。2. GSP 算法核心流程拆解候选生成、计数、剪枝三步走2.1 第一步候选生成规则——L1 拼 L1L2 拼 L2分离点怎么找候选生成是整个 GSP 里最容易懵、也最值得讲透的地方。我们分两种情况看。先说从频繁 1-序列生成候选 2-序列。假设当前频繁 1-序列集合 L1 里有三个项a、b、c。那候选 2-序列 C2 是怎么来的就是两两组合但要区分两种情况两个项是“同一事件内”还是“不同事件”。同一事件内写成(a, b)表示两个项同时发生。不同事件写成(a) (b)表示 a 先发生b 后发生。所以a和b组合会产生两个候选(a, b)和(a) (b)。两个方向的顺序怎么处理因为序列是有序的(a) (b)和(b) (a)是两条不同候选都需要生成。但同一事件内的项要按字典序排好避免重复——(a, b)和(b, a)是同一个序列只保留一个。这个区分是 GSP 最容易出 bug 的地方我见过很多实现把同一事件内的组合丢了导致频繁 2-序列少算一大截。再说从 Lk 生成 Ck1这是 GSP 最核心的合并逻辑。规则描述起来挺绕两个不同的频繁 k-序列如果删除第一个序列的第一个元素后得到的序列与删除第二个序列的最后一个元素后得到的序列完全相等那就可以连接生成一个新的 k1 序列。“第一个元素”和“最后一个元素”怎么理解这里要把“元素”界定清楚要么是单个项要么是整个事件。我直接用例子说明。假设 L3 中有两个频繁 3-序列s1 {a} {b} {c} s2 {a} {b} {d}删除 s1 的第一个元素即第一个事件里的 a得到{b} {c}。删除 s2 的最后一个元素即最后一个事件里的 d得到{a} {b}。这两个剩余部分不相等不能连接。换个例子s1 {a} {b c} s2 {a b} {c}删除 s1 第一个元素 a得到{b c}。删除 s2 的最后一个元素 c它在第二个事件里注意删完后第二个事件变成一个空事件直接去掉得到{a b}。两个剩余部分还是不等不能连。正确的例子s1 {a b} {c} s2 {a} {b c}删除 s1 的第一个元素这里 s1 第一个事件是{a b}如果只删掉项 a事件里还剩 b那么剩余序列是{b} {c}。删除 s2 的最后一个元素s2 最后一个事件是{b c}删掉项 c 后事件里还剩 b剩余序列是{a} {b}。两个剩余部分不等还是不能连。关键来了真正能连接的例子s1 {a} {b c} s2 {b c} {d}删除 s1 的第一个元素结果是{b c}第一个事件整个被移除。删除 s2 的最后一个元素结果也是{b c}最后一个事件整个被移除。剩余部分相同可以连接。连接规则是取 s1 的完整内容再加上 s2 的最后一个元素作为新事件或者写成取 s1 的第一个元素作为新事件再加上 s2 的完整内容。由于刚才删掉的是第一个和最后一个实际生成方式有两种变体新序列 s1 后面追加 s2 的最后一个元素比如{a} {b c} {d}。或者更一般地看s1 删除第一个 追加 s2 最后元素。用文字描述会把人绕晕我这里直接给一个更容易记忆的说法把 s1 和 s2 对齐到一个公共中部P如果 s1 是(第一元素) Ps2 是P (最后元素)那么连接结果就是(第一元素) P (最后元素)。其中元素可以是“单个事件”也可以是“事件内部的单个项”这引出了 GSP 里很著名的“分离点”概念。分离点split point指的是两个要连接的序列从哪个位置分开后能让第一部分尾部等于第二部分头部。分离点在一个事件内部还是在两个事件之间决定了连接时最后一件事物的合并方式。我在代码实现里没有去抽象地找分离点而是用一个更工程化的方式对于 Lk 中的每条序列尝试与其他每条序列合并判断“删除第一”和“删除最后”后的剩余序列是否一致一致则按规则扩展。这样虽然时间复杂度高一些但逻辑绝对正确不会漏候选。这里必须提醒一个常见误区有人会把 Lk 里的序列两两连接时只看“前半相等拼后半”这种简单拼接忽略了同一事件内部拆分的情况导致 Ck1 有大量漏项。正确做法是每次从 s1 中作为“要删除的第一个元素”的可以是整个事件也可以是事件内的某一个项。我建议初次实现时直接在候选生成函数里写两个分支元素级连接和事件级连接分别处理然后做去重宁可多生成几个候选靠剪枝和计数把它们筛掉也不要漏生成。2.2 第二步支持度计数——为什么 GSP 要逐条扫描数据库候选生成完Ck1 里可能躺着成千上万条序列下一步就是扫数据库数一数每条候选序列被多少条数据序列包含。计数逻辑本身不难对每条数据序列d判断候选序列s是不是d的子序列。如果是给s的支持度 1。注意关键约束无论d里包含多少次s每次计数只加 1。举个例子数据序列{a} {b} {a} {b}包含子序列{a} {b}吗包含而且有两次第一次 a 和第一次 b第二次 a 和第二次 b 甚至可以交叉匹配。但计数时只算 1。这就是“一次匹配只计一次”的规则。我最初实现时用了一个集合去重后来发现没必要——直接一层循环做完匹配就返回即可根本不会重复计数。具体到子序列匹配我用的是一种类似贪心的指针扫描法也叫“滑动匹配”。对候选序列s里的每个事件、事件里的每个项到数据序列d里从上次匹配位置之后继续找匹配。能全部找到就说明s是d的子序列。这个方法在某些特殊场景下会出问题。比如数据序列d {a} {a} {a}候选序列s {a} {a}贪心法会匹配到第一次出现的 a 和第二次出现的 a判定成功。那如果这样不算成功呢实际中GSP 的匹配规则就是只要存在一种匹配方式就算包含所以贪心法是可行的。但如果加入了时序约束比如窗口大小和最小/最大间隔问题就变复杂了。街面上很多 GSP 的描述默认不启用时间窗口约束但在真实数据里如果你不设置任何时间约束结果会出现很多跨度过长的“弱相关”模式。比如用户年初搜索了相机年末才购买这条路径也能连起来业务上很可能没有意义。我实际使用时对带时间戳的数据会先把数据序列按时间分小窗口把窗口内部的序列单独提出来计数再把窗口合并。这个操作不是 GSP 的标准算法内容但工程实用性很高。后面我会给一个简化处理办法。2.3 第三步剪枝优化——Apriori 性质如何帮你砍掉无用候选扫描数据库计数是 GSP 性能的瓶颈候选越多扫描越慢。所以候选生成之后必须执行剪枝把那些“不可能频繁”的候选提前删掉不进入计数阶段。剪枝的依据就是 Apriori 性质若候选 k1 序列s是频繁的则它的所有长度为 k 的子序列都必须是频繁的。因此我只要检查候选序列的每个 k-子序列是否都在 Lk 里只要有一个不在这个候选就可以直接丢弃。这步实现起来有讲究。一个 k1 序列要生成它的所有 k-子序列有两种删除方式删除一个事件或者删除事件里的一个项。不能只删除整个事件因为同一个事件内部多个项拆分后也能形成不同子序列。如果漏掉了“事件内部删一个项”的情况剪枝会剪掉不该剪的候选最后导致结果缺失。举一个具体的例子。候选序列s {a b} {c}长度为 2。它的 1-子序列有哪些删除第一个事件里的项 a得到{b} {c}删除第一个事件里的项 b得到{a} {c}删除整个第二个事件得到{a b}。这三个都是它的 1-子序列任何一个不在 L1 里候选就被剪掉。同样的生成 k-子序列时要做两层循环一层遍历位置删除事件一层在保留事件时遍历每个事件内部逐项删除。我在代码里实现剪枝时是先写了一个函数generate_all_subsequences(s, k)用组合方式生成所有删除操作然后在判断sub_seq in Lk时用一个frozenset哈希 Lk 集合查询复杂度降到 O(1)。用 Python 里的set存序列元组配合序列编码见下文代码性能还不错。3. 手工推演 代码实现从零跑通 GSP3.1 手工推演一个 5 条序列的小数据集完整跑一遍纸上得来终觉浅拿一个小数据集完整跑一遍 GSP胜过读十遍原理。设最小支持度min_sup 2数据库如下数据序列编号内容1{a, b} {c}2{a} {c} {d}3{b} {c} {e}4{a} {d} {c}5{a, b} {d}第一步生成所有 1-候选序列。这里的“候选 1-序列”其实就是数据库里出现过的所有项以及它们可能组成的“单事件序列”和“单事件项集序列”。严格来说一个单独的项可以出现在一个事件里那 1-序列统一记作{a}、{b}这种形式。同行内两个项{a, b}不能算 1-序列它们在候选 2-序列阶段才出现。扫描数据库统计每一项出现在多少条序列里注意按序列计数不是按出现次数a序列 1、2、4、5共 4 条。b序列 1、3、5共 3 条。c序列 1、2、3、4共 4 条。d序列 2、4、5共 3 条。e序列 3共 1 条低于 min_sup2淘汰。所以 L1 {{a},{b},{c},{d}}。第二步用 L1 生成候选 2-序列 C2。根据前面说的规则每个项对要生成三种候选严格来说同一事件内的项对按字典序去重后生成一个不同事件的正反顺序各生成一个以 a、b 为例生成(a, b)、(a) (b)、(b) (a)。三个都要保留。同理处理其他项对C2 一共会生成 4 个项自配对组合、12 个不同项对的双方向序列加上同事件组合总共约 28 条候选。这里为了展示核心逻辑不逐个列出了。逐一扫描数据库。以候选(a) (c)为例数据序列 1{a b} {c}包含 a 后包含 c算 1 次数据序列 2{a} {c} {d}也算数据序列 3 无 a不算数据序列 4{a} {d} {c}a 之后有 d 再有 c所以 a 之后能找到 c算数据序列 5 无 c不算。总计支持度 3通过。候选(a, c)同一事件只在数据序列里一个事件同时含 a 和 c 才满足本例所有序列都没有同一事件同时含 a、c支持度为 0淘汰。这一步手工跑完其实相当耗时我在初学阶段用纸推过一次十项左右的数据库两小时起步。强烈建议第一次学习时用笔推能极大加深对候选生成和计数的理解。推完可以跟我下面的代码逻辑对照检查有没有漏项。第三步从频繁 2-序列生成候选 3-序列并剪枝。假设 L2 里有(a) (c)和(c) (d)前者删除第一个元素得到(c)后者删除最后一个元素得到(c)剩余部分相同所以可以连接成(a) (c) (d)。生成之后做剪枝它的所有 2-子序列分别是(a) (c)、(a) (d)、(c) (d)检查它们是否都在 L2 里。如果(a) (d)不在那么候选被剪掉。继续循环直到某一轮 Lk为空算法结束。最终输出的就是所有频繁序列。上面这个例子里如果你完整跑完会发现(a) (c) (d)支持度是 1只有序列 2 同时出现 a、c、d 且顺序符合达不到阈值所以不会被输出。如果 min_sup 降到 1它就会浮出水面。3.2 基于 Python 的 GSP 实现与关键代码解读手工推演和代码实现互相印证是最稳的学习路径。我提供一个简化但功能完整的 Python 实现保留了 GSP 的核心逻辑去掉了复杂的时间窗口扩展方便理解。from itertools import combinations def generate_c1(data): 从数据库提取所有单项构成候选1-序列 items set() for seq in data: for event in seq: for item in event: items.add(item) return [((item,),) for item in sorted(items)] def get_support(cand_seq, data, min_sup): 计算候选序列在数据库中的支持度提前终止 count 0 for seq in data: if is_subsequence(cand_seq, seq): count 1 if count min_sup: return count return count def is_subsequence(cand, seq): 判断候选序列是否为数据序列的子序列贪心匹配 pos 0 for event in cand: matched False while pos len(seq): if set(event).issubset(set(seq[pos])): matched True pos 1 break pos 1 if not matched: return False return True def candidate_gen(lk, k): 从频繁k-序列生成候选(k1)-序列带剪枝 cands set() lk_list list(lk) for s1 in lk_list: for s2 in lk_list: # 元素级连接删除s1第一个事件的第一项删除s2最后一个事件的一项 for i in range(len(s1[0])): # 移除s1第一个事件中的第i项 first_event1 list(s1[0]) first_event1.pop(i) if first_event1: s1_removed (tuple(first_event1),) s1[1:] else: s1_removed s1[1:] for j in range(len(s2[-1])): last_event2 list(s2[-1]) last_event2.pop(j) if last_event2: s2_removed s2[:-1] (tuple(last_event2),) else: s2_removed s2[:-1] if s1_removed s2_removed: # 连接s1 s2的最后一个事件保留最后一项 new_seq s1 (s2[-1],) # 事件级连接 cands.add(new_seq) # 元素级连接将最后一项并入最后一个事件 if len(s2[-1]) 1: last_item s2[-1][-1] merged_event tuple(sorted(s1[-1] (last_item,))) new_seq2 s1[:-1] (merged_event,) cands.add(new_seq2) # 剪枝检查所有k-子序列是否在lk中 pruned set() for cand in cands: if all(subseq in lk for subseq in generate_all_k_subseq(cand, k)): pruned.add(cand) return pruned def generate_all_k_subseq(seq, k): 生成一个序列的所有长度为k的子序列用于剪枝检查 result set() # 逐个删除事件 for i in range(len(seq)): new_seq seq[:i] seq[i1:] if sum(len(e) for e in new_seq) k: result.add(new_seq) # 逐个删除事件内项 for i in range(len(seq)): for j in range(len(seq[i])): new_event list(seq[i]) new_event.pop(j) new_events list(seq) if new_event: new_events[i] tuple(new_event) else: new_events.pop(i) new_seq tuple(new_events) if sum(len(e) for e in new_seq) k: result.add(new_seq) return result def gsp(data, min_sup): GSP主流程 lk set(generate_c1(data)) all_frequent [] k 1 while lk: frequent [] for cand in lk: sup get_support(cand, data, min_sup) if sup min_sup: frequent.append((cand, sup)) frequent sorted(frequent, keylambda x: (len(x[0]), x[0])) all_frequent.extend(frequent) lk set(cand for cand, _ in frequent) k 1 lk candidate_gen(lk, k-1) return all_frequent我来说几个代码里的关键决策。is_subsequence实现的是贪心匹配按候选序列的事件顺序依次在数据序列中找“能包含该事件所有项”的事件找到后继续找下一个。这个实现有一个局限它把候选的一个事件匹配到数据序列的一个事件要求数据序列事件必须完整包含候选事件的所有项。这是 GSP 里最常见的匹配语义如果想支持更宽松的跨事件匹配如候选事件中的项可以分散在数据序列的多个相邻事件里匹配逻辑需要重写但对大多数业务场景现有版本够用。generate_all_k_subseq要兼顾“删整个事件”和“删事件内的项”两种情况否则剪枝会误伤。注意当一个事件删到为空时要把整个事件从序列中移除否则会产生一个“空事件”导致子序列计数不准。这里我做了处理。candidate_gen里同时跑了事件级连接和元素级连接。事件级连接是把 s2 的最后一个事件原样追加到 s1 后面元素级连接是把 s2 最后一个事件“拆散”合并到 s1 的最后一个事件里。这两种连接正好对应了分离点在事件之间和事件内部两种情况。生成完成后统一剪枝剪枝通过就进下一轮。这个实现会多生成一些重复候选靠最后set去重兜底工程上没问题因为候选集再大也比扫描数据库便宜。3.3 关键参数选择最小支持度怎么定min_sup 是 GSP 唯一直接控制输出规模的参数选多少直接决定结果质量。我实际项目里一般这么试探先跑一个较高的阈值比如 0.2 相对支持度看输出模式数量和业务可解释性。然后逐步降低每次观察频繁序列数量增长曲线。如果从 0.1 降到 0.05频繁序列数量从几百暴涨到几万说明你可能已经挖到大量低质量、弱相关的关联业务上往往不可用需要回调。选择 min_sup 还要结合数据特点。点击流数据、搜索日志这类高频行为数据序列数量大、重复性高可以把阈值设高一点而医疗病历、故障工单这类低频数据序列条数少、行为差异大阈值要放得很低甚至设到 1 或 2 条绝对支持度。有一个经验值得记住min_sup 的高低不是算法自己能决定的它本质上是业务风险偏好。阈值高结果少而精但可能漏掉长尾中真正有价值的稀有模式阈值低结果多而杂需要投入大量人力筛选。第一次跑的时候宁可先设高一点把核心稳定模式找出来再逐步放宽挖掘长尾这样更容易说服业务方接受结果。4. 常见问题与排错实录4.1 候选生成常见的几个坑第一个坑连接条件判断错了对象。很多人会把“删除第一个元素和删除最后一个元素”误解成“删除第一个事件和删除最后一个事件”导致事件内有多个项时候选生成不完整。我建议把“元素”拆成两个层级来理解一个是事件级一个是项级。连接时先对每条序列生成所有可能的“删除第一个元素后的版本”以及所有可能的“删除最后一个元素后的版本”用集合比对。两个集合有交集就说明存在可连接的分离点然后把对应的连接结果加进去。第二个坑连接结果的末尾处理。两个序列通过公共部分 P 连接得到第一元素 P 最后元素但“最后元素”到底是一个独立事件还是合并到倒数第二个事件里取决于分离点的位置。比如 s1 的最后一个事件有多项而 s2 的第一部分末尾是一个事件内的子集这时候连接结果有可能把最后一项跟前面合并成同一事件。我在代码里同时生成两种连接结果让剪枝和计数去筛从结果正确性来说是安全的。第三个坑重复候选。用两两连接的方式生成候选必然产生大量重复比如通过 s1s2 和通过 s2s1 可能生成同一个序列顺序相同时。去重必须做而且去重要在剪枝之前做否则剪枝时同一个候选查好几遍浪费时间。Python 里直接用set装冻结元组即可注意别用 list 存候选否则无法哈希。4.2 支持度计数容易出错的细节计数阶段最容易错的是把“包含子序列”误判成“包含子串”。序列{a} {b}在数据序列{a} {c} {b}里是子序列因为 a 在 c 之前、b 在 c 之后顺序满足。但很多人第一直觉会认为 a 和 b 必须相邻导致支持度被低估。GSP 的匹配语义就是允许中间插入任何无关事件这一点在看结果时也要提醒业务方模式{a} {b}不代表 a 和 b 紧挨着发生只代表 a 在 b 之前发生过。另一个高频错误是“重复出现只计一次”。我见过一个数据序列里模式出现了三次实现者给支持度上了三结果整条频繁序列的排名全乱了。排查方式很简单一条数据序列在is_subsequence里返回 True 后就应该跳出循环不再继续匹配下一个候选出现位置。还有一类问题出在空事件处理上。如果候选序列里有一个事件是空的比如()is_subsequence里会直接匹配成功。在剪枝和连接过程中空事件是中间产物但如果没清理干净就进入计数阶段会出现大量“幽灵支持度”。我的建议是所有候选序列在生成和剪枝阶段结束时统一做一次“移除空事件”的清理。4.3 数据格式设计与性能优化GSP 的数据格式设计很影响实现难度。我在代码里用的是 Python 元组嵌套元组比如((a,b),(c,))表示第一事件包含 a、b第二事件包含 c。这个格式直接对应算法的数据模型调试时也容易打印。但真实业务数据通常是从日志表里查出来的一般要先做两步清洗一是把事件按时间排序同一秒或同一分钟内的项归并成一个事件二是把用户 ID、操作类型、商品 ID 转成整数编码加快匹配速度。性能方面GSP 的主要瓶颈在扫描数据库和子序列匹配。我实测过几轮当数据序列超过几万条、候选序列几千条时纯 Python 逐条匹配会慢得让人抓狂。有几个优化策略非常有效第一把候选序列按第一个事件的首项建立索引扫描时先筛掉完全不可能匹配的序列减少is_subsequence调用次数第二用“垂直数据格式”把数据列成项到序列 ID 的倒排表计数时只扫描包含候选首项的数据序列第三对超长数据序列做切段把间隔过远的部分拆成两个独立序列既降低匹配长度也过滤掉无意义的长跨度匹配。我自己的一个项目里数据约两万条序列、每条约十个事件min_sup 设成 30GSP 跑一轮要十几秒。加了倒排索引和首项过滤后压到两秒左右。如果数据到百万级纯 Python 基本不可行需要换 C/Java 实现或使用现成库但对理解和调参来说Python 版本完全够用。5. 应用场景与实践建议5.1 哪些场景真正需要 GSPGSP 最适合的不是“发现共现”而是“发现行为路径”。我实际接触过的几类典型场景电商和内容平台的用户路径分析。业务想看的不是“啤酒和尿布一起买”而是“用户先看了某个商品页第二天又看了同类商品页最终在第四天完成购买”这个完整路径。把用户的每一次行为按天或小时切成事件每天内可以有多个项喂给 GSP能挖出一批高频转化路径或流失路径。这个信息比关联规则直观得多因为结果带着时间顺序业务方可以直接照着模式设计运营策略。运维故障工单分析。机房故障工单通常有先后步骤告警出现、人工介入、尝试 A 操作、尝试 B 操作、最终恢复。用 GSP 去挖高频恢复路径可以总结出常见故障的标准处置流程。这里有个特殊性工单数据量不大但每条序列非常长时间跨度也很长min_sup 要设得很低甚至要按绝对条数设。医疗路径挖掘。病人从就诊、化验、确诊直到治疗方案是一串带时间的行为序列。挖掘高频诊疗路径对优化临床路径管理有参考价值。这类数据隐私要求极高GSP 跑出来的模式需要经过严格医学解释更多是辅助发现而不是自动决策。其他还有 Web 访问日志挖掘、金融反洗钱路径分析、用户在 App 内的操作序列规律发现都是经典适用场景。共同点是数据必须具备明确的主体用户/患者/工单、时间戳、行为类型三个要素缺一个 GSP 效果都会大打折扣。5.2 与其它算法对比与选型建议GSP 之外序列挖掘领域还有 PrefixSpan、SPADE、SPAM 等算法。简单说一下我的选型经验。GSP 和 PrefixSpan 是最常被拿来对比的。GSP 是类 Apriori 的宽度优先搜索要先生成大量候选再做反复扫描PrefixSpan 用前缀投影的方式把每个频繁前缀对应的后缀投影出来不需要生成候选在长序列密集数据上性能通常更好。我自己的体会是序列平均长度在 10 以下、事件内项数不多时GSP 实现简单、结果直观完全够用。序列很长比如每个用户几千个行为点时GSP 的候选量和扫描代价会膨胀得很厉害PrefixSpan 会舒服很多。SPADE 走的是垂直数据格式路线对支持度计算的优化很到位但实现复杂度高适合数据量大且有工程团队支持的项目。SPAM 则是专门为 Web 点击流这类非常长的序列设计的一种深度优先算法内存占用小但在长度短的数据上优势不明显。做选型时还有一个重要考量数据里有没有严格的时间间隔约束。如果业务上要求模式里的两个事件必须在短时间内紧邻比如 10 分钟内GSP 可以通过时间窗口扩展来处理但实现复杂度会直线上升。如果数据天然已经按天/按小时聚成事件直接用 GSP 默认的时间粒度即可这时它的简洁性反而是优点。最后说一个我在项目里反复遇到的“算法之外”的问题GSP 挖出来的模式怎么跟业务解释。很多业务方第一次看到{a} {b} {c}这类符号会下意识把它当成严格连续发生然后质疑“用户不可能 3 分钟就完成这一串操作”。这里其实是因为算法默认“可跳过中间项”匹配业务方用“连续动作”的语义去理解产生偏差。我的建议是输出模式时附带上两条信息每个事件之间的时间间隔分布中位数、四分位数以及模式在全部支持序列中的完整覆盖率。有了这些统计量业务方才能真正判断模式是否有运营价值。GSP 只是帮你把候选模式捞出来最终决策永远要结合业务上下文。我个人跑了这么多轮 GSP 后的最大体会是序列模式挖掘的难点从来不在算法本身而在于数据序列化的设计和结果语义的解释。把用户行为切成一个个“事件”哪些行为合并成一个事件、哪些必须分开直接决定算法输出的模式长什么样。同一个业务问题换一种序列化方式结果可能天差地别。所以如果你打算在自己的项目里用 GSP我建议第一步别急着写代码先花时间设计好“数据序列”的定义——每个主体怎么标识、每个事件怎么聚合、时间粒度选多大。这一步做得越扎实后面 GSP 跑出来的模式就越有业务价值。
阅读完成 · 觉得有帮助？
