Algorithmes de tri : Les k plus proches voisins

En intelligence artificielle, plus précisément en apprentissage automatique, la méthode des k plus proches voisins est une méthode d'apprentissage supervisé. En abrégé, on la note k-NN ou KNN, de l'anglais k-nearest neighbors.

Nous allons maintenant travailler sur un algorithme d'apprentissage automatique, souvent appelé, même en français, algorithme de machine learning. L'idée est d'utiliser un grand nombre de données afin "d'apprendre à la machine" à résoudre un certain type de problème (nous verrons un exemple un peu plus loin).

Cette idée d'apprentissage automatique ne date pas d'hier, puisque le terme de machine learning a été utilisé pour la première fois par l'informaticien américain Arthur Samuel en 1959. Pourquoi le machine learning est tant "à la mode" depuis quelques années ? Simplement parce que le nerf de la guerre dans les algorithmes de machine learning est la qualité et la quantité des données (les données qui permettront à la machine d'apprendre à résoudre un problème), or, avec le développement d'internet, il est relativement simple de trouver des données sur n'importe quel sujet (on parle de "big data"). À noter aussi l'importance des stratégies mises en place par les GAFAM (Google, Apple, Facebook, Amazon et Microsoft) afin de récupérer un grand nombre de données concernant leurs clients. Ces données sont très souvent utilisées pour "nourrir" des algorithmes de machine learning (comment, d'après vous, Amazon arrive à proposer à ces clients des "suggestions d'achats" souvent très pertinentes ?)

Nous allons étudier un algorithme d'apprentissage assez simple à appréhender : l'algorithme des "k plus proches voisins" (en anglais "k nearest neighbors" : knn)

Pour mieux apprehender ces méthodes, nous allons d'abord nous interesser à des méthodes pour trouver la distance entre plusieurs types de données. Pour la recherche des k plus proches voisins, vous trouverez de nombreuses informations en suivant ce lien où vous pourrez comprendre et tester ces algorithmes. Vous trouverez également des informations utiles ici ou encore là
Cette page est aussi pleine d'informations interessantes et utiles, tout comme celle ci . et enfin cette page

Dans le pdf ci dessous, des explications, des programmes à faire et à tester (en python) ainsi que des exercices relatifs à l'algorithme des k plus proches voisins ( à rendre à la fin de la séance )