What is the definition of clustering problems in probability terms?

Question

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?

Answer 1

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.

Answer 2

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.