2
$\begingroup$

I am new to non-paramtric methods. The conditional probability for classification using KNN is gen by: $$ P(y=c|x,D)=\frac{1}{K}\sum_{n\in N_K(x,D)}I(y_n=c) $$ where $N_K(x,D)$ is the set such that $K$ points are included to be nearest to the new point.

The 2 parameters required for the KNN is:

  1. $K$
  2. A distance metric (e.g. Mahalanobis): $$ d(x,\mu)=\sqrt{(x-\mu)^T M(x-\mu)} $$

My question is, why is a distance metric required? When all I need is to get the number of points belonging to a class $c$ and divide it by the total number of points nearest as dictated by $K$. I can repeat this for $c\in L$ and there goes my probability distribution for the most probable class.

To get the nearest $K$ points, shouldn't I just simply create a N-dimensional sphere from my new point and increase the radius until $K$ points are enclosed? I will then extract the labels of these points and do the usual KNN

$\endgroup$
4
  • $\begingroup$ How will you know which points are nearest without using a distance metric? $\endgroup$
    – Sycorax
    Apr 11, 2022 at 4:08
  • $\begingroup$ @Sycorax I think that I can scan the nearby points enclosed by a sphere by increasing the radius where the new point is the center of the said sphere? $\endgroup$
    – wd violet
    Apr 11, 2022 at 4:10
  • 1
    $\begingroup$ Changing the distance metric changes the shape of that sphere, and possibly the number of points inside a radius. For instance, compare Manhattan and Euclidean distances. $\endgroup$
    – Sycorax
    Apr 11, 2022 at 4:11
  • $\begingroup$ Ohh, the metric makes it possible to have a cube instead of sphere or any other kinds of shape. I finally understand thank you! $\endgroup$
    – wd violet
    Apr 11, 2022 at 4:18

1 Answer 1

1
$\begingroup$

Changing the distance metric changes the shape of that sphere enclosing the query point, and possibly the number of points inside a radius. For instance, compare Manhattan and Euclidean distances. The shape of all points in a 2-dimensional space within 1 unit in Manhattan distance is a square, but is a circle for Euclidean distance.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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