L'algorithme des k plus proches voisins, également connu sous le nom de KNN ou k-NN, est un discriminant d'apprentissage supervisé non paramétrique, qui utilise la proximité pour effectuer des classifications ou des prédictions sur le regroupement d'un point de données individuel. Bien qu'il puisse être utilisé pour des problèmes de régression ou de classification, il est généralement utilisé comme algorithme de classification, en partant de l'hypothèse que des points similaires peuvent être trouvés les uns à côté des autres.

Pour les problèmes de classification, un libellé de classe est affecté sur la base d'un vote à la majorité : le libellé de classe le plus fréquemment représenté autour d'un point de données donné est utilisé. Bien que cela soit techniquement considéré comme un « vote à la majorité », le terme « vote majoritaire » est plus couramment utilisé dans la littérature. La distinction entre ces terminologies est que le « vote à la majorité » nécessite techniquement une majorité supérieure à 50 %, ce qui fonctionne principalement lorsqu'il n'y a que deux catégories. Lorsque vous avez plusieurs classes, par ex. quatre catégories, vous n'avez pas nécessairement besoin de 50 % des voix pour tirer une conclusion sur une classe ; vous pouvez affecter un libellé de classe avec un vote supérieur à 25 %. L'Université du Wisconsin-Madison résume bien cela avec un exemple  ici (PDF, 1,2 Mo) (lien externe à ibm.com). 

Les problèmes de régression utilisent un concept similaire à celui des problèmes de classification, mais dans ce cas, la moyenne des k plus proches voisins est utilisée pour faire une prédiction sur une classification. La principale distinction ici est que la classification est utilisée pour les valeurs discrètes, tandis que la régression est utilisée pour les valeurs continues. Cependant, avant qu'une classification puisse être effectuée, la distance doit être définie. La distance euclidienne est la plus couramment utilisée, et nous l'aborderons plus en détail ci-dessous.
Il convient également de noter que l'algorithme KNN fait également partie d'une famille de modèles « d'apprentissage paresseux », ce qui signifie qu'il ne stocke qu'un jeu de données d'apprentissage au lieu d'effectuer une phase d'entraînement. Cela signifie également que tous les calculs ont lieu lorsqu'une classification ou une prédiction est effectuée. Puisqu'il s'appuie fortement sur la mémoire pour stocker toutes ses données d'entraînement, il est également appelé méthode d'apprentissage basée sur les instances ou basée sur la mémoire.
Evelyn Fix et Joseph Hodges sont à l'origine des idées initiales autour du modèle KNN dans cet  article de 1951 (PDF, 1,1 Mo) (lien externe à ibm.com) tandis que Thomas Cover a développé leur concept dans ses recherches (PDF, 1 Mo) (lien externe à ibm.com), « Classification des modèles de voisins les plus proches ». Bien qu'il ne soit plus aussi populaire qu'avant, il reste l'un des premiers algorithmes que l'on apprend en science des données en raison de sa simplicité et de sa précision. Cependant, à mesure qu'un jeu de données grandit, KNN devient de plus en plus inefficace, compromettant la performance globale du modèle. Il est couramment utilisé pour les systèmes de recommandation simples, la reconnaissance de modèle, la fouille de données, les prévisions des marchés financiers, la détection d'intrusion, etc. 

Pour récapituler, l'objectif de l'algorithme des k plus proches voisins est d'identifier les voisins les plus proches d'un point de requête donné, afin que nous puissions attribuer un libellé de classe à ce point. Pour ce faire, KNN a quelques exigences :

Déterminez vos mesures de distance

Afin de déterminer quels points de données sont les plus proches d'un point de requête donné, il vous faudra calculer la distance entre le point de requête et les autres points de données. Ces mesures de distance aident à former des limites de décision, qui partitionnent les points de requête en différentes régions. Vous verrez généralement des limites de décision visualisées avec les diagrammes de Voronoi.

Bien que vous puissiez choisir parmi plusieurs mesures de distance, cet article ne couvrira que les suivantes :

Distance euclidienne (p=2) :  il s'agit de la mesure de distance la plus couramment utilisée, et elle est limitée aux vecteurs à valeurs réelles. En utilisant la formule ci-dessous, elle mesure une ligne droite entre le point de requête et l'autre point mesuré.

Distance de Manhattan (p=1) : il s'agit également d'une autre mesure de distance populaire, qui mesure la valeur absolue entre deux points. Elle est également appelée taxi-distance, ou distance d'un pâté de maisons, car elle est généralement visualisée avec une grille, qui montre comment on peut naviguer d'une adresse à une autre via les rues de la ville.

Distance de Minkowski : cette mesure de distance est la forme généralisée de la mesure de distance euclidienne et de celle de Manhattan. Le paramètre, p, dans la formule ci-dessous, permet la création d'autres mesures de distance. La distance euclidienne est représentée par cette formule lorsque p est égal à deux, et la distance de Manhattan est notée avec p égal à un.

Distance de Hamming : cette technique est généralement utilisée avec des vecteurs booléens ou de chaîne, identifiant les points où les vecteurs ne correspondent pas. De fait, elle a également été appelée la mesure de chevauchement. Elle peut être représentée par la formule suivante :

Par exemple, si vous aviez les chaînes suivantes, la distance de Hamming serait de 2, car seules deux des valeurs diffèrent.

Comme tout algorithme d'apprentissage automatique, k-NN a ses forces et ses faiblesses. Selon le projet et l'application, il peut s'avérer être le bon choix ou le mauvais.

Facile à implémenter : compte tenu de la simplicité et de la précision de l'algorithme, c'est l'un des premiers discriminants qu'un nouveau spécialiste des données apprendra.

Il s'adapte facilement : à mesure que de nouveaux échantillons d'apprentissage sont ajoutés, l'algorithme s'ajuste pour tenir compte de toute nouvelle donnée, toutes les données d'apprentissage étant stockées en mémoire.

Peu d'hyperparamètres : KNN ne nécessite qu'une valeur k et une mesure de distance, ce qui est peu par rapport aux autres algorithmes d'apprentissage automatique.

Mise à l'échelle difficile : puisque KNN est un algorithme paresseux, il utilise plus de mémoire et de stockage de données par rapport aux autres discriminants. Cela peut être coûteux en termes de temps et d'argent. Davantage de mémoire et de stockage augmenteront les dépenses de l'entreprise et plus de données peuvent prendre plus de temps à calculer. Alors que différentes structures de données, telles que Ball-Tree, ont été créées pour remédier aux inefficacités de calcul, un discriminant différent peut s'avérer idéal en fonction de la problématique métier.

Malédiction de la dimensionnalité : l'algorithme KNN a tendance à être victime de la malédiction de la dimensionnalité, ce qui signifie qu'il fonctionne mal avec des entrées de données de grande dimension. Cette dernière est aussi parfois appelée le phénomène de peaking (PDF, 340 Mo) (lien externe à ibm.com), où une fois que l'algorithme a atteint le nombre optimal de fonctions, des fonctionnalités supplémentaires augmentent le nombre d'erreurs de classification, en particulier lorsque la taille d'échantillon est plus petite.

Enclin au surajustement : en raison de la « malédiction de la dimensionnalité », KNN est également plus enclin au surajustement. Bien que les techniques de sélection des fonctions et de réduction de la dimensionnalité soient utilisées pour éviter que cela ne se produise, la valeur de k peut également avoir un impact sur le comportement du modèle. Des valeurs inférieures de k peuvent surajuster les données, tandis que des valeurs plus élevées de k ont tendance à « lisser » les valeurs de prédiction, car il calcule la moyenne des valeurs sur une plus grande zone ou sur le voisinage. Cependant, si la valeur de k est trop élevée, il peut sous-ajuster les données.