You are here

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

TitleAlgorithme Efficace pour la Fouille de Séquences Fréquentes avec la Programmation par Contraintes
Publication TypeConference Paper
Year of Publication2017
AuthorsAoga, John O. R., Guns Tias, and Schaus Pierre
Conference NameTreizièmes journées Francophones de Programmation par Contraintes - JFPC'17
Abstract

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

  1. An Efficient Algorithm for Mining Frequent Sequence with Constraint Programming, Aoga, John O. R., Guns Tias, and Schaus Pierre , Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2016, Riva del Garda, Italy, September 19-23, 2016, Proceedings, Part II, Cham, p.315–330, (2016)
Full text: