An Axiomatic Definition of Hierarchical Clustering

1 Introduction

• Population-level clustering is needed because statistical inference evaluates sample clusterings against an underlying population and asks whether observed clusters are real.Source: §1 · p. 1
• No generally accepted definition of clustering exists at the population level.Source: §1 · p. 1
• Mixture-based clustering can require many components or produce multiple clusters for a unimodal mixture, while gradient-flow clustering requires smoothness assumptions and excludes arbitrarily flat densities.Source: §1 · p. 2
• Hartigan’s population cluster tree uses maximally connected components of density upper level sets and is compatible with Fukunaga and Hostetler’s definition.Source: §1 · p. 2
• The paper develops an axiomatic population hierarchical clustering and recovers Hartigan’s definition for connected-support densities and finitely many suitable connected components.Source: §1 · p. 2

1.1 Related Work

• Previous axiomatic work includes impossibility results for scale-invariance, richness, and consistency, alongside relaxations and characterizations of single linkage.Source: §1.1 · pp. 2–3

2 Preliminaries

• A hierarchical clustering is a nested collection of connected subsets, while a dendrogram adds a nonincreasing height function to the cluster tree.Source: §2 · p. 4
• Hartigan’s cluster tree consists of the maximally connected components of all positive upper level sets of a function.Source: §2 · p. 4
• Merge height records the level at which two points cease to share a cluster, and merge distortion compares dendrograms through these pairwise heights.Source: §2 · p. 4
• The merge distortion metric is stable under uniform perturbations: the merge-height difference is bounded by the functions’ L∞ distance.Source: §2 · pp. 4–5
• Neighboring sets are defined through mutual neighborhood inclusion, with special conventions for empty sets and contacts occurring only at a point or edge.Source: §2 · p. 5
• The internally connected property distinguishes collections whose connected components are linked through neighboring regions, as illustrated by Figure 2.1.Source: §2 · p. 5, Figure 2.1 · p. 5

3 Axioms

• The paper proposes a population cluster-tree definition for piecewise constant densities and extends it to more general densities, recovering Hartigan’s tree under mild conditions.The initial setting uses piecewise constant functions with connected, bounded support and connected interiors.Source: §3 · p. 6, §3.1 · p. 6

3.1.1 Axiom 1: Clusters have connected interior

• Axiom 1 requires every cluster to have connected interior, excluding disconnected regions even when they might be grouped by methods such as K-means.The condition is stronger than ordinary connectedness and avoids ambiguities about cluster boundaries.Source: §3.1.1 · p. 6, Figure 3.1 · p. 7, Figure 3.2 · p. 7

3.1.2 Axiom 2: Clusters do not partition connected regions of constant density

• Axiom 2 forbids splitting a connected constant-density region into smaller clusters, even when within-cluster distances exceed between-cluster distances.This prevents imposing structure absent from the density and distinguishes the definition from K-means behavior.Source: §3.1.2 · p. 7, Figure 3.3 · p. 8

3.1.3 Axiom 3: Clusters are surrounded by regions of lower density

• Axiom 3 requires a cluster’s minimum density to exceed the maximum density in its neighboring region.Thus, a cluster must be surrounded by lower-density regions.Source: §3.1.3 · p. 8, Figure 3.4 · p. 8

3.2 Finest hierarchical clustering

• For every nonnegative f, there exists a unique finest hierarchical clustering among the cluster trees satisfying the three axioms.The construction collects every cluster satisfying (A1), (A2), and (A3), then proves these clusters form a hierarchical clustering.Source: §3.2 · p. 9

3.3 Comparison with Hartigan’s Cluster Tree

• The finest axiom cluster tree is generally different from Hartigan’s tree because Hartigan clusters need only be connected and may violate Axiom 1.Hartigan’s tree satisfies (A2) and (A3), but not necessarily the connected-interior requirement.Source: §3.3 · pp. 9–10
• For densities whose constituent regions have internally connected unions, the Hartigan tree satisfies all three axioms and is contained in the finest axiom tree.The proof then shows every axiom cluster is also a Hartigan cluster, yielding equality under this condition.Source: §3.3 · p. 9
• Relaxing connected interior to ordinary connectedness and modifying neighborhood definitions would recover Hartigan’s tree, but the paper prefers the original stronger axiom.The authors describe connected interiors as more natural and robust for their setting.Source: §3.3 · p. 10

4 Extension to Continuous Functions

• Under the paper’s conditions, finest axiom cluster trees for piecewise constant approximations converge to the Hartigan cluster tree in merge distortion metric.The extension considers sequences in Fint converging to a continuous function and establishes convergence under suitable conditions.Source: §4 · p. 10

4.1 Functions with connected support

• For continuous functions admitting an axiom cluster tree, Hartigan’s tree is itself axiom-compatible, and every axiom cluster tree has zero merge distortion from it.The result is stated for any continuous function that admits an axiom cluster tree.Source: §4.1 · pp. 10–11
• If the support has connected interior, sufficient conditions ensure uniform approximation by functions in Fint: compact closed bounded sets, internally connected partitions, bounded upper level sets, and connected low-level upper sets.Euclidean spaces satisfy the internally connected partition property, supporting the approximation result in common settings.Source: §4.1 · p. 11

4.2 Functions with Disconnected Support

• For disconnected support decomposed into components, a set is a cluster exactly when it is a cluster of one component, so the finest tree is the union of componentwise finest trees.When the components are continuous, the connected-support result applies componentwise.Source: §4.2 · p. 12
• The disconnected-support result generally produces a forest with one tree per component; grouping components further requires an additional clustering procedure, for which single linkage is suggested as natural.This additional grouping is outside the paper’s definition and raises the usual choice of clustering procedure.Source: §4.2 · p. 12

5.1 Extensions

• The axiomatic definition may extend from continuous to piecewise continuous functions with connected support, but constructing compatible internally connected partitions is technically difficult.Partitions must both approximate each continuous region uniformly and retain the internally connected property when combined.Source: §5.1 · pp. 12–13
• A density with disconnected interior can exhibit clustering structure beyond that occurring separately inside its eight connected components.Source: Figure 4.1 · p. 13

5.2.1 Algorithms

• Most existing clustering methods, including K-means and known agglomerative hierarchical methods, do not necessarily satisfy the proposed axioms asymptotically.Single-linkage is a partial exception, although chaining concerns motivate regularized variants such as DBSCAN and robust single linkage.Source: §5.2.1 · p. 13

5.2.2 Clustering in High Dimensions

• Estimating the Hartigan cluster tree under Hölder smoothness requires sample sizes that grow exponentially with dimension, matching density-estimation minimax behavior.The relevant dimension can instead be intrinsic for densities supported on lower-dimensional manifolds, and additional structure may help avoid the usual curse.Source: §5.2.2 · pp. 13–14

5.3 Axiomatic Definition of Flat Clustering

• The paper uses hierarchical clustering to avoid the unresolved problem of defining the correct number of flat clusters.Source: §5.3 · p. 14
• A flat-clustering definition congruent with the hierarchy would partition the support by gradient-ascent basins, but deriving it axiomatically remains future work.The paper identifies the Fukunaga–Hostetler definition as the closest existing formulation under suitable density regularity.Source: §5.3 · p. 14

• Merge distortion is only a pseudometric on general cluster trees: non-isomorphic trees can have dM(C, C′) = 0.The issue arises when different nested clusters share the same heights and therefore leave all pairwise merge heights unchanged.Source: A Merge Distortion Metric · p. 17
• For an indicator density, every nested collection of subsets forms a cluster tree, and all such trees have zero merge distortion from one another.Source: A Merge Distortion Metric · p. 17
• For a continuous density, removing selected Hartigan clusters and adding suitable cluster trees at distinct levels can preserve dM(C, Hf) = 0.The removal levels must have empty interior, while the added trees lie within connected components of corresponding level sets.Source: A Merge Distortion Metric · pp. 17–18
• Closed cluster trees attain the supremum defining each merge height, enabling structural arguments about clusters realizing pairwise merge levels.Source: A Merge Distortion Metric · p. 18
• Connected components of strict and non-strict upper level sets are either disjoint or nested.Source: A Merge Distortion Metric · pp. 18–19
• For continuous functions with bounded upper level sets, every upper-level component contains a mode; with locally finitely many modes, sufficiently small level perturbations preserve the relevant component structure.The latter property is established under the additional assumption that upper level sets have finitely many components.Source: A Merge Distortion Metric · p. 19
• If a closed cluster tree has zero merge distortion from Hf, it contains Hf; under an additional regularity condition, each of its clusters is assembled from connected components above its height.Source: A Merge Distortion Metric · pp. 19–20
• Even for a continuous unimodal-violating density with connected support, adding one branch at a split level can produce a distinct tree at zero merge distortion.For a two-mode density, either separated region R1 or R2 can be added individually, whereas adding both is not hierarchical because they intersect without being nested.Source: A Merge Distortion Metric · p. 20, Figure A.1 · p. 20

• The proof constructs a shifted grid whose unit cells partition R^d, are locally finite, have connected interiors, and have bounded diameter.The two-dimensional instance is illustrated in Figure B.1.Source: B Euclidean Spaces · p. 21, Figure B.1 · p. 21
• Every Euclidean space has the internally connected partition property.Source: B Euclidean Spaces · p. 21
• The internally connected property is established inductively, reducing the d-dimensional case to adjacent cells whose shared boundary connects the relevant interiors.Source: B Euclidean Spaces · pp. 21–22