频繁项集和关联规则
2018-12-02 本文已影响63人
georgeguo
0 频繁项集与关联规则的关系
关联规则的发现的前提是先构建好关联规则。Apriori原理，如果某元素是不频繁的，那么包含该元素的超集也是不频繁的，所以就不需要考虑这些超集。
1 apriori算法
apriori算法一张图
apriori算法图解
apyori中apriori的参数总结
- records, 输入的数据
- min_support=0.0045, 最小支持度
- min_confidence=0.2, 最小置信度
- min_lift=3,
- min_length=2，最小长度
apriori算法的缺点
- 计算速度慢
2 FP-growth算法
FP-growth简介
FP-growth的来源《Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach, 2004》。FP-growth是基于Aprioir构建，只是在完成相同任务的时候，使用了不同的技术。通过将数据集存储在FP-Tree，然后在FP-Tree上发现频繁项集或频繁项对。
FP-growth发现频繁项集的过程
- 步骤1：构建FP-tree
- 第一遍扫描，对所有元素的出现次数进行计数；
- 第二遍扫描，只考虑哪些频繁元素，基于频繁的元素构建FP-Tree
- 步骤2：从FP-Tree中挖掘频繁项集
- 第一步：从FP-Tree中获得条件模式基；(conditional pattern tree)
- 第二步：利用条件模式基，构建一个条件FP-Tree；
- 第三步：重复第一步和第二步，直到树包含一个元素项为止；
如何获取条件模式基？
条件模式基(conditional pattern base)：以所查找元素项为结尾的路径集合。首先从获取的头指针表中的单个频繁元素项开始，对每个元素项获取其对应的条件模式基。每一条路径其实都是一条前缀路径，前缀路径就是介于所查找元素项与根节点之间的内容。每条前缀路径都与一个计数关联，该计数就起始元素的个数。前缀路径将被用于构建条件FP-Tree。
如何创建条件FP-Tree？
和创建FP-Tree的逻辑是一样的，只是输入不一样。
FP-Tree，用于编码数据集的有效方式
FP-growth算法的优缺点
优点
- 每次处理只遍历两次数据，处理速度快，速度明显优于apriori
缺点
- 该算法虽然能够高效的发现频繁项集，但是不能用于发现关联规则。
- 实现比较困难，在某些数据集上性能会下降。
- fp-growth每次创建的树，可能还不一样
