Smart mining of sequences with ASP

Contact

Guyet Thomas (thomas.guyet@irisa.fr), Torsten Schaub (torsten.schaub@inria.fr)

Mots-clés

Constraintes, Answer Set Programming, pattern mining

Description

L’objectif de ce stage est de mettre en place une méthode d’extraction de motifs intéressants dans des séquences de prescriptions médicamenteuses à l’aide de programmation déclarative (ASP).

Les méthodes d’extraction de motifs visent à découvrir des connaissances intéressantes dans des bases de données massives décrivant des transactions (paniers d’achat de clients – itemsets) ou des séries de transactions (séquence d’actions ou d’achats ). Depuis deux décennies, les recherches se sont focalisées, avec un certain succès, sur des approches algorithmiques dédiées très efficaces. Mais des travaux récents s’intéressent à des approches génériques capables d’intégrer au plus tôt des connaissances du domaine et d’extraire des motifs de nature variée (itemsets, séquences, graphes). La plupart de ces approches adoptent le paradigme de la résolution de contraintes [1] : générer des motifs candidats et élaguer au plus tôt ceux qui ne satisfont pas certaines contraintes (syntaxiques ou sémantiques). Le défi consiste alors à exprimer le problème d’extraction de motifs sous la forme de contraintes qui puissent être efficacement résolues. Dans ce domaine, l’extraction de motifs séquentiels posent des problèmes non encore résolus de manière satisfaisante.

L’ASP (Answer Set Programming) est une approche de programmation déclarative, fondée sur un paradigme logique et un langage de modélisation très expressif. Ces dernières années, des outils efficaces, tels que clingo, sont apparus et rendent cette approche de programmation utilisable de manière efficace pour la résolution de problèmes combinatoires. De plus, les capacités récentes de clingo offrent la possibilité de contrôler dynamiquement le processus de résolution. Le langage ASP semble donc être une alternative pertinente pour exprimer les problèmes de fouille de motifs en intégrant des contraintes basées sur des connaissances du domaine.

L’ambition de stage est de mettre en place une méthode d’extraction de motifs séquentiels capables de passer à l’échelle du traitement de grandes données. L’utilisation d’ASP pour l’extraction de motifs reste encore peu explorée [2,3] et le stagiaire pourra s’appuyer sur les travaux en programmation par contraintes pour proposer des modélisations efficaces.

L’approche proposée dans le cadre de ce stage s’inspire de la compression de séquences. Ces techniques d’extraction de motifs s’appuient sur l’idée qu’un motif est intéressant, lorsqu’il compresse efficacement les données [4]. L’intérêt d’une approche par compression est double : extraire les motifs intéressants et construire des résumés des données qui peuvent être présentées aux analystes. Le stagiaire explorera ce principe comme première approche de conception d’un programme ASP pour la fouille de motifs. Les approches mises en place pendant le stage pourront être comparées aux autres approches ASP existantes [2,3] et à des implémentations impératives dédiées. Une partie de l’évaluation quantitative sera menée sur des données simulées. Une seconde partie applicative concernera le développement d’une méthode d’extraction de motifs intéressants dans des séquences de prescriptions médicamenteuses (fournies par l’Assurance Maladie) à l’aide de programmation déclarative (ASP). Ces données sont particulièrement intéressantes car elles sont structurées par des connaissances du domaine imposant des contraintes sur les motifs pertinents à extraire.

Ce projet s’intègre dans le programme de recherche de Torsten Schaub (Pr. Université Potsdam/Berlin) – chaire Internationale INRIA depuis 2014 au sein de l’équipe DREAM. Il coordonne le développement du système Potassco (Potsdam Answer Set Solving Collection) incluant le solveur ASP clingo et dirige une équipe expérimentée dans les techniques de programmation ASP. Dans le cadre de cette collaboration, le stagiaire aura la possibilité de visiter l’équipe de Potsdam (Berlin) pour faciliter les échanges de compétences (prise en charge du déplacement prévue dans le cadre du stage).

Le candidat aura un intérêt fort pour la fouille de motifs. Une connaissance du langage Python est requise. Des compétences en programmation logique (Prolog ou ASP) ou en programmation par contraintes seront les bienvenues.

Bibliographie

  1. Tias Guns, Anton Dries, Guido Tack, Siegfried Nijssen, and Luc De Raedt. MiningZinc: a modeling language for constraint-based mining. In Proceedings of the Twenty-Third international joint conference on Artificial Intelligence (IJCAI’13), Francesca Rossi (Ed.). AAAI Press 1365-1372, 2013.
  2. Matti Järvisalo, Itemset Mining as a Challenge Application for Answer Set Enumeration, In Logic Programming and Nonmonotonic Reasoning, pp. 304-310, 2011.
  3. Thomas Guyet, Yves Moinard, René Quiniou, Using Answer Set Programming for pattern mining, In actes de la conférence IAF, 2014.
  4. Nikolaj Tatti and Jilles Vreeken. The long and the short of it: summarising event sequences with serial episodes. In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining (KDD ’12), 2012.