2
$\begingroup$

Reading https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm knn uses 'majority voting' to classify an object while knn described on page 39 of http://www-bcf.usc.edu/~gareth/ISL/ISLR%20Sixth%20Printing.pdf states 'KNN applies Bayes rule and classifies the test observation x0 to the class with the largest probability.'

Which implementation should I choose and under what conditions ?

$\endgroup$
0
$\begingroup$

The two statement are the same. Because Bayes error rate is coming from minimizing the 0-1 loss (classifications loss). And majority vote will achieve such goal.

Where, the Bayes error is

$$ 1 - E~(\max_j P(Y=j|X)) $$

The 0-1 loss will be minimized, if we assign the probability

$$ P(Y=j|X)=\frac 1 K \sum_{i \in \text{neighbor}} I(y_i=j) $$

where $I(\cdot)$ is the indicator function.


Numerical example: suppose we are doing binary classification $Y$ can be $0$ or $1$. In addition, we use $N=5$, in $5$ neighbors there are $2$ vote for class $0$ and $3$ vote for class $1$.

If we assign $Y=1$, the 0-1 loss will be minimized, and the Bayes error rate is $\frac 2 5$.

$\endgroup$
2
  • $\begingroup$ ' If we assign $Y=1$, the 0-1 loss will be minimized, and the Bayes error rate is $\frac 2 5$. ' should be ' If we assign $Y=1$, the 0-1 loss will be minimized, and the Bayes error rate is $\frac 3 5$. ' as ' 3 vote for class 1 ' ? $\endgroup$
    – blue-sky
    Apr 26 '17 at 17:29
  • $\begingroup$ ' If we assign $Y=1$, the 0-1 loss will be minimized, and the Bayes error rate is $\frac 2 5$. ' if 2 (not 3) vote for class 1 ? $\endgroup$
    – blue-sky
    Apr 26 '17 at 17:30

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.