Нечеткое сопоставление структурированных данных

Question

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

Записи имеют ширину около 12000 байт, а общее количество записей составляет около 150 000.В схеме таблицы 110 столбцов, и 95% поисковых запросов будут приходиться на верхние 5% наиболее часто используемых столбцов.

Данные представляют собой такие вещи, как имена, адреса, номера телефонов и другие отраслевые показатели.Как в корпусе, так и в тестовой записи он вводится вручную и частично структурирован в отдельном поле.На первый взгляд вы могли бы сказать "взвесьте столбцы вручную и сопоставьте в них словосочетания", но это не так просто.Я тоже так думал:если я получу номер телефона, я думал, это будет означать идеальное совпадение.Проблема в том, что в форме нет ни одного поля, частота токенов которого не менялась бы на порядки.Телефонный номер может появляться в корпусе 100 раз или 1 раз в корпусе.То же самое относится и к любому другому полю.Это делает взвешивание на полевом уровне непрактичным.Мне нужен более детальный подход, чтобы получить достойное соответствие.

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

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

Мой первый вопрос адресован статистикам, присутствующим в зале:как бы я использовал частоту в качестве веса?Существует ли точная математическая зависимость между n, количеством записей, f (t), частотой, с которой токен t появлялся в корпусе, вероятностью o того, что запись является оригиналом, а не дубликатом, и вероятностью p того, что тестовая запись действительно является записью x, учитывая, что тест и x содержат одинаковое значение t в одном и том же поле?Как насчет взаимосвязи для нескольких совпадений токенов в нескольких полях?

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

Исключая это, есть ли у кого-нибудь способ сделать это?

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

Answer 1

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

Более конкретно к рассматриваемой проблеме, вот несколько мыслей и идей:

Во-первых, признавая очень неравномерное использование (только от 6 до 10 атрибутов покрывают 95% использования), вы можете / должны применять асимметричные усилия к атрибутам, т. е.вкладывайте больше средств, как с точки зрения времени программирования, так и с точки зрения выделения ресурсов процессора во время выполнения, для работы с этими несколькими атрибутами, чем со 100 с лишним дополнительными атрибутами.

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

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

• Нормализовать данные
  Если вам не разрешено изменять исходные значения полей, возможно, продублируйте соответствующие столбцы в столбец "norm_xxx", где xxx - исходное имя.
  Что и как нормализовать, может варьироваться в зависимости от каждого атрибута;для данных, подобных "свободному тексту", убедитесь, что в них нет ни начальных, ни конечных пробелов, только один пробел между словами, никаких табуляций и непечатаемых символов.Используйте либо все заглавные, либо все строчные буквы (даже если исходный текст / текст для отображения может содержать смешение, ваша обработка будет проходить быстрее, если вы сможете использовать однородный шрифт).В частности, для адресов и / или названий компаний вы можете преобразовать общие термины в стандартную форму (ST для улицы, ST и ST и т.д.). (Обязательно сохраните этот список, поскольку он также будет применен к критериям поиска пользователей).Частью нормализации также может быть полное исключение некоторых шумовых слов (например, CO, INC, GMBH в конце названий компаний).
• Создайте несколько вычисляемых столбцов
  Например, с текстом в обратном порядке для атрибутов, поиск по которым может осуществляться с помощью завершающего подстановочного знака
• Рассмотрите возможность использования преобразования, подобного Soundex, для некоторых атрибутов.
• Полнотекстовый индекс, по отдельности, для всех текстоподобных столбцов
• Создайте простые индексы (SQL) для всех 6-10 часто используемых столбцов

Все вышеперечисленное - это всего лишь подготовка к проведению матчей в автономном режиме.Сейчас же..пользователь вводит свой запрос...вот несколько идей о том, как с этим справиться

• Нормализуйте критерии поиска, которые этого требуют
• Выполните несколько поисковых запросов...
  Это немного сложно;существует несколько, частично противоречащих друг другу, целей для выполнения этого поиска.Мы хотим значительно сократить количество "потенциальных совпадений".:фактически непрактично проводить полное индивидуальное сравнение всех 150 000 записей с критериями, предоставленными пользователем;например, некоторая логика сопоставления может подразумевать вычисление расстояния редактирования между полем данной записи базы данных и критерием поиска.Мы также хотим убедиться, что мы не исключаем записи из списка "потенциальные совпадения" из-за опечатки, скажем, в названии компании...Наконец, мы хотим представить список потенциальных совпадений в ранжированном виде.
  Способ выполнения этих поисков соответствует некоторым заранее определенным эвристикам (я обнаружил, что шаблон разработки стратегии хорошо подходит для этого, обеспечивая гибкость в способе выполнения поиска в зависимости от введенных пользователем данных).В двух словах, мы ищем наиболее отборные слова по наиболее отборным / релевантным атрибутам и, основываясь на количестве найденных "обращений", мы либо "ИЛИ" (объединение), либо "И" с другими результатами поиска, пока у нас не наберется несколько сотен записей.
• Вычислите значение сходства между каждым атрибутом записей "потенциальных совпадений" и соответствующими критериями поиска.Возможно, применить коэффициент к этому значению (позволяющий придать больший вес предположению о [частичном] совпадении названия компании с названием города).
• Подсчитайте общее значение сходства для полной записи (по сравнениюполные критерии поиска)

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

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