Avec la croissance importante du besoin d'analyser une grande masse de données structurées tels que les composés chimiques, les structures de protéines ou même les réseaux sociaux, la fouille de sous-graphes fréquents est devenue un défi réel en matière de fouille de données. Ceci est étroitement lié à leur nombre exponentiel ainsi qu'à la NP-complétude du problème d'isomorphisme d'un sous-graphe général. Face à cette complexité, et pour gérer cette taille importante de l'espace de recherche, les méthodes classiques de fouille de graphes ont exploré des heuristiques de recherche basées sur le support, le langage de description des exemples (limitation aux chemins, aux arbres, etc.) ou des hypothèses (recherche de sous-arborescence communes, de chemins communs, etc.). Dans le cadre de cette thèse, nous nous basons sur une méthode d'appariement de graphes issue du domaine de la programmation par contraintes, nommée AC-projection, qui a le mérite d'avoir une complexité polynomiale. Nous introduisons des approches de fouille de graphes permettant d'améliorer les approches existantes pour ce problème. En particulier, nous proposons deux algorithmes, FGMAC et AC-miner, permettant de rechercher les sous-graphes fréquents à partir d'une base de graphes. Ces deux algorithmes profitent, différemment, des propriétés fortes intéressantes de l'AC-projection. En effet, l'algorithme FGMAC adopte un parcours en largeur de l'espace de recherche et exploite l'approche par niveau introduite dans Apriori, tandis que l'algorithme AC-miner parcourt l'espace en profondeur par augmentation de motifs, assurant ainsi une meilleure mise à l'échelle pour les grands graphes. Ces deux approches permettent l'extraction d'un type particulier de graphes, il s'agit de celui des sous-graphes AC-réduits fréquents. Dans un premier temps, nous prouvons, théoriquement, que l'espace de recherche de ces sous-graphes est moins important que celui des sous-graphes fréquents à un isomorphisme près. Ensuite, nous menons une série d'expérimentations permettant de prouver que les algorithmes FGMAC et AC-miner sont plus efficients que ceux de l'état de l'art. Au même temps, nous prouvons que les sous-graphes AC-réduits fréquents, en dépit de leur nombre sensiblement réduit, ont le même pouvoir discriminant que les sous-graphes fréquents à un isomorphisme près. Cette étude est menée en se basant sur une évaluation expérimentale de la qualité des sous-graphes AC-réduits fréquents dans un processus de classification supervisée de graphes. / With the important growth of requirements to analyze large amount of structured data such as chemical compounds, proteins structures, social networks, to cite but a few, graph mining has become an attractive track and a real challenge in the data mining field. Because of the NP-Completeness of subgraph isomorphism test as well as the huge search space, frequent subgraph miners are exponential in runtime and/or memory use. In order to alleviate the complexity issue, existing subgraph miners have explored techniques based on the minimal support threshold, the description language of the examples (only supporting paths, trees, etc.) or hypothesis (search for shared trees or common paths, etc.). In this thesis, we are using a new projection operator, named AC-projection, which exhibits nice complexity properties as opposed to the graph isomorphism operator. This operator comes from the constraints programming field and has the advantage of a polynomial complexity. We propose two frequent subgraph mining algorithms based on the latter operator. The first one, named FGMAC, follows a breadth-first order to find frequent subgraphs and takes advantage of the well-known Apriori levelwise strategy. The second is a pattern-growth approach that follows a depth-first search space exploration strategy and uses powerful pruning techniques in order to considerably reduce this search space. These two approaches extract a set of particular subgraphs named AC-reduced frequent subgraphs. As a first step, we have studied the search space for discovering such frequent subgraphs and proved that this one is smaller than the search space of frequent isomorphic subgraphs. Then, we carried out experiments in order to prove that FGMAC and AC-miner are more efficient than the state-of-the-art algorithms. In the same time, we have studied the relevance of frequent AC-reduced subgraphs, which are much fewer than isomorphic ones, on classification and we conclude that we can achieve an important performance gain without or with non-significant loss of discovered pattern's quality.

The purpose of this work is to rethink the process of learning in human evolutionary systems. We take a sober look at how game theory, network theory, and chaos theory pertain specifically to the modeling, data, and training components of generalization in human systems. The value of our research is three-fold. First, our work is a direct approach to align machine learning generalization with core behavioral theories. We made our best effort to directly reconcile the axioms of these heretofore incompatible disciplines -- rather than moving from AI/ML towards the behavioral theories while building exclusively on AI/ML intuition. Second, this approach simplifies the learning process and makes it more intuitive for non-technical domain experts. We see increasing complexity in the models introduced in academic literature and, hence, increasing reliance on abstract hidden states learned by automatic feature engineering. The result is less understanding of how the models work and how they can be interpreted. However, these increasingly complex models are effective on the particular benchmark datasets they were designed for, but do not generalize. Our research highlights why these models are not generalizable and why behavioral theoretic intuition must have priority over the black box reliance on automatic feature engineering. Third, we introduce two novel methods that can be applied off-the-shelf: graph transformation for classification in human evolutionary systems (GT-CHES) and dynamic contrastive learning (DyCon). These models are most effective in mixed-motive human systems. While, GT-CHES is most suitable for tasks that involve event-based data, DyCon can be used on any temporal task.

La montée en puissance des écrans tactiles offre de nouvelles possibilités d'interactions gestuelles de plus en plus riches. De nos jours, les utilisateurs se contentent souvent de gestes mono-point ou multipoints simples pour exécuter des manipulations telles que la rotation, le déplacement ou la mise à l'échelle d'objets graphiques, la plupart du temps dans un contexte mono-utilisateur. Le travail décrit ici concerne l'utilisation avancée des gestes multipoints, comportant à la fois plus de commandes de raccourci (appelées commandes indirect es) et de commandes de manipulation (appelées commandes directes) dans un contexte d'utilisateurs multiples sur le même écran. Pour cela, nous analysons la forme des trajectoires composant le geste multipoints et les relations temporelles et spatiales entre ces trajectoires afin de caractériser ce geste. Nous proposons une modélisation par graphes et développons un système complet d'analyse et de reconnaissance. Pour résoudre le conflit entre la reconnaissance des gestes de manipulation et ceux de commande (directes versus indirectes), nous proposons une stratégie de reconnaissance précoce pour les gestes multipoints basée sur une option de rejet combinant plusieurs classifieurs pour reconnaître ces gestes au plus tôt. Pour valider nos approches, nous avons construit la base MTGSet composée de 7 938 gestes isolés multi points de 41 classes différentes et MUMTDB une base de gestes collectés dans un contexte réel d'interaction multiutilisateurs pour l'édition de diagrammes. Les résultats expérimentaux attestent que nos approches peuvent reconnaître les gestes multipoints dans ces différentes situations. / Due to the popularization of the touch screen devices, nowadays people are used to conduct the human-computer interactions with touch gestures. However, limited by current studies, users can use only simple multi-touch gestures to execute only simple manipulations such as rotation, translation, scaling, with most of time one user even if adapted devices are now available. The work reported here concerns the expanding usage of multi-touch gestures, that make them available at the same time for more shortcut commands (called indirect commands, as copy, past, ... ), more manipulation commands (called direct commands like zoom or rotation) and in the context of multiple users on the same screen. For this purpose, we analyze the shape of the gesture's motion trajectories and the temporal and spatial relations between trajectories in order to characterize a multi-touch gesture. We propose a graph modeling to characterize these motion features and develop a graph based analysis and recognition system. To resolve the conflict between interface manipulation and shortcut command inputs, we study and validate an early recognition strategy for multi-touch gesture. We built a reject option based multi-classifier early recognition system to recognize multi-touch gestures in early stage. To set-up, train and validate our systems, we built MTGSet, a multi-touch gesture dataset formed by 7938 gestures from 41 different classes collected in isolated contexts and MUMTDB a dataset of gestures collected in a real multi-user usage case of diagram drawing. The experimental results prove that our system can well recognize multi-touch gestures in these different situations.

No description available.

Cette thèse aborde le problème du manque de performance des outils exploitant des représentationsà base de graphes en reconnaissance des formes. Nous proposons de contribuer aux nouvellesméthodes proposant de tirer partie, à la fois, de la richesse des méthodes structurelles et de la rapidité des méthodes de reconnaissance de formes statistiques. Deux principales contributions sontprésentées dans ce manuscrit. La première correspond à la proposition d'une nouvelle méthode deprojection explicite de graphes procédant par analyse multi-facettes des graphes. Cette méthodeeffectue une caractérisation des graphes suivant différents niveaux qui correspondent, selon nous,aux point-clés des représentations à base de graphes. Il s'agit de capturer l'information portéepar un graphe au niveau global, au niveau structure et au niveau local ou élémentaire. Ces informationscapturées sont encapsulés dans un vecteur de caractéristiques numériques employantdes histogrammes flous. La méthode proposée utilise, de plus, un mécanisme d'apprentissage nonsupervisée pour adapter automatiquement ses paramètres en fonction de la base de graphes àtraiter sans nécessité de phase d'apprentissage préalable. La deuxième contribution correspondà la mise en place d'une architecture pour l'indexation de masses de graphes afin de permettre,par la suite, la recherche de sous-graphes présents dans cette base. Cette architecture utilise laméthode précédente de projection explicite de graphes appliquée sur toutes les cliques d'ordre 2pouvant être extraites des graphes présents dans la base à indexer afin de pouvoir les classifier.Cette classification permet de constituer l'index qui sert de base à la description des graphes etdonc à leur indexation en ne nécessitant aucune base d'apprentissage pré-étiquetées. La méthodeproposée est applicable à de nombreux domaines, apportant la souplesse d'un système de requêtepar l'exemple et la granularité des techniques d'extraction ciblée (focused retrieval). / This thesis addresses the problem of lack of efficient computational tools for graph based structural pattern recognition approaches and proposes to exploit computational strength of statistical pattern recognition. It has two fold contributions. The first contribution is a new method of explicit graph embedding. The proposed graph embedding method exploits multilevel analysis of graph for extracting graph level information, structural level information and elementary level information from graphs. It embeds this information into a numeric feature vector. The method employs fuzzy overlapping trapezoidal intervals for addressing the noise sensitivity of graph representations and for minimizing the information loss while mapping from continuous graph space to discrete vector space. The method has unsupervised learning abilities and is capable of automatically adapting its parameters to underlying graph dataset. The second contribution is a framework for automatic indexing of graph repositories for graph retrieval and subgraph spotting. This framework exploits explicit graph embedding for representing the cliques of order 2 by numeric feature vectors, together with classification and clustering tools for automatically indexing a graph repository. It does not require a labeled learning set and can be easily deployed to a range of application domains, offering ease of query by example (QBE) and granularity of focused retrieval.

Les travaux présentés dans ce mémoire de thèse abordent sous différents angles très intéressants, un sujet vaste et ambitieux : l’interprétation de plans cadastraux couleurs.Dans ce contexte, notre approche se trouve à la confluence de différentes thématiques de recherche telles que le traitement du signal et des images, la reconnaissance de formes, l’intelligence artificielle et l’ingénierie des connaissances. En effet, si ces domaines scientifiques diffèrent dans leurs fondements, ils sont complémentaires et leurs apports respectifs sont indispensables pour la conception d’un système d’interprétation. Le centre du travail est le traitement automatique de documents cadastraux du 19e siècle. La problématique est traitée dans le cadre d'un projet réunissant des historiens, des géomaticiens et des informaticiens. D'une part nous avons considéré le problème sous un angle systémique, s'intéressant à toutes les étapes de la chaîne de traitements mais aussi avec un souci évident de développer des méthodologies applicables dans d'autres contextes. Les documents cadastraux ont été l'objet de nombreuses études mais nous avons su faire preuve d'une originalité certaine, mettant l'accent sur l'interprétation des documents et basant notre étude sur des modèles à base de graphes. Des propositions de traitements appropriés et de méthodologies ont été formulées. Le souci de comblé le gap sémantique entre l’image et l’interprétation a reçu dans le cas des plans cadastraux étudiés une réponse. / This thesis tackles the problem of technical document interpretationapplied to ancient and colored cadastral maps. This subject is on the crossroadof different fields like signal or image processing, pattern recognition, artificial intelligence,man-machine interaction and knowledge engineering. Indeed, each of thesedifferent fields can contribute to build a reliable and efficient document interpretationdevice. This thesis points out the necessities and importance of dedicatedservices oriented to historical documents and a related project named ALPAGE.Subsequently, the main focus of this work: Content-Based Map Retrieval within anancient collection of color cadastral maps is introduced.