模式发掘（2）：高效的模式挖掘方法

基本原理

向下闭包（downward closure）特性是指频繁项集的所有非空子集也必须是频繁的，这也称为Apriori性质。若$\{beer, diaper, nuts\}$是频繁的，那么$\{beer, diaper\}$也是，每个包含$\{beer, diaper, nuts\}$的事务必包含$\{beer, diaper\}$。

如果项集$S$的存在非频繁的子集，那么$S$必不是频繁的。如果项集是非频繁的，它的超集（superset）必是非频繁的，这称为Apriori剪枝原理（Apriori pruning principle）。基于这个原理，主要有三种可扩展的（scalable）频繁模式挖掘方法：Apriori[1]、Eclat[2]和FPgrowth。

Apriori算法

Apriori算法是第一个基于候选集生成与测试的频繁集挖掘方法：

Apriori算法生成候选项集的集合分两步：

1. 自连接（self-join）$F_k$生成候选项集的集合；
2. 剪枝，删除候选项集的集合中的非频繁模式。

图 1: Apriori算法示例 [PNG]

若频繁模式的集合$F_3=\{abc,abd,acd,ace,bcd\}$，自连接可得候选模式的集合$C’_4=\{abcd, acde\}$，但是$ade\notin F_3$，因此剪枝后可得$C_4=\{abcd\}$。

利用SQL语句的候选项集生成方法：

Eclat算法

参考资料

1. [1]R. Agrawal, R. Srikant, and others, “Fast algorithms for mining association rules,” in Proc. 20th int. conf. very large data bases, VLDB, 1994, vol. 1215, pp. 487–499.
2. [2]M. J. Zaki, “Scalable algorithms for association mining,” IEEE Transactions on Knowledge and Data Engineering, vol. 12, no. 3, pp. 372–390, 2000.

脚注