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.
9.3 Random Forests
La tecnica di Random Forests, estensione dell’approccio relativo alla costruzione degli alberi di classificazione, `e stata recentemente proposta da Breiman [7].
L’algoritmo Random Forests si basa sulla costruzione di molti alberi di classificazione. Ogni singolo caso viene fatto passare in tutti gli alberi della foresta; ognuno di essi fornisce una classificazione. La
catalogazione finale viene quindi fatta secondo il criterio di maggioranza: la classe con pi`u voti `e quella
a cui viene assegnato il caso in esame.
Si abbia un campione di n soggetti di cui `e disponibile la classificazione in k classi secondo un dato fattore di interesse; su ognuno dei soggetti si misurano p variabili (categoriali o continue). Per la crescita degli alberi della foresta si usano le seguenti regole:
• Si seleziona un set di n soggetti (campionamento con reinserimento) dal campione in esame.
Questo set di dati ver`a usato nella costruzione dell’albero come training set. I casi non selezionati
(oob, out-of-bag) vengono usati per valutare l’error rate dell’albero e per stabilire l’importanza delle p variabili in sede di classificazione.
• Si sceglie un numero k ≤ p. Ad ogni split k predittori sono selezionati casualmente e solo essi vengono usati per valutare la bipartizione ottimale.
9.3 Random Forests 177
cp
X−val Relative Error
0.0 0.2 0.4 0.6 0.8 1.0 1.2 Inf 0.47 0.066 1 2 3 size of tree
Figura 9.3: Scelta del miglior albero di classificazione per i dati relativi a tre specie di iris. La linea tratteggiata corrisponde all’estremo superiore dell’intervallo di confidenza per l’albero a error rate minore. L’albero migliore `e quello con tre nodi terminali, l’unico con error rate inferiore al livello identificato dalla linea tratteggiata.
• Ogni albero viene fatto crescere fino alla sua massima estensione, senza utilizzare tecniche di pruning.
L’error rate globale della foresta dipende da due fattori: la correlazione esistente fra gli alberi e
la bont`a dei singoli alberi. Aumentando la correlazione aumenta l’error rate, mentre aumentando la
bont`a dei singoli alberi l’erorr rate diminuisce [7]. Diminuendo il valore di k si riducono correlazione
fra gli alberi e bont`a dei singoli alberi, mentre aumentandolo si aumentano entrambi. Un valore di k
intermedio risulter`a quindi ottimale.
Data la metodologia bootstrap con cui vengono costruite, le foreste offrono una stima non distorta dell’error rate, generalizzabile al di fuori del campione utilizzato per stimarlo. Non vi `e quindi necessit`a di rivalidazione su un campione indipendente.
9.3.1 Importanza delle variabili
Un caratteristica particolarmente attraente delle Random Forests `e che esse generano una stima di quali variabili sono importanti per la classificazione, offrendo la possibilit`a di selezionare solo un sottoinsieme che risulti ottimale dal punto di vista statistico.
La procedura che permette di fare questa valutazione `e la seguente. Per ogni albero si classificano i
casi oob per quel particolare albero. Per il j-esimo albero si abbiano Cj casi classificati correttamente.
Si permutano quindi casualmente i valori della i esima variabile per i casi oob e si riclassificano i
soggetti. Sia CPij i casi classificati correttamente dopo la permutazione. Si calcola il valore di
importanza della i-esima variabile Iij:
Iij= Cj− CPij
Si ripete il procedimento su tutti gli alberi della foresta e si fa la media dei valori ottenuti:
Ii= mean(Iij)
l’indice Ii stima l’importanza della i-esima variabile. L’errore standard di tale stima viene valutato
Dividendo la stima Ii per il suo errore standard si ha la stima normalizzata dell’importanza della i-esima variabile.
Un altro indice che permette di valuare l’importanza di una variabile `e sommare su tutti gli alberi
della foresta la decrescita dell’indice di impurit`a di Gini dovuto all’uso di ciascuna variabile. Questa
stima di importanza `e solitamente consistente con la precedente.
In R `e possibile avvaleri di questa tecnica mediante le funzioni implementate nella libreria aggiun-tiva randomF orest.
Esempio
Per illustrare la costruzione di una foresta si fa uso del dataset iris gi`a analizzato in precedenza. La
funzione per costruire una Random Forest `e randomF orest, il cui uso `e il seguente: > library(randomForest)
> set.seed(100) # scelta del seme random
# per un’analisi riproducibile
> iris.rf <- randomForest(Species ~ ., data=iris, importance=TRUE)
In questo caso si usa l’opzione importance = T RU E per richiedere che, durante la costruzione della foresta, venga valutata l’importanza delle variabili. Alte possibili opzioni di uso comune sono ntree (per specificare il numero di alberi che fanno parte della foresta, di default 500) e mtry (il numero di variabili da considerare a ogni split, di default pari alla radice del numero totale delle variabili). Il risultato della chiamata `e il seguente:
> iris.rf Call:
randomForest(formula = Species ~ ., data = iris, importance = TRUE) Type of random forest: classification
Number of trees: 500 No. of variables tried at each split: 2
OOB estimate of error rate: 4%
Confusion matrix:
setosa versicolor virginica class.error
setosa 50 0 0 0.00
versicolor 0 47 3 0.06
virginica 0 3 47 0.06
Si ha una stima dell’error rate - pari al 4% - e la matrice di classificazione dei vari casi. Per visualizare la stima dell’importanza delle variabili si usa la chiamata seguente: > importance(iris.rf)
setosa versicolor virginica MeanDecreaseAccuracy
Sepal.Length 1.371545 1.6961553 1.895610 1.3133882 Sepal.Width 0.973110 0.3076256 1.165498 0.6912411 Petal.Length 3.731889 4.5337883 4.100242 2.5275034 Petal.Width 3.833735 4.6327332 4.365181 2.5581178 MeanDecreaseGini Sepal.Length 9.572410 Sepal.Width 2.221248 Petal.Length 42.076043 Petal.Width 45.369419