У меня простая база данных контактов, но у меня проблемы с тем, что пользователи вводят повторяющиеся данные. Я реализовал простое сравнение данных, но, к сожалению, вводимые повторяющиеся данные не совсем то же самое. Например, имена написаны неправильно или один человек вставит «Билл Смит», а другой - «Уильям Смит» для того же человека.
Итак, существует ли какой-то алгоритм, который может дать процентное отношение к тому, насколько одна запись похожа на другую?
Итак, существует ли какой-то алгоритм, который может дать процентное отношение к тому, насколько одна запись похожа на другую?
Алгоритмы, такие как Soundex и Edit Distance (как было предложено в предыдущем посте), могут решить некоторые из ваших проблем. Однако, если вы серьезно относитесь к очистке данных, этого будет недостаточно. Как утверждали другие, «Билл» совсем не похож на «Уильяма».
Лучшее решение, которое я нашел, - это использовать алгоритм сокращения и таблицу, чтобы сократить имена до корневого имени.
В свою обычную таблицу адресов добавьте корневые версии имен, например, Person (Firstname, RootFirstName, Surname, Rootsurname ....)
Теперь создайте таблицу сопоставления. FirstNameMappings (имя основного ключа, корневое имя)
Заполните таблицу сопоставления следующим образом: Вставьте ИГНОРИРОВАНИЕ (выберите «Имя», «НЕОПРЕДЕЛЕННО» в поле «Человек») в FirstNameMappings.
Это добавит все имена, которые у вас есть в вашей таблице людей, вместе с RootName "UNDEFINED"
К сожалению, теперь вам придется просмотреть все уникальные имена и сопоставить их с RootName. Например, «Билл», «Билл» и «Уилл» все должны быть переведены на «Уильям». Это очень трудоемко, но если для вас действительно важно качество данных, я думаю, что это один из лучших способов.
Теперь используйте только что созданную таблицу сопоставления для обновления поля «Rootfirstname» в вашей таблице Person. Повторите для фамилии и адреса. Как только это будет сделано, вы сможете обнаруживать дубликаты, не страдая от орфографических ошибок.
Вы можете сравнить имена с расстоянием Левенштейна. Если имена совпадают, расстояние равно 0, иначе оно задается минимальным количеством операций, необходимых для преобразования одной строки в другую.
Я полагаю, что эта проблема хорошо изучена, но при первом чтении мне приходит в голову следующее:
Используйте свою существующую базу данных, чтобы получить хорошее первое предположение о пороге, и исправляйте его по мере накопления опыта.
Вы можете предпочесть довольно сильную предвзятость в отношении ложных срабатываний, по крайней мере, на первых порах.
Хотя у меня нет алгоритма для вас, моим первым действием было бы взглянуть на процесс, связанный с вводом нового контакта. Возможно, у пользователей нет простого способа найти контакт, который они ищут. Как и в новой форме вопроса Stack Overflow, вы можете предлагать контакты, которые уже существуют, на новом экране контактов.
Если у вас есть доступ к SSIS, ознакомьтесь с преобразованием «Нечеткое группирование» и «Нечеткий поиск».
http://www.sqlteam.com/article/using-fuzzy-lookup-transformations-in-sql-server-integration-services
http://msdn.microsoft.com/en-us/library/ms137786.aspx
Если у вас большая база данных со строковыми полями, вы можете очень быстро найти множество дубликатов, используя алгоритм simhash.
Это может быть связано или нет, но небольшие орфографические ошибки могут быть обнаружены с помощью поиска Soundex, например , это позволит вам рассматривать Бритни Спирс, Британни Спэрс и Бритни Спирс как дубликаты.
Однако сокращение псевдонимов трудно рассматривать как дубликаты, и я сомневаюсь, что это разумно. Обязательно будет несколько человек по имени Билл Смит и Уильям Смит, и вам придется повторить это с Чарльз-> Чаком, Робертом-> Бобом и т. Д.
Кроме того, если вы рассматриваете, скажем, пользователей-мусульман, проблемы становятся более сложными (например, слишком много мусульман, которых зовут Мухаммед / Мохаммад).
Я не уверен, что это сработает для проблемы имен и псевдонимов, но наиболее распространенным алгоритмом в такой области будет алгоритм редактирования расстояния / расстояния Левенштейна. По сути, это подсчет количества изменений, добавлений и удалений персонажей, необходимых для превращения одного предмета в другой.
Что касается имен, я не уверен, что вы когда-нибудь добьетесь хороших результатов с чисто алгоритмическим подходом - вам действительно нужны массивы данных. Возьмем, к примеру, насколько лучше варианты написания в Google по сравнению с обычными настольными приложениями. Это связано с тем, что Google может обрабатывать миллиарды веб-запросов и смотреть, какие запросы приводят друг к другу, какие ссылки на самом деле нажимаются и т. Д.
Есть несколько компаний, которые специализируются на проблеме сопоставления имен (в основном, для приложений национальной безопасности и мошенничества). Я помню, что Search Software America, похоже, была куплена этими парнями http://www.informatica.com/products_services/identity_resolution/Pages/index.aspx, но я подозреваю, что любое из этих решений было бы слишком дорогим для приложения для работы с контактами.
У FullContact.com есть API, которые могут решить эту проблему за вас, см. Их документацию здесь: http://www.fullcontact.com/developer/docs/?category=name.
У них есть API для нормализации имен (от Билла к Уильяму), средства вывода имен (для необработанного текста) и схожести имен (для сравнения двух имен).
На данный момент все API бесплатны, это может быть хорошим началом.
Вы также можете изучить вероятностное соответствие.
Тем, кто бродит по сети и оказывается здесь, могу я предложить вам попробовать использовать созданное мной дополнение Google Sheet под названием Flookup. Он особенно хорош с именами и имеет несколько других замечательных функций, которые я опишу ниже:
rank из Flookup, чтобы дать алгоритму команду возвращать 1-е, 2-е, 3-е или n-е наилучшее совпадение. Это полезно, если у вас есть дополнительная информация, которую вы можете использовать для идентификации того «Джона Смита», которого вы хотите.John Smith & Apartment A или John Smith & Apartment B в качестве параметра поиска, который поможет различать эти два имени.Я надеюсь, что вы найдете Flookup столь же полезным, как и другие.
