Discerning Linkage-Based Algorithms among Hierarchical Clustering Methods

1 Introduction

Clustering is a fundamental and immensely useful task, with many important applications. There are many clustering algorithms, and these algorithms often produce different results on the same data. Faced with a concrete clustering task, a user needs to choose an appropriate algorithm. Currently, such decisions are often made in a very ad hoc, if not completely random, manner. Users are aware of the costs involved in employing different clustering algorithms, such as running times, memory requirements, and software purchasing costs.

However, there is very little understanding of the differences in the outcomes that these algorithms may produce.

Recently, a new approach for selecting a clustering algorithm has been proposed [2]. The approach involves identifying significant properties that distinguish between different clustering paradigms. By focusing on the input-output behaviour of algorithms, these properties shed light on essential differences between them. Users could then choose desirable properties based on domain expertise, and select an algorithm that satisfies these properties.

The study of properties of clustering algorithms has so far been focused on partitional algorithms ([2], [1], [3], [4]). Partitional algorithms produce a single partition of the data.

In this paper, we study the other prominent class of clustering algorithms, namely hierarchical algorithms. These algorithms output dendrograms, which the user can then traverse to obtain the desired clustering. Dendrograms provide a convenient method for exploring multiple clusterings of the data. Notably, for some applications the dendrogram itself, not any clustering found in it, is the desired final outcome. One such application is found in the field of phylogeny, which aims to reconstruct the tree of life.

One popular class of hierarchical algorithms is linkagebased algorithms. These algorithms start with singleton clusters, and repeatedly merge pairs of clusters until a dendrogram is formed. This class includes commonly-used algorithms such as single-linkage, average-linkage, completelinkage, and Ward's method.

In this paper, we provide a property-based characterization of hierarchical linkage-based algorithms. We identify two properties of hierarchical algorithms that are satisfied by all linkage-based algorithms, and prove that at the same time no algorithm that is not linkage-based can satisfy both of these properties.

The popularity of linkage-based algorithms lead to a common misconception that linkage-based algorithms are synonymous with hierarchical algorithms. We show that even when the internal workings of algorithms are ignored, and the focus is placed solely on their input-output behaviour, there are natural hierarchical algorithms that are not linkagebased. We define a large class of divisive algorithms that includes the popular bisecting k-means algorithm, and show that no linkage-based algorithm can simulate the input-output behaviour of any algorithm in this class.

2 Previous Work

There is some previous work on distinguishing linkage-based algorithms based on their properties in the partitional setting. The k-stopping criterion is used to formulate linkagebased algorithms in the partitional setting, where instead of constructing a dendrogram, clusters are merged until a given number of clusters is formed. Ben-David and Bogah-Zedah [3] provide three properties that uniquely identify singlelinkage with the k-stopping criterion. More recently, Ackerman, Ben-David and Loker [1] characterize linkage-based algorithms with this stopping criterion in terms of three natural properties. These results enable a comparison of the inputoutput behaviour of (a partitional variant of) linkage-based algorithms with other partitional algorithms.

In this paper, we characterize hierarchical linkage-based algorithms, which map data sets to dendrograms. Our characterization is independent of any stopping criterion. It enables the comparison of linkage-based algorithms to other hierarchical algorithms, and clearly delineates the differences between the input/output behaviour of linkage-based algorithms from all other hierarchical algorithms.

3 Definitions

A distance function is a symmetric function d : X ×X → R+, such that d(x, x) = 0 for all x ∈ X. The data sets that we consider are pairs (X, d), where X is some finite domain set and d is a distance function over X. We say that a distance function d over X extends distance function d′ over X′ ⊆ X if d′ ⊆ d.

A k-clustering C = {C1,C2, . . . ,Ck} of a data set X is a partition of X into k non-empty disjoint subsets of X (so, ∪iCi = X). A clustering of X is a k-clustering of X for some 1 ⩽ k ⩽ |X|. For a clustering C, let |C| denote the number of clusters in C. For x, y ∈ X and clustering C of X, we write x ∼C y if x and y belong to the same cluster in C and x ̸∼C y, otherwise.

Given a rooted tree T where the edges are oriented away from the root, let V (T) denote the set of vertices in T, and E(T ) denote the set of edges in T . We use the standard interpretation of the terms leaf, descendent, parent, and child.

A dendrogram over a data set X is a binary rooted tree where the leaves correspond to elements of X. In addition, every node is assigned a level, using a level function (η); leaves are placed at level 0, parents have higher levels than their children, and no level is empty. This definition represents the common graphical depiction of a dendrogram. Formally,

Definition 1 (dendrogram). A dendrogram over (X, d) is a triple (T,M, η) where T is a binary rooted tree, M : leaves(T) → X is a bijection, and η : V (T) → {0, . . . , h} is onto (for some h ∈ Z+ ∪ {0}) such that

1. For every leaf node x ∈ V (T), η(x) = 0.
2. If (x, y) ∈ E(T), then η(x) > η(y).

Given a dendrogram D = (T,M, η) of X, we define a mapping from nodes to clusters C : V (T) → 2X by C(x) = {M(y) | y is a leaf and a descendent of x}. If C(x) = A, then we write v(A) = x. We think of v(A) as the vertex (or node) in the tree that represents cluster A.

We say that A ⊆ X is a cluster in D if there exists a node x ∈ V (T) so that C(x) = A. We say that a clustering C = {C1, . . . ,Ck} of X′ ⊆ X is in D if Ci is in D for all 1 ⩽ i ⩽ k. Note that a dendrogram may contain clusterings that do not partition the entire domain, and ∀i ̸= j, v(Ci) is not a descendent of v(Cj), since Ci ∩ Cj = ∅.

Definition 2 (sub-dendrogram). A sub-dendrogram of (T,M, η) rooted at x ∈ V (T) is a dendrogram (T ′ ,M ′ , η′ ) where

1. T ′ is the subtree of T rooted at x
2. For every y ∈ leaves(T ′ ), M ′ (y) = M(y).
3. For all y, z ∈ V (T ′ ), η′ (y) < η′ (z) if and only if η(y) < η(z).

Definition 3 (Isomorphisms). A few notions of isomorphisms of structures are relevant to our discussion.

1. We say that (X, d) and (X′ , d′ ) are isomorphic domains, denoted (X, d) ∼=X (X′ , d′ ), if there exists a bijection φ : X → X′ so that d(x, y) = d′ (φ(x), φ(y)) for all x, y ∈ X.
2. We say that two clusterings (or partitions) C of some domain (X, d) and C ′ of some domain (X′ , d′ ) are isomorphic clusterings, denoted (C, d) ∼=C (C ′ , d′ ), if there exists a domain isomorphism φ : X → X′ so that x ∼C y if and only if φ(x) ∼C′ φ(y).
3. We say that (T1, η1) and (T2, η2) are isomorphic trees, denoted (T1, η1) ∼=T (T1, η1), if there exists a bijection H : V (T1) → V (T2) so that
4. (a) for all x, y ∈ V (T1), (x, y) ∈ E(T1) if and only if (H(x), H(y)) ∈ E(T2), and
5. (b) for all x ∈ V (T1), η1(x) = η2(H(x)).
6. We say that D1 = (T1,M1, η1) of (X, d) and D2 = (T2,M2, η2) of (X′ , d′ ) are isomorphic dendrograms, denoted D1 ∼=D D2, if there exists a domain isomorphism φ : X → X′ and a tree isomorphism H : (T1, η1) → (T2, η2) so that for all x ∈ leaves(T1), φ(M1(x)) = M2(H(x)).

4 Hierarchical and Linkage-Based Algorithms

Hierarchical algorithms are those that output dendrograms, while linkage-based algorithms are hierarchical algorithms that can be simulated by repeatedly merging close clusters. In this section, we formally define these two types of algorithms.

4.1 Hierarchical algorithms

In addition to outputing a dendrogram, we require that hierarchical clustering functions satisfy a few natural properties.

Definition 4 (Hierarchical clustering function). A hierarchical clustering function F is a function that takes as input a pair (X, d) and outputs a dendrogram (T,M, η). We require such a function, F, to satisfy the following:

1. Representation Independence: Whenever (X, d) ∼=X (X′ , d′ ), then F(X, d) ∼=D F(X′ , d′ ).
2. Scale Invariance: For any domain set X and any pair of distance functions d, d′ over X, if there exists c ∈ R+ such that d(a, b) = c · d′ (a, b) for all a, b ∈ X, then F (X, d) = F (X, d′ ).
3. Richness: For all data sets {(X1, d1), . . . (Xk, dk)} where Xi ∩ Xj = ∅ for all i ̸= j, there exists a distance function ˆ d over ⋃ki=1 Xi that extends each of the di's (for i ⩽ k), so that the clustering {C1, . . . ,Ck} is in F (⋃ki=1 Xi, ˆ d).

The last condition, richness, requires that by manipulating between-cluster distances every clustering can be produced by the algorithm. Intuitively, if we place clusters sufficiently far apart, then the resulting clustering should be in the dendrogram.

In this work we focus on distinguishing linkage-based algorithms from among hierarchical algorithms.

4.2 Linkage-based algorithms

The class of linkage-base algorithms includes some of the most popular hierarchical algorithms, such as single-linkage, average-linkage, complete-linkage, and Ward's method.

Every linkage-based algorithm has a linkage function that can be used to determine which clusters to merge at every step of the algorithm.

Definition 5 (Linkage function). A linkage function is a function

such that,

1. ℓ is representation independent: For all (X1,X2) and (X′1 ,X′2 ), if ({X1,X2}, d) ∼=C ({X′1 ,X′2 }, d′ ) then ℓ(X1, X2, d) = ℓ(X′1 , X′2 , d′ ).
2. ℓ is monotonic: For all (X1,X2, d) if d′ is a distance function over X1 ∪X2 such that for all x ∼{X1,X2} y, d(x, y) = d′ (x, y) and for all x ̸∼{X1,X2} y, d(x, y) ⩽ d′ (x, y) then ℓ(X1, X2, d′ ) ⩾ ℓ(X1, X2, d).

For technical reasons, we shall assume that a linkage function has a countable range. Say, the set of non-negative algebraic real numbers 1 .

For example, the single-linkage linkage function is ℓSL(A, B, d) = mina∈A,b∈B d(a, b) and the average-linkage linkage function is ℓAL(A, B, d) = ∑a∈A,b∈B d(a,b) |A|·|B| .

For a dendrogram D and clusters A and B in D, if parent(v(A)) = parent(v(B)) = x, then let parent(A,B) = x, otherwise parent(A, B) = ∅.

We now define linkage-based functions.

Definition 6 (linkage-based function). A hierarchical clustering function F is linkage-based if there exists a linkage function ℓ so that for all (X, d), F(X, d) = (T,M, η) where

1 Imposing this restriction simplifies our main proof, while not having any meaningful impact on the scope of clusterings considered.

η(parent(A,B)) = m if and only if ℓ(A,B) is minimal in {ℓ(S, T) : S ∩ T = ∅, η(parent(S)) ⩾ m, η(parent(T)) ⩾ m}.

Note that the above definition implies that there exists a linkage function that can be used to simulate the output of F. We start by assigning every element of the domain to a leaf node. We then use the linkage function to identify the closest pair of nodes (wrt the clusters that they represent), and repeatedly merge the closest pairs of nodes that do yet have parents, until only one such node remains.

4.3 Locality

We introduce a new property of hierarchical algorithms. Locality states that if we select a clustering from a dendrogram (a union of clusters that appear in the dendrogram), and run the hierarchical algorithm on the data underlying this clustering, we obtain a result that is consistent with the original dendrogram.

Definition 7 (Locality). A hierarchical function F is local if for all X, d, and X′ ⊆ X, whenever clustering C = {C1,C2, . . . ,Ck} of X′ is in F(X, d) = (T,M, η), then for all 1 ⩽ i ⩽ k

1. Cluster Ci is in F(X′ , d/X′ ) = (T ′ ,M ′ , η′ ), and the sub-dendrogram of F(X, d) rooted at v(Ci) is also a sub-dendrogram of F(X′ , d/X′ ) rooted at v(Ci).
2. For all x, y ∈ X′ , η′ (x) < η′ (y) if and only if η(x) < η(y).

Locality is often a desirable property. Consider for example the field of phylogeny, which aims to reconstruct the tree of life. If an algorithm clusters phylogenetic data correctly, then if we cluster any subset of the data, we should get results that are consistent with the original dendrogram.

4.4 Outer consistency

A basic requirement from a good clustering is that it separate dissimilar elements. Given successfully clustered data, if points that are already assigned to different clusters are drawn even further apart (or become even less similar), then it is natural to expect that, when clustering the resulting new data set, such points will not share the same cluster.

Given a dendrogram produced by a hierarchical algorithm, we select a clustering C from a dendrogram and pull apart the clusters in C (thus making the clustering C more pronounced). If we then run the algorithm on the resulting data, we can expect that the clustering C will occur in the new dendrogram.

Outer consistency is a relaxation of the above property, making this requirement only on a subset of clusterings.

For a cluster A in a dendrogram D, the A-cut of D is a clustering in D represented by nodes on the same level as v(A) or directly below v(A). Formally,

Definition 8 (A-cut). Given a cluster A in a dendrogram D = (T,M, η), the A-cut of D is cutA(D) = {C(u) | u ∈ V (T ), η(parent(u)) > η(v(A)) and η(u) ⩽ η(v(A)).}.

Note that for any cluster A in D of (X, d), the A-cut is a clustering of X, and A is one of the clusters in that clustering.

A distance function d′ over X is (C, d)-outer consistent if d′ (x, y) = d(x, y) whenever x ∼C y, and d′ (x, y) ⩾ d(x, y) whenever x ̸∼C y.

Definition 9 (Outer-Consistency). A hierarchical function F is outer-consistent if for all (X, d) and any cluster A in F(X, d), if d′ is a (cutA(F(X, d)), d)-outer-consistent variant then cutA(F(X, d)) = cutA(F(X, d′ )).

5 Main result

The following is our characterization of linkage-based hierarchical algorithms.

Theorem 1. A hierarchical function F is linkage-based if and only if F is outer-consistent and local.

The proof comprises the rest of this section.

Proof. We begin by showing that every local, outerconsistent hierarchical function F is linkage-based. To prove this direction, we show that there exists a linkage function ℓ so that when ℓ is used in Definition 6 then for all (X, d) the output is F(X, d). Due to the representation independence of F, one can assume w.l.o.g., that the domain sets over which F is defined are (finite) subsets of the set of natural numbers, N.

Definition 10 (The (pseudo-) partial ordering <F ). We consider triples of the form (A,B, d), where A ∩ B = ∅ and d is a distance function over A ∪ B. Two triples, (A,B, d) and (A′ ,B′ , d′ ) are equivalent, denoted (A, B, d) ∼= (A′ , B′ , d′ ) if they are isomorphic as clusterings, namely, if ({A,B}, d) ∼=C ({A′ ,B′ }, d′ ).

<F is a binary relation over equivalence classes of such triples, indicating that F merges a pair of clusters earlier than another pair of clusters. Formally, denoting ∼=- equivalence classes by square brackets, we define it by: [(A,B, d)] <F [(A′ ,B′ , d′ )] if there exists a distance function d∗ over X = A ∪ B ∪ A′ ∪ B′ so that F(X, d∗ ) = (T,M, η) such that

1. d∗ extends both d and d′ (namely, d ⊆ d∗ and d′ ⊆ d∗ ),
2. There exist (x, y), (x, z) ∈ E(T) such that C(x) = A ∪ B, C(y) = A, and C(z) = B
3. For all D ∈ {A′ ,B′ }, either D ⊆ A ∪ B, or D ∈ cutA∪BF (X, d∗ ).
4. η(v(A′ )) < η(v(A∪B)) and η(v(B′ )) < η(v(A∪B)).

For the sake of simplifying notation, we will omit the square brackets in the following discussion.

In the following lemma we show that if (A,B, d) <F (A′ , B′ , d′ ), then A∪B cannot have a lower level than A′∪B′ .

Lemma 1. Given a local and outer-consistent hierarchial function F, whenever (A,B, d) <F (A′ ,B′ , d′ ), then there is no data set (X, d) so that η(v(A′ ∪ B′ ) ⩽ η(v(A ∪ B)), where F (X, d) = (T, M, η).

Proof. By way of contradiction, assume that such (X, d) exists. Let X′ = A ∪ B ∪ A′ ∪ B′ . Since (A,B, d) <F (A′ , B′ , d′ ), there exists d′ that satisfies the conditions of Definition 10.

Consider F(X′ , d/X′ ). By locality, the sub-dendrogram rooted at v(A ∪ B) contains the same nodes in both F(X′ , d/X′ ) and F(X, d), and similarly for the subdendrogram rooted at v(A′ ∪ B′ ). In addition, the relative level of nodes in these subtrees is the same.

By pushing A away from B, and A′ away from B′ it is easy to see that there exists a d∗ over X′ that is both an ({A ∪ B,A′ ∪ B′ }, d/X′ )-outer consistent variant and an ({A∪B, A′ , B′ }, d′ )-outer consistent variant. Note that {A∪ B, A′ ∪B′ } is an (A∪B)-cut of F(X′ , d/X′ ). Therefore, by outer-consistency, cutA∪B(F (X′ , d∗ )) = {A′ ∪ B′ , A ∪ B}.

Since d′ satisfies the conditions in Definition 10, cutA∪BF(X, d′ ) = {A ∪ B, A′ , B′ }. By outer-consistency we get that cutA∪B(F(X′ , d∗ )) = {A′ ∪ B′ ,A,B}. Since these sets are all non-empty, this is a contradiction.

We now define equivalence with respect to <F .

Definition 11 (∼=F ). [(A,B, d)] and [(A′ ,B′ , d′ )] are Fequivalent, denoted [(A,B, d)] ∼=F [(A′ ,B′ , d′ )], if there exists a distance function d∗ over X = A∪B ∪A′ ∪B′ so that F (A ∪ B ∪ A′ ∪ B′ , d∗ ) = (T, η) where

1. d∗ extends both d and d′ ,
2. There exist (x, y), (x, z) ∈ E(T) such that C(x) = A ∪ B, and C(y) = A, and C(z) = B,
3. There exist (x′ , y′ ), (x′ , z′ ) ∈ E(T) such that C(x′ ) = A′ ∪ B′ , and C(y′ ) = A′ , and C(z′ ) = B′ , and
4. η(x) = η(x′ )

(A,B, d) is comparable with (C,D, d′ ) if they are <F comparable or (A, B, d) ∼=F (C, D, d′ ).

Whenever two triple are F-equivalent, then they have the same <F or ∼=F relationship with all other triples.

Lemma 2. Given a local, outer-consistent hierarchical function F, if (A,B, d1) ∼=F (C,D, d2), then for any (E, F, d3), if (E, F, d3) is comparable with both (A,B, d1) and (C,D, d2) then

• if (A,B, d1) ∼=F (E, F, d3) then (C,D, d2) ∼=F (E, F, d3)
• if (A,B, d1) <F (E, F, d3) then (C,D, d2) <F (E, F, d3)

The proof is omitted to save space.

Note that <F is not transitive. To show that <F can be extended to a partial ordering, we first prove the following "anti-cycle" property.

Lemma 3. Given a hierarchical function F that is local and outer-consistent, there exists no finite sequence (A1,B1, d1) <F · · · <F (An,Bn, dn) <F (A1,B1, d1).

Proof. Without loss of generality, assume that such a sequence exists. By richness, there exists a distance function d that extends each of the di where {A1∪B1, A1∪B2, . . . , An∪ Bn} is a clustering in F(⋃i Ai ∪ Bi, d) = (T,M, η).

Let i0 be so that η(v(Ai0 ∪Bi0 ) ⩽ η(v(Aj ∪Bj)) for all j ̸= i0. By the circular structure with respect to <F , there exists j0 so that (Aj0 ,Bj0 , dj0 ) <F (Ai0 ,Bi0 , di0 ). This contradicts Lemma 1.

The following is a well-known result.

Lemma 4. For any cycle-free, anti-symmetric relation P( , ) over a finite or countable domain D there exists an embedding h into R+ so that for all x, y ∈ D, if P(x, y) then h(x) < h(y).

Finally, we define our linkage function by embedding the ∼=F -equivalence classes into the positive real numbers in an order preserving way, as implied by applying Lemma 4 to <F . Namely, ℓF : {[(A,B, d)] : A ⊆ N,B ⊆ N,A ∩ B = ∅ and d is a distance function over A ∪ B} → R+ so that [(A,B, d)] <F [(A′ ,B′ , d′ )] implies ℓF [(A,B, d)] < ℓF [(A, B, d)].

Lemma 5. The function ℓF is a linkage function for any hierarchical function F that satisfies locality and outerconsistency.

Proof. Since ℓF is defined on ∼=F -equivalence classes, representation independence of hierarchical functions implies that ℓF satisfies condition 1 of Definition 5. The function ℓF satisfies condition 2 of Definition 5 by lemma 6.

Lemma 6. Consider d1 over X1 ∪ X2 and d2 an ({X1,X2}, d1)-outer-consistent variant, then (X1,X2, d2) ̸<F (X1,X2, d1), whenever F is local and outer-consistent.

Proof. Assume that there exist such d1 and d2 where (X1, X2, d2) <F (X1, X2, d1). Let d3 over X1∪X2 be a distance function that is both an ({X1, X2}, d1)-outer-consistent variant and d2 an ({X1, X2}, d3)-outer-consistent variant.

Let X = X1∪X2∪X′1 ∪X′2 ∪X′′ 1 ∪X′′ 2 . By richness, there exists a distance function d∗ that extends di for all 1 ⩽ i ⩽ 3 so that {X1 ∪ X2,X′1 ∪ X′2 ,X′′ 1 ∪ X′′ 2 } is a clustering in F (X, d∗ ) = (T, η).

Now, (X′1 ,X′2 , d2) <F (X1,X2, d1), by locality and outer-consistency, we get that η(v(X′1 ∪ X′2 )) < η(v(X1 ∪ X2)). We consider the level (η value) of v(X′′ 1 ∪ X′′ 2 ) with respect to the levels of v(X′1 ∪X′2 ) and v(X1 ∪X2).

The proof proceeds by analyzing the following three cases: η(v(X′′ 1 ∪ X′′ 2 )) ⩽ η(v(X′1 ∪ X′2 )), η(v(X′′ 1 ∪ X′′ 2 )) ⩾ η(v(X1 ∪ X2)) and η(X1 ∪ X2) < η(X′′ 1 ∪X′′ 2 ) < η(X′1 ∪ X′2 ). The details of these cases are omitted for brevity.

The following Lemma concludes the proof that every local, out-consistent hierarchical algorithm is linkage-based.

Lemma 7. Given any hierarchical function F that satisfies locality and outer-consistency, let ℓF be the linkage function defined above. Let LℓF denote the linkage-based algorithm that ℓF defines. Then LℓF agrees with F on every input data set.

Proof. Let (X, d) be any data set. We prove that at every level s, the nodes at level s in F(X, d) represent the same clusters as the nodes at level s in LℓF (X, d). In both F(X, d) =

(T,M, η) and LℓF (X, d) = (T ′ ,M ′ , η′ ), level 0 consists of |X| nodes each representing a unique elements of X.

Assume the result holds below level k. We show that pairs of nodes that do not have parents below level k have minimal ℓF value only if they are merged at level k in F(X, d).

Consider F(X, d) at level k. Since the dendrogram has no empty levels, let x ∈ V (T ) where η(x) = k. Let x1 and x2 be the children of x in F(X, d). Since η(x1), η(x2) < k, these nodes also appear in LℓF (X, d) below level k, and neither node has a parent below level k.

If x is the only node in F(X, d) above level k - 1, then it must also occur in LℓF (X, d). Otherwise, there exists a node y1 ∈ V (T), y1 ̸∈ {x1, x2} so that η(y1) < k and η(parent(y1)) ⩾ k. Let X′ = C(x) ∪ C(y1). By locality, cutC(x)F(X′ , d/X′ ) = {C(x), C(y1)}, y1 is below x, and x1 and x2 are the children of x. Therefore, (x1, x2, d) <F (x1, y1, d) and ℓF (x1, x2, d) < ℓF (x1, y1, d). Similarly, ℓF (x1, x2, d) < ℓF (x2, y1, d)

Assume that there exists y2 ∈ V (T), y2 ̸∈ {x1, x2, y1} so that η(y2) < k and η(parent(y2)) ⩾ k. If parent(y1) = parent(y2) and η(parent(y1)) = k, then (x1, x2, d) ∼=F (y1, y2, d) and so ℓF (x1, x2, d) = ℓF (y1, y2, d).

Otherwise, let X′ = C(x) ∪ C(y1) ∪ C(y2). By richness, there exists a distance function d∗ that extends d/C(x) and d/(C(y1) ∪ C(y1)), so that {C(x), C(y1) ∪ C(y2)} is in F(X′ , d∗ ). Note that by locality, the node v(C(y1) ∪ C(y2)) has children v(C(y1)) and v(C(y2)) in F(X′ , d∗ ). We can separate C(x) from C(y1) ∪ C(y2) in both F(X′ , d∗ ) and F (X′ , d/X′ ) until both are equal. Then by outer-consistency, cutC(x)F(X′ , d/X′ ) = {C(x), C(y1), C(y2)} and by locality y1 and y2 are below x. Therefore, (x1, x2, d) <F (y1, y2, d) and so ℓF (x1, x2) < ℓF (y1, y2).

The other direction of the proof is straight forward, and so the proof of the following Lemma is omitted to save space.

Lemma 8. Every linkage-based hierarchical clustering function satisfies locality and outer-consistency.

6 Divisive algorithms

Our formalism provides a precise sense in which linkagebased algorithms make only local considerations, while many divisive algorithms inevitably take more global considerations into account. This fundamental distinction between these paradigms can be used to help select a suitable hierarchical algorithm for specific applications.

This distinction also implies that divisive algorithms cannot be simulated by any linkage-based algorithm, showing that the class of hierarchical algorithms is strictly richer than the class of linkage-based algorithm (even when focusing only on the input-output behaviour of algorithms).

A 2-clustering function F maps a data set (X, d) to a 2partition of X. An F-Divisive algorithm is a divisive algorithm that uses a 2-clustering function F to decide how to split nodes. Formally,

Definition 12 (F-Divisive). A hierarchical clustering function is F-Divisive wrt a 2-clustering function F, if for all (X, d), F(X, d) = (T,M, η) such that for all x ∈ V (T)/leaves(T) with children x1 and x2, F(C(x)) = {C(x1), C(x2)}.

Note that Definition 12 does not place restrictions on the level function. This allows for some flexibility in the levels. Intuitively, it doesn't force an order on splitting nodes.

The following property represents clustering functions that utilize contextual information found in the remainder of the data set when partitioning a subset of the domain.

Definition 13 (Context sensitive). F is context-sensitive if there exist distance functions d ⊂ d′ such that F({x, y, z}, d) = {{x}, {y, z}} and F({x, y, z, w}, d′ ) = {{x, y}, {z, w}}.

Many 2-clustering functions, including k-means, min-sum, and min-diameter are context-sensitive (see Corollary 2). Natural divisive algorithms, such as bisecting k-means (kmeans-Divisive), rely on context-sensitive 2-clustering functions.

Whenever a 2-clustering algorithm is context-sensitive, then the F-divisive function is not local.

Theorem 2. If F is context-sensitive then the F-divisive function is not local.

Proof. Since F is context-sensitive, there exists a distance functions d ⊂ d′ so that {x} and {y, z} are the children of the root in F({x, y, z}, d), while in F({x, y, z,w}, d′ ), {x, y} and {z,w} are the children of the root and z and w are the children of {z,w}. Therefore, {{x, y}, {z}} is clustering in F({x, y, z, w}, d′ ). Then {{x, y}, {z}} is a clustering in F-divisive({x, y, z}, d). But cluster {x, y} is not in F({x, y, z}, d) , therefore F-divisive is not local.

Applying Theorem 1, we get:

Corollary 1. If F is context-sensitive, then the F-divisive function is not linkage-based.

We say that two hierarchical algorithms strongly disagree if they may output dendrograms with different clusterings. Formally,

Definition 14. Two hierarchical functions F0 and F1 strongly disagree if there exists a data set (X, d) and a clustering C of X so that C is in Fi(X, d) but not in F1-i(X, d), for some i ∈ {0, 1}.

Theorem 3. If F is context-sensitive, then the F-divisive function strongly disagrees with every linkage-based function.

Proof. Let L be any linkage-based function. Since F is context-sensitive, there exists distance functions d ⊂ d′ so that F({x, y, z}, d) = {{x}, {y, z}} and F({x, y, z, w}, d′ ) = {{x, y}, {z, w}}.

Assume that L and F-divisive produce the same output on ({x, y, z,w}, d′ ). Therefore, since {{x, y}, {z}} is a clustering in F-divisive({x, y, z,w}, d′ ), it is also a clustering in L({x, y, z,w}, d′ ). Since L is linkage-based, by Theorem 1, L is local. Therefore, {{x, y}, {z}} is a clustering in L({x, y, z}, d′ ). But it is not a clustering in F-divisive({x, y, z}, d).

Corollary 2. The divisive algorithms that are based on the following 2-clustering functions strongly disagree with every linkage-based function: k-means, min-sum, min-diameter.

Proof. Set x = 1, y = 3, z = 4, and w = 6 to show that these 2-clustering functions are context-sensitive. The result follows by Theorem 3.