# Functorial Hierarchical Clustering with Overlaps

Jared Culbertson  Sensors Directorate, Air Force Research Laboratory, 2241
Avionics Circle, Building 620 Wright–Patterson Air Force Base, Ohio
45433-7302, USA<EMAIL_ADDRESS>,  Dan P. Guralnik  Electrical &
Systems Engineering Dept., University of Pennsylvania, 200 S. 33rd st., 203
Moore Building, Philadelphia, Pennsylvania 19104-6314, USA.
<EMAIL_ADDRESS>and  Peter F. Stiller  Department of Mathematics,
MS3368, Texas A&M University, College Station, Texas 77843-3368, USA.
<EMAIL_ADDRESS>
###### Abstract.

This work draws inspiration from three important sources of research on
dissimilarity-based clustering and intertwines those three threads into a
consistent principled functorial theory of clustering. Those three are the
overlapping clustering of Jardine and Sibson, the functorial approach of
Carlsson and Mémoli to partition-based clustering, and the Isbell/Dress
school’s study of injective envelopes. Carlsson and Mémoli introduce the idea
of viewing clustering methods as functors from a category of metric spaces to
a category of clusters, with functoriality subsuming many desirable
properties. Our first series of results extends their theory of functorial
clustering schemes to methods that allow overlapping clusters in the spirit of
Jardine and Sibson. This obviates some of the unpleasant effects of chaining
that occur, for example with single-linkage clustering. We prove an
equivalence between these general overlapping clustering functors and
projections of weight spaces to what we term clustering domains, by focusing
on the order structure determined by the morphisms. As a specific application
of this machinery, we are able to prove that there are no functorial
projections to cut metrics, or even to tree metrics. Finally, although we
focus less on the construction of clustering methods (clustering domains)
derived from injective envelopes, we lay out some preliminary results, that
hopefully will give a feel for how the third leg of the stool comes into play.

Keywords: hierarchical clustering, clustering with overlaps, functorial
clustering, clustering domain, injective envelope, non-expansive map, sieving
functor, cut metric, tree metric, A-space

2010 MSC: 62H30, 51K05, 52A01, 18B99

##  1\. Introduction

Problems surrounding data clustering have been studied extensively over the
last forty years. Clustering stands as an important tool for analyzing and
revealing the often hidden structure in data (and in today’s big data) coming
from fields as diverse as biology, psychology, machine learning, sociology,
image understanding, and chemistry. Among the earliest systematic treatments
of clustering theory was that of Jardine and Sibson in 1971 [33]. They laid
out important desiderata for overlapping clustering methods and provided a
relatively efficient algorithm for their so-called $B_{k}$ clustering which
allowed overlapping clusters with no more than $k-1$ points in any overlap.
Since then, there have been several distinct directions of research in
clustering theory, with only modest linkage between the methods of researchers
pursuing different paths.

The classical work of Jardine and Sibson was followed by other similarly
comprehensive works such as Everitt [24]. Further theoretical work on these
mostly classical methods was also done by Kleinberg [34] and Carlsson and
Mémoli [9, 10]. Kleinberg in particular showed the incompatibility of a
relatively simple set of desirable axioms for any partition based clustering
method. Carlsson and Mémoli in turn introduced categorical language into
partition based clustering and showed that single-linkage was (up to a
scaling) the only functorial method satisfying all their axioms (which
included the notions of representability and excisiveness) in the category of
finite metric spaces with non-expansive maps.

In another direction, work on computing phylogenetic trees inspired a seminal
paper by Bandelt and Dress [3] on split decompositions of metrics. This line
of research was continued with investigations into split systems and cut
points of injective envelopes of metric spaces. Representative papers include
[19] and [17]. While not explicitly clustering methods, these methods are
quite similar in spirit to stratified/hierarchical clustering schemes. In this
genre, we might also add the classification of the injective envelopes of six-
point metric spaces by Sturmfels and Yu [40]. Bandelt and Dress have also had
a large influence on another field as a result of their work on weak
hierarchies [2, 4]. This led to work by Diatta, Bertrand, Barthélemy, Brucker,
and others on indexed set systems (see, e.g., [5], [14], [6]). Another
interesting development in this area is the work by Janowitz on ordinal
clustering [32].

Recently, with the emergence of the new field of topological data analysis
(TDA), work has been done on topologically-based clustering methods. This
includes the Mapper algorithm by Singh, Mémoli, and Carlsson [39], as well as
work on persistence-based methods [11] and Reeb graphs [28].

Meanwhile, most users of clustering methods default either to a classical
linkage-based clustering method (such as single-linkage or complete linkage)
or to more geometrically-based methods like $k$-means. Unfortunately, the wide
array of clustering theories has had little impact on the actual practice of
clustering. Simply put, the gap between theory and efficient practice has been
hard to bridge.

In this paper we draw inspiration from three of the sources mentioned above,
and strive to intertwine those three threads into a consistent principled
functorial theory of dissimilarity-based clustering. Those three are the
overlapping clustering of Jardine and Sibson, the functorial approach of
Carlsson and Mémoli, and the Dress school approach to clustering, via
injective envelopes, which were independently discovered by Isbell and Dress.
This paper intends to fuse these approaches. Our starting point is the paper
of Carlsson and Mémoli [10] which introduces the idea of viewing clustering
methods as functors from a category of metric spaces to a category of
clusters. Many desirable properties of a clustering method are subsumed in
functoriality when the morphisms are properly chosen. Here the relevant
morphisms under which the particular method is functorial can be viewed as
giving restrictions on the allowable data processing operations - restrictions
that impose consistency constraints across related data sets. One of our first
goals is to extend their theory of functorial clustering schemes to methods
that allow overlapping clusters in the spirit of Jardine and Sibson, and in so
doing obviate some of the unpleasant effects of chaining occurring in some
linkage-based methods. (See [9], Remark $16$, where Carlsson and Mémoli
discuss the chaining effects in single-linkage clustering and propose an
alternate solution based on explicitly considering density.) Rather than
relying on chaining to overcome certain technical problems, we accept
overlapping clusters. This leads to a much richer set of possible clustering
algorithms.

Finally, although in this paper we focus less on the construction of
clustering methods (clustering domains) derived from injective envelopes, we
do in the final section lay out some preliminaries, that hopefully will enable
the reader to get a feel for how the geometry of injective envelopes comes
into play. In addition, lest the reader think we are all theory and no
practice, we mention our ongoing algorithmic work on efficient implementations
of some of these clustering schemes, along the lines of what has already been
done for $q$-metrics by Segarra et al. [37] and for dithered maximal linkage
clustering by Gama et al. [25, 26].

###  1.1. Weight Categories

######  Definition 1.

Let $\mathbf{Weight}$ be the category of finite sets with weights, whose
objects have the form $(X,u)$ with $X$ a finite non-empty set and $u$ a
symmetric non-negative map $u\colon X\times X\to\mathds{R}$, $(x,y)\mapsto
u_{xy}$ satisfying $u_{xx}=0$ for all $x\in X$. A morphism
$f\colon(X,u)\to(Y,v)$ is a set map $f\colon X\to Y$ such that
$v_{f(x)f(x^{\prime})}\leq u_{xx^{\prime}}$; these will be referred to as non-
expansive maps.

For a fixed finite set $X$, we can define a local order structure by pointwise
dominance on the full subcategory $\mathbf{Weight}_{X}$ of $\mathbf{Weight}$
consisting of weights on $X$. In order to simplify notation, when the
underlying set $X$ is fixed we will often refer to the object
$(X,u)\in\mathbf{Weight}_{X}$ only by the weight function $u$ and state that
$u\in\mathbf{Weight}_{X}$. The set of objects of $\mathbf{Weight}_{X}$ is a
partially ordered set (poset) with the ordering given by

$u\leq v\text{ if }u_{xy}\leq v_{xy}\text{ for all }x,y\in X.$

It will be convenient to denote, for any subset $U$ of the objects of
$\mathbf{Weight}_{X}$,

$U\\!\downarrow:=\left\\{w\in\mathbf{Weight}_{X}\,\Big{|}\,\exists{u\in
U}\;w\leq u\right\\}$

and in the case of the singleton set $\\{u\\}$, we will often write
$u\\!\downarrow$ for $\\{u\\}\\!\downarrow$. For any subcategory $\mathbf{C}$
of $\mathbf{Weight}$, we will use the analogous notation $\mathbf{C}_{X}$ for
$\mathbf{C}\cap\mathbf{Weight}_{X}$, which on objects will be the intersection
of the objects of $\mathbf{C}$ and $\mathbf{Weight}_{X}$ with the morphisms of
$\mathbf{C}$. Also, for every map of finite sets $f\colon X\to Y$ and
$w\in\mathbf{Weight}_{Y}$ we define $f^{\ast}(w)\in\mathbf{Weight}_{X}$ to be
the pullback of the weight $w$ to the set $X$, more explicitly,
$f^{\ast}(w)_{xy}:=w_{f(x)f(y)}$. This notation allows another perspective on
morphisms in $\mathbf{Weight}$: the map of finite sets $f\colon X\to Y$
induces a morphism $(X,u)\to(Y,v)$ in $\mathbf{Weight}$ if and only if
$f^{\ast}(v)\leq u$.

######  Definition 2.

We define a weight category to be any full subcategory $\mathbf{C}$ of
$\mathbf{Weight}$ such that $f^{\ast}\mathbf{C}_{Y}\subseteq\mathbf{C}_{X}$
for any map of finite sets $f\colon X\to Y$. We say that $\mathbf{C}$ is
closed under pullbacks, and will sometimes refer to this as the pullback
property. Note that this condition is only on the objects of the category
$\mathbf{C}$.

Note that the category $\mathbf{Met}$ of finite metric spaces and non-
expansive maps, first considered by Isbell [31] for arbitrary metric spaces,
is a weight category in this sense. In this exposition, by metric we will
always mean semimetric; i.e., we will not require that distinct points have
nonzero distance.

######  Remark 3.

Since the pullback property allows arbitrary maps of finite sets, any
permutation mapping $f\colon X\to X$ satisfies
$f^{\ast}\mathbf{C}_{X}=\mathbf{C}_{X}$. In other words, weight categories are
invariant under permutations. In this way, the pullback property is a
generalization of what Jardine and Sibson term “label freedom” in [33], pp.
83–84.

######  Definition 4.

A functor $\mathcal{G}\colon\mathbf{C}\to\mathbf{D}$ between weight categories
will be said to be fibered, if the diagram

$\mathbf{C}$$\mathbf{D}$$\mathbf{Set}$$\mathcal{G}$${\mathcal{F}}_{\mathbf{C}}$$\mathcal{F}_{\mathbf{D}}$

commutes, where $\mathcal{F}_{\mathbf{C}}$ and $\mathcal{F}_{\mathbf{D}}$ are
the respective forgetful functors. For such a functor $\mathcal{G}$ and any
finite set $X$, we have an associated functor
$\mathcal{G}_{X}\colon{\mathbf{C}}_{X}\to{\mathbf{D}}_{X}$. In other words, on
objects, fibered functors fix the underlying set and on morphisms, fix the
underlying set map. Intuitively, a fibered functor acts on weighted spaces
only by deforming the weight structure.

######  Remark 5.

This entire exposition could be reformulated in the setting of fibered
categories and functors, where the fiber over a fixed finite set has the
structure of a directed complete poset, but we did not view the additional
advantage in abstraction and simplicity of definitions worth the overhead cost
of framing the work in those terms. The fibration of a weight category over
$\mathbf{Set}$ is straightforward. In Section 4.3, we give a hint at where
this generality would be important: we explore a subcategory of
$\mathbf{Weight}$ with a restricted set of morphisms. The important thing in
this type of setting is that the cartesian morphisms in each fiber provide
this directed complete poset structure. For $\mathbf{Weight}$, the categories
considered in Section 4.3, as well as for the categories considered by
Carlsson and Mémoli [10], this amounts to noting that the morphisms with
underlying map the identity are cartesian.

##  2\. Clustering with Overlaps: Sieves

Let $\mathbf{Cov}$ be the category of coverings, with an object a pair $(X,C)$
consisting of a finite set $X$ together with a cover $C$ of $X$. A morphism
$f\colon(X,C)\to(Y,D)$ is a set map $f\colon X\to Y$ such that the cover
$f^{-1}(D)$ of $X$ is refined by $C$.

######  Definition 6.

Given a non-empty finite set $X$ we define a non-nested flag cover of $X$ to
be a cover $C$ of $X$ additionally satisfying:

  1. (i)

for all $A,B\in C$ with $A\subseteq B$, we have $A=B$;

  2. (ii)

the abstract simplicial complex $K_{C}$ with vertices corresponding to
elements of $X$ and faces all subsets of the sets in $C$ is a flag complex,
i.e., if all of the edges of a given simplex are in $K_{C}$, then that simplex
itself is also in $K_{C}$.

The category $\mathbf{Cov}_{{}_{\leavevmode\hbox to2.09pt{\vbox
to3.38pt{\pgfpicture\makeatletter\hbox{\hskip 0.4pt\lower-0.4pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{} {{{}{}}{}}{} {{}{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.58333pt}\pgfsys@lineto{1.29166pt}{1.72221pt}\pgfsys@lineto{0.0pt}{0.8611pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}$ is then the full
subcategory of $\mathbf{Cov}$ where the covers are required to be non-nested
flag covers.

######  Remark 7.

For a non-nested flag cover $C$ of $X$, observe that the sets in $C$ provide
the maximal simplices in the simplicial complex defined in $(ii)$ above. Given
a fixed finite set $X$, we will denote the full subcategory of
$\mathbf{Cov}_{{}_{\leavevmode\hbox to2.09pt{\vbox
to3.38pt{\pgfpicture\makeatletter\hbox{\hskip 0.4pt\lower-0.4pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{} {{{}{}}{}}{} {{}{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.58333pt}\pgfsys@lineto{1.29166pt}{1.72221pt}\pgfsys@lineto{0.0pt}{0.8611pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}$ consisting of
covers on $X$ by $\mathbf{Cov}_{{}_{\leavevmode\hbox to2.09pt{\vbox
to3.38pt{\pgfpicture\makeatletter\hbox{\hskip 0.4pt\lower-0.4pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{} {{{}{}}{}}{} {{}{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.58333pt}\pgfsys@lineto{1.29166pt}{1.72221pt}\pgfsys@lineto{0.0pt}{0.8611pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}(X)$. Notice that,
in particular, every partition of $X$ is a flag cover of $X$.

######  Remark 8.

The inclusion functor $\mathbf{Cov}_{{}_{\leavevmode\hbox to2.09pt{\vbox
to3.38pt{\pgfpicture\makeatletter\hbox{\hskip 0.4pt\lower-0.4pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{} {{{}{}}{}}{} {{}{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.58333pt}\pgfsys@lineto{1.29166pt}{1.72221pt}\pgfsys@lineto{0.0pt}{0.8611pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}\to\mathbf{Cov}$,
which simply forgets that a given cover is a non-nested flag cover, has a left
adjoint given by flagification. Formally, any cover $\tilde{C}$ of a finite
set $X$ has a unique associated non-nested flag cover: $\tilde{C}$ can be
“flagified” to a non-nested flag cover $C$ in a minimal way. Explicitly,
$\tilde{C}$ will refine the non-nested flag cover $C$ and $C$ will refine any
other non-nested flag cover which $\tilde{C}$ refines. Algorithmically, this
is very simple and amounts to adding in any subsets required by the flag
condition (i.e., adding a subset $A$ if all of the proper subsets of $A$ are
already in $\tilde{C}$, then iterating this process) and then removing any
subsets from the cover that are entirely contained in another subset. In
principle, this construction would seemingly be important for defining the
morphisms in $\mathbf{Cov}_{{}_{\leavevmode\hbox to2.09pt{\vbox
to3.38pt{\pgfpicture\makeatletter\hbox{\hskip 0.4pt\lower-0.4pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{} {{{}{}}{}}{} {{}{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.58333pt}\pgfsys@lineto{1.29166pt}{1.72221pt}\pgfsys@lineto{0.0pt}{0.8611pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}$. That is, from a
categorical point of view, the refinement criterion for a map of finite sets
$f\colon X\to Y$ to be a $\mathbf{Cov}_{{}_{\leavevmode\hbox to2.09pt{\vbox
to3.38pt{\pgfpicture\makeatletter\hbox{\hskip 0.4pt\lower-0.4pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{} {{{}{}}{}}{} {{}{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.58333pt}\pgfsys@lineto{1.29166pt}{1.72221pt}\pgfsys@lineto{0.0pt}{0.8611pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}$-morphism
$f\colon(X,C)\to(Y,D)$ is not natural in the sense that the cover $f^{-1}(D)$
of $X$ might contain nesting and so $(X,f^{-1}(D))$ is not an object in
$\mathbf{Cov}_{{}_{\leavevmode\hbox to2.09pt{\vbox
to3.38pt{\pgfpicture\makeatletter\hbox{\hskip 0.4pt\lower-0.4pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{} {{{}{}}{}}{} {{}{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.58333pt}\pgfsys@lineto{1.29166pt}{1.72221pt}\pgfsys@lineto{0.0pt}{0.8611pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}$. The more
appropriate condition involves first applying the flagification functor to
$(X,f^{-1}(D))$ and then verifying the refinement condition. However, it is
straightforward to see that these are equivalent: if $C$ is a flag cover on
$X$, then $f^{-1}(D)$ is refined by $C$ if and only if the flagification of
$f^{-1}(D)$ is refined by $C$.

######  Definition 9.

A sieve on a finite set $X$ is a function $\theta\colon\mathds{R}_{\geq
0}\to\mathbf{Cov}_{{}_{\leavevmode\hbox to2.09pt{\vbox
to3.38pt{\pgfpicture\makeatletter\hbox{\hskip 0.4pt\lower-0.4pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{} {{{}{}}{}}{} {{}{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.58333pt}\pgfsys@lineto{1.29166pt}{1.72221pt}\pgfsys@lineto{0.0pt}{0.8611pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}(X)$ such that:

  1. (i)

If $t_{1}<t_{2}$ then $\theta(t_{1})$ refines $\theta(t_{2})$;

  2. (ii)

For any $t$, there is an $\varepsilon>0$ such that
$\theta(t^{\prime})=\theta_{X}(t)$ for all $t^{\prime}\in[t,t+\varepsilon)$;

  3. (iii)

There exists $t\in\mathds{R}_{\geq 0}$ such that $\theta(t)$ is the trivial
cover $\\{X\\}$.

We say that a sieve $\theta$ on $S$ is proper, if $\theta(0)$ is the covering
by singletons. In order to curb the proliferation of parentheses, we will also
use the notation $\theta_{t}$ for $\theta(t)$.

Sieves are the obvious generalization of dendrograms (see [9], Section $4.1$
for a modern, self-contained discussion of dendrograms), which satisfy the
same conditions as sieves, but take values in the more restricted set of
partitions of $X$ rather than coverings of $X$. Jardine and Sibson ([33], p.
$80$) also considered a similar construction to our sieves, though taking
values in symmetric reflexive relations on $X$. They also did not focus on the
morphisms between sieves as we do, starting with the following definition.

######  Definition 10.

We define the category of sieves, $\mathbf{Sieve}$, as the category of pairs
$(X,\theta)$, where $\theta\colon\mathds{R}_{{}_{\geq
0}}\to\mathbf{Cov}_{{}_{\leavevmode\hbox to2.09pt{\vbox
to3.38pt{\pgfpicture\makeatletter\hbox{\hskip 0.4pt\lower-0.4pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{} {{{}{}}{}}{} {{}{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.58333pt}\pgfsys@lineto{1.29166pt}{1.72221pt}\pgfsys@lineto{0.0pt}{0.8611pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}(X)$ is a sieve on a
finite set $X$. The morphisms in $\mathbf{Sieve}$ are an extension of the
morphisms of $\mathbf{Cov}_{{}_{\leavevmode\hbox to2.09pt{\vbox
to3.38pt{\pgfpicture\makeatletter\hbox{\hskip 0.4pt\lower-0.4pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{} {{{}{}}{}}{} {{}{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.58333pt}\pgfsys@lineto{1.29166pt}{1.72221pt}\pgfsys@lineto{0.0pt}{0.8611pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}$; that is, a map of
finite sets $f\colon X\to Y$ is a morphism of sieves $(X,\theta)\to(Y,\psi)$
if for every $t\in\mathds{R}_{\geq 0}$, $\theta_{t}$ refines
$f^{-1}(\psi_{t})$. In other words, for each $t\in\mathds{R}_{{}_{\geq 0}}$,
we have a functor $\mathbf{Sieve}\to\mathbf{Cov}_{{}_{\leavevmode\hbox
to2.09pt{\vbox to3.38pt{\pgfpicture\makeatletter\hbox{\hskip
0.4pt\lower-0.4pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{} {{{}{}}{}}{} {{}{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.58333pt}\pgfsys@lineto{1.29166pt}{1.72221pt}\pgfsys@lineto{0.0pt}{0.8611pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}$. Note that just as
in Remark 8, in general, $(X,f^{-1}(\psi_{t}))$ might be an object of the
ambient category $\mathbf{Cov}$ and not $\mathbf{Cov}_{{}_{\leavevmode\hbox
to2.09pt{\vbox to3.38pt{\pgfpicture\makeatletter\hbox{\hskip
0.4pt\lower-0.4pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{} {{{}{}}{}}{} {{}{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.58333pt}\pgfsys@lineto{1.29166pt}{1.72221pt}\pgfsys@lineto{0.0pt}{0.8611pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}$ due to nesting,
but nonetheless, this condition is equivalent to a more complex condition
involving first flagifying $f^{-1}(\psi_{t})$.

Just as in $\mathbf{Weight}$, the categories
$\mathbf{Cov}_{{}_{\leavevmode\hbox to2.09pt{\vbox
to3.38pt{\pgfpicture\makeatletter\hbox{\hskip 0.4pt\lower-0.4pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{}{{}}{} {{{}{}}{}}{} {{}{}}{}
{{}{}}{}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@setlinewidth{0.8pt}\pgfsys@invoke{
}{}\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@lineto{0.0pt}{2.58333pt}\pgfsys@lineto{1.29166pt}{1.72221pt}\pgfsys@lineto{0.0pt}{0.8611pt}\pgfsys@stroke\pgfsys@invoke{
} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}$ and
$\mathbf{Sieve}$ are also fibered over $\mathbf{Set}$ in a natural way. We
will restrict to fibered functors in our discussion, which in particular
ensures that underlying sets and mappings are fixed by the functors. Any
fibered functor with values in $\mathbf{Sieve}$ then provides a hierarchical
method of clustering that respects the constraints imposed by the morphisms in
$\mathbf{Weight}$ and produces potentially overlapping clusters at any fixed
scale. For clarity in the exposition, we make the following definition.

######  Definition 11.

A sieving functor is a fibered functor $\mathbf{Weight}\to\mathbf{Sieve}$. One
of the primary purposes of this paper is to characterize a particularly “nice”
class of sieving functors, in a way that will be made precise below (see
Theorem 28).

######  Example 12 (Rips Sieving).

Let $(X,u)\in\mathbf{Weight}$ and let $\delta\geq 0$. Recall that the Rips
complex at resolution $\delta$ on $(X,u)$ is the abstract simplicial complex
$K_{u}(\delta)$ with vertex set $X$, where a subset $A\subseteq S$ forms a
face of $K_{u}(\delta)$ if and only if
$\mathtt{diam}\\!\left(A\right)\leq\delta$ (see [23], Section III.2 for a more
detailed treatment of the Rips complex and other related ideas). If
$M_{u}(\delta)$ is the collection of maximal simplices of $K_{u}(\delta)$,
then $M_{u}(\delta)$ forms a non-nested flag cover of $X$. Define
$\mathcal{R}\colon\mathbf{Weight}\to\mathbf{Sieve}$ by

$\mathcal{R}(X,u)_{t}=(X,M_{u}(t)),$

which we will call the Rips sieving functor (elsewhere, including in [12],
this functor is denoted $\mathcal{ML}$ and called maximal-linkage). On
morphisms, $\mathcal{R}$ sends a non-expansive map of weight spaces to the
same underlying set function. It is straightforward to see that this gives a
$\mathbf{Sieve}$-morphism.

######  Proposition 13.

The category $\mathbf{Weight}$ is equivalent to $\mathbf{Sieve}$.

###### Proof.

Given a sieve $(X,\theta)$, define a weight space $(X,u_{\theta})$ pointwise
with $x,y\in X$ by

$u_{\theta}(x,y)=\min\left\\{t\in\mathds{R}_{{}_{\geq 0}}\,\Big{|}\,\exists
A\in\theta_{t},\\{x,y\\}\subseteq A\right\\}.$

At first glance, it might appear that we need to consider the infimum rather
than the minimum, but condition $(ii)$ in Definition 9 ensures that
$u_{\theta}$ is well-defined. This assignment extends to a functor
$\mathcal{J}\colon\mathbf{Sieve}\to\mathbf{Weight}$, and it is straightforward
to check that $\mathcal{J}\circ\mathcal{R},\mathcal{R}\circ\mathcal{J}$ are
the respective identity functors. ∎

######  Remark 14.

This proposition shows that Rips sieving is the canonical way of producing
sieves from weight spaces, in the sense that a weight space can be recovered
from its Rips sieve. The result extends the connection noted by
Carlsson–Mémoli between the category of ultrametrics (Definition 33) and the
category of dendrograms; indeed our proof is a reworking of theirs in this new
context (see [9], Theorem $9$). From this perspective, a natural question is
how to characterize sieving functors that factor through Rips sieving, i.e.,
sieving functors $\mathcal{C}$ which can be realized as a composition
$\mathcal{C}={\mathcal{R}}\circ\mathcal{P}$, for some functor $\mathcal{P}$.
Theorem 28 below shows one result in this direction.

######  Example 15 (Single-Linkage Sieving).

Let $(X,u)\in\mathbf{Weight}$ and $K_{u}(\delta)$ as in Example 12. In this
case, rather than look at maximal simplices, let $C_{u}(\delta)$ be the
connected components of $K_{u}(\delta)$. Then we can define the single-linkage
sieving functor $\mathcal{SL}\colon\mathbf{Weight}\to\mathbf{Sieve}$ by

$\mathcal{SL}(X,u)_{t}=(X,C_{u}(t)),$

with morphisms being sent to the same underlying set maps. This is equivalent
to the many alternative well-known characterizations of single-linkage
clustering, for instance in [38, 27, 10].

######  Example 16 (Čech Sieving).

If $(X,u)\in\mathbf{Weight}$, define a graph $G_{u}(\delta)$ with vertices the
elements of $X$ and an edge $xy$ if there exists an element $z\in X$ with
$u(x,z),u(z,y)\leq\delta$. We then define
$\check{\mathcal{C}}\colon\mathbf{Weight}\to\mathbf{Sieve}$ to be the
assignment which sends any $t\in\mathds{R}_{{}_{\geq 0}}$ to the set of
maximal cliques of $G_{u}(t)$. Again in this case, morphisms are sent to the
same underlying set maps.

Many other examples can be derived from the clustering functors introduced in
our work with Hansen in [12].

##  3\. Clustering Domains

######  Definition 17.

We say that a weight category $\mathbf{D}$ is a clustering domain if for any
non-empty finite set $X$ and any $w\in\mathbf{Weight}_{X}$, the set
$\mathbf{D}_{X}\cap w\\!\downarrow$ is non-empty and $\sup$-closed in
$\mathbf{Weight}_{X}$. That is,

$\left(X,\sup\\{u\in{\mathbf{D}_{X}\cap
w\\!\downarrow}\\}\right)\in\mathbf{D},$

for all $w\in\mathbf{Weight}_{X}$.

The importance of sup-closure was recognized as early as [33], in their
discussion of optimality (p. $85$), and it will often be convenient to satisfy
a stronger (but more easily verified) condition related to the topology on
$\mathbf{Weight}$ induced by the identification of the objects of
$\mathbf{Weight}_{X}$ with the nonnegative real orthant $\mathds{R}_{\geq
0}^{\binom{|X|}{2}}$.

######  Proposition 18.

Let $\mathbf{C}$ be a weight category. If the set of objects of
$\mathbf{C}_{X}$ is closed as a subset of $\mathds{R}_{\geq
0}^{\binom{|X|}{2}}$ and $\mathbf{C}_{X}$ is closed under taking finite
maxima, then $\mathbf{C}$ is a clustering domain.

###### Proof.

If $w\in\mathbf{Weight}_{X}$ and $S\subset\mathbf{C}_{X}$ satisfies $d\leq w$
for all $d\in S$, then $v:=\sup_{d\in S}(d)$ has $v\leq w$ and we consider the
following procedure. For every pair $x,y\in X$ and $\varepsilon>0$ find
$u^{\varepsilon}_{x,y}\in S$ such that
$v(x,y)-u^{\varepsilon}_{x,y}(x,y)<\varepsilon$; then
$u^{\varepsilon}:=\max_{x,y\in X}u^{\varepsilon}_{x,y}\in\mathbf{C}_{X}$ and
satisfies $\left\|v-u^{\varepsilon}\right\|_{\infty}<\varepsilon$, and so we
conclude that $v$ is in the closure of $\mathbf{C}_{X}$. ∎

###  3.1. Projections

The reason to define clustering domains is that, in some sense, clustering
maps “live” on them.

######  Definition 19 (Canonical Projection).

Given a clustering domain $\mathbf{D}$, we define the canonical projection
${\mathcal{P}}_{\mathbf{D}}\colon\mathbf{Weight}\to\mathbf{Weight}$ to be the
fibered functor defined by

${\mathcal{P}}_{\mathbf{D}}(X,w)=\left(X,\sup\\{u\in\mathbf{D}_{X}\cap
w\\!\downarrow\\}\right).$

Recall that the fibered condition implies that ${\mathcal{P}}_{\mathbf{D}}$
sends a morphism in $\mathbf{Weight}$ to the morphism with the same underlying
set map. Also $\left(X,\sup\\{u\in\mathbf{D}_{X}\cap w\\!\downarrow\\}\right)$
is an object in $\mathbf{D}$ since $\mathbf{D}$ is a clustering domain.

We need to verify the assertions made in this definition regarding properties
of ${\mathcal{P}}_{\mathbf{D}}$.

######  Proposition 20 (Properties of the Canonical Projection).

Suppose $\mathbf{D}$ is a clustering domain and
${\mathcal{P}}={\mathcal{P}}_{\mathbf{D}}$ is the associated canonical
projection. Then ${\mathcal{P}}$ is a fibered endofunctor of $\mathbf{Weight}$
satisfying the additional properties:

  1. (1)

${\mathcal{P}}\circ{\mathcal{P}}={\mathcal{P}}$,

  2. (2)

${\mathcal{P}}_{X}w\leq w$ for all sets $X$ and $w\in\mathbf{Weight}_{X}$.

###### Proof.

Since the identities

${\mathcal{P}}(\mathrm{id}_{(X,w)})=\mathrm{id}_{{\mathcal{P}}(X,w)}\,,\quad{\mathcal{P}}(g\circ
f)={\mathcal{P}}(g)\circ{\mathcal{P}}(f)$

are immediate from the definition, one is left only to verify that
${\mathcal{P}}(f)$ is a non-expansive map whenever $f\colon(X,u)\to(Y,v)$ is.
Equivalently, we need to show that
$f^{\ast}({\mathcal{P}}v)\leq{\mathcal{P}}u$ holds whenever $f^{\ast}(v)\leq
u$. By definition, ${\mathcal{P}}v\leq v$ and we have:

${\mathcal{P}}v\leq v\;\Leftrightarrow\;f^{\ast}({\mathcal{P}}v)\leq
f^{\ast}(v)\;\Rightarrow\;f^{\ast}({\mathcal{P}}v)\leq
u\;\Leftrightarrow\;f^{\ast}({\mathcal{P}}v)\in u\\!\downarrow$

Thus, $f^{\ast}({\mathcal{P}}v)\in u\\!\downarrow\cap
f^{\ast}(\mathbf{D}_{Y})\subseteq u\\!\downarrow\cap\mathbf{D}_{X}$, by the
definition of a clustering domain. Finally,
$f^{\ast}({\mathcal{P}}v)\leq{\mathcal{P}}u$ by the definition of
${\mathcal{P}}u$. ∎

In an attempt to construct more general sieving functors in the spirit of the
previous proposition (and the similar conditions of Jardine and Sibson in
[33], pp. 83–85) one might seek to introduce the following definition:

######  Definition 21 (Projection).

Let $\mathbf{C}$ be a weight category. We say that a fibered functor
${\mathcal{P}}\colon\mathbf{C}\to\mathbf{C}$ is a projection, if it satisfies:

  * •

Idempotency ${\mathcal{P}}\circ{\mathcal{P}}={\mathcal{P}}$;

  * •

Contraction ${\mathcal{P}}_{X}w\leq w$ for all sets $X$ and
$w\in\mathbf{C}_{X}$.

######  Remark 22.

The fact that ${\mathcal{P}}$ is a fibered functor implies that for a fixed
set $X$, the self-maps
${\mathcal{P}}_{X}\colon\mathbf{Weight}_{X}\to\mathbf{Weight}_{X}$ are order-
preserving. For all $w_{1},w_{2}\in\mathbf{Weight}_{X}$ one has:

$\displaystyle w_{1}\leq w_{2}$ $\displaystyle\;\Leftrightarrow\;$
$\displaystyle\mathrm{id}_{X}\in\mathrm{Hom}_{\mathbf{Weight}}\left((X,w_{2}),(X,w_{1})\right)$
$\displaystyle\;\Rightarrow\;$
$\displaystyle\mathrm{id}_{X}={\mathcal{P}}(\mathrm{id}_{X})\in\mathrm{Hom}_{\mathbf{Weight}}\left((X,{\mathcal{P}}_{X}w_{2}),(X,{\mathcal{P}}_{X}w_{1})\right)$
$\displaystyle\;\Leftrightarrow\;$
$\displaystyle{\mathcal{P}}_{X}w_{1}\leq{\mathcal{P}}_{X}w_{2}$

The following result was initially observed for single linkage hierarchical
clustering in [42], however its categorification and generalization are new:

######  Proposition 23 (Uniqueness of Projections).

Let $\mathbf{C}\subseteq\mathbf{Weight}$ be a weight category. Then every
weight category $\mathbf{D}\subseteq\mathbf{C}$ admits at most one projection
${\mathcal{P}}\colon\mathbf{C}\to\mathbf{C}$ whose image coincides with
$\mathbf{D}$.

###### Proof.

Suppose ${\mathcal{P}},\mathcal{Q}$ are arbitrary projections with image
$\mathbf{D}$. Fixing a non-empty finite set $X$ and applying the idempotency
requirement, we have that for all $w\in\mathbf{C}_{X}$:

$w\in\mathbf{D}_{X}\;\Leftrightarrow\;{\mathcal{P}}_{X}w=w\;\Leftrightarrow\;\mathcal{Q}_{X}w=w.$

We conclude that ${\mathcal{P}}_{X}$ fixes $\mathcal{Q}_{X}w$ and
$\mathcal{Q}_{X}$ fixes ${\mathcal{P}}_{X}w$ for all $w\in\mathbf{C}_{X}$.
From Remark 22 we then obtain, for all $w\in\mathbf{C}_{X}$:

${\mathcal{P}}_{X}w\leq
w\;\Rightarrow\;{\mathcal{P}}_{X}w=\mathcal{Q}_{X}{\mathcal{P}}_{X}w\leq\mathcal{Q}_{X}w$

We conclude that ${\mathcal{P}}_{X}w\leq\mathcal{Q}_{X}w$ for all
$w\in\mathbf{C}_{X}$. By a symmetric argument, the reverse inequality holds
true as well and we have shown that ${\mathcal{P}}$ and $\mathcal{Q}$ coincide
on $\mathbf{C}$. ∎

######  Corollary 24.

Suppose $\mathbf{C}$ is a weight category containing a clustering domain
$\mathbf{D}$. Then $\mathbf{C}$ admits one and only one projection with image
$\mathbf{D}$: the restriction of the canonical projection
${\mathcal{P}}_{\mathbf{D}}$ to $\mathbf{C}$.

This last corollary emphasizes that the existence of a clustering projection
must be characterized in terms of its image category. We have:

######  Theorem 25 (Existence of Projections).

Let $\mathbf{D}$ be a full subcategory of the category $\mathbf{Weight}$. Then
$\mathbf{D}$ is a clustering domain if and only if it is the image of a
projection functor ${\mathcal{P}}\colon\mathbf{Weight}\to\mathbf{Weight}$.

###### Proof.

If $\mathbf{D}$ is a clustering domain then it is the image of the canonical
projection ${\mathcal{P}}={\mathcal{P}}_{\mathbf{D}}$. Conversely, assume the
full subcategory $\mathbf{D}$ is the image of a clustering projection functor
${\mathcal{P}}\colon\mathbf{Weight}\to\mathbf{Weight}$ and let us prove it is
a clustering domain.

First, we need to see that $\mathbf{D}$ is a weight category. Suppose $f\colon
X\to Y$ is a map of finite sets. For $w\in\mathbf{D}_{Y}$, consider
$v=f^{\ast}w\in\mathbf{Weight}_{X}$: then $f\colon(X,v)\to(Y,w)$ is a morphism
and hence $f\colon(X,{\mathcal{P}}_{X}v)\to(Y,{\mathcal{P}}_{Y}w)=(Y,w)$ is a
morphism as well; or equivalently, $v=f^{\ast}w\leq{\mathcal{P}}_{X}v$. Thus,
by the contraction property of ${\mathcal{P}}$ we have
$v={\mathcal{P}}_{X}v\in\mathbf{D}_{X}$, as desired.

Note that for any finite set $X$ and $w\in\mathbf{Weight}_{X}$, the set
$\mathbf{D}_{X}\cap w\\!\downarrow$ is nonempty since in particular, this
contains ${\mathcal{P}}w$. It remains to prove that $\mathbf{D}_{X}$ is
$\sup$-closed. Let $U$ be the set of objects in $\mathbf{D}_{X}\cap
w\\!\downarrow$. If $v=\sup\\{u\in U\\}$ then $v$ is the minimal weight in
$\mathbf{Weight}_{X}$ satisfying $v\geq u$ for all $u\in U$. By functoriality,
we see that ${\mathcal{P}}v\geq{\mathcal{P}}u=u$, so we must have
${\mathcal{P}}v\geq v$. Since ${\mathcal{P}}$ is a projection, and in
particular, satisfies the contraction property, ${\mathcal{P}}v\leq v$ as well
and so $v\in\mathbf{D}_{X}$, as required. ∎

######  Remark 26.

Let $\mathbf{C}\subset\mathbf{D}$ be clustering domains. Proposition 23
implies that we have a unique factorization:

$\mathbf{Weight}$$\mathbf{D}$$\mathbf{C}$${\mathcal{P}}_{\mathbf{D}}$$\mathrm{Res}_{\mathbf{D}}({{\mathcal{P}}_{\mathbf{C}}})$${\mathcal{P}}_{\mathbf{C}}$

where ${\mathcal{P}}_{C}$ and ${\mathcal{P}}_{D}$ are the respective
projections associated with $\mathbf{C}$ and $\mathbf{D}$ while
$\mathrm{Res}_{\mathbf{D}}({{\mathcal{P}}_{\mathbf{C}}})$ is the restriction
of the functor ${\mathcal{P}}_{C}$ to the subcategory $\mathbf{D}$. Note that
the essential portions of the proof of the proposition depend only on the
order structure of $\mathbf{Weight}_{X}$, and consequently, this factorization
holds even when replacing $\mathbf{Set}$ with a category with fewer morphisms
(see Remark 5), such as only injective maps or only surjective maps.

######  Definition 27.

Let $\mathcal{C}\colon\mathbf{Weight}\to\mathbf{Sieve}$ be a sieving functor
and recall the functor $\mathcal{J}\colon\mathbf{Sieve}\to\mathbf{Weight}$
from the proof of Proposition 13. Then $\mathcal{C}$ will be called stationary
if $\mathcal{J}\circ\mathcal{C}$ is a projection.

Note that the stationary functors that we consider in this paper do not in
general satisfy the straightforward generalizations of either representability
or excisiveness (see [10]) to the setting of coverings. However, in Theorem
$6.3$ of that paper, Carlsson and Mémoli show that their notion of finite
representability (and therefore also excisiveness) implies a factorization
into an endofunctor followed by single-linkage. Thus, our notion of
stationarity is analogous to these conditions in the sense of the following
theorem.

######  Theorem 28.

There is a bijective correspondence between the collection of stationary
sieving functors and the collection of clustering domains: every stationary
sieving functor factors uniquely through a clustering projection and the Rips
sieving functor ${\mathcal{R}}$ restricted to a clustering domain.
Pictorially, for every stationary sieving functor $\mathcal{C}$ there is a
commutative diagram

$\mathbf{Weight}$$\mathbf{Sieve}$.$\mathbf{D}_{\mathcal{C}}$$\mathcal{C}$${\mathcal{P}}_{\mathbf{D}_{\mathcal{C}}}$$\mathrm{Res}_{\mathbf{D}_{\mathcal{C}}}({\mathcal{R}})$

where ${\mathcal{P}}_{\mathbf{D}_{\mathcal{C}}}$ is the unique associated
clustering projection and
$\mathrm{Res}_{\mathbf{D}_{\mathcal{C}}}({\mathcal{R}})$ is the Rips sieving
functor restricted to $\mathbf{D}_{\mathcal{C}}$.

###### Proof.

If $\mathcal{C}\colon\mathbf{Weight}\to\mathbf{Sieve}$ is a stationary sieving
functor, then
${\mathcal{P}}_{\mathbf{D}_{\mathcal{C}}}=\mathcal{J}\circ\mathcal{C}$ is a
projection and so from Theorem 25 we see that the image
$\mathbf{D}_{\mathcal{C}}$ of ${\mathcal{P}}_{\mathbf{D}_{\mathcal{C}}}$ is a
clustering domain. The theorem then follows from Proposition 13. ∎

In our first look at sieving functors, we defined the Čech sieve of Example
16, which is not a stationary sieving functor: for a fixed weight space, after
sufficiently many applications (interleaving applications of the functor
$\mathcal{J}$) it gives the result of the single-linkage sieve (see the
discussion of ${\mathbf{L}^{k}}$ clustering in our previous paper with Hansen
[12], where we describe Čech sieving in terms of set relations). In that
paper, we exhibited many different sieving functors that fail to be
stationary. An interesting generalization of the work here would be to explore
more complex characterizations that would include these non-stationary sieving
functors.

###  3.2. Single-linkage as a projection

In this section, we illustrate the relationship between projections and
clustering domains by revisiting the well-known single-linkage clustering
method from a new perspective. More details than necessary are given in order
to provide a template for one way of using the results in the previous section
to construct a clustering projection.

Let $(X,u)\in\mathbf{Weight}$ and $x_{1},x_{2}\in X$ with $x_{1}\neq x_{2}$.
Also, let $\Delta^{\varepsilon}_{2}$ be the two point space $\\{1,2\\}$ with
distance $\varepsilon$ between the two points. Then define
${\mathcal{E}}_{u}(x_{1},x_{2})$ to be the largest $\varepsilon$ for which
there exists a morphism (non-expansive map)
$f\colon(X,u)\to\Delta^{\varepsilon}_{2}$, with $f(x_{i})=i\text{ for }i=1,2$.
For $x_{1}=x_{2}$, define ${\mathcal{E}}_{u}(x_{1},x_{2})=0$. Note that if the
smallest distance between any two points in $X$ is $u_{\text{sep}}$ (the so-
called separation of $X$), then ${\mathcal{E}}_{u}(x_{1},x_{2})\geq
u_{\text{sep}}$ since we can map $X$ to $\Delta^{u_{\text{sep}}}_{2}$
arbitrarily and have a non-expansive map. Moreover, notice that
${\mathcal{E}}_{u}(x_{1},x_{2})\leq u(x_{1},x_{2})$ since $f$ is required to
be non-expansive. This means that the identity set map on $X$ gives a
$\mathbf{Weight}$-morphism $(X,u)\to(X,{\mathcal{E}}_{u})$, or in the language
of Definition 21, ${\mathcal{E}}$ is a contraction.

######  Definition 29.

Recall that a cut metric (see [13] for a detailed treatment) on any non-empty
set $Y$ is a non-negatively weighted finite combination of cuts. A cut is a
metric given by a subset $A\subset X$ and its complement $A^{c}$, with the
associated metric $\delta_{A}$ on $X$ is defined as

$\delta_{A}(y_{1},y_{2})=\begin{cases}0&\text{if }y_{1},y_{2}\text{ are both
in }A\text{ or both in }A^{c}\\\ 1&\text{otherwise.}\end{cases}$

Notice that $\delta_{A}=\delta_{A^{c}}$ and the trivial cut
$\\{X,\emptyset\\}$ produces the zero metric.

Now for any fixed $x_{1},x_{2}\in X$, and any morphism
$f\colon(X,u)\to\Delta^{{\mathcal{E}}_{u}(x_{1},x_{2})}_{2}$ satisfying
$f(x_{i})=i$ for $i=1,2$, the morphism $f$ defines a bi-partition of $X$ into
$X_{1}=f^{-1}(1)$ and $X_{2}=f^{-1}(2)$ with $x_{1}\in X_{1}$ and $x_{2}\in
X_{2}$. The morphism $f$ will then factor through $X$ with the cut metric
$\delta_{\\{X_{1}\\}}=\delta_{\\{X_{2}\\}}$ scaled by
${\mathcal{E}}_{u}(x_{1},x_{2})$:

${(X,u)}$${\Delta^{{\mathcal{E}}_{u}(x_{1},x_{2})}_{2}}$${(X,{\mathcal{E}}_{u}(x_{1},x_{2})\delta_{\\{X_{1}\\}})\,.}$$\scriptstyle{f}$

Notice that ${\mathcal{E}}_{u}(x_{1},x_{2})\delta_{\\{X_{1}\\}}$ is just the
pullback of the metric $\Delta^{{\mathcal{E}}_{u}(x_{1},x_{2})}_{2}$ by $f$.
In general, we might have several morphisms
$f\colon(X,u)\to\Delta^{{\mathcal{E}}_{u}(x_{1},x_{2})}_{2}$ which give
different bi-partitions.

We now show that the mapping ${\mathcal{E}}$ taking $(X,u)$ to
$(X,{\mathcal{E}}_{u})$ is a projection as described in Definition 21.

######  Proposition 30.

The mapping ${\mathcal{E}}\colon\mathbf{Weight}\to\mathbf{Weight}$ is a
fibered functor with the contraction property, where ${\mathcal{E}}$ takes a
morphism $f\colon(X,u)\to(Y,v)$ in $\mathbf{Weight}$ to the same underlying
set map.

###### Proof.

Since ${\mathcal{E}}$ takes morphisms to the same underlying set map, it is
fibered, and as has already been observed above, ${\mathcal{E}}$ is a
contraction. Hence the only thing requiring proof is that the map
${\mathcal{E}}(g)\colon(X,{\mathcal{E}}_{u})\to(Y,{\mathcal{E}}_{v})$ is a
$\mathbf{Weight}$-morphism. We simply need to see that for every pair of
points $x_{1},x_{2}\in X$ we have
${\mathcal{E}}_{u}(x_{1},x_{2})\geq{\mathcal{E}}_{v}(g(x_{1}),g(x_{2}))$. But
we have morphisms $g$ and $f$:

$(X,u)\xrightarrow{g}(Y,v)\xrightarrow{f}\Delta^{{\mathcal{E}}_{v}(f(x_{1}),f(x_{2}))}_{2}$

whose composition $f\circ g$ is a morphism sending $x_{1}$ and $x_{2}$ to
different points in the set
$\Delta^{{\mathcal{E}}_{v}(f(x_{1}),f(x_{2}))}_{2}$. Since
${\mathcal{E}}_{u}(x_{1},x_{2})$ is defined to be the maximum $\varepsilon$
satisfying this property, we must have
${\mathcal{E}}_{u}(x_{1},x_{2})\geq{\mathcal{E}}_{v}(g(x_{1}),g(x_{2})).$ ∎

######  Proposition 31.

The functor ${\mathcal{E}}$ is idempotent, i.e.
${\mathcal{E}}\circ{\mathcal{E}}={\mathcal{E}}$.

###### Proof.

Since ${\mathcal{E}}$ sends morphisms to the same underlying set map, we only
need to check that ${\mathcal{E}}$ is idempotent on objects. Notice that for
any $\varepsilon>0$, we have
${\mathcal{E}}(\Delta^{\varepsilon}_{2})=\Delta^{\varepsilon}_{2}$. Thus for
any morphism $f\colon(X,u)\to\Delta^{\varepsilon}_{2}$ separating a pair of
points $x_{1},x_{2}\in X$, we have a corresponding morphism
${\mathcal{E}}(f)\colon(X,{\mathcal{E}}_{u})\to\Delta^{\varepsilon}_{2}$ also
separating $x_{1},x_{2}$. Combining this with the fact that
${\mathcal{E}}^{2}(x_{1},x_{2})\leq{\mathcal{E}}(x_{1},x_{2})$, we get
equality. ∎

The previous two propositions then show that ${\mathcal{E}}$ is a projection
and so by Proposition 23, the functor ${\mathcal{E}}$ is the canonical
projection for its image, which must be a clustering domain. The remaining
question is how to characterize this clustering domain. The following lemma
will be useful toward this end.

######  Lemma 32.

Let $\mathbf{D}$ be a clustering domain containing $\Delta^{\varepsilon}_{2}$
for all $\varepsilon\geq 0$. Then
$\mathrm{im}({\mathcal{E}})\subseteq\mathbf{D}$.

###### Proof.

Let ${\mathcal{P}}_{\mathbf{D}}\colon\mathbf{Weight}\to\mathbf{Weight}$ be the
canonical projection with image $\mathbf{D}$ and $(X,u)\in\mathbf{Weight}$.
Then for any $x_{1},x_{2}\in X$, we have

${\mathcal{E}}_{u}(x_{1},x_{2})\leq{\mathcal{P}}_{\mathbf{D}}(u)(x_{1},x_{2})\leq
u(x_{1},x_{2})$

since $f\colon(X,u)\to\Delta^{{\mathcal{E}}_{u}(x_{1},x_{2})}_{2}$ yields a
morphism
${\mathcal{P}}_{\mathbf{D}}(f)\colon(X,{\mathcal{P}}_{\mathbf{D}}(u))\to\Delta^{{\mathcal{E}}_{u}(x_{1},x_{2})}_{2}$.
Proposition 31 then implies that
${\mathcal{E}}\circ{\mathcal{P}}_{\mathbf{D}}={\mathcal{E}}$. Replacing $u$
with ${\mathcal{E}}_{u}$ in the above reasoning, we also get

${\mathcal{E}}_{u}(x_{1},x_{2})\leq{\mathcal{P}}_{\mathbf{D}}({\mathcal{E}}_{u})(x_{1},x_{2})\leq{\mathcal{E}}_{u}(x_{1},x_{2}),$

and we see that ${\mathcal{P}}_{\mathbf{D}}$ fixes
$\mathrm{im}({\mathcal{E}})$. ∎

For further discussion of this point in a different context, see [12], Theorem
$8$. Here Lemma 32 extends the concept of the referenced theorem to the
hierarchical setting, where the infrastructure of clustering domains and
projections affords a succinct statement. In order to state the next result,
we need to recall the definition of an ultrametric.

######  Definition 33.

An ultrametric on a set $X$ is a metric $(X,u)$ satisfying a stronger version
of the triangle inequality: for any $x,y,z$ in $X$, we have

$u(x,z)\leq\max\\{u(x,y),u(y,z)\\}.$

The category of finite ultrametrics $\mathbf{Ult}$ is the full subcategory of
$\mathbf{Weight}$ with objects the finite ultrametric spaces.

######  Corollary 34.

For any $(X,u)\in\mathbf{Weight}$, the weight $(X,{\mathcal{E}}_{u})$ is an
ultrametric.

###### Proof.

Following Lemma 32, it is sufficient to notice that the category
$\mathbf{Ult}$ of ultrametrics contains all two point weight spaces.
Alternatively, we could verify the ultrametric inequality directly. Let
$x_{1},x_{2}\in X$ with $x_{1}\neq x_{2}$, let $y\in X$ and let
$f\colon(X,u)\to\Delta^{{\mathcal{E}}_{u}(x_{1},x_{2})}_{2}$ be a
$\mathbf{Weight}$-morphism that separates $x_{1}$ and $x_{2}$, so that
$f(x_{i})=i$. Now, if $y\in f^{{\scriptscriptstyle-1}}(1)$ then
${\mathcal{E}}_{u}(x_{2},y)\geq{\mathcal{E}}_{u}(x_{1},x_{2})$ by
construction. Likewise, if $y\in f^{{\scriptscriptstyle-1}}(2)$ then we have
${\mathcal{E}}_{u}(x_{1},y)\geq{\mathcal{E}}_{u}(x_{1},x_{2})$. Since $y$ is
in one set or the other, we must have
${\mathcal{E}}_{u}(x_{1},x_{2})\leq\max\\{{\mathcal{E}}_{u}(x_{1},y),{\mathcal{E}}_{u}(x_{2},y)\\}$
as desired. ∎

######  Proposition 35.

The image of ${\mathcal{E}}$ is precisely the category $\mathbf{Ult}$ of
ultrametrics.

###### Proof.

Following the previous corollary, we need to see that every ultrametric
$(X,u)$ is in the image of ${\mathcal{E}}$ (equivalently, that $u$ is fixed by
${\mathcal{E}}$). Given an ultrametric $(X,u)$, and $x_{1},x_{2}\in X_{1}$
with $x_{1}\neq x_{2}$, it suffices to exhibit a non-expansive map from
$(X,u)$ to $\Delta^{u(x_{1},x_{2})}_{2}$. If $u(x_{1},x_{2})=0$ any map will
do, provided $x_{i}$ is sent to $i$.

The ultrametric property allows us to define an equivalence relation on $X$ by
$y_{1}\sim y_{2}$ if $u(y_{1},y_{2})<u(x_{1},x_{2})$.

We can construct our morphism $f\colon(X,u)\to\Delta^{u(x_{1},x_{2})}_{2}$ as
follows. Since $x_{1}$ and $x_{2}$ are in different equivalence classes we map
everything equivalent to $x_{1}$ to $1$ and everything equivalent to $x_{2}$
to $2$. The remaining equivalence classes can be mapped arbitrarily as long as
the entire equivalence class is sent to the same point in
$\Delta^{u(x_{1},x_{2})}_{2}$.

Because points in different equivalence classes are at least $u(x_{1},x_{2})$
apart, we see that $f$ is non-expansive. ∎

Since we know that single-linkage clustering factors through the unique
projection to the category of ultrametrics (see Carlsson and Mémoli [10]), we
now see that, in fact, the functor ${\mathcal{E}}$ is another description of
this projection. In other words, given a weight $(X,u)$, the weight
${\mathcal{E}}_{u}$ is the maximal ultrametric under $u$. Moreover, we can
compose with the Rips sieving functor
${\mathcal{R}}\colon\mathbf{Weight}\to\mathbf{Sieve}$ and recover the single-
linkage sieve:

$\mathbf{Weight}$$\mathbf{Sieve}$$\mathbf{Ult}$$\mathcal{SL}$${\mathcal{E}}$${\mathcal{R}}$

The construction described in this section gives us a characterization of the
maximal ultrametric ${\mathcal{E}}_{u}$ on $X$ underneath a given weight $u$:

${\mathcal{E}}_{u}(x_{1},x_{2})=\max_{\begin{subarray}{c}A\subset X\\\
x_{1}\in A\\\ x_{2}\in A^{c}\end{subarray}}\min_{\begin{subarray}{c}y_{1}\in
A\\\ y_{2}\in A^{c}\end{subarray}}u(y_{1},y_{2}),$

where $A^{c}=X\setminus A$. In other words, we look at splits $A,A^{c}$ of $X$
which separate $x_{1}$ and $x_{2}$ and take one where the two sets are as far
apart as possible.

Finally, the clustering domain $\mathbf{Ult}$ is characterized (by Lemma 32
and Proposition 35) as the smallest clustering domain containing all two-point
spaces, allowing one to think of hierarchical single linkage clustering as
merely the coarsest among all stationary sieving methods which agree with the
Rips sieve on the two point spaces.

###  3.3. Examples of Clustering Domains

By enriching the setting of functorial clustering to allow non-partition based
methods, we discover that there are many viable clustering domains (and hence
stationary sieving functors via Theorem 28) with various potentially
advantageous properties. Here we present a number of examples that help to
illuminate the ideas presented in the theoretical results above and which
clarify what is, or is not, a clustering domain. Once we have identified some
clustering domains, additional ones can be constructed by taking intersections
(by intersection, we mean the full subcategory of $\mathbf{Weight}$ with
objects given by taking intersection of the objects). We can also take
categories that have the relevant pull-back property under non-expansive maps,
but fail to be $\sup$ closed, and “$\sup$ close” them to obtain a clustering
domain. Even if the pull-back property fails, one can restrict the class of
non-expansive maps to so-called admissible (non-expansive) maps where the
pull-back property holds. This necessarily leads to a less restrictive notion
of functoriality. We discuss all of these ideas below. However, our first
example is more in the way of a counterexample.

######  Example 36 (Cut metrics and tree metrics).

Consider the following metric $d$ on the set $X=\\{1,2,3,4,5\\}$:

$d=\left(\begin{array}[]{ccccc}0&1&1&1&2\\\ 1&0&2&2&1\\\ 1&2&0&2&1\\\
1&2&2&0&1\\\ 2&1&1&1&0\end{array}\right)$

$1$$2$$3$$4$$5$

where $d_{ij}$ is the distance from $i$ to $j$. This metric is the path metric
on the graph pictured above where all the edges have length $1$.

It is well known that $(X,d)$ is not a cut metric (see Definition 29). Using
the machinery developed in Section 3.1, we will see how this simple concrete
example precludes the existence of a functorial projection to the category of
cut metrics. Toward this end, consider now the metrics

$d_{1}=\left(\begin{array}[]{ccccc}0&1&1&1&2\\\\[2.0pt]
1&0&\tfrac{4}{3}&\tfrac{4}{3}&1\\\\[2.0pt]
1&\tfrac{4}{3}&0&\tfrac{4}{3}&1\\\\[2.0pt]
1&\tfrac{4}{3}&\tfrac{4}{3}&0&1\\\\[2.0pt]
2&1&1&1&0\end{array}\right)\qquad\text{ and }\qquad
d_{0}=\left(\begin{array}[]{ccccc}0&1&1&1&0\\\ 1&0&2&2&1\\\ 1&2&0&2&1\\\
1&2&2&0&1\\\ 0&1&1&1&0\end{array}\right)$

which have cut decompositions

$\displaystyle d_{1}$
$\displaystyle=\tfrac{1}{3}\delta_{\\{1,2\\}}+\tfrac{1}{3}\delta_{\\{1,3\\}}+\tfrac{1}{3}\delta_{\\{1,4\\}}+\tfrac{1}{3}\delta_{\\{2,5\\}}+\tfrac{1}{3}\delta_{\\{3,5\\}}+\tfrac{1}{3}\delta_{\\{4,5\\}}$
$\displaystyle d_{0}$
$\displaystyle=\delta_{\\{2\\}}+\delta_{\\{3\\}}+\delta_{\\{4\\}}.$

Then clearly we have $d_{0},d_{1}<d$, with $d=\max\\{d_{0},d_{1}\\}$.

Thus the subcategory $\mathbf{Cut}$ of $\mathbf{Weight}$ is not closed under
taking max, and so is not a clustering domain. This leaves the question,
however, of whether we could “sup-close” the category of cut metrics by
throwing in some additional metric spaces and arrive at some proper
subcategory of $\mathbf{Met}$. The following theorem and its corollaries show
that this is not the case; the reasoning used in the five-point example above
is in fact general. Indeed, only finite maximums are needed to produce any
metric, and the smaller category $\mathbf{Tree}$ of tree metrics is sufficient
to generate all of $\mathbf{Met}$. Before stating the theorem, we recall the
definition of tree metrics (see Dress [18] for more details on tree metrics).

######  Definition 37.

A metric space $(Z,d)$ is said to be a tree if it satisfies

  1. (1)

for every $x,y\in Z$, there is a unique isometric embedding
$\varphi_{xy}\colon[0,d_{xy}]\to Z$ with $\varphi_{xy}(0)=x$ and
$\varphi_{xy}(d_{xy})=y$;

  2. (2)

for every arc $z\colon[0,1]\to Z$, $t\mapsto z_{t}$ and for each $t\in[0,1]$
one has $d_{z_{0}z_{t}}+d_{z_{t}z_{1}}=d_{z_{0}z_{1}}$.

A metric $d^{\prime}$ on a finite set $X$ is said to be a tree metric on $X$,
if $(X,d^{\prime})$ embeds isometrically in some tree $(Z,d)$. The category of
tree metrics $\mathbf{Tree}$ is then the full subcategory of $\mathbf{Met}$
with objects the collection of tree metrics. As above, we will denote the tree
metrics on a fixed finite set $X$ by $\mathbf{Tree}_{X}$.

######  Theorem 38.

Let $X$ be a non-empty finite set. Then the $\max$-closure of the set
$\mathbf{Tree}_{X}$ of tree metrics on $X$ is the set $\mathbf{Met}_{X}$ of
metrics on $X$.

###### Proof.

Since $\mathbf{Met}_{X}$ is $\max$-closed, it suffices to show that every
$d\in\mathbf{Met}_{X}$ and every pair $xy\in\binom{X}{2}$ admit a metric
$d^{\prime}\in\mathbf{Tree}_{X}$ such that $d^{\prime}\leq d$ and
$d^{\prime}_{xy}=d_{xy}$.

Let $\rho$ denote Kuratowski’s isometric embedding of $(X,d)$ in
$\ell^{\infty}(X)$ [35], where for all $z\in X$ we have $\rho\colon
z\mapsto\rho_{z}$ and $\rho_{z}(w)=d(z,w)$. Let
$e_{x}\colon\ell^{\infty}(X)\to\mathds{R}$ denote the evaluation map
$e_{x}(f)=f(x)$ and set

$d^{\prime}_{zw}:=\left|\rho_{z}(x)-\rho_{w}(x)\right|=\left|(e_{x}\circ\rho)(z)-(e_{x}\circ\rho)(w)\right|\,.$

Thus, $d^{\prime}$ is a pull-back of the standard metric on the real line,
hence a tree (semi-) metric. Since $e_{x}$ is non-expansive and $\rho$ is an
isometry we also have $d^{\prime}\leq d$. Finally, at the same time we have

$d^{\prime}_{xy}=|\rho_{x}(x)-\rho_{x}(y)|=|0-d_{xy}|=d_{xy}\,,$

which finishes the proof. ∎

An immediate corollary is the non-existence of clustering projections — and
hence, equivalently, of stationary sieving methods — whose image coincides
(for all underlying sets $X$) with the set of tree metrics:

######  Corollary 39.

If $\mathbf{D}$ is a clustering domain satisfying
$\mathbf{D}_{X}\supseteq\mathbf{Tree}_{X}$ for all $X$, then
$\mathbf{D}_{X}\supseteq\mathbf{Met}_{X}$ for all $X$.

Thus, from the point of view of functorial clustering (if based on the metric
category), the class of tree metrics — the first most accepted (and used)
generalization of the class of dendrograms — is not suitable for
characterizing “clustered” objects. Moreover, there exists no “middle ground”
class of metrics lying between tree metrics and general metrics which could be
used for this purpose. In particular, since we have the containments
$\mathbf{Tree}_{X}\subseteq\mathbf{Cut}_{X}\subseteq\mathbf{Met}_{X}$, there
is no hope of obtaining a sieving method characterized by the class of cut
metrics:

######  Corollary 40.

If $\mathbf{D}$ is a clustering domain satisfying
$\mathbf{D}_{X}\supseteq\mathbf{Cut}_{X}$ for all $X$, then we have
$\mathbf{D}_{X}\supseteq\mathbf{Met}_{X}$ for all $X$.

We now move on to examples of subcategories which are in fact clustering
domains. In Section 3.2, we developed an explicit description of a projection
functor for single-linkage. Although that projection highlights the naturality
of the projection, there is also a computationally efficient algorithm for
producing the maximal ultrametric under a given weight: the SLINK algorithm of
Sibson [38]. On the other hand, the minimum spanning tree approach to single-
linkage clustering in [27] provides an efficient way of producing clusters
(i.e., the $\mathcal{SL}$ sieving functor). Additionally, the resulting sieves
are in this case actually dendrograms, where the sieve itself carries
important geometric features (see section Section 4 below). This leads us to
investigate examples of clustering domains for which:

  1. (i)

there is an efficiently computable projection,

  2. (ii)

the associated sieving functor (after composing the projection with the Rips
functor) is computationally tractable,

  3. (iii)

the associated subcategory of $\mathbf{Sieve}$ has objects with a suitable
geometric characterization.

In this section, we will identify several examples, focusing on the first two
items, while the goal of Section 4 is to explore the possibility of extending
the third.

######  Example 41 (Metric spaces).

The category $\mathbf{Met}$ itself can be considered a clustering domain in
$\mathbf{Weight}$. The canonical projection ${\mathcal{P}}_{\mathbf{Met}}$ in
this case is obtained by replacing the weights by the distance given by the
path metric, i.e. the length of the shortest path between the points. This
projection is then a well-studied algorithm with several standard
computationally efficient approaches. Perhaps most importantly, this example
of a clustering domain gives us a way to produce metrics by intersecting with
other clustering domains. Care must be taken, however, as in general the
projection to an intersection is not as simple as applying one projection and
then the other. The associated sieving functor is not known to have an
efficient implementation, as it requires computing the maximal simplices of
the Rips complex (or equivalently, the maximal cliques of the Rips graph) for
arbitrary metric spaces. A geometric characterization of metric sieves is also
an open question.

######  Example 42 (Inframetrics).

A finite weight space $(X,u)$ will be called a $\rho$-inframetric space if
$u_{xz}\leq\rho\max\\{u_{xy},u_{yz}\\}$ for every $x,y,z$ in $X$ and $\rho\geq
1$.

Note that when $\rho=1$, we recover the ultrametric condition, and that all
metric spaces are $2$-inframetric spaces (but some $2$-inframetrics are not
metrics). It is easy to see that the category of (finite) $\rho$-inframetric
spaces is $\sup$ closed and forms a clustering domain.

For $1<\rho<2$, we can intersect the $\rho$-inframetric spaces with
$\mathbf{Met}$ to obtain a clustering domain which contains inframetrics
inside the category of all metric spaces. This would yield a projection
functor whose associated sieving functor gives a functorial (overlapping)
clustering method refining single-linkage. The authors are not aware of
tractable algorithms for computing the general $\rho$-inframetric projections
(for $\rho>1$) or the associated sieving functors. Moreover, the geometry of
$\rho$-inframetric sieves (those sieves in the image of the associated sieving
functor) does not appear to have a known characterization in the non-
ultrametric case, when $\rho>1$.

In a related vein, we could also work with the $\rho$-relaxed triangle
inequality, where $u_{xz}\leq\rho(u_{xy}+u_{yz})$. The $\rho$-inframetric
inequality implies the $\rho$-relaxed triangle inequality which in turn
implies the $2\rho$-inframetric inequality. The $\rho$-relaxed inequality also
leads to a valid clustering domain.

######  Example 43 ($q$-Metric Spaces).

Another example of a clustering domain is the subcategory $\mathbf{Met}_{q}$
of finite $q$-metric spaces of Segarra et al. defined in [37]. For $1\leq
q\leq\infty$, a $q$-metric space is a weight space $(X,u)$ where $u$ satisfies

$\displaystyle(u_{xz})^{q}\leq(u_{xy})^{q}+(u_{yz})^{q}\text{ for }q<\infty$
or $\displaystyle u_{xz}\leq\max\\{u_{xy},u_{yz}\\}\text{ for }q=\infty.$

When $q=1$ we get ordinary metric spaces and when $q=\infty$ we get
ultrametrics. Note that when $q=2$, we have all triangles being acute. Recall
for ultrametrics all triangles are isosceles with the longest side repeating.
Again it is easy to see that $q$-metric spaces form a clustering domain, and a
primary objective of [37] is to investigate the projection for $q<\infty$
defined by
$({\mathcal{P}}_{\mathbf{Met}_{q}}u)_{xy}=\min_{p\in\mathbb{P}(x,y)}\|p\|_{q}$,
where $u\in\mathbf{Weight}$, $\mathbb{P}(x,y)$ is the set of edge-paths from
$x$ to $y$ in the weighted distance graph, considered as vectors in
$\mathds{R}^{k}$ (with $k$ the length of the path) and $\|\cdot\|_{q}$ the
usual $q$-norm. An efficient algorithm for the sieving functor and a geometric
understanding of $q$-metric sieves are still needed.

######  Example 44 (Discretizations).

Let $\mathbf{Int}$ be the category of finite weight spaces with integer
distances. This is obviously $\sup$ closed in the sense that given any finite
set $X$ with a weight $u$ there exists a unique maximal integer weight under
$u$. When restricting to metrics (i.e., intersecting
$\mathbf{Int}\cap\mathbf{Met}$), we must be careful to first take the integer
floor of the distances given by $u$ and then take the resulting path metric on
$X$ with those integer weights. The latter step is necessary since the floor
of $u$ may not be a metric. Also note that reversing this procedure is not
necessarily the same.

Notice that this example can be generalized in a straightforward way using any
given sequence of non-negative real numbers, providing a mechanism for
discretizing in a way appropriate for a given application that does not
destroy the underlying theoretical framework for clustering. Generically, an
efficient algorithm for the sieving functor is bounded in complexity by an
efficient algorithm for Rips sieving, since combinatorially these will produce
the same sieve.

######  Example 45 (Quotient spaces).

Let $X$ be a fixed finite set and suppose $\sim$ is an equivalence relation on
$X$ with quotient $Z$. Let $\pi\colon X\to Z$ denote the quotient map. Then
$\pi^{\ast}\colon\mathbf{Met}_{Z}\to\mathbf{Met}_{X}$ embeds
$\mathbf{Met}_{Z}$ in $\mathbf{Met}_{X}$ as the set of all metrics satisfying
$w_{xy}=0$ whenever $x\sim y$ in $X$. Observe that
$\pi^{\ast}\mathbf{Met}_{Z}$ is a closed and max-closed subset of
$\mathbf{Met}_{X}$, hence also sup-closed, by Proposition 18. Define
$\mathcal{F}_{X}\colon\mathbf{Met}_{X}\to\mathbf{Met}_{X}$ by
$\mathcal{F}_{X}(w)=\sup\\{u\in\pi^{\ast}\mathbf{Met}_{Z}\mid u\leq w\\}$.
Then $\mathcal{F}_{X}^{2}=\mathcal{F}_{X}$,
$\mathcal{F}_{X}(\mathbf{Met}_{X})=\pi^{\ast}\mathbf{Met}_{Z}$,
$\mathcal{F}_{X}w\leq w$, and $w_{1}\leq w_{2}$ implies
$\mathcal{F}_{X}w_{1}\leq\mathcal{F}_{X}w_{2}$ for all
$w,w_{1},w_{2}\in\mathbf{Met}_{X}$. Any map
$\mathcal{H}\colon\mathbf{Met}_{X}\to\mathbf{Met}_{X}$ satisfying these
conditions must coincide with $\mathcal{F}_{X}$.

For any clustering domain $\mathbf{D}$ contained in $\mathbf{Met}$, we have
the diagram:

$\mathbf{Met}_{Z}$$\mathbf{Met}_{X}$$\mathbf{Met}_{Z}$$\mathbf{Met}_{X}$${\pi^{\ast}}^{-1}\circ\mathcal{F}_{X}$${\pi^{\ast}}$$({\mathcal{P}}_{\mathbf{D}})_{Z}$$({\mathcal{P}}_{\mathbf{D}})_{X}$${\pi^{\ast}}^{-1}\circ\mathcal{F}_{X}$$\mathcal{G}_{X}$

We claim that
$\mathcal{G}_{X}={\pi^{\ast}}^{-1}\circ\mathcal{F}_{X}\circ({\mathcal{P}}_{\mathbf{D}})_{X}\circ{\pi^{\ast}}$
coincides with the map $({\mathcal{P}}_{\mathbf{D}})_{Z}$. Indeed, it
satisfies all $3$ requirements for characterizing
$({\mathcal{P}}_{\mathbf{D}})_{Z}$. Thus $\mathcal{F}_{X}$ is a natural
“quotient operation” on metric spaces that commutes with
${\mathcal{P}}_{\mathbf{D}}$.

Recall that, for any metric $w\in\mathbf{Met}_{X}$ the quotient metric
$\bar{w}$ on the quotient $Z$ is defined as follows (see, for example, Section
$3.3$ in [8]). First, for $A,B\in Z$ one considers ‘paths’ from $A$ to $B$:

$\mathbb{P}(A,B):=\left\\{(x_{o},y_{1},x_{1},\ldots,y_{n-1},x_{n-1},y_{n})~{}\left|~{}\begin{aligned}
&x_{0}\in A,y_{n}\in B,n\in\mathbb{N},\\\ &x_{i}\sim y_{i}\text{ for
}i=1,\ldots,n\end{aligned}\right.\right\\}$

Next, for each $p\in\mathbb{P}(A,B)$ as above one defines its length as
$\ell(p):=\sum_{i=1}^{n}w(x_{i-1},y_{i})$. Finally:

$\bar{w}_{AB}:=\inf_{p\in\mathbb{P}(A,B)}\ell(p).$

Since $\pi^{\ast}(\bar{w})\leq w$ for all $w\in\mathbf{Met}_{X}$,
$\mathcal{F}_{X}(w)$ coincides with $\pi^{\ast}(\bar{w})$. This example is a
bit different from those above, but the interesting point here is that
quotient metrics respect any stationary functorial sieving map, providing yet
another reason to adopt this particular generalization of hierarchical
clustering.

######  Example 46 (Any subcategory of $\mathbf{Weight}$).

We remind the reader that any subcategory of W with the pull-back property can
be $\sup$ closed to give a clustering domain. The difficult issue is to
understand exactly what that closure is and how to construct the projection to
it in a practical way. With the ability to take intersections of clustering
domains, it is clear that there are many such subcategories, providing
different clustering methods. Much more work is needed to characterize
additional useful clustering domains.

##  4\. Injective envelopes and the role of antipodes in clustering

The significance of Corollaries 39 and 40 is in their prohibiting a functorial
compromise between the classical notion of hierarchical clustering and the
geometric clustering maps based on split decompositions championed by the
Dress school. However, the rather complicated relation between split-based
clustering methods and the geometry of injective envelopes inspires hope that
a sieving functor having some of the qualities of split-based maps could be
derived from the geometry of the injective envelopes of spaces chosen to lie
in an appropriately defined clustering domain. Setting aside all technical
details for a separate account, we focus in this section on introducing and
reviewing relevant properties of the clustering domain of $\mathit{A}$-spaces,
motivated by a study of rooted injective envelopes (see below), as well as
some additional clustering sub-domains which, we believe, will prove useful as
a means of constructing new classes of hierarchical classifiers lying between
the category of dendrograms provided by $\mathcal{SL}$ and the category of
unrestricted sieves provided by ${\mathcal{R}}$.

###  4.1. Injective envelopes and clustering

Recall111For a modern, self-cointained account of injective envelopes see
[36]. that a metric space $X$ is said to be injective, if, for any isometry
$i\colon A\to B$, any non-expansive map $f\colon A\to X$ extends to a non-
expansive map $F\colon B\to X$ (in the sense that $F\circ i=f$). As any metric
space $X$ embeds isometrically in an injective one (consider Kuratowski’s
Banach embedding [35]), one asks whether an injective envelope $\epsilon X$
exists, that is: an isometry $e\colon X\to\epsilon X$ into an injective space
$\epsilon X$, through which any embedding of $X$ to an injective space must
factor. The construction of $\epsilon X$, discovered independently by Isbell
[31] and Dress [20], is explicit and easy to describe: first setting

$P(X,d):=\left\\{f\colon X\to\mathds{R}_{{}_{\geq 0}}\,\Big{|}\,\forall{x,y\in
X}\;f(x)+f(y)\geq d_{xy}\right\\}$

one then lets $\epsilon X$ be the subset of those $f\in P(X,d)$ that are
pointwise minimal, inheriting its metric from the $\sup$-metric. The mapping
$e\colon X\to\epsilon X$ defined by $e(x)(y)=d_{xy}$ is the required
embedding.

The injective envelope $e\colon X\to\epsilon X$ provides a canonical way to
minimally “fill-in” $X$ so that as many of its points as possible appear as
endpoints of the complete and hyper-convex [1] metric space $\epsilon X$,
prompting the idea that cluster hierarchies $X$ might be derived from
connectivity properties of $\epsilon X$. For example, computing the cut-point
hierarchy [41] of $\epsilon X$ [21] induces a natural nested tree-like
structure on $X$ in the sense of [15]. The study of the relation between
envelopes and split decompositions by the Dress school [3, 16, 22, 17]
following Bunemann’s work [7] pushes this idea even further, but seems to lose
track of the projective/hierarchical aspects of the clustering problem.

###  4.2. Antipodes

Our present outlook on the usefulness of injective envelopes is motivated by
two well known facts. First, any dendrogram $(X,\theta)$ — when realized as a
metric tree with leaf set $X$, in which the length of each edge is equal to
half the absolute value of the difference in heights between its endpoints —
is naturally isometric to the injective envelope of $(X,u)$, where
$u\in\mathbf{Ult}_{X}$ is the ultra-metric corresponding to the given
dendrogram, $(X,\theta)={\mathcal{R}}(X,u)$. Second, a metric tree is the
geometric realization of a dendrogram if and only if it contains a root
vertex: a point at equal distances from all the points of $X$ (also known as
the leaves of the dendrogram). We are led to investigate (compact metric)
spaces with the property that their injective envelope has a unique root in
the same sense. It turns out that these are precisely the (compact, metric)
spaces where every point has an antipode, or $\mathit{A}$-spaces:

######  Definition 47 (Antipode, $\mathit{A}$-space222The notion “Antipodal
Space” has already been put to extensive good use in [30, 29]).

A metric space $(X,d)$ is defined to be an $\mathit{A}$-space if every $x\in
X$ has an antipode, that is: there exists $y\in X$ satisfying
$d_{xy}=\mathtt{diam}\\!\left(X,d\right)$. Denote the set of
$\mathit{A}$-spaces with underlying set $X$ by $\mathbf{A}^{\\!}_{X}$.

######  Remark 48.

For finite $X$, the collection $\mathbf{A}^{\\!}_{X}$ is a closed subspace of
$\mathbf{Weight}_{X}$, and is clearly $\max$-closed, hence also $\sup$-closed.
Note that $(X,d)\in\mathbf{Ult}$ if and only if every subspace of $(X,d)$ is
an $\mathit{A}$-space, or equivalently, if every triple in $(X,d)$ is an
$\mathit{A}$-space. In particular, an ultrametric space is globally an
$\mathit{A}$-space.

Overall, we conclude that the class of $\mathit{A}$-spaces forms a clustering
domain fibering over the the category of finite sets and surjective set maps.
The surjectivity restriction is necessary, because only for surjective set
maps is it true that the pull-back of an $\mathit{A}$-metric is again an
$\mathit{A}$-metric. The surjectivity restriction is also more than a mere
convenience to accommodate the category-theoretical lingo. In fact, it results
in relaxing the consistency requirements on the corresponding sieving functor
from $\mathbf{Met}$ to $\mathbf{Sieve}$, implying that the resulting
clustering method is consistent with respect to quotients, but not necessarily
consistent with respect to sub-sampling (which corresponds to pull-backs via
injective maps). The property of $X$ being an $\mathit{A}$-space is, in fact,
encoded in the geometry of its injective envelope, which we summarize in the
following theorem. The proof is straightforward from the definition of
$\mathit{A}$-spaces and the geometry of injective envelopes.

######  Theorem 49.

Given a compact metric space $(X,d)$, let $\hat{X}$ denote the extension
$X\cup\\{\infty\\}$, $\infty\notin X$, adding $d_{\infty
x}:=\tfrac{1}{2}\mathtt{diam}\\!\left(X,d\right)$ for all $x\in X$. The
following are equivalent:

  1. (1)

$(X,d)$ is an $\mathit{A}$-space;

  2. (2)

$\epsilon\hat{X}$ is isometric to $\epsilon X$ through an isometry fixing $X$
pointwise;

  3. (3)

$\epsilon X$ contains a point — denoted $\infty_{X}$ — at equal distances to
all points of $X$;

  4. (4)

$\epsilon X$ contains a point at a distance
$\tfrac{1}{2}\mathtt{diam}\\!\left(X,d\right)$ to every $x\in X$.

The point $\infty_{X}$ will be referred to as the root of $(X,d)$ in $\epsilon
X$.

The example of a dendrogram viewed as the injective envelope of an ultra-
metric space $(X,d)$ provides a hint at the class of subspaces one might want
to regard as clusters for the general $\mathit{A}$-space. When $\epsilon X$ is
a dendrogram, each $f\in\epsilon X$ is no more than a specification of
distances to the leaves, with the leaves closest to $f$ — and hence of minimal
value under $f$ — forming the associated ‘descendant’ cluster. See Figure 1
for a comparison in four-point spaces.

Figure 1. Envelopes of the two generic types of $4$-point $\mathit{A}$-spaces
(a,b), seen as ‘fattened’ versions of a dendrogram (c), also drawn in a more
standard representation in (d). The root of each envelope is marked with a red
$\otimes$. For a more meaningful comparison, the metric in (a-c) is chosen to
be the path metric induced from embedding in the $\ell_{1}$ plane.

Denote the minimum value of $f$ by $0pt{f}$, and the set of points where
$0pt{f}$ is achieved by $\mathtt{Min}(f)$. For a general $\mathit{A}$-space we
have:

######  Proposition 50.

Suppose $(X,d)$ is an $\mathit{A}$-space, then every $f\in\epsilon X$
satisfies

$\mathtt{dist}\\!\left(\infty_{X},f\right)=\tfrac{1}{2}\mathtt{diam}\\!\left(X,d\right)-0pt{f}$

Moreover, every $f\in\varepsilon(X,d)$ satisfies

$\max_{z\in X}f(z)+0pt{f}=D$

In particular, $f(x)+f(y)=D$ whenever $x\in\mathtt{Min}(f)$ and $y$ is an
antipode of $x$.

Thus, $\mathit{A}$-spaces form a clustering domain containing the ultrametric
clustering domain and generalizing some pertinent geometric properties of
ultrametrics. Moreover:

######  Remark 51.

Given a metric space $(X,d)$, its projection to the category of
$\mathit{A}$-spaces may be computed recursively as follows. Set $d_{0}=d$ and
for any $t\geq 0$ define the set
$E_{t}=\\{xy\,|\,d_{t}(x,y)=\mathtt{diam}\\!\left(X,d_{t}\right)\\}$. If
$E_{t}$ is an edge cover then stop and return $d_{t}$, as $(X,d_{t})$ is an
$\mathit{A}$-space if and only if $E_{t}$ is an edge cover of $X$. Else, for
each $xy\in E_{t}$ set $d_{t+1}(x,y)$ to equal the second-largest distance in
$(X,d_{t})$; for $xy\notin E_{t}$ set $d_{t+1}(x,y)=d_{t}(x,y)$.

###  4.3. Clustering domains of $\mathit{A}$-spaces

####  4.3.1. $4$-point conditions, and more

Additional classes of $\mathit{A}$-spaces exist, forming clustering domains
which contain the domain of ultra-metrics.

######  Definition 52.

Let $m\geq 3$ be an integer. We say that a metric space $(X,d)$ is an
$\mathit{A}^{m}$-space, if every subset of cardinality $m$ is an
$\mathit{A}$-space.

The following lemma is easy to prove:

######  Lemma 53.

Let $m\geq 3$ be an integer. If $(X,d)$ is an $\mathit{A}^{m}$-space, then it
also an $\mathit{A}^{n}$-space for any $n\geq m$. In particular, a finite
$\mathit{A}^{m}$-space of cardinality at least $m$ is an $\mathit{A}$-space.

It is also straightforward to observe that pull-backs of
$\mathit{A}^{n}$-spaces under injective maps remain $\mathit{A}^{n}$-spaces,
as well as that the set of $\mathit{A}^{n}$-spaces with a fixed finite base
space $X$ is a closed and max-closed subset of $\mathbf{Weight}_{X}$. Thus we
have the following corollary for $\mathit{A}^{n}$-spaces.

######  Corollary 54.

For every integer $m\geq 3$, the class of finite metric spaces that are
$\mathit{A}^{m}$-spaces forms a clustering domain over the category of sets
and injective maps. This clustering domain will be denoted by
$\mathbf{A}^{\\!m}$.

The resulting tower of clustering domains over the category of finite sets and
injective set maps,

$\mathbf{A}^{\\!3}\subsetneq\mathbf{A}^{\\!4}\subsetneq\cdots\subsetneq\cdots\mathbf{A}^{\\!m}\cdots\,,$

is bounded above by the class $\mathbf{A}^{\\!}$ of compact
$\mathit{A}$-spaces, though we must be careful not to view $\mathbf{A}^{\\!}$
as a clustering domain in this context, since the morphism structures of
$\mathbf{A}^{\\!m}$ and $\mathbf{A}^{\\!}$ cannot be reconciled. Similarly,
while $\mathbf{A}^{\\!3}=\mathbf{Ult}$ as a class of objects (see Remark 48),
the inclusion map from $\mathbf{Ult}$ to $\mathbf{A}^{\\!4}$ is not a functor,
as $\mathbf{Ult}$ admits all non-expansive set maps—not just the injective
ones. Because the poset structure of the fibers are consistent (see Remark 5),
however, we are still able to consider the factorization of the projections
${\mathcal{P}}_{\mathbf{A}^{\\!m}}$ through
${\mathcal{P}}_{\mathbf{A}^{\\!}}$.

Thus, the sieving functors from $\mathbf{A}^{\\!m}$ to $\mathbf{Sieve}$ should
be viewed as functors which are only consistent with respect to sub-sampling.
We have yet to obtain a projection algorithm to, say,
$\mathbf{A}^{\\!4}$-spaces, or a geometric characterization of their injective
envelopes.

###  4.4. Discussion: Injective envelopes and practical clustering

The view of a sieving functor as a projection in the weight/metric category
followed by Rips clustering is attractive from the point of view of it
providing a relatively simple and geometrically motivated means for
constructing such functors abstractly, but from a computational standpoint it
is a bit naïve. Indeed, the computational complexity of Rips sieving is,
essentially, prohibitive for large data sets. One therefore is after
clustering domains whose geometric properties enable efficient algorithms for
computing the clustering directly.

In this context, the domain of ultra-metrics provides an extreme example,
where computing the sieve associated with a given metric space is not just
efficient, but can be efficiently distributed/decentralized.

On the other extreme, the domain of $\mathit{A}$-spaces seems to offer little
improvement over Rips sieving of a general metric: every finite metric space
$(X,d)$ extends to an $\mathit{A}$-space by adding just one more point (for
instance, adding a point that has distance $\mathtt{diam}\\!\left(X,d\right)$
from every point in $X$ is sufficient); in other words, though geometrically
well-motivated, the requirement that $(X,d)$ be an $\mathit{A}$-space is not
sufficiently restrictive. The algorithm in Remark 51 suggests that unless the
projection $(X,d_{A})$ of $(X,d)$ to the domain of $\mathit{A}$-spaces yields
a clear and roughly even partitioning of $X$ into clusters at some degree of
resolution, Rips-clustering of $(X,d_{A})$ will still require a search through
a significant portion of the $2^{n}$ possible clusters.

Clearly, this ‘malfunction’ of sieving through $\mathit{A}$-spaces is due to a
lack of some kind of hereditary/hierarchical structure in spaces in this
category: no particular collection of subspaces of an $\mathit{A}$-space is
forced to inherit the $\mathit{A}$-space condition. This motivates the
introduction of the notion of $\mathit{A}^{m}$-spaces, best viewed as a
relaxation of the hereditary class of ultra-metric spaces —
$\mathit{A}^{4}$-spaces being of particular interest, in view of the key role
of $4$-point conditions in the metric clustering literature [7, 20].

Judging from the ultra-metric case, it seems plausible that, for a clustering
domain $\mathbf{D}$, the existence of an efficient sieving algorithm requires
a combination of (1) geometric constraints that force some notion of
“thinness” on $\epsilon(X,d)$ whenever $(X,d)\in\mathbf{D}$; (2) all clusters
of $(X,d)\in\mathbf{D}$ lying in $\mathbf{D}$, similarly to the notion of
excisiveness introduced in [10]; and (3) proper restrictions on the base
morphisms. The extent to which this vague conjecture holds true for
$\mathbf{A}^{\\!m}$, $m\geq 4$, is the subject of ongoing work.

##  5\. Acknowledgements

The authors gratefully acknowledge the support of Air Force Office of Science
Research under the LRIR 15RYCOR153, MURI FA9550-10-1-0567 and FA9550-11-10223
grants, respectively. Additionally, the authors would like to express their
sincere appreciation to the reviewers, whose comments and suggestions have
produced more clarity and precision in the exposition.

## References

  * [1] Nachman Aronszajn and Prom Panitchpakdi.  Extension of uniformly continuous transformations and hyperconvex metric spaces.  Pacific J. Math, 6(3):405–439, 1956.
  * [2] Hans-Jürgen Bandelt and Andreas W. M. Dress.  Weak hierarchies associated with similarity measures: An additive clustering technique.  Bull. Math. Biol., 51(1):133–166, 1989.
  * [3] Hans-Jürgen Bandelt and Andreas W. M. Dress.  A canonical decomposition theory for metrics on a finite set.  Adv. Math., 92:47–105, 1992.
  * [4] Hans-Jürgen Bandelt and Andreas W. M. Dress.  An order theoretic framework for overlapping clustering.  Discrete Math., 136(1–3):21–37, December 1994.
  * [5] Patrice Bertrand.  Set systems and dissimilarities.  European J. Combin., 21:727–743, 2000.
  * [6] Patrice Bertrand and Jean Diatta.  Weak hierarchies: A central clustering structure.  In Fuad Aleskerov, Boris Goldengorin, and Panos M. Pardalos, editors, Clusters, Orders, and Trees: Methods and Applications, Springer Optimization and Its Applications, pages 211–230. Springer New York, 2014.
  * [7] O. Peter Buneman.  The recovery of trees from measures of dissimilarity.  In D. G. Kendall and P. Tautu, editors, Mathematics in the Archaeological and Historical Sciences. Edinburgh University Press, 1971.
  * [8] Dmitri Burago, Yuri Burago, and Sergei Ivanov.  A course in metric geometry, volume 33 of Graduate Studies in Mathematics.  American Mathematical Society, Providence, RI, 2001.
  * [9] Gunnar Carlsson and Facundo Mémoli.  Characterization, stability, and convergence of hierarchical clustering methods.  J. Mach. Learn. Res., 11:1425–1470, 2010.
  * [10] Gunnar Carlsson and Facundo Mémoli.  Classifying clustering schemes.  Found. Comput. Math., 13(1):221–252, 2013.
  * [11] Frédéric Chazal, Steve Oudot, Primoz Skraba, and Leonidas J. Guibas.  Persistence-based clustering in Riemannian manifolds.  J. ACM, 60(6), 2013.
  * [12] Jared Culbertson, Dan P. Guralnik, Jakob Hansen, and Peter F. Stiller.  Consistency constraints for overlapping data clustering.  arxiv preprint arXiv:1608.04331, 2016.
  * [13] Michel Marie Deza and Monique Laurent.  Geometry of cuts and metrics, volume 15 of Algorithms and Combinatorics.  Springer-Verlag, Berlin, 1997.
  * [14] Jean Diatta.  One-to-one correspondence between indexed cluster structures and weakly indexed closed cluster structures.  In Paula Brito, Patrice Bertrand, Guy Cucumel, and Francisco de Carvalho, editors, Selected Contributions in Data Analysis and Classification, Studies in Classification, Data Analysis, and Knowledge Organization, pages 477–482. Springer Berlin Heidelberg, 2007.
  * [15] Warren Dicks and Martin John Dunwoody.  Groups acting on graphs, volume 17.  Cambridge University Press, 1989.
  * [16] A. Dress, K. Huber, and V. Moulton.  Some variations on a theme by Buneman.  Ann. Comb., 1:339–352, 1997.
  * [17] Andreas Dress, Vincent Moulton, Andreas Spillner, and Taoyang Wu.  Obtaining splits from cut sets of tight spans.  Discrete Appl. Math., 161:1409–1420, 2013.
  * [18] Andreas W. M. Dress.  Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces.  Adv. in Math., 53(3):321–402, 1984.
  * [19] Andreas W. M. Dress, Katarina T. Huber, and Vincent Moulton.  Totally split-decomposable metrics of combinatorial dimension two.  Ann. Comb., 5(1):99–112, 2001.
  * [20] Andreas WM Dress.  Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces.  Adv. Math., 53(3):321–402, 1984.
  * [21] Andreas WM Dress, Katharina T Huber, Jacobus Koolen, and Vincent Moulton.  An algorithm for computing virtual cut points in finite metric spaces.  In International Conference on Combinatorial Optimization and Applications, pages 4–10. Springer, 2007.
  * [22] Andreas WM Dress, KT Huber, and Vincent Moulton.  A comparison between two distinct continuous models in projective cluster theory: The median and the tight-span construction.  Ann. Comb., 2(4):299–311, 1998.
  * [23] Herbert Edelsbrunner and John Harer.  Computational topology: an introduction.  American Mathematical Society, 2010.
  * [24] Brian Everitt.  Cluster Analysis.  Wiley series in probability and statistics. Wiley, 5 edition, 2011.
  * [25] Fernando Gama, Santiago Segarra, and Alejandro Ribeiro.  Overlapping clustering of network data using cut metrics.  In 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2015.
  * [26] Fernando Gama, Santiago Segarra, and Alejandro Ribeiro.  Hierarchical overlapping clustering of network data using cut metrics.  IEEE Transactions on Signal and Information Processing over Networks, 2017, 2017.
  * [27] John C. Gower and G. J. S. Ross.  Minimum spanning trees and single linkage cluster analysis.  J. R. Stat. Soc. Ser. C. Appl. Stat., pages 54–64, 1969.
  * [28] W Harvey, O Rübel, V Pascucci, P-T Bremer, and Y Wang.  Enhanced topology-sensitive clustering by Reeb graph shattering.  In Ronald Peikert, Helwig Hauser, Hamish Carr, and Raphael Fuchs, editors, Topological Methods in Data Analysis and Visualization II: Theory, Algorithms, and Applications, Mathematics and Visualization, pages 77–90. Springer Berlin Heidelberg, 2012.
  * [29] Katharina T Huber, Jacobus H Koolen, and Vincent Moulton.  The tight span of an antipodal metric space: part II - geometrical properties.  Discrete Comput. Geom., 31(4):567–586, 2004.
  * [30] Katharina T Huber, Jacobus H Koolen, and Vincent Moulton.  The tight span of an antipodal metric space: part I - combinatorial properties.  Discrete Math., 303(1):65–79, 2005.
  * [31] J. R. Isbell.  Six theorems about injective metric spaces.  Coment. Math. Helv., 39(1):65–76, 1964.
  * [32] Melvin F. Janowitz.  Ordinal and Relational Clustering, volume 10 of Interdisciplinary Mathematical Sciences.  World Scientific, 2010.
  * [33] Nicholas Jardine and Robin Sibson.  Mathematical Taxonomy.  Wiley Series in Probability and Mathematical Statistics: Tracts on Probability and Statistics. Wiley, 1971.
  * [34] Jon Kleinberg.  An impossibility theorem for clustering.  Advances in Neural Information Processing Systems, 15, 2002.
  * [35] Casimir Kuratowski.  Quelques problèmes concernant les espaces métriques non-séparables.  Fundamenta Mathematica, 25(1):534–545, 1935.
  * [36] Urs Lang.  Injective hulls of certain discrete metric spaces and groups.  J. Topol. Anal., 05(03):297–331, 2013.
  * [37] Santiago Segarra, Gunnar Carlsson, Facundo Mémoli, and Alejandro Ribeiro.  Metric representations of network data.  preprint, 2015.
  * [38] Robin Sibson.  SLINK: an optimally efficient algorithm for the single-link cluster method.  The Computer Journal, 16(1):30–34, 1973.
  * [39] Gurjeet Singh, Facundo Mémoli, and Gunnar Carlsson.  Topological methods for the analysis of high dimensional data sets and 3D object recognition.  In Symposium on Point-Based Graphics, pages 91–100, 2007.
  * [40] Bernd Sturmfels and Josephine Yu.  Classification of six-point metrics.  Electron. J. Combin., 11, 2004.
  * [41] L. E. Ward.  Axioms for cutpoints.  In General topology and modern analysis (Proc. Conf., Univ. California, Riverside, Calif., 1980), pages 327–336, New York-London, 1981. Academic Press.
  * [42] Dekang Zhu, Dan P Guralnik, Xuezhi Wang, Xiang Li, and Bill Moran.  Statistical properties of the single linkage hierarchical clustering estimator.  arXiv preprint arXiv:1511.07715, 2015.