Processamento de Linguagem Natural para Fuzzy String Matching com Python

Na ciência da computação, fuzzy string matching é a técnica de encontrar cordas que combinam com um padrão aproximadamente (ao invés de exatamente). Em outra palavra, o fuzzy string matching é um tipo de busca que vai encontrar correspondências mesmo quando os usuários digitam palavras erradas ou digitam apenas palavras parciais para a busca. Também é conhecido como correspondência aproximada de cadeia de caracteres.

Pesquisa de cadeia de caracteres difusa pode ser usada em várias aplicações, tais como:

• Um corrector ortográfico e corrector ortográfico, corrector ortográfico. Por exemplo, um usuário digita “Missisaga” no Google, uma lista de acertos é retornada juntamente com “Mostrando resultados para Mississauga”. Ou seja, a consulta de pesquisa retorna resultados mesmo que a entrada do usuário contenha caracteres adicionais ou ausentes, ou outros tipos de erro ortográfico.
• Um software pode ser usado para verificar se há registros duplicados. Por exemplo, se um cliente é listado várias vezes com diferentes compras na base de dados devido a diferentes ortografias do seu nome (ou seja, Abigail Martin vs. Abigail Martinez) um novo endereço, ou um número de telefone inserido por engano.

Fala de deduplicação, pode não ser tão fácil como parece, em particular se você tiver centenas de milhares de registros. Mesmo a Expedia não faz 100% certo:

>

>>

Este post vai explicar o que é o fuzzy string matching junto com seus casos de uso e dar exemplos usando a biblioteca Fuzzywuzzy de Python.

Cada hotel tem sua própria nomenclatura para nomear seus quartos, o mesmo cenário vai para a Agência de Viagens Online (OTA). Por exemplo, um quarto no mesmo hotel, Expedia chama “Studio, 1 King Bed with Sofa bed, Corner”, Booking.com pode achar seguro mostrar o quarto simplesmente como um “Corner King Studio”.

Não há nada de errado aqui, mas pode levar a confusão quando queremos comparar a tarifa do quarto entre OTAs, ou uma OTA quer ter certeza que outra OTA siga o acordo de paridade de tarifas. Em outra palavra, para poder comparar preços, temos que ter certeza de que estamos comparando maçãs com maçãs.

Uma das questões mais consistentemente frustrantes para sites e aplicativos de comparação de preços é tentar descobrir se dois itens (ou quartos de hotel) são para a mesma coisa, automaticamente.

Fuzzywuzzy é uma biblioteca Python que usa a distância Levenshtein para calcular as diferenças entre sequências num pacote simples de usar.

A fim de demonstrar, eu crio meu próprio conjunto de dados, ou seja, para a mesma propriedade de hotel, eu pego um tipo de quarto da Expedia, vamos dizer “Suite, 1 King Bed (Parlor)”, então eu faço a correspondência com um tipo de quarto em Booking.com que é “King Parlor Suite”. Com um pouco de experiência, a maioria dos humanos saberia que eles são a mesma coisa. Siga esta metodologia, eu crio um pequeno conjunto de dados com mais de 100 pares de tipos de quartos que podem ser encontrados em Github.

Usando este conjunto de dados, vamos testar como o Fuzzywuzzy pensa. Em outras palavras, estamos usando Fuzzywuzzy para combinar registros entre duas fontes de dados.

import pandas as pddf = pd.read_csv('room_type.csv')
df.head(10)

>>

>

>>

O conjunto de dados foi criado por mim, portanto, é muito limpo.

Há várias formas de comparar duas cordas em Fuzzywuzzy, vamos tentar uma a uma.

• ratio , compara toda a similaridade de cordas, por ordem.

from fuzzywuzzy import fuzz
fuzz.ratio('Deluxe Room, 1 King Bed', 'Deluxe King Room')

Isto está a dizer-nos que o par “Quarto Deluxe, 1 Cama King” e “Quarto Deluxe King” são cerca de 62% iguais.

fuzz.ratio('Traditional Double Room, 2 Double Beds', 'Double Room with Two Double Beds')

O par “Quarto Duplo Tradicional, 2 Camas Duplas” e “Quarto Duplo com Duas Camas Duplas” são cerca de 69% iguais.

fuzz.ratio('Room, 2 Double Beds (19th to 25th Floors)', 'Two Double Beds - Location Room (19th to 25th Floors)')

O par “Quarto, 2 Camas de Casal (19º a 25º andar)” e “Duas Camas de Casal – Quarto de Localização (19º a 25º andar)” são cerca de 74% iguais.

Sinto-me desapontado com estes. Acontece que a abordagem ingênua é muito sensível a pequenas diferenças na ordem das palavras, palavras ausentes ou extras, e outras questões do gênero.

• partial_ratio , compara similaridade parcial de string.

Ainda estamos usando os mesmos pares de dados.

fuzz.partial_ratio('Deluxe Room, 1 King Bed', 'Deluxe King Room')

fuzz.partial_ratio('Traditional Double Room, 2 Double Beds', 'Double Room with Two Double Beds')

fuzz.partial_ratio('Room, 2 Double Beds (19th to 25th Floors)', 'Two Double Beds - Location Room (19th to 25th Floors)')

Para o meu conjunto de dados, comparar string parcial não traz melhores resultados em geral. Vamos continuar.

• token_sort_ratio , ignora a ordem das palavras.

fuzz.token_sort_ratio('Deluxe Room, 1 King Bed', 'Deluxe King Room')

fuzz.token_sort_ratio('Traditional Double Room, 2 Double Beds', 'Double Room with Two Double Beds')

fuzz.token_sort_ratio('Room, 2 Double Beds (19th to 25th Floors)', 'Two Double Beds - Location Room (19th to 25th Floors)')

Best até agora.

• token_set_ratio , ignora as palavras duplicadas. É semelhante com a relação de classificação de fichas, mas um pouco mais flexível.

fuzz.token_set_ratio('Deluxe Room, 1 King Bed', 'Deluxe King Room')

fuzz.token_set_ratio('Traditional Double Room, 2 Double Beds', 'Double Room with Two Double Beds')

fuzz.token_set_ratio('Room, 2 Double Beds (19th to 25th Floors)', 'Two Double Beds - Location Room (19th to 25th Floors)')

Parece que token_set_ratio é o melhor ajuste para os meus dados. De acordo com esta descoberta, eu decidi aplicar token_set_ratio a todo o meu conjunto de dados.