Complete power-mean agglomerative-linkage hierarchy
DefinitionAggCG_Supplement_linkageHierarchyalgorithm-configurationcomputational-complexitymachine-learningoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1
For disjoint nonempty clusters , the power-mean linkage is the power mean of all cross-distances, with geometric, minimum, and maximum linkage at . Starting from singletons, the algorithm repeatedly merges a pair of clusters of minimum linkage, using a fixed deterministic tie rule.
The complete hierarchy records every partition in this merge sequence; its penultimate partition is the root split.
Definition code
import Mathlib
namespace AggCG.Supplement
open Finset
/-- The power-mean linkage distance `D_α(U, V)` between two clusters of points of `Fin n` under the
distances `δ` (Sharma, *Computational Complexity of Data-Driven Configuration for Integer Programming,
Clustering, and Learning Algorithms*, STOC 2027 submission (manuscript sha256 f7ea0248…), eq. (27),
p.70, PDF p.71):
`D_α(U,V) = ((|U||V|)⁻¹ Σ_{u∈U, v∈V} δ(u,v)^α)^{1/α}` for real `α ≠ 0`, the geometric mean at `α = 0`,
the minimum at `α = −∞` and the maximum at `α = +∞`.
**Formalization Note** `α : EReal` is the exponent line `ℝ ∪ {±∞}`. The value on an empty pair of
clusters is `0`; the linkage run only compares disjoint nonempty clusters. Distances are positive off the
diagonal in every use, so `Real.rpow` and `Real.log` are applied to positive numbers. -/
noncomputable def powerMeanDist {n : ℕ} (δ : Fin n → Fin n → ℝ) (α : EReal)
(U V : Finset (Fin n)) : ℝ :=
if h : (U ×ˢ V).Nonempty then
if α = ⊤ then (U ×ˢ V).sup' h (fun p => δ p.1 p.2)
else if α = ⊥ then (U ×ˢ V).inf' h (fun p => δ p.1 p.2)
else if α.toReal = 0 then
Real.exp ((∑ p ∈ U ×ˢ V, Real.log (δ p.1 p.2)) / ((U.card : ℝ) * V.card))
else ((∑ p ∈ U ×ˢ V, δ p.1 p.2 ^ α.toReal) / ((U.card : ℝ) * V.card)) ^ (1 / α.toReal)
else 0
/-- A fixed deterministic tie rule (p.70: "with any fixed deterministic tie-breaking"): given the number
of points, the current partition into clusters and the set of tied minimum ordered pairs of distinct
current clusters, it returns one of the tied pairs.
**Formalization Note** The rule may depend on the whole current partition and on the tied set, not on the
exponent or on the distances. Pairs are ordered; both orders of a tied pair are in the tied set, and
merging `(U, V)` or `(V, U)` gives the same partition. -/
structure TieRule where
/-- The pair chosen among the tied candidates. -/
pick : (n : ℕ) → Finset (Finset (Fin n)) → Finset (Finset (Fin n) × Finset (Fin n)) →
Finset (Fin n) × Finset (Fin n)
/-- The chosen pair is one of the tied candidates. -/
pick_mem : ∀ n P S, S.Nonempty → pick n P S ∈ S
open Classical in
/-- One step of unmodified agglomerative power-mean linkage (p.70: "At each step, unmodified
agglomerative linkage merges the pair of clusters with smallest `D_α`, with any fixed deterministic
tie-breaking"): among ordered pairs of distinct current clusters, take those of smallest `D_α`, let the
tie rule pick one, and merge it. A partition with fewer than two clusters is left unchanged. -/
noncomputable def linkageStep (tie : TieRule) {n : ℕ} (δ : Fin n → Fin n → ℝ) (α : EReal)
(P : Finset (Finset (Fin n))) : Finset (Finset (Fin n)) :=
let pairs := (P ×ˢ P).filter (fun q => q.1 ≠ q.2)
if h : pairs.Nonempty then
let m := pairs.inf' h (fun q => powerMeanDist δ α q.1 q.2)
let tied := pairs.filter (fun q => powerMeanDist δ α q.1 q.2 = m)
let q := tie.pick n P tied
insert (q.1 ∪ q.2) ((P.erase q.1).erase q.2)
else P
/-- The **complete power-mean linkage hierarchy** (Theorem 3.3, p.4, PDF p.5; §M, p.70): the sequence of
partitions `P_0, P_1, …, P_{n−1}` of the run started from singletons, `P_k` being the partition after
`k` merges. Two hierarchies are equal exactly when every merge of the run agrees. -/
noncomputable def linkageHierarchy (tie : TieRule) {n : ℕ} (δ : Fin n → Fin n → ℝ) (α : EReal) :
Fin n → Finset (Finset (Fin n)) :=
fun k => (linkageStep tie δ α)^[k.val] (Finset.univ.image fun i => ({i} : Finset (Fin n)))
/-- The root split of the run: the partition after `n − 2` merges, i.e. the two children of the last
merge when `n ≥ 2` (p.70: "a specified root bipartition `L | R`"). -/
noncomputable def rootSplit (tie : TieRule) {n : ℕ} (δ : Fin n → Fin n → ℝ) (α : EReal) :
Finset (Finset (Fin n)) :=
(linkageStep tie δ α)^[n - 2] (Finset.univ.image fun i => ({i} : Finset (Fin n)))
/-- The symmetric distance table generated by primitive unordered-pair distances `D_{ij}`, `i < j`
(Theorem 3.3: "its primitive unordered-pair distances"), with `0` on the diagonal. -/
def symDist {n : ℕ} (D : {p : Fin n × Fin n // p.1 < p.2} → ℝ) : Fin n → Fin n → ℝ :=
fun i j => if h : i < j then D ⟨(i, j), h⟩ else if h' : j < i then D ⟨(j, i), h'⟩ else 0
end AggCG.Supplement
Source
Sharma, STOC 2027 submission (manuscript sha256 f7ea0248…), eq. (27) and §M, p.70, PDF p.71; Theorem 3.3, p.4, PDF p.5