What is the optimal value of $k$, for an unweighted Euclidean kNN classifier applied to the Iris data set?
Where optimal implies the value for $k$ which leads to the lowest generalisation error.
$\begingroup$
$\endgroup$
-
2$\begingroup$ Define "optimal" $\endgroup$ – Zach Jul 3 '12 at 16:27
-
$\begingroup$ I know what classification error rates are and I know you can look to find the classifier with the lowest estimate average error rate but what does generalisation error mean? $\endgroup$ – Michael R. Chernick Jul 3 '12 at 16:48
-
$\begingroup$ @image_doctor you also need to explain how you are going to estimate the generalization error... is it the error on a separate test set or with cross-validation? $\endgroup$ – Pardis Jul 3 '12 at 16:50
-
$\begingroup$ @MichaelChernick In this context generalisation error is the term for the average error on unseen data. It is often estimated by some derived metric on test data. Such as n-Fold CV, 50/50 Holdout or Bootstrapping. $\endgroup$ – image_doctor Jul 3 '12 at 17:00
-
$\begingroup$ That then is what I would call average of the class conditional error rates. In a two class problem there are two error rates. So you would try to minimize a weighted average of the two. often the weighting could be equal but not always because sometimes the consequences of making one type error can be a lot greater than the for making the other. For the Iris dat you have three classes and equal weighting would probably make sense. $\endgroup$ – Michael R. Chernick Jul 3 '12 at 17:10
$\begingroup$
$\endgroup$
Lets say you want to use Accuracy (or % correct) to evaluate "optimal," and you have time to look at 25 values for k. The following R code will answer your question using 15 repeats of 10-fold cross-validation. It will also take a long time to run.
library(caret)
model <- train(
Species~.,
data=iris,
method='knn',
tuneGrid=expand.grid(.k=1:25),
metric='Accuracy',
trControl=trainControl(
method='repeatedcv',
number=10,
repeats=15))
model
plot(model)
> confusionMatrix(model)
Cross-Validated (10 fold, repeated 15 times) Confusion Matrix
(entries are percentages of table totals)
Reference
Prediction setosa versicolor virginica
setosa 33.3 0.0 0.0
versicolor 0.0 31.9 1.2
virginica 0.0 1.4 32.1
So, by this criteria, I get an answer of 17, but it looks like the "true" value could lie anywhere between 5 and 20. You can substitute "Kappa" or some other metric if you want, and add more cv-folds as well. You can also try different methods of cross validation, such as leave-one-out, or bootstrap re-sampling.
/Edit: in response for your request for variety, I wrote this function to calculate a variety of metrics for multi-class problems:
#Multi-Class Summary Function
#Based on caret:::twoClassSummary
require(compiler)
multiClassSummary <- cmpfun(function (data, lev = NULL, model = NULL){
#Load Libraries
require(Metrics)
require(caret)
#Check data
if (!all(levels(data[, "pred"]) == levels(data[, "obs"])))
stop("levels of observed and predicted data do not match")
#Calculate custom one-vs-all stats for each class
prob_stats <- lapply(levels(data[, "pred"]), function(class){
#Grab one-vs-all data for the class
pred <- ifelse(data[, "pred"] == class, 1, 0)
obs <- ifelse(data[, "obs"] == class, 1, 0)
prob <- data[,class]
#Calculate one-vs-all AUC and logLoss and return
cap_prob <- pmin(pmax(prob, .000001), .999999)
prob_stats <- c(auc(obs, prob), logLoss(obs, cap_prob))
names(prob_stats) <- c('ROC', 'logLoss')
return(prob_stats)
})
prob_stats <- do.call(rbind, prob_stats)
rownames(prob_stats) <- paste('Class:', levels(data[, "pred"]))
#Calculate confusion matrix-based statistics
CM <- confusionMatrix(data[, "pred"], data[, "obs"])
#Aggregate and average class-wise stats
#Todo: add weights
class_stats <- cbind(CM$byClass, prob_stats)
class_stats <- colMeans(class_stats)
#Aggregate overall stats
overall_stats <- c(CM$overall)
#Combine overall with class-wise stats and remove some stats we don't want
stats <- c(overall_stats, class_stats)
stats <- stats[! names(stats) %in% c('AccuracyNull', 'Prevalence', 'Detection Prevalence')]
#Clean names and return
names(stats) <- gsub('[[:blank:]]+', '_', names(stats))
return(stats)
})
It's a doozy of a function, so it's going to slow down caret a bit, but I'd be very happy if you posted the results of your 1000 repeats of 10-fold CV (I have neither the time not the computational capacity to attempt this at present). Here's my code for 15 repeats of 10-fold CV. Note that you can easily modify this code to try other re-sampling methods, such as bootstrap sampling:
library(caret)
set.seed(19556)
model <- train(
Species~.,
data=iris,
method='knn',
tuneGrid=expand.grid(.k=1:30),
metric='Accuracy',
trControl=trainControl(
method='repeatedcv',
number=10,
repeats=15,
classProbs=TRUE,
summaryFunction=multiClassSummary))
Both ROC and LogLoss seem to peak around 8:
While sensitivity and specificity seem to peak around 15:
Here's some code to output all the plots as a pdf:
dev.off()
pdf('plots.pdf')
for(stat in c('Accuracy', 'Kappa', 'AccuracyLower', 'AccuracyUpper', 'AccuracyPValue',
'Sensitivity', 'Specificity', 'Pos_Pred_Value',
'Neg_Pred_Value', 'Detection_Rate', 'ROC', 'logLoss')) {
print(plot(model, metric=stat))
}
dev.off()
If you put a gun to my head, I'd probably say 8...
-
$\begingroup$ Thanks very much for that, I ran your code with 1,000 repetitions. The most interesting values seemed to be 14 and 17. $\endgroup$ – image_doctor Jul 3 '12 at 23:30
-
2$\begingroup$ @image_doctor: you should also try with "method=boot632" and "method=boot", with a high number of repetitions, and see what number those two methods pick. Also, if my answer is sufficient, feel free to make it as "accepted." $\endgroup$ – Zach Jul 5 '12 at 14:39
-
$\begingroup$ Thanks for your suggestions and your excellent answer. I was hoping to get a diversity of answers in an attempt to draw some a more general conclusions. A sample of one, doesn't leave much space for any variance calculations ;) If no new answers appear after some time, I will very happily make yours the accepted answer. $\endgroup$ – image_doctor Jul 5 '12 at 17:10
-
1$\begingroup$ @image_doctor: You can use the code I posted to get a variety of answers. Try setting the metric to 'Kappa' rather than 'Accuracy' and see what you get for an answer. Then try both metrics, with the train control method set to 'boot', then 'boot632,' 'LOOCV,' and 'LGOCV.' That will get you to a sample size of 10. Next, you can write a custom
summaryFunction,perhaps starting with the average of AUC, Sensitivity, Specificity, Precision, and Recall for each of the three classes. That will get you to a sample size of 35... $\endgroup$ – Zach Jul 6 '12 at 14:31 -
1$\begingroup$ I don't really see a whole lot to add to his answer. Cross-Validation or Bootstrapping are by far the most appropriate ways to understand this. You limited us to Euclidean distance. He appropriately retained uncertainty in his answer (5-20). He chose a common error metric (I'd have chose multivariate log-loss, but it's not available by default in caret). And he introduced an appropriate tool:
caretin R. $\endgroup$ – Shea Parkes Jul 6 '12 at 14:32
