Rule interestingness analysis using OLAP operations

Bing Liu, Kaidi Zhao, Jeffrey Benkler, Weimin XiaoKDD 2006 · DOI

TL;DR

This paper introduces a novel approach to make data mining results more understandable and actionable by framing rule analysis as Online Analytical Processing (OLAP) operations on "rule cubes." This method helps users systematically explore discovered rules within their context, leading to the identification of "general impressions" and actionable insights, as demonstrated by its successful deployment in Motorola.

What Problem Does This Paper Address?

Data mining algorithms, particularly those generating association rules, often produce an overwhelming number of rules. This "interestingness problem" makes it incredibly difficult for users to sift through the results and find genuinely useful knowledge. Existing methods often treat rules in isolation, failing to capture the contextual relationships between them, which domain experts find crucial for understanding. Furthermore, the traditional rule mining paradigm can fragment the knowledge space, creating "holes" and making it hard to see the bigger picture or discover generalized trends. This paper aims to bridge this gap by providing a systematic and user-driven way to explore and understand discovered rules.

Methods

The core innovation of this paper is the application of OLAP operations to analyze discovered rules. Instead of treating rules as individual entities, they are organized into multi-dimensional "rule cubes."

  • Rule Cubes: These are constructed from class association rules (CARs). A rule cube uses attributes as dimensions and the class attribute as one dimension. The "cell value" represents the support count of a rule, and confidence can be computed from these counts.
  • OLAP Operations: Standard OLAP operations like roll-up (aggregating dimensions), drill-down (adding detail), slice (selecting a subset of a dimension), and dice (selecting subsets of multiple dimensions) are adapted to navigate and explore these rule cubes. This allows users to view rules in context and discover relationships.
  • General Impressions (GI) Mining: The system also mines for "general impressions," which are higher-level insights that domain experts find more useful than individual rules. These include:
  • Discriminative Attributes: Attributes that effectively distinguish between classes.
  • Trend Behaviors: How the likelihood of a class changes as an attribute's values increase or decrease (applicable to ordinal/numeric attributes).
  • Context Exceptions: Rules that are highly correlated with a class within a specific context, highlighting deviations from expected behavior.

The system uses a class association rule miner as its backbone, setting minimum support and confidence to zero for rules with one or two conditions to build comprehensive rule cubes, and non-zero values for longer rules to manage complexity.

Datasets

The primary dataset used for development and evaluation is cellular phone call records from Motorola, containing millions of records and hundreds of attributes. The paper notes that the system has since been successfully applied to eleven other diverse datasets within Motorola for diagnostic applications and general data understanding. No new benchmarks were introduced; rather, the focus was on applying the proposed method to real-world industrial data.

Key Insights and Ideas

  • Context is King: A single rule is rarely interesting on its own. Its value emerges when viewed in relation to other rules (its "siblings" or context).
  • General Impressions Trump Individual Rules: Domain experts prefer high-level trends and summaries (like "attribute X is important" or "as attribute Y increases, calls are more likely to fail") over lists of specific rules.
  • OLAP for Rule Exploration: Applying OLAP operations to rule cubes provides a systematic, user-driven, and intuitive way to explore the vast space of discovered rules.
  • Bridging Mining and Visualization: The rule cube and OLAP framework naturally integrate rule mining with visualization, providing context and facilitating discovery.
  • Addressing the "Holes": By constructing rule cubes that cover all attribute values (at least for 1- and 2-condition rules), the system avoids the fragmentation of the knowledge space caused by traditional minsup/minconf thresholds.

Key Results

The paper doesn't present traditional quantitative results like accuracy improvements. Instead, its key result is the successful deployment and daily use of the "Opportunity Map" system in Motorola. This system, built on the proposed OLAP-based rule analysis approach, has been used to:

  • Identify actionable knowledge for diagnosing cellular phone call failures.
  • Analyze eleven other large datasets for various diagnostic applications.
  • Provide users with a systematic way to explore and understand complex data.
  • Enable the discovery of "general impressions" and contextual exceptions that were previously difficult to find.

The effectiveness is primarily demonstrated through user adoption and the system's ability to uncover useful insights in real-world industrial scenarios.

Limitations and Future Work

  • Scalability of Rule Cubes: The paper acknowledges that building rule cubes for all attributes is computationally infeasible due to exponential growth. The current approach focuses on 2- and 3-dimensional cubes, which are sufficient for most practical applications where users prefer shorter rules.
  • Visualization of Long Rules: Rules with more than two conditions are not directly visualized in the current system, though they can be listed separately.
  • Future Work: The paper suggests that the OLAP framework provides a natural foundation for further research in rule visualization and the mining of general impressions. The system's success in various diagnostic applications indicates its broad applicability.

Summary updated

BibTeX
@inproceedings{liu2006rule,
  author = {Bing Liu and Kaidi Zhao and Jeffrey Benkler and Weimin Xiao},
  title = {{Rule interestingness analysis using OLAP operations}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2006},
  doi = {10.1145/1150402.1150437},
}
Figure