Tout sur l’anonymat 4/4 : Anonymiser les données sans perdre d’information : le compromis confidentialité-utilité

Introduction

Cette série d’articles est inspirée du cours Privacy, Data Protection, Security, par Benjamin Nguyen, que j’ai suivi lors de l’école d’été Responsabilité des Algorithmes : enjeux sociétaux et environnementaux organisée par les groupes de recherche Recherche Opérationnelle et Intelligence Artificielle du CNRS.

Dans ce quatrième et dernier article, je parle du compromis confidentialité-utilité : plus un jeu de données est anonymisé, et moins on conserve d’information. On sait mesurer le degré d’anonymisation d’un jeu de données (par exemple le k du k-anonymat, ou le ɛ de la confidentialité différentielle, mais aussi la vulnérabilité statistique à différentes attaques) ; on voudrait donc avoir une mesure de l’utilité du jeu de données anonymisé, ou de la perte d’information engendrée par le processus d’anonymisation. Dans le premier cas, on souhaite maximiser la mesure, dans le second, la minimiser.

Mesures de généralisation

Ces mesures se basent sur le degré de généralisation dû à l’anonymisation : taille des classes obtenues, nombre de généralisations successives, nombre d’observations correspondant à une combinaison de valeurs…​

Degré de généralisation

Définition

La mesure la plus intuitive de la perte d’information, proposée par Latanya Sweeney en 2007 est probablement le degré de généralisation. Chaque attribut (chaque colonne) de notre jeu de données possède un domaine, c’est-à-dire l’ensemble des valeurs prises par cet attribut (puisque notre jeu de données est fini, ce domaine est fini). Une hiérarchie de généralisations d’un domaine est une suite de fonctions

telles que A_0 soit le domaine de l’attribut et A_n le domaine comprenant une seule valeur (la généralisation totale, où l’on supprime l’information liée à l’attribut). Cette hiérarchie implique un ordre sur l’ensemble des Aᵢ, où l’élément maximal est Aₙ et l’élément minimal et A₀. La hauteur de la hiérarchie est n, le nombre total de généralisations qu’elle contient. Plus le domaine d’une colonne comporte d’éléments, et plus les hiérarchies de généralisation de cette colonne peuvent être hautes.

On définit ainsi le degré de généralisation d’une colonne comme le nombre de généralisations successives effectuées dans la hiérarchie, et le degré de généralisation d’un jeu de données comme la somme des degrés de généralisation de ses colonnes. On peut ainsi choisir une généralisation minimale pour le degré d’anonymat souhaité, c’est-à-dire, une généralisation Aⱼ telle que toute généralisation Aₖ où k > i satisfasse aussi ce degré d’anonymat.

Exemple

On considère le tableau suivant, représentant les résultats d’un sondage sur les moyens de transport des Parisiens (note : le fait de se déplacer à vélo ou en trottinette n’est pas considéré comme une donnée personnelle, mais c’est pour l’exemple).

Le domaine de la première colonne est de taille 2. On a une hiérarchie de généralisation de hauteur 2 :

{Vélo, Trottinette} → {Véhicule à deux roues} → {*}

Où {*} représente la suppression totale de l’information contenue dans la colonne. Notons qu’au premier degré de généralisation, on sait quand même que la personne utilise un véhicule à deux roues pour se déplacer, donc la colonne nous donne quand même des informations (à la différence du deuxième niveau de généralisation, où on supprime toute l’information contenue dans la colonne).

Le domaine de la deuxième colonne est de taille 4 et a une hiérarchie de hauteur 3 :

{75001, 75002, 75013, 75018} → {7500*, 7501*} → {75***} → {*****}

Encore une fois, à l’avant-dernier niveau, on conserve l’information du département de résidence de la personne, alors qu’au dernier niveau on supprime entièrement cette information.

Si l’on souhaite rendre le jeu de données 2-anonyme, on peut par exemple procéder aux généralisations suivantes :

La deuxième option possède un degré de généralisation plus important que la première, on préférera donc la première option quand il s’agit d’anonymiser notre jeu de données.

Précision

Définition

Le principal défaut du degré de généralisation est qu’il ne prend pas en compte la taille du domaine non-anonymisé : supprimer un attribut qui ne possède que quelques valeurs (par exemple, le genre d’une personne) et généraliser d’un degré un attribut qui en possède plusieurs centaines (par exemple, passer du code postal au département) ont le même degré de généralisation, alors que la perte d’information n’est pas la même.

Sweeney introduit pour ça la mesure de précision. On commence par définir la distortion d’une colonne comme le rapport entre le degré de généralisation h d’un attribut (le “nombre de pas” dans la hiérarchie), et la hauteur totale H de la hiérarchie de généralisation qui lui est associée. Ainsi, si on généralise d’un degré une colonne dont le domaine contient peu d’éléments, la distortion sera plus importante que si l’on généralise une colonne dont le domaine contient beaucoup d’éléments.

La précision d’une généralisation est alors calculée à partir de la moyenne des distortions des colonnes d’un tableau :

où N est le nombre de colonnes du tableau, et pour chaque i = 1, …, N, hᵢ est le degré de généralisation de la colonne i, et Hᵢ la hauteur totale de la hiérarchie de généralisation.

Exemple

On généralise le tableau précédent afin de le rendre 2-anonyme :

Dans le premier cas, la distortion de la première colonne est de 1/2 (degré de généralisation 1 sur une hiérarchie de hauteur 2), et celui de la deuxième est 0. La distortion moyenne du tableau est donc de 1/4, et la précision de 0,75.

Dans le deuxième cas, la distortion de la première colonne est 0, et celle de la deuxième est de 1/3. La distortion moyenne est donc de 1/6, et la précision d’environ 0,83.

On préférera donc la deuxième option à la première.

Discernabilité

La discernabilité, proposée par Bayardo et Agrawal en 2005, pénalise chaque ligne du tableau en fonction du nombre de lignes équivalentes : on considère que deux lignes sont équivalentes lorsque leurs quasi-identifiants ont les mêmes valeurs ; une classe d’équivalence est un ensemble de toutes les lignes équivalentes. Dans un jeu de données k-anonyme, toutes les classes d’équivalence comprennent au moins k lignes.

Si une ligne est supprimée (par exemple, dans le cas d’un outlier dont la généralisation engendrerait une généralisation trop importante sur l’ensemble de la table) on considère que sa classe d’équivalence est l’ensemble du jeu de données.

On définit alors la discernabilité d’un jeu de données généralisé par

où la première somme porte sur les classes généralisées, et la deuxième somme porte sur les classes supprimées.

Une variante de cette mesure est celle de la taille moyenne d’une classe d’équivalence.

Théorie de l’information et entropie

La dernière catégorie de mesure est celle des mesures basées sur la théorie de l’information ; ces mesures cherchent à quantifier le niveau d’information contenu dans les données, en prenant en compte la distribution des différents attributs avant et après généralisation. On va essayer de maximiser cette information résiduelle (ou d’en minimiser la perte). La mesure présentée ci-dessous a été proposée par Aristides Gionis et Tamir Tassa en 2008.

Un exemple : la perte d’information

La notion principale utilisée dans ces mesures est celle d’entropie. En théorie de l’information, l’entropie quantifie l’incertitude sur les valeurs d’une variable aléatoire. Une variable très homogène (par exemple, l’âge des élèves d’une classe de CE2) possède peu d’entropie : mesurer cette variable nous donne peu d’informations. Une variable qui peut prendre des valeurs plus diverses (par exemple, l’âge de la population de tout un pays) contient plus d’informations.

L’entropie H d’une variable discrète X, pouvant prendre les valeurs x₁, x₂, … xₙ, est définie par

Le terme “- log Pr(X = xᵢ)” désigne l’information contenue dans l’évènement “X = xᵢ” : plus cet évènement est improbable, et plus -log Pr(X = xᵢ) sera élevé. L’entropie est obtenue en calculant l’espérance de ces termes : c’est l’information moyenne apportée par la variable X (notons qu’une variable ayant une seule valeur possible aura une entropie nulle).

Si A désigne les valeurs que peut prendre X et A’ est un sous-ensemble de A, on définit l’entropie conditionnelle de X sachant A’ par

C’est la même formule que ci-dessus avec des probabilités conditionnelles : on se restreint au cas où l’on sait que X est dans le sous-ensemble A’. Un sous-ensemble A’ ayant un seul élément correspondra à une entropie conditionnelle nulle. Au contraire, un sous-ensemble comportant beaucoup de valeurs possibles aura une entropie conditionnelle plus importante.

Supposons maintenant qu’on généralise l’ensemble des valeurs prises par une variable : par exemple, on passe de A = {1, 2, … 100} = {A₁, …, A₁₀₀} à A’ = {1–5, 6–10, 11–15… 96–100} = {A’₁, … A’₂₀}, . La perte d’information engendrée par cette généralisation de A se calcule alors comme suit

C’est l’espérance de l’entropie de la généralisation A’, prise sur tous ses éléments. Une généralisation “nulle”, où chaque A’ᵢ est un singleton contenant une valeur possible (c’est-à-dire que A’ = A), engendrera une perte d’information nulle. Une généralisation complète A’ = {*} représente une perte d’information maximale.

Conclusion : optimiser l’anonymat

Les différentes mesures présentées ci-dessus permettent de quantifier la perte d’information engendrée par une généralisation d’un jeu de données. L’anonymisation devient alors un problème d’optimisation : une fois k choisi, comment trouver la généralisation permettant de minimiser la perte d’informations ?

Selon la mesure choisie, il existe plusieurs algorithmes différents permettant d’effectuer cette optimisation, en temps polynomial voire logarithmique, preuve s’il en est que sa simplicité fait la force du k-anonymat.

Remerciement

Merci à nos collègues Alexandre DO et Lu WANG pour la revue de l’article.

A propos de l’auteur

Après un doctorat en mathématiques fondamentales, Béatrice CHETARD a rejoint La Javaness en tant que data scientist en mars 2021. Elle s’intéresse à tous les aspects de la data science (données structurées, NLP, computer vision), et tout particulièrement aux question d’éthique et de responsabilité des algorithmes.