Construção Indutiva Evolucionária aplicada ao problema de deduplicação de registros

Resumo

Identificar corretamente registros duplicados em grandes bases de dados é uma tarefa complexa e necessária para manter a consistência de bases de dados. Em um hospital, por exemplo, ter registros duplicados de pacientes pode gerar desde pequenas inconveniências administrativas a erros de diagnósticos devido à divisão não intencional dos dados entre os registros.

O processo de deduplicação de registros pode ser considerado complexo por envolver vários estágios e técnicas e é pesquisado desde a década de 1960, tendo início com o trabalho de Fellegi e Sunter (1969). Desde então, diversas abordagens têm sido apresentadas na literatura buscando-se melhorar a eficácia desse tipo de tarefa, como a abordagem descrita por Carvalho et al. (2012), que, até onde vai nosso conhecimento, foi o primeiro a aplicar programação genética no processo de deduplicação de registros.

Neste trabalho, apresenta-se uma abordagem de aprendizado supervisionado baseada em programação genética (GP) e árvores de decisão, gerando classificadores capazes de identificar duplicatas de registros com altos índices de precisão e revocação. Para tanto, é apresentada uma nova heurística de geração de população inicial do GP, além da definição de regras de ligação utilizando uma abordagem baseada em pontos de corte variáveis. Também é apresentado o uso de construção indutiva evolucionária, que utiliza o melhoramento dos indivíduos criado pelo GP para gerar novas propriedades na base de dados e classificá-las posteriormente utilizando indução de árvores de decisão. Os resultados experimentais mostram que a abordagem apresenta melhorias em termos de expressividade e de fitness das soluções geradas, mesmo em seu caso mais simples, quando comparados ao estado-da-arte.