Approches Ensemblistes de Classification et Sélection des Prédicteurs pour la Reconnaissance de Formes

Approches Ensemblistes de Classification et
Sélection des Prédicteurs pour la Reconnaissance de Formes

Concepts Généraux de Combinaison de Classifieurs 

Parmi les nombreuses disciplines représentées en informatique, l’Apprentissage Automatique, ou Machine Learning en anglais, domaine d’étude de l’intelligence artificiel, concerne la conception, la recherche, le développement et l’implémentation d’algorithmes permettant à une machine d’apprendre réaliser l’induction automatique de règles à partir d’un ensemble d’exemples [Gacquer 2008a]. De manière formelle, nous disons que la machine doit apprendre à produire la sortie désirée lorsqu’elle est face à une situation spécifique [Mitchell 1999]. En apprentissage automatique, on peut distinguer deux grandes familles dépendantes des informations disponibles sur les données à classer : l’apprentissage supervisé et l’apprentissage non supervisé. L’apprentissage est dite supervisé [Vincent 2003 ; Oltean 2009] si les classes auxquelles appartiennent les exemples sont connues à l’avance et si la tâche d’apprentissage est guidée par la décision d’un superviseur ou d’un expert. Le but est de trouver un modèle qui décrit au mieux la relation entre les attributs et les classes afin de prédire la classe d’appartenance d’un nouvel exemple issu du système à surveiller. L’apprentissage non-supervisé (ou clustering) [Jain 1999] se distingue de l’apprentissage supervisé par le fait que la nature et le nombre des classes d’appartenance sont déterminés sans aucune connaissance préalable [Hansen 1997]. L’objectif, dans ce cas, est de partitionner un ensemble de données hétérogènes en plusieurs sous-ensembles d’individus ayant des caractères similaires. Les objets sont attribués aux différentes classes Chapitre 1. Concepts Généraux de Combinaison de Classifieurs 9 estimées selon deux critères essentiels qui sont la similitude entre les individus de chaque classe et la bonne séparation entre les classes. Cette thèse concerne plus particulièrement le problème de la classification. La classification [Cormack 1971 ; Belacel 1999 ; Henriet 2000] est l’une des tâches d’apprentissage supervisé consistant à classer les objets dans un ensemble fini de classes. L’objectif de la classification est de construire un modèle qui sera ensuite utilisé pour la classification des nouveaux objets (ou exemples) dont la classe d’appartenance est inconnue. Ces objets représentent des unités de données compactes spécifiques à un problème particulier comme les images, les paroles, les caractères manuscrits et sont généralement appelés « échantillon » ou « instance ». Une instance est représentée par un ensemble de propriétés quantifiables appelées « caractéristiques » qui devraient contenir des informations pertinentes sur la structure de l’objet que nous souhaitons à classer [Zhang 2003]. Ces caractéristiques peuvent potentiellement être collectées à partir d’un grand nombre de sources de données, ce qui se traduirait par un vecteur de mesures de haute dimensionnalité. Pour prendre une décision sur un échantillon non étiqueté, un système de classification doit se baser sur la connaissance a priori qui prend souvent la forme d’exemples connus [Vapnik 1998]. L’ensemble de ces exemples est appelé la base d’apprentissage ou la base d’entraînement. Cette base est fournie par l’expert humain qui structure les données et les étiquettes. Pour mesurer les performances d’un système de classification, une autre base de données étiquetée est utilisée. Cette base; appelée base de test ; ne doit pas avoir servi de connaissance préalable pour ne pas biaiser la mesure de performance. La classification est validée en évaluant sa pertinence à travers le taux des exemples de test bien classés. Afin de garantir la performance globale d’un système de reconnaissance, le processus de classification doit être précédé par d’autres étapes préliminaires qui sont le prétraitement [Liu 2001 ; Zhang 2003] et l’extraction de caractéristiques [Liu 2013 ; ElAtlas 2014 ; Sundararaj 2014]. Un schéma général d’un système de classification est illustré à la figure 1.1. Lors de l’étape de prétraitement, les objets d’entrée sont mis en forme et traités avant toutes manipulations afin de faciliter la tâche d’extraction de caractéristiques. Par exemple, c’est à cette étape qu’un signal sera filtré, qu’une image sera binarisée, normalisée ou redimensionnée pour obtenir une image plus lisible.

Formalisme de la classification supervisée 

Définition d’un classifieur

Soit un ensemble de objets. est un exemple décrit par un vecteur d’attributs [ ] de mesures, , ainsi que par un label qui lui est associé, ou est l’ensemble des classes. Chaque exemple est un vecteur de dimension composé d’un ensemble des paramètres continus (numériques) et / ou discrets (nominaux). Le processus de classification a pour but d’établir une transformation de l’espace d’attributs vers l’espace de classes [Vapnik 1998]. C’est cette transformation qui est souvent appelée classifieur. → (1.1) Basé sur la définition de la classification, un classifieur (prédicteur ou expert) peut être vu comme une fonction permettant d’assigner à chaque vecteur de caractéristiques d’un nouveau exemple une des classes pour lequel on ne dispose pas d’information a priori [Bishop 2006]: → (1.2) La mise en œuvre d’un classifieur nécessite généralement de choisir une représentation pour décrire les données (caractéristiques) et une base d’apprentissage qui permet de fixer les paramètres de l’algorithme de décision. Introduire des modifications à un classifieur que ce soit au niveau des données qu’il traite ou au niveau de ses paramètres (type de  sorties, règles de décision, etc.) modifie ses performances. Une généralisation de la définition d’un classifieur est proposée dans [Duda 1973] : un classifieur est un algorithme permettant d’associer à un exemple à reconnaitre un vecteur de niveau d’appartenance de cet exemple à une classe : [ ] (1.3) La fonction discriminantes avec représente le degré d’appartenance d’un objet à une classe . Dans ce cas, l’exemple peut appartenir à plusieurs classes si . La règle d’agrégation maximale est utilisée pour définir la classification comme suit: (1.4) Selon Xu [1992], cette réponse peut être divisée en trois catégories suivant le type d’information fournis par le classifieur :  Type classe: c’est le type le plus général mais qui apporte le moins d’informations. Dans ce type, le classifieur ne fournis que l’étiquette de classe attribuée à l’exemple d’entrée. Il pointe vers une catégorie unique en tant que classe gagnante en ignorant les informations sur les chances de sélection des autres classes en tant que décision finale. (1.5)  Type rang: dans ce niveau, la sortie d’un classifieur est un vecteur ordonné de classes candidates. La classe positionnée en premier est considérée comme le type de classe le plus probable, tandis que la classe placée à la fin du vecteur est la plus improbable. En outre, il n’y a aucune valeur de confiance incluse dans les étiquettes de classe dans ce type. Cependant, sa position dans la liste montre sa probabilité relative. Soit le rang attribué à la classe par le classifieur , la sortie de est définie par : Type mesure: nombreuses méthodes de classification génèrent leurs décisions sur la base de certaines mesures obtenues par une fonction discriminante d’un classifieur ou de certaines mesures de distance parmi les données de l’espace d’entrée. Dans ce type, la sortie d’un classifieur est un vecteur des mesures de taille , ou chaque mesure représente le niveau de confiance attribué à chaque classe . Cette mesure de confiance, normalisée ou non, peut-être des nombres arbitraires selon la structure de classification utilisée (une probabilité a posteriori, un score, une distance, une possibilité, une crédibilité, etc.). Par conséquent, le type mesure contient plus d’informations par rapport aux autres types de sortie.

Evaluation des classifieurs

L’évaluation des performances d’un classifieur est une phase importante dans le processus de conception d’un système de classification. Elle permet de savoir si ce système est suffisamment performant pour l’application visée et permet également de le comparer avec d’autres méthodes de classification. Une variété de mesures d’évaluation en fonction de différents critères a été proposée pour décrire la performance d’un classifieur, allant de la précision de classification et du taux d’erreur, en passant par la complexité du stockage et le temps de calcul jusqu’à la sensibilité et la robustesse [Vapnik 1998]. Pour évaluer le taux de classification ou la précision d’un classifieur, la méthode communément utilisée consiste à partitionner la base de données disponible en deux sousensembles et . La base est dédiée à l’apprentissage du classifieur et la base est utilisé comme un ensemble d’exemples de test inconnus pour l’évaluation de ses performances. La précision obtenue sur chacun des partitionnements est définie par : | | ∑ { ( )} | | (1.8) Où | | représente la taille de l’ensemble de test , représente la classe prédis par le classifieur pour l’échantillon et est sa classe réelle. La fonction est donnée par : { (1.9) Pour évaluer les qualités prédictives finales du modèle, on considère la précision moyenne des résultats obtenus sur les différents partitionnements réalisés. Cette méthode présente l’avantage de fournir une bonne estimation des facultés prédictives des modèles obtenus, en évitant une dépendance du résultat au choix particulier des échantillons d’apprentissage et de test. Le choix du partitionnement dépend principalement de la quantité de données disponibles. Une quantité très grande des exemples d’apprentissage peut induire un problème de sur-apprentissage du modèle, dont les facultés prédictives sur de nouveaux exemples sont diminuées. A l’inverse, un ensemble d’apprentissage de taille trop faible risque de provoquer une situation de sous-apprentissage, qui se traduit par un modèle incorrect et peu précis. Une étude des différentes approches de validation d’un modèle est présentée dans [Boser 1992] et [Gacquer 2008a]. Nous en présentons quelquesunes :  La méthode Hold-out consiste à partitionner aléatoirement les données de départ en deux sous-ensembles, généralement de tailles égales. Un sous-ensemble est utilisé pour la phase d’apprentissage, et l’autre servant à tester ou évaluer la performance du modèle de classification. Un cas particulier de cette méthode, appelé split-half consiste à de permuter les deux parties et d’évaluer le classifieur par la moyenne des deux estimations ainsi obtenues.  La validation croisée en blocs (k-fold cross validation) partitionne l’ensemble de données aléatoirement en sous-ensembles de taille approximativement égale. À chaque itération, un bloc est utilisé comme ensemble de test tandis que les autres blocs sont combinés pour former un ensemble d’apprentissage. L’algorithme d’apprentissage est exécuté fois, en changeant de bloc pour tester le classifieur. La précision finale est estimée en moyennant les performances obtenues à chaque itération. Afin de garantir que chaque sous-ensemble est un bon représentatif de la base de départ, les données sont souvent stratifiées avant d’être divisées en blocs de sorte que chaque bloc contient à peu près les mêmes proportions de classes que l’ensemble des données initial. Ceci est communément appelé validation croisée stratifiée en blocs.