# k-nn classifier, suspect results, maybe underfitting?

I am using the k-nn classifier in Weka to experiment on the "audiology" dataset.

I am using 10-fold validation, and recording average error rates for 1 <= k <= 200.

I am trying three different version of k-nn. The one labelled "1" using simple voting, that is, each neighbour's vote is a given a weight of 1 indepently of how close said neighbour is.

The one labelled 2 gives each vote a weight of 1/distance, so neighbours which are are further will have elss of a same in how the sample is classified

The one labelled 4 gives a weight of 1-distance.

Note that these are as implemented in weka, in the method make Distribution, class IBk:

switch(this.m_DistanceWeighting) {
case 2:
weight = 1.0D / (distances[i] + 0.001D);
break;
case 4:
weight = 1.0D - distances[i];
break;
default:
weight = 1.0D;
}


(I understand weka automatically normalizes feature vectors so all distances are in range 0 to 1?)

This is the result:

I am struggling to interpret this. By using k = 1 (or anyway a very small k) I would expect the classifier to underfit the data, but it seems to be then it obtains the best results?

Any thoughts on this?

The audiology dataset contains 226 instances, 70 attributes, and 24 classes. Also note that this dataset has only categorical features, and there is thus nothing to normalise (as you suggested weka does), since when comparing categorical feature values weka simply assigns a 0-distance if the feature values match, and a 1-distance otherwise.

First of all note how small the data-set is. And provided that you do ten-fold cross validation this means that whenever the k > 100 or so the 'prediction' by the model simply becomes the most frequent class value in the data set, which explains the similar performance of each model when k becomes very large.

Now lets analyse the classes. You have 24 classes on about 200 instances (taking into account the 9 folds that you train on). Assuming the classes are equally spread among the instances (I did not verify this, but lets take the worst case scenario) this would mean that each class value has about 8 instances. Now if you take k=50 then chances are unlikely that the majority class is the one that you are looking for (you would need to catch all relevant neighbours and make sure that the 42 irrelevant neighbours do not have a large amount of the same class values).

This largely explains why a small amount of neighbours in your case on this dataset works better then a larger amount of neighbours. In addition to that the fact that all features are categorical (and you have 70 of them!) means that the distance is not going to be as effective.

This last observation is perhaps most easily seen when we assume that all instances can be classified according to just the first feature. Let's say that the first feature in fact is the class. Now when you are going to compute a distance measure over 70 features (with each feature being equally important) then you will fail at correctly predicting the class of a instance based on its k neighbours.

All these reasons explain the trend that you see in the model performance with respect to k. Any variability between the methods seems mostly due to the randomness of the 10-fold cross validation in combination with the few amount of instances in your data set.

I recommend you to analyse your data-set in more detail and try to work out how the different aspects of your dataset relate to the algorithm that you want to use, and with what parameters. I personally do no recommend a k-nn algorithm for this dataset.

• That is one of the best answers anybody has given me on the SE network, thank you so much!! :) I assume I should prefer datasets with a large number of instances and prevalently continuous features, or else find a better way to consider categorical data than simply match/mismatch? – MrD Nov 14 '15 at 23:19
• Thanks, you are most welcome! and yes that is indeed correct. Although besides increasing the amount of instances I would also consider limiting the amount of class values. A 24-class classification problem is quite hard for lots of techniques, especially when insufficient data is available, or redundant features are in place. k-NN is also very susceptible to noisy features (as I pointed out with my first feature = class example) so some feature selection/pre-processing may also do wonders. Good luck! – Sjoerd Nov 14 '15 at 23:39