3
$\begingroup$

I am working on KNN algorithm.

I uploaded and prepared the following dataset.

DATA<- read.table("http://archive.ics.uci.edu/ml/machine-learning-databases/breast-cancer-wisconsin/wdbc.data",sep=",",stringsAsFactors = FALSE)

I used the following function to detect the outliers

outlier(DATA)

       V3        V4        V5        V6        V7        V8        V9       V10       V11 
2.811e+01 3.928e+01 1.885e+02 2.501e+03 1.634e-01 3.454e-01 4.268e-01 2.012e-01 3.040e-01 
      V12       V13       V14       V15       V16       V17       V18       V19       V20 
9.744e-02 2.873e+00 4.885e+00 2.198e+01 5.422e+02 3.113e-02 1.354e-01 3.960e-01 5.279e-02 
      V21       V22       V23       V24       V25       V26       V27       V28       V29 
7.895e-02 2.984e-02 3.604e+01 4.954e+01 2.512e+02 4.254e+03 2.226e-01 1.058e+00 1.252e+00 
      V30       V31       V32 
2.910e-01 6.638e-01 2.075e-01 

My question as follows:

Does the presence of the outliers affect the 1NN algorithm? and what is the best way of treatment?

$\endgroup$
2
  • 1
    $\begingroup$ No, since the far away points are likely never to be selected anyway. $\endgroup$ Sep 28, 2018 at 11:04
  • $\begingroup$ @user2974951, how? could you please clarify more? $\endgroup$
    – jeza
    Sep 28, 2018 at 11:08

2 Answers 2

3
$\begingroup$

In general (so this isn't an answer with reference to your data), an outlier in one feature will mess up your classification of that point, especially when using a Euclidean distance metric. If you have 100 features, and a massive outlier in one of them, it can basically wash out the signal contained in the other 99. You can mitigate this by using other distance metrics (such as an L1 norm).

Outliers in your training data won't be as much of a problem. When you try to label a new example, it's unlikely that any of the outlier data will be one of its K nearest neighbours (I think this is what user2974951 is getting at) so you should be OK.

$\endgroup$
4
  • 1
    $\begingroup$ Yes, if the dimension is small enough the distance to these outliers will be huge and so they will likely never be selected as a near neighbor. If, however, the dimension is high, then (because of curse of dimensionality) it may become a little of a problem, so another metric may be better off. $\endgroup$ Sep 28, 2018 at 11:14
  • $\begingroup$ @user297495, gazza89. My data dimension is (569)(32). If I understand you, outliers will affect KNN in this case and L1 would give a better result than Euclidean distance. $\endgroup$
    – jeza
    Sep 28, 2018 at 11:40
  • 1
    $\begingroup$ Hard for us to say what is and what isn't high dimensional, you should try both and see if there are major differences. $\endgroup$ Sep 28, 2018 at 11:49
  • 1
    $\begingroup$ What I actually said was more subtle. If you have outliers in your training data, as long as it's a relatively small fraction of the data, it shouldn't matter. If you want to use knn to classify an unlabeled example, you'd better hope that that example doesn't contain outliers in any feature. $\endgroup$
    – gazza89
    Sep 28, 2018 at 22:41
3
$\begingroup$

It depends on your implementation of KNN but it CAN have an impact on your error. If you're using KNN where K=1 then you're telling your model to only find the training example that is closest to the point you're searching for and return its class. If you use K>1 you're telling it that you want to find the closest K training examples and then do a majority vote with those examples. Using K>1 will smooth out your decision boundaries and, assuming there isn't a clump of outliers, negate any impact that outliers will have on your predictions.

That being said, increasing K also introduces an increase in bias so there is the possibility that your testing error will go up as a result.

TLDR: As long as K>1 and there aren't a cluster of outliers in your data then you have nothing to worry about since KNN's majority vote will negate the effects of outliers.

$\endgroup$
4
  • $\begingroup$ actually I am using KNN=1NN. So what is the best way to treat outliers? In R if that possible? $\endgroup$
    – jeza
    Sep 30, 2018 at 15:00
  • 1
    $\begingroup$ @jeza If you want your KNN implementation to handle them then i would suggest just increasing K to be 3 or 5. With that being done all you do is find the 3 (or 5) closest training examples and return the class that occurs MOST in that set as the algorithm's prediction. Unfortunately, i don't use R so i can't provide an example in it. But the algorithm is as simple as finding the K closest training examples and returning the class that occurs the most times in that set of examples. $\endgroup$
    – Paul
    Oct 1, 2018 at 2:42
  • 1
    $\begingroup$ @jeza I guess you could also remove them from your training data set should you find that they don't generalize well. Doing so would slightly decrease prediction time but it probably wouldn't do much else. But increasing K by itself should be enough to get rid of potential error from using 1NN. $\endgroup$
    – Paul
    Oct 1, 2018 at 2:52
  • $\begingroup$ I have tried to remove the outliers but then I do not know the code does not work because of the different level of the matrix. I also read that remove the outliers is not the best way. $\endgroup$
    – jeza
    Oct 1, 2018 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.