Guia de aula laboratorial

O guia da 8º aula prática está disponível online. Os tópicos abordados incluem conceitos relacionados com limpeza de dados (e.g. detecção de duplicados e correcção de erros).

Limpeza de dados

A limpeza de dados assume um papel muito importante no contexto da criação e gestão de grandes repositórios de informação, lidando com a detecção e remoção de erros/inconsistências por forma a melhorar a qualidade do dados. Nesta aula prática iremos abordar dois problemas típicos de limpeza de dados, nomeadamente:

  • Detecção de duplicados.
  • Correcção ortográfica.

As soluções que vamos ver para ambos estes problemas recorrem a medidas de similaridade entre strings (e.g. duas strings muito similares são provavelmente duplicados e, no caso da correcção ortográfica, a procura de sugestões de correcção é feita com base na similaridade para com strings que se encontrem definidas num dicionário).

Nesta aula prática iremos novamente usar a ferramenta LingPipe ( http://www.alias-i.com/lingpipe ), a qual se apresenta como um pacote Java para extracção de informação e prospecção de texto. Iremos abordar as funcionalidades do LingPipe para medição de similaridade entre strings e para correcção ortográfica, através de alguns exemplos de utilização simples. A quem tenha curiosidade sobre o assunto, aconselha-se a consulta da documentação completa e tutoriais da ferramenta ( http://www.alias-i.com/lingpipe/demos/tutorial/read-me.html )

Todos os exemplos apresentados neste documento podem ser encontrados online no ficheiro limpeza.zip ( http://web.tagus.ist.utl.pt/~bruno.martins/materials/class-materials/labs-gti/limpeza/limpeza.zip ).

Detecção de duplicados

A tarefa de identificar duplicados exactos ou aproximados é um passo essencial de qualquer processo de limpeza (e integração) de dados. Por duplicados aproximados, entendem-se os registos de informação que não são exactamente idênticos mas que ainda assim são duplicados (e.g. a mesma pessoa pode surgir descrita pela string "Bruno M." ou "Bruno Martins"). A utilização de funções de similaridade é uma forma comum de atacar este problema. A ideia chave é a de que dois registos com similaridade máxima correspondem a duplicados exactos, e dois registos com elevada similaridade têm uma elevada probabilidade de ser duplicados.

A ferramenta LingPipe concretiza mecanismos para a computação genérica de funções de similaridade entre strings. O código Java que se segue exemplifica esta funcionalidade:

import com.aliasi.spell.*;
import com.aliasi.util.*;

public class ExampleDuplicateDetection {

public static void main(String[] args) throws Exception {
Distance dist = new JaroWinklerDistance(); // try also with EditDistance();
System.out.println("Testing similarity of (" + args[0] + "," + args[1] +")");
double sim = 1-dist.distance(args[0],args[1]);
System.out.println("Similarity=" + sim);
if (sim >= ((double)1.0)) System.out.println("Records are duplicates.");
else if (sim>((double)0.8)) System.out.println("Records are near duplicates.");
else System.out.println("Records are not duplicates.");
}
}

Neste caso, estamos a usar uma função de similaridade baseada na medida de distância de Jaro e Winkler. Estes dois autores definiram que, de uma forma genérica, a distância entre duas strings s e t pode ser dada pela fórmula:

JaroWinklerScore(s,t) = Jaro(s,t) + (prefixLength* PREFIXSCALE * (1.0f - Jaro(s,t)));

onde prefixLength é o tamanho de um prefixo comum no início da string e PREFIXSCALE é um factor constante que ajusta o peso da medida de distância de acordo com a existência do prefixo comum. A função Jaro(s,t) consiste na medida de similaridade mais simples anteriormente proposta por Jaro, a qual corresponde à seguinte formula:


Neste caso, |s'| corresponde ao numero de caracteres em s que estão aproximadamente na mesma posição em t, |t'| corresponde ao número de caracteres em t que estão aproximadamente na mesma posição em s, e Ts,t corresponde ao número de transposições de caracteres em s' relativamente a t'. A documentação da classe JaroWinklerDistance fornece informação mais detalhada ( http://www.alias-i.com/lingpipe/docs/api/com/aliasi/spell/JaroWinklerDistance.html ).

Importa referir que a escolha da função de similaridade, assim como a definição do limite de similaridade acima do qual se considera que dois registos são duplicados, deve ser feita consoante o problema e o domínio de aplicação. A ferramenta LingPipe disponibiliza uma grande variedade de "noções" de similaridade (e.g., distância de edição, similaridade de Jaccard, distância euclidiana, etc.), sendo ainda relativamente fácil estender a ferramenta por forma a implementar outras noções de similaridade intrínsecas a uma dada aplicação (e.g. soundex, similaridade com base em co-ocorrências, etc.).

Correcção ortográfica

Qualquer grande repositório de informação irá muito provavelmente conter erros de vários tipos. Particularmente quando se trata de dados provenientes da web ou provenientes de formulários preenchidos por humanos, é provável que se dêem ocorrências de erros ortográficos. Uma forma comum de atacar este problema relaciona-se com a utilização de dicionários listando todos os valores possíveis que uma determinada variável pode tomar (e.g. todos os nomes válidos). Estes dicionários permitem não só a detecção de problemas de correcção ortográfica (i.e. todos os nomes que não se encontrem definidos no dicionário são considerados erros) como ainda a correcção dos mesmos (i.e. o nome mais similar que se encontre definido no dicionário pode ser usado como uma correcção).

A ferramenta LingPipe concretiza mecanismos para a detecção e correcção de erros ortográficos. O código Java que se segue exemplifica esta funcionalidade:

import java.io.*;
import java.util.*;
import com.aliasi.lm.*;
import com.aliasi.spell.*;
import com.aliasi.util.*;
import com.aliasi.tokenizer.*;

public class ExampleSpellingCorrection {

private static final int NGRAM_LENGTH = 5;
static final double MATCH_WEIGHT = -0.0;
static final double DELETE_WEIGHT = -4.0;
static final double INSERT_WEIGHT = -1.0;
static final double SUBSTITUTE_WEIGHT = -2.0;
static final double TRANSPOSE_WEIGHT = -2.0;

public static void main(String[] args) throws Exception {
String dictionary = args[0];
String query = args[1];
System.out.println("Input="+query);
FixedWeightEditDistance fixedEdit = new FixedWeightEditDistance(MATCH_WEIGHT,DELETE_WEIGHT,INSERT_WEIGHT,SUBSTITUTE_WEIGHT,TRANSPOSE_WEIGHT);
NGramProcessLM lm = new NGramProcessLM(NGRAM_LENGTH);
TokenizerFactory tokenizerFactory = new IndoEuropeanTokenizerFactory();
TrainSpellChecker sc = new TrainSpellChecker(lm,fixedEdit,tokenizerFactory);
String charSequence = Files.readFromFile(new File(dictionary));
sc.train(charSequence);
ByteArrayOutputStream buf = new ByteArrayOutputStream();
sc.compileTo(new ObjectOutputStream(buf));
CompiledSpellChecker compiledSC = (CompiledSpellChecker) (new ObjectInputStream(new ByteArrayInputStream(buf.toByteArray()))).readObject();
String bestAlternative = compiledSC.didYouMean(query);
if (bestAlternative.equals(query)) {
System.out.println("No spelling correction found.");
} else {
System.out.println("Suggested spelling correction : " + bestAlternative);
}
}
}

O exemplo baseia-se na construção de um modelo estatístico com base num dicionário definido num ficheiro de texto. A geração de correcções ortográficas é posteriormente feita com base de distância de edição entre a string dada como input e as strings que se encontram definidas no modelo. Originalmente proposta pelo cientista russo Vladimir Levenshtein, a distância de edição entre duas strings é dada pelo número mínimo de operações necessárias para transformar uma string na outra. Entendemos por "operações" o inserir, apagar, transpor ou substituir de um caracter. Quando menor a distância de edição mais similares são as strings, e logo mais provável é o facto de estarmos perante um erro ortográfico. Este exemplo usa em concreto uma variante da medida proposta por Levenshtein, na qual as operações de edição têm pesos diferentes (e.g. ao ocorrer um erro, é mais provável que se dê devido à falta de uma letra do que à troca de duas letras).

É de referir ainda que os sistemas de correcção ortográfica usam muitas vezes mecanismos mais sofisticados, tais como distância fonética entre as palavras (e.g. o algoritmo soundex) ou a proximidade entre as teclas num teclado convencional (e.g. substituir um "b" por um "n" é mais provável do que substituir um "b" por um "t", dada a proximidade entre as teclas).

Outras operações de limpeza de dados

Nesta aula prática abordamos apenas superficialmente o problema da limpeza de dados. Começam a surgir no mercado algumas ferramentas especificamente desenhadas para estas tarefas. Estas ferramentas caem sobretudo em duas categorias genéricas:

  • Ferramentas verticais tais como o Trillium , as quais se focam em funcionalidades específicas restritas a um dado domínio (e.g. limpeza de moradas).
  • Ferramentas horizontais tais como o Microsoft SQL Server Integration Services (SSIS), as quais são aplicáveis a vários domínios oferendo um conjunto genérico de operadores para a limpeza e integração de dados. As ferramentas de ETL mencionanas na aula prática anterior também se enquadram nesta categoria.

A quem tenha curiosidade sobre o assunto, aconselha-se a leitura da documentação do Microsoft SQL Server Integration Services ( http://www.microsoft.com/technet/prodtechnol/sql/2005/intro2is.mspx )

Links