4
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ Depends on what you use it for, I guess... $\endgroup$ – Has QUIT--Anony-Mousse Nov 7 '12 at 16:57
  • $\begingroup$ @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) ? $\endgroup$ – shn Nov 8 '12 at 14:25
  • $\begingroup$ 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. $\endgroup$ – emrea Mar 8 '13 at 18:34
1
$\begingroup$

Since you can view k-means as a sort of impoverished Mixture of Normals (specifically with 0 variance), I'd be tempted to use the density function of the Normal distribution if you need a probabilistic metric. If you're willing to assume equal variances in all the clusters you can ignore the variance in the density function, and normalise by the distance across all clusters (you could also include a prior probability of the cluster as the fraction of points assigned to it as well).

It's not pretty and it's not really theoretically justified, but it may suffice.

$\endgroup$
1
$\begingroup$

As noted in the comments, k-means does correspond to a probabilistic model, just like PCA. The connection between machine learning and statistics (Naive-Bayes v. logistic regression) is one of my favorite topics, but that's neither here nor there... As suggested, you could employ a full-blown mixture model to quantify that posterior probability of a new observation given observed data. This would give you some nice tools like posterior predictive checks to understand your model and data more completely. I recommend reading Andrew Gelman for more on that approach.

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

The reason this works is that nearest neighbor is a form of kernel density estimation. Unfortunately, the nearest neighbor classifier isn't a true kernel because it doesn't integrate to 1 as a true kernel (or probability distribution) should, but it's awfully close. This is awesome because a k-nearest neighbor classifier can be implemented to be quite fast with clever data structures, depending on the kind of data you have. This lecture describes the ins and outs of the approach I have outlined above for a mixture of Gaussians, which is essentially what k-means is trying to get at.

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