In this article
Before you start
This page sits in the machine learning algorithms learning path and uses ideas from statistics for machine learning and data roles.
Why interviewers ask this
K-means is reported by candidates in data science and machine learning interviews, usually as "explain k-means" or "how do you choose K". It looks easy because the loop fits in two sentences, so interviewers use it to see what a candidate knows beyond the loop.
A weak answer recites the loop and stops. A strong answer adds that the result depends on where the loop starts, that K must be chosen by you, and that the method assumes compact, similar-sized clusters. A Staff-level answer also explains why the loop must stop, how to pick K with evidence, and when to reach for a different method.
K-means from first principles
- Centroid
- A centroid is the mean of the points in one cluster, calculated coordinate by coordinate. It lives in the same space as the data but, as the scikit-learn guide (read 2026-10-26) notes, it is not in general one of the data points.
- Inertia
- Inertia is the within-cluster sum of squares (WCSS): the sum, over all points, of the squared distance to the nearest centroid. Stanford's clustering lecture calls the same quantity the residual sum of squares (RSS). Lower is better, and k-means tries to make it small.
In plain words
Unsupervised means the data has no labels: nobody tells the algorithm the right groups. Picture a pizza chain placing K delivery hubs. Every house is served by its nearest hub. Then each hub moves to the center of the houses it serves. Houses may now be closer to a different hub, so you repeat. The analogy breaks in one place. Real hubs follow roads. K-means uses straight-line distance, and the hub's spot is an average that may fall where no house stands.
In one precise sentence, k-means looks for K centroids that make the sum of squared distances from each point to its nearest centroid as small as it can reach.
Step 1: Choose K and the starting centroids
K-means needs the number of clusters K and K starting centroids. The scikit-learn guide says the algorithm requires the number of clusters to be specified (read 2026-10-26), so K is your choice, not an output. Random initialization picks K data points as the starting centroids, per the KMeans reference (read 2026-10-26).
K-means++ (k-means with careful seeding) is a seeding rule that picks the first centroid at random, then draws each new one with probability proportional to D(x)², the squared distance from point x to the nearest seed already chosen, so seeds tend to spread out. It is the scikit-learn default and, per the same reference, speeds up convergence. Arthur and Vassilvitskii (2007) report that on their Cloud dataset it ran almost twice as fast with objective values about 20% better.
Input: the data and K. Output: K starting centroids.
Step 2: Assign every point, then move every centroid
Each pass has two moves. In the assign move, every point joins the cluster of its nearest centroid by squared straight-line distance. In the update move, each centroid moves to the mean of the points now assigned to it.
The mean is the right place to move to. For a fixed group of points, the mean is the spot with the smallest total squared distance to them, as the Stanford clustering lecture (read 2026-10-26) argues for the residual sum of squares. Reassigning points to their closest centroid cannot raise inertia either. So neither move can make the objective worse.
Input: the current centroids. Output: new labels and new centroids.
Step 3: Repeat until nothing changes, and why the start decides the answer
The loop stops when no assignment changes, at a local minimum. A local minimum is a solution that no single pass can improve, even though a better one may exist elsewhere. The scikit-learn guide puts it this way: "Given enough time, K-means will always converge, however this may be to a local minimum" (scikit-learn 1.9.1, read 2026-10-26). The KMeans defaults also cap the loop at max_iter=300 passes and stop on a small centroid movement set by tol.
Where it lands depends on the start. On six points, two different pairs of seeds reach inertia 16 and inertia 125.5, and the worse run splits the data the wrong way.1 Finding the clustering with the lowest possible inertia is, in general, among the problems believed to have no fast exact method (Aloise et al., 2009, who prove it hard), so the standard fix is several starts. KMeans keeps the best of n_init runs by inertia; with n_init='auto' that is one run for k-means++ and ten for random seeds.
Step-by-step description
- K seeds become the first centroids.
- Assign every point, then move each centroid.
- Stop when no assignment changes.
- In the assign move, every point joins the cluster of its nearest centroid.
- The loop stops when no assignment changes, at a local minimum.
Knowing it is half the job. Saying it is the other half.
Interview Clozo is an AI interview copilot for real interview rounds: it hears the question and puts a strong answer on your screen, and you say it in your own words. See the features or how it works.
Start Free Trial →Worked example
Take the six points of the KMeans documentation example (read 2026-10-26): (1,2), (1,4), (1,0), (10,2), (10,4) and (10,0), with K = 2. The docs report the centroids (1,2) and (10,2) for this data, and the script reproduces them.1
A good start. Seed the centroids at (1,0) and (10,0). The first assignment sends the left three points to one centroid and the right three to the other, with inertia 40. After the centroids move to (1,2) and (10,2), inertia is 16: each cluster has squared distances 0 + 4 + 4 = 8, so the total is 16. The second pass changes nothing, so the loop stops after two passes.1
A bad start. Seed the centroids at (1,0) and (1,2). The first assignment gives inertia 251. After the update the centroids are (5.5,0) and (5.5,3) and inertia is 125.5. The second pass changes no assignment, so the loop stops there: it split the points into a bottom row and a top group instead of left and right.1
Text description of the diagram
- The first assignment gives inertia 251, and after the update inertia is 125.5.
- The second pass changes no assignment, so the loop stops there.
Choosing K. The elbow method is a heuristic for picking K: plot the lowest inertia for each K and look for the point where the curve bends from a steep fall to a slow one. Checking every possible split of the six points, inertia falls from 137.5 at one cluster to 16 at two clusters and reaches 0 at six clusters.1 The sharp bend at K = 2 matches the two visible groups.
Text description of the diagram
- Inertia falls from 137.5 at one cluster to 16 at two clusters and reaches 0 at six clusters.
- The sharp bend at K = 2 matches the two visible groups.
Checking the result. The silhouette coefficient of one point is (b - a) / max(a, b), where a is the mean distance to the other points in the same cluster and b is the mean distance to the points of the nearest other cluster. The silhouette score is the mean of that coefficient over all points. It runs from -1 to 1, and values near 0 mean overlapping clusters (scikit-learn silhouette_score, read 2026-10-26). For point (1,2) at K = 2, a is 2 and b is about 9.15, so its coefficient is about 0.78; the mean over all six points is about 0.71.1
| Quantity | Value (computed) |
|---|---|
| Inertia with all six points in one cluster | 137.5 |
| Inertia, seeds (1,0) and (10,0): at the seeds, then after the update | 40, then 16 |
| Inertia, seeds (1,0) and (1,2): at the seeds, then after the update | 251, then 125.5 |
| Passes before no assignment changes | 2 |
| Silhouette of point (1,2), and mean silhouette, at K = 2 | about 0.78 and about 0.71 |
| Nearest centroid for new points (0,0) and (12,3) | (1,2) and (10,2) |
A fitted model can label new points: the KMeans reference shows the same six points with predict sending (0,0) and (12,3) to the clusters of (1,2) and (10,2).1
Trade-offs and edge cases
K-means is fast and simple, and Arthur and Vassilvitskii note that it offers no accuracy bound even though its simplicity and speed are appealing in practice. Its weak points are worth naming in an interview.
- K is your choice. Inertia is not normalized and zero is optimal (scikit-learn guide, read 2026-10-26), and in the example it reaches 0 at K = 6, so it cannot pick K alone.1
- Shape. Inertia assumes clusters are convex and isotropic, which is not always the case. Elongated or irregular shapes fit badly, and k-means behaves like a Gaussian mixture model whose components all share one small, spherical covariance (and hard assignments), per the scikit-learn guide; a full Gaussian mixture model with its own covariance per component fits elongated clusters better.
- Scale and dimensions. A feature measured in thousands drowns one measured in fractions, so scale features first. The scikit-learn guide also notes that Euclidean distances inflate in high dimensions and mentions dimensionality reduction, such as principal component analysis (PCA), as a remedy.
- Outliers. A mean moves toward extreme values, so one far-away point can drag a centroid. K-medoids or another median-based variant, which uses a real data point as each centre, is the more outlier-tolerant alternative; flagging extreme points before clustering is the topic of anomaly detection.
- Cost. Each pass measures the distance from every one of n points to each of k centroids over d features, so one pass costs O(n·k·d) and a run of T passes costs O(n·k·d·T). The KMeans reference notes (read 2026-10-26) give the average complexity as O(k n T) and the worst case as O(n^(k+2/p)), where p is the number of features.
- K-means++ is better, not optimal. Per Arthur and Vassilvitskii (2007) it is O(log k)-competitive with the optimal clustering in expectation; on the Intrusion dataset they report objective values better by factors of 10 to 1000 and runs up to 70% faster.
| Method | What you read | Caveat |
|---|---|---|
| Elbow method | the bend in the inertia curve | a heuristic; the bend can be unclear |
| Silhouette score | the K with the highest mean score | defined only for 2 to n minus 1 clusters |
K-means lowers its objective step by step, a little like gradient descent, but it has no learning rate: each pass jumps straight to the best centroids for the current labels.
How to answer it in an interview
How does k-means work, and what are its weaknesses?
K-means splits data into K clusters. I pick K and starting centroids, ideally with k-means++ so the seeds spread out. Then I repeat two steps: assign each point to its nearest centroid, then move each centroid to the mean of its cluster. Each step can only lower the sum of squared distances, so it stops, but at a local minimum, so I run several starts and keep the lowest inertia. It assumes compact, similar-sized clusters, so I scale features first and choose K with the elbow or the silhouette score.
The spoken structure: say what it does, give the two-step loop, then the local-minimum catch and how you handle it, then the assumptions.
Common mistakes
- "K-means finds the best clustering." (wrong) It reaches a local minimum. (right) "It converges to a local minimum, so I keep the best of several starts."
- "The centroids are data points." (wrong) They are means and are not in general points from the data. (right) "Centroids are cluster means; they can fall between points."
- "Pick the K with the lowest inertia." (wrong) Inertia falls as K rises. (right) "I read the elbow or the silhouette score, not the raw minimum."
- "K-means++ gives the optimum." (wrong) It gives a better expected result with a bound, not the best split. (right) "K-means++ spreads the seeds and improves the expected result."
- "Ten starts is always the default." (wrong) In current scikit-learn,
n_init='auto'means one run with k-means++ and ten with random seeds. (right) "I setn_initon purpose."
Follow-up questions
What is the difference between k-means and KNN?
K-means is an unsupervised method that groups unlabeled points into K clusters. K-nearest neighbors (KNN) is a supervised method that outputs a label from the labels of nearby points. The k-means vs KNN page compares them in full.
How do you choose the value of K in k-means?
Run several values of K and compare the inertia curve for a bend, or pick the K with the highest mean silhouette score. Both are guides, so confirm with domain knowledge about how many groups make sense.
Why does k-means converge?
Each assign move and each update move can only lower or keep the inertia, and there are finitely many ways to label the points. With ties broken consistently (a point stays in its current cluster on a tie), the loop therefore cannot cycle and must stop, as the Stanford clustering lecture explains.
What is k-means++ and why use it?
K-means++ chooses starting centroids that tend to be far apart, with probability tied to each point's contribution to inertia. It speeds up convergence and has an expected approximation bound, so it is the scikit-learn default.
How do you run k-means on very large data?
The scikit-learn overview table lists a mini-batch variant for very large numbers of samples. Scale features first and consider reducing dimensions; the feature engineering techniques page covers scaling.
What is the time complexity of k-means?
One pass computes n times k distances over d features, so it costs O(n·k·d), and T passes cost O(n·k·d·T). The KMeans reference gives the average as O(k n T) and a much larger worst case, O(n^(k+2/p)), so in practice the number of passes is what to watch.
- K-means repeats two moves, assign each point to its nearest centroid and move each centroid to its cluster mean, until nothing changes.
- It lowers inertia at every step, so it stops, but only at a local minimum.
- Start choices matter: use k-means++ and keep the best of several runs.
- K is your choice; inertia always falls as K grows, so use the elbow or the silhouette score.
- It assumes compact, similar-sized clusters, so scale features and watch outliers.
Sources
- 2.3 Clustering, K-means section (scikit-learn 1.9.1 documentation) — scikit-learn (accessed 2026-10-26), 26 Oct 2026
- sklearn.cluster.KMeans API reference (scikit-learn 1.9.1) — scikit-learn (accessed 2026-10-26), 26 Oct 2026
- k-means++: The Advantages of Careful Seeding — Arthur and Vassilvitskii, SODA 2007 (accessed 2026-10-26), 1 Jan 2007
- silhouette_score (scikit-learn 1.9.1 documentation) — scikit-learn (accessed 2026-10-26), 26 Oct 2026
- Lecture 14: clustering (K-means, RSS, convergence), CS276 — Stanford University (accessed 2026-10-26), 26 Oct 2026
- NP-hardness of Euclidean sum-of-squares clustering — Machine Learning 75:245-248 (Aloise, Deshpande, Hansen and Popat), 1 Jan 2009
