fuzzy matching de données structurées

Question

J'ai un corpus assez restreint de dossiers structurés assis dans une base de données. Étant donné qu'une infime partie des informations contenues dans un dossier unique, soumis via un formulaire web (si structuré de la même manière que le schéma de la table), (que nous appellerons le dossier de test) je dois tirer rapidement une liste des les dossiers qui sont les matches les plus probables pour l'enregistrement de test, ainsi que de fournir une estimation de la confiance de la façon dont près les termes de recherche correspondent à un enregistrement. L'objectif principal de cette recherche est de savoir si quelqu'un tente d'entrer un enregistrement qui est double à l'un dans le corpus. Il y a une chance raisonnable que le dossier de test sera dupe, et une chance raisonnable le dossier de test ne sera pas dupe.

Les enregistrements sont environ 12000 octets de large et le nombre total d'enregistrements est d'environ 150 000. Il y a 110 colonnes dans le schéma de table et 95% des recherches seront sur les 5% des colonnes recherche le plus souvent.

Les données sont des choses comme les noms, adresses, numéros de téléphone et autres numéros spécifiques de l'industrie. Dans les deux corpus et le dossier d'essai, il est entré dans la main et est semistructurée dans un champ individuel. Vous pourriez dire à première vue « poids les colonnes manuellement et mot de correspondance jetons en eux », mais ce n'est pas si facile. Je pensais aussi: si je reçois un numéro de téléphone, je pensais que ce serait indiquer un match parfait. Le problème est qu'il n'y a pas un seul champ sous la forme dont la fréquence jeton ne varie pas en fonction des ordres de grandeur. Un numéro de téléphone peut apparaître 100 fois dans le corpus ou 1 fois dans le corpus. La même chose vaut pour tout autre domaine. Cela rend la pondération au niveau du terrain impraticable. J'ai besoin d'une approche plus fine pour obtenir l'appariement décent.

Mon plan initial était de créer un hachage de hachages, niveau supérieur étant le nom du champ. Ensuite, je choisirais toutes les informations du corpus pour un champ donné, essayer de nettoyer les données qu'il contient, et tokenize les données aseptisés, hachant les jetons au deuxième niveau, avec les jetons que les clés et la fréquence comme valeur.

J'utiliser le nombre de fréquence en poids: plus la fréquence d'un jeton dans le corpus de référence, le poids moins j'attache à ce jeton si elle se trouve dans le dossier de test

.

Ma première question est pour les statisticiens de la pièce: comment pourrais-je utiliser la fréquence comme un poids? Y at-il une relation mathématique précise entre n, le nombre d'enregistrements, f (t), la fréquence avec laquelle un t jeton est apparu dans le corpus, la probabilité o qu'un dossier est un original et non une copie, et la probabilité p que l'enregistrement de test est vraiment un record x donné le test et x contiennent le même t dans le même domaine? Que diriez-vous de la relation de jetons multiples sur plusieurs champs correspond?

Depuis que je doute sincèrement qu'il ya, est-il quelque chose qui me fait proche, mais est mieux que un hack complètement arbitraire plein de facteurs magiques?

Sauf que, quelqu'un a obtenu une façon de le faire?

Je suis particulièrement vif sur d'autres suggestions qui ne concernent pas le maintien d'une autre table dans la base de données, comme une table de recherche de fréquence jeton.

Answer 1

Vous pouvez probablement obtenir quelques idées de ce différent mais similaire SO question: de calcul de contexte de texte de corrélation sensible .

Plus spécifique au problème à portée de main, voici quelques réflexions et idées:

Tout d'abord, en reconnaissant l'utilisation très biaisée (seulement 6 à 10 attributs couvrent 95% de l'utilisation), vous pouvez / devez appliquer l'effort asymétrique sur les attributs, à savoir investir davantage, à la fois en terme de temps de programmation et en terme de run-time attribution du processeur, pour faire face à ces quelques attributs que pour les attributs supplémentaires de 100 impairs.

Le montant relativement faible des données fournies en entrée pour faire correspondre les doublons possibles dans la base de données, l'ensemble relativement faible des attributs généralement utilisés, et la sémantique apparemment commun de ces (numéro de téléphone, adresse, nom ...) suggèrent une main solution -crafted plutôt que complètement basé sur l'apprentissage de la machine.

Note: un grand nombre de suggestions applicables par la suite n'a pas besoin de tous les attributs (depuis moins d'une douzaine de ceux-ci couvrent la quasi-totalité de l'utilisation, il n'y a pas de point, au moins dans un premier temps d'investir beaucoup avec les autres attributs .

• Normaliser les données
  S'il est interdit pour vous de modifier les valeurs de champ d'origine en double peut-être les colonnes à un coluumn « de norm_xxx » correspondant où xxx est le nom d'origine.
  Que, Comment normalise peut varier avec chaque attribut; pour « texte libre » comme les données, assurez-vous qu'il n'y ait pas de fuite menant ni espaces, un seul espace entre les mots, pas d'onglets et des caractères non imprimables. Utilisez soit en majuscules ou en minuscules (eventhought le texte original / pour affichage peut comprendre un mélange, votre traitement ira plus vite en étant en mesure d'assumer boîtier uniforme). Plus spécifiquement pour les adresses et / ou le nom de l'entreprise, vous pouvez convertir des termes communs à une forme standard (ST pour STREET, ST et ST, etc.) (Assurez-vous de garder cette liste, il sera appliqué aux critères de recherche des utilisateurs et ). Une partie de la normalisation peut également être tout à fait de laisser tomber quelques mots de bruit (comme disent CO, INC, GMBH à la fin des noms de société)
• Créer quelques colonnes calculées
  Pour exemple ceux avec le texte, en sens inverse, pour les attributs qui peuvent être fouillées avec un caractère générique de fin
• Envisagez d'utiliser une conversion Soundex comme pour certains attributs.
• index FULLTEXT, individuellement, toutes les colonnes comme texte
• Créer un index simples (SQL) sur toutes les 6 à 10 colonnes bien utilisées

Tous les ci-dessus, ne sont que des préparations de temps hors ligne pour les matches réellement performants. Maintenant .. l'utilisateur entre son / sa requête ... voici quelques idées sur la façon de traiter avec elle

• Normaliser les critères de recherche qui justifient
• Exécuter plusieurs recherches ...
  Ceci est un peu délicat; il y a plusieurs, partiellement contradictoires, les objectifs pour l'exécution de ces recherche. Nous voulons réduire, de manière significative le nombre de « correspondances possibles »: il est effectivement impossible de faire un plein-sur l'un de tous les comparant 150.000 enregistrements avec les critères fournis par l'utilisateur; par exemple une partie de la logique de mise en correspondance peut impliquer le calcul de la distance d'édition entre un champ d'un enregistrement donné de la base de données et un critère de recherche. Nous voulons aussi nous assurer que nous n'excluons pas les enregistrements de la liste « correspondances possibles » à cause d'une faute de frappe en dire le nom de la société ... Enfin, nous voulons fournir la liste des correspondances possibles de façon classée.
  La façon d'effectuer ces recherches suit quelques heuristiques prédéfinies (j'ai trouvé le modèle de conception de stratégie travail bien pour cela, ce qui permet de la manière flexibilty la recherche sont exécutés, en fonction de l'entrée fournie par l'utilisateur). En un mot nous cherchons les mots les plus sélectifs dans les attributs les plus sélectifs / pertinents, et en fonction du nombre de « hits » trouvé que nous soit « OR » (union) ou « ET » avec d'autres résultats de la recherche, jusqu'à ce que nous avons quelques cent enregistrement.
• Calculer une valeur de similitude entre chaque attribut des enregistrements « matches potentiels » et les critères de recherche correspondants. Peut-être appliquer un coefficient à cette valeur (permettant de mettre plus peser à dire un nom de société [partielle] qui correspond à un match de la ville)
• Tally la valeur de similarité overal pour un dossier complet (par rapport aux critères de recherche complets)

• Afficher les dossiers dépassant un certain seuil de la valeur de similitude avec l'utilisateur final, pour examen

  Enfin, et il arrive un processus partiellement automatisé, vous pouvez modifier certains des paramètres en fonction des commentaires fournis par l'utilisateur final. (Ce qui est très difficile à faire, je vais garder cela pour un autre poste ;-))