Comprendre l'algorithme du plus proche voisin approximatif

La méthode de recherche du plus proche voisin approximatif (ANN) est un algorithme qui trouve, dans un ensemble de données, un point de données très proche d'un point de requête précis, mais qui n'est pas nécessairement le plus proche. Alors qu'un algorithme NN effectue des recherches de manière exhaustive dans toute la base de données pour trouver la correspondance parfaite, l'algorithme ANN se contente d'identifier une correspondance suffisamment proche.

Cette solution n'est pas pour autant moins bonne : elle est en réalité essentielle pour effectuer des recherches de similarités rapides. La méthode ANN utilise des structures de données et des raccourcis intelligents pour naviguer efficacement dans l'espace de recherche. Elle identifie, beaucoup plus facilement et sans demander énormément de temps et de ressources, les points de données qui sont suffisamment proches pour être utiles dans la plupart des scénarios pratiques.

Il s'agit là d'un compromis. La méthode NN est idéale si vous devez à tout prix trouver la meilleure correspondance, et si la vitesse et la performance ne sont pas vos priorités. La méthode ANN est quant à elle plus indiquée si vous pouvez tolérer une petite baisse de la précision.

Le fonctionnement des algorithmes ANN repose tout d'abord sur une réduction de la dimensionnalité, qui consiste à transformer un ensemble de données de plus grande dimensionnalité en un ensemble de plus petite dimensionnalité. L'objectif ? Simplifier la tâche du modèle prédictif et la rendre plus efficace plutôt que de devoir analyser toutes les données.

Ces algorithmes reposent sur le concept mathématique des espaces métriques, au sein desquels se trouvent des points de données et où des distances entre ces points sont définies. Ces dernières doivent respecter des règles précises (non-négativité, identité, symétrie, inégalité triangulaire) et sont calculées à l'aide de fonctions courantes telles que la distance euclidienne ou la similarité cosinus.

Ce n'est pas très clair ? Alors, imaginez que vous êtes en vacances et vous cherchez la villa que vous avez louée. Plutôt que de regarder chaque logement un par un (dimensionnalité plus grande), vous utilisez une carte, qui réduit le problème en deux dimensions (dimensionnalité plus petite). (Nous avons délibérément pris un exemple simple. Les algorithmes ANN emploient d'autres méthodes que la réduction de la dimensionnalité pour améliorer leur efficacité.)

Les algorithmes ANN exploitent également des données de structures intelligentes appelées indexer pour gagner en efficacité. Grâce au pré-traitement des données dans ces index, les algorithmes ANN peuvent naviguer plus rapidement dans l'espace de recherche. Tels des panneaux de signalisation, ils vous aident à trouver votre localisation sur une carte pour retrouver plus rapidement la villa de vos vacances.

Face à l'évolution rapide du monde de la science des données, l'efficacité est reine. Si la recherche du plus proche voisin véritable (recherche exacte du plus proche voisin) est intéressante, elle a souvent un coût informatique, comme nous l'avons déjà évoqué. C'est là que la recherche ANN tire son épingle du jeu, en offrant un compromis convaincant : une vitesse fulgurante couplée à une précision élevée, mais pas absolue.

Mais alors, quand faut-il opter pour la recherche ANN plutôt que les autres méthodes de recherche ?

Bien que la recherche exacte du plus proche voisin soit lente, c'est la meilleure option si la précision est votre priorité ou si vous utilisez de petits ensembles de données. La recherche des k plus proches voisins (kNN) est un bon compromis entre la recherche NN et la recherche ANN, car elle vous permet d'obtenir des résultats rapidement, sans rogner sur la précision. Il n'est cependant pas évident de déterminer la valeur du k et cette méthode peut rencontrer des difficultés avec des données de grande dimensionnalité.

Grâce à sa vitesse et son efficacité, combinées à sa précision élevée (mais pas absolue), la recherche ANN est idéale pour de nombreuses situations :

• Ensembles de données volumineux : la nature exhaustive de la recherche exacte NN explique sa lenteur au moment de brasser des millions voire des milliards de points de données. La recherche ANN excelle dans les environnements de données volumineux en fournissant rapidement des résultats ;

• Données de grande dimensionnalité : l'augmentation de la dimensionnalité s'accompagne d'une explosion des calculs de recherche exacte des NN. Les techniques de réduction de la dimensionnalité de la recherche ANN réduisent significativement l'espace de recherche et permettent de gagner en efficacité dans les données complexes, comme les images ou le texte ;

• Applications en temps réel : si vous avez besoin de résultats immédiats, sachez que les systèmes de recommandation, la détection de la fraude et la détection des anomalies reposent sur les informations exploitables en temps réel. De par sa vitesse, la recherche ANN est l'outil idéal pour ces scénarios.

• Approximation acceptable : la vitesse de la recherche ANN s'avère inestimable si votre application peut tolérer de petites inexactitudes dans les résultats. Pour ce qui est de la recherche d'images par exemple, trouver des images visuellement similaires plutôt que des images les plus proches possibles, peut s'avérer suffisant.

La recherche vectorielle traite des données encodées sous forme de vecteurs denses en capturant des relations complexes et des significations intégrées. Cela en fait l'outil idéal pour la recherche de contenus tels que des images, du texte et les préférences des utilisateurs, lorsque la recherche traditionnelle fondée sur les mots-clés ne répond pas aux attentes. Toutefois, la malédiction de la dimensionnalité s'applique ici également. En effet, avec l'augmentation du nombre de dimensions représentant ces vecteurs, les méthodes de recherche traditionnelles éprouvent des difficultés, elles deviennent plus lentes et perdent en efficacité.

L'algorithme ANN résout ce problème en cherchant des correspondances "suffisamment proches" plutôt que des correspondances exactes. Ceci permet une récupération rapide, votre recherche vectorielle pouvant trouver des vecteurs similaires dans des ensembles de données en un claquement de doigts. Vous bénéficiez aussi d'une scalabilité intégrée, grâce à laquelle vous pouvez faire grossir votre ensemble de données autant que vous le souhaitez sans faire une croix sur la vitesse.

En misant sur ces réponses en temps réel ainsi que sur une pertinence et une efficacité accrues, la méthode ANN joue souvent un rôle clé dans la pleine exploitation du véritable potentiel de vos recherches vectorielles.

Le concept d'ANN offre un avantage indéniable en termes de vitesse de recherche, mais ce terme englobe en réalité de nombreux types d'algorithmes, qui ont tous leurs avantages et leurs inconvénients. Il est donc essentiel de comprendre leurs différences pour choisir l'outil le plus adapté à vos besoins spécifiques de recherche et de données.

Les arbres kd organisent les points de données dans une structure d'arborescence hiérarchique, divisant en partitions l'espace selon des dimensions spécifiques. Ceci permet des recherches rapides et efficaces dans les espaces à faible dimensionnalité et les requêtes basées sur la distance euclidienne.

Si les arbres kb excellent dans la recherche des plus proches voisins dans de petites dimensions, ils souffrent d'une "malédiction de la dimensionnalité". Ainsi, lorsque le nombre de dimensions augmente, l'espace entre les points explose. Dans ces grandes dimensions, la stratégie de division des arbres kb fondée sur des axes uniques devient inefficace. La recherche porte alors sur la plupart des données, ce qui lui fait perdre son avantage en matière d'efficacité. Elle met presque autant de temps qu'un simple balayage linéaire de tous les points.

Puissante technique de recherche ANN, le LSH "hache" les points de données dans des espaces de plus petite dimensionnalité de façon à préserver intelligemment leurs relations de similarité. Ce clustering les rend plus faciles à trouver et permet au LSH d'exceller dans la recherche d'ensembles de données massifs et de grande dimensionnalité, tels que des images ou du texte, avec vitesse et scalabilité, tout en renvoyant des correspondances "suffisamment proches" de manière assez précise. Le LSH peut cependant occasionnellement produire des faux positifs (c'est-à-dire, trouver des points soi-disant similaires alors qu'ils ne le sont pas). Son efficacité peut également varier selon la distance et le type de données. Il existe plusieurs familles de LSH conçues pour fonctionner avec différentes métriques (par exemple, la distance euclidienne, la similarité de Jaccard), ce qui fait du LSH une technique polyvalente.

Annoy (Approximate Nearest Neighbors Oh Yeah) est bien plus qu'un simple algorithme. C'est une bibliothèque open source en C++, qui utilise ses propres algorithmes pour créer et interroger des arbres, sans directement mettre en œuvre le LSH ou des arbres kb. Annoy est conçue pour des recherches rapides et peu gourmandes en mémoire dans les espaces de grande dimensionnalité, ce qui en fait un outil particulièrement adapté pour les requêtes en temps réel. C'est une interface conviviale qui offre une certaine flexibilité pour différents types de données et scénarios de recherche. La force d'Annoy réside dans l'exploitation de plusieurs approches ANN en un seul et même endroit, ce qui vous permet de choisir celle qui correspond le mieux à vos besoins. Si cela simplifie le processus, il convient toutefois de souligner que le choix du bon algorithme interne dans Annoy est essentiel pour une performance optimale et que son efficacité dépend toujours de facteurs tels que vos données et vos exigences en matière de précision.

Bien qu'il ne soit généralement pas considéré comme une technique ANN, le balayage linéaire a toute sa place en raison de son approche par force brute qui vous permet d'obtenir des résultats similaires à d'autres algorithmes. Il effectue des itérations de chaque point de données en séquence, calculant les distances entre les enregistrements et gardant une trace des meilleures correspondances. Plutôt simple, cet algorithme est facile à mettre en œuvre et idéal pour les petits ensembles de données. Il présente cependant plusieurs inconvénients en raison de son approche plus basique : il est inefficace pour les grands ensembles de données, lent lorsqu'il est utilisé avec des données de grande dimensionnalité et peu pratique pour les applications en temps réel.

Voici quelques éléments à prendre en compte avant de choisir une méthode ANN :

• la taille de l'ensemble de données et la dimensionnalité : envisagez de recourir au Locality-Sensitive Hashing pour les ensembles de données volumineux et de grande dimensionnalité, et aux arbres kb pour les ensembles de données de plus petite taille et de plus petite dimensionnalité ;

• le niveau de précision recherché : si vous recherchez la précision absolue, le balayage linéaire est la meilleure option. Si vous recherchez plutôt de la vitesse et une bonne précision, tournez-vous vers le LSH ou Annoy ;

• les ressources informatiques : Annoy offre une certaine flexibilité, mais n'hésitez pas à prendre en compte les limites de mémoire et de traitement avant de choisir un algorithme de la bibliothèque.

Il n'existe aucune solution universelle, d'où la nécessité de tester différents algorithmes et d'évaluer leurs performances par rapport à vos données spécifiques pour trouver la solution adaptée à vos besoins de recherche vectorielle. Outre la multitude d'options qui existent, le monde des algorithmes ANN est en constante évolution. Soyez donc aux aguets pour ne pas passer à côté d'une nouveauté susceptible d'améliorer vos recherches.

Face à l'immensité et à la complexité du monde des données, des outils efficaces sont nécessaires pour ne pas s'y perdre. Dans ce contexte, la méthode ANN peut être l'allié secret qui améliorera vos recherches de similarités. Malgré un léger compromis sur la précision, elle offre vitesse et scalabilité. Chaque semaine, les recherches en cours aboutissent à des avancées, ce qui contribuera à la nature dynamique de l'espace ANN. Les progrès réalisés dans le domaine de l'informatique quantique et du Machine Learning pourraient ainsi donner lieu à de nouveaux types d'algorithmes ANN encore plus rapides et efficaces.

Nous avons abordé différents algorithmes ANN, chacun ayant ses avantages et ses inconvénients. Mais en fin de compte, l'algorithme le plus approprié dépend de vos besoins spécifiques. Il convient donc de prendre en compte des facteurs tels que la taille et la dimensionnalité des données, les exigences en matière de précision et les ressources. N'hésitez pas à tester plusieurs algorithmes pour choisir celui qui vous permettra de tirer pleinement parti des ANN. De la recherche d'images à la détection de la fraude, ces algorithmes peuvent faire une grande différence en révélant des connexions secrètes et en permettant d'obtenir rapidement des informations exploitables basées sur des données. 

Alors, la prochaine fois que vous recherchez une nouvelle chanson à écouter, un nouveau film à regarder ou un nouveau jeu vidéo auquel jouer, pensez aux algorithmes ANN, sans lesquels tout ceci serait impossible.

Pour aller plus loin, voici quatre méthodes qui vous aideront à révéler des informations exploitables à partir des données de votre entreprise :

1. Démarrez un essai gratuit et découvrez l'aide qu'Elastic peut apporter à votre entreprise.

2. Faites le tour de nos offres afin de savoir comment Elasticsearch Platform fonctionne et comment nos solutions s'adaptent à vos besoins.

3. Découvrez comment intégrer l'IA générative dans votre entreprise.

4. Partagez cet article avec une personne de votre réseau qui pourrait être intéressée par son contenu. Partagez cet article par e-mail, sur LinkedIn, sur Twitter ou sur Facebook.