Anonymisation et modèle de classification

Comment anonymiser des données servant à effectuer une classification (binaire ou non) tout en gardant un modèle pertinent et efficace ?

La question de l’anonymisation des données a été introduite chez Blue DME dans un article précédent. Celui-ci introduisait la notion de facteur k pour l’anonymisation et la création de modèles à base d’arbres hiérarchiques. La notion de perte d’informations (IL= information loss) est très importante pour caractériser la destruction d’un jeu de données après anonymisation.

Nous avons vu que la perte d’information s’avère souvent élevée, lors d’une k-anonymisation. Ici, en utilisant des données servant à réaliser une classification, nous allons présenter une technique permettant de garder un modèle performant, c’est-à-dire répondant à la question ci-dessus qui sera le fil conducteur de l’article.

 

Méthodologie et plan 

 

La question introductive en gras constitue un cadre de réflexion important et explicite de ce que l’on veut faire. Il conviendra de toujours l’avoir à l’esprit durant la lecture de cet article.

Pas à pas, nous balayerons les concepts fondamentaux et mettrons en place une méthodologie et un algorithme robuste, efficace et automatisable pour traiter des problèmes d’anonymisation des données, basé sur un modèle d’arbre pour des données servant à de la classification.

La première partie sera consacrée à un rappel de la notion de rajout de bruit et de la façon de la réaliser avec des problèmes se présentant par rapport à la classification.  Ensuite, la deuxième partie permettra de raffiner nos rajouts de bruit, en utilisant des modèles à base d’arbre et nous permettra d’expliciter un algorithme d’anonymisation.

 

I. Rajout de bruit pour les valeurs numériques et catégorielles

 

I.1 Comment rajouter du bruit

Dans tous les cas, notre technique d’anonymisation, contrairement à l’article précédent, se basera sur des techniques d’ajouts de bruit, que ce soient sur des valeurs numériques ou catégorielles.

Nous disposons d’un dataset avec en colonnes des attributs numériques ou catégorielles et en lignes des valeurs permettant d’effectuer un apprentissage pour une classification sur une sortie (binaire ou non).

Pour rajouter du bruit sur les valeurs numérique, il suffit de simuler une loi gaussienne avec une variance à définir et une moyenne nulle et d’additionner les valeurs réelles avec les valeurs bruitées.

Pour chaque colonne on a donc une formule :

 

Nouvelle colonne = Colonne + ε,ε ∼ N(0,σ²) avec σ la variance

 

Pour déterminer la variance, on peut essayer de regarder la distribution de valeurs.

 

Pour rajouter du bruit dans les valeurs catégorielles, il suffit de monter d’un niveau dans les catégories en perdant de l’information. Par exemple, si nous disposons de 3 catégories possibles a, b et c dans une colonne, rajouter du bruit à une valeur a revient à transformer a en (a ou b) , ( a ou c) , (a)  ou ( a ou b ou c ).

 

 

I.2 Discussions

 

Même si globalement la structure des données se conserve en rajoutant du bruit intelligemment, les données servent généralement pour des modèles de scoring ou des modèles de clustering. Ainsi, en rajoutant du bruit, le modèle servant à une classification, par exemple, peut se retrouver totalement perturber par l’ajout de bruit.

 

Imaginons que nous disposons de données servant à effectuer une classification sur binaires pour prédire deux classes a et b. Nous disposons de 2 colonnes x et y pour cette  classification. Voici l’arbre de décision représentant le modèle de classification après apprentissage :

 

 

arbre

 

 

 

 

Prenons une distribution pour x de moyenne 2.2 et de variance 0.5. Nous voyons que si on choisit la valeur 2.2 pour x et 3.8 pour y, on se trouvera nécessairement dans la case a. En rajoutant un bruit qui respecte la distribution et qui n’est pas incohérent, on peut tout de même tomber sur la case b car on peut avoir x qui dépassera 2.202 et y qui dépassera 3.822.

Ainsi, le rajout de bruit peut tout de même détruire un modèle de classification. C’est pourquoi nous allons proposer une technique afin de pouvoir contourner ce problème.

 

II. Modèle à base d’arbres de décision

Dans cette partie, nous allons proposer une technique et un pseudo-code pouvant répondre à la question posée en introduction. L’idée présentée est plus détaillée dans l’article [1] qui donne également une fonction permettant de quantifier la perte d’information.

II.1 Une première proposition à base d’arbres de décision

Voici le pseudo-code proposé :

-Nous disposons d’un jeu de données servant à un modèle de classification binaire ou non.

-Avec ces données, nous allons créer un arbre de décision.

-Pour chaque ligne, nous allons donc rajouter du bruit en cohérence avec l’arbre de décision. Par exemple, en reprenant l’exemple précèdent avec x=2.2 et y=3.8, on peut retracer le parcours servant à placer notre ligne par rapport à la feuille donnant le résultat de la classification. Tout d’abord, comme x est inférieur à 2.202, on se trouve à gauche, donc notre bruit ne devra pas faire dépasser x de la valeur 2.202. Ensuite, x étant supérieur à 1.749, on va à droite. Ainsi, notre bruit devra maintenir x supérieur à 1.749. Puis, y est inférieur  à  4.517. Ainsi, notre bruit sur y devra respecter cette condition. Enfin, x est supérieur  à 2.058 pour se retrouver dans la bonne feuille, qui est une feuille avec la valeur b : le bruit devra respecter cela.

On en déduit donc pour la ligne avec les valeurs x=2.2 et y=3.8, que le bruit suivant devra faire en sorte que y soit inférieur à 4.517 et que x reste compris entre 2.058 et 2.202.

Pour chaque ligne, on disposera de règles différentes  pour l’ajour de bruit.

 

II.2 Pour aller plus loin…

Nous pouvons remarquer que définir pour chaque ligne des règles de bruit revient en fait à effectuer un partitionnement de l’espace des données par rapport aux règles de décision d’un arbre.

Ainsi, en reprenant toujours l’exemple avec les colonnes x et y, nous avons partitionné respectivement l’espace x et y de la manière suivante :

 

part1

 

On distingue 6 classes pour x.

 

part2

 

 

On distingue 5 classes pour y

Ces 2 partitions permettent donc de créer une seule partition pour nos données. On peut faire de même pour  des données combinant du numérique et du non-numérique (la représentation sera alors difficile).

Cette analyse nous permet donc d’aller plus loin et de définir un rajout de de bruit pour des modèles plus complexes qu’un simple arbre de décision, les random forests. Ici, il faudra donc définir des intersections de feuilles entre tous les arbres de notre forêt pour pouvoir définir des partitionnements de nos données et ainsi rajouter du bruit, tout en sauvegardant la pertinence de notre modèle.

 

CONCLUSION

 

Nous avons donc réussi à définir des méthodes d’anonymisation se basant sur des rajouts de bruit  (sur des valeurs numériques ou catégorielles ) plus efficaces qu’un rajout de bruit, prenant seulement en compte la structure des données. Cette fois-ci, nous prenons en compte un modèle d’arbres ou de random forest pour effectuer l’anonymisation. Cela présente l’avantage de conserver l’utilité des données dans le but d’une classification.

 

 

Sources:

[1] An anonymization technique using intersected decision trees

Sam Fletcher, Md Zahidul Islam

http://ac.els-cdn.com/S1319157815000452/1-s2.0-S1319157815000452-main.pdf?_tid=8761724e-816b-11e5-905f-00000aacb361&acdnat=1446473633_571901452adf3568072a19c56d37a906

 

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