Techniques d’apprentissage statistique supervisé pour la classification

Un algorithme d’apprentissage de classification est dit supervisé si l’étiquette (la classe) associée à chaque observation est fournie en entrée. Le but de cet algorithme est de minimiser l’erreur de séparation (classification) sur la base d’apprentissage pour minimiser l’erreur en généralisation (problème d’optimisation). Dans ce qui suit, nous présentons quelques techniques d’apprentissage utilisés dans la classification d’objets, à partir de notre étude bibliographique. 

Classificateur par le plus proche voisin

La comparaison entre une requête (objet inconnu) et les modèles de la base d’apprentissage correspond à une recherche dans l’espace des vecteurs de primitives. En d’autres termes, les vecteurs de primitives sont considérés comme des points dans l’espace de recherche et la meilleure correspondance sera donnée par le voisin le plus proche en termes de distance. Le calcul des distances utilise en général les normes L1 ou L2. Ce classificateur est plus connu en anglais sous le nom KNearest Neighbor (K-NN). Les vecteurs de primitives sont stockés en mémoire sans leur apporter de Reconnaissance SHAIEK Ayet Page 152 modification. Pour prédire la classe d’une requête, l’algorithme cherche les K plus proches voisins de chaque vecteur de la requête et fournit comme classe estimée celle la plus fréquente parmi ces K plus proches voisins. Deux paramètres sont utilisés : le nombre K et la fonction de similarité pour comparer les vecteurs de la requête à ceux en apprentissage.

Métriques d’appariement

L’extraction des primitives des objets en apprentissage se fait au préalable, souvent en hors-ligne. En phase de reconnaissance, une mise en correspondance des objets un à un, compare les vecteurs primitives extraits de l’objet test avec tous ceux de la base d’apprentissage. Pour chaque vecteur (descripteur), l’objet le plus similaire reçoit un vote. L’objet avec le plus grand nombre de votes est choisi comme objet correspondant. Pour l’appariement des descripteurs définis sur les points d’intérêt, une mesure de similarité est calculée. Dans le cas des histogrammes, les mesures de similarité sont souvent les distances usuelles (Euclidienne (Bay, et al., 2006), Mahalanobis, Minkowski, Manhattan,…) ou encore la distance de programmation dynamique (DPD)). Ces métriques d’appariement comparent des bins de mêmes indices et sont par conséquent très sensibles à la quantification. Inversement, la mesure « Earth Mover Distance » EMD (distance de transport), parfois appelée distance du cantonnier, s’affranchit de cette limitation et compare des bins d’indices différents. Si f et g sont deux histogrammes de N bins, la distance EMD entre leurs histogrammes est égale à la distance L1 entre leurs histogrammes cumulés (||F – G||1). Dans le cas circulaire, la distance EMD entre f et g est le minimum en k des distances L1 entre les histogrammes Fk et Gk cumulés circulairement à partir de la k-ième cellule de quantification.  Tangelder, et al. (Tangelder, et al., 2003), utilisent, après extraction de la signature des modèles polyèdres dans leur approche de points saillants pondérés, la mesure Proportionnal Transportation Distance (PTD) inspirée de la distance (EMD) et qui satisfait l’inégalité des triangles. Cette mesure d’appariement permet de garantir l’invariance géométrique des descripteurs mis en correspondance.  Pour la mise en correspondance, le critère le plus intuitif est le seuillage de la mesure de similarité. Le choix d’un seuil global pour la distance du plus proche descripteur est problématique et ne peut pas être généralisé pour toutes les données et tous les descripteurs.  D. Lowe (Lowe, 2004) propose un critère consistant à comparer la distance au plus proche voisin avec la distance au deuxième plus proche voisin. Le plus proche voisin est apparié si le rapport de ces distances est inférieur à un seuil de « validité » de l’appariement. Cette approche exige que le plus proche voisin soit significativement plus proche que le plus proche appariement erroné. Des bons résultats attestent de l’efficacité de ce critère. Cependant, cela restreint la classification à l’appariement avec les deux plus proches voisins outre l’handicap du choix manuel du seuil.  Pour résoudre ces difficultés, Rabin et al. (Rabin, et al., 2007) proposent l’utilisation de la méthode a contrario dont l’idée principale est de valider des groupes en rejetant une hypothèse d’indépendance des structures à classer. En effet, cette méthode est adaptée pour réaliser une validation des mises en correspondances de descripteurs présentant des distances très petites sous l’hypothèse de l’indépendance des distances entre les composantes des deux descripteurs. Par la suite, une probabilité de similarité entre deux descripteurs bornée par un seuil de détection est définie.  Biasotti et al. (Biasotti, et al., 2006) , dans une étude comparative pour des méthodes de classification 3D, en prenant 4 descripteurs de forme différents, comparent la performance de SHAIEK Ayet Page 153 classification de 5 mesures de similarité: classifieur de distance minimum (Minimum Distance), Maximum distance classifier, Average distance classifier, Centroid distance classifier et Atipicity distance classifier. La conclusion était que la mesure de similarité du plus proche voisin donnait les meilleurs résultats. 

Kd-Tree

Dans le but d’organiser les données et d’optimiser le temps de recherche du plus proche voisin, on utilise souvent le Kd- tree (« K-dimensional tree »). Cette structure de données est un cas particulier des BSP trees (« Binary Space Partitionning trees », qui partitionnent l’espace des primitives sous forme d’arbre binaire. Chaque nœud de cet arbre contient un point de dimension K. Cette structure décompose l’espace en volumes englobants (ou voxels) et découpe chaque voxel (nœud non terminal) en deux sous-voxels (branches gauches et droites du nœud courant) grâce à un plan séparateur toujours perpendiculaire aux axes du repère de l’espace. L’algorithme général de construction d’un Kd-Tree est donné par le Tableau 5-1. Une représentation de la division du plan pour la construction et la recherche d’une requête dans un Kd-Tree est donnée dans la Figure 5-1 (Hemant, 2005). Si d est la dimension du descripteur et n le nombre d’entrée du KDtree, alors la complexité de construction de l’arbre est O(n log n) et celui de la recherche du plus proche voisin pour une requête est de O (n1-1/d+k). L’étape de structuration des données est réalisée en hors ligne et est suivie de l’étape de recherche qui se fait en ligne.  Cette méthode d’appariement permet de trouver un compromis entre précision et rapidité.