Deduplicação de registros complexos / Detecção de similaridade

5

Estou trabalhando em um projeto que envolve registros com um grande número de campos (~ 15-20) e estou tentando descobrir uma boa maneira de implementar a deduplicação. Essencialmente, os registros são pessoas, juntamente com alguns dados adicionais. Por exemplo, é provável que os registros incluam informações pessoais como nome, sobrenome, endereço postal, endereço de e-mail, etc., mas nem todos os registros têm a mesma quantidade de dados.

Atualmente os registros são armazenados em um RDBMS (MySQL) e eu quero detectar duplicatas na inserção e ainda tê-los inseridos, mas marcados como duplicados. Ele precisa ser rápido, já que preciso fornecer feedback sobre se é uma duplicata ou não em tempo real. O conjunto de dados é grande (milhões de registros).

Eu considerei as seguintes opções, mas não tenho certeza qual é a melhor / se elas são as melhores opções disponíveis:

  • Use a pesquisa de texto completo do MySQL e use a pesquisa difusa. O principal problema com isto é que parece lento, apenas a versão mais recente suporta índices de texto completo com InnoDB (o mecanismo alternativo é MyISAM que não é bom e criticamente não suporta transações) e a busca difusa por si só não parece ser o melhor método para detecção de similaridade. / li>
  • Use simhash ou similar. Problema com isso é que eu também gostaria de ser capaz de detectar sinônimos que eu não vejo como o simhash lida com isso. Por exemplo, o endereço pode ser: "Some Road" ou "Some Rd". e nomes podem ser: "Mike" ou "Michael"
  • Indexar os dados usando um derivativo do Apache Lucene (elasticsearch / solr / etc) e executar uma consulta que provavelmente retornará inúmeros resultados.

Em termos de uso do Apache Lucene, tenho lido sobre detecção de similaridade e usando similaridade de cosseno para produzir um valor de 0 a 1 a partir dos vetores de frequência de termo que o lucene armazena. Eu poderia aplicar isso aos resultados da consulta lucene e verificar se algum dos resultados está acima de um certo limite. Minha preocupação sobre isso é quão relevante seria a similaridade de cosseno para o tipo de dados que estou armazenando, ou seja, um número de campos com um único ou pequeno número de palavras comparado ao cálculo da semelhança de cosseno de uma comparação de algum documento de texto grande .

Basicamente, estou imaginando qual é a melhor maneira de desduplicar esse tipo de dados (ou, alternativamente, detectar semelhanças com esse tipo de dado)?

    
por Tomdarkness 29.09.2013 / 14:56
fonte

3 respostas

2

Não há bala de prata para desduplicação. Você deve se concentrar primeiro na normalização (a partir de um padrão, não de 3NF) e padronização. Isto dá-lhe algum tipo de igualdade de condições para começar a fazer comparações.

Para conseguir isso, você precisa aplicar as técnicas de padronização que funcionam para cada tipo de dado. A padronização de dados de endereço é um domínio de problema totalmente diferente da padronização de nomes fornecidos. A maioria desses domínios de problemas de padronização de dados é complexa demais para tentar resolver a si mesmo. Considere comprar software de terceiros que faça validação e padronização de endereço postal e um que dê nome à padronização.

Para coisas como endereços de e-mail ou números de telefone, você provavelmente pode criar seus próprios, já que eles são relativamente diretos em comparação.

Uma vez que você tenha seus componentes de dados devidamente padronizados, então você pode se preocupar com o que é melhor: correspondência difusa, distância de Levenshtein ou semelhança de cosseno (etc.)

É melhor considerar a correspondência como subelementos em vez de tentar obter registros como um todo. Então, veja quantos subelementos correspondem razoavelmente. Dois nomes idênticos com diferentes endereços de e-mail e endereços de correspondência são uma correspondência muito fraca. Dois nomes quase idênticos, com endereços de correspondência quase idênticos, com um registro sem o endereço de e-mail, provavelmente são uma correspondência bastante strong.

    
por 29.09.2013 / 19:41
fonte
1

Para muitas técnicas de desduplicação, a padronização de dados é, como apontou Joel Brown, muito importante. Mas você pode conseguir passar sem ela se usar minhash.

Você ainda deseja normalizar os dados o máximo que puder: por exemplo, normalização de maiúsculas e minúsculas, ignorando pontuação em endereços, etc. Você pode até normalizar sinônimos se você tiver grupos de sinônimos conhecidos; então "Mount Saint Helens Street" se torna "mt st helens st" (introduzir uma ambigüidade como essa normalmente não prejudica a precisão de seus resultados, mas melhora a recordação).

Os nomes e endereços ainda são diferentes, com erros de ortografia, possíveis alterações nas encomendas e, talvez, inclusão de itens extras. nomes do meio ou nomes de regiões diferentes. Isso não precisa ser um problema.

O Minhash gera vários hashes por registro, com base nos recursos. Em muitas implementações, as pessoas simplesmente lançam todos os recursos em um único gerador da minhash, e obtêm, digamos, 50 hashes como resultado; mas no seu caso você pode querer dividir isso. Pegue todos os campos de nome, gere, digamos, telhas de 7 caracteres para cada uma delas, e jogue as telhas em um gerador de minsh que cospe, digamos, 5 hashes. Pegue todos os campos de endereço postal / físico e faça o mesmo usando outro gerador da minhash, que cospe, digamos, 15 hashes. Derive, digamos, 3 hashes do endereço de e-mail por conta própria. E assim por diante.

O número de hashes que você mantém para cada tipo de informação pode ser ajustado dependendo de quão importante é essa informação para determinar uma duplicata e da probabilidade de o campo não ter sido preenchido. Os dados mais confiáveis devem ter o máximo hashes atribuídos a ele.

Encontrar duplicatas próximas é bastante simples. É um pouco mais lento que o simhash e pode ocupar um pouco de memória, porque tem que filtrar um grande número de resultados, contando hashes compartilhados para cada um. Na pior das hipóteses, alguns poucos meushes podem ser selecionados de partes muito genéricas do registro, como "@gmail". no endereço de e-mail e pode estar presente em centenas de milhares ou mesmo milhões de outros registros. Mas a beleza da minhash é que ela permite que você encontre resultados que não são apenas 4 ou 5% diferentes, mas 20%, 40% ou o quanto você gosta, realmente.

(Você pode, de certa forma, derrotar esses meushes "genéricos" usando a mesma técnica que a substituição de sinônimos e substituir cadeias genéricas muito comuns, como "@ gmail.com", por marcadores menores, como "@G!". do que a sua telha de 7 caracteres, por isso nunca formará uma telha por conta própria.)

Existem algumas variantes na minhash que melhoram os resultados, exigindo menos hashes para representar os mesmos dados (consulte link ), mas se o tamanho de cada registro for pequeno, isso pode não trazer benefícios significativos. Você pode já ter 30 ou 40 hashes por registro (e hashes de 32 bits podem ser suficientes). Se você ainda não atenuou o problema "meushes genéricos", o hash sensível à localização (LSH) pode ajudar bastante; embora isso reduza a precisão das estimativas de similaridade.

    
por 12.10.2017 / 05:34
fonte
-2

faça o endereço de e-mail como chave primária, pois o endereço de e-mail sempre é único. para que os dados redundantes não estejam lá.

Caso você tenha endereço e nome da pessoa, então você pode usar ambos para checar duplicatas

    
por 29.09.2013 / 17:44
fonte