模式（pattern）是数据集中频繁出现或强相关的条目、子序列或子结构组成的集合，它代表了数据集的本质特征和重要属性。模式发掘（pattern discovery）就是从大规模数据集中发现模式。
模式发掘的重要性
模式发掘的典型应用场景包括：
- 哪些商品常被一起购买？
- 买了iPad之后还会买哪些商品？
- 哪些代码片段可能包括复制粘贴错误（copy-and-paste bug）？
- 语料库中哪些词串可能构成短语？
模式发掘是从数据集中发现内在规则，在数据挖掘中有广泛应用：
- 关联分析、相关分析以及因果分析；
- 挖掘序列模式、结构（例如：子图）模式；
- 分析时空数据、多媒体、时间序列和留数据中的模式；
- 基于判别模式分析的分类；
- 基于模式子空间的聚类。
模式发现广泛应用于购物篮分析（market basket analysis）、交叉营销（cross-marketing）、目录设计（catalog design）、销售活动分析（sale campaign analysis）、Web日志分析（Web log analysis）和生物序列分析（biological sequence analysis）。
频繁模式与关联规则[1][2]
一个或多个项组成的集合称为项集（itemset），$k$-项集记为$ X=\{ x_1,\ldots,x_k\}$。绝对支持度（absolute support）是指项集$ X$在事务中出现的次数，相对支持度（relative support）是指包含项集$ X$的事务所占比率。如果项集$X$的支持度大于某个$minsup$阈值$\sigma$，则称$X$是频繁模式。
令$minsup=50\%$，那么：
- 频繁的$1$-项集包括：$Beer: 3(60\%), Nuts: 3(60\%), Diaper: 4(80\%), Eggs:3(60\%)$；
- 频繁的$2$-项集包括：$\{Beer, Diaper\}:3(60\%)$。
关联规则（association rule）记为$ X\rightarrow Y(s,c)$，支持度$s$为包含项集$ X\cup Y$事务出现的概率，置信度（confidence）$c$为包含项集$ X$的事务中包含项集$ X\cup Y$的事务出现的概率，$c={\sup( X\cup Y)\over\sup( X)}$，置信度可以视为条件概率$P(Y\vert X)$的估计[3][4]。
关联规则挖掘是找出大于最小支持度和置信度的所有关联规则$ X\rightarrow Y$。令$minconf=50\%$，关联规则为 \[ Beer\rightarrow Diapper(60\%, 100\%),~Diaper\rightarrow Beer(60\%,75\%)。 \]
闭模式与最大模式
在频繁模式和关联规则挖掘时，一个长的模式包含很多子模式。
若模式（项集）$ X$是频繁的，并且不存在与$X$有相同支持度的超模式（super-pattern）$ Y\supset X$，则称$ X$为闭模式（closed pattern）[5]。闭模式是频繁模式的无损压缩，虽降低了模式数量，但没有损失支持度信息。因此，每个支持度只对应唯一的闭模式。
若模式$X$是频繁的，并且不存在频繁的超模式$Y\supset X$，则称$X$为最大模式（max-pattern）[6]。最大模式不关注子模式的真实支持度，它是频繁模式的有损压缩，只知道子模式是频繁的，但不知道子模式的真实支持度（知道子模式的支持度最少为多少）。
令事务集$TDB_1$的事务为$T_1:\{a_1,\ldots,a_{50}\},T_2:\{a_1,\ldots,a_{100}\}$并且$minsup=1$，那么$TDB_1$只有两个闭模式$\{a_1,\ldots,a_{50}\}:2,\;\{a_1,\ldots,a_{100}\}:1$（支持度分别为2和1）和唯一的最大模式$\{a_1,\ldots,a_{100}\}:1$。由此可见，最大模式是闭模式的一个子集。
参考资料
- [1]R. Agrawal, T. Imieliński, and A. Swami, “Mining Association Rules Between Sets of Items in Large Databases,” Sigmod Record, vol. 22, no. 2, pp. 207–216, Jun. 1993. [Online]
- [2]J. Han, H. Cheng, D. Xin, and X. Yan, “Frequent pattern mining: current status and future directions,” Data Mining and Knowledge Discovery, vol. 15, no. 1, pp. 55–86, 2007.
- [3]M. Hahsler, B. Gruen, and K. Hornik, “arules – A Computational Environment for Mining Association Rules and Frequent Item Sets,” Journal of Statistical Software, vol. 14, no. 15, pp. 1–25, Oct. 2005. [Online]
- [4]J. Hipp, U. Güntzer, and G. Nakhaeizadeh, “Algorithms for association rule mining—a general survey and comparison,” ACM sigkdd explorations newsletter, vol. 2, no. 1, pp. 58–64, 2000.
- [5]N. Pasquier, Y. Bastide, R. Taouil, and L. Lakhal, “Discovering Frequent Closed Itemsets for Association Rules,” in International Conference on Database Theory, 1999, pp. 398–416.
- [6]R. J. Bayardo, “Efficiently Mining Long Patterns from Databases,” Sigmod Record, vol. 27, no. 2, pp. 85–93, 1998.
