14
$\begingroup$

Is there a useful or agreed-upon category of data sets? In particular, I'm thinking about a point cloud and wondering what an acceptable morphism between point clouds "should" be.

Edit/Clarification: In the context of persistent homology, assuming our data set is a subset of $\mathbb{R}^n$, and given an $\varepsilon > 0$, we get an associated simplicial complex given by the Čech nerve associated to this choice of $\varepsilon$ (in particular there is a 1-simplex between two 0-simplices, which are the data points, if the $\varepsilon$-balls centered at those data points intersect, and so on). From this Čech nerve we get the associated Čech complex, from which we can compute the Čech cohomology. Also note that from the Čech nerve we could apply geometric realization to obtain a topological space representing the data points at resolution, $\epsilon$.

Since many of these processes are functors (all but the first?), I was curious if there is a category of data sets so that I can think of the Čech nerve for $\varepsilon$ as the first functor out of the category of data sets.

$\endgroup$
11
  • 10
    $\begingroup$ What exactly do you want to formalize with such a category, and why do you expect category theory to be of any use in this context? The answers to these questions should help you figure out what the answer is. $\endgroup$ Aug 29, 2017 at 16:37
  • 1
    $\begingroup$ Adding on to @TobiasFritz, in what ways are categories like "Sets" or "Graphs" not sufficient? $\endgroup$
    – zzz
    Aug 29, 2017 at 16:53
  • 4
    $\begingroup$ 1/2 In my opinion this sort of question should be given a wide berth. For a variety of practical reasons computer scientists and statisticians are increasingly turning to functional programming as a toolset for constructing and manipulating transformations between data sets, and the more theoretically inclined are turning to category theory as a source of organizing principles in this endeavor - see en.wikibooks.org/wiki/Haskell/Category_theory, for example. In my opinion, they could use some help from mathematicians. $\endgroup$ Aug 30, 2017 at 21:41
  • 5
    $\begingroup$ 2/2 Even if every reasonable attempt to surface functorial structures in data analysis were represented as an answer to this question, it would still not be the largest "big list" question on this site. Voting to reopen. $\endgroup$ Aug 30, 2017 at 21:43
  • 6
    $\begingroup$ @PaulSiegel I agree with the sentiment (have voted to reopen) but I'm not sure the phrase "given a wide berth" is what you meant dictionary.cambridge.org/dictionary/english/… $\endgroup$
    – Yemon Choi
    Aug 31, 2017 at 4:17

4 Answers 4

11
$\begingroup$

A useful category is that of finite metric spaces with morphisms given by maps that do not increase distance. This and subcategories have been used by Carlsson and Mémoli to classify clustering schemes. (In practice one might often want to normalize an ambient finite metric space so that it has diameter 1.)

$\endgroup$
6
  • $\begingroup$ I need to read more about that reference but as of now, the reason why I'm not sure about using this category is that somehow it seems we want to think of our data set as being "dense" in some geometrically well-defined set. Above, I said that I was thinking about topological data analysis but even in good old fashioned linear regression, at some we "decide" that we're going to pretend our future data values or hypothetical data values will lie on a line. $\endgroup$
    – cheyne
    Aug 30, 2017 at 19:59
  • $\begingroup$ It seems in the paper they are saying this is the correct category to study connected components. Which is great! But might not be the most general setting? I don't know, I have some reading to do now, thanks! $\endgroup$
    – cheyne
    Aug 30, 2017 at 20:05
  • $\begingroup$ A difficulty with this category is that the inverses of many bijections which do not increase distance do, in fact, increase distance, and so they are not in the category. In such cases you can't apply a functor $G$ to the composition $f \circ f^{-1} = Id$ to conclude that $Gf$ is an isomorphism, since $G(f^{-1})$ is not defined... To me, having access to this argument in cases of interest is a minimal requirement for a category (of spaces) to be useful, and unfortunately it fails here. $\endgroup$
    – APR
    Aug 28, 2022 at 4:21
  • $\begingroup$ @APR I’m not sure how your comment (on a 5 year old answer) is relevant to the question — how is the lack of inverses in this subcategory an obstacle for the purpose of modeling data sets? $\endgroup$
    – Alec Rhea
    Aug 28, 2022 at 12:41
  • $\begingroup$ For instance, suppose you have the nth roots of unity taken from a unit circle. You'd like to be able to easily deduce that the Cech cohomology of those points at scale r is isomorphic to, say, the Cech cohomology at radius r/2 of the corresponding points taken from a circle with radius 1/2. The map $f$ sending the first set of points to the second decreases distance, and so it is in the category, but the inverse is not. This deprives you of the most obvious argument to show existence of an isomorphism, namely applying the Cech cohomology functor to the expression $f \circ f^{-1} = Id$. $\endgroup$
    – APR
    Aug 28, 2022 at 13:41
6
$\begingroup$

Here's one definition of the category, which may seem reasonable to people used to working with dataframes in R.

Define a data set as a quadruple $(r,c,m,n)$, where:

  • $r$ and $c$ are positive numbers, to be thought of as row and column counts,
  • $m$ is a set-valued $r\times c$ matrix,
  • $n$ is a list of $c$ distinct sets, to be thought of as names for the columns.

Define a morphism of data sets from $(r,c,m,n)$ to $(r',c',m',n')$ to be an ordered pair $(f, \{(a_i, a_i')\})$, with

  • a map $f$ assigning each row of $m$ to a row of $m'$, and
  • an identification of some column names: a possibly empty set of ordered pairs $\{a_i, a_i')\}$, where the $a_i$ are distinct elements of $n$, and the $a_i'$ are distinct elements of $n'$.

Define the composition and identity morphisms in the way that I hope is obvious.

For example, let $D$ be a dataset of names, birthdays, and other identifying information, and let $E$ be a data set of names and temperatures. Let $f:D\rightarrow E$ say the temperature at each person's location, and let $g:D\rightarrow E$ say the temperature where each person was an hour ago.

Then the equalizer of $f$ and $g$ is a list of names and identifying information, for the people who are at the same temperature that they were an hour ago, together with a map matching those people with the corresponding people in $D$.

Update: In the example from the question, if the original data set has $r$ rows, then the data set for the Cech nerve could have $r$ rows and $r$ columns, to indicate whether each pair of rows in the original data set is within $\epsilon$ of each other. In the corresponding Cech nerve morphism, none of the columns of the two data sets are identified, which shows the abstraction of the operation.

$\endgroup$
1
  • 4
    $\begingroup$ I'll add that the notion of a dataframe has counterparts in Python (via the Pandas package) and in the Spark framework (via the Dataframe and Dataset data structures). This formalism is becoming the "standard" way to work with large data sets. $\endgroup$ Aug 30, 2017 at 21:48
1
$\begingroup$

You can consider "point clouds" as elements of the Ran space $\text{Ran}(\mathbf R^n) = \{P\subseteq \mathbf R^n\ :\ 0<|P|<\infty\}$ (named after Ziv Ran, not for any randomness). This has the Hausdorff topology on it, so you can try to get paths $\gamma$ in this space to induce morphisms between the endpoints $\gamma(0)\to \gamma(1)$ of the path.

However, if you want a morphism just to be a set map, having $|\gamma(1)|>|\gamma(0)|$ means at least one point splits in two (or more) along the way, and it is not clear which of the two should be the image of the original point. One way around this is to allow a single path to induce several morphisms. Another way is to consider only "descending" paths, along which points may only collide, but not split (similar to @SteveHuntsman's mention of the Carlsson-Memoli paper, though I haven't read it).

In the latter case, to make your Čech map functorial you need to restrict even more. That is, if $\check C_\epsilon(\gamma(0))$ is a 1-simplex and $\gamma$ moves the two endpoints apart so that $\check C_\epsilon(\gamma(1))$ is two disconnected 0-simplices, there is no obvious simplicial map between the two images. A fix for this would be to extend the notion of "descending" to a partial order of simplicial complexes, (partly) induced by set inclusion. "Higher" is more vertices with less simplices among them and "lower" is less vertices with more simplices connecting them.

$\endgroup$
0
$\begingroup$

The category of Cech closure spaces (a.k.a. pretopological spaces) enables essentially what is described in the Edit/Clarification part of this post. The basic setup is described in the paper

Rieser, Antonio. Cech Closure Spaces: A Unified Framework for Discrete and Continuous Homotopy, Topology and Its Applications, Vol. 296, 2021, https://doi.org/10.1016/j.topol.2021.107613

The construction of a Cech (co)homology functor is an immediate consequence of the results in

Bentley, H. L., Homology and Cohomology for Merotopic and Nearness Spaces, Quaestiones MAthematicae, 6:1-3, 27-47. https://doi.org/10.1016/j.topol.2021.107613

by applying those results to the merotopic structure generated by interior covers of a closure space. (Interior covers are defined below.) However, this is done more explicitly (and, in my opinion, more clearly) for Cech closure spaces in Luis Palacios' 2019 Bachelor's Thesis from the Universidad de Guanajuato, which can be found at https://itarios.github.io/docs/LJPV_MS_Thesis_.pdf

The basic idea is the following. Just as topological spaces have a closure operator which sends a subset $A$ of a topological space $(X,\tau)$ to its topological closure, it's also possible to define useful closure operators which are not idempotent. For example, if one takes a metric space $(X,d)$ and a positive scale $r>0$, then for any $A\subset X$,

$$c(A) := \{x\in X\mid d(x,A)\leq r \}$$

is a perfectly reasonable closure operation, although the resulting structure is no longer topological (in the sense that $\{X - c(A) \mid A\subset X\}$ is no longer a topology). A function $f:(X,c_X) \to (Y,c_Y)$ between closure spaces is said to be continuous (i.e. is a morphism in the category) iff $\forall A\subset X, f(c_X(A)) \subset c_Y(f(A))$. For $r>0$ in the closure space above, this will include many functions which are not topologically continuous. Nonetheless, one can still recover a significant amount of algebraic topology working in such a category.

To construct Cech (co)homology functorially, let $(X,c)$ be a closure space (such as the one constructed from a metric space and a scale above), and define the interior operator $i:\mathcal{P}(X) \rightarrow \mathcal{P}(X)$ for any $A\subset X$ by

$$i(A) := X - c(X - A).$$

One now says that a collection of subsets $\mathcal{U}$ of $X$ is an interior cover of $X$ iff $X$ is covered by the interiors of the sets in $\mathcal{U}$, i.e.

$$ X = \bigcup_{U\in \mathcal{U}} i(U) $$.

You now run the construction of Cech (co)homology using nerves of interior covers of $(X,c)$ in place of open covers of a topological space, and most of the standard properties of Cech (co)homology can be recovered. In particular, the construction is functorial.

A similar kind of functor may also be constructed for Vietoris-Rips (co)homology using the category of semi-uniform spaces instead of closure spaces, although there are some relationships between these two categories. This is described in

Rieser, Antonio. Vietoris-Rips Homology Theory for Semi-Uniform Spaces. https://arxiv.org/abs/2008.05739

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.