GWKNN : un algorithme k-plus proches voisins amélioré avec reconstruction de métrique G et Grey Wolf Optimizer

Reconnaissance de motifs plus intelligente pour le déluge de données actuel

Des scanners médicaux aux transactions bancaires, la vie moderne génère des océans de données. Une grande partie de ces informations doit être triée automatiquement en catégories : sain ou malade, frauduleux ou normal, spam ou légitime. Un outil classique pour ce type de tâche est l’algorithme k-plus proches voisins (KNN), qui étiquette un nouvel exemple en regardant les exemples passés les plus similaires. Cependant, à mesure que les jeux de données deviennent plus volumineux, plus complexes et plus déséquilibrés, cette idée simple commence à montrer ses limites. L’article présente GWKNN, une version remaniée du KNN conçue pour tirer parti des distances entre points de façon plus intelligente et pour traiter les cas rares mais importants de manière plus équitable.

Pourquoi la similarité simple est insuffisante

Le KNN classique suppose que toutes les caractéristiques d’un point de données contribuent de la même façon et mesure la similarité par une distance euclidienne standard. Cela peut bien fonctionner lorsque les données sont de faible dimension et bien séparées, mais les données réelles sont souvent de haute dimension, bruitées et constituées d’un mélange de types d’informations. Dans ces cas, la distance habituelle peut être trompeuse, poussant l’algorithme à choisir des voisins peu pertinents. Parallèlement, de nombreux jeux de données sont déséquilibrés : certaines catégories dominent, tandis que des catégories rares mais cruciales, comme une maladie à un stade précoce, sont sous-représentées. Quand KNN vote parmi les exemples voisins, la classe majoritaire tend à noyer ces cas minoritaires, entraînant des décisions biaisées et parfois dangereuses.

Apprendre à l’algorithme un meilleur sens de la distance

La première innovation majeure de GWKNN est une mesure de distance apprise. Plutôt que d’imposer la règle euclidienne habituelle, les auteurs laissent l’algorithme découvrir comment les points doivent être espacés pour mieux séparer les catégories. Ils codent cela sous la forme d’une « métrique G » flexible qui reconfigure l’espace afin que les caractéristiques informatives comptent davantage et que les redondantes comptent moins. Pour régler cette métrique, la méthode s’inspire du comportement de chasse des loups gris. Une procédure d’intelligence en essaim, appelée Grey Wolf Optimizer, explore de nombreuses façons possibles d’étirer et de comprimer l’espace des données, en conservant celles qui réduisent les erreurs de classification tout en maintenant la stabilité mathématique. Sur de nombreuses itérations, les « loups » virtuels convergent vers une règle de distance qui permet aux points similaires de se regrouper de manière plus fiable, même dans des jeux de données de haute dimension et entremêlés.

Donner une voix plus forte aux cas rares

La deuxième amélioration vise le biais du vote. Le KNN standard compte simplement combien des k voisins appartiennent à chaque classe et choisit la majorité. GWKNN pèse au contraire chaque vote en fonction de la fréquence de la classe dans l’ensemble d’entraînement. Les classes moins fréquentes reçoivent des poids plus forts ; les classes très fréquentes voient leurs poids réduits. Un petit terme de lissage évite que des catégories extrêmement rares ne dominent la décision. Ainsi, si un nouveau point de données se trouve près d’une poignée d’exemples de la classe minoritaire et de nombreux exemples de la classe majoritaire, les signaux minoritaires ne sont pas automatiquement noyés. Le procédé est simple à calculer mais a un effet puissant : il pousse le classificateur à prêter davantage attention aux motifs rares mais significatifs, améliorant l’équité et le rappel pour les classes minoritaires.

Mettre la nouvelle méthode à l’épreuve

Pour vérifier si GWKNN aide réellement en pratique, les auteurs l’ont évalué sur 12 jeux de données de référence issus du célèbre dépôt UCI. Ces collections couvrent des données financières, des mesures médicales, de l’écriture manuscrite, des graines de plantes et plusieurs jeux de données à haute dimension concernant le cancer et l’expression génique, avec des problèmes à deux classes et multi-classes. Ils ont comparé quatre variantes de KNN : le baseline simple, une version avec uniquement la nouvelle métrique de distance, une version avec uniquement les nouveaux poids de vote, et le GWKNN complet combinant les deux idées. Ils ont aussi opposé GWKNN à sept classificateurs largement utilisés, y compris les machines à vecteurs de support, les arbres de décision, les forêts aléatoires, la régression logistique, le naïf Bayes et un réseau de neurones. Sur des partitions entraînement–test répétées, ils ont suivi non seulement la précision moyenne mais aussi la variabilité des résultats.

Résultats : plus précis et plus stable

L’approche combinée GWKNN s’est classée première ou à égalité pour les meilleures performances sur la plupart des jeux de données, en particulier sur ceux comportant de nombreuses caractéristiques et des tailles de classes inégales. Sur des tâches relativement simples, toutes les méthodes ont bien fonctionné et les gains étaient modestes, mais GWKNN a quand même tendance à améliorer légèrement la précision et à réduire la variabilité. Sur des jeux de données d’expression génique plus difficiles, avec des milliers de caractéristiques, les avantages étaient plus nets : la métrique de distance apprise a aidé l’algorithme à former des voisinages plus signifiants, et le vote pondéré a amélioré la reconnaissance des classes sous-représentées. Des tests statistiques sur l’ensemble des jeux ont confirmé que le classement de GWKNN était significativement meilleur que celui du KNN standard et de certains modèles classiques, indiquant que ses améliorations ne sont pas de simples fluctuations chanceuses mais robustes à différentes conditions de données.

Ce que cela signifie pour les décisions de données du quotidien

Pour les non-spécialistes, la conclusion est que GWKNN affine une idée très intuitive — « regarder des cas passés similaires » — pour mieux correspondre à la réalité désordonnée des données modernes. En apprenant à mesurer la similarité de façon pilotée par les données et en renforçant l’influence des catégories rares lors du vote, la méthode vise à être à la fois plus précise et plus équitable. Si cette sophistication supplémentaire s’accompagne d’un coût computationnel accru, surtout pour des jeux de données très volumineux et de haute dimension, GWKNN montre un fort potentiel pour les tâches où la classification correcte des cas minoritaires est essentielle, comme la détection précoce de maladies ou la détection de fraudes. Ce travail illustre comment des algorithmes classiques peuvent être améliorés par des idées d’optimisation et d’équité pour suivre le rythme de l’échelle et de la complexité de l’information d’aujourd’hui.

Citation: Guo, Z., Liu, G., Liu, W. et al. GWKNN: an enhanced k-nearest neighbor algorithm with G metric reconstruction and Grey Wolf Optimizer. Sci Rep 16, 8857 (2026). https://doi.org/10.1038/s41598-026-41851-2

Mots-clés: k-plus proches voisins, apprentissage de la métrique de distance, Déséquilibre des classes, intelligence en essaim, classification de données