关联规则发现support大于最小support项目集(itemset)，然后使用大型项目集生成所需的规则，这些规则的confidence大于最小的confidence。如果X和Y是独立的，那么规则的升力就是所观察到的支持与期望的比率。一个典型的和广泛使用的关联规则应用实例是市场购物篮分析。
AIS Algorithm
- 首先，候选项集是通过扫描数据库获得。
- 对于每个事务, 确定此事务中包含上一步的大项集是哪一项。
- 通过将这些大型项集与此事务中的其他项一起扩展, 生成新的候选项集。
AIS算法案例如下：
首先生成候选集{1}{2}{3}{5},支持度为2，3，3，3。下一步生产两个候选项集{1,3}{1,4}....{1,5},对应的支持度为2，1，...,1.这里当支持度大于等于2时记录为大项集{1,3}{2,3}{2,5}{3,5},下一步生产三个组合的项集，{1,3,4}{2,3,5}{1,3,5},此时发现{2,3,5}是最终的最大项集。
AIS 算法的缺点是它导致生成和不必要地候选项集, 也会有相应的过多的计算。
SETM算法
SETM算法的目的是希望使用SQL来计算大型项目集。与AIS相似，SETM算法也基于从数据库读取的事务生成候选。因此，它生成并计算AIS算法生成的每个候选项集。但是，为了使用标准的SQL join生成候选操作，SETM将候选生成与计数相分离。它将候选项集与生成事务的TID(transaction id)保存在一个顺序结构中。在传递结束时，通过排序和聚合（sorting and aggregating ）这个顺序结构来确定候选项集的支持数。SETM并记录了使用候选项集生成事务的TIDs。为了避免需要子集操作，通过删除那些没有大于最小支持的候选项，来确定事务读取中包含的大型项目集。假设数据库是按TID顺序排序的，那么SETM可以通过Lk（set of large k-itemsets）对TID进行排序，轻松地在下一个过程中查找事务中包含的大型项目集。实际上，它只需要访问Lk的每个成员一次，并且可以使用关系合并操作进行候选生成。这种方法的缺点主要是由于候选集Ck(set of candidate k-itemsets)的大小；对于每个候选项集，候选项集现在有与候选项集所在的事务数相同的条目。此外，当我们准备在结束时传递对候选项集的支持时，Ck处于错误的顺序，需要对项集进行排序。在对没有最小支持的候选项集进行计数和裁剪之后，生成的Lk需要在TID上进行另一种排序，然后才能在下一次遍历中用于生成候选项。
算法流程：
- 候选项集将在数据库被扫描时动态生成，但在传递结束时进行计数。
- 新的候选项集的生成方式与AIS算法相同，但是生成事务的TID与候选项集保存在顺序结构中。如下图所示。
- 在传递结束时，通过排序和聚合（sorting and aggregating ）这个顺序结构来确定候选项集的支持数。
首先生成候选集{1}{2}{3}{5},支持度分别为2，3，3，3。下一步生产两个候选项集{1,3}{1,4}....{2,5},对应的TID2进行排序获得c2.进行聚合操作获得c3，发现有{1,3,4}{2,3,5}{1,3,5},{2,3,5}为最大项集。
【出处：Blog，URL：http://www.saedsayad.com/association_rules.htm 】
发展历史
关联规则的概念被广泛推广，特别是由于1993年Agrawal等人的文章，截止到2015年8月，它已经根据谷歌学者获得了18000多个引用，因此是数据挖掘领域中引用最多的论文之一。然而，现在被称为“关联规则”的是在1966年的论文中引入的，是由Petr Hajek等人开发的通用数据挖掘方法。
AIS算法是由Agrawal, Imielinski, and Swami提出的第一个关联规则挖掘算法。它着重于提高数据库的质量，以及处理决策支持查询的必要功能。该算法只生成一个项目关联规则。这些规则只包含一个项目。这个算法的缺点是太多的候选项集。最终被证明是小的项目集生成，它会需要更多的空间，这浪费了很多精力。以及这个算法需要对数据库太多的遍历。
SETM 算法中，候选项集在扫描数据库的时候生成，但是最后来计数。transaction identifier TID以顺序结构中的候选项集保存。它在候选生成过程中与计数分离。
1994,Agrawal, Rakesh和 Srikant, Ramakrishnan提出Apriori。它使用一种宽度优先的搜索策略来计算项目集的支持，并使用一个候选生成函数来利用支持的向下关闭属性。
Han, 2000年提出FP（ frequent pattern）growth algorithm算法，FP-Growth（Frequent Pattern Growth，频繁模式增长），它比Apriori算法效率更高，在整个算法执行过程中，只需要遍历数据集2次，就可完成频繁模式的发现。
【出处：新浪新闻， URL：http://www.sohu.com/a/127972540_447946 】
主要事件
| 年份 | 事件 | 相关论文/Reference |
| 1966 | Hájek, P., Havel, I., & Chytil, M.首次引入关联规则 | Hájek, P., Havel, I., & Chytil, M. (1966). The GUHA method of automatic hypotheses determination. Computing, 1(4), 293-308. |
| 1993 | Agrawal, R., Imieliński, T., & Swami, A.将关联规则的概念被广泛推广 | Agrawal, R., Imieliński, T., & Swami, A. (1993, June). Mining association rules between sets of items in large databases. In Acm sigmod record (Vol. 22, No. 2, pp. 207-216). ACM. |
| 1994 | Agrawal, R., & Srikant, R.对关联规则进行评价 | Agrawal, R., & Srikant, R. (1994, September). Fast algorithms for mining association rules. In Proc. 20th int. conf. very large data bases, VLDB (Vol. 1215, pp. 487-499). |
| 1995 | Houtsma, M., & Swami, A.提出setm 算法 | Houtsma, M., & Swami, A. (1995, March). Set-oriented mining for association rules in relational databases. In Data Engineering, 1995. Proceedings of the Eleventh International Conference on (pp. 25-33). IEEE. |
| 2000 | Han,2000年提出*FP（ frequent pattern）-growth algorithm算法* | Han, J., Pei, J., & Yin, Y. (2000, May). Mining frequent patterns without candidate generation. In ACM sigmod record (Vol. 29, No. 2, pp. 1-12). ACM. |
发展分析
瓶颈
SETM算法的缺点主要发生在候选集的大小上；对于每个候选项集，候选项集现在有与候选项集所在的事务数相同的条目。此外，当我们准备在结束时传递对候选项集的支持时，候选集的大小处于错误的顺序，此时，需要对项集进行排序。在对没有最小支持的候选项集进行计数和裁剪之后，生成的Lk（项集）需要在TID上进行另一种排序，然后才能在下一次遍历中用于生成候选项。
未来发展方向
与其他算法相比之下,SETM算法的计算时间似乎太长了。但SETM算法只使用简单的数据库就可以表示为SQL查询。如何减小计算量，提高运行速度值得研究者的思考。
Contributor: Ruiying Cai