AFTD Auto-Formalizing Theoretical Domains

kmeans_plus_plus_two_expected_cost

def

The expected cost E[Phi₂] of two centers chosen by k-means++ on a finite set X is the average over uniformly chosen first center c₁ in X of the expectation of the 2-means cost when the second center c₂ in X is sampled with probability proportional to ||c₂ - c₁||².

Statement

noncomputable def kmeans_plus_plus_two_expected_cost {E : Type*} [NormedAddCommGroup E] (X : Finset E) : ℝ
Defined in
arXiv:2611.14573 Section 2, Algorithm 1
Verified
13 Nov 2026
Axioms
none listed
Built on 2
  • kmeans_cost_oneThe 1-means clustering cost of a finite set of points X in a normed group with respect to a single center c is the sum over x in X of ||x…
  • kmeans_cost_twoThe 2-means clustering cost of a finite set of points X in a normed group with respect to two centers c₁ and c₂ is the sum over x in X of…
Used by 1
  • kmeans_two_competitive_ratiosThe set of 2-means competitive ratios is the collection of all real numbers r for which there exists a dimension d and a finite set X in…

Read back from the Lean

Given a normed additive commutative group E and a finite subset X of E, kmeans_plus_plus_two_expected_cost X is the real number given by the reciprocal of the cardinality of X multiplied by the sum over all c₁ ∈ X of: the reciprocal of kmeans_cost_one X c₁ multiplied by the sum over all c₂ ∈ X of ‖c₂ - c₁‖² * kmeans_cost_two X c₁ c₂.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The expected 2-means cost of the two centers chosen by k-means++ on a finite set X. -/
noncomputable def kmeans_plus_plus_two_expected_cost {E : Type*} [NormedAddCommGroup E] (X : Finset E) : ℝ := (X.card : ℝ)⁻¹ * ∑ c₁ ∈ X, ((kmeans_cost_one X c₁)⁻¹ * ∑ c₂ ∈ X, ‖c₂ - c₁‖^2 * kmeans_cost_two X c₁ c₂)
See it in the graphDiscuss this resultChallenge it