Comment puis-je à construire un algorithme de correspondance?

Question

Je ne l'ai jamais construit un algorithme pour faire correspondre avant et ne sais pas vraiment où commencer. Voici donc mon jeu de base et pourquoi je le fais. Ne hésitez pas à me corriger si je ne suis pas poser les bonnes questions.

J'ai une base de données des noms et des identificateurs uniques pour les personnes. Plusieurs identifiants générés (générés à l'interne et une tierce partie), nom, prénom et date de naissance sont les primaires que j'utiliser.

Plusieurs fois au cours de l'année je reçois une liste d'un tiers qui doit être importé et lié au peuple existant dans ma base de données, mais les données ne sont jamais aussi propre que la mienne. ID pourrait changer, les dates de naissance pourraient avoir des fautes de frappe, les noms pourraient avoir des fautes de frappe, noms de famille pourraient changer, etc.

Chaque importation pourrait avoir 20.000 dossiers même s'il est précis à 99%, c'est encore 200 dossiers que je dois aller manuellement et correspondre. Je pense que je suis à la recherche de plus comme 99,9% de précision en ce qui concerne les personnes correspondant entrants à mes utilisateurs.

Alors, comment dois-je de faire un algorithme qui peut comprendre cela?

PS Même si vous n'avez pas une réponse exacte, mais ne savez de certains matériaux de référence serait également utile.

PPS Quelques exemples seraient semblables à ce que m3rLinEz a écrit:

ID: 9876234 Fname: Jose     LName: Guitierrez       Birthdate:01/20/84  '- Original'

ID: 9876234 Fname: Jose     LName: Guitierrez       Birthdate:10/20/84  '- Typo in birth date'
ID: 0876234 Fname: Jose     LName: Guitierrez       Birthdate:01/20/84  '- Wrong ID'
ID: 9876234 Fname: Jose     LName: Guitierrez-Brown Birthdate:01/20/84  '- Hyphenated last name'
ID: 9876234 Fname: Jose, A. LName: Guitierrez       Birthdate:01/20/84  '- Added middle initial'
ID: 3453555 Fname: Joseph   LName: Guitierrez       Birthdate:01/20/84  '- Probably someone else with same birthdate and same last name'

Answer 1

Vous pourriez être intéressé par Levenshtein .

  

La distance Levenshtein entre deux   chaînes est défini comme le minimum   nombre de modifications nécessaires pour transformer   une chaîne de caractères dans l'autre, avec le   opérations d'édition admissibles étant   insertion, délétion ou substitution   d'un seul caractère. Il s'appelle   après Vladimir Levenshtein, qui   considéré cette distance en 1965. 1

Il est possible de comparer tous vos champs et calcul de la distance totale. Et par essais et erreurs que vous pouvez découvrir le seuil approprié pour permettre les enregistrements à interpréter comme correspondance. Ne l'ont pas mis en œuvre moi-même, mais juste pensé à l'idée:}

Par exemple:

• Enregistrement A - ID: 4831213321, Nom: Jane
• Enregistrer B - ID: 431213321, Nom: Jann
• Enregistrement C - ID: 4831211021, Nom: John

La distance entre A et B sera inférieur à A et C / B et C, ce qui indique une meilleure correspondance.

Answer 2

Quand il vient à quelque chose comme ça, ne pas réinventer la roue. La distance est Levehstein probablement votre meilleur pari si vous devez le faire vous-même, mais sinon, faire des recherches sur les solutions existantes qui font la requête de base de données et les recherches floues. Ils ont fait ça plus que vous, ce sera probablement mieux aussi ..

Bonne chance!

Answer 3

Si vous avez affaire à des ensembles de données de cette taille et différentes ressources importées, vous pouvez regarder dans une solution de gestion des identités. Je suis surtout familier avec Sun Identity Manager, mais il peut être trop pour ce que vous essayez de faire. Il pourrait être intéressant de regarder dans.

Answer 4

Si les données que vous obtenez de 3e parties est compatible (même format à chaque fois), je serais probablement créer une table pour chacun des 3e parties que vous obtenez des données. Puis importer chaque nouvel ensemble de données à la même table chaque fois. Je sais qu'il ya un moyen de rejoindre ensuite les deux tables basées sur des colonnes communes dans chaque aide d'une instruction SQL. De cette façon, vous pouvez effectuer des requêtes SQL et obtenir des données de plusieurs tables, mais la faire ressembler il est venu d'une table unique et unifiée. De même les enregistrements qui ont été ajoutés qui n'ont pas les matchs dans les deux tableaux peuvent être trouvés et puis manuellement appairés. De cette façon, vous conservez vos données « propres » séparé de la malbouffe que vous obtenez de tiers. Si vous vouliez une véritable importation, vous pouvez alors utiliser cette table jointe pour créer une troisième table contenant toutes vos données.

Answer 5

Je commencerais avec le facile près de 100% certains matches et les traiter d'abord, maintenant que vous avez une liste de dire 200 qui ont besoin de fixation.

Pour les lignes restantes, vous pouvez utiliser une version simplifiée de Bayes Théorème.

Pour chaque ligne inégalée, calculer la probabilité qu'il est un match pour chaque ligne de votre ensemble de données en supposant que les données contiennent certains changements qui se produisent avec certaines probabilités. Par exemple, une personne change son nom avec une probabilité de 0,1% (éventuellement dépend également du sexe), modifie son prénom avec une probabilité de 0,01%, et est un a une seule coquille avec probility 0,2% (utilisation distance de Levenshtein pour compter le nombre de fautes de frappe). D'autres champs changent également avec certaines probabilités. Pour chaque ligne calculer la probabilité que la ligne correspond compte tenu de tous les champs qui ont changé. Ensuite, prenez le celui qui a la plus forte probabilité d'être un match.

Par exemple, une ligne avec seulement une petite faute de frappe dans un champ mais égal à tous les autres aurait une chance de 0,2% d'un match, alors que les lignes qui diffèrent dans de nombreux domaines pourraient avoir seulement une chance de 0,0000001%. Donc, vous prenez la ligne avec la petite faute de frappe.

Answer 6

Les expressions régulières sont ce dont vous avez besoin, pourquoi réinventer la roue?