2
$\begingroup$

I am studying Kogan's "Introduction to Clustering Large and High Dimensional Data" because I would like to better understand clustering (I never worked with it). Until now "clustering" means to me to find a partition of a given cloud of data s.t. a given objective function is minimized.

Such objective function is defined by introducing once and for all a distance or "distance-like" function, i.e. a measure of dissimilarity which fails to satisfy all 3 axioms defining a distance on a metric set.

Examples of "distance like" functions are given by

  1. $d(x,y):=|x-y|^2$, with $x,y\in\mathbb R$
  2. Kullback-Leibner divergence
  3. Bregman and $\varphi$-divergences

My first question is: why are "distance-like" functions so much used clustering? Shouldn't we use distances whenever it is possible?

I do not know whether there exists an application independent answer to my question, but I am searching for a list of criteria or examples which should motivate the choice of "distance like" functions instead of distances. If a "distance like" function allows to write a quick and efficient clustering algorithm and it is convex, then (probably?) in applications it is not necessary to introduce a distance function. What do you think about this point? Have you examples/counterexamples to share?

For example, what does make

$$d(x,y):=|x-y|^2$$ and the Kullback-Leibner divergence $D_{KL}$ a more interesting/better/more natural choice in clustering applications than

$$d(x,y):=|x-y|$$ and the information value $IV$?

I thank you for your help.

$\endgroup$
  • 1
    $\begingroup$ Hello Avitus. The important point is to use a "distance" that reflects as best as possible the dissimilarities of interest. The mathematical properties of a "true distance" such as triangular inequality are not primarily important. See an example in this post stats.stackexchange.com/questions/25764/… $\endgroup$ – Stéphane Laurent Jun 21 '13 at 19:49
  • $\begingroup$ @Stephane thanks for the interesting comment. I will read the post you sent me. Thanks! $\endgroup$ – Avitus Jun 21 '13 at 19:53
1
$\begingroup$

Of course it's nice to have proper distance metrics.

But sometimes you don't have one.

Then you want to have algorithms that do not require a metric, but that can work with a distance-like function.

Example: cosine similarity. It's undefined for the origin, so it can't be a metric. It's still very useful.

$\endgroup$

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.