Concetti base

Il modello inter-attributo fortunatamente oltre a permettere di riutilizzare tutte le propriet`a gi`a studiate, consente teoricamente anche di riusare gli stessi algoritmi.

In modo abbastanza elementare possiamo verificare che l’insieme degli item- set σ frequenti, per un database relazionale D, consiste, a parit`a di transazioni contenute in un database binario D’, in un insieme pi`u vasto.

Se nel modello binario venivano considerati solo gli item con valore positivo (che comparivano con il valore 1), adesso, si considerano sempre tutti gli item.

Un item non viene considerato quando compare con il valore nullo, ovvero non compare.

Intuitivamente possiamo gi`a affermare che la fase di Detection diventa pi`u complessa in quanto il modello inferenziale utilizzato dal Detector adesso deve tener conto della semantica degli attributi che risulta essere pi`u ricca di contenuti.

La complessit`a (da un punto di vista insiemistico) aumenta perch`e il numero di possibili combinazioni tra item `e maggiore rispetto a quelle che si potevono ottenere con item il cui dominio poteva assumere solo due valori.

Esempio database inter-attributo

D

a b e # a1 b1 e1 9 a1 b1 e2 2 a2 b1 e3 1

Tabella 4.1: database inter-attributo

Seguendo le linee guida del modello binario definiamo alcune propriet`a:

Definizione 4.2.1 (Dominio di Appartenenza). Dati A1...An attributi chi-

amiamo Dominio di Appartenenza dell’attributo An l’insieme dei possibili valori che esso pu`o assumere: DA(An) = {a1...am}.

Ovviamente ogni Dominio contiene valori dello stesso tipo (omogenei).

Il Dominio di Appartenenza ci consente di poter gestire la semantica di tutti gli attributi che, in questo modello gioca un ruolo molto importante.

Dall’esempio in tabella 4.1 abbiamo che: DA(A)= {a1,a2}, DA(B)= {b1,b2},

DA(E)= {e1,e2,e3}.

Diamo la definizione per un database inter-attributo:

Definizione 4.2.2 (Database Inter-attributo). Un database inter-attributo D = {I,T} `e formato da un insieme di variabili I = {A1,...,An} e i rispettivi

domini di appartenenza DA(A1),...,DA(An) chiamati anche item, e da un

insieme di transazioni T = {t1,...,tk}. Ogni transazione consiste in un vettore

di dimensione n contenente una combinazione dei valori delle variabili in I.

Ridefiniamo il concetto di pattern:

Definizione 4.2.3 (Pattern Inter-attributo). Considerando l’insieme delle variabili I, un pattern inter-attributo `e una proposizione logica costruita con connettivi AND(∧), OR(∨), NOT(¬) sui valori delle variabili in I.

Indicheremo tale insieme Pat(I).

Dalla definizione appena data segue che un possibile pattern `e {A=”a1” ∧

E=”e2”} per {A,E} ∈ I ed a1 ∈ DA(A) e e2 ∈ DA(E).

Differentemente dal modello binario esistono alcune combinazioni di attributi che formano pattern che non possono essere ritenuti conformi poich`e incon- sistenti(ovvero che non rispettano la semantica di come sono disposti gli attributi di ogni tupla del db). La propriet`a di consistenza ci permette di individuare solo i pattern che devono essere tenuti in considerazione.

Definizione 4.2.4 (Pattern Consistente). Diremo che un pattern inter-attributo `e corretto e quindi consistente se e sole non `e composto da sequenze di item appartenenti al medesimo DA legati in AND(∧). Indicheremo l’insieme dei pattern consistenti con P atC(I) ⊆ Pat(I) e l’insieme dei pattern non

consistenti con P atN C(I) = Pat(I)- P atC(I).

Esempio1 Con DA(A) = {a1,a2,a3} DA(B) = {b1,b2} abbiamo che :

Pattern consistenti: {¬A=a1 ∧ ¬A=a2 ∧ B=b1} ≡ {A=a3 ∧ B=b1} ,

{¬A=a1 ∧ B=b1} ≡ {A=a2 ∨ A=a3 ∧ B=b1}.

Pattern inconsistenti: {A=a1 ∧ A=a2} , {B=b1 ∧ B=b2 ∧ A=a3}.

Per semplicit`a da questo momento, senza che la notazioni crei imbarazzo, quando indicheremo un pattern useremo solo i sui valori.

Di pari passo vediamo se il concetto di supporto utilizzato in precedenza va ancora bene.

Per i database binari, avevamo definito il supporto di un pattern p come il numero di transazioni t tali che p(t) risultasse vera. In particolare la funzione p(t) ci diceva se gli item che comparivano in p erano tutti uguali a 1 (essendo il dominio degli attributi[0,1]) in t.

Adesso poich`e ogni pattern `e formato da un insieme di combinazioni di item che hanno sempre un valore ben definito, calcolare il supporto equivale a conteggiare il numero di transazioni che contengono un determinato pattern.

Definizione 4.2.5 (Supporto). Dato un database D, un pattern p e l’insieme delle transazioni T = {t1,...,tm} il supporto di p in D `e:

supD(p) = # ti t.c. p ∈ ti per i = 1...m

Dal database in tabella 4.1 per esempio abbiamo che il supporto del pattern p = {a1 ∧ b1} `e sup_D(p) = 11.

Il supporto, come nel modello binario, permette di escludere tutti quei pat- tern che non compaiono con un valore maggiore di σ. Per tanto definiamo l’insieme degli itemset frequenti FI.

Definizione 4.2.6 (Insieme degli Itemset). L’insieme di tutti gli itemset `e una classe di pattern consistenti ottenuti come combinazioni di item solo in AND(∧). Gli item appartenenti a un itemset sono una combinazione dei possibili valori dei domini di appartenenza DA(A1) o_{n...on DA(An), delle}

variabili I = {A1,...,An} tali che l’itemset risulti consistente. Denoteremo

questo insieme con la lettera V ⊆ P atC(I).

Definizione 4.2.7 (Itemset σ-Frequenti). Dato un database D e una soglia minima di supporto σ l’insieme degli itemset frequenti FI `e formato da tutti i pattern che sono definiti come:

F(D,σ) = {hX, supD(X)i | X ∈ V ∧ supD(X) ≥ σ }

4.2.1

Canali d’inferenza inter-attributo

Dopo aver introdotto tutte le definizioni necessarie per poter studiare un database relazionale, studiamo il problema di come verificare l’esistenza e il riconoscimento di possibili canali d’inferenza contenuti in un insieme di itemset σ frequenti.

Per studiare il problema possiamo sfruttare anche in questo caso i principi di k-anonymity gi`a discussi per i database binari.

Figura 4.1: F(D,σ) per database in tabella 1.1 con σ = 5

Infatti, anche adesso tale principio risulta essere valido per garantire l’anoni- mato dei soggetti rappresentati nell’insieme nei nostri dati che in questo caso sono l’insieme degli itemset frequenti F(D,σ) .

Riportiamo per comodit`a tale pricipio:

Definizione 4.2.8 (Pattern k-Anonimo). Dato un database inter-attributo e una soglia di anonimit`a k un pattern p ∈ P atC(I) `e anonimo con grado k

se supD(p) ≥ k o se supD(p) = 0.

Il concetto di k-anonymity come abbiamo visto, consente di valutare se un canale d’inferenza (individuato con il principio di inclusione esclusione) `e realmente pericoloso poich`e individua un pattern non k-anonimo.

Il problema dei canali d’inferenza per un database relazionale ´e legato al principio di supporto di inferenza definito nel capitolo precedente e che sim- ilmente rimane invariato. In modo elementare `e possibile constatare che cambia solo il dominio delle variabili.

Definizione 4.2.9 (Database compatibile). Un insieme S di coppie hX, ni con X ∈ V e n ∈ N e un database D si dicono compatibili se e solo se ∀ hX, ni ∈ S supD(X) = n.

Definizione 4.2.10 (Supporto di inferenza). Dato un insieme S di coppie hX, ni con X ∈ V e n ∈ N e un pattern p ∈ P atC(I). Supponiamo che esista

un database D compatibile con S. Per supporto di inferenza si intende la possibilit`<sub>a di dedurre S  sup(p) > x o viceversa. Poich`e S `e compatibile con</sub> D implica che ∃ un pattern p in D tale che supD(p) > x o viceversa.

Di seguito possiamo definire un canale d’inferenza inter-attributo, riutiliz- zando la definizione del modello binario, come:

Definizione 4.2.11 (Canale di inferenza inter-attributo). Un canale di in- fernza C `_{e un insieme di coppie hX, ni dove X ∈ V e n ∈ N tale che:}

∃p ∈ P atC(I) t.c. 0 < sup(p) < k .

In particolare, possiamo utilizzare il principio di inclusione-esclusione per i database binari e allo stesso modo possiamo concludere che:

Dati due pattern I,J t.c. I ⊆ J un canale di inferenza `e la coppia: hI, sup(I)i, hJ, sup(J)i. Tale coppia `e il pattern p.

Esempio 3 Dal database in tabella 4.1 e dalla figura 4.1 emerge che i pattern {a1∧ b1∧ e1} con supporto 9 e {a1∧ b1} con supporto pari a 11 rappresentano

un canale d’inferenza inter-attributo con supporto 2. Abbiamo che Ca1b1e1

a1b1 = f

a1b1e1

a1b1 = supD(a1b1) - supD(a1b1e1) = 11 - 9 = 2.

Il pattern non k-anonimo individuato `e p = {a1 ∧ b1 ∧ ¬e1} che ha supporto

uguale a 2. Oss:

Passando a questo modello la struttura dei canali di inferenza cambia se e solo se la cardinalit`a del DA di ogni attributo `e maggiore di due, altrimenti rimaniamo nel caso binario.

In realt`a dall’esempio 3 si ha che il canale d’inferenza individua un pattern che si distingue da quelli visti fin ora.

Introduciamo questa definizione:

Propriet`a 4.2.1 (Negazione di un item inter-attributo). Dato un item xi e

il suo DA(X) = {x1,...,xn} la sua negazione si ottiene come :

¬ xi ≡S(∨_j6=ix_j ∈ DA(X))

Secondo questo principio di equivalenza `e possibile trasformare {¬e1} con a

{e2 ∨ e3} e quindi riscrivere il pattern come {a1 ∧ b1 ∧ (e2 ∨ e3)}

Diversamente dal caso binario questo pattern individua i pattern: P1 = {a1

∧ b1 ∧ e2} e P2 = {a1 ∧ b1 ∧ e3}.

E’ possibile fare questa ipotesi e applicare queste trasformazioni perch`e conos- ciamo DA(E) = {e1,e2,e3}. In caso contrario non avremmo potuto dir niente

a riguardo perch`e guardando l’insieme degli itemset frequenti in figura 4.1 non si evince completamente l’insieme dei valori che pu`o assumere l’attributo ”E”.

Se banalmente guardassimo il database potremmo verificare che P1 ha sup-

ipotesi poich`e il modello di protezione adottato suppone di non conoscere la distribuzione dei dati nel database.

Quindi possiamo dire che per P1 e P2 e pi`u in generale vale la seguente

propriet`a :

Propriet`a 4.2.2 (Di copertura). La somma dei supporti di P1 e P2 `e uguale

al supporto totale del canale d’inferenza che li rappresenta. Pi`u in generale:

Dato DA(A) = {a1...am}, DA(B) = {b1...bs}, DA(C) = {c1,c2...ck} e un canale

d’inferenza :

CJ

I con I = {a1,b1} e J = I ∪ {c1} e con a1,b1 fissi abbiamo :

sup(C

) =

P

i=1

sup

{a

∧ b

∧ c

} ∀ c

∈{DA(C)\

c

}

La propriet`a di copertura ci mostra in pratica un prima sostanziale differenza tra i due modelli. Banalmente nel database binario negare il valore di un attributo significa non prenderlo in considerazione.

Adesso, la possibilit`a di trasformare un attributo negato ci consente di in- dividuare un pattern appartenente a P atC(I) che individua una regione di

item a cavallo tra pi`u transazioni di un database inter-attributo.

Cercheremo di sfruttare le informazioni che ci fornisce la conoscenza di do- minio per capire se il modello inter-attributo presenta nuove tipologie di inferenze. Inoltre sfrutteremo il legame che esiste tra la rappresentazione dei canali di inferenza del database binario con quello inter-attributo per poter riutilizzare, con le opportune modifiche il modello di Detection gi`a studiato precedentemente.