Different use of neighbors in kNN classification algorithm

Question

Suppose for each sample S in training set TS I already know the k nearest neighbors.

The standard algorithms usually give S the same label as the majority of S's neighbors has.

What other use of nearest neighbors could I make? For instance, if I have not 3, not 5, but more neighbors, would it make sense to create a temporary model based on them and only then classify S? If so, what model would you recommend?

Answer 1

I guess by saying

For instance, if I have not 3, not 5, but more neighbors

you define a neighbor as close to the instance of interest. This is a common problem. Either you have to fix the number of neighbors (via k) or define a maximum radius so that all instances within the resulting circle count as neighbor.

Fixing k

When k is fixed, you could add the distance to calculate a weighted score and select the class label whose score is the minimum instead of for the majority.

Let

• x be the example which shall be classified
• dist the distance metric used
• $x_1,...,x_k$ the nearest neighbors
• $c_1,...,c_k$ the classes of the nearest neighbors respectively.

For all classes, calculate the average distance from x to examples with class c $classdistance(x,c)=\frac{1}{|\{c_i|c_i=c,i=1,...,k\}|}\sum_{i,c_i=c}^{k}dist(x,x_i)$

The score for c given x is simply the normalized similarity across all classes, i.e. $score(c|x)= 1-\frac{classdistance(x,c)}{\sum_{c'}classdistance(x,c')}$

Fixing distance

Let's say the maximum distance is d, so that we can define an $\hat{x}$ to be a neighbor of $x$ if $dist(x,\hat{x})<=d$.

So the easiest approach would be to calculate a weighted score as $classdistance(x,c)= AVG_{\hat{x},dist(\hat{x},x)<=d,class(\hat{x}=c)}(dist(x,\hat{x}))$

In another approach, one could throw the distance information with the specified radius away (by setting the distance to 1 for all instances within the radius) and instead uses a kernel function, hence introducing one's own weights. For example, with a uniform kernel, the selection of the final class label would be equivalent to the majority. But others are available to weight the instances farther away less. See Wikipedia - Kernel (statistics) for more functions and a graphical illustration.