4
precedente anche all elaborazione dei dati memorizzati, e quindi un argomento
preso in considerazione da diverse tipologie di studiosi, che nel corso degli anni si
sono impegnati prima di tutto a trovare una definizione per la privacy, poi a
promulgare leggi che la salvaguardassero ed infine a sviluppare tecniche che
elaborassero i dati privati nel rispetto di quelle leggi vigenti. Anche il data mining
si Ł dovuto adeguare a questi nuovi risultati e gli studiosi si sono impegnati a
cercare una soluzione che trovasse un compromesso tra la qualit delle
informazioni estratte dai database e il rispetto della privacy di quegli individui
coinvolti.
Solo negli ultimi anni Ł stato preso in considerazione un problema altrettanto
importante, ma che fino ad ora non era venuto a galla nel contesto del data
mining, perchØ al contrario del problema della privacy esso viene rilevato solo nel
caso di tecniche che attuano il supporto alle decisioni. Si tratta del problema della
discriminazione che avviene in molti contesti perchØ spesso i dati utilizzati per
prendere le decisioni sono gli stessi utilizzati per le statistiche e perci obsoleti e
intrisi di antiche convinzioni che si traducono di solito in discriminazione. Anche
per la discriminazione Ł stato difficile trovare una definizione a livello sociale che
ne comprendesse tutte le forme ed i contesti, e nonostante il problema sia
diventato rilevante gi dopo la Seconda Guerra Mond iale, solo negli ultimi dieci
anni, almeno in Europa, si sta cercando di tutelare realmente gli individui che
subiscono qualunque tipo di sopruso.
PoichØ le tecniche di data mining sono diffuse in tantissimi contesti Ł stato subito
evidente il contrasto esistente tra i risultati ottenuti con la loro applicazione a dati
sensibili e le leggi in vigore che tutelano l individualit e la personalit della gente
che ha concesso di fornire informazioni private per qualunque scopo. Nel corso
degli anni sono stati progettati diversi modelli e tecniche che permettessero di
ottenere buoni risultati nel rispetto delle leggi, anche se ancora oggi non Ł facile
stabilire quale tecnica sia migliore di un altra e se una precisa tecnica rende
completamente sicuri i risultati sia dalla scoperta di informazioni private che dalla
discriminazione.
5
Le difficolt incontrate nello sviluppo di tali mod elli e tecniche sono state
svariate, a cominciare dal semplice fatto che una definizione formale per la
privacy e la discriminazione sono molto difficoltose essendo due concetti astratti e
per questo motivo dipendenti molto dalla realt in cui ci si trova, dal contesto che
viene preso in considerazione, dalle tradizioni e dalla cultura del popolo o della
nazione che affronta l argomento e quindi concetti in continua evoluzione insieme
alle leggi create per tutelare chiunque in qualunque caso. Negli ultimi tempi Ł
stato piø facile omogeneizzare i concetti e le soluzioni da attuare in caso di
violazione di privacy o di comportamento discriminante, grazie anche all avvento
dell Europa Unita e degli accordi tra diversi Paesi.
E naturale che per il problema della discriminazione siano state proposte molte
meno soluzioni nel contesto del data mining rispetto al problema della privacy,
considerato che il primo Ł stato preso in considerazione molto piø tardi rispetto al
secondo.
Altre difficolt importanti incontrate durante lo s viluppo di tali tecniche sono state
soprattutto quelle di mantenere una certa consistenza dell informazione estratta,
parallelamente alla tutela degli individui, cosa non semplice se si considera il fatto
che la maggior parte delle soluzioni comprende l occultamento o la perturbazione
di alcuni dati originali. E quindi Ł chiaro comprendere che non Ł affatto semplice
sapere sino a che punto si pu nascondere dell info rmazione per avere ancora
della conoscenza significativa o qual Ł il minimo dell informazione che deve
essere modificata per fare in modo che le leggi siano rispettate e non ci sia il
rischio che chiunque possa venire a conoscenza di informazione sensibile o
discriminatoria. Anche perchØ Ł stato dimostrato in diverse occasioni che anche se
vengono occultati tutti i dati sensibili, c Ł sempre la possibilit di risalire ad alcuni
di essi o di associare alcune informazioni rese pubbliche agli individui a cui
appartengono tramite ricerche incrociate tra diversi database o con altre
informazioni ormai accessibili a chiunque. Si Ł compreso cos che non erano i soli
dati privati (nel caso della privacy), o i soli attributi considerati discriminanti a
dover essere occultati o modificati, ma anche altri dati apparentemente innocui
6
che in qualche modo permettevano di violare la privacy o fare della
discriminazione. Si Ł perci cercata la soluzione anche per queste casistiche,
cercando di dimostrare che non se ne potessero creare di nuove. Le soluzioni per
la salvaguardia della privacy sono numerose e gli studiosi si impegnano tutt ora a
trovarne di nuove, a migliorare quelle gi esistent i, a dimostrare che quelle
esistenti non risolvono tutti i problemi. Per quanto riguarda la discriminazione
esiste invece ancora molto poco: per quel che ne sappiamo esistono solo degli
studi effettuati dall Universit di Pisa che ha pro posto soluzioni per molte
possibili casistiche e lo sviluppo di alcuni algoritmi. L obiettivo di questa tesi Ł
stato quello di raccogliere la maggior parte delle informazioni possibili sia sulle
leggi in vigore riguardo alle due problematiche esposte, sia sugli studi effettuati
che sulle tecniche piø importanti sviluppate sinora per risolvere i due problemi nel
campo del data mining, le possibili problematiche e le possibili soluzioni.
Per quanto riguarda la salvaguardia della privacy, la soluzione apparentemente
migliore e sicuramente preferita dalla maggior parte dei ricercatori sembra essere
quella del k-anonimato, una soluzione che cerca di risolvere tutti i problemi
inerenti a questa problematica facendo in modo che non siano mai rese pubbliche
informazioni che non siano vere almeno per k individui; perci se il nostro
database di partenza non Ł k-anonimo, viene reso tale generalizzando alcuni
campi o occultandone degli altri. Intorno al k-anonimato gli studiosi si sono
sbizzarriti alla ricerca di migliorie che rendessero le informazioni divulgate ancora
piø sicure mantenendo la maggior parte della conoscenza interessante. Inoltre si Ł
provato ad applicare la stessa tecnica non solo al database di partenza, ma anche
ai pattern estratti, in modo da poter modificare meno dati possibili e avere nello
stesso tempo maggiore sicurezza. In questa tesi verranno esposte le soluzioni piø
interessanti, riportando anche alcune critiche alle tecniche in uso e relative
soluzioni proposte.
Per quanto riguarda invece il problema della discriminazione abbiamo riportato le
ricerche ed i risultati ottenuti dall Universit di Pisa, che comprendono soluzioni
anche per i diversi tipi di discriminazione, a partire da quella diretta e come risulta
7
facile comprendere, anche la piø semplice da individuare, per finire con quella
indiretta, piø subdola e quindi difficile da riconoscere.
Sia che si tratti del problema della privacy che di quello della discriminazione, il
primo passo da compiere per la loro risoluzione Ł quello di capire e individuare
quali sono i dati o i pattern sensibili potenzialmente utilizzabili per risalire a
informazioni private o discriminanti.
Un importante concetto utilizzato per individuare regole discriminanti o meno Ł
quello dell α -discriminazione che si basa su una misura utile per l individuazione
di informazione discriminatoria e da cui vengono sviluppati altri concetti
utilizzabili per risolvere tutte le possibili situazioni pericolose.
Sia nel caso della privacy che della discriminazione, una volta individuato il
pericolo si agisce in maniera tale da rendere innocue le informazioni pericolose e
qualunque risultato si cerchi di ottenere, le tecniche realmente utilizzate si
riducono semplicemente alla perturbazione e all occultamento dei dati.
I.1 Organizzazione della tesi
La tesi Ł organizzata in quattro capitoli principali che espongono gli argomenti
accennati nell introduzione.
Il Capitolo 1 spiega il ruolo del data mining all interno del processo del KDD e
ne espone il significato da un punto di vista logico. Vengono inoltre elencate e
spiegate le differenti tecniche utilizzate per estrarre informazione utile da enormi
database, esplicitando le definizioni piø importanti e significative utili per
l esposizione dell intera tesi.
Il Capitolo 2 affronta i problemi principali che sorgono dall elaborazione dei dati
tramite le tecniche del data mining, problemi che sorgono dall infrazione di leggi
8
emanate per salvaguardare la privacy e per tutelare ogni individuo dalla
discriminazione. Vengono esposte in particolar modo le principali definizioni
esistenti riguardo alla privacy e il suo rapporto con il data mining. Viene
introdotto infine il concetto di discriminazione e il suo rapporto con il data
mining, meglio ampliato nel Capitolo 4.
Il Capitolo 3 spiega quali sono le caratteristiche per cui delle informazioni estratte
con le tecniche di data mining possono essere considerate rispettose della privacy.
Vengono elencati due principali modelli di data mining rispettoso della privacy e
per ogni modello vengono esposte le principali tecniche sviluppate, con una
particolare attenzione al k-anonimato.
Il Capitolo 4 amplia approfonditamente il discorso sulla discriminazione
riportando una summa delle leggi principali che affrontano la questione. Vengono
infine riportati i risultati ottenuti dallo studio effettuato dall Universit di Pisa,
indicando le situazioni piø plausibili comprendenti anche quelle piø subdole e le
relative soluzioni possibili.
9
Capitolo 1
Il Data Mining
1.1 KDD e Data mining
Oggigiorno qualunque azienda, societ , istituto, as sociazione di qualsiasi tipo e
persino i privati sono in possesso o vengono in contatto con migliaia di
informazioni contenute e catalogate in altrettanti database sparsi per il mondo.
Questa crescita spropositata delle dimensioni dei database dovuta innanzitutto al
progresso tecnologico e di conseguenza ad un abbassamento dei prezzi e quindi ad
una maggiore diffusione degli strumenti utili alla memorizzazione dei dati, ha
permesso la nascita, lo sviluppo e lo studio di nuove tecnologie, aprendo nuove
frontiere nella ricerca informatica. Infatti proprio il numero sempre crescente di
queste informazioni, le rende paradossalmente inutilizzabili per operazioni che
divergano dal semplice inserimento o cancellazione, a meno che non vengano
elaborate con appropriate tecniche che le rendano significative da un punto di
vista statistico.
10
Nell ultimo ventennio il progresso tecnologico ha reso possibile la raccolta,
l organizzazione e l elaborazione di queste grandi quantit di dati utilizzabili e
ormai indispensabili per scopi statistici, commerciali, medici, di ricerca scientifica
e di mercato.
Il KDD, acronimo che sta per Knowledge Discovery in Database [24, 74], Ł un
processo creato proprio per rendere significativa questa enorme quantit di dati,
per estrarre informazione, ovvero a partire dai dati contenuti in una o piø basi di
dati vengono estratti pattern significativi, ossia espressioni in un opportuno
linguaggio che descrivono in modo succinto le informazioni estratte dai dati.
Formalmente possiamo utilizzare la seguente definizione:
Definizione 1.1 (Knowledge Discovery in Database o KDD) Il KDD Ł il
processo non banale di identificazione di nuova, valida, potenzialmente utile e
comprensibile conoscenza (pattern) da un database al fine di effettuare decisioni
e comprensivo di tutte le fasi atte a ripulire, filtrare, trasformare i dati contenuti
nel database di partenza.
In questo contesto i dati saranno un insieme di record F in un database, mentre il
pattern Ł un espressione E in un linguaggio L che descrive i fatti contenuti in un
sottoinsieme EF di F. E Ł chiamato pattern se Ł piø semplice della enumerazione
dei fatti di EF .
Per definire formalmente un pattern abbiamo bisogno di chiarire alcuni concetti
fondamentali [1, 2, 3].
Definizione 1.2 (Item) Sia R una relazione con attributi 1a , , na . Diciamo che
un a -item Ł una espressione del tipo a = v , dove a Ł un attributo in { 1a , , na } e
v appartiene al dom ( a ) ovvero al dominio di a . Un item Ł un qualunque a -
item.
11
Esempio 1.1 Prendiamo come esempio il database di una scuola riguardante tutti
gli alunni che la frequentano, i cui attributi sono: [Nome, Cognome, Indirizzo,
Numero di telefono, Classe, Sezione]. Consideriamo l attributo Sezione, il cui
dominio dom(Sezione) sar dato dall insieme { A , B , C , D , E }. Un item
potr essere Sezione = B .
A questo punto possiamo fornire una definizione formale anche per le espressioni
pattern:
Definizione 1.3 (Espressione Pattern) Una espressione pattern X Ł un item, o
true, o false, o 1X ∧ 2X , o 1X ∨ 2X , o ¬ 1X , dove 1X e 2X sono espressioni
pattern. Quindi un pattern Ł un espressione booleana di item.
Esempio 1.2 Riprendendo l Esempio 1.1, un possibile pattern sar dato
dall espressione:
(Classe = 2 a ∧ Sezione = C ) ; oppure ((Nome = Maria ∨ Nome = Mario) ∧
¬ (Classe = 3 a ))
Ritornando alla definizione del KDD, Ł stato specificato che si tratta di un
processo ossia Ł composto di piø passi; poichØ deve essere non banale, deve
richiedere una ricerca. Abbiamo detto che i pattern scoperti devono essere validi,
ovvero devono valere anche su nuovi dati con un certo grado di certezza; i pattern
devono essere nuovi, ovvero non essere precedentemente noti; devono essere
potenzialmente utili, ovvero devono poter permettere nuove potenziali azioni;
devono essere ovviamente comprensibili in modo da facilitare la comprensione
dei dati da cui sono stati estratti.
Il processo di KDD contiene, come abbiamo gi accen nato, diversi passi che
possono essere essenzialmente riassunti in otto punti (Figura 1.1):
12
1. Comprensione del dominio applicativo e degli obiettivi dell utente finale;
2. Consolidamento dei dati;
3. Selezione e preprocessing;
4. Scelta del compito del data mining, ovvero della tecnica di data mining da
applicare;
5. Scelta dell algoritmo di data mining da utilizzare;
6. Data Mining: applicazione dell algoritmo;
7. Interpretazione del pattern estratto e possibile ritorno ai passi 1 e 6 per
ulteriori iterazioni;
8. Consolidamento della conoscenza scoperta: incorporamento della
conoscenza all interno di un sistema oppure all int erno di un documento
da mostrare all utente. Questo include anche la ricerca e la risoluzione di
potenziali conflitti con la conoscenza precedentemente creduta.
13
Figura 1.1: Le diverse fasi del processo del Knowledge Discovery in Database.
Da questi otto punti possiamo dedurre due cose: prima di tutto che il KDD Ł un
processo iterativo in quanto i passi possono essere ripetuti; in secondo luogo Ł un
processo interattivo perchØ richiede l intervento umano per molte decisioni e per
la scelta dei vincoli da imporre agli algoritmi.
Cerchiamo di capire meglio in cosa consistono questi otto punti appena elencati e
prendiamo subito in considerazione il secondo punto, ovvero il consolidamento
dei dati.
Il consolidamento dei dati, conosciuto anche come data integration, riguarda
essenzialmente quelle fasi che permettono di ripulire ed omogeneizzare tutti i dati
che provengono da diversi database sparsi per il mondo e riunificarli in un unico
DBMS o in un Datawarehouse. Infatti Ł chiaro che i diversi database da cui si
Knowledge Discovery in Database
dati
dati selezionati
dati processati
dati trasformati
pattern
conoscenza
DATA MINING
14
raccolgono i dati sono fonti eterogenee sia dal punto di vista della sintassi che
della semantica e proprio per questo motivo il consolidamento risulta essere una
fase fondamentale per poter portare avanti tutto il processo di KDD. La qualit dei
risultati dipender prima di tutto dalla qualit de i dati di partenza e quindi
possiamo affermare che dati di partenza e risultati sono in relazione diretta.
Anche il terzo punto, ovvero la selezione e il preprocessing fanno parte delle fasi
preliminari, dette anche di data cleaning, ovvero di pulizia dei dati, perchŁ
permettono di scegliere quali attributi mantenere o eliminare per svariati motivi.
Potr capitare per esempio che ci sia l impossibili t di utilizzare l intero database,
nel qual caso sar necessario selezionare un campio ne significativo di record: si
parler in questo caso di data reduction; oppure ci sar la necessit di eliminare
alcuni attributi perchØ ridondanti o correlati ad altri; o ancora si potranno
combinare tra di loro diversi attributi facendone la somma o il prodotto e infine
potrebbe esserci la necessit di ridurre il range d egli attributi raggruppando ad
esempio il valore di quelli discreti.
Il data mining [4] (che letteralmente significa estrazione da una miniera di dati),
come abbiamo potuto notare, non Ł altro che un passo del processo di KDD che
riguarda proprio l estrazione (e quindi l elaborazi one), eseguita in modo
automatico o semiautomatico, di informazione utile (ma non immediatamente
visibile) da enormi quantit di dati contenuti in d iversi database.
Considerato all interno del KDD, il data mining consiste in una procedura che,
prendendo dei dati in ingresso contenuti all interno di uno o piø database
precedentemente elaborati nelle altre fasi, produce della conoscenza, la quale pu
eventualmente essere rielaborata. La fase di mining prevede quindi la costruzione
di opportuni modelli che permettano di rappresentare efficacemente questa
conoscenza estrapolata dai dati di partenza.
Possiamo affermare che i compiti del data mining sono essenzialmente due: la
predizione e la descrizione. Per attuare ognuno di questi due compiti esistono
15
diverse tecniche: per la predizione avremo la classificazione e la regressione,
mentre per la descrizione il clustering, la scoperta di regole associative e di regole
di sequenza.
La classificazione Ł l apprendimento di una funzione che permetta di assegnare
ogni oggetto ad una classe compresa in un insieme predefinito di classi, mentre la
regressione Ł l apprendimento di una funzione che assegni un valore reale ad ogni
oggetto. Queste due tecniche vengono utilizzate per la predizione proprio perchØ
permettono di inserire un dato in una classe gi es istente ovvero di predire il
comportamento degli individui in base a regole gi esistenti.
Il clustering Ł la scoperta di sottogruppi di dati, tali che i dati all interno di uno
stesso sottogruppo siano simili tra di loro e siano dissimili da quelli appartenenti
ad altri sottogruppi; la scoperta delle regole associative Ł l estrapolazione di
regole che descrivono regolarit nei dati, mentre l a scoperta di regole di sequenza
si applica su una base di dati di sequenze temporali e si utilizza per determinare
sequenze simili ad una sequenza data e per trovare tutte le coppie di sequenze
simili. Queste altre tre tecniche servono invece per la descrizione perchØ
permettono di descrivere in maniera sintetica e con una buona aderenza alla realt
la porzione di mondo presa in analisi.
Le tecniche e gli algoritmi di data mining hanno quindi lo scopo di analizzare
vasti campioni di dati per identificare possibili ed interessanti regolarit (dette
pattern) in situazioni analoghe. I pattern cos identificati possono essere un buon
punto di partenza per ipotizzare e quindi verificare nuove relazioni di tipo causale
tra fenomeni; inoltre possono essere utili per scopi statistici, per il supporto alle
decisioni e per formulare previsioni sui nuovi insiemi di dati.
Un concetto correlato al data mining Ł quello di machine learning o
apprendimento automatico proprio perchØ l identificazione dei patterns pu
paragonarsi all apprendimento, da parte del sistema di data mining, di una
relazione causale precedentemente ignota. Un rischio che si potrebbe correre con
questi tipi di tecniche Ł quello della scoperta di relazioni causali inesistenti, errate
o discriminanti, dovuta ad esempio all inesattezza dei dati di partenza o alla
16
limitata porzione dei dati su cui si lavora o ancora all esistenza di regole ormai
obsolete.
Non rimane che parlare degli ultimi due punti delle diverse fasi del KDD che
consistono nell interpretazione dei pattern estratti, nella loro valutazione e nel
consolidamento della conoscenza. Lo scopo principale dell interpretazione Ł
prima di tutto quello di facilitare la lettura, da parte di un qualunque utente, dei
pattern estratti, ma risulta non essere l unico. Infatti altro compito fondamentale Ł
quello di filtrare l informazione che sar presenta ta. Questo filtraggio, atto a
valutare la bont di una informazione, viene genera lmente effettuato tramite
l utilizzo di parametri che possono essere sia oggettivi (per esempio basati su
statistiche gi esistenti) che soggettivi (per esem pio attraverso delle stime
riguardanti il grado di novit dell informazione).
A questo punto, se i risultati ottenuti non sono valutati essere buoni, si ripetono le
fasi iniziali del processo, sino a quando non ci si ritiene soddisfatti.
1.2 Inferenza sui dati
Se osserviamo il lavoro svolto dal data mining da un punto di vista logico,
possiamo affermare che il suo compito Ł quello di inferire [46] informazione dalla
base di dati di partenza, giacchØ queste informazioni vengono dedotte, ottenute
tramite una generalizzazione dei campioni rilevati.
Le tecniche esistenti e sinora utilizzate per l inferenza sono essenzialmente tre [5]:
la deduzione, l induzione e l abduzione, che risult a essere di nuova generazione.
17
Generalmente per poter rispondere a problemi di elevato livello abbiamo bisogno
di poter riapplicare ognuna di queste tecniche su dati che sono gi stati inferiti
[21] e a volte si ha la necessit di un ambiente ch e estrapoli delle ipotesi: perci si
comprende il significato della ricerca di nuove tecniche di inferenza quali
l abduzione.
La deduzione Ł un procedimento logico e analitico che permette di pervenire ad
una soluzione particolare partendo da un principio generale, ovvero Ł basato
sull applicazione di una regola generale ad un caso particolare.
L induzione Ł invece un procedimento logico e sintetico che consiste nel ricavare
principi generali partendo da casi particolari.
L abduzione Ł un altro procedimento sintetico, introdotto per la prima volta dal
filosofo Pierce [5], che permette di ipotizzare risultati, ovvero arrivare a
conclusioni che date le premesse hanno buone probabilit di essere reali.
Se prendiamo in considerazione i sillogismi Aristotelici, possiamo facilmente
comprendere questi tre tipi di inferenza logica:
Esempio 1.3 Consideriamo un sillogismo Aristotelico che rappresenta un buon
esempio per il principio della deduzione:
Tutte le biglie di questa sacca sono rosse (regola)
Quelle biglie provengono da questa sacca (premessa)
Quindi, quelle biglie sono rosse (risultato)
Sinteticamente potremo scrivere che la deduzione Ł rappresentata dalla seguente
regola:
,A B A
B
→
.
Ora per ottenere un esempio del principio dell induzione, baster invertire la
regola con il risultato:
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
