Correspondência difusa de dados estruturados

Question

Eu tenho um corpus bastante pequeno de registros estruturados em um banco de dados.Dada uma pequena fração das informações contidas em um único registro, enviado através de um formulário web (estruturado da mesma forma que o esquema da tabela), (vamos chamá-lo de registro de teste), preciso elaborar rapidamente uma lista dos registros que são as correspondências mais prováveis ​​para o registro de teste, bem como fornecem uma estimativa de confiança de quão próximo os termos de pesquisa correspondem a um registro.O objetivo principal desta pesquisa é descobrir se alguém está tentando inserir um registro que seja duplicado no corpus.Há uma chance razoável de que o registro do teste seja ingênuo e uma chance razoável de que o registro do teste não seja ingênuo.

Os registros têm cerca de 12.000 bytes de largura e a contagem total de registros é de cerca de 150.000.Existem 110 colunas no esquema da tabela e 95% das pesquisas estarão nas 5% das colunas mais pesquisadas.

Os dados são nomes, endereços, números de telefone e outros números específicos do setor.Tanto no corpus quanto no registro do teste ele é inserido manualmente e é semiestruturado em um campo individual.À primeira vista, você pode dizer "pesar as colunas manualmente e combinar os tokens de palavras dentro delas", mas não é tão fácil.Também achei:se eu conseguisse um número de telefone, pensei que isso indicaria uma combinação perfeita.O problema é que não existe um único campo no formulário cuja frequência do token não varie em ordens de grandeza.Um número de telefone pode aparecer 100 vezes no corpus ou 1 vez no corpus.O mesmo vale para qualquer outro campo.Isto torna a ponderação no nível do campo impraticável.Preciso de uma abordagem mais refinada para obter uma correspondência decente.

Meu plano inicial era criar um hash de hashes, sendo o nível superior o nome do campo.Em seguida, eu selecionaria todas as informações do corpus para um determinado campo, tentaria limpar os dados contidos nele e tokenizaria os dados higienizados, fazendo hash dos tokens no segundo nível, com os tokens como chaves e a frequência como valor.

Eu usaria a contagem de frequência como peso:quanto maior a frequência de um token no corpus de referência, menor peso atribuo a esse token se ele for encontrado no registro de teste.

Minha primeira pergunta é para os estatísticos presentes:como eu usaria a frequência como peso?Existe uma relação matemática precisa entre n, o número de registros, f(t), a frequência com que um token t apareceu no corpus, a probabilidade o de que um registro seja original e não duplicado, e a probabilidade p de que o registro de teste é realmente um registro x, dado que o teste e x contêm o mesmo t no mesmo campo?E quanto ao relacionamento para correspondências de vários tokens em vários campos?

Como duvido sinceramente que exista, há algo que me aproxime, mas seja melhor do que um hack completamente arbitrário cheio de fatores mágicos?

Tirando isso, alguém tem uma maneira de fazer isso?

Estou especialmente interessado em outras sugestões que não envolvam a manutenção de outra tabela no banco de dados, como uma tabela de pesquisa de frequência de token.

Answer 1

Você provavelmente pode obter algumas idéias desta pergunta SO diferente, mas semelhante:cálculo de correlação de texto sensível ao contexto.

Mais específico para o problema em questão, aqui estão alguns pensamentos e ideias:

Em primeiro lugar, reconhecendo o uso muito distorcido (apenas 6 a 10 atributos cobrem 95% do uso), você pode/deve aplicar esforço assimétrico nos atributos, ou seja,invista mais, tanto em termos de tempo de programação quanto em termos de alocação de CPU em tempo de execução, para lidar com esses poucos atributos do que com mais de 100 atributos adicionais.

A quantidade relativamente pequena de dados fornecidos como entrada para correspondência de possíveis duplicatas no banco de dados, o conjunto relativamente pequeno de atributos normalmente usados ​​e a semântica aparentemente comum destes (número de telefone, endereço, nome...) sugerem uma solução artesanal. em vez de um completamente baseado em aprendizado de máquina.

Observação:muitas das sugestões daí em diante não precisam ser aplicadas a todos os atributos (já que menos de uma dúzia delas cobrem praticamente todo o uso, não faz sentido, pelo menos a princípio, investir muito nos outros atributos.

• Normalize os dados
  Se não for permitido alterar os valores originais do campo, talvez duplique as colunas correspondentes para uma coluna "norm_xxx" onde xxx é o nome original.
  O quê, como normalizar pode variar de acordo com cada atributo;para dados como "texto livre", certifique-se de que não haja espaços no início nem no final, apenas um espaço entre as palavras, nem tabulações e caracteres não imprimíveis.Use todas as letras maiúsculas ou todas as minúsculas (mesmo que o texto original/para exibição possa incluir uma mistura, seu processamento será mais rápido ao ser capaz de assumir maiúsculas e minúsculas uniformes).Mais especificamente para endereços e/ou nomes de empresas, você pode converter termos comuns em um formato padrão (ST para RUA, ST e ST, etc.) (Certifique-se de manter esta lista, pois ela também será aplicada aos critérios de pesquisa do usuário ).Parte da normalização também pode ser eliminar completamente algumas palavras barulhentas (como CO, INC, GMBH no final dos nomes das empresas)
• Crie algumas colunas calculadas
  Por exemplo, aqueles com o texto, ao contrário, para atributos que podem ser pesquisados ​​com um curinga final
• Considere usar uma conversão semelhante ao Soundex para alguns atributos.
• Índice FullText, individualmente, todas as colunas semelhantes a texto
• Crie índices simples (SQL) em todas as 6 a 10 colunas mais usadas

Todos os itens acima são meros preparativos off-line para a realização de partidas.Agora..o usuário insere sua consulta ...aqui estão algumas idéias sobre como lidar com isso

• Normalize os critérios de pesquisa que o justificam
• Faça várias pesquisas...
  Isso é um pouco complicado;existem vários objetivos, parcialmente conflitantes, para realizar essas pesquisas.Queremos reduzir significativamente o número de "potenciais correspondências":é efetivamente impraticável fazer uma comparação individual completa de todos os 150.000 registros com os critérios fornecidos pelo usuário;por exemplo, parte da lógica de correspondência pode implicar o cálculo da distância de edição entre um campo de um determinado registro do banco de dados e um critério de pesquisa.Também queremos garantir que não excluímos registros da lista de "correspondências potenciais" devido a um erro de digitação no nome da empresa...Finalmente, queremos fornecer a lista de possíveis correspondências de forma classificada.
  A forma de realizar essas buscas segue algumas heurísticas pré-definidas (achei que o padrão de design da estratégia funciona bem para isso, permitindo flexibilidade na forma como as buscas são executadas, dependendo da entrada fornecida pelo usuário).Resumindo, procuramos as palavras mais seletivas nos atributos mais seletivos/relevantes e, com base no número de "acertos" encontrados, "OU" (união) ou "AND" com outros resultados de pesquisa, até termos alguns cem recorde.
• Calcule um valor de similaridade entre cada atributo dos registros de "correspondências potenciais" e os critérios de pesquisa correspondentes.Possivelmente aplicar um coeficiente a este valor (permitindo colocar mais peso para dizer que o nome de uma empresa corresponde [parcial] a uma correspondência de cidade)
• Calcule o valor de similaridade geral para um registro completo (vs.os critérios de pesquisa completos)

• Mostrar os registros que excedem um limite específico do valor de similaridade para o usuário final, para revisão

  Finalmente, e chega um processo parcialmente automatizado, você pode alterar alguns dos parâmetros com base em algum feedback fornecido pelo usuário final.(isso é muito complicado de fazer, vou guardar isso para outro post ;-))