Как мне приступить к построению соответствующего алгоритма?

StackOverflow https://stackoverflow.com/questions/2163909

  •  24-09-2019
  •  | 
  •  

Вопрос

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

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

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

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

Решение

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

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

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

Например:

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

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

Другие советы

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

Удачи!

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top