ERBD 2009: Funções de similaridade e suas aplicações

Minhas anotações sobre o mini-curso "Funções de similaridade e suas aplicações" ministrado pela Carina F. Dorneles (dorneles@upf.br), durante o V ERBD.

FUNÇÕES DE SIMILARIDADE

- Como calcular a similaridade?
Similaridade é uma coisa subjetiva e o computador te muita dificuldade de definir se é ou não.

- Consulta
Executar consultas sobre várias bases de dados

- Integração
Efetuar integração dos dados

- Data Cleaning
Efetuar a impeza dos dados antes de inserir em uma nova base como por exemplo DWs

Exemplo de consulta SQL utiliazando a função de similaridade levenshtein

select artigo from bdbcomp where levenshtein (autor, 'agma machado traina') > 0,75

// vai buscar artigos de autores com 75% de similaridade no nome 'agma machado traina'.


Exemplo da mesma função para integração...

levenshtein ("league of ... Action","League of ... Sci-Fi") >= 0.78

// integrar aquilo cujo linar de similaridade maior que 78

É bastante usado Data WareHouses na parte de Data Cleaning, limpeza de dados, exemplo:

levenstein('ijuí - RS','ijuí - RGS')
// pra elimiar inconsistências, erros de digitação etc, vai trocar os RGS por RS se não me engano :D

Avaliaçao de uma função
- Revocação
- Precisão
- Discernabilidade

SIMILARIDADE X DISTÂNCIA

A função de similaridade tem dois parametros e retorna um valor, um escore entre 0 e 1, quanto maior for mais similar são entre si.

A função de distância tem dois parametros e retorna um valor, mas o escore vai de zero até o infinito, quanto menor o valor do escore, maior a similariedade.

Fórmula para transformar distância em similaridade:

similaridade = 1 - (valor de distância normalizado)

Ferramenta
- Similarity Metrics Testing Suite

* valores atomicos: strings
- baseadas em caracter
- baseadas em Token

* valores agregados
- uso em expressões algébricas
- uso em algoritmos

SVM - Inteligência artificial - tuplas - faz algoritmos para testar com funções de distancias partes de atributos para saber se os dados sao similares, criando vetores de valores que sao enviados para SVM fazer a comparação e dizer se os dados sao duplicados ou não.

ROTEIRO
- consultas por similaridade
- integração de dados
- data cleaning
- mineração de dados


SGBDs que implemetam funções de similaridade

POSTGRESQL
MYSQL
DB2
ORACLE


FUNÇÕES NO POSTGRESQL

- levenshtein
- soundex
- dmetaphone (fonético tbm)

APLICATIVO WEKA - FREE

www.CS.WAIKATO.AC.NZ/WEKA
Ferramenta de mineração, vários algoritmos para técnicas mais conhecidas, extensível, algoritmos podem ser usados para compor outras aplicações, é necessário

DEMOSTRAÇÃO
queens.db.toronto.edu/project/spider/demo

FERRAMENTA QUE LEVA EM CONSIDERAÇÃO SINONIMOS -> WORDNET??

Classificação

- Funções para valores atomicos

*Lenshtein
*Soundex
*Achronimous

- Função Token, quebra as strings em partes antes de comparar...

*Jaccard

Bom, minhas anotações ficaram meio desconexas porque eram muitas informações e não dava tempo de prestar atenção e anotar tudo ao mesmo tempo, mas o assunto é interessante e pode ter várias aplicações como, antes de cadastrar uma pessoa, verificar se o nome já existe através da fonética e ai por diante, o problema é que isso pode diminuir muito a performance da aplicação, mas fica a dica e é uma área que ainda existem poucas pesquisas...

Link para material do V ERBD.

Até.