Как создать алгоритм нечеткого поиска на Python

Вся нечеткость Python

Несколько месяцев назад мой коллега по PeriShip YiQing Lan обратился ко мне с проблемой определения правильного клиента из плохо отформатированных данных о доставке. В то время он уже запускал код в продакшене. Они были реализованы в обычных операторах if-else. YiQing интересовался, могу ли я придумать лучший способ улучшить коэффициент соответствия.

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

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

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

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

Весь процесс можно резюмировать следующим образом:

1. Предварительная обработка данных

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

2. Найдите название компании с самым высоким коэффициентом

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

Например, предположим, что в отгрузке указано название компании «ohara cartwright andstracke». В списке названий компаний, которые потенциально соответствуют ему, с использованием нечеткого сопоставления строк, «O’Hara, Cartwright and Stracke» имеет более высокое соотношение, чем другие кандидаты, поэтому оно считается наиболее подходящим названием компании.

Код

from rapidfuzz import process
string_to_match="ohara cartwright andstracke"
string_candidates=["Cartwright PLC", "O'Hara, Cartwright and Stracke", "Stracke and Sons", "O'Hara, White and Moore"]
matches = process.extract(string_to_match, string_candidates)
for match in matches:
    print(f"{match[0]}: {match[1]:.2f}")

Вывод

O'Hara, Cartwright and Stracke: 94.74
Cartwright PLC: 85.50
O'Hara, White and Moore: 60.00
Stracke and Sons: 54.78

3. Оценка и выбор наиболее эффективных пакетов, подходов и функций.

Существует несколько пакетов Python Fuzzy String Matching, и я сузил кандидатов до двух: Fuzzy Wuzzy (SeatGeek, 2020) и Rapid Fuzz. (Бахманн, 2021). Оба пакета имеют два подхода и восемь функций (счетчик / математическая модель / алгоритм) (Way Script, nd) на выбор, что дает 2 * 2 * 8 = 32 комбинации (см. Рисунок 1), а скорость сопоставления и время работы варьируются. при каждой комбинации.

В частности, для двух подходов вы можете либо использовать счетчики непосредственно из Python, fuzz.scorer(str2match, strOptions), либо комбинировать счетчик с extractOne, то есть process.extractOne(str2match, strOptions, scorer).

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

• Коэффициент соответствия = количество отправлений с правильным соответствием / общее количество отправлений * 100%
• Уровень достоверности = количество отправлений с сопоставлением, соотношение которого больше или равно определенному порогу (например, 90) / общее количество отправлений * 100%
• Правильность выше достоверности в процентах = Количество отправлений с правильным соответствием / Количество отправлений с сопоставлением, которое имеет соотношение, превышающее или равное определенному порогу (например, 90) * 100%
• Среднее время доставки = время выполнения / общее количество отправлений.

Вышеупомянутый критерий степени соответствия является нашим главным приоритетом.

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

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

Наконец, мы также учитываем среднее время доставки.

Сравнение производительности различных комбинаций представлено на Рисунке 2 и Рисунке 3. Можно заметить, что большинство функций достигли процентного соотношения выше 90%, а коэффициент W немного превосходит другие кандидаты. Между тем, Rapid Fuzz в большинстве случаев быстрее, чем Fuzzy Wuzzy, и этот подход мало влияет на время выполнения.

В конце концов, я решил использовать функцию W Ratio пакета Rapid Fuzz с методом нечеткости. Основными факторами, которые принимали во внимание, были более высокий коэффициент соответствия и более короткое среднее время доставки.

4. Реализуйте решение на Python.

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

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

Код, связанный с этим исследованием, можно найти в этом репозитории GitHub. Если вас интересует бизнес-проблема, связанная с этим исследованием, и решение, которое приводит к окончательной реализации, пожалуйста, посетите статью YiQing: Для ИИ или не для ИИ? Не в этом вопрос .

Ссылки

Бахманн, М. (2021) Rapid Fuzz. Получено с https://github.com/maxbachmann/RapidFuzz

SeatGeek. (2020). Fuzzy Wuzzy. Получено с https://github.com/seatgeek/fuzzywuzzy

Сценарий пути. (нет данных). FuzzyWuzzy. Получено с https://docs.wayscript.com/library/modules/fuzzywuzzy.

Википедия. (2021 г.). Приблизительное соответствие строк. Получено с https://en.wikipedia.org/wiki/Approximate_string_matching

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

Больше контента на plainenglish.io