Pentaho – Fuzzy Match

Na série de posts desta semana sobre Pentaho, quero iniciar um assunto que adiei e ficou em aberto que trata sobre lookup!

Como no meu último post sobre joins eu deixei as portas abertas para tratar deste assunto e, como disse, já era um desejo. Começaremos a entender como esse processo todo funciona e, a partir disso, utilizarmos em nossas transformações e projetos pessoais de B.I.

O processo de lookup consiste em procurar dados de um local em outro, então, é de se presumir que são necessárias duas fontes ou uma fonte e um destino.

Outra situação que pode ocorrer é a busca dentro de outra stream em paralelo com o objetivo de igualar as duas para um destino final e único.

LOOKUPS E O PENTAHO

Por ser uma ferramenta de ETL o Pentaho não deixa de ter suas opções de lookup, entregando uma boa variedade de steps para uso, sendo os principais:

• Database lookup.
• Fuzzy match.
• Stream lookup
• Combination lookup
• Dimension lookup
• Web Services lookup

Estes são os principais meios de efetuar um lookup e dependendo do caso, o Merge diff também é bem-vindo.

FUZZY MATCH

Como existe um post sobre o stream lookup pronto, podemos avançar para outro tópico e analisarmos o funcionamento do fuzzy match.

Essa transformação funciona melhor com formato string comparando dois inputs textuais e dependendo do tipo de algoritmo, mostra o nível de paridade entre os dois textos.

Essa task também tem a capacidade de limpar dados de fontes que por algum motivo foram ‘corrompidas’ e perderam o sentido para análise.

Veremos dois exemplos neste post, um comparando paridade e outro mais voltado para limpeza.

O primeiro exemplo que irei utilizar será o de limpeza, utilizando alguns algoritmos que o próprio Pentaho possui de forma nativa, dentro do step.

Na próxima imagem mostro as duas fontes utilizadas para demonstração básica.

Destaco antes de mostrar a configuração do fuzzy match que o ordenamento não influencia na transformação.

No quadrante vermelho é a fonte, onde a busca pelos valores originais serão feitas e o campo main stream field contém os dados que foram ‘corrompidos’. Na caixa azul da imagem acima.

Na segunda parte da configuração, em settings, escolhemos os algoritmos e algumas configurações a mais. 

Cada algoritmo tem uma forma de ação e irei falar mais a respeito no próximo post. Como esse é um post básico e introdutório, irei mostrar apenas as opções de uso.

É possível utilizar variáveis armazenadas para remover alguns caracteres especiais, como fiz no caso do exemplo para limpeza.

NOTA: como os 6 primeiros algoritmos são para comparações textuais, utilizá-los neste exemplo não é tão funcional, logo, somente os quatro últimos ajudam mais. 

Irei mostrar apenas um exemplo de como os algoritmos de comparação funcionam neste exemplo.

Veja o resultado abaixo utilizando o algoritmo Pairs letter similarity. 

Como utilizei uma variável para limpar os caracteres especiais, o próprio algoritmo aplicou ao resultado final. O que daria maior trabalho para limpeza num próximo step.

Agora, veja quando utilizamos os dois algoritmos: metaphone  e double metaphone. 

O algoritmo de metaphone é um pouco mais preciso, pelo menos, neste caso, foi!

Vale destacar que ambos os algoritmos não permitem o uso de variáveis, logo, a ‘limpeza’ ocorreu pelo próprio funcionamento nativo deles.

Utilizando os algoritmos de soundEx e refined soundEx.  O resultado é ainda mais assertivo.

ALGORITMOS DE TEXTOS

No tópico anterior, utilizamos exemplos de dados bem ‘sujos’ e quais seriam os melhores algoritmos dentro do fuzzy match para limpar estes campos.

Porém, como cada situação requer um tipo de solução diferente, não podemos aplicar a mesma solução como base, dito isso, que tal conhecermos os algoritmos de aproximação e cálculo de distância textual?

Como podemos ver, o PDI possui alguns algoritmos especializados nisso, como mostra a imagem abaixo:

Cada um deles age de uma forma diferenciada, por exemplo, o de Levenshtein calcula a distância entre os textos. Já o algoritmo de Damerau-Levenshtein é uma adição ao primeiro que calcula também a distância editável.

Não irei entrar em muitos detalhes sobre o que cada algoritmo faz para o post não ficar muito teórico, mas deixarei links de referência ao final para quem quiser aprender sobre os algoritmos!

Abaixo, a estrutura que iremos utilizar para os testes. Por ser um teste básico, criei uma estrutura simples com textos similares.

Aqui, temos as duas fontes de dados para comparação. A fonte em vermelha é a base que o step fará a ‘busca’, aqui no caso, seria comparação; e a azul, a fonte que vamos ‘normalizar’.

Um adendo importante é que para essa etapa configurei o campo field para ter uma compreensão mais clara sobre o funcionamento desta transformação, veja:

Nas duas primeiras imagens, irei testar os algoritmos de Levenshtein(vermelho) e Damerau Levenshtein(azul).

Destaquei em vermelho e azul os resultados respectivos. Perceba que foram exatamente iguais, devido a ação do algoritmo até. Como expliquei brevemente, eles trabalham por aproximação.

A coluna match (configurada no campo field do step) informa mostra com qual valor do campo original ela foi correspondente, e a coluna measure value, o nível de correspondência – aqui vai de 0 – 1.

Agora vamos comparar o resultado utilizando os algoritmos de Jaro. Esse também possui uma variação que é o Jaro – Winkler.

Comparando os dois algoritmos e suas variações podemos perceber que embora o algoritmo de Levenshtein consiga um bom resultado e comparações certeiras, o de Jaro é, de um modo geral, mais preciso e assertivo. Retornando inclusive, campos que o primeiro não conseguiu.

E na comparação “interna” do resultado entre Jaro e Jaro-Winkler(azul) o que percebemos é que o segundo tem um aproveitamento e uma precisão melhor. Este parece ser mais aprimorado.

E por fim, temos a comparação entre os algoritmos de Needleman Wunsch e Pairs letter.

O algoritmo de  Needleman Wunsch funciona da mesma forma que o Levenshtein, inclusive quando não consegue entregar os resultados; já o Pairs letter trabalha com pareamento entre letras o que garante uma precisão ainda maior.

Veja que no resultado azul, nenhuma das comparações conseguiu um resultado > 0.8 justamente por executar um pareamento entre cada letra do campo string.

E como algumas dessas strings estão ‘sujas’, o algoritmo não consegue realizar a comparação retornando uma avaliação mais baixa.

Algumas considerações

Aumentar  o número de cópias não melhora o desempenho, geralmente piora.

Fuzzy match é um processo lento, então, cuidado com a quantidade de dados que serão analisados nas comparações. Trabalhe sempre com blocos pequenos e restritos. 

Procure dividir em blocos ordenados alfabeticamente, e lembre-se que a transformação trabalha com string.

Prefira usar os algoritmos de Jaro e Pairs Letters, sempre que possível, é claro. Além de eliminar impurezas da fonte, é possível medir a qualidade dos dados que estão passando pela stream.

Opte pelo metaphone e soundEx sempre que houver caracteres especiais que são oriundos de collate ou data type diferente. Isso é muito comum quando temos um campo varchar no banco e por algum motivo, ele não entende aquele caractere que está sendo registrado. O que não aconteceria se fosse nvarchar. 

Cuidado com dados duplicados, pode ser um problema na comparação das strings.

Links dos algoritmos:

Levenshtein_distance

Wunsch_algorithm

Winkler_distance

Download da transformação, aqui.