8
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Are you looking for the lowest possible error rate of knn with respect to bayes approach? The Duda & Hart book is pretty good at linking the two. $\endgroup$ Jun 18, 2015 at 5:24

2 Answers 2

8
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Sorry for this interrupting question. But when you give the unconditional density, $p(x)=K/NV$, is it well defined? i.e., if I integrate $p(x)$ over whole space, may I get $1$ in the end? $\endgroup$
    – JumpJump
    Sep 30, 2015 at 12:37
  • $\begingroup$ what is P(x) ? How do you define it? $\endgroup$
    – Dom Jo
    Apr 17, 2020 at 1:49
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This question is about k-nearest-neighbours (kNN), while this answer only mentions k-means. What is the relation? $\endgroup$
    – Jon Nordby
    Jan 2, 2022 at 12:32

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.