CAPITOLE AVANSATE DE BAZE DE DATE

CAPITOLE AVANSATE DE BAZE DE DATE

DATA PRIVACY.

K-ANONIMITY

Data privacy. K-anonymity

In prezent – informatia este cea mai importanta si solicitata resursa. O serie de institutii din sectorul guvernamental sau privat colecteaza

informatii. Aceste informatii sunt solicitate spre a fi mai departe cercetate (statisticieni, cercetatori, etc.) – in format electronic.

Intr-o prima faza, informatia era oferita direct in format statistic. In prezent, se solicita ca informatia sa fie oferita asa cum este stocata – microdata.

Avantajul de a oferi direct microdata in locul informatiilor statistice este flexibilitatea si disponibilitatea informatiei pentru utilizator.

O serie de institutii precum birouri de recensamant, agentii federale, centre de statistica in educatie, departamente pentru inregistrarea vehiculelor, organizatii de sanatate publica, asigurari, comerciale s.a. ofera spre vanzare sau cercetare microdata din bazele lor de date (baze de date statistice – vezi data mining).

In general, insa, aceste microdata contin in forma lor initiala (la posesor) informatie de identificare a subiectilor.


Se considera subiect ca fiind o persoana, un grup de persoane, o institutie, o organizatie... sau orice altceva despre care se retine informatie statistica.

In continuare se considera ca pentru un subiect exista o inregistrare.

Pentru a proteja identitatea subiectilor care au luat parte la studiu, datele care sunt oferite sunt prelucrate in primul rand prin eliminarea oricarei forme de identificare imediata (nume, SSN / CNP, adresa, numar de telefon s.a.).


Totusi, dupa eliminarea datelor de identificare, pot sa ramana informatii, aparent anonime, care sa identifice subiecti in mod unic sau aproape unic.

De exemplu: (data nasterii, sexul, codul postal) identifica unic 87% din populatia SUA.

Aceste date – sunt mari sanse sa fie gasite si in datele oferite de alte surse. Facand o legatura intre diferite seturi de date (microdata oferita fara informatie de identificare si baze de date publice), pe baza acestor informatii oferite, se poate determina subiectul sau un grup restrans de subiecti carora sa le fie asociata o informatie care se considera ca fiind confidentiala.

De exemplu: o serie de institutii de stat din SUA (cel putin) fac publice liste care contin informatii de identificare (nu imediata), informatii demografice, liste de vot, preferinte politice, vehicule, etc. – informatii care pot fi folosite in stabilirea de legaturi.


Figura 1. Se identifica datele persoanei marcate cu .


Figura 2.


Conform exemplului din figura 1. si figura 2., se constata nevoia de a altera chiar si o parte din datele oferite (nu este suficienta eliminarea informatiei de identificare directa).

Observatie: Securizarea datelor nu este o metoda de protectie a datelor private (privacy protection) (securitatea calculatoarelor, criptare, etc.).

Scopul anonimizarii / data privacy nu este de a ascunde toate datele, este de a publica date astfel incat sa nu se publice si date confidentiale

subiectilor, sau sa nu se poata deduce asemenea date (dezvaluire, divulgare) – prin stabilirea de legaturi cu alte surse.

Metode de alterare a datelor: interschimbarea datelor (intre subiecti diferiti) sau adaugarea de „zgomot”,

astfel incat, per ansamblu, datele statistice sa nu fie afectate; insa, in aceasta situatie, veridicitatea datelor este afectata, si poate conduce la rezultate diferite pe anumite interogari (de exemplu: pentru diferite criterii de grupare – distributia (sex, varsta) a persoanelor care cumpara anumite produse);

generalizare si suprimare / eliminare.

K-anonymity – metoda de protejare a datelor private

Se considera: Exista un tabel cu datele originale, care contine informatii de identificare,

informatii confidentiale, plus alte informatii, numit tabel privat (PT). Acest tabel trebuie anonimizat.

Primul pas = eliminarea datelor de identificare directa. Se considera mai departe ca PT contine mai departe doar informatii care le exclud pe cele de identificare directa.

Se considera ca PT = structura relationala: tabel T (A1, . . . ,An) un tuplu t T , t[Ai, . . . ,Aj], o multime de atribute {Ai, . . . ,Aj}

{A1, . . . ,An}, reprezinta secventa de valori pentru atributele Ai, . . . ,Aj in t T [Ai, . . . ,Aj ] = proiectia, cu pastrarea tuplelor duplicat, asupra atributelor Ai,

. . . , Aj in T |T| = cardinalitatea lui T


Se numeste cvasi-identificator un set de atribute din PT care pot fi legate cu informatie externa (coloane dintr-un set extern de date) pentru a re-identifica subiecti ai caror informatie refera.

Fie PD – persoana destinatar – cea care primeste microdata, si cea care dispune de alte seturi de date.

In functie de seturile de date accesibile PD, se pot determina mai multi cvasi-identificatori.

In continuare se considera ca exista un cvasi-identificator stabilit conform unui set extern.

Pentru protejarea datelor private, se considera ca fiind o masura suficienta asigurarea anonimitatii de nivel k (k-anonymity).


Se spune ca un set de date ofera k-anonimitate daca orice tuplu din rezultat nu poate fi corelat cu mai putin de k subiecti, k intreg pozitiv. K este posibil sa fie stabilit prin intelegere intre subiecti si posesorul datelor initiale.

Cerinta de k-anonimitate Fiecare set de date publicat trebuie sa satisfaca cerinta ca fiecare

combinatie de valori ale cvasi-id-ului sa corespunda pentru cel putin k subiecti (fiecare combinatie de valori sa apara de cel putin k ori in setul de date publicat).

k-anonimitate Fie T(A1, ..., An) un tabel si QI un cvasi-id al lui T. T satisface conditia

de k-anonimitate in functie de QI ddaca fiecare secventa de valori ale T[QI] apare de cel putin k ori in T[QI].


Observatie: Cerinta de k-anonimitate nu discuta (deocamdata) repetarile valorilor atributelor care nu fac parte dintr-un cvasi-id.

De exemplu: daca se respecta cerinta de k-anonimitate si toate tuplele care au aceeasi combinatie de valori pentru cvasi-id au aceeasi valoare pentru un alt atribut, dezvaluirea acelui atribut este clara (toti subiectii din grupul de cel putin k – se stie ca au acea proprietate).

Observatie: k-anonimizare cf. QI => exista cel putin k indivizi care sa se potriveasca unei secvente de valori in realitate (mari sanse sa fie mai multi de k indivizi, avand in vedere ca in general un studiu se efectueaza pe o parte a populatiei).

Observatie: Nici un subset al QI nu compromite conditia de k-anonimitate.

Observatie: Este posibil ca fiecarui atribut din QI sa-i fie asociata o pondere / prioritate – ca grad de anonimizare.

Generalizarea datelor. Relatii de generalizare

Fiecare atribut al unui tabel T are asociat un domeniu de valori – se va numi domeniu de baza.

Generalizarea unui atribut = inlocuirea valorilor originale (care apartin domeniului de baza) cu valori mai generale, dar care includ si valorile originale.

Exemplu: Data_nasterii: 12 ian 1995 -> ian 1995 -> 1995 Adresa: Plopilor, 20, Cluj-Napoca, Cluj, RO -> Plopilor, Cluj-Napoca, Cluj, RO

-> Cluj-Napoca, Cluj, RO -> Cluj, RO -> RO

Astfel, se stabileste o multime de domenii de generalizare care contin valori generalizate, si o relatie de asociere a unui domeniu cu domeniile care-l generalizeaza, pentru a face posibil procesul de generalizare.


Asocierea se efectueaza stabilind o relatie de ordine partiala ≤D (relatie de generalizare) – relatie de ordine partiala peste Dom (multimea tuturor domeniilor posibile).

Fie Di si Dj. Di ≤D Dj daca valorile domeniului Dj sunt generalizare a valorilor din domeniul Di.

Relatia de generalizare indeplineste conditiile: oricare Di, Dj, Dz Dom, Di ≤D Dj, Di ≤D Dz => Dj ≤D Dz sau Dz ≤D Dj (relatia

este de ordine totala peste multimea domeniilor de generalizare a unui domeniu de baza).

exista un singur element (domeniu) maximal pentru un proces de generalizare al unui atribut (un domeniu maximal contine o singura valoare; nu se poate generaliza mai mult).

Pentru fiecare domeniu (de baza) D se stabileste astfel, prin relatia de generalizare, o ierarhie de generalizare a domeniilor (DGHD).


O relatie de generalizare a valorilor este o relatie de ordine partiala ≤V care asociaza unei valori din domeniul Di o valoare unica din domeniul Dj, unde Dj este o generalizare directa a Di.

Relatia de generalizare a domeniilor implica, pentru fiecare domeniu D, existenta unei ierarhii de generalizare a valorilor VGHD.

Pentru oricare VGHD, nodurile terminale contin valori din D, iar nodul radacina contine valoarea (unica) din domeniul maximal din DGHD.

Observatie: Ierarhia de generalizare a domeniilor = lista; ierarhia de generalizare a valorilor = arbore.


Figura 3. Exemple DGH, VGH:


Exemple DGH, VGH:


Fie un tuplu t peste atributele (A1, ..., An) cu domeniul DT = (D1, ..., Dn), unde Di Dom, i:=1..n (Di = domeniile de baza).

Se defineste DGHDT = DGHD1 DGHD2 ... DGHDn. DGHDT este definita de o latice (latice de generalizare)

unde DT este elementul minimal, iar elementul maximal al laticii contine domeniul maximal al fiecarui DGHDi, i:=1..n.

Fiecare cale de la elementul minimal la elementul maximal, nodurile si relatiile de generalizare constituie o strategie de generalizare pentru DGHDT (mod prin care se poate generaliza tuplul).

Vezi figura 4. Figura 4.

Tabel generalizat si generalizare minimala

Fie PT.

Un prim pas in asigurarea k-anonimitatii pentru PT este generalizarea (care scade numarul de tuple distincte – pentru QI).

In general, se aplica generalizarea la nivel de atribut (toate valorile dintr-un atribut vor apartine aceluiasi domeniu de generalizare dupa efectuarea substitutiilor).

Fie dom(Ai, T) – domeniul atributului Ai in tabelul T.


Tabel generalizat

Fie Ti(A1, ..., An) si Tj(A1, ..., An) – tabele definite pe acelasi set de atribute. Tj este generalizare a lui Ti, Ti Tj, ddaca: |Ti| = |Tj|. Az {A1, ..., An}, dom(Az, Ti) ≤D dom(Az, Tj). se poate stabili o asociere bijectiva intre ti Ti si tj Tj a.i. ti[Az] ≤V tj[Az]

Pentru acelasi PT pot sa existe mai multe GT care sa ofere k-anonimitate. Caz extrem – cel mai generalizat tabel (domeniu maximal pentru fiecare atribut) => Se pierde din utilitatea datelor!!! => Se doreste generalizare minimala => k trebuie sa asigure o anonimizare destul de buna, plus sa se pastreze

utilitatea datelor


Figura 5. PT si tabele generalizate GT[1,0] (k:=1..3), GT[1,1] (k:=1..6), GT[0,1] (k:=1..2), GT[0,2] (k:=1..4), GT[1,2] (k:=1..12).


Vector distanta (dintre doua tabele)

Fie Ti(A1, ..., An), Tj(A1, ..., An), a.i. Ti Tj (Tj este generalizare a lui Ti). Vectorul distanta de la Ti la Tj este vectorul DVij = [d1, ..., dn], unde dz =

lungimea caii din DGHDz de la dom(Az, Ti) la dom(Az, Tj), z:=1..n.

DV ≤ DV’, DV = [d1, ..., dn], DV’ = [d1’, ..., dn’], ddaca dz ≤ dz’, z:=1..n. DV < DV’ ddaca DV ≤ DV’ si DV <> DV’.

Numarul generalizarilor (la nivel de atribut) pentru T(A1, ..., An) (|DGHDz| = inaltimea ierahiei DGHDz (numarul de arce din ierarhie)):

Exemplu (figura 6): |DGHR| = 1, |DGHZ| = 2


Figura 6. vectorii distanta sunt [1,0], [0,1], [1,1], [0,2], [1,2]; numarul generalizarilor = 2 X 3 = 6


Generalizarea k-minimala

Fie Ti(A1, ..., An), Tj(A1, ..., An), a.i. Ti Tj. Tj este generalizarea k-minimala a lui Ti ddaca: Tj satisface k-anonimitatea. Tz a.i. Ti Tz, Tz satisface k-anonimitatea => (DViz ≤ DVij).

Observatii: A doua conditie spune ca daca exista o alta generalizare Tz a lui Ti, atunci

vectorul distanta de la Ti la Tz nu este mai mic decat vectorul distanta de la Ti la Tj.

exemple - [0,1] [1,1], [0,1] [0,2], intre [1,0] si [0,2] nu se poate stabili o relatie de ordine.

Pot sa existe mai mult de o generalizare k-minimala. Daca Ti satisface k-anonimitatea, atunci Ti este generalizarea k-minimala a lui Ti.

Exemplu: figura 5: k = 2 – gen k-minimala: GT[1,0] si GT[0,1], k = 3 – gen k-minimala: GT[1,0] si GT[0,2].


Figura 5. PT si tabele generalizate GT[1,0] (k:=1..3), GT[1,1] (k:=1..6), GT[0,1] (k:=1..2), GT[0,2] (k:=1..4), GT[1,2] (k:=1..12).

Suprimarea / eliminarea datelor

Suprimarea poate fi folosita ca metoda de sine statatoare in anonimizarea datelor, sau ca metoda complementara generalizarii.

Se presupune (deocamdata) ca se aplica suprimarea la nivel de tuplu (nu se elimina doar unele valori dintr-un tuplu, ci intreg tuplul).

Situatie: fie PT si GT generalizare a lui PT. Este posibil ca GT sa fie de un nivel inalt de generalizare (posibil

chiar maximal pe unele atribute) din cauza catorva tuple. Atunci se prefera eliminarea din rezultat a acestor tuple si aplicarea

unui nivel de generalizare mai scazut. Vezi figura 7, 8, 9.


Figura 7.


Figura 8. GT k-minimale pt PT (k = 2)


Figura 9. PT fara t11 si GT k-minimal (k = 2)


Tabel generalizat – cu suprimare

Fie Ti(A1, ..., An), Tj(A1, ..., An), Ti Tj, Tj generalizare (cu suprimare) a lui Ti ddaca: |Ti| |Tj|. Az {A1, ..., An}, dom(Az, Ti) D dom(Az, Tj). se poate defini o relatie intre tuplele ti Ti si tj Tj a.i. oricarui tj ii

corespunde un ti, unde ti[Az] V tj[Az], z:=1..n. (tuplele ti care nu au corespondent tj sunt cele eliminate din rezultat)

Se stabileste o limita maxima in suprimarea tuplelor: MaxSup O generalizare Tj asigura suprimarea minima daca nu exista o alta generalizare

Tz, cu vector de distanta mai mic decat vect. dist. Tj, care sa suprime mai putine tuple. (exemplu: GT[1,0], GT[0,2], figura 10)

Generalizare vs. Suprimare


Figura 10. PT, GT. Sunt marcate tuplele care trebuie eliminate pentru a fi indeplinita k-anonimitatea, k=2. Daca s-ar elimina alte tuple, nu s-ar respecta k-anonimitatea, iar eliminarea unui super-set al tuplelor marcate – ar fi prea mult si nu necesar.

Generalizare & Suprimare

Generalizare k-minimala cu suprimare

Fie Ti(A1, ..., An), Tj(A1, ..., An), Ti Tj, MaxSup, Tj generalizare k-minimala (cu suprimare) a lui Ti ddaca: Tj – generalizare k-minimala |Ti| - |Tj| MaxSup

Exemplu: pentru figura 10: MaxSup = 0: GT[1,1] (GT[0,0], GT[1,0], GT[0,1], si GT[0,2] elimina mai multe

tuple decat este permis, GT[1,2] nu este minimal din cauza lui GT[1,1]); MaxSup = 1: GT[1,0] si GT[0,2] (GT[0,0] si GT[0,1] elimina mai multe tuple

decat este permis, GT[1,1] nu este minimal din cauza lui GT[1,0], iar GT[1,2] nu este minimal din cauza lui GT[1,0] si GT[0,2]);

MaxSup = 2, 3: GT[1,0] si GT[0,1] (GT[0,0] elimina mai multe tuple decat este permis, GT[0,2] nu este minimal din cauza lui GT[0,1], GT[1,1] si GT[1,2] nu sunt minimale din cauza lui GT[1,0] si GT[0,1]).

MaxSup ≥ 4: GT[0,0] (toate celelalte generalizari nu sunt minimale din cauza lui GT[0,0]).


Fie PT[QI] = T(A1, ..., An), si DGHDT. Algoritmul (Find_vector) determina generalizarea k-minimala cautand printre

toate generalizarile posibile. Totusi, numarul drumurilor de la domeniul de baza la domeniul maximal, pentru un domeniu de tuplu DT = (D1, ..., Dn) este:

unde hi este inaltimea ierarhiei DGHDz, z:=1..n (numarul de arce din ierarhie). Exemplu: R0-R1, Z0-Z1-Z2 => (1 + 2)! / (1! * 2!) = 3

Inaltimea unui vector de distanta DV in laticea vectorilor de distanta VL, VL = (DV, <=): height([d1, ..., dn], VL) = d1 + ... + dn.

Algoritmul Find_vector se bazeaza pe ideea ca – daca pentru o inaltime h nu exista nici un vector pentru care generalizarea nu satisface conditiile de generalizare k-minimala cu suprimare, atunci sigur nu exista un asemenea vector de inaltime mai mica.

!...!

)!...(

1

1

n

n

hh

hh


Exemplu – laticea de generalizare din figura 6. Numarul drumurilor posibile de la (R0, Z0) la (R1, Z2) este 3 Inaltimile vectorilor distanta – vezi figura dreapta

height([1,2], VL) = 3

height([1,1], VL) = 2height([0,2], VL) = 2

height([1,0], VL) = 1height([0,1], VL) = 1

height([0,0], VL) = 0

Generalizare & Suprimare.Algoritm Find_vector (binar)

Input: tabel T = PT[QI] care sa fie generalizat, k, MaxSup, VLDT corespunzatoare DGHDT, unde DT este domeniul tuplului pentru QI, Em este elementul maximal din VL.

Output: vectorul de distanta sol al tabelului de generalizare GTsol, care este generalizare k-minimala cu suprimare pentru T.

low:=0; high:=height(Em, VLDT); sol:=Em;Cattimp low<high

try:=inf((low + high / 2));vectors:={vec | height(vec, VLDT)=try};reach_k:=false;Cattimp vectors<> si reach_k=false

Selecteaza un vector vec din vectors, vectors:=vectors – {vec}Daca satisfies(vec, k, T, MaxSup) atunci

sol:=vec;reach_k:=true;

Sf. daca.Sf. cattimp.Daca reach_k=true

atunci high:=try;altfel low:=try;

Sf. daca.Sf. cattimp.Return sol;


Rezultatul functiei satisfies se poate determina simplu prin calcularea GT(vec) si testarea tuturor conditiilor necesare (k-anonimitatea si suprimarea MaxSup).

Figura 11. Distanta intre valori intr-o ierarhie de generalizare a valorilor.


Un alt mod de calcul, pe baza vectorilor de distanta dintre tuple.

Fie doua tuple x = (v1, ..., vn), y = (v1’, ..., vn’) din tabelul T. Vectorul distanta dintre x si y este vectorul Vx,y = [d1, ..., dn], unde di

este lungimea caii de generalizare de la vi si vi’ (vi si vi’ fac parte din acelasi Di) la cel mai apropiat parinte in ierarhia de generalizare a valorilor, VGHDi.

Folosind vectorii de distanta dintre tuplele unui tabel T se poate determina daca pentru un anumit vector de distanta (pentru generalizare) se poate obtine k-anonimitate, cu eliminare de mai putin de MaxSup inregistrari.


Se construieste o matrice VT astfel: Se adauga cate o linie pentru fiecare tuplu (distinct) x din T,

care apare de mai putin de k ori in T (count(x, T) < k). Se adauga cate o coloana pentru fiecare tuplu distinct din tabel. VT[x,y] = Vx,y contine vectorul de distanta dintre tuplele x si y

(matrice simetrica fata de diagonala principala).


Fie un vector vec, selectat la un moment dat de algoritmul Find_vector pentru care trebuie sa se testeze functia satisfies (vectorul distanta al unei generalizari – potentiala solutie).

Pentru fiecare linie x din VT se calculeaza sum(count(y, T)) pentru y a.i. VT[x,y] <= vec, unde sum(count(y, T)) ne da numarul de inregistrari care ar deveni egale cu x daca s-ar aplica generalizarea vec (numarul de elemente din cluster-ul din care va face parte x).

Numarul inregistrarilor care ar trebui eliminate din T la aplicarea generalizarii vec este data de elim = sum(count(x, T)) pentru care sum(count(y, T)) < k.

Daca elim <= MaxSup, atunci conditia de eliminare este indeplinita, iar vec este o posibila solutie. Altfel, nu este solutie acceptabila.


Figura 12. Vectorii de distanta intre tuplele tabelului PT din figura 7.


Figura 13. k-anonymity, k = 2, MaxSup = 1 sau 0, pentru figura 12.

Corectat: vec = [0,2,1,2,2]

Alterarea minimala a unui tabel

Daca exista mai multe generalizari k-minimale pentru PT, se pune problema sa se aleaga generalizarea care altereaza cat mai putin datele.

Pentru aceasta se poate defini o metrica care ajuta la calculul nivelului de alterare a datelor dintr-un tabel generalizat.

Pentru o celula a tabelului, T, Az, nivelul de alterare = nivel dom(Az, T) / inaltime DGHDz.

Exemplu: nivel 0, nivel 1, nivel 2, inaltime 2: pentru valorile care nu sunt generalizate = 0 / 2, pentru valori de pe nivelul 1 de generalizare = 1 / 2, pentru valorile care apartin domeniului maximal de generalizare = 2 / 2 (alterare maxima).

Fie PT si GT o generalizare a lui PT(A1, ..., An), cu DGHDz, z:=1..n.

nPT

DGH

h

GTprec

n

z

PT

j Dz

1 1

1)(


Observatie: Daca Ti si Tj a.i. Ti Tj, Tj asigura k-anonimitatea si Tj este generalizarea cu alterare minima, atunci Tj este generalizare k-minimala.


Figura 14 (a). DGH


Figura 14 (b). Generalizari. prec(GT[1,0]) = 0.5, prec(GT[1,1]) = 0.25, prec(GT[0,2]) = 0.5, prec(GT[0,1]) = 0.75, unde fiecare GT asigura k-anonimitatea pentru k=2 => GT[0,1] (h(DGH1) = 1, h(DGH2) = 2)

Alg. de determinare a gen. k-minimale cu alterare min. (MinGen)

Input: PT, QI(A1, ..., An), conditia de k-anonimitate, k <= |PT|, DGHDz, z:=1..n

Output: MGT (min GT)

Daca PT[QI] satisface conditia de k-anonimitate atunci MGT := PT;altfel

allgen := {GTi | GTi – generalizare a lui PT};protected := {GTi | GTi allgen si GTi satisface k-anonimitatea};MGT := {GTi | prec(GTi) = max{prec(GTj) | GTj protected}};

// MGT = alege din MGT o generalizare conform unor // criterii particulare, precum “prec”Sf. daca.

MinGen

Observatie: Algoritmul MinGen poate sa produca toate generalizarile la nivel de atribut, sau toate generalizarile la nivel de celula (insa aceasta varianta duce la o complexitate prea mare in realitate).

Observatie: Metrica prec poate fi folosita pentru determinarea generalizarii cu alterare minima si in cazul algoritmului Find_vector.

Algoritmul k-Optimize

Fie PT si QI, confirma caruia trebuie sa se efectueze k-anonimizarea. Se cunosc domeniile de valori pentru fiecare Ai QI. Se stabileste o relatie

de ordine totala intre toate valorile atributelor Ai QI, astfel: daca Ai inainte de Aj, atunci toate valorile din Ai primesc un numar de ordine

(index) mai mic decat toate numerele de ordine ale valorilor din Aj; valorile unui Ai sunt de asemenea numerotate (pentru valori numerice sau

pentru care se poate stabili usor o relatie de ordine – gen lexicografica – se respecta aceasta ordine, iar pentru valorile categorice – utilizatorul furnizeaza ordinea).

Exemplu: figura 15

Figura 15.


Algoritmul k-optimize cauta generalizare k-minimala (conform unei metrici alese) de la cea mai generala generalizare (elementul maximal din laticea generalizarilor), pana la generalizari de nivel inferior.

Fiecare generalizare se poate reprezenta ca reuniune de indecsi – ai atributelor care contribuie la generalizare. Fiecare index reprezinta de fapt multimea de indecsi care sunt mai mari sau egali decat el (in cadrul atributului din care face parte). Astfel, primul index din fiecare atribut nu se reprezinta, pentru ca intotdeauna participa la generalizare.

De exemplu: {8} reprezinta generalizarea care are age = *, gender = *, iar marital_status

are valori pe domeniile de generalizare [married or widowed], [divorced or never_married];

{2} reprezinta generalizarea care are age pe domeniile [10-29] si [30-49], gender = *, marital_status = *

{5, 7} reprezinta generalizarea care are age = *, gender = [M or F], marital_status = [married], [widowed or divorced or never_married]

Se considera ca {} reprezinta generalizarea maximala.


Pentru multimea indecsilor astfel stabiliti se formeaza un alfabet: all = (1-{v1

1} 2-{v21} ... m-{vm

1}) unde vi

1 este valoarea cu indexul minim din fiecare domeniu de atribut. Pentru alfabetul all se stabileste „power set”. Observatie: Power set pentru {1, 2, 3} este multimea {{}, {1}, {2}, {3}, {1, 2}, {1,

3}, {2, 3}, {1, 2, 3}}. Power set peste all se reprezinta sub forma de arbore = numit „set

enumeration” (SE).

Figura 16. Exemplu SE pentru alfabetul {1, 2, 3, 4}


Costul (metrica) considerat se bazeaza pe notiunea de „distinctie” – cum putem sa distingem un tuplu fata de altele din setul de date: daca in urma generalizarii, un tuplu t apartine de un grup E de cel putin k

inregistrari (este un grup de tuple E care se pastreaza in generalizare), atunci costul pentru t este |E| (numarul de tuple fata de care t nu poate fi distins)

daca in urma generalizarii, un tuplu t apartine de un grup E de mai putin de k inregistrari (este un grup de tuple E care se elimina din generalizare), atunci penalitatea asociata lui t este |PT| (fiind eliminat, spunem ca nu se poate distinge fata de toate inregistrarile din dataset).

=> costul generalizarii g (*):

Exemplu: figura 17 – SE pentru indecsii din figura 15.

EPTEkgCkEEkEE

||,||,

2),(


Exemple de cost al generalizarii g (*), k = 3:

1, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4 => 4 x 4 + 2 x 12 + 3 x 3 + 3 x 3 = 58

1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3 => 4 x 4 + 4 x 4 + 4 x 4 = 48

1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4 => 3 x 3 + 3 x 3 + 3 x 3 + 3 x 3 = 36


Figura 17. SE pentru indecsii din figura 15.


In arborele SE se efectueaza o cautare recursiva (in preordine) pentru a determina costul minim al unei generalizari (bineinteles, se poate determina in acelasi timp si generalizarea cu costul minim.

O particularitate a acestui algoritm este faptul ca nu testeaza toate nodurile posibile.

In SE – fiecare nod contine doua parti: head: indecsii de generalizare ai nodului curent; tail: indecsii care vor contribui la formarea nodurilor fiu.

Pentru un nod, A = H T (allset). => Parcurgerea arborelui incepe de la generalizarea maximala si,

coborand pe o ramura (adaugand un element in H), se obtine o specializare (se reduce generalizarea pe un atribut). In general se pleaca in parcurgere cu un cost maxim. Cand se intalneste un nod pentru care costul este mai mic decat cel minim curent, atunci se actualizeaza costul minim curent.


Observatii:

1. Daca generalizarea din nodul H duce la eliminarea a q tuple, atunci sigur orice specializare data de un nod fiu duce la eliminarea a cel putin acelorasi tuple corespunzatoare lui H.

2. Fie un nod H. Fie Ei grupele de tuple egale formate in urma generalizarii H. Adaugarea unui nou index in H (o valoare din T) duce la o noua specializare (o generalizare de nivel inferior). Evident, aceasta specializare face ca anumite grupe Ei sa se divida (e posibil sa nu fie afectate toate). Daca toate grupele afectate de specializare produc sub-grupe a.i. fiecare are mai putin de k inregistrari, atunci acea specializare sigur are costul mai mare si nu are rost sa se mai parcurga sub-arborele respectiv al lui H => acea valoare poate fi eliminata din T, precum si fiii lui H care au in head valoarea v.

Exemplu: in figura 17 – daca se considera in nodul {3,5}<7,8,9> ca valoarea v=7 este nefolositoare (useless), atunci se elimina 7 din T, precum si nodurile {3,5,7}, {3,5,7,8}, {3,5,7,9}, {3,5,7,8,9} din SE.


3. Pentru un nod H se poate stabili cel mai mic cost la care se poate ajunge pe cel mai specializat nod fiu (nod frunza) – prin aplicarea generalizarii A = H T. In primul rand – vezi observatia 1 – in orice specializare din sub-arborele lui H

vor exista cel putin q tuple eliminate, ca si pentru H. In al doilea rand, daca un tuplu nu este eliminat in H, atunci e posibil sa intre

intr-un grup de cel putin k inregistrari (=> penalitate cel putin k), sau sa intre intr-un grup de mai putin de k inregistrari, caz in care se considera penalitate k.

=> cost lower-bounds (**):

Exista cel putin doua situatii in care se pot elimina noduri din calcul: LB(H,A) este mai mare decat costul minim curent. Se poate elimina o valoare din T => se elimina si nodurile fiu

corespunzatoare.

PTt tA HinprimatsuenutkE

HinprimatsuetPTAHLB

),,max(

,),(

,

Algoritm k-Optimize (simplificat)

k-Optimize (k, H, T, c), MaxSup// H = head nod curent// T = tail nod curent// c = cost minim curent (obtinut din verificarea nodurilor

parcurse pana la nodul curent)// output: c

T := elimina_valorile_useless_din_T(T);c := min(c, cost(H)); // formula (*)Daca LB(H, H T) >= c atunci T := ;// formula (**)Sf. daca.Cattimp T <>

v := T[1]; // prima valoare din tailH_new := H {v};T := T - {v};c := k-Optimize(k, H_new, T, c);

Sf. cattimp.Returneaza c.

Algoritmul Incognito

Fie PT si QI. Se cunoaste faptul ca daca un singur atribut din QI nu satisface conditia de k-anonimitate, atunci nici QI nu satisface aceasta conditie.

=> cautare bottom-up in laticea de generalizari.

Fie QI format din m atribute, Ai, i:=1..m.

Pentru fiecare nivel n :=1, m se determina generalizarile minimale de cate n atribute care satisfac k-anonimitatea. La fiecare nivel n se tine cont de generalizarile minimale obtinute la nivelul n-1, pentru a obtine primele combinatii de cate n atribute.


Exemplu: Fie PT din figura 18. QI = {race, sex, marital_status}, k=2 Pas 1: combinatii de cate 1 atribut

<R0> – respecta k-anonimitatea <S0> – respecta k-anonimitatea <M0> – nu respecta k-anonimitatea => <M1> – respecta k-anonimitatea

Pas 2: combinatii de cate 2 atribute (se pleaca de la <R0>, <S0>, <M1>) <R0, S0> – respecta k-anonimitatea <S0, M1> – respecta k-anonimitatea <R0, M1> – nu respecta k-anonimitatea => <R1, M1>; <R0, M2> –respecta k-anonimitatea

Pas 3: combinatii de cate 3 atribute (se pleaca de la <R0, S0>, <S0, M1>, <R1, M1>, <R0, M2>) (combinatia <R0, S0, M1> nu se poate forma deoarece <R0, M1> nu se

gaseste in setul de plecare din acest pas) => <R0, S0, M2>, <R1, S0, M1> - primele combinatii gasite care respecta k-

anonimitatea => STOP.


Figura 18. PT

Sisteme real-world

Printre cele mai cunoscute sisteme care produc seturi de date anonimizate sunt

Datafly – poate sa gaseasca generalizare care nu este k-minimala

–Argus – poate sa gaseasca generalizare care nu respecta k-anonimitatea

Algoritm Datafly (simplificat)


Output: MGT – generalizare pentru PT

freq := lista frecventelor valorilor distincte din QI;Cattimp exista secvente care apar de mai putin de k ori (si

corespund pentru mai mult de k inregistrari din PT)

Fie Aj atributul cu cel mai mare numar de valori distincte in freq;

Generalizeaza valorile lui Aj in freq (un nivel);Sf. cattimp.

Elimina din freq secventele care apar de mai putin de k ori;MGT := construirea GT din freq

Algoritmul Datafly

Figura 19. Datafly: (1) generalizarea, (2) eliminarea tuplelor care nu fac parte dintr-un cluster de k inregistrari, prec(GT) = 0.875, (3) generalizarea k-minimala, cu precizia cea mai buna.

Algoritmul Datafly

Figura 19. Datafly: (1) generalizarea, (2) eliminarea tuplelor care nu fac parte dintr-un cluster de k inregistrari, prec(GT) = 0.75, (3) generalizarea k-minimala, cu precizia cea mai buna.

Algoritm –Argus


Output: MGT – generalizare pentru PT

freq := lista frecventelor valorilor distincte din QI;Generalizeaza fiecare atribut Aj din QI pana cand fiecare valoare din Aj

apare de cel putin k ori;Testeaza combinatii de 2 si 3 atribute din categoriile „Most identifying”,

„More identifying”, „Identifying”. Adauga in outliers combinatiile pentru care exista secvente care apar de mai putin de k ori (combinatiile se adauga in outliers ale tuplurilor carora le corespund secventele problematice);

Utilizatorul poate sa aleaga care atribute sa fie generalizate in continuare:Se generalizeaza atributele selectate (un nivel);Dupa fiecare pas de generalizare, se re-genereaza listele outliers.

Cand utilizatorul nu mai alege alte atribute, se trece la pasul de eliminare:Pentru fiecare combinatie din outliers pentru fiecare tuplu pentru care outliers <> , se elimina valoarea atributului cu cele mai multe aparitii in outliers (pana cand toate combinatiile din outliers au cel putin un atribut pentru care s-a efectuat eliminare).

MGT := construirea GT din freq

Algoritm –Argus

Observatie: fiecare atribut din QI este incadrat in una din categoriile „Not identifying”, „Most identifying”, „More identifying”, „Identifying” in functie de sansele ca atributul sa fie folosit in crearea de legaturi cu un alt set de date. In algoritm vor fi luate in considerare atributele „Most identifying”, „More identifying”, „Identifying”. Se vor testa combinatii de 2 si 3 astfel de atribute (nu toate combinatiile posibile!!!).

Combinatii intotdeauna testate: Identifying X More X Most, Identifying X Most X Most, Most X Most X Most, Identifying X More, Identifying X Most, More X Most, Most X Most

Combinatii testate daca |Identifying| > 1: More X More X Most, More X More

Observatii: Este posibil ca –Argus sa nu determine o generalizare k-anonima. Vezi figura 20. Problema: nu se testeaza toate combinatiile posibile de atribute din QI.

Algoritm –Argus

Figura 20. (1) freq dupa testarea combinatiei {birth, zip}, (2) freq dupa testarea combinatiilor de 2 si 3 atribute, inainte de eliminare, (3) generalizarea obtinuta (dupa eliminare).

Posibile atacuri – k-anonimitate

Situatie 1 Fie PT si doua generalizari, GT[1,0] si GT[0,1], figura 21. Daca ambele tabele generalizate sunt publicate, atunci, daca se pastreaza

ordinea tuplelor (au aceeasi ordine – si in PT – si in GT[1,0] si in GT[0,1]) atunci se pot deduce date (unele din cele originale din PT) prin simpla corespondenta prin pozitia tuplelor in seturi.

Figura 21. PT,

GT[1,0] si GT[0,1]


Situatie 2 Fie PT si GT1, generalizare a lui PT. GT1 asigura k-anonimitatea pentru QI.

GT contine si alte atribute Ai alaturi de QI. Daca pentru acelasi PT se publica o alta generalizare GT3 (care a plecat de

la PT, nu de la GT1), atunci ar trebui avut in vedere faptul ca exista un set extern de date care contine coloanele QI si Ai conform carora se poate stabili legatura cu GT1. Drept urmare, al doilea set de date ar trebui sa considere QI3 = QI Ai.

Exemplu: Figura 22. Se face legatura intre generalizarile GT1 si GT3 (coloana Problem) si rezulta LT, care nu mai asigura k-anonimitatea (la nivel de QI considerat initial).

Posibile atacuri – k-anonimitate Figura 22. PT, GT1, GT3, LT


Situatie 3 Similar situatiei 2: Fie PT la timpul t0 si GT generalizarea publicata pentru PT

la timpul t0. Pana la timpul t1, in PT se adauga / modifica / sterg inregistrari si se obtine PT1. La timpul t1 se publica generalizarea GT1 care este construita pe baza PT1. Desi au ca sursa seturi diferite de inregistrari (cu unele inregistrari ramase comune), se poate stabili legatura intre GT si GT1. Solutii posibile: GT1 sa se genereze pe baza de GT plus noile inregistrari, sau sa se considere ca QI toate coloanele lui GT in generalizarea urmatoare. Vezi figura 23.


Figura 23. PT-t1, GT-t1.

p-sensitive k-anonymity property

Seturile de date care au proprietatea de k-anonimitate protejeaza subiectii impotriva dezvaluirii identitatii, insa sunt situatii in care nu reuseste sa previna dezvaluirea altor atribute. Pentru protejarea altor atribute se propune p-sensitive k-anonymity.

Se considera ca GT publicat contine coloanele din QI si coloane care vor fi numite in continuare atribute confidentiale (de exemplu: boala, venit, etc.).

Se face distinctie intre: Dezvaluire de identitate: se identifica un subiect. Dezvaluire de atribut: se afla ceva nou despre un subiect.

Dezvaluirea de identitatea nu implica neaparat dezvaluire de atribut, sau invers.


Exemplu: fie PT si GT, unde GT asigura k-anonimitatea. Pp exista un set de date extern ET care se poate lega de GT. Pp toti subiectii dintr-un grup de k inregistrari pentru care s-au obtinut aceleasi valori pentru QI sufera de aceeasi boala => k-anonimitatea asigura ca identitatea subiectilor nu poate fi dezvaluita, insa se poate deduce ca toti acei subiecti sufera de boala respectiva => dezvaluire de atribut.


Un set de date respecta proprietatea de p-sensitive k-anonymity daca respecta proprietatea de k-anonimitate si pentru fiecare grup de tuple care au aceeasi secventa de valori pe QI (tuplele care apartin aceluiasi grup de cel putin k tuple) numarul de valori distincte ale unui (fiecarui) atribut confidential este cel putin p => p<=k

=> pentru a se evita dezvaluirea de identitate trebuie ca k>=2, pentru a se evita dezvaluirea de atribut trebuie ca p>=2. Oricum, k si p trebuie sa fie destul de mari. De exemplu: daca k=2, exista sanse de 50% ca subiectul sa fie identificat (mare).

Precum in obtinerea k-anonimitatii, pentru determinarea seturilor de date care sa aiba proprietatea de p-sensitive k-anonymity se pot folosi de asemenea generalizarea si suprimarea de tuple (cand limita de suprimare este cunoscuta).


Generalizarea p-k-minimala Ti este generalizare p-k-minimala pentru T0 daca asigura

proprietatea de p-sensitive k-anonymity si nu exista o generalizare Tj a.i. DV0j <= DV0i.

Fie atributele confidentiale Sj, j:=1..q. Fie numarul de valori distincte pentru Sj = sj.

Este evident faptul ca pentru ca un dataset sa satisfaca proprietatea de p-sensitive k-anonymity, p a.i. p<=min(sj), j:=1..q.

Observatie: Daca exista un atribut Sj pentru care numarul de valori distincte este mai mic decat p, atunci setul de date nu satisface proprietatea de p-sensitive k-anonymity.


Observatie: Modelul (, k)-anonymity (0 < < 1) – cere ca un set de date sa respecte conditia de k-anonimitate pentru QI, si pentru orice atribut confidential, orice valoare a acestuia sa se repete cu o frecventa de cel mult (in fiecare grup cu aceeasi secventa pentru QI).

CAPITOLE AVANSATE DE BAZE DE DATE

Documents

Transcript of CAPITOLE AVANSATE DE BAZE DE DATE