Implementing K-Means Clustering in Python - Convergence implementing Initial Centroids
I've tried everything I can think of but I'm trying to implement the K-Means clustering algorithm from scratch in Python, but I'm running into problems with convergence. I'm using the `numpy` library for matrix operations and I believe my centroid initialization is causing the clusters to not converge properly. Here’s the core of my implementation: ```python import numpy as np class KMeans: def __init__(self, k, max_iters=100): self.k = k self.max_iters = max_iters def fit(self, X): # Randomly initialize centroids random_indices = np.random.choice(len(X), self.k, replace=False) self.centroids = X[random_indices] for _ in range(self.max_iters): # Assign clusters distances = np.linalg.norm(X[:, np.newaxis] - self.centroids, axis=2) self.labels = np.argmin(distances, axis=1) # Re-calculate centroids new_centroids = np.array([X[self.labels == i].mean(axis=0) for i in range(self.k)]) # Check for convergence if np.array_equal(self.centroids, new_centroids): break self.centroids = new_centroids return self.labels ``` The scenario arises when I try with different datasets. Sometimes, the algorithm runs for the maximum number of iterations without reaching convergence, and other times, it produces clusters that don't make intuitive sense. I’ve tried normalizing my data and using different random seed values for centroid initialization, but the behavior remains inconsistent. Here’s how I’m testing it: ```python from sklearn.datasets import make_blobs X, _ = make_blobs(n_samples=300, centers=4, cluster_std=0.60, random_state=0) kmeans = KMeans(k=4) labels = kmeans.fit(X) ``` When I plot the results using `matplotlib`, I notice that sometimes the centroids are placed in the middle of the data points, but other times they end up too close to the edges or even outside the actual clusters. I also get warning messages like `RuntimeWarning: Mean of empty slice` when there are no points assigned to a cluster. Has anyone experienced similar convergence issues, or can anyone suggest effective strategies for centroid initialization or debugging this implementation? This is part of a larger service I'm building. What are your experiences with this? Any pointers in the right direction?