1
$\begingroup$

I'm reading Murphy's Machine Learning- A Probabilistic Perspective. The introductory section on discovering clusters says:

It seems that there might be various clusters, or subgroups, although it is not clear how many. Let $K$ denote the number of clusters. Our first goal is to estimate the distribution over the number of clusters, $p(K|D)$; this tells us if there are subpopulations within the data. For simplicity, we often approximate the distribution $p(K|D)$ by its mode, $K^∗ = \arg \max_K p(K|D)$.

($D = \{\textbf{x}_i\}_{i=1}^N$ is the training data set)

Earlier, it's stated that in unsupervised learning, we're essentially performing density estimation, i.e. we want to build models of the form $p(\textbf{x}_i | \theta)$.

So I'm confused by the above quoted paragraph- instead of estimating the probability distribution of the feature vector, we seem to be estimating the most likely value of the hyperparameter $K$, which is completely different. Is the $K$ estimation a preliminary step before we get to estimate $p(\textbf{x}_i | \theta)$?And what is exactly meant by "estimate the distribution over the number of clusters"? Distribution of what?

$\endgroup$
  • $\begingroup$ The number of clusters is yet another random variable that can be estimated. In purely Bayesian setting, you can put a prior on it. The data (and the model + assumptions you choose) will fit better some cluster numbers than others. Over the range of number of clusters (1,...), you will get a probability distribution over clusters. Something similar can be done is sequence segmentation - position where the switch point is not certain: you get a distribution over positions where the switchpoint is likely to occur. I have implemented examples in Infer.NET framework. $\endgroup$ – Vladislavs Dovgalecs Dec 19 '17 at 19:35
0
$\begingroup$

Choosing k for k-means is a big problem.

Yet, you cannot do k-means without fixing k. So the "hack" for the probability view is to assume every k is there, just with a different probability, and then do all k at once. Then try to maximize both at the same time.

Beware that the book has a "everything is Bayesian" bias. And that usually means "everybody that isn't using Bayesian reasoning is doing it wrong". Then K-means "is not a proper EM algorithm"... That subcommunity can be a bit binary (and I will get downvotes for this...). Also, most "machine learning" books tend to be really not interested in unsupervised learning, and the clustering chapters are often utterly incomplete, missing some of the most popular (and important) methods such as DBSCAN and OPTICS.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ "Yet, you cannot do k-means without fixing k. So the "hack" for the probability view is to assume every k is there, just with a different probability, and then do all k at once. Then try to maximize both at the same time." - I didn't understand this part. Could you please elaborate on this? $\endgroup$ – Shirish Kulhari Dec 19 '17 at 19:22
  • $\begingroup$ See the book for details. In my experience, this doesn't actually work (in particular, not on large data, with acceptable runtime). But don't expect a 1000 page book to answer everything on page 10. $\endgroup$ – Has QUIT--Anony-Mousse Dec 19 '17 at 19:23
  • $\begingroup$ But roughly, a few Bayesian approaches try to model $p(\vec{x}| \theta_K)$, the density if I would know the correct value of K. For all K. Then choose that which has the best fit, following the usual Bayesian maximum likelihood principle. $\endgroup$ – Has QUIT--Anony-Mousse Dec 19 '17 at 19:33

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.