I'm currently studying about K nearest neighbour algorithm. I understand the basics of it. The problem I have is I have the below equation given in a slide and do not understand the purpose of it. Thanks]1
-
$\begingroup$ Can you provide some more context here, like the whole slide? What is $y_i$ and how is it defined? $\endgroup$– The LaconicJun 23, 2018 at 14:03
-
1$\begingroup$ Looks like this is binomial data (i.e. $y_i \in {-1,1}$). This a majority vote of the class of observation $x_q$ using the function $N_k$ to find the nearest neighbors. If the sum of nearest neighbor labels ends up positive, the observation $x_q$ is classified as positive. $\endgroup$– kholJun 23, 2018 at 14:03
-
$\begingroup$ @TheLaconic this is mentioned as the classification algorithm. $\endgroup$– Chiran K.Jun 23, 2018 at 14:10
-
$\begingroup$ @khol Thanks for the answer. can you further explain what is given by y^q. To be more specific, why sign function is used? TIA $\endgroup$– Chiran K.Jun 23, 2018 at 14:11
1 Answer
$x_q$ is the example to be classified, so $q$ indexes the example to be classified.
$N_k(x_q)$ is the set of $k$ nearest neighbors of $x_q$, as it says.
$y_i$ indicates the observed class of observation $i$, and is presumably either -1 or 1.
$\hat{y}_q$ is the predicted class for observation $q$.
The sign function maps positive values to +1, negative values to -1, and zero to zero.
All the equation says is: to predict the class for observation $q$ sum the class indicators $y$ over the $k$ nearest neighbors of $q$. If more of the neighbors have $y=+1$ than $y=-1$, the sum is positive and the predicted value is $+1$. If more of the neighbors have $y=-1$ than $y=+1$, the sum is negative and the predicted value is $-1$. (If the predicted value is zero, then there's no specific prediction, but that's why you probably want to choose $k$ to be odd, so that you always get a definite prediction one way or the other.)