Les thèmes principaux de ce mémoire sont la parcimonie et la discrimination pour la modélisation de données complexes. Dans une première partie de ce mémoire, nous nous plaçons dans un contexte de modèle de mélanges gaussiens: nous introduisons une nouvelle famille de modèles probabilistes qui simultanément classent et trouvent un espace discriminant tel que cet espace discrimine au mieux les groupes. Une famille de 12 modèles latents discriminants (DLM) modèles est introduite et se base sur trois idées: tout d'abord, les données réelles vivent dans un sous-espace latent de dimension intrinsèque plus petite que celle de l'espace observé; deuxièmement, un sous-espace de K-1 dimensions est suffisant pour discriminer K groupes; enfin, l'espace observé et celui latent sont liés par une transformation linéaire. Une procédure d'estimation, appelée Fisher-EM, est proposée et améliore la plupart du temps les performances de clustering grâce à l'utilisation du sous-espace discriminant. Dans un second travail, nous nous sommes intéressés à la détermination du nombre de groupes en utilisant le cadre de la sériation. nous proposons d'intégrer de la parcimonie dans les données par l'intermédiaire d'une famille de matrices binaires. Ces dernière sont construites à partir d'une mesure de dissimilarité basée sur le nombre de voisins communs entre paires d'observations. En particulier, plus le nombre de voisins communs imposé est important, plus la matrice sera parcimonieuse, i.e. remplie de zéros, ce qui permet, à mesure que le seuil de parcimonie augmente, de retirer les valeurs extrêmes et les données bruitées. Cette collection de matrices parcimonieuses est ordonnée selon un algorithme de sériation de type forward, nommé PB-Clus, afin d'obtenir des représentations par blocs des matrices sériées. Ces deux méthodes ont été validées sur une application biologique basée sur la détection du cancer du col de l'utérus.

Cette thèse s'intéresse à l'apprentissage pour données massives. On considère en premier lieu, des trajectoires définies par des séquences de géolocalisations. Une nouvelle mesure de distance entre trajectoires (Symmetrized Segment-Path Distance) permet d'identifier par classification hiérarchique des groupes de trajectoires, modélisés ensuite par des mélanges gaussiens décrivant les déplacements par zones. Cette modélisation est utilisée de façon générique pour résoudre plusieurs types de problèmes liés aux trafic routier : prévision de la destination finale d'une trajectoire, temps d'arrivée à destination, prochaine zone de localisation. Les exemples analysés montrent que le modèle proposé s'applique à des environnements routiers différents et, qu'une fois appris, il s'applique à des trajectoires aux propriétés spatiales et temporelles différentes. En deuxième lieu, les environnements technologiques d'apprentissage pour données massives sont comparés sur des cas d'usage industriels. / This thesis focuses on machine learning techniques for application to big data. We first consider trajectories defined as sequences of geolocalized data. A hierarchical clustering is then applied on a new distance between trajectories (Symmetrized Segment-Path Distance) producing groups of trajectories which are then modeled with Gaussian mixture in order to describe individual movements. This modeling can be used in a generic way in order to resolve the following problems for road traffic : final destination, trip time or next location predictions. These examples show that our model can be applied to different traffic environments and that, once learned, can be applied to trajectories whose spatial and temporal characteristics are different. We also produce comparisons between different technologies which enable the application of machine learning methods on massive volumes of data.

La direction de recherche que nous abordons dans la thèse est l'application des modèles dynamiques d'apprentissage automatique pour résoudre les problèmes de classification supervisée et non supervisée. Les problèmes particuliers que nous avons décidé d'aborder dans la thèse sont la reconnaissance des piétons (un problème de classification supervisée) et le groupement des données d'expression génétique (un problème de classification non supervisée). Les problèmes abordés sont représentatifs pour les deux principaux types de classification et sont très difficiles, ayant une grande importance dans la vie réelle. La première direction de recherche que nous abordons dans le domaine de la classification non supervisée dynamique est le problème de la classification dynamique des données d'expression génétique. L'expression génétique représente le processus par lequel l'information d'un gène est convertie en produits de gènes fonctionnels : des protéines ou des ARN ayant différents rôles dans la vie d'une cellule. La technologie des micro-réseaux moderne est aujourd'hui utilisée pour détecter expérimentalement les niveaux d'expression de milliers de gènes, dans des conditions différentes et au fil du temps. Une fois que les données d'expression génétique ont été recueillies, l'étape suivante consiste à analyser et à extraire des informations biologiques utiles. L'un des algorithmes les plus populaires traitant de l'analyse des données d'expression génétique est le groupement, qui consiste à diviser un certain ensemble en groupes, où les composants de chaque groupe sont semblables les uns aux autres données. Dans le cas des ensembles de données d'expression génique, chaque gène est représenté par ses valeurs d'expression (caractéristiques), à des points distincts dans le temps, dans les conditions contrôlées. Le processus de regroupement des gènes est à la base des études génomiques qui visent à analyser les fonctions des gènes car il est supposé que les gènes qui sont similaires dans leurs niveaux d'expression sont également relativement similaires en termes de fonction biologique. Le problème que nous abordons dans le sens de la recherche de classification non supervisée dynamique est le regroupement dynamique des données d'expression génique. Dans notre cas, la dynamique à long terme indique que l'ensemble de données ne sont pas statiques, mais elle est sujette à changement. Pourtant, par opposition aux approches progressives de la littérature, où l'ensemble de données est enrichie avec de nouveaux gènes (instances) au cours du processus de regroupement, nos approches abordent les cas lorsque de nouvelles fonctionnalités (niveaux d'expression pour de nouveaux points dans le temps) sont ajoutés à la gènes déjà existants dans l'ensemble de données. À notre connaissance, il n'y a pas d'approches dans la littérature qui traitent le problème de la classification dynamique des données d'expression génétique, définis comme ci-dessus. Dans ce contexte, nous avons introduit trois algorithmes de groupement dynamiques que sont capables de gérer de nouveaux niveaux d'expression génique collectés, en partant d'une partition obtenue précédente, sans la nécessité de ré-exécuter l'algorithme à partir de zéro. L'évaluation expérimentale montre que notre méthode est plus rapide et plus précis que l'application de l'algorithme de classification à partir de zéro sur la fonctionnalité étendue ensemble de données... / The research direction we are focusing on in the thesis is applying dynamic machine learning models to salve supervised and unsupervised classification problems. We are living in a dynamic environment, where data is continuously changing and the need to obtain a fast and accurate solution to our problems has become a real necessity. The particular problems that we have decided te approach in the thesis are pedestrian recognition (a supervised classification problem) and clustering of gene expression data (an unsupervised classification. problem). The approached problems are representative for the two main types of classification and are very challenging, having a great importance in real life.The first research direction that we approach in the field of dynamic unsupervised classification is the problem of dynamic clustering of gene expression data. Gene expression represents the process by which the information from a gene is converted into functional gene products: proteins or RNA having different roles in the life of a cell. Modern microarray technology is nowadays used to experimentally detect the levels of expressions of thousand of genes, across different conditions and over time. Once the gene expression data has been gathered, the next step is to analyze it and extract useful biological information. One of the most popular algorithms dealing with the analysis of gene expression data is clustering, which involves partitioning a certain data set in groups, where the components of each group are similar to each other. In the case of gene expression data sets, each gene is represented by its expression values (features), at distinct points in time, under the monitored conditions. The process of gene clustering is at the foundation of genomic studies that aim to analyze the functions of genes because it is assumed that genes that are similar in their expression levels are also relatively similar in terms of biological function.The problem that we address within the dynamic unsupervised classification research direction is the dynamic clustering of gene expression data. In our case, the term dynamic indicates that the data set is not static, but it is subject to change. Still, as opposed to the incremental approaches from the literature, where the data set is enriched with new genes (instances) during the clustering process, our approaches tackle the cases when new features (expression levels for new points in time) are added to the genes already existing in the data set. To our best knowledge, there are no approaches in the literature that deal with the problem of dynamic clustering of gene expression data, defined as above. In this context we introduced three dynamic clustering algorithms which are able to handle new collected gene expression levels, by starting from a previous obtained partition, without the need to re-run the algorithm from scratch. Experimental evaluation shows that our method is faster and more accurate than applying the clustering algorithm from scratch on the feature extended data set...

Au vu des changements globaux actuels engendrés en grande partie par l'être humain, il devient nécessaire de comprendre les moteurs de la stabilité des communautés d'êtres vivants. La synchronie des séries temporelles d'abondances fait partie des mécanismes les plus importants. Cette thèse propose trois angles différents permettant de répondre à différentes questions en lien avec la synchronie interspécifique ou spatiale. Les travaux présentés trouvent des applications en dehors du cadre écologique. Un premier chapitre est consacré à l'estimation du rang effectif de matrices à valeurs dans ℝ ou ℂ. Nous apportons ainsi des outils permettant de mesurer le taux de synchronisation d'une matrice d'observations. Dans le deuxième chapitre, nous nous basons sur les travaux existants sur le problème de détection de ruptures sur les chaînes afin de proposer plusieurs algorithmes permettant d'adapter ce problème au cas des arbres. Les méthodes présentées peuvent être utilisées sur la plupart des données nécessitant d'être représentées sous la forme d'un arbre. Afin d'étudier les liens entre la synchronie interspécifique et les tendances à long termes ou les traits d'espèces de papillons, nous proposons dans le dernier chapitre d'adapter des méthodes de clustering et d'apprentissage supervisé comme les Random Forest ou les Réseaux de Neurones artificiels à des données écologiques. / In the view of actual global changes widely caused by human activities, it becomes urgent to understand the drivers of communities' stability. Synchrony between time series of abundances is one of the most important mechanisms. This thesis offers three different angles in order to answer different questions linked to interspecific and spatial synchrony. The works presented find applications beyond the ecological frame. A first chapter is dedicated to the estimation of effective rank of matrices in ℝ or ℂ. We offer tools allowing to measure the synchronisation rate of observations matrices. In the second chapter, we base on the existing work on change-points detection problem on chains in order to offer algorithms which detects change-points on trees. The methods can be used with most data that have to be represented as a tree. In order to study the link between interspecific synchrony and long term tendencies or traits of butterflies species, we offer in the last chapter adaptation of clustering and supervised machine learning methods, such as Random Forest or Artificial Neural Networks to ecological data.

Le problème de la classification non supervisée (clustering) a été largement étudié dans le contexte de l'analyse de données, où la structure naturelle des données est dévoilée en groupant des objets similaires tout en séparant ceux qui ne le sont pas. L'Aide Multicritère à la Décision (AMCD) modélise les préférences de décideurs et les aide à choisir une solution appropriée parmi un ensemble d'alternatives. Dans ce contexte, les problématiques du choix, du tri et du rangement ont été largement étudiés, alors que celle du clustering l'a été bien moins. De plus, la plupart de ces approches de résolution en AMCD utilisent des mesures de similarité et n'exploitent pas l'information préférentielle supplémentaire qui est disponible. Dans cette thèse nous étudions ce problème du clustering en AMCD en faisant d'abord un parallèle entre l'analyse de données et l'AMCD pour ensuite proposer le problème de la classification non supervisée en AMCD. Différents modèles sont alors proposés pour résoudre ce problème, ainsi que des algorithmes de résolution, qui sont validés sur un grand nombre de problèmes générés artificiellement. Pour terminer, nous envisageons différentes applications via l'utilisation de différentes mesures descriptives des classes, ainsi que l'extension des algorithmes à des volumes de données importants. Une application est résolue à la fin de la thèse pour illustrer l'intérêt des outils proposés.

Les méthodes d'analyse de données et d'apprentissage ont connu un développement très important ces dernières années. En effet, après les réseaux de neurones, les machines à noyaux (années 1990), les années 2000 ont vu l'apparition de méthodes spectrales qui ont fourni un cadre mathématique unifié pour développer des méthodes de classification originales. Parmi celles-ci ont peut citer la méthode LLE pour la réduction de dimension non linéaire et la méthode LDA pour la discrimination de classes. Une nouvelle méthode de classification est proposée dans cette thèse, méthode issue d'une combinaison des méthodes LLE et LDA. Cette méthode a donné des résultats intéressants sur des ensembles de données synthétiques. Elle permet une réduction de dimension non-linéaire suivie d'une discrimination efficace. Ensuite nous avons montré que cette méthode pouvait être étendue à l'apprentissage semi-supervisé. Les propriétés de réduction de dimension et de discrimination de cette nouvelle méthode, ainsi que la propriété de parcimonie inhérente à la méthode LLE nous ont permis de l'appliquer à la segmentation d'images couleur avec succès. La propriété d'apprentissage semi-supervisé nous a enfin permis de segmenter des images bruitées avec de bonnes performances. Ces résultats doivent être confortés mais nous pouvons d'ores et déjà dégager des perspectives de poursuite de travaux intéressantes. / Data analysis and learning methods have known a huge development during these last years. Indeed, after neural networks, kernel methods in the 90', spectral methods appeared in the years 2000. Spectral methods provide an unified mathematical framework to expand new original classification methods. Among these new techniques, two methods can be highlighted : LLE for non-linear dimension reduction and LDA as discriminating classification method. In this thesis document a new classification technique is proposed combining LLE and LDA methods. This new method makes it possible to provide efficient non-linear dimension reduction and discrimination. Then an extension of the method to semi-supervised learning is proposed. Good properties of dimension reduction and discrimination associated with the sparsity property of the LLE technique make it possible to apply our method to color images segmentation with success. Semi-supervised version of our method leads to efficient segmentation of noisy color images. These results have to be extended and compared with other state-of-the-art methods. Nevertheless interesting perspectives of this work are proposed in conclusion for future developments.

Les travaux effectués dans le cadre de cette thèse portent sur l'identification automatique de visages dans des bases de données d'images numériques. L'objectif est de simplifier le déroulement de l'identification biométrique qui consiste à la recherche de l'identité requête parmi l'ensemble des individus de la base de données préenregistrée, appelée aussi galerie. En effet, le schéma d'identification classique est complexe et très coûteux notamment dans le cas de grandes bases de données biométriques. Le processus original que nous proposons ici a pour objectif de réduire la complexité et d'améliorer les performances en terme de temps de calcul et de taux d'identification. Dans ce cadre biométrique, nous avons proposé une étape de classification non supervisée ou clustering des visages pour partitionner la base d'images en plusieurs sous ensembles cohérents et bien discriminés. Pour ce faire, l'algorithme de clustering vise à extraire, pour chaque visage, un ensemble de descripteurs, appelé signature, qui lui soit spécifique. Trois techniques de représentation faciales ont été développées dans le but d'extraire des informations différentes et complémentaires décrivant le visage humain : deux méthodes factorielles d'analyse multidimensionnelle et de projection des données (méthodes dites « Eigenfaces » et « Fisherfaces ») ainsi qu'une méthode d'extraction des moments géométriques de Zernike. Sur la base des différentes classes de signatures extraites pour chaque visage plusieurs méthodes de clustering sont mises en compétition afin de dégager la classification optimale qui conduit à une meilleure réduction de la galerie. Les méthodes retenues sont, soit de type « centres mobiles » telles que les K-moyennes et les centres mobiles de Forgy, ou de type « agglomérative » telle que la méthode de BIRCH. Sur la base de la dépendance des partitions générées, ces différentes stratégies classificatoires sont ensuite combinées suivant une architecture parallèle de manière à optimiser la réduction de l'espace de recherche à un sous ensemble de la base de données. Les clusters retenus in fine étant ceux pour lesquels la probabilité d'appartenance de l'identité requête est quasi certaine.

Cette thèse traite de la reconnaissance des formes dans les images numériques. Une représentation appropriée des formes est déduite de l'analyse des perturbations qui n'affectent pas la reconnaissance : changement de contraste, occlusion partielle, bruit, perspective. Les atomes de cette représentation, appelés "éléments de forme", fournissent des descriptions semi-locales des formes. L'appariement de ces éléments permet de reconnaitre des formes partielles. Les formes globales sont alors définies comme des groupes de formes partielles présentant une cohérence dans leur disposition spatiale. L'aspect fondamental de ce travail est la mise en place de seuils non-supervisés, à tous les niveaux de décision du processus de reconnaissance. Nous proposons des règles de décision pour la en correcpondance de formes partielles ainsi que pour la détection de formes globales. Le cadre proposé est basé sur une méthodologie générale de la détection dans laquelle un événement est significatif s'il n'est pas susceptible d'arriver par hasard.

Les puces tiling arrays sont des puces à haute densité permettant l'exploration des génomes à grande échelle. Elles sont impliquées dans l'étude de l'expression des gènes et de la détection de nouveaux transcrits grâce aux expériences de transcriptome, ainsi que dans l'étude des mécanismes de régulation de l'expression des gènes grâce aux expériences de ChIP-chip. Dans l'objectif d'analyser des données de ChIP-chip et de transcriptome, nous proposons une modélisation fondée sur les modèles à variables latentes, en particulier les modèles de Markov cachés, qui sont des méthodes usuelles de classification non-supervisée. Les caractéristiques biologiques du signal issu des puces tiling arrays telles que la dépendance spatiale des observations le long du génome et l'annotation structurale sont intégrées dans la modélisation. D'autre part, les modèles sont adaptés en fonction de la question biologique et une modélisation est proposée pour chaque type d'expériences. Nous proposons un mélange de régressions pour la comparaison de deux échantillons dont l'un peut être considéré comme un échantillon de référence (ChIP-chip), ainsi qu'un modèle gaussien bidimensionnel avec des contraintes sur la matrice de variance lorsque les deux échantillons jouent des rôles symétriques (transcriptome). Enfin, une modélisation semi-paramétrique autorisant des distributions plus flexibles pour la loi d'émission est envisagée. Dans un objectif de classification, nous proposons un contrôle de faux-positifs dans le cas d'une classification à deux groupes et pour des observations indépendantes. Puis, nous nous intéressons à la classification d'un ensemble d'observations constituant une région d'intérêt, telle que les gènes. Les différents modèles sont illustrés sur des jeux de données réelles de ChIP-chip et de transcriptome issus d'une puce NimbleGen couvrant le génome entier d'Arabidopsis thaliana.

La classification non supervisée, souvent appelée par le terme anglais de clustering, est une tâche importante en Fouille de Données. Depuis une dizaine d'années, la classification non supervisée a été étendue pour intégrer des contraintes utilisateur permettant de modéliser des connaissances préalables dans le processus de clustering. Différents types de contraintes utilisateur peuvent être considérés, des contraintes pouvant porter soit sur les clusters, soit sur les instances. Dans cette thèse, nous étudions le cadre de la Programmation par Contraintes (PPC) pour modéliser les tâches de clustering sous contraintes utilisateur. Utiliser la PPC a deux avantages principaux : la déclarativité, qui permet d'intégrer aisément des contraintes utilisateur et la capacité de trouver une solution optimale qui satisfait toutes les contraintes (s'il en existe). Nous proposons deux modèles basés sur la PPC pour le clustering sous contraintes utilisateur. Les modèles sont généraux et flexibles, ils permettent d'intégrer des contraintes d'instances must-link et cannot-link et différents types de contraintes sur les clusters. Ils offrent également à l'utilisateur le choix entre différents critères d'optimisation. Afin d'améliorer l'efficacité, divers aspects sont étudiés. Les expérimentations sur des bases de données classiques et variées montrent qu'ils sont compétitifs par rapport aux approches exactes existantes. Nous montrons que nos modèles peuvent être intégrés dans une procédure plus générale et nous l'illustrons par la recherche de la frontière de Pareto dans un problème de clustering bi-critère sous contraintes utilisateur. / Cluster analysis is an important task in Data Mining with hundreds of different approaches in the literature. Since the last decade, the cluster analysis has been extended to constrained clustering, also called semi-supervised clustering, so as to integrate previous knowledge on data to clustering algorithms. In this dissertation, we explore Constraint Programming (CP) for solving the task of constrained clustering. The main principles in CP are: (1) users specify declaratively the problem in a Constraint Satisfaction Problem; (2) solvers search for solutions by constraint propagation and search. Relying on CP has two main advantages: the declarativity, which enables to easily add new constraints and the ability to find an optimal solution satisfying all the constraints (when there exists one). We propose two models based on CP to address constrained clustering tasks. The models are flexible and general and supports instance-level constraints and different cluster-level constraints. It also allows the users to choose among different optimization criteria. In order to improve the efficiency, different aspects have been studied in the dissertation. Experiments on various classical datasets show that our models are competitive with other exact approaches. We show that our models can easily be embedded in a more general process and we illustrate this on the problem of finding the Pareto front of a bi-criterion optimization process.