Ordering Policy Using Multi-Level Association Rule Mining

1. Introduction

Association rule mining is a data mining technique introduced by Agrawal et al. (1993) in which many rules are generated and tested on a dataset. It finds rules that satisfy user-specified constraints. Typical applications include retail market basket analysis, item recommendation systems, cross-selling, loss-leader analysis, etc. (Brijs et al. (1999)). Association rule mining aims to find rules of the form: X →Y, where X and Y are two sets of items. The meaning of the rule is that if the left-hand side X occurs, then the right-hand side Y is also very likely to occur. The utility of rules is often measured using support and confidence. Support is defined as the percentage of transactions in the data that contain all items in both the antecedent and the consequent of the rule. Confidence on the other hand is an estimate of the conditional probability of Y given X. Association rule mining output rules with support no less than minimum support and confidence no less than minimum confidence. The two thresholds are specified by users. Several approaches discover association rules at the terminal level of abstraction, i.e. the association rules containing only the items belonging to the transactions of database. Agrawal and Srikant (1994) developed algorithms for discovering all significant association rules between items in a large database of transactions. Zaki et al. (1997) developed a fast association rule mining algorithm which scans the database only once.

However, there is a need in many applications to discover association rules at higher levels of abstraction, these are multi-level association rules (Han and Fu, 1995) or generalized association rules (Srikant and Agrawal, 1995). In multi-level datasets, the data is available in different stages of abstraction or levels. Such levels are represented with concept hierarchies. For example, a user may not only be concerned with the associations between “milk” and “bread”, but also wants to know the association between Amul toned milk and Harvest white bread. Multi-level association rules may lead to the discovery of more specific and concrete knowledge from data as compared to single- level association rules. Instead of considering single attribute for the rules multiple attributes are considered to obtain more specific rules.