Faire un Hash Sim (Localité Hashage Sensible) algorithme plus précis?

Question

J'ai « enregistrements » (essentiellement les chaînes CSV) de deux noms et adresse et un. Je dois trouver des documents qui sont semblables les uns aux autres:. Essentiellement les noms et adresse des parties tous look « aussi bien » comme si elles étaient interprétées par un être humain

Je les idées utilisé cet excellent blog: http://knol.google.com / k / simple simhashing # pour écrire simple SimHash. Si les résultats de l'SimHash pour deux chaînes ou plus sont les mêmes, je passe tous les enregistrements de ce sous-ensemble à un programme correspondant à grains fins est O (n ^ 2), qui compare chaque enregistrement du jeu à tous les autres enregistrement.

Pour la partie SimHash, j'ai paramètres où je peux définir la taille de datagrammes (essentiellement une fenêtre glissante de taille n sur les cordes) et le nombre d'itérations à utiliser pour déterminer le nombre (aléatoire) hachages je dois utiliser pour le calcul SimHash. Jusqu'à présent, une taille de 4 et de datagrammes en utilisant 4 hash pour calculer la SimHash. J'ai essayé diverses autres combinaisons, mais celui-ci donne les meilleurs résultats à ce jour.

La question que je suis en cours d'exécution en est que cette méthode trouve environ 80% des doublons dans les ensembles de données dont je dispose. Je sais parce que je l'ai vérifié l'ensemble des données sur le O douloureusement lent (n ^ 2) match plein mentionné ci-dessus. Le O (n ^ 2) matcher est correct pour les ensembles de moins de 10 ^ 4 de données, mais devient rapidement infaisable car nécessaires pour exécuter des ensembles de taille 10 ^ 8.

Des idées, des suggestions ou des idées sur la façon dont je peux augmenter la précision du SimHash donc plus des dossiers « similaires » sont étiquetés avec le même numéro de SimHash?

EDIT: Avant SimHashing, je capitalise et supprimer tous! [0-9A-Z] caractères. Des exemples de choses qui doivent correspondre (fautes d'orthographe sont intentionnelles):

---

• JOHN SMITH, 123 RUE TOUT X-ville postal
• JOHNNY SMITH, 123 TOUT Stret
• SOMETOWNE postal ROBERT PARKER, 442 RUE TOUT X-ville postal

---

Ici 1 et 2 sont semblables, 3 n'est pas. Sortie doit être: 1 + 2

Answer 1

Avant d'essayer d'être de fantaisie et de changer le hachage sim, avez-vous essayé l'application des connaissances de domaine spécifique au problème?

Avez-vous une liste de paires manquées pour votre algorithme? Y at-il qu'ils ont en commun?

Avez-vous essayé de faire des choses comme la suppression de la capitalisation, la conversion des surnoms aux noms complets, laissant tomber prénoms, l'expansion N, E, S, W et au nord, au sud, à l'est, à l'ouest, l'expansion st à la rue, etc?

Answer 2

(je mettrais le ci-dessous dans un commentaire, mais n'ont pas encore le représentant.)

Qu'est-ce que vous essayez de le faire en fin de compte? Trouver tous les doublons? Comment définissez-vous les doublons? les questions de sensibilité de cas? Un libellé similaire?

Je suis un peu confus sur la façon dont vous allez à ce sujet - trouver des documents similaires et la création d'un ensemble, mais plus tard O (n ^ 2) vérifier ce que je suppose est l'égalité exacte. Si vous vérifiez l'égalité exacte, alors qui semble vaincre le but de trouver des documents similaires (sauf si vous utilisez que comme un filtre pour votre O (n ^ 2) pour gagner du temps.

Quelques pensées aléatoires: Exécutez chaque enregistrement par une sorte de désinfectant pour les mains qui tente de convertir chaque enregistrement à la forme la plus générale (si vous vous souciez / cette question est importante).

Si l'égalité exacte est ce qui vous intéresse, et la mémoire n'est pas une restriction, mais vous êtes à la recherche de vitesse, vous pouvez simplement créer un objet Java pour chaque enregistrement. Définir les equals () pour chaque enregistrement (vous pouvez toujours personnaliser ce pour ne pas faire l'égalité exacte). Vous devrez alors définir un (hashCode) pour cet objet. Ensuite, vous pouvez coller chaque enregistrement dans un HashSet.

Le HashSet résultant aura pas de doublons (tel que défini par vos equals () / mise en œuvre .hashCode ()).

Ou si vous voulez trouver les doublons, puis avant d'ajouter à la HashSet, vérifiez si elle contient le premier enregistrement, si elle fait -. Alors vous avez trouvé un double

Cette mise en œuvre serait très rapide, mais pourrait utiliser beaucoup de mémoire que vous stockerez l'ensemble des données en mémoire. Alternatives à cela serait de créer un hachage pour chaque enregistrement, puis stocker que dans le HashSet et vérifier les valeurs de hachage pour chaque enregistrement pour l'égalité.

L'inconvénient de faire un hachage pour chaque enregistrement est le défi de développer une bonne génération de hachage avec une bonne répartition et puis bien sûr avec dièzes à vous soucier de faux positifs avec des collisions. Mais si votre algorithme de hachage est solide, alors les chances de collision devrait être si rare que vous ne devriez pas vous inquiéter vraiment.

Quelques réflexions sur hash que vous pourriez faire sont quelque chose aussi simple que MD5 de la concaténation de tous les champs. Vous pouvez faire une somme de contrôle. Ou vous pouvez prendre la somme des hashCode pour chaque champ. Je ne suis pas un super génie mathématique, donc je ne peux pas vous dire ce qui aurait le meilleur comportement de distribution et donc entraîner la moindre chance probable pour les collisions. Pourrait être utile si vous décidez des recherches d'emprunter cette voie.

Answer 3

Simhash n'est pas un algorithme approprié à cet effet car il est seulement utile pour quasi-double détection où les différences sont très mineures et la grande proportion de caractéristiques sont identiques. Voir mon tutoriel sur simhash et résoudre le problème de la distance de Hamming .

Une meilleure approche serait minhash, éventuellement avec LSH . Il semble que vos caractéristiques hashing sur le mieux être générés en bardeaux de caractères (avec une longueur de 4 peut-être), plutôt que les bardeaux de mots .

Compte tenu de ces champs de texte courts, et étant donné que les commandes de mots ne sont probablement pas susceptibles de changer beaucoup, vous devriez envisager d'inclure terminer les bardeaux ainsi: les bardeaux du début et la fin d'un champ de texte qui contiennent moins que le nombre normal de caractères , plus un supplément de terminaison. Ceci tend à être plus clément envers les différences d'orthographe sur les petites séries de texte, par exemple « Whitmore » et « Whitemore » sans mettre fin à bardeaux donnerait

[PENTECOTE, HITM, ITMO, TMOR, PLUS] et [PENTECOTE, Hite, ITEM, TEMO, EMOR, PLUS] avec une faible similarité de Jaccard 09/02;

alors qu'avec les bardeaux de terminaison inclus ceux-ci produiraient

[#W, #WH, #WHI, PENTECOTE, HITM, ITMO, TMOR, PLUS, ORE #, RE #, E #] et [#W, #WH, #WHI, PENTECOTE, Hite, ITEM, TEMO, EMOR, PLUS, ORE #, RE #, E #] avec une plus grande similitude de Jaccard 15/08;

Les suggestions de Rob Neuhaus sur pré-normalisant sont très sensibles. Je normaliser les mots à long formulaire en bas à leurs abréviations (par exemple « Saint James Street » serait normalisée à « ST JAMES ST »). Normalisant dans l'autre sens peut être difficile avec parfois des abréviations ambiguës ( « St » -> « RUE » ou « SAINT »?), Et aussi, les formes abrégées contribuent à moins de bardeaux et ont donc moins d'influence sur la similitude globale, qui est bon, parce que les gens souvent faute de frappe « route » pour « Street », etc, et cela ne change pas le sens bien.