# knn 'bayes' versus 'majority voting'

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 ?

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$.

• ' 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 ' ? Apr 26 '17 at 17:29
• ' 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 ? Apr 26 '17 at 17:30