Apriori 算法

定义

Apriori 算法由 Rakesh Agrawal 与 Ramakrishnan Srikant 于 1994 年提出,用于从交易数据库中挖掘频繁项集并生成关联规则,是关联分析(购物篮分析)领域的奠基性算法。

原理

算法依赖"先验性质"(Apriori property):频繁项集的任何子集必然频繁,反之非频繁项集的超集必不频繁。据此逐层搜索:先扫描数据找出频繁 1-项集,再由 k-项集自连接生成 k+1 候选集并用先验性质剪枝,重复扫描计数直到无新频繁集产生;最后从频繁项集中生成满足最小置信度的关联规则,常用支持度、置信度、提升度(lift)三个指标评价。

优缺点

思想简洁、易于实现;但需要多次扫描数据库且候选集可能爆炸,效率是主要瓶颈,FP-Growth 等后继算法针对性地做了改进。

应用

经典应用包括零售商品搭配分析、交叉销售、网站访问模式挖掘。