相关问题——啤酒与尿布
| TID | Items |
|---|---|
| 1 | Bread, Milk |
| 2 | Bread, Diaper, Beer, Eggs |
| 3 | Milk, Diaper, Beer, Coke |
| 4 | Bread, Milk, Diaper, Beer |
| 5 | Bread, Milk, Diaper, Coke |
关联规则是形如的蕴含表达式，其中X和Y是不想交的项集。关联规则的强度可以用它的支持度(support)和置信度(confidence)来度量。支持度确定规则可以数据集的频繁程度，置信度确定Y在包含X的交易中出现的频繁程度。
支持度形式定义：
置信度形式定义：
关联规则挖掘的目标：已知所有交易的集合T和购物篮数据所有项集合I，找到所有满足以下条件的规则
- support
minsupthreshold
- confidence
关联规则挖掘任务分解为如下两个主要任务：
- 频繁项集的产生，目标是发现满足最小支持度阈值的所有项集，称作频繁项集。
- 规则的产生，目标是从上一步发现的频繁项集中提取所有高置信度的规则，称作强规则。
最简单的方法是通过暴力搜索，枚举所有可能项集。
Apriori.png
但是其计算量过大，并不现实，为了降低产生频繁项集的计算复杂度，利用支持度对候选项集剪枝。
Apriori定律1：如果一个集合是频繁项集，则它的所有子集都是频繁项集。
Apriori定律2：如果一个集合不是频繁项集，则它的所有超集都不是频繁项集。
当{A, B}是非频繁集时，所有包含它的超集也是非频繁的。
Apriori2.png
Apriori算法
- Let
- Generate frequent itemsets of length
- Repeat until no new frequent itemsets are identified
- Generate length
candidate itemsets from length
frequent itemsets 排好序
- Prune candidate itemsets containing subsets of length
that are infrequent 删除掉包含非
子集的候选集
- Count the support of each candidate by scanning the database
- Eliminate candidates that are infrequent, leaving only those that are frequent
- Generate length
Apriori3.png
举个例子
Apriori4.png
电信套餐预测中TOP1的方案，其中有一个特征使用关联规则的方法。
TOP1的github
