Découverte de motifs n-aires utilisant la programmation par contraintes

Until recently, data mining and Constraint Programming have been developed separately one from the other. This thesis is one of the first to address the relationships between these two areas of computer science, in particular using constraint programming techniques for constraint-based mining. The data mining community has proposed generic approaches to discover local patterns under constraints, and this issue is rather well-mastered. However, these approaches do not take into consideration that the interest of a pattern often depends on the other patterns. Such a pattern is called n-ary pattern or pattern set. Few works on mining n-ary patterns were conducted and the proposed approaches are ad hoc. This thesis proposes an unified framework for modeling and solving n-ary constraints in data mining. First, the n-ary pattern extraction problem is modeled as a Constraint Satisfaction Problem (CSP). Then, a high-level declarative language for mining n-ary patterns is proposed. This language allows to express a wide range of n-ary constraints. Several solving methods are developed and compared. The main advantages of this framework are its declarative and generic sides. To the best of our knowledge, it is the first generic and flexible framework for modeling and mining n-ary patterns.La fouille de données et la Programmation Par Contraintes (PPC) sont deux domaines de l'informatique qui ont eu, jusqu'à très récemment, des destins séparés. Cette thèse est l'une des toutes premières à s'intéresser aux liens entre la fouille de données et la PPC, et notamment aux apports de cette dernière à l'extraction de motifs sous contraintes. Différentes méthodes génériques pour la découverte de motifs locaux ont été proposées. Mais, ces méthodes ne prennent pas en considération le fait que l'intérêt d'un motif dépend souvent d'autres motifs. Un tel motif est appelé motif n-aire. Très peu de travaux concernant l'extraction de motifs n-aires ont été menés et les méthodes développées sont toutes ad hoc. Cette thèse propose un cadre unifié pour modéliser et résoudre les contraintes n-aires en fouille de données. Tout d'abord, l'extraction de motifs n-aires est modélisée sous forme de problème de satisfaction de contraintes (CSP). Puis, un langage de requêtes à base de contraintes de haut niveau est proposé. Ce langage permet d'exprimer une large panoplie de contraintes n-aires. Plusieurs méthodes de résolution sont développées et comparées. Les apports principaux de ce cadre sont sa déclarativité et sa généricité. Il s'agit du premier cadre générique et flexible permettant la modélisation et la résolution de contraintes n-aires en fouille de données