Aller au contenu
English

Loin des voisins : la distance kNN

  • Leçon 15
  • 35 min
  • Module 4 : Distance, densité et isolement

Où nous en sommes

Nos références de base et nos cartes examinent un nombre à la fois. Une fraude peut sembler normale dans chaque colonne, mais étrange dans leur combinaison. Dans cette leçon, nous attribuons un score à un paiement selon sa distance aux plus proches voisins. Nous voyons comment la mise à l'échelle et le nombre de voisins changent le résultat.

Lue depuis YouTube. Rien ne se charge depuis YouTube avant que vous appuyiez sur lecture. Confidentialité
Leçon 15 sur 38 · Détection d'anomalies : trouver ce qui est inhabituelLoin des voisins : la distance kNN
Aperçu du cours

Ce que vous saurez faire

Attribuez un score à un paiement selon sa distance aux plus proches voisins normaux. Vous pourrez ainsi trouver une fraude qui semble normale dans chaque colonne. Découvrez aussi les deux paramètres qui rendent ce score utile : la mise à l’échelle des variables et le nombre de voisins.

Carnet JupyterFaites cette leçon dans un carnet JupyterColab · Kaggle · GitHub · en anglais

Le carnet (notebook) Jupyter contient toutes les cellules de code, tâches et vérifications de cette leçon, avec les consignes. Ses cellules de configuration installent pandas, NumPy, SciPy, scikit-learn et matplotlib, puis téléchargent les paiements (environ 7 Mo). L’exécution du carnet complet prend environ une minute.

Le carnet est en anglais. Colab et Kaggle ouvrent votre propre copie. Il faut un compte Google ou Kaggle gratuit. Vous êtes bloqué ? Consultez le carnet de solution.

Avant de commencerCe qu’il faut savoir et avoir sous la mainEnviron 35 minutes

Ce que vous devez savoir

Ce qu’il vous faut sur votre ordinateur

Un navigateur et un compte Google gratuit (Colab) ou un compte Kaggle. Rien à installer. Pour travailler localement, utilisez Python 3.12 et la configuration de Découvrir les données de Larkfield.

Testé avec Python 3.12.13 dans Jupyter sur macOS, avec scikit-learn 1.9.1 et pandas 3.1.1. Colab, Kaggle et Windows n’ont pas été testés.

Imaginez une fête. La plupart des invités discutent en petits groupes. Une personne reste seule dans un coin. Vous ne savez rien des invités : ni leurs noms, ni leurs emplois. Pourtant, vous remarquez la personne dans le coin. Elle est loin de tout le monde.

Vous n’avez pas comparé chaque invité à une règle comme « mesure plus de 2 mètres ». Vous avez comparé chaque invité aux autres invités les plus proches. Dans un groupe, les voisins sont proches. Pour la personne dans le coin, ils ne le sont pas.

Cette leçon transforme cette idée en détecteur pour les paiements.

Le problème : normal dans chaque colonne, étrange dans l’ensemble

Section intitulée « Le problème : normal dans chaque colonne, étrange dans l’ensemble »

Dans le module 2, chaque détecteur examinait un nombre à la fois. La MAD par client examinait le montant. La règle de vélocité comptait les paiements en 10 minutes. Chaque détecteur comparait une colonne à ses valeurs habituelles.

Revenons au paiement qui ne cadrait pas, dans la première leçon du cours. La cliente C-01234 fait chaque samedi matin, au Canada, un paiement correspondant au prix d’un café. Le 3 octobre 2025, à 2 h 14, sa carte paie 24,27 dollars au Portugal, sur un nouvel appareil. Examinez chaque colonne séparément :

  • Le montant : 24,27 dollars. Le panier habituel coûte entre 11,15 et 17,98 dollars. Un peu plus que d’habitude, mais rien d’étrange.
  • L’heure : 2 h. Environ 3 % des paiements des mois de référence ont lieu la nuit. Rien d’inhabituel en soi.
  • Le pays : le Portugal. Les clients voyagent : les données contiennent 703 paiements honnêtes effectués en voyage.
  • L’appareil : nouveau. Les gens achètent de nouveaux téléphones.

Chaque colonne, prise seule, a une explication innocente. Mais les quatre ensemble, pour cette cliente, n’en ont aucune. La MAD par client n’a trouvé que 3,3 % des paiements par carte volée (mesure du module 2). Elle examine seulement le montant.

Il nous faut un score qui examine toutes les colonnes d’un paiement en même temps.

Représentez chaque paiement par un point dans un espace. Chaque colonne représente une direction de cet espace : montant, heure, nouveau pays, etc. Les paiements qui se ressemblent sont proches. Un paiement qui ne ressemble à aucun autre est loin de tous les autres.

Pour chaque nouveau paiement, trouvez les k paiements les plus proches parmi les paiements normaux. Mesurez ensuite la distance au k-ième d’entre eux. Cette distance est le score :

  • Un paiement dans un groupe : ses k plus proches voisins sont proches. Petit score.
  • Un paiement seul : même ses plus proches voisins sont loin. Grand score.

C’est la distance aux k plus proches voisins (kNN). « k » est simplement le nombre de voisins que vous choisissez. La « distance » est celle en ligne droite que vous connaissez depuis l’école : dans un plan, on utilise le théorème de Pythagore.

Prenez sept points dans un plan. Six d’entre eux, A à F, sont proches les uns des autres. G est loin. Nous utilisons k = 2 : le score de chaque point est la distance à son 2e plus proche voisin.

Un plan avec sept points. Six points gris, A à F, sont regroupés près du point (1, 1). Un point bleu, G, se trouve à (3, 3), loin des autres. Deux lignes pointillées relient G à ses deux plus proches voisins, D et F. Le texte indique : le 2e plus proche voisin de G est à une distance de 2,62. A à F : leur 2e plus proche voisin est à une distance de 0,22 à 0,32. G a le score le plus élevé.
Sept points et leur score avec k = 2 : la distance au 2e plus proche voisin. G est seul, donc son score est environ dix fois plus grand que les autres.
Description textuelle du diagramme

L’image montre un plan avec sept points. Six points gris, A à F, sont regroupés près du point x = 1, y = 1. Un point bleu, G, se trouve à x = 3, y = 3. Deux lignes pointillées relient G à ses deux plus proches voisins, D et F. Le texte à côté du plan indique que le 2e plus proche voisin de G est à une distance de 2,62. Pour A à F, le 2e plus proche voisin est à une distance de 0,22 à 0,32.

Voici toutes les valeurs. D se trouve à (1,1, 1,2) et G à (3,0, 3,0). La distance de G à D est :

√((3,0 − 1,1)² + (3,0 − 1,2)²) = √(3,61 + 3,24) = √6,85 = 2,62

F se trouve à (1,0, 1,3), lui aussi à une distance de 2,62 de G. Le 2e plus proche voisin de G est donc à une distance de 2,62. Maintenant, A, à (1,0, 1,0) : son plus proche voisin est C, à 0,14, et son 2e est B, à 0,22.

Point 2e plus proche voisin Score (k = 2)
A B 0,22
B D 0,32
C F 0,22
D A 0,22
E C 0,32
F C 0,22
G F 2,62

Le score de G dépasse de plus de huit fois le plus grand score du groupe. Le détecteur n’a besoin d’aucune étiquette. Il lui faut seulement un ensemble de points que nous jugeons majoritairement normaux.

Priya, la scientifique des données de Larkfield, essaie cette idée sur les paiements de Larkfield. Le détecteur apprend ce qui est « normal » à partir d’un échantillon aléatoire de 20 000 paiements des mois de référence, juin à août. Il les conserve. Il attribue ensuite un score à chaque paiement des mois d’évaluation, septembre à novembre.

Chaque paiement devient un point avec huit variables comportementales. Ces variables comparent le paiement au passé du client. Par exemple : le montant par rapport au montant habituel, un nouveau pays, un nouvel appareil et les paiements de la dernière heure. Les variables comptent plus que l’algorithme les construit une à une. Pour l’instant, utilisez-les telles quelles.

Priya compare deux paiements de la même cliente, C-01234. Le premier est un panier ordinaire du samedi, le 27 septembre 2025. Le second est le premier paiement au Portugal, le 3 octobre à 2 h 14. C’est un paiement que nous avons inséré : une carte volée.

Deux panneaux ronds avec des cercles pointillés aux distances 1 à 5. À gauche, un paiement normal : le panier du samedi de C-01234, le 27 septembre. Ses 10 plus proches voisins sont à des distances de 0,005 à 0,025, tous à l'intérieur du point central. Il se classe au rang 1 835 parmi les 2 002 paiements de la journée. À droite, le paiement inséré : le premier paiement de C-01234 au Portugal, le 3 octobre à 2 h 14. Ses 10 plus proches voisins sont à des distances de 2,02 à 4,86, entre les 2e et 5e cercles. Il se classe au rang 2 parmi les 1 780 paiements de la journée.
Les 10 plus proches voisins d'un paiement normal et d'un paiement inséré, parmi 20 000 paiements de référence, à la même échelle. Le panier normal se trouve dans un groupe; le paiement inséré n'a aucun voisin proche.
Description textuelle du diagramme

L’image montre deux panneaux ronds à la même échelle, avec des cercles pointillés aux distances 1, 2, 3, 4 et 5. À gauche, le paiement normal : le panier du samedi de C-01234, le 27 septembre. Ses 10 plus proches voisins sont à des distances de 0,005 à 0,025. Ils sont si proches qu’ils se trouvent tous à l’intérieur du point central. Son score se classe au rang 1 835 parmi les 2 002 paiements de la journée. À droite, le paiement inséré : le premier paiement de C-01234 au Portugal, le 3 octobre à 2 h 14. Ses 10 plus proches voisins sont à des distances de 2,02 à 4,86, entre les 2e et 5e cercles. Son score se classe au rang 2 parmi les 1 780 paiements de la journée. Les directions des points servent seulement au dessin; les distances sont réelles.

Le graphique montre les mêmes distances, voisin par voisin :

Distance du 1er au 10e plus proche voisin, dans les variables comportementales mises à l'échelle. La courbe du panier normal reste à 0,03 ou moins. Le plus proche voisin du paiement inséré est déjà à une distance de 2,02. Avec k = 10, les scores sont 0,025 et 4,86.
Description textuelle du graphique

Un graphique en courbes. L’axe horizontal représente le voisin, de 1 (le plus proche) à 10. L’axe vertical représente la distance, de 0 à 5. La courbe du paiement normal reste plate près de 0 : de 0,005 à 0,025. La courbe du paiement inséré commence à 2,02 pour le plus proche voisin et monte à 4,86 pour le 10e.

Le panier normal ressemble à des milliers d’autres : un petit paiement, au Canada, sur un appareil connu, le matin. Ce n’est pas le cas du paiement inséré. Parmi les 20 000 paiements de référence, aucun n’est proche de lui. Son score est le 2e plus élevé des 1 780 paiements de la journée. Il est donc transmis à l’équipe de Sofia.

Un autre détail mérite notre attention. Parmi les 10 plus proches voisins du paiement inséré, 9 sont des paiements insérés des mois de référence. Les mois de référence ne sont pas exempts de fraude : il y en a chaque mois. Le détecteur fonctionne quand même, car la proportion de paiements insérés est faible. Mais cela explique pourquoi le choix de k compte, comme vous le verrez plus bas.

  1. Ouvrez le carnet dans l’encadré Faites cette leçon dans un carnet Jupyter en haut de cette page. Exécutez les trois cellules de configuration.
  2. Exécutez la section 1, le petit exemple. Vérifiez que G vaut 2,62 et que les autres valent de 0,22 à 0,32.
  3. Exécutez la cellule qui charge les paiements. Elle affiche les trois premières lignes brutes : montant (sous forme de logarithme), heure et type de compte.
  4. Exécutez la cellule qui définit knn_scores(). Elle met les variables à l’échelle, conserve l’échantillon de 20 000 paiements et attribue des scores aux mois d’évaluation.
  5. Vérifiez le tableau. La précision au budget est de 0,219 avec les variables brutes.

La fonction du carnet est courte :

def knn_scores(X, k=10, sample=20_000, seed=0):
"""Distance of each evaluation payment to its k-th nearest neighbour among reference payments."""
scaler = StandardScaler().fit(X.loc[reference.index])
ref = scaler.transform(X.loc[reference.index])
ref = ref[np.random.default_rng(seed).choice(len(ref), sample, replace=False)] # a sample: kNN is slow
nn = NearestNeighbors(n_neighbors=k).fit(ref)
dist, _ = nn.kneighbors(scaler.transform(X.loc[evaluation.index]))
return dist[:, -1]

NearestNeighbors vient de scikit-learn. kneighbors renvoie les distances aux k points conservés les plus proches, du plus proche au plus éloigné. La dernière colonne, dist[:, -1], est la distance au k-ième : le score.

Avec les variables brutes, la distance aux k plus proches voisins atteint une précision au budget de 0,219. Avec les variables comportementales, elle atteint 0,505. Les deux valeurs sont mesurées et figurent dans le tableau comparatif. Gardez la seconde valeur en tête. La dernière leçon de ce module l’explique.

La mise à l’échelle détermine ce que « loin » veut dire

Section intitulée « La mise à l’échelle détermine ce que « loin » veut dire »

Une distance additionne les différences dans chaque colonne. Une colonne contenant de grands nombres peut donc dominer toutes les autres.

Voici un petit exemple. Deux paniers coûtent 40 et 52 dollars : une différence de 12. Deux paiements ont lieu à 3 h et à 15 h : une différence de 12 aussi. Pour la distance, les deux différences sont égales. Mais une différence de 12 dollars est négligeable, alors qu’une différence de 12 heures est grande. Pire encore, les montants atteignent plusieurs milliers de dollars. Une commande d’entreprise de 1 500 dollars est donc « loin » de presque tout, seulement à cause des dollars.

La mise à l’échelle donne le même poids à chaque colonne. La méthode habituelle, la mise à l’échelle standard, soustrait la moyenne de la colonne de chaque valeur. Elle divise ensuite le résultat par l’écart-type de la colonne (sa dispersion habituelle). Après la mise à l’échelle, chaque colonne a une moyenne de 0 et une dispersion de 1.

Prenez la colonne new_country (nouveau pays) dans les mois de référence. Elle vaut 1 pour un paiement provenant d’un pays où le client n’avait jamais payé, sinon 0. Sa moyenne est de 0,011 (environ 1 paiement sur 90) et son écart-type est de 0,106. Un 1 devient donc :

(1 − 0,011) ÷ 0,106 ≈ 9,3

Un « oui » rare devient un grand nombre, et un « non » fréquent reste près de 0 (−0,11). Voilà pourquoi le paiement inséré était si loin. Son nouveau pays (9,3), son heure nocturne (5,4) et son nouvel appareil (4,7) sont tous des valeurs rares.

Le carnet retire la mise à l’échelle pour voir ce qui arrive. Le montant reste en dollars, et l’heure reste entre 0 et 23 :

Distance aux k plus proches voisins avec k = 10 sur les mois d'évaluation de Larkfield (mesurée). Sans mise à l'échelle : les colonnes brutes en dollars et en heures. Avec mise à l'échelle : les mêmes colonnes brutes, le montant sous forme de logarithme, puis la mise à l'échelle standard. Comportement : les huit variables comportementales mises à l'échelle.
Description textuelle du graphique

Un graphique avec trois colonnes. Sans mise à l’échelle : 0,013. Variables brutes mises à l’échelle : 0,219. Variables comportementales mises à l’échelle : 0,505. Sans mise à l’échelle, presque aucune des 50 alertes quotidiennes n’est une fraude insérée.

Sans mise à l’échelle, la précision tombe à 0,013 : moins de 1 fraude insérée pour 50 alertes. La distance dépend alors presque uniquement du montant en dollars. Les alertes correspondent donc aux plus grosses commandes d’entreprise.

Différents types de variables demandent des précautions

Section intitulée « Différents types de variables demandent des précautions »

Les paiements combinent trois types de colonnes. Une distance les traite tous de la même façon :

  • Les montants ont une distribution asymétrique : la plupart sont petits, quelques-uns sont énormes. Le carnet prend d’abord le logarithme : 10 dollars devient 2,3 et 1 000 dollars devient 6,9.
  • Les heures suivent un cycle : 23 h et 0 h sont séparées d’une heure, mais la distance voit 23. Les variables comportementales utilisent une colonne oui/non night (nuit) au lieu de l’heure.
  • Les colonnes oui/non (nouveau pays, compte d’entreprise) valent 0 ou 1. La mise à l’échelle transforme un « oui » rare en une grande valeur, comme vous l’avez vu. C’est souvent ce que vous voulez, mais vérifiez-le.

Aucun paramètre ne règle cela pour vous. Choisissez soigneusement les colonnes et leur forme, puis mesurez.

Le nombre de voisins, k, est l’autre paramètre. Changez-le et mesurez de nouveau, sans rien changer d’autre :

Distance aux k plus proches voisins sur les variables comportementales avec cinq valeurs de k : précision au budget de 50 alertes par jour (mesurée). L'axe commence à 0,40 pour montrer les différences. Le paramètre du cours est k = 10.
Description textuelle du graphique

Un graphique avec cinq colonnes, sur un axe qui commence à 0,40. k = 1 : 0,450. k = 5 : 0,498. k = 10 : 0,505. k = 20 : 0,509. k = 50 : 0,515.

k = 1 donne un résultat nettement moins bon : 0,450. Rappelez-vous les 9 voisins insérés du paiement inséré. Un nouveau paiement par carte volée a souvent une ancienne fraude proche de lui dans l’échantillon de référence. Avec k = 1, cette seule ancienne fraude fait paraître le nouveau paiement normal. Avec k = 10 ou plus, le score dépasse ce petit groupe d’anciennes fraudes pour atteindre le groupe normal derrière lui.

Au-delà de k = 10, le gain est faible : de 0,505 à 0,515. Un k plus grand demande aussi plus de temps. Il lisse aussi le score : avec un très grand k, chaque point semble un peu loin. Un k entre 10 et 50 est un point de départ raisonnable ici. Mesurez sur vos propres données avant de choisir.

Quand utiliser la distance kNN, et ce qu’elle coûte

Section intitulée « Quand utiliser la distance kNN, et ce qu’elle coûte »

Utilisez-la quand les anomalies sont des points qui ne ressemblent à aucun autre. Il vous faut aussi un jeu de données surtout normales. Elle n’a pas besoin d’étiquettes. Elle s’explique facilement à un réviseur : « Ce paiement n’a aucun équivalent proche; voici ses plus proches voisins. »

Faites attention dans trois cas :

  • Vitesse et mémoire. kNN conserve les points normaux et compare chaque nouveau point avec eux. Ici, il conserve un échantillon de 20 000 paiements, pas les 173 271 paiements de référence. Le calcul des scores pour 169 803 paiements d’évaluation avec les variables comportementales a pris 4,1 secondes (mesurées). Avec tous les paiements de référence, il prendrait beaucoup plus de temps.
  • Densités différentes. Les paiements d’un compte d’entreprise sont plus dispersés que ceux d’un compte personnel. Une seule distance ne convient pas aux deux. La prochaine leçon traite de ce problème.
  • Rafales. Plusieurs fraudes du même type, proches les unes des autres, peuvent devenir voisines. Un k plus grand aide.

Erreur courante

Le détecteur qui trouve seulement les grosses commandes d'entreprise

Symptôme : Tomás applique kNN aux colonnes brutes des paiements. La précision au budget est de 0,013. Sofia ouvre les alertes : presque toutes concernent une grosse commande d’entreprise.

Cause : il n’a pas mis les colonnes à l’échelle. Le montant atteint des milliers de dollars; l’heure va de 0 à 23; le type de compte vaut 0 ou 1. Le montant détermine presque toute la distance. « Loin » veut donc dire « cher ».

Solution : prenez le logarithme du montant, puis mettez chaque colonne à l’échelle avec StandardScaler, ajusté seulement sur les mois de référence. Les mêmes colonnes brutes donnent alors 0,219.

Conséquence pour le travail en IA : toute méthode basée sur une distance suit discrètement la colonne aux plus grands nombres. Cela comprend kNN, LOF, k-means et le SVM à une classe (One-Class SVM). Le code s’exécute sans erreur, mais le résultat est faux. Vérifiez toujours l’échelle de chaque colonne d’abord.

Dans le carnet (notebook) Jupyter, la section 6 propose trois tâches :

  1. Dans le petit exemple, écrivez la distance de G à son 2e plus proche voisin dans g_distance. La vérification vous indique si elle est correcte.
  2. Calculez les scores des variables comportementales avec k = 1, 10 et 50. Mettez chaque précision au budget dans un dictionnaire by_k, et le meilleur k dans best_k. Avant d’exécuter le code, prédisez l’ordre des trois résultats. Cette cellule prend environ 20 secondes.
  3. Ajoutez votre meilleur k comme nouvelle ligne du tableau comparatif, puis comparez-le aux lignes précédentes.
Afficher les résultats attendus
  1. g_distance = 2.62.
  2. {1: 0.45, 10: 0.505, 50: 0.515}, donc best_k = 50. k = 1 est le pire : une seule ancienne fraude proche fait paraître normale une nouvelle fraude.
  3. La nouvelle ligne a une précision au budget de 0,515, un peu supérieure à celle avec k = 10 (0,505).

Vérifiez votre compréhension

Dans vos mots : qu'est-ce que le score de distance kNN d'un paiement? Pourquoi une carte volée utilisée à l'étranger, la nuit, sur un nouvel appareil obtient-elle un score élevé? Chaque colonne prise séparément semble pourtant normale.

Afficher la réponse

Le score est la distance entre le paiement et son k-ième plus proche voisin parmi les paiements normaux conservés. Un paiement entouré de paiements semblables a des voisins proches et un petit score. Le paiement par carte volée combine plusieurs valeurs rares pour ce client : nouveau pays, nouvel appareil et nuit. Chaque valeur prise seule a des équivalents honnêtes. La combinaison n’en a aucun. Même ses plus proches voisins sont donc loin, et le score est élevé.

Vérifiez votre compréhension

Prédisez : vous appliquez kNN aux colonnes brutes sans mise à l'échelle. Elles contiennent le montant en dollars, l'heure de 0 à 23 et le type de compte, 0 ou 1. Quels paiements remplissent les alertes, et pourquoi?

Afficher la réponse

Les montants les plus élevés : les grosses commandes d’entreprise. Le montant contient de loin les plus grands nombres. Il détermine donc presque toute la distance. L’heure et le type de compte comptent à peine. Larkfield a mesuré une précision au budget de 0,013 sans mise à l’échelle. Les mêmes colonnes donnent 0,219 avec le logarithme et la mise à l’échelle standard.

Vérifiez votre compréhension

Avec k = 1, kNN trouve moins de fraudes insérées (0,450) qu'avec k = 10 (0,505). Expliquez pourquoi, à partir du contenu des mois de référence.

Afficher la réponse

Les mois de référence contiennent aussi des fraudes insérées. Une nouvelle fraude a donc souvent une ou quelques anciennes fraudes proches. Avec k = 1, le score est la distance à cette seule ancienne fraude. Cette distance est petite, donc la nouvelle fraude semble normale. Avec k = 10, le score est la distance au 10e voisin. Ce voisin se trouve généralement parmi les paiements normaux, loin de la fraude. Le paiement inséré du Portugal avait 9 paiements insérés parmi ses 10 plus proches voisins.

Récapitulatif

  • La distance kNN donne un score à un point selon sa distance au k-ième plus proche voisin parmi les points normaux. Loin de tous les autres veut dire inhabituel. Elle n’a pas besoin d’étiquettes.
  • Elle examine toutes les colonnes à la fois. Elle trouve donc un paiement normal dans chaque colonne, mais étrange quand on les combine.
  • La mise à l’échelle détermine ce que « loin » veut dire. Sans elle, les dollars décident de tout : 0,013 au lieu de 0,219.
  • k compte. Une seule ancienne fraude proche trompe k = 1 (0,450). k = 10 donne 0,505, et k = 50 donne 0,515.
  • Le calcul est lent avec beaucoup de lignes. Il compare chaque nouveau paiement aux paiements conservés. Le cours utilise donc un échantillon de 20 000 paiements.

Vous pouvez maintenant attribuer un score à un paiement selon sa distance à ses voisins. Mais une seule distance ne convient pas à toutes les zones. Les paiements d’un compte d’entreprise sont naturellement dispersés. Ceux d’un compte personnel sont proches les uns des autres. Ensuite, vous évaluerez un paiement selon la densité de sa propre zone, avec le LOF (facteur local d’aberrance).

Leçon suivante : Densité locale : LOF