机器学习中的度量—— 向量距离

机器学习中的度量—— 向量距离

机器学习是当前人工智能领域的重要方向，无论是有监督学习还是无监督学习，都广泛使用各种“度量”来分析不同样本数据的差异度或相似度。良好的“度量”设计能够显著提升算法的分类或预测准确率。本文将重点介绍机器学习中常用的向量距离度量方法，包括欧式距离、曼哈顿距离、切比雪夫距离和闵科夫斯基距离。

1 向量距离

1.1 欧式距离——从勾股定理而来

让我们回顾一下中学时期学过的勾股定理。这个历史悠久的定理告诉我们，在一个直角三角形中，如果两条直角边分别为(a)和(b)，那么斜边(c)与(a)、(b)的关系满足(c^{2} = a^{2} + b^{2})。

图1 勾股定理

图2 成书于宋金时期的《测圆海镜》中的十五个勾股形

直观来看，图2中两个点之间的距离就是蓝线的长度。通过勾股定理，我们可以计算出图2中两个数据点之间的距离。

图3 可汗学院距离教程中的示例

根据勾股定理，上述两点之间的距离可以用以下式子表示：

这个最直观的距离还有一个正式的称呼，即欧几里得距离（Euclidean distance）。在二维空间中，欧氏距离的计算方法如上所述。更一般地，在笛卡尔坐标系（Cartesian Coordinates）中，如果点(x = (x_1, x_2, ..., x_n))和点(y = (y_1, y_2, ..., y_n))是两个欧氏空间的点，则点(x)和点(y)的欧氏距离为：

[
\begin{array}{l}
d_{Euclidean}(x,y) = d_{Euclidean}(y,x) = \sqrt{(|x_1 - y_1|^2 + |x_2 - y_2|^2 + \cdots + |x_n - y_n|^2)} \
\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad ; = \sqrt{\sum\limits_{i=1}^n{|x_i - y_i|^2}} \
\end{array}
]

笛卡尔坐标系是一种正交坐标系。参阅图4，二维的直角坐标系是由两条相互垂直、相交于原点的数线构成的。在平面内，任何一点的坐标是根据数轴上对应的点的坐标设定的。

图4 一个直角坐标系

1.2 曼哈顿距离——行走在纽约曼哈顿街道上

曼哈顿距离（Manhattan distance）是由十九世纪的赫尔曼·闵可夫斯基所创辞汇，用以标明两个点在标准坐标系上的绝对轴距之总和。例如，在平面上，坐标((x_1, x_2))的点(P_1)与坐标((y_1, y_2))的点(P_2)的曼哈顿距离为：

[
|x_1 - y_1| + |x_2 - y_2|
]

如图所示为曼哈顿与欧几里得距离。由曼哈顿距离和欧式距离定义可知两点曼哈顿距离为12，其中红、蓝与黄线分别表示几种不同曼哈顿距离；两点的欧式距离为6√2其中绿线表示唯一的欧几里得距离。

图5 曼哈顿与欧几里得距离

图6 到蓝点的曼哈顿距离为2的所有点构成的“单位圆”

上面是二维空间中曼哈顿距离，更为一般的情况为：在笛卡尔坐标系中如果点(x = (x_1, x_2,..., x_n)) 和点 (y = (y_1, y_2, ..., y_n)) 是两个欧式空间点，则点(x)和点(y)的曼哈顿距离为:

[
\begin{array}{l}
d_{Manhattan}(x,y) = d_{Manhattan}(y,x) = |x_1 - y_1| + |x_2 - y_2| + \cdots + |x_n - y_n| \
\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad ;;; = \sum\limits_{i=1}^n{|x_i - y_i|} \
\end{array}
]

1.3 切比雪夫距离——来下盘国际象棋吧

切比雪夫距离（Chebyshev distance）或是向量空间中的一种度量，二个点之间的距离定义为其各座标数值差的最大值。切比雪夫距离得名自俄罗斯数学家切比雪夫。例如在平面上，坐标((x_1, x_2))的点(P_1)与坐标((y_1, y_2))的点(P_2)的切比雪夫距离为：

[
\max(|x_1 - y_1|, |x_2 - y_2|)
]

若将国际象棋棋盘放在二维直角座标系中，格子的边长定义为1，座标的x轴及y轴和棋盘方格平行，原点恰落在某一格的中心点，则王从一个位置走到其他位置需要的步数恰为二个位置的切比雪夫距离，因此切比雪夫距离也称为棋盘距离。由于王可以往斜前或斜后方向移动一格，因此可以较有效率的到达目的的格子。例如位置F6和位置E2的切比雪夫距离为4。任何一个不在棋盘边缘的位置，和周围八个位置的切比雪夫距离都是1。

图7 国际象棋棋盘上二个位置间的切比雪夫距离

上面是二维空间中切比雪夫距离，更为一般情况为:在笛卡尔坐标系中如果点(x = (x_1, x_2,..., x_n)) 和点 (y = (y_1, y_2, ..., y_n)) 是两个欧式空间点，则点(x)和点(y)切比雪夫距离为:

1.4 闵科夫斯基距离——大统一论

闵科夫斯基距离（Minkowski distance）实际上是欧式距离、曼哈顿距离、切比雪夫距离在笛卡尔坐标系下的一种推广，闵科夫斯基距离将上述所有距离都统一在一个框架中。在笛卡尔坐标系中如果点(x = (x_1, x_2,..., x_n)) 和点 (y = (y_1, y_2, ..., y_n))是两个欧式空间点，则点(x)和点(y)的(p)阶闵科夫斯基距离为:

[
\begin{array}{l}
d_{p-Minkowski}(x,y) = d_{p-Minkowski}(y,x) = \left( (|x_1 - y_1|^p + |x_2 - y_2|^p + \cdots + |x_n - y_n|^p) \right)^{\frac{1}{p}} \
\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad ;;; = \left( \sum\limits_{i=1}^n{|x_i - y_i|^p} \right)^{\frac{1}{p}} \
\end{array}
]

当(p=1)的时候，1阶闵科夫斯基距离等价于曼哈顿距离

[
\begin{array}{l}
d_{1-Minkowski}(x,y) = d_{1-Minkowski}(y,x) = \left( (|x_1 - y_1|^1 + |x_2 - y_2|^1 + \cdots + |x_n - y_n|^1) \right)^{\frac{1}{1}} \
\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad ;;;;;;; = \sum\limits_{i=1}^n{|x_i - y_i|} \
\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad ;;;;;;; = |x_1 - y_1| + |x_2 - y_2| + \cdots + |x_n - y_n| \
\end{array}
]

当(p=2)的时候，2阶闵科夫斯基距离等价于欧几里得距离

[
\begin{array}{l}
d_{2-Minkowski}(x,y) = d_{2-Minkowski}(y,x) = \left( (|x_1 - y_1|^2 + |x_2 - y_2|^2 + \cdots + |x_n - y_n|^2) \right)^{\frac{1}{2}} \
\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad ;;;;;;; = \sqrt{\sum\limits_{i=1}^n{|x_i - y_i|^2}} \
\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad ;;;;;;; = \sqrt{(|x_1 - y_1|^2 + |x_2 - y_2|^2 + \cdots + |x_n - y_n|^2)} \
\end{array}
]

当(p=\infty)的时候，(\infty)阶闵科夫斯基距离等价于切比雪夫距离

[
\begin{array}{l}
d_{\infty-Minkowski}(x,y) = d_{\infty-Minkowski}(y,x) = \lim_{x \to \infty} \left( \sum\limits_{i=1}^n{|x_i - y_i|^p} \right)^{\frac{1}{p}} \
\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad ;;;;;;; = \max(|x_1 - y_1|, |x_2 - y_2|, \cdots, |x_n - y_n|) \
\end{array}
]