Conditions on a legitimate distance measure for clustering

Question

Why does it seem unimportant to use a proper distance metric for clustering, i.e. (i) positive, (ii) zero iff the 2 operands are equal, and (iii) verifying the triangle inequality? I'm thinking in particular of condition (iii), which seems commonly ignored.

In particular, spherical k-means clustering, as defined in a 2001 paper by Dhillon and Modha (http://link.springer.com/article/10.1023/A:1007612920971) represents documents by unit vectors so as to avoid long documents (with large norms in their associated vectors) acting as attractors. And, rather than using a distance measure, they use cosine as a proximity measure.

Noting that documents are represented by vectors of positive numbers, the angle between 2 document vectors (both being in the high-dimensional "top right" quadrant) will be in the interval $[0, {\pi \over 2}]$; then, it is easy to prove that the proximity measure does not satisfy the proximity triangle inequality (symmetric to the distance triangle inequality). $$\alpha \leq \alpha + \beta \\ \cos(\alpha + \beta) \leq \cos\,\alpha \leq \cos\,\alpha + \cos\,\beta$$

However, it seems more meaningful to define the triangle inequality on distances than proximities. The domain of the angles being the interval $[0, {\pi \over 2}]$, the distance measure $1 - \cos\,\theta$ will be positive, and zero exclusively when 2 unit vectors are equal. As for the triangle inequality, it will require the following:

$$1 - \cos\,\alpha + 1 - \cos\,\beta \geq 1 - \cos(\alpha + \beta) \\ 1 \geq \cos\,\alpha + \cos\,\beta - \cos(\alpha + \beta)$$

What I've found empirically, without being able to prove it, is that the expression $\cos\,\alpha + \cos\,\beta - \cos(\alpha + \beta)$ exceeds 1 for all pairs of angles in the interval $[0, {\pi \over 2}]$, except when both angles equal either 0 or $\pi \over 2$, in which case the expression equals exactly 1. (The gradient of the expression is zero at $(0,0)$, but this turns out to be a saddle point. On the other hand, there's a minimum of -1 outside the definition domain, at $(\pi,\pi)$.)

So, my questions are:

1. Would there be anything to gain by enforcing the triangle inequality, for instance by using Euclidean distance on normalized vectors instead of cosine dissimilarity?
2. If the triangle inequality is unessential for defining a legitimate distance or proximity measure for clustering purposes, are there any other constraints I should be aware of when defining such a measure?

---

There's a thread that answers my first question: Is cosine similarity identical to l2-normalized euclidean distance? It turns out that the Euclidean distance between normalized vectors varies monotonically with cosine distance (answer by Lucas). So there's nothing to gain in practice by using one rather than the other.

But I'm still wondering whether just any similarity or divergence measure is good enough as long as it intuitively models reality or some algebraic conditions have to be met so that the clustering space resembles some sort of metric space.

Answer 1

1. Cosine is equivalent to (squared) Euclidean distance on L2 normalized data. So spherical k-means is using a distance. But it's actually using squared Euclidean distance, which does not satisfy the triangle inequality (and matematicians will kill kittens every time you call it a distance). While the nearest center is the same with respect to squared Euclidean and non-squared Euclidean, the optimum center is not. The optimum k-means result is usually not the least-sum-of-distances assignment (but the least-sum-of-squared-deviations).

2. k-means cannot be used with arbitrary distances. Technically, it minimizes variance not distance... Study the convergence proof to understand why it does not converge with aebitrary metrics. It requires Bregman divergences.

3. other algorithms may have other requirements. For example single-link clustering and DBSCAN do not require triangle inequality. DBSCAN does not even require symmetry (and single-link would implicitly use $\min\{ d(x,y), d(y,x)\}$). Other clustering algorithms do not use any distance at all. So your question title is bad. Your question is solely about k-means, and even an incorrect interpretation of k-means as minimizing distance.

Answer 2

1. Without the triangle inequality, is not a distance measure.
2. There are 4 conditions:
   • Non-negativity: d(X,Y)>=0
   • Symmetry: d(X,Y)=d(Y,X)
   • The triangular inequality
   • d(X,X)=0.

Most of them are straigthforward. But a distance has to have all 4.

Try $ d(X,Y) = (\sum_{i=1}^{n}(X_i-Y_i)^r)^{(1/r)} $ as a general form, with $ r \in (0,+\infty) $.

With $r = 2 $ is the euclidean distance