机器学习中的距离度量

Reference

• 距离计算方法总结
• 几种距离度量方法比较
• 欧几里得距离、曼哈顿距离和切比雪夫距离
• 向量相似度匹配之“闵可夫斯基距离”
• 标准化欧式距离
• 马氏距离
• 马氏距离和欧式距离详解

【概述】

在机器学习中的分类、聚类问题中，常常需要估算不同样本之间的相似性度量（Similarity Measurement），这时会计算样本间的距离（Distance）来作为度量的标准

在实际应用中，采用不同的计算距离的方法，关系到处理问题结果的正确与否

【欧氏距离】

欧氏距离（Euclidean Distance）是最基础的一种距离，源自欧氏空间中两点间的距离公式

欧氏距离能够体现个体数值特征的绝对差异，所以更多的用于需要从维度的数值大小中体现差异的分析，例如：使用用户行为指标分析用户价值的相似度或差异

当数据集有很多特征，且任意一对个体之间的欧氏距离都相等，那么就无法通过欧氏距离进行比较

二维平面上，$A(x_1,y_1)$ 和 $B(x_2,y_2)$ 两点间的欧氏距离为：

$$E(A,B) = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$$

三维空间中，$A(x_1,y_1,z_1)$ 和 $B(x_2,y_2,z_2)$ 两点间的欧氏距离为：

$$E(A,B)= \sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2}$$

对于 $n$ 维实数向量空间 $\mathbb{R}^n$，其中的任意两个向量 $\mathbf{x_i}=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})^T\in \mathbb{R}^n$， $\mathbf{x_j}=(x_j^{(1)},x_j^{(2)},…,x_j^{(n)})^T\in \mathbb{R}^n$，它们的欧氏距离为：

$$\begin{align} E(\mathbf{x_i},\mathbf{x_j}) &= \sqrt{\sum_{l=1}^n(x_i^{(l)}-x_j^{(l)})^2} \notag \\ &= \sqrt{(\mathbf{x_i}-\mathbf{x_j})(\mathbf{x_i}-\mathbf{x_j})^T} \notag \end{align}$$

【曼哈顿距离】

曼哈顿距离（Manhattan distance），又称曼氏距离，想象在高楼林立的曼哈顿街道上，从一个十字路口开车到另一个十字路口，除非穿越大楼，否则驾驶距离就是这个“曼哈顿距离”，即两个点在标准坐标系上的绝对轴距总和

曼哈顿距离在某些情况下具有极高的稳定性，但是如果数据集中某些特征值很大，用曼哈顿距离的话，这些特征会掩盖其他特征间的邻近关系

二维平面上，$A(x_1,y_1)$ 和 $B(x_2,y_2)$ 两点间的曼哈顿距离为：

$$M(A,B)=|x_1-x_2| + |y_1-y_2|$$

三维空间中，$A(x_1,y_1,z_1)$ 和 $B(x_2,y_2,z_2)$ 两点间的曼哈顿距离为：

$$M(A,B)= |x_1-x_2| + |y_1-y_2| + |z_1-z_2|$$

对于 $n$ 维实数向量空间 $\mathbb{R}^n$，其中的任意两个向量 $\mathbf{x_i}=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})^T\in \mathbb{R}^n$， $\mathbf{x_j}=(x_j^{(1)},x_j^{(2)},…,x_j^{(n)})^T\in \mathbb{R}^n$，它们的曼哈顿距离为：

$$E(\mathbf{x_i},\mathbf{x_j}) = \sum_{l=1}^n|x_i^{(l)}-x_j^{(l)}|$$

【切比雪夫距离】

定义

切比雪夫距离（Chebyshev distance）是向量空间中的一种度量，二个点之间的距离定义为其各坐标数值差的最大值

在国际象棋中，国王从 $A(x_1,y_1)$ 走到 $B(x_2,y_2)$ 最少需要的步数就是切比雪夫距离，即：

$$C(A,B)=\max (|x_1-x_2|,|y_1-y_2|)$$

对于 $n$ 维实数向量空间 $\mathbb{R}^n$，其中的任意两个向量 $\mathbf{x_i}=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})^T\in \mathbb{R}^n$， $\mathbf{x_j}=(x_j^{(1)},x_j^{(2)},…,x_j^{(n)})^T\in \mathbb{R}^n$，它们的欧氏距离为：

$$\begin{align} E(\mathbf{x_i},\mathbf{x_j}) &= \max\{ |x_i^{(1)}-x_j^{(1)}|,|x_i^{(2)}-x_j^{(2)}|,...,|x_i^{(n)}-x_j^{(n)}| \} \notag \\ &= \max_l\{|x_i^{(l)}-x_j^{(l)}|\} \notag \\ &= \lim_{i\rightarrow +\infty} \sum_{l=1}^n|x_i^{(l)}-x_j^{(l)})|^{\frac{1}{i}} \notag \end{align}$$

注：最后一步由放缩法和夹逼法则推导得来

与曼哈顿距离的转化

切比雪夫距离与曼哈顿距离可以互相转化

考虑最简单的情况，在二维坐标系中，设原点为 $(0,0)$

若用曼哈顿距离表示，与原点距离为 $1$ 的点会构成一个边长为 $\sqrt 2$ 的正方形

若用切比雪夫距离表示，与原点距离为 $1$ 的点会构成一个边长为 $2$ 的正方形

仔细对比可以发现，这两种距离可以通过某种变换相互转化，即：

• 将一个点 $(x,y)$ 变为 $(x+y,x-y)$ 后，原坐标系曼哈顿距离 = 新坐标系切比雪夫距离

• 将一个点 $(x,y)$ 变为 $(\frac{x+y}{2},\frac{x-y}{2})$ 后，原坐标系切比雪夫距离 = 新坐标系曼哈顿距离

【闵科夫斯基距离】

闵科夫斯基距离（Minkowski Distance），又称闵氏距离或 $L_p$ 距离，其实际上并不是一种距离，而是一组距离的定义

对于 $n$ 维实数向量空间 $\mathbb{R}^n$，其中的任意两个向量 $\mathbf{x_i}=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})^T\in \mathbb{R}^n$， $\mathbf{x_j}=(x_j^{(1)},x_j^{(2)},…,x_j^{(n)})^T\in \mathbb{R}^n$，它们的闵氏距离为：

$$L_p(\mathbf{x_i},\mathbf{x_j})=\bigl( \sum_{l=1}^n |x_i^{(l)}-x_j^{(l)}|^p \bigr)^{\frac{1}{p}},\quad p\geq1$$

• 当 $p=1$ 时，$L_1(\mathbf{x_i},\mathbf{x_j})$ 是曼哈顿距离
• 当 $p=2$ 时，$L_2(\mathbf{x_i},\mathbf{x_j})$ 是欧氏距离
• 当 $p\rightarrow \infty$ 时，$L_{\infty}(\mathbf{x_i},\mathbf{x_j})$ 是切比雪夫距离

下图给出了二维空间 $p$ 取不同值时，与原点的距离 $L_p=1$ 的点的图形

根据可变参数 $p$ 的不同，闵氏距离可表示为一类的距离，其包括了曼哈顿距离、欧氏距离、切比雪夫距离，但无论是曼哈顿距离、欧氏距离、切比雪夫距离，都存在明显的缺点

举例来说，对于二维样本（身高，体重），假设有：A(170,50)、B(180,50)、C(170,60)，此时的 A 与 B 闵氏距离等于 A 与 C 的闵氏距离，但身高的 10cm 并不等价于体重的 10kg

也就是说，其将各分量的量纲当做相同来看待，且没有考虑到各个分量的分布可能是不同的

【标准化欧氏距离】

标准化欧式距离（Standardized Euclidean distance），是针对欧氏距离的缺点而作的一种改进方案

考虑到数据各维分量的尺度是不同的，那么就先将各分量都进行标准化，使得各维度的数据分别满足标准正态分布

假设样本集 $X$ 的均值为 $m$，标准差为 $s$，那么 $X$ 的标准化变量 $X’$ 表示为：

$$X'=\frac{X_i-m}{s}$$

对于 $n$ 维实数向量空间 $\mathbb{R}^{n}$，其中的任意两个向量 $\mathbf{x_i}=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})^T\in \mathbb{R}^n$， $\mathbf{x_j}=(x_j^{(1)},x_j^{(2)},…,x_j^{(n)})^T\in \mathbb{R}^n$ 的标准化欧氏距离为：

$$SE(\mathbf{x_i}',\mathbf{x_j}')= \sqrt{\sum_{l=1}^n(\frac{x_i^{(l)}-x_j^{(l)}}{s_l})^2}$$

如果将方差的倒数看成是一个权重，这个公式可以看成是一种加权欧氏距离（Weighted Euclidean distance）

在实际应用中，对长方体区域进行聚类的时，按照普通的距离聚类大多是圆形的区域，无法满足要求，这时候要采用标准的欧式距离

举例来说，当对于长宽比为 $2:1$ 的矩形进行聚类时，采用标准欧拉距离有：

$$s=\sqrt{(\frac{x_2-x_1}{2})^2+(\frac{y_2-y_1}{1})^2}$$

【马氏距离】

引入

下图有两个正态分布总体，他们的均值分别是 $a$、$b$，但方差不同，现在有一点 $A$，则 $A$ 点离哪个总体更近一些？或者说 $A$ 有更大的概率属于谁？

若以欧式距离来计算，那么显然 A 属于 b，但以马氏距离来看，A 离左边的 a 更近一些。

马氏距离能够表示点与一个分布之间的距离，它是一种有效的计算两个未知样本集的相似度的方法。

定义

马氏距离（Mahalanobis Distance）是一种基于样本分布的一种距离，其量纲无关，能排除变量之间的相关性的干扰

就其物理意义而言，马氏距离是在规范化的主成分空间中的欧式距离。规范化的主成分空间是指利用主成分分析对一些数据进行主成分分解，再对所有主成分分解轴归一化，形成新的坐标轴，由这些坐标轴张成的空间就是规范化的主成分空间

马氏距离的计算是建立在总体样本的基础上，如果拿同样的两个样本，放在两个不同的总体中，最后计算出的两个样本间的马氏距离通常是不同的，除非这两个总体的协方差矩阵正好相同

对于 $n$ 维实数向量空间 $\mathbb{R}^n$，其中的任意两个向量 $\mathbf{x_i}=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})^T\in \mathbb{R}^n$， $\mathbf{x_j}=(x_j^{(1)},x_j^{(2)},…,x_j^{(n)})^T\in \mathbb{R}^n$，它们间的平方欧氏距离可写为：

$$\begin{align*} E(\mathbf{x_i},\mathbf{x_j})^2 &= ||\mathbf{x}_i-\mathbf{x}_j||^2_2 \\ &= \sum_{l=1}^n(x_i^{(l)}-x_j^{(l)})^2 \end{align*}$$

若假定不同特征的重要性不同，则可引入特征权重 $w$，即有：

$$\begin{align*} E_{w}(\mathbf{x_i},\mathbf{x_j})^2 &= ||\mathbf{x}_i-\mathbf{x}_j||^2_2 \\ &= \sum_{l=1}^n w_{l}(x_i^{(l)}-x_j^{(l)})^2 \\ &= (\mathbf{x}_i-\mathbf{x}_j)^T W (\mathbf{x}_i-\mathbf{x}_j) \end{align*}$$

其中，$w_l\geq 0$，$W=\text{diag}(w)$ 为对角阵

特征矩阵 $W$ 的非对角线元素均为 $0$，这意味着坐标轴是正交的，即与特征无关

但在实际问题中，特征对应的坐标轴并非正交，为此，通常将特征矩阵 $W$ 替换为一个普通的半正定对称矩阵 $M$，由此便有了马氏距离：

$$\begin{align*} \text{Mah}(\mathbf{x_i},\mathbf{x_j})^2 &= (\mathbf{x}_i-\mathbf{x}_j)^T M (\mathbf{x}_i-\mathbf{x}_j) \end{align*}$$

其中，$M$ 被称为度量矩阵，其是半正定对称矩阵，即必有正交基 $P$ 使得 $M=PP^T$

在机器学习中，马氏距离常用于度量学习

【余弦距离】

几何中，余弦距离（Cosine Distance）可用来衡量两个向量方向的差异，在机器学习中，借用这一概念来衡量样本向量间的差异

二维平面上，$A(x_1,y_1)$、$B(x_2,y_2)$ 两向量间的余弦距离为：

$$\begin{align*}cos\theta &= \frac{A \cdot B}{|A| |B|} \\ &= \frac{x_1x_2+y_1y_2}{\sqrt{x_1^2+y_1^2}\sqrt{x_2^2+y_2^2}} \end{align*}$$

对于 $n$ 维实数向量空间 $\mathbb{R}^n$，其中的任意两个向量 $\mathbf{x_i}=(x_i^{(1)},x_i^{(2)},…,x_i^{(n)})^T\in \mathbb{R}^n$， $\mathbf{x_j}=(x_j^{(1)},x_j^{(2)},…,x_j^{(n)})^T\in \mathbb{R}^n$ 的余弦距离为：

$$\begin{align*}cos\theta &= \frac{\mathbf{x_i} \cdot \mathbf{x_j}}{|\mathbf{x_i}| |\mathbf{x_j}|} \\ &= \frac{\sum\limits_{l=1}^nx_i^{(l)}x_j^{(l)}}{\sqrt{\sum\limits_{l=1}^nx_i^{(l)}}\sqrt{\sum\limits_{l=1}^n x_j^{(l)}}} \end{align*}$$

夹角余弦的取值范围为 $[-1,1]$，余弦越大表示两个向量的夹角越小，余弦越小表示两向量的夹角越大，当两个向量的方向相同时，余弦取最大值 $1$；当两个向量方向完全相反时，余弦取最小值 $-1$

【汉明距离】

汉明距离（Hamming distance）是一个概念，它定义为两个数字对应二进制位不同的位置的数目，其在信息论、密码学等领域都有应用。

例如：1011101 与 1001001 之间的汉明距离是 2

【杰卡德距离】

定义

在给出杰卡德距离的定义前，先引入杰卡德相似系数（Jaccard Similarity Coefficient）

杰卡德相似系数是衡量两个集合的相似度的一种指标，其定义为两个集合 $A$ 和 $B$ 的交集元素在 $A$、$B$ 的并集中所占的比例，一般用 $J(A,B)$ 来表示 $A$、$B$ 两个集合的杰卡德相似系数

即：

$$J(A,B)=\frac{|A \cap B|}{|A \cup B|}$$

而杰卡德距离（Jaccard Distance）与杰卡德相似系数相反，其用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度即：

$$J_{\delta}(A,B)=1-J(A,B)=\frac{|A \cup B|-|A \cap B|}{|A \cup B|}$$

应用

在实际应用中，一般将杰卡德相似系数用于衡量样本的相似度

假设样本 $A$ 与样本 $B$ 是两个 $n$ 维向量，且所有维度的取值都是 $0$ 或 $1$，例如：$A(0,1,1,1)$ 和 $B(1,0,1,1)$

将每个样本看成是一个集合，$1$ 表示集合包含该元素，$0$ 表示集合不包含该元素

定义：

• $p$ ：样本 $A$ 与 $B$ 都是 $1$ 的维度的个数
• $s$ ：样本 $A$ 与 $B$ 都是 $0$ 的维度的个数
• $q$ ：样本 $A$ 是 $1$，样本 $B$ 是 $0$ 的维度的个数
• $r$：样本 $A$ 是 $0$，样本 $B$ 是 $1$ 的维度的个数

那么样本 $A$ 与 $B$ 的杰卡德相似系数可以表示为：

$$J=\frac{p}{p+q+r}$$

这里的 $p+q+r$ 可理解为 $A$ 与 $B$ 的并集的元素个数，而 $p$ 可理解为 $A$ 与 $B$ 的交集的元素个数

而样本 $A$ 与 $B$ 的杰卡德距离表示为：

$$J_{\delta}=\frac{q+r}{p+q+r}$$