Qu'est-ce que la recherche par approximation des plus proches voisins (ANN) ?
Qu'est-ce que la recherche par approximation des plus proches voisins (ANN) ?
La recherche du plus proche voisin approximatif est une technique puissante dans l'apprentissage automatique (ML) et les pipelines de science des données qui permet une recherche efficace de similarité sémantique dans les grands ensembles de données que l'on trouve souvent dans les bases de données vectorielles comme Zilliz. ANNS est une méthode permettant de trouver le plus proche voisin d'un point de requête donné dans un grand ensemble de données de points à l'aide de divers algorithmes d'approximation du plus proche voisin. ANNS vise à trouver un voisin approximatif le plus proche avec une probabilité élevée tout en minimisant le coût de calcul. ANNS navigue intelligemment dans l'espace de recherche pour localiser efficacement les correspondances approximatives, ce qui améliore considérablement les performances par rapport aux recherches exhaustives.
L'algorithme standard de recherche du plus proche voisin (recherche NN) est une recherche exhaustive qui vérifie la distance entre le point d'interrogation et tous les autres points de l'ensemble de données. Cependant, cette méthode peut s'avérer coûteuse en termes de calcul et infaisable pour les grands ensembles de données. ANNS est une solution à ce problème qui utilise une structure de données ou un algorithme pour réduire les calculs de distance nécessaires.
Introduction à ANNS
La recherche approximative du plus proche voisin (ANNS) (https://docs.zilliz.com/docs/ann-search-explained)) est une technique utilisée dans les pipelines d'apprentissage automatique et de science des données pour la recherche efficace de similarités sémantiques dans de grands ensembles de données. ANNS fonctionne dans un espace vectoriel, qui est une représentation mathématique de données à haute dimension utilisée pour effectuer des recherches de similarité efficaces. ANNS vise à trouver un voisin approximatif le plus proche avec une probabilité élevée tout en minimisant les coûts de calcul. Cette approche est particulièrement utile lorsqu'il s'agit de données à haute dimension, pour lesquelles la recherche exacte du plus proche voisin peut s'avérer coûteuse en termes de calcul et peu pratique. En exploitant ANNS, nous pouvons atteindre un équilibre entre la précision et l'efficacité, ce qui en fait un outil précieux pour les applications qui nécessitent une recherche de similarité rapide et fiable.
Évolution des algorithmes de recherche
L'évolution des algorithmes de recherche a été un processus continu, avec l'émergence de diverses techniques pour relever les défis posés par le traitement d'ensembles de données vastes et complexes. Les méthodes de recherche traditionnelles, telles que la recherche exacte du plus proche voisin, étaient initialement utilisées pour trouver les points de données les plus proches d'un point d'interrogation donné. Toutefois, ces méthodes étaient coûteuses en termes de calcul et peu pratiques pour les données à haute dimension. Le développement d'algorithmes de recherche approximative du plus proche voisin (ANN) a marqué une étape importante dans l'évolution des algorithmes de recherche. Les algorithmes ANN, tels que locality-sensitive hashing (LSH) et KD-trees, ont été conçus pour rechercher efficacement les plus proches voisins approximatifs dans des espaces de haute dimension. Ces algorithmes ont été largement adoptés dans diverses applications, notamment la reconnaissance d'images, le traitement du langage naturel et les systèmes de recommandation.
Différences entre NN, ANN et KNN
Ce qui suit clarifie les différences entre le plus proche voisin (NN), le plus proche voisin approximatif (ANN) et le K-Plus proche voisin (KNN) :
- Voisin le plus proche (NN) :
Le NN est un algorithme de base utilisé pour les tâches de classification et de régression.
Il permet de trouver le point de données le plus proche (voisin) d'un point d'interrogation donné sur la base d'une métrique de distance (par exemple, la distance euclidienne).
La classe ou la valeur du point d'interrogation est déterminée par la classe ou la valeur de son voisin le plus proche.
Le NN est un algorithme simple et intuitif, mais il peut s'avérer coûteux en termes de calcul pour les grands ensembles de données.
- Voisin le plus proche approximatif (ANN) :
ANN est une variante de l'algorithme du plus proche voisin qui vise à trouver des voisins approximatifs plutôt qu'exacts.
Il est utilisé lorsque l'ensemble de données est très volumineux et que la recherche des voisins les plus proches exacts est coûteuse en termes de calcul ou irréalisable.
Les algorithmes ANN sacrifient une partie de la précision au profit de la vitesse et de l'efficacité.
Ils utilisent des techniques telles que le hachage sensible à la localité (LSH) ou des structures arborescentes pour trouver rapidement les voisins les plus proches.
Les algorithmes ANN recherchent des partitions multiples basées sur le vecteur d'interrogation afin d'atténuer la perte de précision.
Les algorithmes ANN sont utiles dans les scénarios où un résultat approximatif est suffisant et où l'ensemble de données est trop volumineux pour une recherche exacte des plus proches voisins.
- K-Voisins les plus proches (KNN) :
Le KNN est une extension de l'algorithme du plus proche voisin qui prend en compte les K plus proches voisins au lieu d'un seul.
Il identifie les K points de données les plus similaires dans l'espace des caractéristiques, la similarité étant mesurée à l'aide d'une fonction de distance choisie.
La classe ou la valeur du point de requête est déterminée par la classe majoritaire ou la valeur moyenne de ses K plus proches voisins.
Le KNN est un algorithme non paramétrique et peut être utilisé pour des tâches de classification et de régression.
Le choix de K est important et peut avoir un impact sur les performances et la généralisation de l'algorithme.
Les principales différences entre ces algorithmes sont les suivantes :
NN ne prend en compte qu'un seul voisin le plus proche, tandis que KNN prend en compte K voisins les plus proches.
ANN se concentre sur la recherche efficace des plus proches voisins, sacrifiant une partie de la précision à la rapidité.
KNN est un algorithme plus général qui peut être utilisé pour la classification et la régression, tandis que NN et ANN sont principalement utilisés pour la recherche du plus proche voisin.
Fondamentalement, NN recherche le plus proche voisin, ANN recherche les plus proches voisins de manière efficace et KNN considère K plus proches voisins pour les tâches de classification ou de régression.
Motivation pour les plus proches voisins
Le plus proche voisin est un concept fondamental de l'apprentissage automatique et de la science des données, utilisé dans diverses applications telles que la reconnaissance d'images, le traitement du langage naturel et les systèmes de recommandation. Ces algorithmes utilisent des vecteurs de requête pour représenter les demandes de recherche, qui sont ensuite comparées aux points de données de l'ensemble de données pour trouver les plus similaires. La motivation des algorithmes du plus proche voisin est de trouver les points de données les plus similaires à un point d'interrogation donné, ce qui peut être utilisé pour la classification, la régression et d'autres tâches. Cependant, à mesure que les ensembles de données augmentent en taille et en dimensionnalité, la recherche exacte du plus proche voisin devient de plus en plus difficile. Le coût informatique de la vérification de chaque point de données dans un grand ensemble de données peut être prohibitif, ce qui fait de l'ANNS une solution précieuse. L'ANNS permet de trouver efficacement des points de données similaires sans avoir recours à une recherche exhaustive, ce qui permet de créer des applications d'apprentissage automatique évolutives et performantes.
Mécanisme des plus proches voisins approximatifs
Les algorithmes de recherche par approximation du plus proche voisin (ANN) fonctionnent en cartographiant les points de données dans un espace à haute dimension et en identifiant rapidement les points les plus proches d'un point d'interrogation. La clé de l'efficacité de l'ANN réside dans l'utilisation d'algorithmes tels que le hachage sensible à la localité (LSH), qui place les éléments similaires dans le même bac, réduisant ainsi considérablement le temps de recherche. Contrairement aux méthodes de recherche exhaustive qui évaluent tous les autres points de l'ensemble de données, l'ANN utilise une approche plus efficace. Cette approche implique souvent des méthodes basées sur les graphes, où les points de données sont des nœuds dans un graphe, et la recherche des voisins les plus proches devient un problème de recherche de chemin dans ce graphe. Les mécanismes de la recherche ANN impliquent plusieurs composants clés, notamment le prétraitement des données, la construction d'un index et l'exécution de la requête.
Quand utiliser la recherche approximative du plus proche voisin ?
Les techniques de recherche par approximation du plus proche voisin trouvent des applications dans divers domaines, notamment les systèmes de recommandation, la reconnaissance d'images et de sons, le traitement du langage naturel (NLP) et la génération augmentée de recherche (RAG). Les [recherches vectorielles] (https://zilliz.com/learn/vector-similarity-search) sont essentielles dans ces applications, car elles permettent de retrouver efficacement des éléments similaires sur la base de leurs représentations vectorielles. Les méthodes ANNS peuvent fournir des solutions approximatives qui restent suffisamment précises pour de nombreuses applications, même lorsqu'il s'agit de grands ensembles de données.
Algorithmes ANNS courants
Les algorithmes ANNS utilisent une variété de structures de données et d'algorithmes d'approximation du plus proche voisin conçus pour optimiser le processus de recherche. Parmi les algorithmes ANNS les plus répandus figurent les arbres KD, le [hachage sensible à la localité] (https://zilliz.com/learn/mastering-locality-sensitive-hashing-a-comprehensive-tutorial) (LSH) et la [quantification de produit] (https://zilliz.com/learn/harnessing-product-quantization-for-memory-efficiency-in-vector-databases). Les arbres KD sont couramment utilisés dans les espaces de faible dimension, tandis que LSH est préféré pour les espaces de haute dimension. La [quantification de produit] (https://zilliz.com/learn/scalar-quantization-and-product-quantization) est une technique qui divise l'espace des caractéristiques en sous-espaces et comprime chaque sous-espace dans un petit livre de codes.
L'ensemble de données est divisé en une structure arborescente en arbres KD, où chaque nœud représente une région de points. L'algorithme parcourt l'arbre au cours du processus de recherche, en vérifiant les zones les plus proches du point interrogé. En revanche, LSH regroupe les points similaires dans le même bac, ce qui permet d'extraire rapidement les voisins les plus proches. La quantification par produit vérifie les codes de chaque sous-espace pour trouver le plus proche voisin approximatif.
L'efficacité avec laquelle les algorithmes ANNS peuvent trouver le plus proche voisin approximatif les rend populaires dans diverses applications. Dans les systèmes de recommandation, les algorithmes ANNS peuvent être utilisés pour trouver efficacement des articles ou des utilisateurs similaires. Les algorithmes ANNS peuvent aider à trouver des images et des sons correspondants dans le cadre de la reconnaissance d'images et de sons. Dans le traitement du langage naturel, les algorithmes ANNS peuvent trouver des documents ou des phrases similaires.
Choisir le bon algorithme ANNS
Le choix des algorithmes de plus proche voisin dépend de plusieurs facteurs, notamment de la taille et de la dimensionnalité de l'ensemble de données, du niveau de précision souhaité et des ressources informatiques disponibles. Parmi les algorithmes ANNS les plus répandus, citons les arbres KD, le hachage sensible à la localité (LSH) et la quantification par produit. Les arbres KD conviennent aux données de faible dimension et aux requêtes basées sur la distance euclidienne, tandis que LSH est préférable pour les données de haute dimension et les requêtes basées sur la [similarité cosinusienne] (https://zilliz.com/blog/similarity-metrics-for-vector-search). La quantification par produit est une technique qui divise l'espace des caractéristiques en sous-espaces et comprime chaque sous-espace dans un petit livre de codes. Chacun de ces algorithmes a ses points forts et ses inconvénients, de sorte que le choix de l'algorithme approprié nécessite un examen attentif des exigences spécifiques de votre application.
Implémentation de l'ANNS dans votre application
La mise en œuvre du système ANNS dans votre application comporte plusieurs étapes, notamment le prétraitement des données, la construction de l'index et l'exécution de la requête. Le prétraitement des données consiste à transformer les données dans un format adapté au système ANNS, par exemple en normalisant les vecteurs ou en [réduisant la dimensionnalité] (https://zilliz.com/glossary/dimensionality-reduction). La construction de l'index implique la création d'une structure de données permettant une recherche efficace, telle qu'un arbre KD ou une table de hachage. L'exécution de la requête consiste à rechercher dans l'index les voisins approximatifs les plus proches d'un point d'interrogation donné à l'aide de vecteurs d'interrogation. Plusieurs bibliothèques et frameworks, tels que [FAISS] (https://zilliz.com/learn/faiss) et Annoy, fournissent des implémentations efficaces des algorithmes ANNS qui peuvent être facilement intégrés dans votre application. En suivant ces étapes, vous pouvez exploiter la puissance de l'ANNS pour construire des systèmes de recherche de similarités évolutifs et efficaces.
Quand utiliser la recherche approximative du plus proche voisin ?
Lorsqu'il s'agit de données de haute dimension, la recherche du plus proche voisin exact peut s'avérer coûteuse en termes de calcul et n'est pas nécessaire. Dans la recherche vectorielle, les données sont représentées dans un espace vectoriel, ce qui permet d'effectuer des recherches de similarité efficaces dans des ensembles de données à haute dimension. Dans ce cas, la recherche approximative du plus proche voisin réduit considérablement le temps de recherche tout en fournissant un résultat raisonnablement précis. La recherche approximative du plus proche voisin est couramment utilisée dans des applications telles que la reconnaissance d'images et de la parole, les systèmes de recommandation et le traitement du langage naturel.
Importance de l'ANNS dans la recherche vectorielle
La recherche vectorielle est un élément essentiel de nombreuses applications d'apprentissage automatique, dans lesquelles les données sont représentées sous forme de [vecteurs denses] (https://zilliz.com/learn/dense-vector-in-ai-maximize-data-potential-in-machine-learning) dans des espaces à haute dimension. Les recherches vectorielles font partie intégrante de ces applications, car elles permettent d'extraire rapidement et précisément des éléments similaires sur la base de leurs représentations vectorielles. ANNS joue un rôle crucial dans la recherche vectorielle en permettant la récupération rapide et efficace de vecteurs similaires dans des ensembles de données massifs. En utilisant ANNS, les développeurs peuvent construire des systèmes de recherche vectorielle évolutifs et performants, capables de traiter de grands volumes de données et de fournir des résultats précis en temps réel. Cette capacité est essentielle pour des applications telles que les systèmes de recommandation, la reconnaissance d'images et de sons, et le traitement du langage naturel, où la rapidité et la fiabilité de la recherche de similarités sont primordiales.
La recherche approximative du plus proche voisin dans les applications du monde réel
La recherche approximative du plus proche voisin (ANN) a de nombreuses applications dans le monde réel. Dans le domaine de la reconnaissance d'images, l'ANN permet d'identifier rapidement les images présentant des caractéristiques similaires à partir d'un vaste ensemble de données. Dans les services d'écoute de musique en continu, l'ANN peut être utilisé pour recommander des chansons qui correspondent aux préférences d'un utilisateur, même si elles ne sont pas exactement identiques. Dans le domaine de la santé, l'ANN permet d'identifier rapidement les images diagnostiques similaires à une requête, améliorant ainsi la rapidité et la précision des diagnostics des patients. L'ANN est également utilisé dans le traitement du langage naturel, les systèmes de recommandation et la génération augmentée de recherche (RAG). L'efficacité de la recherche ANN dans ces applications est démontrée par sa capacité à traiter des structures de données complexes et à s'adapter à l'évolution de la taille des données.
Meilleures pratiques pour la mise en œuvre de la recherche par approximation du plus proche voisin
La mise en œuvre de la recherche par approximation du plus proche voisin (ANN) nécessite la prise en compte de plusieurs facteurs. Tout d'abord, il est essentiel de choisir l'algorithme ANN adapté au cas d'utilisation spécifique. Les différents algorithmes, tels que LSH et KD-trees, ont leurs points forts et leurs inconvénients, et le choix de l'algorithme approprié nécessite de prendre en compte les exigences spécifiques de l'application. Deuxièmement, le prétraitement des données est crucial pour la recherche d'ANN. Il s'agit de transformer les données dans un format adapté à l'ANN, par exemple en normalisant les vecteurs ou en réduisant la dimensionnalité. Troisièmement, la création d'un index est une étape critique de la recherche ANN. Il s'agit de créer une structure de données permettant une recherche efficace, telle qu'un arbre KD ou une table de hachage. Enfin, l'exécution de la requête consiste à rechercher dans l'index les voisins approximatifs les plus proches d'un point d'interrogation donné.
L'avenir de la recherche des plus proches voisins approximatifs
L'avenir de la recherche par approximation du plus proche voisin (ANN) est prometteur, grâce aux recherches et aux développements en cours dans ce domaine. L'un des domaines de recherche est le développement d'algorithmes ANN plus efficaces, capables de traiter des ensembles de données encore plus vastes et plus complexes. Un autre domaine de recherche est l'application de la recherche ANN dans des domaines émergents, tels que les véhicules autonomes et la robotique. En outre, l'utilisation croissante de la recherche vectorielle dans diverses applications devrait stimuler la demande d'algorithmes ANN plus efficaces et évolutifs. Au fur et à mesure que le domaine continue d'évoluer, nous pouvons nous attendre à voir davantage d'applications innovantes de la recherche ANN dans divers secteurs et domaines.
Résumé de la recherche par approximation du plus proche voisin
En conclusion, les algorithmes de recherche approximative du plus proche voisin sont des outils précieux pour la science des données et les pipelines d'apprentissage automatique. En utilisant des structures de données et des algorithmes astucieux, la recherche approximative du plus proche voisin peut fournir des solutions réalisables sur le plan du calcul, tout en restant suffisamment précises pour de nombreuses applications. En outre, les techniques ANNS sont largement applicables et permettent une recherche efficace du plus proche voisin dans de grands ensembles de données.
- Introduction à ANNS
- Évolution des algorithmes de recherche
- Différences entre NN, ANN et KNN
- Motivation pour les plus proches voisins
- Mécanisme des plus proches voisins approximatifs
- Quand utiliser la recherche approximative du plus proche voisin ?
- Algorithmes ANNS courants
- Choisir le bon algorithme ANNS
- Implémentation de l'ANNS dans votre application
- Quand utiliser la recherche approximative du plus proche voisin ?
- Importance de l'ANNS dans la recherche vectorielle
- La recherche approximative du plus proche voisin dans les applications du monde réel
- Meilleures pratiques pour la mise en œuvre de la recherche par approximation du plus proche voisin
- L'avenir de la recherche des plus proches voisins approximatifs
- Résumé de la recherche par approximation du plus proche voisin
Contenu
Commencez gratuitement, évoluez facilement
Essayez la base de données vectorielle entièrement managée conçue pour vos applications GenAI.
Essayer Zilliz Cloud gratuitement