Anonymisation : démarche scientifique

Dans le cadre de sa R&D et en en tant que jeune entreprise innovante, Blue DME s’intéresse de près aux différentes techniques d’anonymisation des données afin de s’adapter aux recommandations de la CNIL ,Blue DME va plus loin en essayant d’anticiper et de s’adapter à des législations encore plus protectrices vis  à vis des individus,  de la collecte de leurs données et de la vie privée en générale. Dans ce nouvel article, il s’agit d’aller un peu plus loin dans les techniques d’anonymisation en présentant ce qui pourrait ressembler à une véritable anonymisation de facteur k au sens de la CNIL. Nous allons développer tous ces concepts dans cet article qui est une suite par rapport au précédent. J’ai été confronté à différentes problématiques comme le temps de calcul, la perte d’informations des données anonymiseés par rapport aux données initiales, le choix de la méthode d’anonymisation dont je vous livrerais mes principaux enseignements

 

Qu’est-ce qu’une anonymisation ?

 

Tout d’abord, Blue DME s’est intéressé au contexte juridique d’échange des données. Dans un article précédent [2], nous avons introduit des notions juridiques suite aux travaux de la commission européenne (article 29) et un cadre pour définir l’anonymisation des données.

Voici un petit rappel rapide :

Pour anonymiser les données, le groupe de travail GR29 préconise de se poser  3 grandes questions :

-L’individualisation : est-il toujours possible d’isoler un individu ?

-La corrélation : est-il possible de relier entre eux des ensembles de données distincts      concernant un même individu ?

-L’inférence : peut-on déduire de l’information sur un individu ?

[1]

Blue DME  manipule des données clients (lignes) avec leur comportement  (colonnes), par exemple une personne physique, avec son âge, son code postal et des données comportementales comme un montant de prêt, une durée de prêt,…etc.

Ainsi, Blue DME possède un premier niveau de sécurité qui utilise un algorithme de hashage, c’est une pseudonymisation des données. Cet algorithme a été présenté dans l’article précédent consacré à la sécurité des données. [2]

Le contexte dans lequel Blue DME opère (broker de données entre entreprises et non open-data) fait que les conditions de sécurité des données et les précautions prises pour empêcher de retrouver un individu à partir de certains de ses attributs sont moins restrictives que pour des données accessibles à n’importe qui.

Or, l’article précédent mentionnait bien le fait qu’une pseudonymisation n’est pas une anonymisation, en effet, même en masquant le nom et prénom, on peut retrouver un individu en connaissant son code postal, sa date de naissance et son sexe par exemple.  [2]

C’est pourquoi nous allons essayer d’avoir une anonymisation qui empêche l’individualisation d’une personne, on ne doit pas pouvoir l’isoler selon des critères qui permettent de l’identifier ultérieurement.

Les techniques d’anonymisation peuvent se découper globalement en deux groupes, les techniques de randomisation et les techniques de généralisation. Nous allons présenter ici ces différentes techniques.

Anonymisation : principe de base :

 

Ici, je vais faire une présentation rapide de l’anonymisation des données par généralisation. Concrètement, pour une combinaison d’identifiants bien choisis (difficulté du choix à priori), il faut que  chaque ligne ait une occurrence d’au moins à définir, nous en discuterons plus loin, c’est une technique basé sur le regroupement de lignes.

 

Exemple de regroupement de lignes :

 

On considère ici un tableau avec deux individus (en ligne, la ligne 1 représente l’individu 1 et la 2 l’individu 2, c’est la norme chez Blue DME de travailler sur des personnes physiques ou morales sur les lignes et leur comportement sur les colonnes).

Sur la colonne 1, on retrouve la donnée Homme (M comme masculin) ou Femme (F) comme attribut.

Sur la colonne 2, l’attribut est le code postal.

Sur la colonne 3, c’est la situation maritale (Marié, divorcé, veuf, etc.)

 

Exemple 1 :

 

BMP7

 

Les lignes possèdent des différences (petites comme 75005 et 75006 car les 2 individus  habitent Paris et grandes comme Marié et Divorcé) et des ressemblances (les deux individus sont des hommes). Ainsi, le regroupement de lignes consiste à créer une ligne commune à partir de ces lignes (on peut le faire pour 2,3 ou plus).

 

BMP6 

 

Ici, on voit que l’on a encore deux lignes qui ont les mêmes attributs, M pour la colonne 1, 75 pour la colonne 2 car on a regroupé les codes postaux en utilisant le fait que les deux personnes habitent Paris et Inconnu pour la colonne 3 car c’est la seule façon pour nous de regrouper Marié et Divorcé.

On peut remarquer que nos nouvelles données apportent des informations moins précises que nos données initiales mais par contre on ne peut plus distinguer les 2 personnes  en utilisant ces 3 attributs.

 

 

 

Techniques d’anonymisation : tests et discussions

 

J’ai tout d’abord regardé en détail les différentes méthodes d’anonymisation que propose le groupe de travail G29. Ici, je vais présenter rapidement quelques méthodes retenues dans ma démarche scientifique et détailler plus en détail la k-anonymisation qui est un sujet de recherche important de nos jours.

 

Les techniques d’anonymisation peuvent se découper globalement en deux groupes, les techniques de randomisation et les techniques de généralisation. Nous allons présenter ici ces différentes techniques.

 

 

  1. Randomisation :

 

La randomisation consiste à altérer les données pour affaiblir le lien entre un individu et les données.

Le rajout de bruit est un exemple de technique de randomisation. Pour les valeurs numériques, comme l’âge ou un prix, on peur rajouter un bruit à toutes les valeurs d’une même colonne dans un ensemble de données. Le bruit doit respecter la distribution numérique (pour cela regarder la densité de distribution avant et après rajout de bruit).

Ici, on va illustrer le rajout de bruit en utilisant un tableau avec en ligne les individus, sur la colonne 1, l’âge et sur la 3 un montant.

Les colonnes 2 et 4 représentent des données bruitées avec un bruit cohérent respectant la  distribution des âges et des montants.

 

Exemple 2 :

 

Sans titre

 

Nous pouvons utiliser aussi des techniques de permutation. Cette technique consiste, lorsque l’on dispose d’un tableau de données ou les lignes sont des individus et les colonnes des caractéristiques (sexe, argent, âge, etc.), à permuter certaines valeurs de lignes pour des colonnes prédéfinies. Typiquement, l’idée est donc de stocker ces données permutées puis avant de les traiter ou de les envoyer a quelqu’un, de les remettre à l’endroit.

 

  1. Généralisation :

La généralisation consiste à remplacer des valeurs d’attributs trop précis et permettant une identification par d’autres valeurs plus granulaires. Par exemple, on peut remplacer les codes postaux par des départements.

 

Pseudonymisation

 

La pseudonymisation est un exemple de technique de généralisation. Cette technique a été présentée en détail dans l’article précédent. Attention : Comme vu précédemment, une  pseudonymisation n’est pas une anonymisation !!!

 

K-anonymisation

 

Comme la pseudonymisation n’est pas toujours suffisante pour protéger l’identification d’un individu d’un assaillant potentiel, je me suis attardé sur les techniques de généralisation et plus particulièrement sur la k-anonymisation.

La k-anonymisation est un exemple de technique de généralisation. En choisissant une combinaison d’une ou plusieurs colonnes d’identifiants, on veut que chaque individu ne puisse être distingué  de k-1 autres individus. Concrètement, pour cette combinaison d’identifiants bien choisis (d’où la difficulté du choix à priori), chaque ligne ait une occurrence d’au moins k.

Sur l’exemple 1, nous avons un exemple de 2-anonymisation, on a regroupé des lignes en un paquet contenant au moins k (ici k=2) individus.

 

La l-diversité est un exemple de technique de généralisation. La l-diversité impose une contrainte supplémentaire par rapport à la K-anonymisation. En effet, si par exemple on considère, pour nos données k-anonymisées les valeurs d’un attribut d’une autre colonne, on peut parfois en déduire avec une grande probabilité ou avec certitude la valeur de cet attribut si la distribution de celui-ci a une faible volatilité.

 

 

La k-anonymisation permet donc de garder des données exactes mais avec une granularité différente et moins précise, ce qui peut être acceptable pour Blue DME si la perte d’information n’est pas trop importante lors du changement de granularité des données.

 

 Comment faire en pratique ?

 

Quelques notions mathématiques

Apres avoir regardé différents articles de recherche traitant de la k-anonymisation, j’ai remarqué que les notions étaient souvent assez intuitives comme vu sur l’exemple 1, mais que par contre, formaliser ces notions sur un algorithme avec un langage (R par exemple) est assez difficile, c’est pourquoi je vais introduire ici un formalisme mathématique à travers des notions de distance entre lignes, pour pouvoir justement implanter un algorithme  de k-anonymisation.

 

Calcul de distance entre deux lignes :

On considère un jeu de données possédant des variables à la fois numériques et catégorielles. La distance entre des données numériques est assez simple (c’est la distance entre deux nombres réels). Pour les données catégorielles, cela parait plus compliqué, en effet, si par exemple, dans nos données, nous avons une colonne indiquant un modèle de voiture (Renault, Peugeot, Mercedes,…etc.), il n’y a pas a priori de distances permettant de comparer une Renault et une Peugeot.

 

Il va donc falloir introduite une notion de distance catégorielle. La distance la plus simple à laquelle on peut penser est la distance de Hamming.

 

Définition de la distance de Hamming :

Si a=b alors d (a,b)=0 sinon d(a,b)=1

C’est bien une distance qui satisfait l’inégalité triangulaire et les autres propriétés habituelles donc cette distance est convenable.

La distance de Hamming permet de travailler facilement sur des variables catégorielles binaires (0 ou 1, marié ou non, masculin ou féminin).

Cependant, des lors que on dispose de beaucoup de données catégorielles, cette distance est moins efficace. En effet, si on prenant l’exemple d’une variable code postal, avec la distance de Hamming, en prenant comme code postal « 75005 », »75006 » et « 59000 »,

Les trois éléments étant distincts, la distance entre chacun d’entre eux vaut 1.

Or, intuitivement, il semble que la distance entre « 75005 » et »75006 » devrait être plus faible que la distance entre « 75005 » et « 59000 ».Pour structurer cette intuition, il suffit de représenter chacune nos sous forme d’un arbre hiérarchique.

 

 

Représentation à base d’arbres pour des distances catégorielles

 

On va représenter les distances et les interactions pour un même type (code postal, situation géographique) en utilisant des arbres hiérarchiques.

Par exemple, sur l’arbre hiérarchique suivant, on représente une situation géographique et on a  un modèle hiérarchique de généralisation, c’est-à-dire que si on veut regrouper l’Inde et le Japon, on prendra East, si on veut faire pareil pour Japon et Iran, alors on prendra Asie et entre le Canada et le Japon, on prendra Pays.

La distance va aussi suivre cette logique, la distance entre deux pays dépendra du nombre de  nœuds à parcourir pour passer au nœud père  des deux pays. Par exemple, on peut prendre ici pour distance entre USA et Canada, 1/3, entre USA et Brésil 2/3 et entre USA et Egypte 1.

 

BMP4

 

On décide que la distance maximum pour chaque attribut est de 1.

Pour le  1er attribut, on a les 2 mêmes valeurs, donc la distance est de 0 (modèle hiérarchique à2 niveaux avec des distances valant 0 ou 1)

Pour le  2eme attribut, on a le même  département, donc la distance est de 0.5, si on avait un département différent, on aurait eu une distance de 1 (modèle hiérarchique a 3 niveaux avec une distance de 0, ½ ou 1)

Pour le  3eme attribut, on a 2  valeurs différentes, donc la distance est de 1 (modèle hiérarchique à2 niveaux avec des distances valant 0 ou 1)

 

On peut aussi pour calculer une distance entre deux lignes, attribuer différents poids aux attributs, en considérant que la distance doit plus influer sur la distance que le sexe par exemple, il faut alors prendre conscience que tous nos algorithmes qui seront présentés après dépendent directement des valeurs des distances, donc prendre des poids différents donnera des valeurs différentes âpres anonymisation.

 

Principe général de l’anonymisation et de la k-anonymisation

 

Regroupement entre deux lignes : Le principe d’un regroupement entre deux lignes est la fusion d’attributs catégoriels selon un modèle d’arbre hiérarchique vu dans le paragraphe précédent. Ici, si on a un attribut Iran et un attribut Egypte, on fusionnera ces attributs en un seul en prenant le nœud père.

Comme une ligne et une collection d’attribut numériques ou catégorielles, pour fusionner des lignes on effectuer cela pour chaque attribut catégorielle et pour les numériques, on construit un intervalle, par exemple pour un attribut âge, la fusion de 20 et de 30 sera l’intervalle [20,30].

L’objectif global est donc pour l’anonymisation d’effectuer le moins de regroupement possibles avec le moins de pertes d’informations possibles pour obtenir des données répondant à nos critères.

Pour des critères de k-anonymisation, l’objectif est que suivant certaines colonnes, toutes les combinaisons possibles dans nos données possèdent u moins k-individus  pour assurer que l’on ne puisse pas isoler quelqu’un selon certains critères d’identification.

 

Comment implanter  une k-anonymisation

 

De nombreux algorithmes sont présentés sous la forme pseudo- code dans des articles de recherche. Apres avoir lu quelques articles sur ce sujet, j’ai pu en déduire une trame pour chaque algorithme proposé dans les articles.

 

L’idée principale est de définir un cadre mathématique en utilisant des notions de distance et d’effectuer à la fois les meilleurs regroupements de distance possibles et le plus petit nombre de regroupement possible pour minimiser la perte d’informations après anonymisation, c’est donc un problème de combinatoire.

Comme avec n lignes, le nombre de combinaisons possibles pour regrouper des lignes en de nouvelles lignes possédant au moins k occurrences est gigantesque, il faut faire des choix  et ne pas tester toutes les possibilités pour ensuite faire le meilleur regroupement.

Les personnes souhaitant aller plus loin dans la découverte d’algorithmes et de modèles pour l’anonymisation peuvent lire plusieurs articles, notamment :

 [3] https://epic.org/privacy/reidentification/Sweeney_Article.pdf

[4]  http://www.utdallas.edu/~muratk/courses/privacy08f_files/proj_files/Efficient%20k-Anonymization%20Using%20Clustering%20Techniques.pdf

 

Pseudocode général :

Ici, je fais une proposition de pseudo-code pour implémenter une k-anonymisation qui s’appuie notamment sur l’article scientifique : [5]

  1. Regrouper toutes les lignes identiques en classe

Si toutes les classes possèdent au moins k éléments, c’est bon sinon :

  1. Choisir la 1ere classe i possédant moins de k occurrence
  2. Calculer la distance entre cette classe et toutes les autres
  3. Choisir la classe j minimisant la distance avec la classe i
  4. Regrouper les classes i et j, puis recommencer le processus à 1 jusqu’à ce que les données soient anonymes avec un facteur k

 

Un code en R qui peut résumer tout cela :

 

On dispose d’un jeu de données que l’on nommera data (n lignes et m colonnes), après certaines transformations pour nettoyer la donnée, on utilise le code suivant avec des fonctions que l’on devra écrire mais dont on donne le sens ici seulement :

Ici, pour les besoins de l’écriture, on a gardé le même modèle qu’avant, c’est-à-dire 3 colonnes (sexe, situation maritale et code postal) pour les attributs, la 4eme colonne va représenter le nombre de lignes possédant ces attributs, le dataset possédant 4 colonnes sera classefr.

 

 

 

 

 

Boucle d’arret, si les regroupements ont une occurrence supérieure à k, on arrête.

while( min(classefr[,4])<k)

{

i=vecarret[1]

i représente à chaque itération la 1ere ligne devant être changé, ici on fait un choix en prenant la 1ere ligne qui apparait dans celles ne convenant pas pour la changer, ce choix ne garantit donc plus un regroupement optimal des lignes, mais c’est le plus rapide et le plus simple possible.

vecdist=1:nrow (classefr)

vecdist va représenter à chaque itération notre vecteur de distance entre la ligne i que l’on veut changer et les autres lignes

 

ote=ncol(classefr)

 

for( j in (1:nrow(classefr))[-i])

Dans cette boucle, on calcule pour toutes les lignes le parent entre i et j  et la distance entre i et j.

{

 

parent<-fusionligne(classefr[i,-ote],classefr[j,-ote])

vecdist[j]<-classefr[i,ote]*distligne(classefr[i,-ote],parent)+classefr[j,ote]*distligne(parent,classefr[j,-ote])

}

 

 

vecdist[i]<-1000000000000

 

indmin<-which(vecdist==min(vecdist))

Indice du minimum des distances avec la classe i, c’est donc les lignes i et indmin que l’on va regrouper ensemble.

 

 

if ( length(indmin)>1 )

 

{

 

indvec<-which(indmin %in% vecarret)

 

 

if (length(indvec) >0      )

 

{

 

indmin<-indmin[indvec][1]

 

}   else  {

 

 

indmin<-indmin[1]

 

}

 

 

}

 

indmin<-indmin[1]

 

parent<-fusionligne(classefr[i,-ote],classefr[indmin,-ote])

 

On crée la nouvelle classe fusionnée

 

 

classefr[i,-ote]<-parent

classefr[i,ote]<-classefr[i,ote]+classefr[indmin,ote]

 

classefr<-classefr[-indmin,]

 

On actualise en supprimant  les deux classes par la nouvelle fusionnée <

 

classefa<-as.data.table(classefr)

 

vecarret<-which(classefa[,N]<k)

q<-q+1

 

}

 

 

On a utilisé deux boucles for pour regrouper en classes toutes les lignes non convenables. C’est à cause de ces deux boucles la complexité annoncée au paragraphe suivant est grande puisqu’on parcourt deux fois notre tableau sur les lignes.

 

Résultats de l’algorithme :

Dans nos données initiales, on reprend les catégories précédentes de l’exemple 1, pour la 1ere colonne, le sexe, la 2eme la situation maritale (M=marié, C=célibataire …) et le code postal dans la 3eme colonne, la dernière colonne représente le nombre d’occurrences de cette ligne.

On travaille avec un k=2 ou 3, sur des données possédant 3 colonnes d’attributs, et avec 1000 lignes.

 

Voici un aperçu des résultats après une anonymisation de facteur k=3

On remarque que beaucoup de codes postaux ont été transformés en France, nous avions donc beaucoup de codes postaux avec une faible occurrence (par exemple 34017) tandis que d’autres comme à Paris avec une plus grande concentration de personnes ont mieux résisté à la perte d’information

 BMP2

Voici un aperçu des  résultats après une anonymisation de facteur k=2

On remarque que beaucoup d moins e codes postaux ont été transformés en France par rapport au résultat précèdent, ceci est logique car la contrainte k=2 est moins contraignante que k=3.

 BMP1

Algorithme et complexité

 

L’optimisation par facteur k est un problème NP-complet pour en trouver la meilleure optimisation  qui réduit au maximum la perte d’information.

En effet, comme on l’a vu précédemment, les algorithmes se basent toujours sur des choix de lignes ou de paquets de lignes à regrouper de manière itérative jusqu’à  arriver à des données anonymisées. Comme le nombre de possibilités  totales  de façon d’assembler des lignes est trop élevé pour tester toutes les possibilités et ne garder que la meilleure façon de faire, on fait alors des choix les plus pertinents possibles pour ne pas perdre trop d’informations.

 

Dans la pratique, on peut trouver des algorithmes avec une complexité en      ou en   O (n^2 /  k)  comme celui proposé dans le pseudo-code et code R précédent avec n le nombre de lignes dans le jeu de données et k le facteur d’anonymisation.

 

 

 

Choix de k

 

Comme il n’est pas mentionné ni dans l’article G29 ni ailleurs, une norme national ou international sur le choix de k pour protéger les données, je me suis posé la question sur l’influence de k et sur le choix à faire pour effectuer une anonymisation. Ici, j’introduis la notion de perte d’information (IL=information loss)

 

Un point important est le choix de k, on peut voir les données en sortie et en entrée après une k-anonymisation. On va donc pouvoir définir une nouvelle information, qui sera la distance entre nos nouvelles lignes et nos anciennes lignes. Plus cette distance, sera élevé, plus on aura perdu   d’information, c’est ce qu’on appelle couramment dans les articles  l’IL, information loss. Une idée serait alors de faire tourner l’algorithme  pour chaque k et ensuite  de choisir le k conduisant à la moindre perte d’information. Ainsi, nous pouvons choisir un k qui serait un mix entre une moindre perte d’information et une sécurité des données. C’est un peu la même idée qu’un compromis biais variance et que le choix de k dans un algorithme k-means.

 

Ci-dessous, nous allons tester les résultats de l’algorithme d’optimisation sur le logiciel R avec des données internes. Nous représentons la perte d’information entre les données initiales et les données anonymisées en fonction de k. Ici, k peut valoir 2, 3,4 ou 5. Plusieurs courbes ont été tracés avec pour chacune d’entre elles, un nombre différent de lignes, en effet logiquement l’intuition est que plus on aura de lignes au départ, moins on aura de données à changer car il y aura dès le début plus de redondance. On a travaillé avec 500, 700, 1000,2000 et 5000 lignes, pas plus pour des raisons de complexité algorithmique (voir paragraphe suivant)

 

 

 

Discussion autour des résultats :

 

Dans toutes les courbes, si on se concentre sur la perte d’information, on voit qu’il y en a assez peu  de différences que l’on choisisse k=4 ou k=5.

L’idée que je propose est tout d’abord de s’imposer une plage de k convenables, par exemple k=2 ne convient pas car il faut avoir des paquets plus gros pour bien protéger nos données car un attaquant à alors une chance sur deux d’identifier un individu. Ensuite, il faut se donner une plage de pertes d’informations acceptables (par exemple ne pas perdre plus  de 60% d’informations après anonymisation).

Le choix de k respectant les deux conditions précédentes, si il n’y a pas de k convenable (l’intersection de ces conditions est vide) alors il faut avoir des conditions plus souple.

Ici, par exemple une perte d’information inférieur à 0.7, on choisit naturellement k=3 pour l’anonymisation.

BMP

 

On a  remarqué que plus on a de lignes (d’individus importants), moins l’anonymisation comportera des pertes d’informations. La perte d’information est très dépendante du jeu de données, que ce soit le nombre de lignes, le choix de k, le nombre de possibilités dans chaque attribut catégoriel (attribut non numérique).

Package déjà existants

 

J’ai recherché l’existence d’algorithmes ou de package déjà implanté sur des langages de programmation, j’ai seulement trouvé un package sur R. Comme l’anonymisation dépend beaucoup des données (notamment le modèle de classification hiérarchique), il est difficile d’avoir un algorithme automatique déjà existant qui prend en entrée un jeu de données et rend en sortie des données anonymisées, ceci explique selon moi la non-existence de ces algorithmes

Les fonctions implantées sont par exemple :

addNoise qui comme son nom l’indique permet de rajouter du bruit à des valeurs numériques tout en respectant la distribution, la variance du bruit rajouté est choisi manuellement

freqCalc qui donne la fréquence d’observation de chaque échantillon considérant les variables choisies manuellement, cela permet d’identifier les variables à risque et d’avoir des mesures approprié.

localSuppr permet d’effectuer des suppressions pour atteindre une k-anonymisation

 

Ces fonctions peuvent être utiles pour tester a priori le niveau d’anonymisation d’un dataset, mais la fonction localSuppr est assez grossière puisqu’elles effacent toutes les lignes non convenables.

 

 

Difficultés et limites de l’algorithme :

 

Apres avoir implanté l’algorithme, ma première démarche a été de le tester et  de regarder sa complexité. La complexité  est en O (n^2), ce qui fait que le temps de calcul devient rapidement très grand au fur et à mesure que n augmente.

Lorsqu’on veut travailler avec des données de très grande taille, il parait difficilement convenable d’avoir des algorithmes avec une complexité pareille, j’ai donc essayé d’implanter et de proposer des nouvelles versions qui seront donc plus rapides mais en contrepartie, nous aurons une perte d’informations plus importante.

 

Pour aller plus loin

Utiliser les outils Big data :

 

Première possibilité : Mix entre calcul parallèle et itératif

La  première idée qui m’est venue à l’esprit est d’essayer de paralléliser au maximum les opérations puisqu’on va devoir travailler sur des données de grande taille (Big Data).La difficulté est que l’algorithme, est par nature itératif, il prend en effet à chaque itération la 1ere ligne qui ne convient pas  et la regroupe pour recréer une nouvelle situation.

 

Pour résoudre ce problème, une première chose à faire est de conserver le même algorithme itératif dans sa structure  tout en  parallélisant le calcul des distances entre les lignes avant de choisir celles avec la plus petite distance.

C’est une première approche qui permet de gagner du temps mais qui n’est pas suffisante car on trouve toujours des itérations, or l’idée principal des outils Big Data  est de paralléliser au maximum tous les calculs

 

Deuxième possibilité : Que du calcul parallèle !

Ici, j’ai voulu réaliser un algorithme (typiquement sur Spark) n’utilisant aucune itération, pour cela il faut donc choisir une seule et unique fois pour chaque ligne les autres lignes avec lesquelles on veut la regrouper, cela passer par un produit cartésien d’une ligne avec tous les autres et par des calculs de distance et de parent qui eux sont parallélisables.

 

On peut aussi trouver un algorithme moins précis mais qui exploite tous les avantages d’un langage Big Data comme Spark.

Une idée possible est d’utiliser un produit cartésien pour ainsi tester toutes les possibilités de distance entre chaque ligne, et de faire les regroupements adéquats ensuite grâce aux fonctions de Spark pour ensuite pour chaque ligne, renvoyer sa transformation en parent le plus proche grâce aux fonctions map et collect de Spark.

  1. Produit cartésien de nos données transformées en RDD avec elles-mêmes. Utilisation de RDD.cartesian(RDD)

 

  1. Utilisation de la fonction combineByKey de Spark qui va regrouper selon une clé, ici on va regrouper sur notre clé (une ligne) toutes les distances avec les autres pour ensuite choisir trouver le plus proche parent convenable qui soit présent au moins k fois pour respecter la k-anonymisation

 

Il n’y a qu’une seule itération avec cet algorithme mais en contrepartie, le regroupement choisi est moins bon que dans l’algorithme itératif mais il est par contre beaucoup plus rapide

 

 

Utiliser des algorithmes de machine learning :

 

Nous allons présenter succinctement un autre algorithme possible pour regrouper  nos donnes en paquets d’au moins k individus.

Avec la notion de distance introduite précédemment, on peut créer une matrice de dissimilarité  qui à la case (i,j) indique la distance entre i et j.

En R, la fonction daisy permet de  calculer une telle matrice de dissimilarité pour des données numériques et catégorielles (distance de Hamming seulement). L’idée est de rajouter une autre matrice de dissimilarité, pour les codes postaux par exemple, en tenant compte des modèles d’arbre hiérarchique. Ensuite, on peut faire une moyenne pondérer des matrices de dissimilarité.

Matrice<-daisy(data)

Cette matrice de dissimilarité une fois construite nous permet d’utiliser des méthodes de clustering assez classiques comme l’algorithme k-means, alors nous pouvons regrouper chaque ligne p dans un cluster d’une certaine taille q.

km<-kmeans (daisy,k=choix dans le k-means )

Si le cluster à une taille q supérieure ou égale à k, alors on peut regrouper ces lignes ensemble pour l’anonymisation, si ce n’est pas le cas, on agglomère le cluster à un autre ayant la distance la plus petite par rapport à notre cluster et on recommence jusqu’à  avoir des clusters de taille suffisante.

Cet algorithme permet une plus grande rapidité d’action car le regroupement des lignes pour trouver un parent se fait non plus en explorant toutes les possibilités de manière itérative mais elle se fait d’un seul coup en utilisant un algorithme de type k-means. On perd cependant en précision puisque le regroupement est moins bon que dans l’algorithme itératif. L’autre problème posé par cet algorithme est le calcul de la matrice de dissimilarité au début qui met du temps et doit être stocké en mémoire.

 

CONCLUSION

 

CONCLUSION TECHNIQUE

 

Un pseudo code et son implémentation dans le langage  R a été réalisé avec une discussion sur ses forces (meilleur algorithme pour avoir le moins de pertes d’informations possibles) et ses faiblesses (algorithme itératif avec une complexité polynomial de degré 2).

Pour quelqu’un voulant réaliser une anonymisation la plus efficace possible et possédant des contraintes fortes du type open-data, je recommande d’utiliser une anonymisation de facteur k pour les données catégorielles, pour cela il faut déjà avoir une modélisation en arbre hiérarchique. Cette modélisation sera différente selon le type de données et selon les valeurs des attributs. Pour les données numériques, des techniques de bruit peuvent être utilisées ou bien nous pouvons définir un modèle hiérarchique avec des intervalles pour des valeurs numériques (ex : regroupement de 10 et 20 avec l’intervalle [10,20])

Compte tenu de la complexité  de cet algorithme et des enjeux Big Data (manipulation de grandes bases de données), deux autres algorithmes ont été proposées et peuvent être implémentés, ces algorithmes peuvent toujours être améliorés et font l’objet de travaux de R&D chez Blue DME.

 

CONCLUSION GENERALE

 

Notre champ d’investigation se porte actuellement sur la recherche de solutions les plus pertinentes par rapport à un compromis pertes d’informations/temps de calcul  avec une mise en œuvre sur des données pouvant être très volumineuses.

 

Sources :

 

[1] Groupe de travail G29 WP216

http://ec.europa.eu/justice/data-protection/article-29/documentation/opinion-recommendation/files/2014/wp216_en.pdf

 

[2] Protection des données personnelles, anonymisation, sécurité des données

http://www.bluedme.com/protection-des-donnees-personnelles-anonymisation-securite-des-donnees/

 

 

[3] k-anonymity: a model for protecting privacy

Latanya sweeney

https://epic.org/privacy/reidentification/Sweeney_Article.pdf

 

 

[4]  Efficient k-Anonymization Using Clustering Techniques

Ji-Won Byun, Ashish Kamra, Elisa Bertino, and Ninghui Li

http://www.utdallas.edu/~muratk/courses/privacy08f_files/proj_files/Efficient%20k-Anonymization%20Using%20Clustering%20Techniques.pdf

 

[5] A Practical Approximation Algorithm for Optimal k-Anonymity

Batya Kenig · Tamir Tassa

http://www.openu.ac.il/Personal_sites/tamirtassa/Download/Journals/optimal_k_anon.pdf

 

 

Cette entrée a été publiée dans Blog. Sauvegarder le permalien.