关联规则
关联规则是形如$X \rightarrow Y$ 的蕴含表达式，其中$X$和$Y$是不相交的项集，即$X\bigcap Y=\varnothing$。
关联规则的强度可以用它的支持度(support)和置信度(confidence)度量。
支持度（联合概率）：确定规则可以用与给定的数据集的频繁程度。
置信度（条件概率）：确定$Y$在包含$X$的事物中出现的频繁程度。
$$support(X\rightarrow Y)=\frac{|X\cup Y|}{N}=P(X\cup Y)$$
$$confidence(X\rightarrow Y)=\frac{|X\cup Y|}{|X|}=P(Y|X)$$
项集：属性名称集合。比如，{a,b},{c},{a,d}
如果一个项集同时满足最小支持度阈值和最小置信度阈值，则认为这个项集的关联规则是有趣的。
频繁项集：满足最小支持度的项集。
如果一个项集{a,b}是频繁的，那么它的所有子集{a}也是频繁的。
如果一个项集{a,b}是不频繁的，那么它的所有超集{a,b,c}也是不频繁的。
Apriori是找频繁项集的算法
- 统计一个元素项集出现的频数，找出不小于最小支持度的项集，得到 频繁1-项集。令k=2
- 根据第k-1步生成的 频繁(k-1)-项集 生成 侯选k-项集，然后对数据库进行搜索，得到 侯选k-项集 的支持度，与最小支持度进行比较，从而找到 频繁k-项集，删除 侯选k-项集 中 不频繁k-项集。
- 如果没有 频繁k-项集 生成，则停止，返回 频繁(k-1)-项集 作为 最大频繁项集；
否则，k = k+1，返回步骤2
优点：
- 简单、易理解
缺点：
- 每一步产生侯选项集时循环产生的组合过多，没有排除不应该参与组合的元素
- 每次计算项集的支持度时，都会对数据库的全部记录进行扫描比较，I/O开销大
Reference
https://en.wikipedia.org/wiki/Association_rule_learning
