1.基本概念
1.1定义
关联分析用于发现隐藏在大型数据集中令人兴趣的联系， 所发现的模式通常用关联规则或频
繁项集的形式表示。
关联规则反映一个事物与其他事物之间的相互依存性和关联性。 如果两个或者多个事物之间存在一定的关联关系， 那么， 其中一个事物发生就能够预测与它相关联的其它事物的发生。
项集
支持度：确定项集的频繁程度
置信度：确认Y在包含X的事务中出现的频繁程度
将关联规则挖掘任务分解为如下两个主要的子任务：
- 频繁项集产生 （ Frequent Itemset Generation )
- 其目标是发现满足最小支持度阈值的所有项集， 这些项集称作频繁项集。
- 规则的产生（ RuleGeneration )
- 其目标是从上一步发现的频繁项集中提取所有高置信度的规则， 这些规则称作强规则（ strong rule) 。
2.频繁项挖掘算法
2.1降低产生频繁顷集计算复杂度的算法
- 减少候选项集的数量
先验原理：(Apriori) - 减少比较的次数
替代将每个候选项集与每个事务相匹配， 可以使用更高级的数据结构， 或存储候选项集或压缩数据集，来减少比较次数(FPGrowth)
2.2 Apriori
先验原理：
- 如果一个项集是频繁的， 则它的所有子集一定也是频繁的；
- 相反， 如果一个项集是非频繁的， 则它的所有超集也一定是非频繁的。
算法过程：最小支持度计数==2
注意事项：
①尽管集合具有无序性， 但为了方便比较计数， 通常对所有商品做一个默认的排序 （类似于建立一个字典索引）。
②项的连接：降低候选项的生成。对于任何2个需要连接的项集，去掉第1个项集的首项、第2个项集的尾项，若剩下的一样即可连接。
特点：
①多次扫描数据库
②候选项规模庞大
③计算支持度开销大
提升性能方法：
Hash-based itemset counting (散列项集计数)
Transaction reduction (事务压缩）
Partitioning (划分）
Sampling (釆样）
缺点：
①需要反复的生成候选项， 如果项的数目比较大， 候选项的数目将达到组合爆炸式的增长
2.3 FPGrowth
基本思想
• 只扫描数据库两遍， 构造频繁模式树 (FP-Tree)
• 自底向上递归产生频繁项集
• FP树是一种输入数据的压缩表示， 它通过逐个读入事务， 并把每个事努映射到FP树中的一条路径来构造
方法
- 对每个项， 生成它的条件模式基， 然后生成它的条件FP-tree
- 对每个新生成的条件 FP-tree，重复这个步骤
- 直到结果FP-tree为空， 或只含唯一的一个路径 (此路径的每个子路径对应的项集都是频繁集）
实例1
①构造FP树
- 扫描数据库一次， 得到频繁1-项集
- 把项按支持度递减排序
- 再一次扫描数据库， 建立FP-tree
②生成条件模式
- 从 FP-tree 的头表开始
- 按照每个频繁项的连接遍历 FP-tree
- 列出能够到达此项的所有前缀路径，得到条件模式基
步骤
实例2
优点
- 完 备：
- 不会打破交易中的任何模式
- 包含了频繁模式挖掘所需的全部信息
- 紧密
- 支持度降序排列： 支持度高的项在FP-tree中共享的机会也高
- 决不会比原数据库大
2.4 产生关联规则
针对同一个频繁项集的关联规则， 如果规则的后件满足子集关系， 那么这些规则的置信度间满足反单调性
支持度：确定项集的频繁程度
置信度：确认Y在包含X的事务中出现的频繁程度
3.关联分析的评估
lift计算提升度
