Comprendre l’algorithme K-Nearest Neighbors (K-NN)

En data science, particulièrement en Machine Learning (ML), certains algorithmes sont à la fois simples à comprendre et redoutablement efficaces. C’est le cas de K-Nearest Neighbors, souvent abrégé K-NN pour signifier les K voisins les plus proches.
Derrière son apparente simplicité se cache un algorithme très utilisé pour des tâches de classification et de régression, notamment comme point de départ dans de nombreux projets data.

Dans les lignes qui suivent, nous allons aborder le principe de fonctionnement de K-NN, des exemples concrets d’applications ainsi que ses limitations et points de vigilance.

Principe de fonctionnement de l’algorithme K-NN

K-NN repose sur une idée intuitive “dis-moi qui sont tes voisins et je te dirai à quel groupe de voisins tu appartiens” ou plutôt sur une hypothèse simple : Des données proches dans l’espace des caractéristiques (variables) ont tendance à se ressembler.

C’est un algorithme non paramétrique contrairement à de très nombreux algorithmes de ML. Il est de la famille des algorithmes pour l’apprentissage supervisé.

Quatre étapes clés jalonnent la mise en place de l’algorithme.

Etape 1 : On choisit une valeur de K. Cette valeur représente le nombre de voisins les plus proches que l’on va considérer.

Etape 2 : On calcule la distance qui sépare les différents individus. Les distances les plus courantes sont la distance euclidienne, la distance Manhattan, la distance cosinus (dans certains contextes).

Etape 3 : On identifie les K plus proches voisins. A ce stade on sélectionne les K points les plus proches selon la distance choisie.

Etape 4 : C’est le moment de prendre une décision entre classification et régression. Pour la classification, la classe la plus représentée parmi les K voisins est attribuée. Pour la régression, on calcule la moyenne (ou une moyenne pondérée) des valeurs des voisins.

Les précédentes étapes seront mieux illustrées avec l’exemple concret ci-après. Supposons que nous souhaitons classer un nouveau client en Faible ou Fort (Dépensier) en fonction de son âge et du montant des dépenses. Pour cela, nous avons collecté des données pour entrainer notre modèle. On obtient ceci :

Client	Âge	Montant dépensé (€)	Classe
A	25	200	Faible
B	30	250	Faible
C	45	600	Fort

Comme il s’agit d’un algorithme supervisé, nous avons attribué des classes à chaque client. Supposons à présent que nous avons un nouveau client D âgé de 35 ans et qui a dépensé 400 euros. Nous souhaitons classer le client D dans le groupe en Faible ou Fort. Pour cela, calculons les distances euclidiennes et de Manhattan.

Calcul de la distance (Méthode Euclidienne)

Formule :$$d_{euclidienne} = \sqrt{(x_1 – x_2)^2 + (y_1 – y_2)^2}$$

Distance entre les clients D et A$$\sqrt{(35-25)^2 + (400-200)^2} = \sqrt{100 + 40\,000} = \sqrt{40\,100} ≈ 200.25$$

Distance entre les clients D et B$$\sqrt{(35-30)^2 + (400-250)^2} = \sqrt{25 + 22\,500} = \sqrt{22\,525} ≈ 150.08$$

Distance entre les clients D et C$$\sqrt{(35-45)^2 + (400-600)^2} = \sqrt{100 + 40\,000} = \sqrt{40\,100} ≈ 200.25$$

Classons les clients en fonction de la distance euclidienne.

1. B → 150.08
2. A → 200.25
3. C → 200.25

Calcul de la distance (Méthode de Manhattan)

Formule :$$d_{manhattan} = |x_1 – x_2| + |y_1 – y_2|$$

Distance entre les clients D et A$$|35-25| + |400-200| = 10 + 200 = 210$$

Distance entre les clients D et B$$|35-30| + |400-250| = 5 + 150 = 155$$

Distance entre les clients D et C$$|35-45| + |400-600| = 10 + 200 = 210$$

Si vous n’êtes pas matheux, le symbole |x| signifie la valeur absolue du nombre x. Elle est toujours positive. Par exemple |3| = 3 et |-3| = 3.

Classons les clients en fonction de la distance de Manhattan.

1. B → 155
2. A → 210
3. C → 210

Dans les deux cas, le client B semble le plus proche du client B.

Si on avait choisi K = 1, alors on partirait sur un seul voisin, et dans ce cas, la classe du client B serait dominante car c’est le voisin le plus proche. On prédit alors que le nouveau client D appartient à la classe des clients moins dépensier (Faible).

Si on avait choisi K=3, alors on partirait sur les trois voisins les plus proches. Ici les voisins A et B appartiennent à la même classe (Faible) et le voisin C appartient à une autre classe (Fort). Comme la classe comportant le plus de voisins proches est la classe Faible, alors on prédit que le client D appartient à la classe Faible.

Il est toujours recommandé de normaliser les variables avant toute chose pour éviter qu’une variable ne “cannibalise” les autres. Car dans l’exemple ci-dessus, la variable portant sur le montant dépensé est beaucoup grande que l’âge, elle peut donc avoir un poids plus important et ceci peut être problématique.

Le choix de la variable K est très important car s’il est trop petit le modèle est très sensible au bruit et on parle d’overfitting. Si K est trop grand, le modèle perd de sa précision et on parle d’underfitting.

Exemples concrets d’applications de K-NN

Système de recommandation

K-NN est souvent utilisé pour recommander :

• des films
• des produits e-commerce
• des contenus musicaux

On cherche des utilisateurs “proches” (comportements similaires) et on recommande ce qu’ils ont aimé.

Détection d’anomalie

Un point très éloigné de ses voisins peut être considéré comme :

• une fraude
• une erreur de mesure
• un comportement anormal.

Santé et diagnostic

K-NN est parfois utilisé pour :

• classifier des patients
• prédire des pathologies à partir de données cliniques similaires.

Limites d’utilisation

L’algorithme K-Nearest Neighbors est un excellent outil pour comprendre les bases du Machine Learning car il est assez intuitif, flexible et facile à implémenter. C’est un bon choix d’algorithme si le dataset est de taille modérée, les données sont bien normalisées, et qu’on cherche une solution simple et interprétable.

Il vaut mieux cependant l’éviter si les données sont très volumineuses, la dimension est élevée, les contraintes de performance sont fortes.