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

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

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

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

Каждый импорт может содержать 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'

Ответ 1

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

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

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

Например:

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

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

Ответ 2

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

Удачи!

Ответ 3

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

Ответ 4

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

Ответ 5

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

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

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

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

Ответ 6

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