Como faço para construir um algoritmo correspondente?

Question

Eu nunca construí um algoritmo para combinar antes e não sei por onde começar. Então, aqui está minha configuração básica e por que estou fazendo isso. Sinta -se à vontade para me corrigir se não estiver fazendo as perguntas certas.

Eu tenho um banco de dados de nomes e identificadores únicos para as pessoas. Vários identificadores gerados (gerados internamente e alguns terceiros), sobrenome, primeiro nome e data de nascimento são os principais que eu usaria.

Várias vezes ao longo do ano, recebo uma lista de terceiros que precisam ser importados e vinculados às pessoas existentes no meu banco de dados, mas os dados nunca são tão limpos quanto os meus. Os IDs podem mudar, as datas de nascimento podem ter erros de digitação, nomes podem ter erros de digitação, sobrenomes podem mudar, etc.

Cada importação pode ter 20.000 registros, portanto, mesmo que seja 99% preciso, ainda são 200 registros que eu teria que entrar manualmente e combinar. Acho que estou procurando uma precisão de 99,9% quando se trata de combinar as pessoas que chegam aos meus usuários.

Então, como faço para fazer um algoritmo que pode descobrir isso?

PS Mesmo se você não tiver uma resposta exata, mas saiba que alguns materiais a referência também serão úteis.

PPS Alguns exemplos seriam semelhantes ao que M3rlinez escreveu:

ID: 9876234 Fname: Jose     LName: Guitierrez       Birthdate:01/20/84  '- Original'

ID: 9876234 Fname: Jose     LName: Guitierrez       Birthdate:10/20/84  '- Typo in birth date'
ID: 0876234 Fname: Jose     LName: Guitierrez       Birthdate:01/20/84  '- Wrong ID'
ID: 9876234 Fname: Jose     LName: Guitierrez-Brown Birthdate:01/20/84  '- Hyphenated last name'
ID: 9876234 Fname: Jose, A. LName: Guitierrez       Birthdate:01/20/84  '- Added middle initial'
ID: 3453555 Fname: Joseph   LName: Guitierrez       Birthdate:01/20/84  '- Probably someone else with same birthdate and same last name'

Answer 1

Você pode estar interessado em Distância de Levenshtein.

A distância de Levenshtein entre duas cordas é definida como o número mínimo de edições necessárias para transformar uma corda na outra, com as operações de edição permitidas sendo inserção, exclusão ou substituição de um único caractere. É nomeado em homenagem a Vladimir Levenshtein, que considerou essa distância em 1965.1

É possível comparar todos os seus campos e calcular a distância total. E por tentativa e erro, você pode descobrir o limite apropriado para permitir que os registros sejam interpretados como correspondentes. Não implementaram isso eu mesmo, mas apenas pensei na ideia:}

Por exemplo:

• Registro A - ID: 4831213321, Nome: Jane
• Registro B - ID: 431213321, Nome: Jann
• Registro C - ID: 4831211021, Nome: John

A distância entre A e B será menor que A e C / B e C, o que indica melhor corresponder.

Answer 2

Quando se trata de algo assim, não reinvente a roda. A distância de Levehstein é provavelmente a sua melhor aposta se você precisar fazer isso sozinho, mas, caso contrário, faça algumas pesquisas sobre soluções existentes que fazem consultas de banco de dados e pesquisas difusas. Eles estão fazendo isso há mais tempo do que você, provavelmente será melhor também ..

Boa sorte!

Answer 3

Se você estiver lidando com conjuntos de dados desse tamanho e diferentes recursos que estão sendo importados, convém procurar uma solução de gerenciamento de identidade. Estou familiarizado com o Sun Identity Manager, mas pode ser um exagero para o que você está tentando fazer. Pode valer a pena investigar.

Answer 4

Se os dados que você estiver recebendo de terceiros forem consistentes (o mesmo formato de cada vez) eu provavelmente criaria uma tabela para cada uma das terceiras partes da qual você está obtendo dados. Em seguida, importe cada novo conjunto de dados para a mesma tabela a cada vez. Eu sei que há uma maneira de ingressar nas duas tabelas com base em colunas comuns em cada uma usando uma instrução SQL. Dessa forma, você pode executar consultas SQL e obter dados de várias tabelas, mas faça parecer que veio de uma única tabela unificada. Da mesma forma, os registros adicionados que não têm correspondências em ambas as tabelas podem ser encontrados e depois emparelhados manualmente. Dessa forma, você mantém seus dados 'limpos' separados do lixo que obtém de terceiros. Se você quisesse uma verdadeira importação, poderia usar essa tabela unida para criar uma terceira tabela que contém todos os seus dados.

Answer 5

Eu começaria com o fácil quase 100% de correspondências e lidava com eles primeiro, então agora você tem uma lista de 200 que precisam ser consertados.

Para as linhas restantes, você pode usar uma versão simplificada de Teorema de Bayes.

Para cada linha incomparável, calcule o probabilidade que é uma correspondência para cada linha no seu conjunto de dados, assumindo que os dados contêm certas alterações que ocorrem com certas probabilidades. Por exemplo, uma pessoa altera seu sobrenome com probabilidade de 0,1% (possivelmente também depende do sexo), altera seu primeiro nome com probabilidade de 0,01% e é A possui um único erro de digitação com probabilidade 0,2% (uso Distância de Levenshtein para contar o número de erros de digitação). Outros campos também mudam com certas probabilidades. Para cada linha, calcule a probabilidade que a linha corresponda, considerando todos os campos que mudaram. Em seguida, escolha o que tem a maior probabilidade de ser uma partida.

Por exemplo, uma linha com apenas um pequeno erro de digitação em um campo, mas igual a todos os outros teria uma chance de 0,2% de partida, enquanto linhas que diferem em muitos campos podem ter apenas uma chance de 0,00001%. Então você escolhe a linha com o pequeno erro de digitação.

Answer 6

Expressões regulares são o que você precisa, por que reinventar a roda?