Distance metric methods.

设$X$是一个集合，如果函数$d: X \times X \to R_{\geq 0}$满足以下条件，则称$(X,d)$是一个度量空间，其中$d$称为距离度量 (Distance metric)：

1. 对任意$x,y \in X$，$d(x,y)=d(y,x) \geq 0$
2. $d(x,y)=0$当且仅当$x=y$
3. (三角不等式) 对任意的$x,y,z \in X$，$d(x,y) \leq d(x,z)+d(y,z)$

在许多机器学习任务中需要用到距离度量。不同的距离度量方法各有优缺点，适用于不同的场合。本文介绍以下距离度量方法：

• 向量距离：欧几里得距离、曼哈顿距离、切比雪夫距离、闵可夫斯基距离、马哈拉诺比斯距离、余弦相似度、半正矢距离、汉明距离
• 集合距离：杰卡德距离、戴斯距离、豪斯多夫距离

1. 向量距离

向量距离衡量两个向量$x=(x_1,x_2,…,x_d)$与$y=(y_1,y_2,…,y_d)$之间的距离。常用的向量距离度量方法包括：

• 欧几里得距离 Euclidean Distance
• 曼哈顿距离 Manhattan Distance
• 切比雪夫距离 Chebyshev Distance
• 闵可夫斯基距离 Minkowski Distance
• 马哈拉诺比斯距离 Mahalanobis Distance
• 余弦相似度 Cosine Similarity
• 半正矢距离 Haversine Distance
• 汉明距离 Hamming Distance

⚪ 欧几里得距离 Euclidean Distance

欧式距离是最常见的距离测量方法之一，它衡量两点之间的线段长度，计算如下：

主要缺点:

• 欧式距离并不是尺度不变的，这意味着计算出的距离可能会根据特征的单位而有所偏斜。通常在使用这种距离测量之前，需要对数据进行归一化。而Mahalanobis距离尺度不变的。
• 此外，随着数据维度的增加，欧式距离的作用减小。这与维度诅咒(数据在高维空间中的分布是不均匀的)有关。

应用场合：对于低维数据，且需要考虑向量本身的大小时，可以使用欧氏距离。如对低维数据进行kNN或HDBSCAN。

⭐ 计算两组向量的欧氏距离

一般地，计算两组向量$A \in \mathbb{R}^{m \times d}$和$B \in \mathbb{R}^{n \times d}$之间的欧氏距离:

则首先求出以下三个矩阵：

则向量$A$和$B$之间的欧氏距离的平方矩阵计算为:

# numpy：from scratch
def EuclideanDistances(A, B):
    ABT = np.dot(A, B.transpose()) # [m, n]

    SqA = A**2 # [m, d]
    sumSqA = np.sum(SqA, axis=1, keepdims=True) # [m, 1]
    SqB = B**2 # [n, d]
    sumSqB = np.sum(SqB, axis=1)[np.newaxis,:] # [1, n]

    SqED = sumSqBEx + sumSqAEx - 2*ABT # broadcast
    ED = np.sqrt(SqED)
    return ED

# scipy:
from scipy.spatial import distance
distance.cdist(A, B, 'euclidean')

# pytorch: 
torch.cdist(A, B, p=2) # [b, m, d], [b, n, d] -> [b, m, n]

⚪ 曼哈顿距离 Manhattan Distance

曼哈顿距离也被称作出租车距离或城市街区距离。计算曼哈顿距离时考虑两个向量之间的“直角”距离，计算如下：

主要缺点：曼哈顿距离的测量并不直观，且不可能是最短路径。

应用场合：当数据集是离散或二进制的，此时欧氏距离是没有意义的，可以用曼哈顿距离。

⚪ 切比雪夫距离 Chebyshev Distance

切比雪夫距离也被称为棋盘距离，它衡量两个向量沿任何坐标维度之间的最大差异，即沿某一轴线的最大距离。计算如下：

主要缺点：切比雪夫距离并不是一个通用的距离测量方法，只适用于非常特殊的情况。

应用场合：切比雪夫距离可以用来测量从一个方格到另一个方格所需的最少步数。在实践中，切比雪夫距离经常被用于仓库物流。

⚪ 闵可夫斯基距离 Minkowski Distance

闵可夫斯基距离是在规范向量空间（$n$维实空间）中使用的一种距离度量方法，计算如下：

参数$p$选择不同时，闵可夫斯基距离退化为不同的距离：

• $p=1$：曼哈顿距离
• $p=2$：欧几里得距离
• $p=∞$：切比雪夫距离

主要缺点：实际使用时选择合适的参数$p$并不容易。

应用场合：闵可夫斯基距离的优点是是可以对参数$p$进行迭代，找到最适合的距离度量，使得距离度量具有很大的灵活性。

⚪ 马哈拉诺比斯距离 Mahalanobis Distance

（1）马氏距离的定义

马氏距离(Mahalanobis Distance)是一种距离的度量，可以看作是欧氏距离的一种修正：修正了数据中各个维度尺度不一致且相关的问题；马氏距离可以应对高维线性分布的数据中各维度间非独立同分布的情况。

单个样本点$x$的马氏距离计算如下：

样本点$x,y$之间的马氏距离计算如下：

其中$Σ$是多维随机变量的协方差矩阵，$\mu$是均值；如果协方差矩阵是单位阵，也就是各维度独立同分布，马氏距离就变成了欧氏距离。

马氏距离的物理意义是在规范化的主成分空间中的欧氏距离。所谓规范化的主成分空间就是对数据进行主成分分解，再对所有主成分分解轴做归一化，形成新的坐标轴。主成分分析把椭球分布的样本改变到另一个空间里，使其成为球状分布。而马氏距离就是在样本呈球状分布的空间里面所求得的欧式距离。

主要缺点：

1. 协方差矩阵必须满秩：计算马氏距离需要求数据的协方差矩阵的逆矩阵，要求数据要有原维度个特征值；如果没有可以考虑先进行PCA，这种情况下PCA不会损失信息。
2. 不能处理非线性流形(manifold)上的问题：马氏距离只对线性空间有效；如果要处理流形，只能在局部定义，可以用来建立KNN图。

（2）马氏距离的推导

为了使得数据分布的尺度统一且互不相关，可以将数据按照主成分方向进行旋转，让维度间相互独立，然后进行标准化。

由于主成分方向就是特征向量方向，每个方向的方差就是对应的特征值，所以只需要按照特征向量的方向旋转，然后缩放特征值的倍数即可。

下面介绍对于样本集$X$内任意两点之间的马氏距离的计算。一般地，若需要计算样本集$X,Y$之间的马氏距离，可以首先计算$[X,Y]$，然后取两个对角块元素即可。

对样本集$X$按照主成分方向进行旋转，等价于使用一个旋转矩阵$U$（正交矩阵）进行线性变换；假设变换后的数据为$F$，变换前后的样本均值为$\mu_X,\mu_F$，则有：

由于变换后$F$的维度间线性无关且每个维度自己的方差为特征值，所以满足：

马氏距离是旋转变换缩放之后的欧式距离，所以马氏距离的计算公式为：

（3）马氏距离的实现

def mahalanobis_distance(x, y):
    X = np.vstack([x, y]) # [m,d], [n,d] -> [m+n,d]
    # 对特征维度计算协方差
    S = np.cov(X.T) # [d,d]
    SI = np.linalg.inv(S) #协方差矩阵的逆矩阵
    dist = []
    # 马氏距离计算两个样本集之间的距离
    for i in range(0, x.shape[0]):
        for j in range(x.shape[0], X.shape[0]):
            delta = X[i] - X[j]
            d = np.sqrt(np.dot(np.dot(delta,SI),delta.T))
            dist.append(d)
    return np.array(dist)

⚪ 余弦相似度 Cosine Similarity

余弦相似度计算两个向量之间夹角的余弦。两个方向完全相同的向量的余弦相似度为$1$，而两个方向截然相反的向量的相似度为$-1$。余弦相似度是方向的度量，其向量的大小并不重要。计算如下：

主要缺点：余弦相似度的主要缺点是没有考虑向量的大小，只考虑其方向。在实际应用中，这意味着没有考虑数值的差异。

应用场合：对于高维数据且向量的大小并不重要时，可以使用余弦相似度。比如在文本分析中，每一个文档用不同词语出现次数组成的向量表示。当一个词语在一个文档中出现的频率高于另一个文档时，并不意味着该文档与该词的关系更大，可能是文档的长度不均匀，因此计数的大小并不重要，此使可以使用不考虑大小的余弦相似度。

⚪ 半正矢距离 Haversine Distance

半正矢距离是指球面上两点的经纬度距离，相当于球面上的欧式距离。计算如下：

主要缺点：半正矢距离假设数据点分布在球体上，在实践中很少有标准的球体。如地球并不是标准的球体。Vincenty距离则建立在椭圆体假设上。

应用场合：半正矢距离常用于导航，计算两个国家之间的飞行距离。

⚪ 汉明距离 Hamming Distance

汉明距离用来计算两个向量之间相差的位数。它通常用于比较两个长度相等的二进制字符串之间的相似度，也可以用来计算两个字符串之间不同的字符数。

主要缺点：当两个向量的长度不相等时，无法计算汉明距离。汉明距离比较两个向量的差异，而不考虑他们之间差值的大小。

应用场合：汉明距离通常用在计算机网络上传输数据时的纠错/检测。它可以用来确定二进制字符串中的失真位数。此外，汉明距离还可以用来测量分类变量之间的距离。

2. 集合距离

集合距离衡量两个集合\(A=\{a_1,a_2,...,a_m\}\)与\(B=\{b_1,b_2,...,b_n\}\)之间的距离。常用的集合距离度量方法包括：

• 杰卡德距离 Jaccard Distance
• 戴斯距离 Dice Distance
• 豪斯多夫距离 Hausdorff Distance

⚪ 杰卡德距离 Jaccard Distance

（1）杰卡德指数

Jaccard指数 (Jaccard index)也被称为交并比(Intersection over Union, IoU)指数，用于衡量样本集的相似性。它是两个样本集交集的大小除以并集的大小。计算如下：

（2）杰卡德距离

Jaccard距离是用$1$减去Jaccard指数，计算如下：

主要缺点：Jaccard指数受数据集大小影响较大。大的数据集会使并集大小显著增大。

应用场合：Jaccard指数可以用于目标检测中计算边界框交并比；也可以用于文本相似性分析，以衡量文档之间用词的重叠程度。

⚪ 戴斯距离

（1）Dice指数

Dice指数与Jaccard指数类似，都是衡量两个样本集的相似性。Dice指数的计算更为直观，衡量两个样本集的重叠百分比，其取值范围是$[0,1]$。计算如下：

（2）Dice距离

Dice距离定义为：

主要缺点：与Jaccard距离相似，受数据集大小影响较大。

应用场合：与Jaccard距离相似，通常用于图像检测或分割任务以及文本相似性分析。

⚪ 豪斯多夫距离 Hausdorff Distance

（1）豪斯多夫距离的定义

豪斯多夫距离是描述两组点集之间相似程度的一种量度，它是两个点集之间距离的一种定义形式：假设有两组集合\(A=\{a_i\},B=\{b_j\}\)，则这两个集合之间的豪斯多夫距离定义为：

上式计算了双向豪斯多夫距离，其中$h(A,B)$和$h(B,A)$分别称为从$A$集合到$B$集合和从$B$集合到$A$集合的单向豪斯多夫距离。

$h(A,B)$实际上首先对点集$A$中的每个点$a_i$到距离此点$a_i$最近的$B$集合中点$b_j$之间的距离$‖a_i-b_j‖$进行排序，然后取该距离中的最大值作为$h(A,B)$的值；$h(B,A)$同理可得。

（2）豪斯多夫距离的计算

双向豪斯多夫距离是单向距离$h(A,B)$和$h(B,A)$两者中的较大者，它度量了两个点集间的最大不匹配程度。给定集合\(A=\{a_0,a_1,…\},B=\{b_0,b_1,…\}\)，则豪斯多夫距离的计算流程为：

• 取$A$集合中的一点$a_0$，计算$a_0$到$B$集合中所有点的距离，保留最短的距离$d_0$；
• 遍历$A$集合中所有点，图中一共两点$a_0$和$a_1$，计算出$d_0$和$d_1$；
• 比较所有的距离$d_0, d_1,…$，选出最长的距离$d_1$；
• 这个最长的距离$h$是$A→B$的单向豪斯多夫距离，记为$h( A, B )$；
• 对于$A$集合中任意一点$a$，可以确定的是以点$a$为圆心，$h$为半径的圆内部必有$B$集合中的点；
• 交换$A$集合和$B$集合的角色，计算$B→A$的单向豪斯多夫距离$h( B, A )$，选出$h( A, B )$和$h( B, A )$中最长的距离，就是$A,B$集合的双向豪斯多夫距离。

豪斯多夫距离对图像中的像素点集合的边界比较敏感，所以主要用在图像分割任务中。可以使用scipy.spatial.distance.directed_hausdorff(u, v)计算两个二维数组之间的豪斯多夫距离，其中对之间的距离使用欧几里得度量来计算。

from scipy.spatial.distance import directed_hausdorff
u = np.array([(1.0, 0.0),
              (0.0, 1.0),
              (-1.0, 0.0),
              (0.0, -1.0)])
v = np.array([(2.0, 0.0),
              (0.0, 2.0),
              (-2.0, 0.0),
              (0.0, -4.0)])

# 求两个二维坐标数组之间的有向 Hausdorff 距离
directed_hausdorff(u, v)[0] # 2.23606797749979
directed_hausdorff(v, u)[0] # 3.0

# 求两个二维坐标数组之间的一般(对称)豪斯多夫距离：
max(directed_hausdorff(u, v)[0], directed_hausdorff(v, u)[0]) # 3.0

# 求生成 Hausdorff 距离(Hausdorff 对)的点的索引：
directed_hausdorff(v, u)[1:] # (3, 3)

（3）通过距离变换图近似计算豪斯多夫距离

在图像分割任务中，真实目标轮廓点集$\delta p$和预测目标轮廓点集$\delta q$之间的豪斯多夫距离可以通过真实掩码图$p$和预测掩码图$q$的距离变换图进行近似计算。

距离变换图给出了图像中的每个像素到目标边界的最短距离，则两个单向豪斯多夫距离分别计算为真实掩码图$p$和预测掩码图$q$的交集$\bar{p} \triangle \bar{q}=(\bar{p} \backslash \bar{q}) \cup(\bar{q} \backslash \bar{p})$中的像素点在两个距离变换图$d_p,d_q$中的距离的最大值。