Mining Confident Rules Without Support Requirement

(File Last Modified Tues, May 28, 2002.)

• Review: Mining Confident Rules Without Support Requirement
• Problem Addressed
• Approach Proposed
• Validation
• Conclusion
• Comments
• Insight

Review: Mining Confident Rules Without Support Requirement

Problem Addressed

• An open problem is to find all rules that satisfy a minimum confidence but not necessarily a minimum support.
• With only the confidence requirement available, the widely used support-based pruning strategy does not apply.

Approach Proposed

A confidence-based pruning stratege is proposed by exploiting the universal-existential upward closure property of confidence.

• universal-existential upward closure
  1. For every attribute Ai not occurring in a rule x->c, some Ai-specialization of x->c has at least the confidence of x->c.
     
  2. If x->c is confident, so is some Ai-specialization of x->c.
     
• The level-wise candidate generation: The confidence-based pruning
  1. Projection-based pruning Every candidate of size k-1(except longest ones) must come from some confident Ai-specializtion. i.e., a projection of a confident k-rule.
     
  2. Intersection-based pruning Every candidate of size k-1(except longest ones) must come from a confident Ai-specializtion for every attribute Ai not yet in the candidate.There are m-k+1 such attributes Ai for a candidate of size k-1, so each candidate of size k-1 comes from intersecting the projection of m-k+1 confident k-rules.
     

The bottleneck of this approach is that the memory is often too small to hold all candidate/rules.The authors present a clustering scheme and an access method to cluster the candidates/rules on disk in the way they are requested. They designed a disk-based implementation to minimize the dominating I/O cost as in a typical database environment.

The disk-based implementation:

1. hash-partition scheme
   
2. buffer allocation
   
3. blocking heuristics
   

Validation

The authors conducted experiments to evaluate the proposed algorithm, and compared their algorithm with Dense-Miner.

• Environment: PIII500, 512M memory, NT4.0
• Synthetic databases: attributes:9, classes:10, cases:100k (discretization: equal-width inteval partition)
• effectiveness of pruning strategies: 2 out of every 3 candidates generated are actually confident rules.
• effectiveness of patition scheme, blocking heuristics, buffer allocation. (100k database, 1500sec)
• the scalability: as the database size increases, the execution time linearly increases; as the dimension increases, there is a quick growth in both the number of rules and the execution time.

Conclusion

• Confidence rules can be mined using confidence-based pruning strategy by exploiting the universal-existential upward closure. This pruning method often yields a very tight search space, in the sense that out of every three candidates generated, two are actually confident.
• By addressing several performance related issures, i.e., data partitioning and data blocking, a disk-based implementation of the pruning strategy is proposed and proved to a superior performance compared to existing methods.
• Related work: According to the authors, they are the first to mine confidence rules with respect to i)LHS can have multiple values, ii) attributes are not restricted to certain domains. The only other algorithm that can be used for finding confidence rules without support requirement is relatively ineffective.

Comments

• The authors claim that the significance of mining confidence rules without support requirement is that: with a high minimum support, discovered rules often are obvious and well known, and rules of low support but high confidence, which usually provides new insights, are not discovered.
• The number of confidence rules generated by their system is too large: between 1e+6 to 2e+6, I doubt the practical value of those overwhelming rules. Without supporting requirement, the evaluation of those rules is a serious issue, for example, if there are total 9 attributes in the datase, any unique k-tuple is a confident k-rule(k=9) with confidence=100%, but can we say this kind of rules are significant? Clearly, there exists large redundance in the rules.
• According to their algorithm, most of the confident rules have a large size, because the more attributes in a rule, the more possible it is confident. This is contrary to rules satisfy both minimum confidence and support.

Insight

• (my opinion)The algorithm and implementation of mining confidence rules proposed in this paper are very impressive, but the value of all the rules generated is hardly conclusive. I still insist that our concentration on mining association (discriminative) rules with a small number of atributes is of more practical value.
• I think, in TAR3, I should introduce in the support as an additional constraint to overcome the exsiting problem in TAR2. The point is: by doing so, we are exactly following other's path of mining association rules(at least from the algorithm point of view). Is this the discovery of my literature review? Help me!
• In general, there are two points we can disscuss:
  1. The size of the LHS: the possiblility for large size of LHS rules to suffer from overfitting.
     
  2. The value of support measurement. Here I realize that my measurement heuristic may have some insight: the ratio of the size of the cases belong to the best class after appling the treatment to the original size of the cases belong to the best class maybe a more apporpriate measurement than the classical support measurement for the discriminate ability of our rules. How do you think?