Click4Ai

83.

Easy

Implement the **Elbow Method** to find the optimal number of clusters for K-Means.

Inertia (WCSS):

Inertia = sum of squared distances from each point to its assigned centroid

= sum_over_clusters( sum_over_points_in_cluster( ||x - centroid||^2 ) )

Write two functions:

1. calculate_inertia(X, centroids, labels): Compute total WCSS

2. elbow_method(X, max_k): Run K-Means for k=1 to max_k, return list of inertia values

Example:

inertias = elbow_method(X, max_k=10)

# Plot inertias vs k -- look for the "elbow" point

# inertias = [100, 50, 20, 18, 17, 16.5, ...] # elbow at k=3

**Explanation:** As k increases, inertia always decreases. The "elbow" is where adding more clusters stops significantly reducing inertia, suggesting the optimal k.

Constraints:

  • Return a list of floats with length max_k
  • For each k, run a simple K-Means (random init, 100 iterations)

    • Test Cases

    Test Case 1
    Input: 3 well-separated clusters, max_k=5
    Expected: Inertia drops sharply at k=3, then flattens
    Test Case 2
    Input: calculate_inertia with perfect clustering
    Expected: 0.0 (all points at centroids)
    Test Case 3
    Input: len(elbow_method(X, max_k=10))
    Expected: 10
    + 2 hidden test cases