kNN - what happens if more than K observation have the same distance to the centroid of the cluster

Question

EDIT It was pointed out in the Answers-section that I am confusing k-means and kNN. Indeed I was thinking about kNN but wrote k-means since I'm still new to this topic and confuse the terms quite often. So here is the changed question.

I was looking at kNN today and something struck me as odd or - to be more precise - something that I was unable to find information about namely the following situation.

Imagine that we pick kNN for some dataset. I want to remain as general as possible, thus $k$ will not be specified here. Further we select, at some point, an observation where the number of neighbors that fulfill the requirement to be in the neighbourhood are actually more than the specified $k$.

What criterion/criteria should be applied here if we are restricted to use the specific K and thus cannot alter the structure of the neighborhood (number of neighbors). Which observations will be left out and why? Also is this a problem that occurs often, or is it something of an anomaly?

Answer 1

You are mixing up kNN classification and k-means.

There is nothing wrong with having more than k observations near a center in k-means. In fact, this it the usual case; you shouldn't choose k too large. If you have 1 million points, a k of 100 may be okay. K-means does not guarantee clusters of a particular size. Worst case, clusters in k-means can have only one element (outliers) or even disappear.

What you probably meant to write, but got mixed up, is what to do if a point is at the same distance to two centers.

From a statistical point of view, it doesn't matter. Both have the same squared error.

From an implementation point of view, choose any deterministic rule, so that your algorithm converges and doesn't go into an infinite loop of reassignment.

Update: with respect to kNN classification:

There are many ways to resolve this, that will surprisingly often work just as good as the other, without a clear advantage of one over the other:

1. randomly choose a winner from the tied objects
2. take all into account with equal weighting
3. if you have m objects at the same distance where you expected only r, then put a weight of r/k on each of them.

E.g. k=5.

distance   label   weight
    0        A       1
    1        B       1
    1        A       1
    2        A      2/3
    2        B      2/3
    2        B      2/3

yields A=2.66, B=2.33

The reason that randomly choosing works just as good as the others is that usually, the majority decision in kNN will not be changed by contributions with a weight of less than 1; in particular when k is larger than say 10.

Answer 2

K-means does not make an assumption regarding how many observations should be assigned to each cluster. K is simply the number of clusters one chooses to generate. During each iteration, each observation is assigned to the cluster having the nearest mean. There is no assumption that all clusters should have a comparable number of observations assigned (i.e., for N observations, there is no expectation that each cluster should have ~ N/K observations assigned).

It is quite possible that the numbers of observations in the various clusters are highly imbalanced. This can be due to the distribution of the data, the number of clusters chosen (K), or even how the cluster means are initialized.

Answer 3

[Since you've updated your question to refer to a different algorithm (changed k-means to kNN), I'm adding this as a separate answer specifically for kNN.]

It appears you may still be confusing kNN with k-means. kNN does not have multiple stages of refinement, nor does it require computing centroids. It is a lazy learner that classifies a new observation by examining the k training observations that are closest to the new observation and picks whichever class is most prevalent among those k training observations. Note that the distances are not relative to a cluster centroid. You don't have to worry about there being more than k training observations in the neighborhood of the new observation because the neighborhood isn't based on a threshold distance - it is defined simply by the k points nearest to the new observation (i.e., it changes for each new observation being evaluated).

A possible pathological case is when multiple training observations lie at exactly the same distance from the new observation, which would require you to evaluate more than k neighbors. But you would still simply pick the class that is most prevalent among that group of observations.