Sistemi di supporto alle decisioni
Ing. Leonardo Rigutini, Ph.D.
Dipartimento di Ingegneria dell’Informazione
Università di Siena
[email protected]
http://www.dii.unisi.it/ ~rigutini/
Introduzione
L’informazione è un bene a valore crescente, necessario per
pianificare e controllare le attività produttive:
costituisce la materia prima che viene trasformata dai sistemi informativi
Come è noto ai Web navigator l’equazione dati = informazione
non è sempre corretta:
spesso la disponibilità di troppi dati rende arduo, se non impossibile,
estrarre informazioni significative
Sistemi per l’estrazione, l’analisi e l’organizzazione automatica di
queste enormi moli di dati possono fornire un supporto nei
processi decisionali umani:
sistemi di supporto alle Decisioni (DSS)
Sistemi di supporto alle decisioni - Leonado Rigutini
Introduzione - 2
In particolare, i DSS nascono a seguito dell’enorme accumulo di
dati registrato nell’ultimo ventennio in forma elettronica, e dalla
pressante richiesta di utilizzo di tali dati per scopi che superano
quelli legati all’elaborazione giornaliera
Tali sistemi aiutano il decisore umano sia nelle decisioni
operative, che nelle decisioni strategiche, a più lungo termine ed a
più ampio respiro
Sistemi di supporto alle decisioni - Leonado Rigutini
Introduzione - 3
Applicazioni
Commercio  analisi delle vendite e dei reclami, controllo di
spedizioni ed inventari, cura del rapporto con i clienti
Manifattura  controllo dei costi di produzione, supporto
fornitori e ordini
Servizi finanziari  analisi del rischio, analisi utilizzo delle
carte di credito, rilevamento di frodi
Trasporti  gestione parco mezzi, gestione carico e
distribuzione
Telecomunicazioni  analisi del flusso delle chiamate e del
profilo dei clienti
Sanità  analisi di ricoveri e dimissioni, contabilità per centri
di costo
Sistemi di supporto alle decisioni - Leonado Rigutini
Introduzione - 4
L’utilizzo dei DSS non è ristretto in ambito aziendale e d’impresa:
spazia dall’area medicoepidemiologica a quella demografica, dalle
scienze naturali alla didattica
Caratteristica comune ai diversi ambiti è la necessità di strumenti
di archiviazione e di interrogazione, per ottenere, dall’enorme
quantità di dati contenuti nei database o resi disponibili da
Internet...
informazioni di sintesi che permettano la valutazione di un fenomeno
la scoperta di correlazioni significative
l’acquisizione di conoscenza utile a stabilire una strategia decisionale
Sistemi di supporto alle decisioni - Leonado Rigutini
Sistemi di supporto alle decisioni - 1
La funzione svolta dalle basi di dati in ambito aziendale è stata,
fino a tempi recenti, quella di memorizzare dati operazionali,
ossia dati generati da operazioni, in genere di carattere
amministrativo, svolte all’interno dei processi gestionali (gestione
acquisti, gestione vendite, fatturazione)
Tuttavia, per ogni azienda, è fondamentale poter disporre in
maniera rapida e completa delle informazioni necessarie al
processo decisionale:
le indicazioni strategiche sono estrapolate dalla mole dei dati operazionali,
attraverso un procedimento di selezione e sintesi progressiva
Sistemi di supporto alle decisioni - Leonado Rigutini
Sistemi di supporto alle decisioni - 2
L’aumento esponenziale del volume dei dati operazionali ha reso
il calcolatore l’unico supporto adatto al processo decisionale
Il ruolo delle basi di dati è sensibilmente cambiato, dalla fine
degli anni `80, con la nascita dei DSS
Nasce il data warehouse: una raccolta di dati integrata, subject
oriented, variabile nel tempo e non volatile di supporto ai
processi decisionali
Sistemi di supporto alle decisioni - Leonado Rigutini
Sistemi di supporto alle decisioni - 3
Un sistema informativo “converte dati in informazioni”,
ed ha lo scopo precipuo di collezionare, trasformare e
distribuire informazione:
Es. search engine
Un sistema di supporto alle decisioni è un sistema
informativo “intelligente” che aiuta l’utente a prendere
decisioni, senza sostituirsi ad esso
Sistemi di supporto alle decisioni - Leonado Rigutini
Sistemi di supporto alle decisioni - 4
Il DSS, attraverso procedure interattive, fornisce al decisore:
la disponibilità di tutte le informazioni necessarie per la comprensione del
problema
la possibilità di esplorare i dati secondo diversi punti di vista, in base alle
esigenze dello stesso utente
la possibilità di valutare gli scenari conseguenti alle scelte compiute
I DSS si adattano al trattamento di problemi strutturati o
semistrutturati, per i quali non è possibile fornire una soluzione
algoritmica
Sistemi di supporto alle decisioni - Leonado Rigutini
Sistemi di supporto alle decisioni - 5
Tra le problematiche da affrontare per la realizzazione di un
sistema di supporto alle decisioni ricordiamo la necessità di...
…gestire grandi moli di dati
…accedere a diverse fonti di dati su piattaforme eterogenee
…garantire l’accesso a più utenti  con compiti differenziati 
per interrogazioni, analisi in tempo reale e simulazioni
…gestire versioni storiche dei dati
Sistemi di supporto alle decisioni - Leonado Rigutini
Obiettivi di un DSS
Permettere l’estrazione di informazione da grandi database, in
tempi brevi ed in modo flessibile, per supportare e migliorare il
processo decisionale
Necessità di separare i dati generati dalle operazioni di
gestione (operational database) dai dati utili ai processi
decisionali (data warehouse)
Data warehouse  contiene un sottoinsieme dei dati
mantenuti nell’operational database, ottimizzato per analisi
focalizzate ai processi decisionali
Nell’operational database e nel data warehouse i dati sono
memorizzati a livelli diversi di aggregazione
Capacità di analisi dei dati contenuti nel data warehouse in tempo
reale e da diversi punti di vista
Sistemi di supporto alle decisioni - Leonado Rigutini
Data Warehous
Data warehouse - 1
Integrazione
Nel data warehouse confluiscono dati provenienti da più
sistemi transazionali e da fonti esterne
L’obiettivo dell’integrazione viene raggiunto mediante
l’utilizzo di metodi di codifica uniformi
Orientamento al soggetto
I dati vengono archiviati per poter essere facilmente reperiti ed
analizzati dagli utenti
Non si mira a minimizzare la ridondanza, ma piuttosto a
fornire dati che abbiano una struttura in grado di favorire la
produzione di informazioni
Sistemi di supporto alle decisioni - Leonado Rigutini
Data warehouse - 2
Variabilità nel tempo
Nel DW sono contenute informazioni relative alle aree di
interesse che colgono la situazione relativa ad un dato
fenomeno in un determinato intervallo temporale
(generalmente antecedente all’interrogazione)
Non volatilità
Non modificabilità dei dati contenuti nel DW, che consente
accessi in sola lettura
Semplicità di progettazione: non si ricorre a strumenti
complessi per gestire l’integrità referenziale o per bloccare
record cui possono accedere più utenti in fase di
aggiornamento
Sistemi di supporto alle decisioni - Leonado Rigutini
Data warehouse - 3
Pertanto, il DW contiene i dati necessari ai processi decisionali
L’operational database è aggiornato costantemente: deve “fotografare”
l’istante corrente
Il DW contiene i dati aggregati in particolari istanti di tempo (es. dati
settimanali, mensili, trimestrali)
Nel DW, i dati che provengono dall’operational database devono essere
integrati con i dati relativi all’ambiente esterno (che condizionano il
processo decisionale)
Il DW è una sorta di storico che raccoglie istantanee significative
dell’operational database, o meglio…
…è una collezione di metodi, tecnologie e strumenti di ausilio al knowledge
worker (amministratore, gestore, analista, dirigente) per condurre analisi dei
dati finalizzate all’attuazione di processi decisionali e al miglioramento del
patrimonio informativo
Sistemi di supporto alle decisioni - Leonado Rigutini
Data warehouse - 4
Mario Rossi
Via Diotisalvi, 2
Pisa
10.000
Operational
Database
Mario Rossi
Mario Rossi
5000€
Mario15000€
Rossi
10000€
Web
Sistemi di supporto alle decisioni - Leonado Rigutini
Data Warehouse
Data mining
Knowledge Data Discovery - 1
Gli stadi che caratterizzano un processo KDD sono stati
identificati da Fayyad, PiatetskyShapiro, Smyth e Uthurusamy
(1996)
Nell’elencare e descrivere le fasi del KDD, tale ricerca ha
posto particolare accento sulla fase di Data Mining (DM), cioè
sulle tecniche per l’esplorazione e lo studio dei dati
Il DM è ritenuta la fase più importante dell’intero processo
KDD e tale importanza rende sempre più difficile, soprattutto
in termini pratici, distinguere il processo KDD dal DM
Sistemi di supporto alle decisioni - Leonado Rigutini
Knowledge Data Discovery - 2
Il processo KDD prevede in input “dati grezzi” e fornisce in
output informazioni utili ottenute attraverso le fasi di:
Selezione
Preprocessing
Trasformazione dei dati
Data mining
Interpretazione e valutazione
Sistemi di supporto alle decisioni - Leonado Rigutini
Knowledge Data Discovery - 3
dati
dati selezionati
dati elaborati
dati trasformati
Selezione
Preprocessing
pattern
Trasformazione
dei dati
conoscenza
DATA MINING
Interpretazioni e
valutazioni
Sistemi di supporto alle decisioni - Leonado Rigutini
Knowledge Data Discovery - 4
Selezione
I dati raw vengono segmentati e selezionati secondo criteri
predefiniti, per pervenire ad un sottoinsieme di dati che
rappresentano i target data o dati obiettivo; il database
operazionale può contenere informazioni inutili per il
problema specifico
Esempio: se l’obiettivo è lo studio delle associazioni tra i
prodotti di una catena di supermercati, non ha senso
conservare i dati relativi alla professione dei clienti; tali dati
potrebbero invece fornire informazioni d’interesse relative al
comportamento di determinate fasce di clienti, per effettuare
un’analisi discriminante
Sistemi di supporto alle decisioni - Leonado Rigutini
Knowledge Data Discovery - 5
Preprocessing
Spesso, pur avendo a disposizione i dati obiettivo non è
conveniente, né necessario, analizzarne l’intero contenuto;
occorre prima campionare le tabelle e, successivamente,
effettuare un’analisi su base campionaria
Fa inoltre parte dello stadio di preprocessing la fase di pulizia
dei dati, o data cleaning, che prevede l’eliminazione dei
possibili errori e la definizione dei meccanismi di
comportamento in caso di dati mancanti
Sistemi di supporto alle decisioni - Leonado Rigutini
Knowledge Data Discovery - 6
Trasformazione dei dati
Dopo il preprocessing, i dati, per essere utilizzabili, devono
essere trasformati
Si possono effettuare conversioni di tipo o definizioni di
nuovi dati ottenuti attraverso l’uso di operazioni
matematiche e logiche sulle variabili
Inoltre, quando i dati provengono da fonti diverse, è
necessario codificarli omogeneamente, per garantirne la
consistenza
Sistemi di supporto alle decisioni - Leonado Rigutini
Knowledge Data Discovery - 7
Data mining
Ai dati trasformati vengono applicate tecniche per l’estrazione
di informazione non banale: i tipi di dati a disposizione e gli
obiettivi da raggiungere indicano implicitamente il tipo di
algoritmo DM da scegliere
Il processo KDD è:
interattivo, presuppone infatti un “dialogo” costante tra l’utente e il
software utilizzato
iterativo, nel senso che la fase di DM può prevedere un’ulteriore
trasformazione dei dati originali o un’ulteriore pulizia dei dati, ovvero
una riesecuzione delle fasi preliminari
Sistemi di supporto alle decisioni - Leonado Rigutini
Knowledge Data Discovery - 8
Interpretazione e valutazione
Il DM crea dei pattern, ovvero dei modelli, che possono
costituire un valido supporto alle decisioni
Non è sufficiente, tuttavia, interpretare i risultati ottenuti, ma
occorre utilizzarli per validare i modelli (dati e algoritmi)
È dunque possibile, alla luce di risultati non perfettamente
soddisfacenti, intervenire (in maniera sia adattiva che
perfettiva) su una o più fasi del processo KDD
Sistemi di supporto alle decisioni - Leonado Rigutini
Data mining - 1
Con Data Mining si indica l’attività di individuazione automatica
ed estrazione di informazioni, quali relazioni ed associazioni tra i
dati, precedentemente sconosciute all’utente
Principali tecniche per il data mining:
Sistemi a regole
Algoritmi di clustering
Algoritmi genetici
Reti neurali e Support Vector Machine (SVM)
Sistemi di supporto alle decisioni - Leonado Rigutini
Data mining - 2
Il data mining è l’estrazione non banale di informazione
implicita, precedentemente sconosciuta e potenzialmente utile,
attraverso l’utilizzo di differenti approcci tecnici (Frawley,
PiatetskyShapiro e Matheus, 1991)
Il data mining è una combinazione di tecniche potenti che aiutano
a ridurre i costi e i rischi e ad aumentare le entrate, estraendo
informazione dai dati disponibili (T. Fahmy)
Il data mining consiste nell’uso di tecniche statistiche da
utilizzare con i database aziendali per scoprire modelli e relazioni
che possono essere impiegati in un contesto di business (Trajecta
lexicon)
Sistemi di supporto alle decisioni - Leonado Rigutini
Data mining - 3
Il data mining è l’esplorazione e l’analisi, attraverso mezzi
automatici e semiautomatici, di grosse quantità di dati allo scopo
di scoprire modelli e regole significative (Berry e Linoff, 1997)
Il data mining è la ricerca di relazioni e modelli globali che sono
presenti in grandi database, ma che sono nascosti nell’immenso
ammontare di dati. Tali relazioni rappresentano una preziosa
conoscenza del database e, se il database è uno specchio fedele,
del mondo reale che esso descrive (Holshemiere e Siebes, 1994)
Sistemi di supporto alle decisioni - Leonado Rigutini
Data mining - 4
Il termine Knowledge Data Discovery (KDD) si riferisce
all’intero processo, interattivo ed iterativo, di scoperta della
conoscenza, che consiste nella identificazione di relazioni tra dati
che siano valide, nuove, potenzialmente utili e comprensibili
I dati sono una collezione di fatti F (per esempio tuple di una
tabella di un database relazionale)
Una relazione, o modello, o pattern, è un’espressione E in un
linguaggio L che descrive fatti in un sottoinsieme FE di F; una
relazione deve essere più semplice, rispetto ad un dato criterio
di semplicità, dell’enumerazione di tutti i fatti in FE
Sistemi di supporto alle decisioni - Leonado Rigutini
Data mining - 5
Un processo di scoperta della conoscenza è un insieme di attività
che coinvolgono la preparazione dei dati, la ricerca di relazioni, la
valutazione e il raffinamento della conoscenza estratta
Si assume che il processo sia non banale, cioè che le relazioni
scoperte non siano già note
Le relazioni scoperte sono valide se valgono, con un grado di
certezza prefissato, anche su dati diversi da quelli usati per la
scoperta delle stesse
Individuare un “grado di certezza” è essenziale per stabilire
quanta fiducia si può riporre nel sistema e nella relazione
estratta
Sistemi di supporto alle decisioni - Leonado Rigutini
Data mining - 6
Le relazioni scoperte devono essere nuove almeno per il sistema,
devono cioè aumentare la conoscenza necessaria ad affrontare il
problema decisionale
Le relazioni dovrebbero potenzialmente condurre a delle azioni
utili; per esempio, la scoperta di una dipendenza fra articoli
acquistati da uno stesso cliente in un supermercato potrebbe
attivare opportune strategie di marketing
I pattern devono essere comprensibili agli utenti per facilitare una
migliore conoscenza dei fatti coinvolti
Poiché è difficile misurare “la comprensibilità di un pattern”
spesso si ricorre a misure surrogate di semplicità
sintattica/semantica
Sistemi di supporto alle decisioni - Leonado Rigutini
Data mining - Esempio
Prestiti
o
x
x
x
x
x
x
x
x
x
x
x
x
x
o
x
o
o
o
o
o
x
o
o
o
o
o
o o o
o
Stipendio
Persone che hanno ricevuto un prestito dalla banca:
x: persone che hanno mancato la restituzione di rate
o: persone che hanno rispettato le scadenze
Sistemi di supporto alle decisioni - Leonado Rigutini
Data mining - Esempio
Prestiti
o
x
x
x
x
x
x
x
x
x
x
x
x
o
x
o
o
o
o
x
o
x
o
o
o
o
o
o o o
o
k
Stipendio
IF stipendio < k THEN mancati pagamenti
Sistemi di supporto alle decisioni - Leonado Rigutini
Data mining - esempio
Validità
I pattern scoperti devono essere validi su nuovi dati con un grado
di certezza prestabilito: lo spostamento a destra del valore di k
porta riduzione del grado di certezza
Utilità
Aumento di profitto atteso dalla banca associato alla regola
estratta
Sistemi di supporto alle decisioni - Leonado Rigutini
Data mining: tecniche di analisi - 1
La scelta del particolare algoritmo di data mining dipende
dall’obiettivo da raggiungere e dal tipo di dati da analizzare
1) Regole di associazione
2) Classificazione
3) Clustering
4) Similarity search
Sistemi di supporto alle decisioni - Leonado Rigutini
Data mining: tecniche di analisi - 2
Le tecniche di clustering e le reti neurali non supervisionate
consentono il “raggruppamento di dati”, cioè l’individuazione di
gruppi omogenei, che presentano delle regolarità al loro interno,
in grado di caratterizzarli e differenziarli dagli altri gruppi
Le reti neurali supervisionate, le support vector machine e gli
alberi di decisione consentono di effettuare operazioni di
classificazione, fanno cioè uso della conoscenza acquisita in fase
di addestramento per classificare nuovi oggetti o prevedere nuovi
eventi
Le tecniche di analisi delle associazioni consentono di individuare
regole nelle occorrenze concomitanti di due o più eventi
Sistemi di supporto alle decisioni - Leonado Rigutini
Applicazione del DM - 1
Indagini di mercato (Database Marketing)  applicazione di
tecniche di clustering per individuare gruppi omogenei in termini
di comportamento d’acquisto e di caratteristiche
sociodemografiche; l’individuazione delle diverse tipologie di
clienti...
...permette di effettuare campagne di marketing mirate e di valutarne gli
effetti
...permette di ottenere indicazioni su come modificare la propria offerta
...rende possibile monitorare nel tempo l’evoluzione della propria clientela
e l’emergenza di nuove tipologie
Analisi testuale (Text Mining)  applicazione di tecniche di
clustering per individuare gruppi omogenei di documenti in
termini di argomento trattato; consente di accedere più
velocemente all’argomento di interesse e di individuarne i legami
con argomenti correlati
Sistemi di supporto alle decisioni - Leonado Rigutini
Applicazione del DM - 2
Analisi del “paniere” (Basket Analysis)  applicazione di
tecniche di individuazione di associazioni a dati di vendita per
conoscere quali prodotti vengono acquistati congiuntamente
Consente di migliorare l’offerta dei prodotti (disposizione sugli scaffali) e
di incrementare le vendite di particolari prodotti tramite offerte su generi
associati
Technology Watch (Competitive Intelligence)  applicazione di
tecniche di clustering a banche dati di tipo tecnicoscientifico al
fine di individuare i gruppi tematici principali, le loro relazioni,
l’evoluzione temporale, le persone o le aziende coinvolte
Sistemi di supporto alle decisioni - Leonado Rigutini
Regole di associazione
Regole di associazione - 1
Dati del problema:
I  insieme di item
Esempio: prodotti venduti da un supermercato
transazione T  insieme di item t.c. T  I
Esempio: oggetti acquistati nella stessa transazione di
cassa al supermercato
base di dati D  insieme di transazioni
Sistemi di supporto alle decisioni - Leonado Rigutini
Regole di associazione - 2
Regola di associazione:
X  Y dove X,Y  I
Supporto - rilevanza statistica:

# (X Y) ˆ
S(X,Y) 
 P(X,Y)
#I
Confidenza - importanza dell’implicazione:

notare che:

# (X Y) ˆ
C(X,Y) 
 P(Y | X)
#X
S(X,Y )
C(X,Y ) 
S(X)
Sistemi di supporto alle decisioni - Leonado Rigutini
Regole di associazione - esempio 2
Transazioni:
Acquisto 1: A,B,C
Acquisto 2: A,C
Acquisto 3: A,D
Acquisto 4: B,E,F
Regole ottenute:
AC
supporto 50% e confidenza 66.6%
C A
supporto 50% e confidenza 100%
Sistemi di supporto alle decisioni - Leonado Rigutini
Esempi di applicazione
Analisi market basket
  Uova
cosa si deve promuovere per aumentare le vendite di uova?
Latte  
quali altri prodotti devono essere venduti da un supermercato che
vende latte?
Dimensione del problema:
oggetti: 105, transazioni: > 106
base di dati: 10100 GB
Sistemi di supporto alle decisioni - Leonado Rigutini
Regole di associazione - Esempio 1
Latte  Uova
Supporto:
il 2% delle transazioni contiene entrambi gli elementi (latte e uova)
Confidenza:
il 30% delle transazioni che contengono latte contiene anche uova
Sistemi di supporto alle decisioni - Leonado Rigutini
Decomposizione del problema
Passo1:
Trovare tutti gli insiemi di item che hanno supporto maggiore
di una soglia pefissata  frequent itemset
Passso 2:
Generazione delle regole a partire dai frequent itemset
Algoritmo fondamentale:
APRIORI (Agrawal et al., 1994)
Sistemi di supporto alle decisioni - Leonado Rigutini
Esempio decomposizione - 1
Passo 1:
estrazione frequent itemset
Transazioni
Acquisto 1: A,B,C
Acquisto 2: A,C
Acquisto 3: A,D
Acquisto 4: B,C,D
Frequent itemset
Supporto
{A}
{B}
{C}
{A,C}
75%
50%
50%
50%
Sistemi di supporto alle decisioni - Leonado Rigutini
Esempio decomposizione - 2
Passo 2  estrazione regole
confidenza minima 50%
Esempio:
regola A  C
supporto {A,C} = 50%
confidenza = supporto{A,C}/supporto{A} = 66.6%
regole estratte
A  C supporto 50%, confidenza 66.6%
C  A supporto 50%, confidenza 100%
Sistemi di supporto alle decisioni - Leonado Rigutini
Importanza delle regole estratte - 1
Non tutte le regole con supporto e confidenza superiori ad una
soglia prestabilita sono interessanti
Esempio:
scuola con 5000 studenti
60% (3000) gioca a pallacanestro
75% (3750) mangia fiocchi di mais a colazione
40% (2000) gioca a pallacanestro e mangia fiocchi di mais a
colazione
Sistemi di supporto alle decisioni - Leonado Rigutini
Importanza delle regole estratte - 2
Con supporto min. 40% e confidenza min. 60%:
gioca a pallacanestro  mangia fiocchi di mais
supporto = 2000/5000 = 0.4
confidenza = 2000/3000 = 0.66 > 0.6
 regola fuorviante perché il 75% degli studenti mangia fiocchi di
mais !
Nuova “misura”:
S(A,B)
M
 S(B)
S(A)
Sistemi di supporto alle decisioni - Leonado Rigutini
Clustering
Clustering
Data una base di dati di oggetti:
Suddividere gli oggetti in gruppi, in modo che…
...oggetti appartenenti allo stesso gruppo siano molto simili
...oggetti in gruppi diversi siano molto diversi
I gruppi possono essere disgiunti (hard clustering),
parzialmente sovrapposti (soft clustering) oppure
organizzati gerarchicamente (hierarchical clustering)
Sistemi di supporto alle decisioni - Leonado Rigutini
Esempi di applicazioni
Identificazione di popolazioni omogenee di clienti in basi di dati di marketing
Valutazione dei risultati di esperimenti clinici
Monitoraggio dell’attività di aziende concorrenti
Identificazione di geni con funzionalità simili
Nel WWW…
Classificazione di documenti
Identificazione di gruppi di utenti (in base ai file di log) con caratteristiche
di “navigazione” simili
Sistemi di supporto alle decisioni - Leonado Rigutini
Esempi di applicazioni
La tecniche di clustering vengono utilizzate generalmente quando si
hanno dati eterogenei e si è alla ricerca di elementi anomali: le
compagnie telefoniche utilizzano il clustering per individuare in
anticipo gli utenti che diventeranno morosi
Normalmente, tali utenti hanno un comportamento nettamente
diverso rispetto alla maggioranza degli utenti telefonici e le tecniche
di clustering riescono sovente ad individuarli o, comunque,
definiscono un cluster dove vengono concentrati tutti gli utenti che
hanno un’elevata probabilità di diventare morosi
Sistemi di supporto alle decisioni - Leonado Rigutini
Case study: k-Means - 1
Caratteristiche:
Appartiene ai metodi di tipo partitioning
Dato un intero k, si calcola un partizionamento dei dati in
ingresso in k cluster, che ottimizza il criterio di
partizionamento scelto
Kmeans (MacQueen, 1967): ogni cluster è rappresentato dal
centro (media) del cluster
La scelta iniziale dei k centroidi viene effettuata in maniera
casuale
Sistemi di supporto alle decisioni - Leonado Rigutini
Case study: k-Means - 2
1. Scegli i k centri iniziali
2. Repeat
Assegna ciascun oggetto al cluster più vicino (il cui centro risulta il più
vicino all’oggetto dato)
2. Calcola i centroidi (punti medi) dei cluster
1.
until gli assegnamenti non cambiano (o cambiano poco)
Viene minimizzato l’errore
quadratico medio
E K   xk  mc ( xk )
k
Sistemi di supporto alle decisioni - Leonado Rigutini
2
Case study: k-Means - 3
Limiti di Kmeans:
Può essere applicato solo se il tipo di dato permette di definire
la media
Occorre specificare in anticipo il numero k di cluster
Sebbene sia possibile dimostrare che il procedimento termina
sempre, non è detto che venga raggiunto il minimo globale (il
risultato è influenzato dalla scelta dei centri iniziali)
Non garantisce la connessione dei cluster trovati e l’assenza di
punti isolati
Può produrre risultati scadenti quando…
…i cluster hanno differenti dimensioni, densità, forma non globulare
…i dati contengono outlier
Sistemi di supporto alle decisioni - Leonado Rigutini
Case study: k-Means - 4
Soluzione: usare molti cluster
In questo caso…
…i cluster calcolati sono partizioni dei cluster effettivamente
presenti
…è necessario fondere i cluster calcolati
Sistemi di supporto alle decisioni - Leonado Rigutini
Case study: k-Means - 5
Tuttavia... il mondo reale non è “crisp”
Effettuando il clustering non è sempre possibile definire in
maniera precisa se un punto appartiene ad un cluster oppure ad un
altro
Sistemi di supporto alle decisioni - Leonado Rigutini
Case study: SOM - 1
Il clustering può anche essere interpretato come una forma di
classificazione non supervisionata
Come tale, può essere realizzato mediante un particolare tipo di
architettura neurale, chiamata SelfOrganizing Map (SOM), che
viene addestrata in modalità non supervisionata, cioè non
conoscendo l’output atteso per ciascun dato in input
Sistemi di supporto alle decisioni - Leonado Rigutini
Case study: SOM - 2
La SOM sarà comunque in grado, al termine della fase di
apprendimento, di raggruppare i dati in cluster, ovvero di produrre
output simili per input “vicini”, secondo una qualche metrica
nello spazio degli ingressi
Sistemi di supporto alle decisioni - Leonado Rigutini
Similarity search
Data un base di dati di sequenze temporali o oggetti, determinare:
Sequenze/oggetti simili ad una sequenza/oggetto data/o
Tutte le coppie di sequenze/oggetti simili
Due tipi di interrogazione:
Matching completo  la sequenza cercata e le sequenze della
base di dati hanno la stessa lunghezza
Matching parziale  la sequenza cercata può essere
sottosequenza di quelle recuperate dalla base di dati
Sistemi di supporto alle decisioni - Leonado Rigutini
Esempi di applicazioni
Identificazione delle società con comportamento simile di crescita
Determinazione di prodotti con profilo simile di vendita
Identificazione di azioni con andamento simile
Individuazione porzioni di onde sismiche non simili per
determinare irregolarità geologiche
Ricerca in database visuali
Allineamento di sequenze di acidi nucleici e proteine
Sistemi di supporto alle decisioni - Leonado Rigutini
Metriche di similarità
Definita la modalità di descrizione di sequenze/ oggetti da ricercare, è
necessario definire una metrica da usare per valutarne la similarità, in base alla
distanza tra i rispettivi descrittori
La metrica dovrebbe rispettare la “percezione” del concetto di similarità:
descrittori “vicini” corrispondono a sequenze/oggetti simili
Una metrica d(x,y), definita su uno spazio S, è una funzione che associa uno
scalare a coppie di elementi in S, con le seguenti proprietà:
Non negatività: d(x,y)  0
Riflessività: d(x,y) = 0 sse x=y
Simmetria: d(x,y) = d(y,x)
Disuguaglianza triangolare: d(x,y)+d(y,z)  d(x,z)
Sistemi di supporto alle decisioni - Leonado Rigutini

Metriche vettoriali
In generale, una metrica di similarità per pattern in n è la
metrica di Minkowsky, nota anche come metrica Lk:
d(x, y) 
n
k
(x
 y i ) , x, y  
k
i
n
i1
Per k=1 si ha la distanza di Manhattan o cityblock
Per k=2 si ha la distanza Euclidea
Sistemi di supporto alle decisioni - Leonado Rigutini
Metriche per dati strutturati
Per il confronto tra grafi si definisce una distanza tra nodi del
grafo ed una distanza tra gli archi
Generalmente, infatti, all’interno dei nodi del grafo si
rappresentano caratteristiche locali delle singole regioni mentre
con gli archi si descrivono le relazioni spaziali
Per calcolare una distanza si dovranno tenere presenti sia le
relazioni spaziali che le caratteristiche locali delle regioni
Il problema è complicato perché spesso i grafi da confrontare
hanno un diverso numero di nodi (subgraph matching – NP hard)
Le reti neurali ricorsive possono essere addestrate per apprendere
la similarità tra grafi
Sistemi di supporto alle decisioni - Leonado Rigutini
Esempio: classificazione di immagini
Segmentazione
Trasformazione
da RAG a grafo
orientato
Estrazione del grafo
di adiacenza (RAG)
Sistemi di supporto alle decisioni - Leonado Rigutini