Skip to content
Machine Learning & Data Science

K-Means Clustering interview questions and answers

50 questions, 28 with code. About 5 h 33 min to read them all.

By TestLab · Updated

Plan for an interview
50 questions

Track what you know and what to revise.

Sign in to track progress

You can open a few full answers without signing in. Sign in to read all

1

Why use K-Means clustering for unsupervised grouping?

K-Means clustering is useful when you want a simple, scalable way to partition unlabeled numerical data into groups around representative centroids. It supports tasks such as customer segmentation, vector or image compression, and exploratory grouping, with the main trade-off being its simplicity and speed versus sensitivity to initialization, outliers, feature scaling, cluster geometry, and the need to choose k.

Read full answer

Applies toK-Means concepts and scikit-learn 1.5+ (Python 3.12)

Why K-Means Can Be Useful

  • Fast grouping: It efficiently partitions large numerical datasets into a specified number of clusters.

  • Interpretable representatives: Each cluster is summarized by its centroid, making broad cluster profiles easy to inspect.

  • Useful preprocessing: Cluster assignments can support segmentation, grouping, compression, or initialization in other models.

  • Simple objective: It directly minimizes within-cluster variation, measured by inertia.

K-Means is most appropriate when features are numerical, clusters are expected to be roughly compact and similar in size, and approximate rather than mathematically perfect groupings are acceptable.

How It Works

K-Means is an unsupervised learning algorithm. Given n observations, it creates k hard, non-overlapping assignments and represents each cluster by its mean vector, or centroid.

Its objective is the within-cluster sum of squares, also called inertia:

WCSS = sum(i = 1..k) sum(x in C_i) ||x - mu_i||^2

  • WCSS: total squared distance of observations from their assigned centroids.

  • k: number of clusters.

  • i: cluster index from 1 through k.

  • C_i: observations assigned to cluster i.

  • x: an observation belonging to C_i.

  • mu_i: mean vector of the observations in cluster i.

  • ||x - mu_i||^2: squared Euclidean distance between the observation and its centroid.

Lloyd’s algorithm proceeds as follows:

  1. Initialize centroids: Select k starting centroids.

  2. Assign observations: Assign each point to its nearest centroid using Euclidean distance.

  3. Recompute centroids: Replace each centroid with the mean of its assigned observations.

  4. Repeat: Continue until assignments stabilize or centroid movement falls below the implementation’s tolerance.

Each iteration cannot increase the objective, so the algorithm converges. It normally reaches a local optimum, however, meaning another initialization could produce lower overall inertia.

Initialization and Selecting k

  • k-means++: Scikit-learn’s default initialization selects the first center randomly and chooses later centers with higher probability where existing squared distances are large.

  • n_init: Controls the number of independent initializations and retains the run with the lowest inertia. In scikit-learn 1.5+, n_init="auto" uses 10 runs for init="k-means++" and one run for init="random".

  • Elbow method: Plot inertia against several values of k and look for a point where improvements begin to level off. It is a heuristic, not an exact selection method.

  • Silhouette score: Compares each point’s distance to its own cluster with its distance to neighboring clusters. Higher values generally indicate better-separated clusters.

Cluster stability, domain knowledge, interpretability, and downstream usefulness should also influence the selected k.

Complexity and Alternatives

A Lloyd iteration costs approximately O(n * k * d), where d is the number of features. Across T iterations, the approximate total is O(T * n * k * d). Storing the input requires O(n * d) memory; a basic implementation may also store an O(n * k) distance or assignment matrix, although chunked implementations reduce that auxiliary requirement. MiniBatchKMeans is useful for very large datasets because it updates centroids from smaller batches.

Method How it works Strengths Weaknesses Suitable use
K-Means Assigns points to nearest mean Fast and scalable Assumes compact, similar-sized clusters General-purpose numerical grouping
K-Medoids Uses actual observations as centers More resistant to outliers than means Usually slower; needs a suitable dissimilarity Outlier-prone data; mixed data with an appropriate dissimilarity
Gaussian Mixture Model Models clusters as probability distributions Supports soft assignments More parameters and computation Overlapping or elliptical clusters
DBSCAN/HDBSCAN Groups points by density Finds irregular shapes and noise Requires density-related parameter choices Irregular clusters and outliers

Practical Guidance

  • Scale features: K-Means uses Euclidean distance, so large-scale or high-variance features can dominate.

  • Handle missing values: Impute them before clustering because K-Means does not accept NaNs directly.

  • Inspect outliers: Extreme observations can pull centroids substantially.

  • Avoid raw categorical data: Use k-modes or another method with a suitable distance.

  • Set a random seed: Initialization is stochastic, so reproducibility requires a fixed seed.

  • Profile the results: Examine feature distributions, stability, and business usefulness rather than assuming every cluster is meaningful.

  • Consider hardware: Standard K-Means is primarily CPU-oriented; MiniBatchKMeans can reduce processing requirements on large datasets.

Common Pitfalls

  • Not scaling features: Variables with larger numeric ranges dominate the distance calculation.

  • Choosing k from inertia alone: More clusters cannot increase minimum WCSS, but they may only produce small improvements or no improvement.

  • Treating the elbow as exact: The elbow may be subtle or absent.

  • Ignoring local optima: Compare several restarts or use k-means++.

  • Interpreting clusters prematurely: Examine cluster profiles, stability, and downstream usefulness.

  • Using inappropriate data: K-Means is poorly suited to raw categorical data, severe outliers, or strongly non-spherical groups.

Common interview follow-ups include why k-means++ is used, how n_init affects stability, why scaling matters, how to select k, and how K-Means differs from DBSCAN or a Gaussian Mixture Model.

2

How do supervised and unsupervised learning differ, and where does K-Means fit?

Supervised learning learns a mapping from labeled examples to known targets, while unsupervised learning discovers structure in unlabeled data. K-Means is an unsupervised clustering algorithm that groups similar observations without target labels; its main trade-off is low annotation cost in exchange for sensitivity to initialization, feature scaling, outliers, and the need to choose k.

Read full answer

Applies tomachine learning concepts and scikit-learn 1.5+ (Python 3.12)

Core Differences

Aspect Supervised Learning Unsupervised Learning
Training data Includes known target labels Usually excludes target labels
Objective Predict a target Discover groups, patterns, or representations
Typical evaluation Accuracy, F1, ROC-AUC, PR-AUC, RMSE, or R² Inertia, silhouette score, stability, and practical usefulness
Examples Spam classification and house-price prediction Customer segmentation and document grouping
Main challenge Obtaining reliable labels and preventing leakage Interpreting patterns and choosing suitable assumptions

Accuracy can be misleading for imbalanced classification because a model that always predicts the majority class may achieve a high score without identifying minority cases.

Where K-Means Fits

K-Means is appropriate when observations have meaningful numerical features, no target label is required, and clusters are expected to be compact, roughly spherical, and not extremely unequal in size. For example, a retailer could cluster customers using purchasing frequency and average order value, then profile the resulting segments before using them for marketing.

It is generally unsuitable for raw categorical data, strongly irregular clusters, or data heavily affected by outliers.

How K-Means Works

K-Means partitions n observations into k clusters using Lloyd’s algorithm:

  1. Initialize k centroids.

  2. Assign each point to its nearest centroid using Euclidean distance.

  3. Recalculate each centroid as the mean of its assigned points.

  4. Repeat the assignment and recalculation steps until assignments stop changing or another stopping condition is reached.

Its objective is the within-cluster sum of squares:

inertia = sum from i = 1 to n of ||x_i - c_i||²

Here, n is the number of observations, x_i is the feature vector for observation i, c_i is the centroid of the cluster assigned to that observation, and ||x_i - c_i|| is their Euclidean distance. Squaring and summing these distances makes larger assignment errors contribute more heavily. Lower inertia means a smaller total squared distance, but Lloyd’s algorithm guarantees convergence to a local optimum rather than the global optimum.

Initialization, Convergence, and Complexity

  • k-means++ initialization: This is scikit-learn’s default. It chooses initial centroids that are more likely to be separated, reducing the risk of a poor local optimum.

  • Restarts with n_init: Setting n_init=10, for example, runs ten initializations and retains the result with the lowest inertia. In scikit-learn 1.5+, n_init="auto" uses one run with the default init="k-means++".

  • Stopping behavior: max_iter limits the number of iterations, while scikit-learn’s tolerance stops refinement when centroid movement becomes sufficiently small.

  • Complexity: Each iteration costs O(n * k * d), where d is the number of features; for T iterations, the approximate total is O(T * n * k * d).

  • Large datasets: MiniBatchKMeans reduces per-iteration computation by updating the model with subsets of observations, at the cost of potentially less stable results.

Choosing k and Alternatives

The elbow method examines how inertia changes across several values of k; because inertia cannot increase when k increases, the useful signal is where improvements diminish. The silhouette score compares each observation’s distance to its assigned centroid with its average distance to neighboring clusters. Neither metric gives an exact answer, so domain knowledge remains important.

Algorithm How It Works Strengths Weaknesses When to Use Typical Complexity or Scale
K-Means Assigns points to nearest means Fast and simple Sensitive to scaling, outliers, initialization, and cluster shape Compact, roughly spherical clusters O(T * n * k * d)
k-medoids Uses actual observations as centers More robust to outliers Typically slower to fit Small or medium datasets with outliers PAM initialization commonly requires O(n²) distance work
Gaussian Mixture Model Models clusters as probability distributions Soft assignments and elliptical clusters More computationally expensive Overlapping or elliptical clusters Roughly O(n * k * d) to O(n * k * d²) per iteration, depending on covariance
DBSCAN/HDBSCAN Finds density-connected regions Detects irregular clusters and outliers; no k required Density and dimensionality can be difficult; HDBSCAN uses more memory Irregular clusters and noise Dataset-dependent; spatial indexing can approach O(n log n), while worst-case neighbor searches can reach O(n²)

Common Pitfalls

  • Not scaling features: Larger numeric ranges dominate Euclidean distance; use StandardScaler or MinMaxScaler when scales differ.

  • Choosing k mechanically: Treat the elbow and silhouette score as evidence, then profile clusters and assess their usefulness.

  • Assuming spherical clusters: K-Means performs poorly on elongated, highly irregular, or extremely unequal groups.

  • Ignoring outliers: Extreme values can pull centroids away from the main data distribution.

  • Using categorical features directly: Use k-modes or an appropriate encoding and interpretation strategy.

  • Fitting preprocessing on all data: Fit scalers, encoders, and imputers only on training data, such as within a scikit-learn Pipeline.

  • Ignoring missing values: K-Means does not accept NaNs, so impute them without leaking information from validation or test data.

  • Overinterpreting clusters: A statistical grouping is not automatically a meaningful business or behavioral category.

3

What are centroids in K-Means clustering?

A centroid is the arithmetic mean of all data points assigned to a cluster, so it represents that cluster’s center in feature space. K-Means moves each centroid toward the mean of its assigned points, minimizing the within-cluster sum of squares (inertia). The main trade-off is that K-Means is simple and fast, but its result depends on initialization and the assumption that clusters are roughly compact and similarly sized.

Read full answer

Applies tomachine learning concepts; scikit-learn 1.5+ with Python 3.12

What a Centroid Represents

For cluster ©, its centroid is calculated as:

centroid © = (1 / number of points in cluster ©) × sum of those points

Here:

  • Cluster © means the group currently assigned to centroid ©.

  • Number of points is the number of observations in that group.

  • Sum of those points adds their values across all features.

  • Centroid is therefore one mean vector with the same number of features as the input data.

For example, if a cluster contains customers with ages 20, 24, and 30, its age centroid is (20 + 24 + 30) / 3 = 24.67. With multiple features, the centroid contains one mean per feature.

Centroids are not necessarily real observations. They can represent a synthetic “typical” customer, transaction, or measurement that does not exactly match any row in the dataset.

How Lloyd’s Algorithm Updates Centroids

Lloyd’s algorithm is the standard K-Means procedure:

  1. Initialize centroids: Select (k) starting positions, often using k-means++.

  2. Assign points: Give each observation to its nearest centroid, usually measured with Euclidean distance.

  3. Recompute centroids: Replace each centroid with the mean of the observations assigned to it.

  4. Repeat: Continue assigning and recomputing until the assignments stop changing or another stopping condition is reached.

The objective minimized is the inertia, also called the within-cluster sum of squares:

inertia = sum over all clusters of the sum of squared distances from each point to its cluster centroid

Every term in this formula measures how far observations are from their assigned centers. Lower inertia means the clusters are more internally compact, but inertia generally decreases as (k) increases, so it cannot be used alone to select the number of clusters.

Initialization and Local Optima

K-means++ is scikit-learn’s default initialization method. It chooses initial centroids that are relatively spread apart, using distance-based probabilities when selecting later centers. This generally reduces the chance of starting with several centroids in the same region.

The n_init parameter controls how many independent initializations are attempted. When set to a number greater than one, scikit-learn retains the run with the lowest inertia. In scikit-learn 1.5+, n_init="auto" means one run for init="k-means++" and multiple runs for init="random".

Because the objective is non-convex, K-Means converges to a local optimum, not necessarily the globally optimal partition. It is also sensitive to initialization, outliers, feature scaling, and the selected value of (k).

Computational Cost and Alternatives

Each full iteration costs approximately O(n × k × d), where:

  • (n) is the number of observations,

  • (k) is the number of clusters,

  • (d) is the number of features.

For large datasets, MiniBatchKMeans processes smaller batches and can reduce computation time, though it may produce less stable results.

Alternative How it works Main advantage Main limitation
K-Medoids Uses actual observations as cluster centers More robust to outliers More computationally expensive
Gaussian Mixture Model Models clusters as probability distributions Can represent elliptical clusters and overlapping membership Requires distributional assumptions
DBSCAN Groups points through density-connected regions Finds arbitrary-shaped clusters and noise Sensitive to density parameters
HDBSCAN Builds a hierarchy of density-based clusters Handles varying densities and noise More resource-intensive than DBSCAN

Common Pitfalls

  • Not scaling features: A feature measured in thousands can dominate distance calculations. Standardization is usually appropriate when features have substantially different units.

  • Choosing (k) arbitrarily: Use inertia, the elbow method, silhouette score, and domain knowledge together; the elbow is not an exact cutoff.

  • Ignoring outliers: Extreme values can pull centroids away from the main data distribution.

  • Using categorical variables directly: K-Means is designed for continuous numerical features; use k-modes or an appropriate encoding and distance measure for categorical data.

  • Overinterpreting clusters: Centroids describe mathematical groupings, not necessarily meaningful customer segments. Always profile cluster characteristics and validate them against the original objective.

4

What are the algorithmic steps of K-Means clustering?

K-means clustering partitions unlabeled numeric data into k groups by assigning observations to their nearest centroid and updating each centroid to the mean of its assigned points. It solves grouping and segmentation problems when labels are unknown; its main trade-offs are the need to choose k, sensitivity to scaling, outliers, and initialization, and convergence to a local rather than guaranteed global optimum.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

Lloyd’s Algorithm

K-means commonly uses Lloyd’s algorithm:

  1. Initialize centroids

  2. Choose the number of clusters, k.

  3. Initialize k centroids, usually with k-means++.

  4. Assign observations

  5. Calculate the squared Euclidean distance from each observation to each centroid.

  6. Assign the observation to its closest centroid.

  7. Recompute centroids

  8. Calculate the mean of the observations assigned to each cluster.

  9. Replace that cluster’s centroid with the mean.

  10. Repeat

  11. Repeat the assignment and centroid-update steps until assignments stabilize or the iteration limit is reached.

  12. In scikit-learn, convergence is detected when the centroids move by less than the configured tol; max_iter limits the number of updates.

The objective is the within-cluster sum of squares, also called inertia:

WCSS = sum over clusters c and assigned observations i of ||x_i - μ_c||²

Here, x_i is observation i’s feature vector, μ_c is the centroid of cluster c, and ||x_i - μ_c||² is its squared Euclidean distance from that centroid. Lloyd’s updates reduce this objective and normally converge to a local minimum.

Initialization and Convergence

  • k-means++ chooses the first centroid uniformly at random, then chooses later centroids with probability proportional to their squared distance from the closest already-selected centroid. This tends to produce better-separated initial centroids than uniform random selection, although it does not guarantee a global optimum.

  • k-means++ is the default initializer in scikit-learn 1.5+.

  • n_init controls how many initializations are run; scikit-learn retains the run with the lowest inertia. With n_init="auto", the default is one run for k-means++ and ten runs for random initialization.

  • Because the objective is non-convex, different initializations can produce different local optima. Multiple restarts reduce this risk.

Complexity and Practical Considerations

For n observations, k clusters, d features, and T iterations:

  • Time per iteration is approximately O(n × k × d); total time is approximately O(T × n × k × d).

  • Storing the data and centroids requires approximately O(n × d + k × d) memory.

  • MiniBatchKMeans is useful for large datasets because it updates centroids from small batches instead of the entire dataset on every iteration.

Issue Practical guidance
Feature scale Standardize or normalize features so large-range variables do not dominate Euclidean distance.
Missing values Remove or impute missing values before fitting; KMeans does not accept NaN values.
Outliers and geometry K-means is sensitive to outliers and works best for roughly spherical, similarly sized clusters.
Categorical data Use k-modes rather than treating category codes as meaningful distances.
Unknown k Compare inertia, cross-validated silhouette scores, cluster stability, and domain knowledge; do not treat an elbow as an exact answer.
Interpretation Profile each cluster’s features; cluster IDs are identifiers, not ordered or inherently meaningful categories.

Alternatives include k-medoids for robust cluster centers, Gaussian mixture models for probabilistic elliptical clusters, and DBSCAN or HDBSCAN for irregular clusters and noise.

Code Example

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.model_selection import KFold, cross_val_score, train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler


# Generate reproducible synthetic data with three underlying groups.
X, _ = make_blobs(
    n_samples=500,
    centers=3,
    cluster_std=1.0,
    random_state=42,
)

# Reserve the test set for one final evaluation.
X_train, X_test = train_test_split(
    X,
    test_size=0.30,
    random_state=42,
)


def scaled_silhouette(estimator, X, y=None):
    """Compute silhouette in the feature space used by KMeans."""
    labels = estimator.predict(X)
    X_scaled = estimator.named_steps["scaler"].transform(X)
    return silhouette_score(X_scaled, labels)


cv = KFold(n_splits=5, shuffle=True, random_state=42)
best_k = 2
best_score = -np.inf

print("k | training inertia | CV silhouette")
for k in range(2, 7):
    pipeline = Pipeline([
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=k,
            init="k-means++",
            n_init=10,
            random_state=42,
        )),
    ])

    scores = cross_val_score(
        pipeline,
        X_train,
        cv=cv,
        scoring=scaled_silhouette,
    )
    mean_score = float(scores.mean())

    # Fit on all training data to report training inertia for the elbow.
    pipeline.fit(X_train)
    inertia = pipeline.named_steps["kmeans"].inertia_
    print(f"{k} | {inertia:.2f} | {mean_score:.3f}")

    if mean_score > best_score:
        best_k = k
        best_score = mean_score

# Fit the selected model, then evaluate it once on the untouched test set.
final_model = Pipeline([
    ("scaler", StandardScaler()),
    ("kmeans", KMeans(
        n_clusters=best_k,
        init="k-means++",
        n_init=10,
        random_state=42,
    )),
])
final_model.fit(X_train)

test_labels = final_model.predict(X_test)
X_test_scaled = final_model.named_steps["scaler"].transform(X_test)
test_silhouette = silhouette_score(X_test_scaled, test_labels)
cluster_sizes = np.bincount(test_labels, minlength=best_k)

print("Selected k:", best_k)
print("Held-out cluster sizes:", cluster_sizes)
print("Held-out silhouette:", round(test_silhouette, 3))

Inertia generally decreases as k increases, so it cannot independently identify the correct number of clusters. Cross-validated silhouette scores, stability checks, and domain knowledge provide complementary evidence.

Common Pitfalls

  • Not scaling features: Large-range variables can dominate the distance calculations.

  • Data leakage: Fit preprocessing only on training folds and reserve the test set for final evaluation.

  • Choosing k only from inertia: More clusters almost always reduce inertia, so use several indicators.

  • Ignoring outliers or cluster shape: K-means can split elongated groups incorrectly and can be pulled away by extreme values.

  • Interpreting labels literally: Profile clusters before assigning them business meaning; their numeric IDs are arbitrary.

5

Which distances are valid for K-Means clustering?

Distance metrics determine which centroid is closest to each data point, and therefore define the clusters produced by K-Means. Standard K-Means uses squared Euclidean distance to minimize the within-cluster sum of squares. Its main trade-off is efficiency and simplicity versus sensitivity to feature scaling, outliers, and non-spherical cluster shapes.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12, NumPy 2.x)

How Distance Metrics Affect K-Means

K-Means follows Lloyd’s algorithm:

  1. Initialize k centroids, commonly using k-means++.

  2. Assign every point to its nearest centroid according to the chosen distance.

  3. Recalculate each centroid as the arithmetic mean of its assigned points.

  4. Repeat until assignments stop changing or another stopping condition is reached.

The standard objective is:

inertia = sum of ||x_i - μ_c||² over all points

In this formula, x_i is data point i, μ_c is its assigned centroid, ||x_i - μ_c||² is squared Euclidean distance, and inertia is the total within-cluster sum of squares.

Because minimizing squared Euclidean distance produces mean-based centroids, ordinary Euclidean distance and squared Euclidean distance produce the same assignments; only the calculation differs.

Supported and Alternative Distances

Distance Appropriate use Important limitation
Squared Euclidean Standard K-Means and scikit-learn’s KMeans Sensitive to scale, outliers, and elongated clusters
Euclidean Standard K-Means assignment Gives identical assignments to squared Euclidean distance
Manhattan Custom Manhattan K-Means or median-based clustering Mean updates do not properly optimize Manhattan distance; K-Medoids is usually preferable
Cosine Clustering by direction rather than magnitude Magnitudes are largely ignored; usually implemented as spherical K-Means
Minkowski Custom generalized-distance K-Means Requires a corresponding objective and update rule

scikit-learn’s KMeans does not provide a metric parameter for selecting Manhattan or cosine distance. Its algorithm parameter selects an implementation such as "lloyd" or "elkan", not a different distance metric.

Initialization, Convergence, and Complexity

  • k-means++: The default initialization in scikit-learn. It selects initial centroids with a probability related to their squared distance from previously selected centroids, reducing the likelihood of a poor starting configuration.

  • n_init: Controls how many initializations are attempted. For example, n_init=10 runs ten restarts and keeps the solution with the lowest inertia.

  • Local optimum: K-Means is not guaranteed to find the global minimum. Different initial centroids can produce different final clusters.

  • Complexity: Each iteration is approximately O(n * k * d), where n is the number of points, k the number of clusters, and d the number of features.

  • Large datasets: MiniBatchKMeans processes subsets of observations per iteration and is substantially faster, at the cost of potentially less stable assignments.

Practical Guidance

  • Scale features: Standardization or min-max scaling is usually necessary because distance-based assignment is dominated by features with larger numeric ranges.

  • Handle missing values: scikit-learn’s KMeans does not accept NaN; impute them within the training pipeline.

  • Choose k carefully: Compare the elbow in inertia with silhouette scores and domain knowledge. The elbow is a visual guide, not an exact rule.

  • Avoid unsupported data: K-Means is intended for numerical data. Use K-Modes or another method for categorical features.

  • Profile clusters: Examine feature distributions within each cluster before assigning an interpretation.

  • Consider alternatives: Use K-Medoids for Manhattan-like robustness, Gaussian mixture models for elliptical or probabilistic clusters, and DBSCAN or HDBSCAN for irregular shapes and noise.

Common Pitfalls

  • Using unscaled features, which changes the effective weighting of distance dimensions.

  • Choosing k solely from the elbow and ignoring validation metrics.

  • Treating a local optimum as the globally optimal clustering.

  • Assuming spherical, similarly sized clusters; K-Means performs poorly on elongated or unequal clusters.

  • Interpreting cluster identifiers as labels or causal groups.

  • Evaluating repeatedly against the test set, which introduces data leakage.

6

How do you choose k for K-Means clustering?

Choose k by combining an elbow/inertia curve with validation measures such as silhouette score, stability checks, and domain interpretation. K-means groups unlabeled numeric observations into k clusters by minimizing within-cluster squared distance, so an overly small k merges distinct groups while an overly large k splits meaningful groups into arbitrary pieces. The main trade-off is parsimonious, interpretable clusters versus enough resolution to preserve real structure.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

Selecting the Number of Clusters

Use several signals rather than relying on one metric:

  • Elbow method: Plot inertia against k and look for the point where additional clusters produce diminishing reductions in inertia. This is a visual heuristic, not an exact cutoff.

  • Silhouette score: Measures how well each point fits its assigned cluster compared with neighboring clusters. Scores range from -1 to 1; higher is generally better.

  • Stability: Refit the model on bootstrapped samples or with different seeds. A useful k should produce similar groupings across runs.

  • Domain usefulness: Examine cluster profiles and ask whether each group is actionable, distinguishable, and large enough to matter. Statistical metrics cannot determine business meaning.

How Lloyd’s Algorithm Finds Clusters

Lloyd’s algorithm repeats two operations:

  1. Initialize k centroids, normally using k-means++ in scikit-learn.

  2. Assign every point to its nearest centroid using Euclidean distance.

  3. Recompute each centroid as the mean of its assigned points.

  4. Repeat until assignments stop changing or max_iter is reached.

The objective minimized is:

inertia = sum from j=1 to k of sum over x_i in cluster j of squared_distance(x_i, centroid_j)

Here, k is the number of clusters, x_i is an observation, centroid_j is the mean of cluster j, and inertia is the total within-cluster sum of squares.

K-means++ chooses initial centroids that are unlikely to be close together, which often avoids poor local solutions. With n_init=10, scikit-learn runs ten initializations and retains the result with the lowest inertia. K-means still converges to a local optimum, so initialization and scaling can affect the result.

Alternatives and Limitations

Method How it works Strengths Weaknesses Typical scale
K-means Assigns points to nearest mean Fast and scalable Requires k; sensitive to scaling and outliers O(n * k * d) per iteration
GMM Uses probabilistic clusters Models elliptical cluster shapes More parameters; can overfit Roughly O(n * k * d) per iteration
K-medoids Uses actual observations as centers More robust to outliers Usually slower Often quadratic distance computation
DBSCAN/HDBSCAN Groups density-connected points Finds arbitrary shapes without k Sensitive to density parameters Indexed versions scale well; worst case quadratic

K-means also assumes roughly spherical, similarly sized clusters. It should generally be applied to continuous numeric features, not categorical data.

Code Example

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

# Synthetic data; generated labels are intentionally not used.
X, _ = make_blobs(
    n_samples=600,
    centers=4,
    cluster_std=1.0,
    random_state=42,
)

# Select k using training and validation data only.
X_train_val, X_test = train_test_split(
    X, test_size=0.20, random_state=42
)
X_train, X_val = train_test_split(
    X_train_val, test_size=0.50, random_state=42
)


def make_model(k: int) -> Pipeline:
    return Pipeline([
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=k,
            n_init=10,
            random_state=42,
        )),
    ])


results = []

for k in range(2, 8):
    model = make_model(k)
    model.fit(X_train)

    scaler = model.named_steps["scaler"]
    kmeans = model.named_steps["kmeans"]

    X_val_scaled = scaler.transform(X_val)
    val_labels = kmeans.predict(X_val_scaled)
    val_silhouette = silhouette_score(X_val_scaled, val_labels)

    results.append((k, val_silhouette))
    print(f"k={k}, inertia={kmeans.inertia_:.2f}, "
          f"validation silhouette={val_silhouette:.3f}")

# Choose the candidate with the highest validation silhouette.
selected_k = max(results, key=lambda row: row[1])[0]

# Refit the selected pipeline on training plus validation data.
final_model = make_model(selected_k)
final_model.fit(np.vstack((X_train, X_val)))

X_test_scaled = final_model.named_steps["scaler"].transform(X_test)
test_labels = final_model.named_steps["kmeans"].predict(X_test_scaled)
test_silhouette = silhouette_score(X_test_scaled, test_labels)
cluster_sizes = np.bincount(test_labels, minlength=selected_k)

print(f"Selected k: {selected_k}")
print(f"Test silhouette: {test_silhouette:.3f}")
print(f"Cluster sizes: {cluster_sizes.tolist()}")

Practical Guidance

  • Standardize features before clustering because K-means minimizes squared distances; unscaled features with large ranges dominate the result.

  • Fit imputers and scalers only on training data to prevent leakage. The Pipeline in the example enforces this for the scaler.

  • Use MiniBatchKMeans when the dataset is large because it processes subsets rather than all observations in every assignment step.

  • Profile clusters by feature distributions and population segments; cluster IDs are arbitrary and do not imply ordering.

  • If true labels are available, external metrics such as adjusted Rand index or normalized mutual information can supplement—but not replace—unsupervised evaluation.

Common Pitfalls

  • Treating the elbow as an exact answer rather than a visual heuristic.

  • Forgetting feature scaling or allowing extreme outliers to distort centroids.

  • Applying K-means directly to categorical variables; consider k-modes or an appropriate embedding.

  • Using the test set repeatedly while comparing candidate values of k.

  • Assuming silhouette score must always be positive or that a higher score guarantees useful clusters.

  • Reporting accuracy for an unsupervised clustering task without labeled ground truth.

  • Interpreting clusters without profiling their features, sizes, and stability.

7

Which centroid initialization methods are used in K-Means?

Centroid initialization determines the starting cluster centers used by K-Means. The standard choices are random selection, known as Forgy initialization, and k-means++, which is scikit-learn’s default; explicit centroids and custom strategies are also possible. Smarter initialization reduces the risk of a poor local optimum but adds some computation and cannot guarantee a globally optimal clustering.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

Common Initialization Methods

Method How It Works Strengths Weaknesses
Random selection (Forgy) Randomly selects k observations as the initial centroids. Simple and inexpensive May select nearby or unrepresentative points and produce poor clustering
k-means++ Selects the first centroid randomly, then selects later centroids with probability proportional to their squared distance from the nearest existing centroid. Spreads the initial centers apart and usually produces lower inertia More expensive than random selection and still may reach only a local optimum
Explicit centroids Supplies centroid coordinates directly, manually or from another algorithm. Provides controlled and reproducible starting points Requires reliable domain knowledge or a separate clustering stage
Custom hierarchical or density-based seeding Uses an agglomerative, histogram, or density estimate to choose starting centers. Can provide more informed starting points for specialized datasets Adds preprocessing complexity and is not a built-in scikit-learn initialization option

Scikit-learn’s KMeans supports init="random", init="k-means++", an array of initial centroid coordinates, and a callable initialization function. Its default is init="k-means++".

Initialization in Lloyd’s Algorithm

K-Means applies Lloyd’s algorithm after initializing the centroids:

  1. Initialize centroids: Choose k starting points, normally using k-means++.

  2. Assign observations: Assign each point to its nearest centroid using Euclidean distance.

  3. Recompute centroids: Replace each centroid with the mean of the observations assigned to its cluster.

  4. Repeat: Continue assigning and recomputing until the assignments stop changing or another stopping condition is reached.

  5. Select the best run: When multiple initializations are used, retain the run with the lowest inertia.

The objective is the within-cluster sum of squares:

WCSS = sum for each cluster of the sum of squared distances between each observation and that cluster’s centroid

Here, WCSS is the objective value, a cluster is a group of observations, each observation is a feature vector, and each centroid is the mean vector of its assigned observations. Squaring the Euclidean distance makes large differences contribute more strongly to the objective, which is why K-Means is sensitive to outliers.

The n_init Setting

n_init controls how many independent initializations scikit-learn tries, with the lowest-inertia result retained:

  • With init="k-means++", n_init="auto" performs 10 runs.

  • With init="random", n_init="auto" performs one run.

  • With an explicit centroid array or callable initializer, only one initialization is performed.

  • Setting random_state=42 makes the random initialization choices reproducible.

Initialization affects which local optimum Lloyd’s algorithm reaches, so different starts can produce different cluster assignments even when their final inertias are similar.

Practical Considerations

  • Feature scaling: Standardize numerical features before clustering because Euclidean-distance assignments are sensitive to feature scale.

  • Choosing k: Compare inertia across several values of k and use silhouette scores and domain knowledge. The elbow is a heuristic rather than an exact answer.

  • Data separation: When evaluating a clustering pipeline, fit the scaler and K-Means only on training data, then transform and evaluate held-out observations separately.

  • Missing values and outliers: KMeans does not accept NaN, and extreme values can pull centroids toward themselves; impute missing values and inspect outliers.

  • Cluster structure: K-Means assumes roughly spherical clusters with similar sizes and densities.

  • Large datasets: MiniBatchKMeans reduces computation by updating centroids from small batches rather than the entire dataset.

  • Alternatives: Consider k-medoids for greater robustness to outliers, Gaussian mixture models for elliptical probabilistic clusters, and DBSCAN or HDBSCAN for irregularly shaped, density-based structures.

Common Pitfalls

  • Not scaling features: Features with large numeric ranges dominate the distance calculation.

  • Trusting one random start: Use multiple restarts or k-means++ to reduce initialization sensitivity.

  • Treating the elbow as exact: Combine inertia, silhouette scores, stability checks, and domain knowledge.

  • Using K-Means on categorical data: It is designed for numerical distances; use k-modes or another suitable method.

  • Interpreting clusters without profiling them: Examine feature distributions, cluster sizes, stability, and business meaning before assigning labels.

  • Confusing clusters with classes: K-Means is unsupervised and its clusters do not necessarily correspond to labeled target classes.

8

Can K-Means clustering handle categorical data?

K-Means can technically cluster categorical data after converting nominal values into numeric features, usually with one-hot encoding. It solves the problem of grouping similar observations without labels, but its main trade-off is that squared Euclidean distance and mean-based centroids do not naturally model nominal categories. For predominantly categorical data, k-modes is usually more appropriate.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

Handling Categorical Features

Standard K-Means cannot consume raw strings or unordered category labels directly. A common workflow is:

  1. Encode each categorical column with one-hot encoding.

  2. Optionally scale numeric features; scaling one-hot columns is optional and can change how categories influence distances.

  3. Fit K-Means on the transformed matrix.

  4. Inspect clusters using frequencies of the original categories.

One-hot encoding treats categories symmetrically and avoids the false distance order introduced by integer codes such as red = 0, green = 1, and blue = 2. For unscaled one-hot features, two observations differ by two squared distance units for each categorical field in which they disagree (one indicator turns off and another turns on). A field’s number of possible levels does not directly change the cost of one mismatch, although higher-cardinality fields add dimensions and can affect aggregate distances and centroid behavior.

K-Means centroids on one-hot data are fractional averages rather than actual category values. Consequently, each cluster should be interpreted by profiling its original category frequencies. For mixed data, numerical features should generally be standardized so their scale does not dominate the clustering.

Lloyd’s Algorithm

Lloyd’s algorithm implements K-Means iteratively:

  1. Initialize centroids: Select k starting centroids. Scikit-learn uses k-means++ by default, which probabilistically favors initial centers that are relatively far apart and reduces the chance of a poor local solution.

  2. Assign points: Assign each observation to its nearest centroid using squared Euclidean distance.

  3. Recompute centroids: Replace each centroid with the mean of the observations assigned to it.

  4. Repeat: Continue until assignments stop changing or the iteration limit is reached.

The objective minimized by the algorithm is the within-cluster sum of squares, also called inertia:

WCSS = sum(i=1 to n) ||x_i - μ_(c_i)||²

Here, x_i is observation i, c_i is its assigned cluster, μ_(c_i) is that cluster’s centroid, and ||x_i - μ_(c_i)||² is the squared Euclidean distance from the observation to its centroid.

A Lloyd iteration costs approximately O(n × k × d), where n is the number of observations, k is the number of clusters, and d is the number of encoded features. The n_init parameter controls the number of initializations; scikit-learn retains the run with the lowest inertia. In scikit-learn 1.5+, n_init="auto" uses one run with the default k-means++ initialization and ten runs with random initialization, while an integer requests that many runs.

K-Means converges to a local optimum, so its result can depend on initialization. MiniBatchKMeans is a more practical option for large datasets.

Choosing k and Comparing Alternatives

Approach How it works Strengths Weaknesses When to use Typical complexity
One-hot K-Means Euclidean distance on encoded categories Uses standard K-Means tooling Fractional centroids; high-cardinality dimensions can be troublesome Low-cardinality or mixed data O(n × k × d) per iteration
k-modes Uses category modes and matching distance Designed for nominal data Separate tooling; generally limited to categorical variables Primarily categorical datasets Approximately O(n × k × d) per iteration
k-medoids Uses actual observations as cluster centers More robust to outliers than K-Means Pairwise distances can be expensive Numeric or mixed data where robustness matters Often O(n²)
Gaussian mixture models Models clusters as probability distributions Soft assignments and covariance modeling Assumes Gaussian-shaped clusters Uncertain membership or overlapping clusters Implementation-dependent
DBSCAN/HDBSCAN Groups points by density Finds irregular clusters and noise Sensitive to distance and density settings Non-spherical clusters or outliers Roughly O(n log n) to O(n²) depending on implementation

Choose k using inertia, silhouette score, cluster stability, and domain knowledge. An elbow is a visual guide rather than an exact answer. Gower distance is another option for mixed data because it can combine categorical and numerical dissimilarities.

Common Pitfalls

  • Using raw category codes: This creates a false ordering and distance structure.

  • Ignoring feature importance: A one-hot distance and any subsequent weighting should reflect the importance of each original field.

  • Choosing k only from the elbow: Combine quantitative diagnostics with stability checks and domain knowledge.

  • Interpreting centroids as categories: One-hot centroids are fractional averages; profile the original observations instead.

  • Fitting preprocessing on all data: When using held-out evaluation, fit encoders and scalers only on the training data.

  • Ignoring outliers and sparsity: K-Means is sensitive to outliers and can perform poorly on very high-cardinality sparse data.

  • Confusing local and global optimality: Use multiple initializations, a fixed random_state, and compare alternative methods when necessary.

Interviewers commonly ask why k-modes is preferable, how one-hot encoding changes distance, how k is selected, and how initialization affects convergence.

9

What is cluster inertia in K-Means clustering?

Cluster inertia, also called the within-cluster sum of squares, measures how tightly points are grouped around their assigned centroids. In K-Means, it is the sum of the squared Euclidean distances between each point and the centroid of its assigned cluster, so lower inertia indicates more compact clusters. Its main trade-off is that the optimal inertia generally decreases as k increases, meaning inertia alone cannot identify the correct number of clusters.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

Definition and Formula

For a dataset with n points assigned to k clusters, the objective is:

Inertia = sum from i = 1 to n of ||x_i - μ_(z_i)||²

In plain text:

Inertia = ||x₁ - μ₁||² + ||x₂ - μ₂||² + … + ||xₙ - μₙ||²

  • n: The total number of data points.

  • xᵢ: The coordinates of data point i.

  • zᵢ: The cluster assigned to point i.

  • μᵢ: The centroid of the cluster assigned to point i.

  • ||xᵢ - μᵢ||²: The squared Euclidean distance between the point and its assigned centroid.

The result is also called WCSS, or within-cluster sum of squares. After fitting, scikit-learn exposes it through the KMeans.inertia_ property.

How Lloyd’s Algorithm Minimizes Inertia

  1. Initialize the centroids: Scikit-learn defaults to init="k-means++", which selects initial centers in a way that avoids placing all of them in the same dense region. The first center is selected randomly; later centers are selected with probability influenced by their squared distance from the nearest existing center.

  2. Assign points: Each point is assigned to the nearest centroid according to squared Euclidean distance.

  3. Recompute centroids: Each centroid is replaced by the mean of the points assigned to its cluster.

  4. Repeat: Assignment and centroid-update steps continue until assignments stop changing or the iteration limit is reached.

Lloyd’s algorithm decreases the objective and converges to a local optimum, so its result depends partly on initialization. Multiple restarts can reduce that dependence: scikit-learn keeps the run with the lowest inertia. With n_init="auto", scikit-learn performs one run for the default "k-means++" initialization and 10 for "random"; use an explicit integer such as n_init=10 when several k-means++ restarts are desired.

Interpreting and Choosing k

Observation Interpretation
Lower inertia Points are closer to their assigned centroids
Higher inertia Points are more dispersed around their centroids
More clusters The optimal inertia cannot increase because splitting a cluster cannot increase its squared error
k equals the number of points Inertia reaches zero, but the result is trivial and generally not useful

An elbow plot graphs inertia against candidate values of k. The elbow is where another cluster produces a relatively small reduction in inertia, but it is a visual heuristic rather than an exact boundary. It should be supplemented with:

  • Silhouette score: Higher values generally indicate better cohesion and separation.

  • Calinski-Harabasz index: Higher values generally indicate a better ratio of within-cluster to between-cluster dispersion.

  • Davies-Bouldin index: Lower values generally indicate less dispersion relative to separation between clusters.

  • Domain knowledge: Clusters should have a meaningful and actionable interpretation.

Inertia values are comparable only when they use the same observations, features, and preprocessing. Comparing values from different feature spaces is generally meaningless.

Complexity, Assumptions, and Alternatives

For n points, k centroids, and d features:

  • Time per Lloyd iteration: O(n * k * d).

  • Multiple restarts: Multiply the iteration cost by the number of runs.

  • Memory: Approximately O(n * d + k * d + n) for the data, centroids, and labels. Scikit-learn can chunk distance calculations, so a full n * k distance matrix need not be stored.

For large datasets, MiniBatchKMeans reduces computation by updating centroids from smaller batches rather than processing the entire dataset in every iteration.

K-Means assumes roughly spherical, similarly sized clusters and is sensitive to feature scaling and outliers. Alternatives include:

Algorithm Main difference Useful when
K-Medoids Uses representative data points as centers Medoid-based robustness or non-Euclidean dissimilarity is needed
Gaussian Mixture Model Models clusters as probability distributions Cluster variances or orientations differ
DBSCAN/HDBSCAN Connects dense regions without requiring k Cluster count is unknown or cluster shapes are irregular

Common Pitfalls

  • Not scaling features: Features with larger numerical ranges dominate the Euclidean distance.

  • Treating the elbow as exact: It is a heuristic, not a mathematical proof of the best k.

  • Using K-Means on categorical data: Use a categorical-specific method such as K-Modes.

  • Ignoring outliers: Extreme values can strongly pull centroids.

  • Interpreting clusters without profiling them: Examine cluster sizes, centroids, feature distributions, and domain meaning.

  • Assuming convergence proves global optimality: Lloyd’s algorithm reaches a local optimum, so initialization and multiple restarts matter.

  • Leaking evaluation information: If clustering is part of a supervised workflow, fit preprocessing and clustering only on training folds.

10

What limitations does K-Means clustering have?

K-Means is an unsupervised algorithm that groups similar data points by minimizing the distance between each point and its cluster centroid. Its main trade-off is efficiency and simplicity versus sensitivity to the choice of k, feature scaling, outliers, and the assumption that clusters are compact and roughly spherical. Its resulting partitions do not necessarily represent meaningful real-world groups.

Read full answer

Applies tomachine learning concepts; scikit-learn 1.5+ (Python 3.12)

How K-Means Works

K-Means commonly uses Lloyd’s algorithm:

  1. Initialize k centroids.

  2. Assign every data point to its nearest centroid.

  3. Recompute each centroid as the mean of its assigned points.

  4. Repeat until assignments stop changing or another stopping condition is reached.

It minimizes the within-cluster sum of squares:

WCSS = Σ_c Σ_(x∈c) ||x - μ_c||²

Here, c is a cluster, x is one of its data points, and μ_c is that cluster’s centroid, or mean. The term ||x - μ_c||² is the squared Euclidean distance, and WCSS is the total of these squared distances across all points.

Scikit-learn uses k-means++ initialization by default, which selects initial centroids that are more spread out than uniform random selection. Setting n_init to an integer greater than one performs several restarts and retains the solution with the lowest inertia. K-Means converges to a local optimum, so initialization can affect the result.

Main Limitations

  • Requires choosing k in advance: Standard K-Means does not select the number of clusters itself. An inappropriate k may fragment natural groups or merge distinct ones.

  • Assumes compact, roughly spherical clusters: It works best when groups can be separated using Euclidean distance.

  • Can struggle with very different cluster sizes or densities: Small clusters may be absorbed while larger clusters are divided.

  • Is sensitive to outliers: Extreme values can pull centroids away from the main distribution; k-medoids is often more robust.

  • Is sensitive to feature scale: When features have different units or materially different ranges, larger-range features dominate the distance calculation. Standardization or normalization should then be considered.

  • Converges to a local optimum: Initialization affects the result, although several restarts can reduce this problem.

  • Does not naturally model noise or arbitrary shapes: Every point is assigned to one of the selected clusters, even when it does not belong to a meaningful group.

  • Produces hard assignments: A point belongs to exactly one cluster rather than receiving membership probabilities.

  • Is unsuitable for most categorical features: Euclidean distances and centroid means are generally inappropriate; consider k-modes instead.

Choosing the Number of Clusters

The elbow method plots WCSS, exposed by scikit-learn as inertia_, against k. It identifies a point after which additional clusters produce smaller improvements, but the elbow is only a heuristic rather than an exact answer.

Interpret it alongside the silhouette score, domain knowledge, stability across random seeds or resamples, and profiles of the resulting clusters. Stability and interpretability are often more useful than the lowest WCSS alone.

Alternatives

Method How it works Strengths Weaknesses When to use Complexity or scale
K-Means Assigns points to nearest mean-based centroid Fast and scalable Sensitive to scaling, outliers, initialization, and k Large numeric datasets with compact clusters O(n * k * d) per iteration
K-Medoids Uses actual observations as cluster centers More robust to outliers Slower for large datasets Noisy data where means are unreliable Commonly O(n² * d) per iteration
Gaussian Mixture Models Models clusters as probability distributions Soft assignments and covariance estimates More computationally expensive Uncertain membership or non-isotropic clusters Often O(n * k * d) to O(n * k * d²) per iteration
DBSCAN Connects density-reachable neighborhoods Finds irregular clusters and identifies noise Sensitive to density parameters and varying densities Spatial data with irregular cluster shapes Roughly O(n * d) with efficient neighborhood search
HDBSCAN Builds a hierarchy of density-based clusters Does not require a fixed cluster count and handles noise Can be expensive in high dimensions Unknown cluster counts and varying densities Best suited to moderate-size datasets; cost depends on implementation

Complexity and Practical Concerns

For n points, k clusters, and d features, each K-Means iteration takes approximately O(n * k * d) time. Stored data requires O(n * d) space, centers require O(k * d), and labels require O(n). Scikit-learn can process distances in chunks rather than retaining a full O(n * k) matrix.

For large datasets, MiniBatchKMeans processes smaller batches, reducing computation at the cost of potentially less stable results. K-Means generally runs efficiently on CPUs and does not require a GPU. Missing values, inconsistent units, duplicate observations, and highly correlated features should be reviewed before clustering. Because there are no target labels, ordinary accuracy is not automatically an appropriate metric; inspect cluster composition, separation, stability, and usefulness.

Common Pitfalls

  • Not scaling features: Standardize numeric features when their units or ranges differ materially.

  • Treating the elbow as definitive: Combine it with silhouette analysis, stability checks, and domain knowledge.

  • Ignoring cluster geometry: Consider density-based or probabilistic methods for irregular groups.

  • Ignoring outliers: Check distributions and compare with robust methods when necessary.

  • Using K-Means on categorical data: Choose a method designed for categorical variables.

  • Over-interpreting clusters: A mathematical partition is not automatically a meaningful business or scientific category.

  • Selecting k from repeatedly inspected results: Keep model selection separate from final interpretation to avoid overfitting the selected solution.

11

How do K-Means and hierarchical clustering differ?

K-Means clustering groups data around a fixed number of centroids, while hierarchical clustering organizes data into a hierarchy of nested groups. K-Means is fast and scalable but requires choosing k and can settle for a local optimum; hierarchical clustering reveals multi-level structure without committing to k initially, but it is generally more expensive and sensitive to distance and linkage choices.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12), with algorithm concepts applicable more broadly

How K-Means Works

K-Means minimizes the within-cluster sum of squares, also called inertia:

WCSS = Σ(j) Σ(x in Cj) ||x - μj||²

Here, Cj is cluster j, x is a data point in that cluster, μj is the cluster’s centroid, and ||x - μj||² is its squared Euclidean distance from the centroid. Lower WCSS means points are, on average, closer to their assigned centroids.

The standard Lloyd’s algorithm proceeds as follows:

  1. Choose k and initialize k centroids.

  2. Assign each point to its nearest centroid, usually using Euclidean distance.

  3. Recompute each centroid as the mean of its assigned points.

  4. Repeat assignment and recomputation until assignments stop changing or another stopping condition is reached.

In scikit-learn, init="k-means++" is the default. It selects initial centroids with a probability scheme that favors spreading them apart and generally reduces the risk of poor local solutions.

The n_init parameter controls how many initializations are attempted. In scikit-learn 1.5+, n_init="auto" uses one initialization with init="k-means++" and 10 with init="random". Setting a numeric n_init greater than one performs several restarts, and scikit-learn keeps the run with the lowest inertia. Nevertheless, K-Means can converge to a local optimum, so repeated runs and multiple values of k are advisable.

How Hierarchical Clustering Works

Hierarchical clustering produces a tree of merges, commonly displayed as a dendrogram. In agglomerative clustering, every point begins as its own cluster, and the algorithm repeatedly merges the two closest clusters. A user can cut the dendrogram at a chosen height to obtain a particular number of clusters.

Common linkage methods include:

  • Single linkage: Merges clusters using their smallest pairwise distance. It can connect clusters through chains and produce elongated, loosely defined groups.

  • Complete linkage: Uses the largest pairwise distance between clusters. It tends to produce compact, similarly sized clusters.

  • Average linkage: Uses the average pairwise distance, balancing the tendencies of single and complete linkage.

  • Ward linkage: Merges clusters to minimize the increase in within-cluster variance. It is particularly suitable for continuous, Euclidean data.

Divisive hierarchical clustering works in the opposite direction, beginning with all points in one cluster and repeatedly splitting clusters. Unlike K-Means, hierarchical clustering does not require k before the analysis, although a final k is still needed for deployment or comparison.

Direct Comparison

Aspect K-Means Hierarchical Clustering
How it works Iteratively assigns points to centroids and recomputes their means Repeatedly merges or splits clusters to build a hierarchy
Number of clusters Must be specified before fitting Can be selected afterward by cutting the dendrogram
Main objective Minimizes within-cluster squared distance Depends on the distance metric and linkage method
Output Cluster assignments, centroids, and inertia Dendrogram and assignments at a chosen cut
Strengths Fast, simple, and effective on compact numerical clusters Reveals nested structure and supports flexible cluster counts
Weaknesses Sensitive to initialization, outliers, scaling, and cluster shape More computationally expensive; agglomerative merges cannot be reversed
Best suited for Large datasets with roughly spherical, similar-sized clusters Smaller datasets where hierarchical relationships matter
Typical complexity O(n * k * d) per iteration A straightforward agglomerative implementation can require up to O(n³) time and O(n²) memory

n is the number of points, k is the number of clusters, and d is the number of features.

Choosing and Validating a Method

Use K-Means when the dataset is large, the features are numerical and reasonably scaled, and the expected clusters are compact. For very large datasets, consider MiniBatchKMeans, which updates centroids using small batches rather than assigning all observations during every iteration; it reduces computation at the possible cost of noisier results.

Use hierarchical clustering when the dataset is modest, cluster structure may be nested, or the number of groups is uncertain and a dendrogram would provide useful insight.

Neither method automatically discovers meaningful business segments. Compare solutions using internal measures such as silhouette score, Davies–Bouldin index, and inertia where applicable. Also check stability across random seeds, samples, or linkage choices. If clustering is used to create features for a supervised model, fit the clustering and scaler only on the training partition to prevent leakage; use Pipeline for this purpose.

Common Pitfalls

  • Failing to scale features: K-Means and Euclidean-distance hierarchical methods can let large-magnitude features dominate the result. Standardize numerical features when their units differ.

  • Choosing k only from the elbow method: Treat the elbow as guidance rather than an exact answer, and combine it with silhouette scores and domain knowledge.

  • Applying K-Means to categorical data: Use K-Modes or another method designed for categorical similarity instead.

  • Ignoring outliers: Extreme values can pull centroids or distort distances. Inspect and handle them explicitly.

  • Assuming spherical clusters: K-Means performs poorly on elongated, crescent-shaped, or unequal-sized groups.

  • Interpreting clusters without profiling them: Examine feature distributions, cluster sizes, and representative members before assigning business meaning.

  • Ignoring initialization or linkage sensitivity: Run K-Means with multiple initializations and compare hierarchical results under different linkage methods.

Useful interview follow-ups include: “Why does K-Means need standardized features?”, “How would you select k?”, “Why can K-Means reach a local optimum?”, and “When would DBSCAN, HDBSCAN, GMMs, or K-Medoids be preferable?”

12

How does K-Means handle clusters with non-spherical shapes?

K-Means clustering partitions data into regions centered on centroid means, so it works best for compact, roughly spherical groups. For elongated, curved, crescent-shaped, or unevenly sized groups, it may split one structure across multiple clusters or combine parts of different structures. Its main trade-off is fast, simple partitioning versus the flexibility offered by density-based or distribution-based alternatives.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

Why Cluster Shape Matters

K-Means assigns every point to its nearest centroid. These assignments create Voronoi regions, which have convex boundaries around the centroids. It therefore struggles when the ideal clusters cannot be represented by convex regions.

Typical behavior includes:

  • Elongated clusters: K-Means may divide a long structure perpendicular to its length.

  • Crescent or ring-shaped clusters: Separate sections may be merged because their points are closer to the same centroids.

  • Unequal cluster sizes: Large clusters can be split while small clusters disappear.

  • Different densities: Sparse regions may form their own cluster or be absorbed into nearby clusters.

  • Irregular boundaries: Centroids can fall outside the densest part of a non-convex cluster.

How Lloyd’s Algorithm Handles Them

The within-cluster sum of squares, also called inertia, is:

WCSS = sum over i of ||x_i - mu_c(i)||²

Here, i identifies a data point, x_i is its feature vector, mu_c(i) is the mean of its assigned cluster, and ||...||² is the squared Euclidean distance.

Lloyd’s algorithm proceeds as follows:

  1. Initialize centroids: Scikit-learn uses k-means++ by default. It selects one initial centroid randomly, then selects others with probability proportional to their squared distance from the closest existing centroid.

  2. Assign points: Each point joins its nearest centroid.

  3. Recompute centroids: Each centroid becomes the mean of its assigned points.

  4. Repeat: Assignments and means are updated until assignments stop changing or another stopping condition is reached.

  5. Keep the best result: Among the launched runs, scikit-learn retains the result with the lowest inertia. In version 1.5+, n_init="auto" launches 10 runs for datasets with at most 10,000 samples and one run for larger datasets; specify a positive integer to control the number of restarts.

Each iteration costs approximately O(n * k * d), where n is the number of points, k the number of clusters, and d the number of features. The result depends on initialization and generally converges to a local optimum rather than the global optimum.

Alternatives for Non-Spherical Data

Algorithm How it works Strengths Weaknesses Use when Typical complexity or scale
K-Means Assigns points to nearest mean Fast and scalable Convex clusters; sensitive to outliers and scaling Roughly spherical clusters O(T * n * k * d)
Gaussian Mixture Models Models clusters as probability distributions Supports elliptical clusters and soft assignments Still struggles with strongly non-convex shapes Overlapping elliptical groups Roughly O(T * n * k * d) per EM iteration
DBSCAN Groups density-connected points Finds arbitrary shapes; identifies noise Sensitive to density parameters; struggles with varying densities Irregular clusters with outliers Average O(n log n); worst-case O(n²)
HDBSCAN Uses hierarchical density clustering Handles varying densities without choosing an eps threshold More computational overhead Complex density structures Intended for moderately large datasets
K-Medoids Uses actual data points as centers More robust to outliers than means Pairwise distances can be expensive; still partitions around centers Small or medium datasets needing robust centers Often O(n²) distance storage
Spectral K-Means Clusters points in a spectral embedding Captures non-convex structure Expensive for large datasets Complex shapes where geometry matters Dense versions can require O(n³) time

Practical Guidance

  • Scale features: K-Means uses Euclidean distance, so variables with larger scales dominate the result.

  • Choose k carefully: Combine the elbow method, silhouette analysis, cluster stability, and domain knowledge.

  • Inspect clusters: Profile each group’s features and size rather than interpreting cluster IDs as meaningful classes.

  • Handle outliers: Means are sensitive to extreme values; robust methods such as K-Medoids may be preferable.

  • Handle missing values: Scikit-learn K-Means does not accept NaN values, so impute them before fitting.

  • Avoid categorical data: Use k-modes for categorical variables rather than encoding them as arbitrary numbers.

  • Check reproducibility and stability: Set random_state and compare results across random initializations.

  • Use MiniBatchKMeans for large datasets: It reduces update cost but may produce less stable assignments than full K-Means.

Common Pitfalls

  • Expecting spherical discoveries: K-Means cannot naturally represent curved cluster boundaries.

  • Treating the elbow as exact: It is a visual heuristic, not a definitive selection rule.

  • Fitting preprocessing on all data: When evaluating generalization, fit the scaler only on training data to avoid leakage.

  • Ignoring empty or tiny clusters: Examine cluster sizes and centroid positions.

  • Using silhouette alone: A high score does not guarantee meaningful or well-separated clusters.

  • Likely interview follow-ups: “Why does K-Means fail on moons?”, “How does k-means++ reduce initialization risk?”, “How would you select k?”, or “Which algorithm would you use for irregular clusters and outliers?”

13

How do you handle outliers with K-Means clustering?

K-Means is sensitive to outliers because centroids are arithmetic means, so extreme values can pull clusters toward themselves. Detect outliers using thresholds learned only from training data, then remove, winsorize, or downweight them before fitting the model. The main trade-off is that treating valid boundary observations as outliers can remove meaningful structure or distort cluster boundaries.

Read full answer

Applies toscikit-learn 1.5+ and NumPy 2.x (Python 3.12)

Why Outliers Hurt K-Means

K-Means minimizes the within-cluster sum of squares:

inertia = sum(||x_i - c_assigned(x_i)||^2)

Here, x_i is an observation, c_assigned(x_i) is its assigned centroid, and ||...||^2 is squared Euclidean distance. A distant point contributes a large value and can significantly influence its centroid’s location.

Common responses include:

  • Remove outliers: Appropriate when they are clearly measurement errors or corrupted records.

  • Winsorize values: Replace extreme values with a training-derived percentile boundary.

  • Downweight outliers: Give them a smaller sample_weight during fitting so they influence centroids less.

  • Use a robust alternative: Consider K-Medoids when outliers should remain in the dataset.

When only one feature is extreme, capping or winsorizing that feature is usually preferable to deleting the entire observation, provided the transformation is domain-appropriate.

How Lloyd’s Algorithm Works

K-Means repeatedly performs these steps:

  1. Initialize k centroids, normally using K-Means++, which favors initial centers in dense regions.

  2. Assign every point to its nearest centroid.

  3. Recalculate each centroid as the mean of its assigned points.

  4. Repeat until assignments stop changing or another stopping condition is reached.

scikit-learn runs multiple initializations through n_init and retains the solution with the lowest inertia. Lloyd’s algorithm converges to a local optimum, so different initializations can produce different results.

Each iteration takes approximately O(n * k * d) time, where n is the number of points, k the number of clusters, and d the number of features. MiniBatchKMeans reduces computation for large datasets by updating centroids from batches.

Choosing an Outlier Strategy

Approach How it works Strengths Weaknesses When to use Typical complexity or scale
Remove or cap Deletes records or clips extreme values Simple and effective Can discard valid cases Known errors or extreme measurements O(n * d) preprocessing
Weighted K-Means Reduces the influence of suspicious points Preserves observations Requires defensible weights Mild numeric contamination O(n * k * d) per iteration
K-Medoids Uses observations as cluster centers Less influenced by extreme values More expensive Small or medium robust datasets Pairwise costs commonly make builds O(n^2) or worse
DBSCAN/HDBSCAN Groups dense regions and identifies noise Handles irregular clusters Parameter and scaling sensitive Noisy spatial data Neighborhood-search dependent; can approach O(n^2)
Gaussian mixture models Models probabilistic clusters Soft assignments and covariance information Strong distributional assumptions Elliptical or overlapping clusters Roughly O(n * k * d^2) per full-covariance EM iteration

Code Example

This example learns robust outlier thresholds from the training partition, prints inertia for several cluster counts, and downweights detected outliers:

import numpy as np
from sklearn.cluster import KMeans
from sklearn.compose import ColumnTransformer
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

# Generate reproducible data with two extreme observations.
X, _ = make_blobs(
    n_samples=300,
    centers=3,
    cluster_std=0.8,
    random_state=42,
)
X = np.vstack([X, np.array([[8.0, -8.0], [9.0, -9.0]])])

# Split before learning thresholds or preprocessing parameters.
X_train, X_test = train_test_split(
    X, test_size=0.2, random_state=42
)

# Learn robust location and scale from training data only.
center = np.median(X_train, axis=0)
mad = np.median(np.abs(X_train - center), axis=0)
robust_scale = 1.4826 * mad
robust_scale[robust_scale == 0] = 1.0

train_outliers = (
    np.abs(X_train - center) / robust_scale
).max(axis=1) > 3.5

test_outliers = (
    np.abs(X_test - center) / robust_scale
).max(axis=1) > 3.5

weights = (~train_outliers).astype(float)


def make_model(k):
    return Pipeline([
        ("preprocessor", ColumnTransformer([
            ("numeric", StandardScaler(), [0, 1]),
        ])),
        ("kmeans", KMeans(
            n_clusters=k,
            n_init=10,
            random_state=42,
        )),
    ])


# Compare inertia for several candidate values of k.
models = {}
for k in range(2, 6):
    candidate = make_model(k)
    candidate.fit(X_train, kmeans__sample_weight=weights)
    models[k] = candidate
    print(
        f"k={k}, inertia="
        f"{candidate.named_steps['kmeans'].inertia_:.3f}"
    )

model = models[3]
train_labels = model.predict(X_train)
inlier_mask = ~train_outliers

# Use the same transformed feature space in which K-Means was fitted.
X_train_scaled = model.named_steps["preprocessor"].transform(X_train)

print("Detected outliers (train/test):",
      int(train_outliers.sum()), int(test_outliers.sum()))
print("Inlier cluster sizes:",
      np.bincount(train_labels[inlier_mask], minlength=3))
print("Training silhouette:",
      silhouette_score(X_train_scaled[inlier_mask],
                       train_labels[inlier_mask]))

Common Pitfalls

  • Choosing k carelessly: K-Means requires a predefined k; compare inertia, silhouette, stability, and domain evidence rather than treating the elbow as exact.

  • Not scaling features: K-Means uses distances, so features measured on very different scales distort the result.

  • Using categorical data directly: Distances on nominal features are not meaningful; use K-Modes or suitable embeddings.

  • Leaking preprocessing information: Learn imputation, scaling, and outlier thresholds only from training data or folds.

  • Assuming clusters are naturally meaningful: Profile each cluster’s feature distributions and business characteristics before interpreting it.

  • Ignoring rare groups: K-Means favors similarly sized, roughly spherical clusters, so rare clusters may disappear.

14

How does feature scaling affect K-Means clustering?

Feature scaling changes the relative distances used by K-Means by rescaling features before clustering. It usually prevents features with large numerical ranges from dominating the Euclidean-distance calculation, but it can suppress genuinely meaningful magnitude differences and does not make K-Means robust to outliers. The main trade-off is that scaling roughly equalizes features’ variance-based influence rather than preserving their original units and relative magnitudes.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

Why Scaling Matters

K-Means assigns observations to the nearest centroid using Euclidean distance and minimizes the within-cluster sum of squares:

WCSS = sum(c=1 to k) sum(i in C_c) ||x_i - mu_c||_2^2

Here, k is the number of clusters, C_c is the set of observations assigned to cluster c, x_i is an observation’s feature vector, mu_c is that cluster’s centroid, and ||x_i - mu_c||_2^2 is their squared Euclidean distance. Scikit-learn reports this objective as inertia_.

If income ranges from thousands while age ranges from tens, income contributes disproportionately to each squared distance even when both features are equally informative.

  • Standardization (StandardScaler): Subtracting the training mean and dividing by the training standard deviation produces approximately zero mean and unit variance.

  • Min-max scaling (MinMaxScaler): Maps each feature to a fixed interval, commonly [0, 1].

  • Robust scaling (RobustScaler): Uses the median and interquartile range, making the scaling operation less sensitive to extreme values.

  • No scaling: Appropriate when features already have comparable scales and their original relative magnitudes are intentional.

Scaling does not change Lloyd’s algorithm; it changes the geometry in which centroids and distances are calculated. Standardization also does not guarantee equal semantic importance, particularly when features are correlated.

Lloyd’s Algorithm and Initialization

Lloyd’s algorithm performs these steps:

  1. Initialize centroids: Select k initial cluster centers.

  2. Assign observations: Assign each observation to its nearest centroid using Euclidean distance.

  3. Recompute centroids: Replace each centroid with the mean of its assigned observations.

  4. Repeat: Continue until assignments stop changing or another stopping criterion is reached.

Each update cannot increase the within-cluster sum of squares, but K-Means can converge to a local optimum, not necessarily the globally optimal partition.

Scikit-learn uses k-means++ initialization by default. It selects initial centroids probabilistically, giving observations far from existing centroids a higher chance of being selected. In scikit-learn 1.5+, n_init="auto" performs 10 initializations for the default k-means++ method, and the run with the lowest inertia_ is retained. Results still depend on initialization and the random seed.

Complexity and Large Datasets

For n observations, k clusters, d features, T iterations, and n_init restarts:

  • Time per iteration: approximately O(n * k * d).

  • Total time: approximately O(n * k * d * T * n_init).

  • Memory: primarily O(n * d + k * d), including the data and centroids.

MiniBatchKMeans processes subsets of observations per iteration and is substantially faster on large datasets. Its assignments can be less stable than those produced by full K-Means.

Choosing k and Interpreting Clusters

inertia_ generally decreases as k increases because allowing more clusters reduces the optimized within-cluster sum of squares, so its smallest value does not identify the best cluster count.

  • Elbow plot: Look for diminishing reductions in inertia rather than treating one elbow as exact.

  • Silhouette score: Higher values generally indicate better separation, but the score can be misleading for overlapping, highly unequal, or geometrically mismatched clusters.

  • Cluster stability: Compare assignments across random seeds, resamples, or time periods.

  • Domain knowledge: Confirm that the proposed groups are useful and interpretable.

  • Cluster profiles: Examine feature distributions within each cluster and compare them with the original population.

Limitations and Alternatives

K-Means assumes roughly spherical, similarly sized clusters separated by distance. It requires choosing k, is sensitive to scaling and initialization, and can be pulled away by extreme observations.

Alternative How it works Strengths Weaknesses When to use Typical complexity or scale
K-Medoids Uses actual observations as cluster centers Less sensitive to outliers than centroid means More computationally expensive Small or medium datasets containing outliers Many implementations use an O(n^2) pairwise-distance matrix
Gaussian Mixture Model Models clusters as probability distributions Supports elliptical clusters, overlap, and soft assignments Requires distributional assumptions Overlapping or probabilistic groups Roughly O(n * k * d) per EM iteration for diagonal covariances; full covariance is costlier
DBSCAN Connects observations through density neighborhoods Finds arbitrary shapes and identifies noise Sensitive to density parameters and varying density Irregular clusters with noise Approximately O(n * d) on average with a spatial index; worst case approaches O(n^2 * d)
HDBSCAN Builds a density hierarchy and extracts stable clusters Finds variable-density clusters and noise without fixing k Less intuitive parameters and additional hierarchy overhead Clusters with varying density Index- and hierarchy-dependent; often costlier than DBSCAN

Common Pitfalls

  • Not scaling features: Large-range features may determine assignments unintentionally.

  • Assuming robust scaling solves outliers: RobustScaler limits their effect on scaling, but K-Means centroids can still be pulled by outliers.

  • Ignoring missing values: K-Means does not accept NaN values; impute them before scaling and clustering, fitting the imputer on training data only during held-out evaluation.

  • Using categorical features directly: K-Means relies on numerical distance; use k-modes for categorical data.

  • Treating the elbow as exact: It is a heuristic rather than proof of an optimal k.

  • Leaking preprocessing information: Fit scalers and imputers only on the training partition when developing or evaluating a clustering pipeline.

  • Repeatedly tuning against test data: This can overfit the evaluation set; use training data, validation data, or cross-validation for selection.

  • Ignoring reproducibility and cluster profiles: Use fixed random states and multiple restarts, then profile and validate clusters using domain knowledge.

Common follow-ups include why scaling changes distances without changing the algorithm, how k-means++ reduces poor initializations, why optimized inertia tends to decrease as k increases, and when MiniBatchKMeans is preferable.

15

Why is K-Means clustering a greedy algorithm?

K-Means clustering is greedy because it makes locally optimal assignments and centroid updates without backtracking to search for a better global partition. It solves the problem of grouping unlabeled observations into k clusters, with the main trade-off being its efficiency and simplicity versus the risk of converging to a local rather than global optimum.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12), using Lloyd’s algorithm

Why It Is Greedy

“Greedy” means that the algorithm commits to decisions that improve the current solution and does not explore alternative decisions that might lead to a better final result.

In each Lloyd iteration, K-Means:

  1. Assigns every point to its nearest current centroid.

  2. Recomputes each centroid as the mean of its assigned points.

  3. Repeats until assignments stabilize or the iteration limit is reached.

The assignment step is optimal for the current centroids, and the centroid update is optimal for the current assignments. However, the complete clustering problem is non-convex: different initial centroids can produce different partitions and different final inertia values. K-Means therefore does not guarantee the global minimum of the objective.

Lloyd’s Algorithm and Objective

The objective minimized by K-Means is the within-cluster sum of squares:

WCSS = sum over clusters c of sum over points x in C_c of ||x - mu_c||^2

Here, WCSS is the within-cluster sum of squares, c identifies a cluster, C_c is the set of observations assigned to that cluster, x is one observation, mu_c is that cluster’s centroid, and ||x - mu_c||^2 is the squared Euclidean distance between the observation and its centroid. In scikit-learn, the fitted model exposes this value as inertia_.

Lloyd’s algorithm performs the following steps:

  1. Initialize centroids: Select k initial cluster centers.

  2. Assign points: Assign each observation to the closest centroid using Euclidean distance.

  3. Recompute centroids: Replace each centroid with the mean of its assigned observations.

  4. Repeat: Continue until assignments stop changing or max_iter is reached.

Each complete update does not increase the objective. If the assignments stabilize, the resulting partition is a local optimum; if the iteration limit is reached first, the algorithm may not yet have converged.

Initialization and Multiple Restarts

k-means++, scikit-learn’s default initialization method, selects initial centroids probabilistically while favoring observations far from centers already selected. This produces more widely separated starting centers than purely random selection, although it does not guarantee the global optimum. K-means++ is itself greedy because each new center is chosen using the current set of centers without reconsidering earlier choices.

The n_init parameter controls initialization attempts. With the default init="k-means++", n_init="auto" performs one run; setting it to an integer requests that many restarts. Scikit-learn retains the run with the lowest inertia. More restarts reduce the chance of selecting an especially poor local optimum but cannot prove that the result is globally optimal.

Complexity and Alternatives

For n observations, k clusters, d features, and T iterations, Lloyd’s algorithm takes O(T * n * k * d) time, or O(n * k * d) per iteration. MiniBatchKMeans is more suitable for very large datasets because it updates centroids using smaller batches rather than the entire dataset at once.

Method How it works Strengths Weaknesses When to use Typical scale or complexity
K-Means Repeatedly assigns points to nearest centroids and updates each centroid as a mean. Simple, fast, and scalable. Requires choosing k; sensitive to scaling, outliers, and initialization; favors spherical clusters. Numerical data with approximately spherical, similarly sized clusters. O(T * n * k * d) time; scales well with MiniBatchKMeans.
K-Medoids Uses an actual observation as each cluster center. More resistant to outliers than centroid means. More computationally expensive and still sensitive to initialization and scaling. Small or medium numerical datasets where representative observed points are useful. Can require O(n²) pairwise-distance storage.
Gaussian Mixture Models Models observations as a probabilistic mixture of Gaussian components. Supports soft assignments and elliptical clusters. Requires distributional assumptions and may converge slowly or overfit. Data plausibly generated from overlapping Gaussian populations. Cost grows with sample count, component count, and covariance parameterization.
DBSCAN or HDBSCAN Groups observations by local density and can label low-density points as noise. Handles irregular cluster shapes and does not require choosing k beforehand. Sensitive to neighborhood parameters and potentially costly in high dimensions. Irregularly shaped clusters, outliers, or noise where density structure matters. Neighbor-search cost can become significant on large datasets.

Common Pitfalls

  • Not scaling features: Features with larger numerical ranges can dominate the distance calculation.

  • Treating the elbow as exact: The inertia-versus-k curve often has several plausible choices rather than one unambiguous optimum.

  • Ignoring assumptions: K-Means works best for roughly spherical, similarly sized clusters.

  • Using categorical data directly: K-Means is designed for numerical distance-based data; use K-Modes for categorical variables.

  • Overlooking outliers and initialization sensitivity: Outliers can pull centroids, while poor initial centers can produce an inferior local optimum.

  • Interpreting clusters without profiling them: Examine feature distributions and assess whether each cluster has a meaningful practical interpretation.

16

Why does the Elbow Method matter for K-Means clustering?

The Elbow Method is a graphical heuristic for choosing k in K-Means by plotting inertia, or the within-cluster sum of squares, for several cluster counts and locating the bend where additional clusters provide diminishing returns. It matters because K-Means has no target labels that reveal the appropriate number of clusters. Its main trade-off is that it is simple and interpretable but remains a subjective heuristic rather than an exact selection rule.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

How the Elbow Method Works

K-Means minimizes the following objective:

Inertia(k) = sum from j=1 to k of sum over points x in cluster j of ||x - centroid_j||²

Here:

  • k is the number of clusters.

  • j identifies a cluster.

  • x is a data point assigned to that cluster.

  • centroid_j is the mean position of the cluster.

  • ||x - centroid_j||² is the squared Euclidean distance from the point to its centroid.

  • The sums aggregate squared distances within every cluster.

As k increases, inertia generally decreases because additional centroids allow points to lie closer to a center. The Elbow Method identifies the point where the curve changes from a steep decline to a flatter region. Before that elbow, extra clusters substantially improve compactness; after it, the improvement is usually smaller while model complexity continues to increase.

The elbow is therefore a visual judgment, not a mathematical cutoff. It is especially useful because inertia alone cannot answer how many clusters to choose: without a validation target, it would always favor the largest candidate k.

Connection to Lloyd’s Algorithm

Scikit-learn’s KMeans uses Lloyd’s algorithm to minimize inertia:

  1. Initialize centroids: The default k-means++ initialization selects relatively well-separated starting centers. After the first center is chosen, each subsequent center is selected with probability proportional to its squared distance from the closest existing center.

  2. Assign points: Each point is assigned to its nearest centroid.

  3. Recompute centroids: Each centroid becomes the mean of its assigned points.

  4. Repeat: Assignments and centroid updates continue until assignments stabilize or another stopping condition is reached.

Each iteration reduces or preserves inertia, but the algorithm can converge to a local optimum. The n_init parameter controls the number of initializations, and scikit-learn retains the result with the lowest inertia. In scikit-learn 1.5+, n_init="auto" uses one initialization for k-means++ and 10 for random initialization; setting an explicit value such as n_init=10 requests several restarts.

With n points, k clusters, and d features, each Lloyd iteration costs approximately O(n * k * d).

Choosing and Validating k

  • Inspect the inertia curve: Look for the bend where additional clusters produce relatively small reductions in inertia.

  • Use domain knowledge: Prefer a cluster count that has a meaningful interpretation in the application.

  • Check silhouette score: This compares each point’s mean intra-cluster distance with its mean distance to the nearest other cluster. Higher values generally indicate better-separated clusters.

  • Profile clusters: Examine feature distributions and application-specific meaning; mathematically compact clusters may still be uninformative.

  • Keep final evaluation separate: If repeatedly selecting k on a validation set, retain an untouched test set or use nested cross-validation.

The elbow and silhouette score are complementary: the elbow emphasizes diminishing returns, while silhouette measures separation more directly.

Limitations and Alternatives

K-Means is sensitive to feature scale, outliers, initialization, and cluster shape. It generally assumes roughly spherical, convex, similarly sized clusters. MiniBatchKMeans is an alternative for large datasets because it processes smaller batches.

Method How it works Strengths Weaknesses When to use Typical scale
K-Means Assigns points and repeatedly updates means Fast and easy to interpret Sensitive to scaling, outliers, and initialization Compact numerical clusters O(n * k * d) per iteration
K-Medoids Uses representative data points as centers Less influenced by extreme values Usually slower and still partition-based Outlier-sensitive data or representative observed centers PAM construction can reach O(n² * k)
Gaussian Mixture Model Assigns probabilistic membership Models elliptical clusters and uncertainty Requires stronger assumptions and more parameters Overlapping or soft cluster assignments About O(n * k * d) per EM iteration
DBSCAN/HDBSCAN Connects dense regions and can identify noise Finds irregular clusters and outliers Sensitive to density settings and less predictable at very large scale Irregular clusters or noisy data Often near O(n log n) with indexing; worst case can approach O(n²)

Common Pitfalls

  • Not scaling features: Standardize features whose numerical ranges are not comparable.

  • Treating the elbow as exact: Combine it with silhouette analysis, stability checks, domain knowledge, and cluster profiling.

  • Ignoring outliers: Investigate extreme values or consider K-Medoids.

  • Using K-Means on categorical data: Use k-modes or a method designed for categorical dissimilarities.

  • Interpreting clusters as classes: K-Means clusters are geometric groups, not automatically meaningful business categories.

  • Selecting k on the final test set: Keep model selection separate from final evaluation.

  • Ignoring convergence variability: Inspect n_iter_ and repeat with different random seeds to assess stability.

17

How does the curse of dimensionality affect K-Means clustering?

The curse of dimensionality describes how distances become less informative as the number of features grows, making meaningful groups harder to distinguish. It affects K-Means because assignments based on Euclidean distance can become unstable, arbitrary, or dominated by irrelevant features. The main trade-off is that K-Means remains computationally manageable, but its resulting clusters may not represent meaningful structure.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

Why High Dimensions Are Problematic

In low-dimensional data, nearby points often share similar characteristics. As dimensionality increases:

  • Coverage becomes sparse: with a fixed number of samples, points occupy a vanishing fraction of the available feature space.

  • Distances concentrate: under common data assumptions, pairwise distances become increasingly similar, reducing their ability to distinguish groups.

  • Nearest-centroid assignments lose meaning: a point may be almost equally distant from many centroids.

  • Noise gains influence: numerous uninformative features can outweigh a small number of meaningful ones.

  • Outliers have greater impact: because K-Means minimizes squared distances, extreme values can pull centroids substantially.

K-Means still minimizes its objective mathematically, but a low inertia value does not guarantee meaningful clusters. The underlying data may simply contain no useful cluster structure.

Lloyd’s Algorithm and Initialization

Lloyd’s algorithm repeatedly performs two steps:

  1. Assign points: assign every point to its nearest centroid.

  2. Update centroids: calculate each centroid as the mean of its assigned points.

The process repeats until assignments stop changing or another stopping criterion is reached. The objective is the within-cluster sum of squares:

inertia = sum(||x_i - μ_c(i)||²)

Here, x_i is point i, μ_c(i) is its assigned centroid, and ||...||² is the squared Euclidean distance.

Scikit-learn uses k-means++ initialization by default. It selects initial centroids with some separation, making them more likely to represent the data than purely random initialization. In scikit-learn 1.5+, n_init="auto" performs 1 initialization when init="k-means++" and 10 when init="random"; setting n_init to an integer explicitly requests that many restarts. The solution with the lowest inertia is retained. Nevertheless, K-Means converges to a local optimum rather than necessarily the global optimum.

Computational and Practical Effects

Each Lloyd iteration costs approximately O(n * k * d), where n is the number of samples, k is the number of clusters, and d is the number of features. Increasing dimensionality therefore increases computation and the cost of distance calculations.

K-Means also assumes compact, roughly spherical, similarly sized clusters, assumptions that can be difficult to satisfy in high-dimensional spaces. Practical mitigations include:

  • Standardize features so units and scales do not dominate distances.

  • Remove irrelevant or redundant features using domain knowledge, correlation analysis, or PCA.

  • Impute missing values before clustering because scikit-learn’s K-Means does not accept NaN values.

  • Use MiniBatchKMeans for large datasets when approximate clustering is acceptable.

  • Inspect cluster profiles before assigning a business or scientific interpretation.

PCA should generally be fitted only on training data when it is learned from the dataset. Although a final clustering model may be refitted on all validated data, preprocessing must not use validation or test information during model selection.

Alternatives for Difficult Cluster Structures

Algorithm How it works Strengths Weaknesses When to use
K-Means Groups points around mean centroids Fast and scalable Sensitive to scaling, outliers, initialization, and k Large datasets with compact, roughly spherical clusters
K-Medoids Uses actual data points as centers More robust to outliers Slower; still needs k Small or medium datasets with outliers
Gaussian Mixture Model Models clusters as overlapping probability distributions Supports elliptical clusters and soft assignments Strong distributional assumptions Gaussian-looking groups with varying density or overlap
DBSCAN/HDBSCAN Connects points according to local density Finds arbitrary shapes and detects noise; HDBSCAN handles variable density Density parameters can be difficult and performance can weaken in high dimensions Irregular clusters and noise

Common Pitfalls

  • Not scaling features: variables with larger numeric ranges dominate Euclidean distance.

  • Treating the elbow as exact: the elbow is a heuristic, not proof of the correct cluster count.

  • Using K-Means on categorical data: use a categorical-specific method such as k-modes.

  • Adding every available feature: irrelevant features weaken distance-based grouping.

  • Ignoring outliers: squared distances amplify their influence.

  • Interpreting labels without profiling them: cluster numbers have no inherent meaning.

  • Failing to check reproducibility: compare multiple seeds and stability metrics.

  • Leaking preprocessing information: fit scalers, imputers, and feature selectors only on training data.

18

Can K-Means cluster high-dimensional data effectively?

K-Means can cluster high-dimensional data, but its effectiveness often declines as dimensionality increases because distances may become less discriminative, irrelevant features can distort the result, and computation becomes more expensive. Its main trade-off is scalability versus its assumptions of compact, approximately spherical, similarly sized clusters and the need to choose k carefully.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

When K-Means Is Suitable

K-Means partitions observations by minimizing the within-cluster sum of squares, also called inertia:

WCSS = sum over all clusters of the sum of squared distances between each point and its cluster centroid.

  • Higher WCSS: Points are relatively far from their assigned centroids.

  • Lower WCSS: Points form more compact groups around their centroids.

  • The objective is optimized locally, so initialization and the chosen k affect the result.

High dimensionality introduces several potential problems:

  • Distance concentration: In many high-dimensional settings, pairwise Euclidean distances become increasingly similar, making nearest-centroid assignments less discriminative.

  • Irrelevant features: Noise dimensions can distort which points are considered close.

  • Computational cost: Each Lloyd iteration costs approximately O(n * k * d), where n is the number of samples, k is the number of clusters, and d is the number of features.

  • Sparse or weakly informative representations: Distances may fail to reflect meaningful similarity when most coordinates contribute little information.

K-Means can still work well when the data contains meaningful continuous features, the expected clusters are compact, and unnecessary dimensions are removed with techniques such as PCA.

Lloyd’s Algorithm

Scikit-learn’s KMeans follows Lloyd’s algorithm:

  1. Initialize k centroids using k-means++ by default.

  2. Assign every point to its nearest centroid.

  3. Recompute each centroid as the mean of its assigned points.

  4. Repeat the assignment and recomputation steps until assignments stabilize or another stopping condition is reached.

  5. Run multiple initializations and retain the solution with the lowest inertia.

k-means++ chooses initial centroids that are more separated than a completely random initialization, reducing the risk of starting with poorly distributed centers. Setting n_init=10 explicitly requests ten initializations; combined with a fixed random_state, this makes the result reproducible. Despite these restarts, K-Means converges to a local optimum rather than guaranteeing the global optimum.

Practical Strategy

A defensible workflow for high-dimensional data is:

  1. Split the data into a development portion and a final held-out evaluation portion.

  2. Fit a StandardScaler on the development data only.

  3. Optionally fit PCA on that same development data to reduce correlated or noisy dimensions.

  4. Fit K-Means for several candidate values of k.

  5. Compare inertia, silhouette score, stability across random seeds, and domain evidence using only the development data.

  6. Evaluate the selected pipeline on the held-out portion and profile cluster characteristics before interpreting them.

Feature scaling is important because K-Means uses Euclidean distance. A feature measured in thousands can otherwise dominate a feature measured in single digits. For very large datasets, MiniBatchKMeans reduces computation by updating centroids from small batches rather than processing the entire dataset in every iteration.

Limitations and Alternatives

Method How it works Strengths Weaknesses When to use
K-Means Assigns points to nearest mean centroid Fast and scalable Requires k; sensitive to scaling and outliers Compact, approximately spherical clusters
MiniBatchKMeans Updates centroids from random batches Faster on large datasets Less stable and potentially lower quality Very large datasets
k-medoids Uses actual observations as cluster centers More robust to certain noise and outlier effects Slower than K-Means Irregular clusters or smaller datasets
Gaussian Mixture Models Models clusters as probability distributions Accounts for covariance and cluster overlap More parameters and computational work Elliptical clusters with soft assignments
DBSCAN/HDBSCAN Groups points by density connectivity Finds irregular clusters without initially choosing k DBSCAN is sensitive to density parameters Arbitrary shapes and noise

Common Pitfalls

  • Not scaling features: Fit the scaler only on development data, normally inside a Pipeline.

  • Choosing k only from the elbow plot: Combine inertia, silhouette score, stability, and domain knowledge.

  • Tuning on the final test set: Select the pipeline and k using development data; reserve the held-out data for final evaluation.

  • Assuming clusters are real: Profile cluster characteristics and validate them with subject-matter expertise.

  • Using categorical features directly: K-Means assumes numeric distances; use k-modes or an appropriate encoding and modeling strategy.

  • Ignoring outliers: Extreme values can pull centroids substantially; inspect them or consider k-medoids.

  • Omitting reproducibility controls: Set random_state and use an explicit n_init value.

  • Confusing clusters with classes: K-Means is unsupervised and does not use target labels.

19

What is the silhouette coefficient in K-Means clustering?

The silhouette coefficient evaluates how well each point belongs to its assigned cluster by comparing its distance from that cluster with its distance from the nearest alternative cluster. It helps compare candidate values of k without requiring ground-truth labels. Its main trade-off is that higher scores favor compact, well-separated clusters, but the metric can favor the spherical, similarly sized clusters assumed by K-Means.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

How the Coefficient Is Calculated

For each sample i, scikit-learn’s default Euclidean-distance formulation is:

a(i) = mean distance from point i to other points in the same cluster

b(i) = smallest mean distance from point i to any other cluster

s(i) = (b(i) - a(i)) / max(a(i), b(i))

  • a(i) measures intra-cluster cohesion: the average distance to the point’s clustermates.

  • b(i) measures separation from the closest competing cluster.

  • i identifies the sample being evaluated, while s(i) is its individual silhouette value.

  • Dividing by max(a(i), b(i)) keeps the result between -1 and 1 and avoids division by zero.

  • The overall silhouette score is the mean of s(i) across all samples.

A value near 1 indicates a tightly grouped and well-separated cluster assignment, a value near 0 indicates a point near a cluster boundary, and a negative value indicates that the point may be closer to another cluster than to its assigned one. A singleton cluster receives 0 by convention. In scikit-learn, silhouette_score returns the overall mean, while silhouette_samples returns one value per point.

Using It With K-Means

A practical model-selection workflow is:

  1. Split the data into training, validation, and test sets.

  2. Fit StandardScaler on the training data only, then transform the validation and test data with that fitted scaler.

  3. Fit K-Means models for candidate values of k using the scaled training data.

  4. Predict validation assignments, calculate silhouette scores in the same scaled feature space, and select a reasonable k.

  5. Evaluate the selected model once on the held-out test set.

K-Means uses Lloyd’s algorithm:

  1. Initialize k centroids.

  2. Assign every point to its nearest centroid.

  3. Recompute each centroid as the mean of its assigned points.

  4. Repeat until assignments stop changing or another stopping condition is reached.

These updates reduce the within-cluster sum of squares, exposed as KMeans.inertia_, but they generally converge to a local optimum rather than the global optimum. The default init="k-means++" chooses separated initial centroids, while n_init=10 performs ten initializations and retains the run with the lowest inertia.

Each Lloyd iteration takes approximately O(n * k * d) time, where n is the sample count, k is the cluster count, and d is the feature count. K-Means does not build a pairwise-distance matrix, but silhouette evaluation considers pairwise distances and therefore typically requires O(n² * d) time. For large datasets, MiniBatchKMeans reduces fitting cost by updating centroids with subsets of the data.

Comparing Clustering Approaches

Silhouette scores should be considered alongside the inertia curve and domain knowledge. In particular, inertia generally decreases as k increases, so the elbow is more useful than choosing the model with the smallest absolute inertia.

Method How it works Strengths Weaknesses Typical use and scale
K-Means Assigns points to centroids and repeatedly updates their means Fast and simple Sensitive to scaling, initialization, and outliers; assumes roughly spherical clusters Large continuous datasets; O(n * k * d) per iteration
k-medoids Uses actual observations as cluster centers More resistant to outliers than means More expensive and still sensitive to initialization Moderate-sized data where robustness matters; PAM preprocessing can be O(n²)
Gaussian mixture model Estimates a probability distribution with soft assignments Handles elliptical clusters and probabilistic membership More computation and possible overfitting Moderate-sized continuous data; roughly O(n * k * d) per E-step for diagonal covariances
DBSCAN Connects dense regions reachable by a distance threshold Finds arbitrary-shaped clusters and noise Sensitive to density parameters and density variation Clustering without a fixed k; typically near O(n log n) with spatial indexing, but worst-case O(n²)
HDBSCAN Builds a cluster hierarchy and extracts stable clusters Handles varied densities and noise without fixed k More computationally intensive than K-Means Unknown k and non-spherical clusters; available as sklearn.cluster.HDBSCAN in scikit-learn 1.5+

Common Pitfalls

  • Skipping feature scaling: Large-scale features can dominate both K-Means assignments and silhouette distances.

  • Choosing k mechanically: The highest silhouette score is evidence, not proof; inspect cluster profiles and consider the elbow.

  • Evaluating only on training data: Held-out data can reveal that the selected clustering does not generalize well.

  • Ignoring outliers: K-Means centroids can be pulled toward distant observations.

  • Using unsuitable data: K-Means expects continuous numeric features and does not natively support missing or categorical values.

  • Overinterpreting the score: Silhouette measures geometric separation, not business meaning, causality, or semantic validity.

Interviewers commonly ask why K-Means is initialization-sensitive, how k-means++ helps, why scaling matters, and which alternatives support non-spherical clusters or greater resistance to outliers.

20

What is the difference between hard and soft clustering?

Hard clustering assigns each data point to exactly one cluster, whereas soft clustering represents a point’s membership across multiple clusters. Hard assignments are simple and interpretable but conceal ambiguity; soft assignments capture uncertainty and overlap but may be less interpretable and require a more detailed model.

Read full answer

Applies tomachine learning concepts and scikit-learn 1.5+ (Python 3.12)

How They Work

In hard clustering, each point belongs exclusively to its selected cluster. For example, a customer with membership probabilities of 0.62 and 0.38 could still receive only the label of the more likely cluster.

In soft clustering, every point has a vector of membership values. These values may be:

  • Probabilities: They sum to 1, as with the posterior responsibilities in a Gaussian Mixture Model.

  • Membership degrees: They lie between 0 and 1; some formulations also constrain them to sum to 1, while others do not.

A hard assignment can be derived from soft memberships by taking the largest value with argmax, but doing so discards the uncertainty represented by the other memberships.

A common hard-assignment formula for K-means is:

z_i = argmin_j ||x_i - μ_j||²

Here, x_i is data point i, μ_j is centroid j, and ||x_i - μ_j||² is their squared Euclidean distance. The expression argmin_j selects the cluster index z_i with the smallest distance.

A Gaussian Mixture Model computes soft assignments using:

r_ij = p(z_i = j | x_i) = [π_j N(x_i | μ_j, Σ_j)] / Σ_l [π_l N(x_i | μ_l, Σ_l)]

Here, r_ij is the posterior responsibility of point i for cluster j, and p(z_i = j | x_i) is the conditional probability of that cluster given the point. The symbol π_j is the mixture weight for cluster j, N is a Gaussian probability density, μ_j is the cluster mean, and Σ_j is its covariance matrix. The denominator sums over all candidate clusters l, ensuring that the responsibilities for each point sum to 1.

Hard Clustering with K-Means

K-means implements Lloyd’s algorithm:

  1. Choose k initial centroids. The scikit-learn default, k-means++, selects each new centroid with probability proportional to its squared distance from the closest centroid already chosen.

  2. Assign every point to its nearest centroid.

  3. Recompute each centroid as the mean of the points assigned to it.

  4. Repeat until assignments stabilize or the implementation reaches its convergence tolerance or max_iter limit.

  5. When n_init is an integer, run that many initializations and retain the solution with the lowest inertia. In scikit-learn 1.5+, n_init="auto" selects one initialization for k-means++ and ten for random initialization.

The inertia is the within-cluster sum of squares:

inertia = sum_j sum_(i:z_i=j) ||x_i - μ_j||²

It measures how tightly the points fit around their centroids. Each Lloyd iteration costs approximately O(n * k * d), where n is the number of points, k is the number of clusters, and d is the number of features. K-means converges to a local optimum, and MiniBatchKMeans can be more practical for very large datasets.

Comparison

Aspect Hard clustering Soft clustering
Membership Exactly one cluster label per point A vector of membership values or probabilities
Typical output A hard cluster label A membership vector; a hard label can be obtained with argmax
Typical algorithm K-means Gaussian Mixture Model or fuzzy c-means
Main strength Simple, fast, and easy to interpret Represents uncertainty, overlap, and gradual transitions
Main weakness Hides ambiguous or overlapping membership Can be less interpretable and require more parameters or model assumptions
Boundary behavior Creates abrupt boundaries Allows gradual transitions between groups
When to use Groups are expected to be mutually exclusive and a simple partition is sufficient Points may plausibly belong to several groups or uncertainty matters
Typical scale K-means uses approximately O(n * k * d) per iteration Model-dependent; fuzzy c-means is iterative, while a full-covariance GMM is generally more expensive per evaluation

Common Pitfalls

  • Skipping feature scaling: K-means distances are highly sensitive to features measured on different scales.

  • Choosing k mechanically: The elbow method is a heuristic rather than an exact answer; also examine silhouette scores and cluster profiles.

  • Ignoring model assumptions: K-means favors compact, roughly spherical clusters, while Gaussian Mixture Models assume underlying Gaussian distributions.

  • Treating probabilities as calibrated: Gaussian mixture responsibilities depend on model fit and assumptions; they are not automatically calibrated probabilities.

  • Using categorical features directly: Use suitable methods such as k-modes rather than encoding categories without considering their meaning.

  • Ignoring outliers: Extreme values can pull K-means centroids away from the main data distribution.

  • Interpreting labels as ground truth: Cluster numbers are arbitrary and should be profiled before assigning business meaning.

  • Leaking preprocessing information: When evaluating on held-out data, fit scalers and other learned transformations on the training partition only, using an sklearn pipeline.

21

How does mini-batch K-Means differ from standard K-Means?

Mini-batch K-Means is a scalable variant of K-Means that updates centroids from small batches of observations rather than processing the entire dataset in every full iteration. It targets the same within-cluster sum-of-squares objective as standard K-Means, often producing a useful clustering faster on large datasets, but with potentially less stable results and somewhat higher objective error.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

How It Works

Standard K-Means uses Lloyd’s algorithm:

  1. Initialize centroids: Select k initial centers, normally with k-means++.

  2. Assign points: Assign every observation to its nearest centroid using squared Euclidean distance.

  3. Recompute centroids: Replace each centroid with the mean of the observations assigned to it.

  4. Repeat: Continue until assignments stabilize or another stopping condition is reached.

The objective is:

WCSS = sum from i = 1 to n of ||x_i - c_(z_i)||²

Here, n is the number of observations, x_i is observation i, z_i is its assigned cluster, and c_(z_i) is that cluster’s centroid. This value is scikit-learn’s inertia_. Lloyd’s algorithm converges to a local optimum, not necessarily the global minimum.

Mini-batch K-Means follows a stochastic version of this process:

  • It samples a batch of b observations.

  • It assigns each sampled observation to a nearest centroid.

  • It incrementally updates the selected centroid using a running-mean-style, per-centroid learning rate.

  • It can perform a reassignment step governed by reassignment_ratio, which limits how many samples are assigned to any one cluster and can add computation.

  • It repeats until the iteration limit or a configured early-stopping condition is reached.

Standard vs. Mini-Batch

Aspect Standard K-Means Mini-Batch K-Means
Data processed All n observations per iteration A batch of b observations per update
Centroid update Recomputed from complete cluster means Updated incrementally from sampled observations
Per-update complexity O(n * k * d) O(b * k * d)
Objective value Usually lower inertia and more stable centroids Inertia may be slightly higher and centroids may vary more
Best fit Small or medium datasets Large datasets where full-batch processing is expensive
Memory behavior Distance calculations can be chunked Avoids routine full-batch distance calculations, although the dataset remains in memory and reassignment adds overhead

Here, k is the number of clusters and d is the number of features. Mini-batch K-Means is therefore useful when the cost of repeatedly assigning every observation dominates.

Initialization and Evaluation

k-means++, the default initializer in scikit-learn, chooses the first centroid randomly and selects later centroids with greater probability when they are far from existing centers. This reduces the likelihood of a poor initialization.

The n_init parameter specifies the number of independent initializations, and scikit-learn retains the run with the lowest inertia. Set it explicitly to an integer when comparing experiments. In scikit-learn 1.5+, both classes follow the same n_init="auto" policy: it resolves to one run for k-means++ initialization and ten runs for random initialization.

Choose k using several signals:

  • Elbow curve: Look for diminishing reductions in inertia.

  • Silhouette score: Higher values generally indicate better-separated clusters.

  • Domain knowledge: Check whether the resulting clusters have a meaningful interpretation.

The elbow is only a heuristic. Mini-batch solutions may also vary across random seeds because different samples produce different centroid updates.

Practical Guidance

  • Standardize features with StandardScaler, or consider RobustScaler when outliers are present.

  • If evaluating on held-out data, fit the scaler only on the training partition and transform the validation or test partition with that fitted scaler.

  • Handle missing values before clustering because scikit-learn’s K-Means implementations do not accept NaN values.

  • Fix random_state for reproducibility and compare multiple seeds when judging stability.

  • Use standard K-Means when obtaining the lowest inertia on a manageable dataset matters more than training speed; use mini-batch K-Means when dataset size makes repeated full-batch updates costly.

Common Pitfalls

  • Not scaling features: Features with larger numeric ranges dominate Euclidean distances.

  • Treating the elbow as exact: Validate several values of k and inspect whether every cluster is useful.

  • Ignoring outliers: Extreme values can pull centroids away from the main data distribution.

  • Using categorical variables directly: Use k-modes or another method designed for categorical data.

  • Missing rare groups: Mini-batch sampling may underrepresent small clusters, so compare seeds and inspect cluster sizes.

  • Overinterpreting clusters: Clustering is exploratory and does not prove that natural categories exist.

  • Ignoring alternatives: Consider k-medoids for robustness, Gaussian Mixture Models for elliptical or probabilistic clusters, and DBSCAN or HDBSCAN for irregular shapes and noise.

Common interview follow-ups include why k-means++ is used, whether Lloyd’s algorithm guarantees a global optimum, how inertia differs from silhouette score, and when mini-batch K-Means is preferable to full-batch K-Means.

22

How can K-Means be optimized for very large datasets?

K-Means partitions data into k clusters by minimizing the distance between each point and its cluster centroid. For very large datasets, MiniBatchKMeans reduces computation by updating centroids from small batches rather than the entire dataset. The main trade-off is faster, more scalable clustering at the cost of less stable results and potentially higher inertia.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

How Lloyd’s Algorithm Works

K-Means minimizes the within-cluster sum of squares:

WCSS = sum(i = 1 to n) ||x_i - mu_c(i)||²

  • n is the number of data points.

  • x_i is point i.

  • mu_c(i) is the centroid of the cluster assigned to point i.

  • ||...||² is the squared Euclidean distance.

Lloyd’s algorithm proceeds as follows:

  1. Initialize centroids: Select k initial centroids. Scikit-learn uses k-means++ by default, selecting initial points with some separation to improve convergence.

  2. Assign points: Assign every point to its nearest centroid.

  3. Recompute centroids: Replace each centroid with the mean of the points assigned to that cluster.

  4. Repeat: Continue until assignments stop changing, convergence is detected, or max_iter is reached.

The result depends on initialization and generally converges to a local rather than global optimum. Running several initializations and keeping the result with the lowest inertia reduces this risk.

Large-Data Optimizations

Approach How it works Strengths Weaknesses Typical scale
KMeans Full-batch Lloyd iterations Accurate centroids and stable results Expensive for repeated full-data passes Medium to large in-memory data
MiniBatchKMeans Updates centroids using small batches Much faster and suitable for streaming-style processing More variable results and slightly higher inertia Very large datasets
PCA/SVD plus K-Means Clusters in a reduced feature space Lower memory and computational cost Reduced dimensions may discard useful structure High-dimensional data
GPU K-Means Runs distance calculations and updates on a GPU High throughput with large batches Requires compatible libraries and hardware; results may vary Specialized large-scale workloads

Additional optimizations include:

  • Reduce iterations: Lower max_iter and use a reasonable tol when quick approximate results are acceptable.

  • Control restarts: KMeans supports several initializations through n_init; scikit-learn keeps the run with the lowest inertia. With k-means++, n_init="auto" currently means one initialization, so use an explicit value such as n_init=10 for several restarts.

  • Reduce dimensions: Apply PCA or TruncatedSVD before clustering, while fitting the transformation on training data only.

  • Use batch processing: MiniBatchKMeans provides batch_size and incremental fitting options for data delivered in chunks.

  • Scale features: K-Means uses Euclidean distance, so features with larger numeric ranges can dominate the result.

Choosing and Validating k

The elbow method plots inertia across several values of k. Inertia always decreases as k grows, so look for a point where improvements become smaller rather than treating the elbow as exact. The silhouette score measures how well points fit their assigned clusters; values near 1 indicate strong separation, while values near 0 indicate weak separation.

Cluster quality should also be checked by profiling each group’s feature distributions and domain meaning. A visually low-inertia solution is not automatically useful.

Code Example

import time

import numpy as np
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans, MiniBatchKMeans
from sklearn.model_selection import train_test_split

# Synthetic large-scale dataset with a fixed seed.
X, _ = make_blobs(
    n_samples=20_000,
    n_features=2,
    centers=5,
    cluster_std=1.5,
    random_state=42,
)

# Split before fitting the scaler to avoid evaluation leakage.
X_train, X_test = train_test_split(
    X, test_size=0.2, random_state=42
)

def build_pipeline(algorithm, k):
    if algorithm == "KMeans":
        cluster = KMeans(
            n_clusters=k,
            init="k-means++",
            n_init=5,
            max_iter=300,
            random_state=42,
        )
    else:
        cluster = MiniBatchKMeans(
            n_clusters=k,
            init="k-means++",
            n_init=5,
            batch_size=2048,
            max_iter=100,
            random_state=42,
        )

    return Pipeline([
        ("scaler", StandardScaler()),
        ("cluster", cluster),
    ])

for k in range(2, 7):
    for algorithm in ("KMeans", "MiniBatchKMeans"):
        model = build_pipeline(algorithm, k)

        started = time.perf_counter()
        model.fit(X_train)
        elapsed = time.perf_counter() - started

        scaler = model.named_steps["scaler"]
        cluster = model.named_steps["cluster"]
        X_test_scaled = scaler.transform(X_test)
        labels = cluster.predict(X_test_scaled)

        silhouette = silhouette_score(X_test_scaled, labels)
        sizes = np.bincount(labels, minlength=k)

        print(
            f"k={k}, algorithm={algorithm}, "
            f"inertia={cluster.inertia_:.2f}, "
            f"silhouette={silhouette:.3f}, "
            f"fit_time={elapsed:.3f}s, sizes={sizes}"
        )

Complexity and Practical Guidance

  • Full K-Means: Each iteration is approximately O(n * k * d), where n is the number of points, k the number of clusters, and d the number of features.

  • MiniBatchKMeans: Each update is approximately O(m * k * d), where m is the batch size.

  • Memory: Standard KMeans requires the dataset in memory, typically O(n * d), plus O(k * d) for centroids.

  • Reproducibility: Set random_state for repeatable comparisons.

  • Missing values: K-Means does not directly support them; use an appropriate imputer inside a Pipeline.

  • Outliers: They can pull centroids toward themselves, so inspect or robustly preprocess extreme values.

Common Pitfalls

  • Not scaling features can cause high-variance variables to dominate clustering.

  • Treating the elbow as an exact answer ignores the lack of an objective ground-truth k.

  • Using K-Means directly on categorical variables is inappropriate; consider k-modes or another categorical method.

  • Interpreting clusters without profiling them can produce misleading or unusable groups.

  • For irregular clusters, outliers, or clusters with very different densities, consider k-medoids, Gaussian Mixture Models, DBSCAN, or HDBSCAN.

23

Why does K-Means++ improve K-Means initialization?

K-Means++ improves ordinary K-Means by choosing initial centroids that are more likely to be widely separated, reducing the chance of converging to a poor local optimum. It changes only the initialization step; assignment and centroid-update steps remain the same. The main trade-off is slightly higher initialization cost, and it still does not guarantee the globally optimal clustering.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

Core Objective

K-Means partitions observations into k groups by minimizing the within-cluster sum of squares, also called inertia:

J = sum over all points of ||x_i - mu_c(i)||²

  • x_i is the feature vector for observation i.

  • c(i) is the cluster assigned to observation i.

  • mu_c(i) is the mean of that cluster.

  • ||...||² is the squared Euclidean distance.

  • J is the total inertia; lower values indicate tighter clusters.

How K-Means++ Works

K-Means++ uses a probability-based initialization procedure:

  1. Select the first centroid uniformly at random from the observations.

  2. Calculate each point’s squared distance to its nearest selected centroid.

  3. Select subsequent centroids with probability proportional to those squared distances.

  4. Repeat until k centroids have been selected.

  5. Continue with Lloyd’s algorithm.

Consequently, points in sparse or distant regions are more likely to become centroids, while points close to an existing centroid have a lower chance of being selected. Scikit-learn’s greedy implementation samples several candidates for each new centroid using this probability rule and retains the candidate that most reduces the initialization objective.

Lloyd’s Algorithm

After initialization, scikit-learn performs Lloyd’s algorithm:

  1. Assign each observation to its nearest centroid using Euclidean distance.

  2. Recompute each centroid as the mean of the observations assigned to it.

  3. Repeat until assignments stop changing or another stopping condition is reached.

  4. Return the final centroids and cluster assignments.

Each iteration has O(n × k × d) time complexity, where n is the number of observations, k is the number of clusters, and d is the number of features. Lloyd’s algorithm converges to a local optimum rather than guaranteeing the global optimum.

Why It Improves Ordinary K-Means

With random initialization, several centroids may land in the same dense region while an important sparse region remains unrepresented. K-Means++ reduces this risk by encouraging centroid separation.

  • Better starting position: It often begins closer to a useful low-inertia solution.

  • Less redundant initialization: Centroids are less likely to compete in the same area, although final empty clusters remain possible.

  • Lower observed inertia: Under comparable initialization budgets, it often produces tighter clusters than an unfavorable random start.

  • Not a guarantee: A dataset can still produce a poor local optimum, and the result remains sensitive to the data.

In scikit-learn, init="k-means++" is the default. The n_init parameter controls how many independent initializations are attempted; using multiple restarts and retaining the lowest-inertia result reduces dependence on one initial seed.

Practical Guidance and Alternatives

  • Scale features: Standardization prevents features with larger numerical ranges from dominating Euclidean distance.

  • Choose k carefully: Use inertia, the elbow method, silhouette score, and domain knowledge rather than treating the elbow as exact.

  • Use MiniBatchKMeans for large data: It updates centroids from small batches and reduces computation, though results may be less stable.

  • Profile clusters: Examine feature distributions and domain meaning before assigning an interpretation.

  • CPU versus GPU: Standard scikit-learn K-Means is CPU-oriented; MiniBatchKMeans is usually the simpler choice for large datasets.

Algorithm How it works Strengths Weaknesses When to use Typical complexity or scale
K-Means Repeatedly assigns points and updates centroids as means Fast and scalable Requires k; sensitive to scaling and outliers Approximately spherical, similarly sized clusters O(n_k_d) per iteration
K-Medoids Partitions around representative data points Less sensitive to outliers than means Slower than K-Means Small or medium datasets needing robust centers Roughly O(n²) preprocessing for PAM; medium-sized data
Gaussian Mixture Model Uses probabilistic membership and EM updates Models elliptical clusters and overlap More computationally expensive Elliptical or overlapping clusters O(n_k_d²) per full-covariance EM iteration
DBSCAN/HDBSCAN Connects dense regions and identifies noise Finds arbitrary-shaped clusters Density-related parameter assumptions Cluster structures with noise or irregular shapes Often O(n log n) with spatial indexing; implementation-dependent

Common Pitfalls

  • Not scaling features: Distance-based assignments can become misleading when units differ.

  • Using categorical features directly: K-Means is intended for numerical data; use k-modes for categorical data.

  • Assuming spherical clusters: K-Means struggles with elongated, irregular, or very differently sized groups.

  • Ignoring outliers: Extreme values can pull centroids away from the main data distribution.

  • Selecting k only from inertia: Inertia generally decreases as k increases, so consider silhouette score and domain knowledge too.

  • Overinterpreting clusters: Cluster labels have no inherent meaning until their feature profiles and domain context are examined.

24

How can K-Means clustering be made more computationally efficient?

K-Means partitions unlabeled data into k clusters by repeatedly assigning points to centroids and updating each centroid to its cluster’s mean. Computational efficiency can be improved with MiniBatchKMeans, dimensionality reduction, fewer initialization restarts, or smaller datasets, with the main trade-off being faster execution versus potentially lower clustering quality.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12, NumPy 2.x)

How Lloyd’s Algorithm Works

K-Means minimizes the within-cluster sum of squares, also called inertia:

inertia = Σ_i ||x_i - μ_(c_i)||²

Here, i indexes the observations, x_i is observation i, c_i is its assigned cluster, μ_c is the mean centroid of cluster c, and ||...||² is the squared Euclidean distance. The summation adds this distance over every observation.

Lloyd’s algorithm performs these steps:

  1. Initialize k centroids, commonly with k-means++.

  2. Assign every point to its nearest centroid.

  3. Recompute each centroid as the mean of its assigned points.

  4. Repeat until assignments stabilize or another convergence criterion is reached.

K-means++ tends to select well-separated initial centroids and reduces the risk of a poor starting configuration. Because initialization affects the result, set n_init to an integer such as 10 to run several restarts and retain the run with the lowest inertia. In scikit-learn 1.5+, n_init="auto" uses one restart with the default init="k-means++"; it does not itself request many restarts. K-Means converges to a local optimum rather than guaranteeing a global optimum.

Main Efficiency Strategies

  • Use MiniBatchKMeans: Updates centroids from small batches instead of processing the complete dataset in every update. This is useful for large datasets when an approximate solution is acceptable.

  • Reduce dimensionality: PCA or feature selection lowers d, the number of features. Fit any learned transformation only on the training partition to avoid holdout leakage.

  • Reduce restarts: Lowering n_init reduces runtime but can produce higher inertia and less stable clusters.

  • Reduce k or sample size: Fewer centroids or observations reduce computation, but may discard useful detail.

  • Use optimized implementations: Avoid Python loops over individual observations and distances; scikit-learn uses compiled implementations.

  • Control stopping criteria: A smaller max_iter reduces runtime but may terminate before convergence, while tol determines how small a centroid movement is considered convergence.

Complexity and Trade-offs

For n observations, k centroids, and d features, one full K-Means iteration costs approximately O(n × k × d). Each of the n_init restarts performs its own iterations. Excluding the input data, working storage is approximately O(n + k × d) for labels and centroids.

A MiniBatchKMeans update using batch size b costs approximately O(b × k × d). Total runtime still depends on the number of updates and convergence, while the resulting clustering is generally less precise than full K-Means.

Code Example

import time

import numpy as np
from sklearn.cluster import KMeans, MiniBatchKMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

X, _ = make_blobs(
    n_samples=3000,
    n_features=2,
    centers=4,
    cluster_std=1.0,
    random_state=42,
)

# Keep held-out observations separate from fitted preprocessing and clustering.
X_train, X_test = train_test_split(
    X, test_size=0.30, random_state=42
)

full_times = {}

for k in range(2, 7):
    model = Pipeline([
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=k,
            n_init=10,
            random_state=42,
        )),
    ])

    started = time.perf_counter()
    model.fit(X_train)
    elapsed = time.perf_counter() - started
    full_times[k] = elapsed

    scaler = model.named_steps["scaler"]
    estimator = model.named_steps["kmeans"]
    scaled_train = scaler.transform(X_train)
    labels = estimator.labels_

    print(
        f"k={k}: inertia={estimator.inertia_:.2f}, "
        f"silhouette={silhouette_score(scaled_train, labels):.3f}, "
        f"time={elapsed:.3f}s, "
        f"cluster_sizes={np.bincount(labels, minlength=k).tolist()}"
    )

# Approximate alternative for a large dataset.
mini_model = Pipeline([
    ("scaler", StandardScaler()),
    ("kmeans", MiniBatchKMeans(
        n_clusters=4,
        batch_size=512,
        n_init=10,
        max_iter=100,
        random_state=42,
    )),
])

started = time.perf_counter()
mini_model.fit(X_train)
mini_elapsed = time.perf_counter() - started

mini_scaler = mini_model.named_steps["scaler"]
mini_estimator = mini_model.named_steps["kmeans"]
scaled_train = mini_scaler.transform(X_train)
mini_labels = mini_estimator.labels_
test_labels = mini_model.predict(X_test)

print(
    f"MiniBatchKMeans: "
    f"silhouette={silhouette_score(scaled_train, mini_labels):.3f}, "
    f"time={mini_elapsed:.3f}s, "
    f"test_cluster_sizes={np.bincount(test_labels, minlength=4).tolist()}"
)
print(f"Full K-Means time for k=4: {full_times[4]:.3f}s")

Alternatives

Algorithm How it works Strengths Weaknesses Typical complexity or scale
K-Medoids Uses observations as cluster centers More robust to noise Can be memory-intensive Straightforward implementations require O(n²) pairwise-distance storage
Gaussian Mixture Model Models probabilistic clusters Soft assignments and elliptical clusters More parameters and iterative fitting Diagonal-covariance EM is about O(n × k × d) per iteration; medium-sized datasets
DBSCAN Connects density-reachable observations Finds arbitrary shapes and noise Sensitive to density parameters Often O(n log n) with spatial indexing, but O(n²) worst case
HDBSCAN Builds a density hierarchy Handles varied densities Higher memory use and implementation complexity Best suited to small-to-medium datasets; runtime is implementation-dependent

Common Pitfalls

  • Not scaling features: Large-scale features dominate Euclidean distance; use StandardScaler before K-Means.

  • Treating the elbow as exact: Inspect inertia, silhouette scores, cluster sizes, and domain usefulness rather than treating one value of k as definitive.

  • Ignoring outliers: Means are pulled toward extreme observations.

  • Using categorical data directly: K-Means is intended for numerical vectors; consider k-modes or suitable encoding.

  • Assuming spherical, similar-sized clusters: K-Means performs poorly when clusters differ substantially in shape, density, or size.

  • Interpreting clusters without profiling them: Examine feature distributions and validate the clusters’ practical usefulness.

  • Leaking held-out data: Fit scaling, PCA, and other learned preprocessing only on training data.

Common interview follow-ups include how k-means++ works, why inertia alone cannot select k, how MiniBatchKMeans differs from full K-Means, and when DBSCAN or a Gaussian Mixture Model is preferable.

25

How do you verify that K-Means clustering has converged?

K-Means convergence means Lloyd’s algorithm has reached a stable solution rather than changing substantially between iterations. In scikit-learn, n_iter_ < max_iter confirms that the convergence tolerance was reached before the iteration limit; n_iter_ == max_iter is inconclusive. The main trade-off is that convergence identifies a local optimum, not necessarily the best or most meaningful clustering.

Read full answer

Applies toscikit-learn 1.5+ and NumPy 2.x (Python 3.12)

Convergence Criteria

K-Means uses Lloyd’s algorithm:

  1. Initialize k centroids.

  2. Assign every observation to its nearest centroid.

  3. Recompute each centroid as the mean of its assigned observations.

  4. Repeat until the assignments and centroids stabilize.

Conceptually, assignments that remain unchanged form a fixed point. Operationally, scikit-learn stops when its centroid-shift test satisfies the relative tol threshold, whose default is 1e-4, or when max_iter is reached.

  • n_iter_ < max_iter: The tolerance was satisfied before the iteration limit.

  • n_iter_ == max_iter: Inconclusive, because convergence may have occurred on the final permitted iteration.

  • If inconclusive: Rerun with a larger max_iter and the same random_state. Unchanged assignments and inertia provide practical confirmation.

K-Means minimizes inertia, also called the within-cluster sum of squares:

WCSS = sum_i ||x_i - c_(z_i)||^2

Here, x_i is observation i, z_i is its assigned cluster, and c_(z_i) is that cluster’s centroid.

Initialization and Complexity

The default init="k-means++" first selects a random centroid and then selects subsequent centroids with greater probability near points far from existing centroids. In scikit-learn 1.5+, n_init="auto" resolves to 1 run for the default k-means++ initialization and 10 runs for init="random"; scikit-learn retains the restart with the lowest inertia. The result still depends on initialization and is only a local optimum.

Each Lloyd iteration has O(n * k * d) time complexity, where n is the number of observations, k the number of clusters, and d the number of features. For large datasets, MiniBatchKMeans reduces computation by updating centroids from subsets of observations.

Interpreting the Result

Convergence does not establish that k is appropriate or that the clusters are useful. Compare inertia and silhouette score across several values of k, but treat the elbow as a heuristic and profile clusters using domain knowledge.

Standardize numerical features measured on different scales, handle missing values and outliers, and do not use K-Means directly on categorical data; use a categorical-specific method such as k-modes. K-Means also favors roughly spherical, similarly sized clusters.

Alternatives

Method How it works Strengths Weaknesses Typical scale
K-medoids Uses observations as centers Interpretable; more outlier-resistant Expensive at scale Small or medium data; exact PAM is roughly O(n² * k)
Gaussian mixture Models clusters as probability distributions Soft assignments; elliptical clusters Sensitive to covariance assumptions About O(n * k * d²) per iteration
DBSCAN Connects dense regions Arbitrary shapes and noise detection Sensitive to varying densities O(n²) worst case; faster with spatial indexing
HDBSCAN Builds a density hierarchy Handles variable densities and noise More memory and computation Superlinear time and substantial memory

Code Example

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

X, _ = make_blobs(
    n_samples=300,
    n_features=2,
    centers=3,
    cluster_std=1.5,
    random_state=42,
)

# Keep the test set separate from fitting and model selection.
X_train, X_test = train_test_split(
    X, test_size=0.2, random_state=42
)

models = {}

for k in (2, 3, 4):
    model = Pipeline([
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=k,
            n_init=10,
            max_iter=300,
            tol=1e-4,
            random_state=42,
        )),
    ])
    model.fit(X_train)

    kmeans = model.named_steps["kmeans"]
    scaled_train = model[:-1].transform(X_train)
    status = (
        "converged before max_iter"
        if kmeans.n_iter_ < kmeans.max_iter
        else "inconclusive: max_iter reached"
    )

    print(
        f"k={k}, iterations={kmeans.n_iter_}, status={status}, "
        f"inertia={kmeans.inertia_:.3f}, "
        f"silhouette={silhouette_score(scaled_train, kmeans.labels_):.3f}, "
        f"sizes={np.bincount(kmeans.labels_, minlength=k)}"
    )
    models[k] = model

# The pipeline scales X_test before assigning clusters.
test_labels = models[3].predict(X_test)
print("Test cluster sizes:", np.bincount(test_labels, minlength=3))

Common Pitfalls

  • Treating n_iter_ == max_iter as definite failure: It is inconclusive; rerun with a larger limit and compare labels and inertia.

  • Ignoring feature scale or outliers: Both can materially change the clusters.

  • Using K-Means on categorical data: Use k-modes or another suitable method.

  • Choosing k from the elbow alone: Combine inertia, silhouette analysis, domain knowledge, and cluster profiling.

  • Equating convergence with optimality: Initialization, random seeds, and unsuitable features can produce poor local optima.

  • Fitting the scaler on all data: Fit preprocessing only on training data to avoid leakage.

26

How should initial centroids be selected for K-Means clustering?

Initial centroid selection should place the k starting centers in promising, distinct regions of the data because Lloyd’s algorithm can converge to different local optima depending on where it starts. In scikit-learn, k-means++ is the preferred default over purely random initialization, while multiple restarts reduce the risk of selecting one poor run. The main trade-off is additional computation for better seeding and more restarts versus a lower chance of obtaining a poor clustering.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

How Initialization Affects the Result

K-Means minimizes the within-cluster sum of squares:

inertia = sum(||x_i - c_(z_i)||²)

Here, i indexes observations, x_i is observation i, z_i is its assigned cluster, and c_(z_i) is that cluster’s centroid. The norm is Euclidean distance, so inertia is the total squared distance of observations from their assigned centroids.

Lloyd’s algorithm monotonically reduces this objective from a given starting configuration, but it normally converges to a local rather than guaranteed global optimum. Initialization therefore affects which optimum is reached. Good starting centers should:

  • Lie in regions containing observations.

  • Represent different parts of the dataset.

  • Avoid concentration in one dense area.

  • Reduce the chance of an unstable or poor partition.

Choosing Initial Centroids

  1. Standardize the features first. K-Means uses Euclidean distance, so features measured on very different scales can dominate centroid placement.

  2. Prefer init="k-means++" for unstructured data. It selects the first center randomly from the observations. In the classical k-means++ rule, each later candidate is sampled with probability proportional to its squared distance from the closest selected center.

  3. Account for scikit-learn’s greedy refinement. With the default n_local_trials=None, scikit-learn evaluates several local seeding candidates for each new center and greedily chooses the candidate that reduces inertia.

  4. Use several restarts. Set n_init to an integer such as 10; scikit-learn retains the run with the lowest inertia. The n_init="auto" setting uses one run for k-means++ and ten for random initialization, so an explicit integer is preferable when several k-means++ restarts are desired.

  5. Set random_state for reproducibility. A fixed seed does not guarantee the global optimum, but it makes repeated runs reproducible.

  6. Use domain knowledge cautiously. If suitable starting regions are known, provide an array of k centers with shape (k, n_features) through init. An array initialization is run once, so use n_init=1 and compare it with other configurations rather than assuming it is necessarily superior.

Lloyd’s Algorithm

  1. Initialize k centroids using the selected strategy.

  2. Assign each observation to its nearest centroid.

  3. Recompute each centroid as the mean of its assigned observations.

  4. Repeat until assignments stabilize or a stopping criterion is reached.

Each iteration has approximately O(n × k × d) time complexity, where n is the number of observations, k is the number of clusters, and d is the number of features. For large datasets, consider MiniBatchKMeans, which processes subsets of observations per iteration and can reduce computation and memory requirements.

Limitations and Alternatives

Algorithm How It Works Strengths Weaknesses When to Use
K-Means Assigns observations to centroids and updates their means Fast and relatively scalable Requires choosing k; sensitive to scaling and outliers; favors compact, roughly spherical, similar-sized clusters Numerically structured data with plausible centroids
K-Medoids Uses representative observations as cluster centers More robust to outliers Slower and more memory-intensive Data where actual observations should represent groups
Gaussian Mixture Makes probabilistic, soft assignments Models overlapping groups and uncertainty Requires stronger distributional assumptions Elliptical or overlapping clusters
DBSCAN/HDBSCAN Connects dense regions and identifies noise Finds irregular cluster shapes Sensitive to density-related settings Irregular clusters or substantial noise

K-Means also does not directly support missing values and is generally inappropriate for categorical data; use k-modes or another method designed for mixed and categorical features.

Common Pitfalls

  • Not scaling features: Large-range variables dominate the Euclidean-distance objective.

  • Using one initialization: Multiple restarts reduce sensitivity to an unlucky starting configuration.

  • Treating the elbow as exact: It suggests candidate values of k, not a uniquely correct answer.

  • Ignoring empty or unstable clusters: Inspect cluster sizes, convergence behavior, and stability across seeds.

  • Interpreting clusters without profiling them: Analyze feature distributions and domain meaning before assigning business significance.

  • Typical follow-ups: Why does K-Means converge to a local optimum? How would you choose k? When are K-Medoids or density-based methods preferable?

27

How do you validate K-Means clustering results?

K-Means validation checks whether the resulting clusters are compact, stable, reproducible, and meaningful for the intended application. It combines internal metrics such as inertia and silhouette score with external labels when available and stability or domain checks; the main trade-off is that geometrically compact clusters may still lack practical or semantic meaning.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

What K-Means Produces

K-Means minimizes the within-cluster sum of squares:

WCSS = sum from j = 1 to k, sum for x in Cj of ||x - mu_j||²

  • k: Number of clusters.

  • Cj: Set of points assigned to cluster j.

  • mu_j: Centroid, or mean, of cluster j.

  • ||x - mu_j||²: Squared Euclidean distance between point x and its centroid.

  • The outer and inner sums add the squared distances across every cluster and every assigned point.

Lloyd’s algorithm performs the following steps:

  1. Initialize k centroids, using k-means++ by default in scikit-learn.

  2. Assign each point to its nearest centroid.

  3. Recompute each centroid as the mean of its assigned points.

  4. Repeat until assignments stabilize or another stopping condition is reached.

Each iteration has approximately O(n * k * d) time complexity, where n is the number of points, k the number of clusters, and d the number of features. K-Means converges to a local optimum, so initialization matters.

The n_init parameter controls how many initializations are tried, with the result having the lowest inertia. For several restarts, use a number such as n_init=10; with the default init="k-means++", n_init="auto" performs one initialization.

How Results Are Validated

Validation method What it checks Interpretation
Inertia Within-cluster compactness Lower is better for a fixed dataset and k, but it normally decreases as k increases
Silhouette score Separation and cohesion across clusters Ranges from approximately -1 to 1; higher is generally better
Adjusted Rand Index Agreement with known class labels Useful for labeled benchmarks; 1 indicates perfect agreement
Normalized Mutual Information Shared information with known labels Useful when true groups are available but labels may overlap
Resampling stability Whether similar partitions appear across samples or perturbations Persistent cluster assignments indicate stronger reproducibility
Domain validation Whether groups are actionable and interpretable Often the decisive business or scientific check

A holdout set can assess how well centroids and assignments generalize, but splitting does not make unsupervised clustering inherently “correct.” Stability analysis, often using bootstrap or perturbed samples, is usually more informative.

Choosing k and Assessing Stability

The elbow method plots inertia against k and looks for a sharp change in the curve. The elbow is not an exact statistical test, so it should be supported by silhouette score, the gap statistic, stability analysis, and domain constraints.

K-Means is most suitable when clusters are:

  • Roughly spherical.

  • Similar in size and density.

  • Separated in scaled feature space.

  • Represented by continuous numerical features.

It is sensitive to outliers, feature scaling, initialization, and non-spherical cluster shapes. Alternatives include k-medoids for robustness to outliers, Gaussian mixture models for elliptical or probabilistic clusters, and DBSCAN or HDBSCAN for irregular groups and density-based discovery. For large datasets, MiniBatchKMeans reduces training cost, although it may produce less stable results.

Code Example

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import (
    adjusted_rand_score,
    silhouette_score,
)
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

# Synthetic data with known generating labels for external validation.
X, y_true = make_blobs(
    n_samples=600,
    centers=3,
    cluster_std=1.0,
    random_state=42,
)

# Split before fitting the scaler or clustering model.
X_train, X_test, y_train, y_test = train_test_split(
    X,
    y_true,
    test_size=0.2,
    random_state=42,
)

records = []

for k in range(2, 7):
    model = Pipeline([
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=k,
            init="k-means++",
            n_init=10,
            random_state=42,
        )),
    ])

    model.fit(X_train)

    train_labels = model.predict(X_train)
    test_labels = model.predict(X_test)

    # Evaluate in the same scaled feature space used by K-Means.
    X_test_scaled = model.named_steps["scaler"].transform(X_test)

    # Pipeline.score delegates to KMeans.score, which is negative inertia.
    validation_inertia = -model.score(X_test)
    train_inertia = model.named_steps["kmeans"].inertia_

    if 2 <= len(np.unique(test_labels)) < len(test_labels):
        silhouette = silhouette_score(X_test_scaled, test_labels)
    else:
        silhouette = float("nan")

    ari = adjusted_rand_score(y_test, test_labels)
    sizes = np.bincount(test_labels, minlength=k)

    records.append((k, silhouette))
    print(
        f"k={k}, train_inertia={train_inertia:.2f}, "
        f"validation_inertia={validation_inertia:.2f}, "
        f"silhouette={silhouette:.3f}, ARI={ari:.3f}, "
        f"cluster_sizes={sizes.tolist()}"
    )

best_k, best_silhouette = max(
    records,
    key=lambda record: record[1],
)
print(f"Highest validation silhouette: k={best_k}")

# The split contains 480 training points and 120 validation points.
# Numeric metrics may vary slightly across library versions.

Common Pitfalls

  • Not scaling features: Features with larger numeric ranges dominate Euclidean distance. Fit StandardScaler on training data only, preferably inside a Pipeline.

  • Treating the elbow as exact: The elbow depends on the dataset and may be ambiguous. Combine it with silhouette, stability, and domain evidence.

  • Using categorical data directly: K-Means assumes continuous numeric features; use k-modes or an appropriate embedding.

  • Ignoring outliers and missing values: K-Means does not accept NaN values, and extreme points can pull centroids. Impute appropriately and consider robust alternatives.

  • Overfitting to one validation split: Repeatedly choosing k using the same holdout set biases the result. Use resampling or multiple splits.

  • Interpreting clusters without profiling them: Examine feature distributions, cluster sizes, stability, and whether the groups support a useful decision.

  • Ignoring local optima: Use multiple initializations, such as n_init=10, and preserve random_state for reproducibility.

28

How does K-Means clustering influence business decision-making?

K-Means clustering influences business decisions by turning customer, product, or location data into actionable segments based on numeric similarity. These segments can guide targeting, assortment, inventory, site planning, and service policies. Its main trade-off is simple, scalable grouping versus strong assumptions and a descriptive—not causal—interpretation.

Read full answer

Applies toK-Means clustering concepts; scikit-learn 1.5+ where implementation-specific behavior is noted (Python 3.12)

Business Decisions Supported by K-Means

  • Customer segmentation: Group customers by spending, purchase frequency, recency, and engagement to identify segments such as high-value or low-engagement customers.

  • Marketing: Create segment-specific campaigns instead of one generic message for every customer.

  • Product assortment: Group products by sales, margins, dimensions, or demand to guide bundles, recommendations, and store layouts.

  • Site planning: Compare locations by customers, sales, costs, and demographics to choose store formats or regional strategies.

  • Inventory and operations: Identify demand or activity bands that support different replenishment, capacity, or service policies.

The clusters must be translated into understandable business profiles. The algorithm identifies groups; profiling, domain knowledge, and follow-up analysis determine what action each segment warrants.

How K-Means Works

K-Means minimizes the within-cluster sum of squares, also called inertia:

inertia = sum(i = 1 to n) ||x_i - centroid[cluster(i)]||²

Here, n is the number of observations, x_i is observation i, cluster(i) is its assigned cluster index, and centroid[cluster(i)] is that cluster’s mean. The norm term is the squared Euclidean distance.

  1. Initialize centroids: Select k initial cluster centers.

  2. Assign observations: Assign each point to its nearest centroid using Euclidean distance.

  3. Recompute centroids: Replace each center with the mean of its assigned observations.

  4. Repeat: Continue assigning and recomputing until assignments stabilize or another stopping condition is reached.

  5. Select the best restart: When several runs are performed, retain the solution with the lowest inertia.

Scikit-learn defaults to k-means++ initialization, which selects initial centers with some separation to reduce the likelihood of a poor local solution. K-Means converges to a local optimum, not necessarily the global optimum. In scikit-learn 1.5+, n_init="auto" means one initialization when k-means++ is used; set n_init to an integer such as 10 for several restarts.

Each iteration has approximate time complexity O(n * k * d), where k is the number of clusters and d is the number of features. The centroids require O(k * d) storage, while fitted cluster labels require O(n). For large datasets, MiniBatchKMeans is often more practical because it updates the model from mini-batches rather than processing all observations in every update.

Selecting and Validating Segments

  • Elbow method: Plot inertia for several values of k and look for diminishing returns; the elbow is not an exact optimum.

  • Silhouette score: Use the score, which ranges from -1 to 1, to assess separation, while recognizing that the mathematically best score may not be the most useful business segmentation.

  • Business usefulness: Prefer distinct, interpretable, actionable, and sufficiently populated clusters.

  • Stability: Check whether similar profiles emerge across time periods, resamples, or reasonable feature changes.

When comparing candidate values of k, fit scaling and clustering on training partitions only and evaluate validation partitions separately. Keep the test set untouched until model selection is complete, and assess whether segment-level outcomes differ in ways that justify the operational action.

Alternatives and Trade-offs

Alternative How It Works Strengths Weaknesses When to Use Complexity or Scale
K-medoids Uses actual observations as cluster representatives Interpretable centers and greater robustness to outliers Pairwise distances can be expensive Small or medium datasets where prototypes matter Distance computation is often O(n²d)
Gaussian mixture models Assigns soft, probabilistic memberships Flexible elliptical clusters and membership probabilities More computation and covariance-estimation issues Data expected to contain overlapping Gaussian groups About O(nkd²) per full-covariance EM iteration
DBSCAN Connects dense regions and marks sparse points as noise Finds arbitrary shapes and does not require k Sensitive to density parameters and difficult in high dimensions Spatial data with irregular groups and noise Worst-case neighbor search can approach O(n²)
HDBSCAN Builds a hierarchy of density-based clusters Handles variable-density groups and noise without one global density threshold Can require more time and memory than DBSCAN Clusters with differing densities Implementation-dependent; usually greater than basic DBSCAN

Common Pitfalls

  • Failing to scale comparable data: Standardize features with different units or ranges; otherwise large-range features dominate Euclidean distance. Standardization is unnecessary when all features are already on comparable scales.

  • Choosing k mechanically: Treat the elbow and silhouette score as evidence, not as substitutes for business judgment.

  • Ignoring assumptions: K-Means favors roughly spherical, similarly sized clusters and is sensitive to outliers. Use k-modes for categorical data or consider an appropriate alternative.

  • Leaving missing values untreated: scikit-learn’s KMeans does not accept NaN values, so impute them within a training-fitted preprocessing pipeline.

  • Leaking information: Fit the scaler and clustering model only on training data, then transform validation and test data with that fitted pipeline.

  • Overinterpreting clusters: Cluster IDs have no inherent meaning. Profile their centroids, sizes, business metrics, and stability without assuming membership caused an outcome.

  • Ignoring initialization sensitivity: Set random_state and use multiple initializations when reproducibility and stable solutions are important.

29

How can K-Means clustering solve a customer segmentation problem?

K-Means clustering is an unsupervised algorithm that groups customers around a chosen number of centroids. It can support targeted marketing by finding groups with similar purchasing behavior, but results depend on feature choice, scaling, and k; its main trade-off is speed and simplicity versus sensitivity to initialization, outliers, and non-spherical shapes.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

Real-World Scenario

An online retailer can represent each customer with recency, frequency, total spend, average order value, and return count. After scaling, K-Means might produce four groups:

  • High-value loyal customers: frequent purchases and high spending

  • Recent customers: strong recency but lower lifetime value

  • At-risk customers: previously active but purchasing infrequently

  • Low-value customers: infrequent purchases and low spending

Each group can receive a different campaign, but only controlled business validation establishes whether a segment is useful.

How It Works

K-Means optimizes the within-cluster sum of squares, also called inertia:

inertia = sum over points of squared Euclidean distance to its assigned centroid

Each point contains feature values, each centroid is the mean of its cluster, and the sum measures within-cluster variation.

Lloyd’s algorithm proceeds as follows:

  1. Initialize k centroids, using k-means++, which is scikit-learn’s default.

  2. Assign every point to its nearest centroid.

  3. Recalculate each centroid as the mean of its assigned points.

  4. Repeat until assignments stabilize or the maximum number of iterations is reached.

With k-means++, the first centroid is selected randomly, and each later centroid is sampled with probability proportional to its squared distance from the nearest existing centroid. This reduces the risk of poor starting positions. Each run can still converge to a local optimum. Setting n_init greater than 1 performs multiple restarts and retains the result with the lowest inertia; the example below uses n_init=10.

For n points, k clusters, and d features, each iteration costs approximately O(n × k × d). MiniBatchKMeans is preferable for very large datasets because it updates centroids using batches rather than the complete dataset.

Practical Evaluation

Several complementary checks are needed:

  • Elbow plot: Plot inertia for several values of k and look for diminishing improvements. The elbow is a heuristic, not an exact answer.

  • Silhouette score: Ranges from -1 to 1; higher values generally indicate better-separated clusters, although irregular or uneven clusters can mislead it.

  • Cluster profiles: Inspect centroid values and feature distributions for business meaning.

  • Business validation: Test whether segment-specific campaigns improve conversion, retention, or lifetime value.

  • Stability: Refit on resampled data and compare segment definitions.

Code Example

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

# Synthetic customer-like data with two informative dimensions
X, _ = make_blobs(
    n_samples=600,
    centers=4,
    cluster_std=1.8,
    random_state=42,
)

# Split before fitting the scaler or clustering model
X_train, X_test = train_test_split(
    X,
    test_size=0.2,
    random_state=42,
)

models = {}

for k in range(2, 7):
    model = Pipeline([
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=k,
            init="k-means++",
            n_init=10,
            random_state=42,
        )),
    ])

    # The scaler and K-Means learn only from training data
    model.fit(X_train)

    kmeans = model.named_steps["kmeans"]
    scaled_test = model.named_steps["scaler"].transform(X_test)
    test_labels = model.predict(X_test)

    models[k] = model

    print(
        f"k={k}: "
        f"training inertia={kmeans.inertia_:.2f}, "
        f"validation silhouette="
        f"{silhouette_score(scaled_test, test_labels):.3f}"
    )

# Select the four-segment solution
final_model = models[4]
test_labels = final_model.predict(X_test)
cluster_sizes = np.bincount(test_labels, minlength=4)

print("Validation cluster sizes:", cluster_sizes)

Limitations and Alternatives

Algorithm How It Works Strengths Weaknesses When to Use Typical Scale
K-Means Assigns points to nearest means and updates means Fast and scalable Requires k; sensitive to scaling, outliers, and initialization Roughly spherical, similarly sized groups O(nkd) per iteration
K-Medoids Uses actual points as representatives More robust to outliers Usually costlier than K-Means Small or medium datasets Can approach quadratic cost
Gaussian Mixture Models Provides probabilistic membership Soft assignments; elliptical clusters Requires distributional assumptions Overlapping or variable-density groups Cost grows with points and components
DBSCAN Connects dense regions Finds arbitrary shapes and noise Sensitive to density parameters Irregular clusters with meaningful noise Often near-linear with indexing; worst case O(n²)
HDBSCAN Builds a hierarchy of dense clusters Does not require choosing k; detects outliers More computationally costly Complex density structures Higher cost than basic DBSCAN

Common Pitfalls

  • Not scaling features: Large-scale features can dominate Euclidean distances; standardize measurements with different units.

  • Choosing k arbitrarily: Combine the elbow method, silhouette score, domain knowledge, and interpretability.

  • Treating the elbow as exact: Inertia generally decreases as k increases, so k remains a modeling decision.

  • Using categorical data directly: K-Means expects numerical distances; use K-Modes or another suitable method.

  • Ignoring missing values or outliers: Impute missing values within a fitted pipeline and inspect or robustly handle outliers.

  • Overclaiming business value: A well-separated cluster is not automatically a profitable segment.

  • Confusing clusters with classes: K-Means has no ground-truth labels, so classification accuracy is not an appropriate evaluation metric.

Useful follow-up questions include: How would you choose k? Why does scaling matter? How would you detect outliers? What causes local optima? How would you validate a segment’s business value?

30

How should data be prepared before K-Means clustering?

Data preparation for K-Means means converting data into a clean numeric matrix whose features can be compared fairly by distance. It prevents missing, differently scaled, irrelevant, or extreme values from distorting centroids and assignments; the main trade-off is that imputation, clipping, and dimensional reduction can change the cluster structure being discovered. K-Means minimizes the within-cluster sum of squares, called inertia, only to a local optimum.

Read full answer

Applies toscikit-learn 1.5+ and NumPy 2.x (Python 3.12)

Recommended Preprocessing Workflow

  1. Clean and select features

  2. Remove data-entry errors, contradictory values, identifiers, constants, and unnecessary correlated measurements.

  3. Review exact duplicates because repeated observations receive additional weight in centroid calculations.

  4. Avoid feature selection based on a later prediction target, which would introduce target leakage.

  5. Handle missing values

  6. K-Means does not accept NaN values, so impute them before clustering.

  7. Median imputation is a reasonable default for approximately symmetric numeric features; mean imputation requires a suitably shaped distribution.

  8. If missingness is informative, a carefully evaluated missing-value indicator may help, but it is another scaled feature that affects distances.

  9. Address outliers

  10. Extreme observations can pull centroids toward themselves because centroids are feature-wise means.

  11. Remove genuine errors and consider clipping or winsorization for valid but extreme values.

  12. RobustScaler limits the influence of extreme values when calculating feature scales, but it does not stop those observations from pulling centroids.

  13. Scale numeric features

  14. K-Means uses Euclidean distance, so a feature measured in thousands can dominate one measured in single digits.

  15. Apply StandardScaler when features have different units or ranges and roughly equal influence is appropriate.

  16. Apply RobustScaler when scale estimates should be less sensitive to extreme feature values, while retaining the outlier caveat above.

  17. Handle categorical data appropriately

  18. Do not treat arbitrary category codes as continuous measurements or casually one-hot encode them for K-Means.

  19. Use k-modes for purely categorical data, or an algorithm supporting mixed-type distances such as k-medoids with a suitable Gower-distance implementation.

  20. Reduce dimensionality only when justified

  21. Consider PCA after scaling when many correlated features obscure the clustering structure.

  22. Interpret the resulting clusters in the PCA-transformed space rather than as if they were based on every original feature.

Important Algorithm Settings

  • Lloyd’s algorithm: Initialize k centroids, assign each point to its nearest centroid, recompute centroids as feature-wise means, and repeat until assignments stop changing.

  • Initialization: scikit-learn uses k-means++ by default, selecting relatively well-separated initial centroids.

  • Restarts: n_init=10 fits several initial configurations and retains the solution with the lowest inertia.

  • Local optimum: Different initializations can produce different clusters, especially for weakly separated groups.

  • Complexity: Each iteration is approximately O(n * k * d), where n is the sample count, k is the number of clusters, and d is the feature count.

  • Large datasets: Consider MiniBatchKMeans when standard K-Means is too slow or memory-intensive.

Code Example

This example uses a validation split to compare values of k and reserves the test split for final evaluation.

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.impute import SimpleImputer
from sklearn.metrics import silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

rng = np.random.default_rng(42)

X, _ = make_blobs(
    n_samples=600,
    centers=3,
    cluster_std=1.2,
    random_state=42,
)
X[rng.random(X.shape) < 0.03] = np.nan

X_train, X_test = train_test_split(
    X, test_size=0.25, random_state=42
)
X_fit, X_validation = train_test_split(
    X_train, test_size=0.25, random_state=42
)

results = []

for k in range(2, 7):
    model = Pipeline([
        ("imputer", SimpleImputer(strategy="median")),
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=k,
            init="k-means++",
            n_init=10,
            random_state=42,
        )),
    ])

    model.fit(X_fit)

    # Transform before silhouette_score so it receives no NaN values.
    X_fit_prepared = model[:-1].transform(X_fit)
    X_validation_prepared = model[:-1].transform(X_validation)

    fit_labels = model.predict(X_fit)
    validation_labels = model.predict(X_validation)

    inertia = model.named_steps["kmeans"].inertia_
    validation_silhouette = silhouette_score(
        X_validation_prepared, validation_labels
    )

    results.append((validation_silhouette, k))
    print(
        f"k={k} "
        f"inertia={inertia:.3f} "
        f"validation_silhouette={validation_silhouette:.3f}"
    )

# Select k using validation results, never the test split.
best_k = max(results, key=lambda result: result[0])[1]

final_model = Pipeline([
    ("imputer", SimpleImputer(strategy="median")),
    ("scaler", StandardScaler()),
    ("kmeans", KMeans(
        n_clusters=best_k,
        init="k-means++",
        n_init=10,
        random_state=42,
    )),
])
final_model.fit(X_train)

train_labels = final_model.predict(X_train)
cluster_sizes = np.bincount(train_labels, minlength=best_k)

X_test_prepared = final_model[:-1].transform(X_test)
test_labels = final_model.predict(X_test)
test_silhouette = silhouette_score(X_test_prepared, test_labels)

print("Selected k:", best_k)
print("Cluster sizes:", cluster_sizes)
print(f"Test silhouette: {test_silhouette:.3f}")

Common Pitfalls

  • Not scaling: Features with larger numerical ranges dominate Euclidean distances.

  • Treating the elbow as exact: It suggests candidate values of k, not a uniquely correct answer; combine it with silhouette scores and domain knowledge.

  • Ignoring model assumptions: K-Means favors compact, roughly spherical, similarly sized clusters. GMMs, DBSCAN, HDBSCAN, or k-medoids may suit other structures.

  • Using categorical variables directly: Use a method designed for categorical or mixed-type data.

  • Over-interpreting clusters: Profile clusters with feature summaries, domain knowledge, and stability checks.

  • Data leakage: Fit imputation, scaling, PCA, and feature selection within the pipeline. Select k without the test split; after final evaluation, refit the complete pipeline on all data intended for clustering.

31

How do I implement K-Means clustering from scratch in Python?

K-Means is an unsupervised algorithm that partitions data into k clusters by minimizing the squared distance between each point and its cluster’s centroid. The implementation below follows Lloyd’s algorithm, uses k-means++ initialization, and keeps the best result across several restarts. Its main trade-off is speed and simplicity versus sensitivity to initialization, scaling, outliers, and the chosen k.

Read full answer

Applies toPython 3.12 with NumPy 2.x and scikit-learn 1.5+

How Lloyd’s Algorithm Works

  1. Choose k initial centroids.

  2. Assign every point to its nearest centroid using squared Euclidean distance.

  3. Recompute each centroid as the mean of its assigned points.

  4. Repeat until assignments stop changing or max_iter is reached.

The objective is the within-cluster sum of squares:

inertia = sum_i ||x_i - mu_c(i)||^2

Here, x_i is point i, mu_c(i) is the centroid of its assigned cluster, and || || denotes Euclidean distance.

Initialization and Complexity

K-means++ selects the first centroid randomly, then chooses each additional centroid with probability proportional to its squared distance from the closest existing centroid. This favors separated starting points and is scikit-learn’s default initialization. Setting n_init=10 performs several restarts and retains the clustering with the lowest inertia.

The objective decreases with each Lloyd update, but the result is a local optimum that can depend on initialization. Each iteration costs O(n * k * d) time. The vectorized implementation below temporarily uses O(n * k * d) memory while constructing the distance tensor; an optimized implementation can reduce this to O(n * k). For large datasets, MiniBatchKMeans is more practical.

Code Example

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler


def kmeans_plus_plus(X, k, rng):
    """Return k centroids initialized with k-means++."""
    n_samples = X.shape[0]
    selected = [int(rng.integers(n_samples))]
    closest = np.sum((X - X[selected[0]]) ** 2, axis=1)

    for _ in range(1, k):
        index = int(rng.choice(n_samples, p=closest / closest.sum()))
        selected.append(index)
        distance = np.sum((X - X[index]) ** 2, axis=1)
        closest = np.minimum(closest, distance)

    return X[selected].copy()


def kmeans_from_scratch(X, k, n_init=10, max_iter=300, seed=42):
    """Fit Lloyd's algorithm with k-means++ initialization."""
    X = np.asarray(X, dtype=np.float64)

    if X.ndim != 2 or not np.isfinite(X).all():
        raise ValueError("X must be a finite, two-dimensional array")
    if not 1 <= k <= X.shape[0]:
        raise ValueError("k must be between 1 and the number of samples")
    if np.unique(X, axis=0).shape[0] < k:
        raise ValueError("X must contain at least k distinct points")

    rng = np.random.default_rng(seed)
    best_labels = best_centroids = None
    best_inertia = np.inf

    for _ in range(n_init):
        centroids = kmeans_plus_plus(X, k, rng)
        previous_labels = None

        for _ in range(max_iter):
            distances = np.sum(
                (X[:, None, :] - centroids[None, :, :]) ** 2,
                axis=2,
            )
            labels = np.argmin(distances, axis=1)

            # Stable assignments mean Lloyd's algorithm has converged.
            if previous_labels is not None and np.array_equal(
                labels, previous_labels
            ):
                break

            counts = np.bincount(labels, minlength=k)
            sums = np.zeros_like(centroids)
            np.add.at(sums, labels, X)

            new_centroids = centroids.copy()
            nonempty = counts > 0
            new_centroids[nonempty] = (
                sums[nonempty] / counts[nonempty, None]
            )

            # Relocate empty clusters to distant observations.
            empty_clusters = np.flatnonzero(~nonempty)
            if empty_clusters.size:
                farthest = np.argsort(np.min(distances, axis=1))[::-1]
                for offset, cluster in enumerate(empty_clusters):
                    new_centroids[cluster] = X[
                        farthest[offset % len(farthest)]
                    ]

            centroids = new_centroids
            previous_labels = labels.copy()

        distances = np.sum(
            (X[:, None, :] - centroids[None, :, :]) ** 2,
            axis=2,
        )
        labels = np.argmin(distances, axis=1)
        inertia = np.sum(distances[np.arange(len(X)), labels])

        if inertia < best_inertia:
            best_labels = labels.copy()
            best_centroids = centroids.copy()
            best_inertia = inertia

    return best_labels, best_centroids, best_inertia


X, _ = make_blobs(
    n_samples=300,
    centers=3,
    cluster_std=0.8,
    random_state=42,
)
X_train, X_test, _, _ = train_test_split(
    X, test_size=0.2, random_state=42
)

# Fit preprocessing only on the training data.
preprocess = Pipeline([("scaler", StandardScaler())])
X_train_scaled = preprocess.fit_transform(X_train)
X_test_scaled = preprocess.transform(X_test)

labels, centroids, inertia = kmeans_from_scratch(
    X_train_scaled, k=3, n_init=10, seed=42
)
print("Custom cluster sizes:", np.bincount(labels, minlength=3))
print("Custom inertia:", round(inertia, 2))

# Compare several k values using scikit-learn.
for k in range(1, 6):
    candidate = Pipeline([
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=k,
            n_init=10,
            random_state=42,
        )),
    ])
    candidate.fit(X_train)

    model = candidate.named_steps["kmeans"]
    scaled_train = candidate.named_steps["scaler"].transform(X_train)
    silhouette = (
        round(silhouette_score(scaled_train, model.labels_), 3)
        if k > 1 else "not applicable"
    )
    print(
        f"k={k}, sizes={np.bincount(model.labels_, minlength=k)}, "
        f"inertia={model.inertia_:.2f}, silhouette={silhouette}"
    )

Choosing k and Practical Guidance

  • Elbow method: inspect inertia across k; the elbow is a heuristic rather than an exact answer.

  • Silhouette score: higher values generally indicate better separation, but the measure also has limitations.

  • Scaling: standardize features with different units or magnitudes before clustering.

  • Interpretation: profile clusters using feature summaries before assigning business meaning.

  • Reproducibility: fix the seed and record the initialization method and n_init.

Limitations and Alternatives

Algorithm How it works Strengths Weaknesses Typical use
K-Means Assigns points to nearest means Fast and scalable Sensitive to scaling, outliers, initialization, k, and cluster size Spherical, similar-sized clusters
K-Medoids Uses actual observations as centers More robust to outliers Slower and often more memory-intensive Noisy or non-Euclidean data
Gaussian Mixture Models probability distributions Soft assignments and covariance information More assumptions and parameters Elliptical or overlapping clusters
DBSCAN/HDBSCAN Groups points by density Finds irregular shapes and noise Parameters can be difficult to tune Irregular clusters and outliers

Common Pitfalls

  • Not scaling features lets high-magnitude variables dominate distances.

  • Missing values are unsupported by K-Means; impute them using a leakage-safe process.

  • Choosing k from the elbow alone is unreliable; combine diagnostics with domain knowledge.

  • Categorical data makes means and Euclidean distances inappropriate; consider k-modes.

  • Fitting the scaler before splitting causes leakage.

  • Expecting a unique solution ignores local optima and initialization sensitivity.

32

How can Python determine the best k with the elbow method?

K-means elbow method compares the within-cluster sum of squares, called inertia, across several candidate values of k. It selects the point where improvements begin to level off, providing a simple way to choose the number of clusters. The main trade-off is that the elbow is a heuristic rather than an exact optimum and can be sensitive to scaling, initialization, and cluster shape.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12, NumPy 2.x, pandas 2.2+)

How the Method Works

For each candidate k, fit a separate k-means model and record:

  • inertia_: Total squared distance between every sample and its assigned centroid.

  • Silhouette score: Measures how well samples fit their own cluster compared with neighboring clusters, ranging from -1 to 1.

The inertia formula is:

inertia = sum(||x_i - c_assigned(i)||^2)

Here, x_i is sample i, c_assigned(i) is its assigned centroid, and ||...||^2 is the squared Euclidean distance. Lower inertia indicates clusters that are more internally compact.

The inertia usually decreases as k grows. The elbow is where the reduction becomes substantially smaller, so adding another cluster provides little benefit.

Lloyd’s Algorithm and Initialization

K-means uses Lloyd’s algorithm:

  1. Initialize k centroids.

  2. Assign each point to its nearest centroid.

  3. Recompute each centroid as the mean of its assigned points.

  4. Repeat until assignments stop changing or another stopping condition is reached.

The implementation uses k-means++ initialization, the scikit-learn default. It selects initial centroids with a bias toward well-separated points, reducing the chance of starting with a poor solution.

Setting n_init=10 runs ten initializations and retains the result with the lowest inertia. K-means converges to a local optimum rather than guaranteeing a global optimum.

Choosing the Elbow

There is no single mandatory elbow-detection algorithm. A common geometric heuristic is:

  1. Normalize the candidate k values and inertia values.

  2. Draw a line between the first and last normalized points.

  3. Select the candidate with the greatest perpendicular distance from that line.

Silhouette score should also be inspected. A higher silhouette score suggests better-separated clusters, but it does not make the choice automatic because different criteria can identify different values of k.

Code Example

import numpy as np
import pandas as pd

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler


def find_best_k_by_elbow(X, max_k=10, random_state=42):
    """Estimate k with an elbow heuristic and silhouette diagnostics."""
    X = np.asarray(X, dtype=np.float64)

    if X.ndim != 2:
        raise ValueError("X must be a two-dimensional feature matrix.")
    if not np.isfinite(X).all():
        raise ValueError("X must contain only finite values.")
    if max_k < 4 or max_k >= len(X):
        raise ValueError("max_k must be between 4 and n_samples - 1.")

    k_values = list(range(2, max_k + 1))
    rows = {}
    models = {}

    for k in k_values:
        model = Pipeline([
            ("scale", StandardScaler()),
            ("kmeans", KMeans(
                n_clusters=k,
                n_init=10,
                random_state=random_state,
            )),
        ])

        # The pipeline fits the scaler and k-means on training data only.
        model.fit(X)
        scaled_X = model.named_steps["scale"].transform(X)
        labels = model.predict(X)
        kmeans = model.named_steps["kmeans"]

        rows[k] = {
            "k": k,
            "inertia": kmeans.inertia_,
            "silhouette": silhouette_score(scaled_X, labels),
        }
        models[k] = model

    results = pd.DataFrame(rows.values())

    # Normalize both axes so units do not dominate the distance calculation.
    x = np.asarray(k_values, dtype=np.float64)
    y = results["inertia"].to_numpy()
    x = (x - x.min()) / np.ptp(x)

    if np.ptp(y) == 0:
        y_normalized = np.zeros_like(y)
    else:
        y_normalized = (y - y.min()) / np.ptp(y)

    points = np.column_stack([x, y_normalized])
    start, end = points[0], points[-1]
    direction = end - start

    projections = np.clip(
        ((points - start) @ direction) / np.dot(direction, direction),
        0.0,
        1.0,
    )
    closest_points = start + projections[:, None] * direction
    distances = np.linalg.norm(points - closest_points, axis=1)

    best_index = int(np.argmax(distances))
    best_k = k_values[best_index]
    return best_k, results, models[best_k]


# Synthetic data with three visually distinct clusters.
X, _ = make_blobs(
    n_samples=600,
    n_features=2,
    centers=3,
    cluster_std=1.0,
    random_state=42,
)

# Keep the holdout set out of elbow selection.
X_train, X_test = train_test_split(
    X,
    test_size=0.20,
    random_state=42,
)

best_k, results, best_model = find_best_k_by_elbow(X_train)

print("Candidate models:")
print(results.to_string(index=False, float_format=lambda value: f"{value:.3f}"))
print(f"Selected k by elbow: {best_k}")

train_labels = best_model.predict(X_train)
test_labels = best_model.predict(X_test)
scaled_test = best_model.named_steps["scale"].transform(X_test)

print("Training cluster sizes:",
      np.bincount(train_labels, minlength=best_k))
print("Held-out cluster sizes:",
      np.bincount(test_labels, minlength=best_k))
print("Selected model training inertia:",
      best_model.named_steps["kmeans"].inertia_)
print("Held-out silhouette:",
      round(silhouette_score(scaled_test, test_labels), 3))

Practical Guidance

  • Scale features: K-means uses Euclidean distances, so variables with larger numeric ranges can dominate the result.

  • Missing values: K-means cannot fit NaN or infinite values. Impute missing values inside a pipeline fitted only on the training data.

  • Complexity: One k-means iteration costs approximately O(n * k * d), where n is the sample count, k the cluster count, and d the feature count.

  • Large datasets: Consider MiniBatchKMeans when repeated full k-means fits are expensive.

  • Validation: Compare the elbow with silhouette scores and cluster profiles. Ordinary classification cross-validation is not directly applicable to unsupervised clustering.

  • Interpretability: Inspect feature distributions within each cluster before assigning it a business meaning.

Method How it works Strengths Weaknesses When to use and typical scale
K-means Assigns points to centroids and repeatedly updates their means Fast and simple Assumes roughly spherical, similarly sized clusters; sensitive to scaling and outliers Standardized numerical data; O(n * k * d) per iteration; use MiniBatchKMeans for very large data
K-medoids Uses actual observations as cluster centers Less sensitive to outliers; supports nonstandard dissimilarities Usually slower and more memory-intensive Small or medium datasets where k-means assumptions fail
Gaussian mixture model Estimates a probabilistic distribution with overlapping clusters Provides soft assignments and models elliptical covariance Assumes Gaussian components; can degenerate or overfit Moderate-sized data with approximately Gaussian clusters
DBSCAN/HDBSCAN Groups dense regions using density connectivity Finds irregular clusters and noise without specifying k Sensitive to density parameters; performance can degrade in dense spaces Spatial or irregular data; use spatial indexes and generally favor medium-sized datasets

Common Pitfalls

  • Not scaling data: Standardization or another suitable transformation should usually precede k-means.

  • Treating the elbow as exact: The detected value is a starting point, not proof that another k is invalid.

  • Ignoring outliers: Extreme values can pull centroids; less-sensitive alternatives include k-medoids.

  • Using unsuitable data: K-means works best for roughly spherical, similarly sized clusters. It is not appropriate for categorical features; use k-modes instead.

  • Overinterpreting clusters: Profile cluster characteristics and validate their stability before assigning them business meaning.

33

How do you scale features and run K-Means clustering with scikit-learn?

K-Means clustering groups unlabeled observations into k clusters by minimizing the squared distance between each point and its cluster centroid. Scaling features first prevents high-magnitude variables from dominating the distance calculation. Its main trade-off is simplicity and scalability versus the need to choose k and the assumption that clusters are roughly spherical and similarly sized.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

How It Works

The objective is the within-cluster sum of squares, called inertia:

inertia = sum(||x_i - c_(assignment_i)||²)

Here, x_i is observation i, c_(assignment_i) is its assigned centroid, and ||...||² is its squared Euclidean distance from that centroid. Lower inertia means observations are, on average, closer to their cluster centers.

Lloyd’s algorithm proceeds as follows:

  1. Initialize centroids: scikit-learn uses k-means++ by default. It selects the first center uniformly, then selects subsequent centers with higher probability when they are far from existing centers.

  2. Assign observations: Each point is assigned to its nearest centroid using Euclidean distance.

  3. Recompute centroids: Each centroid becomes the mean of the points assigned to it.

  4. Repeat: Assignment and recomputation continue until assignments stabilize or the iteration limit is reached.

  5. Select the best run: With n_init=10, scikit-learn performs ten initializations and keeps the run with the lowest inertia.

K-Means converges to a local optimum, so its result can depend on initialization.

Choosing and Evaluating k

No metric identifies a universally correct number of clusters:

  • Elbow method: Plot inertia for several values of k and look for the point where improvements begin to diminish. The elbow is a visual guide, not an exact threshold.

  • Silhouette score: Measures both within-cluster cohesion and between-cluster separation. It generally ranges from -1 to 1, with higher values indicating better separation.

  • Domain knowledge: Cluster sizes, feature profiles, and the intended use of the clustering should influence the final choice.

  • Stability checks: Run K-Means on different subsets or seeds and compare how consistently observations are assigned.

Silhouette values should be calculated using the same scaled feature space used to fit the model.

Limitations and Alternatives

Method How it works Strengths Weaknesses When to use Typical scale
K-Means Assigns points to the nearest mean Fast, simple, scalable Requires k; sensitive to outliers, scaling, and initialization Roughly spherical clusters with similar densities O(n * k * d) per iteration
K-Medoids Uses actual observations as centers More robust to outliers Usually slower than K-Means Smaller datasets with possible outliers Moderate to large datasets with efficient implementations
Gaussian Mixture Model Models clusters as probability distributions Supports elliptical and overlapping clusters More parameters and greater computational cost Soft assignments and probabilistic modeling Heavier for high-dimensional data
DBSCAN/HDBSCAN Groups points through density-connected regions Finds arbitrary-shaped clusters and can label noise Sensitive to density parameters; challenging in high dimensions Irregular clusters and unknown cluster counts Can become expensive in high dimensions

For large datasets, MiniBatchKMeans processes subsets of observations per iteration and can reduce training time.

Code Example

import numpy as np

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler


# Create a reproducible synthetic dataset with three underlying groups.
X, _ = make_blobs(
    n_samples=600,
    centers=3,
    cluster_std=1.0,
    random_state=42,
)

# Hold out data so the scaler is fitted only on training observations.
X_train, X_test = train_test_split(
    X,
    test_size=0.20,
    random_state=42,
)


def build_kmeans_pipeline(k: int) -> Pipeline:
    """Create scaling and clustering steps without preprocessing leakage."""
    return Pipeline(
        steps=[
            ("scaler", StandardScaler()),
            (
                "kmeans",
                KMeans(
                    n_clusters=k,
                    init="k-means++",
                    n_init=10,
                    random_state=42,
                ),
            ),
        ]
    )


# Evaluate several possible values of k.
candidate_results = {}

for k in range(2, 7):
    model = build_kmeans_pipeline(k)
    model.fit(X_train)

    scaled_train = model.named_steps["scaler"].transform(X_train)
    train_labels = model.predict(X_train)
    inertia = model.named_steps["kmeans"].inertia_
    silhouette = silhouette_score(scaled_train, train_labels)

    candidate_results[k] = (model, inertia, silhouette)
    print(
        f"k={k}: inertia={inertia:.3f}, "
        f"silhouette={silhouette:.3f}"
    )

# Select k after inspecting the elbow, silhouette scores, and cluster profiles.
best_k = 3
final_model, final_inertia, final_silhouette = candidate_results[best_k]

# Assign observations using the fitted scaler and centroids.
train_labels = final_model.predict(X_train)
test_labels = final_model.predict(X_test)
all_labels = final_model.predict(X)

print(f"\nSelected k: {best_k}")
print(f"Final inertia: {final_inertia:.3f}")
print(f"Final silhouette: {final_silhouette:.3f}")
print(
    "Training cluster sizes:",
    np.bincount(train_labels, minlength=best_k),
)
print(
    "Test cluster sizes:",
    np.bincount(test_labels, minlength=best_k),
)
print(
    "All assigned cluster sizes:",
    np.bincount(all_labels, minlength=best_k),
)

The Pipeline ensures that StandardScaler learns its means and standard deviations from X_train only. Applying that fitted transformation to X_test prevents preprocessing leakage. The held-out split is less conventional for fully unsupervised work because there is no target label to generalize, but it still provides a clean way to demonstrate leakage-free preprocessing and assignment of new observations.

Best Practices

  • Scale features: Use StandardScaler when features have different units or magnitudes. Standardization is generally unnecessary only when all features already represent comparable scales.

  • Use multiple signals: Combine the elbow method, silhouette scores, cluster profiles, and domain requirements rather than relying on one score.

  • Inspect clusters: Summarize feature distributions within each cluster. Cluster numbers are arbitrary identifiers and do not inherently represent meaningful categories.

  • Handle missing values: K-Means does not accept NaN values. Impute them using a training-fitted imputer inside the pipeline.

  • Avoid categorical measurements directly: Euclidean distance is not meaningful for unordered categories; use k-modes or an appropriate embedding.

  • Check outliers: Extreme observations can pull centroids toward themselves and create poorly separated clusters.

  • Set a random seed: random_state improves reproducibility, although different valid local optima may still have different inertia values.

  • Plan for scale: Prefer MiniBatchKMeans or another approximate method when the full dataset does not fit comfortably in memory.

Common Pitfalls

  • Skipping scaling: Variables with large numerical ranges can determine the clusters almost exclusively.

  • Treating the elbow as exact: The curve often has no sharp, objectively correct turning point.

  • Selecting k only for a high silhouette: The metric can be misleading for non-spherical, unbalanced, or very small clusters.

  • Ignoring feature relevance: Uninformative variables can weaken the clustering even after scaling.

  • Interpreting clusters without profiling them: Statistical separation does not establish business meaning or causal relationships.

  • Repeatedly tuning against the test set: Keep the final holdout separate from model and preprocessing selection.

Common interviewer follow-ups include: Why does K-Means use centroids instead of arbitrary points? Why can K-Means produce different results for different random seeds? How would you detect empty or unstable clusters? When would you choose MiniBatchKMeans, K-Medoids, or HDBSCAN instead?

34

How can I visualize 2D K-Means clustering results in Python?

K-Means clustering groups unlabeled data points into k clusters by assigning each point to its nearest centroid and repeatedly updating centroids as cluster means. For 2D data, visualize the assignments by coloring each point by its cluster label and marking the centroids with a distinct symbol. The main trade-off is speed and simplicity versus sensitivity to feature scaling, outliers, initialization, and the assumption of compact, similarly sized clusters.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12), NumPy 2.x, Matplotlib 3.9+

How the Visualization Works

Fit KMeans to two-dimensional features, then use:

  • labels_: the cluster assigned to each observation.

  • cluster_centers_: the centroid coordinates.

  • inertia_: the within-cluster sum of squares.

  • silhouette_score: a measure of cluster separation and compactness.

Scale continuous features before clustering because K-Means uses Euclidean distance. The points and centroids must be plotted in the same coordinate space; the example below plots standardized data and centers from the same fitted pipeline.

K-Means Mechanics and Choosing k

K-Means uses Lloyd’s algorithm:

  1. Initialize k centroids.

  2. Assign each point to its nearest centroid.

  3. Recompute each centroid as the mean of its assigned points.

  4. Repeat until assignments stop changing or another stopping condition is reached.

The objective is:

WCSS = sum(||x_i - c_label[i]||^2)

Here, x_i is point i, c_label[i] is its assigned centroid, and ||...||^2 is squared Euclidean distance. Lower WCSS means points are closer to their centers.

Scikit-learn uses k-means++ initialization by default: after selecting the first center randomly, subsequent centers are sampled with a preference for locations far from existing centers. With n_init=10, K-Means performs ten initializations and keeps the result with the lowest inertia. It converges to a local optimum, so results depend on initialization.

Each Lloyd iteration takes approximately O(n * k * d) time, where n is the number of points, k is the number of clusters, and d is the number of features. Use MiniBatchKMeans when computation on a very large dataset is excessive.

Use an elbow plot, silhouette score, stability checks, and domain knowledge to choose k. Training inertia is non-increasing as k increases, so it cannot select k by itself. Silhouette scores range from -1 to 1, with higher values generally indicating better separation.

Code Example

import matplotlib.pyplot as plt
import numpy as np

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler


# Create a reproducible 2D dataset.
X, _ = make_blobs(
    n_samples=500,
    centers=4,
    cluster_std=1.2,
    random_state=42,
)

# Keep a separate validation set for selecting k.
X_train, X_valid = train_test_split(
    X, test_size=0.30, random_state=42
)

results = []

for k in range(2, 7):
    # The scaler is fitted only on X_train by Pipeline.fit().
    pipeline = Pipeline([
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=k,
            init="k-means++",
            n_init=10,
            random_state=42,
        )),
    ])
    pipeline.fit(X_train)

    scaler = pipeline.named_steps["scaler"]
    model = pipeline.named_steps["kmeans"]
    X_valid_scaled = scaler.transform(X_valid)
    valid_labels = model.predict(X_valid_scaled)

    results.append((
        k,
        model.inertia_,
        silhouette_score(X_valid_scaled, valid_labels),
    ))

# Select k using validation silhouette score.
best_k = max(results, key=lambda row: row[2])[0]

# Refit the selected model on all data for the final visualization.
final_pipeline = Pipeline([
    ("scaler", StandardScaler()),
    ("kmeans", KMeans(
        n_clusters=best_k,
        init="k-means++",
        n_init=10,
        random_state=42,
    )),
])
final_pipeline.fit(X)

final_scaler = final_pipeline.named_steps["scaler"]
final_model = final_pipeline.named_steps["kmeans"]
X_scaled = final_scaler.transform(X)
labels = final_model.predict(X_scaled)
centers = final_model.cluster_centers_
cluster_sizes = np.bincount(labels, minlength=best_k)

print("k\tTraining inertia\tValidation silhouette")
for k, inertia, score in results:
    print(f"{k}\t{inertia:.3f}\t\t{score:.3f}")

print(f"\nSelected k: {best_k}")
print(f"Cluster sizes: {dict(enumerate(cluster_sizes.tolist()))}")
print(f"Final inertia: {final_model.inertia_:.3f}")

# Plot cluster assignments, elbow curve, and silhouette scores.
fig, axes = plt.subplots(1, 3, figsize=(18, 5))

axes[0].scatter(
    X_scaled[:, 0],
    X_scaled[:, 1],
    c=labels,
    cmap="viridis",
    alpha=0.75,
    edgecolors="none",
)
axes[0].scatter(
    centers[:, 0],
    centers[:, 1],
    color="red",
    marker="X",
    s=220,
    label="Centroids",
)
axes[0].set_title(f"Standardized Data with {best_k} Clusters")
axes[0].set_xlabel("Feature 1")
axes[0].set_ylabel("Feature 2")
axes[0].legend()

axes[1].plot(
    [row[0] for row in results],
    [row[1] for row in results],
    marker="o",
)
axes[1].set_title("Elbow Method")
axes[1].set_xlabel("Number of clusters")
axes[1].set_ylabel("Training inertia")
axes[1].grid(alpha=0.3)

axes[2].plot(
    [row[0] for row in results],
    [row[2] for row in results],
    marker="o",
    color="darkorange",
)
axes[2].set_title("Silhouette Scores")
axes[2].set_xlabel("Number of clusters")
axes[2].set_ylabel("Validation silhouette")
axes[2].grid(alpha=0.3)

fig.tight_layout()
plt.show()

Best Practices and Alternatives

  • Handle missing values with an imputation strategy fitted only on training data.

  • Profile each cluster using feature summaries rather than interpreting only its plotted location.

  • Set random_state for reproducibility and retain multiple initializations with n_init.

  • Treat the elbow as a heuristic, and do not repeatedly tune against a final test set.

  • Do not apply K-Means directly to arbitrary categorical codes; use K-Modes or another suitable method.

Method How it works Strengths Weaknesses When to use
K-Medoids Uses actual observations as centers More robust to outliers Slower than K-Means Small or medium datasets with outliers
Gaussian Mixture Model Models clusters as probability distributions Supports soft assignments and elliptical shapes Strong distributional assumptions Overlapping or elliptical clusters
DBSCAN/HDBSCAN Groups points through density connectivity Finds irregular shapes and noise Sensitive to density assumptions Irregular clusters or data containing noise
K-Modes Groups categorical values by their modes Supports categorical features Does not model continuous geometry Primarily categorical data

Common Pitfalls

  • Running K-Means on unscaled features lets large-scale variables dominate distance.

  • Selecting k only from the elbow plot can overlook separation and domain meaning.

  • Interpreting clusters as supervised classes is incorrect; they are geometric groupings.

  • Reporting only inertia favors larger k and does not establish cluster validity.

  • Interviewers commonly ask about Lloyd’s algorithm, k-means++, local optima, feature scaling, outliers, and how complexity changes with n, k, and d.

35

How do I benchmark K-Means centroid initialization methods in Python?

K-means initialization determines the initial centroids used by Lloyd’s algorithm. A useful benchmark compares final clustering quality, held-out quality, convergence iterations, runtime, and variability across random seeds. The main trade-off is that better initialization methods such as k-means++ usually improve starting positions while adding initialization computation.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

How Lloyd’s Algorithm Works

K-means minimizes the within-cluster sum of squares, also called inertia:

WCSS = sum of squared distances from each observation to its assigned centroid

A point close to its centroid contributes little to this objective.

  1. Initialize centroids: Select k starting centroids using random selection, k-means++, or a supplied array.

  2. Assign observations: Assign each point to its nearest centroid using Euclidean distance.

  3. Recompute centroids: Replace every centroid with the mean of its assigned points.

  4. Repeat: Continue until assignments stop changing or another stopping condition is reached.

Each iteration has approximate time complexity O(n * k * d), where n is the number of observations, k is the number of clusters, and d is the number of features. Lloyd’s algorithm produces a local optimum, not a guaranteed global optimum.

Comparing Initialization Strategies

Method How it works Strengths Weaknesses When to use Typical scale
Random Selects k observations uniformly at random as initial centroids. Simple and inexpensive Can start in poor configurations and vary considerably by seed Baseline comparisons or very large datasets O(k) centroid selection; Lloyd iteration remains O(n * k * d)
k-means++ Selects the first centroid randomly, then favors points far from existing centroids. Usually finds better starts and is less seed-sensitive Requires more initialization computation and temporary storage General-purpose default, including large datasets k greedy selection rounds, followed by O(n * k * d) Lloyd iterations
  • n_init: Specifies how many complete initialization-and-optimization runs are performed; scikit-learn retains the run with the lowest inertia.

  • Multiple seeds: Vary random_state to measure sensitivity rather than relying on one favorable run.

  • Local optimum: Initialization affects which local optimum is reached, so compare repeated runs rather than one result.

Benchmark Design

  • Standardize training data: Fit StandardScaler only on the training partition through a Pipeline to avoid leakage.

  • Training inertia: Lower is better for the fitted training objective.

  • Validation inertia: Lower suggests better centroid fit on unseen observations.

  • Silhouette score: Higher is better, although it is sensitive to geometry, dimensionality, and scaling.

  • Adjusted Rand Index: Compares predicted labels with known synthetic labels and is invariant to cluster-label permutations.

  • Runtime and iterations: Record end-to-end pipeline fit time and n_iter_ to quantify computational behavior.

  • Use a held-out validation set for comparing configurations; reserve a separate untouched test set for final evaluation if these results drive selection.

Code Example

import time

import numpy as np

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import adjusted_rand_score, silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

X, y = make_blobs(
    n_samples=600,
    n_features=2,
    centers=4,
    cluster_std=1.0,
    random_state=42,
)

X_train, X_validation, y_train, y_validation = train_test_split(
    X,
    y,
    test_size=0.25,
    random_state=42,
    stratify=y,
)


def make_model(init, n_init, seed):
    # The pipeline fits the scaler only on X_train.
    return Pipeline([
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=4,
            init=init,
            n_init=n_init,
            random_state=seed,
        )),
    ])


def safe_silhouette(features, labels):
    unique_count = len(np.unique(labels))
    if unique_count <= 1 or unique_count >= len(features):
        return np.nan
    return silhouette_score(features, labels)


def evaluate(model, X_validation_scaled, y_validation):
    kmeans = model.named_steps["kmeans"]
    predictions = kmeans.predict(X_validation_scaled)

    squared_distances = (
        X_validation_scaled[:, None, :] - kmeans.cluster_centers_[None, :, :]
    ) ** 2
    validation_inertia = squared_distances.sum(axis=2).min(axis=1).sum()

    return {
        "train_inertia": kmeans.inertia_,
        "validation_inertia": validation_inertia,
        "silhouette": safe_silhouette(X_validation_scaled, predictions),
        "adjusted_rand_index": adjusted_rand_score(y_validation, predictions),
    }


configs = {
    "random, 1 run": ("random", 1),
    "k-means++, 1 run": ("k-means++", 1),
    "random, 10 runs": ("random", 10),
    "k-means++, 10 runs": ("k-means++", 10),
}

rows = []
representative_sizes = {}

for seed in range(10):
    for name, (init, n_init) in configs.items():
        model = make_model(init, n_init, seed)

        start = time.perf_counter()
        model.fit(X_train)
        fit_seconds = time.perf_counter() - start

        X_validation_scaled = model.named_steps["scaler"].transform(
            X_validation
        )
        metrics = evaluate(model, X_validation_scaled, y_validation)
        metrics["pipeline_fit_seconds"] = fit_seconds
        metrics["iterations"] = model.named_steps["kmeans"].n_iter_
        rows.append({"configuration": name, **metrics})

        if seed == 0:
            labels = model.named_steps["kmeans"].labels_
            representative_sizes[name] = np.bincount(labels, minlength=4)

print("Initialization comparison: mean +/- standard deviation")
for name in configs:
    selected = [row for row in rows if row["configuration"] == name]
    print(f"\n{name}")
    for metric in (
        "train_inertia",
        "validation_inertia",
        "silhouette",
        "adjusted_rand_index",
        "pipeline_fit_seconds",
        "iterations",
    ):
        values = np.array([row[metric] for row in selected], dtype=float)
        print(
            f"  {metric}: {np.nanmean(values):.3f} "
            f"+/- {np.nanstd(values):.3f}"
        )
    print(
        f"  first-run cluster sizes: {representative_sizes[name].tolist()}"
    )

# Inspect plausible values of k with an elbow-style diagnostic.
print("\nElbow diagnostic using k-means++")
print(" k    train inertia    silhouette")
for k in range(2, 7):
    model = make_model("k-means++", 10, 42)
    model.fit(X_train)
    X_train_scaled = model.named_steps["scaler"].transform(X_train)
    kmeans = model.named_steps["kmeans"]
    score = safe_silhouette(X_train_scaled, kmeans.labels_)
    print(f"{k:2d}    {kmeans.inertia_:12.3f}    {score:11.3f}")

Common Pitfalls

  • Not scaling features: Features with larger numerical scales dominate Euclidean distances.

  • Treating the elbow as exact: It is a visual heuristic; combine it with silhouette scores and domain knowledge.

  • Ignoring outliers or cluster shape: K-means favors roughly spherical, similarly sized clusters; consider k-medoids, Gaussian mixtures, DBSCAN, or HDBSCAN.

  • Using categorical features directly: Consider k-modes for nominal variables.

  • Overfitting the benchmark: Do not repeatedly tune against an untouched final test set.

  • Ignoring variability and runtime: Report multiple seeds, convergence iterations, and fit time rather than one result.

  • Large datasets: Consider MiniBatchKMeans when standard K-means becomes too slow.

36

How do you compute the silhouette coefficient for clustering evaluation in Python?

The silhouette coefficient measures how well each point fits its assigned cluster by comparing its average distance to its own cluster with its average distance to the nearest other cluster. A higher mean score indicates better-defined clusters, with values ranging from -1 to 1. Its main trade-off is easy interpretation in exchange for sensitivity to distance choice, feature scaling, cluster shape, and the selected number of clusters.

Read full answer

Applies toscikit-learn 1.5+ and NumPy 2.x (Python 3.12)

How It Works

For each sample i, the silhouette coefficient is:

s(i) = (b(i) - a(i)) / max(a(i), b(i))

  • a(i): Average distance from sample i to other samples in its cluster; smaller means better cohesion.

  • b(i): Smallest average distance from sample i to samples in any other cluster; larger means better separation.

  • Silhouette score: Mean of s(i) across all evaluated samples.

Scikit-learn assigns 0 to samples in singleton clusters because no meaningful intra-cluster average exists. Such values can make the overall result misleading, so cluster sizes should also be inspected.

K-Means Context

Lloyd’s algorithm proceeds as follows:

  1. Initialize k centroids. Scikit-learn defaults to init="k-means++", which selects initial centers with probability proportional to their squared distance from the closest existing center.

  2. Assign every sample to its nearest centroid.

  3. Recompute each centroid as the mean of its assigned samples.

  4. Repeat the assignment and recomputation steps until assignments stop changing or another stopping criterion is reached.

This optimizes the within-cluster sum of squares, exposed by scikit-learn as inertia_, but normally converges to a local optimum. A numeric n_init=10 runs ten initializations and retains the result with the lowest inertia; n_init="auto" means one initialization for init="k-means++" in scikit-learn 1.5+. Use MiniBatchKMeans when the dataset is too large for standard K-Means.

Evaluation Guidance

  • Compare silhouette scores across reasonable values of k or clustering algorithms.

  • Standardize features with different units or magnitudes before clustering.

  • Use validation data for model selection and reserve test data for final evaluation.

  • Do not rely on silhouette alone; inspect cluster sizes, centroids, and domain-level meaning.

Code Example

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_samples, silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

# Generate reproducible synthetic clusters.
X, _ = make_blobs(
    n_samples=600,
    n_features=2,
    centers=3,
    cluster_std=1.0,
    random_state=42,
)

# Separate training, validation, and final test data.
X_train, X_temp, X_test = train_test_split(
    X, test_size=0.2, random_state=42
)
X_train, X_validation = train_test_split(
    X_train, test_size=0.25, random_state=42
)


def make_model(k):
    return Pipeline([
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=k,
            init="k-means++",
            n_init=10,
            random_state=42,
        )),
    ])


# Compare candidate values of k without inspecting the test set.
for k in range(2, 6):
    candidate = make_model(k)
    candidate.fit(X_train)
    validation_labels = candidate.predict(X_validation)
    validation_score = silhouette_score(
        X_validation, validation_labels
    )
    inertia = candidate.named_steps["kmeans"].inertia_
    print(
        f"k={k}: inertia={inertia:.3f}, "
        f"validation silhouette={validation_score:.3f}"
    )

# The synthetic data was generated with three centers.
final_model = make_model(3)
final_model.fit(X_train)
test_labels = final_model.predict(X_test)
values = silhouette_samples(X_test, test_labels)
score = silhouette_score(X_test, test_labels)

print(f"Test silhouette score: {score:.3f}")
print(f"Per-sample range: {values.min():.3f} to {values.max():.3f}")
for cluster_id in np.unique(test_labels):
    size = np.sum(test_labels == cluster_id)
    print(f"Cluster {cluster_id}: {size} samples")

Practical Considerations

  • Euclidean distance is conventional, but silhouette_score and silhouette_samples accept other metric values.

  • Exact silhouette evaluation can require O(n²) pairwise-distance work and storage.

  • The coefficient is most informative for compact, reasonably separated clusters.

Common Pitfalls

  • Not scaling features: Large-magnitude features can dominate both clustering and distance calculations.

  • Choosing k from one score: Combine silhouette analysis with the elbow method, stability checks, and domain interpretation; the elbow is not an exact cutoff.

  • Ignoring assumptions: K-Means requires choosing k and tends to assume roughly spherical, similarly sized clusters; it is also sensitive to outliers.

  • Ignoring cluster profiles: A high score does not prove that clusters have meaningful business interpretations.

  • Handling degenerate clusters: Scikit-learn relocates centroids for empty clusters encountered during Lloyd iterations, while singleton clusters receive silhouette values of 0.

  • Using unsuitable alternatives: For categorical data, consider k-modes; for non-spherical or irregular structures, consider k-medoids, Gaussian Mixture Models, DBSCAN, or HDBSCAN.

37

How do I implement MiniBatchKMeans clustering in Python?

Mini-batch K-Means is an unsupervised clustering algorithm that divides unlabeled data into k groups by minimizing the squared distance between each point and its cluster centroid. It solves customer segmentation, document grouping, image compression, and other partitioning problems. Its main trade-off is faster training on large datasets in exchange for less stable results than full K-Means.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

How the Algorithm Works

Lloyd’s algorithm performs these steps:

  1. Initialize k centroids.

  2. Assign every point to its nearest centroid.

  3. Recalculate each centroid as the mean of its assigned points.

  4. Repeat until assignments stop changing or another convergence condition is reached.

Mini-batch K-Means modifies step 2 by processing small batches instead of the entire dataset. Each batch updates the centroids using exponentially decaying weights, allowing the algorithm to perform less computation per update.

The objective is the inertia, also called the within-cluster sum of squares:

inertia = sum of the squared Euclidean distance from each point to its assigned centroid

The sum covers all n points. The number of clusters is k, and the number of features is d.

Initialization and Convergence

  • k-means++ initialization: Selects the first centroid randomly, then selects later centroids with higher probability when they are far from existing centroids. This is the scikit-learn default for both KMeans and MiniBatchKMeans.

  • n_init: Runs the algorithm several times and retains the run with the lowest inertia. Using n_init=10 is more reliable than relying on a single run.

  • Local optimum: K-Means can stop at a locally optimal solution, so different initializations can produce different clusters.

  • batch_size: Controls how many samples participate in each update. Smaller batches update more frequently but may be noisier.

  • max_no_improvement: Stops when inertia has not improved for the specified number of consecutive iterations.

  • reassignment_ratio: Limits the fraction of samples that can be reassigned to a cluster during a mini-batch update. Its default is 0.01.

  • partial_fit: Updates the existing centroids with new data without reinitializing them, allowing incremental or online learning.

Full K-Means requires approximately O(n * k * d) work per iteration. A mini-batch update has dominant arithmetic of approximately O(batch_size * k * d), although total work depends on the number of batches processed. The model stores O(k * d) centroid parameters, while a batch buffer requires memory proportional to the batch and feature dimensions.

Selecting k and Comparing Alternatives

Use the elbow method to inspect inertia across several values of k, and use the silhouette score to measure separation. Neither criterion identifies one universally correct answer; combine them with domain knowledge and cluster stability.

Algorithm How it works Strengths Weaknesses Typical use
KMeans Full Lloyd iterations Accurate on compact clusters Slow on very large datasets Medium-sized numeric datasets
MiniBatchKMeans Updates centroids from small batches Fast and memory efficient More initialization sensitivity Large or incremental datasets
K-Medoids Uses actual data points as centers More robust to outliers Slower and memory intensive Small or noisy datasets
Gaussian Mixture Models probabilistic clusters Supports soft assignments Assumes cluster distributions Overlapping numeric clusters
DBSCAN/HDBSCAN Groups points through density connectivity Finds arbitrary-shaped clusters Parameter-sensitive Irregular clusters or noisy data

Code Example

import numpy as np

from sklearn.cluster import KMeans, MiniBatchKMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

# Generate reproducible synthetic data with four underlying groups.
X, _ = make_blobs(
    n_samples=500,
    centers=4,
    cluster_std=1.25,
    random_state=42,
)

# Keep final evaluation data separate from model fitting.
X_train, X_test = train_test_split(
    X,
    test_size=0.2,
    random_state=42,
)


def build_pipeline(estimator):
    # Pipeline fits the scaler only on the training data.
    return Pipeline([
        ("scaler", StandardScaler()),
        ("cluster", estimator),
    ])


candidate_results = []

for k in range(2, 7):
    # Full K-Means provides a reference inertia curve.
    full_model = build_pipeline(
        KMeans(
            n_clusters=k,
            init="k-means++",
            n_init=10,
            random_state=42,
        )
    )
    full_model.fit(X_train)

    # MiniBatchKMeans is the scalable clustering implementation.
    mini_model = build_pipeline(
        MiniBatchKMeans(
            n_clusters=k,
            init="k-means++",
            n_init=10,
            batch_size=64,
            max_iter=100,
            max_no_improvement=10,
            reassignment_ratio=0.01,
            random_state=42,
        )
    )
    mini_model.fit(X_train)

    scaler = mini_model.named_steps["scaler"]
    clusterer = mini_model.named_steps["cluster"]

    scaled_train = scaler.transform(X_train)
    train_labels = clusterer.predict(scaled_train)
    silhouette = silhouette_score(scaled_train, train_labels)

    candidate_results.append((k, silhouette))
    print(
        f"k={k}: MiniBatch inertia={clusterer.inertia_:.3f}, "
        f"silhouette={silhouette:.3f}, "
        f"KMeans reference inertia="
        f"{full_model.named_steps['cluster'].inertia_:.3f}"
    )

# Select the candidate with the highest training silhouette score.
best_k = max(candidate_results, key=lambda result: result[1])[0]

# Fit the selected mini-batch model for deployment.
final_model = build_pipeline(
    MiniBatchKMeans(
        n_clusters=best_k,
        init="k-means++",
        n_init=10,
        batch_size=64,
        max_iter=100,
        max_no_improvement=10,
        reassignment_ratio=0.01,
        random_state=42,
    )
)
final_model.fit(X_train)

scaler = final_model.named_steps["scaler"]
clusterer = final_model.named_steps["cluster"]

train_labels = clusterer.predict(scaler.transform(X_train))
test_labels = clusterer.predict(scaler.transform(X_test))
cluster_sizes = np.bincount(train_labels, minlength=best_k)

print("Selected k:", best_k)
print("Cluster sizes:", cluster_sizes)
print("Final inertia:", clusterer.inertia_)

if 2 <= len(np.unique(test_labels)) < len(test_labels):
    test_silhouette = silhouette_score(
        scaler.transform(X_test),
        test_labels,
    )
    print("Test silhouette:", test_silhouette)

Common Pitfalls

  • Skipping feature scaling: Features with larger numeric ranges dominate Euclidean distance. Scale numeric features before clustering.

  • Treating the elbow as exact: The elbow is a heuristic, not proof of an optimal cluster count.

  • Ignoring outliers: Extreme values can pull centroids substantially. Inspect, transform, or remove severe outliers.

  • Using categorical features directly: K-Means is designed for numerical distances; use K-Modes or an appropriate embedding for categorical data.

  • Assuming spherical clusters: K-Means works best for roughly compact, similarly sized groups. Consider DBSCAN, HDBSCAN, or Gaussian Mixture Models otherwise.

  • Interpreting clusters without profiling them: Analyze feature distributions, sizes, and business meaning before assigning a label to each cluster.

  • Reporting an unstable result: Compare multiple random seeds and restarts. Mini-batch clustering can vary more than full K-Means.

38

How do I assign a new data point to a K-Means centroid?

A new observation is associated with the nearest-centroid cluster using Euclidean distance. In scikit-learn, KMeans.predict() returns the cluster label, while KMeans.transform() returns the distance to every centroid. K-Means is fast and interpretable, but its result depends on initialization and it assumes compact, roughly spherical clusters.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

How Lloyd’s Algorithm Works

K-Means minimizes the within-cluster sum of squares, also called inertia:

inertia = sum_i ||x_i - c_(cluster of x_i)||^2

Here, x_i is observation i, c_(cluster of x_i) is its assigned centroid, and ||...||^2 is squared Euclidean distance.

  1. Initialize centroids: Select k initial cluster centers.

  2. Assign observations: Assign each point to the closest centroid.

  3. Recompute centroids: Calculate the mean position of all points assigned to each cluster.

  4. Repeat: Continue until assignments stop changing or max_iter is reached.

The implementation uses k-means++ initialization, scikit-learn’s default. After choosing the first centroid randomly, subsequent centers are selected with a probability based on their squared distance from the closest existing center. This usually produces better-separated initial centroids than uniform random selection.

With n_init=10, Lloyd’s algorithm runs ten times, and scikit-learn retains the run with the lowest inertia. Because the objective is non-convex, the result is a local optimum rather than a guaranteed global optimum.

Assigning a New Point

For an already fitted model, assignment does not require retraining:

  • model.predict(new_point) returns the nearest centroid’s cluster label.

  • model.transform(new_point) returns the Euclidean distance from the point to each centroid.

  • The smallest distance identifies the selected centroid.

When a Pipeline contains a StandardScaler and KMeans, transform the new raw observation with the fitted scaler before calling the K-Means methods. The example below also converts the selected standardized centroid back to the original feature units.

Complexity and Alternatives

Each Lloyd iteration takes approximately O(n × k × d) time, where n is the number of observations, k is the number of clusters, and d is the number of features. For large datasets, MiniBatchKMeans reduces computation by updating centroids using small batches.

Method How it works Strengths Weaknesses When to use
K-Means Assigns points and updates centroid means Fast, scalable, simple Sensitive to scaling, outliers, initialization, and k Approximately spherical numerical clusters
K-Medoids Uses actual observations as centers More robust to outliers Slower on large datasets Small or medium datasets with outliers
Gaussian Mixture Model Models clusters as probability distributions Supports elliptical clusters and soft assignments More computationally expensive Overlapping or differently shaped clusters
DBSCAN/HDBSCAN Finds density-connected groups Does not require k; detects noise Density assumptions complicate tuning Irregular clusters or datasets containing noise

Code Example

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler


def identify_nearest_centroid(
    model: Pipeline,
    new_point: np.ndarray,
) -> tuple[int, np.ndarray, np.ndarray]:
    """Return the cluster label, centroid distances, and raw-space centroid."""
    point = np.asarray(new_point, dtype=float)

    if point.ndim == 1:
        point = point.reshape(1, -1)
    if point.ndim != 2:
        raise ValueError("new_point must contain one or more observations")

    scaler = model.named_steps["scaler"]
    kmeans = model.named_steps["kmeans"]

    if point.shape[1] != kmeans.n_features_in_:
        raise ValueError("new_point has an incorrect number of features")

    # Apply the preprocessing fitted only on the training data.
    scaled_point = scaler.transform(point)

    # Assignment does not modify or refit the existing model.
    cluster_id = int(kmeans.predict(scaled_point)[0])
    distances = kmeans.transform(scaled_point)[0]

    # Express the selected centroid in the original feature units.
    raw_centroid = scaler.inverse_transform(
        kmeans.cluster_centers_[cluster_id].reshape(1, -1)
    )[0]

    return cluster_id, distances, raw_centroid


# Generate reproducible synthetic data and split before fitting preprocessing.
X, y = make_blobs(
    n_samples=300,
    centers=3,
    cluster_std=1.0,
    random_state=42,
)
X_train, X_test, y_train, y_test = train_test_split(
    X,
    y,
    test_size=0.2,
    random_state=42,
    stratify=y,
)

# Compare several values of k using training inertia and test silhouette.
models = {}
silhouette_scores = {}

for k in range(2, 6):
    candidate = Pipeline([
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=k,
            init="k-means++",
            n_init=10,
            random_state=42,
        )),
    ])
    candidate.fit(X_train)

    scaler = candidate.named_steps["scaler"]
    kmeans = candidate.named_steps["kmeans"]
    scaled_test = scaler.transform(X_test)
    test_labels = kmeans.predict(scaled_test)

    models[k] = candidate
    silhouette_scores[k] = silhouette_score(scaled_test, test_labels)

    print(
        f"k={k}: inertia={kmeans.inertia_:.2f}, "
        f"silhouette={silhouette_scores[k]:.3f}"
    )

# Retain the fitted model with the highest silhouette score.
best_k = max(silhouette_scores, key=silhouette_scores.get)
best_model = models[best_k]
best_kmeans = best_model.named_steps["kmeans"]

cluster_sizes = np.bincount(
    best_kmeans.labels_,
    minlength=best_k,
)
print(f"Selected k: {best_k}")
print(f"Training cluster sizes: {cluster_sizes}")

# Assign a new observation expressed in the original feature units.
cluster_id, distances, centroid = identify_nearest_centroid(
    best_model,
    np.array([[5.0, 1.8]]),
)

print(f"Selected cluster: {cluster_id}")
print(f"Distances to centroids: {distances}")
print(f"Selected centroid in original units: {centroid}")

Common Pitfalls

  • Skipping feature scaling: Large-magnitude features dominate Euclidean distance; fit StandardScaler on training data only.

  • Confusing an elbow with an exact answer: Compare multiple k values using inertia, silhouette, domain knowledge, and cluster profiling.

  • Refitting during assignment: Use the existing fitted scaler and K-Means model; do not refit on the new point.

  • Ignoring outliers: K-Means centroids can be pulled toward isolated extreme observations.

  • Using Euclidean distance on arbitrary categorical features: Use a suitable categorical method such as k-modes instead.

  • Interpreting clusters without profiling: Examine feature distributions and cluster characteristics before assigning semantic meaning.

  • Leakage: Fit preprocessing only on training data and evaluate transformations on validation or test data separately.

  • Likely interview follow-ups: Explain why k-means++ is used, why results vary between runs, or how MiniBatchKMeans reduces computation.

39

How to clean and prepare real-world data for K-Means clustering?

K-Means clustering is an unsupervised method that groups observations around k centroids to minimize within-cluster variation. It supports customer segmentation, grouping, and pattern discovery, but its main trade-offs are sensitivity to initialization, scale, and outliers, along with the need to choose k. Its objective is WCSS = sum(j=1..k) sum(i in Cj) ||x_i - μ_j||², where x_i is observation i, μ_j is centroid j, Cj contains observations assigned to j, and the final term is squared Euclidean distance.

Read full answer

Applies toscikit-learn 1.5+ and pandas 2.2+ (Python 3.12)

Lloyd’s Algorithm

Lloyd’s algorithm repeats these steps:

  1. Initialize centroids: Select k starting centers, commonly with k-means++.

  2. Assign observations: Assign each point to its nearest centroid.

  3. Recompute centroids: Calculate each centroid as the mean of its assigned points.

  4. Repeat: Continue until assignments stabilize or max_iter is reached.

The updates do not increase WCSS, also called inertia, but the result is a local optimum rather than necessarily the global optimum.

Initialization and Complexity

  • k-means++: The scikit-learn default; it selects initial centers with some separation to reduce poor local solutions.

  • n_init: The number of initializations. Scikit-learn retains the run with the lowest inertia; n_init=10 explicitly requests ten restarts.

  • Time complexity: Approximately O(n * k * d) per iteration, where n is observations, k is clusters, and d is features.

  • Large datasets: MiniBatchKMeans updates centers from small batches and scales better, although its centers may be less precise.

Data Preparation

  • Remove exact duplicate records and coerce invalid numeric values to missing values.

  • Impute missing values, fitting the imputer only on the relevant training partition.

  • Standardize numerical features so large-scale variables do not dominate Euclidean distances.

  • Inspect outliers because extreme observations can pull centroids toward themselves.

  • Avoid arbitrary encoding of categorical variables; use k-modes or another method designed for categorical data.

  • Select k using cross-validation, silhouette scores, and domain knowledge; the elbow is a guide, not an exact answer.

  • Profile clusters using original feature values. Labels such as cluster 0 have no inherent meaning.

Code Example

import numpy as np
import pandas as pd
from sklearn.cluster import KMeans
from sklearn.datasets import load_breast_cancer
from sklearn.impute import SimpleImputer
from sklearn.metrics import silhouette_score
from sklearn.model_selection import KFold, train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

data = load_breast_cancer()
df = pd.DataFrame(data.data, columns=data.feature_names)

# Perform structural cleaning without learning any parameters.
df = df.apply(pd.to_numeric, errors="coerce")
duplicate_mask = df.duplicated(keep="first")
df = df.loc[~duplicate_mask].reset_index(drop=True)

features = [
    "mean radius",
    "mean texture",
    "mean compactness",
    "mean concavity",
]
X = df[features]

X_train, X_test = train_test_split(
    X, test_size=0.25, random_state=42
)

def build_model(k):
    return Pipeline([
        ("preprocess", Pipeline([
            ("imputer", SimpleImputer(strategy="median")),
            ("scaler", StandardScaler()),
        ])),
        ("kmeans", KMeans(
            n_clusters=k,
            init="k-means++",
            n_init=10,
            random_state=42,
        )),
    ])

# Cross-validation fits preprocessing separately on each training fold.
cv = KFold(n_splits=5, shuffle=True, random_state=42)
results = []

for k in range(2, 8):
    scores = []
    for train_idx, validation_idx in cv.split(X_train):
        fold_model = build_model(k)
        fold_model.fit(X_train.iloc[train_idx])

        scaled_validation = fold_model.named_steps[
            "preprocess"
        ].transform(X_train.iloc[validation_idx])
        labels = fold_model.named_steps["kmeans"].predict(
            scaled_validation
        )

        if 1 < len(np.unique(labels)) < len(labels):
            scores.append(
                silhouette_score(scaled_validation, labels)
            )

    model = build_model(k).fit(X_train)
    inertia = model.named_steps["kmeans"].inertia_
    mean_score = np.nanmean(scores)
    results.append((k, mean_score, inertia))
    print(
        f"k={k}: inertia={inertia:.2f}, "
        f"CV silhouette={mean_score:.3f}"
    )

selected_k = max(results, key=lambda result: result[1])[0]
model = build_model(selected_k).fit(X_train)

labels = model.predict(X_train)
print("Selected k:", selected_k)
print("Cluster sizes:", pd.Series(labels).value_counts().sort_index().to_dict())

centroids = model.named_steps["kmeans"].cluster_centers_
profile = pd.DataFrame(
    model.named_steps["preprocess"].inverse_transform(centroids),
    columns=features,
)
print(profile.round(2))

scaled_test = model.named_steps["preprocess"].transform(X_test)
test_labels = model.named_steps["kmeans"].predict(scaled_test)
print(f"Test silhouette={silhouette_score(scaled_test, test_labels):.3f}")

Alternatives and Limitations

Method How it works Strengths Weaknesses When to use
KMeans Euclidean distance and mean centers Fast and scalable Requires spherical, similar-sized clusters; sensitive to outliers Well-scaled continuous data
MiniBatchKMeans Updates centers from sample batches Faster for large data Less precise centers Very large datasets
k-medoids Uses actual observations as centers Interpretable centers Less scalable and still outlier-sensitive Small or moderate datasets
Gaussian mixture Probabilistic assignments Soft assignments and elliptical clusters More computation and stronger assumptions Overlapping continuous distributions
DBSCAN/HDBSCAN Connects dense regions Arbitrary shapes and noise detection Parameter or density assumptions Irregular clusters or substantial noise

Common Pitfalls

  • Not scaling: Larger-range variables dominate distance.

  • Ignoring outliers: Extreme points can substantially shift centroids.

  • Using categorical data: Arbitrary numeric categories create meaningless distances.

  • Choosing k mechanically: Combine validation results, domain knowledge, and interpretability.

  • Leakage: Fit imputers, scalers, and K-Means only on the appropriate training data.

  • Overfitting: Too many clusters can produce narrow, unstable groups.

  • Ignoring reproducibility: Set random_state and retain multiple initializations.

  • Misusing accuracy: K-Means has no required ground-truth label mapping; use inertia, silhouette score, stability, and interpretability.

Interviewers commonly ask about feature scaling, local optima, selecting k, and when DBSCAN or a Gaussian mixture model is preferable.

40

How to visualize multi-dimensional K-Means clusters with PCA?

K-Means clustering groups unlabeled data points around k centroids, making it useful for customer segmentation, document grouping, and pattern discovery. PCA can then project the high-dimensional clusters onto two axes for visualization, but it does not perform the clustering itself. The main trade-off is that K-Means is simple and fast, but sensitive to feature scaling, outliers, initialization, and the chosen value of k.

Read full answer

Applies toscikit-learn 1.5+ with NumPy 2.x (Python 3.12)

How It Works

K-Means uses Lloyd’s algorithm:

  1. Choose k centroids. Scikit-learn uses k-means++ initialization by default, which selects initial centroids that are more separated than a purely random selection.

  2. Assign every point to its nearest centroid.

  3. Recompute each centroid as the mean of its assigned points.

  4. Repeat until assignments stop changing or another stopping condition is reached.

  5. Set n_init to a positive integer such as 10 to run several initializations and retain the solution with the lowest inertia. With n_init="auto", scikit-learn runs one k-means++ initialization.

The objective is the within-cluster sum of squares:

inertia = sum over points of squared distance to the assigned centroid

A smaller inertia means the points are, on average, closer to their centroids. Each iteration has approximate time complexity O(n * k * d), where n is the number of points, k is the number of clusters, and d is the number of features. K-Means converges to a local optimum rather than necessarily the globally optimal partition.

Code Example

import numpy as np
import matplotlib.pyplot as plt

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.decomposition import PCA
from sklearn.metrics import silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler


# Create five-dimensional data containing three synthetic groups.
X, y = make_blobs(
    n_samples=600,
    n_features=5,
    centers=3,
    cluster_std=1.2,
    random_state=42,
)

# Keep the test set separate for final evaluation.
X_temp, X_test, y_temp, y_test = train_test_split(
    X, y, test_size=0.25, stratify=y, random_state=42
)

# Use the remaining data for model fitting and k selection.
X_train, X_val, y_train, y_val = train_test_split(
    X_temp, y_temp, test_size=0.25, stratify=y_temp, random_state=42
)


def build_pipeline(k):
    return Pipeline([
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=k,
            n_init=10,
            random_state=42,
        )),
    ])


# Compare several values of k on validation data.
validation_results = []

for k in range(2, 7):
    candidate = build_pipeline(k).fit(X_train)

    X_val_scaled = candidate.named_steps["scaler"].transform(X_val)
    val_labels = candidate.predict(X_val)

    silhouette = (
        silhouette_score(X_val_scaled, val_labels)
        if len(np.unique(val_labels)) > 1
        else float("nan")
    )

    train_inertia = candidate.named_steps["kmeans"].inertia_
    validation_results.append((k, train_inertia, silhouette))

    print(
        f"k={k}: training inertia={train_inertia:.2f}, "
        f"validation silhouette={silhouette:.3f}"
    )

# Select k using validation performance, not test performance.
best_k = max(validation_results, key=lambda result: result[2])[0]

# Refit the selected model using training and validation data.
X_fit = np.vstack((X_train, X_val))
final_model = build_pipeline(best_k).fit(X_fit)

scaler = final_model.named_steps["scaler"]
kmeans = final_model.named_steps["kmeans"]

# Evaluate on the untouched test set.
X_test_scaled = scaler.transform(X_test)
test_labels = kmeans.predict(X_test_scaled)

test_inertia = np.sum(
    (X_test_scaled - kmeans.cluster_centers_[test_labels]) ** 2
)

test_silhouette = (
    silhouette_score(X_test_scaled, test_labels)
    if len(np.unique(test_labels)) > 1
    else float("nan")
)

# Assign every point using the already fitted model.
X_all_scaled = scaler.transform(X)
all_labels = kmeans.predict(X_all_scaled)
cluster_sizes = np.bincount(all_labels, minlength=best_k)

print(f"\nSelected k: {best_k}")
print(f"Test inertia: {test_inertia:.2f}")
print(f"Test silhouette score: {test_silhouette:.3f}")
print("Cluster sizes:", cluster_sizes)

# Fit PCA only on data used to train the final model.
X_fit_scaled = scaler.transform(X_fit)
pca = PCA(n_components=2, random_state=42)
pca.fit(X_fit_scaled)
coordinates = pca.transform(X_all_scaled)

print(
    "PCA explained variance:",
    np.round(pca.explained_variance_ratio_, 3),
)

# Compare the synthetic groups with the discovered clusters.
fig, axes = plt.subplots(1, 2, figsize=(12, 5))

axes[0].scatter(
    coordinates[:, 0], coordinates[:, 1],
    c=y, cmap="viridis", alpha=0.7
)
axes[0].set_title("Original synthetic groups")

axes[1].scatter(
    coordinates[:, 0], coordinates[:, 1],
    c=all_labels, cmap="viridis", alpha=0.7
)
axes[1].set_title("K-Means clusters")

for ax in axes:
    ax.set_xlabel("Principal component 1")
    ax.set_ylabel("Principal component 2")

plt.tight_layout()
plt.show()

Choosing and Evaluating k

  • Elbow method: Plot inertia against k and look for a point where further increases in k produce diminishing reductions in inertia. The elbow is a heuristic, not an exact rule.

  • Silhouette score: Ranges from -1 to 1; higher values generally indicate better separation, where 0 represents substantial overlap and negative values suggest incorrect assignments.

  • Cluster inspection: Examine feature profiles within each cluster. Cluster numbers are arbitrary labels and do not imply an ordering or meaning.

PCA is fitted on the same scaled features used to train the final model. Its two-dimensional projection may obscure structure present in the original space, so inspect the explained variance and compare results in the original feature space when decisions matter.

Best Practices

  • Scale features: K-Means minimizes squared Euclidean distance, so large-scale features can dominate the assignment process.

  • Prevent leakage: Fit the scaler, K-Means, and PCA only on training or training-validation data, as shown above.

  • Address outliers: Extreme values can pull centroids away from dense regions.

  • Control reproducibility: Set random_state=42; K-Means can produce different local optima from different initializations.

  • Use the appropriate method: K-Means works best for roughly spherical, similarly sized numeric clusters. Consider MiniBatchKMeans for large datasets, k-medoids for robustness to outliers, Gaussian mixture models for elliptical clusters, or DBSCAN/HDBSCAN for irregular clusters and noise.

Common Pitfalls

  • Running K-Means on unscaled numerical features.

  • Selecting k from the test set, which contaminates final evaluation.

  • Treating the elbow as an objectively correct cluster count.

  • Applying K-Means directly to categorical data; use k-modes or appropriate embeddings instead.

  • Interpreting clusters without profiling their feature values and validating them against the business objective.

41

How does K-Means segment retail customers?

K-Means segments retail customers by grouping customers with similar behavioral features such as recency, order frequency, and spending. It minimizes within-cluster squared distance by assigning customers to centroids and repeatedly updating each centroid to its cluster’s mean. Its main trade-off is speed and simplicity versus sensitivity to scaling and outliers, the need to choose k, and the assumption that clusters are roughly spherical and similarly sized.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

How It Works

  1. Create customer features: Use one row per customer, such as recency_days, average monthly orders, annual spending, or average order value.

  2. Scale the features: Apply StandardScaler so large-valued features do not dominate Euclidean distances. Fit it only on training data to prevent leakage.

  3. Run Lloyd’s algorithm:

  4. Initialize k centroids.

  5. Assign every customer to its nearest centroid.

  6. Recalculate each centroid as the mean of its assigned customers.

  7. Repeat until assignments stabilize or another stopping criterion is reached.

The minimized objective is:

WCSS = sum(j=1 to k) sum(x_i in C_j) ||x_i - μ_j||²

Here, WCSS is the within-cluster sum of squares, k is the number of clusters, C_j is cluster j, x_i is customer i’s feature vector, and μ_j is centroid j. The summation adds every customer’s squared Euclidean distance from its centroid.

Scikit-learn uses k-means++ initialization, which selects later centroids probabilistically based on squared distances from existing centroids. Its n_init parameter performs multiple initializations and retains the solution with the lowest inertia. The result depends on initialization and converges to a local optimum rather than guaranteeing the global optimum.

After fitting, calculate each segment’s average recency, frequency, and spending, then assign a business-meaningful label. Cluster IDs alone have no business meaning.

Code Example

import numpy as np
import pandas as pd

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

# Generate deterministic synthetic customer features.
blob, _ = make_blobs(
    n_samples=600,
    centers=4,
    n_features=3,
    cluster_std=1.1,
    random_state=42,
)
X = np.column_stack([
    np.clip(35 + 6 * blob[:, 0], 1, None),
    np.clip(8 + 2.5 * blob[:, 1], 0, None),
    np.clip(700 + 180 * blob[:, 2], 0, None),
])

# Hold out data before fitting the scaler and clustering model.
X_train, X_temp = train_test_split(X, test_size=0.40, random_state=42)
X_val, X_test = train_test_split(X_temp, test_size=0.50, random_state=42)

results = []
for k in range(2, 7):
    pipeline = make_pipeline(
        StandardScaler(),
        KMeans(n_clusters=k, n_init=10, random_state=42),
    )
    pipeline.fit(X_train)

    scaler = pipeline.named_steps["standardscaler"]
    model = pipeline.named_steps["kmeans"]
    labels_val = model.predict(scaler.transform(X_val))

    results.append({
        "k": k,
        "inertia": model.inertia_,
        "silhouette": silhouette_score(
            scaler.transform(X_val), labels_val
        ),
    })

scores = pd.DataFrame(results)
print(scores.round(3))
best_k = int(scores.loc[scores["silhouette"].idxmax(), "k"])

# Fit the selected model and evaluate it on unseen test data.
final_model = make_pipeline(
    StandardScaler(),
    KMeans(n_clusters=best_k, n_init=10, random_state=42),
)
final_model.fit(X_train)

scaler = final_model.named_steps["standardscaler"]
model = final_model.named_steps["kmeans"]
labels_test = model.predict(scaler.transform(X_test))
print("Selected k:", best_k)
print("Test silhouette:", round(silhouette_score(
    scaler.transform(X_test), labels_test
), 3))

# Assign segment IDs and profile the segments.
labels_all = final_model.predict(X)
customers = pd.DataFrame(
    X, columns=["recency_days", "orders_month", "annual_spend"]
)
customers["segment"] = labels_all
print("Cluster sizes:", np.bincount(labels_all, minlength=best_k))
print(customers.groupby("segment").mean().round(2))

Choosing and Evaluating k

  • Inertia: The globally optimized objective cannot increase when another cluster is allowed, but independently fitted local solutions can occasionally be non-monotonic. Smaller inertia therefore does not automatically mean a better segmentation.

  • Elbow method: Look for diminishing reductions in inertia, but treat the elbow as a heuristic rather than an exact answer.

  • Silhouette score: Ranges from -1 to 1; higher values generally indicate better-separated clusters.

  • Business validation: Combine these metrics with cluster stability, segment size, interpretability, and usefulness to marketing or operations.

Each Lloyd iteration takes approximately O(n * k * d) time, where n is the number of customers, k is the number of clusters, and d is the number of features. For large datasets, MiniBatchKMeans processes smaller batches and is generally faster.

Alternatives and Trade-offs

Algorithm How it works Strengths Weaknesses When to use
K-Means Assigns points to nearest centroid Fast and scalable Requires k; sensitive to outliers and cluster shape Large datasets with compact clusters
K-Medoids Uses actual observations as centers Interpretable and more robust to outliers Can be slow at large scale Medium datasets requiring representative customers
Gaussian Mixture Models probabilistic, elliptical clusters Soft assignments More assumptions and parameters Overlapping customer groups
DBSCAN/HDBSCAN Groups dense regions and identifies noise Handles irregular clusters Less interpretable centers; distance calculations can be costly Complex behavioral or spatial segments

Common Pitfalls

  • Not scaling features: Larger numerical ranges can dominate the distance calculation.

  • Ignoring missing values: StandardScaler and KMeans do not accept NaN; impute with a training-fitted imputer or remove incomplete rows before clustering.

  • Selecting k mechanically: Use the elbow and silhouette score as supporting evidence, then profile the segments.

  • Using categorical features directly: Use k-modes, suitable encodings, or another method where Euclidean distance on arbitrary category codes is not meaningful.

  • Ignoring outliers: Extreme spending values can pull centroids away from typical customers.

  • Leaking preprocessing information: Fit the scaler only on training data, as the pipeline does.

  • Treating cluster IDs as personas: Assign business labels only after examining behavior.

  • Ignoring temporal behavior: For predictive segmentation, use chronological splits to prevent future information from leaking into training.

Common follow-up questions include how k-means++ works, why inertia alone cannot choose k, how outliers affect centroids, and when DBSCAN or HDBSCAN is preferable.

42

How does K-Means clustering compress images?

K-Means clustering compresses an image through color quantization: it learns a small palette of representative colors and replaces every pixel with its nearest palette entry. The main trade-off is palette size versus color distortion. It is fast and effective for images dominated by a few colors, but initialization, outliers, and feature scaling can affect the result.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

How It Works

Represent each pixel as a feature vector:

  • RGB image: [red, green, blue]

  • Grayscale image: [intensity]

  • Alternative color spaces: CIELAB can better approximate perceptual differences for some applications.

For k clusters, K-Means learns k centroids, which become the palette. Its objective is:

J = sum_i ||x_i - c[label_i]||^2

  • x_i is pixel i.

  • label_i is that pixel’s assigned cluster.

  • c[label_i] is the assigned centroid.

  • ||...||^2 is squared Euclidean distance.

  • J is the within-cluster sum of squares, exposed as inertia_ by scikit-learn.

The result is a palette plus one palette index per pixel. For 8-bit RGB with k <= 256, the palette occupies 3 * k bytes and each index fits in one byte. These are raw payload sizes; an entropy-coding image codec may produce a smaller final file.

Lloyd’s Algorithm and Initialization

Lloyd’s algorithm performs these steps:

  1. Initialize centroids: scikit-learn defaults to k-means++, which selects initial centers with probability proportional to their squared distance from previously selected centers.

  2. Assign pixels: Give every pixel to its nearest centroid.

  3. Recompute centroids: Replace each centroid with the mean of its assigned pixels.

  4. Repeat: Continue until assignments stabilize or another stopping condition is reached.

K-Means converges to a local optimum and depends on initialization. The n_init parameter controls restarts; scikit-learn retains the restart with the lowest inertia. Each iteration costs approximately O(n * k * d), where n is the pixel count, k the palette size, and d the number of features.

Choosing the Palette Size

A small k improves compression but increases banding and color loss; a large k improves fidelity but reduces the benefit. Compare inertia, silhouette score, reconstruction error, visual quality, and final encoded file size. An elbow plot suggests candidates but does not identify one universally correct value.

Code Example

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

rng = np.random.default_rng(42)
centers = rng.uniform(0, 255, size=(6, 3))

pixel_data, _ = make_blobs(
    n_samples=1200,
    n_features=3,
    centers=centers,
    cluster_std=8.0,
    random_state=42,
)

# Convert the synthetic samples into an 8-bit RGB-like image.
pixel_data = (
    (pixel_data - pixel_data.min(axis=0))
    / np.ptp(pixel_data, axis=0)
    * 255
)
image = pixel_data.reshape(30, 40, 3).astype(np.uint8)
flat_pixels = image.reshape(-1, 3).astype(np.float64)

# Learn the palette only from training pixels.
train_pixels, heldout_pixels = train_test_split(
    flat_pixels, test_size=0.25, random_state=42
)

def fit_palette(k):
    model = Pipeline([
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=k,
            init="k-means++",
            n_init=10,
            random_state=42,
        )),
    ])
    model.fit(train_pixels)
    return model

# Compare candidate palette sizes using training and held-out data.
for k in range(2, 8):
    model = fit_palette(k)
    scaler = model.named_steps["scaler"]
    kmeans = model.named_steps["kmeans"]

    scaled_train = scaler.transform(train_pixels)
    silhouette = silhouette_score(scaled_train, kmeans.labels_)

    heldout_labels = kmeans.predict(scaler.transform(heldout_pixels))
    palette = scaler.inverse_transform(kmeans.cluster_centers_)
    reconstructed = palette[heldout_labels].clip(0, 255)
    heldout_mse = np.mean((heldout_pixels - reconstructed) ** 2)

    sizes = np.bincount(kmeans.labels_, minlength=k)
    print(
        f"k={k}, sizes={sizes.tolist()}, "
        f"inertia={kmeans.inertia_:.2f}, "
        f"silhouette={silhouette:.3f}, "
        f"heldout_mse={heldout_mse:.2f}"
    )

# Select one evaluated value and quantize the complete image.
chosen_k = 6
model = fit_palette(chosen_k)
scaler = model.named_steps["scaler"]
kmeans = model.named_steps["kmeans"]

palette = scaler.inverse_transform(kmeans.cluster_centers_)
labels = kmeans.predict(scaler.transform(flat_pixels))

palette_u8 = palette.clip(0, 255).astype(np.uint8)
index_image = labels.astype(np.uint8).reshape(image.shape[:2])
reconstructed = palette_u8[labels].reshape(image.shape)

cluster_sizes = np.bincount(labels, minlength=chosen_k)
mse = np.mean((flat_pixels - reconstructed.reshape(-1, 3)) ** 2)

print("Cluster sizes:", cluster_sizes)
print(f"RGB reconstruction MSE: {mse:.2f}")
print(f"Raw pixel payload: {image.nbytes} bytes")
print(
    "Palette plus 8-bit indices:",
    palette_u8.nbytes + index_image.nbytes,
    "bytes",
)

This example demonstrates clustering in standardized RGB space. For exact Euclidean distortion in raw RGB space, fit K-Means directly on raw RGB values while still restricting training to a representative sample.

Limitations and Alternatives

K-Means requires choosing k, assumes roughly spherical clusters of similar size, and is sensitive to outliers and the distance metric. Use MiniBatchKMeans or sampled-pixel training for very large images.

Method How it works Strengths Weaknesses Typical scale and use
K-Means Assigns points to centroids Fast and simple Needs k; sensitive to outliers and initialization Large datasets; palette quantization
K-Medoids Uses actual pixels as representatives More robust representative colors Slower Small or medium datasets; noisy palettes
Gaussian Mixture Model Uses probabilistic clusters Supports soft assignments Assumes distributional structure Color-distribution modeling
DBSCAN/HDBSCAN Groups dense regions and detects noise Finds irregular shapes Does not directly create a fixed-size palette Segmentation and anomaly detection

Common Pitfalls

  • Ignoring feature geometry: Scaling changes RGB distances; use raw RGB when exact raw-RGB error is intended.

  • Treating the elbow as exact: Validate candidates with reconstruction quality and visual inspection.

  • Ignoring outliers or unrepresentative samples: Sample pixels broadly and inspect cluster profiles.

  • Using categorical data directly: Use k-modes or another suitable method.

  • Ignoring encoding overhead: Compare final encoded files, not only raw palette and index sizes.

  • Losing reproducibility: Record k, n_init, preprocessing, and random_state.

43

How should you cluster text documents using K-Means?

K-Means clustering groups unlabeled text documents by representing them as TF-IDF vectors and assigning each vector to a nearby centroid. It is fast and easy to interpret through cluster terms and representative documents, but results depend strongly on text representation, initialization, and the choice of k. A sound workflow combines training-only preprocessing, several initializations, quantitative evaluation, and semantic profiling.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

Recommended Workflow

  1. Prepare the documents

  2. Remove HTML, boilerplate, and malformed characters.

  3. Lowercase text when case carries no meaning.

  4. Tokenize words, optionally remove stop words, and retain meaningful bigrams such as “machine learning.”

  5. Represent documents with TF-IDF

  6. TfidfVectorizer weights terms by their within-document frequency and rarity across the corpus.

  7. Its default L2 normalization gives each nonempty document equal overall vector length.

  8. Prefer TF-IDF to raw counts, where repeated words can dominate Euclidean distance. Standard scaling is not normally needed for L2-normalized sparse TF-IDF.

  9. Fit K-Means

  10. Use init="k-means++" to reduce the chance of poorly separated initial centroids.

  11. Use multiple restarts with n_init=10; scikit-learn retains the run with the lowest inertia.

  12. The result remains dependent on initialization and can converge to a local optimum.

  13. Choose and validate k

  14. Compare several values using inertia, silhouette score, cluster sizes, and representative documents.

  15. Treat the elbow and silhouette as heuristics rather than exact answers.

  16. Profile and refit

  17. Inspect representative documents and high-weight terms in every cluster.

  18. After selecting k, refit the complete pipeline on all documents for the final clustering.

How Lloyd’s Algorithm Works

  1. Initialize k centroids, normally with k-means++.

  2. Assign each document vector x_i to its nearest centroid μ_cluster(i).

  3. Recompute each centroid as the mean of its assigned vectors.

  4. Repeat until assignments stop changing or another convergence condition is reached.

The minimized objective is the within-cluster sum of squares:

inertia = sum over all documents of ||x_i - μ_cluster(i)||²

Here, x_i is a document vector, μ_cluster(i) is its assigned centroid, and ||...||² is squared Euclidean distance. Each iteration costs approximately O(n * k * d), where n is the document count, k is the cluster count, and d is the feature count. MiniBatchKMeans processes subsets and is preferable for very large corpora.

Code Example

import numpy as np
import pandas as pd

from sklearn.base import clone
from sklearn.cluster import KMeans
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.metrics import silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline

rng = np.random.default_rng(42)

topics = {
    "machine learning": [
        "Neural networks learn patterns from training data",
        "Gradient descent optimizes a model loss function",
        "Classification predicts labels from input features",
        "Cross validation evaluates model generalization",
        "Feature scaling helps distance based algorithms",
        "Training data is transformed by a fitted pipeline",
    ],
    "cooking": [
        "The recipe requires flour sugar and eggs",
        "Bake the bread until the crust turns brown",
        "Chopping vegetables prepares a fresh dinner",
        "Season the soup with salt and fresh herbs",
        "Mix the butter and flour for the sauce",
        "Roast the vegetables before serving them",
    ],
    "travel": [
        "The flight arrives at the airport terminal",
        "Book a hotel near the city center",
        "Passengers collect luggage after landing",
        "Take the train through the mountain valley",
        "Tourists visit museums and historic landmarks",
        "The hotel offers breakfast and airport transport",
    ],
}

extra_terms = {
    "machine learning": ["gradient", "network", "model", "training"],
    "cooking": ["oven", "recipe", "sauce", "bread"],
    "travel": ["hotel", "flight", "passenger", "airport"],
}

documents = []
topic_labels = []

for topic, sentences in topics.items():
    for sentence in sentences:
        documents.append(
            f"{sentence} The {rng.choice(extra_terms[topic])} is relevant."
        )
        topic_labels.append(topic)

# Split before fitting TF-IDF so its vocabulary and IDF values are
# learned from training documents only.
X_train, X_test = train_test_split(
    documents, test_size=0.25, random_state=42
)

models = {}
results = []

for k in (2, 3, 4):
    model = Pipeline([
        ("tfidf", TfidfVectorizer(
            stop_words="english",
            ngram_range=(1, 2),
            min_df=1,
        )),
        ("kmeans", KMeans(
            n_clusters=k,
            init="k-means++",
            n_init=10,
            random_state=42,
        )),
    ])

    model.fit(X_train)

    vectorizer = model.named_steps["tfidf"]
    kmeans = model.named_steps["kmeans"]

    train_matrix = vectorizer.transform(X_train)
    test_matrix = vectorizer.transform(X_test)
    train_labels = kmeans.labels_
    test_labels = kmeans.predict(test_matrix)

    test_silhouette = (
        silhouette_score(test_matrix, test_labels)
        if 1 < len(np.unique(test_labels)) < len(test_labels)
        else np.nan
    )

    models[k] = model
    results.append({
        "k": k,
        "inertia": kmeans.inertia_,
        "silhouette": silhouette_score(train_matrix, train_labels),
        "test_silhouette": test_silhouette,
        "sizes": np.bincount(train_labels, minlength=k).tolist(),
    })

print("k | inertia | silhouette | held-out silhouette | training sizes")
for row in results:
    print(
        f"{row['k']} | {row['inertia']:.3f} | "
        f"{row['silhouette']:.3f} | "
        f"{row['test_silhouette']:.3f} | {row['sizes']}"
    )

# Select k using training-only evidence.
best_k = max(results, key=lambda row: row["silhouette"])["k"]

# Refit the selected pipeline on every document for final clustering.
final_model = clone(models[best_k])
final_model.fit(documents)

final_kmeans = final_model.named_steps["kmeans"]
final_labels = final_kmeans.labels_

print(f"\nSelected k: {best_k}")
print("Final cluster sizes:")
print(pd.Series(final_labels).value_counts().sort_index())

print("\nSynthetic topic versus cluster profile:")
print(pd.crosstab(
    pd.Series(topic_labels, name="topic"),
    pd.Series(final_labels, name="cluster"),
))

feature_names = final_model.named_steps["tfidf"].get_feature_names_out()
print("\nTop terms per cluster:")
for cluster_id, center in enumerate(final_kmeans.cluster_centers_):
    top_indices = np.argsort(center)[-5:][::-1]
    top_terms = ", ".join(feature_names[index] for index in top_indices)
    print(f"Cluster {cluster_id}: {top_terms}")

Advantages and Limitations

  • K-Means is simple, reproducible with random_state, and usually efficient on CPU.

  • It assumes roughly spherical, similarly sized clusters and is sensitive to outliers, vocabulary choices, and initialization.

  • Sparse TF-IDF vectors are high-dimensional, so Euclidean clusters may reflect vocabulary overlap rather than deep semantics.

  • Consider k-medoids for robustness, Gaussian mixture models for overlapping distributions, and DBSCAN or HDBSCAN for irregular clusters and noise.

Common Pitfalls

  • Raw counts or inconsistent scaling: use normalized TF-IDF rather than raw term frequencies.

  • Mechanical k selection: combine quantitative metrics with semantic review.

  • Leakage: fit the vectorizer only on training data during evaluation, then refit on all documents after selection.

  • Empty or malformed documents: remove or specially handle them before clustering.

  • Unprofiled clusters: inspect documents and terms; cluster IDs have no intrinsic meaning.

  • Categorical data: use k-modes rather than K-Means for categorical records.

Interview Tips

Explain Lloyd’s alternating assignment and recomputation steps, k-means++, n_init, local optima, and O(n * k * d) iteration complexity. Also explain why fitting TF-IDF only on training data prevents preprocessing leakage and when MiniBatchKMeans is preferable.

44

How do you apply K-Means clustering for anomaly detection?

K-Means anomaly detection treats observations far from their nearest learned centroid as anomalies. It is fast and simple, but its distance-only scores can miss anomalies inside dense clusters and are sensitive to scaling and outliers.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12, NumPy 2.x)

How It Works

  1. Fit K-Means on representative training data, ideally known or assumed to contain mostly normal observations.

  2. Standardize the features so variables with large scales do not dominate Euclidean distance.

  3. Calculate each observation’s anomaly score:

score(x) = min_j ||x - μ_j||₂

Here, x is one observation, μ_j is centroid j, ||x - μ_j||₂ is their Euclidean distance, and min_j selects the nearest centroid. 4. Choose a threshold from a validation set, an assumed anomaly rate, a percentile of validation scores, or labeled validation data. 5. Flag observations whose scores exceed the threshold. A higher score therefore means greater distance from every centroid.

Lloyd’s Algorithm

K-Means minimizes the within-cluster sum of squares, exposed as inertia_:

inertia_ = Σ_i ||x_i - μ_c(i)||²

The sum runs over all observations i; x_i is observation i, c(i) is its assigned cluster, and μ_c(i) is that cluster’s centroid. Lloyd’s algorithm:

  1. Initializes k centroids.

  2. Assigns each point to its nearest centroid.

  3. Recomputes each centroid as the mean of its assigned points.

  4. Repeats until assignments stop changing or another stopping condition is reached.

Scikit-learn uses k-means++ initialization by default, spreading initial centroids more effectively than a purely random start. The result still depends on initialization and converges to a local rather than guaranteed global optimum. Setting n_init=10 performs ten restarts and retains the run with the lowest inertia.

Code Example

This example selects k using silhouette score, estimates a threshold from validation scores, and evaluates the detector on held-out test data.

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import (
    average_precision_score,
    confusion_matrix,
    f1_score,
    precision_score,
    recall_score,
    roc_auc_score,
    silhouette_score,
)
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

rng = np.random.default_rng(42)

# Generate two normal clusters.
X_normal, _ = make_blobs(
    n_samples=160,
    centers=[[-3.0, -3.0], [3.0, 3.0]],
    cluster_std=0.7,
    random_state=42,
)

# Generate distant, intended anomalies.
signs = rng.choice([-1.0, 1.0], size=(12, 1))
X_anomalies = rng.uniform(7.0, 10.0, size=(12, 2)) * signs

X = np.vstack([X_normal, X_anomalies])
y = np.concatenate([
    np.zeros(len(X_normal), dtype=np.int64),
    np.ones(len(X_anomalies), dtype=np.int64),
])

# Split before fitting the scaler or clustering model.
X_train_val, X_test, y_train_val, y_test = train_test_split(
    X, y, test_size=0.25, stratify=y, random_state=42
)
X_train, X_val, y_train, _ = train_test_split(
    X_train_val,
    y_train_val,
    test_size=0.25,
    stratify=y_train_val,
    random_state=42,
)

# Cluster only known normal training observations.
X_train_normal = X_train[y_train == 0]

# Compare candidate values of k using training data only.
candidate_scores = {}
for candidate_k in range(2, 6):
    candidate = Pipeline([
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=candidate_k,
            init="k-means++",
            n_init=10,
            random_state=42,
        )),
    ])
    candidate.fit(X_train_normal)

    scaled = candidate.named_steps["scaler"].transform(X_train_normal)
    labels = candidate.named_steps["kmeans"].labels_
    score = silhouette_score(scaled, labels)
    inertia = candidate.named_steps["kmeans"].inertia_
    candidate_scores[candidate_k] = score
    print(f"k={candidate_k}, inertia={inertia:.3f}, silhouette={score:.3f}")

# Select the candidate with the highest silhouette score.
best_k = max(candidate_scores, key=candidate_scores.get)

final_model = Pipeline([
    ("scaler", StandardScaler()),
    ("kmeans", KMeans(
        n_clusters=best_k,
        init="k-means++",
        n_init=10,
        random_state=42,
    )),
])
final_model.fit(X_train_normal)

scaler = final_model.named_steps["scaler"]
kmeans = final_model.named_steps["kmeans"]
centers = kmeans.cluster_centers_

def nearest_distance(features: np.ndarray) -> np.ndarray:
    """Return Euclidean distance from each row to its nearest centroid."""
    squared = (
        np.sum(features**2, axis=1)[:, None]
        - 2.0 * features @ centers.T
        + np.sum(centers**2, axis=1)[None, :]
    )
    return np.sqrt(np.maximum(squared, 0.0)).min(axis=1)

X_val_scaled = scaler.transform(X_val)
val_scores = nearest_distance(X_val_scaled)

# Assume approximately 8% of deployment observations are anomalous.
contamination = 0.08
threshold = np.quantile(val_scores, 1.0 - contamination)

X_test_scaled = scaler.transform(X_test)
test_scores = nearest_distance(X_test_scaled)
y_pred = (test_scores > threshold).astype(np.int64)

print("Selected k:", best_k)
print("Cluster sizes:", np.bincount(kmeans.labels_, minlength=best_k))
print("Test anomalies detected:", int(y_pred.sum()))
print("Confusion matrix:", confusion_matrix(y_test, y_pred).tolist())
print("Precision:", round(precision_score(y_test, y_pred, zero_division=0), 3))
print("Recall:", round(recall_score(y_test, y_pred), 3))
print("F1:", round(f1_score(y_test, y_pred, zero_division=0), 3))
print("PR-AUC:", round(average_precision_score(y_test, test_scores), 3))
print("ROC-AUC:", round(roc_auc_score(y_test, test_scores), 3))

Practical Guidance and Alternatives

  • Missing values: K-Means rejects NaN and infinite values; remove or impute them using preprocessing fitted on training data only.

  • Metrics: Use precision, recall, F1, PR-AUC, and ROC-AUC. Accuracy can mislead because anomalies are usually rare.

  • Leakage: Select the threshold on validation data and reserve test data for final evaluation.

  • Complexity: Lloyd’s algorithm takes approximately O(n * k * d) per iteration, where n is observations, k is clusters, and d is features.

  • Reproducibility: Fixed random_state values make initialization repeatable for the same data and environment; n_init controls the number of restarts.

Tool How it works Strengths Weaknesses Use when Typical scale
K-Means Groups points around means Fast and scalable Assumes spherical clusters Compact numeric groups O(n * k * d) per iteration
MiniBatchKMeans Updates centroids from mini-batches Cheaper on large data Less exact results Very large datasets Batch- and epoch-controlled
k-medoids Uses actual observations as centers Less sensitive to outliers Expensive Mixed or outlier-prone data May require O(n²) comparisons
GMM Models probabilistic components Soft and elliptical clusters Assumes a component model Overlapping Gaussian groups Depends on covariance structure
DBSCAN/HDBSCAN Connects density-reachable points Handles irregular clusters Can need density tuning Non-spherical density groups Often near O(n log n), worst O(n²)

Common Pitfalls

  • Not scaling features: Distances may reflect units rather than meaningful differences.

  • Choosing k mechanically: The elbow and silhouette score are evidence, not exact answers; profile clusters.

  • Ignoring initialization and outliers: Outliers can pull centroids, and different starts can produce different local solutions.

  • Missing non-spherical anomalies: Points inside a normal cluster may receive low anomaly scores.

  • Using categorical features directly: Euclidean distance is usually inappropriate; use k-modes or another categorical method.

  • Overfitting the validation set: Do not repeatedly tune k and the threshold on one validation set and then treat it as unbiased test performance.

45

How can K-Means clustering support market trend analysis?

K-Means clustering groups similar observations into k clusters by minimizing the squared distance between each point and its cluster center. In market analysis, it can reveal customer segments such as loyal, discount-driven, or lapsed buyers, whose characteristics and proportions can be tracked over time. Its main trade-off is speed and simplicity versus sensitivity to scaling, outliers, initialization, and the need to choose k.

Read full answer

Applies toNumPy 2.x, pandas 2.2+, and scikit-learn 1.5+ (Python 3.12)

How It Works

K-Means minimizes the within-cluster sum of squares, also called inertia:

WCSS = sum over clusters j of sum over points x in cluster j of ||x - mean(x in cluster j)||²

Here, n is the number of observations, k is the number of clusters, d is the number of features, each x is an observation, and each cluster mean is its centroid.

Lloyd’s algorithm proceeds as follows:

  1. Initialize k centroids, commonly using k-means++.

  2. Assign every point to its nearest centroid using Euclidean distance.

  3. Recompute each centroid as the mean of its assigned points.

  4. Repeat the assignment and recomputation steps until assignments stop changing or the maximum number of iterations is reached.

The k-means++ initialization selects the first center randomly and chooses later centers with a higher probability when they are far from existing centers. With n_init=20, scikit-learn performs 20 initializations and retains the solution with the lowest inertia. K-Means still converges to a local rather than guaranteed global optimum.

Each iteration costs approximately O(n * k * d), with O(n * k) memory for assignments. For large datasets, MiniBatchKMeans reduces computation by processing smaller batches of observations.

Interpreting Market Trends

A practical customer-segmentation model might use:

  • Purchase frequency: number of purchases during a period.

  • Average order value: average spending per purchase.

  • Recency: days since the most recent purchase.

  • Discount dependency: proportion of spending associated with promotions.

After clustering, analysts inspect each cluster’s profile and assign a business meaning. For example, a cluster with low recency, high purchase frequency, and high order value may represent loyal customers. To identify trends, fit a model on a reference period, apply that same fitted model to monthly customer snapshots, and track each segment’s size and average behavior over time.

Code Example

The example generates synthetic customer behavior, evaluates several values of k, selects the best training silhouette score, and prints cluster profiles in the original feature units.

import numpy as np
import pandas as pd

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler


# Synthetic market segments:
# frequent loyal, casual, discount-driven, and lapsed customers
feature_names = [
    "purchases_last_90_days",
    "average_order_value",
    "recency_days",
    "discount_spend_share",
]

centers = np.array([
    [12.0, 140.0, 12.0, 0.15],
    [6.0, 85.0, 35.0, 0.25],
    [4.0, 55.0, 55.0, 0.55],
    [1.5, 30.0, 100.0, 0.35],
])

X, _ = make_blobs(
    n_samples=1200,
    centers=centers,
    cluster_std=[1.5, 12.0, 8.0, 0.06],
    random_state=42,
)

# Add reproducible market noise.
rng = np.random.default_rng(42)
X += rng.normal(loc=0.0, scale=0.01, size=X.shape)

# Enforce valid ranges for the synthetic customer features.
X[:, 0] = np.clip(np.rint(X[:, 0]), 0, None)
X[:, 1] = np.clip(X[:, 1], 0, None)
X[:, 2] = np.clip(np.rint(X[:, 2]), 0, None)
X[:, 3] = np.clip(X[:, 3], 0.0, 1.0)

# Keep held-out data separate from preprocessing and model fitting.
X_train, X_validation = train_test_split(
    X, test_size=0.20, random_state=42
)


def build_clustering(k):
    return Pipeline([
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=k,
            init="k-means++",
            n_init=20,
            random_state=42,
        )),
    ])


# Compare inertia and silhouette scores for several possible k values.
rows = []
for k in range(2, 7):
    candidate = build_clustering(k)
    candidate.fit(X_train)

    scaler = candidate.named_steps["scaler"]
    clusterer = candidate.named_steps["kmeans"]
    scaled_train = scaler.transform(X_train)

    rows.append({
        "k": k,
        "inertia": clusterer.inertia_,
        "silhouette": silhouette_score(scaled_train, clusterer.labels_),
    })

evaluation = pd.DataFrame(rows)
selected_k = int(
    evaluation.loc[evaluation["silhouette"].idxmax(), "k"]
)

# Fit the final model using training data only.
model = build_clustering(selected_k)
model.fit(X_train)

train_labels = model.named_steps["kmeans"].labels_
validation_labels = model.predict(X_validation)

# Convert centroids back to original units for business interpretation.
scaler = model.named_steps["scaler"]
clusterer = model.named_steps["kmeans"]
profiles = pd.DataFrame(
    scaler.inverse_transform(clusterer.cluster_centers_),
    columns=feature_names,
)
profiles.insert(0, "cluster", profiles.index)

print("Model evaluation:")
print(evaluation.round(3).to_string(index=False))
print(f"\nSelected k: {selected_k}")
print("\nTraining cluster sizes:")
print(pd.Series(train_labels).value_counts().sort_index().to_string())
print("\nValidation cluster sizes:")
print(pd.Series(validation_labels).value_counts().sort_index().to_string())
print("\nCluster profiles in original units:")
print(profiles.round(2).to_string(index=False))

Alternatives and Trade-offs

Method How it works Strengths Weaknesses Typical use or scale
K-Medoids Uses an actual data point as each center More robust to outliers Usually slower than K-Means Smaller or outlier-sensitive datasets
Gaussian Mixture Model Assigns probabilistic, soft memberships Models elliptical clusters Assumes Gaussian components Customer segmentation with uncertain membership
DBSCAN Connects dense regions and marks sparse points as noise Finds arbitrary-shaped clusters Sensitive to density parameters Geospatial data with noise; expected O(n * d) neighborhood work
HDBSCAN Builds a hierarchy of density-based clusters Handles variable density and noise Higher computational overhead Medium-to-large datasets with varied cluster densities

Common Pitfalls

  • Skipping standardization: Features with larger numeric ranges dominate Euclidean distance. Fit the scaler only on training data to prevent leakage.

  • Treating the elbow as exact: Inertia always decreases as k increases. Combine the elbow method, silhouette score, cluster stability, and business interpretability.

  • Ignoring outliers: K-Means centroids are influenced by extreme values; investigate, transform, or use K-Medoids.

  • Using categorical features directly: Euclidean distance is not meaningful for nominal categories; use K-Modes or a domain-appropriate method.

  • Overinterpreting clusters: Profile clusters and validate their stability before associating them with market segments.

  • Ignoring time dependence: For actual trend analysis, compare cluster proportions across monthly snapshots rather than treating all observations as one static population.

  • Interview follow-ups: Expect questions about choosing k, the meaning of inertia, k-means++ initialization, local optima, computational complexity, and why preprocessing must occur inside the training pipeline.

46

How can K-Means clustering balance loads across distributed workers?

K-Means clustering can group workers with similar resource profiles and route incoming workloads to an appropriate worker group, where a scheduler selects the least-loaded eligible worker. It provides simple, fast workload classification, but it is not a real-time load-balancing algorithm by itself: results depend on feature scaling, initialization, the chosen number of clusters, and the quality of the worker profiles.

Read full answer

Applies toscikit-learn 1.5+ and NumPy 2.x (Python 3.12)

How K-Means Works

K-Means partitions observations into k groups while minimizing inertia, the within-cluster sum of squared distances:

inertia = sum from i = 1 to n of ||x_i - mu_c(i)||²

  • n: number of observations.

  • x_i: feature vector for observation i.

  • mu_c(i): mean, or centroid, of the cluster assigned to observation i.

  • || ... ||²: squared Euclidean distance.

Lloyd’s algorithm performs these steps:

  1. Initialize k centroids. k-means++, the scikit-learn default, chooses initial centroids that are relatively well separated.

  2. Assign each observation to its nearest centroid.

  3. Recalculate each centroid as the mean of its assigned observations.

  4. Repeat until assignments stop changing or another stopping criterion is reached.

K-Means converges to a local optimum, so its result can depend on initialization. Setting n_init=10 performs ten restarts and retains the result with the lowest inertia.

Applying It to Load Balancing

  1. Build worker profiles: Represent each server using telemetry such as CPU capacity, available memory, network bandwidth, throughput, and task-concurrency limits.

  2. Build workload profiles: Represent incoming tasks by their expected CPU, memory, I/O, and network requirements.

  3. Cluster reference workers: Fit K-Means on a training set of historical worker profiles. The clusters represent worker or resource classes.

  4. Route incoming work: Scale task requirements, find the nearest centroid, and select a worker from that cluster using live metrics such as queue length, CPU utilization, or predicted completion time.

  5. Rebalance when needed: Trigger remapping when live load diverges from the cluster model or when workers become unavailable.

K-Means groups similar profiles; the scheduler still performs the actual balancing. Within a cluster, choosing the worker with the lowest current load prevents all new work from repeatedly reaching the same member.

Operational Considerations

  • Complexity: Each Lloyd iteration costs approximately O(n * k * d), where n is the number of observations, k is the cluster count, and d is the feature count.

  • Large datasets: MiniBatchKMeans reduces training cost by processing smaller batches, at the expense of potentially less stable results.

  • Choosing k: Use inertia and silhouette score, plus operational constraints. The elbow is a heuristic, not an exact optimum, and a very large k can overfit noise.

  • Scaling: Standardize features because Euclidean distances are sensitive to units and magnitude.

  • Missing values: K-Means requires finite numeric features. Impute missing values inside a training-fitted Pipeline rather than filling them using statistics from the full dataset.

  • Reproducibility: Use a fixed random_state and multiple initializations with n_init; results can still change when the data, preprocessing, or k changes.

  • Assumptions: K-Means works best for roughly spherical, similarly sized clusters and is sensitive to outliers.

Alternative How it works Strengths Weaknesses When to use Typical complexity or scale
k-medoids Uses actual observations as cluster representatives More robust to outliers More expensive; large datasets are challenging Small or medium numerical datasets with outliers Classical PAM is typically O(n²d) per iteration
Gaussian Mixture Models Models clusters as probabilistic distributions Soft assignments; supports elliptical clusters More computation; may overfit Uncertain or overlapping cluster membership Roughly O(nkd) to O(nkd²) per iteration, depending on covariance model
DBSCAN/HDBSCAN Connects observations through density neighborhoods Finds irregular clusters and noise Sensitive to density assumptions at high dimensions Spatial data, irregular groups, and outliers Data-dependent; HDBSCAN is typically near O(n log n), while neighborhood search can degrade toward O(n²)

Code Example

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

# Synthetic worker profiles: CPU, memory, and network dimensions
centers = np.array([
    [0.75, 0.80, 0.70],
    [0.50, 0.65, 0.85],
    [0.85, 0.55, 0.75],
])

workers, worker_types = make_blobs(
    n_samples=60,
    centers=centers,
    cluster_std=0.10,
    random_state=42,
)

# Fit preprocessing and clustering only on the training workers
X_train, X_test, y_train, y_test = train_test_split(
    workers,
    worker_types,
    test_size=1 / 3,
    stratify=worker_types,
    random_state=42,
)

# Compare several values of k
for k in range(2, 6):
    model = Pipeline([
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=k,
            init="k-means++",
            n_init=10,
            random_state=42,
        )),
    ])
    model.fit(X_train)

    scaled_train = model.named_steps["scaler"].transform(X_train)
    labels = model.named_steps["kmeans"].labels_

    print(
        f"k={k}, "
        f"inertia={model.named_steps['kmeans'].inertia_:.2f}, "
        f"silhouette={silhouette_score(scaled_train, labels):.3f}"
    )

# Final model with three operational worker classes
model = Pipeline([
    ("scaler", StandardScaler()),
    ("kmeans", KMeans(
        n_clusters=3,
        init="k-means++",
        n_init=10,
        random_state=42,
    )),
])
model.fit(X_train)

worker_clusters = model.predict(X_test)

# Synthetic incoming workload profiles
requests, _ = make_blobs(
    n_samples=120,
    centers=centers,
    cluster_std=0.10,
    random_state=43,
)
request_clusters = model.predict(requests)

# Select the least-loaded worker within the matching cluster
worker_load = np.zeros(len(X_test))
worker_capacity = X_test[:, 0]
assigned_tasks = np.zeros(len(X_test), dtype=int)
unassigned_tasks = 0

for cluster_id, request in zip(request_clusters, requests):
    candidates = np.flatnonzero(worker_clusters == cluster_id)

    # Requeue the request when no matching worker is available
    if candidates.size == 0:
        unassigned_tasks += 1
        continue

    load_ratios = worker_load[candidates] / worker_capacity[candidates]
    selected = candidates[np.argmin(load_ratios)]

    worker_load[selected] += request[0]
    assigned_tasks[selected] += 1

print("Workers per cluster:", np.bincount(worker_clusters, minlength=3))
print("Requests per cluster:", np.bincount(request_clusters, minlength=3))
print("Tasks assigned per worker:", assigned_tasks)
print("Unassigned tasks:", unassigned_tasks)
print("Workload assigned per worker:", worker_load)

Common Pitfalls

  • Not scaling features: Distances can become dominated by high-magnitude variables.

  • Choosing k mechanically: Validate cluster stability and operational usefulness; the elbow is not exact.

  • Using categorical data directly: Use k-modes or encode categories in a way that preserves meaningful distance.

  • Confusing clusters with balanced workers: K-Means creates groups, not a complete scheduling policy.

  • Ignoring outliers: Extreme workers or tasks can distort centroids; use robust preprocessing or k-medoids.

  • Fitting preprocessing on all data: Fit the scaler and K-Means only on the designated training or reference cohort.

  • Routing to ineligible workers: If no matching resource class has capacity, requeue or defer work rather than forcing it into an incompatible cluster.

  • Interpreting clusters without profiling: Examine each cluster’s workload characteristics, size, cost, and operational behavior before trusting it.

47

How can K-Means improve a recommendation system project?

K-Means can improve a recommender by grouping users with similar behavioral profiles and using each group’s training-item affinities as a personalization signal. It is simple and fast, but its value depends on feature scaling, meaningful cluster selection, and comparison with simpler baselines.

Read full answer

Applies toscikit-learn 1.5+ and NumPy 2.x (Python 3.12)

How It Helps

  • Build a user profile from purchase counts, average basket value, recency, category affinity, and session frequency.

  • Cluster profiles, then calculate item affinities from training interactions within each cluster.

  • Blend cluster affinity with collaborative-filtering and popularity scores, tuning their weights on validation data.

  • Profile each cluster to verify that it represents a useful audience rather than an arbitrary partition.

K-Means supports cold start only when a new user has some early interactions or contextual features to profile. Users with no usable information still require a popularity or context-based fallback.

How K-Means Works

Lloyd’s algorithm operates as follows:

  1. Initialize k centroids.

  2. Assign each point to its nearest centroid using Euclidean distance.

  3. Recompute each centroid as the mean of its assigned points.

  4. Repeat until assignments stop changing or another stopping condition is reached.

The objective is the within-cluster sum of squares, or inertia:

inertia = Σᵢ ||xᵢ - μzᵢ||²

Here, i indexes users, xᵢ is a user profile, zᵢ is the assigned cluster, and μzᵢ is that cluster’s centroid. Lower inertia means more compact clusters.

Scikit-learn uses k-means++ initialization by default, which selects initial centroids with probability proportional to squared distance from existing centroids. With n_init=10, it runs ten initializations and retains the solution with the lowest inertia. K-Means converges to a local optimum.

Its cost is approximately O(n × k × d) per iteration, where n is the number of users, k is the cluster count, and d is the feature count. MiniBatchKMeans reduces update work for large datasets.

Evaluation

Evaluate with Precision@K, Recall@K, and NDCG@K: precision measures the relevant fraction among top recommendations, recall measures how many relevant items were retrieved, and NDCG rewards relevant items ranked higher. Compare against popularity-only and non-clustered baselines, then confirm online gains through an A/B test. Use inertia, silhouette score, temporal stability, and downstream metrics to choose k; the elbow is guidance, not an exact answer.

Code Example

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

rng = np.random.default_rng(42)

# Synthetic behavioral profiles for 240 users.
user_features, latent_groups = make_blobs(
    n_samples=240,
    centers=3,
    n_features=5,
    cluster_std=0.7,
    random_state=42,
)

n_train_users = 180
n_items = 12
events = []

# Generate item interactions associated with each latent behavioral group.
for user_id, group in enumerate(latent_groups):
    probabilities = np.full(n_items, 0.02)
    probabilities[group * 4:(group + 1) * 4] = 0.25
    probabilities /= probabilities.sum()

    items = rng.choice(
        n_items, size=8, replace=False, p=probabilities
    )
    for event_number, item_id in enumerate(items):
        timestamp = user_id * 8 + event_number
        events.append((user_id, int(item_id), timestamp))

# Chronological holdout: earlier users are training users.
cutoff = n_train_users * 8
train_events = [event for event in events if event[2] < cutoff]
test_events = [event for event in events if event[2] >= cutoff]

X_train = user_features[:n_train_users]
X_test = user_features[n_train_users:]


def make_segmenter(k):
    return Pipeline([
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=k,
            init="k-means++",
            n_init=10,
            random_state=42,
        )),
    ])


# Compare candidate values of k using training users only.
for k in range(2, 6):
    model = make_segmenter(k)
    labels = model.fit_predict(X_train)
    scaled_train = model.named_steps["scaler"].transform(X_train)

    inertia = model.named_steps["kmeans"].inertia_
    silhouette = silhouette_score(scaled_train, labels)
    print(f"k={k}, inertia={inertia:.2f}, silhouette={silhouette:.3f}")

# Assume downstream validation selected k=3.
segmenter = make_segmenter(3)
segmenter.fit(X_train)
train_labels = segmenter.predict(X_train)
test_labels = segmenter.predict(X_test)

print("Cluster sizes:", np.bincount(train_labels, minlength=3))

# Learn global and cluster-level affinities from training events only.
global_counts = np.bincount(
    [item_id for _, item_id, _ in train_events],
    minlength=n_items,
)
cluster_counts = np.zeros((3, n_items))
for user_id, item_id, _ in train_events:
    cluster_counts[train_labels[user_id], item_id] += 1


def top_items(scores):
    return np.argsort(-scores, kind="stable")[:3].tolist()


test_by_user = {}
for user_id, item_id, _ in test_events:
    test_by_user.setdefault(user_id, set()).add(item_id)

baseline_precision = []
cluster_precision = []

for user_id, relevant_items in test_by_user.items():
    baseline = top_items(global_counts)
    cluster_id = test_labels[user_id - n_train_users]
    personalized = top_items(cluster_counts[cluster_id])

    baseline_precision.append(
        len(set(baseline) & relevant_items) / 3
    )
    cluster_precision.append(
        len(set(personalized) & relevant_items) / 3
    )

print("Popularity precision@3:", np.mean(baseline_precision))
print("Cluster precision@3:", np.mean(cluster_precision))

Alternatives and Scale

Method How it works Strengths Weaknesses Typical use or scale
K-Means Assigns points to centroid means Fast and simple Requires k; sensitive to scaling and outliers Compact numerical clusters; O(nkd) per iteration
MiniBatchKMeans Updates centroids from mini-batches Lower update cost Sometimes less stable Very large datasets
Gaussian mixture Estimates probabilistic memberships Soft and elliptical clusters Greater computational cost Soft assignments; O(nkd) per EM iteration plus covariance work
DBSCAN/HDBSCAN Connects dense regions Finds irregular shapes and noise Parameter sensitivity Irregular clusters; cost depends on neighborhood queries
k-medoids/k-modes Uses medoids or categorical modes Robust or supports categorical data Slower and less standardized tooling Outlier-heavy or categorical data

Common Pitfalls

  • Not scaling: Standardize numerical features before clustering.

  • Choosing k mechanically: Combine inertia, silhouette, stability, business meaning, and downstream metrics.

  • Leakage: Fit profiles, scalers, centroids, and affinities only on information available at prediction time.

  • Unsupported cold start: Provide contextual features or a fallback when a user has no behavior.

  • Ignoring outliers: Investigate robust alternatives when unusual users pull centroids.

  • Misinterpreting clusters: Profile clusters and confirm downstream improvement with an online experiment.

48

How can K-Means clustering improve CDN edge placement and routing?

K-Means clustering groups similar CDN demand profiles so operators can place or expand POPs, prepare caches, and choose routing policies. Its main trade-off is simple, fast geometric partitioning versus the need to optimize latency, cost, capacity, and failover separately.

Read full answer

Applies toscikit-learn 1.5+ (Python 3.12)

How Lloyd’s Algorithm Works

K-Means partitions observations into k clusters by minimizing the within-cluster sum of squares, or inertia:

WCSS = sum from i = 1 to n of ||x_i - mu_c(i)||²

Here, n is the number of observations, x_i is observation i, mu_c(i) is its assigned cluster’s mean, and ||...||² is the squared Euclidean distance from that mean.

Lloyd’s algorithm proceeds as follows:

  1. Initialize centroids: Select k initial cluster centers.

  2. Assign observations: Assign each point to its nearest centroid.

  3. Recompute centroids: Replace each centroid with the mean of its assigned points.

  4. Repeat: Continue until assignments stabilize or another stopping condition is reached.

Scikit-learn uses k-means++ initialization by default. It selects the first center randomly and chooses subsequent centers with probability proportional to their squared distance from existing centers, reducing the chance of poor initial placement. The n_init parameter controls how many initializations are attempted, and scikit-learn retains the result with the lowest inertia. With init="k-means++", n_init="auto" means ten initializations; the example uses an explicit n_init=10.

Each iteration costs approximately O(n * k * d), where d is the number of features. K-Means converges to a local optimum, so initialization and restarts affect the result.

Applying K-Means to a CDN

K-Means can operate offline on aggregated POP, region, or time-window profiles:

  • Edge placement: Group demand profiles using geographic, bandwidth, request-rate, content-volume, and latency features. Allocate capacity to POPs associated with high-value clusters.

  • Cache preparation: Identify clusters with high-volume, similar content-access patterns and prewarm the corresponding POP caches.

  • Request routing: Map a request’s features to the nearest cluster and use its associated POP policy as a candidate. Final routing should also use live latency, POP health, capacity, and failover signals.

  • Capacity planning: Compare cluster sizes and request rates to estimate required compute, bandwidth, and storage capacity.

A centroid is a standardized demand profile, not necessarily a physical location. Geographic features should be handled carefully, and a geographic-only clustering can be used when actual POP coordinates are required.

Code Example

This synthetic example uses cross-validation to select k, fits each scaler and K-Means model only on its training folds, and reserves a test set for final evaluation.

import numpy as np

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.model_selection import KFold, train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

RANDOM_SEED = 42

# Synthetic CDN dimensions: delay, bandwidth, request rate, and content volume.
X, _ = make_blobs(
    n_samples=1500,
    centers=4,
    n_features=4,
    cluster_std=1.2,
    random_state=RANDOM_SEED,
)

X_dev, X_test = train_test_split(
    X, test_size=0.20, random_state=RANDOM_SEED
)
cv = KFold(n_splits=5, shuffle=True, random_state=RANDOM_SEED)


def build_pipeline(k):
    return Pipeline([
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=k,
            init="k-means++",
            n_init=10,
            random_state=RANDOM_SEED,
        )),
    ])


scores = {}
mean_inertias = {}

for k in range(2, 7):
    fold_scores = []
    fold_inertias = []

    for train_index, validation_index in cv.split(X_dev):
        pipeline = build_pipeline(k)
        pipeline.fit(X_dev[train_index])

        labels = pipeline.predict(X_dev[validation_index])
        scaler = pipeline.named_steps["scaler"]
        scaled_validation = scaler.transform(X_dev[validation_index])

        fold_scores.append(silhouette_score(scaled_validation, labels))
        fold_inertias.append(
            pipeline.named_steps["kmeans"].inertia_
        )

    scores[k] = np.mean(fold_scores)
    mean_inertias[k] = np.mean(fold_inertias)
    print(f"k={k}, mean inertia={mean_inertias[k]:.2f}, "
          f"mean silhouette={scores[k]:.3f}")

best_k = max(scores, key=scores.get)

final_pipeline = build_pipeline(best_k)
final_pipeline.fit(X_dev)

dev_labels = final_pipeline.predict(X_dev)
test_labels = final_pipeline.predict(X_test)

scaler = final_pipeline.named_steps["scaler"]
kmeans = final_pipeline.named_steps["kmeans"]
scaled_test = scaler.transform(X_test)

cluster_sizes = np.bincount(dev_labels, minlength=best_k)
test_silhouette = silhouette_score(scaled_test, test_labels)
centroids = scaler.inverse_transform(kmeans.cluster_centers_)

print(f"\nSelected k: {best_k}")
print("Cluster sizes:", cluster_sizes)
print(f"Test silhouette: {test_silhouette:.3f}")
print("Centroids in original feature scale:")
print(np.round(centroids, 2))

Alternatives and Trade-offs

Method How it works Strengths Weaknesses Appropriate use
K-Means Assigns points to the nearest mean Fast and scalable Spherical, similarly sized clusters; sensitive to scaling and outliers Large traffic-segmentation datasets
K-Medoids Uses actual observations as representatives Interpretable and supports non-Euclidean distances More expensive Small or atypical datasets
Gaussian Mixture Models Estimates probabilistic, elliptical clusters Soft assignments and uncertainty Strong distributional assumptions Overlapping demand groups
DBSCAN/HDBSCAN Groups dense regions; HDBSCAN also builds a cluster hierarchy Handles irregular clusters and noise Less suitable for very large datasets Anomalous or irregular traffic

For very large datasets, MiniBatchKMeans reduces training cost by processing observation subsets, although its solution may be less stable than full K-Means.

Common Pitfalls

  • Skipping scaling: Large-range features dominate Euclidean distance; standardize numerical features before clustering.

  • Choosing k only from inertia: Inertia usually decreases as k rises. Consider the elbow, cross-validated silhouette, operational constraints, and interpretability.

  • Treating silhouette as business performance: It measures geometric separation, not latency, cost, or cache efficiency.

  • Leakage: Fit imputation, scaling, and clustering only on permitted training data.

  • Ignoring outliers, missing values, or categorical data: Investigate spikes, handle missing values, and use K-Modes or suitable encodings for categorical features.

  • Misusing clusters: Profile traffic, geography, content, and economics before assigning operational policies, and retain live routing signals.

49

How does Lloyd’s Algorithm enable K-Means clustering enhancements?

Lloyd’s algorithm is the iterative assignment-and-update procedure behind standard K-Means. It reduces the within-cluster sum of squares by assigning observations to their nearest centroids and replacing each centroid with the mean of its assigned observations. Because the objective is non-convex, it can converge to a local optimum, making initialization, repeated runs, and mini-batch variants important extensions.

Read full answer

Applies toscikit-learn 1.6+ (Python 3.12; NumPy 2.x)

How Lloyd’s Algorithm Works

For n observations, k clusters, and d features, the algorithm performs these steps:

  1. Initialize centroids: Select k initial centroids randomly, using k-means++, or from user-supplied locations.

  2. Assign observations: Assign each observation to the centroid with the smallest squared Euclidean distance: c_i = arg min_j ||x_i - μ_j||².

  3. Update centroids: Replace each centroid with the mean of the observations assigned to its cluster: μ_j = mean(x_i for observations assigned to cluster j).

  4. Repeat: Continue until assignments stop changing, inertia changes fall below the tolerance, or the iteration limit is reached.

The minimized objective is the within-cluster sum of squares, or inertia:

WCSS = sum_i ||x_i - μ_assigned(i)||²

Here, x_i is observation i, μ_j is centroid j, and c_i is the cluster index assigned to observation i. The index j ranges over the k centroids, and arg min returns the index with the smallest squared distance. In the inertia formula, μ_assigned(i) is the centroid assigned to observation i.

Enhancements Built on Lloyd’s Algorithm

  • k-means++ initialization: After choosing the first centroid uniformly, each subsequent centroid is selected with probability proportional to its squared distance from the nearest already-selected centroid. This reduces redundant initial centroids and the risk of an especially poor local optimum.

  • Multiple restarts: n_init=10 runs Lloyd’s algorithm ten times with different initializations and retains the run with the lowest inertia. With init="k-means++", the default n_init="auto" performs one run; with init="random", it performs 10 runs.

  • MiniBatchKMeans: Uses mini-batches of observations for assignment and centroid updates, reducing memory and computation on large datasets at the cost of less precise estimates.

  • Stopping controls: Tighter tolerances or iteration limits can control when updates stop without changing the basic assign-and-update structure.

Lloyd’s algorithm does not guarantee the global minimum of inertia, so different initializations can produce different clusters.

Practical Considerations and Alternatives

Approach How it works Strengths Weaknesses When to use Typical scale
KMeans Repeated assignment and mean updates Simple and fast Requires choosing k; sensitive to scaling and outliers Compact, roughly spherical clusters Batch data; O(n * k * d) per iteration
MiniBatchKMeans Lloyd-style updates on mini-batches Faster with lower memory use Less precise and seed-sensitive Very large datasets O(b * k * d) per batch update
GMM Probabilistic assignment using EM Supports elliptical clusters and soft assignments More computation and covariance assumptions Overlapping elliptical groups Small to medium datasets
DBSCAN/HDBSCAN Density-based neighborhood expansion Finds irregular clusters and labels noise Density parameters can be difficult to tune Non-spherical data and outliers Medium to large datasets
k-medoids Uses actual observations as cluster centers More resistant to extreme values than means Pairwise-distance computation is expensive Small or medium datasets with outliers Usually small to medium datasets

Standardize features before clustering because large-scale variables otherwise dominate distances. Choose k using inertia, the elbow method, silhouette score, stability across seeds, and domain knowledge—not one metric alone.

Code Example

import numpy as np
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score
from sklearn.model_selection import train_test_split
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler

# Deterministic synthetic data; the generated labels are not used.
X, _ = make_blobs(
    n_samples=300,
    centers=4,
    cluster_std=1.0,
    random_state=42,
)

# Use validation data to compare k; in a real project, also hold out an untouched test set.
X_train, X_validation = train_test_split(
    X,
    test_size=0.30,
    random_state=42,
)

# Compare several values of k.
for k in range(2, 7):
    pipeline = Pipeline([
        ("scaler", StandardScaler()),
        ("kmeans", KMeans(
            n_clusters=k,
            init="k-means++",
            n_init=10,
            algorithm="lloyd",
            random_state=42,
        )),
    ])

    train_labels = pipeline.fit_predict(X_train)
    validation_labels = pipeline.predict(X_validation)

    model = pipeline.named_steps["kmeans"]
    scaler = pipeline.named_steps["scaler"]
    X_validation_scaled = scaler.transform(X_validation)

    silhouette = (
        silhouette_score(X_validation_scaled, validation_labels)
        if len(np.unique(validation_labels)) > 1
        else float("nan")
    )
    cluster_sizes = np.bincount(train_labels, minlength=k)

    print(
        f"k={k}, inertia={model.inertia_:.2f}, "
        f"silhouette={silhouette:.3f}, sizes={cluster_sizes}"
    )

Common Pitfalls

  • Not scaling features: Large numeric ranges dominate centroid distances.

  • Treating the elbow as exact: The elbow is a visual guide, not a definitive cluster count.

  • Ignoring outliers: Extreme observations can pull centroids away from the main distribution.

  • Using KMeans on categorical data: Use a suitable categorical method such as k-modes.

  • Interpreting clusters without profiling them: Inspect feature distributions and domain meaning before assigning labels.

  • Using supervised accuracy blindly: Clustering is unsupervised; use inertia, silhouette, stability, and external validation where labels exist.

  • Leaking evaluation data: Fit preprocessing on training data, select k on validation data or cross-validation, and reserve an untouched test set for final reporting.

Interviewers commonly ask why Lloyd’s algorithm reaches a local optimum, how k-means++ differs from random initialization, when MiniBatchKMeans is preferable, and how the number of clusters should be selected.

50

What are recent K-Means advances for big data clustering?

K-Means clustering partitions unlabeled observations into k groups by minimizing the squared distance between each point and its centroid. Recent advances target scalability, distribution, robustness, privacy, sparse data, and complex representations, trading computational efficiency and simplicity for reduced sensitivity to initialization, outliers, feature scale, and cluster shape.

Read full answer

Applies toK-Means concepts and scikit-learn 1.5+ guidance (Python 3.12)

Core Algorithm

Lloyd’s algorithm performs these steps repeatedly:

  1. Initialize centroids: Choose k representative points. Scikit-learn’s default, init="k-means++", selects centers probabilistically, giving points far from previously selected centers a higher chance of being chosen.

  2. Assign observations: Assign each point to its nearest centroid using squared Euclidean distance.

  3. Recompute centroids: Replace each centroid with the mean of its assigned observations.

  4. Repeat: Continue until assignments stabilize, the convergence tolerance is reached, or max_iter is exhausted.

The objective is the within-cluster sum of squares, or inertia:

inertia = sum over i of ||x_i - c_assigned(i)||²

Here, i indexes an observation, x_i is that observation, c_assigned(i) is its assigned centroid, and || ||² denotes squared Euclidean distance. Lower inertia means tighter clusters. For globally optimal partitions, inertia is non-increasing as k grows, but it cannot select k by itself.

The objective is non-convex, so Lloyd’s algorithm converges to a local optimum whose result can depend on initialization. The n_init parameter controls how many independent starts are run, with scikit-learn retaining the result having the lowest inertia. For n observations, k centroids, and d features, one iteration costs approximately O(n × k × d) time.

Big-Data and Research Advances

  • MiniBatchKMeans: Updates centroids from small batches, reducing per-update computation and supporting incremental use. It is useful for large datasets but returns approximate results.

  • Distributed algorithms: Approaches such as k-means|| avoid repeatedly transferring all observations among workers by exchanging compact center information.

  • GPU acceleration: Parallelizes distance calculations and centroid updates, especially for large, dense numerical datasets. CPU methods remain preferable when data transfer dominates.

  • Robust variants: Trimmed, winsorized, and outlier-aware methods reduce the influence of extreme observations, at the cost of extra parameters and tuning.

  • Sparse and non-Euclidean clustering: Spherical K-Means uses cosine similarity and can suit normalized document or embedding vectors, although sparse centroids may become dense.

  • Federated clustering: Systems exchange model updates or centroid statistics instead of raw records. Privacy is not automatic because repeated updates can still disclose information.

  • Deep and multi-view clustering: Neural methods jointly learn representations and assignments, potentially capturing nonlinear structure but adding optimization, interpretability, and computational complexity.

Variant and Alternative Comparison

Approach How it works Main strength Main limitation
Standard K-Means Lloyd iterations with squared Euclidean distance Simple and fast Sensitive to scaling, outliers, and initialization
MiniBatchKMeans Updates centers from small batches Scalable and incremental Approximate and potentially less stable
Spherical K-Means Clusters using cosine similarity Suitable for normalized directional data Requires careful normalization
Robust K-Means Reduces outlier influence Better for contaminated data Additional parameters and tuning
Federated K-Means Exchanges updates rather than raw data Supports collaborative systems Privacy and communication risks
DBSCAN/HDBSCAN Finds density-connected regions and noise Handles irregular clusters Less suitable for evenly separated convex clusters

For unusual distances or greater outlier resistance, consider k-medoids, although it is usually more expensive. For overlapping or elliptical clusters with probabilistic assignments, consider a Gaussian mixture model, which uses expectation-maximization and can be costly at big-data scale.

Common Pitfalls

  • Failing to scale features: Large-magnitude features dominate Euclidean distances; fit the scaler on training data only.

  • Ignoring missing values: K-Means estimators reject NaN values; impute or remove them within training folds to prevent leakage.

  • Choosing k from the elbow alone: Treat the elbow as a heuristic and combine it with silhouette scores, stability across seeds, domain knowledge, and cluster profiling.

  • Overfitting the validation set: Compare limited candidate values of k and reserve final test data for one final evaluation.

  • Using the wrong data representation: K-Means assumes roughly convex, similarly sized numerical clusters; use k-modes or another method for categorical data.

  • Ignoring outliers and geometry: Extreme observations pull centroids, and spherical assumptions can hide elongated or unequal clusters.

  • Interpreting clusters without profiling: A geometric partition is not automatically a meaningful business or scientific category.

Common follow-ups include why results vary across runs, how k-means++ reduces initialization risk, when MiniBatchKMeans is appropriate, and how outliers or unequal cluster densities affect centroids.

Sign in to keep reading

You've opened 2 full answers. Sign in to read all 50 K-Means Clustering answers, mark what you know and pick up where you left off.

Report a mistake

What's wrong?

All Machine Learning & Data Science subjects