Fouille de motifs diversifiés : une approche basée sur la relaxation et l'échantillonnage
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.