Estado da arte em desduplicação

Quais são os métodos de ponta na desduplicação de registro? Às vezes, a desduplicação também é chamada: ligação de registro, resolução de entidade, resolução de identidade, mesclagem / eliminação. Eu sei, por exemplo, sobre CBLOCK [1].

Eu apreciaria se as respostas também incluíssem referências ao software existente que implementa os métodos. Eu sei, por exemplo, que o Mahout implementa cluster de copa . Há também Duke que usa Lucene.

Existem muitos sistemas comerciais para desduplicação. Seria valioso saber como eles funcionam e quão eficientes são.

Estou interessado tanto na desduplicação em um único conjunto de dados quanto na vinculação entre vários conjuntos de dados provenientes de diferentes fontes. A eficiência e a capacidade de processar grandes quantidades de dados também são importantes.

[1] CBLOCK: um mecanismo de bloqueio automático para tarefas de desduplicação em larga escala

Tamr (anteriormente Data Tamer) realiza a desduplicação de banco de dados em escala. Naive Bayes e agrupamento de gráficos estão envolvidos.

Acredito que os algoritmos sejam amplamente implementados no SQL, o que é um tanto estranho, mas o principal autor do whitepaper é Michael Stonebraker, que ajudou a liderar a criação do PostgreSQL.

Confira o whitepaper aqui .

Editar: Resumi as etapas que o artigo deles segue abaixo. Algumas das minhas palavras são quase as mesmas do artigo.

O sistema de desduplicação da Tamr possui duas etapas principais para lidar com uma nova fonte de dados: (1) identificação de atributo e (2) consolidação de entidade. Eles são aproximadamente equivalentes à desduplicação de coluna e desduplicação de linha.

1) Comparando uma nova fonte de dados com uma existente, a primeira etapa é a identificação de atributo.

Os atributos (colunas) da nova fonte são mapeados para os atributos da fonte existente com quatro algoritmos:

• Comparar nomes de atributos com comparação de cadeias difusas (semelhança do trigrama cosseno)
• Considere uma coluna inteira como um documento, tokenize, meça a similaridade de cosseno da frequência total / frequência inversa do documento (TF-IDF) entre essa e outras colunas.
• Comprimento descritivo mínimo: compare duas colunas com base nos tamanhos de sua interseção e união com a correspondência exata.
• Para colunas numéricas, execute um teste t entre a nova coluna e as colunas numéricas existentes para determinar se elas vieram da mesma distribuição.

2) Consolidação de entidade (deduplicação de linha)

Após a identificação do atributo, queremos deduplicar as linhas (registros).

Categorização com armazenamento em cluster

Os registros são primeiro agrupados em categorias base na similaridade e, em seguida, as regras de deduplicação são aprendidas no nível da categoria. O exemplo que eles dão da categorização é para um banco de dados de estações de esqui, onde estações de esqui ocidentais devem ser uma categoria diferente das estações de esqui orientais, já que recursos como elevação da base são fortemente separados por se o resort é leste ou oeste. A categorização é feita com um algoritmo de agrupamento, com médias k dadas como exemplo.

Desduplicando com Naive Bayes

Depois que os atributos são identificados e os registros foram agrupados em categorias, aprendemos as regras de deduplicação para cada categoria com base em um conjunto de treinamento de enganadores e não enganadores.

Existem dois tipos de regras de deduplicação:

1. Limiares para semelhanças de atributos em relação a uma função de distância que faz sentido para o atributo. (O artigo não está claro sobre como esses limites são aprendidos.)
2. Distribuições de probabilidade para enganadores e não enganadores em cada atributo. por exemplo P("Title" values similar | duplicate) ~ 1e Pr("State" values are different | duplicate) ~ 0

Para cada par de registros, calculamos a semelhança de cada um de seus atributos com uma métrica de distância apropriada. Se algum atributo tiver uma similaridade acima de seu limite, o par de registros é alimentado por meio de um classificador Naive Bayes para ser classificado como dupe ou não dupe.

Minha suposição é que para os registros X1 = (a1,b1,c1,d1), X2 = (a2,b2,c2,d2)eles calcular um vector similaridade S = (s_a, s_b, s_c, s_d)onde s_iuma semelhança para que wrt atributo para a métrica distância correta.

Presumo que o classificador Naive Bayes tenha essa estrutura:

P(dupe|S) = P(dupe)P(s_a|dupe)(s_b|dupe)(s_c|dupe)P(s_d|dupe) / P(S)

Resolução de entidade com agrupamento de gráficos

Após a etapa de classificação, temos um subconjunto de registros de uma determinada categoria que se acredita serem duplicatas em pares. Agora eles precisam ser resolvidos em entidades distintas . Isso resolve um problema de transitividade: se o registro t1 é um tolo de t2 e t2 é um tolo de t3, então t1 também deve ter um tup de t3. Isto é, t1, t2 e t3 representam a mesma entidade .

Uma estrutura gráfica é usada para esta etapa. Dentro da categoria, cada registro que pode ser um dupe é um nó. Os nós suspeitos de serem enganadores um do outro têm bordas entre eles. Os clusters são descobertos no gráfico e depois mesclados com base nos limites relativos à força com que um cluster está conectado a outro. Aqui estão três exemplos de pares de cluster que podem ou não ser mesclados com base em sua conexão:

  c1        c2    

x-x-x-----y-y-y
|\|/|     |\|/|
x-x-x-----y-y-y  Meets similiarity threshold
|/|\|     |/|\|
x-x-x-----y-y-y    

x-x-x     y-y-y
|\|/|     |\|/|
x-x-x-----y-y-y  Does not meet similarity threshold
|/|\|     |/|\|
x-x-x     y-y-y    

    x     y
    |     |
    x-----y      Meets similarity threshold
    |     |
    x     y

Quando o algoritmo termina, cada cluster deve representar uma entidade distinta dentro da categoria . Para concluir o processo, os atributos desta entidade devem ser determinados a partir dos atributos dos registros contidos nela . Os nulos são descartados primeiro e, em seguida, métodos incluindo frequência, média, mediana e mais longos são usados.

O documento também desenvolve alguns métodos para o uso de especialistas em domínio para ajudar quando os algoritmos não estão certos e como usar vários especialistas com diferentes níveis de conhecimento.