机器学习中的距离计算

发表于 | 分类于

距离定义：基础知识

在机器学习中，我们经常需要计算样本之间的差异，进而评价个体的相似性和类别等信息。特征空间中两个样本之间的距离就是两个样本相似性的一种反映。常见的分类和聚类算法，如k近邻、k-means、层次聚类等、等都会选择一种距离或相似性的度量方法。根据数据特性的不同，可以采用不同的度量方法。一般而言，定义一个函数 d ( x , y ) d(x,y) d(x,y), 若它是一种“距离度量”，则需要满足一些基本性质：

非负性： d ( x , y ) ≥ 0 两点之间的距离一定是非负的
同一性： d ( x , y ) = 0 ⇔ x = y 当且仅当两个点是同一个点时，距离为0
对称性： d ( x , y ) = d ( y , x ) 交换两个点的位置，不会对两点见的距离计算产生影响
三角不等式： d ( x , y ) ≤ d ( x , z ) + d ( z , y ) 三角形定理任意两点距离之和大于第三个点

image

距离定义（一）：欧几里得距离（Euclidean Distance）

欧几里得距离或欧几里得度量是欧几里得空间中两点间的即直线距离。使用这个距离，欧氏空间成为度量空间，相关联的范数称为欧几里得范数。
$$
d(x, y)=({\sum_{i=1}^n|x_i-y_i|^2})^{1/2} = \sqrt{(x_1-y_1)^2+(x_2-y_2)^2+…+(x_n-y_n)^2}
$$

python 计算距离的代码

1
2
3
4
5
def EuclideanDistance(x, y):
    import numpy as np
    x = np.array(x)
    y = np.array(y)
    return np.sqrt(np.sum(np.square(x-y)))

距离定义（二）：曼哈顿距离（Manhattan Distance）

曼哈顿距离是种使用在几何度量空间的几何学用语，用以标明两个点在标准坐标系上的绝对轴距总和。

下图中红线代表曼哈顿距离，绿色代表欧氏距离，也就是直线距离，而蓝色和黄色代表等价的曼哈顿距离。
image

曼哈顿距离在2维平面是两点在纵轴上的距离加上在横轴上的距离，即：

$$
d(x, y)=({\sum_{i=1}^n|x_i-y_i|^1})^{1/1}=∣ x 1 − y 1 ∣ + ∣ x 2 − y 2 ∣
$$

对于一个具有正南正北、正东正西方向规则布局的城镇街道（如：曼哈顿），从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离，因此，曼哈顿距离又称为出租车距离。曼哈顿距离不是距离不变量，当坐标轴变动时，点间的距离就会不同。曼哈顿距离示意图在早期的计算机图形学中，屏幕是由像素构成，是整数，点的坐标也一般是整数，原因是浮点运算很昂贵，很慢而且有误差，如果直接使用AB的欧氏距离（欧几里德距离：在二维和三维空间中的欧氏距离的就是两点之间的距离），则必须要进行浮点运算，如果使用AC和CB，则只要计算加减法即可，这就大大提高了运算速度，而且不管累计运算多少次，都不会有误差。

多维空间中的曼哈顿距离：
$$
d(x, y)=\sum_{i=1}^n|x_i-y_i|
$$

python 计算距离的代码

1
2
3
4
5
def ManhattanDistance(x, y):
    import numpy as np
    x = np.array(x)
    y = np.array(y)
    return np.sum(np.abs(x-y))

距离定义（三）：闵可夫斯基距离（Minkowski Distance）

其实细心的话，可以发现我们在介绍曼哈顿和欧几里得公式时候，有一个相似格式的前置公式。
$$ d(x, y)=({\sum_{i=1}^n|x_i-y_i|^1})^{1/1} 和 d(x, y)=({\sum_{i=1}^n|x_i-y_i|^2})^{1/2} $$

而 闵可夫斯基距离其实就是对这两个公式的一种抽象，所以闵可夫斯基距离本身不是一个具体的距离计算方式，而是一类特定格式的距离计算类型。
$$ d(x, y)=({\sum_{i=1}^n|x_i-y_i|^p})^{1/p} $$
而之前介绍的欧几里得距离（p=2）和曼哈顿距离（p=1）就是闵可夫斯基距离的两种最常用的特例。

为了帮助大家更感观的理解感受，
从计算公式可以知道，坐标平面上到原点的欧氏距离(p=2)相等的所有点组成的形状是一个圆，比如距离为1，则为一个半径为1的圆。类似的当p=1时，形状为菱形，p趋于∞时，形状是正方形，如图2：
alt text
而针对不同的p值，我们到原地距离相同的点所构成的同行分别示例如下：
alt text

注意，当p<1时，闵可夫斯基距离不再满足直递性（即三角不等式），举个简单的反例：假设点xxi=(0,0)，xxj=(1,1)，和另一点xxu=(0,1)，当p<1时，带入公式（1.1）计算xxi=(0,0)到xxj=(1,1)的距离等于(1+1)1/p>2, 而xxu=(0,1)到这两个点的距离都是1。

python 计算距离的代码

1
2
3
4
5
def MinkowskiDistance(x, y, p):
    import math
    import numpy as np
    zipped_coordinate = zip(x, y)
    return math.pow(np.sum([math.pow(np.abs(i[0]-i[1]), p) for i in zipped_coordinate]), 1/p)

距离定义（四）：切比雪夫距离（Chebyshev Distance）

是闵可夫斯基距离的另一个特例 (p=+∞)，在p=+∞ 时候，我们可以对原公式进行如下转换
$$ d(x, y)=({\sum_{i=1}^n|x_i-y_i|^{+∞}})^{1/+∞} $$
$$= (|x_1-y_1|^{+∞}+|x_2-y_2|^{+∞}+…+|x_n-y_n|^{+∞})^{1/+∞} $$
$$ ≈\max_{1<=i<=n}(|x_i-y_i|^{+∞})^{1/+∞} $$
$$ ≈(\max_{1<=i<=n}(|x_i-y_i|)) $$
基于上述结果，所以我们切比雪夫距离，实际计算的就是两点之间距离向量投影到所有维度后，投影距离最大的单维度上的距离。

国际象棋棋盘上二个位置间的切比雪夫距离是指王要从一个位子移至另一个位子需要走的步数。由于王可以往斜前或斜后方向移动一格，因此可以较有效率的到达目的的格子。下图是棋盘上所有位置距王位置的切比雪夫距离。

python 计算距离的代码

1
2
3
4
5
def ChebyshevDistance(x, y):
    import numpy as np
    x = np.array(x)
    y = np.array(y)
    return np.max(np.abs(x-y))

距离定义（五）：标准化的欧几里得距离（Standardized Euclidean Distance）

其实在介绍切比雪夫距离时候，我们就可以发现一个问题，两个点在不同维度的距离上是可能是不一致的，虽然在欧几里得距离（p=2）的影响没有切比雪夫距离（p=+∞）大，但是在某些情况下，这个影响依然是无法忽略的，所以产生了标准化的欧几里得距离，和常规欧几里得距离的区别就是，我们在计算距离前，先对各个维度的距离进行标准化，将各个分量都“标准化”到均值、方差相等的区间。
$$ X∗=(X−m​)/s $$
X* 为标准化后的值， X 为原值， m 为分量的均值， s 为分量的标准差。所以 n n n维空间中标准化的欧几里得距离为：
$$ d ( x , y ) = \sqrt{\sum_{i=1}^n (( x_i − y_i)/ s_i )^2} $$

python 计算距离的代码

1
2
3
4
5
6
7
8
def StandardizedEuclideanDistance(x, y):
    import numpy as np
    x = np.array(x)
    y = np.array(y)
    
    X = np.vstack([x,y])
    sigma = np.var(X, axis=0, ddof=1)
    return np.sqrt(((x - y) ** 2 /sigma).sum())

距离定义（六）：马氏距离（Mahalanobis Distance）

距离定义（七）：兰氏距离（Lance and Williams Distance）/堪培拉距离（Canberra Distance）

距离定义（八）：余弦距离（Cosine Distance）

余弦距离是一种用于测量两个向量方向的相似性的度量方法，而不考虑它们的大小。对于两个向量 $𝑢u$ 和 $𝑣v$，余弦距离可以表示为它们的夹角的余弦值的补数：
$$cos(\theta)=1-\frac{u·v}{||u|| · ||v||}$$
其中 $u·v $表示向量 $u$ 和 $v$ 的点积，$||u|| · ||v||$ 表示向量 $u$ 和 $v$ 的范数。

距离定义（九）：测地距离（Geodesic Distance）

距离定义（十）： 布雷柯蒂斯距离（Bray Curtis Distance）

距离定义（十一）：汉明距离（Hamming Distance）

距离定义（十二）：编辑距离（Edit Distance，Levenshtein Distance）

距离定义（十三）：杰卡德距离（Jaccard Distance）和杰卡德相似系数（Jaccard Similarity Coefficient）

距离定义（十四）：Ochiia系数（Ochiia Coefficient）

距离定义（十五）：Dice系数（Dice Coefficient）

距离定义（十六）：豪斯多夫距离（Hausdorff Distance）

距离定义（十七）：皮尔逊相关系数（Pearson Correlation）

距离定义（十八）：卡方距离（Chi-square Measure）

距离定义（十九）：交叉熵（Cross Entropy）

距离定义（二十）：相对熵（Relative Entropy）/KL散度（Kullback-Leibler Divergence）

距离定义（二十一）：JS散度（Jensen–Shannon Divergence）

距离定义（二十二）：海林格距离（Hellinger Distance）

距离定义（二十三）：α-散度（α-Divergence）

距离定义（二十四）：F-散度（F-Divergence）

距离定义（二十五）：布雷格曼散度（Bregman Divergence）

距离定义（二十六）：Wasserstein距离（Wasserstei Distance）/EM距离（Earth-Mover Distance）

距离定义（二十七）：巴氏距离（Bhattacharyya Distance）

距离定义（二十八）：最大均值差异（Maximum Mean Discrepancy, MMD）

距离定义（二十九）：点间互信息（Pointwise Mutual Information, PMI）

参考资料：blog

-------------本文结束感谢您的阅读-------------