关联规则学习

1、什么是关联规则学习

关联规则学习(association rule learning)又叫关联分析(association analysis)，即从大规模数据集中寻找物品间隐含的关系。
如尿布与啤酒的例子，据报道，一家超市发现男人们会在周四买尿布和啤酒。
关联分析的最终目标就是要找出关联规则。

2、与关联规则学习相关的几个名词

事务：每一条交易称为一个事务。
项：交易中的每项物品，如酸奶，啤酒，尿布。
项集：包含多个项的集合，如{酸奶，啤酒，尿布}，一个事务中包含一个项集。
频繁项集：经常出现在一块的物品的集合。
支持度：如超市里买了啤酒和尿布的人数/有购买东西的总人数

置信度：计算在购买了x东西的人中，同时购买y东西的概率

3、关联规则的目标
（1）、发现频繁项集（通过计算支持度）
（2）、发现关联规则（通过计算可信度）

4、Apriori算法

原理：如果一个项集是频繁的，那么它的所有子集都是频繁的，反之，一个项集不是频繁的，则所有子集也不频繁。

有个一看就明白的计算例子见：
https://www.jianshu.com/p/469dff109fae

5、FP-growth算法：
由于Apriori算法每次迭代会频繁扫描整个数据集，导致计算量大，效率偏低，故提出了高效发现频繁项集的方法：FP-growth算法。
在FP-growth算法中，通过两次扫描事务数据库，把每个事务所包含的频繁项目按其支持度降序压缩存储到FP树中。在以后发现频繁模式的过程中，不需要再扫描事务数据库，而仅在FP-Tree中进行查找即可，并通过递归调用FP-growth的方法来直接产生频繁模式，因此在整个发现过程中也不需产生候选模式。该算法克服了Apriori算法中存在的问颢．在执行效率上也明显好于Apriori算法。
例子同样见：
https://www.jianshu.com/p/469dff109fae

Reference：
https://blog.csdn.net/DD18203614685/article/details/98057386