Tree mining: Equivalence classes for candidate generation - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Intelligent Data Analysis Année : 2009

Tree mining: Equivalence classes for candidate generation

Résumé

With the rise of active research fields such as bioinformatics, taxonomies and the growing use of XML documents, tree data are playing a more and more important role. Mining for frequent subtrees from these data is thus an active research problem and traditional methods (e.g., itemset mining from transactional databases) have to be extended in order to tackle the problem of handling tree-based data. Some approaches have been proposed in the literature, mainly based on generate-and-prune methods. However, they generate a large volume of candidates before pruning them, whereas it could be possible to discard some solutions as they contain unfrequent subtrees. We thus propose a novel approach, called pivot, based on equivalence classes in order to decrease the number of candidates. Three equivalence classes are defined, the first one relying on a right equivalence relation between two trees, the second one on a left equivalence relation, and the third one on the ground of a root equivalence relation. In this paper, we introduce this new method, showing that it is complete (i.e., no frequent subtree is forgotten), and efficient, as illustrated by the experiments led on synthetic and real datasets.
Fichier principal
Vignette du fichier
Treemining.pdf (453.64 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-00798708 , version 1 (05-04-2019)

Identifiants

Citer

Federico del Razo Lopez, Anne Laurent, Pascal Poncelet, Maguelonne Teisseire. Tree mining: Equivalence classes for candidate generation. Intelligent Data Analysis, 2009, 13 (4), pp.555-573. ⟨10.3233/IDA-2009-0381⟩. ⟨lirmm-00798708⟩
208 Consultations
253 Téléchargements

Altmetric

Partager

More