L'un des plus gros défauts de la recherche de plus proches voisins avec kNN, c'est qu'elle effectue une recherche exhaustive.
LE PROBLÈME
kNN compare ta requête à tout

Autrement dit, le point de requête doit être comparé à tous les points de données pour trouver son ou ses plus proches voisins.
C'est très inefficace, surtout quand il y a beaucoup de points de données et qu'il faut une réponse quasi instantanée.
L'IDÉE
Réduire l'espace de recherche
C'est pourquoi les algorithmes de recherche approximative de plus proches voisins (ANN) sont de plus en plus populaires.
L'idée centrale est de réduire l'espace de recherche grâce à des techniques d'indexation, ce qui améliore le temps d'exécution global.

L'INDEXATION
L'Inverted File Index (IVF)
L'Inverted File Index (IVF) est sans doute l'une des techniques les plus simples et les plus intuitives dans ce domaine, et tu peux l'utiliser tout de suite.
Voici comment ça marche :
Étant donné un ensemble de points dans un espace de grande dimension, l'idée est de les organiser en différentes partitions, généralement avec un algorithme de clustering comme k-means.

Résultat : chaque partition a un centroïde correspondant, et chaque point de données est associé à une seule partition, celle de son centroïde le plus proche.

Chaque centroïde conserve aussi l'information sur tous les points de données qui appartiennent à sa partition.

L'indexation est terminée !
LA RECHERCHE
D'abord le bon centroïde
Voici comment on cherche.
Pour trouver le ou les plus proches voisins du point de requête, au lieu de chercher dans tout le jeu de données, on commence par trouver le centroïde le plus proche de la requête :

Une fois ce centroïde trouvé, on cherche le plus proche voisin uniquement parmi les points de données qui appartiennent à la partition correspondante :

LA COMPLEXITÉ
Combien de temps tu gagnes
Voyons comment la complexité en temps se compare à celle du kNN classique.
Prenons les hypothèses suivantes :
Il y a N points de données.
Chaque point de données a D dimensions.
On crée K partitions.
Enfin, pour simplifier, on suppose que chaque partition contient le même nombre de points.
Avec kNN, le point de requête est comparé aux N points de données, ce qui donne une complexité en temps de O(ND).
Avec IVF, en revanche, il y a deux étapes :
Comparer la requête à tous les centroïdes → O(KD).
Trouver le plus proche voisin dans la partition la plus proche → O(ND/K).
La complexité finale en temps est donc la suivante :

C'est nettement inférieur à celle du kNN.
Pour te donner un ordre de grandeur, imaginons 10 millions de points de données. La complexité de la recherche kNN sera proportionnelle à 10M.
Avec IVF, disons qu'on divise les données en 100 partitions, chacune avec son centroïde et environ 100k points de données.
La complexité en temps est alors proportionnelle à 100 + 100k = 100 100, soit presque 100 fois plus rapide. (D est un facteur commun aux deux méthodes, on peut donc l'ignorer dans ce calcul.)
LE COMPROMIS
Le prix à payer : la précision
Bien sûr, il faut garder en tête que si certains points de données sont en réalité proches du point de requête mais se trouvent dans la partition voisine, on les manque pendant la recherche, comme ci-dessous :

Mais ce compromis sur la précision, on l'accepte volontairement pour de meilleures performances d'exécution, et c'est précisément pour ça que ces techniques s'appellent « recherche approximative de plus proches voisins ».
À retenir : IVF accepte de rater parfois un voisin pour ne chercher que dans une partition au lieu de tout le jeu de données, et c'est ce compromis qui rend la recherche beaucoup plus rapide.
Et si c'est la fiabilité de ton kNN qui te pose problème plutôt que sa vitesse, j'ai détaillé deux techniques dans ce shot :
Envie d'aller plus loin ? DataXp t'attend : formations et parcours pour progresser en data science, machine learning et IA.
👉 Et maintenant, à toi de jouer : dans quel projet à toi accepterais-tu d'échanger un peu de précision contre une recherche presque 100 fois plus rapide, et dans quel projet refuserais-tu ce compromis ?


