L’apprentissage automatique (machine learning) désigne un ensemble de méthodes permettant à un programme d’améliorer ses performances sur une tâche à partir de données, sans que la logique de décision soit programmée explicitement règle par règle. Un cas particulier central en est l’apprentissage supervisé : on dispose d’exemples déjà étiquetés — une main humaine, ou un processus de mesure fiable, a associé à chaque exemple la réponse attendue — et l’on cherche une méthode pour prédire l’étiquette de nouveaux exemples, non encore vus.
L’algorithme des k plus proches voisins (souvent noté k-NN, de l’anglais k-nearest neighbors) est l’une des méthodes les plus simples d’apprentissage supervisé : il ne « construit » aucun modèle abstrait à proprement parler, mais classe un nouveau point en regardant simplement quelles sont ses étiquettes les plus proches parmi les exemples déjà connus. Cette simplicité en fait un excellent point d’entrée dans l’apprentissage automatique, et une référence à laquelle comparer des méthodes plus sophistiquées.
Le programme officiel précise que « la connaissance dans le détail des algorithmes de cette section n’est pas un attendu du programme » : l’objectif de ce chapitre est de comprendre le principe de la méthode et de savoir la mettre en œuvre sur un exemple simple, non d’en maîtriser toutes les subtilités.
Avant de décrire l’algorithme lui-même, il faut préciser ce qu’est une donnée pour la machine, et comment on mesure la « proximité » entre deux données — c’est cette notion de proximité qui est au cœur de la méthode.
Un jeu de données étiqueté (ou jeu d’apprentissage) est une famille finie de couples (x1,y1),(x2,y2),…,(xn,yn) où chaque xi∈Rp est un vecteur de p attributs (ou features) décrivant un exemple, et yi est son étiquette (ou classe), appartenant à un ensemble fini {c1,…,cm} de classes possibles.
Pour deux points x=(x(1),…,x(p)) et x′=(x′(1),…,x′(p)) de Rp, la distance euclidienne entre x et x′ est d(x,x′)=j=1∑p(x(j)−x′(j))2. C’est la généralisation directe de la distance usuelle dans le plan ou l’espace : d(x,x′) est la longueur du segment reliant x à x′.
D’autres façons de mesurer un écart entre deux points existent (par exemple en sommant les valeurs absolues des écarts coordonnée par coordonnée), mais seule la distance euclidienne est au programme pour l’algorithme des k plus proches voisins.
Encore 15 blocs dans ce document. Le reste du programme est écrit de la même main, avec les figures interactives et votre progression.