Record Linkage em Big Data na Loft
Na Loft, nós do squad de Market Data realizamos record linkage em grande escala com Spark em nosso pipeline de dados, para deduplicar entidades semelhantes entre as diversas fontes de dados.
Record Linkage, também conhecido como Data Matching ou Entity Resolution, é o processo de encontrar itens similares que representam a mesma entidade entre diferentes fontes de dados.
Existem dois tipos de Record Linkage: Determinístico e Probabilístico.
No determinístico, usamos diversas regras e heurísticas para relacionar duas entidades. Por exemplo, sabemos que a entidade Pessoa é a mesma se o CPF for idêntico.
Já no probabilístico, conhecido também como fuzzy-matching, dependemos da probabilidade de duas entidades serem similares. Aqui são usados métodos como por exemplo: Levenshtein, Jaro–Winkler, Fellegi Sunter, entre outros.
O processo de comparação (matching) executado durante o record linkage é custoso, possuindo a complexidade de um algoritmo de produto cartesiano. Supondo que temos dois conjuntos de dados, cujos tamanhos são dados por M e N respectivamente, então a complexidade assintótica seria de O(M*N).
A seguir veremos um pouco de como funciona o pipeline responsável pelo match de dados, que é composto por dois jobs principais: o de match e do grouping.
Matching com SQL
O match é responsável por comparar uma entidade com todas as outras, e levantar um score do quão parecidas elas são. Uma das formas de realizar essa comparação é através de um produto cartesiano, o qual pode ser feito com SQL usando o CROSS JOIN.
A Tabela 1 foi gerada com o CROSS JOIN. Durante o join, é computado o valor da coluna Score, a qual indica a probabilidade de semelhança entre Entidade e Matches.
Logo abaixo, a Tabela 1 foi transformada para uma versão mais compacta, exibida na Tabela 2. Em ambas versões evitamos a comparação entre entidades idênticas (A com A), contudo, na nova versão, também evitamos comparações comutativas (A com B, B com A) — mais em notas de rodapé ₁.
É importante ressaltar que B não dá match com C. Isso pode ser por diversos motivos. No exemplo, para efeitos de demonstração, foi escolhido o score mínimo de 0.73 para ser um match com confiança alta. Ou seja, tudo abaixo deste threshold deve ser considerado como entidades distintas, e tudo acima como sendo a mesma entidade.
Isso completa a etapa de comparação. Entretanto, ainda é preciso um passo a mais para agrupar ou deduplicar as entidades.
Notas de rodapé
₁ Esta mudança afeta apenas o resultado final, que fica mais compacto para a etapa de agrupamento: reduzimos 6 linhas para 3 linhas. Contudo, não há melhorias relacionadas com a performance do algoritmo. Ou seja, tanto a Tabela 1 quanto a Tabela 2 são resultados de um produto cartesiano.
A query da Figura 1 mostra como gerar uma tabela parecida com a Tabela 2. Na Figura 2 podemos verificar o operador CartesianProduct no Query Plan que o Spark executou.
Agrupamento
O objetivo do processo de agrupamento é o de juntar todas as entidades semelhantes em grupos distintos. A definição de semelhança vai depender de qual método foi usado durante a etapa de comparação: probabilístico ou determinístico.
No método determinístico é mais fácil agrupar itens semelhantes, já que a definição de semelhança é binária: a entidade é ou não é a mesma. Já no probabilístico, é necessário definir um threshold de certeza sobre o score. A escolha de um threshold ótimo envolve técnicas de ciência de dados e aprendizado de máquina, como matriz de confusão e métricas como acurácia e precisão. Dada a complexidade do tema, isso não será discutido neste artigo.
Agrupamento V1.0
Nossa primeira versão do pipeline de agrupamento rodava em cima da Tabela 1. A Figura 3 mostra uma versão simplificada de como o agrupamento era feito com uma query SQL.
O resultado deste agrupamento são três grupos, um para cada entidade. Sendo eles:
- K = {A,B,C}
- N = {A,B}
- M = {A,C}
Aqui já podemos notar dois problemas. O primeiro é que existem subgrupos, N ⊆ K e M ⊆ K. O segundo problema é que B e C foram agrupados, mas de acordo com nossa regra de threshold de score, eles deviam estar separados, já que não são itens semelhantes.
Relação com Grafos
Uma observação interessante sobre este agrupamento: o grupo formado é composto pela entidade e todos os seus vizinhos. Isso porque, K é formado pelas arestas B<-A->C, N por B->A e M por C->A.
Modelando o Problema como um Grafo
Com o insight do agrupamento V1.0, ao observar novamente a Tabela 2, notamos que ela tem a propriedade de ser uma lista de arestas não direcionadas.
Sabendo disso, passamos a usar esta versão mais compacta do resultado do record linkage para remodelar o problema usando um grafo como estrutura de dados.
A Figura 4 mostra como a Tabela 2 ficaria modelada como um grafo. Lembrando que B perdeu a aresta com C por causa do filtro de threshold de score que havíamos mencionado.
Com as entidades ligadas por arestas, formando um grafo não-direcionado, agora temos algumas formas possíveis de agrupamento, cada uma resultando em grupos diferentes.
Segue lista de possíveis algoritmos de agrupamento de subgrafos que consideramos:
- Neighbors
- Connected Components
- Max Cliques
Neighbors (Vizinhos)
Como já discutimos anteriormente na versão 1, este algoritmo trouxe alguns problemas nos grupos, como a formação de subgrupos, e itens não semelhantes dentro do mesmo conjunto.
Agrupamento V2.0 — Connected Components
O algoritmo Connected Components (componentes conexas) agrupa todos os vértices que possuem alguma conexão, independente do grau, e que não fazem parte de um de um subgrafo maior.
A Figura 5 mostra quatro diferentes exemplos de arranjamentos de arestas entre os vértices {A, B, C, D}, e como eles seriam agrupados. Se os arranjamentos da figura fizessem parte do mesmo grafo, ou seja, cada arranjamento fosse entre diferentes vértices, teríamos então quatro grupos como resultado do algoritmo.
Apesar deste algoritmo não gerar subgrupos como o de Neighbors, ele também tem o problema de agrupar itens não semelhantes. Dado esse comportamento, decidimos ir com a versão 3, usando o algoritmo de Max Cliques.
Agrupamento V2.1 — Max Cliques
Em determinados contextos, para que os vértices sejam considerados uma mesma entidade é necessário que todos os elementos relacionados sejam suficientemente parecidos com todos os outros elementos do mesmo grupo.
De acordo com a teoria dos grafos, um clique (conhecido também como grafo completo) é um grafo ou subgrafo em que todo mundo se conhece, ou seja, existe uma aresta entre todos os pares contidos naquele conjunto. Um clique máximo, ou max clique, é simplesmente um clique que não é um subconjunto de nenhum outro clique.
A Figura 6 mostra os mesmos arranjamentos de arestas entre os vértices {A, B, C, D} da Figura 5, mas agora os agrupamentos foram formados de acordo com o algoritmo de max cliques. O resultado é a formação de nove grupos — cinco a mais do que o visto anteriormente.
Conclusão
O processo de record linkage pode ser determinístico ou probabilístico. Na etapa seguinte da comparação, o agrupamento precisa ser realizado, A criação de grupos pode ser feita de diversas formas, sendo que aqui neste artigo foram apresentadas três, sendo elas: vizinhos, componentes conexas, clique máximo.
Como mencionado acima, aqui na Loft realizamos record linkage em grande escala com Spark em nosso pipeline de dados, para deduplicar entidades semelhantes entre as diversas fontes de dados.
Assim como é feito no aprendizado de máquina, também separamos nosso dataset em dois, um para treino e outro para testes, durante a evolução do nosso modelo de record linkage e agrupamento. Isso foi muito útil para saber onde estávamos, e aonde gostaríamos de chegar.
Foram diversos experimentos. A cada iteração, utilizamos métricas como acurácia, precisão e matriz de confusão para medir os resultados. Além disso, observamos também estatísticas em relação à formação dos grupos, como o tamanho médio, diâmetro e densidade.
Por fim, tivemos os melhores resultados com a mudança de match probabilístico para determinístico, e com a alteração do agrupamento para usar o algoritmo de clique máximo. O resultado final foi uma grande melhoria na deduplicação, que passou de 72% para até 98% de acurácia.
