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

Ответ 1

Предложите подходить к этому так:

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

• Сделайте много сравнения x для сравнения строк и скопируйте их по строковому расстоянию. Кто-то предложил Левенштейну; есть лучшие для этой задачи, расстояние Яро-Винклера и Смит-Уотерман работают лучше. Библиотека, такая как SimMetrics, облегчит жизнь.

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

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

Обновление. Основываясь на вашем обновлении выше, предлагаем следующие шаги

• Сгруппируйте свои столбцы в одну строку, возможно, создайте db-представление. Например,

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

• Напишите отдельное приложение (скажем, в Java или С#/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. Наконец, вы можете упорядочить по сходству, чтобы получить кластер из самых похожих адресов и решить подходящий порог. Не знаете, почему вы застряли.

Ответ 2

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

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

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

Ответ 3

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

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

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

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

Ответ 4

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

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

Ответ 5

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

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

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

Вы также получите эти строки от "H. Baskerville", "Sir Henry Baskerville Smith" и, к сожалению, "Гарольд Смит", но мы говорим о нечеткой совпадении здесь!

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

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

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

Ответ 6

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

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

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

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

Ответ 7

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

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

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

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

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

Ответ 8

Просматриваете ли вы службы интеграции SQL Server? Компонент Fuzzy Lookup позволяет найти "Близкие совпадения": http://msdn.microsoft.com/en-us/library/ms137786.aspx

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

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

Ответ 9

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

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

• Определите все уникальные слова, используемые в каждом поле базы данных, и подсчитайте их вхождения.
• Устранить очень распространенные слова и аббревиатуры. (Street, st., Appt, apt и т.д.)

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

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

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

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

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

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

Ответ 10

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

Добавляя некоторые dll как sql пользовательские функции, мы можем использовать алгоритмы сравнения строк с помощью библиотеки SimMetrics.

Проверьте

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

Ответ 11

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

Ответ 12

Вы можете выбросить все адреса в веб-службе, например в Google Maps (я не знаю, подходит ли это для этого), и посмотреть, подходят ли они к идентичным GPS-координатам.

Ответ 13

Возможность состоит в том, чтобы таблица словаря в базе данных отображала все варианты в "правильную" версию слова:

*Value* | *Meaning*
Apt.    | Apartment
Ap.     | Apartment
St.     | Street

Затем вы запускаете каждое слово через словарь перед сравнением.

Изменить: это слишком наивно, чтобы быть практичным (см. комментарий).

Ответ 14

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

3 Jane Dr. -> Dr (in 3rd position (or last)) means Drive
Dr. Jones St -> Dr (in 1st position) means Doctor

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

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

Похоже, что некоторые коммерческие продукты должны делать это там.

Ответ 15

Одним из методов может быть применение алгоритма Levenshtein distance в полях адреса. Это позволит вам сравнить строки для сходства.

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