Как обнаружить повторяющиеся данные?

У меня есть простая база данных контактов, но у меня возникают проблемы с входом пользователей в дубликаты данных. Я реализовал простое сравнение данных, но, к сожалению, дублированные данные, которые вводятся, не совсем то же самое. Например, имена неправильно написаны или один человек будет помещен в "Билл Смит", а другой - "Уильям Смит" для одного и того же человека.

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

Ответы

Ответ 1

Итак, есть какой-то алгоритм что может дать процент за то, как аналогичная запись в другую?

Алгоритмы как расстояния Soundex и Edit (как показано в предыдущем сообщении) могут решить некоторые из ваших проблем. Однако, если вы серьезно относитесь к очистке данных, этого будет недостаточно. Как утверждали другие, "Билл" звучит не так, как "Уильям".

Лучшее решение, которое я нашел, - использовать алгоритм сокращения и таблицу, чтобы уменьшить имена для этого имени.

В свою обычную таблицу адресов добавьте корневые версии имен, например Person (Имя, RootFirstName, Surname, Rootsurname....)

Теперь создайте таблицу сопоставления. FirstNameMappings (первичное имя KEY, имя корня)

Заполните таблицу сопоставления: Вставьте IGNORE (выберите Firstname, "UNDEFINED" из Person) в FirstNameMappings

Это добавит все первые имена, которые вы используете в своей таблице, вместе с RootName из "UNDEFINED"

Теперь, к сожалению, вам придется пройти через все уникальные имена и сопоставить их с RootName. Например, "Билл", "Биллл" и "Уилл" должны быть переведены на "Уильяма", Это очень трудоемко, но если качество данных действительно важно для вас, я считаю это одним из лучших способов.

Теперь используйте вновь созданную таблицу сопоставления для обновления поля "Rootfirstname" в таблице Person. Повторите для фамилии и адреса. Как только это будет сделано, вы сможете обнаружить дубликаты, не испытывая орфографических ошибок.

Ответ 2

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

Ответ 3

Я предполагаю, что эта проблема хорошо понята, но что происходит со мной в первом чтении:

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

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

Вы можете предпочесть довольно сильное отклонение от ложных срабатываний, по крайней мере, сначала.

Ответ 4

В то время как у меня нет алгоритма для вас, моим первым действием было бы взглянуть на процесс, связанный с вводом нового контакта. Возможно, у пользователей нет простого способа найти контакт, который они ищут. Как и в случае новой формы вопроса "Переполнение стека", вы можете предлагать контакты, которые уже существуют на новом экране контакта.

Ответ 6

Если у вас есть большая база данных со строковыми полями, вы можете очень быстро найти много дубликатов, используя алгоритм simhash.

Ответ 7

Это может быть или не быть связанным, но незначительные орфографические ошибки могут быть обнаружены Soundex search, например, это позволит вам рассмотреть Бритни Спирс, Бритни Спирс и Бритни Спирс в качестве дубликатов.

Сокращения ников, однако, трудно рассматривать как дубликаты, и я сомневаюсь, что это разумно. Будут связаны несколько человек по имени Билл Смит и Уильям Смит, и вам придется повторять это с Чарльзом → Чак, Робертом → Бобем и т.д.

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

Ответ 8

В FullContact.com есть API, который может решить это для вас, см. их документацию здесь: http://www.fullcontact.com/developer/docs/?category=name.

У них есть API для нормализации имен (Bill in William), Name Deducer (для сырого текста) и сходства имен (сравнение двух имен).

В настоящий момент все API-интерфейсы бесплатны, это может быть хороший способ начать работу.

Ответ 9

Я не уверен, что он будет хорошо работать для проблемы с именами и прозвищами, но наиболее распространенным алгоритмом в этом виде области будет расстояние редактирования/Левенштейн расстояние. Это в основном подсчет количества изменений, дополнений и абзацев, необходимых для превращения одного элемента в другой.

Для имен, я не уверен, что вы когда-либо добьетесь хороших результатов с помощью чисто алгоритмического подхода. Что вам действительно нужно - это масса данных. Возьмем, к примеру, насколько лучше правильные предложения Google, чем в обычном настольном приложении. Это связано с тем, что Google может обрабатывать миллиарды веб-запросов и смотреть, какие запросы ведут друг к другу, какие "вы имели в виду" ссылки на самом деле получают клики и т.д.

Есть несколько компаний, которые специализируются на проблеме сопоставления имен (в основном для приложений национальной безопасности и мошенничества). Тот, который я помню, Search Software America, похоже, был выкуплен этими парнями http://www.informatica.com/products_services/identity_resolution/Pages/index.aspx, но я подозреваю, что любой из этих видов решения могут оказаться весьма дорогостоящими для приложений контактов.

Ответ 10

Вы также можете посмотреть вероятностное соответствие.

Ответ 11

Для тех, кто бродит по сети и заканчивает здесь, могу ли я предложить вам попробовать созданное мной дополнение Google Sheet под названием Flookup. Это особенно хорошо с именами и имеет несколько других замечательных функций, которые я опишу ниже:

  1. Скажем, у вас есть список имен и есть 2 человека по имени "Джон Смит". Вы можете использовать параметр rank из Flookup, чтобы дать алгоритму команду вернуть 1-е, 2-е, 3-е или n-е наилучшее совпадение. Это полезно, если у вас есть дополнительная информация, которую вы можете использовать для идентификации нужного вам "Джона Смита".
  2. Скажем, у вас есть дополнительная база данных/список номеров квартир. Вы можете указать, какой "Джон Смит" вы хотите, введя: John Smith & Apartment A или John Smith & Apartment B в качестве параметра поиска, чтобы помочь различать два имени.

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