Sélection de caractéristiques : Méthodes et applications
Institution:
Paris 5Disciplines:
Directors:
Abstract EN:
In many domains such as computer vision or pattern recognition, solving a problem is based on processing data extracted from a set of real world data acquired by means of sensors or resulting from some data processing. Data are structured as vectors. The quality of a processing system highly depends on the choice of these vector content. However, in many cases the vectors’ high dimensionality makes it almost impossible to use them to solve the problem, both because of the data themselves and of the learning set size. Hence, it is usually recommended, and sometimes required to reduce the vector size in order to make them more usable, even if the reduction might lead to information loss. Sometimes, solving complex problems with large descriptors can also be accomplished using a small set of features selected from initial data set. This can be done if the selected features are relevant with respect to the considered problem. Reducing vector dimensionality is often considered as a pre-processing step dedicated to noise and redundant information elimination. One type of dimensionality reduction methods is feature selection. It consists in selecting the most relevant features from an initial set. Existing feature selection methods reveal limitations on many levels such as complexity, interaction between the features, dependence on the evaluation classifier, and so on. In this thesis, in order to limit these drawbacks, we propose a fast selection method based on a genetic algorithm. Each feature is closely associated with a single feature classifier. We propose to use multi-objectives and mono-objective genetic algorithms, to find a good combination of simple classifiers. Experiments have shown that our method is fast, it has the ability to select a small number of features while maintaining good classification rates. The performances of the proposed method are shown through a comparison with other state of art methods. Finally, our method was applied in two types of applications: the indexing of drop caps extracted from old documents and biological data analysis. We have shown that a small number of features is enough for historians to index automatically a drop caps database. In the biology field, the quality of the molecules classification system according to specific classes identified by the biologists, has been improved while reducing the number of molecular descriptors by 78%.
Abstract FR:
Dans de nombreux domaines (vision par ordinateur, reconnaissance des formes, etc. ), la résolution de la plupart des problèmes se base sur le traitement de données extraites à partir des données acquises dans le monde réel, et structurées sous forme de vecteurs. La qualité du système de traitement dépend directement du bon choix du contenu de ces vecteurs. Mais dans de nombreux cas, la résolution du problème devient presque impossible à cause de la dimension trop importante de ces vecteurs. Par conséquent, il est souvent utile, et parfois nécessaire, de réduire celle-ci à une taille plus compatible avec les méthodes de résolution, même si cette réduction peut conduire à une légère perte d’informations. Dans ce cadre, nous proposons dans cette thèse une nouvelle méthode rapide de sélection de caractéristiques. Les méthodes existantes présentent des faiblesses au niveau de leur complexité très élevée, de la dépendance des caractéristiques pertinentes sélectionnées par rapport au classificateur utilisé, de la redondance entre les caractéristiques sélectionnées ainsi que des interactions entre les caractéristiques. Dans le but de limiter ces inconvénients, la méthode proposée est basée sur la construction et la sélection de classificateurs simples associés à chacune des caractéristiques. Nous proposons d’utiliser des algorithmes génétiques, monoobjectifs et multiobjectifs, afin de trouver une bonne combinaison des classificateurs simples. Les expérimentations ont montré que notre méthode est rapide, qu’elle a la capacité à sélectionner un nombre réduit de caractéristiques tout en conservant des taux de classification très satisfaisants. Les performances de la méthode proposée sont mises en évidence à travers une comparaison avec d’autres méthodes de la littérature du domaine. Enfin notre méthode a été appliquée dans deux applications concernant des domaines bien différents, celui de l’indexation de lettrines extraites de documents anciens et celui de l’analyse de données biologiques. Nous avons montré qu’un petit nombre de caractéristiques suffisait aux historiens pour indexer automatiquement une base de lettrines. Dans le domaine de la biologie, la classification de molécules selon des cibles bien précises définies par les biologistes a été améliorée en qualité tout en diminuant de 78% le nombre des descripteurs moléculaires.