What is the mathematical objective function K-Means optimises, and why can it converge to a local minimum?

K-Means seeks to partition n points into k clusters by minimising the within-cluster sum of squares (WCSS), also called inertia: J = Σₖ Σ_{x ∈ Cₖ} ‖x - μₖ‖², where μₖ is the centroid (mean) of cluster k. This is a non-convex combinatorial optimisation problem — finding the global optimum requires checking every possible partition of n points into k groups, which is computationally infeasible (NP-hard) for any realistic dataset size.

Lloyd's algorithm (the standard K-Means algorithm) solves this approximately through alternating optimisation: (1) assign each point to its nearest centroid, (2) recompute each centroid as the mean of its assigned points, repeat until convergence. Each step is guaranteed to never increase J, so the algorithm converges — but only to a local minimum that depends heavily on the random initial centroid positions.

from sklearn.cluster import KMeans
import numpy as np

# k-means++ initialization (default) spreads initial centroids apart
# to reduce the chance of poor local minima — much better than random init
km = KMeans(n_clusters=3, init='k-means++', n_init=10, random_state=42)
km.fit(X)

print('Inertia (WCSS):', km.inertia_)
print('Cluster centers:', km.cluster_centers_)

# n_init=10 runs the algorithm 10 times with different initializations
# and keeps the result with lowest inertia — mitigates local minima

# Elbow method to choose k: plot inertia vs k, look for the 'elbow'
inertias = []
for k in range(1, 10):
    km = KMeans(n_clusters=k, n_init=10, random_state=42).fit(X)
    inertias.append(km.inertia_)
# inertia always decreases with more clusters — look for diminishing returns

Invest now in Acorns!!! 🚀
Join Acorns and get your $5 bonus!

Acorns is a micro-investing app that automatically invests your "spare change" from daily purchases into diversified, expert-built portfolios of ETFs. It is designed for beginners, allowing you to start investing with as little as $5. The service automates saving and investing. Disclosure: I may receive a referral bonus.

Invest now!!! Get Free equity stock (US, UK only)!

Use Robinhood app to invest in stocks. It is safe and secure. Use the Referral link to claim your free stock when you sign up!.

The Robinhood app makes it easy to trade stocks, crypto and more.

Webull! Receive free stock by signing up using the link: Webull signup.