Dynamic itemset counting and implication rules for market basket data

TLDR

The paper addresses market‑basket data analysis, outlining key contributions. The study aims to introduce a more efficient algorithm for large itemset mining and a novel method for generating true implication rules. The authors develop a multi‑pass, low‑candidate algorithm enhanced by item reordering and a rule‑generation technique that normalizes antecedent and consequent. Experiments reveal that real data characteristics significantly influence system performance and result patterns compared to synthetic data.

Abstract

We consider the problem of analyzing market-basket data and present several important contributions. First, we present a new algorithm for finding large itemsets which uses fewer passes over the data than classic algorithms, and yet uses fewer candidate itemsets than methods based on sampling. We investigate the idea of item reordering, which can improve the low-level efficiency of the algorithm. Second, we present a new way of generating “implication rules,” which are normalized based on both the antecedent and the consequent and are truly implications (not simply a measure of co-occurrence), and we show how they produce more intuitive results than other methods. Finally, we show how different characteristics of real data, as opposed by synthetic data, can dramatically affect the performance of the system and the form of the results.