Introduzione alle tecniche di

Data Mining

Prof. Giovanni Giuffrida

Programma

• Contenuti

– Introduzione al Data Mining

– Mining pattern frequenti, regole associative

– Alberi decisionali

– Clustering

Nome Matricola Indirizzo Citta

Mario Rossi 456 Via Roma 1 Catania

Ugo Bianchi 567 Via Etnea 154 Ragusa

Teo Verdi 678 Via Parma 12 Ragusa

Leo Poldo 555 Via Etnea 7 Catania

Franco Bollo 892 Corso Italia 7 Catania

Matr_Studente Corso Voto

678 Programmazione 27

456 Architettura 19

678 Statistica 28

567 Programmazione 29

456 Matematica 20

892 Diritto 18

892 Economia 19

678 Matematica 28

678 Architettura 30

567 Matematica 27

555 Diritto 21

567 Diritto 21

456 Architettura 19

555 Matematica 18

555 Statistica 20

456 Statistica 18

892 Matematica 20

456 Diritto 19

555 Economia 18

Denominazione Docente

Programmazione Ferro

Architettura Pappalardo

Matematica Lizzio

Diritto Fazio

Informatica Giuffrida

Economia Fazio

Statistica Ricci

Studenti Esami

Corsi

Esempio di analisi

Libro di testo

• Data Mining: Concepts and Techniques,

2nd ed.

– Jiawei Han and Micheline Kamber

– The Morgan Kaufmann Series in Data

Management Systems

Data Mining

• Necessità di analizzare database di grandi dimensioni

• Scoperta di proprietà (pattern) generali, non banali e potenzialmente utili, a partire da un insieme di dati per specifiche applicazioni

• Nomi alternativi – Knowledge discovery (mining) in database (KDD), knowledge

extraction, data/pattern analysis, data archeology, data dredging, information harvesting, business intelligence, etc.

Esempi di applicazioni

• Regole per la concessione di prestiti bancari dall’analisi delle storie precedenti

• Pianificazione di sconti su aerei, alberghi, ecc. dall’analisi dei comportamenti di flussi turistici

• Pianificazione delle attività promozionali in un supermercato

• Disposizioni di articoli in un supermercato dall’analisi dei carrelli della spesa

• Suggerimenti di articoli correlati durante l’acquisto

• Sistemi di fraud detection: carte di credito, furto di SIM, etc.

• => Adattamento di queste tecniche per analisi sociali

Comunità Scientifiche interessate

Data Mining

Database Statistici

Machine Learning

Pattern Recognition

Algoritmi Esperti dominio

Visualizzazione

Fasi del Data-Mining Process

• Data gathering (raccolta dati): – datadase, web search, etc..

• Data Cleaning (pulizia): – Elimina gli errori, le ambiguità

• Feature extraction (estrarre dati significativi): – Mantenere solo gli attributi interessanti dei dati

• Pattern extraction and discovery: – questo e’ il vero e proprio data mining

• Visualization: – Visualizzare i dati in maniera significativa

• Evaluation: – valutare quali fatti scoperti sono utili

Fasi del Data-Mining Process

Data Cleaning

Data Integration

Databases

Data Warehouse

Task-relevant Data

Selection

Data Mining

Pattern Evaluation

Association rules, frequent pattern analysis

• Market-basket problem: – Analisi dei carrelli della spesa per capire quali prodotti

vengono comprati insieme

• Birra e pannolini?!

• Frequent pattern: un pattern (un insieme di item) che si presenta (ripete) frequentemente nei dati

• Questa informazione viene usata, ad esempio, per posizionare i prodotti sugli scaffali o effettuare promozioni coordinate

• Lo stesso concetto viene generalizzato in molti altri contesti, ad esempio: – Letture articoli su quotidiano online

– Risposte questionari

– Acquisto pacchetti di viaggio

Risultati del Mining

• Association Rules: – regole del tipo se un cliente compra x1, …, xk allora

compra anche Y con alta probabilità

• La probabilità minima che noi desideriamo si chiama confidenza. Vogliamo che questa sia decisamente più alta di quella attesa (significatività) – Ad esempio, la regola latte,burro pane potrebbe

derivare dal fatto che quasi tutti comprano pane, mentre la regola pannolinibirra vale con confidenza molto più alta della percentuale di clienti che compra birra

Concetti di base: Association Rule

• Trovare tutte le regole X Y

con «supporto» e «confidenza»

– supporto, s, numero di «carrelli»

che contengono sia X che Y

– confidenza, c, probabilità

condizionata che un carrello che

contiene X contenga anche Y

Frequenze nell’esempio: Birra:3, Noccioline:3,

Pannolini:4, Uova:3, {Birra, Pannolini}:3

• Association rule: – Birra Pannolini (3, 100%) – Pannolini Birra (3, 75%)

Clienti che acquistano

pannolini

Clienti che acquistano

entrambi i prodotti

Clienti che

acquistano birra

Tid Prodotti acquistati

10 Birra, Noccioline, Pannolini

20 Birra, Caffè, Pannolini

30 Birra, Pannolini, Uova

40 Noccioline, Uova, Latte

50 Noccioline, Caffè, Pannolini, Uova, Latte

Insiemi frequenti di articoli

• Nella maggior parte delle applicazioni ci

interessano solo quelle regole che riguardano

insiemi di articoli che appaiono insieme in un’alta

percentuale di carrelli (soglia di supporto)

• La ragione è che le altre non sono statisticamente

affidabili

Algoritmo Apriori - Esempio

Database TDB

1st scan

C1

L1

L2

C2 C2

2nd scan

C3 L3 3rd scan

Tid Item

10 A, C, D

20 B, C, E

30 A, B, C, E

40 B, E

Itemset sup

{A} 2

{B} 3

{C} 3

{D} 1

{E} 3

Itemset sup

{A} 2

{B} 3

{C} 3

{E} 3

Itemset

{A, B}

{A, C}

{A, E}

{B, C}

{B, E}

{C, E}

Itemset sup

{A, B} 1

{A, C} 2

{A, E} 1

{B, C} 2

{B, E} 3

{C, E} 2

Itemset sup

{A, C} 2 {B, C} 2 {B, E} 3 {C, E} 2

Itemset

{B, C, E} Itemset sup

{B, C, E} 2

Supmin = 2

Introduzione alla classificazione

• Classificare dati (creare un modello)

basato su insiemi di apprendimento e

valori degli attributi di un classificatore

• Processo in due fasi

Costruzione del modello

Uso del modello Per classificazioni successive

Classificazione

processo a due fasi

• Costruzione del modello: descrivere un insieme di classi predefinite – Ogni tupla appartiene ad una classe predefinita, questo viene

determinato dall’etichetta dell’attributo classificatore

– L’insieme di tuple usate per costruire il modello è chiamato training set

– Il modello è rappresentato attraverso regole di classificazione, alberi decisionali, formule matematiche,…

• Uso del modello: per classificare nuovi oggetti – Stimare l’accuratezza del modello

• Le etichette note sono confrontate con quelle restituite dal modello

• Il tasso di accuratezza è la percentuale di test del campione che vengono classificati correttamente

– Se l’accuratezza è accettabile il modello può essere usato per classificare dati nuovi

Alberi decisionali

• Gli alberi decisionali sono uno strumento noto

nel machine learning, nella statistica e nel data

mining

• Hanno la forma di un albero rovesciato

• Si costruiscono a partire da una relazione

esistente in cui esiste una, ed una sola,

variabile da classificare (la classe)

• Ogni nodo interno dell’albero contiene un test

che stabilisce quale sottoalbero deve essere

visitato

• Le foglie contengono la «decisione»

Training Dataset

• La relazione in input è

classificata sulla base

di osservazioni

passate

• L’albero generato

serve a fare

«predizioni» sul

futuro, cioè, si cerca

di indovinare la classe

(«Play» nel nostro

caso)

Outlook Temperature Humidity Windy Play?

sunny hot high false N

sunny hot high true N

overcast hot high false Y

rain mild high false Y

rain cool normal false Y

rain cool normal true N

overcast cool normal true Y

sunny mild high false N

sunny cool normal false Y

rain mild normal false Y

sunny mild normal true Y

overcast mild high true Y

overcast hot normal false Y

rain mild high true N

Costruzione albero decisionale, primo passo

sunny

false true

N Y

rain

overcast

Y Y

cool

mild hot

false true

N Y

Y

normal

Y

false true

N Y

temperature

=?

outlook

=? outlook

=?

windy

=?

rain

sunny

overcast

windy

=?

humidity

=?

windy

=?

high

IF (temperature = cool AND outlook = rain AND windy = false) THEN play

overcast

high normal false true

sunny rain

N N Y Y

Y

Outlook

=?

humidity

=?

windy

=?

Albero decisionale, versione finale

overcast

high normal false true

sunny rain

N N Y Y

Y

Outlo

ok

=?

humidi

ty

=?

wind

y

=?

Outlook Tempreature Humidity Windy Play?

overcast hot high false Y

overcast cool normal true Y

overcast mild high true Y

overcast hot normal false Y

rain mild high false Y

rain cool normal false Y

rain cool normal true N

rain mild normal false Y

rain mild high true N

sunny hot high false N

sunny hot high true N

sunny mild high false N

sunny cool normal false Y

sunny mild normal true Y

• La generazione dell’albero passa attraverso varie fasi

• La versione finale è in genere un compromesso tra precisione e

semplicità

Alberi decisionali, considerazioni finali

• Il modello degli alberi decisionali è uno dei

modelli di classificazione più rappresentativi

• Esistono algoritmi molto efficienti per la loro

generazione

• Molto utilizzati in tanti campi

• Altri modelli di classificazione si basano sugli

stessi principi di funzionamento