7.1
Introduzione al capitolo
In questo capitolo proporremo brevemente un possibile sistema di Sanitiz- zazione per il modello inter-attributo. In particolare il sistema utilizza un ap- proccio che fa uso di tecniche di Generalizzazione degli attributi per bloccare le inferenze che permettono di individuare i pattern non k-anonimi.
7.2
Generalizzazione: Concetti base
Il concetto di Generalizzazione `e abbastanza semplice e intuitivo, ultima- mente `e stato utilizzato in molti algoritmi che seguono la linea del primo modello di data mining rispettoso della privacy gi`a discusso nel secondo capitolo.
L’idea di base consiste nel rimpiazzare il valore di un attributo con un altro meno specifico, ma che somiglia a quello originale. Con somiglia in par- ticolare ci riferiamo al fatto che il nuovo attributo contiene, parzialmente, la stessa informazione contenuta dall’attributo orginale ma, non l’identifica univocamente.
Questo rimpiazzo viene effettuato secondo una precisa gerarchia di valori, nota a priori.
Dalla letteratura[...], abbiamo che per ogni attributo esiste: 1. Un dominio della gerarchia di generalizzazione DGH
Che rappresenta come `e organizzata la gerarchia semantica degli at- tributi.
2. Un insieme di valori della gerarchia VGH
Che rappresenta l’insieme di tutti i possibili valori, che pu`o assumere un attributo, organizzati secondo una opportuna tassanomia.
Esempio concettuale
Senza entrare nello specifico consideriamo una tabella T e supponiamo di avere come attributo la regione di provenienza di ogni individuo di nazionalit`a italiana. Se ad esempio la Detection individua che tutti i canali d’inferenza sono correlati ai patterns che contengono l’attributo regione di provenienza si potrebbe pensare di generalizzare quest’ultimo. Una possibile gerarchia di generalizzazione `e quella mostrata in figura:
Figura 7.1: Tassonomia
Facendo un paragone con quanto detto fin ora e ci`o che `e stato discusso nei capitoli precedenti sulla Sanitization, sembrerebbe che ci siamo allontanati dalle metodologie utilizzate per ripulire i FI dalle possibile inferenze.
In realt`a concettualmente la generalizzazione di fondo unisce le tecniche di sanitizzazione additiva e sottrattiva.
Infatti quando un attributo viene generalizzato, dal punto di visto del suppor- to, si diminuisce il supporto di tutti quei pattern che contengono l’attributo in questione ma allo stesso modo si aumenta il supporto di tutti quei pattern che contengono l’attributo pi`u generico scelto per il rimpiazzo.
Possiamo cos`ı affermare che in sostanza ci ritroviamo con gli stessi proble- mi che avevamo prima. Anzi questa volta le difficolt`a sono maggiori poich`e bisogna trattare contemporaneamente due problemi. Inoltre il compito di individuare una possibile gerarchia per un attributo risulta esserre un proble- ma non banale che dipende da come `e strutturato il dominio di appartenenza dell’attributo DA.
Abbiamo visto che la k-anonymity `e un concetto che pu`o essere utilizzato in due contesti differenti. (A seconda del modello di protezione adottato. Il primo contesto riguarda problemi la cui natura consiste nel cercare le tuple il cui supporto `e minore di k mentre il secondo si riferisce a tutti i pattern il cui supporto `e minore di k.
Allo stesso modo la generalizzazione, indipendentemente dai due scenari, risulta essere un concetto sempre valido per implementare un qualsiasi mod- ello di protezione dei dati.
Soffermandoci sul fatto di come flessibili e quindi applicabili siano questi concetti. A seconda dei casi, non dovr`a sembrare strano se affermiamo che per sanitizzare i canali d’inferenza dovremo generalizzare pattern che possono avere supporto maggiore di k e che quindi non violano il principio di k- anonymity.
Ci`o dipende da come `e organizzata la gerarchia dei possibili valori che pu`o assumere un attributo.
Un possibile algoritmo potrebbe scandire tutti i pattern non k-anonimi trovati dall’algoritmo di Detection implementato nel nostro Tool e per ognuno di essi ricavare l’insieme degli item negati.
Una volta individuati tali item si potrebbe procedere con la fase di gen- eralizzazione che rimpiazza i suddetti item con un item pi`u generico nella gerarchia.
Se si vengono a creare in FI pi`u pattern identici si possono eliminare le ri- dondanze e incrementare il supporto dell’ unico pattern che li rappresenter`a.
Esempio applicativo
Dall’esempio 3 del capitolo quattro avevamo un canale d’inferenza (CM I , fIM)
= (Ca1,b,ca1,b,c,d1,d2, 1) esso era inferibile dai pattern: M = {a1 ∧ b ∧ c ∨ (d1 ∧
d2)} con supporto 46 e dal pattern I = {a1 ∧ b ∧ c1} con supporto 47.
Il Dominio di appartenenza DA(d) = {d1,d2,d3} `e abbastanza semplice quindi,
di conseguenza, avremo che DGH e VGH saranno in questo caso banali e in particolare avremo una solo un livello nella gerarchia.
Figura 7.2: Tassonomia
L’idea come detto, `e di generalizzare tutti gli item che compongono un canale di inferenza che compaiono con valore negato.
Nel nostro esempio generalizzeremo il pattern M. In realt`a M `e un pattern aggregato poich`e `e l’unione di K = {a1∧ b ∧ c ∧ d1} con ssupporto 19 e J =
{a1 ∧ b ∧ c ∧ d2} con suppporto pari a 27. Quindi dobbiamo generalizzare i
appartiene allo stesso DA avremmo che K e J rappresenterebbero lo stesso pattern.
1: K= {a1 ∧ b ∧ c ∧ d*} con supporto 19
2: J= {a1 ∧ b ∧ c ∧ d*} con supporto 27
Per quanto detto la generalizzazione equivale alla sanitizzazione additiva e sottrattiva. Quindi, dobbiamo eliminare dai FI i pattern K e J e aggiungerne un nuovo. Il nuovo pattern avr`a come item {a1∧ b ∧ c ∧ d*} e come supporto
la somma dei supporti.
Inoltre per rendere compatibile il nuovo pattern con l’insieme degli item- set σ frequenti FI bisogner`a generalizzare tutti i sub-pattern di K e J che contengono gli attributi d1 e d2.
Questa bozza di algoritmo, di fondo contiene molti problemi. Ad esem- pio risulta complicato la scelta del grado dell’albero di generalizzazione per scegliere un valore adatto per il rimpiazzo. Altre perplessit`a possiamo indi- viduarle dal punto di vista che si ha nella distorsione sui dati e nella possibilit`a di creare nuove inferenza.
Sicuramente, ulteriori studi potrebbero contribuire all scrittura di un algo- ritmo capace di eliminare le inferenze presenti in un database inter-attributo con l’obbiettivo di rendere completo il Tool di Detection proposto.