Clustering formulas

Clustering: k-means, k-medoids and hierarchical clustering. 14 formulas for GATE DA Machine Learning, each with when to use it. Each is explained in the topic notes.

All 14 Clustering formulas

EUCLIDEAN DISTANCE

d_{2} (x, y) = j = 1 \sum d (x_{j} - y_{j})^{2}

Default distance. k-means is built around its square.

MANHATTAN DISTANCE

d_{1} (x, y) = j = 1 \sum d ∣ x_{j} - y_{j} ∣

Sum of absolute coordinate differences. For (1,1) and (4,5): Manhattan = 3 + 4 = 7, Euclidean = 5.

K-MEANS OBJECTIVE (WCSS)

J = k = 1 \sum K x \in C_{k} \sum ∥ x - μ_{k} ∥^{2}

Squared Euclidean distance of each point to its own cluster's centroid, summed over all points.

ASSIGNMENT STEP

c (i) = ar g k min ∥ x_{i} - μ_{k} ∥^{2}

Nearest centroid in Euclidean distance (squaring does not change which centroid is nearest). Ties need a fixed rule: keep the point in its current cluster if that cluster is among the nearest, otherwise take the lowest index.

UPDATE STEP (CENTROID)

μ_{k} = \frac{1}{∣ C _{k} ∣} x \in C_{k} \sum x

Defined for a non-empty cluster. The mean is the point that minimises the sum of squared Euclidean distances to the cluster's points, so this step cannot increase $J$ .

WCSS FROM PAIRWISE DISTANCES

x \in C \sum ∥ x - μ ∥^{2} = \frac{1}{2 ∣ C ∣} x \in C \sum y \in C \sum ∥ x - y ∥^{2}

The double sum runs over all ordered pairs (each unordered pair counted twice). Useful when only distances are given. Check: for {1, 2, 4} the right side is 28/6 = 4.667, the same as the left.

SILHOUETTE COEFFICIENT OF POINT I

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

$a (i)$ = mean distance from point $i$ to the other points of its own cluster; $b (i)$ = the smallest, over the other clusters, of the mean distance from $i$ to that cluster's points. $- 1 \leq s (i) \leq 1$ : near 1 means well placed, negative means $i$ is on average closer to another cluster. By convention $s (i) = 0$ if $i$ is alone in its cluster. A higher average $s (i)$ over all points indicates a better $K$ .

MEDOID OF A CLUSTER

m_{k} = ar g x \in C_{k} min y \in C_{k} \sum d (x, y)

The member of the cluster with the smallest total dissimilarity to the other members. k-medoids minimises $\sum_{k} \sum_{x \in C_{k}} d (x, m_{k})$ .

SINGLE LINKAGE (NEAREST NEIGHBOUR)

D (A, B) = a \in A, b \in B min d (a, b)

Closest pair across the two clusters. Prone to chaining: a line of nearby points joins distant groups into one long cluster.

COMPLETE LINKAGE (FARTHEST NEIGHBOUR)

D (A, B) = a \in A, b \in B max d (a, b)

Farthest pair across the two clusters. Favours compact clusters of similar diameter.

AVERAGE LINKAGE

D (A, B) = \frac{1}{∣ A ∣ ∣ B ∣} a \in A \sum b \in B \sum d (a, b)

Mean of all cross-cluster pairwise distances. For the same pair of clusters it lies between the single-linkage and complete-linkage values.

WARD'S LINKAGE

D_{Ward} (A, B) = \frac{∣ A ∣ ∣ B ∣}{∣ A ∣ + ∣ B ∣} ∥ μ_{A} - μ_{B} ∥^{2}

The increase in total WCSS caused by merging $A$ and $B$ ; it merges the pair that increases the WCSS least. Needs Euclidean coordinates (centroids). Software scales the reported height differently, but the order of merges is the same.

CENTROID LINKAGE

D (A, B) = ∥ μ_{A} - μ_{B} ∥

Distance between the cluster means. Needs Euclidean coordinates, and it can give inversions (a later merge lower than an earlier one).

AVERAGE-LINKAGE UPDATE AFTER MERGING A AND B

D (A \cup B, C) = \frac{∣ A ∣ D ( A , C ) + ∣ B ∣ D ( B , C )}{∣ A ∣ + ∣ B ∣}

Weight the two old distances by cluster size. The plain average of $D (A, C)$ and $D (B, C)$ is wrong unless $∣ A ∣ = ∣ B ∣$ .

Where this was asked: 2024 (2), 2025 (1), 2026 (1). See the 4 previous-year questions on Clustering. This shows what was asked, not what will be asked.

KEEP GOING

Clustering: the notes and 4 solved previous-year questions