How the squared Euclidean distance is an example of non-metric function?

Question

I am reading a book on Pattern Recognition (by Prof V Susheela Devi and Prof Murty) where in the chapter of data representation 2.3.3 the non metric similarity function is defined as those which do not obey either the triangular inequality or symmetry.

In that context, it further adds The squared Euclidean distance is itself an example of a non-metric, but it gives the same ranking as the Euclidean distance which is a metric.

Is the squared Euclidean distance different from the Euclidean distance?

How is the squared Euclidean distance non-metric?

Answer 1

Let $x, y \in \mathbb{R}^n$. The Euclidean distance $d$ is defined as $$ d(x,y) = \sqrt{\sum_{i=1}^n (x_i - y_i)^2}. $$ The squared Euclidean distance is therefore $$ d(x,y)^2 = \sum_{i=1}^n (x_i - y_i)^2. $$

---

We know that Euclidean distance is a metric. Let us check whether squared Euclidean distance is also a metric. I will use the definition from Wikipedia (Ankit Seth's definition is equivalent).

1. Non-negativity: $d(x,y)^2 \ge 0$. This one is obvious.
2. Identity of indiscernibles: $d(x,y)^2 = 0$ if and only if $x=y.$ This is true because $d$ is a metric, and $d(x,y)^2 = 0$ if and only if $d(x,y) = 0$.
3. Symmetry: $d(x,y)^2 = d(y,x)^2$. This is again true because $d$ is a metric and therefore $d(x,y) = d(y,x).$

(You can also see that 2. and 3. are true directly from the definition of $d(x,y)^2$). Looks fine so far. But:

4. Triangle inequality: Do we have $d(x,z)^2 \le d(x,y)^2 + d(y, z)^2$ for all $x, y, z \in \mathbb{R}^n$? No. Pick an arbitrary $x \in \mathbb{R}^n \setminus \{0\}$ and set $y = 2x$ and $z=3x$. Then $$ d(x,z)^2 = \sum_{i=1}^n (x_i - 3x_i)^2 = 4 \sum_{i=1}^n x_i^2 $$ and $$d(x,y)^2 + d(y,z)^2 = \sum_{i=1}^n x_i^2 + \sum_{i=1}^n x_i^2 = 2 \sum_{i=1}^n x_i^2. $$ Since $4\sum_{i=1}^n x_i^2 > 2 \sum_{i=1}^n x_i^2$, we have found a counterexample that shows that the triangle inequality does not hold.

---

What does it mean that squared Euclidean distance gives the same ranking as Euclidean distance? Suppose we have $x, y, z$ such that $d(x,y) < d(x,z)$. Then $d(x,y)^2 < d(x,z)^2$ as well: It ranks points in the same way as Euclidean distance.

This is good to know. For instance, this tells us that the $k$-nearest neighbors classifiers gives the exact same results for squared Euclidean distance and Euclidean distance.

Answer 2

First of all, I looked at the context, it is in 4.3 (Similarity between vectors) in point 4 (Proximity measures) in chapter 2.

Is the squared Euclidean distance different from the Euclidean distance?

Well, simply stated, yes it is different, the difference being same as the difference between Variance and Standard Deviation. One is a number and another is square root of that number.

How is the squared Euclidean distance non-metric?

The author says- It is tacitly assumed that the distance function, d(x, y) where x and y are patterns, is a metric..... Now look at the definition of metric, he says a metric is one which satisfies the following properties-

1. Positive reflexivity
2. Symmetry
3. Triangular inequality

He also proves that squared euclidean distance is not a metric by giving an example. Because it does not satisfy the property 3 of metric definition, squared euclidean distance is not a metric.

Hope this helps.