RNTI

MODULAD
Fouille de motifs diversifiés : une approche basée sur la relaxation et l'échantillonnage
In SDC 2024, vol. RNTI-A-9, pp.33-70
Résumé
Dans cet article, nous proposons une approche basée sur la programmation par contraintes pour l'extraction de motifs fréquents fermés et diversifiés. La diversité est contrôlée par une contrainte de seuil sur l'indice de Jaccard. Nous montrons que cette mesure n'a pas de propriété de monotonie et proposons une nouvelle contrainte globale, CLOSEDDIVERSITY, qui exploite une relaxation anti-monotone de l'indice de Jaccard pour élaguer les motifs non diversifiés. Une seconde relaxation, basée sur une borne supérieure, est exploitée via une nouvelle heuristique de branchement. Enfin, nous montrons comment intégrer notre contrainte pour l'échantillonnage de motifs diversifiés. Les résultats expérimentaux sur plusieurs jeux de données démontrent l'efficacité en temps de calcul et en termes de diversité de notre approche par rapport aux approches concurrentes.