基于高频模式树的项约束关联规则发现方法

Mining constrained association rules based on frequent pattern tree

项约束关联规则发现是在关联规则发现中加入先验知识、提高算法执行效率、精简所发现的规则数量的重要方法 .现有的项约束关联规则发现算法都基于 Apriori算法框架 ,在高密度数据库上的执行性能不佳 ,而且没有提出高效的约束条件检验方法 .在一种新型高效关联规则发现算法 FP- Growth的基础上 ,提出了一种全新的项约束关联规则发现算法 FPC.FPC算法利用 FP- Growth算法逐步生成高频项集的方式 ,构造了一种约束树数据结构 ,及时检查高频项集满足约束条件的情况 ,尽早删去不满足约束的条件 .实验证明 ,此算法执行效率比 Reorder等基于 Apriori的算法高一个数量级 .

Constrained association rule mining is an important method for integrating Apriori knowledge, improving efficiency of algorithms, and reducing size of discovered rules in the association rule mining. The existing algorithms for mining constrained association rules are all based on the Apriori algorithm, whose performance will decline on dense databases. In this paper a novel algorithm for mining constrained association rules, FPC, which is based on a new type algorithm for association rule mining, FP Growth, was proposed. The FPC algorithm takes advantage of the stepwise method of the FP Growth algorithm for generating frequent patterns to construct a constraint tree to check whether the generated frequent patterns satisfy the constraints, and then prune those that do not satisfy the constraints. Experiments comparing the FPC with the existing algorithm, Reorder, showed that the former runs an order faster than the latter.