基于Galois联络的最小非冗余关联规则挖掘

Mining Minimal Non-Redundant Association Rules Based on Galois Connection

关联规则挖掘是NP难题,关键是如何约简频繁项集。本文以Galois联络为理论基础,应用Galois联络的闭包运算及其性质定义数据库中的频繁项和封闭频繁项,提出了挖掘关联规则生成子、精确关联规则生成基和近似关联规则本征基的概念,并由此构造最小非冗余精确关联规则和近似关联规则挖掘的MNRM算法。该算法与Apriori算法相比较,挖掘的关联规则是最小非冗余的,降低了计算复杂度,而且规则具有不丢失任何信息、最小前件和最大后件以及对用户最实用和最相关等优点。

Since the association rule＇s mining is NP-hard,the key is how to reduce frequent itemsets.In the paper,the generating basis for exact association rules and the proper basis for approximate association rules are addressed based on the Galois connection,and the Galois closure properties.This paper presents a new algorithm called MNRM to discover minimal non-redundant exact and approximate rules.Compared with the Apriori algorithm,these rules are the most non-redundant,the computing complexity is reduced.And these rules have many strongpoints,such as minimal antecedents and maximal consequents,the most relevant association rules,limiting the number of rules produced without information loss,the most user-useful and user-relevant.