Standard k-means++

Overview

Standard k-means++ is the classic k-means initialization algorithm that carefully seeds cluster centers using D² sampling to achieve an \(O(\\log k)\) approximation to the optimal k-means clustering.

When to use:

  • Small to medium datasets (n < 10,000)

  • When you need the baseline/reference implementation

  • When theoretical guarantees are critical

  • For comparison with faster approximations

Key advantages:

✅ Proven \(O(\\log k)\) approximation guarantee

✅ Simple and well-understood

✅ No hyperparameters to tune

✅ Baseline for comparing other algorithms

Python API

kmeans_seeding.kmeanspp(X, n_clusters, *, random_state=None)[source]

Standard k-means++ initialization using D² sampling.

Parameters:

  • X (array-like of shape (n_samples, n_features)) – Training data

  • n_clusters (int) – Number of clusters

  • random_state (int, optional) – Random seed for reproducibility

Returns:

Initial cluster centers

Return type:

ndarray of shape (n_clusters, n_features)

Examples:

from kmeans_seeding import kmeanspp
import numpy as np

X = np.random.randn(1000, 20)
centers = kmeanspp(X, n_clusters=10, random_state=42)

With scikit-learn:

from kmeans_seeding import kmeanspp
from sklearn.cluster import KMeans

centers = kmeanspp(X, n_clusters=10)
kmeans = KMeans(n_clusters=10, init=centers, n_init=1)
labels = kmeans.fit_predict(X)

Algorithm

D² Sampling

The algorithm selects k centers sequentially:

  1. Choose first center uniformly at random

  2. For each subsequent center:

    1. Compute D²(x) = squared distance to nearest selected center

    2. Sample new center with probability ∝ D²(x)

    3. Add to selected centers

Time complexity: \(O(nkd)\) for n points, k centers, d dimensions

Space complexity: \(O(nd)\) for storing data

Approximation: \(\\mathbb{E}[\\Phi] \\leq O(\\log k) \\cdot \\Phi_k(X)\)

Advantages

  1. Strong theoretical guarantees: Proven \(O(\\log k)\) approximation

  2. No hyperparameters: Works out of the box

  3. Deterministic quality: Given seed, always same quality

  4. Simple implementation: Easy to understand and verify

Limitations

  1. Slow for large data: \(O(nkd)\) becomes prohibitive

  2. Sequential: Can’t easily parallelize center selection

  3. No approximation: Must compute all distances exactly

When to Use Alternatives

Use faster alternatives when:

  • n > 10,000: RS-k-means++ or AFK-MC² are much faster

  • k > 100: Fast-LSH scales better with many clusters

  • d > 100: Fast-LSH optimized for high dimensions

  • Need speed: Any fast algorithm is 10-100× faster

Recommendation: Use standard k-means++ for: - Small datasets - Establishing baselines - When simplicity matters - Academic/research comparisons

See Also