Comment utiliser la bibliothèque Annoy de Spotify en Python pour une recherche de similarité de vecteurs
Published on
![Découvrez comment Annoy, l'algorithme Oh Yeah des voisins les plus proches approximatifs, révolutionne les recherches de voisins les plus proches en Python. Apprenez ses concepts fondamentaux, comment l'implémenter et pourquoi c'est le choix privilégié des professionnels de l'apprentissage automatique.](/_next/image?url=https%3A%2F%2Fraw.githubusercontent.com%2Flynn-mikami%2FImages%2Fmain%2Fannoy-python-spotify.webp%3Fx-oss-process%3Dimage%2Fresize%2Climit_0%2Cm_fill%2Cw_1536%2Ch_1024%2Fquality%2Cq_100&w=3840&q=75)
En avez-vous marre des recherches de voisins les plus proches lentes et inefficaces dans vos projets d'apprentissage automatique ? Souhaitez-vous qu'il existe un moyen d'accélérer cette étape cruciale sans sacrifier trop de précision ? Eh bien, votre souhait est sur le point de se réaliser. Bienvenue dans le monde d'Approximate Nearest Neighbor Oh Yeah (Annoy), une bibliothèque Python qui fait sensation dans la communauté de l'apprentissage automatique.
Dans ce guide complet, nous plongerons profondément dans Annoy, en explorant son fonctionnement interne, son implémentation Python et pourquoi il devient rapidement le choix privilégié des professionnels du domaine. Attachez vos ceintures, car nous allons faire un voyage palpitant à travers le paysage des recherches de voisins les plus proches rapides et efficaces.
Qu'est-ce que Approximate Nearest Neighbor Oh Yeah (Annoy) ?
Avant de plonger dans les détails techniques, clarifions nos définitions. Approximate Nearest Neighbor Oh Yeah (Annoy) est un algorithme conçu pour gérer les recherches de voisins les plus proches de manière plus efficace. Contrairement aux méthodes traditionnelles qui effectuent des recherches exhaustives, Annoy utilise une structure de données astucieuse - les arbres binaires de recherche - pour partitionner l'espace de recherche et accélérer le processus.
- Méthodes traditionnelles : Recherches lentes et exhaustives.
- Annoy : Recherches rapides et approximatives en utilisant des arbres binaires de recherche.
Quels sont les avantages d'Annoy ?
Vous vous demandez peut-être pourquoi vous devriez opter pour Annoy alors qu'il existe d'autres algorithmes et bibliothèques disponibles pour la recherche de voisins les plus proches. Voici quelques raisons convaincantes :
- Rapidité : Annoy est incroyablement rapide, grâce à son utilisation efficace des arbres binaires de recherche.
- Efficacité en mémoire : Annoy utilise un fichier mappé en mémoire, ce qui permet à plusieurs processus de partager les mêmes données.
- Flexibilité : Annoy prend en charge différentes métriques de distance comme l'euclidienne, la manhattan et l'angulaire.
- Facilité d'utilisation : Avec sa bibliothèque Python, l'implémentation d'Annoy est un jeu d'enfant.
Comment fonctionne Annoy ?
Maintenant que nous savons ce qu'est Annoy, plongeons dans son fonctionnement réel. Au cœur d'Annoy se trouve une structure de données appelée arbre binaire de recherche qui partitionne l'espace vectoriel. Cela est fondamentalement différent des méthodes traditionnelles qui utilisent des graphes connectés ou des recherches exhaustives.
La structure de données centrale : les arbres binaires de recherche
Dans Annoy, chaque nœud de l'arbre binaire de recherche représente un vecteur dans l'ensemble de données. L'arbre est construit en partitionnant de manière récursive l'espace vectoriel en deux moitiés. Cette partition est effectuée à l'aide de plans hyperplans qui sont équidistants entre deux vecteurs sélectionnés au hasard dans l'ensemble de données.
- Hyperplans : Utilisés pour partitionner l'espace vectoriel.
- Vecteurs aléatoires : Deux vecteurs sont sélectionnés au hasard pour définir chaque hyperplan.
Par exemple, supposons que nous ayons les vecteurs (A) et (B). Un hyperplan équidistant de (A) et (B) divisera l'espace en deux moitiés. Tous les vecteurs plus proches de (A) iront dans le sous-arbre gauche, et ceux plus proches de (B) iront dans le sous-arbre droit.
Partitionnement récursif : le génie derrière Annoy
La véritable magie opère pendant le partitionnement récursif de l'espace vectoriel. Chaque nœud de l'arbre est associé à un hyperplan qui divise l'espace en deux. Ce processus est répété pour chacun des nœuds enfants, partitionnant ainsi davantage l'espace jusqu'à ce que chaque nœud feuille contienne moins d'un certain nombre prédéfini d'éléments, disons (K).
- Nœuds feuilles : Contiennent moins de (K) éléments.
- (K) : Un paramètre défini par l'utilisateur qui contrôle la granularité du partitionnement.
En utilisant cette structure d'arbre, Annoy peut rapidement identifier dans quelle partition tombe un vecteur de requête, réduisant ainsi le nombre de vecteurs avec lesquels il doit être comparé. C'est ce qui rend Annoy si rapide et efficace.
Indexation dans Annoy : Un guide étape par étape
Après avoir compris les concepts fondamentaux d'Annoy, il est temps de mettre les mains dans le cambouis avec une véritable implémentation. L'indexation est la première étape cruciale dans l'utilisation d'Annoy, et c'est là que la magie des arbres binaires de recherche entre en jeu.
Étape 1 : Installer la bibliothèque Annoy
Premièrement, vous devez installer la bibliothèque Annoy. Vous pouvez le faire facilement avec pip :
pip install annoy
Étape 2 : Importer la bibliothèque et initialiser l'index
Une fois installée, importez la bibliothèque et initialisez l'index Annoy. Voici comment faire :
from annoy import AnnoyIndex
# Initialiser l'index avec 40 dimensions
t = AnnoyIndex(40, 'angular')
- 40 : Le nombre de dimensions pour chaque vecteur.
- 'angular' : La métrique de distance utilisée (les distances euclidienne, de Manhattan et angulaire sont disponibles).
Étape 3 : Ajouter des éléments à l'index
Maintenant, ajoutez vos éléments (vecteurs) à l'index. Chaque élément est identifié par un ID entier.
# Ajouter trois vecteurs à l'index
t.add_item(0, [1.0, 2.1, 3.2, ...])
t.add_item(1, [4.5, 5.1, 6.3, ...])
t.add_item(2, [7.2, 8.1, 9.4, ...])
Étape 4 : Construire l'index
Après avoir ajouté tous vos éléments, construisez l'index. C'est là qu'Annoy construit les arbres binaires de recherche.
# Construire l'index avec 10 arbres
t.build(10)
- 10 : Le nombre d'arbres dans l'index. Plus il y a d'arbres, plus la précision est élevée, mais plus le temps de requête est lent.
Étape 5 : Enregistrer et charger l'index
Vous pouvez enregistrer l'index sur un disque et le charger ultérieurement pour les requêtes.
# Enregistrer l'index
t.save('my_index.ann')
# Charger l'index
u = AnnoyIndex(40, 'angular')
u.load('my_index.ann')
En suivant ces étapes, vous avez créé avec succès un index Annoy prêt pour des requêtes de voisinage les plus proches rapides et efficaces.
Comment interroger Annoy pour obtenir les voisins les plus proches ?
Une fois votre index construit, l'interrogation des voisins les plus proches est un jeu d'enfant. Les méthodes get_nns_by_item
et get_nns_by_vector
sont les fonctions à utiliser pour cela.
Utilisation de get_nns_by_item
Cette méthode permet de récupérer les voisins les plus proches d'un élément donné dans l'index.
# Trouver les 5 voisins les plus proches de l'élément 0
print(t.get_nns_by_item(0, 5))
Utilisation de get_nns_by_vector
Alternativement, vous pouvez trouver les voisins les plus proches d'un vecteur spécifique.
# Trouver les 5 voisins les plus proches du vecteur donné
print(t.get_nns_by_vector([1.0, 2.1, 3.2, ...], 5))
Les deux méthodes renvoient une liste d'identifiants d'éléments triés par leur distance par rapport à l'élément ou au vecteur de requête.
3 exemples d'utilisation d'Annoy avec Python
Exemple 1 : Initialisation de base et construction de l'index
Dans cet exemple, nous initialisons un index Annoy avec un ensemble de données et construisons l'index avec un nombre spécifié d'arbres. Il s'agit d'une utilisation courante pour la recherche de voisins les plus proches à grande échelle.
from annoy import AnnoyIndex
import os
import logging
def main(args):
data = Dataset(args.dataset)
f = data.base.shape[1]
t = AnnoyIndex(f)
idxpath = os.path.join(args.exp_dir, 'sift_annoy_ntrees%d.idx' % ntrees)
if not os.path.exists(idxpath):
logging.info("Ajout des éléments...")
for i in range(data.nbae):
t.add_item(i, data.base[i])
logging.info("Construction des index...")
t.build(ntrees)
logging.info("Enregistrement de l'index...")
t.save(idxpath)
Dans cet exemple, nous utilisons le logging pour suivre le processus. L'index est enregistré sur disque, ce qui permet un chargement rapide lors de futures exécutions.
Exemple 2 : Travailler avec des données clairsemées
Ici, nous montrons comment construire un index Annoy avec des données clairsemées. C'est particulièrement utile lorsque votre ensemble de données est de haute dimension mais clairsemé.
from annoy import AnnoyIndex
import numpy as np
from scipy.sparse import csr_matrix
import os
def test_build_sparse_annoy_index(annoy_index_file):
data = np.random.choice([0, 1], size=(10, 5))
sparse_data = csr_matrix(data)
index = AnnoyIndex(5, metric='angular')
index.load(annoy_index_file)
assert os.path.exists(annoy_index_file)
Dans cet exemple, nous utilisons la méthode csr_matrix
de la bibliothèque SciPy pour créer des données clairsemées. Nous chargeons ensuite un index Annoy existant à partir d'un fichier.
Exemple 3 : Utilisation d'Annoy dans les systèmes de recommandation
Dans cet exemple, nous intégrons Annoy dans un système de recommandation pour trouver rapidement des articles similaires.
import annoy
import logging
def fit(self, Ciu, show_progress=True):
super(AnnoyAlternatingLeastSquares, self).fit(Ciu, show_progress)
logging.debug("Construction de l'index des articles similaires avec Annoy")
self.similar_items_index = annoy.AnnoyIndex(self.item_factors.shape[1], 'angular')
for i, row in enumerate(self.item_factors):
self.similar_items_index.add_item(i, row)
self.similar_items_index.build(self.n_trees)
Ici, nous étendons une classe AnnoyAlternatingLeastSquares
et ajoutons une méthode pour construire un index Annoy pour les articles similaires. Cela permet au système de recommandation d'obtenir rapidement des articles similaires.
Conclusion : Annoy - La bibliothèque indispensable pour une recherche rapide et efficace des voisins les plus proches
En résumé, Annoy est un outil indispensable pour toute personne travaillant avec des ensembles de données volumineux et de grande dimension, et ayant besoin d'une recherche rapide et approximative des voisins les plus proches. Sa vitesse, son efficacité et sa facilité d'utilisation en font un choix privilégié pour une large gamme d'applications, des systèmes de recommandation au traitement du langage naturel et à la reconnaissance d'images. Bien qu'il ne puisse pas offrir la précision exacte de certains autres algorithmes, ses performances sont souvent largement suffisantes pour des applications réelles. Si vous souhaitez implémenter une recherche de voisins les plus proches dans votre projet, Annoy devrait certainement figurer sur votre liste.
Quels sont les principaux cas d'utilisation d'Annoy ?
Annoy est couramment utilisé dans les systèmes de recommandation, le traitement du langage naturel et les tâches de reconnaissance d'images. Sa capacité à trouver rapidement les voisins les plus proches approximatifs en fait un outil idéal pour ces applications.
Comment Annoy parvient-il à sa rapidité ?
Annoy utilise une forêt d'arbres, plus précisément des arbres de projection aléatoire, pour partitionner l'espace en régions plus petites. Cela lui permet d'éliminer rapidement de grandes portions de l'ensemble de données qui sont peu susceptibles de contenir les voisins les plus proches, ce qui se traduit par des temps de recherche plus rapides.
Annoy convient-il à tous les types de données ?
Annoy est particulièrement adapté aux données de haute dimension. Cependant, il peut également être utilisé pour des données de plus basse dimension. La clé est de choisir les bons paramètres, tels que le nombre d'arbres et le paramètre search_k, pour optimiser ses performances pour votre ensemble de données spécifique.
Comment Annoy se compare-t-il à d'autres algorithmes de voisins les plus proches ?
Annoy est généralement plus rapide et utilise moins de mémoire que d'autres algorithmes tels que les arbres K-D et les arbres de balles. Bien qu'il s'agisse d'un algorithme de voisins les plus proches approximatif, sa précision est souvent suffisante pour la plupart des applications réelles.
Puis-je utiliser Annoy avec d'autres langages que Python ?
Oui, Annoy dispose de bindings pour plusieurs autres langages tels que C++, Java et Lua. Cela le rend polyvalent et adapté à l'intégration dans différents types de projets.
Quelles sont quelques techniques avancées pour optimiser Annoy ?
Certaines techniques avancées consistent à utiliser une distance différente, à optimiser le nombre d'arbres pour votre cas d'utilisation spécifique et à utiliser des fichiers mappés en mémoire pour les ensembles de données volumineux. Celles-ci peuvent vous aider à obtenir des performances encore meilleures avec votre index Annoy.
Vous voulez vous tenir au courant des dernières actualités sur LLM ? Consultez le dernier classement LLM !