What is the definition of clustering problems in probability terms?

Say that $\mathcal{X}$ is the samples set and $X$ is a r.v. that takes value in it, and $\mathcal{Y}$ is the labels set with $Y$ a r.v. that takes value in it.

Classification problems are easily represented in probability terms. For example, when we wish to classify some sample $x \in \mathcal{X}$ our goal i to find $\hat y$ that solves this: $$\hat y = \underset{y \in \mathcal{Y}}{\text{args max }} \Pr(Y=y|X=x)$$

That definition represents the optimum classification problem solver. We can say that all supervised learning algorithms (e.g. SVM, RF, etc) try to estimate that conditional-probability maximizer above. The definition is generic, simple, and commonly found in books/Internet.

But the challenge that I am facing is how to define clustering problems in probability terms, i.e. similar to what I showed earlier for classification, but for clustering instead.

My attempt

Let's say that $\mathcal{C} = \{i:1 \le i \le k\}$ is a set that has a bijection against $\mathcal{Y}$, and $C$ is a random variable that takes values in $\mathcal{C}$.

Then I suppose that clustering in probability terms aims to only find:

• $k$ (which implies finding $\mathcal{C}$).
• $f_{X,C}$ is the joint the density of r.vs $X$ and $C$.

That maximize the following:

$$\begin{split} (k^*,f^*_{X,C}) &= \underset{(k,f_{X,C}) \in \mathcal{H}}{\text{arg max }} \sum_{c\in\mathcal{C}} \prod_{x\in\mathcal{X}} f_{X,C}(x,c) \,\,\,\,\,\,\,\,(1)\\ \end{split}$$

Here $\mathcal{H}$ is the space of hypothesis. Usually domain knowledge is used to reduce its size by assuming things like maybe $p_C(c) = \frac{1}{|\mathcal{C}|}$ (for any $c$), or that $f_{X|C=c}$ is normally distributed (for any $c$), and plug this information into $f_{X,C}(x,c)=p_C(c)f_{X|C=c}(x)$.

Once $k^*$ and $f^*_{X,C}$ are found, for any sample $x$ we predict its cluster identifier to be: $$c^* = \underset{c \in \{1,2,\ldots,k^*\}}{\text{arg max }} f_{X,C}^*(x,c)$$

Q1: Is equation $(1)$ the expectation maximization algorithm?

Q2: Is there any clustering problem that its optimal solution is not representable by this?

• Cluster analysis, in general, does not have to refer to any random variable having a specific distribution. In that general sense cluster analysis is a not probability-paradigm technique. Some specific clustering methods, though could be formulated in terms of probability. GeoMatt22, for example, offers to see clustering as a form of latent class analysis. It is possible, perhaps in some cases, but speaking generally - it is a stretch. – ttnphns Dec 18 '16 at 9:07
• If C is a bijection with |Y|, then |C|is|Y|? – Has QUIT--Anony-Mousse Dec 18 '16 at 10:06
• @Anony-Mousse Yes (if $k$ is predicted correctly). – caveman Dec 20 '16 at 13:46
• I updated my attempt above. I think I terribly omitted important things. Hopefully what I say makes sense. I'm not a statistician so I could still be deeply wrong. Any correction is highly appreciated. – caveman Dec 20 '16 at 15:25

In this context, you could consider clustering to be classification with latent (hidden) labels $y$.

Commonly the conditional distribution of $x|y$ is assumed to have some parametric form (e.g. Gaussian) whose parameters $\theta|y$, along with the class labels $y$, are inferred from the data $x$ using the Expectation Maximization (EM) algorithm.

With this approach the number of labels $|\mathcal{Y}|$ is another free parameter, which may or may not be estimated from the data.

• Thank you. I edited my question with an attempt that does what I think is what you said, plus some extra things from Anony-Mousse. Any thoughts? – caveman Dec 18 '16 at 8:27

If you look at cluster evaluation, you will find the answer.

Labels are just random, but they bear the information which objects are related, and which are not related.

So rather than predicting label(x), what you are predicting is whether for any two objects x and y, label(x)=label(y). So instead of looking at single objects, always look at pairs.

• Thank you. I edited my question with an attempt that does what I think is what you said, plus some extra things from GeoMatt22. Any thoughts? – caveman Dec 18 '16 at 8:27
• Its true, but the OP asked on clustering-to-do, not on ready cluster solution to evaluate. – ttnphns Dec 18 '16 at 8:51
• @ttnphns I'm not saying this is itself the entire solution. But this transformation maps the clustering problem to a binary problem "are a and b related" that is more similar to classification, and supposedly much easier to model. – Has QUIT--Anony-Mousse Dec 18 '16 at 10:05