language: en

Theoretical Foundations of Association Rules

Mohammed J. Zaki and Mitsunori Ogihara
Computer Science Department, University of Rochester,
Rochester NY 14627
{zaki,ogihara}@cs.rochester.edu

Abstract 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