K-means

K-Means is an unsupervised machine learning algorithm that partitions a dataset into K non-overlapping clusters by minimizing the total squared distance between each data point and its assigned cluster centroid. This page explains how the algorithm works, how to implement it in Python with scikit-learn, how to choose the right number of clusters, and the key pitfalls to avoid.

What is K-Means Clustering?

K-Means groups data points so that points within the same cluster are as similar as possible, while points in different clusters are as different as possible. "Similar" is measured by Euclidean distance — the straight-line distance between two points in feature space.

Because K-Means works with raw distance values, it is an unsupervised algorithm: it discovers structure in unlabeled data without needing a target variable.

Common real-world applications include:

• Customer segmentation — group customers by spending habits and demographics.
• Image compression — reduce colors by replacing each pixel with the color of its nearest centroid.
• Document clustering — group news articles or support tickets by topic.
• Anomaly detection — points far from every centroid may be outliers.

How the Algorithm Works

K-Means alternates between two steps until the cluster assignments stop changing (convergence):

1. Initialize — choose K initial centroids (starting points). The default k-means++ strategy spaces them apart to reduce bad initializations.
2. Assign — assign every data point to the nearest centroid, forming K clusters.
3. Update — recalculate each centroid as the mean of all points assigned to it.
4. Repeat steps 2–3 until no point changes cluster, or a maximum number of iterations is reached.

The quantity being minimized is called inertia (also written WCSS — within-cluster sum of squares):

inertia = sum over all points of (distance from point to its centroid)²

Lower inertia means tighter, more compact clusters.

k-means++ initialization

The default init='k-means++' (scikit-learn's default) selects the first centroid randomly, then picks each subsequent centroid with probability proportional to its squared distance from the nearest already-chosen centroid. This spreads the initial centroids apart and typically finds better clusters faster than pure random initialization.

Feature Scaling Before Clustering

K-Means relies entirely on Euclidean distance. If one feature is measured in thousands (for example, annual income) and another in single digits (for example, a rating from 1 to 5), the large-valued feature dominates the distance calculation and the smaller feature is effectively ignored. Always scale your features first.

from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

StandardScaler centers each feature to mean 0 and standard deviation 1. See the Scale chapter for alternatives such as MinMaxScaler.

Implementing K-Means with scikit-learn

The following example generates a synthetic dataset, scales it, fits K-Means, and inspects the results.

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
import numpy as np

# Generate 300 points in 3 natural clusters
X, y_true = make_blobs(n_samples=300, centers=3, random_state=42)

# Scale the features — always required before K-Means
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# Fit K-Means with 3 clusters
kmeans = KMeans(n_clusters=3, init='k-means++', n_init=10, random_state=42)
kmeans.fit(X_scaled)

# Cluster assignment for every training point (0-indexed)
labels = kmeans.labels_
print('Cluster labels (first 10):', labels[:10])
# e.g. [2 2 0 1 0 1 2 2 0 1]

print('Cluster sizes:', np.bincount(labels))
# e.g. [100 100 100]

print('Inertia (WCSS):', round(kmeans.inertia_, 2))
# e.g. 18.26

print('Iterations to converge:', kmeans.n_iter_)
# e.g. 2

Key attributes after fitting:

Predicting cluster membership for new data

After fitting the scaler and the model on training data, use scaler.transform() + kmeans.predict() to assign new points to existing clusters. Never refit the scaler on new data.

import numpy as np

# Two new, unseen points (original feature scale)
new_points = np.array([[0.5, -0.5],
                        [-1.0,  2.0]])

# Transform with the SAME scaler used during training
new_scaled = scaler.transform(new_points)

# Predict cluster membership
predictions = kmeans.predict(new_scaled)
print('Predicted clusters:', predictions)
# e.g. [2 0]

Choosing the Right Number of Clusters (K)

K-Means requires you to specify K upfront, which is often the hardest part. Two complementary techniques help: the Elbow method and the Silhouette score.

The Elbow method

Plot inertia (WCSS) against K. As K grows, inertia always decreases — but the rate of improvement slows. The "elbow" is the point where adding another cluster yields diminishing returns.

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
import matplotlib.pyplot as plt

X, _ = make_blobs(n_samples=300, centers=3, random_state=42)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

wcss = []
for k in range(1, 11):
    km = KMeans(n_clusters=k, n_init=10, random_state=42)
    km.fit(X_scaled)
    wcss.append(km.inertia_)

plt.plot(range(1, 11), wcss, marker='o')
plt.xlabel('Number of clusters (K)')
plt.ylabel('Inertia (WCSS)')
plt.title('Elbow method')
plt.tight_layout()
plt.show()

On this dataset (3 natural clusters), inertia drops steeply from K=1 to K=3, then levels off. The elbow at K=3 confirms the true number of clusters.

The Silhouette score

The silhouette score measures how well each point fits into its own cluster compared to the nearest neighboring cluster. It ranges from -1 (wrong cluster) to +1 (perfectly separated cluster). A score above 0.5 is generally good; above 0.7 is strong.

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score

X, _ = make_blobs(n_samples=300, centers=3, random_state=42)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

for k in range(2, 8):
    km = KMeans(n_clusters=k, n_init=10, random_state=42)
    labels = km.fit_predict(X_scaled)
    score = silhouette_score(X_scaled, labels)
    print(f'k={k}  silhouette={score:.3f}')

Output:

k=2  silhouette=0.688
k=3  silhouette=0.848
k=4  silhouette=0.679
k=5  silhouette=0.522
k=6  silhouette=0.357
k=7  silhouette=0.371

K=3 produces the highest silhouette score (0.848), confirming that three clusters best describe this data. Use both methods together — the Elbow plot tells you where improvement stalls; the Silhouette score gives a single number to compare across values of K.

Visualizing K-Means Clusters

Scatter plots reveal whether the clusters are well-separated. For datasets with more than two features, you would first apply dimensionality reduction (such as PCA) before plotting.

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
import matplotlib.pyplot as plt

X, _ = make_blobs(n_samples=300, centers=3, random_state=42)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

kmeans = KMeans(n_clusters=3, n_init=10, random_state=42)
labels = kmeans.fit_predict(X_scaled)
centers = kmeans.cluster_centers_

plt.scatter(X_scaled[:, 0], X_scaled[:, 1], c=labels, cmap='viridis', s=40, alpha=0.7)
plt.scatter(centers[:, 0], centers[:, 1],
            c='red', marker='X', s=200, zorder=5, label='Centroids')
plt.legend()
plt.title('K-Means clustering (k=3)')
plt.xlabel('Feature 1 (scaled)')
plt.ylabel('Feature 2 (scaled)')
plt.tight_layout()
plt.show()

Each color represents one cluster. Red crosses mark the centroids — the average position of all points in that cluster.

Advantages and Limitations

Advantages

• Simple and fast. K-Means is O(n · k · i) where n is the number of points, k is the number of clusters, and i is the number of iterations. It scales to millions of data points with MiniBatchKMeans.
• Easy to interpret. Centroids give a concrete summary of each cluster's typical values.
• Works well when clusters are roughly spherical and equally sized.
• No labeled data required. Fully unsupervised — no target variable needed.

Limitations

• K must be specified upfront. Use the Elbow method and Silhouette score to guide the choice, but neither gives a definitive answer for ambiguous data.
• Sensitive to initialization. A bad starting configuration can converge to a local optimum. k-means++ and multiple restarts (n_init=10) reduce this risk.
• Assumes spherical, equally sized clusters. K-Means struggles with elongated, crescent-shaped, or very unequal clusters. Use Hierarchical Clustering or DBSCAN for non-globular shapes.
• Sensitive to outliers. A single extreme point can pull a centroid far from the true cluster center. Remove or cap outliers before fitting.
• Scale-sensitive. Features on different scales must be standardized — see the Scale chapter.

Common Pitfalls

Skipping feature scaling. This is the single most common mistake. Without scaling, features with large numeric ranges dominate the distance calculation and smaller-range features are ignored.

Setting n_init=1. The default in older scikit-learn versions was n_init='warn' (which warned if you did not set it). Always set n_init=10 (or more) to run K-Means with 10 different random initializations and keep the best result.

Refitting the scaler on new data. Fit the StandardScaler once on your training data, then call transform() on any new data. Calling fit_transform() again on new data changes the scale and makes the model inconsistent.

Treating cluster IDs as meaningful order. The cluster IDs (0, 1, 2, …) are arbitrary labels assigned by scikit-learn. They are not ordinal — cluster 2 is not "larger" or "more important" than cluster 0. Compare clusters by their centroid values and member counts.

Using K-Means on non-numeric data. K-Means requires numeric features to compute distances. For categorical data, encode it first (for example with one-hot encoding) and consider whether Euclidean distance still makes sense for your use case. See the Categorical Data chapter.

K-Means vs Hierarchical Clustering

Use K-Means when your dataset is large and you already have a good estimate of K. Use Hierarchical Clustering when you want to explore several values of K without refitting, or when clusters may not be spherical.

Practical Checklist

Follow this checklist when applying K-Means to a new dataset:

1. Remove or cap outliers — extreme values distort centroids.
2. Encode categorical variables — K-Means requires numeric input.
3. Scale features with StandardScaler (or MinMaxScaler if the feature distribution is bounded).
4. Use the Elbow plot to narrow down candidate values of K.
5. Use the Silhouette score to compare specific K values quantitatively.
6. Set n_init=10 and init='k-means++' for robust initialization.
7. Inspect cluster sizes with np.bincount(labels) — very unequal sizes may indicate a poor K or outlier contamination.
8. Visualize with a scatter plot (or PCA projection for high-dimensional data).

Related Chapters

• Scale — standardizing features before clustering
• Hierarchical Clustering — an alternative that does not require K upfront
• K-Nearest Neighbors — a supervised method that also uses distance
• Decision Tree — supervised classification without distance assumptions
• Train / Test Split — evaluating machine learning models
• Scatter Plot — visualizing clusters with Matplotlib