Why is it not always possible to compute the centroid of feature vectors?

Question

Hi in the data mining and machine learning course that I'm taking there is a subject on feature spaces and there is this part about feature vector aggregation and metric spaces that I don't really understand. Now our curriculum is basically a huge presentation and the whole information about feature vector aggregation fits on one slide, anyway what I don't understand is this:

For a given sample $D$ the centroid can be computed as $C_D = \frac{1}{|D|}\cdot\sum_{o\in D} o$

and then on the slide it says, quote:

In a general metric space (that is, not a vector space), where we only have pairwise distances, it might not be possible to compute a centroid

I don't really think I understand what "only pairwise distance" means (my guess is it has something to do with the fact that a metric space defines the distances between all pairs of elements in its set) or why the consequence of it is that you can't always compute the centroid.

I read somewhere that metric spaces does not have to define addition or scaling and if that is the case it makes sense to me that you can not calculate the centroid. Is this what it essentially is about or am I completely misunderstanding something?

Answer 1

A metric space consists of a set $X$ of "points" and a metric $d\colon X \times X \to \mathbb{R}_{\geq 0}$ (giving the "distance" between any two points) which satisfies the following constraints:

1. Symmetry: $d(x,y) = d(y,x)$ for all $x,y \in X$.
2. Non-triviality: $d(x,y) = 0$ if and only if $x = y$.
3. Triangle inequality: $d(x,y) \leq d(x,z) + d(z,y)$ for all $x,y,z \in X$.

The definition of centroid doesn't make sense for a general metric space, since you cannot perform arithmetic on the elements of $X$.

Answer 2

In a general metric space (that is, not a vector space), where we only have pairwise distances, it might not be possible to compute a centroid

The above quote is correct but it is misleading. A centroid is only defined for the Euclidean space. It is the coordinate-wise average of each point in the dataset. Another definition of a centroid is that it is a point in the Euclidean space that minimizes the sum of squared distances of the points in the dataset $\mathcal{D}$, i.e., $$\mu = \arg min_{c \in \mathbb{R}^{d}} \sum_{x \in D}\|x-c\|^{2}$$.

As Yuval said the concept of a centroid is meaningless in general metric space.

Let us look at a practical example of a metric space, where the above definition does not make any sense. Consider an undirected graph $G = (V,E)$ with weights on the edges. Such a graph could be a representation of a road/railway network of a country, i.e., a node representing a city, an edge representing a road, and weight representing the length of the road.

Note that cities can be mapped to a 2-D Euclidean space. However, the Euclidean distance between them is not useful here since there might not be a direct road connecting every pair of two cities. A more meaningful measure would be the shortest path distance between every pair of two cities/nodes in the graph.

Suppose, we want to establish an industrial site in one of the cities such that the sum of transportation cost to every other city is minimized. In other words, we want to find a city $c$ that minimizes the following objective function:

$$\mu = \arg min_{c \in V} \sum_{v \in V}d(v,c)$$

This definition is similar to the definition of a centroid. However, here $d(v,c)$ is the shortest path distance between the cities $v$ and $c$, instead of the Euclidean distance. Also, note that the space is a metric space since the shortest path distances follow triangle inequality. The other properties of the metric space are also easy to verify.

Opening the industry at the centroid makes no sense at all since the Euclidean distances are not representing the actual transportation cost.