Merge-and-split k-means heuristics escape Lloyd's local optima, shows Nielsen & Nock

FrnkNlsn · x · 2026-11-05

In arXiv:1406.6314, Frank Nielsen and Richard Nock tackle the NP-hard optimal k-means clustering problem with new heuristics:

• They extend Lloyd's batched relocation and Hartigan's single-point relocation heuristics to handle empty-cluster and single-point-cluster events, which grow more frequent as k, dimension, or restarts increase — and show these events are a blessing, allowing partial re-seeding while further minimizing the objective.
• They propose merge-and-split k-means: merge two clusters, re-split with two new centers if it improves the objective, beating Hartigan's de facto standard heuristic empirically after it converges to a local minimum.
• The paper also proves Lloyd's k-means can have exponentially many stable local minima (Ω(2^2k)) and introduces the (k,l)-means objective, where points associate to their l closest centers, convertible to k-means to reach better local minima.

Original post →

More from Research

• DialFork: first benchmark targeting procedural hallucination in LLM agents, from Idiap — sergbur · 2026-11-05
• Max Planck paper: reasoning makes LLMs agree more — even on shared mistakes — rohanpaul_ai · 2026-11-05
• Qwen3.5-0.8B 'weight-space programming' finetune trends on Hugging Face — RikiyaT · 2026-11-05
• Emergent misalignment published in Nature: narrow finetuning causes broad LLM misalignment — davidmanheim · 2026-11-05
• FineWeb-30M speedrun record falls to 14.2s on one 8xH100 node, a 1.64x speedup — RobertTLange · 2026-11-05
• Trajectory's Ronak Malde on continual learning: Harvey trained 6x cheaper than frontier — Training Data (Sequoia) · 2026-11-05

Research channel →