2
$\begingroup$

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?

$\endgroup$
1

2 Answers 2

3
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ Thanks for the clarification, I already read the wiki (and other websites too). However the way it is written in the slide suggest that it is the rule rather than the exception that the centroid can be calculated for a general metric space (suggesting that addition and scaling is usually defined?) $\endgroup$
    – Mads
    Aug 14, 2019 at 20:50
  • $\begingroup$ I will just paste the quote from my slide here again, i probably didn't make it clear that this was a quote from the slides: "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" $\endgroup$
    – Mads
    Aug 14, 2019 at 20:53
  • $\begingroup$ This is the same as asking why someone claims that some vehicles have more than four wheels, although most vehicles you encounter in practice do have four wheels. I don’t really understand what kind of answer you expect. I suspect that you are really interested in a somewhat different question, which you should try to formulate. $\endgroup$ Aug 15, 2019 at 11:41
  • $\begingroup$ Ok, I apoligize if its not clear, maybe I'm not really sure either, reading from slides that leaves out a lot of details makes it easy to misunderstand things personally. Its really just the quote that confuses me, probably the main thing I don't understand is what "pairwise distance" has to do with computing the centroid. $\endgroup$
    – Mads
    Aug 15, 2019 at 13:12
  • 1
    $\begingroup$ It doesn’t have anything to do with it. That’s exactly the point. In a general metric space you only have pairwise distances, and so the concept of centroid is meaningless. $\endgroup$ Aug 15, 2019 at 13:16
0
$\begingroup$

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.

$\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.