# Distances vs. “distance like functions” in clustering

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.

• 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/… – Stéphane Laurent Jun 21 '13 at 19:49
• @Stephane thanks for the interesting comment. I will read the post you sent me. Thanks! – Avitus Jun 21 '13 at 19:53