Capitolo 13 K-Nearest Neighbors (I K vicini più vicini: KNN)
13.1 Introduzione
Dato un numero intero positivo \(K\) ed una osservazione di test \(x\), il classificatore K-Nearest Neighbors (KNN) dapprima identifica i \(K\) punti nei dati di training più prossimi a \(x\); poi stima la probabilità che l’osservazione di test appartenga a ciascuna delle classi \(j\) della variabile di risposta come la frazione di punti in \(K\) il cui valore di risposta è uguale a \(j\). Infine, classifica l’osservazione di test \(x\) alla classe con il valore più alto di probabilità stimata.
Anche se KNN è un approccio mollto semplice, può spesso produrre risultati sorprendentemente buoni. Il punto chiave nell’applicazione del KNN è la scelta di \(K\), il numero di osservazioni più prossime da includere nel “vicinato” di un dato punto. Quando \(K\) è piccolo, il metodo produce soglie di decisione molto flessibili. Mano a mano che \(K\) cresce, il metodo diventa meno flessibile e produce soglie di decisione sempre piuttosto simili a rette. \(K\) è usualmente scelto usando il osiddetto metodo di “cross-validation”.
Un vantaggio di KNN è che è approccio totalmente non parametrico, poiché non si formula alcun assunto sulla forma delle soglie di decisione. Pertanto, KNN può ottenere risultati migliori di LDA e regressione logistica, specialmente quanto le soglie di decisione sono foremente non lineari. Dall’altra parte, KNN è meno informativa di LDA e regressione logistica, poiché non fornisce alcuna indicazione intuitiva su qualie predittori sono importanti per discriminare le classi di risposta, poiché non produce una tabella di coefficienti. Infine, KNN “soffre” in maniera abbastanza importante quando si hanno molti predittori, perché al crescere del numero di predittori si ha una corrispondente crescita (non lineare) del numero di osservazioni necessarie per ottenere delle previsioni attendibili.
13.2 Esempio: Dati stock market
Applicheremo ora KNN ai dati Smarket; sono gli stessi dati stock market usati per LDA.
Il package caret contiene la funzione knn3Train() che ritorna direttamente le previsioni
per la variabile di risposta. Questa funzione richiede i valori dei predittori sia per i dati di
training che per i dati di test, le etichette delle classi per le osservazioni di training, ed un
valore per \(K\). Useremo ancora i dati dal 2005 come insieme di test e tutte le osservazioni
rimanenti per il training:
## Loading required package: lattice## Loading required package: ggplot2train <- (Smarket$Year < 2005)
train_X <- Smarket[train, c("Lag1", "Lag2")]
test_X <- Smarket[!train, c("Lag1", "Lag2")]
train_Y <- Smarket[train, "Direction"]
test_Y <- Smarket[!train, "Direction"]
# random seed necessario perché R assegnerà a caso valori con uguale probabilità
set.seed(123)
knn_pred_1 <- as.factor(knn3Train(train_X, test_X, train_Y, k = 1, use.all = FALSE))
confusionMatrix(data = knn_pred_1, reference = test_Y, positive = "Up")## Confusion Matrix and Statistics
##
## Reference
## Prediction Down Up
## Down 43 58
## Up 68 83
##
## Accuracy : 0.5
## 95% CI : (0.4366, 0.5634)
## No Information Rate : 0.5595
## P-Value [Acc > NIR] : 0.9751
##
## Kappa : -0.0242
##
## Mcnemar's Test P-Value : 0.4227
##
## Sensitivity : 0.5887
## Specificity : 0.3874
## Pos Pred Value : 0.5497
## Neg Pred Value : 0.4257
## Prevalence : 0.5595
## Detection Rate : 0.3294
## Detection Prevalence : 0.5992
## Balanced Accuracy : 0.4880
##
## 'Positive' Class : Up
## Usando k = 1 solo il 50% delle osservazioni del test sono clasificate correttamente.
Possiamo provare a ripetere le analisi usando k = 3:
knn_pred_3 <- as.factor(knn3Train(train_X, test_X, train_Y, k = 3, use.all = FALSE))
confusionMatrix(data = knn_pred_3, reference = test_Y, positive = "Up")## Confusion Matrix and Statistics
##
## Reference
## Prediction Down Up
## Down 48 55
## Up 63 86
##
## Accuracy : 0.5317
## 95% CI : (0.4681, 0.5946)
## No Information Rate : 0.5595
## P-Value [Acc > NIR] : 0.8294
##
## Kappa : 0.0427
##
## Mcnemar's Test P-Value : 0.5193
##
## Sensitivity : 0.6099
## Specificity : 0.4324
## Pos Pred Value : 0.5772
## Neg Pred Value : 0.4660
## Prevalence : 0.5595
## Detection Rate : 0.3413
## Detection Prevalence : 0.5913
## Balanced Accuracy : 0.5212
##
## 'Positive' Class : Up
## Con k = 3 otteniamo risultati leggermente migliori (53.6% correttamente classificati).
Nel tentativo di migliorare i risultati, cercheremo il valore ottimo di \(K\) calcolando il
valore di tasso d’errore sui dati di test su più valori di \(K\) e scegliendo il valore di
\(K\) che minimizza lo minimizza:
kmax <- 100
test_error <- numeric(kmax)
for (k in 1:kmax) {
knn_pred <- as.factor(knn3Train(train_X, test_X, train_Y, k = k, prob = FALSE,
use.all = FALSE))
cm <- confusionMatrix(data = knn_pred, reference = test_Y, positive = "Up")
test_error[k] <- 1 - cm$overall[1]
}
k_min <- which.min(test_error)
knn_pred_min <- as.factor(knn3Train(train_X, test_X, train_Y, k = k_min, prob = FALSE,
use.all = FALSE))
cm <- confusionMatrix(data = knn_pred_min, reference = test_Y, positive = "Up")
ggp <- ggplot(data.frame(test_error), aes(x = 1:kmax, y = test_error)) +
geom_line(colour="blue") +
geom_point(colour="blue") +
xlab("K (#vicini)") + ylab("Errore di test") +
ggtitle(paste0("Valore ottimo di K = ", k_min,
" (errore minimo = ",
format((1 - cm$overall[1])*100, digits = 4), "%)"))
print(ggp)
k = 72 sembra fornire il tasso d’errore di test più basso (attorno al 46%). Per
concludere, sembra che KNN non fornisca un risultato migliore di LDA e QDA.
Inoltre, per verificare le prestazioni di KNN, bisognerebbe in realtà applicare il risultato così
ottenuto su un terzo set di dati.
Il package caret fornisce molte funzioni molto generali, quale train(), per
adattare un gran numero di tipi di modelli predittivi usando la cross-validation o altri
metodi di ricampionamento; queste fuzioni sono tuttavia un po’ più complesse da usare.