Clustering & Model-Based Clustering

Definition of Clustering

Clustering is the process of grouping a set of data objects into classes (clusters) so that objects within the same cluster are as similar to one another as possible, and objects in different clusters are as dissimilar as possible. It is an unsupervised learning task because no class labels are assumed known in advance. Similarity/dissimilarity is usually measured by a distance (Euclidean, Manhattan, etc.) or by correlation.

Example: grouping customers by purchasing behaviour into clusters such as "low spenders", "regular buyers", "occasional big-ticket buyers", etc.

Clustering is used for data compression, outlier detection, market segmentation, bioinformatics (gene grouping), and as a pre-processing step for other mining tasks.

Model-Based Clustering Techniques

Model-based methods assume that the data fit a probabilistic (statistical mixture) model, and try to find the best fit of the data to the assumed model, usually by maximising the likelihood of the model having generated the observed data. Each cluster is modelled by a probability distribution (e.g., a Gaussian) rather than by a centroid alone.

1. Statistical approach — Expectation–Maximization (EM) for Gaussian mixtures (GMM).
Assume the data come from a mixture of $K$ Gaussian distributions; each cluster is one component distribution with its own mean $\mu_k$ and covariance $\Sigma_k$, mixed with weight $\pi_k$. EM iterates two steps:

• E-step (expectation): compute for every point its probability (responsibility) of belonging to each cluster using Bayes' rule:

$$\text{responsibility}(i,k) = \frac{\pi_k \, p(x_i \mid \mu_k, \Sigma_k)}{\sum_j \pi_j p(x_i \mid \mu_j, \Sigma_j)}$$

• M-step (maximisation): re-estimate the parameters $\pi_k$, $\mu_k$, $\Sigma_k$ by maximising the expected likelihood, using each point's responsibility values as weights.

The two steps are repeated until the likelihood (or the parameters) converges. Each object is assigned to the cluster for which its responsibility is highest.

2. Neural-network/symbolic models (self-organising maps, SOM).
Each cluster corresponds to a node (neuron) with a prototype; competitive learning adjusts the winning neuron and its neighbourhood, producing clusters on a low-dimensional map.

3. Fuzzy / probabilistic clustering (fuzzy c-means).
Instead of a hard assignment, every point receives a degree of membership in every cluster (between 0 and 1), a fuzzy generalisation of model-based membership.

4. Model selection.
The appropriate number of clusters $K$ can be chosen using statistical criteria such as BIC (Bayesian Information Criterion) or AIC, comparing how well models with different $K$ fit the data.

Advantages of model-based clustering:

• Can model clusters of different shapes, sizes and orientations (through each cluster's covariance), unlike k-Means.
• Provides a probabilistic interpretation — each object has posterior membership probabilities.
• Offers a sound statistical basis (likelihood), and $K$ need not be fixed exactly — model-selection criteria guide the choice.

Limitations:

• A parametric form must be assumed; if the assumption is wrong, the results may be poor.
• EM can converge to a local optimum, is sensitive to initial parameters, and is computationally heavier than simple partitioning methods.

      cluster 1                    cluster 2
  (Gaussian: μ1, Σ1)          (Gaussian: μ2, Σ2)
      ~~~~~︿~~~~                 ~~~~~︿~~~~
   EM assigns each point to the most likely bell
   curve (posterior probability) → soft membership