Comprendre le hachage des fonctionnalités

10

Wikipedia fournit l'exemple suivant lors de la description du hachage des fonctionnalités ; mais le mappage ne semble pas cohérent avec le dictionnaire défini

Par exemple, todoit être converti en 3fonction du dictionnaire, mais il est codé comme à la 1place.

Y a-t-il une erreur dans la description? Comment fonctionne le hachage des fonctionnalités?

Les textes:

John likes to watch movies. Mary likes too.
John also likes to watch football games.

peut être converti en utilisant le dictionnaire

{"John": 1, "likes": 2, "to": 3, "watch": 4, "movies": 5, "also": 6, 
"football": 7, "games": 8, "Mary": 9, "too": 10}

à la matrice

[[1 2 1 1 1 0 0 0 1 1]
 [1 1 1 1 0 1 1 1 0 0]]
feature-construction Josh
la source

Réponses:

10

La matrice est construite de la manière suivante:

  • les lignes représentent les lignes
  • les colonnes représentent les entités

et chaque matrice d'entrée (i, j) = k signifie:

Dans la ligne i, le mot d'index j apparaît k fois.

So toest mappé à l'index 3. Il apparaît exactement une fois dans la ligne 1. Donc m (1,3) = 1.

Plus d'exemples

  • likesest mappé à l'index 2. Il apparaît exactement deux fois dans la première ligne. Donc m (1,2) = 2
  • also est mappé à l'index 6. Il n'apparaît pas à la ligne 1, mais une fois à la ligne 2. Donc m (1,6) = 0 et m (2,6) = 1.
steffen
la source
Dans le contexte du hachage des fonctionnalités, nous n'avons pas de dictionnaire. Nous n'avons qu'une fonction de hachage. Cela fonctionne-t-il de la même manière dans le sens où vous (1) calculez la valeur de hachage de la fonction et (2) incrémentez l'index donné par la fonction de hachage de 1 chaque fois que vous voyez un point de données? Par exemple, comme l'indique @ user20370 ci-dessous, si vous décidez de coder vos fonctionnalités avec 13 bits et que la valeur de hachage de "likes" est 5674, alors l'index 5674 est-il incrémenté de 1? Et si vous utilisez moins de bits, modifiez-vous simplement 5674 par 2 ^ (# bits) et incrémentez cet index?
Vivek Subramanian
1
@VivekSubramanian oui. Le défi est de trouver une fonction de hachage sans collisions (c'est-à-dire des mots différents, mais la même valeur de hachage), ou avec des collisions se produisant rarement. Il s'agit d'un domaine de recherche en informatique ( en.wikipedia.org/wiki/Perfect_hash_function ).
steffen
4

Comme l'a souligné Steffen, l'exemple de matrice code le nombre de fois qu'un mot apparaît dans un texte. La position de l'encodage dans la matrice est donnée par le mot (position de colonne sur la matrice) et par le texte (position de ligne sur la matrice).

Maintenant, l'astuce de hachage fonctionne de la même manière, bien que vous n'ayez pas à définir initialement le dictionnaire contenant la position de la colonne pour chaque mot.

En fait, c'est la fonction de hachage qui vous donnera la plage de positions de colonne possibles (la fonction de hachage vous donnera une valeur minimale et maximale possible) et la position exacte du mot que vous souhaitez encoder dans la matrice. Ainsi, par exemple, imaginons que le mot "likes" soit haché par notre fonction de hachage dans le nombre 5674, alors la colonne 5674 contiendra les encodages relatifs au mot "likes".

De cette façon, vous n'aurez pas besoin de créer un dictionnaire avant d'analyser le texte. Si vous utiliserez une matrice clairsemée comme matrice de texte, vous n'aurez même pas à définir exactement la taille de la matrice. Juste en scannant le texte, à la volée, vous convertirez les mots en positions de colonne par la fonction de hachage et votre matrice de texte sera remplie de données (fréquences, c'est-à-dire) en fonction du document que vous analysez progressivement (position de la ligne).

user20370
la source