Clustering Theory: K-Means, DBSCAN, and Spectral

Module: Machine Learning | Difficulty: Advanced

K-Means Objective

Lloyd's Algorithm

1. Initialize centroids
2. Assign:
3. Update:

Convergence: iterations in practice.

DBSCAN

• Core point:
• Border point: in -neighborhood of core point
• Noise: neither core nor border

Spectral Clustering

Eigenvectors of provide a low-dimensional embedding for clustering.

import numpy as np
from scipy.spatial.distance import cdist

class KMeans:
    def __init__(self, k=3, max_iter=100):
        self.k = k; self.max_iter = max_iter
    def fit(self, X):
        idx = np.random.choice(len(X), self.k, replace=False)
        self.centroids = X[idx].copy()
        for _ in range(self.max_iter):
            dists = cdist(X, self.centroids)
            labels = dists.argmin(axis=1)
            new_centroids = np.array([X[labels==k].mean(0) if (labels==k).any() else self.centroids[k] for k in range(self.k)])
            if np.allclose(self.centroids, new_centroids): break
            self.centroids = new_centroids
    def predict(self, X):
        return cdist(X, self.centroids).argmin(axis=1)

Research Insight: K-means converges to a local minimum of the K-means objective. The quality depends heavily on initialization. K-means++ provably achieves an approximation to the optimal clustering.