3
$\begingroup$

I'm studying k-nearest neighbor algorithms and the book I'm reading mentions that records are weighted according to their inverse square in order to perform weighted voting.

so I was wondering what do they mean by "inverse square" the example in the book is:

$\text{votes(record)}= \frac{1}{d(a,b)^2} = 1/0.004393^2 \sim 51,818$

so does inverse square just mean diving one by the distance of a specific record? any further insight into what that might mean will be greatly appreciated.

$\endgroup$
7
$\begingroup$

Imagine that we want to classify as red or blue the unknown gray point in the data cloud. Your algorithm is set up to measure Euclidean distances to the $k =3$ closest neighbors:

enter image description here

Two of them are blue, and the third one is red. Even assigning uniform weight (equal vote) to each one of the three points, the algorithm correctly classifies the unknown gray ball as blue. However, we start wondering why we gave equal vote to the third ball (the red ball tangentially touching on the "sphere of influence" around the gray ball). It is not entirely fair that it exerts as much leverage on the classification as the first and second closer balls.

So we weight the vote by the inverse of the square of the Euclidean distance to avoid a situation in which it could have have resulted in a spurious classification:

enter image description here

In this case two of the neighbors incorrectly point to a red assignment, and win over the final vote, overruling the influence of the much closer blue neighbor, an effect that can be factored in by weighting by the inverse of the squared distance so that the farthest-away red ball has the least say in the classification:

enter image description here

Computationally, the algorithm will attempt to resolve each case with a formula such as:

$$\hat y=\text{max}_r\left(\sum_{i=1}^k w_{(i)}\,\mathbf{1}_{y{(i)}=r}\right)$$

$r$ stands for the number of classes (in this case, $2$, {red,blue}), $\mathbf{1}$ is the indicator variable: the sum is obtained for each class. Finally the weights $w_{(i)}$ calculated through a kernel function, with in the case you describe could be an inversion kernel $\frac{1}{\lvert d\rvert}.$

$\endgroup$
  • 1
    $\begingroup$ +1. Thank you for joyful, explaining pictures, and for playing kernel curling for us. $\endgroup$ – ttnphns Jan 29 '17 at 7:13
  • 1
    $\begingroup$ @ttnphns You are a class act! (will erase to avoid "chatter"). $\endgroup$ – Antoni Parellada Jan 29 '17 at 7:18

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.