1
$\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$
0
$\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$
  • $\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 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 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$ – Yuval Filmus Aug 15 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 at 13:12
  • $\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$ – Yuval Filmus Aug 15 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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