一、关联规则的背景
在一组数据中找到某种内在联系，举个例子：在国外的某家超市，工作人员发现牛奶、啤酒、尿布经常在男性的账单中出现，看似风马牛不相及的事情，但确实就发生了，后来超市采取三者放在比较近的地方以提高销售量，事实证明他们真的成功了，其实是劳累了一天的爸爸在买孩子尿布的时候顺便买了啤酒，本质上是有因果关系的。所以关联分析就是通过数据分析出隐藏的关系的一种机器学习方法。
二、基本概念
- 项集
由一个或者多个项组成的集合，例如： {牛奶, 面包, 尿布}
- 支持数($\sigma$)
一个项集出现的次数，例如：$\sigma$({牛奶, 面包, 尿布}) = 2
- 支持度
包含项集的记录占总记录的比例
$S(x) = \sigma(x)/N$
- 频繁项集
支持度大于最小支持度阈值的项集
三、关联规则的产生
1.定义
$X->Y$
X到Y是不相交的项集
例子: {牛奶, 尿布}-> {啤酒}
2.满足的条件
- 支持度
包含项集X和Y的记录数占总记录数的比例
S(X->Y) = $\sigma{(X\cup Y)}/N$
- 置信度
包含项集X和Y的记录数占项集X的支持数
需要满足支持度和置信度都大于给定的最小阈值
3.寻找关联规则的策略
关联规则的寻找也可以采用枚举的办法找到
- 寻找频繁项集
支持度大等于最小支持度阀值的项集
- 寻找支持度和置信度满足条件的规则
在满足频繁项集的基础上满足置信度也大于等于最小置信度的规则
4.频繁项集的产生
减少候选项集的数目
- 先验原理
项集是频繁的，则它的子集也是频繁的
反之，如果项集是非频繁的，则超集(父集)也是非频繁的
支持度的反单调性：项集的支持度不大于子集的支持度
- Apriori算法
利用剪枝技术进行实现，开始假设每个项都是一个关联规则，然后计算支持度，不满足要求的这个项直接去掉，实现剪枝的目的
然后再增加一个项，将剩余的满足条件的项进行组合，得到一个所有可能的组合表，可能产生的候选集比较多，可以采用特殊的数据结构进行处理，然后对两个项的规则再次计算支持度，最后也利用最小支持度进行剪枝，反复进行，直至达到预期的规则，此时就产生了一个频繁项集
减少比较次数
可将候选集合存储再一个hash表中以减少比较次数
5.产生规则
由同一个频繁项集可以产生多种不同的规则，对这些产生的规则进行置信度的计算，选择一个比较高的作为关联规则学习的结果，例如
{牛奶, 尿布}-> {啤酒} c~1~ = 66.7%
{牛奶, 啤酒}-> {尿布} c~2~ = 50%
{啤酒, 尿布}-> {牛奶} c~3~ = 100%
选择c~3~更加合适
