Nearest neighbor where several vectors have exact same values

Question

I'm trying to classify 6-dimension feature vectors in two different classes using the nearest neighbor algorithm. After analyzing my training data, I realized that the same vector is present numerous times in both classes. What does this mean?

• Does it indicate a bad feature choice?
• During training, should I group identical vectors and label it with the class which has the highest count? (i.e., vector A is present in both class A and B, but label it class A since vector A is found more often in class A than in class B)
• something else?

Answer 1

It means that their is no deterministic relationship from your feature vectors to the class it belongs to.

Possible explanations include:

1. The feature representation is not sufficient,
2. The feature representation is noisy (unlikely, since the vectors are exactly the same),
3. The underlying process is not deterministic.

If you are able to engineer the feature representation I would say to try to get a richer one. (This depends on the application).

Maybe this still fails and you should model the uncertainty by treating the class relationship as a random variable. In the case of KNN this is easy - just take something like $p(C|x) = \frac{\text{#vectors of class C in neighbourhood of size k}}{k}$.

Other approaches, namely the probabilistic ones like logistic regression, do this naturally.