Mining generalised disjunctive association rules

Abstract

This paper introduces generalised disjunctive association rules such as "People who buy bread also buy butter or jam", and "People who buy either raincoats or umbrellas also buy flashlights". A generalised disjunctive association rule allows the disjunction of conjuncts, "People who buy jackets also buy bow ties or neckties and tiepins". Such rules capture contextual inter-relationships among items. Given a context (antecedent), there may be a large number of generalised disjunctive association rules that satisfy the minsupp and minconf constraints. It is computationally expensive to find all such rules. We present algorithm thrifty-traverse which borrows concepts such as subsumption from propositional logic to mine a subset of such rules in a computationally feasible way. We experimented with our algorithm on US census data as well as transaction data from a grocery superstore to demonstrate its computational feasibility, utility and scalability.