Discovering associations with numeric variables

Geoffrey I. WebbKDD 2001 · DOI

TL;DR

This paper introduces "impact rules" for discovering associations between conditions and numeric outcomes, going beyond traditional association rules. It presents an efficient search algorithm (OPUS_IR) that overcomes the computational limitations of previous methods, particularly for dense datasets, and avoids arbitrary constraints on rule coverage.

What Problem Does This Paper Address?

Traditional association rules, like those found by the Apriori algorithm, excel at finding relationships between categorical items (e.g., "people who buy bread also buy milk"). However, they struggle when the target outcome is a numeric variable (e.g., predicting customer profitability). While regression techniques can predict numeric values, they don't explicitly identify segments of data with specific characteristics that lead to a particular outcome. Existing methods that try to adapt association rules for numeric data often rely on discretizing numeric variables into bins. This discretization can distort the underlying relationships and lead to a loss of information, making it difficult to accurately assess the impact on the numeric target. The paper aims to bridge this gap by enabling the discovery of rules that directly characterize segments of data and their impact on a numeric variable, without the information loss of discretization.

Methods

The core contribution is the introduction of impact rules. These rules consist of an antecedent (a conjunction of conditions, similar to the left-hand side of a traditional association rule) and a consequent that summarizes the impact on a numeric target variable (e.g., mean, sum, count).

The paper proposes an efficient search algorithm called OPUS_IR, based on the existing OPUS search framework. OPUS is designed for systematic search through combinations of conditions, pruning branches of the search space that cannot lead to a solution. OPUS_IR leverages this by:

  • Systematic Search: It explores combinations of conditions to form antecedents.
  • Efficient Pruning: It uses pruning rules to eliminate unpromising branches of the search space, significantly reducing computational cost. This is crucial for handling large datasets.
  • Avoiding Frequent Itemset Generation: Unlike prior work (e.g., Aumann and Lindell), OPUS_IR does not rely on generating frequent itemsets first. This bypasses the memory and computational bottlenecks associated with frequent itemset mining, especially for dense datasets.
  • Flexible Interestingness Measures: It supports various measures of interestingness for the consequent, including deviation from the overall mean, sum, and a novel "impact" measure that considers both the mean and the size of the covered segment.

Datasets

The paper evaluates its approach on several real-world datasets from the UCI knowledge discovery and machine learning repositories. These include:

  • Abalone
  • Covtype
  • Housing
  • IPUMS.la.99
  • KDDcup98
  • Ticdata2000

For these datasets, numeric attributes (other than the target) were discretized into three categorical values to form the conditions for the antecedents.

Key Insights and Ideas

  • Direct Numeric Impact: Impact rules offer a more direct way to understand how specific data segments influence numeric outcomes compared to discretized association rules. This avoids the information loss and potential distortions of binning.
  • Efficiency for Dense Data: The OPUS_IR algorithm's ability to avoid frequent itemset generation makes it significantly more efficient for dense datasets, where traditional methods struggle.
  • Avoiding Arbitrary Constraints: The proposed method can discover interesting rules without requiring users to pre-specify arbitrary minimum coverage constraints, which can sometimes lead to missing important rules.
  • Novel "Impact" Measure: The introduction of an "impact" measure that balances the mean of the target with the size of the segment provides a valuable tool for identifying segments that contribute significantly to the overall outcome, not just those with high average values.

Key Results

The paper demonstrates the effectiveness of OPUS_IR through experimental evaluation:

  • Speed: OPUS_IR was significantly faster than a frequent itemset-based approach, especially on larger datasets. For instance, the frequent itemset approach failed to complete on some datasets due to memory or time constraints.
  • Rule Discovery: OPUS_IR successfully discovered impact rules for all tested datasets.
  • Illustrative Examples: The paper provides compelling examples of impact rules that identify small segments of data accounting for a disproportionately large share of the target variable (e.g., a segment representing 5% of data accounting for over 25% of total income, or 5% of data accounting for over 99% of donations). These examples highlight the practical utility of impact rules in identifying high-value segments.

Limitations and Future Work

  • Discretization: While the paper addresses the limitations of discretization, it still relies on it for non-target numeric attributes. The authors acknowledge that this is a necessary step for forming Boolean conditions.
  • Computational Cost: While OPUS_IR is efficient, the search space remains exponential in the number of conditions. The paper limits the depth of the search (maximum 5 conditions) to manage this.
  • Future Work: The paper suggests that the framework can be extended to discover rules that minimize interestingness measures, not just maximize them. Further exploration of more sophisticated interestingness measures is also implied.

Summary updated

BibTeX
@inproceedings{webb2001discovering,
  author = {Geoffrey I. Webb},
  title = {{Discovering associations with numeric variables}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2001},
  doi = {10.1145/502512.502569},
}
Figure