Il confronto tra la classificazione delle funzioni discriminanti e la realt`a si ottiene facilmente con la
chiamata: > table(grp, discr.val$class) grp 1 2 3 1 4 0 1 2 0 0 4 3 1 1 4
Si nota che solamente 8 anfore sono classificate in maniera esatta alla rivalidazione, ossia 4 di meno di
quanto ottimisticamente ottenuto in precedenza. Si pu`o quindi concludere che le funzioni discriminati
ottenute hanno un error rate stimato di 7/15 = 46.7%, con intervallo di confidenza al 95% valutabile con la chiamata:
> binom.test(7, 15) [...]
95 percent confidence interval: 0.2126667 0.7341387
9.2 Alberi di classificazione
Come la tecnica dell’analisi discriminante, anche la costruzione di un albero di classificazione (classifi-cation tree) `e utile per effettuare una classificazione automatica di soggetti in base ai valori misurati di
un set di variabili. La flessibilit`a di questo metodo lo fa talvolta preferire alle analisi pi`u tradizionali,
in particolar modo quando le assunzioni su cui queste ultime si poggiano vengono meno o non possono essere facilmente verificate.
La caratteristica che contraddistingue gli alberi di classificazione `e la loro natura gerarchica. Per chiarire il concetto con un esempio si supponga di avere una pila di monete composta da pezzi di
tre valori diversi che differiscono per il loro diametro. Per suddividerle velocemente si pu`o pensare di
setacciare il mucchio con un setaccio che abbia fori abastanza piccoli da lasciar pasare solo le monete di diametro inferiore, che vengono quindi rapidamente isolate. Il mucchio restante viene passato in
un nuovo setaccio, dalle maglie di dimensioni tali che solo le monete pi`u piccole fra quelle rimaste
possano cadere. Questo `e un esempio di albero di classificazione che, con una procedura gerarchica in due passi, arriva alla classificazione del mucchio di monete.
Un albero di classificazione si presenta come un diagramma ad albero rovesciato (il nodo radice, o root node, `e in alto) che si biforca ogni volta che viene presentata una scelta, basata sul valore di una delle variabili in gioco (come nel caso dell’algoritmo implementato in R) o sul valore di una
combinazione di pi`u variabili (questo caso non `e coperto dalle librerie disponibili). Si distinguono due
tipologie di nodo: i nodi non terminali - i quali hanno due discendenti diretti - e i nodi terminali (o foglie) che non subiscono ulteriori bipartizioni. In questo tipo di albero ogni split, basato sul valore di una singola variabile, divide sempre un nodo genitore in due nodi figli. In questo tipo di analisi `e possibile far rientrare sia variabili qualitative che quantitative.
L’algoritmo di costruzione degli alberi implementato in R, `e del tipo CART (Classification And Regression Trees). Questo algoritmo parte dai dati raggruppati in un unico nodo (root node) ed esegue ad ogni passo una ricrca esaustiva fra tutte le possibili suddivisioni. A ogni passo viene scelta
la suddivisione migliore, cio`e quella che produce rami il pi`u possibile omogenei fra loro. Per valutare
la bont`a di uno split si usa comunemente l’indice di impurit`a di Gini, che per il nodo i-esimo `e definito
come: 1 −X k ˆ p2 ik
dove l’indice k corre sulle classi del fattore di classificazione e ˆ
pik =nik
`e la frazione degli ni soggetti nel nodo i-esimo assegnato alla k-esima classe. Si sceglie come split quello che riduce l’impurit`a media delle due foglie.
Dopo che si `e individuato lo split migliore per il nodo radice, l’algoritmo ripete il processo di ricerca
per ogni nodo figlio continuando a bipartire finch´e ci`o non `e pi`u possibile (se un nodo `e costituito
da un solo caso oppure quando tutti i casi che compongono un nodo afferiscono alla stessa classe) o finch´e il processo non `e arrestato per qualche ragione (tipicamente perch´e un nodo `e costituito da un numero troppo esiguo di casi; per la libreria rpart questa soglia `e di 20 casi). Quando un nodo viene riconosciuto come terminale bisogna stabilire come classificare i casi che in esso sono contenuti. Un semplice criterio al riguardo consiste nell’assegnare al nodo l’etichetta del gruppo maggiormente rappresentato.
Originariamente la costruzione degli alberi di classificazione avveniva splittando ogni nodo finch´e
non smetteva di essere soddisfatto un qualche criterio di bont`a di bipartizione. Quando tutti i rami
uscenti dal nodo radice raggiungevano dei nodi terminali, il processo di costruzione dell’albero veniva considerato ultimato. La filosofia dell’algoritmo CART `e completamente diversa. Invece di cercare di stabilire se un nodo `e terminale o meno, il CART procede diramando l’albero finch´e `e possibile ed esaminando sotto-alberi ottenuti dalla potatura dei rami (tree pruning) dell’albero di partenza. Tra
tutti i sotto-alberi possibili si sceglier`a il migliore in base a un criterio del minimo costo-complessit`a.
Sia Ri una misura di adeguatezza, valutata su ognuna delle foglie dell’albero (tale misura pu`o ad
esempio essere il numero di casi mal classificati all’interno della foglia i-esima). Sia R la somma di
tali valori su tutte le foglie dell’albero. Si definisce l’indice Rα:
Rα= R + α nT
con nT pari alla dimensione dell’albero (ossia al numero delle sue foglie). All’aumentare di α si penalizzano alberi con molte foglie. Per valutare quale sia il valore di α ottimale gli algoritmi ricorrono a una procedura di rivalidazione interna, dividendo il set di dati in 10 sottoparti, usandone quindi 9 per sviluppare l’albero e usando la decima per una procedura di validazione. Questa procedura `e ripetuta tenendo fuori a turno uno dei sottocampioni e mediando poi i risultati (questo processo `e noto come 10-fold cross-validation). Per ulteriori informazioni si rimanda ad esempio a [45].
Il problema principale degli algoritmi stile CART `e il fatto che essi non tengono assolutamente conto dell’influenza che la scelta di una particolare divisione ha sui futuri divisori. In altre parole, la decisione della divisione avviene ad ogni nodo dell’albero, in un preciso momento durante l’esecuzione
dell’algoritmo, e non `e mai pi`u riconsiderata in seguito. Dato che tutte le suddivisioni vengono scelte
sequenzialmente e ognuna di esse di fatto dipende dalle predecedenti, si ha che tutte le divisioni sono dipendenti dal nodo radice dell’albero; una modifica del nodo radice potrebbe portare alla costruzione di un albero completamente differente.
I dettagli matematici e algoritmici che sono alla base della costruzione e della selezione di un albero di classificazione sono numerosi e non possono essere trattati qui nel dettaglio. Per ulteriori particolari si rimanda a testi come [8, 45].
Esempio
Le funzioni con cui R tratta gli alberi di classificazione sono disponibili nella librerie aggiuntive rpart (che sar`a qui utilizzata) e tree. Per un esempio del loro impiego si usa un datatset standard della distribuzione.
I dati impiegati si riferiscono a misure (in cm) di quattro caratteristiche (lungezza e larghezza dei sepali e lungezza e larghezza dei petali) rispettivamente di 50 fiori di iris di tre specie differenti: Iris setosa, Iris versicolor e Iris virginica. Si inizia l’analisi caricando la libreria rpart e il dataset: > library(rpart)
> data(iris) > iris
Sepal.Length Sepal.Width Petal.Length Petal.Width Species
1 5.1 3.5 1.4 0.2 setosa
9.2 Alberi di classificazione 175
[...]
150 5.9 3.0 5.1 1.8 virginica
Il fit dell’albero di classificazione `e molto semplice:
> ir.rp <- rpart(Species ~ ., data=iris)
Il risultato del fit si ottiene con la chiamata: > ir.tr
n= 150
node), split, n, loss, yval, (yprob) * denotes terminal node
1) root 150 100 setosa (0.33333333 0.33333333 0.33333333)
2) Petal.Length< 2.45 50 0 setosa (1.00000000 0.00000000 0.00000000) *
3) Petal.Length>=2.45 100 50 versicolor (0.00000000 0.50000000 0.50000000)
6) Petal.Width< 1.75 54 5 versicolor (0.00000000 0.90740741 0.09259259) *
7) Petal.Width>=1.75 46 1 virginica (0.00000000 0.02173913 0.97826087) *
da cui si vede che l’albero ha 3 nodi terminali. La classificazione dei soggetti nelle tre specie come risulta dalle regole dell’albero si ottiene con la chiamata:
> pred <- predict(ir.rp, type="class")
e la sua accuratezza si pu`o valutare con la funzione table, confrontando la classificazione reale con
quella ottenuta dall’algoritmo: > table(iris$Species, pred)
setosa versicolor virginica
setosa 50 0 0
versicolor 0 49 1
virginica 0 5 45
Si nota che solo 6 fiori su 150 sono classificati in modo errato(error rate ER = 4%). Ovviamente anche qui vale il discorso fatto per le funzioni discriminanti: la performance dell’albero `e ottimale per il set di dati su cui `e costruito, ma `e necessario convalidarla su dati indipendenti in modo da avere una stima realistica della sua efficienza.
Per avere la rappresentazione grafica dell’albero, che di solito rappresenta l’obiettivo dell’analisi, si eseguono le chiamate:
> plot(ir.rp)
> text(ir.rp, use.n=TRUE)
che producono l’output di Fig. 9.2. La funzione plot disegna lo scheletro dell’albero, mentre la funzione text etichetta i nodi con le condizioni di divisione o, per i nodi terminali, con l’etichetta di gruppo. L’opzione use.n = T RU E serve ad aggiungere ai nodi terminali il numero di soggetti delle varie classi che finiscono in quel nodo. Si vede ad esempio che il nodo relativo al gruppo “setosa” `e un nodo puro, cio`e contiene solo soggetti della specie Iris setosa, mentre entrambi gli altri non lo sono e contengono sia soggetti della classe dominante che da il nome al nodo, sia soggetti di un’altra classe. Come si vede solo due delle variabili (quelle riguardanti le dimensioni dei petali) entrano nella costruzione dell’albero.
Per verificare che l’abero completo sia il migliore o se sia invece opportuno effettuare una potatura
(pruning) si pu`o far uso della chiamata seguente:
| Petal.Length< 2.45 Petal.Width< 1.75 setosa 50/0/0 versicolor 0/49/5 virginica 0/1/45
Figura 9.2: Albero di classificazione per i i dati relativi a tre specie di iris.
che produce il grafico di Fig. 9.3. In tale grafico si hanno sulle ascisse i valori del parametro α (che in R `e chiamato cp) che corrispondono ad alberi con diversi numeri di foglie (valori riportati sull’asse delle ascisse addizionale, posto in alto). In ordinata si hanno i valori degli error rate in rivalidazione per ognuno degli alberi considerati, ottenuti con il processo 10-fold cross-validation. Le barre d’errore sono a loro volta ottenute dal processo bootstrap, semplicemente calcolando la deviazione standard delle 10 stime di error rate per ciscun albero. Gli error rate vengono espressi relativamente all’error rate dell’albero a un unico nodo terminale costruito con i dati campionari, al quale spetterebbe in ordinata il valore 1 (si noti che `e possibile ottenere nel processo bootstrap error rate relativi superiori
a 1). Solitamente si sceglie l’albero pi`u piccolo, quindi pi`u a sinistra possibile, il cui error rate sia al
di sotto della linea orizzontale tratteggiata che coincide con il valore del minimo assoluto pi`u il suo
errore. Questo metodo di scelta, largamente usato in ambito multivariato, va sotto il nome di tecnica 1SE. Nel caso in questione l’albero ottimale `e proprio quello con tre foglie.