Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

06 février 2007 Projet informatique Algorithme des k-plus-proches-voisins 1 Pré

06 février 2007 Projet informatique Algorithme des k-plus-proches-voisins 1 Préliminaires Avant de s’intéresser à la programmation de l’algorithme des k-plus-proches-voisins, ou k-ppv il faudra avoir ﬁni les étapes suivantes : – tâches de base concernant les dessins (rectangle, manipulation de pixels) ; – transformation en HSV ; – enregistrer une image/partie d’image dans un ﬁchier ; – découpage en modules ! ! ! ! ! Et écriture d’un Makeﬁle. 2 Algorithme des k-ppv L’algorithme des k-plus-proches-voisins est l’un des algorithmes les plus simple d’apprentissage auto- matique supervisé. En supposant qu’une base d’apprentissage correctement étiquetée soit à disposition, cette méthode permet d’obtenir de très bon résultats de classiﬁcation. 2.1 Contexte : classiﬁcation supervisée Par classiﬁcation supervisée, on entend le problème suivant : à partir d’un échantillon ﬁni d’objets étiquetés/classés, on désire construire une fonction capable d’étiqueter/classer au mieux de nouveau objets (ne faisant pas partie de l’échantillon initial). Cela correspond parfaitement à la situation d’un élève de CP qui apprend à lire : sa maîtresse lui dessine au tableau des symboles représentant des lettres (les classes) et l’idée d’un apprentissage réussi est que l’élève arrive à lire n’importe quels caractères, quels que soient les scripteurs. . .le concept-clé de l’apprentissage est donc la généralisation. C’est également le cas en apprentissage automatique, où de multiples algorithmes ont été proposés pour la tâche de classiﬁcation. Les meilleurs algorithmes d’apprentissage reposent sur des résultats de statistique théorique extrêmement forts. Pour la détection de visage, les objets que nous allons considérer sont simplement des images, ou des portions d’image, et les classes utilisées sont simplement visage/non visage. 2.2 K-ppv : classiﬁeur « paresseux » L’algorithme k-ppv est un algorithme de la famille des algorithmes dits « paresseux » : à l’inverse de beaucoup d’autres méthodes d’apprentissage automatique (tels que la régression logistique, les réseaux de neurones artiﬁciels, les méthodes à noyaux, etc.) aucun apprentissage ne prend réellement place, c’est-à- dire qu’il n’y a pas de phase de détermination de paramètres d’une fonction par le biais d’une optimisation mathématique (cf. les prochains TD sur la régression logistique). Le principe est le suivant : étant donnée une base d’apprentissage d’images étiquetés correctement et un entier k, le classiﬁeur k-ppv détermine la classe d’un nouvel objet en lui attribuant la classe majoritaire des k objets lui ressemblant le plus dans la base d’apprentissage. Les ﬁgures suivantes illustrent le principe de fonctionnement de ce classiﬁeur (sources : http://www.vias.org/tmdatanaleng/cc_classif_knn.html et http://www. nysaes.cornell.edu/fst/faculty/siebert/FS608/syllabus.html). L. Ralaivola L2/L3 Télé-enseignement 1 06 février 2007 Projet informatique On note deux aspects importants de l’algorithme k-ppv : d’une part, à chaque nouvelle classiﬁcation il est nécessaire de parcourir l’ensemble de la base d’apprentissage, ce qui en fait un algorithmes qui n’est pas nécessairement très eﬃcaces (surtout que, habituellement, on cherche à avoir la base d’ap- prentissage la plus grande possible aﬁn d’avoir un meilleur classiﬁeur), et d’autre part, un point crucial de cet algorithme est la fonction de distance utilisée pour mesurer la proximité des objets. Il n’existe pas de distance/similarité universellement optimale et une bonne connaissance du problème traité guide généralement le choix de cette distance/similarité. 3 Travail à faire Le travail à faire concernant l’algorithme k-ppv s’étalera sur deux séances car il comporte plusieurs phases plus ou moins conséquentes : 1. récupération d’un base d’images représentant des visages et d’autres des non visages : ces bases constitueront l’ensemble d’apprentissage ; 2. calcul des histogrammes d’une image en représentation RGB et HSV ; 3. programmation de l’algorithme k-ppv ; 4. utilisation de la distance euclidienne et du cosinus dans le k-ppv pour mesurer l’eﬃcacité de la classiﬁcation eﬀectuée par l’aglorithme ; 5. connexion du module des k-ppv à l’interface graphique et encadrement des régions des images représentant des visages ; 6. (partie diﬃcile) ré-étiquetage à la souris des régions d’image mal classées pour l’enrichissement de la base d’aprpentissage. L. Ralaivola L2/L3 Télé-enseignement 2 uploads/Ingenierie_Lourd/ kppv.pdf