Post on 21-Jul-2020
1 Data Mining - S. Orlando
Classification
Salvatore Orlando
2 Data Mining - S. Orlando
Classificazione
Dati una collezione di dati (training set ) – Ciascun record contiene un insieme di attributi, uno dei quali è
la classe di appartenenza. Trova un modello per l’attributo classe che diventa
funzione degli altri attributi
Obiettivo: trovare una funzione che assegni in modo accurato l’attributo classe a nuovi records non classificati. – Un test set è usato per determinare l’accuratezza del modello. – Di solito il dataset iniziale è suddiviso in training e test sets:
costruiamo il modello con il training set, e usiamo il test set per validarlo.
3 Data Mining - S. Orlando
Esempio di classificazione
Test Set
Training Set Model
Learn Classifier
Cheat = truffatore,imbroglione
4 Data Mining - S. Orlando
Classificazione vs. Clustering
Supervised learning (classification) – Supervisione: I dati del training set (osservazioni, misure, etc.) sono
stati preventivamente associati a etichette che indicano la classe di appartenenza
• conoscenza supervisionata
– I nuovi record di dati sono segmentati assegnando etichette di classe ai vari record, usando il modello costruito sulla base del training set
Unsupervised learning (clustering) – L’etichetta della classe è sconosciuta – Dati un insieme di misure, osservazioni, ecc. lo scopo del clustering è
quello di segmentare i dati, ovvero di stabilire l’esistenza di gruppi/classi omogenei nei dati
• Imparare l’esistenza di un qualche modello presente nei dati, che dà luogo ad una suddivisione dei dati, senza conoscenza precedente
5 Data Mining - S. Orlando
Tecniche di classificazione
Metodi basati sugli Alberi di Decisione (Decision Tree) Metodi Rule-based Memory-based reasoning Neural Networks Genetic Algorithms Naïve Bayes Support Vector Machines
6 Data Mining - S. Orlando
Classificazione basata su Decision Tree
I modelli di classificazione basati su Decision Tree sono considerati tra i migliori – Non costosi da costruire – Facili da interpretare – Facili da integrare con le basi di dati – Buona accuratezza in molte applicazioni, anche in confronto ad
altri metodi di classificazione
7 Data Mining - S. Orlando
Decision tree
Decision Tree – Un struttura ad albero che somiglia ad un flow-chart – Ogni nodo interno denota un test su un attributo
• Gli archi uscenti rappresentano i risultati del test – Ogni nodo foglia rappresenta un’etichetta di classe o la
distribuzione delle varie classi
Uso di un Decision Tree – Per classificare un nuovo dato campione sulla base degli
attributi • ovvero per assegnare un’etichetta di classe al nuovo dato
– Effettua i test sui valori degli attributi del campione rispetto ai test presenti nel decision tree
• A partire dalla radice, e sulla base degli attributi del campione da classificare, segue un cammino fino ad una foglia
• L’etichetta della foglia definisce la classe di appartenenza del campione
8 Data Mining - S. Orlando
Esempio di albero di classificazione
Refund
MarSt
TaxInc
YES NO
NO
NO
Yes No
Married Single, Divorced
< 80K > 80K
Splitting Attributes
9 Data Mining - S. Orlando
Un altro albero di classificazione
MarSt?
Refund?
TaxInc?
YES NO
NO
NO
Yes No
Married Single,
Divorced
< 80K > 80K
Si possono derivare più alberi dagli stessi dati!
10 Data Mining - S. Orlando
Un altro esempio
age?
student? credit rating?
no yes fair excellent
<=30 >40
31..40
NO YES NO YES
YES
11 Data Mining - S. Orlando
Algoritmo per Decision Tree Induction
Algoritmo di base (metodo greedy) – L’albero è costruito in modo:
• top-down - ricorsivo - divide-and-conquer – All’inizio tutti gli esempi di training sono in corrispondenza della
radice – Gli esempi di training sono partizionati ricorsivamente sulla
base degli attributi selezionati – Gli attributi di test sono selezionati in base ad un’euristica o a
misure statistiche (es., gini index, information gain) • Scopo: suddividere gli esempi creando partizioni omogenee • Esistono metodi che funzionano su attributi di test categorici e/o su
attributi numerici
Condizioni per stoppare il partizionamento – Tutti gli esempi di una partizione in una stessa classe – Non abbiamo più attributi sulla cui base partizionare
ulteriormente – usiamo una tecnica di majority voting per classificare la foglia
12 Data Mining - S. Orlando
Come effettuare lo splitting: attributi nominali
Ciascuna partizione è caratterizzato da un sottoinsieme di valori. Multi-way split: Usa tanti ramificazioni dello split quanti sono i
valori distinti.
Binary split: Divisi i valori in due sottoinsiemi. Bisogna individuare un partizionamento ottimale.
CarType Family
Sports Luxury
CarType {Family, Luxury} {Sports}
CarType {Sports, Luxury} {Family} oppure
13 Data Mining - S. Orlando
Come effettuare lo splitting: attributi ordinali
Ciascuna partizione è caratterizzato da un sottoinsieme di valori. Multi-way split: Usa tanti ramificazioni dello split quanti sono i
valori distinti.
Binary split: Divisi i valori in due sottoinsiemi. Bisogna individuare un partizionamento ottimale.
Questo partizionamento potrebbe essere possibile?
oppure
Size Small
Medium Large
Size {Medium,
Large} {Small} Size
{Small, Medium} {Large}
Size {Small, Large} {Medium}
14 Data Mining - S. Orlando
Come effettuare lo splitting: attributi numerici
Metodi differenti – Binary Decision: (A < v) or (A ≥ v)
• considera tutti i possibili split e individua il miglior taglio • Può risultare molto costo computazionalmente, anche se
esistono dei metodi basati sull’ordinamento – Discretizzazione per formare un attributo categorico
(ordinale) • La scala di variazione dell’attributo viene suddiviso in N
intervalli, ciascuno associato ad un attributo ordinale • Trasforma il data set, assegnando ad ogni valore
dell’attributo continuo l’intervallo in cui esso valore cade • Statico – discretizzato a priori prima della trasformazione • Dinamico – le suddivisioni possono essere trovati tramite
equal interval partitioning, equal frequency partitioning, o distance-based clustering.
15 Data Mining - S. Orlando
Discretizzazione
Equal-width (distance) partitioning: – Dividi la scala di variazione dell’attributo in N intervalli identici – Se A e B sono il più piccolo e il più grande valore di un attributo, la
larghezza degli intervalli sarà: W = (B-A)/N. – E’ il metodo più semplice, ma gli outlier (o dati non ben distribuiti)
possono dare problemi al metodo di discretizzazione Equal-depth (frequency) partitioning:
– Dividi la scala di variazione dell’attributo in N intervalli, ciascuno contenente approssimativamente lo stesso numero di campioni
– Buon metodo Cluster analysis partitioning:
– Può risultare costoso
16 Data Mining - S. Orlando
Discretizzazione
Data Equal interval width
Equal frequency K-means (clustering)
Dati con 2 attributi X, Y continui Discretizzazione di X
17 Data Mining - S. Orlando
Criterio di splitting
Come scegliere l’attributo e il relativo splitting? – uso di particolari indici di dispersione dei valori dell’attributo
categorico di classe
Gini index (algoritmo di IBM IntelligentMiner, CART, SLIQ, SPRINT)
Information gain (algoritmi ID3/C4.5)
18 Data Mining - S. Orlando
Gini index
In corrispondenza di un certo nodo t dell’albero in costruzione, e rispetto alla corrispondente partizione del dataset di training, possiamo definire il Gini Index:
(NOTA: p( j | t) è la frequenza relativa della classe j al nodo t).
– Misura l’impurità/disordine del dataset corrispondente a t. • Massimo valore (1 - 1/nc) quando i record sono equamente
distribuiti tra tutte le classi ⇒ informazione meno interessante • Minimo valore (0.0) quando tutti i record appartengono ad una sola
classe ⇒ informazione più interessante
€
GINI(t) =1− [p( j | t)]2j∑
19 Data Mining - S. Orlando
Gini
Una sola classe: – 1 - 12 = 0
nc classi equiprobabili: – 1 - \sum ((n / nc) / n)2 = 1 - \sum (1 / nc)2 = 1 – nc (1 / nc)2 = 1 – 1 / nc
20 Data Mining - S. Orlando
Esempi relativi a Gini Index
P(C1) = 0/6 = 0 P(C2) = 6/6 = 1
Gini = 1 – P(C1)2 – P(C2)2 = 1 – 0 – 1 = 0 €
GINI(t) =1− [p( j | t)]2j∑
P(C1) = 1/6 P(C2) = 5/6
Gini = 1 – (1/6)2 – (5/6)2 = 0.278
P(C1) = 2/6 P(C2) = 4/6
Gini = 1 – (2/6)2 – (4/6)2 = 0.444
21 Data Mining - S. Orlando
Uso del GINI Index
Criterio di Splitting: Minimizza il Gini Index della suddivisione. Quando un nodo t è suddiviso in k partizioni (figli), la qualità della
suddivisione è calcolata come:
dove, ni = numero di record della partizione (figlio) i, n = numero di record del dataset al nodo t.
ni /n costituisce il peso dei vari GINI(i)
Dato il dataset associato al nodo t, si sceglie l’attributo che fornisce il più piccolo GINIsplit(t) per partizionare il dataset – È necessario enumerare tutti i possibili punti di splitting per
ciascun attributo
€
GINIsplit =ninGINI(i)
i=1
k
∑
22 Data Mining - S. Orlando
Calcolare il GINI Index per attributi binari
Suddivisione in due partizioni Si cercano partizioni più grandi e più pure possibili.
B?
Yes No
Node N1 Node N2
23 Data Mining - S. Orlando
Calcolare il GINI Index per attributi categorici
Per ciascuna classe nel dataset, conta il numero dei valori differenti per ogni attributo – computa le singole righe delle matrici di conteggio
Usa la matrice dei conteggi per prendere le decisioni
Multi-way split Two-way split
(bisogna trovare il migliore partizionamento dei valori)
24 Data Mining - S. Orlando
Calcolare il GINI Index per attributi continui
Solitamente si usa Binary Decision, basato su un singolo valore di splitting – Non abbiamo bisogno di discretizzare
Sono possibili scelte diverse per il valore di splitting – Es.: Numero di possibili valori di splitting = Numero di valori distinti
assunti dall’attributo Per ciascun valore di splitting abbiamo una matrice di conteggi
associata – Conteggio delle varie classi per ciascuna partizione, (A < v) e (A ≥ v)
Metodo naive per scegliere il miglior v – Per ciascun v, scandisci il database per raccogliere la matrice dei
conteggi e computare il corrispondente Gini Index (GINIsplit) – Questo metodo è computazionalmente inefficiente! Lavoro ridondante.
25 Data Mining - S. Orlando
Calcolare il GINI Index per attributi continui (2)
Metodo per migliorare l’efficienza Per ciascun attributo
– Ordina rispetto ai valori degli attributi – Scandisci linearmente questi valori, aggiornando ogni volta la matrice dei
conteggi necessario per calcolare il GINI index • considera che, quando spostiamo il pivot, abbiamo un singolo elemento
(appartenente ad una certa classe) che passa da una partizione all’altra • +/- 1 in una particolare riga
– Scegli le posizioni di split che hanno il GINI index minore
Split Positions Sorted Values
26 Data Mining - S. Orlando
Criterio di splitting alternativo: Information Gain
In corrispondenza di un certo nodo t dell’albero in costruzione, e rispetto alla corrispondente partizione del dataset di training, possiamo definire l’Information Gain:
(NOTA: p( j | t) è la frequenza relativa della classe j al nodo t).
– Misura l’omogeneità/ordine di un nodo. • Massimo (log nc) quando i record sono equamente distribuiti tra
tutte le classi ⇒ implica meno informazione • Minimo valore (0.0) quando tutti i record appartengono ad una sola
classe ⇒ implica più informazione – I calcoli basati sulla misura dell’Entropia sono simili a quelle
basate sul GINI index
€
Entropy(t) = − p( j | t)log p( j | t)j∑
27 Data Mining - S. Orlando
Entropy
Una sola classe: - (1 * log 1) = 0
nc classi equiprobabili: - (\sum ( (n / nc) / n) * log ((n / nc) / n) ) =
= - ( \sum ( (1 / nc) * log (1 / nc) ) = = - nc * (1 / nc) * log (1 / nc) = = - log (1 / nc) = - (log 1 - log nc) = log nc
28 Data Mining - S. Orlando
Esempi relativi all’Information Gain (Entropia)
P(C1) = 0/6 = 0 P(C2) = 6/6 = 1
Entropy = – 0 log 0 – 1 log 1 = – 0 – 0 = 0
P(C1) = 1/6 P(C2) = 5/6
Entropy = – (1/6) log2 (1/6) – (5/6) log2 (1/6) = 0.65
P(C1) = 2/6 P(C2) = 4/6
Entropy = – (2/6) log2 (2/6) – (4/6) log2 (4/6) = 0.92
€
Entropy(t) = − p( j | t)log2 p( j | t)j∑
29 Data Mining - S. Orlando
Uso dell’Entropia come criterio di splitting
Quando un nodo t è suddiviso in k partizioni (figli), la qualità della suddivisione è calcolata come IG (Information Gain):
dove, ni = numero di record della partizione (figlio) i, n = numero di record del dataset al nodo t.
ni /n costituisce il peso dei vari Entropy(i)
Misura la riduzione nell’Entropia in conseguenza dello split. Scegli lo split che raggiunge la riduzione maggiore (massimizza il GAIN)
Usato in ID3 e C4.5
€
GAINsplit = Entropy(t) − ninEntropy(i)
i=1
k
∑
30 Data Mining - S. Orlando
Problemi legati all’Information Gain
Svantaggio: – l’IG tende a preferire suddivisioni che producono molte partizioni,
piccole ma pure (ovvero che comprendono elementi appartenenti ad una singola classe). Si rischia di costruire un albero overfitted rispetto al training set
Gain Ratio:
Il nodo padre, è suddiviso in k partizioni ni è il numero di record della partizione i
– Corregge l’Information Gain dello split usando l’entropia del partizionamento (SplitINFO).
– Valori alti di SplitINFO all’aumento del numero di piccole partizioni bilanciate! ⇒ l’aumento di SplitINFO penalizza Gain Ratio
– Usato in C4.5
€
GainRATIOsplit =GAINSplit
SplitINFO
€
SplitINFO = −ninlog ni
ni=1
k
∑
31 Data Mining - S. Orlando
Algoritmo C4.5 - like
32 Data Mining - S. Orlando
Decision Tree: Web Mining Application
Prima di applicare tecniche di Web Mining, es.: per sintetizzare un Web recommender, dobbiamo pulire l’user log – dobbiamo distinguere tra accessi fatto da umani e da robot/crawler,
per poter poi rimuovere i secondi in modo automatico Nel log di sopra ogni linea è un accesso, e i vari accessi sono
segmentati rispetto all’utente (IP address) – nota Requested e Referrer/From page
33 Data Mining - S. Orlando
Decision Tree: Web Mining Application
Ogni sessione è un grafo diretto – nodi: pagine – archi” hyperlink
34 Data Mining - S. Orlando
Decision Tree: Web Mining Application
Grafo della sessione 1
breadth
depth
35 Data Mining - S. Orlando
Decision Tree: Web Mining Application
Estrazione di feature caratterizzanti le varie sessioni
36 Data Mining - S. Orlando
Decision Tree: Web Mining Application
Costruzione di un dataset (Web log) supervisionato – 2916 record – 50% classe 1 (Web Robot) – 50% classe 0 (Human users)
10% training dataset 90% test dataset
Costruzione di un decision tree per poter classificare le sessioni, e rimuovere le sessioni generate dai robot
37 Data Mining - S. Orlando
Decision Tree: Web Mining Application
I robot fanno ricerche con “breadth” grandi e “depth” piccolo
Gli utenti umani fanno ricerche con “breadth” piccolo e “depth” più grandi
– navigazioni focalizzate e profonde
I robot non scaricano le immagini
Le sessioni dei robot sono molto lunghe rispetto a quelle degli umani
I robot ripetono le richieste quando seguono i link per tornare indietro, mentre gli umani non lo fanno grazie alla cache dei browser
38 Data Mining - S. Orlando
Decision Boundary
Le linee di confine tra due regioni vicine create dal classificatore sono anche chiamate decision boundary
Nei decision tree le decision boundary sono parallele agli assi Ogni test condition coinvolge un singolo attributo alla volta
39 Data Mining - S. Orlando
Oblique Decision Trees
x + y < 1
Class = + Class =
Difficile derivare un decision tree accurato dal training set sopra illustrato Possibile soluzione
Condizioni di test che coinvolgono attributi multipli Aumenta la complessità per individuare il test ottimo
40 Data Mining - S. Orlando
Overfitting
L’albero può overfit-are i dati di training – Troppi rami, alcuni dei quali possono riflettere anomalie dovuti a rumori
o outlier – Poca accuratezza (troppi errori) per campioni non visti (test dataset)
L’overfitting è un problema comune a tutti i classificatori, non è solo un problema dell’albero di decisione
Overfitting
Training/Apparent Errors
Generalized Errors
41 Data Mining - S. Orlando
Overfitting: Pre-Pruning
Pre-Pruning (Early Stopping Rule) – Stop dell’algoritmo prima che esso produca un albero fully-
grown – Le tipiche condizioni di stopping:
• Stop se tutte le istanze appartengono alla stessa classe • Stop se tutti i valori degli attributi hanno lo stesso valore
– Condizioni più restrittive per il pruning: • Stop se il numero di istanze è minore di uno user-specified
threshold – Evita la creazione di piccole partizioni – Difficile trovare il threshold
• Stop se espandendo il nodo corrente non miglioriamo la misura di impurità (es., Gini o Information Gain).
42 Data Mining - S. Orlando
Overfitting: Post-Pruning
Post-Pruning – Rimuovi nodi/rami da un albero completo (“fully grown” tree)
• Elimina i nodi in modo bottom-up • Un sottoalbero può essere sostituito con
– un nodo foglia (subtree replacement) – il cammino più frequentemente scelto (subtree raising)
– Usa un insieme di dati differenti dal training data (testing data) per decidere qual è il “best pruned tree”
– Se l’errore sui dati di testing migliora dopo la sostituzione del sotto-albero con un nodo foglia
• Sostituisci in maniera permanente, generando un albero pruned • L’etichetta di classe da assegnare al nuovo nodo foglia è
determinato dalla classe maggioritaria nel sotto albero
43 Data Mining - S. Orlando
Overfitting: Post-Pruning
44 Data Mining - S. Orlando
Presentation: decisiontree
45 Data Mining - S. Orlando
Presentation: decisiontree
46 Data Mining - S. Orlando
Estrarre regole di classificazione da alberi
Rappresenta la conoscenza nella forma di regole IF-THEN – Una regola per ogni cammino dalla radice ad una foglia – Ciascuna coppia attributo-valore lungo un cammino forma una
congiunzione – Il nodo foglia restituisce la predizione della classe per la regola
estratta Le regole sono più facili da capire Esempi
IF age = “<=30” AND student = “no” THEN buys_computer = “no” IF age = “<=30” AND student = “yes” THEN buys_computer = “yes” IF age = “31…40” THEN buys_computer = “yes” IF age = “>40” AND credit_rating = “excellent” THEN buys_computer =
“yes” IF age = “>40” AND credit_rating = “fair” THEN buys_computer = “no”
47 Data Mining - S. Orlando
Le regole possono essere semplificate
In generale le regole sono – mutuamente esclusive ed esaustive
Ma possiamo fare del pruning: – semplificare o eliminare
Regola iniziale: – (Refund=No) ∧ (Status=Married) → No
Regola semplificata – (Status=Married) → No
Problemi: – le regole non sono più mutuamente esclusive ed esaustive – aggiungi una regola di default – dai un punteggio ad ogni regola
48 Data Mining - S. Orlando
Bayesian Classification: Perchè?
Incremental: Ogni nuova osservazione può essere usata per migliorare la conoscenza pregressa ed aggiornare il modello.
Probabilistic: Può elaborare e produrre diverse ipotesi con delle probabilità associate.
Standard: Generalmente sono un punto di riferimento per valutare nuovi algoritmi
49 Data Mining - S. Orlando
Classificatori Bayesiano
Metodo probabilistico (Bayesian) per risolvere il problema della classificazione
Probabilità condizionali:
Teorema di Bayes :
A
C
50 Data Mining - S. Orlando
Esempio di applicazione del teorema di Bayes
Conoscenza pregressa: – Un dottore sa che la meningite causa rigidità del collo per il 50% dei
casi • P(rigidità del collo | meningite) = 1/2
– La probabilità incondizionata che un paziente possa avere la meningite è
• P(meningite) = 1/50000 = 0,00002 – La probabilità incondizionata che un paziente possa avere rigidità del
collo è • P(rigidità del collo) = 1/20 = 0,05
Se un paziente ha rigidità del collo, qual è la probabilità che egli abbia la meningite?
51 Data Mining - S. Orlando
Classificatori Bayesiano
Considera i vari attributi e l’etichetta della classe come variabili casuali
Dato un record R contenente gli attributi (A1, A2,…,An) – Lo scopo è predire la classe C di R – Più specificatamente, vogliamo trovare il valore di C che massimizza:
P(C| A1, A2,…,An )
Possiamo stimare P(C| A1, A2,…,An ) direttamente dai dati?
52 Data Mining - S. Orlando
Classificatori Bayesiano
€
P(C | A1A2…An ) =P(A1A2…An |C)P(C)
P(A1A2…An )
53 Data Mining - S. Orlando
Classificatore Naïve Bayes
€
P(Cj | A1A2…An ) =P(A1A2…An |Cj)P(Cj)
P(A1A2…An )
54 Data Mining - S. Orlando
Come stimiamo la probabilità dai dati?
Probabilità delle Classi: – P(C) = Nc/N – dove Nc è il numero di istanze
che appartengono alla classe C
– Es., P(No) = 7/10, P(Yes) = 3/10
Per attributi discreti: – P(Ai | Ck) = |Aik| / Nck – dove |Aik| è il numero di istanze
che hanno l’attributo Ai e appartengono alla classe Ck
– dove Nck è il numero di istanze che appartengono alla classe Ck
– Esempi:
P(Married | No) = 4/7 P(Refund=Yes | Yes)=0
55 Data Mining - S. Orlando
Come stimiamo la probabilità dai dati?
Per attributi continui: – Abbiamo bisogno di conoscere la probabilità condizionale
P(Ai|C) • nota che il particolare valore dell’attributo continuo Ai potrebbe
non essere presente nel dataset di training
– Assumiamo che gli attributi obbediscono a certe distribuzioni di probabilità
• Tipicamente, si assume la distribuzione normale • Si usano i dati per stimare i parametri della distribuzione di
probabilità (ovvero, media e varianza)
• Una volta che la distribuzione di probabilità è nota, possiamo usarla per stimare la probabilità condizionale P(Ai|C)
56 Data Mining - S. Orlando
Come stimiamo le probabilità dai dati?
Distribuzione normale:
– Una per ciascuna coppia (Ai,cj)
Per (Income, Class=No): – Se Class=No
• µij (media nel campione) = 110 • σ2
ij (varianza nel campione) = 2975
57 Data Mining - S. Orlando
Esempio di classificatore Naïve Bayes
P(X|Class=No) = P(Refund=No| Class=No) × P(Married| Class=No) × P(Income=120K| Class=No) = 4/7 × 4/7 × 0.0072 = 0.0024
P(X|Class=No) × P(No) = 0.0024 × 0.7 = 0.00168
P(X|Class=Yes) = P(Refund=No| Class=Yes) × P(Married| Class=Yes) × P(Income=120K| Class=Yes)
= 1 × 0 × 1.2 × 10-9 = 0 P(X|Class=Yes) × P(Yes) = 0.0 × 0.3 = 0.0
Poiché P(X|No)P(No) > P(X|Yes)P(Yes) abbiamo che: P(No|X) > P(Yes|X)
=> Class = No
Dato il seguente test:
P(Refund=Yes|No) = 3/7 P(Refund=No|No) = 4/7 P(Refund=Yes|Yes) = 0 P(Refund=No|Yes) = 1 P(Marital Status=Single|No) = 2/7 P(Marital Status=Divorced|No) = 1/7 P(Marital Status=Married|No) = 4/7 P(Marital Status=Single|Yes) = 2/3 P(Marital Status=Divorced|Yes) = 1/3 P(Marital Status=Married|Yes) = 0
Per Income: Se No: media = 110
varianza = 2975 Se Yes: media = 90
varianza = 25
58 Data Mining - S. Orlando
Esempio di classificatore Naïve Bayes
A: attributes
M: mammals
Non-M: non-mammals
P(A|M)P(M) > P(A|N)P(N)
=> Mammals
Test sugli attributi:
59 Data Mining - S. Orlando
Classificatore Naïve Bayes: sommario
Robusto rispetto al rumore
Gestisce i valori mancanti ignorando le istanze durante il calcolo della stima di probabilità
Purtroppo l’assunzione di indipendenza può non essere valida per qualche attributo
Per superare queste limitazioni: – Bayesian networks, che combinano ragionamenti Bayesiani con
relazioni di causalità tra gli attributi – Alberi di decisione, che ragionano su un attributo alla volta,
considerando gli attributi più importanti per primi
60 Data Mining - S. Orlando
Classificatori Instance-Based • Memorizza le istanze di training
=> “Ritarda” nella costruzione del modello (lazy learner)
• Usa le istanze di training per predire l’etichetta di classe di nuovi casi non visti
• Approcci Tipici
• k-nearest neighbor
• Locally weighted regression
• Case-based reasoning
61 Data Mining - S. Orlando
K-nearest neighbor
Istanze come vettori a n dimensioni, ad esempio punti nel piano euclideo – attributi continui
Richiede tre cose: – L’insieme di istanze
memorizzate – Metrica di Distanza – Il valore di k, il numero di
vicini “nearest” da estrarre dall’insieme delle istanze
Per la classificazione: – Estrai i k nearest neighbors – Usa le etichette di classe dei
nearest neighbors per determinare l’etichetta di classe dell’istanza non vista (es., attraverso il voto a maggioranza)
62 Data Mining - S. Orlando
K-nearest neighbor
I K-nearest neighbors di un’istanza x sono i punti che hanno le K più piccole distanze da x
63 Data Mining - S. Orlando
1 nearest-neighbor
A causa del costo della classificazione, è necessario indicizzare/precomputare informazioni per velocizzare il calcolo dei K vicini più prossimi
Voronoi Diagram
64 Data Mining - S. Orlando
Classificatore K-nearest neighbor
Calcola la distanza tra due punti: – Distanza Euclidea
Distanza per pesare i voti dei k vicini – fattore di peso, w = 1/d2 – pesa il voto in accordo alla distanza
65 Data Mining - S. Orlando
Classificatore K-nearest neighbor ………
Scegliere il valore di k: – Se k è troppo piccolo, il classificatore è sensibile al rumore – Se k è troppo grande,
• costoso dal punto di vista computazionale • la cerchia dei vicini può includere punti appartenenti ad altre classi, e può
portare a errori di classificazione
66 Data Mining - S. Orlando
Case-Based Reasoning
Anche questo metodo usa: lazy evaluation + analisi delle istanze più simili
Differenza: Le istanze non sono “punti in uno spazio Euclideo”
Metodologia – Le istanze/casi sono rappresentate da una ricca descrizione simbolica
(es., grafi, funzioni) – Un case-based reasoner prima cerca di capire se esiste un caso di
training identico al nuovo caso da classificare => classificazione OK – Se questo caso uguale non esiste, si cercano casi di training “vicini”,
ovvero con componenti simili a quelli del nuovo caso • Es.: se i casi sono rappresentati come grafi, si cercano sottografi comuni
Problemi – Trovare una buona misura di similarità (es. per il matching tra grafi) – Metodi di indicizzazione per velocizzare la ricerca di casi simili
67 Data Mining - S. Orlando
Lazy (pigro) vs. eager (impaziente) evaluation
Instance-based learning: lazy evaluation Decision-tree and Bayesian classification: eager evaluation Differenze più importanti
– I metodi lazy considerano l’istanza della query q da classificare assieme alla decisione sulla generalizzazione rispetto al dataset D di training
– I metodi eager non possono farlo, poiché nel momento in cui vedono la query q hanno già scelto approssimazioni globali per costruire il modello
Efficienza: i metodi lazy impiegano meno tempo per il training, ma più tempo per predire la classe
Accuratezza – I metodi lazy: usano efficientemente uno spazio di ipotesi più ricco
ritagliato sulla query q – I metodi eager: devono convergere da subito ad una ipotesi singola che
copre l’intero spazio delle istanze di training
68 Data Mining - S. Orlando
Metriche per valutare i classificatori
Siamo interessati alle prestazioni dei classificatori – rispetto alla capacità predittiva del modello – possibile tradeoff rispetto alla velocità dell’algoritmo
Confusion Matrix:
PREDICTED CLASS
ACTUAL CLASS
Class=Yes Class=No
Class=Yes a b
Class=No c d
a: TP (true positive)
b: FN (false negative)
c: FP (false positive)
d: TN (true negative)
Conteggi: a, b, c, e d anche esprimibili in percentuale
69 Data Mining - S. Orlando
Metriche per valutare i classificatori
Metrica più usata:
Error Rate = 1 - Accuracy
PREDICTED CLASS
ACTUAL CLASS
Class=Yes Class=No
Class=Yes a (TP)
b (FN)
Class=No c (FP)
d (TN)
70 Data Mining - S. Orlando
Problemi con lo sbilanciamento delle classi
Se il problema non è bilanciato P(Class=Y) molto diverso da P(Class=N)
Accuracy non è una misura adeguata o obiettiva Esempio:
– Class=Yes transazione di carta di credito fraudolenta – solo l’1% delle transazioni di carte di credito sono fraudolente – il 99% sono quindi lecite ! – un modello che classifica tutte le transazioni come legittime (Class=No)
ha un’accuratezza dello 0.99 !!! – ma il modello è cattivo ⇒ ha un rate di FN dell’1%, ma questo 1%
include TUTTE le transazioni fraudolente a cui siamo interessati
PREDICTED CLASS
ACTUAL CLASS
Class=Yes Class=No Class=Yes 0%
(TP) 1% (FN)
Class=No 0% (FP)
99% (TN)
71 Data Mining - S. Orlando
Altre misure
Necessarie misure che considerano le classi rare più interessanti
Nella classificazione binaria, di solito la classe rara = positiva True positive rate (TPR) o sensibilità
– TPR = TP / (TP + FN) (esempio TPR=0) – frazione di veri positivi individuati, rispetto a tutti i positivi
True negative rate (TNR) o specificità – TNR = TN / (TN + FP) (esempio TNR=99/99=1) – frazione di veri negativi individuati, rispetto a tutti i negativi
Recall e Precision – misure tipiche dell’Information Retrieval
Recall: r = TP / (TP + FN) sensibilità Precision: p = TP / (TP + FP)
in IR la quantità TP+FP corrisponde ai documenti ritenuti rilevanti e ritornati dal motore di ricerca
72 Data Mining - S. Orlando
Metodi di valutazione dei classificatori
Vogliamo valutare la bontà di un algoritmo di classificazione – Quanto è accurato nel predire la classe di un nuovo campione?
Continuare ad usare il training set per valutare l’accuratezza di un algoritmo di classificazione può generare errori – Stime troppo ottimistiche – I modelli ottenuti sono super specializzati rispetto ai dati di training
(overfitting) – Holdout è il metodo più comune per evitare stime sbagliate
Holdout – Usa 2/3 del dataset classificato per il training, e 1/3 per il testing – Problemi dovuti alla riduzione degli esempi per il training, e al fatto che
training e test sono sottoinsiemi dello stesso dataset
73 Data Mining - S. Orlando
Metodi di valutazione
Random subsampling – Holdout ripetuto – Ad ogni iterazione, una certa proporzione è selezionata in modo random per il
set training, il resto dei dati è usato per il testing – acci : accuratezza del modello all’iterazione i-esima – accsub = Σi=1,k acci/k – Holdout ripetuto ancora non ottimo: overlapping tra i set di test
Cross validation – Partiziona il dataset in k sottoinsiemi disgiunti – Stesso record usato lo stesso numero di volte per il training, e una sola volta per
il testing – k-fold: allena su k-1 partizioni, e testa sulla partizione rimanente
• Valore tipico per k nel k-fold è 10 – Leave-one-out: Cross-validation con k=N
Bootstrap – Training: Sampling with replacement – Lo stesso record può apparire più volte nel training dataset – Dati N record, un training costituito da N record contiene circa il 63.2% dei
record originali – Test set = record non selezionati – Ripetuto b volte
74 Data Mining - S. Orlando
Ensemble methods
Ensemble methods: – l’unione fa la forza – uso una combinazione di modelli
Bagging Boosting
75 Data Mining - S. Orlando
Bagging
Bootstrap aggregation
eseguo k bootstrap sample dal dataset da ognuno creo un classificatore per classificare un oggetto mai visto prima
– raccolgo le previsioni di ciascun classificatore – prendo per buona quella più popolare
Ha sempre una accuratezza migliore di un classificatore standard
Motivazione: – riduce la varianza di un classificatore
76 Data Mining - S. Orlando
Boosting
Creo un classificatore a partire dai dati iniziali Viene assegnato un peso (aumentato il peso) degli oggetti che non
sono classificati correttamente dal classificatore Viene creato un altro classificatore sul nuovo dataset “pesato” Si ripete il processo fino ad ottenere k classificatori
Per classificare un oggetto mai visto – chiedo a tutti i classificatori – assegno un peso ad ogni classificatore in funzione della sua
accuratezza
77 Data Mining - S. Orlando
Ada Boost
Faccio un sampling con replacement del dataset creo un nuovo classificatore incremento il peso degli oggetti classificati male decremento il peso degli oggetti classificati bene ripeto il procedimento N.B.: durante il sampling un oggetto ha probabilità di
essere scelto pari al suo peso !
78 Data Mining - S. Orlando
Bagging vs. Boosting
Boosting tende ad essere più accurato
Ma Bagging è meno suscettibile a over-fitting
79 Data Mining - S. Orlando
Prediction (vs. Classification)
I metodi predittivi sono simili a quelli per la classificazione – Prima costruisci il modello – Poi usa il modello per predire i valori sconosciuti
• Il metodo di predizione più importante è la regressione – Regressione Lineare e Multipla – Regressione non-lineare
La predizione è differente dalla classificazione – La classificazione predice etichette di classe categoriche – I metodi predittivi si occupano di predire valori continui non conosciuti
80 Data Mining - S. Orlando
Metodi predittivi
Regressione lineare: Y = α + β X – Modelliamo una variabile Y (variabile che vogliamo predire) come una
funzione lineare di un’altra variabile X (che di solito è nota, e sulla quale basiamo la predizione di Y)
– I coefficienti del modello (α, β) determinati sulla base dei dati conosciuti (di training del modello)
• Metodi dei minimi quadrati applicati ai valori conosciuti del training dataset Y1, Y2, …, X1, X2, ….
Y = 21.7 + 3.7 X
81 Data Mining - S. Orlando
Metodi predittivi
Regressione lineare multipla: Y = b0 + b1 X1 + b2 X2 …. – Abbiamo variabili multiple di predizione X1, X2, ecc. su cui basare il
valore di Y – Ancora minimi quadrati
Regressione non lineare – I dati non mostrano l’esistenza di una dipendenza lineare – La variabile di predizione X ha una relazione con la variabile da predire
Y modellabile con una funzione polinomiale Y = α + β1 X + β2 X2 + β3 X3
– Possiamo introdurre nuove variabili (X1 = X, X2 = X2, X3 = X3) per trasformare l’equazione polinomiale in una lineare, su cui applicare il metodo dei minimi quadrati
82 Data Mining - S. Orlando
Conclusioni
La Classificazione è stato un problema studiatissimo (soprattutto in statistica, machine learning)
La Classificazione è probabilmente una delle tecniche di data mining più usate, e rispetto alle quali sono state introdotte moltissime estensioni
Direzioni di ricerca: classificazione di dati non-relazionali, es.: testi, dati spaziali, multimedia, etc..