Strumenti di
supporto alle decisioni
Alessandro Mazzetti
Definizione
Strumento che aiuti l’uomo nel prendere decisioni
•
•
•
•
•
•
•
•
analisi di scenari
simulazione di evoluzione
planning
valutazione del rischio
teoria dei giochi
analisi multivariate ed econometriche
analisi break-even
alberi decisionali
Per decidere bisogna conoscere
Generazione della conoscenza
• Business Intelligence
– ricerca di conoscenza utile e fruibile
• Data Mining
– investigazione di dati per trarne conoscenza
– scoperta di informazioni inattese
• Machine Learning (apprendimento autom.)
– generazione automatica di conoscenza
"Pierino, sei una bestia! Non hai capito niente
della Rivoluzione Francese!".
"Eppure avevo imparato a memoria tutto il
capitolo del libro...".
"Non serve. Hai fatto un lavoro inutile: dovevi
capire, non imparare a memoria!".
Apprendimento
• Capire  Imparare a Memoria
• Capire =
– collegare
– notare
– generalizzare
Tipi di apprendimento
• per spiegazione
– il discente può comunicare col docente
– il discente deve avere una conoscenza pre-esistente
• da esempi
– il discente non ha la conoscenza necessaria per
comunicare col docente
– quello che avviene nei neonati
(imparare a camminare, a parlare, a riconoscere,…)
Apprendimento da esempi =
generalizzazione
• la palla va giù
• il biberon va giù
• l’acqua va giù
RICORDARE
Gli oggetti cadono
CAPIRE
Esempio
Osservare partite a carte
Trarne le regole del gioco
Due forme di conoscenza
• “Imparare a memoria” casi specifici
– occupa tanta memoria
– copre solo i casi enumerati
• la palla cade, la penna cade, la forchetta cade,…
• il termosifone cade ?
• Generalizzare
– forma compatta
– copre anche casi mai visti
• TUTTI gli oggetti cadono (anche i termosifoni)
Conoscenza indotta
•
•
•
•
ieri il sole è tramontato ad ovest
anche l’altroieri
anche settimana scorsa
anche l’anno scorso
Il sole tramonta SEMPRE ad ovest
Quindi anche domani !
Difficoltà
• È molto difficile generalizzare correttamente
– tutti gli italiani mangiano la pizza
– tutti gli uomini sono traditori
– le bionde sono belle
• Una buona generalizzazione deve essere:
– completa (coprire tutti gli esempi positivi)
– consistente (escludere tutti gli esempi negativi)
– significativa (classificare correttamente gli
esempi non visti)
Inferenza e apprendimento
• DEDUZIONE (Aristotele IV secolo a.C.)
IF A THEN B
deduzione (de-duco=portare fuori)
A vero implica B vero
A falso non implica nulla
• INDUZIONE (Hume XVI secolo d.C.)
A vero
A falso
A vero
A falso
B vero
B falso
B vero
B vero
induzione (in-duco=portare dentro)
IF A THEN B (ma non ne sono sicuro)
Proprietà dell’induzione
• La deduzione preserva la verità
– data una conoscenza generale corretta, ottengo
un’informazione particolare corretta
• L’induzione preserva la falsità
– non bastano miliardi di esempi a verificare una
regola
– basta un solo controesempio a falsificare una
regola
Preservazione della falsità
•
•
•
•
Ferrari:
Lamborghini:
Topolino:
Porche:
rossa
rossa
blu
nera
veloce
veloce
lenta
veloce
Le auto rosse sono veloci (può darsi)
• Panda:
rossa
lenta
Rosso NON implica veloce (DI SICURO)
Apprendimento da esempi
• apprendimento supervisionato
– esiste un maestro che conosce il concetto da
apprendere (ma non lo spiega)
– generazione di conoscenza che soddisfi il
comportamento del maestro
• apprendimento non supervisionato
– scoperta da osservazioni
– generazione di conoscenza del tutto autonoma,
notando somiglianze, correlazioni, regolarità
Esempi di apprendimento
supervisionato
• Leggi fisiche
– maestro = Natura
• Relazioni sociali
– maestro = esperienze
• Operazioni finanziarie
– maestro = andamento della Borsa
Esempi di apprendimento
non supervisionato
• Categorizzare le persone
– le donne sono più intuitive degli uomini
– i Capricorni sono cocciuti
• Notare differenze all’estero
– in Francia non si usa il bidet
– gli inglesi fanno la coda uno ad uno
• Correlare attributi
– le piccole cooperative sono tipiche del nord
– gli uomini che comprano pannolini,
comprano anche alcoolici
…in termini più tecnici...
• Apprendimento supervisionato:
– è noto l’attributo da apprendere
– al conoscenza appresa è una regola
statura
capelli
occhi
aspetto
basso
alto
alto
basso
alto
alto
alto
basso
biondi
biondi
rossi
scuri
scuri
biondi
scuri
biondi
blu
scuri
blu
blu
blu
blu
scuri
scuri
bello
brutto
bello
brutto
brutto
bello
brutto
brutto
Concetto da apprendere
se capelli=rossi
se capelli=scuri
allora aspetto=bello
allora aspetto=brutto
…in termini più tecnici...
• Apprendimento NON-supervisionato:
– non è noto l’attributo da apprendere
– al conoscenza appresa è una tassonomia
statura
capelli
occhi
aspetto
basso
alto
alto
basso
alto
alto
alto
basso
biondi
biondi
rossi
scuri
scuri
biondi
scuri
biondi
blu
scuri
blu
blu
blu
blu
scuri
scuri
bello
brutto
bello
brutto
brutto
bello
brutto
brutto
si assomigliano
(alto, occhi-blu)
Esiste la categoria degli alti cogli occhi blu
Cosa c’è alla base
• Una grande quantità di dati
• raccolti per altri motivi
• organizzati in maniera adeguata
DATA WAREHOUSE
Generazione di alberi decisionali
• ID3 (Iterative Dichotomizer)
– Ross Quinlan (1982)
• derivato da CLS (Concept Learning System)
– Hunt (1966)
• Input = tabella
• Output = procedura decisionale
rappresentabile come:
– regole
– albero
– procedura
Albero generato da ID3
statura
capelli
occhi
aspetto
basso
alto
alto
basso
alto
alto
alto
basso
biondi
biondi
rossi
scuri
scuri
biondi
scuri
biondi
blu
scuri
blu
blu
blu
blu
scuri
scuri
bello
brutto
bello
brutto
brutto
bello
brutto
brutto
L’idea base di ID3
• cercare l'attributo piu' simile al concetto da
apprendere (cioe' la colonna "bellezza")
• considerare la frequenza di ogni valore
possibile ("alto", "basso",...)
• scegliere l’attributo che discrimina meglio
• ripartire daccapo considerando la sottotabella rimanente
• finché ottengo una sotto-tabella vuota
Teoria dell’informazione di Shannon
• su 8 esempi, 3 sono di belli e 5 di brutti
-3/8 log 3/8
2
- 5/8 log 5/8
2
= 0.954 bit
• quindi ho un'informazione di 0.954 bits
• Quanto conta la statura?
– media pesata degli alti belli rispetto ai brutti belli
5/8 * 0.971 + 3/8 * 0.918 = 0.951 bit
• L’attributo che conta di più è “capelli”
• Si genera il nodo “capelli” e si riparte
Esercizio
• Visitare
http://www.planasia.it/DemoMine.html
• definire interattivamente il concetto da far
apprendere
• analizzare le tre forme di conoscenza
generata
• Riuscite a generare la regola “sei malato se
hai la febbre oppure se starnutisci” ?
Apprendimento non-supervisionato
• sistema in grado di creare tassonomie a partire
da un insieme di dati "sciolti"
• vengono notate le similarita’ fra i dati
• viene scoperta l'esistenza di categorie
• si forma una partizione (clustering) dei dati
• i dati appartenenti alla stessa classe si
assomigliano fra di loro
Tassonomia
Apprendimento incrementale
Progetti storici
• "Cluster" (R. Michalski, 1983),
• "Unimem" (M. Lebowitz, 1986),
• "Cobweb" (D. Fisher, 1987)
• approfondiamo Unimem
L’input è una tabella “disordinata”
fiat_tipo
renault_clio
jeep
subaru_legacy
renault_19
toyota_4x4
citroen_zx
opel_omegaSW
rolls_royce
peugeot_205
range_rover
vw_golf
fiat_uno
porshe
fiat_tempra_SW
renault_nevada
mercedes_500
ferrari
cc1600, abbordabile, posti(5), porte(5), consumo(medio)
economica, corta, cc1200, posti(5), porte(3), consumo(basso)
non_veloce, cc2000, alta, porte(5), cara, consumo(alto)
lunga, cara, veloce, cc2000, posti(5), consumo(medio), vol2
abbordabile, cc1400, posti(5), porte(5), consumo(medio)
cara, non_veloce, cc2500, alta, porte(5), consumo(alto)
abbordabile, cc1600, posti(5), porte(5), consumo(medio)
cara, veloce, lunga, cc2000, posti(5), consumo(medio), vol2
carissima, lunga, vol3, posti(5), porte(4), consumo(alto)
corta, cc1000, posti(5), economica, porte(3), consumo(basso)
cara, alta, cc2500, posti(6), porte(5), consumo(alto)
abbordabile, cc1600, posti(5), porte(5), consumo(medio)
economica, cc1100, posti(5), porte(3), consumo(basso)
carissima, velocissima, cc3600, posti(2), porte(2), consumo(alto)
lunga, cara, veloce, cc1800, consumo(medio), vol2
cara, veloce, cc2000, posti(7), consumo(medio), lunga, vol2
carissima, vol3, cc5000, posti(5), porte(4), consumo(alto)
carissima, velocissima, cc5000, posti(2), porte(2), consumo(alto)
Cos’ha scoperto ?
radice [ ]
range_rover renault_nevada
classe_a [abbordabile,posti(5),porte(5),consumo(medio)]
renault_19 /* e' una 1400 cc */
classe_c [cc1600]
fiat_tipo citroen_zx vw_golf
classe_b [cara,non_veloce,alta,porte(5),consumo(alto)]
jeep toyota_4x4
classe_d [cara,veloce,lunga,cc2000,posti(5),consumo(medio),vol2]
subaru_legacy opel_omegaSW fiat_tempra_SW
classe_e [corta,posti(5),economica,porte(3),consumo(basso)]
renault_clio peugeot_205 fiat_uno
classe_f [carissima,vol3,posti(5),porte(4),consumo(alto)]
rolls_royce mercedes_500
classe_g [carissima,velocissima,posti(2),porte(2),consumo(alto)]
porshe ferrari
Cos’ha scoperto ? I tipi di auto !
radice [ ]
range_rover renault_nevada
/* non classificate */
classe_a [abbordabile,posti(5),porte(5),consumo(medio)]
renault_19 /* e' una 1400 cc */
/* berline */
classe_c [cc1600]
fiat_tipo citroen_zx vw_golf
classe_b [cara,non_veloce,alta,porte(5),consumo(alto)]
jeep toyota_4x4
/* fuoristrada */
classe_d [cara,veloce,lunga,cc2000,posti(5),consumo(medio),vol2]
subaru_legacy opel_omegaSW fiat_tempra_SW
/* familiari */
classe_e [corta,posti(5),economica,porte(3),consumo(basso)]
renault_clio peugeot_205 fiat_uno
/* utilitarie */
classe_f [carissima,vol3,posti(5),porte(4),consumo(alto)]
rolls_royce mercedes_500
/* lussuose */
classe_g [carissima,velocissima,posti(2),porte(2),consumo(alto)]
porshe ferrari
/* sportive */
Metrica
• È alla base dell’apprendimento nonsupervisionato
• misura quanto si assomigliano due casi
• metrica forte
– [a,b,c,d] assomiglia ad [x,d,c,b] ma non a [d,b]
• metrica debole
– [a,b,c,d] assomiglia ad [x,d,y,b] ma non a [b]
Conclusioni
• Apprendimento = generazione di conoscenza
• Utile per supportare le decisioni
• Campi d’applicazione
–
–
–
–
–
segmentazione del mercato (supermarket, banche,…)
investigazione di frodi (clonazione cellulari,…)
manutenzione preventiva (guast frequenti,…)
valutazione del rischio (ambientale, finanziario,…)
previsione di consumo (energetico, beni,…)