Motivation

Je travaille avec des ensembles de données contenant des informations d'identification personnelle (PII) et ayant parfois besoin de partager une partie d'un ensemble de données avec des tiers, de manière à ne pas exposer les PII et ne pas engager la responsabilité de mon employeur. Notre approche habituelle consiste à retenir les données entièrement ou, dans certains cas, à en réduire la résolution; par exemple, remplacer une adresse exacte par le comté ou le secteur de recensement correspondant.

Cela signifie que certains types d'analyse et de traitement doivent être effectués en interne, même lorsqu'un tiers dispose de ressources et d'une expertise plus adaptées à la tâche. Étant donné que les données source ne sont pas divulguées, la manière dont nous procédons à cette analyse et à ce traitement manque de transparence. Par conséquent, la capacité de tout tiers à effectuer une AQ / CQ, à ajuster des paramètres ou à apporter des améliorations peut être très limitée.

Anonymisation des données confidentielles

L'une des tâches consiste à identifier les personnes par leur nom, dans les données soumises par l'utilisateur, tout en tenant compte des erreurs et des incohérences. Un particulier peut être enregistré à un endroit comme "Dave" et à un autre comme "David", les entités commerciales peuvent avoir de nombreuses abréviations différentes, et il y a toujours des fautes de frappe. J'ai développé des scripts en fonction d'un certain nombre de critères qui déterminent le moment où deux enregistrements portant des noms non identiques représentent le même individu et leur attribuent un ID commun.

À ce stade, nous pouvons rendre anonyme le jeu de données en retenant les noms et en les remplaçant par ce numéro d'identification personnel. Mais cela signifie que le destinataire n'a presque aucune information sur, par exemple, la force du match. Nous préférerions pouvoir transmettre le plus d’informations possible sans divulguer notre identité.

Ce qui ne marche pas

Par exemple, il serait intéressant de pouvoir chiffrer des chaînes tout en préservant la distance de montage. De cette manière, des tiers pourraient effectuer leur propre assurance qualité / contrôle de la qualité ou choisir de procéder eux-mêmes à un traitement ultérieur, sans jamais accéder à (ou être en mesure de procéder à une ingénierie inverse). Peut-être que nous faisons correspondre les chaînes en interne avec une distance d'édition <= 2 et que le destinataire souhaite examiner les implications du resserrement de cette tolérance pour une distance d'édition <= 1.

Mais la seule méthode que je connaisse pour cela est ROT13 (plus généralement, tout chiffre décalé ), qui compte à peine comme un chiffrement; c'est comme écrire les noms à l'envers et dire: "Promets-tu de ne pas retourner le papier?"

Une autre mauvaise solution serait de tout abréger. "Ellen Roberts" devient "ER" et ainsi de suite. C'est une mauvaise solution car, dans certains cas, les initiales, associées à des données publiques, révèlent l'identité d'une personne et, dans d'autres cas, elles sont trop ambiguës. "Benjamin Othello Ames" et "Bank of America" ​​porteront les mêmes initiales, mais leurs noms sont différents. Donc, il ne fait aucune des choses que nous voulons.

Une alternative inélégante consiste à introduire des champs supplémentaires pour suivre certains attributs du nom, par exemple:

+-----+----+-------------------+-----------+--------+
| 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    |
+-----+----+-------------------+-----------+--------+

J'appelle cela "inélégant" parce qu'il faut prévoir quelles qualités pourraient être intéressantes et que c'est relativement grossier. Si les noms sont supprimés, vous pouvez raisonnablement conclure quant à la force de la correspondance entre les lignes 2 et 3, ou à la distance entre les lignes 2 et 4 (c.-à-d. À quelle distance se trouve leur correspondance).

Conclusion

L'objectif est de transformer les chaînes de manière à préserver autant que possible les qualités utiles de la chaîne d'origine tout en obscurcissant la chaîne d'origine. Le déchiffrement devrait être impossible ou tellement peu pratique qu'il soit effectivement impossible, quelle que soit la taille de l'ensemble de données. En particulier, une méthode qui préserve la distance d'édition entre des chaînes arbitraires serait très utile.

J'ai trouvé quelques articles qui pourraient être pertinents, mais ils sont un peu au-dessus de ma tête:

• Protection de la confidentialité des comparaisons de chaînes basées sur la distance de Levenshtein
• Comparaison empirique d'approches pour la correspondance approximative de chaînes dans le couplage d'enregistrements privés

L'une des références que j'ai mentionnées dans le PO m'a conduit à une solution potentielle qui semble assez puissante, décrite dans " Couplage d' enregistrements préservant la confidentialité à l'aide de filtres de Bloom" ( doi: 10.1186 / 1472-6947-9-41 ):

Un nouveau protocole a été mis au point pour le couplage d’enregistrements préservant la confidentialité avec des identifiants chiffrés permettant des erreurs dans les identifiants. Le protocole est basé sur les filtres de Bloom sur q-grammes d'identifiants.

L'article décrit en détail la méthode, que je résumerai ici au mieux de mes capacités.

Un filtre de Bloom est une série de bits de longueur fixe stockant les résultats d'un ensemble fixe de fonctions de hachage indépendantes, chacune étant calculée sur la même valeur d'entrée. Le résultat de chaque fonction de hachage doit être une valeur d'index parmi les index possibles du filtre; Autrement dit, si vous avez une série de 10 bits indexée par 0, les fonctions de hachage doivent renvoyer (ou être mappées sur) des valeurs comprises entre 0 et 9.

Le filtre commence avec chaque bit défini sur 0. Après hachage de la valeur d'entrée avec chaque fonction de l'ensemble des fonctions de hachage, chaque bit correspondant à une valeur d'index renvoyée par une fonction de hachage est défini sur 1. Si le même index est renvoyé par qu'une fonction de hachage, le bit à cet index n'est défini qu'une fois. Vous pouvez considérer le filtre de Bloom comme une superposition de l'ensemble de hachages sur la plage de bits fixe.

Le protocole décrit dans l'article lié ci-dessus divise les chaînes en n-grammes, qui sont dans ce cas des ensembles de caractères. À titre d’exemple, vous "hello"pourriez obtenir l’ensemble de 2 grammes suivant:

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

Rembourrer le devant et le dos avec des espaces semble être généralement optionnel lors de la construction de n-grammes; les exemples donnés dans l'article qui propose cette méthode utilisent un tel remplissage.

Chaque n-gramme peut être haché pour produire un filtre de Bloom, et cet ensemble de filtres de Bloom peut être superposé sur lui-même (opération OU au niveau du bit) afin de produire le filtre de Bloom pour la chaîne.

Si le filtre contient beaucoup plus de bits qu'il n'y a de fonctions de hachage ou de n-grammes, il est relativement peu probable que des chaînes arbitraires produisent exactement le même filtre. Cependant, plus deux chaînes ont de points communs en n-grammes, plus le nombre de bits que leurs filtres partageront en fin de compte sera grand. Vous pouvez ensuite comparer deux filtres quelconques A, Bau moyen de leur coefficient de dés:

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

Où hest le nombre de bits définis à 1 dans les deux filtres, ale nombre de bits défini à 1 uniquement dans le filtre A et ble nombre de bits défini à 1 uniquement dans le filtre B. Si les chaînes sont exactement identiques, le coefficient de dés sera 1; plus ils diffèrent, plus le coefficient sera proche de 0.

Etant donné que les fonctions de hachage mappent un nombre indéterminé d'entrées uniques sur un petit nombre d'indices de bits possibles, différentes entrées peuvent produire le même filtre, de sorte que le coefficient n'indique qu'une probabilité que les chaînes soient identiques ou similaires. Le nombre de fonctions de hachage différentes et le nombre de bits dans le filtre sont des paramètres importants pour déterminer la probabilité de faux positifs - des paires d’entrées beaucoup moins similaires que le coefficient Dice produit par cette méthode.

J'ai trouvé ce tutoriel très utile pour comprendre le filtre de Bloom.

Il y a une certaine flexibilité dans la mise en œuvre de cette méthode; voir également ce document de 2010 (également lié à la fin de la question) pour des indications sur sa performance par rapport à d'autres méthodes et à divers paramètres.

À la moitié de la lecture de votre question, j'ai réalisé que Levenshtein Distance pouvait constituer une solution intéressante à votre problème. Il est bon de voir que vous avez un lien vers un document sur le sujet. Laissez-moi voir si je peux éclairer un peu à quoi une solution de Levenshtein ressemblerait.

La distance de Levenshtein est utilisée dans de nombreux secteurs pour la résolution d'entités, ce qui la rend utile est qu'elle permet de mesurer la différence entre deux séquences. Dans le cas de la comparaison de chaînes, il ne s'agit que de séquences de caractères.

Cela pourrait aider à résoudre votre problème en vous permettant de fournir un nombre qui donne une mesure de la similarité du texte d'un autre champ.

Voici un exemple d'utilisation de base de Levenshtein avec les données que vous avez fournies:

Ceci fournit une solution satisfaisante, la distance de 8 donne une indication de la relation et il est très conforme à la PII. Cependant, ce n’est toujours pas très utile, voyons ce qui se passera si nous faisons de la magie du texte pour ne prendre que la première initiale du prénom et le nom de famille complet sans rien insérer au milieu:

Comme vous pouvez le constater, la distance de Levenshtein égale à 0 indique bien une relation. Généralement, les fournisseurs de données combinent un ensemble de permutations de Levenshtein des noms et prénoms avec 1, 2, ou tous les caractères, pour donner une dimension dimensionnelle à la manière dont les entités sont liées tout en maintenant l'anonymat dans les données.

Si possible, je lierais des enregistrements associés (par exemple, Dave, David, etc.) et les remplacerais par un numéro de séquence (1, 2, 3, etc.) ou un hachage salé de la chaîne utilisée pour représenter tous les enregistrements associés ( par exemple, David au lieu de Dave).

Je suppose que les tiers n'ont pas besoin de savoir le nom réel, sinon vous pourriez aussi bien le leur donner.

modifier : Vous devez définir et justifier le type d'opérations que le tiers doit pouvoir effectuer. Par exemple, qu’est-ce qui ne va pas avec l’utilisation des initiales suivies d’un numéro (par exemple, BOA-1, BOA-2, etc.) pour lever l’ambiguïté de Bank of America de Benjamin Othello Ames? Si cela est trop révélateur, vous pouvez classer certaines des lettres ou des noms; par exemple, [AE] -> 1, [FJ] -> 2, etc., de sorte que BOA deviendrait 1OA, ou ["Bank", "Barry", "Bruce", etc.] -> 1, de sorte que Bank of America redevient 1OA.

Pour plus d'informations, voir k-anonymity .

Une option (en fonction de la taille de votre jeu de données) consiste simplement à fournir des distances de montage (ou d'autres mesures de similarité que vous utilisez) en tant que jeu de données supplémentaire.

Par exemple:

1. Générer un ensemble de noms uniques dans l'ensemble de données
2. Pour chaque nom, calculez la distance d'édition entre chaque nom.
3. Générer un identifiant ou un hachage irréversible pour chaque nom
4. Remplacer les noms dans le jeu de données d'origine par cet ID
5. Fournir une matrice de distances d'édition entre les numéros d'identification en tant que nouvel ensemble de données

Cependant, il reste encore beaucoup à faire pour désanonymiser les données de ces données.

Par exemple, si «Tim» est connu pour être le nom le plus populaire pour un garçon, le comptage fréquentiel des identifiants qui correspondent de près au pourcentage connu de Tims dans la population peut donner ce nom. À partir de là, vous pouvez rechercher des noms avec une distance d'édition de 1 et en conclure que ces identifiants peuvent faire référence à "Tom" ou à "Jim" (lorsqu'ils sont combinés avec d'autres informations).

Je ne suis pas tout à fait sûr, mais peut-être que le hachage sensible à la localité est une bonne solution. Il effectue le hachage des données d’entrée (dans votre cas - les noms), afin que les chaînes originales soient préservées. D'un autre côté, l'idée principale de LSH est de maximiser la probabilité de hachage pour des éléments similaires. Il y a beaucoup de différentes implémentations de LSH. J'ai essayé Nilsimsa-hash pour comparer des textes de tweet, et cela a très bien fonctionné. Mais je ne sais pas si cela fonctionnera bien en cas de chaînes courtes (noms) - ce problème nécessite des tests. J'ai essayé vos exemples et voici le résultat (nom A, nom B, "distance" - 120 au maximum):

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

Comme vous le voyez, CHRISTOPH BAUER et CJ BAUER se sont révélés être la paire la plus proche. Mais la différence n'est pas significative. Et juste par exemple - représentation hachée de ces noms:

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

Voici une approche que je n'ai pas vue mentionnée: séparez le processus en deux étapes: la première étape consiste à coder les noms afin que les versions alternatives du même nom soient codées de la même manière (ou presque), et la deuxième étape à la création les anonymes.

Pour la première étape, vous pouvez utiliser l’un des algorithmes phonétiques (Soundex et variantes) , appliqué au prénom, au nom de famille et aux initiales dans divers ordres. (Voir cet article aussi). C'est dans cette étape que vous résolvez les similitudes et les différences de noms pour équilibrer les faux positifs des faux négatifs.

Pour la deuxième étape, vous pouvez choisir n’importe quelle méthode de hachage ou de chiffrement, sans vous soucier de l’effet de cette méthode sur la correspondance des noms. Cela vous donne la liberté d'utiliser une méthode qui présente les meilleures caractéristiques en termes de performances, de robustesse et d'anonymat.