Как обнаружить дубликаты данных?

Question

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

Так есть ли какой-нибудь алгоритм, который может дать процент за то, насколько запись похожа на другую?

Answer 1

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

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

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

В свою обычную таблицу адресов добавьте Root-версии имен, например, Персона (Имя, Имя RootFirstName, Фамилия, Имя Rootsurn ....)

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

Заполните таблицу сопоставления: Вставьте IGNORE (выберите Имя, «НЕ УКАЗАНО» из Персона) в FirstNameMappings

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

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

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

Answer 2

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

Answer 3

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

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

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

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

Answer 4

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

Answer 5

Если у вас есть доступ к службам SSIS, проверьте преобразование «Нечеткая группировка» и «Нечеткий поиск».

http://www.sqlteam.com/article/using-fuzzy-lookup-transformations-in-sql-server-integration-services

http://msdn.microsoft.com/en-us/library/ms137786.aspx

Answer 6

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

Answer 7

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

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

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

Answer 8

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

У них есть API для нормализации имен (Билл-Уильям), Имя дедуцера (для необработанного текста) и Сходство имен (сравнение двух имен).

На данный момент все API бесплатны, это может быть хорошим способом для начала.

Answer 9

Возможно, вы также захотите изучить вероятностное соответствие.

Answer 10

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

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

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