Clustering Distance Measures

Definition of a distance

A distance on the space \(\mathbb{R}^n,\:n\geq 2\), is a function \(d:\mathbb{R}^n\times\mathbb{R}^n\rightarrow [0,\infty)\).

It must satisfy some required properties.

P1. \(d(\mathbf{x},\mathbf{y})= 0\iff \mathbf{x}=\mathbf{y}\) (identity of indiscernibles);

P2. \(d(\mathbf{x},\mathbf{y})= d(\mathbf{y},\mathbf{x})\) (symmetry);

P3. \(d(\mathbf{x},\mathbf{y})+d(\mathbf{y},\mathbf{z})\geq d(\mathbf{x},\mathbf{z})\) (triangle inequality),

where \(\mathbf{x}=(x_1,\cdots,x_n)\), \(\mathbf{y}=(y_1,\cdots,y_n)\) and \(\mathbf{z}=(z_1,\cdots,z_n)\) are any three vectors of \(\mathbb{R}^n\).

Classical distances

1. Euclidean distance \[d(\mathbf{x},\mathbf{y})=\sqrt{\sum_{i=1}^n (x_i-y_i)^2}\]

2. Manhattan distance \[d(\mathbf{x},\mathbf{y}) =\sum_{i=1}^n |x_i-y_i|\]

Both are special casesof the Minkowski distance (resp. p = 2 and p=1).

\[ d(\mathbf{x},\mathbf{y}) = \left[\sum_{i=1}^n |x_i-y_i|^{p}\right]^{1/p},\: p\geq 1 \]

To proof of the triangular inequality is bases onthe Minkowski inequality

\[ \left[\sum_{i=1}^n |x_i+y_i|^{p}\right]^{1/p}\leq \left[\sum_{i=1}^n |x_i|^{p}\right]^{1/p} + \left[\sum_{i=1}^n |y_i|^{p}\right]^{1/p},\:p\geq 1. \]

One proof of Minkowski inequality requires the use of Hölder inequality

\[ \sum_{i=1}^n |x_iy_i|\leq \left[\sum_{i=1}^n |x_i|^{p}\right]^{1/p} \left[\sum_{i=1}^n |y_i|^{q}\right]^{1/q},\:\frac{1}{p}+\frac{1}{q}=1,\:p,q> 1. \] Note that the equality holds iff at least one vector is null or the two vectors are proportional.

Note that the above inequality implies

\[ \sum_{i=1}^n |x_i|\leq \left[\sum_{i=1}^n |x_i|^{p}\right]^{1/p} ,\:p\geq 1. \] To prove Minkowski, notice that

\[ |x_i+y_i|^{p}=|x_i+y_i| |x_i+y_i|^{p-1}\leq (|x_i|+|y_i|) |x_i+y_i|^{p-1},\;i=1,\cdots, n, \] so that

\[ |x_i+y_i|^{p}\leq |x_i| |x_i+y_i|^{p-1}+ |y_i||x_i+y_i|^{p-1},\;i=1,\cdots, n, \]

Applying Hölder inequality, we get \[ |x_i+y_i|^{p}= |x_i+y_i| |x_i+y_i|^{p-1},\;i=1,\cdots, n \]

Correlation-based distances

1. Pearson correlation distance \[ {\sqrt{\sum_{i=1}^n (x_i-\bar{x})^2\sum_{i=1}^n (y_i-\bar{y})^2}}\]

2. Eisen cosine correlation distance

3. Spearman correlation distance

4. Kendall correlation distance