3
$\begingroup$

We know that the Gaussian Mixture Model is a probabilistic counterpart of k-means algorithm. Is there a probabilistic counterpart for kNN? (which is similar to k-means, but supervised.)

$\endgroup$
  • $\begingroup$ Instead of the kNN predicting a class you want it to predict an array of probabilities for each class? $\endgroup$ – Andrew Cassidy Mar 17 '14 at 21:07
  • $\begingroup$ It sounds like "parametric" or "model-based" would be more helpful terms. $\endgroup$ – David Robinson Mar 17 '14 at 21:17
  • $\begingroup$ @AndrewCassidy: That is one possible generalization. The other option would be an array of probabilities over k. $\endgroup$ – Daniel Mar 18 '14 at 3:57
  • 1
    $\begingroup$ Parzen window based classifiers are probably what you're looking for. $\endgroup$ – alto Mar 21 '14 at 14:27
3
$\begingroup$

The way I'd model it (I haven't seen this in the literature, but it wouldn't surprise me if it were already out there) is:

I'd think of it as expressing the posterior distribution over class labels, given that you have a (test) sample $x$, as a marginalization over a sub-set of the training sample nodes, $n_i$: $$ p(c \vert x) = \sum p(c \vert n_i ) p(n_i \vert x) $$

In the back of my mind, I have the idea that the test sample is assigned-to (or is essentially the same as) one of the test-samples; but since we don't know which one, we marginalize over all of the feasible ones.

The first factor defines, for each training-sample node, the probability distribution over class labels, given that the test-sample was "assigned" to node $n_i$. If each training sample has a particular label, then this might be just an indicator function for that label; the various extensions to actual distributions are going to be problem domain specific.

The second factor is the probability that node $n_i$ is the correct assignment choice. The direct mapping of $kNN$ is to have $p(n_i \vert x) = 1/k$ when $n_i$ is in the set of $kNN$'s, and zero otherwise; i.e. a cookie-cutter type of distribution. Again, this could be generalized into something with a softer roll-off, e.g. a Gaussian type of shape in feature space, if desired.

In my opinion, this captures the the essential general structure of $kNN$:

  1. You pick a population who gets to vote, this is achieved by $p(n_i \vert x)$, and then
  2. you combine the results of each vote, in this case each vote is a probability distribution over classes, $p(c \vert n_i)$

whether you want to have a soft or hard inclusion function, the exact methods for defining the vote probabilities distributions and so on are problem-specific details.

$\endgroup$
2
$\begingroup$

Something very similar is Logistic regression with a Radial Basis Function (sometimes called Gaussian) kernel (http://en.wikipedia.org/wiki/Radial_basis_function_kernel), with all weights constrained to be $1$.

A fitted RBF kernel regression will compute weighted distances to various points, compute a Gaussian pseudo-probability of being a neighbor based on the distance, and average the values at the points in the training set weighted by that Gaussian pseudo-probability.

This is very similar to kNN, where $k$=size of the training set.

You can reduce the number of points under consideration via a Laplacian prior ($L_1$ regularization), but this won't have the same effect as varying $k$ in kNN, as the $k$ points chosen will be the only ones considered.

If weights are fixed at $1$, only the distance matters. When weights are allowed to vary, it affects how much each point is allowed to vary.

$\endgroup$
2
$\begingroup$

This paper formulates explicitly a probabilistic version of KNN:

C.C. Holmes, N.M. Adams: A probabilistic nearest neighbour method for statistical pattern recognition. J. Roy. Statist. Soc. Ser. B, 64 (2) (2002), pp. 295–306.

Dave's idea also comes up in this paper:

A. Kaban. A probabilistic neighborhood translation approach for non-standard text categorization. Proc. Discovery Science (DS08), 2008.

$\endgroup$
  • 1
    $\begingroup$ Beware that in the Holmes and Adams paper the model specification is incoherent. Check out Cucala, Marin, Robert and Titterington (2009). $\endgroup$ – Zen Feb 1 '16 at 23:50
1
$\begingroup$

Gaussian mixture model is rather a generalization of $k$-means where variances are not identity matrices. One way to construct a probabilistic model which will be a generalization of kNN is to assume there is a gaussian centered at each data point with unknown variances whose distribution is fixed.

$\endgroup$

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.