0/318

00:00:00

Description

Editorial

Variance Ratio Criterion for Cluster Quality Assessment

MEDIUM20 pts

When performing unsupervised learning, one of the most challenging aspects is determining how good a clustering solution actually is. Unlike supervised learning where we have ground truth labels, clustering requires intrinsic metrics that evaluate cluster quality based solely on the data structure.

The Variance Ratio Criterion (VRC), also known as the Calinski-Harabasz Index, is a powerful internal evaluation metric that quantifies cluster separation quality. It operates on a fundamental principle: good clustering should produce compact, well-separated groups—points within the same cluster should be close together, while points in different clusters should be far apart.

Mathematical Foundation

The VRC score is computed as the ratio of between-cluster dispersion to within-cluster dispersion, normalized by degrees of freedom:

$$VRC = \frac{B_k / (k - 1)}{W_k / (n - k)}$$

Where:

n = total number of data points
k = number of clusters
B_k = between-cluster dispersion (trace of between-group scatter matrix)
W_k = within-cluster dispersion (trace of within-group scatter matrix)

Between-Cluster Dispersion (B_k)

This measures how spread out the cluster centroids are from the global centroid:

$$B_k = \sum_{q=1}^{k} n_q \cdot |c_q - c|^2$$

Where:

n_q = number of points in cluster q
c_q = centroid of cluster q
c = global centroid of all data points

Within-Cluster Dispersion (W_k)

This measures how tightly packed points are within their respective clusters:

$$W_k = \sum_{q=1}^{k} \sum_{x \in C_q} |x - c_q|^2$$

Interpretation

Higher VRC values indicate better clustering — clusters are dense and well-separated
Lower VRC values indicate poorer clustering — clusters overlap or are too dispersed
The metric is useful for comparing different clustering configurations on the same dataset
Edge cases: Return 0.0 when there's only one cluster (k = 1) or when k = n (each point is its own cluster)

Your Task

Implement a function that computes the Variance Ratio Criterion given a dataset and its cluster assignments. Handle edge cases appropriately and return the score rounded to 4 decimal places.

Example

Input

X = [[0, 0], [1, 0], [0, 1], [10, 10], [11, 10], [10, 11]]
labels = [0, 0, 0, 1, 1, 1]

Output

450.0

Explanation

Dataset Analysis: The dataset contains 6 points in 2D space, divided into 2 distinct clusters.

Cluster 0: Points near the origin

(0, 0), (1, 0), (0, 1)
Centroid c₀ = (0.333, 0.333)

Cluster 1: Points near (10, 10)

(10, 10), (11, 10), (10, 11)
Centroid c₁ = (10.333, 10.333)

Global Centroid: c = (5.333, 5.333)

Within-Cluster Dispersion (W_k):

Cluster 0: sum of squared distances from points to c₀
Cluster 1: sum of squared distances from points to c₁
Both clusters are compact with small internal variance

Between-Cluster Dispersion (B_k):

3 × ||(0.333, 0.333) - (5.333, 5.333)||² + 3 × ||(10.333, 10.333) - (5.333, 5.333)||²
The two cluster centroids are far apart, yielding high dispersion

Result: VRC = 450.0

This high score indicates excellent cluster separation—the clusters are tight internally and well-separated from each other.

Example

Input

X = [[0.445, -1.0836], [0.1704, -0.892], [0.395, -0.3682], [9.8784, 9.5017], [9.1809, 8.9391], [9.6732, 10.102], [20.4938, 20.3002], [20.7388, 19.6266], [20.3168, 20.5986]]
labels = [0, 0, 0, 1, 1, 1, 2, 2, 2]

Output

2076.7937

Explanation

Dataset Analysis: 9 points in 2D space divided into 3 clusters, each with very tight groupings.

Cluster 0: Points near origin (lower-left region)

Average position around (0.337, -0.781)

Cluster 1: Points near (9.5, 9.5) (middle region)

Average position around (9.577, 9.514)

Cluster 2: Points near (20.5, 20.2) (upper-right region)

Average position around (20.516, 20.175)

Key Observations:

Each cluster contains points very close to each other (low within-cluster dispersion)
The three cluster centroids are approximately 10 units apart from adjacent clusters (high between-cluster dispersion)
With k=3 clusters and n=9 samples, we have good degrees of freedom

Result: VRC = 2076.7937

This very high score reflects the exceptional cluster quality: extremely compact clusters with large separation distances between them.

Example

Input

X = [[9.1443, -3.2681], [-8.1451, -8.0657], [6.9499, 2.0745], [6.1426, 4.5946], [0.7246, 9.4623]]
labels = [0, 0, 0, 0, 0]

Output

0.0

Explanation

Edge Case: Single Cluster

When all data points are assigned to the same cluster (k = 1), the Variance Ratio Criterion cannot be meaningfully computed because:

No between-cluster dispersion exists — there's only one cluster centroid, which is identical to the global centroid
Division by (k-1) = 0 — the formula's denominator in the between-cluster term becomes zero
No comparison baseline — we cannot evaluate "separation" when there's nothing to separate from

By convention, we return 0.0 for this edge case, indicating that the clustering provides no information about cluster quality.

Similarly, if k = n (each point is its own cluster), we return 0.0 because within-cluster dispersion would be zero with single-point clusters.

Accepted0/0·0% Acceptance

Constraints

2 ≤ n_samples ≤ 10,000 (number of data points)
1 ≤ n_features ≤ 100 (dimensionality of feature space)
1 ≤ k ≤ n_samples (number of unique clusters)
-10⁶ ≤ X[i][j] ≤ 10⁶ (feature values)
Cluster labels are consecutive integers starting from 0
Each cluster contains at least one data point
Return 0.0 if k = 1 or k = n_samples
Round the final result to 4 decimal places

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

X =

[[9.1443,-3.2681],[-8.1451,-8.0657],[6.9499,2.0745],[6.1426,4.5946],[0.7246,9.4623]]

labels =

[0,0,0,0,0]

Mathematical Foundation

The VRC score is computed as the ratio of between-cluster dispersion to within-cluster dispersion, normalized by degrees of freedom:

$$VRC = \frac{B_k / (k - 1)}{W_k / (n - k)}$$

Where:

n = total number of data points

k = number of clusters

B_k = between-cluster dispersion (trace of between-group scatter matrix)

W_k = within-cluster dispersion (trace of within-group scatter matrix)

Between-Cluster Dispersion (B_k)

This measures how spread out the cluster centroids are from the global centroid:

$$B_k = \sum_{q=1}^{k} n_q \cdot |c_q - c|^2$$

Where:

n_q = number of points in cluster q

c_q = centroid of cluster q

c = global centroid of all data points

Within-Cluster Dispersion (W_k)

This measures how tightly packed points are within their respective clusters:

$$W_k = \sum_{q=1}^{k} \sum_{x \in C_q} |x - c_q|^2$$

Interpretation

Higher VRC values indicate better clustering — clusters are dense and well-separated

Lower VRC values indicate poorer clustering — clusters overlap or are too dispersed

The metric is useful for comparing different clustering configurations on the same dataset

Edge cases: Return 0.0 when there's only one cluster (k = 1) or when k = n (each point is its own cluster)

Variance Ratio Criterion for Cluster Quality Assessment

Mathematical Foundation

Between-Cluster Dispersion (B_k)

Within-Cluster Dispersion (W_k)

Interpretation

Your Task

Hints

Variance Ratio Criterion for Cluster Quality Assessment

Mathematical Foundation

Between-Cluster Dispersion (B_k)

Within-Cluster Dispersion (W_k)

Interpretation

Your Task

Hints