Upload
diego-mendes
View
8
Download
2
Embed Size (px)
Citation preview
DIEGO SARMENTO MENDES
ALGORITMOS ESPECIALIZADOS DE
JUNÇÃO POR SIMILARIDADE BASEADA
EM MÚLTIPLOS CONJUNTOS
LAVRAS – MG
2013
DIEGO SARMENTO MENDES
ALGORITMOS ESPECIALIZADOS DE JUNÇÃO POR SIMILARIDADE
BASEADA EM MÚLTIPLOS CONJUNTOS
Projeto apresentado ao Departamento de Ciência
da Computação da Universidade Federal de Lavras,
como parte das exigências da disciplina PRG130
– Trabalho de Conclusão de Curso I, referente
ao trabalho a ser desenvolvido no final do curso
para obtenção de título de Bacharel em Ciência da
Computação
Orientador
Prof. Dr. Leonardo Andrade Ribeiro
LAVRAS – MG
2013
2
1 INTRODUÇÃO
Um problema muito comum em sistemas de banco de dados é a presença de múl-
tiplas representações de uma mesma entidade do mundo real (duplicatas, por bre-
vidade). Este tipo de informação redundante pode causar sérios transtornos em
diversos cenários. Por exemplo, em sistemas de controle de estoque, operações
como envio de correspondências e produtos podem ser repetidas desnecessaria-
mente; em sistemas de suporte a decisão, modelos de mineração de dados podem
ser corrompidos devido a estatísticas infladas erroneamente.
Neste contexto, ferramentas de data cleaning são fundamentais (ARASU et
al., 2011). Entretanto, a identificação de duplicatas é difícil porque, muitas vezes,
as mesmas não são idênticas entre si. Este é o de caso duplicatas textuais geradas
por erros tipográficos de usuários ou ausência de padronização na forma de repre-
sentar informações. Nestes casos, operações baseadas no conceito de similaridade
são imprescindíveis: por exemplo, uma junção por similaridade pode ser usada
para encontrar objetos similares em um banco de dados; estes objetos são então
classificados como possíveis duplicatas e selecionados para análise posterior.
1.1 Jutificativa
Infelizmente, o suporte a junções por similaridade ainda é bastante limitado nos
Sistemas Gerenciadores de Banco de Dados Relacionais (SGBDRs) atuais, e a
abordagem direta de comparar todos os registros das bases de dados possui um
custo computacional proibitivamente alto.
Diversas técnicas foram apresentadas utilizando uma série de filtros em eta-
pas de geração de candidatos para contornar este problema. Contudo, tais técnicas
fazem um mapeamento de cada registro, onde todos os atributos destes são conca-
3
tenados em uma única string e transformados em um conjunto de subpalavras, que
é utilizado por uma função se similaridade em etapas subsequentes. A principal
desvantagem desta abordagem é que valores textuais com semântica distinta (e.g.,
nome e endereço) são combinados, o que pode degradar a qualidade dos resul-
tados. Neste contexto, seria desejável que tuplas com múltiplos atributos fossem
representadas por múltiplos conjuntos.
1.2 Objetivos
O objetivo deste trabalho é desenvolver um novo algoritmo especializado para
junção por similaridade capaz de generalizar técnicas de otimização da abordagem
de junção baseada em um único conjunto para múltiplos conjuntos, sem perder
eficiência.
1.2.1 Objetivos Específicos
As atividades envolvidas no escopo deste projeto de pesquisa para atingir o obje-
tivo geral são listadas abaixo:
• Revisão de literatura em similaridade e, em particular, em algoritmos espe-
cializados para junção por similaridade baseada em conjuntos;
• Estudar algoritmos existentes para junção por similaridade baseada em um
único conjunto (PPJOIN e MPJOIN);
• Projeto e implementação do algoritmo que generaliza as técnicas de otimi-
zação do estado da arte para múltiplos conjuntos;
• Validação dos Resultados.
4
1.3 Estrutura do Documento
Na seção 2, Referencial, são abordados conceitos importantes para a compreenção
deste trabalho. Na seção 3, Metodologia, são abordados conceitos relacionados ao
tipo de pesquisa que será realizada neste projeto. A seção 4, Cronograma, possui
um planejamento de quando serão realizadas cada etapa do projeto. Finalmente,
a seção 5, Resultados Esperados, traz uma discussão sobre resultados que são
esperados ao fim deste trabalho.
5
2 REFERENCIAL TEÓRICO
O conceito de similaridade pode ser utilizado em diferentes áreas de pesquisa,
sendo que uma entidade é dita similar à outra caso ambas apresentem característi-
cas em comum. No contexto de banco de dados não é diferente: um objeto de um
banco de dados é dito similar a outro caso os mesmos compartilhem atributos com
valores similares.
Diante disso, uma função de similaridade tem a finalidade de quantificar o
grau de semelhança entre os objetos de um banco de dados. Em grande parte das
implementações de funções de similaridade, dois atributos textuais são compara-
dos e um valor entre 0 e 1 é retornado, indicando a similaridade entre os mesmos.
Valores próximos de 1 indicam maior similaridade enquanto valores próximos de
0 indicam baixa similaridade. Assim, são selecionados para análise posterior as
palavras que possuem uma similaridade maior ou igual a um limite (threshold)
entre 0 e 1 passado pelo usuário.
As funções de similaridade podem ser divididas em duas classes: funções
baseadas em conjuntos de tokens e funções baseadas em distância de edição.
A funções baseadas em distância de edição identificam a similaridade entre
entidades de um banco de dados indicando o número mínimo de operações como
substituição, deleção, inserção ou troca de caracteres, necessárias para transformar
uma sequência de caracteres A em outra sequencia de caracteres B.
Já as funções de similaridade baseadas em conjuntos de tokens utilizam de
operações de conjuntos, tais como união, interseção e módulo, para medir a simi-
laridade entre as entidades. No restante deste documento iremos utilizar o termo
função de similaridade para denotar funções de similariade baseadas em conjuntos
de tokens.
6
2.1 Tokenização
Neste trabalho, o termo tokens denota unidades básicas indivisíveis de informação
(textual). O processo de tokenização consiste em converter a representação textual
de uma entidade para um conjunto de tokens.
Por exemplo, um simples processo de tokenização consiste em mapear pa-
lavras separadas por caracteres especiais (como espaços em branco, por exemplo)
em tokens. Por exemplo, a palavra “Microsoft Inc Brasil” poderia ser transformada
no conjunto de tokens { Microsoft , Inc, Brasil }.
Outro processo amplamente utilizado consiste no uso de q-grams como to-
kens (UKKONEN, 1992). Q-grams são subpalavras de tamanho q, que podem ser
geradas pelo deslocamento de uma janela de tamanho q nos caracteres da palavra
original. Por exemplo, a string “Microsoft Inc.” pode ser transformada no con-
junto de tokens { Mic, icr, cro, ros, oso, sof, oft, ft , t I, In, Inc }, considerando
q = 3.
2.2 Funções de Similaridade Baseadas em Conjuntos
Funções de similaridade são funções que recebem duas strings como entrada e re-
tornam um valor entre 0 e 1, indicando a similaridade entre as strings de entrada.
Diante disso, quando as entidades comparadas são mapeadas para um conjunto
de subpalavras, denominadas tokens, as funções de similaridade determinam a si-
milaridade entre as entidades comparadas por meio de operações de conjuntos,
tais como União, Interseção e Módulo, sobre tais conjuntos de tokens. Tal classe
de funções de similaridade é denominada Funções de Similaridade Baseadas em
Conjuntos (FSCs).
7
Na maior parte destas funções, são consideradas similares entidades cuja in-
terseção de seus conjuntos de tokens possuem muitos elementos. Na tabela 2.1 são
ilustradas as fórmulas de algumas das principais funções de similaridade baseadas
em conjuntos, onde x1 e x2 são conjuntos de tokens (RIBEIRO; HÄRDER, 2011).
Tabela 2.1: Definição das Funções de Similaridade Baseadas em Conjunto
Função Definição
Jaccard |x1∩x2||x1∪x2|
Cosseno |x1∩x2|√|x1||x2|
Dice 2 |x1∩x2||x1|+|x2|
Uma estratégia que também pode ser adotada para melhorar a qualidade da
função de similaridade é a ponderação dos tokens. Segundo (ROBERTSON; JO-
NES, 1976), características raras são mais significativas para definir se duas enti-
dades são similares. Diante disso, uma estratégia de atribuição de pesos aos tokens
amplamente utilizada para se aproveitar de características raras dos tokens é IDF
(do ingles Inverse Document Frequency), onde tokens raros recebem um peso alto
e tokens muito frequentes recebem pesos baixos (RIBEIRO; HÄRDER, 2011).
Por simplicidade, no restante deste documento será utilizado o termo função
de similaridade para referir-se a função de similaridade Jaccard, definida na tabela
2.1.
2.3 Junção por Similaridade
Dados uma coleção de registros de alguma base de dados, uma função de simi-
laridade sim(), e um limiar (threshold) t definido pelo usuário, uma Junção por
Similaridade (JS) consiste em encontrar todos os pares de tuplas, < x,y >, que
8
possuam similariade maior ou igual ao threshold t, ou seja, sim(x,y)≥ t (XIAO et
al., 2011).
A abordagem naïve para realizar uma operação de junção por simililaridade
é comparar todos os pares de de tuplas de duas base de dados, retornando pares
que possuam uma similaridade maior que o threshold definido pelo usuário. Con-
tudo, esta abordagem possui um custo computacional proibitivamente alto quando
as bases de dados possuem muitos registros, uma vez que o número total de com-
parações feitas é O(n2)(XIAO et al., 2011).
Entretanto, técnicas atuais implementam táticas para reduzir o custo compu-
tacional da operação de JS.
2.4 Junção por Similaridade Baseada em um Único Con-
junto
A técnica de Junção por Similaridade baseada em um Único Conjunto faz uso
de funções de similaridade para realizar uma operação de JS entre duas bases de
dados, retornando pares de tuplas que possuam similaridade maior que um limiar
(threshold) fornecido pelo usuário.
Para cada tupla de uma base de dados, todos atributos desta tupla são conca-
tenados em uma única string. Um exemplo deste processo é ilustrado na figura
2.1.
Figura 2.1: Passo a passo da junção por similaridade utilizando único conjunto
Na próxima etapa, a string concatenada é mapeada para um conjunto de to-
kens, conforme ilustrado em 2.2.
9
Figura 2.2: Passo a passo da junção por similaridade utilizando único conjunto
Depois de gerados os conjuntos de tokens de cada tupla, muitas das técnicas
atuais reduzem o problema de medir a similaridade de duas tuplas para um pro-
blema de interseção de conjuntos (RIBEIRO; HÄRDER, 2011). Assim, dado um
threshold t, o problema de mesurar a similaridade entre duas tuplas é convertido
para o problema de contar o número de elementos em comum que os dois con-
juntos de tokens de cada tupla possuem em comum. Este processo é ilustrado na
figura 2.3.
Figura 2.3: Passo a passo da junção por similaridade utilizando único conjunto
Assim sendo, para reduzir o custo computacional da operação de JS, utiliza-
se uma série de filtros para reduzir o número de pares de tuplas comparadas pelas
10
FSCs (SARAWAGI; KIRPAL, 2004; XIAO et al., 2011; RIBEIRO; HÄRDER,
2011). Tais técnicas dividem o problema em três fases: Indexação, Geração de
Candidatos e Verificação (XIAO et al., 2011).
Na fase de Indexação, pares inciais de candidatos são gerados com a utilização
de índices invertidos (XIAO et al., 2011). Esta lista invertida é utilziada para
mapear cada token w para uma lista de identicadores de registros que possuem w.
Assim, pode-se facilmente analisar um token x e todas as tuplas que possuem tal
token e, combinando-se estas tuplas, gera-se os primeiros pares de candidatos.
Na próxima fase, denominada Geração de Candidatos, pares de candidatos
iniciais com nenhuma chance de serem similares são eliminados. Isto é feito por
meio de uma série de filtros, tais como Filtro de Tamanho e Filtro de Prefixo.
Por fim, na fase de Verificação, os pares de canditados gerados, que já pas-
saram pelos filtros na etapa anterior, são verificados por meio de uma função de
similaridade. Apenas aqueles que tiverem uma similaridade maior que o threshold
fornecido pelo usuário são adicionados à saída da junção.
2.5 Junção Similaridade Baseada em Múltiplos Conjun-
tos
Todas as técnicas existentes até o presente momento operam apenas sobre um
único conjunto para determinar se duas bases de dados são similares. Entretanto,
devido à concatenação de múltiplos atributos em etapas inicias, tais técnicas po-
dem degradar a qualidade do resultado, uma vez que, por exemplo, duas tuplas
que possuam nome, endereço e telefone, na qual a primeira tupla possua o nome
“Willian” e a segunda, por sua vez, possua endereço “Willian”, serão considera-
das similares, mesmo que os atributos nome e endereço estejam em semânticas
distintas.
11
Diante disso, para evitar que características de diferentes atributos sejam con-
sideradas para determinar a similaridade entre entidades, a técnica proposta de
Junção por Similaridade baseada em Múltiplos Conjuntos (JSMC) utiliza uma sé-
rie de conjuntos, um para cada atributo da entidade (ver figura 2.4), sendo compa-
radas em funções de similaridades apenas subconjuntos que pertençam a mesma
semântica. Além disso, utilizando a abordagem proposta, é possível que o usuário
determine diferentes thresholds para cada atributo dos elementos.
Figura 2.4: Passo a passo da junção por similaridade utilizando múltiplos conjuntos
Assim, o problema da JSMC pode é definido como:
Dado uma coleção de conjuntos de uma ou mais bases de dados, uma serie
de atributos a1,a2, ...,an destes elemetos, uma função de similariade sim(), e uma
série de thresholds t1, t2, ..., tn, onde n é o número de atributos das entidades, uma
JSMC consiste em mapear todos os pares de tuplas < x,y > dos quais todos pre-
dicados da forma sim(xai ,yai)≥ ti sejam verdadeiros, ou seja:
∧ni=1sim(xai ,yai)≥ ti
onde o operador ∧ é entedido como o operador booleano and, e só seriam
adicionadas à saída da junção pares de tuplas que atendam todos os predicados. A
figura 2.5 ilustra um exemplo deste processo.
12
Figura 2.5: Passo a passo da junção por similaridade utilizando múltiplos conjuntos
Entretanto, diversas questões surgem quando pensamos a respeito de utilizar
múltiplos conjuntos, uma vez que, por exemplo, será necessário identificar em
qual dos conjuntos serão aplicadas as otimizações para geração de candidatos, tais
como os filtros de prefixo e tamanho. Diante destas questões, nota-se que uma
parte essencial do projeto é a criação de um modelo de custos para identificação
do conjunto que resultará no maior ganho de performance.
13
3 METODOLOGIA
Antes de dar início as atividades necessárias para a realização deste projeto, foi
feito um estudo em artigos que tratam do assunto de junção por similaridade por
conjuntos para a escrita de um referencial teórico inicial.
Para a realização dos experimentos, será feita a criação de um ambiente de tes-
tes, onde serão necessários geradores de dados “sujos” sintéticos e semi-seintéticos,
que serão gerados a partir de uma base de dados limpa, por meio de cópias das en-
tidades originais que serão modificadas de forma a simular erros tipográficos.
Neste ambiente de testes será possível realizar experimentos para estudos de-
talhados, sendo que diferentes técnicas poderiam ser testadas em condições idên-
ticas. Assim, ajustes de performance poderiam ser feitos nos algoritmos propostos
baseando-se em experimentos sucessivos e observação dos resultados (pesquisa
empírica).
Os critérios de avaliação que serão utilizados para comparar o algoritmo pro-
posto com outros já existenstes serão:
• Eficácia;
• Eficiência;
• Escalabilidade;
• Consumo de recursos computacionais.
Técnicas comumente utilizadas na área de Recuperação de Informação serão
utilizadas para para medir a eficácia do algoritmo proposto, tais como precisão, re-
vocação e MAP (do acrônimo inglês mean avarage precision), considerando, prin-
cipalmente, a quantidade de pares de duplicadas encontrados (BAEZA-YATES;
RIBEIRO-NETO, 2011).
14
Já a eficiência do algoritmo proposto será mesurada considerando o tempo
médio de execução dos algoritmos.
A escalabilidade será obtida observando o comportamento do tempo de exe-
cução do algoritmo conforme uma variação no tamanho das bases de dados nas
quais o algoritmo opera.
No que diz respeito ao consumo de recursos computacionais, será observado,
principalmente, a quantidade de memória principal demandada pelos algoritmos.
15
4 CRONOGRAMA
As atividades envolvidas no escopo deste projeto são listadas a seguir:
1. Revisão Bibliográfica de Artigos;
2. Estudo dos algoritmos de JS por um único conjunto (PPJOIN e MPJOIN);
3. Criação do Ambiente de Testes;
4. Projeto e Implementação do Algoritmo;
5. Criação de um modelo de custos para escolha do melhor conjunto para apli-
car as otimizações;
6. Realização de Experimentos;
7. Escrita da monografia.
Tabela 4.1: Cronograma
Atividades 02/13 03/13 04/13 05/13 06/13 07/13 08/13 09/13
Revisão X X X
PPJOIN e MPJOIN X X X
Ambiente de Testes X X X
Projeto e Implementação do Algoritmo X X X X
Modelo de Custos X X
Experimentos X X X X
Escrita Monografia X X X X X X
16
5 RESULTADOS ESPERADOS
Ao final deste trabalho espera-se obter um algoritmo especializado capaz de reali-
zar operações de junção por similiaridade considerando múltiplos conjuntos, com
tempo de execução tão eficiente quanto o de técnicas que consideram apenas um
único conjunto para a junção e, devido a própria natureza do algoritmo, espera-se
que a qualidade dos resultados da junção seja superior ao de técnicas que utilizam
apenas um único conjunto.
17
REFERÊNCIAS BIBLIOGRÁFICAS
ARASU, A.; CHAUDHUR, S.; CHEN, Z.; GANJAM, K.; KAUSHIK aghav;
NARASAYYA ivek. Towards a domain independent platform for data cleaning.
Data Engineering, p. 43, 2011.
BAEZA-YATES, R.; RIBEIRO-NETO, B. Modern Information Retrieval.
Addison Wesley Professional, 2011. ISBN 9780321416919. Disponível em:
<http://books.google.com.br/books?id=HbyAAAAACAAJ>.
RIBEIRO, L. A.; HÄRDER, T. Generalizing prefix filtering to improve set
similarity joins. Information Systems, v. 36, n. 1, p. 62–78, 2011. ISSN
0306-4379. Selected Papers from the 13th East-European Conference on
Advances in Databases and Information Systems (ADBIS 2009). Disponível em:
<http://www.sciencedirect.com/science/article/pii/S0306437910000657>.
ROBERTSON, S. E.; JONES, K. S. Relevance weighting of search terms. Journal
of the American Society for Information science, Wiley Online Library, v. 27, n. 3,
p. 129–146, 1976.
SARAWAGI, S.; KIRPAL, A. Efficient set joins on similarity predicates. In:
Proceedings of the 2004 ACM SIGMOD international conference on Management
of data. New York, NY, USA: ACM, 2004. (SIGMOD ’04), p. 743–754. ISBN 1-
58113-859-8. Disponível em: <http://doi.acm.org/10.1145/1007568.1007652>.
UKKONEN, E. Approximate string matching with q-grams and maximal
matches. Theor. Comput. Sci., v. 92, n. 1, p. 191–211, 1992.
XIAO, C.; WANG, W.; LIN, X.; YU, J. X.; WANG, G. Efficient similarity joins
for near-duplicate detection. ACM Trans. Database Syst., ACM, New York, NY,
USA, v. 36, n. 3, p. 15:1–15:41, ago. 2011. ISSN 0362-5915. Disponível em:
<http://doi.acm.org/10.1145/2000824.2000825>.