A logic-based framework for mining and simplifying partial implications (association rules)

Association rule mining creates many redundant rules. This paper proposes a formal ‘Simplification Logic’ (SLAR) to manipulate and reduce sets of association rules (with confidence < 1) to a smaller, non-redundant basis without losing information.

Keywords

Simplification logic, SLAR, Association rules, Redundancy, Apriori, Confidence, Support, Luxenburger basis

Association rule mining is a cornerstone of data mining, but the vast number of redundant rules generated by standard algorithms is a major practical problem. While FCA provides a link to non-redundant bases (e.g., the Luxenburger basis), a formal logic for manipulating and simplifying sets of partial implications (rules with confidence $<$ 1) is lacking. This paper bridges this gap by extending the Simplification Logic paradigm from formal implications to association rules. We define logical inference for rules with confidence and support, and we develop a set of sound simplification rules that allow for the reduction of a large set of association rules to a smaller, equivalent, and more informative basis. We provide an algorithm to perform this simplification and demonstrate its effectiveness in drastically reducing the number of rules generated from real-world datasets without loss of information.

Introduction

Since their introduction, association rules have been a key tool for discovering patterns in transactional data. However, algorithms like Apriori generate an enormous number of rules, many of which are redundant (i.e., they can be logically inferred from other, simpler rules). This makes exploration and interpretation by human analysts difficult.

The connection between FCA and association rules via the Luxenburger basis provides a path to non-redundant sets of rules. However, this connection is structural. There is no corresponding “logic” that allows one to reason with and simplify arbitrary sets of association rules in the way Simplification Logic does for formal implications.

This paper introduces such a logic. Our goal is to equip data miners with a formal tool to “clean” and “compress” sets of association rules. Our contributions are:

1. A formal semantics and syntax for a Simplification Logic for Association Rules (SLAR), defining how support and confidence propagate through inference.
2. A set of sound simplification and deduction rules for SLAR.
3. An efficient algorithm that applies these rules to reduce a given set of association rules to a more compact, non-redundant basis.

Methodology and expected theoretical results

The main challenge is to correctly define how confidence and support measures behave under logical deduction.

Theoretical foundation: The logic SLAR

Let a rule be a triple $(A \to B, c, s)$ where $c$ is confidence and $s$ is support. * Inference rule (transitivity): The cornerstone will be a generalized transitivity rule. If we have $A \to B$ with $(c_1, s_1)$ and $A \cup B \to C$ with $(c_2, s_2)$, what can we say about the rule $A \to C$? We will prove that $A \to C$ holds with confidence $c = c_1 \cdot c_2$ and support $s=s_2$. This is a well-known result, but we will integrate it into a complete logical system. * Simplification rule: The key rule will be a generalization of the simplification rule $A \to B, C \to D \vdash A \cup (C \setminus B) \to D$. The challenge is to derive the confidence and support of the resulting rule. This is a non-trivial problem and will likely result in a lower bound on the confidence. * Main theoretical result (soundness and completeness): We will prove that the proposed set of rules is sound (any derived rule is valid in the original data) and investigate its completeness (can all valid rules be derived from a basis?).

Algorithmic approach

Based on the logic, we will design an algorithm that takes a large set of association rules (e.g., generated by Apriori) as input and iteratively applies the simplification rules to eliminate redundancies and reduce the size of the set. This will be analogous to the algorithms used for simplifying functional dependencies.

Work plan

• Months 1-4: Develop the full theory of SLAR. This is the most research-intensive part and will be done in collaboration with Prof. María Eugenia Cornejo Piñero and the M-CIS group.
• Months 5-7: Design and implement the simplification algorithm.
• Months 8-10: Test the algorithm on datasets from the UCI repository. Measure the percentage of rule reduction and the computational time of the simplification process.
• Months 11-12: Write the manuscript, highlighting the novelty of a logical (rather than purely statistical) approach to association rule post-processing.

Potential target journals

1. Data Mining and Knowledge Discovery (Q1): The top journal for fundamental contributions to data mining algorithms and theory.
2. IEEE Transactions on Knowledge and Data Engineering (TKDE) (Q1): Another premier venue for data mining research.
3. International Journal of Approximate Reasoning (Q2): An excellent fit given the focus on reasoning with uncertain rules (confidence $<$ 1).

Minimum viable article (MVA) strategy

This topic is rich and can generate a series of papers.

• Paper 1 (The MVA - the logic and algorithm):
  • Scope: Introduce the SLAR logic for the classical binary case. Present the simplification rules, prove their soundness, and provide the core simplification algorithm. An empirical evaluation on a few datasets showing significant rule reduction would be essential.
  • Goal: To introduce the novel concept of a formal logic for simplifying association rules.
  • Target venue: A top data mining conference like KDD, ICDM, or ECML-PKDD, followed by a submission to Data Mining and Knowledge Discovery.
• Paper 2 (The fuzzy/mixed extension):
  • Scope: Extend the SLAR framework to handle fuzzy association rules or rules with mixed (positive/negative) attributes. This requires redefining how fuzzy confidence/support values propagate through the logical rules, which is a significant theoretical step.
  • Goal: To generalize the framework to more complex and realistic data types.
  • Target venue: A journal focused on fuzzy systems or reasoning, such as IEEE Transactions on Fuzzy Systems or International Journal of Approximate Reasoning.