2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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