Алгоритм поиска практически похожих значений

Question

У меня есть Persons таблица в SQL Server 2008 .

Моя цель - найти людей, которые имеют почти одинаковые адреса.

Адрес описывается столбцами state, town, street, house, apartment, postcode и phone.

Из-за некоторых специфических различий в некоторых штатах (не в США) и в человеческом факторе (ошибки в адресах и т. Д.) Адрес не заполняется одинаковым образом.

Самые распространенные ошибки в адресах

1. Чувствительность к регистру
2. Кто-то написал «apt.», Другой - «квартиру» или «ap». (хотя адреса не написаны на английском языке)
3. Пробелы, точки, запятые
4. Различия в написании названий улиц, например, "Доктор" Джонс-стрит "или" Доктор Джонс-стрит "или" Д. Джон. st. "или" Dr Jones st "и т. д.

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

Есть ли алгоритм для такого рода проблем?

Заранее спасибо.

UPDATE

1. Как я уже говорил, адрес разделен на разные столбцы. Должен ли я генерировать строку, объединяющую столбцы, или делать ваши шаги для каждого столбца? Я предполагаю, что я не должен объединять столбцы, но если я буду сравнивать столбцы отдельно, как мне организовать их? Должен ли я найти сходства для каждого столбца, объединить их или пересечь или что-нибудь еще?
2. Нужно ли мне собирать статистику или какой-то алгоритм обучения?

Answer 1

Предложите подойти к нему так:

1. Создание n-граммов на уровне слов (триграмма / 4-грамм может сделать это) из различных записей

2. Выполните сравнение много-много раз для сравнения строк и сгруппируйте их по расстоянию строк. Кто-то предложил Левенштейна; Есть более подходящие для такого рода задач, Jaro-Winkler Distance и Smith-Waterman работают лучше. Такие библиотеки, как SimMetrics сделают жизнь намного проще

3. Когда у вас есть кластеры n-грамм, вы можете разрешить всю строку, используя составляющие подграммы, то есть D.Jones St => Davy Jones St. => DJones St.

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

Обновление: на основе вашего обновления выше, вот предлагаемые шаги

1. Объедините ваши столбцы в одну строку, возможно, создайте db "view". Например,

   создать вид vwAddress как выберите топ 10000 государственный город, улица, дом, квартира, почтовый индекс, штат + город + улица + дом + квартира + почтовый индекс как адрес от ...

2. Напишите отдельное приложение (скажем, на Java или C # / VB.NET) и используйте алгоритм, такой как JaroWinkler, чтобы оценить расстояние до строки для объединенного адреса, чтобы создать сравнение много-много раз. и записать в отдельную таблицу адрес1 | адрес n | Сходство

Вы можете использовать Simmetrics, чтобы получить сходство таким образом:

 JaroWinnkler objJw = new JaroWinkler()
double sim =  objJw.GetSimilarity (address1, addres n);

3. Вы также можете запрограммировать его так, чтобы адрес, такой как «1 Jones Street, Sometown, SomeCountry», стал «1 Jones Street», «Jones Street Sometown» и т. Д. и сравните триграммы. (или даже 4 грамма) для более высокой точности.

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

Answer 2

Я бы попытался сделать следующее:

• разделить адрес на несколько слов, избавиться от пунктуации одновременно
• проверьте все слова на наличие шаблонов, которые обычно пишутся по-разному, и замените их общим именем (например, замените квартиру, ap., ... на apt, замените Doctor на Dr., ...)
• положить все слова обратно в одну строку в алфавитном порядке
• сравнить все адреса, используя алгоритм сравнения нечетких строк, например, Левенштейн
• настроить параметры алгоритма Левенштейна (например, вы хотите разрешить больше различий для более длинных строк)
• наконец, сделайте ручную проверку строк

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

Answer 3

Я делал такой проект в прошлом столетии.В основном это была консолидация двух клиентских файлов после слияния, и включала имена и адреса из трех разных источников.

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

Затем просмотрите имя и укажите первую букву имени, плюс первую фамилию.(Не так просто подумать «Доктор Мед. Сэр Генри де Баскервиль Смит»), но не волнуйтесь, если есть какие-то неясности, просто возьмите оба!Так что если вам повезет, вы получите HBASKERVILLE и HSMYTHE.Теперь избавьтесь от всех гласных, так как именно здесь происходит большинство вариантов написания, так что теперь у вас есть HBSKRVLL HSMTH.

Вы также можете получить эти строки у "Х. Баскервиля", "Сэра Генри Баскервиля Смита" и, к сожалению, "Гарольда Смита", но здесь мы говорим о нечетком совпадении!

Выполните аналогичное упражнение наулица, а также квартиры и почтовые индексы.Но не выбрасывайте исходные данные!

Теперь вы подошли к интересному фрагменту, сначала сравнив каждую из исходных строк и дав, скажем, 50 баллов за каждую строку, которая точно соответствует.Затем пройдитесь по «нормализованным» строкам и дайте, скажем, 20 баллов за каждый, который точно соответствует.Затем пройдитесь по всем строкам и дайте, скажем, 5 баллов за каждые четыре или более подстроки, которые у них общие.Для каждой сравниваемой пары у вас получатся баллы> 150, которые вы можете считать определенным совпадением, некоторые с баллами менее 50, которые вы можете считать несоответствующими, а некоторые между ними с некоторой вероятностью совпадения.

Вам нужно еще немного подправить, чтобы улучшить это, добавив различные правила, такие как «вычесть 20 очков для фамилии« кузнец »».Вы действительно должны продолжать работать и дорабатывать до тех пор, пока не будете довольны полученными совпадениями, но, как только вы посмотрите на результаты, вы получите довольно хорошее представление о том, какой счет считать «совпадением», и какие ложные срабатывания вам нужно избавить.из.

Answer 4

У вас есть поле с почтовым индексом !!!

Итак, почему бы вам просто не купить таблицу почтовых индексов для вашей страны? и использовать это, чтобы очистить информацию о вашей улице / городе / регионе / провинции?

Answer 5

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

Я работаю в фирме, где мы должны точно решить эту проблему - боюсь, я должен сказать вам, что такого рода проверка списков адресов для навигационных систем выполняется "вручную" большую часть времени. Сокращения иногда зависят от контекста, и есть другие вещи, которые затрудняют это. Ofc замена строки и т. Д. Выполняется с помощью python, но рассказывает вам ЗНАЧЕНИЕ такого аббревиатуры. может быть сделано только по сценарию в нескольких случаях. («Св.» -> Может быть «Святой» и «Улица». Как решить? Невозможно ... это человеческая работа.).

Другая большая проблема заключается в том, как вы сказали: "Есть ли улица" DJones "или человек? Или и то и другое? Какой из них здесь? Является ли этот DJones таким же, как доктор Джонс или тем же, что и Дон Джонс? Это невозможно решить". !

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

Answer 6

Я нашел отличную статью.

Добавление некоторых библиотек в виде sql пользовательских функций мы можем использовать алгоритмы сравнения строк с использованием библиотеки SimMetrics .

Проверьте это

http://anastasiosyal.com/archive/2009/01/11/18.aspx

Answer 7

Я предполагаю, что время отклика не является критическим и что проблема заключается в нахождении существующего адреса в базе данных, а не в слиянии дубликатов.Я также предполагаю, что база данных содержит большое количество адресов (скажем, 3 миллиона), а не число, которое можно было бы очистить экономически вручную или механическим турком Amazon .

Предварительное вычисление - определение фрагментов адреса с высоким содержанием информации.

1. Определение всех уникальных слов, используемых в каждом поле базы данных, и подсчет их вхождений.
2. Исключите очень распространенные слова и сокращения.(Улица, улица, апп, апт и т. Д.)

При представлении с входным адресом

1. Определить наиболее уникальное слово ипоиск (Street LIKE '% Jones%') существующих адресов, содержащих эти слова.
2. Используйте предварительно вычисленную статистику, чтобы оценить, сколько адресов будет в наборе результатов.
3. Если набор оценочных результатов слишком велик, выберите второе самое уникальное слово и объедините его вsearch (Street LIKE '% Jones%' AND Town LIKE '% Anytown%')
4. Если оценочный набор результатов слишком мал, выберите второе наиболее уникальное слово и объедините его в поиске (Street LIKE '% Aardvark% 'OR Town LIKE'% Anytown ')
5. , если набор результатов фактический слишком велик / мал, повторите запрос, добавив дополнительные термины, как и раньше.

Идея состоит в том, чтобы найти в адресе достаточно фрагментов с высоким содержанием информации, которые можно искать, чтобы найти разумное количество альтернатив, а не найти наиболее оптимальное соответствие.Для большей устойчивости к орфографическим ошибкам вместо слов можно использовать триграммы, тетраграммы или коды soundex.

Очевидно, что если у вас есть списки реальных штатов / городов / улиц, то некоторая очистка данных может выполняться как вв базе данных и в поисковом адресе.(Я очень удивлен, что Армянская почтовая служба не предоставляет такой список, но я знаю, что некоторые почтовые службы взимают за эту информацию чрезмерные суммы.)

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

(Также подумайте о подходе, основанном на латеральном мышлении: можете ли вы найти брокерскую компанию по рассылке почтовых заказов, которая очистит вашу базу данных для вас? Возможно, они даже захотят заплатить вам за использование адресов.)

Answer 8

Рассматривали ли вы службы интеграции SQL Server для этого?Компонент Fuzzy Lookup позволяет находить «Совпадения рядом»: http://msdn.microsoft.com/en-us/library/ms137786.aspx

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

Здесь приведен пример сопоставления адреса: http://msdn.microsoft.com/en-us/magazine/cc163731.aspx

Answer 9

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

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

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

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

После того, как вы последовательно обработали ввод, n-граммы смогут найти похожие адреса.

Answer 10

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

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

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

РЕДАКТИРОВАТЬ: (возможно, я должен уточнить, что я предполагал, чтоимена исполнителей чаще встречаются чаще, чем названия песен.)