Application du hachage sensible à la localité dans la recherche approximative du voisin le plus proche

Locale Sensitive Hashing (LSH) est une méthode de recherche approximative du voisin le plus proche, particulièrement adaptée aux données dans un espace de grande dimension. Dans de nombreuses applications pratiques, telles que les données texte et image, la dimensionnalité des points de données peut être très élevée. Dans un espace de grande dimension, les méthodes traditionnelles de mesure de distance telles que la distance euclidienne ne sont plus efficaces et les méthodes de recherche linéaire traditionnelles sont inefficaces. Nous avons donc besoin d’algorithmes efficaces pour résoudre ce problème. L'idée de base de LSH est de mapper des points de données similaires à des compartiments de hachage similaires via une fonction de hachage. De cette façon, nous n'avons besoin que de rechercher dans des compartiments de hachage similaires au lieu de parcourir l'ensemble des données, améliorant ainsi considérablement l'efficacité de la recherche. Le cœur de l’algorithme LSH est de concevoir une fonction de hachage adaptée. La fonction de hachage doit avoir deux caractéristiques : premièrement, des points de données similaires ont une forte probabilité d'être mappés à des compartiments de hachage similaires, c'est-à-dire qu'ils ont une sensibilité locale. Deuxièmement, des points de données différents

hachage localement sensible (L'idée de base de ​​LSH consiste à mapper des points de données dans un espace de grande dimension vers un espace de basse dimension via une fonction de hachage, afin d'effectuer une recherche approximative du voisin le plus proche dans un espace de basse dimension. En introduisant des techniques de randomisation, LSH peut augmenter la probabilité que des points de données similaires soient mappés sur le même compartiment, réduisant ainsi l'espace de recherche. L’avantage de LSH est qu’il réduit considérablement l’espace de recherche tout en garantissant une certaine précision des requêtes, améliorant ainsi l’efficacité des requêtes.

LSH est largement utilisé, comme la recherche d'images similaires dans les moteurs de recherche, les recommandations de chansons similaires dans les systèmes de recommandation musicale et les recommandations d'utilisateurs similaires dans les réseaux sociaux. Ce qui suit présentera le principe et le processus de mise en œuvre de LSH à travers un exemple simple.

Supposons que nous ayons un ensemble de données et que chaque point de données soit un vecteur à 100 dimensions. Afin d'interroger cet ensemble de données pour les points de données les plus similaires à un vecteur donné, nous espérons utiliser LSH (Locality Sensitive Hashing) pour améliorer l'efficacité des requêtes. Étant donné que la dimensionnalité des points de données est très élevée, les méthodes de recherche linéaire traditionnelles prennent beaucoup de temps. LSH peut mapper des points de données dans un espace de grande dimension vers un espace de faible dimension, gardant des points de données similaires relativement proches dans un espace de faible dimension et réduisant le temps de recherche. Par conséquent, l’utilisation de LSH pour les requêtes peut accélérer la recherche et améliorer l’efficacité.

Tout d'abord, nous devons définir une fonction de hachage pour mapper le vecteur à 100 dimensions dans un espace de faible dimension. Il existe deux fonctions de hachage couramment utilisées : le hachage euclidien et le hachage cosinus. Le hachage euclidien mappe les vecteurs sur le domaine des nombres réels en générant aléatoirement des hyperplans pour mapper les points de données dans différents compartiments. Le hachage cosinus mappe les vecteurs sur une hypersphère de haute dimension et mappe également les points de données sur différents compartiments en générant aléatoirement des hyperplans. Dans cet exemple, nous utilisons le hachage euclidien comme exemple.

Nous pouvons exprimer la fonction de hachage sous la forme h(x)=lfloorfrac{a^Tx+b}{w}rfloor, où a est un vecteur aléatoire, b est une constante aléatoire et w est la largeur d'un seau , lfloorrfloor signifie arrondir vers le bas. Pour tout vecteur x, il sera mappé à un compartiment et le numéro du compartiment est h(x).

Maintenant, nous devons choisir un vecteur aléatoire a et une constante aléatoire b, ainsi que la largeur du seau w. Afin de mapper autant que possible des points de données similaires au même compartiment, nous devons choisir certains paramètres de sorte que la probabilité que des points de données similaires soient mappés au même compartiment soit relativement élevée et que des points de données différents soient mappés au même compartiment. . La probabilité est relativement faible. Ce processus peut être réalisé en ajustant les paramètres.

De manière générale, nous devons choisir plusieurs fonctions de hachage et mapper chaque fonction de hachage une fois. Grâce au mappage de ces fonctions de hachage, nous pouvons obtenir plusieurs compartiments. Nous pouvons considérer ces compartiments comme un ensemble candidat, puis effectuer une recherche approximative du voisin le plus proche dans cet ensemble candidat. Plus précisément, nous pouvons calculer la distance entre le vecteur de requête et chaque point de données de l'ensemble candidat, puis sélectionner le point de données avec la plus petite distance comme voisin le plus proche. Étant donné que la taille de l’ensemble candidat est bien inférieure à la taille de l’ensemble des données, ce processus est beaucoup plus efficace que la recherche linéaire.

Il convient de noter que LSH est une méthode approximative et qu'elle ne peut garantir l'exactitude des résultats de la requête. Il peut y avoir des erreurs dans les résultats de la requête LSH, et la taille de l'erreur est liée au choix de la fonction de hachage et aux paramètres. Par conséquent, dans les applications pratiques, nous devons sélectionner les fonctions et paramètres de hachage appropriés en fonction de scénarios et d'exigences spécifiques pour atteindre un équilibre entre la précision et l'efficacité des requêtes.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!