2
【Apriori】关联规则
source link: https://www.guofei.site/2017/11/26/apriori.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
【Apriori】关联规则
2017年11月26日Author: Guofei
文章归类: 3-3-图模型 ，文章编号: 350
版权声明：本文作者是郭飞。转载随意，但需要标明原文链接，并通知本人
原文链接：https://www.guofei.site/2017/11/26/apriori.html
模型
定义
支持度(surpport) LHS和RHS所包含的商品同事出现的概率 置信度(confidenct) 购买左项商品的情况下，又购买了右项商品的条件概率 提升度(lift) 置信度/右项的概率，提升度>1表示正关联，提升度<1表示副关联。 频繁项集 支持度高于某个阈值的项集
方案
关联规则挖掘，通常需要我们找出支持度和置信度高于阈值的规则。
通常算法的复杂度是相当高的，Apriori算法可以大大降低算法复杂度。
先验性质(Apriori):频繁项集的所有非空子集一定是频繁项集
通过这个先验性质，可以大大减少搜索空间，提高效率
算法：
先找频繁1项集，
迭代，从频繁i-1项集中找频繁i项集
计算confidence, confidence(A→B)surpport(AB)surpportAconfidence(A→B)surpport(AB)surpportA
FP-tree
- 生成一个树，FP-tree
- 每个事物映射到一条路径上。不同的事务有可能会有重叠的路径，重叠越多，压缩效果越好
- 仅需扫描2次数据库，计算复杂度大大降低
step1：扫描数据库，得到频繁1-项集，并按照support降序排序
step2：扫描数据库，构造FP-tree
step3：从下往上搜索FP-tree
Python实现
您的支持将鼓励我继续创作！
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK