Two Scores for One Grouping

In Choosing K you judged clusterings by eye: a good one keeps every point close to its own centroid and keeps the centroids far apart. Two standard scores turn that judgement into numbers, so you can compare groupings of the same data without drawing a picture.

All distances here are ordinary straight-line (Euclidean) distances. Cluster $i$ holds $n_i$ points, and its centroid $c_i$ is the average of those points. The centre of all the data, $\bar c$ , is the average of every point. There are $n$ points and $k$ clusters.

Davies–Bouldin score (lower is better)

Each cluster's spread $s_i$ is the average distance from its points to its centroid. For any two different clusters $i$ and $j$ , their ratio is

R_{ij} = \frac{s_i + s_j}{\lVert c_i - c_j \rVert}

This ratio is large when two clusters are wide and close together, which is bad.

Find every cluster's spread $s_i$ . Use plain distances, not squared ones.
Compute $R_{ij}$ for every pair of different clusters.
Each cluster keeps its worst ratio, $D_i = \max_{j \ne i} R_{ij}$ . That is the ratio with the cluster it is most easily confused with.
The score is the average of $D_i$ over all $k$ clusters.

Calinski–Harabasz score (higher is better)

B = \sum_{i} n_i \, \lVert c_i - \bar c \rVert^2, \qquad W = \sum_{i} \; \sum_{x \in \text{cluster } i} \lVert x - c_i \rVert^2

\text{CH} = \frac{B / (k - 1)}{W / (n - k)}

$B$ measures how far the centroids sit from the middle of the data, with each centroid counted once for every point it holds. $W$ is the error left inside the clusters, the same quantity the elbow plot tracks.

Task: write cluster_scores(points, labels). It returns the tuple (davies_bouldin, calinski_harabasz), each rounded to 4 decimal places.

points is a list of points. Each point is a list of numbers, and all points have the same length (2, 3 or more coordinates).
labels[i] is the cluster of points[i]. Labels can be any values, numbers or strings, and only the grouping they describe matters.
There are always at least 2 clusters and more points than clusters. No two clusters share a centroid, and not every point sits exactly on its centroid.

A coffee shop's customers, plotted by visits per week and average spend, can be grouped in many ways. Score two groupings with this function, and the better one usually wins on both numbers: a lower Davies–Bouldin score and a higher Calinski–Harabasz score. The two scores measure the idea differently, so now and then they disagree.

Two Scores for One Grouping

Examples

Hints