A fast compound algorithm for mining generators, closed itemsets, and computing links between equivalence classes

Abstract : In pattern mining and association rule mining, there is a variety of algo-rithms for mining frequent closed itemsets (FCIs) and frequent generators (FGs), whereas a smaller part further involves the precedence relation between FCIs. The interplay of these three constructs and their joint computation have been studied within the formal concept analysis (FCA) field yet none of the proposed algorithms is scalable. In frequent pattern mining, at least one suite of efficient algorithms has been designed that exploits basically the same ideas and follows the same overall computational schema. Based on an in-depth analysis of the aforementioned inter-play that is rooted in a fundamental duality from hypergraph theory, we propose a new schema that should enable for a more parsimonious computation. We exemplify L. Szathmary (B) L. Szathmary et al. the new schema in the design of Snow-Touch, a concrete FCI/FG/precedence miner that reuses an existing algorithm, Charm, for mining FCIs, and completes it with two original methods for mining FGs and precedence, respectively. The performance of Snow-Touch and of its closest competitor, Charm-L, were experimentally compared using a large variety of datasets. The outcome of the experimental study suggests that our method outperforms Charm-L on dense data while on sparse one the trend is reversed. Furthermore, we demonstrate the usefulness of our method and the new schema through an application to the analysis of a genome dataset. The initial results reported here confirm the capacity of the method to focus on significant associations.
Type de document :
Article dans une revue
Annals of Mathematics and Artificial Intelligence, Springer Verlag, 2014, 70, pp.81 - 105. 〈10.1007/s10472-013-9372-8〉
Liste complète des métadonnées

Littérature citée [38 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01101140
Contributeur : Amedeo Napoli <>
Soumis le : vendredi 9 janvier 2015 - 17:06:03
Dernière modification le : jeudi 11 janvier 2018 - 06:25:24
Document(s) archivé(s) le : samedi 12 septembre 2015 - 00:45:26

Fichier

ls-etal-amai70-2014.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Laszlo Szathmary, Petko Valtchev, Amedeo Napoli, Robert Godin, Alix Boc, et al.. A fast compound algorithm for mining generators, closed itemsets, and computing links between equivalence classes. Annals of Mathematics and Artificial Intelligence, Springer Verlag, 2014, 70, pp.81 - 105. 〈10.1007/s10472-013-9372-8〉. 〈hal-01101140〉

Partager

Métriques

Consultations de la notice

283

Téléchargements de fichiers

303