Model-Based Clustering Methods

1. Idea

Model-based methods assume that the data are generated by an underlying model (usually a mixture of probability distributions) and try to fit the model to the data, then assign each object to the model component that most probably generated it. Unlike heuristic methods (k-means, DBSCAN), they give:

A statistically principled objective (maximum likelihood / posterior probability),
The number of clusters can be determined automatically (model selection),
Each cluster comes with a probability distribution, so cluster shapes need not be spherical and soft (probabilistic) membership is available,
Noise and outliers are explicitly modelled (as low-probability points).

2. Mixture Model Formulation

Assume $k$ components with parameters $\Theta = \{\theta_1,\dots,\theta_k\}$ and mixing weights $\alpha_j$ :

P(x \mid \Theta) = \sum_{j=1}^{k} \alpha_j\, P(x \mid \theta_j),\qquad \alpha_j \ge 0,\qquad \sum_{j=1}^{k}\alpha_j = 1

Most common: Gaussian mixture model (GMM) — each component is a multivariate normal with mean $\mu_j$ and covariance $\Sigma_j$ :

P(x \mid \mu_j,\Sigma_j)=\frac{1}{(2\pi)^{d/2}|\Sigma_j|^{1/2}}\exp\left(-\frac{1}{2}(x-\mu_j)^{T}\Sigma_j^{-1}(x-\mu_j)\right)

The posterior probability (responsibility) that object $x_i$ belongs to cluster $j$ :

w_{ij}=P(j \mid x_i)=\frac{\alpha_j\,P(x_i \mid \theta_j)}{\sum_{l=1}^{k}\alpha_l\,P(x_i \mid \theta_l)}

3. Parameter Estimation — the EM Algorithm (Expectation–Maximisation)

EM iteratively increases the log-likelihood

\log L(\Theta \mid D)=\sum_{i=1}^{n}\log\left(\sum_{j=1}^{k}\alpha_j P(x_i\mid\theta_j)\right)

Algorithm

1. Initialise parameters: means, covariances, mixing weights (random or k-means based)
2. repeat
   // E-step: soft assignment using the current parameters
      for each i, j:  w_ij = alpha_j * N(x_i | mu_j, Sigma_j)
                            / sum_l alpha_l * N(x_i | mu_l, Sigma_l)
   // M-step: re-estimate parameters from the responsibilities
      alpha_j = (1/n) * sum_i w_ij
      mu_j    = sum_i w_ij x_i  /  sum_i w_ij
      Sigma_j = sum_i w_ij (x_i - mu_j)(x_i - mu_j)^T  /  sum_i w_ij
   recompute log-likelihood
   until (log-likelihood change < epsilon  or  max iterations)
3. Assign each object to argmax_j w_ij   (hard clustering; w_ij available for soft)

EM guarantees the log-likelihood never decreases; it converges to a local maximum, so multiple restarts are usual.

Worked numerical (1-D, k = 2, one iteration sketch) — data {1, 2, 4, 8, 9}, initial $\mu_1 = 2$ , $\mu_2 = 8$ , equal variances $\sigma = 1$ , $\alpha_1 = \alpha_2 = 0.5$ :

$x$	$P(x\mid\mu_1)$	$P(x\mid\mu_2)$	$w_{i1}$	$w_{i2}$
1	0.242	8.3e-13	1.00	0.00
2	0.399	1.3e-9	1.00	0.00
4	0.054	0.0029	0.95	0.05
8	1.3e-9	0.399	0.00	1.00
9	8.3e-13	0.242	0.00	1.00

M-step: $\alpha_1 = \alpha_2 = 0.5$ ; $\mu_1 = (1+2+0.95\times4)/(1+1+0.95)=1.88$ ; $\mu_2 = (0.05\times4+8+9)/(0.05+1+1)=8.17$ . The means move outward and the responsibilities sharpen → clusters {1,2,4} and {8,9}.

4. Choosing the Number of Clusters — Model Selection

Use Bayesian model selection rather than a heuristic elbow:

BIC (Bayesian Information Criterion): $\text{BIC} = -2\log L + m\log n$ — penalises complexity ( $m$ = number of free parameters).
AIC (Akaike Information Criterion): $\text{AIC} = -2\log L + 2m$ .
MDL (Minimum Description Length): choose the model giving the shortest description of the data.

\hat{k}=\arg\min_{k}\ \text{BIC}(k)

Choose the model with the lowest BIC/AIC — this balances goodness of fit against the number of parameters, automatically avoiding too many clusters.

5. AUTO-CLASS — Bayesian Classification (Class-Based Model)

AUTO-CLASS is a naive Bayes-based model for multidimensional data that assigns each tuple to the most probable class, treating each attribute as:

Gaussian (normal) when values are numeric — parameters $\mu$ , $\sigma$ estimated by maximum likelihood;
Discrete / Poisson when values are categorical or count-like, with the method of moments used to estimate the distribution.

Algorithm outline

1. (Unsupervised learning) Start with only one class; moving a tuple to a new class
   is attempted and the "goodness" of the resulting class distribution is scored
   with a Bayesian score (posterior probability of the classification given the data).
2. Accept the new class only if it improves the Bayesian score (MDL-style penalty
   for extra parameters keeps the number of classes small).
3. (Classification) For any new tuple, compute the posterior probability of each
   class under the independent-attribute assumption and assign the maximum.

Bayesian (posterior) score used for scoring classes:

P(\mathcal{C} \mid D)=\frac{P(D \mid \mathcal{C})\,P(\mathcal{C})}{P(D)}\ \propto\ P(\mathcal{C})\prod_{\text{attributes}}P(x_a \mid \theta_a)

Properties of AUTO-CLASS: handles class overlap and outliers naturally; determines the number of classes automatically; assumptions (conditional independence of attributes, distribution families) are its main limitation.

6. Other Model-Based / Probabilistic Approaches

Approach	Idea
COBWEB	Incremental hierarchical conceptual clustering; builds a classification tree whose nodes are probabilistic concepts; uses category utility to decide merge/split/add
SOM (Self-Organising Map)	Neural-network variant of model/prototype-based clustering — a lattice of prototype vectors trained competitively; good for visualisation of high-dimensional data
Latent Dirichlet Allocation (LDA)	Generative topic model (mixture) used for text clustering
Hybrid / statistical frameworks	Bayesian networks, mixture of experts, hidden Markov models for sequence clustering

Category utility used by COBWEB (guides which concept is best):

CU(C)=\sum_{k}P(C_k)\Big[\sum_i\sum_j P(A_i{=}v_{ij}\mid C_k)^2-\sum_i\sum_j P(A_i{=}v_{ij})^2\Big]

7. Advantages and Limitations

Advantages

Statistical foundation; soft (probabilistic) assignments; discovers elliptical clusters via full covariance.
Number of clusters chosen by model selection (BIC/AIC/MDL) rather than trial and error.
Handles noise, incomplete data (via EM's marginalisation) and mixed distributions.
Natural framework to combine prior knowledge (priors) and to do classification with the same machinery.

Limitations

Assumes a distribution family; wrong assumptions → wrong clusters (k-means is a special case of GMM with equal spherical covariance).
EM converges only to a local maximum; needs restarts; can be slow and prone to singular covariance (variance → 0) unless regularised.
Computationally heavier than k-means ( $O(nkd^2)$ per iteration with full covariances); not practical for a very large $n$ or very high $d$ without approximations.

8. Exam Points

Explain model-based clustering and the EM algorithm with the E-step and M-step formulas — 10 marks (frequent).
Give the Gaussian mixture model and derive the posterior/responsibility $w_{ij}$ — 7 marks.
Explain how the optimal number of clusters is decided (BIC/AIC/MDL) — 5 marks.
Explain AUTO-CLASS with its Bayesian score and handling of Gaussian vs Poisson attributes — 5-7 marks.
Short note on COBWEB and category utility — 3-5 marks.

Model-Based Clustering Methods