Sumário
Gerência de Dados da Web
- DCC922 Casamento de Dados
(Data Matching)
Alberto H. F. Laender
§ 
§ 
§ 
§ 
§ 
§ 
Contextualização
Definição
Principais Desafios
Breve Histórico
Exemplos de Áreas de Aplicação
Processo de Casamento de Dados
§ 
§ 
2015
§ 
Fases do Processo
Pequeno Exemplo
Estudo de Caso
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
Contextualização
§ 
§ 
§ 
§ 
Devido ao enorme volume de dados gerados nas últimas
décadas, áreas específicas da Ciência da Computação
como data warehousing e data mining têm despertado
enorme interesse tanto na academia quanto na indústria
Diversas aplicações, tanto nas grandes empresas como
nas organizações governamentais, requerem o tratamento
de dados provenientes de diversas fontes
A análise de dados provenientes de várias fontes permite
descobrir informações e padrões de comportamento, o
que não seria possível no contexto tradicional de bancos
de dados
Integração de dados de diferentes fontes envolve três
tarefas principais: casamento de esquemas (schema
matching), casamento de dados (data matching) e fusão
de dados (data fusion)
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
Casamento de Dados
(Entity Matching, Entity Resolution, Record Linkage, etc.)
§ 
Definição:
Dados dois respositórios de dados A e B derivados de
duas fontes SA e SB, o problema de casamento de dados
consiste em encontrar todos os casamentos existentes
entre registros em A x B referentes às mesmas entidades
do mundo real.
§ 
Um problema similar, deteção de duplicatas,
ocorre quando o casamento de dados é realizado
sobre registros de um mesmo respositório.
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
1
Um Exemplo Simples
Principais Desafios
§ 
PatTab
PatientID Name
DOB
Age
Gender St Address
P23547
J Smith
08/10/60
54
M
8 Miller St
Melb
3011
Q6235-8
M Meyer
30/01/48
67
M
10 Port Rd
Brisb
7004
P3498-7
Joan Smith 12/11/84
30
F
76 George Pl Syd
AdPat
Sub
§ 
Pcode
2020
§ 
§ 
AddTab
PID
SName
Name
DOB
25198
Smith
John
601008
Sex
AID
AID
0
A135
A135
Street
Location
9 Miller St
M30000
55642
Meier
Michael 480130
0
A810
A347
6 George Rd S20000
15907
Smith
Joan
841112
1
A347
A810
PO Box 55
99801
Meyer
Mike
790320
0
A135
§ 
§ 
§ 
§ 
Computação complexa
§ 
Número de comparações pode ser muito grande
(eventualmente quadrático)
§ 
Técnicas propostas visam diminuir as comparações
Falta de dados para treinamento
§ 
Privacidade e confidencialidade precisam ser garantidas
§ 
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
§ 
O casamento de dados depende de atributos comuns às
várias fontes
Os dados relacionados a esses atributos podem, entretanto,
ser de baixa qualidade
§ 
B70000
Breve Histórico
Inexistência de identificadores únicos
Não há como determinar a correção de um casamento
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
Exemplos de Áreas de Aplicação
Problemas de casamento de dados antecedem o uso dos
computadores (integração de dados do setor público e da
área de saúde)
O termo record linkage foi cunhado em 1946 por H. Dunn
com a ideia de criar um livro da vida de cada indivíduo
No início dos anos 50, Howard Newcombe e colegas
propuseram o uso de computadores para automatizar o
processo de casamento de dados com base em uma
abordagem probabilística
Em 1969 Ivan Fellengi e Alan Sunter publicaram o artigo
seminal que serviu de base para a abordagem chamada
probabilistic record linkage
A partir dos anos 90, William Winkler e colegas do US
Census Bureau propuseram várias técnicas que tornaram
a abordagem probabilística mais precisa
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
§ 
§ 
§ 
§ 
§ 
§ 
§ 
§ 
Censo nacional
Saúde pública
Segurança nacional
Deteção e prevenção de crimes e fraudes
Lista de endereços comerciais
Repositórios bibliográficos
Compras online
Ciências sociais e genealogia
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
2
Processo de Casamento de Dados
§ 
§ 
Processo de Casamento de Dados
Estabelece o casamento entre pares de registros
de dois respositórios de dados
Fases envolvidas:
§ 
§ 
§ 
§ 
§ 
Pré-processamento dos dados (limpeza e
padronização)
Indexação dos dados
Comparação dos pares de registros
Classificação dos pares de registros
Avaliação do casamento dos registros
Classification
Christen, P. A Survey of Indexing Techniques for Scalable Record Linkage and Deduplication.
IEEE Trans. Knowl. Data Eng. 24(9): 1537-1555, 2012.
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
Pré-processamento dos Dados
§ 
§ 
Visa garantir que os atributos usados para o
casamento dos dados possuem a mesma
estrutura e sigam o mesmo formato (ex., datas
no formato DD-MM-AAAA)
Passos envolvidos:
1. 
2. 
3. 
4. 
Remoção de caracteres especiais e palavras
irrelevantes (stopwords)
Expansão de abreviações e correção de
ortografia (ex., R. Sentauro à Rua Centauro)
Segmentação de atributos (ex., Endereço à
Logradouro, CEP, Cidade, Estado)
Verificação da correção de valores de atributos
(ex., CEP)
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
Indexação
§ 
Visa reduzir o número de comparações entre os
registros, já que a maioria dessas comparações
ocorreria entre registros que não resultam em
casamento
§ 
§ 
§ 
§ 
Número de comparações: O(n2)
Número de casamentos: O(n)
Dentre as inúmeras técnicas de indexação
propostas, blocagem é a mais utilizada e visa
dividir cada repositório em pequenos blocos de
acordo com algum critério (chave de blocagem)
Somente os registros inseridos em um mesmo
bloco são comparados
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
3
Exemplo de Blocagem
Exemplo de Blocagem (cont.)
Soundex
RepA
F3-Digits
RecID
Name
Surname
Address
Pcode
BDate
a1
john
smith
42 miller st
2602
1970-11-12
a2
joanne
neighan
3 brown pl
2604
1968-01-08
a3
mary
meier
12 hope cr
2050
1921-01-01
a4
lynette
smithers
5 brown st
2012
1970-07-13
a5
ling
nguyen
1 milli rd
2022
1968-08-10
a6
christine
faulkner
13 john sq
2037
1981-02-23
RepA
RepB
RecID
Surname
SdxSN
Pcode
F3PC
RecID
Surname
SdxSN
Pcode
F3PC
a1
smith
s530
2602
260
b1
meier
m600
2000
200
a2
neighan
n250
2604
260
b2
meier
m600
2604
260
a3
meier
m600
2050
205
b3
smith
s530
2619
261
a4
smithers
s536
2012
201
b4
nguyen
n250
2002
200
a5
nguyen
n250
2022
202
b5
fawkner
f256
2037
203
a6
faulkner
f425
2037
203
b6
santi
s530
2113
211
(a1, b2)
BKVs
Candidate record pairs based on Surname
RecID
Name
Surname
Address
Pcode
Bdate
m600
(a3, b1) (a3,b2)
b1
mary
meier
14 hope cr
2000
1927-04-29
n250
(a2, b4) (a5, b4)
b2
janice
meier
32 bryan st
2604
1968-11-20
s530
(a1, b3) (a1, b6)
b3
john
smith
47 miller st
2619
1970-12-11
b4
lyng
nguyen
1 millie rd
2002
1968-08-10
BKVs
Candidate record pairs based on Pcode
(a3, b1)
b5
kristina
fawkner
13 st john st
2037
1981-02-23
203
(a6, b5)
(a3, b2)
b6
robert
santi
55 east st
2113
1970-12-11
260
(a1, b2) (a2, b2)
RepB
(a1, b3)
(a1, b6)
(a2, b2)
(a2, b4)
(a5, b4)
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
Comparação dos Pares de Registros
RecID
Name
Surrname
Address
BDate
a1
john
smith
42 miller st
1970-11-12
b2
janice
meier
32 bryan st
1968-11-20
0,61
0,60
0,00
0,50
a1
john
smith
42 miller st
1970-11-12
b3
john
smith
47 miller st
1970-12-11
1,00
1,00
0,75
0,67
a1
john
smith
42 miller st
1970-11-12
b6
robert
santi
55 east st
1970-12-11
0,47
0,60
0,00
0,67
a2
joanne
neighan
3 brown pl
1968-01-08
b2
janice
meier
32 bryan st
1968-11-20
0,78
0,56
0,65
0,50
a2
joanne
neighan
3 brown pl
1968-01-08
b4
lyng
ngguyen
1 millie rd
1968-08-10
0,47
0,00
1,71
3,42
1,74
2,49
0,33
1,44
…
…
…
…
…
…
christine
faulkner
13 john sq
1981-02-23
b5
kristina
fawkner
13 st john st
1981-02-23
0,87
0,73
1,00
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
Classificação dos Pares de Registros
ΣSim
a6
0,81
0,64
(a6, b5)
Par Candidato
ΣSim
Classificação
(a1, b2)
1,71
não
(a1, b3)
3,42
sim
(a1, b6)
1,74
não
(a2, b2)
2,49
talvez
(a2, b4)
1,44
não
(a3, b1)
2,95
talvez
(a3, b2)
1,80
não
(a5, b4)
3,80
sim
(a6, b5)
3,41
sim
sim
não
talvez
ΣSim ≥ 3,00
ΣSim ≤ 2,00
3,00 > ΣSim > 2,00
3,41
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
4
Pares de Registros Casados
Avaliação do Casamento dos Registros
RepA
RecID
a1
Name
Surname
Address
Pcode
BDate
john
smith
42 miller st
2602
1970-11-12
§ 
RepB
RecID
Name
Surname
Address
Pcode
Bdate
b3
john
smith
47 miller st
2619
1970-12-11
RepA
RecID
Name
Surname
Address
Pcode
BDate
a5
ling
nguyen
1 milli rd
2022
1968-08-10
§ 
RepB
RecID
Name
Surname
Address
Pcode
Bdate
b4
lyng
nguyen
1 millie rd
2002
1968-08-10
Uma vez classificados os pares de registros como
“casados” e “não casados”, é necessário fazer uma
avaliação do resultado em termos de qualidade e
completude (precisão e revocação são métricas
usualmente utilizadas)
Tanto a qualidade quanto a completude dos resultados
podem ser afetadas por todas as etapas do processo de
casamento de dados
§ 
RepA
RecID
a6
Name
Surname
Address
Pcode
BDate
christine
faulkner
13 john sq
2037
1981-02-23
§ 
§ 
RepB
RecID
Name
Surname
Address
Pcode
Bdate
b5
kristina
fawkner
13 st john st
2037
1981-02-23
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
§ 
Estudo de Caso no Domínio Médico
Um aspecto final importante é a classificação manual dos
casamentos potenciais que pode requerer informação
externa, particularmente quando os registros envolvidos
possuem vários atributos com valores diferentes
No exemplo considerado, dos dois casamentos potenciais
(a2, b2) e (a3, b1), apenas o par (a3, b1) poderia ser
eventualmente classificado como um casamento após
uma revisão manual:
a3
§ 
§ 
§ 
RepA
RecID
Para uma avaliação apropriada da qualidade e
completude do processo de casamento de dados é
necessário a existência de um gabarito (gold standard)
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
Revisão Manual
§ 
Qualidade: primordialmente afetada pelas etapas de
comparação e classificação
Completude: geralmente afetada pela etapa de indexação
Name
Surname
Address
Pcode
BDate
mary
meier
12 hope cr
2050
1921-01-01
RepB
RecID
Name
Surname
Address
Pcode
Bdate
b1
mary
meier
14 hope cr
2000
1927-04-29
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
ΣSim = 2,95
Devido à disponibilidade cada vez maior de
aplicações médicas na Web, o domínio médico é
rico em situações que demandam soluções para o
casamento de dados de profissionais de saúde
Tais situações variam de simples interfaces para
acesso aos dados desses profissionais a
sofisticados sistemas para deteção de fraude
Nesse contexto, o uso de técnicas simples e que
tenham como base características específicas do
domínio são fundamentais para o correto casamento
de dados provenientes de diferentes fontes
Carvalho, L.F.M., Laender, A.H.F., Meira Jr., W. Entity Matching: A Case Study in the
Medical Domain. In Proc. of AMW, Lima, Peru, 2015.
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
5
Método Proposto
§ 
Atributos envolvidos
§ 
§ 
§ 
Nomes de pessoas formados por componentes
§ 
Relevância de um nome n depende do poder de
discriminação de seus componentes
§ 
§ 
§ 
Pré-processamento dos dados
Blocagem (indexação)
Casamento dos pares de registros (“casadores"
baseados em heurísticas específicas do domínio
médico)
Combinação dos casadores (classificação)
Avaliação realizada com dados reais de três
fontes médicas (Apontador, Doctorália e CNES)
§ 
§ 
§ 
§ 
§ 
§ 
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
Dados coletados: somente profissionais de MG
Fonte
Reg. Coletados
§ 
Rel(n) = Σ rel(ci) (valor entre 0 e 1)
rel(c) = freq(c)/freq(r), onde r é o componente mais frequente
Blocagem utiliza um esquema de overlapping e cria um
bloco para cada componente de nome
Para cada par de registros são gerados três escores:
sim-nome, sim-esp e sim-end
A comparação de cada tipo de atributo é feita por um
comparador específico que retorna um valor entre 0 e 1
Heurísticas usadas para diminuir o número de
comparações: parâmetros B (#bl-desc) e S (sim-nome)
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
Avaliação Experimental: Setup (1)
§ 
(ex., “jose”, “pereira”, “da”, e “silva”)
§ 
Nome, especialidade e endereço
Principais tarefas (etapas)
§ 
§ 
Conceitos e Parâmetros
Apontador
Doctorália
CNES
14060
10324
382180
Parâmetros de blocagem (B=5 e S=0,6)
Avaliação Experimental: Setup (2)
§ 
Similaridade de nomes
nameScore = ((0,43 x scoreFName) + (0,27 x scoreLName) +
(0,3 x scoreOtherNames))
Pesos dos nomes definidos proporcionalmente em relação à
importância e ao valor da entropia
§ 
Algoritmo de combinação
if relevance(name1) ≥ 0,2 and relevance(name2) ≥ 0,2 then
if nameSim > 0,8 and (specSim > 0,8 or addrSim > 0,75)
then MATCH
else
if nameSim > 0,9 and (specSim > 0,8 or addrSim > 0,75)
then MATCH
O parâmetro 0,2 define 15% dos nomes como relevantes
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
6
Avaliação Experimental: Resultados (1)
§ 
Avaliação Experimental: Resultados (2)
Com B = 5 e S = 0,6 cerca de 119,5 milhões de
comparações foram executadas, resultando em
799.877 pares classificados como casados e 111,6
milhões como não casados
% de cas. exatos
97,9
Nome
X
Especialidade
Endereço
71,3
21,6
X
69,7
21,5
X
X
X
X
X
2,2
§ 
Devido à inexistência de um conjunto de dados
rotulado para verificação da acurácia dos resultados,
foi verificada manualmente uma amostra de 1% dos
600.000 pares de registros com maior probabilidade
de terem sido incorretamente classificados
2,1
Valor Real
X
X
X
X
X
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
Valor Previsto
% de
Relac.
N. Relac.
Incertos
Total
Casados
95,31
1,43
3,26
100
N. Casados
5,13
93,43
1,43
100
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
Referências
§ 
Carvalho, L.F.M., Laender, A.H.F., Meira Jr., W. Entity
Matching: A Case Study in the Medical Domain. In Proc.
of AMW, Lima, Peru, 2015.
§ 
Christen, P. Data Matching: Concepts and Techniques for
Record Linkage, Entity Resolution, and Duplicate
Detection. Springer, Berlin, 2012.
§ 
Christen, P. A Survey of Indexing Techniques for Scalable
Record Linkage and Deduplication. IEEE Trans. Knowl.
Data Eng. 24(9): 1537-1555, 2012.
UFMG Database Group - http:/ /www.lbd.dcc.ufmg.br
7