Как мне создать алгоритм сопоставления?

Question

Я никогда раньше не создавал алгоритм для сопоставления и не знаю, с чего начать. Итак, вот мои основные настройки и почему я это делаю. Не стесняйтесь поправлять меня, если я не задаю правильные вопросы.

У меня есть база данных имен и уникальных идентификаторов для людей. Несколько сгенерированных идентификаторов (внутренних и сторонних), фамилия, имя и дата рождения являются основными, которые я буду использовать.

Несколько раз в течение года я получал список от третьей стороны, который нужно импортировать и привязать к существующим в моей базе данных людям, но данные никогда не бывают такими же чистыми, как мои. Идентификаторы могут измениться, даты рождения могут содержать опечатки, имена могут содержать опечатки, фамилии могут измениться и т. Д.

В каждом импорте может быть 20 000 записей, поэтому, даже если он будет на 99% точным, это все равно 200 записей, которые мне нужно будет ввести вручную и сопоставить. Я думаю, что я ищу более 99,9% точности, когда дело доходит до сопоставления входящих людей с моими пользователями.

Итак, как мне создать алгоритм, который может это понять?

PS Даже если у вас нет точного ответа, но вы знаете о некоторых материалах, ссылки на которые также могут быть полезны.

PPS Некоторые примеры будут похожи на то, что написал m3rLinEz:

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

Вас может заинтересовать Расстояние Левенштейна .

Расстояние Левенштейна между двумя Строки определяются как минимум количество правок, необходимых для преобразования одна строка в другую, с допустимые операции редактирования вставка, удаление или замена одного персонажа. Это называется после Владимира Левенштейна, который учел это расстояние в 1965 году. 1

Можно сравнить каждое из ваших полей и вычислить общее расстояние. И методом проб и ошибок вы можете обнаружить соответствующий порог, чтобы позволить интерпретировать записи как совпадающие. Я не реализовал это сам, но только подумал об этой идее:}

Например:

• Запись A - ID: 4831213321, Имя: Джейн
• Запись B - ID: 431213321, Имя: Янн
• Запись C - ID: 4831211021, Имя: Джон

Расстояние между A и B будет меньше, чем A и C / B и C, что указывает на лучшее соответствие.

Answer 2

Когда речь идет о чем-то подобном, не изобретайте велосипед. Расстояние Левехштейна, вероятно, является лучшим выбором, если вы ДОЛЖНЫ сделать это самостоятельно, но в противном случае проведите некоторое исследование существующих решений, которые выполняют запросы к базе данных и нечеткие поиски. Они занимаются этим дольше, чем вы, и, вероятно, тоже будет лучше ..

Удачи!

Answer 3

Я бы начал с простых почти 100% определенных совпадений и сначала обработал их, так что теперь у вас есть список, скажем, 200, который необходимо исправить.

Для остальных строк вы можете использовать упрощенную версию Теорема Байеса .

Для каждой несопоставленной строки рассчитайте вероятность того, что она соответствует каждой строке в вашем наборе данных, при условии, что данные содержат определенные изменения, которые происходят с определенными вероятностями. Например, человек меняет свою фамилию с вероятностью 0,1% (возможно, также зависит от пола), меняет свое имя с вероятностью 0,01% и имеет одну опечатку со стабильностью 0,2% (используйте расстояние Левенштейна посчитать количество опечаток). Другие поля также изменяются с определенной вероятностью. Для каждой строки рассчитайте вероятность совпадения строки, учитывая все поля, которые изменились. Затем выберите тот, который имеет наибольшую вероятность совпадения.

Например, строка с небольшой опечаткой в ​​одном поле, но равной по всем остальным, будет иметь шанс совпадения на 0,2%, тогда как строки, отличающиеся во многих полях, могут иметь вероятность только 0,0000001%. Таким образом, вы выбираете строку с маленькой опечаткой.

Answer 4

Если данные, которые вы получаете от третьих сторон, совпадают (каждый раз в одном и том же формате), я бы, вероятно, создал таблицу для каждой из сторонних организаций, от которых вы получаете данные. Затем каждый раз импортируйте каждый новый набор данных в одну и ту же таблицу. Я знаю, что есть способ объединить две таблицы на основе общих столбцов в каждой, используя оператор SQL. Таким образом, вы можете выполнять запросы SQL и получать данные из нескольких таблиц, но сделать так, чтобы они выглядели так, как будто они получены из одной объединенной таблицы. Аналогичным образом, записи, которые были добавлены и не имеют совпадений в обеих таблицах, могут быть найдены и затем спарены вручную. Таким образом, вы сохраняете свои «чистые» данные отдельно от мусора, который вы получаете от третьих лиц. Если вам нужен настоящий импорт, вы можете использовать эту соединенную таблицу для создания третьей таблицы, содержащей все ваши данные.

Answer 5

Если вы имеете дело с наборами данных такого размера и различными импортируемыми ресурсами, вы можете обратиться к решению Identity Management. Я в основном знаком с Sun Identity Manager, но это может быть излишним для того, что вы пытаетесь сделать. Возможно, стоит разобраться.

Answer 6

Регулярные выражения - это то, что вам нужно, зачем изобретать велосипед?