# Probablistic counterpart for kNN

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

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

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.

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.

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.

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

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.