What is kmeans++ initialization, and how does it work?

In this article

1. Before you start
2. Why interviewers ask this
3. kmeans++ initialization from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one step of the machine learning algorithms learning path.

Why interviewers ask this

The question separates a candidate who has run k-means from one who knows why it can fail. Anyone can say "k-means picks k centers and repeats." The follow-up is where the starting centers come from and what goes wrong when they are chosen badly.

A weak answer says "k-means++ picks centers that are far apart." A strong answer says the first center is uniform, each later center is sampled with probability proportional to squared distance, and that far points are likely but not certain. A Staff-level answer adds what the method does not do: it improves the starting point, it does not remove local minima, and the published bound is on the expected cost. The related question of how k-means differs from a classifier is covered in k-means versus k-nearest neighbors.

kmeans++ initialization from first principles

kmeans++ initialization

kmeans++ initialization is a seeding rule for k-means that chooses the first center uniformly at random from the data points and each later center from the data points with probability proportional to its squared distance from the nearest center already chosen, before the ordinary k-means loop starts.

D² weighting

D² weighting is the sampling rule inside kmeans++ initialization in which a data point x is chosen with probability $D(x{)}^2$ divided by the sum of $D(x{)}^2$ over all points, where $D(x)$ is the distance from x to the closest center already chosen.

In plain words

Imagine opening k pizza shops in a town so that every house is close to one. The first shop goes anywhere. For the second, you spin a wheel with one slice per house. A house far from every existing shop gets a fat slice, a house next door to a shop gets a sliver. You will probably land far away, but you might not. That is kmeans++ initialization explained without math. The analogy breaks in one place: in real k-means the seeds are data points, and afterwards each center moves to the middle of its cluster.

k-means is a clustering method that groups points around k centers. Its loop has two moves. Each point joins its nearest center. Then each center moves to the centroid of its points; a centroid is the mean position of the points assigned to one cluster. The loop repeats until nothing changes. It always stops, but it may stop at a local minimum, which is a solution that no small change improves although a better one exists elsewhere. The same idea appears in gradient descent.

In one precise sentence, kmeans++ initialization chooses the k starting centers by sequential sampling with $D(x{)}^2$ weights, then hands them to the ordinary loop.

Step 1: Pick the first center uniformly at random

The goal of k-means is stated in Arthur and Vassilvitskii (2007): "choose k centers so as to minimize φ, the sum of the squared distances between each point and its closest center." Solving this exactly is nondeterministic polynomial-time (NP) hard, so in practice the loop is used. The paper notes it is standard practice to choose the initial centers uniformly at random, and that this can give arbitrarily bad clusterings.

kmeans++ starts the same way. The first center is a data point chosen uniformly at random. Input: n points. Output: one center, which is one of those points. After this step the weights of Step 2 take over.

Step 2: Weight every point by its squared distance to the nearest center

Let $D(x)$ be the shortest distance from a data point x to the closest center chosen so far. Arthur and Vassilvitskii (2007) choose the next center from the data points with probability $D(x{)}^2$ divided by the sum of all $D(x{)}^2$, and call this D² weighting. The reason for the square is that $D(x{)}^2$ is exactly point x's current share of the cost φ, so the draw targets the points that add the most cost (Arthur and Vassilvitskii, 2007).

This is not "take the farthest point." A far point has a large weight, so it is likely, but a near point still has some chance, so the draw stays random. A point that is already a center has distance zero and weight zero, so it cannot be picked twice. Every center is an actual data point. Squaring the distance makes the weight grow faster than the distance, so one far group dominates the draw.

As an analogy, D² weighting resembles the balance described in exploration versus exploitation: it favors unexplored areas without ruling out anything.

Step 3: Draw the next center and repeat until k are chosen

After each draw, the distances are updated: a point's $D(x)$ is the smaller of its old value and its distance to the new center. Then the weights are recomputed and another center is drawn. This repeats until k centers have been taken altogether.

Input: the current centers. Output: one more center, with the weights shrinking near it. The cost follows from the loop. Updating $D(x)$ for all n points against the newest center, in d dimensions, takes work proportional to n times d, and k centers need k such passes, so seeding costs on the order of n times k times d. That is derived here, not quoted from the paper. Seeding is a small addition to the loop that follows.

Step 4: Run the ordinary k-means loop

The last step changes nothing. The k seeds go into the standard loop of assigning points and moving centers. The paper's text says to proceed as with the standard k-means algorithm. The scikit-learn guide says the result depends strongly on the starting centers and that k-means may converge to a local minimum (scikit-learn user guide, version 1.9.1, accessed 2026-10-26).

The paper also proves a bound on the cost. Theorem 3.1 of Arthur and Vassilvitskii (2007) states

where $\phi$ is the cost of the seeding and ${\phi }_{\text{opt}}$ is the cost of the best possible clustering. The authors prove it holds after the seeding step alone, and the later loop can only lower the cost. You now have the whole method: a random start, weighted draws, then the standard loop.

1 · First center2 · Weights3 · Draw and repeat4 · Ordinary loopReplay

Step-by-step description

1. One data point is chosen uniformly at random.
2. Each point is weighted by its squared distance.
3. The next center is drawn until k are chosen.
4. The standard k-means loop starts from the seeds.

• The first center is a data point chosen uniformly at random.
• Each next center is drawn with probability proportional to its squared distance from the nearest chosen center.

Worked example

Take the six points from the scikit-learn documentation: (1,2), (1,4), (1,0), (10,2), (10,4) and (10,0), with k set to two. Suppose the first center is (1,2). The squared distances to it are 0, 4, 4, 81, 85 and 85, which sum to 259.¹ Each probability is a squared distance divided by 259.

Of being the second center, each far point has probability 0.3127 or 0.3282, and each near point has 0.0154.¹ Uniform random choice gives every other point 0.2.¹ The far group together gets 0.9691 against 0.6, so kmeans++ lands in the other cluster almost every time without being certain to.

Text description of the diagram

• With the first center at (1,2), each far point has probability 0.3127 or 0.3282 of being the second center, and each near point has 0.0154.
• Uniform random choice gives every other point 0.2.

If the draw is (10,2), the loop assigns three points to each center. Each cluster has squared distances 0, 4 and 4, so its cost is 8 and the inertia is 16.0, the value in the scikit-learn k_means page.¹

Now a case where seeding matters. Put six illustrative points on a line: 0, 1, 10, 11, 20 and 21, with k equal to three. The best clustering pairs them, with centers at 0.5, 10.5 and 20.5 and an inertia of 1.5.¹ Start the loop from the bad seeds 0, 1 and 10 and it stops with centers 0, 1 and 15.5, an inertia of 101.0, a local minimum.¹ Three uniform draws put one seed in each pair with probability 0.4.¹ With kmeans++, after the first center 0, the chance that the second is the neighbor 1 is 1 in 1063, or 0.0009, against 0.2 for a uniform draw.¹

The bound is a different kind of number. For k equal to 10 the factor 8(ln k + 2) is 34.4, and for k equal to 100 it is 52.8.¹ This is a worst-case expected ratio, not typical performance. The paper reports that its experiments show the method often improves both speed and accuracy "quite dramatically", but the authors' experimental figures were not re-read for this page, so none is quoted here.

Trade-offs and edge cases

kmeans++ improves the starting point, not the model. Four cases show where the textbook answer needs care.

The bound is on average. The factor is on the expected cost, so a single run can still land in a local minimum. The analysis is also tight (Arthur and Vassilvitskii, 2007, Section 4), so the logarithmic factor cannot be improved for this seeding. The scikit-learn guide still says to run k-means several times with different starts (user guide).

scikit-learn is not the paper. The paper's bound applies to the vanilla algorithm, while scikit-learn uses a greedy variant that makes several trials at each sampling step and keeps the best candidate (KMeans documentation). Also, scikit-learn runs one initialization with k-means++ and ten with random when n_init is auto; the value was 10 before version 1.4.

Text description of the diagram

• The paper's bound applies to the vanilla algorithm, while scikit-learn uses a greedy variant.
• scikit-learn runs one initialization with k-means++ and ten with random when n_init is auto.

Random seeding has no bound on the ratio of its cost to the optimal cost. The paper says so for the standard method.

Outliers and scale. A distant outlier has a large squared distance, so it is a likely center. This follows from the weighting rule; it is not a result quoted from the paper. Distances drive the weights, so features on very different scales distort them; see feature engineering techniques for scaling.

Wrong k and odd shapes. A better start does not fix a wrong number of clusters or clusters that are not round. Bisecting k-means cannot use this seeding by design (scikit-learn user guide). The stability example in the scikit-learn gallery compares random and k-means++ starts for how much the final inertia varies.

How to answer it in an interview

The spoken structure: name the rule, say the weighting, say what stays the same, then give the bound and its limit.

Common mistakes

• "kmeans++ picks the farthest points." (wrong) It samples, so far points are likely but not certain. (right) "It draws each center with probability proportional to squared distance."
• "kmeans++ finds the best clustering." (wrong) The bound is on the expected cost and the loop can still stop at a local minimum. (right) "It starts closer to a good solution on average, and I still use restarts."
• "kmeans++ is a different clustering algorithm." (wrong) Only the seeding changes. (right) "After the seeds, it is the standard k-means loop."
• "scikit-learn runs the paper's algorithm." (wrong) It runs a greedy variant with several trials per step. (right) "scikit-learn's k-means++ is the greedy version, so the paper's bound is for the vanilla one."

Follow-up questions

Does k-means++ pick the farthest points?

No. It samples each center with probability proportional to squared distance, so far points are favored but a nearby point can still be drawn. Choosing the farthest point every time would be a different rule that is easily pulled toward outliers.

Does k-means++ find the global optimum?

No. It gives an expected cost within a factor of 8(ln k + 2) of optimal, and the final result can still be a local minimum (scikit-learn user guide).

Why does k-means++ use squared distance and not plain distance?

Because $D(x{)}^2$ is exactly the amount point x currently adds to the cost φ, so squared-distance sampling picks points in proportion to their share of the cost, the link the proof of Theorem 3.1 relies on (Arthur and Vassilvitskii, 2007). Plain distance would not match the quantity k-means minimizes.

Is scikit-learn's k-means++ the same as the paper's algorithm?

Not exactly. The scikit-learn documentation describes "greedy k-means++", which makes several trials at each sampling step and keeps the best centroid among them.

Do you still need several restarts with k-means++?

Often yes. The scikit-learn guide recommends several initializations, and the default of one k-means++ run is a default choice, not a proof that restarts are useless. Seed-to-seed spread in inertia is optimization randomness, not the model variance of bias versus variance.

What does the bound on k-means++ actually say?

It says the expected cost after seeding is at most 8(ln k + 2) times the optimal cost. It is an average over the random draws, grows slowly with k, and is a worst-case limit on the ratio, not a prediction for your data.

Sources

1. k-means++: The Advantages of Careful Seeding — Arthur and Vassilvitskii, SODA 2007 (date is the conference date; the linked copy is the published SODA 2007 paper), 7 Jan 2007
2. sklearn.cluster.KMeans — scikit-learn documentation, version 1.9.1 (accessed 2026-10-26), 26 Oct 2026
3. sklearn.cluster.k_means — scikit-learn documentation, version 1.9.1 (accessed 2026-10-26), 26 Oct 2026
4. 2.3 Clustering: K-means — scikit-learn user guide, version 1.9.1 (accessed 2026-10-26), 26 Oct 2026
5. Empirical evaluation of the impact of k-means initialization — scikit-learn example gallery, version 1.9.1 (accessed 2026-10-26), 26 Oct 2026