Como posso transformar nomes em um conjunto de dados confidenciais para torná-lo anônimo, mas preservar algumas das características dos nomes?

42

Motivação

Trabalho com conjuntos de dados que contêm informações de identificação pessoal (PII) e às vezes preciso compartilhar parte de um conjunto de dados com terceiros, de uma maneira que não exponha as PII e sujeite meu empregador a responsabilidades. Nossa abordagem usual aqui é reter os dados inteiramente ou, em alguns casos, reduzir sua resolução; por exemplo, substituindo um endereço exato da rua pelo município ou setor censitário correspondente.

Isso significa que certos tipos de análise e processamento devem ser feitos internamente, mesmo quando um terceiro tiver recursos e conhecimentos mais adequados à tarefa. Como os dados de origem não são divulgados, o modo como processamos essa análise e processamento carece de transparência. Como resultado, a capacidade de terceiros de executar controle de qualidade / controle de qualidade, ajustar parâmetros ou fazer refinamentos pode ser muito limitada.

Anonimizando dados confidenciais

Uma tarefa envolve a identificação de indivíduos por seus nomes, nos dados enviados pelo usuário, levando em consideração erros e inconsistências. Um indivíduo particular pode ser gravado em um local como "Dave" e em outro como "David", as entidades comerciais podem ter muitas abreviações diferentes e sempre há alguns erros de digitação. Desenvolvi scripts com base em vários critérios que determinam quando dois registros com nomes não idênticos representam o mesmo indivíduo e atribuem a eles um ID comum.

Nesse ponto, podemos tornar o conjunto de dados anônimo, retendo os nomes e substituindo-os por esse número de identificação pessoal. Mas isso significa que o destinatário quase não tem informações sobre, por exemplo, a força da partida. Preferimos poder transmitir o máximo de informação possível sem divulgar a identidade.

O que não funciona

Por exemplo, seria ótimo poder criptografar seqüências de caracteres, preservando a distância de edição. Dessa forma, terceiros podem fazer parte de seu próprio controle de qualidade / controle de qualidade, ou optar por fazer um processamento adicional por conta própria, sem nunca acessar (ou poderem potencialmente fazer engenharia reversa) as IIP. Talvez combinemos as strings internamente com a distância de edição <= 2, e o destinatário deseja examinar as implicações de aumentar essa tolerância para editar a distância <= 1.

Mas o único método que eu conheço que faz isso é o ROT13 (mais geralmente, qualquer cifra de deslocamento ), que dificilmente conta como criptografia; é como escrever os nomes de cabeça para baixo e dizer: "Promete que não vai virar o papel?"

Outra solução ruim seria abreviar tudo. "Ellen Roberts" se torna "ER" e assim por diante. Essa é uma solução ruim porque, em alguns casos, as iniciais, em associação com dados públicos, revelam a identidade de uma pessoa e, em outros casos, é ambíguo demais; "Benjamin Othello Ames" e "Bank of America" ​​terão as mesmas iniciais, mas seus nomes são diferentes. Portanto, ele não faz nenhuma das coisas que queremos.

Uma alternativa deselegante é a introdução de campos adicionais para rastrear certos atributos do nome, por exemplo:

+-----+----+-------------------+-----------+--------+
| Row | ID | Name              | WordChars | Origin |
+-----+----+-------------------+-----------+--------+
| 1   | 17 | "AMELIA BEDELIA"  | (6, 7)    | Eng    |
+-----+----+-------------------+-----------+--------+
| 2   | 18 | "CHRISTOPH BAUER" | (9, 5)    | Ger    |
+-----+----+-------------------+-----------+--------+
| 3   | 18 | "C J BAUER"       | (1, 1, 5) | Ger    |
+-----+----+-------------------+-----------+--------+
| 4   | 19 | "FRANZ HELLER"    | (5, 6)    | Ger    |
+-----+----+-------------------+-----------+--------+

Eu chamo isso de "deselegante" porque requer antecipar quais qualidades podem ser interessantes e é relativamente grossa. Se os nomes forem removidos, não há muito que você possa concluir razoavelmente sobre a força da correspondência entre as linhas 2 e 3 ou sobre a distância entre as linhas 2 e 4 (ou seja, quão próximas elas estão da correspondência).

Conclusão

O objetivo é transformar cadeias de caracteres de maneira que o máximo possível de qualidades úteis da cadeia original seja preservado, enquanto oculta a cadeia original. A descriptografia deve ser impossível, ou tão impraticável que seja efetivamente impossível, independentemente do tamanho do conjunto de dados. Em particular, um método que preserva a distância de edição entre cadeias arbitrárias seria muito útil.

Encontrei alguns documentos que podem ser relevantes, mas estão um pouco exagerados:

Ar
fonte

Respostas:

19

Uma das referências que mencionei no OP me levou a uma solução potencial que parece bastante poderosa, descrita em " Vinculação de registros de preservação de privacidade usando filtros Bloom" ( doi: 10.1186 / 1472-6947-9-41 ):

Um novo protocolo para ligação de registros de preservação da privacidade com identificadores criptografados, permitindo erros nos identificadores, foi desenvolvido. O protocolo é baseado em filtros Bloom em q-gramas de identificadores.

O artigo entra em detalhes sobre o método, que resumirei aqui da melhor maneira possível.

Um filtro Bloom é uma série de bits de tamanho fixo que armazena os resultados de um conjunto fixo de funções hash independentes, cada uma calculada no mesmo valor de entrada. A saída de cada função de hash deve ser um valor de índice dentre os possíveis índices no filtro; ou seja, se você possui uma série de 10 bits indexada a 0, as funções de hash devem retornar (ou ser mapeadas para) valores de 0 a 9.

O filtro começa com cada bit definido como 0. Após o hash do valor de entrada com cada função do conjunto de funções hash, cada bit correspondente a um valor de índice retornado por qualquer função hash é definido como 1. Se o mesmo índice for retornado por mais de uma função hash, o bit nesse índice é definido apenas uma vez. Você pode considerar o filtro Bloom como uma superposição do conjunto de hashes no intervalo fixo de bits.

O protocolo descrito no artigo vinculado acima divide as seqüências de caracteres em n gramas, que são nesse caso conjuntos de caracteres. Como exemplo, "hello"pode render o seguinte conjunto de 2 gramas:

["_h", "he", "el", "ll", "lo", "o_"]

Preencher a frente e as costas com espaços parece ser geralmente opcional ao construir n-gramas; os exemplos dados no artigo que propõe esse método usam esse preenchimento.

Cada n-grama pode ser dividido em hash para produzir um filtro Bloom, e esse conjunto de filtros Bloom pode ser sobreposto (operação OR bit a bit) para produzir o filtro Bloom para a string.

Se o filtro contiver muito mais bits do que as funções hash ou n-gramas, é improvável que cadeias arbitrárias produzam exatamente o mesmo filtro. No entanto, quanto mais n-gramas duas seqüências tiverem em comum, mais bits seus filtros compartilharão. Você pode comparar quaisquer dois filtros A, Bpor meio do coeficiente de dados:

D A, B = 2h / (a ​​+ b)

Onde hé o número de bits que estão definidos para 1 em ambos os filtros, aé o número de bits definidos como 1 em única filtro A, e bé o número de bits definidos como 1 em única filtro B. Se as cordas são exatamente o mesmo, o coeficiente de dados será 1; quanto mais diferem, mais próximo estará o coeficiente 0.

Como as funções hash estão mapeando um número indeterminado de entradas exclusivas para um pequeno número possível de índices de bits, entradas diferentes podem produzir o mesmo filtro, portanto, o coeficiente indica apenas uma probabilidade de que as seqüências sejam iguais ou semelhantes. O número de diferentes funções de hash e o número de bits no filtro são parâmetros importantes para determinar a probabilidade de falsos positivos - pares de entradas muito menos semelhantes ao previsto pelo coeficiente de dados produzido por este método.

Achei este tutorial muito útil para entender o filtro Bloom.

Existe alguma flexibilidade na implementação desse método; veja também este artigo de 2010 (também vinculado no final da pergunta) para algumas indicações de quão bom é o desempenho em relação a outros métodos e com vários parâmetros.

Ar
fonte
Marcando isso como a resposta aceita, porque das abordagens sugeridas, é a mais promissora para o meu caso de uso específico.
Air
Obrigado por todos esses detalhes e antecedentes. Você encontrou alguma implementação (por exemplo, em Python) dessa abordagem?
amball
@amball eu não tenho.
Air
8

No meio da leitura da sua pergunta, percebi que o Levenshtein Distance poderia ser uma boa solução para o seu problema. É bom ver que você tem um link para um artigo sobre o assunto, deixe-me ver se consigo esclarecer como seria uma solução Levenshtein.

A distância de Levenshtein é usada em muitos setores para a resolução de entidades, o que o torna útil é que é uma medida da diferença entre duas seqüências. No caso de comparação de strings, são apenas seqüências de caracteres.

Isso pode ajudar a resolver seu problema, permitindo que você forneça um número que forneça uma medida de quão semelhante é o texto de outro campo.

Aqui está um exemplo de uma maneira básica de usar o Levenshtein com os dados que você forneceu:

insira a descrição da imagem aqui

Isso fornece uma solução aceitável, a distância de 8 fornece alguma indicação de um relacionamento e é muito compatível com PII. No entanto, ainda não é super útil, vamos ver o que acontece se fizermos alguma mágica em texto para pegar apenas a primeira inicial do primeiro nome e o sobrenome completo, deixando qualquer coisa no meio:

insira a descrição da imagem aqui

Como você pode ver, a distância de 0 de Levenshtein é bastante indicativa de um relacionamento. Geralmente, os provedores de dados combinam várias permutações de Levenshtein do nome e sobrenome com 1, 2 ou todos os caracteres apenas para dar alguma dimensionalidade à forma como as entidades estão relacionadas, mantendo o anonimato nos dados.

neone4373
fonte
1
O que me interessa no artigo que vinculei é que ele afirma mostrar um método para executar esse tipo de cálculo sem o conhecimento das duas seqüências de entrada . No jornal, cada ator tem conhecimento de uma sequência, o que não é útil para meus propósitos; Eu precisaria de um ator para poder executar o cálculo sem o conhecimento de qualquer uma das strings. Calculá-los com antecedência só é viável para conjuntos de dados muito pequenos ou produtos muito limitados; um produto cruzado completo de distâncias inteiras no meu conjunto de dados levaria ~ 10 PB de armazenamento.
Air
Foi por isso que criei a idéia de uma cifra de substituição (ROT13), pois ela preserva a distância entre as strings; mas não é seguro, e suspeito que seja impossível criptografar com segurança as strings, preservando a distância de edição. (Gostaria muito de estar errado!) #
Air
Certo, eu apenas filtraria a matriz para incluir apenas Levenshteins abaixo de um determinado ponto de corte, para que você esteja preenchendo apenas onde houver uma alta probabilidade de sobreposição. Além disso, quando se trata de PII, penso que se você incluir informações suficientes para determinar um relacionamento entre entidades diferentes em seus conjuntos de dados, é muito improvável que você esteja preservando o anonimato dos clientes. O objetivo do anonimato dos dados é evitar possíveis dores de cabeça regulatórias relacionadas às PII nessa linha (os padrões sempre podem ser mais rígidos), de modo que, pessoalmente, eu não correria o risco.
neone4373
7

Se possível, vincularia registros relacionados (por exemplo, Dave, David etc.) e os substituiria por um número de sequência (1,2,3 etc.) ou um hash salgado da string usada para representar todos os registros relacionados ( por exemplo, David em vez de Dave).

Suponho que terceiros não precisam ter nenhuma idéia de qual é o nome verdadeiro; caso contrário, você também pode dar a eles.

editar : você precisa definir e justificar que tipo de operações o terceiro precisa ser capaz de executar. Por exemplo, o que há de errado em usar as iniciais seguidas de um número (por exemplo, BOA-1, BOA-2 etc.) para desambiguar o Bank of America de Benjamin Othello Ames? Se isso é muito revelador, você pode colocar algumas das letras ou nomes; por exemplo, [AE] -> 1, [FJ] -> 2, etc., para que o BOA se torne 1OA, ou ["Bank", "Barry", "Bruce" etc.] -> 1 para que o Bank of America esteja novamente 1OA.

Para mais informações, consulte k-anonimato .

Emre
fonte
Aprecie a referência do anonimato k e a sugestão do bin - que me dá algumas coisas novas em que pensar.
Air
6

Uma opção (dependendo do tamanho do conjunto de dados) é fornecer apenas as distâncias de edição (ou outras medidas de similaridade que você está usando) como um conjunto de dados adicional.

Por exemplo:

  1. Gere um conjunto de nomes exclusivos no conjunto de dados
  2. Para cada nome, calcule a distância de edição um do outro
  3. Gere um ID ou hash irreversível para cada nome
  4. Substitua nomes no conjunto de dados original por esse ID
  5. Fornecer matriz de distâncias de edição entre números de ID como novo conjunto de dados

Embora ainda haja muito a ser feito para anular a descriptografia dos dados.

Por exemplo, se "Tim" é conhecido como o nome mais popular para um garoto, a contagem de IDs com frequência que se aproxima da porcentagem conhecida de Tims na população pode denunciá-lo. A partir daí, você pode procurar nomes com uma distância de edição de 1 e concluir que esses IDs podem se referir a "Tom" ou "Jim" (quando combinados com outras informações).

Dave Challis
fonte
5

Não tenho muita certeza, mas talvez o hash sensível à localidade seja uma boa solução. Faz hash de dados de entrada (no seu caso - nomes), para que as strings originais sejam preservadas. Por outro lado, a idéia principal do LSH é maximizar a probabilidade de hashes para itens semelhantes. Existem muitas implementações diferentes de LSH. Tentei o Nilsimsa-hash para comparar textos de tuítes e funcionou muito bem. Mas não tenho certeza de quão bem ele funcionará no caso de cadeias curtas (nomes) - esse problema requer teste. Eu tentei seus exemplos, e aqui está o resultado (nome A, nome B, "distância" - o máximo é 120):

1. AMELIA BEDELIA  - CHRISTOPH BAUER - 107
2. AMELIA BEDELIA  - C J BAUER       - 82
3. AMELIA BEDELIA  - FRANZ HELLER    - 91
4. CHRISTOPH BAUER - C J BAUER       - 81
5. CHRISTOPH BAUER - FRANZ HELLER    - 98
6. C J BAUER       - FRANZ HELLER    - 83

Como você vê, CHRISTOPH BAUER e CJ BAUER apareceram para ser o par mais próximo. Mas a diferença não é significativa. E apenas por exemplo - representação hash desses nomes:

AMELIA BEDELIA  6b208299602b5000c3005a048122a43a828020889042240005011c1880864502
CHRISTOPH BAUER 22226448000ab10102e2860b52062487ff0000928e0822ee106028016cc01237
C J BAUER       2282204100961060048050004400240006032400148000802000a80130402002
FRANZ HELLER    58002002400880080b49172044020008030002442631e004009195020ad01158
sobach
fonte
3

Aqui está uma abordagem que não vi mencionada: separe o processo em duas etapas: a primeira etapa focada na codificação de nomes, para que versões alternativas com o mesmo nome sejam codificadas da mesma (ou quase a mesma) e a segunda etapa focada em tornar eles anônimos.

Para a primeira etapa, você pode usar um dos algoritmos fonéticos (Soundex e variantes) , aplicado ao nome, sobrenome e iniciais em várias ordens. (Veja este artigo também). É nesta etapa que você resolve semelhanças versus diferenças de nomes para equilibrar falsos positivos e falsos negativos.

Para a segunda etapa, você pode escolher qualquer método hash ou criptográfico que desejar, sem se preocupar com o modo como esse método afeta a correspondência de nomes. Isso lhe dá liberdade para usar um método que tenha as melhores características para desempenho, robustez e anonimato.

MrMeritology
fonte
Não acho que essa sugestão resolva o problema, conforme apresentado na pergunta. Onde está a flexibilidade pós-criptografia? Como refino sua análise sem acesso aos dados originais?
Air
@AirThomas Sinto muito, mas não entendo suas duas perguntas. O que você quer dizer com "flexibilidade pós-criptografia"? Não vi nada na sua pergunta / descrição assim. O que você quer dizer com "refine sua análise sem acesso aos dados originais"? Não vi nada sobre "refinar".
MrMeritology
1
Tentei identificar o problema no segundo parágrafo da seção Motivação . Imagine, por exemplo, que você queira liberar seu conjunto de dados para vários pesquisadores que desejam fazer alguma modelagem. Existem inúmeras metodologias inteligentes e eficazes que poderiam ser aplicadas, e cada pesquisador trabalha de maneira um pouco diferente. Você não pode divulgar os nomes de indivíduos particulares em seu conjunto de dados. Se você executar essa parte da análise antes de liberar os dados, isso força sua escolha de metodologia para todos.
Air
Se você fornecer adicionalmente hashes dos nomes, o benefício é que terceiros podem distinguir a identidade exata, mas não mais. Portanto, a pergunta é: como você pode fornecer mais informações sobre os dados que não pode liberar? Por exemplo, existe um método que preserva na saída de hash / criptografia a distância de edição entre entradas arbitrárias? Encontrei pelo menos um método que pelo menos se aproxima dessa funcionalidade (para obter mais informações, consulte minha própria resposta). Espero que isso torne as coisas mais claras.
Air