Fuzzy string matching
Comparando strings e aproximando igualdades
Introdução
Várias vezes, nós temos texto como parte dos nossos dados (strings). Em várias aplicações (não só em machine learning), esses dados vem de usuários - quando você preenche um formulário, coloca seu nome, endereço, etc.
O problema é que muitas pessoas não escrevem os dados igual. Por exemplo, eu ja vi meu nome escrito como murilo, Murilo, murilio, murillo, Murilo, Mr. Murilo, etc. Mas todos essas strings deveriam se referir pra mesma coisa. Como que a gente pode decidir se esses são iguais ou não?
Fuzzy string matching
Os algoritmos que resolvem esse problema se chamam fuzzy string matching, ou aproximações em comparações de strings. Um algoritmo popular é a distância Levenshtein, que basicamente vai computando quantas alterações você teria de fazer entre as duas strings. Por exemplo, indo de kitten para sitting (exemplo do Wikipedia:
$$kitten \rightarrow \textbf{s}itten\rightarrow sitt\textbf{i}n \rightarrow sittin\textbf{g}$$
A distância Levenshtein nesse caso é 3, porque temos 3 transformações entre a palavra de origem e a palavra de destino:
- Substituição de
kpors - Substituição de
epori - inserção de
gno final
E essa é a idéia principal (e passando por cima de alguns detalhes 😅). Simples, né? O algoritmo também é implementado com recursão por eficiência, mas quão efficiente é esse algoritmo? Na vida real (especialmente em machine learning), nós temos muitos dados, então é importante vermos como que esse algoritmo escala. Isso é, quanto tempo demora/quanta memória vamos usar enquando o volume de dados aumenta?
FuzzyWuzzy
FuzzyWuzzy é uma biblioteca em python (bem popular) que implementa esse algoritmo. Além disso, o pacote também oferece uma versão mais rápida que faz algumas aproximações. Vamos ver como funciona o API.
# exemplo da documentação da biblioteca
from fuzzywuzzy import fuzz, process
choices = ["Atlanta Falcons", "New York Jets", "New York Giants", "Dallas Cowboys"]
%timeit process.extract("new york jets", choices, limit=2) # só pra registrar o tempo
process.extract("new york jets", choices, limit=2)
%timeit process.extractOne("cowboys", choices) # só pra registrar o tempo
process.extractOne("cowboys", choices)
E é isso! Mas mais uma vez, quanto tempo será que demora quando temos mais dados? Vamos ver.
Conectando ou deduplicando datasets
Um outro caso que é importante é quando temos dois datasets (tabelas nesse caso), algumas colunas tem os mesmos dados, mas elas estão escritos de maneiras diferentes! Ou então, quando os dados se repetem, e temos que deduplicar os dados. Isso acontece por exemplo quando o usuário se registra mas coloca um email ou nome errado, então preenche o formulário de novo. Vamos ver um exemplo.
import pandas as pd
from recordlinkage.datasets import load_febrl1
df = load_febrl1()
df.head()
Vamos focar no nome completo, ou seja o given_name e surname
# collapse
df[["given_name", "surname"]] = df[["given_name", "surname"]].fillna("")
df["full_name"] = df["given_name"] + " " + df["surname"]
df = df[["full_name"]].reset_index()
df.head()
Vamos fazer todas as comparações possíveis! Esse dataset tem só 500 entradas então não tem muito problema
# collapse
df = df.merge(df, how="cross").sample(
frac=1, random_state=42
) # cria todas as combinações e depois mistura as linhas
df = df[
df["full_name_x"] != df["full_name_y"]
] # vamos retirar as que são exatamente iguais
df = df[["rec_id_x", "rec_id_y", "full_name_x", "full_name_y"]].reset_index(
drop=True
) # reorganizando as colunas
df["names"] = pd.Series(
zip(df["full_name_x"], df["full_name_y"])
) # criando a coluna pra comparar os nomes
df.head()
E agora podemos computar o algoritmo!
%%time
df["fuzzywuzzy"] = df["names"].apply(lambda x: fuzz.ratio(x[0], x[1]))
df.head()
Para a nossa tabela com 998512 linhas, o algoritmo demorou 2.9 segundos. Nada mal. E as comparações parecem boas! Alguns exemplos de igualdade:
df[["full_name_x", "full_name_y", "fuzzywuzzy"]].sort_values(
by="fuzzywuzzy", ascending=False
).head()
E alguns exemplos de desigualdade:
df[["full_name_x", "full_name_y", "fuzzywuzzy"]].sort_values(
by="fuzzywuzzy", ascending=False
).tail()
Vamos olhar o tempo mais de perto... Será que a gente poderia melhorar isso?
%timeit df["names"].apply(lambda x: fuzz.ratio(x[0], x[1]))
RapidFuzz
RapidFuzz é uma outra biblioteca em python. Mais nova, que tem algumas pequenas diferenças:
- A licença que eles estão usando é mais permissiva. Aqui você está livre pra usar qualquer licença no seu projeto (no
FuzzyWuzzyvocê era obrigado a usar uma licença GPL). Não muito interessante 🥱 - É mais rapida! Tem algumas melhorias na parte da implementação do algoritmo mas também é implementada em C++!!⚡️⚡️
O quão mais rápida? Vamos ver.
Usando a mesma estratégia de antes:
# usando os mesmo exemplos do início (e também na biblioteca)
from rapidfuzz import fuzz, process # noqa: F811
choices = ["Atlanta Falcons", "New York Jets", "New York Giants", "Dallas Cowboys"]
%timeit process.extract("new york jets", choices, limit=2) # só pra registrar o tempo
process.extract("new york jets", choices, limit=2)
%timeit process.extractOne("cowboys", choices) # só pra registrar o tempo
process.extractOne("cowboys", choices)
Antes o código demorou 89.3µs e 191µs, respectivamente. Agora, demoramos 8.23µs e 14.4µs (<10% do tempo de antes)! Mas como escala? Vamos de novo olhar pro exemplo da deduplicação de dados:
%%time
df["rapidfuzz"] = df["names"].apply(lambda x: fuzz.ratio(x[0], x[1]))
df.head()
E os resultados dos dois algoritmos são exatamente iguais! (Com a pequena excessão que o FuzzyWuzzy retorna números inteiros e o RapidFuzz retorna frações)
%timeit df["names"].apply(lambda x: fuzz.ratio(x[0], x[1]))
Menos 15% do tempo de antes!! Só trocando a biblioteca!
Além disso a documentação faz mais comparações pra diferentes tarefas e como são os números com a maior quantidade de dados.
Pra mais gráficos, fica a documentação.
Uma última coisa...
A gente pode melhorar isso ainda mais quando quisermos deduplicar linhas na minha tabela?
Sim. Mas não na parte algoritmica. Na vida real, temos também de ser espertos na hora de computar as coisas. Se estivermos comparando endereços por exemplo, a rua e número talvez estejam diferentes, mas a cidade e estado provavelmente não, especialmente porque numa grande parte esses vem de um dropdown, então os dados vem "limpos".
Nesses casos, ao invés de criar todas as combinações possiveis, a gente pode criar as combinações dentro de cada grupo - no nosso exemplo quando os estados e cidades são iguais. Reduzindo o número de combinações já reduz bastante o trabalho. E na maioria dos casos, é ai que temos os maiores ganhos. E ainda por cima, existem bibliotecas como o Record Linkage Toolkit que são feitos exatamente pra isso.
Ou seja, as vezes é melhor sentar e pensar antes de ficar quebrando a cabeça em como otimizar um algoritmo. 😇
