4
$\begingroup$

i stumbled upon a paper, that introduces a distance metric, which is then used to cluster data (https://doi.org/10.1137/1.9781611972795.35). I noticed however, that this "distance" violated at least one property of the mathematical definition of distance, namely $dist(x,x) \neq 0$ for some $x$. Additionally, I am pretty sure, that $dist(x,y) < 0$ for some $x,y$

I was wondering, what could go wrong when clustering data if theses properties of distances are violated? And what happens if other properties are violated such as symmetry or triangle inequality?

$\endgroup$
1
$\begingroup$

This may not be the answer you're looking for, but in the simplest terms (and admittedly perhaps unhelpfully), the benefit of having a distance metric that corresponds to an actual metric in the mathematical sense means that you can consider your set of elements, along with the metric, in a metric space, which automatically gives you a lot of tools to think about your problem and your clustering goals, the most important of them being lots of topological properties that automatically come with a metric space.

As for the downsides of not having a proper metric, it's precisely that your space, equipped with this 'fake' metric, will not be a metric space in the mathematical sense. Depending on the properties of your 'fake' metric, and depending on what you want to achieve, this may or may not be a big deal, and you can certainly consider an alternative space other than a metric space, but it may be harder to know what tools you do and do not have access to in this space of yours. It certainly can be quite problematic in most clustering applications for symmetry of your metric to fail, as that suggests that how you pair elements matters, so considering (x,y) would be different than (y,x), but I'm sure you can come up with weird situations where that is okay, or even desirable.

I havn't looked very carefully at the paper, and your question seems more about general concepts, but I just wanted to point out that metrics that do not obey the mathematical definition of a metric are commonly used in many fields, including string metrics. For example, the Jaro-Winkler string distance is very popular, but it does not satisfy triangle inequality. Is it 'wrong' to cluster strings using J-W? A lot of people would argue no, because it captures a different concept of distance that is useful with strings, and especially shorter strings (I think that's usually when JW is preferable to Levenstein, though don't quote me on that), and I'm sure there's lots of work out there about how to cluster using JW and acknowledging the lack of the triangle inequality being satisfied.

More generally, in math, it's often the case that failing to satisfy some established criteria for something does not mean nothing works, but rather that you're dealing with a slightly different object, and that's totally okay (and in fact, exciting, because you're exploring new ideas). In fact, metrics without triangle inequality have a name for themselves, and they are called semimetrics so in that case, you'd just have a semimetric space instead of a metric space for your clustering problem, and maybe it's interesting to explore clustering properties in such spaces. In fact, just quickly googling 'clustering in semimetric spaces', there's this article that came up that may be of interest for that case (though your case is different since it violates other conditions).

$\endgroup$
2
  • 1
    $\begingroup$ The metric described in the question is not a semimetric because, in addition to violating the triangle inequality, it also violates the first three metric axioms. Semimetrics only violate the triangle inequality. I'm not sure if you were implying this but I think it is worth clarifying. $\endgroup$
    – Ryan Volpi
    Jun 3 '20 at 19:49
  • 1
    $\begingroup$ Yeah, I did not look carefully at the paper, but the question seemed more general so I just wanted to illustrate some ideas. $\endgroup$
    – doubled
    Jun 3 '20 at 19:52

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.