Comment hacher des vecteurs dans des compartiments dans Hacking sensible à la localisation (en utilisant la distance jaccard)?

J’implémente une application de recherche de voisin proche qui trouvera des documents similaires. Jusqu’ici, j’ai lu une bonne partie de la littérature relative à LSH (la théorie derrière LSH est une sorte de confusion et je ne suis pas encore capable de la comprendre à 100%).

Mon code est capable de calculer la masortingce de signature en utilisant les fonctions minhash (je suis proche de la fin). J’applique également la stratégie de bandes sur la masortingce de signature. Cependant, je ne suis pas capable de comprendre comment hacher des vecteurs de signature (de colonnes) dans une bande en compartiments.

Ma dernière question est peut-être la plus importante, mais je dois poser quelques questions d’ introduction :

q1: La fonction de hachage mappera-t-elle uniquement les mêmes vecteurs dans le même compartiment? (En supposant que nous ayons assez de seaux)

q2: La fonction de hachage doit-elle mapper les vecteurs similaires dans le même compartiment? Si oui, quel est le degré / la définition de cette similitude, puisque je ne calcule pas une comparaison, mais que je fais du hachage.

q3: En fonction des questions ci-dessus, quel type d’algorithme de table de hachage dois-je utiliser?

q4: Mon point le plus faible est que je ne sais pas comment générer une fonction de hachage qui prend des vecteurs en entrée et sélectionne un compartiment en sortie. Je peux en implémenter un seul en fonction de q1 et q2 … Des suggestions sur la génération de fonctions de hachage pour le bucketing LSH?

q1: Vous n’êtes pas censé hacher le vecteur entier, mais des parties de celui-ci. Supposons que vous avez des vecteurs de longueur 100 qui représentent chaque élément, vous pouvez hacher 5 tranches de longueur 20.

q2: C’est l’idée principale derrière tout: vous mesurez la similarité en comparant des parties de choses pour l’égalité. Si vous considérez les phrases d’un texte comme des vecteurs, il est peu probable que 2 phrases soient exactement identiques (le même résultat de hachage). Cependant, si vous les divisez en parties et que vous les hachez séparément, les hachages de certains mots individuels identiques dans les mêmes positions renverraient le même résultat de hachage, ce qui vous donnerait une idée de la similarité des phrases.

Le nombre et la longueur des tranches sont des parameters importants qui ont une incidence sur la précision du résultat de similarité. Trop de tranches donneraient beaucoup de faux positifs tandis que trop peu de tranches ne pourraient identifier que les degrés de similarité les plus élevés.

Vous pouvez trouver plus d’informations à ce sujet dans le livre “Mining of Massive Datasets”, disponible ici: http://infolab.stanford.edu/~ullman/mmds.html

q3: Vous avez besoin d’une structure de données qui, pour chaque niveau de tranche, conserve les résultats du hachage pour chaque tranche de vecteur, ainsi que le vecteur qui l’a produit. Ensuite, lorsque vous souhaitez trouver les voisins similaires du vecteur X, vous pouvez vérifier la structure de vos données pour chaque tranche et voir si la sortie de hachage que vous avez obtenue a également été produite par un autre vecteur.

Q4: Je ne suis pas sûr de ce que vous voulez dire ici. Si vous hachez un object, vous obtenez généralement en sortie une chaîne de bits, un entier ou un float, en fonction de la langue. C’est le seau. Si vous obtenez la même sortie avec la même fonction de hachage sur un object différent, cela signifie qu’ils ont été hachés sur le même compartiment.

Un moyen simple de générer une fonction de hachage pour LSH est le suivant:

Pour une min-hash signature donnée i pour chaque bande b, calculez la sum des lignes de la bande, appelez-la S_ib . Créez un S_ib pour S_ib . Pour l’ensemble complet, le compartiment sera ajouté aux entrées où la sum correspond à S_ib, sinon un nouveau compartiment est généré .

depuis les collections import defaultdict

 .... LSHdictlist = [defaultdict(list) for b in range(bands)] .... tempsum = np.int(np.sum(M[i,b*rowsinband:(b+1)*rowsinband])) LSHdictlist[b][tempsum].append(i) 

vous pouvez également utiliser le produit au lieu de la sum.