K Means Clustering and Unsupervised Learning Questions

Unsupervised learning finding patterns in data without labeled outcomes. K-Means: a centroid-based algorithm that partitions data into k clusters by iteratively assigning points to the nearest cluster center and updating centers until convergence. Covers algorithm mechanics (initialization including random and k-means++, assignment, centroid update, convergence criteria), distance metrics (Euclidean, Manhattan) and their tradeoffs, choosing k (elbow method using inertia, silhouette score), and known advantages (simple, fast, scalable) and disadvantages (sensitive to initialization, assumes roughly spherical/similarly-sized clusters, sensitive to outliers and feature scaling, struggles with categorical or missing data). Also covers other unsupervised clustering approaches conceptually: hierarchical clustering (agglomerative/divisive, dendrograms, linkage criteria) and DBSCAN (density-based clustering for non-spherical clusters and noise/outlier detection). Depth ranges from core mechanics and tradeoffs to production concerns: scaling to large n/d, handling missing or categorical features, choosing between K-Means and alternatives (GMM, DBSCAN, hierarchical) for a given data shape, and building reproducible, auditable clustering pipelines.

HardTechnical

40 practiced

Design a statistical framework to compare two clustering algorithms A and B on the same unlabeled dataset and test whether A produces significantly better clusters. Discuss which internal metrics to compare, how to use bootstrap or permutation testing to obtain confidence intervals, and how to account for randomness in initializations.

Sample Answer

Overview: Treat the comparison as a paired statistical test on an internal cluster-quality metric (or a set) aggregated over resamples. Use bootstrapping and permutation to get CIs and p-values; explicitly model algorithm randomness by repeated runs.

1) Choose metrics (internal):- Silhouette score (captures cohesion vs separation).- Calinski–Harabasz (variance ratio) and Davies–Bouldin (lower is better) for complementary views.- If cluster sizes matter, include entropy or balance measures.Use a primary metric (e.g., mean silhouette) and secondary metrics for robustness.

2) Experimental protocol:- For i in 1..R (e.g., R=50) repeat: - Run A with different random seeds → get clustering A_i. - Run B with different random seeds → get clustering B_i. - For each clustering compute metric M(A_i), M(B_i).This yields paired samples {(M(A_i), M(B_i))} capturing initialization variability.

3) Bootstrap CIs for difference:- Compute D_i = M(A_i) - M(B_i).- Use bootstrap (resample R pairs with replacement B_boot times, e.g., 2000) to compute bootstrap distribution of mean(D). Report 95% CI via percentile or BCa.

4) Permutation test for significance:- Use a paired permutation test: for each paired sample i, randomly swap A and B labels with prob 0.5, compute mean difference over R; repeat P times (e.g., 5000) to get null distribution. p-value = fraction of permuted mean differences >= observed mean difference (one-sided if directional).- This respects dependence between paired runs and initialization.

5) Account for dataset sampling (optional):- If dataset variability matters, perform a nested bootstrap: sample data points (with replacement), run algorithms on each bootstrap dataset, compute metrics, and combine with algorithm randomness (seeds) — treat seed and data resample as two sources of variation.

6) Multiple metrics and corrections:- If testing multiple metrics, control FDR (Benjamini–Hochberg) or use multivariate tests (e.g., paired Hotelling’s T2 on vector of metrics after verifying assumptions).

7) Practical considerations:- Ensure R large enough to capture initialization variance; balance compute cost.- Report effect size (mean difference, Cohen’s d on paired samples) and CIs.- Visualize distributions (violin/boxplots), bootstrap and permutation histograms.- If clustering outputs differ in K, restrict comparison to same K or use metrics robust to K, or compare stability/consistency instead.

This framework provides paired, nonparametric inference that accounts for algorithmic randomness and sampling uncertainty, yielding interpretable CIs, p-values, and effect sizes.

HardTechnical

57 practiced

Propose and justify improvements to standard K-Means to handle anisotropic clusters that have different covariance shapes (elongated or rotated clusters). Describe algorithmic changes (e.g., Mahalanobis distance, per-cluster covariance estimation, switching to Gaussian Mixture Models), provide pseudocode for one approach, discuss numerical stability and complexity, and outline experiments on synthetic anisotropic datasets to validate your approach.

Sample Answer

Approach summary:To handle anisotropic (elongated/rotated) clusters, replace isotropic Euclidean distances with Mahalanobis distance using per-cluster covariance estimates, or move to a full Gaussian Mixture Model (GMM) fitted by EM. Mahalanobis K-Means is a lightweight extension: iteratively assign points to clusters by Mahalanobis distance d_k(x) = (x-µ_k)^T Σ_k^{-1} (x-µ_k), then update µ_k and Σ_k (regularized). For richer modeling and soft assignments use full GMM (means, covariances, priors) with EM.

Pseudocode (Mahalanobis K-Means with regularized covariances):

python

# pseudocode (Python-like)
initialize K means µ_k (k=1..K) by k-means++ or random
for k: Σ_k = I (dxd identity)
for iter in 1..T:
    # Assignment step using Mahalanobis distance
    for each point x_i:
        assign to cluster c = argmin_k ( (x_i-µ_k).T @ inv(Σ_k) @ (x_i-µ_k) )
    # Update step
    for k in 1..K:
        X_k = points assigned to k
        if |X_k| == 0: reinitialize µ_k, Σ_k
        µ_k = mean(X_k)
        Σ_k = cov(X_k) + λ I   # regularize to ensure PD
        # optionally shrink toward global covariance: Σ_k = α Σ_k + (1-α) Σ_global
    if assignments converged: break
return {µ_k, Σ_k}

Key reasoning:- Mahalanobis accounts for orientation and scale of clusters; per-cluster Σ_k models anisotropy.- Regularization λ>0 prevents singular Σ_k when |X_k| ≤ d or when points are collinear.- Shrinking toward a global covariance improves stability when clusters small.

Numerical stability:- Use Cholesky or SVD for Σ_k^{-1} and log-determinant computations. If Σ_k is near-singular, add λ I (e.g., λ = 1e-6 * trace(Σ_k)/d).- For high-dim data, reduce dimensionality (PCA retaining >95% variance) before estimating covariances to reduce variance and computational cost.- Monitor condition number; cap it to avoid unstable inverse.

Complexity:- Per iteration: assignment cost O(N K d^2) if inverting Σ_k naively; but precompute Σ_k^{-1} (O(K d^3) per update). For moderate d, cost manageable. GMM-EM has similar per-iteration cost but also computes responsibilities (soft assignments) and log-likelihood; number of iterations may differ.

Alternatives & trade-offs:- Full GMM (full covariances) handles anisotropy naturally with principled likelihood; supports soft clusters and model selection (BIC/AIC). Drawback: slower, sensitive to initialization.- Constrained covariances (diagonal / tied) reduce params and variance.- Spectral clustering or DBSCAN if shapes are non-ellipsoidal.

Validation experiments (synthetic):1. Datasets: generate 2D/10D mixtures with K clusters, vary: - Aspect ratio (eigenvalue ratios of Σ_k: 1, 5, 20) - Rotation angles uniformly random - Cluster overlap (Mahalanobis distance between means) - Different cluster sizes2. Baselines: Euclidean K-Means, Mahalanobis K-Means, GMM (full cov), spectral clustering.3. Metrics: Adjusted Rand Index (ARI), Silhouette (Mahalanobis-aware), average log-likelihood (for GMM), runtime, convergence iterations.4. Ablations: test λ values, PCA preprocessing, tied vs per-cluster covariances.5. Visualization: 2D scatter with ellipses for estimated covariances; plot ARI vs aspect ratio and overlap.

Expected outcome:Mahalanobis K-Means significantly improves clustering for elongated/rotated ellipsoidal clusters over Euclidean K-Means with modest extra cost; full GMM gives best likelihood and smoother boundaries but at higher runtime and sensitivity to initialization. Regularization and dimensionality reduction are critical for numerical stability in practice.

EasyTechnical

44 practiced

Using scikit-learn in Python, explain how to fit a KMeans model and interpret the key attributes: cluster_centers_, labels_, inertia_, and n_iter_. Show a concise example of fitting KMeans with 5 clusters and using the model to predict cluster assignments for new points.

Sample Answer

To fit KMeans in scikit-learn and interpret its key attributes: use sklearn.cluster.KMeans. Fit builds centroids; attributes give model state.

python

from sklearn.cluster import KMeans
import numpy as np

# Example data
X = np.random.randn(200, 2)

# Instantiate and fit KMeans with 5 clusters
kmeans = KMeans(n_clusters=5, random_state=42)
kmeans.fit(X)

# Key attributes
centers = kmeans.cluster_centers_   # shape (5, 2)
labels = kmeans.labels_             # length 200, cluster index per sample
inertia = kmeans.inertia_           # sum of squared distances to centroids
n_iter = kmeans.n_iter_             # iterations run until convergence

# Predict cluster for new points
new_points = np.array([[0, 0], [2, 2], [-1, 3]])
preds = kmeans.predict(new_points)
print(centers, labels[:5], inertia, n_iter, preds)

Explanation:- cluster_centers_: centroid coordinates — use for prototype inspection or initialization in downstream tasks.- labels_: assignment of each training sample to a cluster.- inertia_: lower is better (within-cluster variance); useful to compare k choices (elbow method).- n_iter_: iterations KMeans used to converge (monitor for convergence issues).

Edge cases / tips:- Standardize features beforehand if scales differ.- Set n_init (default 10+) and random_state for stable results.- KMeans assumes roughly spherical clusters; consider other clustering for complex shapes.

HardSystem Design

43 practiced

Design an online K-Means variant suitable for streaming data with limited memory. Specify data structures to maintain, incremental update rules, how to decay the influence of old data (time-weighting), detection criteria for when to split or merge clusters, and how to bound memory while maintaining reasonable cluster quality.

Sample Answer

Requirements & constraints:- Infinite streaming points, limited memory (fixed budget B of cluster summaries), low-latency updates, ability to adapt to concept drift (time-weighting), maintain reasonable cluster quality.

High-level approach:Use a micro-cluster summary representation (similar to CluStream/StreamKM++): maintain up to B weighted summaries (centroid, weight, timestamp, sum-of-squares) and update them online. Periodically run lightweight reclustering among summaries if needed.

Data structures to maintain (per micro-cluster):- id- N: effective weight (sum of time-decayed counts)- LS: linear sum vector (sum w_i * x_i) — for centroid computation- SS: squared sum (sum w_i * x_i^2) — for variance and radius- t_last: last update timestamp- t_created: creation time- optional: covariance diagonal or max-radius

Incremental update rules:- On arrival of point x at time t: - Apply time decay to cluster weights: for cluster c, scale N, LS, SS by exp(-λ*(t - t_last_c)) or multiply by γ^{Δt}, then set t_last_c = t. - Find nearest cluster centroid (Euclidean or other). If distance d <= threshold R_c (adaptive), absorb point: - w_point = 1 - N' = N + w_point - LS' = LS + w_point * x - SS' = SS + w_point * x^2 - centroid = LS'/N' - If no cluster within threshold, create a new micro-cluster. If B exceeded, trigger memory bounding (see below).

Time-weighting / decay:- Exponential decay with rate λ (or factor γ per time unit) applied lazily at cluster update time to N, LS, SS. This reduces influence of old points and enables concept drift adaptation.- Alternative: sliding-window reservoir implemented by decay factor that approximates fixed horizon.

Split & merge criteria:- Merge: Periodically compute pairwise merge candidates among current micro-clusters ordered by centroid distance / combined variance. Merge clusters i,j if: - distance(ci,cj) < α * sqrt(var_combined) and combined N <= threshold_N_merge - or merging reduces total BIC/AIC-like penalty. - Update LS,SS,N,t_created=min, t_last=max.- Split: For a cluster c, consider splitting if: - cluster variance (from SS and LS) > σ_max and N > N_min (enough weight), and a 2-means on points assigned to that micro-cluster (approx using synthetic samples from LS/SS or buffered recent points) shows two well-separated centroids (gap > β*std). - Implement split by creating two clusters initialized from buffered recent points or by perturbing centroid along top variance axis.

Bounding memory while maintaining quality:- Keep at most B micro-clusters. On creation when full: - Option A (merge smallest-distance pair): merge the two clusters whose merge increases distortion least (min ΔWCSS). - Option B (drop oldest/low-weight): expire clusters with N below a threshold or whose decayed N < ε (old/outliers). - Hybrid: first remove tiny/noisy clusters, then merge closest clusters until <=B.- Maintain a small circular buffer of recent points per cluster for possible split tests (bounded total memory).

Auxiliary components:- Periodic reclustering: every T points or time window, run k-means on micro-cluster centroids (weighted by N) to produce K higher-level clusters for downstream tasks.- Monitoring: track cluster counts, average radius, drift indicators (rapid centroid movement) to tune λ, thresholds.

Complexity & trade-offs:- Per-point update: O(M) to find nearest among M<=B (use approximate NN like HNSW or LSH to reduce to sublinear).- Memory: O(B * d) where d is dimensionality (+ small buffers).- Trade-offs: larger B and buffers improve quality but cost memory/compute. Aggressive decay helps drift but may fragment stable clusters.

Practical tips:- Normalize features, use cosine or Mahalanobis distance if features vary.- Choose λ based on expected drift rate; tune merge/split thresholds on held-out streaming traces.- Use weighted reclustering on summaries to rebuild high-quality centroids occasionally.

MediumTechnical

52 practiced

Compute the silhouette coefficient by hand for a small labeled example. Given points and assignments:Cluster A: p1=(0,0), p2=(0,1), p3=(1,0)Cluster B: p4=(5,5), p5=(5,6), p6=(6,5)Calculate a(i) and b(i) for p1 and then compute p1's silhouette. Finally compute the average silhouette for the clustering. Show your steps and formulas.

Unlock Full Question Bank

Get access to hundreds of K Means Clustering and Unsupervised Learning interview questions and detailed answers.

Join thousands of developers preparing for their dream job.