Prince: An Algorithm for Generating Rule Bases Without Closure Computations

摘要

The problem of the relevance and the usefulness of extracted association rules is becoming of primary importance, since an overwhelming number of association rules may be derived, even from reasonably sized databases. To overcome such drawback, the extraction of reduced size generic bases of association rules seems to be promising. Using the concept of minimal generator, we propose an algorithm, called PRINCE, allowing a shrewd extraction of generic bases of rules. To this end, PRINCE builds the partial order. Its originality is that this partial order is maintained between minimal generators and no more between closed itemsets. A structure called minimal generator lattice is then built, from which the derivation of the generic association rules becomes straightforward. An intensive experimental evaluation, carried out on benchmarking sparse and dense datasets, showed that PRINCE largely outperforms the pioneer level-wise algorithms, i.e., CLOSE, A-CLOSE and TITANIC.