Granular association rules on two universes with four measures

Fan Min, Qinghua Hu, William ZhuarXiv 2012 · OpenReview

TL;DR

This paper introduces "granular association rules" that go beyond traditional support and confidence measures to capture richer relationships between entities in multiple tables. By proposing four new measures and specialized algorithms, the authors enable more nuanced pattern discovery in relational databases, leading to significant performance improvements for rule mining.

What Problem Does This Paper Address?

Traditional association rule mining, while powerful for single datasets, struggles to capture complex relationships hidden across multiple related tables in a database. Existing relational association rule methods often rely on limited measures like support and confidence, which can be insufficient to fully describe the strength and nature of a rule. For instance, a rule might indicate a general connection, but fail to specify how much of a certain attribute is involved or how many entities satisfy the condition. This ambiguity limits their practical application, especially in areas like recommendation systems where nuanced understanding is crucial. The authors aim to bridge this gap by introducing a more expressive framework for relational association rules.

Methods

The core contribution is the introduction of granular association rules, which operate on two "universes" (sets of objects) and utilize four measures: source coverage, target coverage, source confidence, and target confidence. These measures provide a more detailed semantic understanding of the discovered patterns.

Key methodological aspects include:

  • Granular Computing: The concept of "granules" (representing sets of objects with shared properties) is central, allowing for the representation of abstract concepts rather than just individual objects.
  • Four Measures:
    • Source Coverage: The proportion of objects in the first universe that satisfy the rule's premise.
  • Target Coverage: The proportion of objects in the second universe that satisfy the rule's conclusion.
  • Source Confidence: The proportion of objects in the first universe's granule that are connected to the second universe's granule.
  • Target Confidence: The proportion of objects in the second universe's granule that are connected to the first universe's granule.
  • Subtypes of Rules: The authors define three subtypes based on specific confidence values (complete match, left-hand side partial match, right-hand side partial match) and a general "partial match" case.
  • Algorithms:
    • Sandwich Algorithm: A general algorithm that generates candidate granules from both universes and then checks for valid rules. It includes specialized rule-checking approaches for each subtype, leading to significant speedups.
  • Forward and Backward Algorithms: Two specialized algorithms designed for the "complete match" subtype, aiming for improved efficiency.

Datasets

The authors evaluated their algorithms on two real-world datasets:

  • MovieLens: A widely used dataset for recommender systems, containing user ratings for movies. The data was preprocessed to include user attributes (age, gender, occupation), movie attributes (release year, genre), and a "rates" relation.
  • Minnan Normal University Course Selection Data: This dataset contains student and course information, along with a "selects" relation indicating which students enrolled in which courses.

Key Insights and Ideas

  • Richer Semantics: The four measures offer a more nuanced understanding of relational patterns than traditional support and confidence, enabling more interpretable and actionable insights.
  • Granularity Matters: The use of granules allows for discovering relationships between abstract concepts (e.g., "men" and "alcohol") rather than just individual instances.
  • Subtype Specialization is Key: Tailoring rule-checking algorithms to specific subtypes of granular association rules leads to dramatic performance improvements, highlighting the importance of understanding the structure of discovered patterns.
  • Tradeoffs Exist: There's an inherent tradeoff between source and target confidence, especially in the general "partial match" case, requiring careful parameter selection.

Key Results

  • Performance Improvement: Dedicated rule-checking approaches for the three subtypes within the sandwich algorithm were 2-3 orders of magnitude faster than the general partial match approach.
  • Meaningful Rules: Experiments on both datasets yielded rules that were considered meaningful and interpretable by the authors, demonstrating the practical applicability of granular association rules. For example, rules like "male students between 18 to 24 years old like movies that belong to action, adventure and scientific fiction" were identified.
  • Algorithm Comparison: For the MovieLens dataset, the sandwich algorithm performed best, while for the course selection dataset, the forward and backward algorithms showed better scalability, especially with decreasing thresholds. This suggests that algorithm choice can depend on dataset characteristics.

Limitations and Future Work

  • Computational Complexity: The authors acknowledge that the proposed algorithms, while improved by subtype specialization, can still be computationally intensive for very large datasets.
  • Parameter Setting: The need for four thresholds (ms, mt, sc, tc) might be cumbersome for users.
  • Data Types: The current work primarily focuses on symbolic data. Future work could explore handling numeric, heterogeneous, and data with missing values.
  • Algorithm Efficiency: Further research is needed to develop even more efficient algorithms, potentially by leveraging the Apriori property more effectively or exploring heuristic approaches.
  • Theoretical Foundations: Extending the theoretical framework to handle more complex scenarios, including variable precision rough sets and decision-theoretic rough sets, is suggested.
  • Generalization to More Universes: Extending the approach to handle relationships involving more than two universes is a significant area for future research.

Summary updated

Abstract

Relational association rules reveal patterns hide in multiple tables. Existing rules are usually evaluated through two measures, namely support and confidence. However, these two measures may not be enough to describe the strength of a rule. In this paper, we introduce granular association rules with four measures to reveal connections between granules in two universes, and propose three algorithms for rule mining. An example of such a rule might be "40% men like at least 30% kinds of alcohol; 45% customers are men and 6% products are alcohol." Here 45%, 6%, 40%, and 30% are the source coverage, the target coverage, the source confidence, and the target confidence, respectively. With these measures, our rules are semantically richer than existing ones. Three subtypes of rules are obtained through considering special requirements on the source/target confidence. Then we define a rule mining problem, and design a sandwich algorithm with different rule checking approaches for different subtypes. Experiments on a real world dataset show that the approaches dedicated to three subtypes are 2-3 orders of magnitudes faster than the one for the general case. A forward algorithm and a backward algorithm for one particular subtype can speed up the mining process further. This work opens a new research trend concerning relational association rule mining, granular computing and rough sets.
BibTeX
@misc{min2012granular,
  author = {Fan Min and Qinghua Hu and William Zhu},
  title = {{Granular association rules on two universes with four measures}},
  year = {2012},
  eprint = {1209.5598},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1209.5598},
}

Loading related content...

Figure