Implement K-Means and Explain Convergence

Problem Statement

Implement the K-means clustering algorithm in Python. Your implementation should take a dataset of points and an integer k as input and return the final cluster centroids and the cluster assignments for each point.

Requirements

• Use Euclidean distance to measure the proximity between points and centroids.
• Implement a function kmeans(data, k, max_iters) that performs the algorithm.
• Include logic to handle the update of centroids.
• Stop iterating if centroids do not change between iterations or max_iters is reached.

Function Signature

def kmeans(data, k, max_iters=100):
    # data: list of lists or numpy array of shape (n_samples, n_features)
    # k: number of clusters
    # returns: (centroids, assignments)
    pass

Constraints

• n_samples up to 10,000, n_features up to 50.
• Handle the edge case where a cluster might become empty during an iteration (e.g., re-initialize the centroid to a random point).

Example

data = [[1, 2], [1, 4], [1, 0], [10, 2], [10, 4], [10, 0]]
k = 2
# Output: Centroids will likely converge to [1, 2] and [10, 2]

Convergence and Theory

1. Explain the objective function that K-means minimizes (the Within-Cluster Sum of Squares).
2. Why is the algorithm guaranteed to converge?
3. Discuss the time complexity of a single iteration in terms of n, k, and d (features).