How to explain KNN in Bayesian probability?

Question

I am wondering how to explain k-nearest neighborhood algorithm from a Bayesian approach, especially on how to justify the best choice of k value?

Answer 1

kNN from a Bayesian viewpoint

Let suppose that we have a data set comprising $N_{k}$ points in class $\mathcal{C}_{k}$ with $N$ total points, so that $\sum_{k}N_{k} = N$.

We want to classify a new point $\mathbf{x}$ by drawing a sphere centred on $\mathbf{x}$ containing precisely $K$ points irrespective of their class. Suppose that such a sphere has volume $V$ and contains $K_{k}$ points from class $\mathcal{C}_{k}$.

Then,

$$ p(\mathbf{x}|\mathcal{C}_{k}) = \frac{K_{k}}{N_{k}V}$$

provides an estimate of the density associated with each class. Similarly, the unconditional density is given by

$$ p(\mathbf{x}) = \frac{K}{NV}, $$

while the class priors are given by

$$ p(\mathcal{C}_{k}) = \frac{N_{k}}{N}. $$

We can now combine the three equations using Bayes' theorem to obtain the posterior probability of class membership

$$ p(\mathcal{C}_{k}|\mathbf{x}) = \frac{ p(\mathbf{x}|\mathcal{C}_{k}) p(\mathcal{C}_{k})}{p(\mathbf{x})} = \frac{K_{k}}{K}. $$

If we wish to minimize the probability of misclassification, we have to assign the test point $\mathbf{x}$ to the class having the largest posterior probability, corresponding to the largest value of $\frac{K_{k}}{K}$.

Answer 2

As explained in detail in this other answer, kNN is a discriminative approach. In order to cast it in the Bayesian framework, we need a generative model, i.e. a model that tells how samples are generated. This question is developed in detail in this paper (Revisiting k-means: New Algorithms via Bayesian Nonparametrics).

The approach follows two steps: first finding a smooth version of k-means (GMM) and then use the Dirichlet Process (DP) to model the mixture of Gaussians.

The first step builds upon the asymptotic relationship between kmeans and GMM. This is necessary in order to have an efficient model of the conditional probabilities, for which we have efficient sampling algorithms.

As already said, the DP models the distribution of Gaussian mixtures which could have generated the observed data. Initially one may even have an infinite number of components!. The goal is then to find the likeliest values that could have generated the data.