# How to define a posterior probability of y given x when the model is not probabilistic?

Suppose we have a very simple online k-means where each new data-point is assigned to its nearest center (the mean is updated incrementally). Each center (cluster) is labelled with the most common label of data-points assigned to that cluster. In this special configuration: is it possible to compute a sort of "posterior probability"? I.e., can the posterior probability of a class label $y$ given a data-point $x$ ($P(y|x)$) just be $1/\text{distance}(x, m_y)$, where $m_y$ is a center labelled with $y$ which is nearest to $x$?

• Depends on what you use it for, I guess... – Has QUIT--Anony-Mousse Nov 7 '12 at 16:57
• @Anony-Mousse I want to have some confidence about how probable the instance x is of a class y. I want to use this probability to let the learning algorithm be able to actively queries the data-points about which it is least certain how to label (i.e. ask for there labels). This is often strainghtforward for probabilistic learning models. For example when using a probabilistic model for binary classification, it will simply queries the instances whose posterior probability of being positive is nearest 0.5. Now how to define P(y|x) when the model is not probabilistic (e.g. with the online KM) ? – shn Nov 8 '12 at 14:25
• Why do you say k-means is non-probabilistic? k-means assumes that each data point is generated by one of the clusters and each cluster is assumed to be distributed as a multivariate normal distribution with identity covariance. It is a latent probabilistic model. 'Latent' comes from the fact that which cluster generates which data point is hidden/unknown. – emrea Mar 8 '13 at 18:34

If you are wedded to k-means for practical reasons (i.e. you already implemented it or your boss knows k-means is the way to go), then you could still use some cool tricks to get a non-parametric posterior density estimate of new observations give your data (and estimated cluster centers). Namely, you could use k-nearest neighbors. In this case, you would be training nearest neighbor algorithm with class labels assigned by k-means. Thus, the posterior probability of a new datum belonging to class $i$ is the proportion of k-neighbors belonging to class $i$, i.e. $Pr(X_{new}=i|X_{obs})=\frac{k_i}{k}$.