Theoretical Foundations of Association Rules
Mohammed Javeed Zaki, Mitsunori Ogihara · 2007
In this paper we describe a formal framework for the problem of mining association rules. The theoretical foundation is based on the field of formal concept analysis. A concept is composed of closed subsets of attributes (itemsets) and objects (transactions). We show that all frequent itemsets are uniquely determined by the frequent concepts. We further show how this lattice-theoretic framework can be used to find a small rule generating set, from which one can infer all other association rules. 1 Introduction Association rule discovery, a successful and important mining task, aims at uncovering all frequent patterns among sets (or transactions) composed of data attributes. Most of the current work has focused on developing efficient algorithms [2, 3, 4, 15, 19, 20, 23, 24, 25, 29]. On the other hand, there has been little work in formulating a theory of associations. Such a theory can help in estimating the complexity of the mining task, and also in developing a unified framework for...