概念
关联规则挖掘可以让我们从数据集中发现项与项（item 与 item）之间的关系。
支持度是个百分比，它指的是某个商品组合出现的次数与总次数之间的比例。支持度越高，代表这个组合出现的频率越大。
置信度是个条件概念，就是说在 A 发生的情况下，B 发生的概率是多少。
提升度用来衡量 A 出现的情况下，是否会对 B 出现的概率有所提升。提升度 (A→B)= 置信度 (A→B)/ 支持度 (B)
提升度有三种可能：
1. 提升度 (A→B)>1：代表有提升；
2. 提升度 (A→B)=1：代表有没有提升，也没有下降；
3. 提升度 (A→B)<1：代表有下降。
Apriori 的工作原理
Apriori 算法是查找频繁项集 (frequent itemset) 的过程，频繁项集就是支持度大于等于最小支持度 (Min Support) 阈值的项集，所以小于最小值支持度的项目就是非频繁项集，而大于等于最小支持度的项集就是频繁项集。
Apriori算法的递归流程：
1. K=1，计算 K 项集的支持度；
2. 筛选掉小于最小支持度的项集；
3. 如果项集为空，则对应 K-1 项集的结果为最终结果。
否则 K=K+1，重复 1-3 步。
Apriori 的改进算法：FP-Growth 算法
Apriori 算法会浪费很多计算空间和计算时间，为此人们提出了 FP-Growth 算法，它的特点是：
1. 创建了一棵 FP 树来存储频繁项集。在创建前对不满足最小支持度的项进行删除，减少了存储空间。
2. 整个生成过程只遍历数据集 2 次，大大减少了计算量。
工作原理：
1. 创建项头表（item header table）
创建项头表的作用是为 FP 构建及频繁项集挖掘提供索引。这一步的流程是先扫描一遍数据集，对于满足最小支持度的单个项（K=1 项集）按照支持度从高到低进行排序，这个过程中删除了不满足最小支持度的项。项头表包括了项目、支持度，以及该项在 FP 树中的链表。初始的时候链表为空。
2. 构造 FP 树
FP 树的根节点记为 NULL 节点。整个流程是需要再次扫描数据集，对于每一条数据，按照支持度从高到低的顺序进行创建节点（也就是第一步中项头表中的排序结果），节点如果存在就将计数 count+1，如果不存在就进行创建。同时在创建的过程中，需要更新项头表的链表。
3. 通过 FP 树挖掘频繁项集
到这里，我们就得到了一个存储频繁项集的 FP 树，以及一个项头表。我们可以通过项头表来挖掘出每个频繁项集。具体的操作会用到一个概念，叫“条件模式基”，它指的是以要挖掘的节点为叶子节点，自底向上求出 FP 子树，然后将 FP 子树的祖先节点设置为叶子节点之和。
