Le calcul de motifs dans de grandes relations binaires a été très étudié. Un succès emblématique concerne la découverte d'ensembles fréquents et leurs post-traitements pour en dériver des règles d'association. Il s'agit de calculer des motifs dans des relations binaires qui enregistrent quelles sont les propriétés satisfaites par des objets. En fait, de nombreux jeux de données se présentent naturellement comme des relations n-aires (avec n > 2). Par exemple, avec l'ajout de dimensions spatiales et/ou temporelles (lieux et/ou temps où les propriétés sont enregistrées), la relation binaire Objets x Propriétés est étendue à une relation 4-aire Objets x Propriétés x Lieux x Temps. Nous avons généralisé le concept de règle d'association dans un tel contexte multi-dimensionnel. Contrairement aux règles usuelles qui n'impliquent que des sous-ensembles d'un seul domaine de la relation, les prémisses et les conclusions de nos règles peuvent impliquer des sous-ensembles arbitraires de certains domaines. Nous avons conçu des mesures de fréquence et de confiance pour définir la sémantique de telles règles et c'est une contribution significative de cette thèse. Le calcul exhaustif de toutes les règles qui ont des fréquences et confiances suffisantes et l'élimination des règles redondantes ont été étudiés. Nous proposons ensuite d'introduire des disjonctions dans les conclusions des règles, ce qui nécessite de retravailler les définitions des mesures d'intérêt et les questions de redondance. Pour ouvrir un champ d'application original, nous considérons la découverte de règles dans des graphes relationnels dynamiques qui peuvent être codés dans des relations n-aires (n ≥ 3). Une application à l'analyse des usages de bicyclettes dans le système Vélo'v (système de Vélos en libre-service du Grand Lyon) montre quelques usages possibles des règles que nous savons calculer avec nos prototypes logiciels. / Pattern discovery in large binary relations has been extensively studied. An emblematic success in this area concerns frequent itemset mining and its post-processing that derives association rules. In this case, we mine binary relations that encode whether some properties are satisfied or not by some objects. It is however clear that many datasets correspond to n-ary relations where n > 2. For example, adding spatial and/or temporal dimensions (location and/or time when the properties are satisfied by the objects) leads to the 4-ary relation Objects x Properties x Places x Times. Therefore, we study the generalization of association rule mining within arbitrary n-ary relations: the datasets are now Boolean tensors and not only Boolean matrices. Unlike standard rules that involve subsets of only one domain of the relation, in our setting, the head and the body of a rule can include arbitrary subsets of some selected domains. A significant contribution of this thesis concerns the design of interestingness measures for such generalized rules: besides a frequency measures, two different views on rule confidence are considered. The concept of non-redundant rules and the efficient extraction of the non-redundant rules satisfying the minimal frequency and minimal confidence constraints are also studied. To increase the subjective interestingness of rules, we then introduce disjunctions in their heads. It requires to redefine the interestingness measures again and to revisit the redundancy issues. Finally, we apply our new rule discovery techniques to dynamic relational graph analysis. Such graphs can be encoded into n-ary relations (n ≥ 3). Our use case concerns bicycle renting in the Vélo'v system (self-service bicycle renting in Lyon). It illustrates the added-value of some rules that can be computed thanks to our software prototypes.

Dans le contexte manufacturier, un ensemble de produits sont acheminés entre différents sites avant d’être vendus à des clients finaux. Chaque site possède différentes fonctions : création, stockage, mise en vente, etc. Les données de traçabilités décrivent de manière riche (temps, position, type d’action,…) les événements de création, acheminement, décoration, etc. des produits. Cependant, de nombreuses anomalies peuvent survenir, comme le détournement de produits ou la contrefaçon d’articles par exemple. La découverte des contextes dans lesquels surviennent ces anomalies est un objectif central pour les filières industrielles concernées. Dans cette thèse, nous proposons un cadre méthodologique de valorisation des traces unitaires par l’utilisation de méthodes d’extraction de connaissances. Nous montrons comment la fouille de données appliquée à des traces transformées en des structures de données adéquates permet d’extraire des motifs intéressants caractéristiques de comportements fréquents. Nous démontrons que la connaissance a priori, celle des flux de produits prévus par les experts et structurée sous la forme d’un modèle de filière, est utile et efficace pour pouvoir classifier les traces unitaires comme déviantes ou non, et permettre d’extraire les contextes (fenêtre de temps, type de produits, sites suspects,…) dans lesquels surviennent ces comportements anormaux. Nous proposons de plus une méthode originale pour détecter les acteurs de la chaîne logistique (distributeurs par exemple) qui auraient usurpé une identité (faux nom). Pour cela, nous utilisons la matrice de confusion de l’étape de classification des traces de comportement pour analyser les erreurs du classifieur. L’analyse formelle de concepts (AFC) permet ensuite de déterminer si des ensembles de traces appartiennent en réalité au même acteur. / In a manufacturing context, a product is moved through different placements or sites before it reaches the final customer. Each of these sites have different functions, e.g. creation, storage, retailing, etc. In this scenario, traceability data describes in a rich way the events a product undergoes in the whole supply chain (from factory to consumer) by recording temporal and spatial information as well as other important elements of description. Thus, traceability is an important mechanism that allows discovering anomalies in a supply chain, like diversion of computer equipment or counterfeits of luxury items. In this thesis, we propose a methodological framework for mining unitary traces using knowledge discovery methods. We show how the process of data mining applied to unitary traces encoded in specific data structures allows extracting interesting patterns that characterize frequent behaviors. We demonstrate that domain knowledge, that is the flow of products provided by experts and compiled in the industry model, is useful and efficient for classifying unitary traces as deviant or not. Moreover, we show how data mining techniques can be used to provide a characterization for abnormal behaviours (When and how did they occur?). We also propose an original method for detecting identity usurpations in the supply chain based on behavioral data, e.g. distributors using fake identities or concealing them. We highlight how the knowledge discovery in databases, applied to unitary traces encoded in specific data structures (with the help of expert knowledge), allows extracting interesting patterns that characterize frequent behaviors. Finally, we detail the achievements made within this thesis with the development of a platform of traces analysis in the form of a prototype.

La maîtrise du rendement d’un site de fabrication et l’identification rapide des causes de perte de qualité restent un défi quotidien pour les industriels, qui font face à une concurrence continue. Dans ce cadre, cette thèse a pour ambition de proposer une démarche d’analyse permettant l’identification rapide de l’origine d’un défaut, à travers l’exploitation d’un maximum des données disponibles grâce aux outils de contrôle qualité, tel que la FDC, la métrologie, les tests paramétriques PT, et le tri électriques EWS. Nous avons proposé une nouvelle méthode hybride de fouille de données, nommée CLARIF, qui combine trois méthodes de fouille de données à savoir, le clustering, les règles d’association et l’induction d’arbres de décision. Cette méthode se base sur la génération non supervisée d’un ensemble de modes de production potentiellement problématiques, qui sont caractérisés par des conditions particulières de production. Elle permet, donc, une analyse qui descend au niveau des paramètres de fonctionnement des équipements. L’originalité de la méthode consiste dans (1) une étape de prétraitement pour l’identification de motifs spatiaux à partir des données de contrôle, (2) la génération non supervisée de modes de production candidats pour expliquer le défaut. Nous optimisons la génération des règles d’association à travers la proposition de l’algorithme ARCI, qui est une adaptation du célèbre algorithme de fouille de règles d’association, APRIORI, afin de permettre d’intégrer les contraintes spécifiques à la problématique de CLARIF, et des indicateurs de qualité de filtrage des règles à identifier, à savoir la confiance, la contribution et la complexité. Finalement, nous avons défini un processus d’Extraction de Connaissances à partir des Données, ECD permettant de guider l’utilisateur dans l’application de CLARIF pour expliquer une perte de qualité locale ou globale. / Controlling the performance of a manufacturing site and the rapid identification of quality loss causes remain a daily challenge for manufacturers, who face continuing competition. In this context, this thesis aims to provide an analytical approach for the rapid identification of defect origins, by exploring data available thanks to different quality control systems, such FDC, metrology, parametric tests PT and the Electrical Wafer Sorting EWS. The proposed method, named CLARIF, combines three complementary data mining techniques namely clustering, association rules and decision trees induction. This method is based on unsupervised generation of a set of potentially problematic production modes, which are characterized by specific manufacturing conditions. Thus, we provide an analysis which descends to the level of equipment operating parameters. The originality of this method consists on (1) a pre-treatment step to identify spatial patterns from quality control data, (2) an unsupervised generation of manufacturing modes candidates to explain the quality loss case. We optimize the generation of association rules through the proposed ARCI algorithm, which is an adaptation of the famous association rules mining algorithm, APRIORI to integrate the constraints specific to our issue and filtering quality indicators, namely confidence, contribution and complexity, in order to identify the most interesting rules. Finally, we defined a Knowledge Discovery from Databases process, enabling to guide the user in applying CLARIF to explain both local and global quality loss problems.

Les deux dernières décennies ont été marquées par une augmentation significative des données collectées dans les systèmes d'informations. Cette masse de données contient des informations riches et peu exploitées. Cette réalité s’applique au secteur de la santé où l'informatisation est un enjeu pour l’amélioration de la qualité des soins. Les méthodes existantes dans les domaines de l'extraction de processus, de l'exploration de données et de la modélisation mathématique ne parviennent pas à gérer des données aussi hétérogènes et volumineuses que celles de la santé. Notre objectif est de développer une méthodologie complète pour transformer des données de santé brutes en modèles de simulation des parcours de soins cliniques. Nous introduisons d'abord un cadre mathématique dédié à la découverte de modèles décrivant les parcours de soin, en combinant optimisation combinatoire et Process Mining. Ensuite, nous enrichissons ce modèle par l’utilisation conjointe d’un algorithme d’alignement de séquences et de techniques classiques de Data Mining. Notre approche est capable de gérer des données bruitées et de grande taille. Enfin, nous proposons une procédure pour la conversion automatique d'un modèle descriptif des parcours de soins en un modèle de simulation dynamique. Après validation, le modèle obtenu est exécuté pour effectuer des analyses de sensibilité et évaluer de nouveaux scénarios. Un cas d’étude sur les maladies cardiovasculaires est présenté, avec l’utilisation de la base nationale des hospitalisations entre 2006 et 2015. La méthodologie présentée dans cette thèse est réutilisable dans d'autres aires thérapeutiques et sur d'autres sources de données de santé. / During the last two decades, the amount of data collected in Information Systems has drastically increased. This large amount of data is highly valuable. This reality applies to health-care where the computerization is still an ongoing process. Existing methods from the fields of process mining, data mining and mathematical modeling cannot handle large-sized and variable event logs. Our goal is to develop an extensive methodology to turn health data from event logs into simulation models of clinical pathways. We first introduce a mathematical framework to discover optimal process models. Our approach shows the benefits of combining combinatorial optimization and process mining techniques. Then, we enrich the discovered model with additional data from the log. An innovative combination of a sequence alignment algorithm and of classical data mining techniques is used to analyse path choices within long-term clinical pathways. The approach is suitable for noisy and large logs. Finally, we propose an automatic procedure to convert static models of clinical pathways into dynamic simulation models. The resulting models perform sensitivity analyses to quantify the impact of determinant factors on several key performance indicators related to care processes. They are also used to evaluate what-if scenarios. The presented methodology was proven to be highly reusable on various medical fields and on any source of event logs. Using the national French database of all the hospital events from 2006 to 2015, an extensive case study on cardiovascular diseases is presented to show the efficiency of the proposed framework.

Cette thèse concerne la fouille de données en sciences humaines. Cette branche récente de l'intelligence artificielle consiste en un ensemble de méthodes visant à extraire de la connaissance à partir de données stockées sur des supports informatiques. Parmi celles-ci, l'extraction de motifs et de règles d'association est une méthode de traitement des données qui permet de représenter de façon symbolique la structure des données, comme le font les méthodes statistiques classiques, mais qui, contrairement à celles-ci, reste opérationnelle en cas de données complexes, volumineuses. Toutefois ce modèle informatique des données, construit à partir de comptages de cooccurrences, n'est pas directement utilisable par les chercheurs en sciences humaines : il est essentiellement dédié aux données dichotomiques (vrai/faux), ses résultats directs, très morcelés, sont difficiles à interpréter, et sa validité peut paraître douteuse aux chercheurs habitués à la démarche statistique. Nous proposons des techniques que nous avons construites puis expérimentées sur des données réelles dans le but de réduire les difficultés d'utilisation que nous venons de décrire : 1) un test de randomisation à base d'échanges en cascade dans la matrice sujets x propriétés permet d'obtenir les liaisons statistiquement significatives entre deux propriétés, 2) une extension floue de la méthode d'extraction classique des motifs, qui produit des règles d'association floues généralisant les règles binaires et proches des règles floues définies par les chercheurs poursuivant les travaux de Zadeh, 3) MIDOVA, un algorithme extrayant les interactions n-aires entre variables - problème peu connu, peu abordé en informatique, et abordé avec de fortes limitations en statistiques - et 4) des méta-règles pour nettoyer le jeu de règles d'association de ses principales contradictions et redondances.

Ce mémoire porte sur mes travaux de recherche en traitement automatique des langues (TAL) et en fouille de données textuelles. Il présente comment ces travaux s'organisent autour de la problématique de l'accès à l'information dans les textes. Notre démarche s'appuie sur la prise en compte de l'aspect sémantique de la langue sous forme de modélisation linguistique et de ressources linguistiques pour le développement d'applications. La méthodologie de l'accès à l'information est donc ici vue comme un accès au sens à partir d'une modélisation linguistique relative à l'application visée plutôt qu'un accès aux formes de surface comme l'utilisent par exemple actuellement les méthodes prédominantes des moteurs de recherche. En retour, la formalisation du modèle linguistique et son expérimentation sur corpus visent à améliorer notre connaissance des phénomènes traités et permettre un retour qualitatif, c'est-à-dire explicatif, sur le modèle. L'intérêt pour les méthodes de fouille fondées sur les motifs et la volonté de les intégrer au TAL -- par exemple, pour acquérir automatiquement des ressources linguistiques et alimenter à moindre coût les systèmes de TAL -- procède de la même démarche. Une telle combinaison vise d'une part à repenser la manière dont les processus de TAL peuvent tirer bénéfice de méthodes de fouille spécifiquement adaptées au texte, et d'autre part à renforcer les processus de fouille, en fonction des spécificités de la donnée textuelle, par une prise en compte d'informations de nature linguistique visant notamment à sélectionner l'information la plus pertinente.

Détecter et suivre les objets principaux d’une vidéo est une étape nécessaire en vue d’en décrire le contenu pour, par exemple, permettre une indexation judicieuse des données multimédia par les moteurs de recherche. Les techniques de suivi d’objets actuelles souffrent de défauts majeurs. En effet, soit elles nécessitent que l’utilisateur désigne la cible a suivre, soit il est nécessaire d’utiliser un classifieur pré-entraîné à reconnaitre une classe spécifique d’objets, comme des humains ou des voitures. Puisque ces méthodes requièrent l’intervention de l’utilisateur ou une connaissance a priori du contenu traité, elles ne sont pas suffisamment génériques pour être appliquées aux vidéos amateurs telles qu’on peut en trouver sur YouTube. Pour résoudre ce problème, nous partons de l’hypothèse que, dans le cas de vidéos dont l’arrière-plan n’est pas fixe, celui-ci apparait moins souvent que les objets intéressants. De plus, dans une vidéo, la topologie des différents éléments visuels composant un objet est supposée consistante d’une image a l’autre. Nous représentons chaque image par un graphe plan modélisant sa topologie. Ensuite, nous recherchons des motifs apparaissant fréquemment dans la base de données de graphes plans ainsi créée pour représenter chaque vidéo. Cette approche nous permet de détecter et suivre les objets principaux d’une vidéo de manière non supervisée en nous basant uniquement sur la fréquence des motifs. Nos contributions sont donc réparties entre les domaines de la fouille de graphes et du suivi d’objets. Dans le premier domaine, notre première contribution est de présenter un algorithme de fouille de graphes plans efficace, appelé PLAGRAM. Cet algorithme exploite la planarité des graphes et une nouvelle stratégie d’extension des motifs. Nous introduisons ensuite des contraintes spatio-temporelles au processus de fouille afin d’exploiter le fait que, dans une vidéo, les objets se déplacent peu d’une image a l’autre. Ainsi, nous contraignons les occurrences d’un même motif a être proches dans l’espace et dans le temps en limitant le nombre d’images et la distance spatiale les séparant. Nous présentons deux nouveaux algorithmes, DYPLAGRAM qui utilise la contrainte temporelle pour limiter le nombre de motifs extraits, et DYPLAGRAM_ST qui extrait efficacement des motifs spatio-temporels fréquents depuis les bases de données représentant les vidéos. Dans le domaine du suivi d’objets, nos contributions consistent en deux approches utilisant les motifs spatio-temporels pour suivre les objets principaux dans les vidéos. La première est basée sur une recherche du chemin de poids minimum dans un graphe connectant les motifs spatio-temporels tandis que l’autre est basée sur une méthode de clustering permettant de regrouper les motifs pour suivre les objets plus longtemps. Nous présentons aussi deux applications industrielles de notre méthode / Detecting and following the main objects of a video is necessary to describe its content in order to, for example, allow for a relevant indexation of the multimedia content by the search engines. Current object tracking approaches either require the user to select the targets to follow, or rely on pre-trained classifiers to detect particular classes of objects such as pedestrians or car for example. Since those methods rely on user intervention or prior knowledge of the content to process, they cannot be applied automatically on amateur videos such as the ones found on YouTube. To solve this problem, we build upon the hypothesis that, in videos with a moving background, the main objects should appear more frequently than the background. Moreover, in a video, the topology of the visual elements composing an object is supposed consistent from one frame to another. We represent each image of the videos with plane graphs modeling their topology. Then, we search for substructures appearing frequently in the database of plane graphs thus created to represent each video. Our contributions cover both fields of graph mining and object tracking. In the first field, our first contribution is to present an efficient plane graph mining algorithm, named PLAGRAM. This algorithm exploits the planarity of the graphs and a new strategy to extend the patterns. The next contributions consist in the introduction of spatio-temporal constraints into the mining process to exploit the fact that, in a video, the motion of objects is small from on frame to another. Thus, we constrain the occurrences of a same pattern to be close in space and time by limiting the number of frames and the spatial distance separating them. We present two new algorithms, DYPLAGRAM which makes use of the temporal constraint to limit the number of extracted patterns, and DYPLAGRAM_ST which efficiently mines frequent spatio-temporal patterns from the datasets representing the videos. In the field of object tracking, our contributions consist in two approaches using the spatio-temporal patterns to track the main objects in videos. The first one is based on a search of the shortest path in a graph connecting the spatio-temporal patterns, while the second one uses a clustering approach to regroup them in order to follow the objects for a longer period of time. We also present two industrial applications of our method

Les jeux de données décrivant des objets par des propriétés Booléennes sont des relations binaires, c'est à dire des matrices 0/1. Dans une telle relation, un ensemble fermé est un sous-ensemble maximal d'objets partageant le même sous-ensemble maximal de propriétés. L'extraction de ces motifs, satisfaisant des contraintes de pertinences définies par l'utilisateur, a été étudiée en profondeur. Néanmoins, beaucoup de jeux de données sont des relations n-aires, c'est à dire des tenseurs 0/1. Réduire leur analyse à deux dimensions revient à en ignorer d'autres qui sont potentiellement intéressantes. Par ailleurs, la présence de bruit dans les jeux de données réelles conduit à la fragmentation des motifs à découvrir. On généralise facilement la définition d'un ensemble fermé aux relations de plus grande arité et à la tolérance au bruit. Au contraire, généraliser leur extraction est très difficile. Notre extracteur parcourt l'espace des motifs candidats d'une façon originale qui ne favorise aucune dimension. Cette recherche peut être guidée par une très grande classe de contraintes de pertinence que les motifs doivent satisfaire. En particulier, cette thèse étudie des contraintes spécifiques à la fouille de graphes dynamiques. Notre extracteur est plusieurs ordres de grandeurs plus efficace que les algorithmes existants, pourtant plus restreints dans leurs applications. Malgré ces résultats, une approche exhaustive ne peut souvent pas, en un temps raisonnable, lister des motifs tolérants beaucoup de bruit. Dans ce cas, compléter l'extraction avec une agglomération hiérarchique des motifs permet d'arriver à ses fins.

L'interprétation d'images satellitales dans un cadre spatiotemporel devient une voie d'investigation de plus en plus pertinente pour l'étude et l'interprétation des phénomènes dynamiques. Cependant, le volume de données images devient de plus en plus considérable ce qui rend la tâche d'analyse manuelle des images satellitales plus difficile. Ceci a motivé l'intérêt des recherches sur l'extraction automatique de connaissances appliquée à l'imagerie satellitale. Notre thèse s'inscrit dans ce contexte et vise à exploiter les connaissances extraites à partir des images satellitales pour prédire les changements spatiotemporels de l'occupation du sol. L'approche proposée consiste en trois phases : i) la première phase permet une modélisation spatiotemporelle des images satellitales, ii) la deuxième phase assure la prédiction de changements de l'occupation du sol et iii) la troisième phase consiste à interpréter les résultats obtenus. Notre approche intègre trois niveaux de gestion des imperfections : la gestion des imperfections liées aux données, la gestion des imperfections liées à la prédiction et finalement la gestion des imperfections liées aux résultats. Pour les imperfections liées aux données, nous avons procédé par une segmentation collaborative. Le but étant de réduire la perte d'information lors du passage du niveau pixel au niveau objet. Pour les imperfections liées à la prédiction, nous avons proposé un processus basé sur les arbres de décisions floues. Ceci permet de modéliser les imperfections liées à la prédiction de changements. Finalement, pour les imperfections liées aux résultats, nous avons utilisé les techniques de Raisonnement à Base des Cas et de fusion pour identifier et combiner les décisions pertinentes. L'expérimentation de l'approche proposée est scindée en deux étapes : une étape d'application et une étape d'évaluation. Les résultats d'évaluation ont montré la performance de notre approche mesurée en termes de taux d'erreur par rapport à des approches existantes.

L'extraction automatique de connaissances à partir des données peut être considérée comme la découverte d'informations enfouies dans de très grands volumes de données. Les approches Actuelles, pour évaluer la pertinence des informations extraites, se distinguent en deux catégories : les approches objectives qui mettent en oeuvre des mesures d'intérêt afin d'évaluer les propriétés statistiques des modèles extraits et les approches subjectives qui confrontent les modèles extraits à des connaissances exprimées sur le domaine et nécessitent généralement l'interrogation d'experts. Toutefois, le choix de modèles pertinents en regard de la connaissance métier d'un expert reste un problème ouvert et l'absence de formalisme dans l'expression des connaissances nuit à la mise au point de techniques automatiques de confrontation des modèles permettant d'exploiter toute la richesse sémantique des connaissances expertes. L'approche KEOPS que nous proposons dans ce mémoire, répond à cette problématique en proposant une méthodologie qui intègre les connaissances des experts d'un domaine tout au long du processus de fouille. Un système d'information dirigé par une ontologie (ODIS) joue un rôle central dans le système KEOPS en permettant d'organiser rationnellement non seulement la préparation des données mais aussi la sélection et l'interprétation des modèles générés. Une mesure d'intérêt est proposée afin de prendre en compte les centres d'intérêt et le niveau de connaissance des experts. Le choix des modèles les plus pertinents se base sur une évaluation à la fois objective pour évaluer la précision des motifs et subjective pour évaluer l'intérêt des modèles pour les experts du domaine. Enfin l'approche KEOPS facilite la définition de stratégies pour améliorer le processus de fouille de données dans le temps en fonction des résultats observés. Les différents apports de l'approche KEOPS favorisent l'automatisation du processus de fouille de données, et ainsi, une dynamique d'apprentissage peut être initiée pour obtenir un processus de fouille particulièrement bien adapté au domaine étudié. KEOPS a été mise en oeuvre dans le cadre de l'étude de la gestion des relations avec les allocataires au sein des Caisses d'Allocations Familiales. L'objectif de cette étude a été d'analyser la relation de service rendu aux allocataires afin de fournir aux décideurs des connaissances précises, pertinentes et utiles pour l'amélioration de ce service.