José Luis Balcázar (Universitat Politècnica de Catalunya y Universidad de Cantabria)

Towards a Logic of Association Rules: Deduction,
Optimum Axiomatizations, and Objective Novelty

An association rule is a form of partial
implication between two terms (sets of propositional variables, understood
conjunctively). In the case of standard implications, we are just back in Horn
logic; but, in association rules, the notion of implication is redefined to
allow exceptions or different populations. Association rules are among the most
widely employed data analysismethods in the field of Data Mining.

Naive uses of association miners end up often
providing far too large amounts of mined associations to result actually useful in
practice. Many proposals exist for selecting appropriate association rules,
trying to measure their interest in various ways; most of these approaches are
statistical in nature, or share their main traits with statistical notions. In
the most common approach, association rules are parameterized by a lower bound
on their confidence, which is the empirical conditional probability of their
consequent given the antecedent, and/or by some other parameter bounds such as
``support'' or deviation from independence.

Alternatively, some existing notions of
redundancy among association rules allow for a logical-style characterization
and lead to irredundant bases (axiomatizations) of absolutely minimum size. We
will discuss notions of redundancy, that is, of logicalentailment, among association rules, and how to
complement the association rule mining process by filtering also the obtained
rules according to their novelty, measured in a relative way with respect to
the confidences of related rules.

Recent papers describing these advances are
available from the author's webpage. Additionally, we can actually offer a
preliminary version of a rule-mining proof-of-concept system implementing our
contributions.