Fouille de Motifs Fermés et Diversifiés Basée sur la Relaxation

International audienceDans cet article, nous proposons une nouvelle approche basée sur la programmation par contraintes pour l'extraction de motifs fréquents fermés et diversifiés (Hien et al., 2020a). 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, ce qui rend le processus d'extraction infaisable. Pour y remédier, nous 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