Contributions to Pattern Discovery and Formal Concept Analysis

The process of collecting and analyzing data to answer predictive, explanatory, and decision-making issues has come to be known as ``data science'' for more than thirty years. Firstly used only by scientists, mainly by statisticians, the term is now widely used in the academics and industrial world. This can be explained in two ways: (i) data is ubiquitous, large, and varied, and (ii) there has been an awareness of the omniscient potential of data. The latter can be economic, societal, scientific, or related to health-care, and is based not only on the data that an entity has, but also on data that it can get (sensors, social networks, open data, etc., freely or not) making the data a black oil that still needs algorithms, methods and methodologies, to be properly refined.One component of data science, Knowledge Discovery in databases (KDD), deals in particular with the Data-Information-Knowledge process with the aim of explaining relationships or discovering hidden properties. Opposed to a purely statistical approach, a family of methods has met an important success over the last twenty years: data-mining and especially pattern-mining. Their goal is to describe, summarize, raise hypotheses from data. In particular, pattern mining makes it possible to efficiently find regularities of various types (such as frequent patterns in a set of transactions, molecular sub-graphs characteristic of toxicity, locally co-expressed gene groups, etc.). In fact, where conventional approaches aim to validate or invalidate an hypothesis given a priori, the search of patterns is seen as an enumeration technique of all the possible hypotheses (a set of exponential size w.r.t the input data) verifying some given constraints or maximizing a certain interest for the expert. Once discovered, the best hypotheses can then be tested, validated or invalidated and ultimately validated as knowledge unit.My scientific adventure began with the study of a binary relationship, very often illustrated by grocery store transaction data, linking customers and products they buy. How to make this relationship speak? What knowledge, behavioral habits, recommendations, etc. can we characterize?This initial question allowed me to travel through different application fields (biology, neuroscience, social networks and video games analytics), seeking to implement or adapt data mining methods to try to understand some phenomena while properly formalizing data and patterns in the most rigorous way. This is the story of this manuscript, according to three main research axes: the formalism framing the methods (Formal Concept Analysis), the methodological and algorithmic aspects related in Data mining, and finally the Knowledge Discovery ``in practice'' through several concrete applications encountered during collaborations with other scientists or industrial partners.Le processus qui permet de collecter des volumes de données puis de les analyser pour répondre à des questions à buts prédictifs, explicatifs et décisionnels, est apparu sous le vocable "science des données'' (data science) il y a déjà plus de trente années. Accaparé d'abord par les scientifiques (notamment les statisticiens et largement pratiqué par les physiciens), ce terme connaît aujourd'hui un usage répandu dans le monde industriel et les collectivités. Cela s'explique de deux manières : (i) les données sont aujourd'hui omniprésentes, en grandes quantités, et variées, et (ii) il y a eu une prise de conscience du potentiel omniscient de ces données. Ce dernier peut être économique, sociétal, sanitaire ou encore scientifique, et se base non plus seulement sur des données qu'une entité possède, mais également sur des données qu'elle peut se procurer (capteurs, réseaux sociaux, données ouvertes open data, etc., gratuitement ou non) faisant de la donnée un or noir toujours trop peu raffiné.Une composante de la science de données, la "découverte de connaissances'' (DC ou Knowledge discovery in databases, KDD), traite en particulier de la chaîne Données–Informations–Connaissances avec le souci d'expliciter des relations ou propriétés enfouies. Se différenciant d'une approche purement statistique une famille de méthodes a connu un succès vaste ces vingt dernières années : la fouille de données sous-contraintes. Elles visent à décrire, résumer, soulever des hypothèses à partir de données. Notamment, la fouille de motifs permet de trouver de manière efficace des régularités de divers types (comme des motifs fréquents dans un ensemble de transactions, des sous-graphes moléculaires caractéristiques d'une toxicité, des groupes gènes localement co-exprimés, etc.). En fait, là où les approches classiques visent à valider ou invalider une hypothèse donnée a priori, la fouille de motifs se voit au contraire comme une technique d'énumération de toutes les hypothèses possibles vérifiant certaines contraintes ou encore maximisant un certain intérêt pour l'expert parmi un ensemble de taille exponentiel. Une fois découvertes, les meilleures hypothèses peuvent être alors testées, validées ou invalidées. On fait donc véritablement face à un processus de découverte d'hypothèses ayant le plus de chances d'être validées ensuite comme connaissances.Mon initiation scientifique a commencé par l'étude d'une relation binaire, très souvent illustrée par le panier de la ménagère, liant clients et produits qu'ils achètent. Comment faire parler cette relation données ? Quelles connaissances, habitudes comportementales, recommandations, etc. peut-on extraire ?Cette question initiale m'a alors permis de voyager à travers différents domaines applicatifs (biologie, neurosciences, réseaux sociaux et jeux-vidéo), cherchant à mettre en application ou adaptant des méthodes de fouille de données pour tenter comprendre des phénomènes tout en formalisant le plus rigoureusement possible le cadre dans lequel ces méthodes s'inscrivent. C'est donc cette histoire que je vais raconter dans ce manuscrit, selon trois axes principaux : le formalisme cadrant les méthodes avec l'Analyse de Concepts Formels, l'aspect méthodologique et algorithmique à travers la Fouille de données, et enfin la Découverte de Connaissances à travers plusieurs applications concrètes rencontrées lors de collaborations avec d'autres scientifiques ou industriel