BLOCAGEM ADAPTATIVA E
FLEXÍVEL PARA O
PAREAMENTO APROXIMADO
DE REGISTROS
Luiz Evangelista, Eli Cortez, Altigran Soares – UFAM
Wagner Meira - UFMG
ROTEIRO

Introdução


Definição do Problema e exemplo.
Trabalhos relacionados

Métodos estáticos e dinâmicos

O Método BGP

Resultados experimentais

Conclusões e trabalhos futuros.
INTRODUÇÃO

Um dos principais problemas encontrados em integração de
dados é: identificar registros que correspondam a
mesma entidade no mundo real.


Record Linkage (RL) ou Pareamento de Registros

Mesma fonte ou distintas fontes de dados

Registros com múltiplos atributos
Problema comum em tarefas de..

..Junção de registros de fontes diferentes;

..Deduplicação de registros;

..Data cleaning.
3
INTRODUÇÃO - EXEMPLO

Falta de Padrão de Representação (Abreviação, Pontuação, etc)
4
INTRODUÇÃO

Cenário não possibilita casamento exato de strings


Técnicas de Silimaridade Textual
Abordagem ingênua considerando 2 arquivos de banco
de dados com 5.000 registros:

25 milhões de pares de registros;

Estimando o tempo de 0.01s para a verificação de cada
par de registros:
25 milhões de verificações → 250.000 seg → ~3 dias.
5
INTRODUÇÃO

Diminuição do número de verificações:

Solução: Seleção de pares candidatos.
Possível abordagem:
Blocagem de registros.
6
INTRODUÇÃO - BLOCAGEM



Os registros são agrupados usando algum critério
de processamento rápido
Os pares candidatos são formados com os
registros de cada bloco
Em agrupamentos considerados bons:

Os pares de registros duplicados podem ser
identificados com maior facilidade em pares
candidatos;

Os pares candidatos são conjuntos menores e podem
ser analisados com maior rigor após a blocagem.
7
INTRODUÇÃO - BLOCAGEM

Blocagem como etapa de pareamento de registros:
Conjunto(s)
de
registros
Dados
Blocos de
Registros
pares
candidatos
de
registros
Blocagem
(pares com
alta
probabilidade
de registros
duplicados)
Deduplicação,
junção
aproximada de
registros,
data cleaning
8
TRABALHOS RELACIONADOS
TRABALHOS RELACIONADOS

Métodos estáticos:


Baseados em regras predefinidas para a comparação
e agrupamento de registros.
Métodos dinâmicos e adaptativos:

Parte da coleção de registros é usada como amostra
para Aprendizagem de Máquina (Machine Learning).
10
TRABALHOS RELACIONADOS

Métodos estáticos:

Canopy Blocking [McCallum et al, KDD’00]
Agrupamento de registros em 2 etapas.
 Entidades diferentes podem apresentar registros
semelhantes, fazendo com que sejam associadas aos
mesmos blocos


Soft TF-IDF [Cohen et al, AAAI’03]
Técnica de similaridade de texto
 Regra de termos em comum para a verificação de freqüência
dos termos;


Registros de mesma entidade sem termos em comum não são
comparados.
11
TRABALHOS RELACIONADOS

Métodos dinâmicos:

DNF Blocking [Bilenko et al, ICDM’06]




Baseado em várias regras para comparação e agrupamento de
registros. Termos em comum, Casamento exato de strings, etc.
As regras são associadas a atributos, formando predicados de
blocagem: {nome, termosEmComum}.
Os melhores predicados são escolhidos, formando um esquema
de blocagem na forma normal disjuntiva (FND):
Exemplo:
( {name, termosEmComum} && {address, casamentoExato} ) ||
( {surname, casamentoExato} ).
12
TRABALHOS RELACIONADOS

Métodos dinâmicos:

BSL Blocking [Michelson and Knoblock, AAAI’06]



Semelhante ao DNF Blocking:
Cada conjunção de blocagem é obtida em uma etapa de
aprendizagem de máquina.
Requer somente pares verdadeiros de registros.
13
MÉTODO BGP
BLOCKING USING GENETIC
PROGRAMMING
MÉTODO BGP

Adaptativo (aprendizagem de máquina);

Baseado em programação genética:


Vantagens: Escalabilidade + Flexibilidade;

Maior eficiência na identificação de registros
duplicados.
Resultados: Índices de acertos acima de 90% na
detecção de registros duplicados.
15
MÉTODO BGP
GERAÇÃO
INICIAL
Esquemas de
blocagem
gerados
aleatoriamente
Melhores
esquemas
Operadores
genéticos
Fim do
processo
PRÓXIMA
GERAÇÃO
Esquemas de
blocagem
melhores
Melhores
esquemas
Operadores
genéticos
Melhor
esquema de
blocagem
16
MÉTODO BGP


Esquemas de blocagem são representados como
árvores ao longo do processo de evolução
Maior flexibilidade na extração de segmentos das
expressões de esquemas de blocagem
17
MÉTODO BGP - FUNÇÃO DE FITNESS

Avaliação de esquemas com maiores chances de
produzir bons resultados.

Resultado em função de dois fatores:

Cobertura de Pares Verdadeiros
PVidC
PC 
,
PVt

• PVidC é o número de pares verdadeiros identificados
corretamente;
• PVt é o número de pares verdadeiros existentes.
Redução de Pares Candidatos
PV
RR  1  [ idV ],
Pt
• PVidV é o número de pares candidatos
• Pt é o número de pares formados com todos
registros disponíveis.
18
MÉTODO BGP - FUNÇÃO DE FITNESS


A avaliação ocorre com a análise do conjunto de
pares candidatos de registros;
Um bom conjunto de pares candidatos deve
apresentar:

O maior número possível de pares de mesma entidade
(boa cobertura de pares verdadeiros de registros);

O menor número possível de pares de entidades
diferentes (pares falsos), reduzindo o número de pares
candidatos de registros.
19
MÉTODO BGP - FUNÇÃO DE FITNESS


Os melhores esquemas são os que apresentam
maiores índices de acertos de pares verdadeiros e
falsos registros;
Esquemas de blocagem com maiores números de
conjunções são favorecidos.
Fitness 
Onde:
2
1
1

PC RR

C
,
100
C = Número de conjunções em esquemas de blocagem.
20
20
MÉTODO BGP

Experimentado em duas versões:

BGP-SR (Blocking using GP – Simple/Specific Rules)

Mesmas regras da técnica DNF Blocking:


{autor, bigramasEmComum} && {titulo, termosEmComum}.
BGP-PR (Blocking using GP – Parameter-based Rules)

Regras: N-gramas e termos em comum:

{autor, nGramas-9} && {titulo, termosEmComum-4}.
21
MÉTODO BGP
22
MÉTODO BGP
• Vantagens: Combinação de atributos + regras +
parâmetros para formar esquemas de blocagem.
•
Escalável: É possível verificar uma quantidade maior de
predicados para formação de esquemas de blocagem;
•
Flexível: Usando conjuntos maiores de predicados, e
regras mais flexíveis, podem ser definidos esquemas
mais adaptados aos dados.
• Desvantagem: Risco de overfitting.
23
EXPERIMENTOS
MÉTRICAS DE AVALIAÇÃO

Critérios usados para avaliação:

Pairs Completeness – PC (Cobertura de pares
verdadeiros)

Reduction Ratio – RR (Redução do número de pares
candidatos).
25
COLEÇÕES

Coleções utilizadas:

Cora [Bilenko et al, ICDM’06];

CiteSeer [Sarawagi et al, KDD’02];

Evolbase [Carvalho et al, JCDL’06].
26
COLEÇÕES
Coleção
Cora
Citesser
Evolbase
No. Total
de
Registros
Registros
no Treino
(%)
No.
Pares
Média de
Pares
Verdadeiros
1.295
5%
2.016
75
154
30%
1.035
17
1.000
5%
1.225
5
5% de registros apresentavam poucos exemplos de duplicatas,
prejudicial ao BSL Blocking
27
EXPERIMENTOS


10 execuções de experimentos realizados com
amostras de 5% (Cora e Evolbase) 30% (CiteSeer)
dos registros;
Configuração GP
Parâmetro
Valor usado
Número de gerações
5
Profundidade máxima da árvore de representação dos indivíduos
4
Número de indivíduos em cada geração
Número de melhores indivíduos copiados para geração posterior
Probabilidade de ocorrência de mutação
Profundidade máxima em segmentos de mutação
100
4
95%
3
28
TÉCNICAS DE REFERÊNCIA

Como baseline, foram usadas os métodos:
DNF Blocking [Bilenko et al, ICDM’06]; e
 BSL Blocking [Michelson et al, AAAI’06].


Nos experimentos realizados:

BGP-SR, DNF Blocking e BSL Blocking foram
testados com o mesmo conjunto de regras simples;

BGP-PR foi usado com regras baseadas em
parâmetros para formar os esquemas de blocagem.
29
AVALIAÇÃO DE QUALIDADE
BGP Apresenta melhores resultados devido à grande eficácia
do algoritmos de programação genética na combinação dos
predicados
30
ESCALABILIDADE
Cobertura de pares duplicados de registros
(Pairs Completeness - PC)
(%)
BGP-PR
BGP-SR
DNF Blocking
BSL Blocking
100
98
96
94
92
90
88
86
84
82
1000
2000
3000
4000
5000
6000
7000
8000
(# registros)
Método BGP PR e SR mantiveram alta qualidade mesmo com
DNF
Blocking
alcança
BGP
poucos
registros
na fonte
desomente
dados após 4 ml registros
31
ESCALABILIDADE
Redução do número de pares candidatos de registros
(Reduction Ratio - RR)
BGP-PR
BGP-SR
DNF Blocking
BSL Blocking
120
100
(%)
80
60
40
20
0
1000
2000
3000
4000
5000
6000
7000
8000
(# registros)
BSL Blocking foi o método menos estável
BGP continuou sendo o método mais eficaz
32
ESCALABILIDADE
Tempos de agrupamento de registros
(segundos)
BGP-PR
BGP-SR
DNF Blocking
BSL Blocking
10000
9000
8000
7000
6000
5000
4000
3000
2000
1000
0
1000
2000
3000
4000
5000
6000
7000
8000
(# registros)
Métodos
baseados em
Programação
Genéticaapós
se monstram
BGP-PR aumentou
tempo
de processamento
7 mil
tão
escaláveis
quanto
DNF
e BSLde predicados utilizando
registros
devido
grande
número
regra de ngramas.
33
RESULTADOS

BGP apresentou os melhores resultados:

Escalabilidade: Não há restrições para o número de
regras de blocagem que pode ser usado;

Flexibilidade: Usando regras flexíveis e em maior
número.
34
CONCLUSÕES



Nova Abordagem de Blocagem utilizando
programação genética
Técnica baseada em parâmetros que dá maior
flexibilidade a tarefa de blocagem (BGP-PR)
Experimentos realizados demonstram efetividade
da proposta em comparação a métodos da
literatura corrente.
35
TRABALHOS FUTUROS

Redução do tamanho das amostras de
aprendizagem de máquina:


Uso de técnicas de Aprendizagem Ativa (Active
Learning) [Sarawagi et al, KDD’02].
Verificação de abordagem híbrida:

Uso de um conjunto híbrido de regras (BGP-SR +
BGP-PR) como solução para o problema de blocagem.
36
Perguntas..
37
Método BGP:
http://vitoria.dcc.ufam.edu.br/~projetos/bgp
38
BLOCAGEM BASEADA EM PREDICADOS
BOLEANOS – REGRAS DE BLOCAGEM
39