Universita degli Studi di MilanoPolo Didattico e di Ricerca di Crema

Facolta di Scienze Matematiche, Fisiche e NaturaliCorso di Sistemi Informativi

Data Mining applicato aisistemi informativi, una

panoramica dei principalialgoritmi

Studenti: Docente del corso:Massimo Manara 656814 Enrico SpoletiniAndrea Gobbi 651008

Anno Accademico 2005/2006

.

.

Indice 3

Indice

1 Introduzione 4

2 Cosa e il Data Mining 52.1 Un po di storia . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Interdisciplinare . . . . . . . . . . . . . . . . . . . . . . . . . . 52.3 Il processo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 Alcune tecniche 83.1 Mining association rules . . . . . . . . . . . . . . . . . . . . . 93.2 Alberi di decisione . . . . . . . . . . . . . . . . . . . . . . . . 103.3 GA - Algoritmi genetici . . . . . . . . . . . . . . . . . . . . . 103.4 Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

4 CRM - Customers Oriented 14

5 Quali standard 15

6 E la Privacy? 16

A Articolo 17A.1 Il data mining non serve per sconfiggere il terrorismo, ma si

diffonde in Usa. . . . . . . . . . . . . . . . . . . . . . . . . . . 17

Bibliografia 20

4 1 Introduzione

1 Introduzione

In ogni momento della nostra giornata siamo assaliti da moltissimi dati edinformazioni e importante tuttavia definire nel modo piu chiaro possibile ladistinzione tra dato ed informazione:

• Dato1: e qualcosa che possiamo vedere, ascoltare; per fare un esempio,un dato puo essere un libro.

• Informazione2: l’informazione, ci da qualcosa in piu sul dato; nel-l’esempio fatto prima l’informazione del dato libro potrebbe essere iltitolo, l’editore, il numero di pagine del libro [7].

Il data mining e un processo tramite il quale e possibile sapere sulla base dimolti dati gli andamenti delle vendite, delle offerte; nel caso di un supermer-cato.Questa tecnica, puo inoltre essere applicata a moltissimi campi; ed a suavolta fa uso di moltissime discipline: matematica, statistica, chimica, fisica,economia. . . Il data mining puo essere visto come il naturale sviluppo dell’IT,inoltre deve essere visto come risultato di un process.

1Per dato nella legge italiana, si intende informazione codificata da un pc.2Per informazione nella legge italiana, si intende delle informazioni non contenute

all’interno del pc.

2 Cosa e il Data Mining 5

2 Cosa e il Data Mining

Traducendo letteralmente il termine, si trova: miniera di dati; interpretandoil termine nel contesto informatico, si puo capire come questa sia la base dipartenza di un processo che prende il nome di data mining.In altre parole, e un processo attraverso il quale e possibile grazie ad unaquantita notevole di dati e attraverso particolari algoritmi, estrarre delleinformazioni nascoste: estrarre la conoscenza; knowledge [1].

2.1 Un po di storia

Figura 1: L’evoluzione della tecnologia dei database

2.2 Interdisciplinare

Le tecniche di data minig, possono essere applicate in moltissimi ambiti:ambito biomedico e DNA analysis, analisi finanziarie, telecomunicazioni. . . a

6 2 Cosa e il Data Mining

sua volta la tecnica di DM, si basa molte altre discipline. Alcuni esempi:

• Data Mining

– Database technology

– Informatica

– Statistica

– Tecniche di visualizzazione dei dati

– Machine Learning (apprendimento automatico);infatti, l’identificazione di pattern puo paragonarsi all’apprendi-mento, da parte del sistema data mining, di una relazione causaleprecedentemente ignota, cosa che trova applicazione in ambiti co-me quello degli algoritmi euristici e della intelligenza artificiale[4].

– Altre

2.3 Il processo

Il processo di data mining e formato da varie fasi:

• Data CleaningIn applicazioni reali, e difficile a volte riuscire a definire con precisionee con completezza le informazioni; consideriamo per esempio il caso diun database contenente dati identificativi di persone; non e detto checonosca tutti i dati di tutti i record.Come sopperire a questo problema:

– Tuple Ignorate

– Uso di attributi per completare quelli mancanti

– Usare il valore piu probabile per completare quello mancante

– Correzione dei dati inconsistenti, riferimenti esterni.

• Data IntegrationSempre piu spesso, ed anche per motivi di prestazioni, i database sonodistribuiti; progettati su piattaforme uguali, in questo caso non ci sonoproblemi o su piattaforme diversificate ed in questo caso possono sor-gere problemi di integrazione appunto.Per risolvere questo problema, vanno considerati anche aspetti comela ridondanza3 delle informazioni al fine di ridurre al minimo sprechi

3Si intende un dato che puo essere ricavato da altre tabelle

2 Cosa e il Data Mining 7

e perdita di prestazioni. Questi dati ridondanti possono essere trovatigrazie ad una analisi di correlazione:

rA,B =

∑(A− A) · (B − B)

(n− 1)σaσB

(1)

dove con n, si indica il numero di tuple, con A e B il significato4 e σA,σB, la deviazione standard5. Se il risultato dell’equazione (1) e mag-giore di 0 allora A e B sono correlati; cioe se cresce il valore di A ancheB cresce. Se il valore e zero allora A e B sono indipendenti; mentre seil risultato e minore di zero A e B sono correlati negativamente, cioe seA cresce, B diminuisce.

• Data TrasformationIn questa fase si cerca di trasformare o consolidare i dati affinche laforma di questi sia la piu adatta alla applicazione degli algoritmi. Ingenere si procede in vari passi:

– Caratteristiche comuni (Smoothing): cluster, cioe avere gruppi didati con caratteristiche comuni vedi Figura 2 a Pagina 7

Figura 2: Cluster Analisi

4Significato:

A =

∑A

n .

5Deviazione standard:

σA =

√∑(A− A)2

n− 1

8 3 Alcune tecniche

– Aggregazione: raggruppare i dati per mese di vendita ad esem-pio, per anno per settimana (Usato nella Data-Cube analisys,raggruppare dati secondo delle direzioni rappresentate sul cubo).

– Generalizzazione: dividere i dati in livelli di importanza, es. citta,via, numero civico. . .

– Costruzione di attributi: per favorire il processo di ricerca, ag-giungere nuovi attributi se necessario

• Data MiningL’algoritmo usato viene eseguito su i dati al fine di produrre i risultati.

• Pattern evaluationAl fine di valutare se il pattern e valido, si cerca di rispondere alleseguenti domande: capire se e di facile lettura per l’uomo, se sono in-teressanti tutti i patterns oppure solo alcuni; nella maggior parte deicasi solo alcuni.La risposta a queste domande e definita con una probabilita rappre-sentata dai concetti di supporto e confidenza [5].Definiti come:

– supporto(X ⇒ Y ) = P (X ∪ Y ).

– confidenza(X ⇒ Y ) = P (Y |X).

Il primo rappresenta la percentuale di transazioni dove sono contenutesia X che Y ; mentre il secondo rappresenta la probabilita che unatransazione che contiene X, contenga Y. Un esempio si puo otteneresostituendo ad X e Y dei valori ad esempio X = birra, Y = pannolini.

3 Alcune tecniche

Esistono parecchi modi di analizzare i dati al fine di giungere a delle con-clusioni; molti algoritmi gia esistenti e molti studi ancora sono in continuosviluppo per cercarne di nuovi e migliorarne, ottimizzarne altri.Alcuni di questi sono:

• Mining Association rulesApplicata soprattutto nella MBA: Market basket Analysis

• Classification and PredictionFanno parte di questa categoria i metodi Bayesiani, i GA GeneticAlgorithms, approcci Fuzzy

• Cluster Analysis

3 Alcune tecniche 9

3.1 Mining association rules

Come gia accennato questa tecnica viene usata nella Market Basket Analysis,la quale cerca di dare una risposta alla domanda

Quale oggetti sono acquistati insieme da un acquirente?

Tabella 1: Base di dati per “basket analysis”

Transazione Data Oggetto Qta Prezzo

1 17/12/98 pantaloni-sci 1 140e1 17/12/98 scarponi 1 180e2 18/12/98 maglietta 1 25e2 18/12/98 giacca 1 300e2 18/12/98 stivali 1 670e3 18/12/98 giacca 1 300e4 19/12/98 giacca 1 300e4 19/12/98 maglietta 3 25e

Questa tecnica si basa sull’uso dei concetti di supporto e confidenza presentatinella Sezione 2.3 a Pagina 6.

Tabella 2: Regole di associazione

Testa Corpo Supporto Confidenza

pantaloni-sci scarponi 0.25a 1scarponi pantaloni-sci 0.25 1

. . . . . . . . . . . .giacche magliette 0.5 0.66b

magliette,stivali giacche 0.25 1. . . . . . . . . . . .

a Numero di transazioni dove c’e sia il corpo che la testa diviso il numero di transazionitotale; vedi Tabella 1 a Pagina 9

b Numero di transazioni dove c’e sia il corpo che la testa diviso il numero di transazionidove e presente il corpo vedi Tabella 1 a Pagina 9

10 3 Alcune tecniche

3.2 Alberi di decisione

Un albero di decisione e un diagramma simile ad una struttura ad albero(vedi Figura 3 a Pagina 10), dove ogni nodo ha al suo interno ha un testsu un attributo ed ogni scelta, rappresenta un risultato del test; le fogliedell’albero rappresentano la classe o le classi di distribuzione.Questo algoritmi si basa sulla tecnica greedy.

Figura 3: Albero di decisione

La Figura 3 mostra l’albero delle decisioni del concetto di acquirenti di com-puter; indica se una persona in base all’eta compra o meno un pc. Il percorsonodo radice, foglia, risulta essere la classe di previsione.

3.3 GA - Algoritmi genetici

Questo tipo di algoritmi, si basa sull’idea dell’evoluzione naturale. In generalel’evoluzione comincia come:

• Popolazione inizialeCreata con delle regole generate in modo casuale; ogni regola puo essererappresentata da una stringa di bit.

Consideriamo ad esempio, due attributi booleani A1, A2 e due classi, C1, C2.La regola:

if {A1 && (not A2)}then

C2

3 Alcune tecniche 11

possa essere rappresentata dalla stringa di bit “100” dove i primi due bitrappresentano A1, A2 mentre l’ultimo bit rappresenta C2.Un altro esempio:

if {not A1 && (not A2)}then

C1

puo essere codificato con la stringa di bit “001”. Se ho una variabile k dovek > 2, allora si useranno k bit per rappresentarla.Dalla nozione di sopravvivenza, una nuova popolazione e formata da tuttauna serie di regole. In genere la forma di una regola e valutata sulla base diun insieme semplice.I figli, sono creati attraverso il crossover; vengono prese un paio di regole emodificate, scambiate (swapped) per formare un nuovo paio di regole.Mentre con la fase di mutazione, vengono scelti dei bit in una regola ed inmodo aleatorio vengono invertiti.Questo processo di evoluzione continua affinche la popolazione non e diven-tata della misura voluta.In genere questi tipi di algoritmi applicati all’ottimizzazione dei problemi.Mentre nella data mining possono venire applicati per valutare la forma dialtri algoritmi.

Figura 4: Evoluzione

12 3 Alcune tecniche

3.4 Software

Figura 5: Progetto Weka

Weka e una collezione di machine learning algorithms per il data mining.Questo programma e scritto in Java, e tramite questo linguaggio e possibilerichiamare dei dataset su cui applicare gli algoritmi.Weka contiene degli strumenti per il pre-processing dei dati, per la classifi-cazione, per il clustering e l’associazione di regole.

Figura 6: Screenshot Weka

Questo software e stato sviluppato dall’universita di Waikato [6].

3 Alcune tecniche 13

Il secondo software che presentiamo e una suite commerciale di Microsoft:Microsoft Dynamics.

E un software che permette di gestire una organizzazione nel suo insieme,fornendo anche un supporto per il data mining [9].

Figura 7: Microsoft Dynamics

Altri vendors nel campo del data mining sono:

• SAS

• Oracle

– Integrazione del data mining nei database

• Angoss

– Una delle prime applicazioni per il data mining

• HNC

– Fornisce delle soluzioni mirate e specifiche

• Unica

14 4 CRM - Customers Oriented

4 CRM - Customers Oriented

Le applicazioni di Customer Relationship Management (CRM) sono essen-ziali per acquisire e mantenere le relazioni con il Cliente. Includono aspetti dimarketing automation, sales force automation. Questo tipo di applicazionirisultano fortemente strategiche per la sopravvivenza del business.L’azienda ricorre alle soluzioni Customer Relationship Management per mi-gliorare la qualita e l’accessibilita delle informazioni attraverso una lorogestione ottimale, il tutto in un’ottica customer-centric.

Il concetto che sta alla base del Customer Relationship Management siriassume brevemente nella capacita di raccogliere e gestire in modo appro-priato la conoscenza (da con confondere con “informazione”) relativa ad uncliente o ad un gruppo di clienti che l’azienda gia possiede all’interno della suastruttura ma che non usa in modo appropriato per incrementare la CustomerSatisfaction come mezzo per raggiungere un’elevata Customer Retention6.

In altre parole, le aziende tramite il data mining come supporto dei CRM,possono sapere molte informazioni, per esempio, le preferenze di acquisto deiloro clienti e quindi fornire un prodotto piu mirato alle loro esigenze.

6Tenere i clienti soddisfatti; in altre parole non perdere clienti.

5 Quali standard 15

5 Quali standard

• Predictive Model Markup Language7 (PMML)

– Data Mining Group [10]

– basato su XML (DTD)

• Java Data Mining API(JSR-000073)8

– Oracle, Sun, IBM. . .

– Supporto per data mining APIs su piattaforme J2EE

– Costruzione, gestione, attivita programmate [11]

• OLE9 database a supporto del Data Mining

– Basati su tabelle

– Microsoft

– PMML

In genere alcune applicazioni si basano su piu standard per essere piuproduttive.

1 <?xml version="1.0"?>

<!DOCTYPE PMML [

3 <!ELEMENT MapValuesPair EMPTY >

<!ATTLIST MapValuesPair

5 column CDATA #REQUIRED

in CDATA #REQUIRED

7 out CDATA #REQUIRED

>

9 ]>

<PMML version="2.0">

11 <Header copyright="Copyright (c) 2001, Oracle Corporation. All rights

reserved.">

<Application name="Oracle 9i Data Mining" version="9.2.0"/>

13 </Header >

15 <Itemset id="1" support="0.033" numberOfItems="1">

<ItemRef itemRef="2"/>

17 </Itemset >

<AssociationRule support="0.033" confidence="0.121951" antecedent="5"

consequent="170"/>

19 <AssociationRule support="0.033" confidence="0.185185" antecedent="170"

consequent="5"/>

</AssociationModel >

21 </PMML>

Codice 1: Esempio PMML

7Predictive Model Markup Language (PMML) e un linguaggio basato su XML chedescrive modelli statistici e di data mining.

8E uno standard Java che permette di comunicare con altri standard ad esempio PMML.9Object Linking and Embedding

16 6 E la Privacy?

6 E la Privacy?

In Italia esiste la legge 31 dicembre 1996, n. 675: “Tutela delle persone edi altri soggetti rispetto al trattamento dei dati personali”, pubblicata nellaGazzetta Ufficiale n. 5 dell’8 gennaio 1997 - Supplemento Ordinario n. 3;la quale regola il trattamento dei dati personali. E stata puoi riunita con ildecreto legislativo n◦ 196 del 30 giugno 2003 che ha fornito un Testo Unicoper la privacy (L. 675/96, DPR 318/99).Ad esempio nel CAPO 3, Sezione 1, Art. 9:

1. I dati personali oggetto di trattamento devono essere:

(a) trattati in modo lecito e secondo correttezza;

(b) raccolti e registrati per scopi determinati, espliciti e legittimi,ed utilizzati in altre operazioni del trattamento in termini nonincompatibili con tali scopi;

(c) esatti e, se necessario, aggiornati;

(d) pertinenti, completi e non eccedenti rispetto alle finalita per lequali sono raccolti o successivamente trattati;

(e) conservati in una forma che consenta l’identificazione dell’interes-sato per un periodo di tempo non superiore a quello necessario agliscopi per i quali essi sono stati raccolti o successivamente trattati.

Un altra importante parte e quella del consenso. Abbiamo aggiunto que-sta sezione sulla privacy in quanto e importante sapere che dati si stia trat-tando, a volte questo aspetto viene sottovalutato, a discapito delle persone edelle norme vigenti.

A Articolo 17

A Articolo

A.1 Il data mining non serve per sconfiggere il terro-rismo, ma si diffonde in Usa.

Nel mondo post-11 settembre si presta molta attenzione a unire i punti.Molti credono che il data mining sia la sfera di cristallo che ci permettera di

svelare future trame terroristiche

Nel mondo post-11 settembre si presta molta attenzione a unire i punti.Molti credono che il data mining sia la sfera di cristallo che ci permettera disvelare future trame terroristiche. Ma anche nelle proiezioni piu sfrenatamen-te ottimistiche, il data mining non e sostenibile per tale scopo. Non stiamobarattando la privacy per la sicurezza; stiamo rinunciando alla privacy senzaottenere in cambio alcuna sicurezza. Moltissime persone scoprirono per laprima volta in che cosa consiste il data mining nel novembre 2002, quandofece notizia un massiccio programma governativo di data mining chiamatoTotal Information Awareness. L’idea di fondo era audace quanto ripugnante:raccogliere quanti piu dati possibile su chiunque, passarli al vaglio grazie apotentissimi calcolatori, e investigare quei pattern, quelle ricorrenze che po-trebbero indicare trame terroristiche. Gli americani di ogni credo politicodenunciarono il programma, e nel settembre 2003 il Congresso ne elimino ifondi e ne chiuse gli uffici.

Ma Total Information Awareness non scomparve.

Secondo The National Journal cambio semplicemente nome e fu spostatoall’interno del Dipartimento della Difesa.

Cio non dovrebbe sorprendere. Nel maggio 2004, il General AccountingOffice pubblico un rapporto che elencava 122 diversi programmi di data mi-ning varati dal governo federale che si servivano delle informazioni personalidei cittadini. Tale lista non comprendeva i programmi segreti, come le inter-cettazioni della NSA o programmi a livello statale come MATRIX10.

La promessa del data mining e avvincente, e molti ne sono affascinati.Ma tutto cio e sbagliato. Non scopriremo trame terroristiche con sistemi

10Informazioni reperibili all’indirizzo: http://www.aclu.org/privacy/spying/15701res20050308.html, (Multistate Anti-TeRrorism Information eXchange) e unsistema di sorveglianza che combina informazioni su persone da database governativi edaltri database di multinazionali.

18 A Articolo

come questo, e siamo in procinto di sprecare risorse preziose inseguendo falsiallarmi. Per capire perche, occorre osservare l’economia del sistema.

La sicurezza e sempre un compromesso, e perche un sistema sia valido,i vantaggi devono essere maggiori degli svantaggi. Un programma di datamining nazionale trovera una certa percentuale di attacchi reali, e una cer-ta percentuale di falsi allarmi. Se i benefici derivanti dall’individuare e dalfermare quegli attacchi superano i costi (in denaro, in liberta, ecc.) allora ilsistema e buono. In caso contrario, sarebbe preferibile spendere quei costi inaltro modo.

Il data mining funziona al meglio quando si e alla ricerca di un ben de-terminato profilo, un numero ragionevole di attacchi ogni anno, e un costocontenuto per i falsi allarmi. La frode delle carte di credito e un caso disuccesso del data mining: tutte le compagnie di carte di credito esaminanoi propri database delle transazioni in cerca di pattern di spesa che indichinola presenza di una carta di credito rubata. Molti ladri di carte di creditopresentano un simile pattern: l’acquisto di costosi beni di lusso, l’acquisto dioggetti facilmente smerciabili tramite ricettazione, ecc.; e i sistemi di datamining in molti casi possono minimizzare le perdite bloccando la carta. Inpiu, il costo dei falsi allarmi e rappresentato solo da una telefonata al titolaredella carta, richiedendogli di verificare un paio di acquisti. E i titolari dellecarte non sono nemmeno seccati da queste chiamate (purche avvengano dirado), per cui il costo si riduce semplicemente ad alcuni minuti di chiamatacon un operatore.

Le trame terroristiche sono differenti. Non esiste un profilo ben deter-minato, e gli attacchi sono molto rari. Presi insieme, questi fatti significanoche i sistemi di data mining non rileveranno alcun complotto terroristico ameno che non siano molto accurati, e che anche i sistemi piu accurati sarannotalmente inondati da falsi allarmi da diventare inutili. [. . . ]

Per ridurre entrambi quei numeri, e necessario un profilo ben definito.Ed e questo il problema quando si e alle prese con il terrorismo. Col senno dipoi, era davvero semplice unire i punti dell’11 settembre e puntare ai vari se-gnali d’allarme, ma e molto piu difficile prima dell’evento. Di sicuro esistonosegnali d’allarme comuni a molti complotti terroristici, ma ognuno e al tem-po stesso unico. Piu e possibile definire nei dettagli cio che si sta cercando,migliori saranno i risultati. Il data mining alla caccia di trame terroristichee destinato a essere approssimativo, e sara difficile scoprire qualcosa di utile.

A Articolo 19

Il data mining e come cercare un ago in un pagliaio. Vi sono 900 milionidi carte di credito in circolazione negli Stati Uniti. Secondo lo FTC IdentityTheft Survey Report del settembre 2003, ogni anno circa l’1% (10 milioni)delle carte di credito viene rubato e usato in modo fraudolento. Il terrorismoe diverso. Vi sono trilioni di connessioni fra persone ed eventi (cose che il si-stema di data mining dovra osservare) e pochissimi complotti. Questo livellodi rarita rende inutili persino i sistemi di identificazione piu accurati. [. . . ]

Questo sistema irrealisticamente accurato generera un miliardo di falsiallarmi per ogni complotto terroristico rilevato. Ogni giorno di ogni anno leforze dell’ordine dovranno investigare 27 milioni di potenziali complotti perpoter arrivare a scoprire l’unico vero complotto terroristico ogni mese. Au-mentiamo l’accuratezza dei falsi positivi a un assurdo 99,9999% e si dovrannoaffrontare ancora 2.750 falsi allarmi al giorno; ma questo fara aumentare ine-vitabilmente anche i falsi negativi, e sara molto probabile mancare uno diquei dieci veri complotti terroristici. [. . . ]

Il data mining puo funzionare. Aiuta Visa a contenere i costi delle frodi,cosı come aiuta Amazon.com a mostrarmi libri che potrebbero interessarmie che potrei comprare, e Google a mostrarmi annunci pubblicitari che po-trebbero incuriosirmi. Ma queste sono tutte istanze in cui il costo dei falsipositivi e basso (una chiamata di un operatore Visa, un annuncio non inte-ressante) e riguardano sistemi che hanno valore anche se il numero di falsinegativi e elevato.

Scoprire complotti terroristici non e un problema che si presta a essererisolto dal data mining. E il tipico caso dell’ago nel pagliaio, e aumentare lapila di paglia non facilita la risoluzione del problema. Sarebbe molto meglioincaricare persone all’investigazione di potenziali trame terroristiche e per-mettere a queste persone di dirigere i computer, invece di assegnare l’incaricoai computer e lasciar decidere a loro chi bisognerebbe indagare [2], [3].

di Bruce Schneierhttp://www.nazioneindiana.com/

http://www.nazioneindiana.com/2006/04/09/antiterrorismo-e-datamining/

#comments

20 Riferimenti bibliografici

Riferimenti bibliografici

[1] Jiawei Han M. Kamber (2001), Data Mining Concepts and TecniquesMorgan Kuafmann Publishers

[2] http://www.schneier.com

[3] http://www.businessonline.it

[4] http://it.wikipedia.org/ “Data mining”Data accesso 30.04.2006

[5] P. Atzeni, S. Ceri, S. Paraboshi, R. Torlone (1999), Basi di dati Secondaedizione McGraw-Hill

[6] http://www.cs.waikato.ac.nz/ml/weka/index.html

[7] M. J. A. Berry, G. Linoff (1997), Data mining techniques For Marketing,Sales, and Custumer Suport Wiley Computer Publishing

[8] Paolo Giudici (2001), Data mining Metodi statistici per le applicazioniaziendali McGraw-Hill

[9] http://www.microsoft.com/italy/dynamics/products/navision/4_

0/navision_40_release.mspx

[10] http://www.dmg.org/

[11] http://www.thearling.com/