# On intrinsic isometries to Euclidean space.

Anton Petrunin

###### Abstract

I consider compact metric spaces which admit intrinsic isometries to Euclidean
$d$-space. The main result roughly states that the class of these spaces
coincides with class of inverse limits of Euclidean $d$-polyhedra.

##  1 Introduction

The _intrinsic isometries_ are defined in section 2; it is a variation of
notion of _path isometry_ , i.e. map which preservs the lengths of curves. Any
intrinsic isometry is a path isometry, the converse does not hold in general.

The following statement is one of the reason we prefer intrinsic isometry.

1.1. Trivial statement. Let $\mathcal{X}$ be a compact metric space which
admits an intrinsic isometry to $d$-dimensional Euclidean space (further
denoted by $\mathbb{E}^{d}$). Then $\mathop{\rm
dim}\nolimits\mathcal{X}\leqslant d$, where $\mathop{\rm dim}\nolimits$
denotes the Lebesgue’s covering dimension.

This statement is proved in section 3. An analogous statement for path
isometry does not hold, see example 4. The Hausdorff dimension can not be
bounded on the similar way. For example, $\mathbb{R}$-tree admits an intrinsic
isometry to $\mathbb{R}$ and it contains compact subsets of arbitrary large
Hausdorff dimension.

Here are some known results on length spaces which admit _intrinsic isometry_
to $\mathbb{E}^{d}$.

1.2. Theorem. Let $\mathcal{R}$ be $d$-dimensional Riemannian space and
$f\colon\mathcal{R}\to\mathbb{E}^{d}$ be a short map111i.e. $1$-Lipschitz map.
Then given $\varepsilon>0$, there is an intrinsic isometry
$\imath\colon\mathcal{R}\to\mathbb{E}^{d}$ such that

$|f(x)\,\imath(x)|_{\mathbb{E}^{d}}<\varepsilon$

for any $x\in\mathcal{R}$.

In particular, any Riemannian $d$-space admits an intrinsic isometry to
$\mathbb{E}^{d}$.

For path isometries, this theorem was proved in [Gromov, 2.4.11], and the same
proof works for intrinsic isometries. Applying this theorem, one can show that
any limit of increasing sequence of Riemannian metrics on a fixed
$d$-dimensional manifold admits an intrinsic isometry to $\mathbb{E}^{d}$.
(The proof is similar to “if”-part of the main theorem.) In particular, any
sub-Riemannian metric on $d$-dimensional manifold admits an intrinsic isometry
to $\mathbb{E}^{d}$.

1.3. Theorem. Let $\mathcal{P}$ be a Euclidean polyhedron and
$f\colon\mathcal{P}\to\mathbb{E}^{d}$ be a short map. Then, given
$\varepsilon>0$, there is a piecewise linear intrinsic isometry
$\imath\colon\mathcal{P}\to\mathbb{E}^{d}$ such that

$|f(x)\,\imath(x)|_{\mathbb{E}^{d}}<\varepsilon$

for any $x\in\mathcal{P}$.

1.4. Corollary. Any $d$-dimensional Euclidean polyhedron admits a piecewise
linear intrinsic isometry to $\mathbb{E}^{d}$.

The corollary was proved in [Zalgaller] for dimension $\leqslant 4$, but a
slight modification of the proof works in all dimensions, see [Krat]. The
2-dimensional case of this theorem was proved in [Krat]. Later, the proof was
extend to all dimensions in [Akopyan]; the proof use a _piecewise linear
analog of Nash–Kuiper theorem_. This theorem was proved in [Brehm], but this
work was left without attention for many years and reproved independently in
[Akopyan–Tarasov].

Iff-condition. Now we describe the main result of the paper.

A compact metric space $\mathcal{X}$ is called _pro-Euclidean space of rank
$\leqslant d$_ if it can be presented as an _inverse limit_
$\mathcal{X}=\varprojlim\mathcal{P}_{n}$ (see section 2) of a sequence of
Euclidean $d$-polyhedra $\mathcal{P}_{n}$.

1.5. Main theorem. A compact metric space $\mathcal{X}$ admits an intrinsic
isometry to $\mathbb{E}^{d}$ if and only if $\mathcal{X}$ is a pro-Euclidean
space of rank $\leqslant d$.

The proof is straightforward. I like the formulation of the theorem; it seems
to be the first case when inverse limits help to solve a natural problem in
metric geometry.

Note that the statement in theorem 1 (in the compact case) is equivalent to
the fact that any compact Riemannian $d$-space is a pro-Euclidean space of
rank $\leqslant d$. The later can be obtained directly from the following
exercise; this way the main theorem provides an alternative proof to theorem 1
in the compact case.

1.6. Exercise. Show that any compact Riemannian space admits a Lipschitz
approximation by Euclidean polyhedra.

A non-example. Let us remind that _Minkowski space_ is finite dimensional real
vector spaces with metric induced by a norm.

1.7. Proposition. Let $\Omega$ be an open subset of Minkowski $d$-space
$\mathbb{M}^{d}$. Assume $\Omega$ admits an intrinsic222In fact the same is
true for path isometry. isometry to $\mathbb{E}^{m}$ then $d\leqslant m$ and
$\mathbb{M}^{d}$ is isometric to a $\mathbb{E}^{d}$.

In particular, the condition 1 on Lebesgue’s dimension is not sufficient.

I’m grateful to A. Akopyan, D. Burago, S. Ivanov and anonymous referee for
helpful letters and discussions.

##  2 Preliminaries

Standard definitions. Given a metric space $\mathcal{X}$ and two points
$x,x^{\prime}\in\mathcal{X}$, we will denote by
$|xx^{\prime}|=|xx^{\prime}|_{\mathcal{X}}$ the distance from $x$ to
$x^{\prime}$ in $\mathcal{X}$.

A _length space_ is a metric space such that for any two points $x,x^{\prime}$
the distance $|xx^{\prime}|$ coincides with the infimum of lengths of curves
connecting $x$ and $x^{\prime}$.

A map $f\colon\mathcal{X}\to\mathcal{Y}$ between metric spaces $\mathcal{X}$
and $\mathcal{Y}$ is called _short_ if for any $x,x^{\prime}\in\mathcal{X}$ we
have

$|f(x)f(x^{\prime})|_{\mathcal{Y}}\leqslant|xx^{\prime}|_{\mathcal{X}}.$

A length space $\mathcal{P}$ is called _Euclidean $d$-polyhedron_ if there is
a finite triangulation of $\mathcal{P}$ such that each simplex is isometric to
a simplex in $\mathbb{E}^{d}$.

Inverse limit. Consider an _inverse system_ of compact metric spaces
$(\mathcal{X}_{n})_{n=0}^{\infty}$ and short maps
$\varphi_{m,n}:\mathcal{X}_{m}\to\mathcal{X}_{n}$ for $m\geqslant n$; i.e.,

  1. 1.

$\varphi_{m,n}\circ\varphi_{k,m}=\varphi_{k,n}$ for any triple $k\geqslant
m\geqslant n$ and

  2. 2.

for any $n$, the map $\varphi_{n,n}$ is identity map of $\mathcal{X}_{n}$.

A compact metric space $\mathcal{X}$ is called _inverse limit of the system
$(\varphi_{m,n},\mathcal{X}_{n})$_ (denoted by
$\mathcal{X}=\varprojlim\mathcal{X}_{n}$) if its underling space consists of
all sequences $x_{n}\in\mathcal{X}_{n}$ such that $\varphi_{m,n}(x_{m})=x_{n}$
for all $m\geqslant n$ and for two such sequences $(x_{n})$ and
$(x^{\prime}_{n})$ the distance is defined by

$|(x_{n})\,(x^{\prime}_{n})|_{\mathcal{X}}=\lim_{n\to\infty}|x_{n}\,x^{\prime}_{n}|_{\mathcal{X}_{n}}.$

If $\mathcal{X}=\varprojlim\mathcal{X}_{n}$, then the map
$\psi_{n}\colon\mathcal{X}\to\mathcal{X}_{n}$, defined by
$\psi_{n}\colon(x_{i})_{i=0}^{\infty}\mapsto x_{n}$ are called _projections_.
Clearly $\psi_{n}=\varphi_{m,n}\circ\psi_{m}$ for all $m\geqslant n$.

Comments. The above definition is equivalent to the usual inverse limit in the
category with class of objects formed by compact metric spaces and class of
morphisms formed by short maps.

Note that inverse limit is not always defined, and if defined it is the result
is compact by definition. (In principle, the category of compact metric spaces
can be extended so that the limit of any inverse system is well defined.)

It is easy to see that inverse limit of length spaces is a length space.

In general, the inverse limit of a system of spaces differ from its
Gromov–Hausdorff limit. For example, consider inverse system
$\mathcal{X}_{n}=[0,1]$ with maps $\varphi_{m,n}(x)\equiv 0$. The inverse
limit of this system is isometric to one-point space, while the
Gromov–Hausdorff limit is isometric to $[0,1]$. Nevertheless, it is easy to
see that if for any $\varepsilon>0$ the images of $\varphi_{m,n}$ form an
$\varepsilon$-net in $X_{n}$ for all sufficiently large $m$ and $n$, then
$\mathcal{X}=\varprojlim\mathcal{X}_{n}$ is isometric to the Gromov–Hausdorff
limit.

Intrinsic isometries and pull back metrics. Let $\mathcal{X}$ and
$\mathcal{Y}$ be metric spaces and $f\colon\mathcal{X}\to\mathcal{Y}$ be
continuous map. Given two points $x,x^{\prime}\in\mathcal{X}$, a sequence of
points $x=x_{0},x_{1},\dots,x_{n}=x^{\prime}$ is called $\varepsilon$-chain
from $x$ to $x^{\prime}$ if $|x_{i-1}x_{i}|\leqslant\varepsilon$ for all
$i>0$. Set

$\mathop{\rm
pull}\nolimits_{f,\varepsilon}(x,x^{\prime})=\inf\\!\left\\{\sum_{i=1}^{n}|f(x_{i-1})f(x_{i})|_{\mathcal{Y}}\right\\}$

where the infimum is taken along all $\varepsilon$-chains $(x_{i})_{i=0}^{n}$
from $x$ to $x^{\prime}$.

Clearly $\mathop{\rm pull}\nolimits_{f,\varepsilon}$ is a pre-metric333i.e. it
satisfies triangle inequality, it is symmetric, non-negative and $\mathop{\rm
pull}\nolimits_{f,\varepsilon}(x,x)=0$, but it might happen that $\mathop{\rm
pull}\nolimits_{f,\varepsilon}(x,x^{\prime})=0$ for $x\not=x^{\prime}$. on
$\mathcal{X}$ and $\mathop{\rm pull}\nolimits_{f,\varepsilon}(x,x^{\prime})$
is non-increasing in $\varepsilon$. Thus, the following (possibly infinite)
limit

$\mathop{\rm pull}\nolimits_{f}(x,x^{\prime})=\lim_{\varepsilon\to
0}\mathop{\rm pull}\nolimits_{f,\varepsilon}(x,x^{\prime})$

is well defined. The pre-metric $\mathop{\rm
pull}\nolimits_{f}\colon\mathcal{X}\times\mathcal{X}\to[0,\infty]$ will be
called _pull back metric_ for $f$.

A map $f\colon\mathcal{X}\to\mathcal{Y}$ between length spaces $\mathcal{X}$
and $\mathcal{Y}$ is an _intrinsic isometry_ if

$|xx^{\prime}|_{\mathcal{X}}=\mathop{\rm pull}\nolimits_{f}(x,x^{\prime})$

for any $x,x^{\prime}\in\mathcal{X}$.

Any intrinsic isometry is a short map. Moreover, it is easy to see that
intrinsic isometry preserves the lengths of curves. The converse does not
hold, see section 4.

2.1. Proposition. Let $\mathcal{X}$ be a compact (or even proper444I.e. all
closed bounded sets in $\mathcal{X}$ are compact.) metric space. Then
existence of intrinsic isometry $f\colon\mathcal{X}\to\mathcal{Y}$ implies
that $\mathcal{X}$ is a length space.

The proof is left to the reader. Note that for general $\mathcal{X}$ it is not
true. Consider two points which connected by countable number of unit
intervals $\mathbb{I}_{n}$ and one interval of length $\frac{1}{2}$; equip the
obtained space with natural intrinsic metric. Let us remove from our space the
interval of length $\frac{1}{2}$. The metric on the remaining space
$\mathcal{X}$ is not intrinsic. Further let us construct a map
$f\colon\mathcal{X}\to\mathbb{R}$ so that the restriction
$f_{n}=f|_{\mathbb{I}_{n}}$ is an intrinsic isometry, $f_{n}(0)=0$,
$f_{n}(1)=\tfrac{1}{2}$ and $f_{n}(x)$ converges uniformly to $\tfrac{x}{2}$.
It is easy to see that $f\colon\mathcal{X}\to\mathbb{R}$ is an intrinsic
isometry.

2.2. Proposition. Let $\mathcal{X}$ and $\mathcal{Y}$ be metric spaces,
$\mathcal{X}$ be compact and the continuous map
$f\colon\mathcal{X}\to\mathcal{Y}$ is such that

$\sup_{x,x^{\prime}\in\mathcal{X}}\mathop{\rm
pull}\nolimits_{f}(x,x^{\prime})<\infty.$

Then given $\varepsilon>0$ there is $\delta=\delta(f,\varepsilon)>0$ such that
for any short map $h\colon\mathcal{X}\to\mathcal{Y}$ such that

$|f(x)\,h(x)|_{\mathcal{Y}}<\delta\ \ \text{for any}\ \ x\in\mathcal{X}$

we have

$\mathop{\rm pull}\nolimits_{f}(x,x^{\prime})<\mathop{\rm
pull}\nolimits_{h}(x,x^{\prime})+\varepsilon$

for any $x,x^{\prime}\in\mathcal{X}$.

The proof is a direct application of the lemma 2.

For a compact metric space $\mathcal{X}$, we denote by $\mathop{\rm
pack}\nolimits_{\varepsilon}\mathcal{X}$ the maximal number of points in
$\mathcal{X}$ on distance $>\varepsilon$ from each other. Clearly $\mathop{\rm
pack}\nolimits_{\varepsilon}\mathcal{X}$ is finite for any $\varepsilon>0$.

2.3. Lemma. Let $\mathcal{X}$ and $\mathcal{Y}$ be metric spaces,
$\mathcal{X}$ is compact and $f,h\colon\mathcal{X}\to\mathcal{Y}$ be two
continuous maps.

Assume for any $x\in\mathcal{X}$, $|f(x)h(x)|<\delta$ then for any
$x,x^{\prime}\in\mathcal{X}$ we have

$\mathop{\rm pull}\nolimits_{f,\varepsilon}(x,x^{\prime})\leqslant\mathop{\rm
pull}\nolimits_{h,\varepsilon}(x,x^{\prime})+4{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\delta{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}\mathop{\rm
pack}\nolimits_{\varepsilon}\mathcal{X}.$

Proof. Assume $\mathop{\rm pull}\nolimits_{h,\varepsilon}(x,x^{\prime})<\ell$,
i.e. there is an $\varepsilon$-chain $\\{x_{i}\\}_{i=0}^{n}$ from $x$ to
$x^{\prime}$ such that

$\sum_{i=1}^{n}|h(x_{i-1})\,h(x_{i})|_{\mathcal{Y}}<\ell.$ $None$

Since $|h(x_{i})f(x_{i})|<\delta$,

$\mathop{\rm
pull}\nolimits_{f,\varepsilon}(x,x^{\prime})\leqslant\sum_{i=1}^{n}|f(x_{i-1})\,f(x_{i})|_{\mathcal{Y}}<\sum_{i=1}^{n}|h(x_{i-1})\,h(x_{i})|_{\mathcal{Y}}+2{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}n{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}\delta$

Assume $n$ is the smallest number for which there is an $\varepsilon$-chain
satisfying $(*)$. It is enough to show that

$n<2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}\mathop{\rm
pack}\nolimits_{\varepsilon}\mathcal{X}.$

If $n\geqslant 2{\hskip 0.5pt\cdot\nobreak\hskip 0.5pt}\mathop{\rm
pack}\nolimits_{\varepsilon}\mathcal{X}$, there are $i$ and $j$ such that
$j-i>1$ and $|x_{i}x_{j}|\leqslant\varepsilon$. Remove from this chain all
elements $x_{k}$ with $i<k<j$; i.e. consider new $\varepsilon$-chain

$x=x_{0},\dots,x_{i-1},x_{i},x_{j},x_{j+1},\dots,x_{n}=x^{\prime}$

By triangle inequality in $\mathcal{Y}$, the new chain satisfies $(*)$; i.e.
$n$ is not the smallest number, a contradiction. ∎

2.4. Proposition. Let $\mathcal{X}$ and $\mathcal{Y}$ be metric spaces,
$\mathcal{X}$ be compact and $\imath\colon\mathcal{X}\to\mathcal{Y}$ be an
intrinsic isometry.

Then given $\varepsilon>0$ there is $\delta=\delta(\imath,\varepsilon)>0$ such
that for any connected set $W\subset\mathcal{X}$

$\mathop{\rm diam}\nolimits\imath(W)<\delta\ \ \Longrightarrow\ \ \mathop{\rm
diam}\nolimits W<\varepsilon.$

Proof. Assume contrary, i.e. there is a sequence of connected subsets
$W_{n}\subset\mathcal{X}$ such that $\mathop{\rm
diam}\nolimits\imath(W_{n})\to 0$ as $n\to\infty$ but $\mathop{\rm
diam}\nolimits W_{n}>\varepsilon$. Thus there are two sequences of points
$x_{n},x_{n}^{\prime}\in W_{n}$ such that
$|x_{n}x_{n}^{\prime}|\geqslant\varepsilon$. Pass to a subsequence of $n$ so
that $W_{n}\to W$ in Hausdorff sense and $x_{n}\to x$, $x_{n}^{\prime}\to
x^{\prime}$. We obtain a closed connected subset $W\subset\mathcal{X}$ with
two distinct points $x$ and $x^{\prime}$ such that $\imath(W)=p$ for some
$p\in\mathcal{Y}$.

Since $W$ is connected, for any $\varepsilon>0$ there is an
$\varepsilon$-chain $(x_{i})_{i=0}^{n}$ from $x$ to $x^{\prime}$ such that
$\imath(x_{i})=p$ for all $i$. Thus, we have $\mathop{\rm
pull}\nolimits_{\imath,\varepsilon}(x,x^{\prime})=0$ for any $\varepsilon>0$;
i.e., $\mathop{\rm pull}\nolimits_{\imath}(x,x^{\prime})=0$, a contradiction.
∎

##  3 The proofs

Proof of the trivial statement (1). Given $\varepsilon>0$ choose
$\delta=\delta(\imath,\varepsilon)$ as in proposition 2. Since $\mathop{\rm
dim}\nolimits\mathbb{E}^{d}=d$, there is a finite open covering
$\\{U_{i}\\}_{i=1}^{n}$ of $\imath(\mathcal{X})$ with multiplicity $\leqslant
d+1$ and such that $\mathop{\rm diam}\nolimits U_{i}<\delta$ for each $i$.

Consider the covering $\\{V_{\alpha}\\}$ of $\mathcal{X}$ by connected
components of $\imath^{-1}(U_{i})$ for all $i$. According to proposition 2,
$\mathcal{X}$ is a length space. In particular, all sets $V_{\alpha}$ are
open. According to proposition 2, $\mathop{\rm diam}\nolimits
V_{\alpha}<\varepsilon$. Clearly multiplicity of $\\{V_{\alpha}\\}$ is at most
$d+1$. Thus, the statement follows. ∎

Proof of “if” in the main theorem (1). Let $\mathcal{X}$ be a pro-Euclidean
space of rank $\leqslant d$. Assume $(\mathcal{P}_{n})_{n=0}^{\infty}$ is a
sequence of $d$-dimensional Euclidean polyhedra and

$\varphi_{m,n}\colon\mathcal{P}_{m}\to\mathcal{P}_{n}$

is an inverse system of short maps such that
$\mathcal{X}=\varprojlim\mathcal{P}_{n}$. Let
$\psi_{n}\colon\mathcal{X}\to\mathcal{P}_{n}$ be the projections.

According to theorem 1, given $\varepsilon_{n+1}>0$ and a piecewise linear
intrinsic isometry $\imath_{n}\colon\mathcal{P}_{n}\to\nobreak\mathbb{E}^{d}$
there is a piecewise linear intrinsic isometry
$\imath_{n+1}\colon\mathcal{P}_{n+1}\to\nobreak\mathbb{E}^{d}$ such that

$|\imath_{n+1}(x)\ \imath_{n}{\circ}\varphi_{n+1,n}(x)|<\varepsilon_{n+1}.$

for any $x\in\mathcal{P}_{n}$. It remains to show that sequence
$\varepsilon_{n}$ can be chosen on such a way that $\imath_{n}{\circ}\psi_{n}$
converges to an intrinsic isometry $\imath\colon\mathcal{X}\to\mathbb{E}^{d}$.

Let us choose $\varepsilon_{n+1}>0$ so that

$\varepsilon_{n+1}<\tfrac{1}{2}\min\\!\left\\{\varepsilon_{n},\delta(\imath_{n},\tfrac{1}{n})\right\\},$

where $\delta(\imath_{n},\tfrac{1}{n})$ as in proposition 2. Clearly,
$\sum_{i}\varepsilon_{i}<\infty$, thus the the following limit exists

$\imath=\lim_{n\to\infty}\imath_{n}\circ\psi_{n},\ \
\imath\colon\mathcal{X}\to\mathbb{E}^{d}.$

Obviously, $\imath$ is short. Further, for any $x\in\mathcal{X}$,

$|\imath(x)\
\imath_{n}{\circ}\psi_{n}(x)|<\sum_{i=n+1}^{\infty}\varepsilon_{i}<\delta(\imath_{n},\tfrac{1}{n}).$

Thus, according to proposition 2,

$\mathop{\rm pull}\nolimits_{\imath}(x,x^{\prime})+\tfrac{1}{n}>\mathop{\rm
pull}\nolimits_{\imath_{n}\circ\psi_{n}}(x,x^{\prime})\geqslant|\psi_{n}(x)\,\psi_{n}(x^{\prime})|_{\mathcal{P}_{n}}.$

Since
$|\psi_{n}(x)\,\psi_{n}(x^{\prime})|_{\mathcal{P}_{n}}\to|xx^{\prime}|_{\mathcal{X}}$
as $n\to\infty$, the map $\imath\colon\mathcal{X}\to\mathbb{E}^{d}$ is an
intrinsic isometry.∎

Proof of “only if” in the main theorem (1). We will give a construction a
polyhedron $\mathcal{P}$ associated to an intrinsic isometry
$\imath\colon\mathcal{X}\to\mathbb{E}^{d}$ and a tiling of $\mathbb{E}^{d}$ by
coordinate $a$-cubes. (The space $\mathcal{P}$ will be glued out of
$a$-cubes.) The construction will be done in such a way that if a tiling
$\tau^{\prime}$ is a subdivision of a tiling $\tau$ then for corresponding
polyhedra $\mathcal{P}^{\prime}$ and $\mathcal{P}$ there will be a natural
intrinsic isometry $\mathcal{P}^{\prime}\to\mathcal{P}$. Thus we will
construct the needed inverse system of polyhedra out of nested subdivisions of
$\mathbb{E}^{d}$.

Take sequences $a_{n}=\tfrac{1}{2^{n}}$ and set $r_{n}=\tfrac{1}{10}{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}a_{n}$. Fix $n$ for a while and consider tiling
of $\mathbb{E}^{d}$ by coordinate $a_{n}$-cubes. Let us construct a Euclidean
polyhedron $\mathcal{P}_{n}$ associated to this tiling.

The image $\imath(\mathcal{X})$ is covered by finite number of such
$a_{n}$-cubes, say $\\{\square_{n}^{i}\\}$. For each $\square_{n}^{i}$,
consider all connected components $\\{W^{ij}_{n}\\}$ of

$B_{r_{n}}(\imath^{-1}(\square_{n}^{i}))\subset\mathcal{X},$

where $B_{r}(S)$ denotes $r$-neighborhood of set $S$.

According to proposition 2, $\mathcal{X}$ is a length space. In particular,
each set $W^{ij}_{n}$ is open and contains a ball of radius $r_{n}$. Thus for
fixed $i$ the collection of open sets $\\{W^{ij}_{n}\\}$ is finite . Therefore
the set of all $\\{W^{ij}_{n}\\}$ for all $\\{\square^{i}_{n}\\}$ forms a
finite open cover of $\mathcal{X}$. For each $W^{ij}_{n}$ make an isometric
copy $\square^{ij}_{n}$ of $\square^{i}_{n}$ and fix an isometry
$\imath^{ij}_{n}\colon\square^{ij}_{n}\to\square^{i}_{n}$. The Euclidean
polyhedron $\mathcal{P}_{n}$, is glued from $\square^{ij}_{n}$ by the
following rule: glue $\square^{i_{1}j_{1}}_{n}$ to $\square^{i_{2}j_{2}}_{n}$
along $(\imath^{i_{2}j_{2}}_{n})^{-1}\circ\imath^{i_{1}j_{1}}_{n}$ iff
$W^{i_{1}j_{1}}_{n}\cap W^{i_{2}j_{2}}\not=\varnothing$. (The map
$(\imath^{i_{2}j_{2}}_{n})^{-1}\circ\imath^{i_{1}j_{1}}_{n}$ sends one of the
faces of $\square^{i_{1}j_{1}}_{n}$ isometrically to a face of
$\square^{i_{2}j_{2}}_{n}$.)

The constructed polyhedron $\mathcal{P}_{n}$ admits a natural piecewise linear
intrinsic isometry $\imath_{n}\colon\mathcal{P}_{n}\to\mathbb{E}^{d}$, defined
as $\imath_{n}(x)=\imath^{ij}_{n}(x)$ if $x\in\square^{ij}_{n}$. Further,
there is uniquely defined intrinsic isometry
$\varphi_{m,n}\colon\mathcal{P}_{m}\to\mathcal{P}_{n}$ for $m\geqslant n$
which satisfies $\imath_{m}=\imath_{n}\circ\varphi_{m,n}$ and

$\varphi_{m,n}(\square^{i^{\prime}j^{\prime}}_{m})\subset\square^{ij}_{n}\subset\mathcal{P}_{n}\
\ \Rightarrow\ \ W^{i^{\prime}j^{\prime}}_{m}\subset
W^{ij}_{n}\subset\mathcal{X}.$

Further, set $\psi_{n}\colon\mathcal{X}\to\mathcal{P}_{n}$ to be intrinsic
isometry which uniquely determined by $\imath_{n}\circ\psi_{n}=\imath$ and

$\psi_{n}(x)\in\square^{ij}_{n}\subset\mathcal{P}_{n}\ \ \Rightarrow\ \ x\in
W^{ij}_{n}\subset\mathcal{X}.$

Clearly, $\mathcal{P}_{n}$ together with $\varphi_{m,n}$ form an inverse
system and $\psi_{n}=\varphi_{m,n}\circ\psi_{m}$ for any pair $m\geqslant n$.

In order to prove that $\mathcal{X}=\varprojlim\mathcal{P}_{n}$, it only
remains to show that

$|xx^{\prime}|_{\mathcal{X}}\leqslant\lim_{n\to\infty}|\psi_{n}(x)\,\psi_{n}(x^{\prime})|$
$None$

for all $x,x^{\prime}\in\mathcal{X}$.

Given a subset $K\subset\mathcal{P}_{n}$, let us denote by
$K^{*}\subset\mathcal{X}$ the union of all $W^{ij}_{n}\subset\mathcal{X}$ such
that $\square^{ij}_{n}\cap K\not=\varnothing$. Clearly, if $K$ is connected
then so is $K^{*}$. More over, $\imath(K^{*})\subset
B_{r_{n}}(\imath_{n}(K))$. Thus, from proposition 2, we have that for any
$\varepsilon>0$ we can find $\delta>0$ such that

$r_{n}+\mathop{\rm diam}\nolimits K<\delta\ \ \Longrightarrow\ \ \mathop{\rm
diam}\nolimits K^{*}<\varepsilon$ $None$

Assume $(*)$ is wrong, then one can choose $x,x^{\prime}\in\mathcal{X}$ and
$\varepsilon,\ell>0$ so that

$\mathop{\rm
pull}\nolimits_{\imath,\varepsilon}(x,x^{\prime})>\ell>|\psi_{n}(x)\,\psi_{n}(x^{\prime})|_{\mathcal{P}_{n}}$
$None$

for all $n$. In particular, for all $n$ there is a path
$\gamma_{n}\colon[0,1]\to\mathcal{P}_{n}$ from $\psi_{n}(x)$ to
$\psi_{n}(x^{\prime})$ with length $<\ell$. Choose
$\delta=\delta(\imath,\varepsilon)$ as in proposition 2. Let $0=\nobreak
t_{0}<\nobreak t_{1}<\nobreak\dots<t_{m}=1$ be such that

$\mathop{\rm diam}\nolimits\gamma([{t_{i-1}},{t_{i}}])<\tfrac{\delta}{2}.$
$None$

Clearly one can assume that $m\leqslant 2{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\lceil\tfrac{\ell}{\delta}\rceil$. For each $t_{i}$ choose a point
$x_{i}\in\nobreak\gamma(t_{i})^{*}\subset\mathcal{X}$; clearly

$|\imath(x_{i})\ \imath_{n}{\circ}\gamma(t_{i})|_{\mathbb{E}^{d}}<2{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}a_{n}.$ $None$

Note that $x_{i-1},x_{i}\in\gamma([t_{i-1},t_{i}])^{*}$. Thus,
$(\mathrel{\vbox{\offinterlineskip\hbox{${*}{*}$}\hbox{${*}{*}$}}})$ and
$(**)$ imply that

$|x_{i-1}x_{i}|<\mathop{\rm
diam}\nolimits\gamma_{n}([t_{i-1},t_{i}])^{*}<\varepsilon$

for all large $n$. Thus $x_{i}$ forms an $\varepsilon$-chain from $x$ to
$x^{\prime}$, and $(\mathrel{\vbox{\offinterlineskip\hbox{$\mkern
4.5mu{*}{*}$}\hbox{${*}{*}{*}$}}})$ implies

$\displaystyle\mathop{\rm pull}\nolimits_{\imath,\varepsilon}(x,x^{\prime})$
$\displaystyle\leqslant\sum_{i=1}^{m}|\imath(x_{i-1})\,\imath(x_{i})|<$
$\displaystyle<\sum_{i=1}^{m}|\imath_{n}{\circ}\gamma_{n}(t_{i-1})\
\imath_{n}{\circ}\gamma_{n}(t_{i})|+4{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}a_{n}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\lceil\tfrac{\ell}{\delta}\rceil<$ $\displaystyle<\ell+4{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}a_{n}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\lceil\tfrac{\ell}{\delta}\rceil$

which contradicts $(\mathrel{\vbox{\offinterlineskip\hbox{$\mkern
4.5mu{*}$}\hbox{${*}{*}$}}})$ for large enough $n$. ∎

Remark. In the constructed inverse system $(\varphi_{m,n},\mathcal{P}_{n})$,
the images of $\varphi_{m,n}$ form a $\sqrt{d}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}a_{n}$-net in $\mathcal{P}_{n}$. It follows that the space $\mathcal{X}$
is isometric to the Gromov–Hausdorff limit of $\mathcal{P}_{n}$ (see also
section 2).

Proof of proposition 1. The inequality $d\leqslant m$ follow from trivial
statement 1. In the proof of the second part, we use the following two
statements:

  1. 1.

Assume $\imath\colon\Omega\subset\mathbb{M}^{d}\to\mathbb{E}^{m}$ is an
intrinsic isometry, then it is a Lipschitz map for a Euclidean structure on
$\Omega$. Thus, according to Rademacher’s theorem (see [Federer, 3.1.6]) the
differential $d_{p}\imath$ is well defined almost all $p\in\Omega$.

  2. 2.

For any curve $\gamma(t)$ with natural parameter in a metric space, we have
that for almost all values of parameter $t_{0}$ we have

$|\gamma({t_{0}})\,\gamma({t_{0}+\varepsilon})|=\varepsilon+o(\varepsilon),$

see [BBI, 2.7.5].

Let us denote by $\|{*}\|$ the norm which induces metric on $\mathbb{M}^{d}$.
Fix $u$ so that $\|u\|=1$. Consider pencil of lines of the form $p+u{\hskip
0.5pt\cdot\nobreak\hskip 0.5pt}t$ in $\Omega$. Two statements above imply that
$|d_{p}\imath(v)|\buildrel\hbox{\tiny\it
a.e.}\over{=\joinrel=}\nobreak\|{v}\|$ Hence we obtain parallelogram identity

$2{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}\\!\left(\|u\|^{2}+\|v\|^{2}\right)=\|u+v\|^{2}+\|u-v\|^{2}$

is satisfied for any two vectors $v$ and $w$. I.e. the norm $\|{*}\|$ is
Euclidean. ∎

##  4 About path isometries

In this section we will relate the notion of intrinsic isometry defined in
section 2 with more common (but less natural) notion of path and weak path
isometries.

4.1. Definition. Let $\mathcal{X}$ and $\mathcal{Y}$ be two length spaces. A
map $\imath\colon\mathcal{X}\to\mathcal{Y}$ is called

  1. 1.

_path isometry_ if for any path $\gamma\colon[0,1]\to\mathcal{X}$ we have

$\mathop{\rm length}\nolimits\gamma=\mathop{\rm
length}\nolimits\imath\circ\gamma.$

  2. 2.

_weak path isometry_ if for any rectifiable path
$\gamma\colon[0,1]\to\mathcal{X}$ we have

$\mathop{\rm length}\nolimits\gamma=\mathop{\rm
length}\nolimits\imath\circ\gamma.$

As it was noted in section 2, any intrinsic isometry is a path isometry (and
therefore, a weak path isometry). Next we will show that converse does not
hold. Similar counterexamples for weak path isometries are much simpler: one
can take a left-invariant sub-Riemannian metric $d$ on Heisenberg group $H$
then factorizing by center gives an weak path isometry
$(H,d)\to\mathbb{E}^{2}$ (which is not a path isometry and thus not an
intrinsic isometry).

4.2. Example. There is a length space $\mathcal{X}$ and a path isometry
$f\colon\mathcal{X}\to\mathbb{R}$ such that $f^{-1}(0)$ is connected
nontrivial subset.

Moreover, in such example the Lebesgue covering dimension of $f^{-1}(0)$ can
be made arbitrary large.

In particular, an analog of 1 does not hold for path isometries.

The following construction was suggested by D. Burago; it is based on two
ideas: (1) the construction in [BIS, 3.1], (2) the construction of _pseudo-
arc_ given in [Knaster] (see also the survey [Lewis] and references therein).
In fact, for the first part of theorem $f^{-1}(0)$ will be homeomorphic to a
pseudo-arc and for the second part $f^{-1}(0)$ will be homeomorphic to a
product of pseudo-arcs.

Proof. The space $\mathcal{X}$ will be a completion $\bar{\Gamma}$ of certain
metric graph555i.e., locally finite graph with intrinsic metric, such that
each edge is isometric to a real interval. $\Gamma$.

First let us describe the construction of $f$ modulo a construction of
$\Gamma$. Set $\grave{\Gamma}=\bar{\Gamma}\backslash\Gamma$. Consider map
$f\colon\bar{\Gamma}\to\mathbb{R}$, where $f(x)$ is the distance from $x$ to
$\grave{\Gamma}$. Then $f$ is a path isometry on $\Gamma$ and
$f(\grave{\Gamma})=0$. To finish that proof we will have to construct $\Gamma$
on such a way that

  1. (i)

$\grave{\Gamma}$ is connected and contains more than one point;

  2. (ii)

$f$ is a path isometry on whole $\bar{\Gamma}$ (not only on $\Gamma$).

$\mathbb{I}$$\mathbb{J}$$\varepsilon$Graph of an$\varepsilon$-crooked map.

Construction of $\Gamma$. For two real intervals $\mathbb{I}$ and
$\mathbb{J}$, a continuous onto map $h\colon\mathbb{I}\to\mathbb{J}$ will
called _$\varepsilon$ -crooked_ if for any two values $t_{1}<t_{2}$ in
$\mathbb{I}$ there are values $t_{1}<\nobreak t^{\prime}_{2}<\nobreak
t^{\prime}_{1}<\nobreak t_{2}$ such that
$|h(t_{i}^{\prime})-h(t_{i})|\leqslant\varepsilon$ for $i\in\\{1,2\\}$. The
existence of $\varepsilon$-crooked map for any given $\mathbb{I}$ and
$\varepsilon>0$ is easy to prove by induction on
$n=\lceil\tfrac{1}{\varepsilon}{\hskip 0.5pt\cdot\nobreak\hskip
0.5pt}{\mathop{\rm length}\nolimits\mathbb{J}}\rceil$.

Let us fix a sequence of real intervals $\mathbb{J}_{n}$ with short
$\tfrac{1}{2^{n}}$-crooked maps
$h_{n}\colon\mathbb{J}_{n}\to\mathbb{J}_{n-1}$. The topological inverse limit
$\mathbb{J}_{\infty}=\varprojlim\mathbb{J}_{n}$ is a connected compact which
has no nontrivial paths.

We can think of $\mathbb{J}_{n}$ as a (linear) metric graph with length of
each edge $\leqslant\tfrac{1}{2^{n}}$. Construct a graph $\Gamma$ from a
disjointed union $\sqcup_{n}\mathbb{J}_{n}$ by joining each vertex $v$ of
$\mathbb{J}_{n}$ to a vertex of $\mathbb{J}_{n-1}$ which is closest to
$h_{n}(v)$ by an edge of length $\tfrac{1}{2^{n}}$. Then $\grave{\Gamma}$ is
homeomorphic to $\mathbb{J}_{\infty}$; thus we get (i).

Let us denote by $\Gamma_{n}$ the finite subgraph of $\Gamma$ formed by all
vertexes in $\mathbb{J}_{1},\mathbb{J}_{2},\dots,\mathbb{J}_{n}$. Note that
there is a short map $\Gamma_{n}\to\Gamma_{n-1}$ which is identity on
$\Gamma_{n-1}$. It follows that for any path
$\alpha\colon[0,1]\to\bar{\Gamma}$ we have that the total length of
$\alpha\backslash\grave{\Gamma}$ is at least
$|\alpha(0)\,\alpha(1)|_{\bar{\Gamma}}$. Thus (ii) follows.

Second part. We construct a graph $\Gamma^{(m)}$ to make
$\grave{\Gamma}^{(m)}$ homeomorphic to a product on $m$ copies of
$\grave{\Gamma}$.

We will do the case $m=2$; the others are analogous. The set of vertexes of
$\Gamma^{(2)}$ is disjoint union $\sqcup_{n}(\mathop{\rm
Vert}\mathbb{J}_{n}\times\mathop{\rm Vert}\mathbb{J}_{n})$, where $\mathop{\rm
Vert}\mathbb{J}_{n}$ denotes the set of vertexes of $\mathbb{J}_{n}$. We
connect two vertexes $(x,y)\in\mathop{\rm Vert}\mathbb{J}_{n}\times\mathop{\rm
Vert}\mathbb{J}_{n}$ and $(x^{\prime},y^{\prime})\in\mathop{\rm
Vert}\mathbb{J}_{k}\times\mathop{\rm Vert}\mathbb{J}_{k}$ iff the pairs
$(x,x^{\prime})$ and $(y,y^{\prime})$ were connected in $\Gamma$; the length
of this edge must be maximum of lengths of edges $xx^{\prime}$ and
$yy^{\prime}$ (we assume that a vertex is connected to it-self by an edge of
length $0$).

Clearly, there is a homeomorphism
$\grave{\Gamma}^{(2)}\to\grave{\Gamma}\times\grave{\Gamma}$. Note that there
are two short coordinate projections
$\varsigma_{1},\varsigma_{2}\colon\Gamma^{(2)}\to\Gamma$. Thus for any path
$\alpha\colon[0,1]\to\bar{\Gamma}^{2}$, we have that total length of
$\alpha\backslash\grave{\Gamma}$ is at least as big as
$\max_{i}|\varsigma_{i}{\circ}\alpha(0)\,\varsigma_{i}{\circ}\alpha(1)|$. That
ensures that pulled back metric on $\grave{\Gamma}^{(2)}$ is bi-Lipschitz to
the product metric on $\grave{\Gamma}\times\grave{\Gamma}$. ∎

##  5 Comments and open questions

A length space $\mathcal{M}$ is called _Minkowski $d$-polyhedron_ if there is
a finite triangulation of $\mathcal{M}$ such that each simplex is isometric to
a simplex in a Minkowski space. Correspondingly, a compact metric space
$\mathcal{X}$ is called _pro-Minkowski space_ of rank $\leqslant d$ if it can
be presented as an inverse limit of Minkowski $d$-polyhedra.

5.1. Question. Is it true that any length space with Lebesgue’s covering
dimension $d$ is a pro-Minkowski space of rank $d$?

Or even more specific:

5.2. Question. Is it true that any metric space which homeomorphic to a disk
is a pro-Minkowski space of rank $2$?

One can reformulate it philosophically: Is there any essential difference
between Finsler metric and general metric on $n$-manifold? This question was
asked by D. Burago; it was also original motivation for this paper (see also a
related example [BIS, theorem 1]).

If one removes restriction on dimension, then the answer to the above question
is YES. Namely, the following exercise can be solved by using Kuratowski
embedding $x\mapsto\mathop{\rm dist}_{x}$.

5.3. Exercise. Show that any compact length space is an inverse limit of
Minkowski polyhedra $\mathcal{M}_{n}$ with $\mathop{\rm
dim}\nolimits\mathcal{M}_{n}\to\infty$.

5.4. Question. Is it true that any path isometry from a closed Euclidean ball
to Euclidean space is an intrinsic isometry?

## References

  * [Akopyan] Akopyan, A. V., A piecewise linear analogue of Nash–Kuiper theorem, a preliminary version (in Russian) can be found on www.moebiuscontest.ru
  * [Akopyan–Tarasov] Akopyan, A. V.; Tarasov, A. S. A constructive proof of Kirszbraun’s theorem. (Russian) Mat. Zametki 84 (2008), no. 5, 781–784.
  * [BIS] Burago, D.; Ivanov, S.; Shoenthal, D. Two counterexamples in low dimensional length geometry, St.Petersburg Math. J. Vol. 19 (2008), No. 1, Pages 33–43
  * [BBI] Burago, D.; Burago, Yu.; Ivanov, S., A course in metric geometry. Graduate Studies in Mathematics, 33. American Mathematical Society, Providence, RI, 2001. xiv+415 pp. ISBN: 0-8218-2129-6
  * [Brehm] Brehm, U., Extensions of distance reducing mappings to piecewise congruent mappings on $R^{m}$. J. Geom. 16 (1981), no. 2, 187–193.
  * [Federer] Federer, H., Geometric Measure Theory, Springer, 1969.
  * [Knaster] Knaster, B. Un continu dont tout sous-continu est indécomposable. Fundamenta math. 3, 247–286 (1922).
  * [Krat] Krat, S. Approximation Problems in Length Geometry, Thesis, 2005
  * [Lewis] Lewis, Wayne The pseudo-arc. Bol. Soc. Mat. Mexicana (3) 5 (1999), no. 1, 25–77.
  * [Gromov] Gromov, M., Partial differential relations, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) 9, Springer-Verlag, Berlin, 1986, x+363,
  * [Zalgaller] Zalgaller, V. A. Isometric imbedding of polyhedra. (Russian) Dokl. Akad. Nauk SSSR 123 1958 599–601.


11institutetext: Faculty of Mathematics and Computer Science, Eindhoven
University of Technology
11email<EMAIL_ADDRESS>11email<EMAIL_ADDRESS>
# From strings to data science: a practical framework for automated string
handling

John W. van Lith (🖂)  Joaquin Vanschoren

###### Abstract

Many machine learning libraries require that string features be converted to a
numerical representation for the models to work as intended. Categorical
string features can represent a wide variety of data (e.g., zip codes, names,
marital status), and are notoriously difficult to preprocess automatically. In
this paper, we propose a framework to do so based on best practices, domain
knowledge, and novel techniques. It automatically identifies different types
of string features, processes them accordingly, and encodes them into
numerical representations. We also provide an open source Python
implementation111Open-source library: https://github.com/ml-tue/automated-
string-cleaning to automatically preprocess categorical string data in tabular
datasets and demonstrate promising results on a wide range of datasets.

###### Keywords:

Data cleaning String features Automated data science.

##  1 Introduction

Datasets acquired from the real world often contain categorical string data,
such as zip codes, names, or occupations. Many machine learning algorithms
require that such string features be converted to a numerical representation
to work as intended. Depending on the type of data, specific processing is
required. For example, geographical string data (e.g., addresses) may be best
expressed by latitudes and longitudes. Data scientists are required to
manually preprocess such unrefined data, requiring a significant amount of
time, up to 60% of their day [10]. Automated data cleaning tools exist but
often fail to robustly address the wide variety of categorical string data.
This paper presents a framework that systematically identifies various types
of categorical string features in tabular datasets and encodes them
appropriately. We also present an open-source Python implementation that we
evaluate on a wide range of datasets.

##  2 Challenges and Related Work

Our framework addresses a range of challenges. First, _type detection_ aims to
identify predefined ‘types’ of string data (e.g., dates) that require special
preprocessing. Probabilistic Finite-State Machines (PFSMs) [9] are a practical
solution based on regular expressions and can produce type probabilities. They
can also detect missing or anomalous values, such as numeric values in a
string column.

_Statistical type inference_ predicts a feature’s statistical type (e.g.,
ordinal or categorical) based on the intrinsic data distribution. Valera et
al. [29] use a Bayesian approach to discover whether features are ordinal,
categorical, or real-valued, although some manual assessment is still needed.
Other techniques that predict classes using features of the data use random
forest and gradient boosting classifiers [11], which could be leveraged to
achieve class prediction for the statistical type.

_Encoding techniques_ convert categorical string data to numeric values, which
is challenging because there may be small errors (e.g., typos) and intrinsic
meaning (e.g., a time or location). Cerda et al. [7, 8] use string similarity
metrics and min-hashing to tackle morphological variants of the same string.
Geocoding APIs (e.g., pgeocode and geopy) can convert geographical strings to
coordinates [3, 5]. For ordinal string data, heuristic approaches exist that
could determine order based on antonyms, superlatives, and quantifiers, e.g.
using WordNet [22] or sentiment intensity analyzers (e.g. VADER, TextBlob, and
FlairNLP) [6, 13, 20].

Methods have been proposed that recognize, categorize, and process different
string entities based on regular expressions [28] or domain knowledge that can
outperform human experts [12, 14]. Data cleaning tools exist that are manually
operated [1, 2, 4], semi-automated [23, 30], or fully automated [15, 16, 17,
21, 26]. At present, however, these automated tools do not focus on string
handling [15, 16, 26] or they focus on specific steps such as error correction
[17, 21].

Figure 1: The overall workflow of the framework.

##  3 Methodology

Our framework, shown in Fig. 1, is designed to detect and appropriately encode
different types of string data in tabular datasets. First, we use PFSMs to
infer whether a column is numerical, a known type of string feature (e.g., a
date), or any other type of ‘standard’ string data. Based on this first
categorization, appropriate missing value and outlier handling methods are
applied to the entire dataset to repair inconsistencies. Next, columns with
recognized string types go through intermediate type-specific processing,
while the remaining columns are classified based on their statistical type
(e.g., nominal or ordinal). Finally, the data is encoded by applying the most
fitting encoding for each feature.

###  3.1 String feature inference

In the first step, we build on PFSMs and the ptype library [9]. We created
PFSMs based on regular expressions for nine types of string features:
coordinates, days, e-mail addresses, filepaths, months, numerical strings,
sentences, URLs, and zip codes. A detailed description for each of these can
be found in Appendix 0.A.

###  3.2 Handling missing values and outliers

Next, missing values are imputed based on the missingness of the data
according to Little’s test [19, 27] (missing at random, missing not at random,
missing completely at random) using mean/mode imputation or a multivariate
imputation technique [24]. Minor typos are corrected using string metrics
[18], and data type outliers are corrected if applicable to ensure robustness
in the remaining steps.

###  3.3 Processing inferred string features

Next, we perform intermediate processing of all the string types identified by
the PFSMs. First, we simplify the strings, for instance, by only taking the
nouns in sentences. Second, we assign or perform specific encoding techniques,
such as replacing a date with year-month-day values. Third, we include
additional information, such as fetching latitude and longitude values for zip
codes.

Figure 2: Workflow to predict the statistical type for a given string column.

###  3.4 Statistical type prediction

String features not identified by the PFSMs are marked as ‘standard’ strings.
For these, we infer their statistical type, i.e., whether they contain ordered
(ordinal) data or unordered (nominal) data. The prediction is based on eight
properties extracted from the feature, shown in Fig. 2, including the
uniqueness of the string values, whether the column name or values suggests
ordinality, and whether a GloVe word embedding of the string values shows
clear relationships between the values. The rationale behind these is
explained in Appendix 0.B. These features are fed to a gradient boosting
classifier to predict the statistical type. This classifier was trained on
real-world features, manually annotated, listed in Appendix 0.C.

###  3.5 Encoding

Finally, an appropriate encoding is applied for each categorical string
feature. For the string types identified by the PFSMs, a predefined encoding
is applied, per Appendix 0.A. For nominal data, we use category encoders and
target encoding due to their robustness to morphological variants and high
cardinality features [7, 8]. We apply the similarity, Gamma-Poisson, and min-
hash encoders when the cardinality is below 30, below 100, and at least 100,
respectively. For ordinal data, the ordering is defined by a text sentiment
intensity analyzer (FlairNLP [6]) that converts string values (e.g., very bad,
very good) to an ordered encoding.

Figure 3: Relative mean performance of our framework against baseline
preprocessing. The smaller dots represent the scores of individual folds of
each method.

##  4 Evaluation

We evaluate our framework and its individual components on a range of real-
world datasets with categorical string features, listed in Appendix 0.C. We
evaluate the downstream performance of gradient boosting models trained on the
encoded data. Boosting models are intrinsically robust against high-
dimensional data, thus allowing a fairer comparison. We use stratified 5-fold
cross-validation, and measure accuracy for classification tasks and MAE for
regression tasks.

Global framework evaluation. First, we evaluate the framework as a whole and
compare it to a baseline where the data is manually preprocessed using
mean/mode imputation and ordinal or target encoding for the categorical string
features. Fig. 3 shows the relative performance differences for each of the
five folds and their mean. These results indicate that our framework performs
well on real-world data. On the winemag-130k dataset, the automated encoding
proves suboptimal, which is likely tied to the specific heuristics used.

Feature type inference. In Table 1, we compare the predictions of our PFSMs
against the ground truth feature types. Most PFSMs report perfect accuracy.
Filepaths and sentences are detected with 70-80% accuracy, since the exact
format of such data can be unexpected. Outliers are also detected correctly,
except for sentence PFSMs, where out of the 130217 entries, 42158 entries were
false negatives, which is certainly a point for improvement.

String feature |  | Nr. of
---
columns
| Nr. of correctly
---
inferred columns
Accuracy |  | Nr. of false
---
negative outliers
| Ratio of false
---
negative outliers
Coordinate | 2 | 2 | 1.0 | 0 | -
Day | 1 | 1 | 1.0 | 0 | -
E-mail | 4 | 4 | 1.0 | 0 | -
Filepath | 5 | 4 | 0.80 | 0 | -
Month | 3 | 3 | 1.0 | 0 | -
Numerical | 6 | 6 | 1.0 | 0 | -
Sentence | 4 | 3 | 0.75 | 42158 | 0.32
URL | 4 | 4 | 1.0 | 0 | -
Zip code | 3 | 3 | 1.0 | 0 | -

Table 1: Results of string feature inference using PFSMs. Figure 4: Difference
in performance metrics (mean accuracy/MAE, preprocessing time, and training
time) with and without processing of known string feature types. The smaller
dots represent individual folds or runs.

Processing inferred string features. Fig. 4 compares the performance of our
framework with and without intermediate processing for the string feature
types identified by the PFSMs. For some features, this processing causes a 10%
performance improvement, while on others, it remains about the same. This
processing does require extra processing time, caused by API latency and text
processing, yet it seems worth the extra time for zip codes and sentences.
Moreover, the reduced string complexity (removing redundant words) and
conversion of numerical strings (e.g. ‘$>10$’) into numerical representations
reduce the training time by at least ten percent on half of the datasets.

Statistical type prediction. Tables 2(a) and 2(b) evaluate the gradient
boosting classifier that predicts whether standard string features are nominal
or ordinal, by comparison against the ground truth using leave-one-out cross-
validation. These predictions are highly accurate, with very few
misclassifications. Hence, our eight extracted features are highly indicative
of ordinality in the feature values.

Metric | Score
---|---
Accuracy | 0.980 ± 0.14
F1 score | 0.978
Precision | 0.971
Recall | 0.985
AUC score | 0.980

(a) Statistical type prediction scores

| Predicted class
---|---
Ordinal | Nominal
Actual class | Ordinal | 79 | 2
Nominal | 1 | 67

(b) Statistical type prediction: Confusion matrix

Ordering method | Rank Correlation
---|---
Baseline | 0.1562 | ± 0.5313
FlairNLP | 0.7189 | ± 0.5356

(c) Spearman Rank Correlation for ordinal encoders vs. ground truth ordering.

Table 2: Results from various modules of the framework.

Ordinal encoding. Finally, we compare the ordinal encoding based on sentiment
intensity (FlairNLP) vs. the baseline ordinal encoding by comparing them to an
oracle with the ground-truth ordering. Table 2(c) and Fig. 5 show that
FlairNLP significantly outperforms the baseline, although the effect on
downstream model performance is limited ($<1\%$), and FlairNLP does require
significantly more preprocessing time.

Figure 5: Difference in mean performance metrics between different ordering
strategies. The smaller dots represent individual folds or runs.

##  5 Conclusions and future work

The automation of data cleaning is a fledgling open research field. We
presented a framework that combines state-of-the-art techniques and additional
novel components to enable automated string data cleaning. This framework
shows promising results, and some of its novel components (e.g., string
feature type inference, ordinality detection, and encoding using FlairNLP)
perform very well, especially in terms of identifying special types of
categorical string data and adequately processing and encoding them. However,
several challenges remain. First, string feature type inference using (regular
expression-based) PFSMs is sensitive to the exact formatting of strings. More
robust techniques are needed, such as sub-pattern matching and better use of
type probabilities in subsequent processing (e.g., if it is only 60% certain
that a string feature represents a date, a more robust encoding is needed, or
a human should be brought in the loop). Second, the string type-specific
processing was suboptimal or no better than the baseline on some datasets in
some aspects, providing interesting cases for further study. Finally, the
encoding of ordinal string data still leaves room for improvement. The
sentiment intensity-based encoding has shown to perform well on some aspects
and poorly on others. We believe that more sophisticated approaches are
possible, e.g., paying special attention to numbers appearing in the string
data. Overall, we hope that this framework and open-source implementation will
speed up research in these areas.

####  5.0.1 Acknowledgements

The authors would like to thank Marcos de Paula Bueno on his valuable feedback
on this paper. Furthermore, this work was partly funded by the European
Research Council under EU Horizon 2020 progamme, project 592215 (TAILOR).

## References

  * [1] Data Ladder. https://dataladder.com/, https://dataladder.com/
  * [2] DataCleaner. https://datacleaner.github.io/, https://datacleaner.github.io/
  * [3] geopy 2.1.0. https://github.com/geopy/geopy
  * [4] OpenRefine. https://openrefine.org/
  * [5] Roman Yurchark. pgeocode 0.3.0. https://github.com/symerio/pgeocode
  * [6] Akbik, A., Bergmann, T., Blythe, D., Rasul, K., Schweter, S., Vollgraf, R.: FLAIR: An easy-to-use framework for state-of-the-art NLP. In: Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics (Demonstrations). pp. 54–59 (2019)
  * [7] Cerda, P., Varoquaux, G.: Encoding high-cardinality string categorical variables. IEEE Transactions on Knowledge and Data Engineering (2020)
  * [8] Cerda, P., Varoquaux, G., Kégl, B.: Similarity encoding for learning with dirty categorical variables. Machine Learning 107(8-10), 1477–1494 (2018)
  * [9] Ceritli, T., Williams, C.K., Geddes, J.: ptype: probabilistic type inference. Data Mining and Knowledge Discovery 34(3), 870–904 (2020). https://doi.org/10.1007/s10618-020-00680-1
  * [10] CrowdFlower: Data Science Report (2016)
  * [11] Grabczewski, K., Jankowski, N.: Feature selection with decision tree criterion. In: Fifth International Conference on Hybrid Intelligent Systems (HIS’05). pp. 6–pp. IEEE (2005)
  * [12] Hardesty, L.: Automating big-data analysis (Oct 2015), https://news.mit.edu/2015/automating-big-data-analysis-1016
  * [13] Hutto, C., Gilbert, E.: Vader: A parsimonious rule-based model for sentiment analysis of social media text. In: Proceedings of the International AAAI Conference on Web and Social Media. vol. 8 (2014)
  * [14] Kanter, J.M., Veeramachaneni, K.: Deep Feature Synthesis: Towards automating data science endeavors. In: 2015 IEEE international conference on data science and advanced analytics (DSAA). pp. 1–10. IEEE (2015)
  * [15] Krishnan, S., Wang, J., Franklin, M.J., Goldberg, K., Kraska, T., Milo, T., Wu, E.: SampleClean: Fast and Reliable Analytics on Dirty Data. IEEE Data Eng. Bull. 38(3), 59–75 (2015)
  * [16] Krishnan, S., Wang, J., Wu, E., Franklin, M.J., Goldberg, K.: Activeclean: Interactive data cleaning for statistical modeling. Proceedings of the VLDB Endowment 9(12), 948–959 (2016)
  * [17] Krishnan, S., Wu, E.: AlphaClean: Automatic Generation of Data Cleaning Pipelines. CoRR abs/1904.11827 (2019), http://arxiv.org/abs/1904.11827
  * [18] Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. In: Soviet physics doklady. vol. 10, pp. 707–710. Soviet Union (1966)
  * [19] Little, R.J.: A test of missing completely at random for multivariate data with missing values. Journal of the American statistical Association 83(404), 1198–1202 (1988)
  * [20] Loria, S.: TextBlob Documentation. Release 0.15 2 (2018)
  * [21] Mahdavi, M., Abedjan, Z., Castro Fernandez, R., Madden, S., Ouzzani, M., Stonebraker, M., Tang, N.: Raha: A configuration-free error detection system. In: Proceedings of the 2019 International Conference on Management of Data. pp. 865–882 (2019)
  * [22] Miller, G.A.: WordNet: a lexical database for English. Communications of the ACM 38(11), 39–41 (1995)
  * [23] Musleh, M., Ouzzani, M., Tang, N., Doan, A.: CoClean: Collaborative Data Cleaning. In: Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. pp. 2757–2760 (2020)
  * [24] Pedregosa, F., Varoquaux, G., Gramfort, A., Michel, V., Thirion, B., Grisel, O., Blondel, M., Prettenhofer, P., Weiss, R., Dubourg, V., Vanderplas, J., Passos, A., Cournapeau, D., Brucher, M., Perrot, M., Duchesnay, E.: Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research 12, 2825–2830 (2011)
  * [25] Pennington, J., Socher, R., Manning, C.D.: Glove: Global vectors for word representation. In: Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). pp. 1532–1543 (2014)
  * [26] Rekatsinas, T., Chu, X., Ilyas, I.F., Ré, C.: HoloClean: Holistic Data Repairs with Probabilistic Inference. CoRR abs/1702.00820 (2017), http://arxiv.org/abs/1702.00820
  * [27] Rubin, D.B.: Inference and missing data. Biometrika 63(3), 581–592 (1976)
  * [28] Shahbaz, M., McMinn, P., Stevenson, M.: Automated discovery of valid test strings from the web using dynamic regular expressions collation and natural language processing. In: 2012 12th International Conference on Quality Software. pp. 79–88. IEEE (2012)
  * [29] Valera, I., Ghahramani, Z.: Automatic Discovery of the Statistical Types of Variables in a Dataset. In: Precup, D., Teh, Y.W. (eds.) Proceedings of the 34th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 70, pp. 3521–3529. PMLR (06–11 Aug 2017)
  * [30] Zöller, M.A., Huber, M.F.: Benchmark and Survey of Automated Machine Learning Frameworks. arXiv preprint arXiv:1904.12054 (2019)

##  Appendix 0.A Details on string features and processing

####  0.A.0.1 Coordinate

This is a string feature that represent GPS or Degree-Minute-Second (DMS)
coordinates such as N29.10.56 W90.00.00, N29:10:56, and 29° 10’56.22"N.
Coordinates can be distinguished from other string features based on the
following characteristics:

  * •

Two sequences of at most two digits and a third sequence which is a float with
at most two digits before the decimal point.

  * •

A character that separates the three sequences of digits (e.g., . or :). In
the context of DMS coordinates, these characters are °, ’, and " respectively.

  * •

A cardinal direction at the beginning or at the end of the string (i.e., N, E,
S, and W).

This string feature is processed as follows. First, the string feature is
split up into two separate parts for each coordinate in the entry, in which
one part represents the cardinal direction of the coordinate and the other
part represents the numerical information. Second, the current format of the
coordinate string feature is converted into the corresponding decimal latlong
value. The string feature is formatted using degrees, minutes, and seconds.
This format can be converted to representative decimal values using the
following formula222Taken from “Geographic coordinate conversion” at
https://en.wikipedia.org/wiki/Geographic\\_coordinate\\_conversion:

$\text{decimal}=\begin{cases}-(\text{degrees}+\frac{\text{minutes}}{60}+\frac{\text{seconds}}{3600})&\text{if
}c\in\\{S,W\\}\\\
\text{degrees}+\frac{\text{minutes}}{60}+\frac{\text{seconds}}{3600}&\text{otherwise}\end{cases}$

Last, additional information is extracted in case the string feature contains
both the latitude and the longitude values. The additional information that
can be extracted includes Earth-Centered Earth-Fixed representations of the
latlong value and postal codes and country codes via geopy [3]. If the user
decides to encode the data, the extracted postal and country codes will
receive a nominal encoding in the final step of the framework.

####  0.A.0.2 Day

This string feature represent the names of the seven days in the week such as
Monday. These names can appear in data in several formats. For example, Monday
can be written as Mon and Mo. Days can be distinguished from other string
features based on the following characteristics:

  * •

A prefix of at least two characters, indicating the day of the week (e.g., Mo
for Monday, Th for Thursday, etc.).

  * •

The suffix day, if present.

  * •

A distinct set of characters that comes after the prefix and before the suffix
(e.g., if the string is Thursday, then Th should be followed by urs).

As this string feature is the least complex out of all inferred string
features, it is also the most simple to process. Considering only the first
two characters for days is the most reduction that can be done while still
being able to make a distinction between each unique day of the week. If the
user decides to encode the data, this string feature will receive a nominal
encoding in the final step of the framework.

####  0.A.0.3 E-mail

This string feature represents all valid e-mail addresses from any domain such
as<EMAIL_ADDRESS>and<EMAIL_ADDRESS>This feature can be distinguished
from others based on the following characteristics:

  * •

The character @ which is between two sets of characters.

  * •

A substring in front of the @ (i.e., the name of the e-mail) which is composed
of valid characters (e.g., the e-mail address #<EMAIL_ADDRESS>is invalid as
the characters before the final @ cannot be included in an e-mail name).

  * •

A substring that comes after the @ which is composed of valid characters and
at least one dot inbetween those characters (e.g., name@hotmail is not a valid
e-mail address as the domain name is incomplete).

This string feature is processed as follows. We first remove the longest
common suffix of all entries. Then, additional special characters are removed
to simplify the values. If the user decides to encode the data, this string
feature will receive a nominal encoding in the final step of the framework.

####  0.A.0.4 Filepath

This string feature represents paths within a local system such as C:/Windows/
and C:/Users/Documents. Filepaths can be distinguished from other string
features by the following characteristics:

  * •

A series of substrings which are separated from each other using either / or \
(e.g., home/users).

  * •

Each substring cannot contain any of the following characters: \/:*?"<>|

  * •

If present, a prefix that represents the root disk or a sequence of dots
followed by a slash or a backslash (e.g., C:/, ../, etc.).

Processing this string feature is similar to how e-mail addresses are
processed and is aimed to reduce string complexity. For this feature, the
longest common prefix and suffix are removed from all entries and all special
characters are removed. If the user decides to encode the data, this string
feature will receive a nominal encoding in the final step of the framework.

####  0.A.0.5 Month

This string feature represents the non-numerical representation of a month
with or without year and day and can be distinguished based on the following
criteria:

  * •

A prefix of at least three characters, representing a unique month (e.g.,
Apr).

  * •

If present, the remaining substring that comes after the prefix (e.g., il
comes after the prefix Apr).

  * •

If present, a sequence of at most two digits before or after the month which
represents a day in the month (e.g., 1 January or January 1).

  * •

If present, a sequence of at most four digits or a sequence with prefix ’
followed by two digits that comes after the month which represents the year
(e.g., January 2000 or January ’00). Both day and year can be present at the
same time.

Processing this string feature is based on the format that is being presented.
Each format is split up into individual components that represent either a
day, month, or year. The key step in this procedure is to ensure that the
string representative of the month is turned into the corresponding numerical
representation. After this key step is performed, all values are concatenated
to each other according to the format yyyymmdd. The overall workflow of this
processing step is depicted in Fig. 6. As the string feature is already
transformed to its numerical representation, no encoding would be required if
the user requested so.

Figure 6: The overall workflow for processing month string features.

####  0.A.0.6 Numerical

There are a variety of entries that are relatively easy for users to
distinguish as numerical values but are usually inferred as strings by any
type detection or inference technique due to the presence of certain non-
numerical characters. It is therefore important to categorize such entries as
a string feature to properly handle and process them. We obtain numerical
string features using any of the following characteristics:

  * •

Between two sequences of digits, one of the following characters: -+_/:;&’ A
space or the substring to is also applicable (e.g., 100 to 200).

  * •

Before a single sequence of digits, any of the following words: Less than,
Lower than, Under, Below, Greater than, Higher than, Over, Above.

  * •

Before or after a single sequence of digits, any of the following characters:
<>+$%=

Numerical string features are processed based on what they represent. If the
string feature represents a range of values, the mean of the range is
calculated for each entry. After that, the range entries are encoded according
to the numerical order of the ranges. If the string feature does not represent
a range, we remove all special characters and consider all resulting numbers
as separate numerical features. As the string feature is already transformed
to its numerical representation, no encoding would be required if the user
requested so.

####  0.A.0.7 Sentence

This string feature is composed of a sequence of words, typically found in
datasets that contain reviews or descriptions. It is slightly more difficult
to express this string feature as a regular expression compared to the others
because of its overlapping characteristics with regular string entries that
consists of a couple of words. However, it is still possible to perform string
feature inference for sentences based on the following characteristics:

  * •

A substring of characters followed by a space for at least five times (i.e.,
the entry is at least six words long).

The goal for processing sentence string features is to remove redundancy in
the entry and to make these more relevant for use in tabular data. The
technique used to achieve this goal is the NLTK word tokenizer, which takes a
sentence and divides these into tuples containing each word and their
associated part of speech. Then, every word that is associated with a noun is
joined together with a space into a single string which is then passed on. The
result is a group of nouns that are supposed to represent the essence of the
sentence and are ready to be encoded in the next step of the library. If the
user decides to encode the data, this string feature will receive a nominal
encoding in the final step of the framework.

####  0.A.0.8 URL

This string feature represents any link to a website or domain such as
https://www.tue.nl/ and http://canvas.tue.nl/login. The characteristics of
this string feature is similar to that of filepaths, with a few exceptions:

  * •

An optional suffix which represents a certain protocol (e.g., http://).

  * •

A series of at most four character sequences, separated from each other by a
dot (e.g., www.google.com or google.com). Note that the last (pair of)
sequence(s) contain(s) at most three characters.

Processing this string feature follows the same procedure as filepaths. If the
user decides to encode the data, this string feature will receive a nominal
encoding in the final step of the framework.

####  0.A.0.9 Zip code

This string feature represents zip or postal codes from a handful of
countries. Note that we are only able to infer zip codes that contain non-
numerical characters as numerical-only zip codes are much more difficult to
infer using PFSMs without overlapping actual numerical features.

Processing this string feature is mainly done to extract additional
information from each entry. In our case, we make use of the geopy library to
fetch the latitude, longitude, and country code of the zip code. Furthermore,
we also calculate the ECEF coordinate using the latitude and longitude values.
If the user decides to encode the data, the zip code string feature will
receive a nominal encoding in the final step of the framework.

##  Appendix 0.B Details on ordinality feature extraction

  * •

The total number of rows in the column: It is possible that the number of rows
in combination with other extracted features can increase the performance of
the classifier. Obtaining this value is done by measuring the length of the
column.

  * •

The number of unique values in the column: In general, nominal data tends to
vary more in cardinality as opposed to ordinal data. Furthermore, some ordinal
data columns tend to adhere to Likert-scale characteristics regarding the
possible number of unique entries, which also limits its cardinality. The
value is obtained by counting all unique entries in a column.

  * •

The ratio between the number of unique values and the total number of rows: As
a rule of thumb, some domain experts tend to classify data as ordinal when the
ratio between the unique values and the total number of rows is at most 0.05.
The ratio for nominal data tends to be at most 0.2. As a result of this rule
of thumb, we extract the ratio for use in the classifier by dividing the
number of unique values by the total number of rows.

  * •

The mean of the variance of the distance between the word embeddings of unique
entries: The idea behind extracting this feature is that the word embeddings
of certain entries showcase interesting linear substructures in the word
vector space. By taking a pre-trained word vector space, the classifier may be
able to make a distinction between ordered and unordered data based on
differences in the substructure. The first step is to split each entry into a
set of words which are then embedded using a pre-trained word vector space.
This work makes use of the Wikipedia word vector space by GloVe, which
consists of over 400 000 words in the vocabulary embedded into a
50-dimensional vector space [25], to assign each word in an entry to a vector.
A random point in the vector space will be assigned to a word in case it does
not appear in the pre-trained corpus. Next, the mean of all dimensions for
each word vector in the entry is calculated such that all word vectors of the
entry are now represented as a single point in the 50-dimensional vector
space. After this is done for all entries in the column, the variance between
each dimension is calculated. Finally, the mean of each dimension is taken and
the resulting value is a single float value that can be used to potentially
distinguish ordered data from unordered data.

  * •

Whether the column name is commonly used in ordinal data: There are a set of
keywords that can commonly be found in column names for ordinal data. Examples
of certain keywords include grade, stage, and opinion. By checking whether a
column name is contained within one of those keywords and vice versa, we are
able to tell whether the data in the column is more likely to be ordinal or
not. Note that keywords for column names used in this work are created based
on domain expertise, which means that results may vary when other keywords are
used.

  * •

Whether the column name is commonly used in nominal data: The approach of
extracting this feature is similar to that of checking ordinal traits in the
column name, except that the names obtained via domain expertise are now
commonly used in nominal data. Typical nominal column names include address,
city, name, and type. Again, since the used names are based on domain
expertise, results in performance may vary when other names are used.

  * •

Whether the unique entries contain keywords that are commonly found in ordinal
data: Extracting this feature is similar to the two aforementioned techniques,
except that ordinality will now be implied based on keywords that are commonly
found in ordinal data. The keywords that were used in this work are adjectives
and nouns that are typically found in Likert-scale questionnaires.

  * •

Whether the unique entries share a number of common substrings: Ordinal data
tends to contain entries with overlapping substrings. For example, the strings
disagree, agree, and wholeheartedly agree all contain the substring agree. By
checking whether there are common substrings in the data of sufficient length,
it is possible that the classifier associates the occurrence of substrings
with the implication that the data is ordinal.

##  Appendix 0.C Datasets

A list of all datasets that were used during the evaluation are provided here,
including additional information on what was used from the data.

###  0.C.1 String feature inference and processing

Some of the datasets listed below were used to evaluate both string feature
inference and string feature processing. The datasets without model, task, and
target were only used to evaluate string feature inference based on the
manually assigned ground truth of the columns. The datasets with the
previously mentioned components were used for both string feature inference
(with manual labeling of string feature) and string feature processing
(evaluation by running the associated task).

####  0.C.1.1 Coordinate

  * •

Digital altimetric data information - GPS. Columns: latgms, loggms.
https://www.kaggle.com/mpwolke/cusersmarildownloadsgpscsv

####  0.C.1.2 Day

  * •

San Francisco Crime Classification. Columns: DayOfWeek. Model:
GradientBoostingClassifier. Task: Classification. Target: Category.
https://www.kaggle.com/kaggle/san-francisco-crime-classification

####  0.C.1.3 E-mail

  * •

Data_UK. Columns: email. https://www.kaggle.com/phool1804/data-uk

  * •

Enrico’s Email Flows. Columns: sender, receiver.
https://www.kaggle.com/emarock/enricos-email-flows

  * •

Indian Companies Registration Data [1857 - 2020]. Columns: EMAIL _ADDR.
https://www.kaggle.com/rowhitswami/all-indian-companies-registration-
data-1900-2019

####  0.C.1.4 Filepath

  * •

Collection of Classification & Regression Datasets. Columns: Image Index.
https://www.kaggle.com/balakrishcodes/others?select=xrayfull.csv

  * •

Hillary Clinton’s Emails. Columns: MetadataPdfLink.
https://www.kaggle.com/kaggle/hillary-clinton-emails?select=Emails.csv

  * •

Liver and Liver Tumor Segmentation. Columns: filepath, liver_maskpath,
tumor_maskpath. https://www.kaggle.com/andrewmvd/lits-png?select=lits\\_df.csv

####  0.C.1.5 Month

  * •

FIFA 19 complete player dataset. Model: GradientBoostingRegressor. Task:
Regression. Target: Value. Columns: Joined.
https://www.kaggle.com/karangadiya/fifa19

  * •

Netflix Movies and TV Shows. Columns: date_added.
https://www.kaggle.com/shivamb/netflix-shows

  * •

Metacritic-Game Releases by Score. Columns: Date.
https://www.kaggle.com/abhishekdataset/metacriticgame-releases-by-score

####  0.C.1.6 Numerical

  * •

FIFA 19 complete player dataset. Columns: LS, ST, RS, LW. Model:
GradientBoostingRegressor. Task: Regression. Target: Value.
https://www.kaggle.com/karangadiya/fifa19

  * •

HR Analytics: Job Change of Data Scientists. Columns: company_size.
https://www.kaggle.com/arashnic/hr-analytics-job-change-of-data-
scientists?select=aug\\_train.csv

  * •

Students’ Academic Performance Dataset. Columns: StudentAbsenceDays.
https://www.kaggle.com/aljarah/xAPI-Edu-Data

####  0.C.1.7 Sentence

  * •

Wine Reviews. Columns: description. Model: GradientBoostingRegressor. Task:
Regression. Target: points https://www.kaggle.com/zynicide/wine-reviews

  * •

World Development Indicators. Columns: SpecialNotes, SystemOfNationalAccounts.
https://www.kaggle.com/worldbank/world-development-indicators

####  0.C.1.8 URL

  * •

FIFA 19 complete player dataset. Columns: Photo, Flag, Club Logo. Model:
GradientBoostingRegressor. Task: Regression.
Target: Value. https://www.kaggle.com/karangadiya/fifa19

  * •

Walmart Product Details 2020. Columns: Product Url.
https://www.kaggle.com/promptcloud/walmart-product-details-2020

####  0.C.1.9 Zip code

  * •

Data_UK. Columns: postal. https://www.kaggle.com/phool1804/data-uk

  * •

OpenAddresses - Europe. Columns: POSTCODE.
https://www.kaggle.com/openaddresses/openaddresses-
europe?select=netherlands.csv

  * •

OpenAddresses - North America (excluding U.S.). Columns: POSTCODE.
https://www.kaggle.com/openaddresses/openaddresses-north-america-excluding-
us?select=bermuda.csv

  * •

House Price Data, England & Wales, 2015 to 2019. Columns: SS2 6ST. Model:
GradientBoostingRegressor. Task: Regression. Target: 249995.
https://www.kaggle.com/dmaso01dsta/house-price-data-england-wales-2015-to-2019

###  0.C.2 Statistical type prediction and determining order in data

Some of the datasets listed below were used for both statistical type
prediction and determining the order in ordinal data. The datasets without
model, task, and target were only used to classify the statistical type based
on the manually labeled ground truth of the columns. The datasets with the
previously mentioned components were used for both statistical type prediction
(with manual labeling of ordinality) and performance evaluation of FlairNLP
(evaluation by running the associated task).

####  0.C.2.1 Nominal datasets

  * •

[NeurIPS 2020] Data Science for COVID-19 (DS4C). Columns: province, city.
https://www.kaggle.com/kimjihoo/coronavirusdataset?select=Case.csv

  * •

[NeurIPS 2020] Data Science for COVID-19 (DS4C). Columns: type, gov_policy.
https://www.kaggle.com/kimjihoo/coronavirusdataset?select=Policy.csv

  * •

AB_NYC_2019. Columns: name, host_name, neighborhood_group, neighborhood,
room_type.
https://www.kaggle.com/chadra/ab-nyc-2019

  * •

Automobile Dataset. Columns: make.
https://www.kaggle.com/toramky/automobile-dataset

  * •

Craft Beers Dataset. Columns: style.
https://www.kaggle.com/nickhould/craft-cans?select=beers.csv

  * •

Craft Beers Dataset. Columns: city, state.
https://www.kaggle.com/nickhould/craft-cans?select=breweries.csv

  * •

FIFA 19 complete player dataset. Columns: Nationality, Club.
https://www.kaggle.com/karangadiya/fifa19

  * •

FiveThirtyEight Comic Characters Dataset. Columns: ALIGN, EYE, HAIR.
https://www.kaggle.com/fivethirtyeight/fivethirtyeight-comic-characters-
dataset?select=dc-wikia-data.csv

  * •

HR Analytics: Job Change of Data Scientists. Columns: city, major_discipline,
company_type.
https://www.kaggle.com/arashnic/hr-analytics-job-change-of-data-
scientists?select=aug\\_train.csv

  * •

IBM HR Analytics Employee Attrition & Performance. Columns: Department,
EducationField, JobRole. Model: GradientBoostingRegressor. Task: Regression.
Target: MonthlyIncome.
https://www.kaggle.com/pavansubhasht/ibm-hr-analytics-attrition-dataset

  * •

Kickstarter Projects. Columns: category, main_category, currency, country.
https://www.kaggle.com/kemical/kickstarter-projects?select=ks-
projects-201612.csv

  * •

Mushroom Classification. Columns: class, cap-shape, cap-surface, cap-color,
bruises, odor, gill-attachment, gill-spacing, gill-size, gill-color, stalk-
shape, stalk-root, stalk-surface-above-ring, stalk-surface-below-ring, stalk-
color-above-ring, stalk-color-below-ring, veil-type, veil-color, ring-numer,
ring-type, spore-print-color, population, habitat.
https://www.kaggle.com/uciml/mushroom-classification

  * •

Pokemon with stats. Columns: Type 1, Type 2.
https://www.kaggle.com/abcsds/pokemon

  * •

Ramen Ratings. Columns: Brand, Variety, Style, Country.
https://www.kaggle.com/residentmario/ramen-ratings

  * •

Stroke Prediction Dataset. Columns: work_type, smoking_status.
https://www.kaggle.com/fedesoriano/stroke-prediction-dataset

  * •

Students’ Academic Performance Dataset. Columns: PlaceOfBirth, GradeID,
SectionID, Topic.
https://www.kaggle.com/aljarah/xAPI-Edu-Data

  * •

Students Performance in Exams. Columns: race/ethnicity.
https://www.kaggle.com/spscientist/students-performance-in-exams

  * •

Wine Reviews. Columns: country, province, region_1, variety. Model:
GradientBoostingRegressor. Task: Regression. Target: points.
https://www.kaggle.com/zynicide/wine-reviews

####  0.C.2.2 Ordinal datasets

  * •

Amazon - Ratings (Beauty Products). Columns: Rating.
https://www.kaggle.com/skillsmuggler/amazon-
ratings?select=ratings\\_Beauty.csv

  * •

Audiology (Original) Data Set. Columns: air, ar_c, ar_u, bone, o_ar_c, o_ar_u,
speech.
https://archive.ics.uci.edu/ml/datasets/Audiology+\%28Original\%29

  * •

Basic Income Survey - 2016 European Dataset. Columns: dem_education _level,
awareness, vote, age_group.
https://www.kaggle.com/daliaresearch/basic-income-survey-european-dataset

  * •

Car Evaluation Data Set. Columns: buying, maint, doors, persons, lug_boot,
safety, class value. Model: GradientBoostingClassifier. Task: Classification.
Target: Class Values.
https://archive.ics.uci.edu/ml/datasets/Car+Evaluation

  * •

Earthquake Magnitude, Damage and Impact. Columns: damage_overall _colapse,
damage_overall_leaning, damage_grade, technical_solution_proposed.
https://www.kaggle.com/arashnic/earthquake-magnitude-damage-and-
impact?select=csv\\_building\\_damage\\_assessment.csv

  * •

Earthquake Magnitude, Damage and Impact. Columns: education_level
_household_head.
https://www.kaggle.com/arashnic/earthquake-magnitude-damage-and-
impact?select=csv\\_household\\_demographics.csv

  * •

Hayes-Roth Data Set. Columns: age, educational level, marital status.
https://archive.ics.uci.edu/ml/datasets/Hayes-Roth

  * •

Linux Gamers Survey, Q1 2016. Columns: LinuxUserHowLong,
DesktopLinuxGamerHowLong, HeavyGamer, LinuxExclusivity, LinuxGamingHabit-
Change, LinuxGamingHabitFuture, LinuxGamingMachineShared, FolksAround-
YouAwareLinux, LinuxGamesPurchaseFrequency, SatisfactionSteam,
SatisfactionGOG, SatisfactionHB, DistroChangeFrequency,
DistroImpactPerformance, HardwareUpgradeIntent, AwarenessBrandedSteamMachines,
AwarenessSteamController, AwarenessSteamLink, SteamMachineConceptLike,
SteamMachinesExpandLinuxDoubtful, SteamMachinesLaunchEvaluation,
SteamMachinesAwarenessAlienware, SteamMachinesAwarenessZotac,
SteamMachinesAwarenessSyber, SteamMachinesWantToBuy, MachinesMaximumPrice,
MachinesDIYIntent, SteamControllerPurchaseIntent, SteamOSEverTried,
SteamIHSUage, SteamLinkPurchaseIntent, WINEUsageVanilla, PlayOnLinux,
Crossover, WINEEvaluation.
https://www.kaggle.com/sanqualis/linuxgamerssurvey

  * •

Nursery Data Set. Columns: parents, has_nurs, form, housing, finance, social,
health. Model: GradientBoostingClassifier. Task: Classification. Target:
Nursery.
https://archive.ics.uci.edu/ml/datasets/Nursery

  * •

Solar Flare Data Set. Columns: activity, evolution, previous_24h_flare_acti-
vity_code, area. Model: GradientBoostingRegressor. Task: Regression. Target:
C-class, M-class, X-class.
https://archive.ics.uci.edu/ml/datasets/Solar+Flare

  * •

Soybean (Large) Data Set. Columns: precip, temp, crop-hist, area-damaged,
severity, stem-cankers. Model: GradientBoostingClassifier. Task:
Classification. Target: class.
https://archive.ics.uci.edu/ml/datasets/Soybean+\%28Large\%29