Test sull’algoritmo di Detection

Nelle prossime righe proporremo una suite di test svolti sul tool di Detection sviluppato. Questi test sono mirati a sollecitare la parte del sistema che in- divudua i canali d’inferenza. I risultati ottenuti comprendono sia il tempo necessario alla fase di espansione della conoscenza, partendo dagli itemset calcolati dall’input, che al tempo impiegato nella fase di ricerca dei possibili pattern non k-anonimi.

Primo Test

Il test propone di cronometrare il tempo impiegato dal sistema di Detection per individuare le possibili inferenze utilizzando le tecniche deduttive esam- inate. Chiameremo tale tempo TCDeductive. Esso `e stato valutato in funzione

del numero di tuple in input e del variare del numero di attributi.

In realt`a, il sistema prende in input l’insieme degli itemset frequenti calcolati con l’implementazione dell’algoritmo Apriori proposta da [...]. Poich`e l’in- sieme degli itemset calcolati dall’algoritmo Apriori dipende dalla grandez- za del database in input, per comodit`a ci riferiremo al numero di tuple computate da Apriori.

In questo test sono stati considerati tre configurazioni per il numero di at- tributi in input. Per non avere grosse variazioni nei risultati, l’insieme di cardinalit`a minore `e un sottoinsieme degli attributi dell’insieme che ha mag- giore cardinalit`a. Inoltre il numero di valori che ogni attributo pu`o assumere `e compreso nel range [3,10]

Per tutte le possibili configurazioni degli attributi, viene fatto variare il valore di σ. Esso influisce sulla dimensione dell’insieme degli itemset frequenti sui cui si effettua l’intera computazione.

Dalla figura 1.1 `e possibile notare che con 14 attributi i tempi di risposta del sistema variano notevolmente rispetto a quelli ottenuti considerando un insieme di cardinalit`a minore. In linea di principio, per quanto detto in 4.3.3 la dimensione dello spazio di ricerca cresce in base al numero di attributi e alla loro dimensione.

Fondamentalmente, oltre alla crescita dello spazio di ricerca, cresce in mo- do proporzionale la dimensione delle strutture dati che contengono tutte le informazioni necessarie per portare avanti la computazione.

Ad esempio con 14 attributi e σ = 60% abbiamo che all’incirca l’insieme degli itemset frequenti `e composto da 1000 pattern. L’insieme dei pattern closed risulta 450 di cui 50 sono massimi.

La fase di espansione per ogni pattern massimo cerca un pattern closed che sia un suo sottoinsieme (quindi compatibile per applicare il principio

Figura 6.1: TCDeductive con 50.000 tuple e k = 50

di inclusione-esclusione) e crea un DPattern. In questo caso risultano circa 2.000 DPattern (Alive) che rappresentato l’input del Detector vero e proprio. Come osservato nel capitolo dell’implementazione, Java (come ogni sistema basato su ”VM”) non preserva l’utilizzo della memoria e, nel nostro caso non disponendo di un piattaforma hardware di test pi`u potente, abbiamo indi- viduato in 14 attributi la soglia massima per poter effettuare dei rilevamenti attinenti alla scala dei tempi considerata in figura.

Tuttavia potendo disporre di memoria sufficiente, la computazione sembra assumere andamenti lineari. Ovviamente, nel castro caso, poich`e la memoria fisica viene saturata (e quindi entra in gioco l’allocazione su disco) lo stato di avanzamento del processo di Detection compromette la stabilit`a della pi- attaforma.

Secondo Test

completamento del sistema di Detection ma, in funzione del variare della soglia di anonimit`a k.

Figura 6.2: TCDeductive con 50.000 tuple e 12 attributi

Il test vuole mostrare che anche il valore di k incide sul costo della com- putazione. In particolare `e stato preso in considerazione solo un insieme campione di 12 attributi. Ci`o `e dovuto al fatto che i tempi di complemta- mento, come visto nel test precedente, sono fortemente variabili a partire da una certa soglia di attributi, quindi non ha molto senso confrontarli.

Dalla figura 1.2 si pu`o notare che al crescere di k il tempo necessario al sistema di Detection per cercare i pattern non k-anonimi cresce.

Secondo la logica di funzionamento del Detector il risultato non `e cos`ı sconta- to. Infatti se cerchiamo dei pattern con basso supporto, partendo da insiemi di DPattern che hanno un supporto abbastanza grande (maggiore di σ), in generale dobbiamo decrementare il supporto di ogni DPattern.

Quindi minore `e k, maggiore `e il numero di sottrazioni (e ricerche in FI per individuare tutti i pattern che contiene un DPattern) che dobbiamo effettuare per decrementare il supporto originario.

La risposta a tale risultato si pu`o cercarla nella distribuzione dei dati in in- put. Infatti, pu`o accadere che che in base alla combinazione del supporto in-

iziale dei pattern contenuti nell’insieme degli itemset frequenti, `e impossibile individuare pattern con supporto minore del k assegnato.

Questa circostanza si presenta quando non `e possibile ricavare il supporto dei pattern che vengono dedotti nella fase di espansione in quanto la combi- nazione dei loro item non `e compatibile con l’insieme degli itemset dato in input.

In questo caso l’algoritmo di Detection non riesce ad abbassare il supporto del pattern che sta elaborano e quindi lo scarta.

Terzo Test

Questo ultimi test vogliono mostrare il numero dei pattern non k-anonimi individuati dal sistema di Detection.

Figura 6.3: Num di pattern non k anonimi con 12 attributi e σ = 50%

La figura 1.3 mostra il numero di pattern non k-anonimi trovati dal sistema di Detection variando il numero di tuple in input e il valore di k.

In particolare dal risultato si pu`o vedere che per k = 100 e 10.000 tuple si individuano pi`u canali che non con lo stesso valore di k e 100.000 tuple. Aumentando la grandezza del database in input, come ribadito, pu`o accadere che molti pattern si appiattiscono perch`e i loro supporti tendono ad assumere gli stessi valori.

A causa di questo fenomeno, abbiamo che anche l’output prodotto nei due casi, individua pattern non k-anonimi differenti poich`e contenenti opposte categorie di item.

L’ultimo test, figura 1.4, mostra i risultati ottenuti variando il valore di σ. Come gi`a visto in altri casi, aumentare σ significa restringere l’insieme degli itemset presi in esame e, dai risultati si evince che tale aumento provoca una diminuizione delle inferenze individuate.