Cluster Analysis: Zero to Hero Tutorial

This comprehensive tutorial takes you from the foundational concepts of Cluster Analysis all the way through advanced algorithms, evaluation, interpretation, and practical usage within the DataStatPro application. Whether you are encountering cluster analysis for the first time or looking to deepen your understanding of unsupervised learning and data segmentation, this guide builds your knowledge systematically from the ground up.

Table of Contents

1. Prerequisites and Background Concepts
2. What is Cluster Analysis?
3. The Mathematics Behind Cluster Analysis
4. Assumptions of Cluster Analysis
5. Types of Cluster Analysis Methods
6. Using the Cluster Analysis Component
7. Hierarchical Clustering
8. K-Means and K-Medoids Clustering
9. Model-Based and Density-Based Clustering
10. Model Fit and Evaluation
11. Advanced Topics
12. Worked Examples
13. Common Mistakes and How to Avoid Them
14. Troubleshooting
15. Quick Reference Cheat Sheet

1. Prerequisites and Background Concepts

Before diving into cluster analysis, it is helpful to be comfortable with the following foundational statistical and mathematical concepts. Each is briefly reviewed below.

1.1 Distance and Similarity

Cluster analysis is fundamentally about grouping objects that are similar to each other and dissimilar from objects in other groups. The core computational tool is a distance or dissimilarity measure between pairs of observations.

For two observations $\mathbf{x}_i = (x_{i1}, x_{i2}, \dots, x_{ip})$ and $\mathbf{x}_j = (x_{j1}, x_{j2}, \dots, x_{jp})$ with $p$ variables, the most commonly used distance measure is the Euclidean distance:

$d(\mathbf{x}_i, \mathbf{x}_j) = \sqrt{\sum_{k=1}^{p}(x_{ik} - x_{jk})^2}$

Key properties of a valid distance measure:

• $d(\mathbf{x}_i, \mathbf{x}_j) \geq 0$ (non-negativity).
• $d(\mathbf{x}_i, \mathbf{x}_j) = 0 \Leftrightarrow \mathbf{x}_i = \mathbf{x}_j$ (identity of indiscernibles).
• $d(\mathbf{x}_i, \mathbf{x}_j) = d(\mathbf{x}_j, \mathbf{x}_i)$ (symmetry).
• $d(\mathbf{x}_i, \mathbf{x}_k) \leq d(\mathbf{x}_i, \mathbf{x}_j) + d(\mathbf{x}_j, \mathbf{x}_k)$ (triangle inequality).

A similarity measure $s(\mathbf{x}_i, \mathbf{x}_j)$ is the inverse concept: high similarity means the objects are close. It can always be converted to a dissimilarity: $d = 1 - s$ (for similarities bounded by [0, 1]).

1.2 Vectors and Centroids

An observation in a dataset with $p$ variables is represented as a vector in $p$-dimensional space:

$\mathbf{x}_i = (x_{i1}, x_{i2}, \dots, x_{ip})^T \in \mathbb{R}^p$

The centroid of a set of $n_k$ observations $\{\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_{n_k}\}$ is their arithmetic mean:

$\bar{\mathbf{x}}_k = \frac{1}{n_k}\sum_{i=1}^{n_k}\mathbf{x}_i$

In $K$-means clustering, the centroid is the representative point of each cluster.

1.3 Variance and Within-Group Variance

The total variance of a dataset measures overall dispersion:

$SS_{total} = \sum_{i=1}^{n}\sum_{k=1}^{p}(x_{ik} - \bar{x}_k)^2$

The within-cluster sum of squares (WCSS) measures how tightly packed observations are within their assigned clusters:

$\text{WCSS} = \sum_{c=1}^{K}\sum_{i \in C_c}\|\mathbf{x}_i - \bar{\mathbf{x}}_c\|^2$

Where $C_c$ is the set of observations in cluster $c$ and $\bar{\mathbf{x}}_c$ is the centroid of cluster $c$. Minimising WCSS is the objective of $K$-means clustering.

1.4 Matrix Notation and the Distance Matrix

Given $n$ observations, the distance matrix $\mathbf{D}$ is an $n \times n$ symmetric matrix where element $d_{ij}$ is the distance between observations $i$ and $j$:

$\mathbf{D} = \begin{pmatrix} 0 & d_{12} & d_{13} & \cdots & d_{1n} \\ d_{21} & 0 & d_{23} & \cdots & d_{2n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ d_{n1} & d_{n2} & d_{n3} & \cdots & 0 \end{pmatrix}$

The distance matrix is the primary input to hierarchical and many other clustering algorithms. It is always symmetric ($d_{ij} = d_{ji}$) with zeros on the diagonal.

1.5 Probability Distributions and Mixture Models

A probability distribution $f(x)$ describes the likelihood of observing each value of a random variable $X$. In model-based clustering, the data are assumed to arise from a mixture of distributions:

$f(\mathbf{x}) = \sum_{k=1}^{K} \pi_k f_k(\mathbf{x} \mid \boldsymbol{\theta}_k)$

Where:

• $K$ = number of mixture components (clusters).
• $\pi_k$ = mixing proportion for component $k$ ($\sum_k \pi_k = 1$, $\pi_k > 0$).
• $f_k(\mathbf{x} \mid \boldsymbol{\theta}_k)$ = density function of component $k$ with parameters $\boldsymbol{\theta}_k$.

The most common choice is the Gaussian mixture model (GMM), where each component is a multivariate normal distribution.

1.6 Optimisation and Convergence

Many clustering algorithms work by iteratively optimising an objective function (e.g., minimising WCSS). Key concepts:

Iteration: Repeating the same update steps until a stopping criterion is met.

Convergence: The algorithm has converged when the objective function changes by less than a small threshold $\varepsilon$ between iterations:

$|F^{(t+1)} - F^{(t)}| < \varepsilon$

Local vs. Global Optimum: Iterative algorithms like $K$-means often converge to a local (not global) optimum — the solution depends on the random starting configuration. Running the algorithm multiple times with different starts helps find a better (though still not guaranteed globally optimal) solution.

1.7 Supervised vs. Unsupervised Learning

Supervised learning uses labelled data (known outcomes) to train a model — examples include regression and classification. Unsupervised learning discovers structure in unlabelled data without a predefined outcome variable.

Cluster analysis is unsupervised — there is no "correct answer" against which to evaluate the solution. This makes cluster analysis both powerful (works without labels) and challenging (no ground truth for validation). All cluster validation is internal (based on the structure of the clustered data itself) or theoretical (based on external knowledge).

2. What is Cluster Analysis?

2.1 The Core Idea

Cluster analysis (also called clustering or cluster detection) is a class of unsupervised statistical learning methods that partition a dataset into groups (clusters) such that:

• Observations within the same cluster are as similar as possible to each other (high intra-cluster homogeneity).
• Observations in different clusters are as different as possible from each other (high inter-cluster separation).

Unlike classification (which assigns new observations to predefined categories), cluster analysis discovers the categories themselves from the data. The researcher does not specify what the groups should look like — the algorithm determines which observations naturally belong together.

2.2 What Cluster Analysis Can and Cannot Do

Cluster analysis CAN:

• Reveal natural groupings in complex high-dimensional data.
• Generate hypotheses about subgroup differences.
• Reduce data complexity by summarising observations by their cluster membership.
• Identify outliers and unusual observations (those that do not fit well in any cluster).
• Segment populations for targeted interventions or personalisation.

Cluster analysis CANNOT:

• Prove that clusters are "real" in a statistical testing sense — there is always some grouping solution, even for completely random data.
• Identify causes of group differences (it is descriptive, not inferential).
• Tell you the "right" number of clusters — this requires the researcher's judgement.
• Produce clusters that generalise to new samples without validation.

2.3 Real-World Applications

2.4 Cluster Analysis vs. Related Methods

2.5 The Fundamental Challenge: Defining Similarity

Every clustering algorithm embeds assumptions about what "similar" means. The choice of:

• Distance measure (Euclidean, Manhattan, cosine, etc.).
• Linkage method (for hierarchical clustering).
• Number of clusters $K$.
• Cluster shape assumption (spherical, elliptical, arbitrary).

...all profoundly influence the resulting clusters. There is no universally correct clustering solution — different algorithms and distance measures can produce very different groupings from the same data. Always examine results from multiple approaches.

3. The Mathematics Behind Cluster Analysis

3.1 Distance and Dissimilarity Measures

The choice of distance measure determines how "closeness" is defined and which clusters are formed. Different measures emphasise different aspects of dissimilarity.

Euclidean Distance (L2 norm):

$d_E(\mathbf{x}_i, \mathbf{x}_j) = \sqrt{\sum_{k=1}^{p}(x_{ik} - x_{jk})^2} = \|\mathbf{x}_i - \mathbf{x}_j\|_2$

Sensitive to scale differences between variables — standardisation is essential.

Manhattan Distance (L1 norm, City Block):

$d_M(\mathbf{x}_i, \mathbf{x}_j) = \sum_{k=1}^{p}|x_{ik} - x_{jk}|$

Less sensitive to outliers than Euclidean distance. Appropriate for grid-like data.

Minkowski Distance (generalisation of Euclidean and Manhattan):

$d_p(\mathbf{x}_i, \mathbf{x}_j) = \left(\sum_{k=1}^{p}|x_{ik} - x_{jk}|^p\right)^{1/p}$

• $p = 1$: Manhattan distance.
• $p = 2$: Euclidean distance.
• $p \to \infty$: Chebyshev distance ($\max_k |x_{ik} - x_{jk}|$).

Mahalanobis Distance (accounts for correlations and scale):

$d_{Mah}(\mathbf{x}_i, \mathbf{x}_j) = \sqrt{(\mathbf{x}_i - \mathbf{x}_j)^T \mathbf{S}^{-1} (\mathbf{x}_i - \mathbf{x}_j)}$

Where $\mathbf{S}$ is the sample covariance matrix. Invariant to scale and rotation; accounts for correlations among variables.

Cosine Dissimilarity (based on angle between vectors):

$d_{cos}(\mathbf{x}_i, \mathbf{x}_j) = 1 - \frac{\mathbf{x}_i^T \mathbf{x}_j}{\|\mathbf{x}_i\| \cdot \|\mathbf{x}_j\|}$

Appropriate for high-dimensional data (text, documents) where magnitude is less important than direction.

Gower's Distance (for mixed variable types):

For a dataset with $p$ variables of mixed types (continuous, ordinal, binary, nominal):

$d_G(\mathbf{x}_i, \mathbf{x}_j) = \frac{\sum_{k=1}^{p} \delta_{ijk} \cdot d_{ijk}}{\sum_{k=1}^{p} \delta_{ijk}}$

Where $\delta_{ijk} = 1$ if the $k$-th variable is usable for comparison (non-missing), and $d_{ijk}$ is the contribution of variable $k$ to the dissimilarity:

• Continuous: $d_{ijk} = |x_{ik} - x_{jk}| / \text{range}_k$
• Binary/Nominal: $d_{ijk} = \mathbf{1}[x_{ik} \neq x_{jk}]$
• Ordinal: Similar to continuous after ranking.

3.2 Distance Measure Comparison Table

3.3 The Hierarchical Clustering Algorithm

Hierarchical clustering builds a dendrogram (tree structure) by successively merging (agglomerative) or splitting (divisive) clusters.

Agglomerative clustering algorithm (bottom-up):

Step 1: Start with $n$ clusters, each containing exactly one observation:

$\mathcal{C} = \{C_1, C_2, \dots, C_n\}$ where $C_i = \{\mathbf{x}_i\}$

Step 2: Compute the $n \times n$ distance matrix $\mathbf{D}$.

Step 3: Find the two clusters $C_i$ and $C_j$ with minimum inter-cluster distance:

$(i^*, j^*) = \arg\min_{i \neq j} d(C_i, C_j)$

Step 4: Merge $C_{i^*}$ and $C_{j^*}$ into a new cluster:

$C_{new} = C_{i^*} \cup C_{j^*}$

Step 5: Update the distance matrix by removing rows/columns for $C_{i^*}$ and $C_{j^*}$ and adding a new row/column for $C_{new}$ using the chosen linkage method.

Step 6: Repeat Steps 3–5 until a single cluster remains.

The result is a binary tree (dendrogram) recording the order and heights of all merges.

3.4 Linkage Methods

The linkage method determines how the distance between two clusters is computed from the distances between their constituent observations. Different linkage methods produce dramatically different cluster shapes.

Single Linkage (Minimum):

$d_{SL}(C_i, C_j) = \min_{\mathbf{x} \in C_i, \mathbf{y} \in C_j} d(\mathbf{x}, \mathbf{y})$

Distance = distance between the closest pair of observations from each cluster. Prone to chaining — elongated, chain-like clusters.

Complete Linkage (Maximum):

$d_{CL}(C_i, C_j) = \max_{\mathbf{x} \in C_i, \mathbf{y} \in C_j} d(\mathbf{x}, \mathbf{y})$

Distance = distance between the farthest pair of observations from each cluster. Produces compact, roughly equal-sized clusters.

Average Linkage (UPGMA):

$d_{AL}(C_i, C_j) = \frac{1}{|C_i| \cdot |C_j|}\sum_{\mathbf{x} \in C_i}\sum_{\mathbf{y} \in C_j} d(\mathbf{x}, \mathbf{y})$

Distance = average of all pairwise distances between the two clusters. A compromise between single and complete linkage.

Ward's Method (Minimum Variance):

Merges the two clusters that result in the smallest increase in total within-cluster sum of squares (WCSS):

$d_{Ward}(C_i, C_j) = \frac{|C_i| \cdot |C_j|}{|C_i| + |C_j|} \|\bar{\mathbf{x}}_{C_i} - \bar{\mathbf{x}}_{C_j}\|^2$

Where $\bar{\mathbf{x}}_{C_i}$ and $\bar{\mathbf{x}}_{C_j}$ are the centroids of clusters $C_i$ and $C_j$. Ward's method tends to produce compact, similarly sized spherical clusters and is the most widely used linkage in practice.

Centroid Linkage:

$d_{Centroid}(C_i, C_j) = \|\bar{\mathbf{x}}_{C_i} - \bar{\mathbf{x}}_{C_j}\|^2$

Distance = squared Euclidean distance between cluster centroids. Can produce inversions in the dendrogram (a merged cluster appearing lower than its components) — generally not recommended.

3.5 The K-Means Objective Function

$K$-means clustering partitions $n$ observations into $K$ clusters by minimising the within-cluster sum of squares (WCSS), also called the inertia:

$\text{WCSS} = \sum_{k=1}^{K} \sum_{\mathbf{x}_i \in C_k} \|\mathbf{x}_i - \bar{\mathbf{x}}_k\|^2$

Where:

• $K$ = number of clusters (pre-specified by the researcher).
• $C_k$ = set of observations in cluster $k$.
• $\bar{\mathbf{x}}_k = \frac{1}{|C_k|}\sum_{\mathbf{x}_i \in C_k} \mathbf{x}_i$ = centroid of cluster $k$.

The WCSS can be equivalently written using the between-cluster sum of squares (BCSS):

$\text{WCSS} = SS_{total} - \text{BCSS}$

Where:

$\text{BCSS} = \sum_{k=1}^{K} |C_k| \|\bar{\mathbf{x}}_k - \bar{\mathbf{x}}\|^2$

And $\bar{\mathbf{x}}$ is the global mean of all observations.

3.6 The K-Means Algorithm (Lloyd's Algorithm)

Initialisation: Randomly select $K$ observations as initial centroids $\bar{\mathbf{x}}_1^{(0)}, \bar{\mathbf{x}}_2^{(0)}, \dots, \bar{\mathbf{x}}_K^{(0)}$.

Step 1 — Assignment Step: Assign each observation $\mathbf{x}_i$ to the cluster with the nearest centroid:

$c_i^{(t)} = \arg\min_{k \in \{1,\dots,K\}} \|\mathbf{x}_i - \bar{\mathbf{x}}_k^{(t)}\|^2$

Step 2 — Update Step: Recompute each centroid as the mean of all observations assigned to that cluster:

$\bar{\mathbf{x}}_k^{(t+1)} = \frac{1}{|C_k^{(t)}|}\sum_{\mathbf{x}_i \in C_k^{(t)}} \mathbf{x}_i$

Convergence: Repeat Steps 1–2 until cluster assignments no longer change:

$c_i^{(t+1)} = c_i^{(t)} \quad \forall i$

Or until the change in WCSS is below a threshold $\varepsilon > 0$:

$|\text{WCSS}^{(t+1)} - \text{WCSS}^{(t)}| < \varepsilon$

Convergence guarantee: $K$-means always converges in a finite number of iterations because:

1. The assignment step never increases WCSS.
2. The update step never increases WCSS.
3. The number of possible cluster assignments is finite.

However, the converged solution may be a local optimum. Run with at least 20–50 random starts and keep the solution with the lowest WCSS.

3.7 K-Means++ Initialisation

Standard random initialisation of $K$-means often converges to poor local optima. K-means++ (Arthur & Vassilvitskii, 2007) provides a smarter initialisation:

Step 1: Choose the first centroid uniformly at random from the data:

$\bar{\mathbf{x}}_1 \sim \text{Uniform}\{\mathbf{x}_1, \dots, \mathbf{x}_n\}$

Step 2: For each subsequent centroid $\bar{\mathbf{x}}_k$ ($k = 2, \dots, K$), choose observation $\mathbf{x}_i$ with probability proportional to its squared distance from the nearest already-chosen centroid:

$P(\mathbf{x}_i) = \frac{D(\mathbf{x}_i)^2}{\sum_{j=1}^{n} D(\mathbf{x}_j)^2}$

Where $D(\mathbf{x}_i) = \min_{c \in \text{chosen centroids}} \|\mathbf{x}_i - c\|$.

Step 3: Repeat Step 2 until $K$ centroids are chosen, then run standard K-means.

K-means++ provides an $O(\log K)$ approximation guarantee on the WCSS and typically converges much faster than random initialisation.

3.8 The Gaussian Mixture Model (GMM)

Model-based clustering assumes that the data arise from a finite mixture of multivariate Gaussian distributions. Each component represents a cluster:

$f(\mathbf{x}) = \sum_{k=1}^{K} \pi_k \cdot \mathcal{N}(\mathbf{x} \mid \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k)$

Where:

• $\pi_k$ = mixing proportion of component $k$ ($\sum_k \pi_k = 1$).
• $\boldsymbol{\mu}_k$ = mean vector of component $k$.
• $\boldsymbol{\Sigma}_k$ = covariance matrix of component $k$.
• $\mathcal{N}(\mathbf{x} \mid \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k)$ = multivariate normal density:

$\mathcal{N}(\mathbf{x} \mid \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k) = \frac{1}{(2\pi)^{p/2}|\boldsymbol{\Sigma}_k|^{1/2}} \exp\left(-\frac{1}{2}(\mathbf{x} - \boldsymbol{\mu}_k)^T \boldsymbol{\Sigma}_k^{-1} (\mathbf{x} - \boldsymbol{\mu}_k)\right)$

3.9 The EM Algorithm for GMM

The parameters $\boldsymbol{\Theta} = \{\pi_k, \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k\}_{k=1}^K$ are estimated by maximising the log-likelihood:

$\ell(\boldsymbol{\Theta}) = \sum_{i=1}^{n} \ln\left[\sum_{k=1}^{K} \pi_k \mathcal{N}(\mathbf{x}_i \mid \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k)\right]$

The Expectation-Maximisation (EM) algorithm iterates between two steps:

E-Step (Expectation): Compute the posterior responsibility (soft assignment probability) of component $k$ for observation $i$:

$r_{ik}^{(t)} = \frac{\pi_k^{(t)} \mathcal{N}(\mathbf{x}_i \mid \boldsymbol{\mu}_k^{(t)}, \boldsymbol{\Sigma}_k^{(t)})}{\sum_{j=1}^{K} \pi_j^{(t)} \mathcal{N}(\mathbf{x}_i \mid \boldsymbol{\mu}_j^{(t)}, \boldsymbol{\Sigma}_j^{(t)})}$

M-Step (Maximisation): Update parameters using the current responsibilities:

Effective cluster sizes:

$N_k^{(t)} = \sum_{i=1}^{n} r_{ik}^{(t)}$

Updated mixing proportions:

$\pi_k^{(t+1)} = \frac{N_k^{(t)}}{n}$

Updated means:

$\boldsymbol{\mu}_k^{(t+1)} = \frac{1}{N_k^{(t)}}\sum_{i=1}^{n} r_{ik}^{(t)} \mathbf{x}_i$

Updated covariance matrices:

$\boldsymbol{\Sigma}_k^{(t+1)} = \frac{1}{N_k^{(t)}}\sum_{i=1}^{n} r_{ik}^{(t)} (\mathbf{x}_i - \boldsymbol{\mu}_k^{(t+1)})(\mathbf{x}_i - \boldsymbol{\mu}_k^{(t+1)})^T$

The EM algorithm is guaranteed to converge to a local maximum of the log-likelihood. Key advantage over $K$-means: soft (probabilistic) cluster memberships — each observation belongs to each cluster with a probability, not a hard 0/1 assignment.

4. Assumptions of Cluster Analysis

4.1 The Existence of Clusters (Clusterability)

The most fundamental assumption is that the data contain genuine cluster structure — that the population from which the data are drawn is genuinely multimodal or heterogeneous.

Why it matters: Clustering algorithms will always produce clusters, even for completely random, uniform data. A solution from random data is meaningless.

How to check:

• Hopkins statistic: Tests whether data are uniformly distributed (no cluster structure).

$H = \frac{\sum_{i=1}^{m} u_i^d}{\sum_{i=1}^{m} u_i^d + \sum_{i=1}^{m} w_i^d}$

Where $u_i$ is the distance from a randomly sampled point to its nearest neighbour in the data, and $w_i$ is the distance from a randomly chosen data point to its nearest neighbour. Under a uniform distribution, $H \approx 0.5$. $H > 0.75$ suggests cluster structure.

• Visual methods: Plot pairwise scatter plots and look for visible groupings.

4.2 Scale and Measurement Consistency

All continuous variables must be on comparable scales before computing Euclidean distances. If one variable is measured in millimetres (range 1–10) and another in kilograms (range 50–100), the larger-scale variable will dominate the distance calculation.

How to check:

• Compare the standard deviations of all variables.
• If they differ substantially, standardise (z-score) all variables before clustering.

Standard z-score transformation:

$z_{ik} = \frac{x_{ik} - \bar{x}_k}{\sigma_{x_k}}$

When NOT to standardise:

• When the original scale differences are meaningful (e.g., all variables are on the same scale, such as blood cell counts in the same unit).
• When using Mahalanobis distance (already scale-invariant).

4.3 Absence of Extreme Outliers

Outliers severely distort distance-based clustering methods (especially $K$-means and Ward's hierarchical clustering):

• Outliers may form their own singleton clusters.
• Outliers pull centroids toward them, distorting the clusters for all other observations.

How to check:

• Univariate: Box plots, $z$-scores $> 3$.
• Multivariate: Mahalanobis distance with chi-squared critical value.
• Visualise: Scatter plot matrix for small $p$.

How to handle:

• Remove extreme outliers before clustering (and report their removal).
• Use outlier-robust clustering methods (e.g., $K$-medoids, DBSCAN).
• Add outlier detection as a separate pre-processing step.

4.4 Appropriate Choice of Distance Measure

The distance measure should be appropriate for the type and scale of the variables:

• Continuous variables: Euclidean or Mahalanobis (after standardising).
• Binary variables: Jaccard or Dice coefficient.
• Mixed types: Gower's distance.
• High-dimensional: Cosine similarity.

Choosing the wrong distance measure can produce meaningless clusters even when genuine structure exists.

4.5 Spherical Cluster Shape (for K-Means)

$K$-means assumes clusters are convex and roughly spherical in shape (equal variance in all directions). Non-spherical cluster shapes (elongated, curved, or irregular) will be poorly recovered by $K$-means.

How to check:

• After clustering, plot the clusters and visually inspect their shapes.
• Compute silhouette coefficients — low values for many points suggest non-spherical clusters.

Remedy: Use GMM (which can model elliptical shapes), hierarchical clustering with single linkage (for chain-like clusters), or DBSCAN (for arbitrary shapes).

4.6 Appropriate Number of Clusters (K)

The number of clusters $K$ must be chosen appropriately. Specifying too few clusters over-groups heterogeneous observations; too many clusters fragments natural groups.

How to determine $K$: Use multiple criteria (see Section 10) including the elbow method, silhouette analysis, gap statistic, and BIC. Never rely on a single criterion.

4.7 Adequate Sample Size

Reliable clustering requires sufficient observations per cluster for stable, reproducible results:

Where $K$ is the number of clusters and $p$ is the number of variables.

⚠️ With small samples ($n < 50$), cluster solutions are highly unstable and may not replicate in new data. Always validate the solution using bootstrapping or an independent sample.

5. Types of Cluster Analysis Methods

5.1 Classification by Methodology

Clustering methods are broadly classified by their algorithmic strategy:

5.2 Hierarchical vs. Partitional Methods

5.3 Agglomerative vs. Divisive Hierarchical Clustering

5.4 Hard vs. Soft (Fuzzy) Clustering

5.5 DataStatPro Implementation Overview

The DataStatPro Cluster Analysis component implements:

6. Using the Cluster Analysis Component

The Cluster Analysis component in DataStatPro provides a complete end-to-end workflow for performing, evaluating, and visualising cluster analyses.

Step-by-Step Guide

Step 1 — Select Dataset

Choose the dataset from the "Dataset" dropdown. Ensure:

• All clustering variables are in separate numeric columns.
• Categorical variables are appropriately recoded (dummy-coded or use Gower's distance).
• The dataset has been screened for missing data and extreme outliers.
• Variables are on comparable scales (or will be standardised in Step 4).

💡 Tip: Run descriptive statistics and a correlation matrix before clustering. Variables that are highly correlated ($|r| > 0.90$) are redundant — consider removing one from each pair to avoid over-weighting that dimension in the distance calculation.

Step 2 — Select Clustering Variables

Select all variables to include in the cluster analysis from the "Clustering Variables" dropdown. Only include variables that are:

• Theoretically relevant to the grouping hypothesis.
• Sufficiently variable (variables with near-zero variance contribute nothing to clustering).
• Measured on compatible scales (or will be standardised).

⚠️ Important: Do not include identifier variables (ID numbers), date variables, or outcome variables you intend to use to validate the clusters (these should be held out for post-hoc validation, not used in forming the clusters).

Step 3 — Select Clustering Method

Choose from the "Method" dropdown:

• Hierarchical (Agglomerative): For exploratory analysis; produces a dendrogram. Select linkage method: Ward (recommended), Complete, Average, or Single.
• K-Means: For large datasets with a known approximate number of clusters. Uses K-Means++ initialisation by default.
• K-Medoids (PAM): More robust than K-Means; works with any distance matrix.
• Gaussian Mixture Model (GMM): For soft assignments and elliptical clusters. Select covariance structure: VVV (most flexible), EEE (equal covariance), or others.
• DBSCAN: For arbitrary-shaped clusters and automatic outlier detection. Specify $\varepsilon$ (neighbourhood radius) and MinPts (minimum points).

Step 4 — Standardisation Options

Select how to scale the variables before clustering:

• Standardise (z-scores): Recommended for most analyses with continuous variables of different scales. Transforms each variable to mean = 0, SD = 1.
• Range normalisation (0–1): Scales all variables to the range [0, 1]. $x^* = (x - x_{min})/(x_{max} - x_{min})$.
• No standardisation: Use when variables are already on comparable scales.
• Robust standardisation (median/IQR): Recommended when outliers are present. $x^* = (x - \text{median})/\text{IQR}$.

Step 5 — Select Distance Measure

Choose the appropriate distance measure for your data type:

• Euclidean (default): Continuous, standardised variables.
• Manhattan (City Block): Continuous variables with potential outliers.
• Mahalanobis: Continuous, correlated variables.
• Gower: Mixed variable types (continuous, ordinal, binary, nominal).
• Cosine: High-dimensional data (text, genomics).
• Correlation (1-r): When pattern matters more than magnitude.

Step 6 — Specify Number of Clusters

• For Hierarchical: The dendrogram is produced for all $K$ — cut it at any level to obtain the desired number of clusters. Use the automatic cutting tools in the application (based on height ratios or number of clusters).
• For K-Means / K-Medoids: Specify the number of clusters $K$, or use the automated Elbow Method, Silhouette Analysis, or Gap Statistic to recommend $K$.
• For GMM: Specify the range of $K$ to evaluate; the application selects the optimal $K$ using BIC or ICL.
• For DBSCAN: No $K$ specified; clusters emerge automatically from $\varepsilon$ and MinPts.

💡 Best practice: Always evaluate at least three values of $K$ (your hypothesised number, one fewer, and one more) and compare the solutions on both statistical criteria and theoretical interpretability.

Step 7 — Display Options

Select which outputs and visualisations to display:

• ✅ Dendrogram with highlighted clusters (Hierarchical).
• ✅ Scree/Elbow plot of WCSS vs. $K$.
• ✅ Silhouette plot and average silhouette width.
• ✅ Cluster profile table (means/medians per cluster per variable).
• ✅ PCA biplot coloured by cluster.
• ✅ Cluster size table (n per cluster, percentage).
• ✅ Within-cluster and between-cluster sum of squares.
• ✅ Gap statistic plot.
• ✅ Cluster stability indices (bootstrapped).
• ✅ Heatmap of variable means by cluster.

Step 8 — Run the Analysis

Click "Run Cluster Analysis". The application will:

1. Standardise variables (if selected).
2. Compute the distance matrix.
3. Run the clustering algorithm.
4. Compute cluster validity indices (silhouette, Calinski-Harabasz, Davies-Bouldin).
5. Generate all selected visualisations.
6. Produce a cluster membership variable that can be saved back to the dataset for further analysis.

7. Hierarchical Clustering

7.1 The Dendrogram

The dendrogram is the primary output of hierarchical clustering. It is a binary tree where:

• Leaves (bottom): Individual observations.
• Internal nodes: Cluster merges.
• Height of each node: The dissimilarity at which the merge occurred.
• Root (top): A single cluster containing all observations.

The dendrogram encodes a complete hierarchical clustering solution for all possible numbers of clusters $K$ from 1 to $n$. Cutting the dendrogram at a given height $h$ produces the clustering solution for that number of clusters.

Reading the dendrogram:

• Observations (or clusters) that are merged at a low height are very similar.
• A large gap between consecutive merging heights suggests a natural cut point.
• The number of vertical lines cut by a horizontal cut at height $h$ equals the number of clusters $K$.

7.2 Choosing the Cut Point

Method 1 — Largest height gap:

Inspect the heights of consecutive merges and cut below the largest jump:

$K^* = \arg\max_{k} [h(k) - h(k-1)]$

Where $h(k)$ is the height of the $k$-th merge from the top (merging the last $k$ clusters into $k-1$).

Method 2 — Consistent percentage:

Cut at a height corresponding to a fixed percentage (e.g., 70%) of the total dendrogram height range.

Method 3 — External criteria:

Use cluster validity indices (silhouette width, Calinski-Harabasz) evaluated for several cut heights to determine the optimal $K$.

💡 There is no single "correct" cut point. Combine statistical guidance with theoretical reasoning about the expected number of subgroups in your population.

7.3 Linkage Method Comparison

⚠️ Ward's linkage with Euclidean distance (on standardised data) is the most commonly recommended default. However, it assumes roughly spherical, equally-sized clusters. If clusters are expected to differ dramatically in size or shape, consider average linkage.

7.4 Cophenetic Correlation Coefficient

The cophenetic correlation coefficient (CCC) measures how faithfully the dendrogram preserves the pairwise distances in the original data:

$r_{coph} = \frac{\sum_{i < j}(d_{ij} - \bar{d})(c_{ij} - \bar{c})}{\sqrt{\sum_{i < j}(d_{ij} - \bar{d})^2 \cdot \sum_{i < j}(c_{ij} - \bar{c})^2}}$

Where:

• $d_{ij}$ = original pairwise distance between observations $i$ and $j$.
• $c_{ij}$ = cophenetic distance (height at which $i$ and $j$ first merge in the dendrogram).
• $\bar{d}$, $\bar{c}$ = means of $d_{ij}$ and $c_{ij}$ respectively.

A high CCC ($> 0.75$) indicates that the dendrogram is a faithful representation of the original distances. Compare CCC across linkage methods and choose the one with the highest CCC.

7.5 Hierarchical Clustering for Large Datasets

Standard agglomerative hierarchical clustering has time complexity $O(n^2 \log n)$ and space complexity $O(n^2)$ — it requires storing the full $n \times n$ distance matrix. For large $n > 5{,}000$:

• Use minimax linkage or robust single linkage methods designed for scalability.
• Use DIANA (Divisive Analysis) which can be implemented more efficiently for some data.
• Cluster a random subsample first, then assign remaining observations.
• Use $K$-means or DBSCAN for large $n$.

7.6 Dissimilarity Matrix Heatmap

A dissimilarity heatmap displays the $n \times n$ distance matrix as a colour-coded image, with observations reordered according to the dendrogram. In a well-structured dataset:

• Block-diagonal patterns emerge when clusters are distinct.
• Observations within the same cluster appear in low-dissimilarity (dark) blocks.
• Off-diagonal blocks show higher dissimilarity (lighter colour) between clusters.

This visual provides an immediate, intuitive check on the quality and separation of the cluster solution.

8. K-Means and K-Medoids Clustering

8.1 Choosing K — The Elbow Method

The elbow method plots WCSS (total within-cluster sum of squares) against $K$ and looks for an "elbow" — a point where the rate of decrease in WCSS slows dramatically:

$\text{WCSS}(K) = \sum_{k=1}^{K}\sum_{\mathbf{x}_i \in C_k}\|\mathbf{x}_i - \bar{\mathbf{x}}_k\|^2$

As $K$ increases from 1 to $n$:

• WCSS decreases monotonically (more clusters always explain more variance).
• The marginal decrease diminishes after the "true" number of clusters.
• The elbow occurs at the $K$ where the curve transitions from steep to relatively flat.

Limitation: The elbow is often subjective — in real data, the curve is frequently smooth without a clear kink. Combine with silhouette analysis and the gap statistic.

8.2 The Silhouette Coefficient

For each observation $i$ assigned to cluster $C_k$, the silhouette coefficient measures how well the observation fits its assigned cluster compared to the nearest other cluster:

$a(i)$: Average distance from observation $i$ to all other observations in the same cluster $C_k$ (intra-cluster cohesion):

$a(i) = \frac{1}{|C_k| - 1}\sum_{j \in C_k, j \neq i} d(i, j)$

$b(i)$: Minimum average distance from observation $i$ to all observations in any other cluster (inter-cluster separation):

$b(i) = \min_{l \neq k} \frac{1}{|C_l|}\sum_{j \in C_l} d(i, j)$

Silhouette coefficient for observation $i$:

$s(i) = \frac{b(i) - a(i)}{\max[a(i), b(i)]}$

Ranges from $-1$ to $+1$:

• $s(i) \approx +1$: Observation is well-matched to its cluster and poorly matched to neighbouring clusters.
• $s(i) \approx 0$: Observation is on or very close to the boundary between two clusters.
• $s(i) \approx -1$: Observation would be better placed in a neighbouring cluster (probable misclassification).

Average silhouette width (ASW): The mean $s(i)$ across all observations:

$\bar{s} = \frac{1}{n}\sum_{i=1}^{n} s(i)$

Choose $K$ that maximises $\bar{s}$.

8.3 The Gap Statistic

The gap statistic (Tibshirani, Walther & Hastie, 2001) compares the observed WCSS for $K$ clusters to the expected WCSS under a null reference distribution (uniform data with no cluster structure):

$\text{Gap}(K) = E^*[\log \text{WCSS}(K)] - \log \text{WCSS}(K)$

Where $E^*[\cdot]$ is the expectation under the null reference distribution (estimated by Monte Carlo simulation of $B = 100$ uniform datasets).

Choosing $K$: Select the smallest $K$ such that:

$\text{Gap}(K) \geq \text{Gap}(K+1) - s_{K+1}$

Where $s_{K+1} = SD[\log \text{WCSS}(K+1)] \cdot \sqrt{1 + 1/B}$ is the simulation error.

The gap statistic accounts for sampling variability and provides a more principled stopping rule than the elbow method.

8.4 Calinski-Harabasz Index (Variance Ratio Criterion)

The Calinski-Harabasz (CH) index (also called the Variance Ratio Criterion) measures the ratio of between-cluster variance to within-cluster variance:

$CH(K) = \frac{\text{BCSS}/(K-1)}{\text{WCSS}/(n-K)}$

Where:

• $\text{BCSS} = \sum_{k=1}^{K} n_k \|\bar{\mathbf{x}}_k - \bar{\mathbf{x}}\|^2$ = between-cluster sum of squares.
• $\text{WCSS} = \sum_{k=1}^{K}\sum_{\mathbf{x}_i \in C_k}\|\mathbf{x}_i - \bar{\mathbf{x}}_k\|^2$ = within-cluster sum of squares.

Higher CH index = better-defined clusters. Choose $K$ that maximises $CH(K)$.

8.5 Davies-Bouldin Index

The Davies-Bouldin (DB) index measures the average similarity between each cluster and its most similar other cluster:

$DB(K) = \frac{1}{K}\sum_{k=1}^{K} \max_{l \neq k} \left(\frac{\sigma_k + \sigma_l}{d(\bar{\mathbf{x}}_k, \bar{\mathbf{x}}_l)}\right)$

Where:

• $\sigma_k = \frac{1}{n_k}\sum_{\mathbf{x}_i \in C_k}\|\mathbf{x}_i - \bar{\mathbf{x}}_k\|$ = average within-cluster distance from centroid.
• $d(\bar{\mathbf{x}}_k, \bar{\mathbf{x}}_l)$ = distance between centroids of clusters $k$ and $l$.

Lower DB index = better separation. Choose $K$ that minimises $DB(K)$.

8.6 K-Medoids (PAM — Partitioning Around Medoids)

$K$-medoids is a robust alternative to $K$-means that represents each cluster by an actual medoid — the observation within the cluster that minimises the total dissimilarity to all other cluster members:

$\text{medoid}(C_k) = \arg\min_{\mathbf{x}_i \in C_k} \sum_{\mathbf{x}_j \in C_k} d(\mathbf{x}_i, \mathbf{x}_j)$

PAM algorithm:

Step 1 (BUILD): Sequentially select $K$ initial medoids.

Step 2 (SWAP): For each medoid $m$ and each non-medoid observation $o$:

• Tentatively swap $m$ with $o$ and compute the total cost (sum of dissimilarities).
• If the total cost decreases, make the swap permanent.

Step 3: Repeat until no improvement is possible.

Objective function:

$\text{Total Cost} = \sum_{k=1}^{K}\sum_{\mathbf{x}_i \in C_k} d(\mathbf{x}_i, \text{medoid}_k)$

Advantages of K-Medoids over K-Means:

• Works with any distance matrix (not just Euclidean).
• Medoids are actual data points (interpretable).
• More robust to outliers (outliers are not selected as medoids under PAM).
• Applicable to mixed data with Gower's distance.

Disadvantage: Computationally more expensive than $K$-means ($O(K(n-K)^2)$ per iteration).

8.7 K-Modes for Categorical Data

When all variables are categorical (nominal), $K$-means and $K$-medoids are not directly applicable. $K$-modes (Huang, 1998) extends $K$-means by:

• Replacing the mean with the mode as the cluster representative.
• Using the simple matching dissimilarity (proportion of mismatches):

$d(\mathbf{x}_i, \mathbf{x}_j) = \sum_{k=1}^{p} \mathbf{1}[x_{ik} \neq x_{jk}]$

For mixed data (continuous + categorical), $K$-prototypes combines:

$d(\mathbf{x}_i, \mathbf{x}_j) = \sum_{k=1}^{p_c}(x_{ik} - x_{jk})^2 + \gamma \sum_{k=1}^{p_d}\mathbf{1}[x_{ik} \neq x_{jk}]$

Where $p_c$ = number of continuous variables, $p_d$ = number of categorical variables, and $\gamma > 0$ is a weight balancing the two contributions.

9. Model-Based and Density-Based Clustering

9.1 Gaussian Mixture Models (GMM) — Model-Based Clustering

Model-based clustering (Fraley & Raftery, 2002) treats clustering as a model selection problem. The data are assumed to arise from a GMM, and the optimal number of clusters $K$ and covariance structure are selected using the Bayesian Information Criterion (BIC).

Covariance matrix parameterisation:

The key advantage of GMM is the ability to model different cluster shapes, sizes, and orientations by parameterising the covariance matrices $\boldsymbol{\Sigma}_k$.

Using eigenvalue decomposition of $\boldsymbol{\Sigma}_k$:

$\boldsymbol{\Sigma}_k = \lambda_k \mathbf{D}_k \mathbf{A}_k \mathbf{D}_k^T$

Where:

• $\lambda_k = |\boldsymbol{\Sigma}_k|^{1/p}$ = volume (overall size of cluster $k$).
• $\mathbf{D}_k$ = matrix of eigenvectors = orientation (direction of cluster axes).
• $\mathbf{A}_k$ = diagonal matrix with normalised eigenvalues = shape (ratio of axes).

By constraining or freeing these three components across clusters, 14 different model types are defined in the mclust framework:

BIC for model selection:

$\text{BIC}(K, \text{model}) = 2\hat{\ell} - q \ln(n)$

Where $\hat{\ell}$ is the maximised log-likelihood and $q$ is the number of free parameters. Higher BIC = better model (note: some software uses $-2\hat{\ell} + q\ln(n)$; here higher means better for the positive convention used in mclust).

ICL (Integrated Complete-data Likelihood):

$\text{ICL}(K) = \text{BIC}(K) + 2\sum_{i=1}^{n}\sum_{k=1}^{K} \hat{r}_{ik}\ln(\hat{r}_{ik})$

ICL adds an entropy penalty for fuzzy assignments. Models where observations are clearly assigned (low entropy) are favoured by ICL over BIC.

9.2 Soft Cluster Membership in GMM

A major advantage of GMM over $K$-means is the production of posterior probabilities of cluster membership for each observation. After EM convergence:

$P(\text{cluster} = k \mid \mathbf{x}_i) = r_{ik} = \frac{\hat{\pi}_k \mathcal{N}(\mathbf{x}_i \mid \hat{\boldsymbol{\mu}}_k, \hat{\boldsymbol{\Sigma}}_k)}{\sum_{j=1}^{K} \hat{\pi}_j \mathcal{N}(\mathbf{x}_i \mid \hat{\boldsymbol{\mu}}_j, \hat{\boldsymbol{\Sigma}}_j)}$

These probabilities allow identification of:

• Borderline cases ($r_{ik} \approx 0.5$ for two clusters) — observations near cluster boundaries.
• Atypical members (low probability of belonging to any cluster).
• Uncertainty maps — spatial or other visualisations of cluster membership uncertainty.

9.3 DBSCAN — Density-Based Spatial Clustering

DBSCAN (Density-Based Spatial Clustering of Applications with Noise; Ester et al., 1996) identifies clusters as dense regions of the data space, separated by low-density regions. It does not require specifying $K$ in advance and can identify outliers (noise points).

Key parameters:

• $\varepsilon$ (epsilon): The neighbourhood radius — how far from a point to look for neighbours.
• MinPts: The minimum number of points within distance $\varepsilon$ for a point to be considered a core point.

Point classification:

A point $\mathbf{x}_i$ is classified as:

Core point: $|\mathcal{N}_\varepsilon(\mathbf{x}_i)| \geq \text{MinPts}$

Where $\mathcal{N}_\varepsilon(\mathbf{x}_i) = \{\mathbf{x}_j : d(\mathbf{x}_i, \mathbf{x}_j) \leq \varepsilon\}$ is the $\varepsilon$-neighbourhood of $\mathbf{x}_i$.

Border point: Not a core point, but within distance $\varepsilon$ of a core point.

Noise point (outlier): Neither a core point nor a border point.

DBSCAN algorithm:

1. Label all points as unvisited.
2. For each unvisited core point $p$: mark as visited; create a new cluster $C$; add all points in $\mathcal{N}_\varepsilon(p)$ to $C$.
3. For each newly added point $q$ in $C$: if $q$ is a core point, add all points in $\mathcal{N}_\varepsilon(q)$ to $C$ (density reachability).
4. Continue until no more points can be added to $C$; label all non-core border points.
5. Mark remaining unvisited non-core points as noise.

Key properties of DBSCAN:

• Does not require specifying $K$.
• Can discover clusters of arbitrary shape.
• Automatically identifies and labels outliers as noise.
• Produces the same results for the same $\varepsilon$ and MinPts (deterministic).
• Struggles with clusters of varying density.

9.4 Choosing DBSCAN Parameters

Setting MinPts:

• Rule of thumb: MinPts $= 2 \times p$ (twice the number of dimensions).
• Larger MinPts → more stringent core point requirement → fewer, larger clusters.
• Minimum recommended: MinPts $\geq 4$ for 2D data; MinPts $\geq 2p$ for higher dimensions.

Setting $\varepsilon$:

• Plot the $k$-nearest neighbour distance plot (k-NN distance plot) where $k = \text{MinPts}$.
• Sort observations by their MinPts-nearest neighbour distance in decreasing order.
• The knee/elbow of this plot corresponds to the appropriate $\varepsilon$.

$\varepsilon^* \approx d_{MinPts-NN, \text{knee}}$

9.5 HDBSCAN — Hierarchical DBSCAN

HDBSCAN extends DBSCAN to handle varying density clusters by transforming the space using the concept of mutual reachability distance:

$d_{mreach,MinPts}(\mathbf{x}_i, \mathbf{x}_j) = \max[\text{core}_{MinPts}(\mathbf{x}_i), \text{core}_{MinPts}(\mathbf{x}_j), d(\mathbf{x}_i, \mathbf{x}_j)]$

Where $\text{core}_{MinPts}(\mathbf{x}_i)$ is the MinPts-nearest neighbour distance (the core distance) of point $\mathbf{x}_i$.

HDBSCAN builds a hierarchical clustering tree on this transformed space and extracts a flat clustering by selecting the most stable clusters across all density levels. Only MinPts needs to be specified (not $\varepsilon$).

9.6 Fuzzy C-Means

Fuzzy C-Means (FCM) is a soft-assignment generalisation of $K$-means. Each observation has a degree of membership $u_{ik} \in [0, 1]$ in each cluster $k$, with $\sum_{k=1}^K u_{ik} = 1$.

FCM objective function:

$J_m = \sum_{i=1}^{n}\sum_{k=1}^{K} u_{ik}^m \|\mathbf{x}_i - \bar{\mathbf{x}}_k\|^2$

Where $m > 1$ is the fuzziness parameter (typically $m = 2$):

• $m \to 1$: Hard assignments (approaches $K$-means).
• $m \to \infty$: All memberships equal $1/K$ (completely fuzzy, no structure).

FCM update equations:

Centroids:

$\bar{\mathbf{x}}_k = \frac{\sum_{i=1}^{n} u_{ik}^m \mathbf{x}_i}{\sum_{i=1}^{n} u_{ik}^m}$

Memberships:

$u_{ik} = \frac{1}{\sum_{j=1}^{K}\left(\frac{\|\mathbf{x}_i - \bar{\mathbf{x}}_k\|}{\|\mathbf{x}_i - \bar{\mathbf{x}}_j\|}\right)^{2/(m-1)}}$

Iterate until convergence ($\|U^{(t+1)} - U^{(t)}\| < \varepsilon$).

10. Model Fit and Evaluation

Evaluating cluster quality is fundamentally more challenging than evaluating supervised model fit because there is no ground truth to compare against. Multiple complementary criteria must be consulted.

10.1 Internal Validity Indices

Internal validity indices assess cluster quality using only the clustering data and the resulting cluster assignments.

Average Silhouette Width (ASW):

$\bar{s} = \frac{1}{n}\sum_{i=1}^{n} s(i), \quad s(i) = \frac{b(i) - a(i)}{\max[a(i), b(i)]}$

Higher is better. Optimal $K$ = $K$ that maximises $\bar{s}$.

Calinski-Harabasz (CH) Index:

$CH = \frac{(n - K) \cdot \text{BCSS}}{(K - 1) \cdot \text{WCSS}}$

Higher is better.

Davies-Bouldin (DB) Index:

$DB = \frac{1}{K}\sum_{k=1}^{K}\max_{l \neq k}\frac{\sigma_k + \sigma_l}{d(\bar{\mathbf{x}}_k, \bar{\mathbf{x}}_l)}$

Lower is better.

Dunn Index:

$D = \frac{\min_{k \neq l} d_{min}(C_k, C_l)}{\max_m \Delta(C_m)}$

Where $d_{min}(C_k, C_l) = \min_{\mathbf{x} \in C_k, \mathbf{y} \in C_l} d(\mathbf{x}, \mathbf{y})$ is the minimum inter-cluster distance and $\Delta(C_m) = \max_{\mathbf{x}, \mathbf{y} \in C_m} d(\mathbf{x}, \mathbf{y})$ is the diameter (maximum intra-cluster distance) of cluster $m$.

Higher Dunn index = better separation and compactness. Sensitive to outliers.

Summary of Internal Validity Indices:

10.2 External Validity Indices

When true cluster labels are available (e.g., in a validation or simulation study), external validity indices compare the clustering result to the known ground truth.

Adjusted Rand Index (ARI):

The Rand Index counts agreements between pairs of observations in the clustering and in the true partition. The Adjusted Rand Index corrects for chance agreement:

$\text{ARI} = \frac{\text{RI} - E[\text{RI}]}{\max(\text{RI}) - E[\text{RI}]}$

More explicitly, for contingency table $\mathbf{N}$ with elements $n_{ij}$ (number of objects in cluster $i$ of solution 1 AND cluster $j$ of solution 2):

$\text{ARI} = \frac{\sum_{ij}\binom{n_{ij}}{2} - \left[\sum_i\binom{a_i}{2}\sum_j\binom{b_j}{2}\right]/\binom{n}{2}}{\frac{1}{2}\left[\sum_i\binom{a_i}{2} + \sum_j\binom{b_j}{2}\right] - \left[\sum_i\binom{a_i}{2}\sum_j\binom{b_j}{2}\right]/\binom{n}{2}}$

Where $a_i = \sum_j n_{ij}$ and $b_j = \sum_i n_{ij}$ are row and column marginals.

Normalised Mutual Information (NMI):

$\text{NMI}(U, V) = \frac{2 \cdot I(U; V)}{H(U) + H(V)}$

Where $I(U;V)$ is the mutual information and $H(U)$, $H(V)$ are the entropies of the two clusterings: