Does k-means++ Seeding Matter After Lloyd's Algorithm? Exact One-Cluster Identities, a Monotone-Descent Proof and a Test of the Arthur–Vassilvitskii Guarantee on Three Real Data Sets

k-means++ chooses initial cluster centres with probability proportional to squared distance and carries a proven expected approximation factor of 8(ln k + 2). I prove the exact identities behind this guarantee in the one-cluster case (the expected cost of a uniformly chosen data point as centre is exactly twice the optimum) and the monotone descent of Lloyd's algorithm, and verify both to machine precision on the UCI Combined Cycle Power Plant data. I then compare uniform and k-means++ seeding, each with and without Lloyd iterations, in 20 runs for each of k = 5, 10, 25 and 50 on three UCI data sets (MAGIC, 19,020 points; CCPP, 9,568 points; Spambase, 4,601 points). Seeds alone cost 1.49 to 2.00 times the best solution found, far inside the guarantee of 28.9 to 47.3. k-means++ seeds are better in seven of the eight MAGIC and CCPP cells (for example 1.551 against 1.804 on MAGIC at k = 50), but not on Spambase. After Lloyd's algorithm the two methods end within 1.00 to 1.04 of the best solution on average, and the advantage of k-means++ survives clearly only on MAGIC at large k (1.0084 against 1.0331 at k = 50), where it also cuts the iterations by about a third.