Apriori算法介绍
Apriori，中文是先验，开始的意思。这个算法为了规避前面说到的指数爆炸的问题，采取了提前剪枝的办法。核心是两条定律：
定律一：如果一个集合是频繁项集，则它的所有子集都是频繁项集。
定律二：如果一个集合不是频繁项集，则它的所有超集都不是频繁项集。
Apriori定律举例
举例1：假设一个集合{A,B}是频繁项集，即A、B同时出现在一条记录的次数大于等于最小支持度min_support，则它的子集{A},{B}出现次数必定大于等于min_support，即它的子集都是频繁项集。
Apriori定律举例
举例2：假设集合{A}不是频繁项集，即A出现的次数小于min_support，则它的任何超集如{A,B}出现的次数必定小于min_support，因此其超集必定也不是频繁项集。
利用这两条定律，可以过滤掉很多的候选项集
利用性质1通过已知的频繁项集构成长度更大的项集，并将其称为候选频繁项集。
利用性质2过滤候选频繁项集中的非频繁项集
二项频繁集由在一项频繁集的基础上产生的，三项频繁项集由二项频繁项集的基础上产生的，以
此类推。
上面的图演示了Apriori算法的过程，注意看由二级频繁项集生成三级候选项集时，没有{牛奶,面包,啤酒}，那是因为{面包,啤酒}不是二级频繁项集，这里利用了Apriori定理。
最后生成三级频繁项集后，没有更高一级的候选项集，因此整个算法结束，{牛奶,面包,尿布}是最大频繁子集。
计算菜品间的关联度
首先计算出所有的频繁项集，这里最小支持度为0.2
得出L1、L2、L3的各个项集均为频繁项集，再进行计算每个频繁项集的置信度，其中L1不必计算。计算结果如下
Apriori算法不足
可能产生大量的候选集,以及可能需要重复扫描数据库，是Apriori算法的两大缺点。
主要改进方向：
减少候选集产生
降低无效的扫描库次数
提高候选集与原数据的比较效率
Ck中的每个元素需在交易数据库中进行验证来决定其是否加入Lk，这里的验证过程是算法性能的一个瓶颈。这个方法要求多次扫描可能很大的交易数据库，即如果频集最多包含10个项，那么就需要扫描交易数据库10遍，这需要很大的I/O负载。
1.一个项集是频集当且仅当它的所有子集都是频集。那么，如果Ck中某个候选项集有一个(k-1)-子集不属于Lk-1，则这个项集可以被修剪掉不再被考虑，这个修剪过程可以降低计算所有的候选集的支持度的代价。
2.扫描数据库只为了为候选集计数，但一些行比候选集长度还短，再比较就没必要。
3.利用一些hash位图等技术加速原始数据行与候选集的比较功能
FP-Growth算法
相对Apriori算法的改进
Han等人提出FP-Growth（频繁模式增长）算法，通过把交易集D中的信息压缩到一个树结构中，可以在寻找频繁集的过程中不需要产生候选集，大大减少了扫描全库的次数，从而大大提高了运算效率。
FP-TRee
FP-Tree（频繁模式树）是一个树形结构，包括一个频繁项组成的头表，一个标记为null的根结点，它的子结点为一个项前缀子树的集合。
频繁项
单个项目的支持度超过最小支持度则称其为频繁项（frequentitem）
频繁头表
频繁项头表的每个表项由两个域组成，一个是项目名称，一个是链表指针，指向下一个相同项目名称的结点。
生成FP-Growth树
1、遍历数据集，统计各元素项出现次数，创建头指针表
2、移除头指针表中不满足最小值尺度的元素项
3、第二次遍历数据集，创建FP树。对每个数据集中的项集：
3.1初始化空FP树
3.2对每个项集进行过滤和重排序
3.3使用这个项集更新FP树，从FP树的根节点开始：
3.3.1如果当前项集的第一个元素项存在于FP树当前节点的子节点中，则更新这个子节点的计数值
3.3.2否则，创建新的子节点，更新头指针表
3.3.3对当前项集的其余元素项和当前元素项的对应子节点递归3.3的过程
FP-Growth算法更进一步，通过将交易数据巧妙的构建出一颗FP树，然后在FP树中递归的对频繁项进行挖掘。
FP-Growth算法仅仅需要两次扫描数据库，第一次是统计每个商品的频次，用于剔除不满足最低支持度的商品，然后排序得到FreqItems。第二次，扫描数据库构建FP树。
构建频繁项集
第一步，扫描数据库，统计每个商品的频次，并进行排序，显然商品e仅仅出现了一次，不符合minSupport,剔除。最终得到的结果如下表：
