Расчет контекстно-зависимой текстовой корреляции

Question

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

Пример: «West Lawnmower Drive 54 A», вероятно, такой же, как «W. Lawn Mower Dr. 54A», но отличается от «East Lawnmower Drive 54 A».

Как бы вы подошли к этой проблеме? Нужно ли иметь какой-то контекстный словарь, который знает, в случае адреса, что "W", "W". а "запад" одинаков? А как насчет орфографических ошибок («движитель» вместо «газонокосилка» и т. Д.)?

Я думаю, что это сложно - возможно, есть какие-то известные алгоритмы там?

Answer 1

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

• Изменить расстояние (он же расстояние Левенштейна)
• Ratcliff / Obershelp

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

• токенизирует ввод, т.е. видит ввод как массив слов, а не как строку
• токенизация также должна содержать информацию о номере строки
• нормализует ввод с использованием краткого словаря общих замен (таких как «dr» в конце строки = «drive», «Jack» = «John», «Bill» = «William» .. ., "W" в начале строки - "Запад" и т. Д.
• Определение (немного похоже на тегирование, как в тегах POS) природы некоторых объектов (например, почтового индекса и расширенного почтового индекса, а также города
• Идентифицируйте (ищите) некоторые из этих объектов (например, сравнительная короткая таблица базы данных может включать все города / города в целевой области
• Идентифицируйте (ищите) некоторые связанные с доменом объекты (если все / многие адреса касаются, скажем, юристов в юридической профессии, может помочь поиск названий юридических фирм или федеральных зданий.
• Как правило, добавьте больше веса к токенам, которые идут из последней строки адреса
• Надеть больший (или меньший) вес на токены с определенным типом сущности (например, «Драйв», «Улица», «Суд» следует с гораздо меньшим количеством токенов, которые предшествуют им.
• Рассмотрим модифицированный SOUNDEX алгоритм, помогающий нормализовать

Учитывая вышесказанное, реализуйте оценщик на основе правил . Ориентировочно, правила могут быть реализованы как посетители древовидной / массивной структуры, где входные данные анализируются изначально ( Шаблон проектирования посетителя ).
Преимущество основанной на правилах структуры состоит в том, что каждая эвристика выполняет свои собственные функции, и правила могут быть приоритетными, т.е. помещать некоторые правила в начале цепочки, позволяя преждевременно прервать оценку, с некоторой сильной эвристикой (например, другой город = > Корреляция = 0, уровень доверия = 95% и т. Д.).

Важным соображением при поиске корреляций является необходимость a priori сравнить каждый отдельный элемент (здесь адрес) с каждым другим элементом , следовательно, требуется до 1/2 n^2 элемента Уровневые сравнения. Из-за этого может быть полезно хранить ссылочные элементы таким образом, чтобы они были предварительно обработаны (проанализированы, нормализованы ...), а также, возможно, иметь дайджест / ключ сортировки , который может быть используется как [очень грубый] индикатор возможной корреляции (например, ключ из 5-значного ZIP-кода, за которым следует значение SOUNDEX «основного» имени).

Answer 2

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

Answer 3

Я бы посмотрел на создание метрики сравнения подобия, которая, учитывая два объекта (возможно, строки), возвращает «расстояние» между ними.

Если вы соответствуете следующим критериям, то это помогает:

1. расстояние между объектом и сам ноль. (Рефлексивный)
2. расстояние от a до b одинаково в оба направления (переходные)
3. расстояние от А до С не более чем расстояние от а до б плюс расстояние от а до ц. (треугольник править)

Если ваша метрика подчиняется им, вы можете расположить ваши объекты в метрическом пространстве, что означает, что вы можете запускать такие запросы, как:

• Какой другой объект больше всего похож этот
• Дайте мне 5 предметов больше всего нравится этот.

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

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

Я уверен, что вы могли бы придумать что-то более продвинутое, но вы могли бы начать с чего-то простого, такого как сокращение адресной строки до цифр и первой буквы каждого слова, а затем сравнить результат с использованием самого длинного общего алгоритма подпоследовательности. .

Надеюсь, это чем-то поможет.

Answer 4

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

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

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

Answer 5

Отказ от ответственности: Я не знаю ни одного алгоритма, который делает это, но на самом деле было бы интересно узнать его, если он существует. Этот ответ - наивная попытка решить проблему без каких-либо предварительных знаний. Комментарии приветствуются, пожалуйста, не смейтесь слишком хвалите.

Если вы попытаетесь сделать это вручную, я бы предложил применить некоторую «нормализацию» к вашим строкам: сделать их строчными, убрать пунктуацию, возможно заменить обычные сокращения полными словами (Dr. => drive, St => street и т.д ...).

Затем вы можете попробовать различные выравнивания между двумя сравниваемыми строками и вычислить корреляцию, усредняя абсолютные различия между соответствующими буквами (например, a = 1, b = 2 и т. Д. И corr(a, b) = |a - b| = 1):

west lawnmover drive
   w lawnmower street

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