案例库 · 研发与科研 · 技术决策 · 1994
IBM的Apriori通过剪枝不可能的候选项来挖掘顾客一起购买的商品
Agrawal和Srikant在1994年提出的Apriori算法利用子集规则提前剪枝，从海量交易日志中找出频繁项集。
IBM阿尔马登研究中心
那一手
零售商想知道哪些商品会被一起购买，但随着商品种类（SKU）的增加，可能的商品组合数量呈指数级爆炸。
1994年发表的Apriori算法利用了这样一个性质：任何不频繁项集的超集也必然不频繁。它先统计单品数量，保留频繁项，将它们组合成对并重复，因此绝不会计算那些父项已失败的候选。
这一技巧将原本迅速变得难以管理的搜索，转化为只触及频繁集合的小前沿。它让购物篮分析变成了一种实用的数据库查询。
为什么管用
- 向下封闭性在搜索增长之前就进行了剪枝，因此运行时间与频繁集相关，而非全部集合。
- 每层扫描数据库，使内存仅受候选集限制。
- 它给出精确的频繁集，而非启发式或抽样近似。
- 同样的剪枝方法可推广到序列和模式挖掘，不仅限于购物篮。
值了多少如果一个集合是稀有的，那么它的所有超集也是稀有的聪明
可以搬走什么
在搜索巨大空间之前，寻找一个单调性质，让你能一次丢弃整个分支。一条能排除区域的规则，能将搜索从指数级缩减至线性。
后来呢
Apriori成为经典的关联规则算法和数据挖掘的标准课程。它催生了推荐、品类和交叉销售分析等领域，后来FP-Growth等方法进一步减少了扫描次数。
资料来源
发现哪里写错了？告诉我们。