Symétries et Extraction de Motifs Ensemblistes
Abstract
Les symétries sont des propriétés structurelles qu'on détecte dans un
grand nombre de bases de données. Dans cet article, nous étudions l'exploitation
des symétries pour élaguer l'espace de recherche dans les problèmes d'extraction
de motifs ensemblistes. Notre approche est basée sur une intégration
dynamique des symétries dans les algorithmes de type Apriori permettant de réduire
l'espace des motifs candidats. En effet, pour un motif donné, les symétries
nous permettent de déduire les motifs qui lui sont symétriques et vérifiant par
conséquent les mêmes propriétés. Nous détaillons notre approche en utilisant
l'exemple des motifs fréquents. Ensuite, nous la généralisons au cadre unificateur
de Mannila et Toivonen pour l'extraction des motifs ensemblistes. Les expériences
menées montrent la faisabilité et l'apport de notre approche d'élagage
basé sur les symétries.