Algorithme Efficace pour la Fouille de Séquences Fréquentes avec la Programmation par Contraintes

La programmation par contraintes (CP) a séduit la communauté de fouille de données grâce à son approche hautement déclarative et sa flexibilité. Cependant, ces avantages n’offrent pas une garantie d’efficacité. En témoigne la littérature où les méthodes basées sur la CP n’ont toujours pas réussi à être aussi performante que les méthodes spécialisées. Dans ce papier publié au ECML-PKDD’16 [1], nous montrons comment en combinant les techniques des deux mondes on peut arriver à une méthode très robuste et efficace en plus d’être modulaire et flexible pour résoudre les problèmes de fouille de séquences fréquentes. Notre approche, intitulée PPIC, est une contrainte globale, conçue sur les méthodes de projection de base de données. Cette contrainte utilise une structure de données auto-backtraquante (trailing) pour stocker et restaurer efficacement les bases de données projetées. Le calcul des supports et le filtrage reposent sur des améliorations algorithmiques utilisant des données pré-calculées. Des expériences détaillées montrent comment cette approche, pour la première fois, surpasse à la fois les méthodes basées sur la CP et celles spécialisées. Ainsi, le moindre qu’on puisse dire est que le tandem fouille de données et CP a encore de beaux jours devant lui.

References