Apriori算法
•Apriori算法将发现关联规则的过程分为两个步骤：
1、通过迭代，检索出事务数据库中的所有频繁项集，即支持度不低于用户设定的阈值的项集
2、利用频繁项集构造出满足用户最小置信度的规则。
其中，检索所有频繁项集是该算法的核心，占整个计算量的大部分
•Apriori算法的重要性质
性质1：频繁项集的子集必为频繁项集。如果{B，C}是频繁的，那么{B}，{C}也一定是频繁的
性质2：非频繁项集的超集一定是非频繁的。例如{A,B}是非频繁的，那么{A,B, C}，{A,B, C, D}也一定是频繁的
运用Apriori算法的性质，我们就能去掉很多非频繁的项集，大大简化计算量：
我们发现{A,B}这个项集是非频繁的，那么{A,B}这个项集的超集{A,B,C},{A,B,D}等也都是非频繁的，这些就都可以忽略不去计算。
•使用Apriori算法构造出满足用户最小置信度的规则：
现有频繁项集l，生成每个非空子集S，若S满足最小置信度:
则输出关联规则(l-s)->s
Example:
最小支持度计数为2，minconf=80%
Step1:生成频繁项集：
Step2:生成关联规则：
•对于step1得到的频繁集{B,C,E},有子集{B},{C},{E},{B,E},{B,C},{C,E}，分别计算置信度：
confidence(BE->C)=2/3<80%
confidence(BC->E)=2/2>80%
confidence(CE->B)=2/2>80%
confidence(B->CE)=2/3<80%
confidence(C->BE)=2/3<80%
confidence(E->BC)=2/3<80%
则满足条件的为BC->E和CE->B两条规则
Apriori的优点：
•适合稀疏数据集。
•算法原理简单，易实现。
•适合事务数据库的关联规则挖掘。
•易编码实现
Apriori的缺点：
•可能产生庞大的候选集。
•算法需多次遍历数据集，算法效率低，耗时。
•在大数据集上可能较慢
FP-Growth算法
•FpGrowth算法通过构造一个树结构来压缩数据记录，使得挖掘频繁项集只需要扫描两次数据记录，而且该算法不需要生成候选集合，效率高。 而Apriori算法对于每个潜在的频繁项集都会扫描数据集判定给定模式是否频繁。
•FpTree的数据结构：
FpTree是一种树结构，树结构定义如下：
Example:
假设最小支持度为3
Step 1：扫描数据记录，生成一级频繁项集，并按出现次数由多到少排序：
Step 2：再次扫描数据记录，对每条记录中出现在Step1产生的表中的项，按表中的顺序排序。
Step 3：遍历每一条记录，生成fpTree。初始时，新建一个根结点，标记为null:
Step 4：根据step1得到的一级频繁项集建立项头表：
Step5:利用FpTree挖掘频繁项集。从表头header的最后一个项开始挖掘,得到每一项的条件模式基。
此处即从{啤酒}开始，根据{啤酒}的线索链找到所有{啤酒}结点，然后找出每个{啤酒}结点的前缀路径{牛奶，面包，尿布：1}，{牛奶，尿布:1}，{面包，尿布:1}。其中的“1”表示出现频次，由后缀结点{啤酒}的次数决定。
根据前缀路径我们可以生成条件FpTree，构造方式跟之前一样，此处的数据记录变为：
Step6：使用条件模式基构造条件fpTree:
构造好条件树后，对条件树进行递归挖掘，当条件树只有一条路径时，路径的所有组合即为条件频繁集。此处的条件频繁集为：{{}，{尿布}}，于是得到以{啤酒}为后缀的频繁集为{啤酒}、{尿布，啤酒}。
接下来重复step5,step6找header表头的倒数第二个项{尿布}的频繁集,直到header表头每个项挖掘完成。
{尿布}的前缀路径为：{面包：1}，{牛奶：1}，{牛奶，面包：2}
得到一组频繁项集{尿布}，{牛奶，尿布}，{面包，尿布}，{牛奶，面包，尿布}
重复以上步骤，对header表头的每个项进行挖掘，即可得到整个频繁项集
FP-Growth算法总结：
•两次扫描数据库：
第一次扫描得出单个频率
第二次扫描构建FP-Tree树
•步骤：
扫描(计数、去除不满足最小支持度的项集）
重排
构建FPTree
从下往上扫描项头表，构建每一项的条件模式基并构造条件FPTree
递归条件FPTree得到频繁项
•优点：
只需两次扫描数据库
•缺点：
内存开销大
单维布尔关联规则
