做用户行为分析的时候我经常要面对一长串带时间戳的操作日志用户先点了A页面隔了一会儿又点了B按钮最后在C页面完成转化。普通关联规则只能告诉你A商品和B商品经常一起出现在同一笔订单里但没法回答用户买了A之后多久之内买B才算一条有价值的转化路径。这时候就需要序列模式挖掘出手。GSP算法是这个领域最经典的起点我最初就是靠它把序列模式这四个字真正弄明白的也是在用它跑真实日志、踩完一轮坑之后才理解后面那些更花哨的算法到底在优化什么。这篇文章不打算做成教科书式的算法讲解而是按我自己实现和应用GSP时的思路来写先说明为什么序列数据不能直接套关联规则再把GSP的候选生成、支持度扫描、时间约束这几个核心环节拆开讲透最后用一个手工可复算的小例子走完整轮迭代并补上真实应用中容易翻车的地方。目标读者是想自己动手实现序列模式挖掘、或者在课堂上被GSP弄得一头雾水的同学。看完之后你能亲手算出每一层候选怎么来、为什么被剪、支持度怎么数也能在项目里判断GSP到底合不合适。1. 为什么序列数据需要一种会排队的关联规则1.1 从购物篮到购物车序列多了一个先后维度经典关联规则处理的是购物篮数据每一行是一个事务比如订单号、包含的商品集合。它只关心哪些商品经常在同一笔订单里共现输出类似买啤酒的人也买尿布这样的规则。这种建模方式把所有事务看成彼此独立的袋子袋子里面的商品没有先后之分袋子之间也没有顺序关系。但很多真实问题天然是带顺序的。用户在电商网站上的行为是一条路径先浏览商品详情页再加入购物车最后提交订单患者就医是一串事件挂号、检查、开药、复诊设备故障是一组报警告警A发生后过一段时间告警B触发再往后是告警C。这些数据如果强行压成购物篮把每个用户的所有行为揉成一袋子你会丢掉先后这个最关键的信息也就无法回答用户做出某个行为之后下一个最可能做什么。序列模式挖掘就是把顺序放回数据里。它要找的模式不是啤酒和尿布共现而是啤酒出现之后隔了若干时间尿布也会出现。GSP算法Generalized Sequential Pattern正是最早也最经典的解决方案之一由研究者们在1996年前后提出核心思路是从频繁1-序列开始逐层生成更长的候选序列再扫描数据库验证支持度直到无法生成新候选为止。后面出现的PrefixSpan、SPADE等算法可以说都是在和GSP候选太多、扫描太多次这两个毛病作斗争。1.2 Apriori直接搬过来为什么必错刚接触序列挖掘的人最容易犯的错是把关联规则里的Apriori算法原封不动搬过来用。表面上两者确实很像都是候选生成—支持度验证—剪枝的框架都要维护频繁项集的子集一定频繁这条性质。但有一个关键差异会让Apriori直接失效Apriori处理的是同一个事务内部的共现关系项与项之间没有时间先后而序列模式里的顺序信息是发生在不同事务之间的。举个例子Apriori里{面包, 牛奶}这个项集表示一笔订单里同时包含面包和牛奶支持度计算只要看某一笔订单是否同时包含这两项。但在序列数据里面包→牛奶和牛奶→面包是两个完全不同的模式前者表示先买面包再买牛奶后者相反。如果只统计同时出现就会把两种顺序完全不同的行为混成一条模式质量大打折扣。更麻烦的是序列数据里还要区分同一个事务内的多项和不同事务间的先后。同样两条日志一条是用户在同一个订单里买了面包和牛奶另一条是用户先下了一单买面包隔天又下了一单买牛奶前者对应同元素项集{面包,牛奶}后者对应序列{面包},{牛奶}。这两种形态在GSP里是不同长度的序列在Apriori眼里却可能是同一条记录。所以把Apriori直接搬过来第一步建候选就建错了。1.3 GSP的基本流程和Apriori同款骨架换了内脏GSP的整体流程和Apriori非常像但每一步都针对序列数据做了重新定义。算法从扫描数据库、统计每个单项的支持度开始把支持度不小于min_sup的单项组成频繁1-序列然后进入迭代循环第k轮用频繁k-序列通过连接生成候选(k1)-序列再用剪枝删除那些存在非频繁子序列的候选接着重新扫描数据库统计每个候选序列的支持度过滤得到新的频繁(k1)-序列。直到某一轮连接生成不出任何新候选算法结束输出所有频繁序列。整个过程可以概括为四步扫描一次数据库统计所有单项的出现频次得到频繁1-序列。由频繁k-序列集合第1轮时k1通过连接步生成候选(k1)-序列集合。对候选集合做剪枝只要某个候选序列存在一个长度为k的子序列不在频繁k-序列集合里就把它删掉。再扫描数据库计算每个候选序列的真实支持度保留不小于min_sup的候选得到频繁(k1)-序列。重复第2到第4步直到某次生成的候选全部被剪掉或全部不满足支持度为止。这里的每一步都有个序列版的细节连接步不再是简单地把两个项集拼在一起而是要处理项和元素两个层次剪枝步里的子序列也不是任意删掉几个项而是保持原有元素边界删项。这些细节正是新手最容易写错的地方下一节我把它们一个个掰开讲。2. GSP候选生成的两个算子连接步和剪枝步2.1 连接步先比腰再看尾连接步的目的是从两个频繁k-序列合并出一个候选(k1)-序列。GSP的连接条件比Apriori多了个弯给定两个频繁k-序列s1和s2先把s1去掉第一个项注意是第一个项不是第一个元素再把s2去掉最后一个项如果去掉之后得到的两个序列完全相等那么s1和s2可以连接。很多人第一次实现GSP就栽在这个去掉第一个项上。什么叫去掉第一个项比如序列{1,2},{3}第一个元素是{1,2}去掉第一个项1之后这个元素还剩{2}所以去掉第一个项后的序列是{2},{3}。如果你理解成去掉第一个元素得到的就是{3}那连接条件就完全错了。连接条件设计成这样是有道理的。一个候选(k1)-序列去掉第一个项之后剩下的部分是一个k序列去掉最后一个项之后剩下的也是同一个k序列。只有当两个k-序列拥有相同的躯干时中间部分完全重合才可能通过在一头一尾补项形成(k1)-序列。这跟Apriori里两个k项集必须共享前k-1个项才能连接是同一个逻辑只是从项集扩展到了有结构的序列。举个例子s1{1,2},{3}s2{2,3},{4}。s1去掉第一个项1后得到{2},{3}s2去掉最后一个项4后得到{2,3}。注意这里{2},{3}和{2,3}并不相等前者是两个独立元素后者是同一个元素里装了两个项所以这两条序列不能连接。但如果s2是{2},{3,4}去掉最后一个项4后得到{2},{3}和s1去掉第一个项后的结果相等那么s1和s2就可以连接。2.2 两种连接结果尾巴独立还是一伙连接条件判断完之后真正拼接时还要分两种情况这是GSP最容易写错的分支点。设s1和s2可以连接i是s2的最后一个项。如果i在s2里是独立元素也就是它所在的元素只有i这一个项那么新序列就是在s1末尾追加一个只包含i的新元素。如果i在s2里和其他项待在同一个元素中那么新序列就是s1但把s1的最后一个元素改成原最后一个元素并上{i}。用我之前那两个例子直观看。s1{1,2}s2{2},{3}s2去掉最后一个项3后得到{2}s1去掉第一个项1后得到{2}相等。在s2里最后一项3是独立元素所以新序列是{1,2},{3}也就是先在同一事务里买1和2然后在另一个事务里买3。再看s1{1,2}s2{2,3}同样满足连接条件但s2的最后一项3和2在同一个元素{2,3}里所以新序列是{1,2,3}含义是1、2、3出现在同一个事务中。为什么要分这两种情况因为GSP的序列长度是按项算的不是按事务算的。{1,2}这个序列长度是2含两个项{1},{2}这个序列长度也是2含两个项但它们代表完全不同的行为模式。连接时如果闭着眼把尾巴项直接拼到末尾就会把同元素项集和跨元素先后这两种结构搞混。2.3 剪枝步把Apriori性质搬到序列世界Apriori里有一条核心性质频繁项集的任何非空子集一定频繁。GSP继承了同样的思路但换成了序列版本如果一个k-序列是频繁的那么它的所有(k-1)-子序列也一定频繁反过来如果某个候选(k1)-序列存在一个不频繁的k-子序列那么这个候选序列本身不可能频繁可以直接剪掉。这里的子序列定义很有讲究。GSP里说删除序列中的一个项得到子序列如果删除的那个项所在的元素还有其他项那么保留下来的项继续留在原元素里如果删除后元素变空就把这个空元素去掉后面的元素依次前移。这种保留元素边界的删法和任意挖掉几个位置完全不同。例如序列{1,2},{3}删除项1后得到{2},{3}删除项2后得到{1},{3}删除项3后得到{1,2}只有这三个2-子序列没有{1},{3}之外的其他变形。剪枝步的代价很低收益却非常可观。第4节手工推演中你会看到10个候选里往往有六七个因为某个子序列不频繁而被提前淘汰免去了这些候选参与数据库扫描的开销。连接步负责造剪枝步负责筛这一对组合就是GSP每轮迭代的核心引擎。3. 广义到底广在哪时间约束、滑动窗口与分类层次3.1 max-gap和min-gap限制两个元素之间的时间距离GSP之所以叫Generalized就是因为它不满足于最简单序列先A再B。真实场景里先A再B这个词太模糊了——A和B隔1秒算不算隔1年算不算如果用户先买了一台冰箱一年之后才买了张桌子你把它算成冰箱→桌子的频繁序列对业务几乎没有任何指导意义。所以GSP引入了两个时间约束max-gap限制了数据序列中两个相邻匹配元素的时间戳之差的最大值min-gap限制了这个差的最小值。通俗地说max-gap回答两个行为隔得太远就不算同一条路径min-gap回答两个行为贴得太紧也不像两个独立步骤。举例来说定义min-gap2分钟、max-gap7天那么一条候选序列{浏览A},{购买B}在匹配某个用户日志时浏览A的时间戳和购买B的时间戳必须满足B比A晚至少2分钟并且晚不超过7天。如果B在2分钟之内出现视为同一意图下的连续操作不算两个元素如果B在7天之后才出现视为两条独立路径也不计入支持度。这个设定对真实日志非常实用能滤掉大量噪声但也意味着实现GSP时数据库里每条记录必须带时间戳否则约束无从谈起。3.2 滑动窗口允许松散的同元素前面反复区分同元素和跨元素在理想的分好事务的数据集里一个元素就是一笔事务天然清晰。但很多日志数据根本没有事务边界只有一条条带时间戳的事件。比如用户一小时内浏览了A、B、C三个商品这算一个元素{ A,B,C }还是三个独立元素{A},{B},{C}取决于你的分析粒度。GSP用滑动窗口参数window-size来解决这个问题如果一个元素内各项的时间戳跨度不超过这个窗口大小就把它们视为同一个元素。假设window-size30分钟那么10:00浏览A10:20浏览B在匹配元素{ A,B }时可以算作同一元素如果B是12:00浏览的超过窗口就不能算同一元素只能当作后续元素。窗口参数在电商行为序列、金融交易流水这类高频数据里尤其重要。它把用时间闩锁定义聚合粒度这件事交给了业务方而不是让算法在同一事务这个模糊概念上撞运气。3.3 分类层次把具体商品抽象成品类第三个扩展是分类层次taxonomy。很多数据项的天然结构不是平铺的商品可以归到品牌、品类、类目页面事件可以归到模块、功能、漏斗阶段。GSP允许在匹配前用分类层次做抽象这样挖掘出来的模式就不局限于具体商品A后跟着具体商品B而可以是某个品类出现后某个另一个品类出现。分类层次的实用价值在于缓解数据稀疏。用户买品牌X旗舰手机再买品牌Y充电宝这种模式在单品级别可能只出现一两次根本达不到支持度阈值但上升到手机→充电配件这个品类级别后数据量一下子宽起来模式也更有业务规律。代价是模式语义变粗有时候会失去细节解读能力所以实际应用中我通常建议把单品级和品类级两套结果都跑出来对比着看。3.4 这些约束在实现中意味着什么说了这么多扩展落到代码层面会明确感受到GSP比Apriori难实现的地方支持度扫描不再是简单的子集判断而是带时间条件的序列匹配。计算候选序列{1},{3}在一条用户日志里的支持度时哪怕找到了1在3之前的位置还要验证两个元素的时间戳差是否落在[min-gap, max-gap]区间内窗口越大匹配方式越灵活计算量也随之上升。这也是GSP被后来者诟病慢的一个原因——不仅仅是候选多连单条匹配都比Apriori的项集判断复杂。但反过来如果你要处理的场景恰好需要这些约束多数真实日志场景都如此那么GSP提供的是一整套开箱即用的时间语义而PrefixSpan和SPADE的经典版本反而需要你自己去扩展这些逻辑。这也是我在某些项目中仍然坚持用GSP的最重要理由。4. 手工推演一个完整的小库从L1算到算法终止4.1 输入数据和min_sup设定这一节我准备了一个很小的序列数据库总共6条数据序列每条序列里的尖括号表示一个事务元素逗号分隔同一事务内的不同项。为了省去时间约束的干扰本轮推演只考虑纯顺序不设gap和window。D1: (1,2), (3,4) D2: (1,2), 3 D3: 1, (2,3), 4 D4: (2,3), (1,4) D5: 3, (1,2) D6: 4, (2,3)设定min_sup2也就是一个模式至少要出现在2条数据序列中才算频繁。我不建议在实际项目里把min_sup设成2这么小的数这里纯粹是为了让推演规模可控、能手工复现。先扫一遍数据库统计单项支持度。项1出现在D1、D2、D3、D4、D5共5条序列项2出现在全部6条项3出现在D1、D2、D3、D4、D5、D6共6条项4出现在D1、D3、D4、D6共4条。所以频繁1-序列是{1}、{2}、{3}、{4}记为L1。4.2 L1与C216个候选的过滤过程由L1通过连接步生成候选2-序列时两个长度为1的序列去掉首项和末项后都变成空序列任意两个都能连接。因此所有两个项的有序组合都可能进入候选集既包括同一事务内的项集形式如{1,2}、{2,3}也包括跨事务的先后形式如{1},{3}、{3},{1}。不考虑重复项的无意义情况有效候选大约在18个左右。这一步数据量小手工扫描数据库逐一数支持度是可行的但我相信大部分人没有耐心数完18个。我把最终筛出来的、支持度不低于2的候选2-序列整理成下表候选2-序列含义支持度来自哪些数据序列{1,2}1和2在同一事务中3D1, D2, D5{2,3}2和3在同一事务中3D3, D4, D6{1},{3}先1后33D1, D2, D3{3},{1}先3后12D4, D5{1},{4}先1后42D1, D3{2},{3}先2后32D1, D2{2},{4}先2后43D1, D3, D4{3},{4}先3后42D3, D4其余候选比如{2},{1}只在D4出现、{3},{2}只在D5出现、{2,4}一条都不出现全部因为支持度不足2被淘汰。L2共有8个频繁2-序列。4.3 C3的连接配对与剪枝检查这一轮要做的是用L2里的8个序列两两配对找出满足去掉首项后的序列等于去掉末项后的序列的组合。以A{1,2}为例去掉第一个项1后得到{2}能与它连接的s2必须满足s2去掉最后一个项后也等于{2}。比如s2{2},{3}去掉最后一个项3后得到{2}所以A可以和F{2},{3}连接由于F里的最后一项3是独立元素新序列是{1,2},{3}。把每一组可连接配对的结果和剪枝判定列出来就是下面这张表s1s2连接结果剪枝判定{1,2}{2,3}{1,2,3}不频繁2-子序列{1,3}不存在剪掉{1,2}{2},{3}{1,2},{3}子序列都在L2保留{1,2}{2},{4}{1,2},{4}子序列都在L2保留{2,3}{3},{1}{2,3},{1}子序列{2},{1}不在L2剪掉{2,3}{3},{4}{2,3},{4}子序列都在L2保留{1},{3}{3},{1}{1},{3},{1}子序列{1},{1}不在L2剪掉{1},{3}{3},{4}{1},{3},{4}子序列都在L2保留注意尾巴是独立元素{3},{1}{1,2}{3},{1,2}子序列{3},{2}不在L2剪掉{2},{3}{3},{1}{2},{3},{1}子序列{2},{1}不在L2剪掉{2},{3}{3},{4}{2},{3},{4}子序列都在L2保留经过剪枝候选3-序列只剩5个{1,2},{3}、{1,2},{4}、{2,3},{4}、{1},{3},{4}、{2},{3},{4}。4.4 L3支持度扫描与C4终止现在重新扫描数据库计算这5个候选的支持度。这里最容易数错的是候选里的不同元素必须匹配数据序列里的不同事务元素同一个事务里的项不能拆出来同时充当两个元素。{1,2},{3}在D1和D2各出现一次D1中3藏在{3,4}元素里D2中3是独立元素支持度2{1,2},{4}只有D1支持支持度1{2,3},{4}在D3和D4支持支持度2{1},{3},{4}在D3支持D1虽然同时有1、3、4但3和4落在同一个元素里不能拆成两个独立元素去匹配候选的{3}和{4}所以不算支持度1{2},{3},{4}支持度0D3里2和3在同元素内不能拆D6里4在2和3之前顺序不对。L3最终为3{1,2},{3}和{2,3},{4}。进入第4轮时s1{1,2},{3}去掉首项后是{2},{3}s2{2,3},{4}去掉末项后是{2,3}两者不相等反向组合也同理不相等。没有任何可连接配对C4为空算法终止。最终输出是L1、L2、L3的并集。整个手工推演里值得记住的一课是剪枝步在第3轮砍掉了5个候选中的一半而连接步又精确控制了候选的增长形态没有这两步的配合候选膨胀会非常快。5. 实际应用中必须处理的三个问题5.1 支持度阈值怎么定很多教程讲完算法就结束但真正跑数据时第一个问题就是min_sup该设多少如果数据有1万条用户序列min_sup1%就是100条用户这个量级的模式通常才有点业务意义。我的习惯是先设一个偏高的阈值比如5%看跑出来的数据大概有多少然后逐步往下调到2%、1%直到频繁序列的数量出现明显增长为止。如果某一次调试结果突然从几百条跳到上万条说明阈值已经越过了一个模式质量悬崖再往下跑只会得到一堆噪声。用绝对计数还是百分比取决于你的产出物形态。团队内部做分析时我倾向于用绝对计数因为至少100个用户出现该序列比支持度0.8%更容易和业务方沟通算法落地为定期任务时用百分比更稳妥因为用户规模每天在增长固定绝对阈值会导致模式数量越来越不稳定。5.2 候选爆炸怎么扛GSP最被人诟病的就是候选集爆炸。如果你的数据里有大量单项频繁出现第2轮生成的候选2-序列数量是O(n^2)n是频繁1-序列个数第3轮开始虽然有了剪枝约束但候选规模依然可能大到内存吃紧。我在一台8G内存的机器上跑过几十万个单项的日志数据C2生成阶段直接把内存撑爆过教训非常深刻。可行的缓解手段有几种。第一提高min_sup这是最粗暴也最有效的方法频繁1-序列数量一降后面全链条都轻松。第二在生成候选时严格利用剪枝步不要等全部候选生成完再统一剪而是每生成一个候选立刻检查子序列是否频繁尽早丢弃。第三如果数据是稀疏的、用户数巨大且序列很长建议直接用SPADE或PrefixSpan别在GSP上强行优化——这两类算法本质上就是在解决GSP的候选爆炸问题。还有个小技巧如果单条序列内部项数较多先把序列长度做截断比如只保留每个用户时间上最近的50个事件这样能大幅降低匹配成本。截断会损失部分长序列模式但换来的是整体运行速度的提升很多时候是值得的。5.3 时间戳与数据质量最容易翻车的环节GSP的匹配结果对时间戳极度敏感而数据工程上时间戳恰恰是最容易出问题的地方。我见过某同学把毫秒时间戳当成秒去做max-gap计算导致窗口被放大了1000倍也见过移动端埋点和服务端日志合并时两套时钟差了十几分钟结果顺序被整体反转一条浏览→支付的路径硬生生算成了支付→浏览。处理这类问题我现在的流程是固定三步先统一所有日志的时间戳单位全部转成秒级或毫秒级并做字段注释再做一次单用户序列有效性校验抽查10个用户按时间顺序打印序列确认没有乱序最后再进入GSP扫描。整个过程听起来很基础但能绕开后面至少三个小时的排查时间。另外min-gap和max-gap这两个参数如果带业务含义一定要让业务方把多久算同一次路径的预期讲清楚而不是自己拍脑袋。业务上一次购买路径和两次独立购买路径的边界往往比你想象中复杂得多。6. GSP和PrefixSpan、SPADE放在一起怎么选6.1 三种算法的本质差异GSP走的是候选生成—测试的路线每层都造一堆候选再用全库扫描去验证开销集中在候选集的构建和多轮扫描上。PrefixSpan走的是前缀投影的路线从长度为1的频繁前缀开始把包含此前缀的数据序列投影到后续部分递归地挖掘增长模式全程不生成候选2-序列避免了大量无谓的候选验证。SPADE走的是垂直数据格式的路线把每个项转换成它在所有序列中出现的ID列表支持度计算变成集合交集理论上只需要扫描数据库一到三次后续都在内存里用格点遍历完成。这三种路线各有各的代价。GSP的代价是重复扫描全库PrefixSpan的代价是投影数据库会不断膨胀递归深度也容易失控SPADE的代价是垂直ID列表在数据量大时非常占内存且对时间约束等扩展支持需要额外改造。6.2 一张表看场景取舍维度GSPPrefixSpanSPADE核心策略候选生成剪枝前缀投影递归增长垂直格式列表交集数据库扫描每一层都要扫全库逐层扫描投影库通常1到3次全库内存压力候选集明显膨胀投影库累积开销大垂直列表开销大原生时间约束支持max-gap/min-gap/window需要自行扩展需要自行扩展模式可解释性高每一步可手工核查中递归过程较抽象中典型适用中小数据、教学、带时间窗需求长序列、稠密数据大但规整的数据实现难度中细节多中高高从这张表的最后一行也能看出我的倾向如果你是要快速理解序列模式挖掘GSP是最合适的入口如果数据量已经大到GSP跑不动而且没有复杂的时间约束PrefixSpan通常是工程上更轻松的选择如果数据规模更大、结构规整SPADE的垂直格式路线则值得认真考虑。6.3 什么情况下我仍然推荐先把GSP实现一遍即便PrefixSpan和SPADE在效率上普遍优于GSP我仍然建议每一位接触序列模式挖掘的同学先动手把GSP完整实现一遍。原因很简单GSP的候选生成逻辑把项、元素、序列长度、子序列这些最基础也最容易混淆的概念全部暴露了一遍你把这些概念捋清楚了后面看任何序列挖掘算法都不会再有概念悬空的感觉。我在实际项目里也保留着GSP的用武之地当业务方明确要求两个行为间隔不能超过N天这类时间约束时GSP的原生支持让改造成本最低当数据量只有几万用户、模式可解释性优先时GSP跑出来的结果每一步都能手算验证比黑盒式的优化算法更合适。最后分享一个我自己的习惯第一次跑GSP时先用一条SQL把原始日志转成用户ID、项、时间戳的三列表再用一个简单的脚本去掉明显的时间戳脏数据然后才进入算法流程。C2生成阶段如果频繁序列的数量超过预期我会先在内存里打印出Top 20候选的构成快速判断是阈值问题还是数据问题而不是傻等它跑完。这轮流程走完你对自己的数据分布会有远超普通报表的理解这份理解才是GSP留给你最值钱的产出。 
长河君 · 2026/10/16 20:45:57 · 阅读 1.2k GSP算法详解：序列模式挖掘的候选生成与剪枝实践
做用户行为分析的时候我经常要面对一长串带时间戳的操作日志用户先点了A页面隔了一会儿又点了B按钮最后在C页面完成转化。普通关联规则只能告诉你A商品和B商品经常一起出现在同一笔订单里但没法回答用户买了A之后多久之内买B才算一条有价值的转化路径。这时候就需要序列模式挖掘出手。GSP算法是这个领域最经典的起点我最初就是靠它把序列模式这四个字真正弄明白的也是在用它跑真实日志、踩完一轮坑之后才理解后面那些更花哨的算法到底在优化什么。这篇文章不打算做成教科书式的算法讲解而是按我自己实现和应用GSP时的思路来写先说明为什么序列数据不能直接套关联规则再把GSP的候选生成、支持度扫描、时间约束这几个核心环节拆开讲透最后用一个手工可复算的小例子走完整轮迭代并补上真实应用中容易翻车的地方。目标读者是想自己动手实现序列模式挖掘、或者在课堂上被GSP弄得一头雾水的同学。看完之后你能亲手算出每一层候选怎么来、为什么被剪、支持度怎么数也能在项目里判断GSP到底合不合适。1. 为什么序列数据需要一种会排队的关联规则1.1 从购物篮到购物车序列多了一个先后维度经典关联规则处理的是购物篮数据每一行是一个事务比如订单号、包含的商品集合。它只关心哪些商品经常在同一笔订单里共现输出类似买啤酒的人也买尿布这样的规则。这种建模方式把所有事务看成彼此独立的袋子袋子里面的商品没有先后之分袋子之间也没有顺序关系。但很多真实问题天然是带顺序的。用户在电商网站上的行为是一条路径先浏览商品详情页再加入购物车最后提交订单患者就医是一串事件挂号、检查、开药、复诊设备故障是一组报警告警A发生后过一段时间告警B触发再往后是告警C。这些数据如果强行压成购物篮把每个用户的所有行为揉成一袋子你会丢掉先后这个最关键的信息也就无法回答用户做出某个行为之后下一个最可能做什么。序列模式挖掘就是把顺序放回数据里。它要找的模式不是啤酒和尿布共现而是啤酒出现之后隔了若干时间尿布也会出现。GSP算法Generalized Sequential Pattern正是最早也最经典的解决方案之一由研究者们在1996年前后提出核心思路是从频繁1-序列开始逐层生成更长的候选序列再扫描数据库验证支持度直到无法生成新候选为止。后面出现的PrefixSpan、SPADE等算法可以说都是在和GSP候选太多、扫描太多次这两个毛病作斗争。1.2 Apriori直接搬过来为什么必错刚接触序列挖掘的人最容易犯的错是把关联规则里的Apriori算法原封不动搬过来用。表面上两者确实很像都是候选生成—支持度验证—剪枝的框架都要维护频繁项集的子集一定频繁这条性质。但有一个关键差异会让Apriori直接失效Apriori处理的是同一个事务内部的共现关系项与项之间没有时间先后而序列模式里的顺序信息是发生在不同事务之间的。举个例子Apriori里{面包, 牛奶}这个项集表示一笔订单里同时包含面包和牛奶支持度计算只要看某一笔订单是否同时包含这两项。但在序列数据里面包→牛奶和牛奶→面包是两个完全不同的模式前者表示先买面包再买牛奶后者相反。如果只统计同时出现就会把两种顺序完全不同的行为混成一条模式质量大打折扣。更麻烦的是序列数据里还要区分同一个事务内的多项和不同事务间的先后。同样两条日志一条是用户在同一个订单里买了面包和牛奶另一条是用户先下了一单买面包隔天又下了一单买牛奶前者对应同元素项集{面包,牛奶}后者对应序列{面包},{牛奶}。这两种形态在GSP里是不同长度的序列在Apriori眼里却可能是同一条记录。所以把Apriori直接搬过来第一步建候选就建错了。1.3 GSP的基本流程和Apriori同款骨架换了内脏GSP的整体流程和Apriori非常像但每一步都针对序列数据做了重新定义。算法从扫描数据库、统计每个单项的支持度开始把支持度不小于min_sup的单项组成频繁1-序列然后进入迭代循环第k轮用频繁k-序列通过连接生成候选(k1)-序列再用剪枝删除那些存在非频繁子序列的候选接着重新扫描数据库统计每个候选序列的支持度过滤得到新的频繁(k1)-序列。直到某一轮连接生成不出任何新候选算法结束输出所有频繁序列。整个过程可以概括为四步扫描一次数据库统计所有单项的出现频次得到频繁1-序列。由频繁k-序列集合第1轮时k1通过连接步生成候选(k1)-序列集合。对候选集合做剪枝只要某个候选序列存在一个长度为k的子序列不在频繁k-序列集合里就把它删掉。再扫描数据库计算每个候选序列的真实支持度保留不小于min_sup的候选得到频繁(k1)-序列。重复第2到第4步直到某次生成的候选全部被剪掉或全部不满足支持度为止。这里的每一步都有个序列版的细节连接步不再是简单地把两个项集拼在一起而是要处理项和元素两个层次剪枝步里的子序列也不是任意删掉几个项而是保持原有元素边界删项。这些细节正是新手最容易写错的地方下一节我把它们一个个掰开讲。2. GSP候选生成的两个算子连接步和剪枝步2.1 连接步先比腰再看尾连接步的目的是从两个频繁k-序列合并出一个候选(k1)-序列。GSP的连接条件比Apriori多了个弯给定两个频繁k-序列s1和s2先把s1去掉第一个项注意是第一个项不是第一个元素再把s2去掉最后一个项如果去掉之后得到的两个序列完全相等那么s1和s2可以连接。很多人第一次实现GSP就栽在这个去掉第一个项上。什么叫去掉第一个项比如序列{1,2},{3}第一个元素是{1,2}去掉第一个项1之后这个元素还剩{2}所以去掉第一个项后的序列是{2},{3}。如果你理解成去掉第一个元素得到的就是{3}那连接条件就完全错了。连接条件设计成这样是有道理的。一个候选(k1)-序列去掉第一个项之后剩下的部分是一个k序列去掉最后一个项之后剩下的也是同一个k序列。只有当两个k-序列拥有相同的躯干时中间部分完全重合才可能通过在一头一尾补项形成(k1)-序列。这跟Apriori里两个k项集必须共享前k-1个项才能连接是同一个逻辑只是从项集扩展到了有结构的序列。举个例子s1{1,2},{3}s2{2,3},{4}。s1去掉第一个项1后得到{2},{3}s2去掉最后一个项4后得到{2,3}。注意这里{2},{3}和{2,3}并不相等前者是两个独立元素后者是同一个元素里装了两个项所以这两条序列不能连接。但如果s2是{2},{3,4}去掉最后一个项4后得到{2},{3}和s1去掉第一个项后的结果相等那么s1和s2就可以连接。2.2 两种连接结果尾巴独立还是一伙连接条件判断完之后真正拼接时还要分两种情况这是GSP最容易写错的分支点。设s1和s2可以连接i是s2的最后一个项。如果i在s2里是独立元素也就是它所在的元素只有i这一个项那么新序列就是在s1末尾追加一个只包含i的新元素。如果i在s2里和其他项待在同一个元素中那么新序列就是s1但把s1的最后一个元素改成原最后一个元素并上{i}。用我之前那两个例子直观看。s1{1,2}s2{2},{3}s2去掉最后一个项3后得到{2}s1去掉第一个项1后得到{2}相等。在s2里最后一项3是独立元素所以新序列是{1,2},{3}也就是先在同一事务里买1和2然后在另一个事务里买3。再看s1{1,2}s2{2,3}同样满足连接条件但s2的最后一项3和2在同一个元素{2,3}里所以新序列是{1,2,3}含义是1、2、3出现在同一个事务中。为什么要分这两种情况因为GSP的序列长度是按项算的不是按事务算的。{1,2}这个序列长度是2含两个项{1},{2}这个序列长度也是2含两个项但它们代表完全不同的行为模式。连接时如果闭着眼把尾巴项直接拼到末尾就会把同元素项集和跨元素先后这两种结构搞混。2.3 剪枝步把Apriori性质搬到序列世界Apriori里有一条核心性质频繁项集的任何非空子集一定频繁。GSP继承了同样的思路但换成了序列版本如果一个k-序列是频繁的那么它的所有(k-1)-子序列也一定频繁反过来如果某个候选(k1)-序列存在一个不频繁的k-子序列那么这个候选序列本身不可能频繁可以直接剪掉。这里的子序列定义很有讲究。GSP里说删除序列中的一个项得到子序列如果删除的那个项所在的元素还有其他项那么保留下来的项继续留在原元素里如果删除后元素变空就把这个空元素去掉后面的元素依次前移。这种保留元素边界的删法和任意挖掉几个位置完全不同。例如序列{1,2},{3}删除项1后得到{2},{3}删除项2后得到{1},{3}删除项3后得到{1,2}只有这三个2-子序列没有{1},{3}之外的其他变形。剪枝步的代价很低收益却非常可观。第4节手工推演中你会看到10个候选里往往有六七个因为某个子序列不频繁而被提前淘汰免去了这些候选参与数据库扫描的开销。连接步负责造剪枝步负责筛这一对组合就是GSP每轮迭代的核心引擎。3. 广义到底广在哪时间约束、滑动窗口与分类层次3.1 max-gap和min-gap限制两个元素之间的时间距离GSP之所以叫Generalized就是因为它不满足于最简单序列先A再B。真实场景里先A再B这个词太模糊了——A和B隔1秒算不算隔1年算不算如果用户先买了一台冰箱一年之后才买了张桌子你把它算成冰箱→桌子的频繁序列对业务几乎没有任何指导意义。所以GSP引入了两个时间约束max-gap限制了数据序列中两个相邻匹配元素的时间戳之差的最大值min-gap限制了这个差的最小值。通俗地说max-gap回答两个行为隔得太远就不算同一条路径min-gap回答两个行为贴得太紧也不像两个独立步骤。举例来说定义min-gap2分钟、max-gap7天那么一条候选序列{浏览A},{购买B}在匹配某个用户日志时浏览A的时间戳和购买B的时间戳必须满足B比A晚至少2分钟并且晚不超过7天。如果B在2分钟之内出现视为同一意图下的连续操作不算两个元素如果B在7天之后才出现视为两条独立路径也不计入支持度。这个设定对真实日志非常实用能滤掉大量噪声但也意味着实现GSP时数据库里每条记录必须带时间戳否则约束无从谈起。3.2 滑动窗口允许松散的同元素前面反复区分同元素和跨元素在理想的分好事务的数据集里一个元素就是一笔事务天然清晰。但很多日志数据根本没有事务边界只有一条条带时间戳的事件。比如用户一小时内浏览了A、B、C三个商品这算一个元素{ A,B,C }还是三个独立元素{A},{B},{C}取决于你的分析粒度。GSP用滑动窗口参数window-size来解决这个问题如果一个元素内各项的时间戳跨度不超过这个窗口大小就把它们视为同一个元素。假设window-size30分钟那么10:00浏览A10:20浏览B在匹配元素{ A,B }时可以算作同一元素如果B是12:00浏览的超过窗口就不能算同一元素只能当作后续元素。窗口参数在电商行为序列、金融交易流水这类高频数据里尤其重要。它把用时间闩锁定义聚合粒度这件事交给了业务方而不是让算法在同一事务这个模糊概念上撞运气。3.3 分类层次把具体商品抽象成品类第三个扩展是分类层次taxonomy。很多数据项的天然结构不是平铺的商品可以归到品牌、品类、类目页面事件可以归到模块、功能、漏斗阶段。GSP允许在匹配前用分类层次做抽象这样挖掘出来的模式就不局限于具体商品A后跟着具体商品B而可以是某个品类出现后某个另一个品类出现。分类层次的实用价值在于缓解数据稀疏。用户买品牌X旗舰手机再买品牌Y充电宝这种模式在单品级别可能只出现一两次根本达不到支持度阈值但上升到手机→充电配件这个品类级别后数据量一下子宽起来模式也更有业务规律。代价是模式语义变粗有时候会失去细节解读能力所以实际应用中我通常建议把单品级和品类级两套结果都跑出来对比着看。3.4 这些约束在实现中意味着什么说了这么多扩展落到代码层面会明确感受到GSP比Apriori难实现的地方支持度扫描不再是简单的子集判断而是带时间条件的序列匹配。计算候选序列{1},{3}在一条用户日志里的支持度时哪怕找到了1在3之前的位置还要验证两个元素的时间戳差是否落在[min-gap, max-gap]区间内窗口越大匹配方式越灵活计算量也随之上升。这也是GSP被后来者诟病慢的一个原因——不仅仅是候选多连单条匹配都比Apriori的项集判断复杂。但反过来如果你要处理的场景恰好需要这些约束多数真实日志场景都如此那么GSP提供的是一整套开箱即用的时间语义而PrefixSpan和SPADE的经典版本反而需要你自己去扩展这些逻辑。这也是我在某些项目中仍然坚持用GSP的最重要理由。4. 手工推演一个完整的小库从L1算到算法终止4.1 输入数据和min_sup设定这一节我准备了一个很小的序列数据库总共6条数据序列每条序列里的尖括号表示一个事务元素逗号分隔同一事务内的不同项。为了省去时间约束的干扰本轮推演只考虑纯顺序不设gap和window。D1: (1,2), (3,4) D2: (1,2), 3 D3: 1, (2,3), 4 D4: (2,3), (1,4) D5: 3, (1,2) D6: 4, (2,3)设定min_sup2也就是一个模式至少要出现在2条数据序列中才算频繁。我不建议在实际项目里把min_sup设成2这么小的数这里纯粹是为了让推演规模可控、能手工复现。先扫一遍数据库统计单项支持度。项1出现在D1、D2、D3、D4、D5共5条序列项2出现在全部6条项3出现在D1、D2、D3、D4、D5、D6共6条项4出现在D1、D3、D4、D6共4条。所以频繁1-序列是{1}、{2}、{3}、{4}记为L1。4.2 L1与C216个候选的过滤过程由L1通过连接步生成候选2-序列时两个长度为1的序列去掉首项和末项后都变成空序列任意两个都能连接。因此所有两个项的有序组合都可能进入候选集既包括同一事务内的项集形式如{1,2}、{2,3}也包括跨事务的先后形式如{1},{3}、{3},{1}。不考虑重复项的无意义情况有效候选大约在18个左右。这一步数据量小手工扫描数据库逐一数支持度是可行的但我相信大部分人没有耐心数完18个。我把最终筛出来的、支持度不低于2的候选2-序列整理成下表候选2-序列含义支持度来自哪些数据序列{1,2}1和2在同一事务中3D1, D2, D5{2,3}2和3在同一事务中3D3, D4, D6{1},{3}先1后33D1, D2, D3{3},{1}先3后12D4, D5{1},{4}先1后42D1, D3{2},{3}先2后32D1, D2{2},{4}先2后43D1, D3, D4{3},{4}先3后42D3, D4其余候选比如{2},{1}只在D4出现、{3},{2}只在D5出现、{2,4}一条都不出现全部因为支持度不足2被淘汰。L2共有8个频繁2-序列。4.3 C3的连接配对与剪枝检查这一轮要做的是用L2里的8个序列两两配对找出满足去掉首项后的序列等于去掉末项后的序列的组合。以A{1,2}为例去掉第一个项1后得到{2}能与它连接的s2必须满足s2去掉最后一个项后也等于{2}。比如s2{2},{3}去掉最后一个项3后得到{2}所以A可以和F{2},{3}连接由于F里的最后一项3是独立元素新序列是{1,2},{3}。把每一组可连接配对的结果和剪枝判定列出来就是下面这张表s1s2连接结果剪枝判定{1,2}{2,3}{1,2,3}不频繁2-子序列{1,3}不存在剪掉{1,2}{2},{3}{1,2},{3}子序列都在L2保留{1,2}{2},{4}{1,2},{4}子序列都在L2保留{2,3}{3},{1}{2,3},{1}子序列{2},{1}不在L2剪掉{2,3}{3},{4}{2,3},{4}子序列都在L2保留{1},{3}{3},{1}{1},{3},{1}子序列{1},{1}不在L2剪掉{1},{3}{3},{4}{1},{3},{4}子序列都在L2保留注意尾巴是独立元素{3},{1}{1,2}{3},{1,2}子序列{3},{2}不在L2剪掉{2},{3}{3},{1}{2},{3},{1}子序列{2},{1}不在L2剪掉{2},{3}{3},{4}{2},{3},{4}子序列都在L2保留经过剪枝候选3-序列只剩5个{1,2},{3}、{1,2},{4}、{2,3},{4}、{1},{3},{4}、{2},{3},{4}。4.4 L3支持度扫描与C4终止现在重新扫描数据库计算这5个候选的支持度。这里最容易数错的是候选里的不同元素必须匹配数据序列里的不同事务元素同一个事务里的项不能拆出来同时充当两个元素。{1,2},{3}在D1和D2各出现一次D1中3藏在{3,4}元素里D2中3是独立元素支持度2{1,2},{4}只有D1支持支持度1{2,3},{4}在D3和D4支持支持度2{1},{3},{4}在D3支持D1虽然同时有1、3、4但3和4落在同一个元素里不能拆成两个独立元素去匹配候选的{3}和{4}所以不算支持度1{2},{3},{4}支持度0D3里2和3在同元素内不能拆D6里4在2和3之前顺序不对。L3最终为3{1,2},{3}和{2,3},{4}。进入第4轮时s1{1,2},{3}去掉首项后是{2},{3}s2{2,3},{4}去掉末项后是{2,3}两者不相等反向组合也同理不相等。没有任何可连接配对C4为空算法终止。最终输出是L1、L2、L3的并集。整个手工推演里值得记住的一课是剪枝步在第3轮砍掉了5个候选中的一半而连接步又精确控制了候选的增长形态没有这两步的配合候选膨胀会非常快。5. 实际应用中必须处理的三个问题5.1 支持度阈值怎么定很多教程讲完算法就结束但真正跑数据时第一个问题就是min_sup该设多少如果数据有1万条用户序列min_sup1%就是100条用户这个量级的模式通常才有点业务意义。我的习惯是先设一个偏高的阈值比如5%看跑出来的数据大概有多少然后逐步往下调到2%、1%直到频繁序列的数量出现明显增长为止。如果某一次调试结果突然从几百条跳到上万条说明阈值已经越过了一个模式质量悬崖再往下跑只会得到一堆噪声。用绝对计数还是百分比取决于你的产出物形态。团队内部做分析时我倾向于用绝对计数因为至少100个用户出现该序列比支持度0.8%更容易和业务方沟通算法落地为定期任务时用百分比更稳妥因为用户规模每天在增长固定绝对阈值会导致模式数量越来越不稳定。5.2 候选爆炸怎么扛GSP最被人诟病的就是候选集爆炸。如果你的数据里有大量单项频繁出现第2轮生成的候选2-序列数量是O(n^2)n是频繁1-序列个数第3轮开始虽然有了剪枝约束但候选规模依然可能大到内存吃紧。我在一台8G内存的机器上跑过几十万个单项的日志数据C2生成阶段直接把内存撑爆过教训非常深刻。可行的缓解手段有几种。第一提高min_sup这是最粗暴也最有效的方法频繁1-序列数量一降后面全链条都轻松。第二在生成候选时严格利用剪枝步不要等全部候选生成完再统一剪而是每生成一个候选立刻检查子序列是否频繁尽早丢弃。第三如果数据是稀疏的、用户数巨大且序列很长建议直接用SPADE或PrefixSpan别在GSP上强行优化——这两类算法本质上就是在解决GSP的候选爆炸问题。还有个小技巧如果单条序列内部项数较多先把序列长度做截断比如只保留每个用户时间上最近的50个事件这样能大幅降低匹配成本。截断会损失部分长序列模式但换来的是整体运行速度的提升很多时候是值得的。5.3 时间戳与数据质量最容易翻车的环节GSP的匹配结果对时间戳极度敏感而数据工程上时间戳恰恰是最容易出问题的地方。我见过某同学把毫秒时间戳当成秒去做max-gap计算导致窗口被放大了1000倍也见过移动端埋点和服务端日志合并时两套时钟差了十几分钟结果顺序被整体反转一条浏览→支付的路径硬生生算成了支付→浏览。处理这类问题我现在的流程是固定三步先统一所有日志的时间戳单位全部转成秒级或毫秒级并做字段注释再做一次单用户序列有效性校验抽查10个用户按时间顺序打印序列确认没有乱序最后再进入GSP扫描。整个过程听起来很基础但能绕开后面至少三个小时的排查时间。另外min-gap和max-gap这两个参数如果带业务含义一定要让业务方把多久算同一次路径的预期讲清楚而不是自己拍脑袋。业务上一次购买路径和两次独立购买路径的边界往往比你想象中复杂得多。6. GSP和PrefixSpan、SPADE放在一起怎么选6.1 三种算法的本质差异GSP走的是候选生成—测试的路线每层都造一堆候选再用全库扫描去验证开销集中在候选集的构建和多轮扫描上。PrefixSpan走的是前缀投影的路线从长度为1的频繁前缀开始把包含此前缀的数据序列投影到后续部分递归地挖掘增长模式全程不生成候选2-序列避免了大量无谓的候选验证。SPADE走的是垂直数据格式的路线把每个项转换成它在所有序列中出现的ID列表支持度计算变成集合交集理论上只需要扫描数据库一到三次后续都在内存里用格点遍历完成。这三种路线各有各的代价。GSP的代价是重复扫描全库PrefixSpan的代价是投影数据库会不断膨胀递归深度也容易失控SPADE的代价是垂直ID列表在数据量大时非常占内存且对时间约束等扩展支持需要额外改造。6.2 一张表看场景取舍维度GSPPrefixSpanSPADE核心策略候选生成剪枝前缀投影递归增长垂直格式列表交集数据库扫描每一层都要扫全库逐层扫描投影库通常1到3次全库内存压力候选集明显膨胀投影库累积开销大垂直列表开销大原生时间约束支持max-gap/min-gap/window需要自行扩展需要自行扩展模式可解释性高每一步可手工核查中递归过程较抽象中典型适用中小数据、教学、带时间窗需求长序列、稠密数据大但规整的数据实现难度中细节多中高高从这张表的最后一行也能看出我的倾向如果你是要快速理解序列模式挖掘GSP是最合适的入口如果数据量已经大到GSP跑不动而且没有复杂的时间约束PrefixSpan通常是工程上更轻松的选择如果数据规模更大、结构规整SPADE的垂直格式路线则值得认真考虑。6.3 什么情况下我仍然推荐先把GSP实现一遍即便PrefixSpan和SPADE在效率上普遍优于GSP我仍然建议每一位接触序列模式挖掘的同学先动手把GSP完整实现一遍。原因很简单GSP的候选生成逻辑把项、元素、序列长度、子序列这些最基础也最容易混淆的概念全部暴露了一遍你把这些概念捋清楚了后面看任何序列挖掘算法都不会再有概念悬空的感觉。我在实际项目里也保留着GSP的用武之地当业务方明确要求两个行为间隔不能超过N天这类时间约束时GSP的原生支持让改造成本最低当数据量只有几万用户、模式可解释性优先时GSP跑出来的结果每一步都能手算验证比黑盒式的优化算法更合适。最后分享一个我自己的习惯第一次跑GSP时先用一条SQL把原始日志转成用户ID、项、时间戳的三列表再用一个简单的脚本去掉明显的时间戳脏数据然后才进入算法流程。C2生成阶段如果频繁序列的数量超过预期我会先在内存里打印出Top 20候选的构成快速判断是阈值问题还是数据问题而不是傻等它跑完。这轮流程走完你对自己的数据分布会有远超普通报表的理解这份理解才是GSP留给你最值钱的产出。