Construa um mecanismo de pesquisa escalonável para correspondência de strings difusas

Christoph Ostertag em Rumo à Ciência de Dados Seguir em 28 de junho · 6 min ler Fonte: https://emerj.com/wp-content/uploads/2018/04/3-waves-of-ai-transformation-in-industry-pattern-matching-ubiquitous-access-and-deductive-reasoning.png

Na coincidência fuzzy, nosso objetivo é marcar a string A para a string B em termos de quão próximos eles estão juntos. Queremos encontrar cadeias semelhantes. Por exemplo, "prefeito" pode ser muito próximo de "grande", ou algo como "ameaça" muito perto de um erro de digitação como "thraet", mas também "Christoph Alexander Ostertag" pode ser muito próximo de "Christoph Ostertag". Existem vários algoritmos para calcular essas distâncias.

Distância Levenshtein

O número mínimo de substituições, excluir e inserir operações necessárias para transformar a cadeia A na cadeia B. “Major” e “Mayor” precisariam apenas de uma operação de cadeia de caracteres. Basta desligar o "j" e "y".

Distância Jaccard

O número de subparts correspondentes da string A e B. Essas subpartes podem ser palavras inteiras ou geralmente n-grams. N-gramas são partes de uma cadeia que consiste em n elementos divididos por uma janela deslizante. "Major" se separaria com um n de 3 em {"Maj", "ajo", "jor"}. Na verdade, neste caso, cada elemento seria diferente de "Mayor", que se divide em {"May", "yao", "aor"}. Poderíamos usar um n mais baixo para encontrar semelhanças, no entanto, isso significaria que também correspondemos a partes menores das strings que podem aparecer com mais frequência no conjunto de strings.

(Lembre-se dos n-gramas, eles serão importantes mais tarde!)

Semelhança cosseno

Isso também é semelhante à distância do jaccard. Nós dividimos nossas strings em n-grams primeiro. Uma vez que fizemos isso, primeiro nós tokenizamos os n-gramas e então vetorizamos os tokens. Isso poderia ser algo assim.

  1. N-grama: “Major” -> {“Maj”, “ajo”, “jor”}
  2. Tokenize: {“Maj”, “ajo”, “jor”} -> {0,2,3}
    Dicionário de exemplo para o tokenizer:
    {"Maj": 0, "ped": 1, 2: "ajo", 3: "jor",…}
  3. Vetorizar: é a mesma coisa que uma codificação quente. O número de nossos tokens se torna o índice do vetor. Contamos quantas vezes cada palavra aparece.
    {0,2,3} -> [1,0,1,1]

Uma vez que tenhamos uma representação vetorial, nós as normalizamos. Isso significa formar o vetor unitário que tem um comprimento de 1. Então calculamos o ângulo entre os vetores.

Semelhança cosseno. Fonte: https://www.oreilly.com/library/view/statistics-for-machine/9781788295758/assets/2b4a7a82-ad4c-4b2a-b808-e423a334de6f.png

Um probleminha suja – Escalabilidade

Vamos fazer um cálculo simples. Em nosso caso de uso, temos um banco de dados de nomes de 10 MB. Soa não como big data, certo? Agora vamos dizer que cada palavra consiste em uma média de 10 caracteres codificados por 1 byte cada. Isso significa que temos um banco de dados que consiste em 10 MB / (10 bytes / word) = 1.000.000 palavras. Não tão pouco, mas agora fica interessante. Para cada palavra, queremos encontrar as palavras mais próximas. Para fazer isso, temos que fazer uma string de comparação de strings de 1M para strings de 1M. Imaginando isso como uma matriz com o tamanho de 1M * 1M entradas.

Matriz de Similaridade. Fonte: https://kapilddatascience.files.wordpress.com/2016/05/san_francisco_sim_matrix.png

Se usarmos números de ponto flutuante de 32 bits e três métricas por comparação, isso resultará em 96 bits por comparação ou metade disso, porque todas as métricas de similaridade são unidirecionais. Multiplicar isso por 1M * 1M leva a um escalonamento de 4,5 TB apenas para armazenar essa matriz. Calculá-lo é ainda mais difícil. Tudo se resume a 1,5 trilhões de cálculos. Levaria meses em um computador normal, como o que estou escrevendo este artigo no momento.

Então o que nós podemos fazer? Primeiro devemos olhar para a notação Big O.

Esse algoritmo é dimensionado para o poder de dois. Se dobrarmos o número de strings para comparar, quadruplicaremos o tempo de computação. A notação grande O é T (n) = O (n²). O que gostaríamos de ter é O (n), onde se duplicarmos as strings para comparar o tempo de computação, também duplicaremos. Isso significaria, no entanto, que devemos comparar nossos n strings com um número constante de outras strings.

Podemos excluir strings que não queremos comparar? Por que devemos comparar "Major" com "Burger King"? Isto faz algum sentido?

Se quisermos fazer menos comparações, digamos, comparar nossas strings de 1M com apenas 100 strings, precisaríamos excluir 99,99% dos dados. Excluir 99,99% dos nossos dados significa também reduzir o tempo de computação em 99,99%.

Construa dicionários de pesquisa

Normalmente usamos indexação para pesquisa rápida, mas isso só funciona se compararmos algo como ("Anastasia", "Student") com ("Anastassia", "Student"). Então podemos combinar exatamente na mesma linha “aluno” e encontrar um link de Anastasia para Anastassia. Mas no nosso caso, assumimos que não temos informações extras.

Como poderíamos combinar Anastasia com Anastassia? Lembre-se de n-gramas?
0: {"Ana", "nas", "ast", "sta", "tas", "ast", "sta", "tas", "asi", "sia"}
1: {"Ana", "nas", "ast", "sta", "tas", "asno", "sst", "sta", "tas", "asi", "sia"}
Fechar, certo? Na verdade, combinamos exatamente 9 n-gramas.

Vamos apenas construir um dicionário de pesquisa então.

  1. Primeiro mapeamos todos os n-gramas para todos os índices das palavras:
    {“Ana”: [0, 1],…, “sst”: [1], “pap”: [1, 2],…}

2. Em seguida, crie outro dicionário de pesquisa. Agora, basta combinar todos os índices com todos os outros índices que aparecem juntos. Isso também é possível ao fazer o loop uma vez no primeiro dicionário. {0: [0, 1], 1: [0, 1, 2], 2: [1, 2]}

Agora temos que comparar 0 apenas com 0 e 1, mas não 2. E também temos que comparar 2 apenas com 1 e 2. É claro que essa economia computacional é apenas pequena. Mas se o tamanho médio dos jogos agora cair para digamos 100, nós realmente economizamos 99,99% do tempo de computação para calcular nossas distâncias (Levenshtein, Jaccard, Cosine).

Existem algumas propriedades diferentes que você pode usar para correspondência:

  • N-gramas de tamanhos diferentes => n = {2,3,4,5,6,…}
  • Palavras da string => “Christoph” de “Christoph Ostertag”
  • Outras propriedades de Nome => É estudante, tem o mesmo ID de cliente, número de segurança social,…
  • Indústria / Tópico Balde => Tem algumas palavras em comum para um determinado balde: {basquete, tênis} tanto nos esportes

Considerações práticas

  1. Profundidade de pesquisa:
    Só podemos comparar nossa string a outras strings com as quais nossa string está em relação direta ou podemos aumentar nossa profundidade de pesquisa para procurar por strings que tenham relação com strings que nossa string tenha relação com.
    (String A -> Strings (Depth 1) -> Strings (Depth 2))
  2. Overmatching – Reduzindo a conectividade do gráfico:
    Se combinarmos nossas strings com muitas outras strings, remover os n-grams mais comuns ou outras propriedades com as quais combinamos pode ser útil. Combinar todos os AGs juntos pode não ser muito útil. Portanto, apenas definimos a frequência com que uma correspondência deve ser permitida ou qual porcentagem da maioria das correspondências que desejamos eliminar.

Conclusão

Tornar a correspondência fuzzy útil é possível, basta pensar em como torná-la escalável e o que realmente queremos alcançar com ela. Queremos apenas encontrar erros de digitação ou queremos combinar empresas ou pessoas que poderiam ser iguais. Há muito o que podemos fazer, e a discussão deve ser menos sobre qual é a melhor coisa a fazer em geral, mas que caso de negócio estamos tentando resolver.