PRINCE: Extraction optimisé'e des bases gé'né'riques de ré'gles sans calcul de fermetures

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. This requires the extraction of generic bases of association rules, of reduced size and which summarize the same information. Using the concept of minimal generator, we propose an algorithm, called PRINCE, allowing an optimized extraction of the 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 experimental evaluation, carried out on benchmarking sparse and dense datasets, have shown that the proposed approach largely outperforms the pioneer algorithms CLOSE, A-CLOSE and TITANIC.