K-means clustering

K-means is an unsupervised machine learning algorithm used for partitioning a dataset into K distinct, non-overlapping subgroups (clusters). It uses Clustering metrics for evaluation.
Not to be confused with knn. KNN is a supervised algorithm for classification/regression finding nearest neighbors, K-means is an unsupervised algorithm for clustering finding cluster centroids.

How It Works

1. Choose the number K of clusters

2. Initialize K centroids randomly

3. Repeat until convergence:

   • Assign each data point to the nearest centroid
   • Update the centroids by calculating the mean of all points assigned to that centroid
     The algorithm has converged when the assignments no longer change

4. Initialization: ${\mu }_1,{\mu }_2,...,{\mu }_K\in {\mathbb{R}}^n$

5. Assignment Step: $c^{(i)}:=\arg {\min }_j||x^{(i)}-{\mu }_j|{|}^2$

6. Update Step: ${\mu }_j:=\frac{{\sum }_{i=1}^{m}1c^{(i)}=j{x}^{(i)}}{{\sum }_{i=1}^{m}1c^{(i)}=j}$

Where:

• ${\mu }_j$ is the centroid for cluster j
• $c^{(i)}$ is the cluster assignment for data point i
• $x^{(i)}$ is the i-th data point

Distance Metrics

Typically uses Euclidean distance: $d(x,y)=\sqrt{{\sum }_{i=1}^n(x_i-y_i{)}^2}$

Choosing K

1. Elbow Method: Plot the within-cluster sum of squares (WCSS) against K and look for the “elbow”
2. Silhouette Analysis: Measure how similar an object is to its own cluster compared to other clusters
3. Gap Statistic: Compare the total within intra-cluster variation for different values of k with their expected values under null reference distribution of the data

Advantages

1. Simple
2. Scales well to large datasets
3. Guarantees convergence
4. Can warm-start with known centroids if available

Disadvantages

1. Needs to specify K beforehand
2. Sensitive to initial centroid placement
3. Sensitive to outliers

Variations

K-means++

K-means++ helps the convergence by improving initialization. It selects initial cluster centroids using sampling based on an empirical probability distribution of the points’ contribution to the overall inertia.

Mini-batch K-means (K-means with buckets)

Instead of using the entire dataset in each iteration, Mini-Batch K-means uses small, random batches of data. The process repeats until convergence or a maximum number of iterations is reached.

Code example

> import numpy as np
 
class KMeans:
    def __init__(self, k=3, max_iters=100):
        self.k = k
        self.max_iters = max_iters
 
    def kmeans_plus_plus(self, X):
        centroids = [X[np.random.randint(X.shape[0])]]
        for _ in range(1, self.k):
            distances = np.min([np.sum((X - c) ** 2, axis=1) for c in centroids], axis=0)
            probabilities = distances / distances.sum()
            cumulative_probabilities = probabilities.cumsum()
            r = np.random.rand()
            for j, p in enumerate(cumulative_probabilities):
                if r < p:
                    centroids.append(X[j])
                    break
        return np.array(centroids)
 
    def fit(self, X):
        # Randomly initialize centroids
        self.centroids = X[np.random.choice(X.shape[0], self.k, replace=False)]
        # Or use K-means++ initialization
        self.centroids = self.kmeans_plus_plus(X)
 
        for _ in range(self.max_iters):
            # Assign points to closest centroid
            distances = np.sqrt(((X - self.centroids[:, np.newaxis])**2).sum(axis=2))
            labels = np.argmin(distances, axis=0)
 
            # Update centroids
            new_centroids = np.array([X[labels == i].mean(axis=0) for i in range(self.k)])
 
            # Check for convergence
            if np.all(self.centroids == new_centroids):
                break
 
            self.centroids = new_centroids
 
        return labels
 
    def predict(self, X):
        distances = np.sqrt(((X - self.centroids[:, np.newaxis])**2).sum(axis=2))
        return np.argmin(distances, axis=0)

Links

• Stanford lecture-