k-means++: The Advantages of Careful Seeding
2007 · paper · Computer science
Proposes k-means++, which picks starting cluster centers randomly with probability based on each point's contribution to the error. It is shown to be within a logarithmic factor of the optimal clustering, and preliminary experiments show better speed and accuracy than standard k-means.
Checked: PDF from theory.stanford.edu, fetched 4 Oct 2026. Page numbers are those of that PDF.
3 findings
Substance Sec. 6.3: "on the Spam and Intrusion datasets, k-means++ achieved potentials 20 to 1000 times smaller than those achieved by standard k-means". With ratio = 1/(1 − improvement), Tables 3–4 give factors from about 2× (Spam k=10, 49.43%) to about 770× (Intrusion k=50 minimum, 99.87%).
- p. 8 Section 6.3, third paragraph
k-means++ achieved potentials 20 to 1000 times smaller than those achieved by standard k-means
- p. 7 Table 4 (Spam), Average φ k-means++ column
49.43%
- p. 7 Table 3, Intrusion, k=10, Average φ
93.37%
- p. 7 Table 4, k=10 average φ
3.698 · 104 49.43%
Only the authors can say what is right here.
Judge's note: I read Tables 3 and 4 on the page 7 image and converted each printed improvement to a ratio using the caption's definition. Spam: average 1.98×, 8.9×, 21.5×; minimum 2.2×, 9.6×, 17.5×. Intrusion: average 15.1×, 125×, 625×; minimum 17.9×, 147×, 769×. Five of the twelve entries fall below 20×. None reaches 1000×, even allowing for rounding of the printed percentages (99.875% would give 800×). The sentence restricts itself to Spam and Intrusion and gives no narrower restriction. Only the authors can say which comparison the range was meant to describe.
Second check: another model agreed
Report a problem with this finding
Wording In the uncovered-cluster case of the Lemma 3.3 proof, the text reads "It follows that our contribution to E[φOPT] in this case is at most"; the quantity bounded is E[φ′].
- p. 4 Proof of Lemma 3.3, inductive step, uncovered-cluster case (right column, top)
follows that our contribution to E[φOPT] in this case is
- p. 4 Proof of Lemma 3.3, second case (right column, top)
follows that our contribution to E[φOPT] in this case is at most
- p. 4 Proof of Lemma 3.3, second case
contribution to E[φOPT] in this case
- p. 5 Proof of Theorem 3.1
E[φOPT] ≤
Judge's note: This is on p4, at the top of the right column. φOPT is the fixed optimal potential (Section 2), so its expectation is not the random quantity being bounded. The covered case says 'our contribution to E[φ′]', and the combining paragraph says 'Combining the potential contribution to E[φ′] from both cases'. The displayed bound is the contribution to E[φ′]. This is a symbol misprint: the derivation and the lemma are unaffected. The analogous slip in the Theorem 3.1 proof is handled separately as C008.
Second check: another model agreed
Report a problem with this finding
Wording The Theorem 3.1 proof displays "E[φOPT] ≤ (φ(A) + 8φOPT − 8φOPT(A)) · (1 + H_{k−1})"; the left-hand side should be the expected k-means++ potential E[φ].
- p. 5 Proof of Theorem 3.1, displayed inequality
E[φOPT] ≤
- p. 5 Proof of Theorem 3.1, displayed inequality (left column, top)
E[φOPT] ≤ (φ(A) + 8φOPT − 8φOPT(A)) · (1 + Hk−1).
Judge's note: This is on p5, at the top of the left column. I reworked the step. Lemma 3.3 with t=u=k−1 and X_c=A gives E[φ′] ≤ (φ(A)+8(φOPT−φOPT(A)))(1+H_{k−1}), where φ′ is the final seeding potential φ. Then E[φ(A)]=2φOPT(A) by Lemma 3.1 and H_{k−1} ≤ 1+ln k, which gives E[φ] ≤ 8(ln k+2)φOPT. As printed, the left side is the expectation of the constant φOPT, which does not state the theorem. The result stands; the symbol is misprinted. This is distinct from the Lemma 3.3 slip (C006).
Second check: another model agreed
Report a problem with this finding
11 minor (typos and the like; most checked by the judge only)
Reference or label Section 1.1 cites "Mishra et al. [12]", but reference [12] is listed as "Sudipto Guha, Adam Meyerson, Nina Mishra, Rajeev Motwani, and Liadan O'Callaghan".
- p. 2 Section 1.1, last paragraph
Mishra et al. [12]
- p. 9 Reference [12]
Sudipto Guha, Adam Meyerson, Nina Mishra, Rajeev
- p. 2 Section 1.1 Related work, last paragraph
and Mishra et al. [12] and Charikar et al. [6]
- p. 9 Reference [12]
Sudipto Guha, Adam Meyerson, Nina Mishra, Rajeev Motwani, and Liadan O’Callaghan.
Judge's note: On p2 the left column, last paragraph of 1.1, reads 'Mishra et al. [12]'. On p9 reference [12] has Guha as first author and Mishra as third. Elsewhere the paper cites by first author (Inaba et al. [16], Kanungo et al. [17], Ostrovsky et al. [24], Charikar et al. [6]). The reference is relevant; only the attribution form departs from the paper's convention.
Second check: another model agreed
Report a problem with this finding
Wording Related work says of Mettu and Plaxton: "our experimental results seem to be better in terms of both speed and accuracy". Section 6 and Tables 1–4 compare only k-means and k-means++, and Section 7 describes comparisons with other variants as ongoing work.
- p. 2 Section 1.1 Related work, Mettu and Plaxton paragraph
our experimental results seem to be better in terms of both speed and accuracy
- p. 8 Section 7, last paragraph
we are measuring the performance of not only k-means++ and standard k-means, but also other variants
Only the authors can say what is right here.
Judge's note: Checked p2 (Section 1.1), the p6–p7 experiments (Tables 1–4 contain only the k-means and k-means++ columns), and p8 Section 7 ("we are measuring the performance of not only k-means++ and standard k-means, but also other variants"). The paper reports no data comparing against successive sampling. The claim is hedged ('seem to be'), so this is a wording and support question for the authors.
Second check: another model agreed
Report a problem with this finding
Wording Lemma 4.1 is stated for "an arbitrary clustering on X with k − t ≥ 1 centers", but the base case "φ′ = φ = (n − u·n/k − k)·δ² + u·n/k·∆²" holds only when the centers are distinct points of X. The lemma's hypothesis needs to say this.
- p. 5 Lemma 4.1, opening hypothesis
Let C be an arbitrary clustering on X
- p. 5 Lemma 4.1 proof, first displayed equation
φ′ = φ = (n − u · n/k − k) · δ² + u · n/k · ∆².
- p. 5 Lemma 4.1 statement and base case of its proof
Let C be an arbitrary clustering on X with k − t ≥ 1 centers
- p. 5 Proof of Lemma 4.1, base case t = 0
φ′ = φ =
Only the authors can say what is right here.
Judge's note: I read Lemma 4.1 and its proof on the page image (p.5). In the base case t = 0, the cost formula gives each center cost 0, every other point in a covered cluster cost δ², and every point in an uncovered cluster cost ∆². That is true only if the k centers are distinct data points. I rechecked the reviewer's counterexample using the paper's construction: k=2, n=100, δ=1, ∆=100, C = {c1, x_{2,1}}. The simplex radius squared is (n−k)/(2n)·δ² = 0.49. Cluster 2 is the only cluster with a chosen data point, so u = 1, and φ′ = 50·0.49 + 49·1 = 73.5. The printed base-case formula gives 500048. The lemma's lower bound gives 0.96·(100·1.5·0.9996 + 499800) ≈ 479952. Both are far above 73.5, so the lemma is false as literally worded. A second check, with the optimal centers {c_i} and u = 0, gives the same result. However, the paper defines 'uncovered' as 'those clusters of C0 from which we have not chosen a center', and the lemma is applied only to D²-seeded centers, which are distinct data points. So the restriction is implicit in the paper, and the lower-bound theorem is unaffected. The fix is to state in the hypothesis that the centers are distinct points of X. The step is false as worded but the main result stands, so I rated it S3 and sent it to the authors as a query.
Second check: another model agreed
Report a problem with this finding
Wording Sec. 6.3 says "k-means++ consistently outperformed k-means, both by achieving a lower potential value ... and also by having a faster running time", but Table 1 (Norm25, k=50) prints Average T improvement "−1.62%", which means k-means++ was slower in that case.
- p. 8 Section 6.3 Results, first paragraph
We observe that k-means++ consistently outperformed
- p. 7 Table 1, k=50, Average T, k-means++
−1.62%
- p. 8 Section 6.3 Results, first paragraph
We observe that k-means++ consistently outperformed k-means, both by achieving a lower potential value, in some cases by several orders of magnitude, and also by having a faster running time.
- p. 8 6.3 Results
k-means++ consistently outperformed k-means
Only the authors can say what is right here.
Judge's note: I checked page 7, Table 1. The minus sign is printed. The caption defines improvement as 100%·(1 − k-means++ value / k-means value), so a negative value means k-means++ took longer: about 2.04*1.0162 ≈ 2.07 s against 2.04 s. All the other 11 time entries in Tables 1–4 are positive, and every potential improvement is positive, including the small 0.53% and 0.93%. So the potential part of the claim holds and only 'consistently ... faster running time' has an exception. The gap is small and may be noise, so this is a wording overstatement rather than a wrong result.
Second check: another model agreed
Report a problem with this finding
Wording Sec. 6.3: "Each trial also completed two to three times faster" (in the context of Spam and Intrusion). Using the paper's own rule (a 90% improvement = a factor 10 speedup), the Average T improvements in Tables 3–4 give about 1.8×–3.0× for Intrusion and 3.2×–5.0× for Spam.
- p. 8 Section 6.3, third paragraph
Each trial also completed two to three times faster
- p. 7 Table 4, Average T k-means++, k=25
79.84%
- p. 7 Table 3, Intrusion, Average T, k=10
44.49%
- p. 7 Tables 1-4, Average T
−1.62%
Only the authors can say what is right here.
Judge's note: I read the Average T columns on page 7. The paper's rule (90% improvement = factor 10 speedup) gives speedup = 1/(1 − improvement). Intrusion: 44.49%→1.80×, 49.19%→1.97×, 66.70%→3.00×. Spam: 69.00%→3.23×, 79.84%→4.96×, 75.76%→4.13×. The stated range '2 to 3' is a loose summary that the Spam values exceed and Intrusion k=10 falls slightly below. This is a wording imprecision. The −1.62% pointer refers to Norm25, which this sentence does not cover; that point is handled in C016.
Second check: another model agreed
Report a problem with this finding
Typo Grammar error in Section 2.1: "To see that Step 3 does in fact decreases φ"; this should read "decrease".
- p. 2 Section 2.1, paragraph before Lemma 2.1
that Step 3 does in fact decreases φ
- p. 2 Section 2.1
Step 3 does in fact decreases φ
Judge's note: Seen on the p2 page image, right column, paragraph before Lemma 2.1.
Second check: none (judge only)
Report a problem with this finding
Typo Duplicated word in the Lemma 3.3 statement: "Let C′ denote the the resulting clustering".
- p. 4 Lemma 3.3 statement
Let C′ denote the the
- p. 4
h D2 weighting. Let C′ denote the the resulting clusterin
Judge's note: Seen on the p4 page image, left column, in the Lemma 3.3 statement; the duplication sits within a single line.
Second check: code check
Report a problem with this finding
Typo Section 4 uses an undefined symbol: "(those clusters of C_0 from which we have not chosen a center)"; the optimal clustering is denoted C_OPT everywhere else.
- p. 5 Section 4, paragraph before Lemma 4.1
those clusters of C0 from which we have not chosen a center
- p. 5 Section 4, paragraph before Lemma 4.1
(those clusters of C0 from which we have not chosen a center)
- p. 5 Section 4
those clusters of C0 from which
Judge's note: The C009-a crop clearly shows a calligraphic C with subscript 0. C_0 is never defined. Lemma 4.1, immediately below, uses 'u clusters from C_OPT uncovered'.
Second check: none (judge only)
Report a problem with this finding
Typo Lemma 4.1 defines H′_u with a subscript, but the proof displays use "H′(u) − H′(u−1)" (p5 bottom, p6 top) next to "H′_u − H′_{u−1}".
- p. 5 End of Lemma 4.1 proof, last display
H′(u) −H′(u −1)
- p. 6 Top of left column
H′(u) −H′(u −1)
Judge's note: Seen on p5 (last display, right column) and p6 (top left), where both notations appear within two lines. The meaning is clear; this is a cosmetic inconsistency.
Second check: none (judge only)
Report a problem with this finding
Typo Duplicated word in the Lemma 4.1 statement: "Let C′ denote the the resulting clustering".
- p. 5 Lemma 4.1 statement
Let C′ denote the the
Judge's note: Seen in the C009-a crop and on the p5 page image, left column, in the Lemma 4.1 statement. The wording is the same as in Lemma 3.3 but this is a separate occurrence.
Second check: none (judge only)
Report a problem with this finding
Typo Duplicated word in Section 6.1: "well separated Gaussians with the the true centers".
- p. 6 Section 6.1, Norm25 description
with the the true centers
- p. 6 6.1 Datasets, Norm25
Gaussians with the the true
- p. 6
well separated Gaussians with the the true centers provid
Judge's note: Seen on the p6 page image, right column, in the Norm25 description.
Second check: code check