频繁模式是在数据集中出现的频率不小于用户指定的阈值的项目集、子序列或子结构（著名例子：尿布和啤酒）。例如，frequent itemset，如牛奶和面包，就是频繁项集。子序列，例如先购买PC，然后是数码相机，然后是存储卡，如果它经常出现在购物历史数据库中，是一种(频繁的)顺序模式。子结构，subsequence可以参考不同的结构形式，例如子图、子树或子格，这些结构形式可能与项目集或子序列相结合。如果一个子结构经常出现在一个图形数据库中，它被称为(频繁)结构模式a (frequent) structural pattern。发现频繁模式在挖掘关联、关联和数据之间的许多其他有趣关系中扮演着重要的角色。此外，它还有助于数据索引、分类、集群和其他数据挖掘任务。因此，频繁的模式挖掘已经成为数据挖掘研究中的一个重要的数据挖掘任务和一个聚焦的主题。
其比较典型的有Apriori, FP-growth and Eclat三个算法，下面就讲解以下Apriori算法的流程：
假设一家大型超市通过库存单位对每一项商品的销售数据进行跟踪:每一项，如“黄油”或“面包”，都是由最小库存管理单元（Stock Keeping Unit, SKU）识别出来的。超市有一个交易数据库，每笔交易都是一套在一起购买的。让交易数据库包括以下项目集:
A | |
1 | Itemsets |
2 | {1,2,3,4} |
3 | {1,2,4} |
4 | {1,2} |
5 | {2,3,4} |
6 | {2,3} |
7 | {3,4} |
8 | {2,4} |
举例将使用Apriori来确定该数据库的频繁项集。如果一个项目集出现在数据库的至少3个交易中时，那么就认为它是频繁的:3也就是支持阈值。
Apriori的第一步是分别计算每个成员项的出现次数，称为“支持”。通过对数据库进行第一次扫描，得到如下结果。可以发现，1，2，3，4单独出现的次数都大于3.那么它们当前被认为是频繁项。
Item | Support | |
1 | {1} | 3 |
2 | {2} | 6 |
3 | {3} | 4 |
4 | {4} | 5 |
所以，下一步是生成所有对频繁项的列表，通过上图的单个频繁项而来。例如，关于一对{1,2}。
Item | Support | |
1 | {1,2} | 3 |
2 | {1,3} | 1 |
3 | {1,4} | 2 |
4 | {2,3} | 3 |
5 | {2,4} | 4 |
6 | {3,4} | 3 |
这时我们发现，{1，3}，{1，4}，出现的次数都是小于阈值3的，所以目前的频繁项是{1，2}，{2，3}，{2，4}，{3，4}.之后再继续找三元频繁项，下图发现{2，3，4}只出现2次，说明该例子中没有三频繁项。这就是整个Apriori算法的整体流程。
Item | Support | |
1 | {2,3,4} | 2 |
整个Apriori算法的整体流程：
1.扫描数据库，生成候选1项集和频繁1项集。
2.从2项集开始循环，由频繁k-1项集生成频繁频繁k项集。
- 频繁k-1项集两两组合，判定是否可以连接，若能则连接生成k项集。
- 对k项集中的每个项集检测其子集是否频繁，舍弃掉子集不是频繁项集即不在频繁k-1项集中的项集。
- 扫描数据库，计算2.3步中过滤后的k项集的支持度，舍弃掉支持度小于阈值的项集，生成频繁k项集。
3.若当前k项集中只有一个项集时循环结束。
【描述来源：wiki，URL：https://en.wikipedia.org/wiki/Apriori_algorithm】
发展历史
描述
二十多年来，频繁模式挖掘一直是数据挖掘研究的重点。当然，这项研究已经取得了巨大进展,从效率和可伸缩的频繁项集挖掘算法在事务数据库中大量的研究前沿,如序列模式挖掘、结构化模式挖掘、关联挖掘,关联分类,和频繁的基于模式的聚类,以及他们的广泛应用。
频繁模式挖掘是Agrawal在1993年首次提出的，它用来研究超市里的商品之间贩卖的关联性。如，当一个客户买了牛奶了，那么这位顾客还有可能买些什么商品呢？
自从首次提出后，该类算法的应用也有很衍生，从可伸缩的数据挖掘方法，处理广泛的数据类型，各种扩展的挖掘任务，以及各种各样的新应用。称为了数据挖掘的基础实用的方法之一。
其比较典型的有Apriori, FP-growth and Eclat三个算法，Agrawal and Srikant在1994年发现了一个有意思的downward closure特性，也叫Apriori。他发现只有当所有子项目集都是频繁的时，k项集才会频繁发生。之后，对apriori算法的改进也都应运而生，如哈希技术(Park et al. 1995)，分区技术(Savasere et al. 1995)，抽样方法(Toivonen 1996)，动态项目集计数(Brin et al. 1997)，增量挖掘(张et al. 1996)，并行和分布式采矿(Park et al. 1995; Agrawal1996; zhanget al. 1996; Zaki et al. 1997)，并将挖掘与关系数据库系统集成(Sarawagi et al. 1998)。Geerts等人(2001)推导出了一种紧密的上界，即可以在水平挖掘方法中生成的候选模式的数量。
但是apriori有两个问题（1）生成大量候选集，(2)反复扫描数据库并检查模式匹配对候选对象。Han et al. (2000)提出了FP-growth算法在没有候选集合下，挖掘频繁项目集的完整集合。FP-growth是一种新的方法，它只需要扫描两次数据集。FP-growth包含两部分内容，首先需要构造FP-tree，它高度压缩了数据库中的信息。然后在FP-tree上挖掘出频繁模式。
Zaki在2000年提出Equivalence CLASS Transformation（Eclat）算法使用垂直格式挖掘频繁项集，与fp-growth和apriori算法不同，Eclat算法加入了倒排的思想，具体就是将事务数据中的项作为key，每个项对应的事务ID作为value。特点：仅需要一次扫描数据库，TID集合很长的话需要消耗大量的内存和计算时间
之后，对高维数据的频繁模式挖掘技术也研究很多，如Pan et al. (2003)提出的CARPENTER, Pan et al.(2004)提出的COBBLER,Liu et al.(2006)提出的TD-Close算法等都是对高维数据中频繁模式进行挖掘。从挖掘数据的结构讲，graphs, trees and lattices都进行了研究。2007年，作者Han, J.,对频繁模式挖掘技术进行了详细的回顾。
【描述来源：论文，URL：https://link.springer.com/content/pdf/10.1007%2Fs10618-006-0059-1.pdf】
主要事件
A | B | C | |
1 | 年份 | 事件 | 相关论文 |
2 | 1994 | Agarwal, R., & Srikant, R.首次提出apriori算法 | Agarwal, R., & Srikant, R. (1994, September). Fast algorithms for mining association rules. In Proc. of the 20th VLDB Conference (pp. 487-499). |
3 | 2000 | Zaki在2000年提出Equivalence CLASS Transformation（Eclat）算法 | Dür, W., Vidal, G., & Cirac, J. I. (2000). Three qubits can be entangled in two inequivalent ways. Physical Review A, 62(6), 062314. |
4 | 2007 | Han, J.,对频繁模式挖掘技术进行了详细的回顾 | Han, J., Cheng, H., Xin, D., & Yan, X. (2007). Frequent pattern mining: current status and future directions. Data mining and knowledge discovery, 15(1), 55-86. |
发展分析
瓶颈
- 感到频繁模式挖掘的瓶颈不是我们能否在一定的约束下获得完整的频繁模式集，而是取决于我们是否能够获得在应用程序中最有用的紧凑而高质量的模式集。
- 尽管我们有高效的方法来挖掘精确和完整的频繁模式，但在许多应用程序中，近似频繁的模式可能是最好的选择。例如，在对DNA或蛋白质序列的分析中，我们希望找到与生物实体相似的长序列模式，类似于BLAST（Basic Local Alignment Search Tool）。但我们能有效地挖掘这些模式吗？要使这种挖掘比目前生物信息学中现有的工具更加有效，仍然需要进行大量的研究。
未来发展方向
我们需要对模式深入理解并且解释机制，例如对频繁模式的语义注释，以及频繁模式的上下文分析。模式分析的主要研究工作集中在模式组合(例如，项目集模式中的项目集)和频率。频繁模式的语义包含了更深层次的信息:模式的含义是什么; 什么是同义词模式;这个模式的典型事务是什么？这些问题都值得我们去思考。
Contributor: Frequent Pattern Mining