BEYOND MARKET BASKETS - GENERALIZING ASSOCIATION RULES TO DEPENDENCE RULES

One of the more well-studied problems in data mining is the search for association rules in market basket data. Association rules are intend ed to identify patterns of the type: ''A customer purchasing item A of ten also purchases item B.'' Motivated partly by the goal of generaliz ing beyond market basket data and partly by the goal of ironing out so me problems in the definition of association rules, we develop the not ion of dependence rules that identify statistical dependence in both t he presence and absence of items in itemsets. We propose measuring sig nificance of dependence via the chi-squared test for independence from classical statistics. This leads to a measure that is upward-closed i n the itemset lattice, enabling us to reduce the mining problem to the search for a border between dependent and independent itemsets in the lattice. We develop pruning strategies based on the closure property and thereby devise an efficient algorithm for discovering dependence r ules. We demonstrate our algorithm's effectiveness by testing it on ce nsus data, text data (wherein we seek term dependence), and synthetic data.