模型
定义
- 支持度(surpport)
- LHS和RHS所包含的商品同事出现的概率
- 置信度(confidenct)
- 购买左项商品的情况下，又购买了右项商品的条件概率
- 提升度(lift)
- 置信度/右项的概率，
提升度>1表示正关联，提升度<1表示副关联。 - 频繁项集
- 支持度高于某个阈值的项集
方案
关联规则挖掘，通常需要我们找出支持度和置信度高于阈值的规则。
通常算法的复杂度是相当高的，Apriori算法可以大大降低算法复杂度。
先验性质(Apriori):频繁项集的所有非空子集一定是频繁项集
通过这个先验性质，可以大大减少搜索空间，提高效率
算法：
先找频繁1项集，
迭代，从频繁i-1项集中找频繁i项集
计算confidence, $confidence(A \to B) \dfrac{surpport (AB)}{surpport A}$
FP-tree
- 生成一个树，FP-tree
- 每个事物映射到一条路径上。不同的事务有可能会有重叠的路径，重叠越多，压缩效果越好
- 仅需扫描2次数据库，计算复杂度大大降低
step1：扫描数据库，得到频繁1-项集，并按照support降序排序
step2：扫描数据库，构造FP-tree
step3：从下往上搜索FP-tree
