Conditions on a legitimate distance measure for clustering

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.

• It is confusing to call the cosine a "proximity measure," because its value decreases as the distance increases. It can readily be adjusted to give a value that--at least locally--truly is a distance. – whuber Sep 29 '16 at 22:02
• 1. Terminology: "proximity" is generic term for distance (=dissimilarity) or similarity. 2. Cosine is similarity, while a "metric" (with the 3 axioms of metricity) is a subclass of distances. 3. sqrt(1-cos) is euclidean distance, which is, of course, a metric. – ttnphns Sep 30 '16 at 12:13
• Would there be anything to gain by enforcing the triangle inequality? If the triangle inequality is unessential for defining a legitimate distance... for clustering It depends on the clustering method and the kind of data (see pt2 here). Some methods require euclidean distance or at worst case other metric distance. Other methods will be OK to use with any distances or similarities. Some special methods may require special proximity measures. – ttnphns Sep 30 '16 at 12:31
• See this related thread about triangular inequality of some correlation-based distances (the same holds also for cosine-based). – ttnphns Sep 30 '16 at 12:40

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.

• But it's actually using squared Euclidean distance, which does not satisfy the triangle inequality. There one should be wary not to mix up technical (in computations) usage of a distance with the conceptual (theoretical) distance implied. For example, hierarchical centroid method processes squared euclidean, but the distance actually implied as the proximity between clusters is nonsquared euclidean. Your point 1. suppresses that distinction. – ttnphns Sep 30 '16 at 22:32
• The first two points are specific to k-means, and k-means tries to minimize the sun of squared deviations; not the sum of Euclidean distances. So that distinction is not necessary here; both technically and conceptually, k-means is based on squares. For other methods, e.g. DBSCAN, you get the same result with both (if you substitute $\vareps$ by $\vareps^2$). – Anony-Mousse Oct 1 '16 at 5:22
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