Proposed Interestingness Measure for Characteristic Rules

AAAI 1996

TL;DR

This paper introduces a novel measure, IC(r), to quantify the "interestingness" of characteristic rules in knowledge discovery. Unlike existing measures designed for discriminant rules, IC(r) specifically addresses the unique nature of characteristic rules, which describe common properties within a class, by leveraging the concept of sufficiency. This work is crucial for effectively filtering and prioritizing rules discovered from databases, especially in noisy real-world data.

What Problem Does This Paper Address?

In knowledge discovery, systems generate numerous rules from databases, but only a fraction are truly "interesting" or useful. Existing measures of rule interestingness, like J-measure or rule strength, are primarily designed for discriminant rules. These rules identify how objects of one class differ from others (e.g., "if X, then class Y"). However, characteristic rules have a different purpose: they describe common properties of objects within a specific class (e.g., "if X, then it's characteristic of class Y"). These rules are valuable for understanding class profiles. The challenge is that existing measures don't adequately capture the nuances of these characteristic rules, especially when dealing with noisy data where strict adherence to a characteristic might be relaxed. This paper aims to fill this gap by proposing a new measure tailored for characteristic rules.

Methods

The authors propose a new interestingness measure called IC(r) for a characteristic rule r of the form h → e (where h represents the class and e represents the evidence or characteristics). This measure is defined as the product of the rule's utility (P(h)) and its "goodness." The goodness is operationalized using the concept of sufficiency, denoted as Suf(r). Sufficiency, defined as P(he) / P(hē), measures how much the presence of h influences the presence of e. A higher Suf(r) indicates that h strongly implies e.

The IC(r) measure is formally defined as: IC(r) = (1 - 1/Suf(r)) * P(h) for 1 < Suf(r) < ∞ IC(r) = 0 otherwise.

This formula ensures that IC(r) lies within the range [0, 1], with 1 being the most interesting. The measure increases monotonically with Suf(r) when Suf(r) is greater than 1, meaning more certain characteristics lead to higher interestingness. The probabilities P(h) and P(he) are estimated from the data.

Datasets

Not discussed in the paper. The paper focuses on the theoretical definition and proposal of the measure, with a mention of applying it to order rules, but specific datasets are not detailed.

Key Insights and Ideas

  • Distinction between Rule Types: The paper highlights a critical distinction between discriminant and characteristic rules, arguing that a single measure of interestingness is insufficient for both.
  • Sufficiency as a Core Concept: The concept of sufficiency, borrowed from technical definitions of probability, is identified as a key metric for evaluating how well a class characteristic holds true.
  • Handling Noisy Data: The proposed measure is designed to be more robust to noisy data by allowing Suf(r) to be greater than 1, rather than strictly requiring it to be a perfect indicator.
  • Monotonicity and Range: The IC(r) measure is designed to be intuitive, ranging from 0 to 1, and to increase as the rule becomes more characteristic and useful.

Key Results

The paper proposes the IC(r) measure and demonstrates its potential. While quantitative results on specific datasets are not presented due to space limitations, the authors state that their preliminary application of the measure to order characteristic rules showed promising performance, placing more complete and accurate rules higher in the ranking. The primary result is the introduction and formal definition of this novel interestingness measure.

Limitations and Future Work

The authors acknowledge that further testing is required to fully validate the measure's performance. Their future work will focus on using this measure to constrain the search space for characteristic rule discovery from databases, implying that the measure can guide the search process towards more promising rules.

Summary updated

BibTeX
@inproceedings{1996proposed,
  title = {{Proposed Interestingness Measure for Characteristic Rules}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure