CODEWITHSUNDEEP
algorithmmachine-learningclassificationknn
Daniel
Daniel

Reputation: 7714

Correct implementation of weighted K-Nearest Neighbors

From what I understood, the classical KNN algorithm works like this (for discrete data):

How would I introduce weights on this classic KNN? I read that more importance should be given to nearer points, and I read this, but couldn't understand how this would apply to discrete data.

For me, first of all, using argmax doesn't make any sense, and if the weight acts increasing the distance, than it would make the distance worse. Sorry if I'm talking nonsense.

Upvotes: 2

Views: 2065

Answers (2)

Prune
Prune

Reputation: 77850

Consider a simple example with three classifications (red green blue) and the six nearest neighbors denoted by R, G, B. I'll make this linear to simplify visualization and arithmetic

R B G x G R R

The points listed with distance are

class dist
  R     3
  B     2
  G     1
  G     1
  R     2
  R     3

Thus, if we're using unweighted nearest neighbours, the simple "voting" algorithm is 3-2-1 in favor of Red. However, with the weighted influences, we have ...

red_total   = 1/3^2 + 1/2^2 + 1/3^2  = 1/4 + 2/9 ~=  .47
blue_total  = 1/2^2 ..............................=  .25
green_total = 1/1^2 + 1/1^2 ......................= 2.00

... and x winds up as Green due to proximity.

That lower-delta function is merely the classification function; in this simple example, it returns red | green | blue. In a more complex example, ... well, I'll leave that to later tutorials.

Upvotes: 2

Srini
Srini

Reputation: 1649

Okay, off the bat let me say I am not the fan of the link you provided, it has image equations and follows a different notation in the images and the text.

So leaving that off let's look at the regular k-NN algorithm. regular k-NN is actually just a special case of weighted k-NN. You assign a weight of 1 to k neighbors and 0 to the rest.

  1. Let Wqj denote the weight associated with a point j relative to a point q
  2. Let yj be the class label associated with the data point j. For simplicity let us assume we are classifying birds as either crows, hens or turkeys => discrete classes. So for all j, yj <- {crow, turkey, hen}
  3. A good weight metric is the inverse of the distance , whatever distance be it Euclidean, Mahalanobis etc.
  4. Given all this, the class label yq you would associate with the point q you are trying to predict would be the the sum of the wqj . yj terms diviided by the sum of all weights. You do not have to the division if you normalize the weights first.
  5. You would end up with an equation as follows somevalue1 . crow + somevalue2 . hen + somevalue3 . turkey
  6. One of these classes will have a higher somevalue. The class witht he highest value is what you will predict for point q
  7. For the purpose of training you can factor in the error anyway you want. Since the classes are discrete there are a limited number of simple ways you can adjust the weight to improve accuracy

Upvotes: 1

Related Questions