La classification multi-label est une extension de la classification traditionnelle dans laquelle les classes ne sont pas mutuellement exclusives, chaque individu pouvant appartenir à plusieurs classes simultanément. Ce type de classification est requis par un grand nombre d’applications actuelles telles que la classification d’images et l’annotation de vidéos. Le principal objectif de cette thèse est la proposition de nouvelles méthodes pour répondre au problème de classification multi-label. La première partie de cette thèse s’intéresse au problème d’apprentissage multi-label dans le cadre des fonctions de croyance. Nous développons une méthode capable de tenir compte des corrélations entre les différentes classes et de classer les individus en utilisant le formalisme de représentation de l’incertitude pour les variables multi-valuées. La deuxième partie aborde le problème de l’édition des bases d’apprentissage pour la classification multi-label. Nous proposons un algorithme basé sur l’approche des k-plus proches voisins qui permet de détecter les exemples erronés dans l’ensemble d’apprentissage. Des expérimentations menées sur des jeux de données synthétiques et réelles montrent l’intérêt des approches étudiées. / Multi-label classification is an extension of traditional single-label classification, where classes are not mutually exclusive, and each example can be assigned by several classes simultaneously . It is encountered in various modern applications such as scene classification and video annotation. the main objective of this thesis is the development of new techniques to adress the problem of multi-label classification that achieves promising classification performance. the first part of this manuscript studies the problem of multi-label classification in the context of the theory of belief functions. We propose a multi-label learning method that is able to take into account relationships between labels ant to classify new instances using the formalism of representation of uncertainty for set-valued variables. The second part deals withe the problem of prototype selection in the framework of multi-label learning. We propose an editing algorithm based on the k-nearest neighbor rule in order to purify training dataset and improve the performances of multi-label classification algorithms. Experimental results on synthetic and real-world datasets show the effectiveness of our approaches.

Cette thèse s'inscrit dans le cadre de la statistique non paramétrique et porte sur la classification et la discrimination en grande dimension, et plus particulièrement sur la sélection de variables. Une première partie traite de la sélection de variables à travers CART, dans un cadre de régression et de classification binaire. La procédure exhaustive développée s'appuie sur le principe de la sélection de modèle qui permet d'obtenir des inégalités ``oracle'' et de réaliser la sélection de variables par contraste pénalisé. Une seconde partie est motivée par un problème industriel. Il s'agit de déterminer parmi les signaux temporels, mesurés au cours d'essais, ceux capables d'expliquer le ressenti de confort du conducteur, puis d'identifier les pages temporelles responsables de cette pertinence. La démarche adoptée s'articule autour du prétraitement des signaux, de la réduction de la dimension par projection dans une base d'ondelettes commune, et de la sélection de variables en mêlant CART et une stratégie pas à pas. Une dernière partie aborde le thème de la classification de données fonctionnelles au moyen des k-plus proches voisins. La procédure consiste à appliquer les k-plus proches voisins sur les coordonnées de la projection des données dans un espace fini dimensionnel. Cette procédure implique de déterminer simultanément la dimension de l'espace de projection et le nombre de voisins. La version usuelle des k-plus proches voisins et une version légèrement pénalisée sont considérées théoriquement. Un travail sur données réelles et simulées semble montrer qu'un faible terme de pénalité stabilise la sélection en conservant de bonnes performances.

L'indexation et la recherche efficiente de données complexes constitue un besoin croissant face à la taille et à la variété des bases de données actuelles. Nous proposons une structure d'index arborescent basée sur un partitionnement d'un espace métrique à base de boules et d'hyper-plans. Les performances de cet index sont évaluées expérimentalement sur des collections de complexités intrinsèques différentes. La parallélisation de l'algorithme de recherche des k plus proches voisins est également effectuée afin d'encore améliorer les performances.

Mesures de similarité statistiques et estimateurs par k plus proches voisins : une association pour gérer des descripteurs de haute dimension en traitement d'images et de vidéos

L'objectif de cette Thèse est d'apporter une contribution au problème de l'apprentissage statistique, notamment en développant des méthodes pour prendre en compte des données fonctionnelles. Dans la première partie, nous développons une approche de type plus proches voisins pour la régression fonctionnelle. Dans la deuxième, nous étudions les propriétés de la méthode de quantification dans des espaces de dimension infinie. Nous appliquons ensuite cette méthode pour réaliser une étude comportementale de bancs d'anchois. Enfin, la dernière partie est dédiée au problème de l'estimation des ensembles de niveaux de la fonction de régression dans un cadre multivarié.

Les performances des algorithmes d'apprentissage automatique dépendent de la métrique utilisée pour comparer deux objets, et beaucoup de travaux ont montré qu'il était préférable d'apprendre une métrique à partir des données plutôt que se reposer sur une métrique simple fondée sur la matrice identité. Ces résultats ont fourni la base au domaine maintenant qualifié d'apprentissage de métrique. Toutefois, dans ce domaine, la très grande majorité des développements concerne l'apprentissage de distances. Toutefois, dans certaines situations, il est préférable d'utiliser des similarités (par exemple le cosinus) que des distances. Il est donc important, dans ces situations, d'apprendre correctement les métriques à la base des mesures de similarité. Il n'existe pas à notre connaissance de travaux complets sur le sujet, et c'est une des motivations de cette thèse. Dans le cas des systèmes de filtrage d'information où le but est d'affecter un flot de documents à un ou plusieurs thèmes prédéfinis et où peu d'information de supervision est disponible, des seuils peuvent être appris pour améliorer les mesures de similarité standard telles que le cosinus. L'apprentissage de tels seuils représente le premier pas vers un apprentissage complet des mesures de similarité. Nous avons utilisé cette stratégie au cours des campagnes CLEF INFILE 2008 et 2009, en proposant des versions en ligne et batch de nos algorithmes. Cependant, dans le cas où l'on dispose de suffisamment d'information de supervision, comme en catégorisation, il est préférable d'apprendre des métriques complètes, et pas seulement des seuils. Nous avons développé plusieurs algorithmes qui visent à ce but dans le cadre de la catégorisation à base de k plus proches voisins. Nous avons tout d'abord développé un algorithme, SiLA, qui permet d'apprendre des similarités non contraintes (c'est-à-dire que la mesure peut être symétrique ou non). SiLA est une extension du perceptron par vote et permet d'apprendre des similarités qui généralisent le cosinus, ou les coefficients de Dice ou de Jaccard. Nous avons ensuite comparé SiLA avec RELIEF, un algorithme standard de re-pondération d'attributs, dont le but n'est pas sans lien avec l'apprentissage de métrique. En effet, il a récemment été suggéré par Sun et Wu que RELIEF pouvait être considéré comme un algorithme d'apprentissage de métrique avec pour fonction objectif une approximation de la fonction de perte 0-1. Nous montrons ici que cette approximation est relativement mauvaise et peut être avantageusement remplacée par une autre, qui conduit à un algorithme dont les performances sont meilleurs. Nous nous sommes enfin intéressés à une extension directe du cosinus, extension définie comme la forme normalisée d'un produit scalaire dans un espace projeté. Ce travail a donné lieu à l'algorithme gCosLA. Nous avons testé tous nos algorithmes sur plusieurs bases de données. Un test statistique, le s-test, est utilisé pour déterminer si les différences entre résultats sont significatives ou non. gCosLA est l'algorithme qui a fourni les meilleurs résultats. De plus, SiLA et gCosLA se comparent avantageusement à plusieurs algorithmes standard, ce qui illustre leur bien fondé.

Cette thèse s'intéresse aux systèmes de recherche d'images par le contenu, où le but est de rechercher les images les plus similaires à une image requête fournie en exemple. Pour cela, il est d'abord nécessaire de décrire les images stockées dans la base. L'objectif est de traduire la similarité visuelle entre images en une simple notion de proximité spatiale entre descripteurs. Ainsi, pour retrouver les images similaires à l'image requête, il suffit de retrouver les descripteurs les plus proches du descripteur de l'image requête. Ce mode de recherche, appelé recherche de plus proches voisins, est cependant extrêmement coûteux même lorsque les techniques s'indexation multidimensionnelles sont utilisées. Les performances de celles-ci se dégradent exponentiellement lorsque la dimension des descripteurs augmente (phénomène de la malédiction de la dimension). Il s'avère toutefois que l'on peut fortement réduire le coût de ces recherches en effectuant des recherches approximatives. Le principe est alors de négocier une réduction du temps de réponse contre l'introduction d'imprécisions durant la recherche. Ce travail reprend ce principe et propose une nouvelle méthode de recherche approximative de plus proches voisins qui permet un contrôle fin et intuitif de la précision de la recherche. Ce contrôle s'exprime au travers d'un seul paramètre qui indique la probabilité maximale de ne pas trouver un des plus proches voisins recherchés. Dans le but d'évaluer rigoureusement ses performances dans le cadre d'un système réel, la méthode proposée a été ensuite intégrée dans un système de recherche d'images pour la détection de copies. Les expérimentations effectuées montrent que la méthode proposée est efficace, fiable et son imprécision n'a qu'un impact mineur sur la qualité des résultats finaux.

Récemment, la localisation statique et dynamique d'un objet ou d'une personne est devenue l'un des plus importantes fonctionnalités d'un système de communication, du fait de ses multiples applications. En effet, connaître la position d'un terminal mobile (MT), en milieu extérieur ou intérieur, est généralement d'une importance majeure pour des applications fournissant des services basés sur la localisation. Ce développement des systèmes de localisation est dû au faible coût des infrastructures de réseau sans fil en milieu intérieur (WLAN). Les techniques permettant de localiser des MTs diffèrent selon les paramètres extraits des signaux radiofréquences émis entre des stations de base (BSs) et des MTs. Les conditions idéales pour effectuer des mesures sont des environnements dépourvus de tout obstacle, permettant des émissions directes entre BS et MT. Ce n'est pas le cas en milieu intérieur, du fait de la présence continuelle d'obstacles dans l'espace, qui dispersent les rayonnements. Les mesures prises dans ces conditions (NLOS, pour Non Line of Sight) sont imprévisibles et diffèrent de celles prises en condition LOS. Afin de réduire les erreurs de mesure, différentes techniques peuvent être utilisées, comme la mitigation, l'approximation, la correction à priori, ou le filtrage. En effet, l'application de systèmes de suivi (TSs) constitue une base substantielle pour la navigation individuelle, les réseaux sociaux, la gestion du trafic, la gestion des ressources mobiles, etc. Différentes techniques sont appliquées pour construire des TSs en milieu intérieur, où le signal est bruité, faible voire inexistant. Bien que les systèmes de localisation globaux (GPS) et les travaux qui en découlent fonctionnent bien hors des bâtiments et dans des canyons urbains, le suivi d'utilisateurs en milieu intérieur est bien plus problématique. De ce fait, le problème de prédiction reste un obstacle essentiel à la construction de TSs fiable dans de tels environnements. Une étape de prédiction est inévitable, en particulier, dans le cas où l'on manque d'informations. De multiples approches ont été proposées dans la littérature, la plupart étant basées sur un filtre linéaire (LF), un filtre de Kalman (KF) et ses variantes, ou sur un filtre particulaire (PF). Les filtres de prédiction sont souvent utilisés dans des problèmes d'estimation et l'application de la dérivation non entière peut limiter l'impact de la perte de performances. Ce travail présente une nouvelle approche pour la localisation intérieure par WLAN utilisant un groupement des coordonnées. Ensuite, une étude comparative des techniques déterministes et des techniques d'apprentissage pour la localisation intérieure est présentée. Enfin, une nouvelle approche souple pour les systèmes de suivi en milieu intérieur, par application de la dérivation non entière, est présentée

La théorie des processus empiriques joue un rôle central en statistique, puisqu'elle concerne l'ensemble des résultats limites généraux se rapportant aux échantillons aléatoires. En particulier, des lois uniformes du logarithme ont permis d'aborder de manière systématique la convergence en norme sup des estimateurs à noyau. Dans cette thèse, nous obtenons premièrement des lois fonctionnelles uniformes du logarithme pour les incréments du processus des quantiles normé, qui permettent d'établir des propriétés nouvelles des estimateurs basés sur les k-plus proches voisins. Le même type de résultat est ensuite obtenu pour les incréments du processus empirique de Kaplan-Meier, conduisant naturellement à des lois du logarithme uniformes pour des estimateurs de la densité et du taux de mortalité en présence de censure à droite. Dans le cas de la régression multivariée, des lois analogues sont obtenues pour des estimateurs à noyau, notamment dans le cas censuré. Enfin, nous développons un estimateur non paramétrique de la régression sous l'hypothèse du modèle additif dans le cas de censure à droite, permettant de se défaire du fléau de la dimension. Cet estimateur repose essentiellement sur la méthode d'intégration marginale.

La technique des K-plus proches voisins (K-Nearest Neighbors (KNN) en Anglais) est une méthode efficace pour trouver des données similaires au sein d'un grand ensemble de données. Au fil des années, un grand nombre d'applications ont utilisé les capacités du KNN pour découvrir des similitudes dans des jeux de données de divers domaines tels que les affaires, la médecine, la musique, ou l'informatique. Bien que des années de recherche aient apporté plusieurs approches de cet algorithme, sa mise en œuvre reste un défi, en particulier aujourd'hui alors que les quantités de données croissent à des vitesses inimaginables. Dans ce contexte, l'exécution du KNN sur de grands ensembles pose deux problèmes majeurs: d'énormes empreintes mémoire et de très longs temps d'exécution. En raison de ces coût élevés en termes de ressources de calcul et de temps, les travaux de l'état de l'art ne considèrent pas le fait que les données peuvent changer au fil du temps, et supposent toujours que les données restent statiques tout au long du calcul, ce qui n'est malheureusement pas du tout conforme à la réalité. Nos contributions dans cette thèse répondent à ces défis. Tout d'abord, nous proposons une approche out-of-core pour calculer les KNN sur de grands ensembles de données en utilisant un seul ordinateur. Nous préconisons cette approche comme un moyen moins coûteux pour faire passer à l'échelle le calcul des KNN par rapport au coût élevé d'un algorithme distribué, tant en termes de ressources de calcul que de temps de développement, de débogage et de déploiement. Deuxièmement, nous proposons une approche out-of-core multithreadée (i.e. utilisant plusieurs fils d'exécution) pour faire face aux défis du calcul des KNN sur des données qui changent rapidement et continuellement au cours du temps. Après une évaluation approfondie, nous constatons que nos principales contributions font face aux défis du calcul des KNN sur de grands ensembles de données, en tirant parti des ressources limitées d'une machine unique, en diminuant les temps d'exécution par rapport aux performances actuelles, et en permettant le passage à l'échelle du calcul, à la fois sur des données statiques et des données dynamiques. / The K-Nearest Neighbors (KNN) is an efficient method to find similar data among a large set of it. Over the years, a huge number of applications have used KNN's capabilities to discover similarities within the data generated in diverse areas such as business, medicine, music, and computer science. Despite years of research have brought several approaches of this algorithm, its implementation still remains a challenge, particularly today where the data is growing at unthinkable rates. In this context, running KNN on large datasets brings two major issues: huge memory footprints and very long runtimes. Because of these high costs in terms of computational resources and time, KNN state-of the-art works do not consider the fact that data can change over time, assuming always that the data remains static throughout the computation, which unfortunately does not conform to reality at all. In this thesis, we address these challenges in our contributions. Firstly, we propose an out-of-core approach to compute KNN on large datasets, using a commodity single PC. We advocate this approach as an inexpensive way to scale the KNN computation compared to the high cost of a distributed algorithm, both in terms of computational resources as well as coding, debugging and deployment effort. Secondly, we propose a multithreading out-of-core approach to face the challenges of computing KNN on data that changes rapidly and continuously over time. After a thorough evaluation, we observe that our main contributions address the challenges of computing the KNN on large datasets, leveraging the restricted resources of a single machine, decreasing runtimes compared to that of the baselines, and scaling the computation both on static and dynamic datasets.