M-各种距离定义

0.目录

欧几里得距离 (Euclidean Distance)
曼哈顿距离 (Manhattan Distance)
切比雪夫距离 (Chebyshev distance)
闵可夫斯基距离 (Minkowski Distance)
马哈拉诺比斯距离 (Mahalanobis Distance)
汉明距离 (Hamming Distance)
巴塔恰里雅距离 (Bhattacharyya distance)
引用

一般而言，定义一个距离函数 $d(x,y)$ , 需要满足下面几个准则：
1). $d(x,x) = 0$ ，即到自己的距离为0
2). $d(x,y) >= 0$ ，距离非负
3). $d(x,y) = d(y,x)$ ，对称性: 如果 A 到 B 距离是 $a$ ，那么 B 到 A 的距离也应该是 $a$
4). $d(x,k)+d(k,y) >= d(x,y)$ ，三角形法则: (两边之和大于第三边)

1.欧几里得距离（Euclidean Distance）

在数学中，欧几里得距离或欧几里得度量是欧几里得空间中两点间“普通”（即直线）距离。使用这个距离，欧氏空间成为度量空间。相关联的范数称为欧几里得范数。

定义

在欧几里得空间中，点 $p=(p_1,p_2,...,p_n)$ ， $q=(q_1,q_2,...,q_n)$ 之间的欧氏距离为：

$d(p,q)=d(q,p)=\sqrt{(p_1-q_1)^2+(p_2-q_2)^2+···+(p_n-q_n)^2}=\sqrt{\sum_{i=1}^n{(p_i-q_i)^2}}$

欧式空间中的两个点可以看做空间中的两个以原点为起始点的向量，则向量 $\vec{p}$ 的自然长度即向量的模长，为该点到原点的距离：

$||\vec{p}||=\sqrt{p_1^2+p_2^2+···+p_n^2}=\sqrt{\vec{p}·\vec{p}}$

它是一个纯数值。在欧几里得度量下，两点之间线段最短。

2.曼哈顿距离（Manhattan Distance）

曼哈顿距离(Manhattan distance or Manhattan length)十九世纪的赫尔曼·闵可夫斯基所创辞汇，为欧几里得几何度量空间的几何学之用语，用以标明两个点上在标准坐标系上的绝对轴距之总和。

定义

在直角坐标系的n维实向量空间中，两个向量 $\vec{p}$ , $\vec{q}$ 的曼哈顿距离 $d_1$ 为两个点连成的线段在各坐标轴上的投影之和，表示为：

$d_1(\vec{p},\vec{q})=||\vec{p}-\vec{q}||_1=\sum_{i=1}^n{|p_i-q_i|}$

例如在平面上，坐标 $(x_1,y_1)$ 的点 $P_1$ 与坐标 $(x_2,y_2)$ 的点 $P_2$ 的曼哈顿距离为： $|x_1-x_2|+|y_1-y_2|$

要注意的是，曼哈顿距离依赖座标系统的旋转，而非系统在座标轴上的平移或映射。

性质

圆

曼哈顿距离下的圆由与欧几里得几何中不同的度量来确定，圆的形状也发生变化。一个圆是由从圆心向各个固定曼哈顿距离标示出来的点围成的区域，因此其形状为正方形，其侧面与坐标轴成45°角。

当使用欧几里得度量时，每边的长度为 $\sqrt{2}r$ ，其中 $r$ 是圆的半径，但在曼哈顿距离下每条边长度为 $2r$ 。因此，圆的周长为 $8r$ 。因此，在此几何中，类似于 $\pi$ 的几何模拟的值是4。而在直角坐标系中单位圆的公式为 $|x|+|y|=1$ ，在极坐标系中公式为 $r=\frac{1}{|sin\theta|+|cos\theta|}$ 。

计程车几何学满足除了SAS全等定理之外的希尔伯特几何公理。

如果有一群圆，且任两圆皆相交，则整群圆必在某点相交；因此曼哈顿距离会形成一个超凸度量空间。对一个半径为 $r$ 的圆来说，这个正方形的圆每边长 $\sqrt{2}r$ 。此'"圆"的半径 $r$ 对切比雪夫距离（ $L_\infty$ 空间）的二维平面来说，也是一个对座标轴来说边长为 $2r$ 的正方形，因此二维切比雪夫距离可视为等同于旋转且放大过的二维曼哈顿距离。然而这种介于 $L_1$ 与 $L_\infty$ 的相等关系并不能延伸到更高的维度。

应用

国际象棋棋子的移动
压缩感测
频率分布的差异

3.切比雪夫距离（Chebyshev distance）

数学上，切比雪夫距离（Chebyshev distance）或是 $L_\infty$ 度量是向量空间中的一种度量，二个点之间的距离定义为其各座标数值差的最大值。以 $(x_1,y_1)$ 和 $(x_2,y_2)$ 二点为例，其切比雪夫距离为 $max(|x_2-x_1|,|y_2-y_1|)$ 。切比雪夫距离得名自俄罗斯数学家切比雪夫。

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

定义

若二个向量或二个点 $\vec{p}$ 、 $\vec{q}$ ，其座标分别为 $p_i$ 、 $q_i$ ，则两者之间的切比雪夫距离定义如下： $D_{Chebyshev}(x,y):=\max_i(|x_i-y_i|)$ .

这也等于以下L_p度量的极值： $\lim_{k\rightarrow\infty}{(\sum_{i=1}^n{|p_i-q_i|}^k)^{1/k}}$ ，

因此切比雪夫距离也称为 $L_\infty$ 度量。以数学的观点来看，切比雪夫距离是由一致范数（或称为上确界范数）所衍生的度量，也是超凸度量的一种。

在平面几何中，若二点p及q的直角坐标系坐标为 $(x_1,y_1)$ 、 $(x_2,y_2)$ ，则切比雪夫距离为 $D_{Chebyshev}=max(|x_2-x_1|,|y_2-y_1|)$ .

依以上的度量，以任一点为准，和此点切比雪夫距离为r的点会形成一个正方形，其边长为 $2r$ ，且各边都和坐标轴平行。

在棋盘上，使用的是离散的切比雪夫距离，以任一位置为准，和此点切比雪夫距离为r的所有位置也会形成一正方形，若以位置的中心量到其他位置的中心，此正方形的“边长”为 $2r$ ，正方形的边会有 $2r+1$ 个方格，例如，和一位置切比雪夫距离为1的所有位置会形成一个3×3的正方形。

性质

一维空间中，所有的 $L_p$ 度量都是一样的－即为二座标差的绝对值。

二维空间下，和一点的曼哈顿距离 $L_1$ 为定值 $r$ 的点也会形成一个正方形，但其边长为 $\sqrt{2}r$ ，而且正方形的边和坐标轴会有 $π/4$ （45°）的夹角，因此平面的切比雪夫距离可以视为平面曼哈顿距离旋转再放大后的结果。

不过上述 $L_1$ 度量及 $L_\infty$ 度量之间的关系在更高维度的空间不成立。和一点有相等切比雪夫距离的点会形成一个立方体，各面都和坐标轴垂直，而和一点有相等曼哈顿距离的点会形成一个正八面体。

对一个网格（例如棋盘），和一点的切比雪夫距离为1的点为此点的Moore型邻居。

当 $p$ 达到无穷大时，切比雪夫距离是Minkowski距离的极限情况。

应用

切比雪夫距离有时用于仓库物流中，因为它可以有效地测量高架起重机移动物体所需的时间（因为起重机可以同时沿x和y轴移动）。

它还广泛用于电子CAM应用程序，尤其是针对这些应用程序的优化算法。与高架起重机类似，许多工具，例如在平面上操作的绘图或钻孔机，光绘仪等，通常由两个电动机在x和y方向上控制。

4.闵可夫斯基距离(Minkowski Distance)

闵可夫斯基距离，是欧氏空间中的一种测度，被看做是欧氏距离和曼哈顿距离的一种推广。严格意义上讲，闵可夫斯基距离不是一种距离，而是一组距离的定义。

定义

两点 $X=(x_1,x_2,...,x_n)$ $and$ $Y=(y_1,y_2,...,y_n)\in\mathbb{R}^n$ 的 $n$ 阶Minkowski 距离定义为：

$D(X,Y)=\Bigg(\sum_{i=1}^n{|x_i-y_i|^p}\Bigg)^{\frac{1}{p}}$

$p$ 为1时为曼哈顿距离
$p$ 为2即为欧氏距离
$p$ 为 $+\infty$ 时为切比雪夫距离

$\lim_{p\rightarrow\infty}{\Bigg(\sum_{i=1}^n{|x_i-y_i|}^p\Bigg)}^{\frac{1}{p}}=\max_{i=1}^{n}{|x_i-y_i|}$

$\lim_{p\rightarrow-\infty}{\Bigg(\sum_{i=1}^n{|x_i-y_i|}^p\Bigg)}^{\frac{1}{p}}=\min_{i=1}^{n}{|x_i-y_i|}$

Minkowski距离也可以看作是 $P$ 和 $Q$ 之间的分量方差的幂均值的倍数。
下图显示了具有各种 $p$ 值的单位圆（所有距中心单位距离的点的集合）

当 $p<1$ 时，闵可夫斯基距离不再符合三角形法则，举个例子：当 $p<1$ , $(0,0)$ 到 $(1,1)$ 的距离等于 $(1 +1)^{1/p}>2$ , 而 $(0,1)$ 到这两个点的距离都是 $1$ 。

闵可夫斯基距离比较直观，但是它与数据的分布无关，具有一定的局限性，如果 x 方向的幅值远远大于 y 方向的值，这个距离公式就会过度放大 x 维度的作用。所以，在计算距离之前，我们可能还需要对数据进行 z-transform 处理，即减去均值，除以标准差：
$(x_1,y_1)\rightarrow(\frac{x_1-\mu_x}{\sigma_x},\frac{y_1-\mu_y}{\sigma_y})$ ， $\mu$ :该维度上的均值， $\sigma$ :该维度上的标准差

可以看到，上述处理开始体现数据的统计特性了。这种方法在假设数据各个维度不相关的情况下利用数据分布的特性计算出不同的距离。如果维度相互之间数据相关（例如：身高较高的信息很有可能会带来体重较重的信息，因为两者是有关联的），这时候就要用到马氏距离（Mahalanobis distance）了。

5.马哈拉诺比斯距离(Mahalanobis Distance)

马哈拉诺比斯距离是由印度统计学家 P. C. Mahalanobis 在1936年提出的，表示数据的协方差距离。它是一种有效的计算两个未知样本集的相似度的方法。与欧氏距离不同的是它考虑到各种特性之间的联系（例如：一条关于身高的信息会带来一条关于体重的信息，因为两者是有关联的）并且是尺度无关的（scale-invariant），即独立于测量尺度。

定义

对于一个均值为 $\vec{\mu}=(\mu_1,\mu_2,...,\mu_N)^T$ ，协方差矩阵为 $\Sigma$ 的多变向量 $\vec{x}=(x_1,x_2,...,x_N)^T$ ，其马氏距离为：

$D_M(\vec{x})=\sqrt{(\vec{x}-\vec{\mu})^T\Sigma^{-1}(\vec{x}-\vec{\mu})}$

马哈拉诺比斯距离也可以定义为两个服从同一分布并且其协方差矩阵为 $\Sigma$ 的随机变量 $\vec{x}$ 与 $\vec{y}$ 的差异程度：

$d(\vec{x},\vec{y})=\sqrt{(\vec{x}-\vec{y})^T\Sigma^{-1}(\vec{x}-\vec{y})}$

如果协方差矩阵为单位矩阵，马哈拉诺比斯距离就简化为欧氏距离；如果协方差矩阵为对角阵，其也可称为标准化欧氏距离。

$d(\vec{x},\vec{y})=\sqrt{\sum_{i=1}^{p}{\frac{(x_i-y_i)^2}{\sigma_i^2}}}$

其中 $\sigma_i$ 是 $x_i$ 的标准差。

Mahalanobis距离在数据跨空间的满秩线性变换下得以保留。这意味着，如果数据具有非平凡的零空间，则可以在将数据（非退化地）向下投影到数据的适当维数的任何空间之后，计算马氏距离。

正态分布

对于任何维数的正态分布，观测的概率密度唯一地由马氏距离 $d$ 确定。具体而言， $d^2$ 是卡方分布的。例如，维数为2时，特定计算的 $d$ 小于某个阈值 $t$ 的概率为 $1-e^{-t^2/2}$ ，要确定达到特定概率 $p$ 的阈值， $t=\sqrt{-2\ln{(1-p)}}$ 。对于除2以外的维数，参询卡方分布。

在正态分布中，马氏距离小于1的区域（即椭圆体内距离1的区域）恰好是概率分布为凹形的区域。

对于正态分布，马氏距离与负对数似然的平方根成正比（在添加常数后，最小值为零）。

应用

马氏距离的定义源于1927年基于测量确定头骨相似性的问题。

马氏距离已广泛用于聚类分析和分类技术。它与用于多变量统计检验的霍特林T平方分布(Hotelling's T-square distribution)和用于监督分类的Fisher线性判别分析(Fisher's Linear Discriminant Analysis)密切相关。

为了使用马氏距离将测试点分类为属于N个类别之一，通常首先基于已知属于每个类别的样本来估计每个类别的协方差矩阵。然后，给定一个测试样本，计算每个类别的马氏距离，并将测试点分类为马氏距离最小的那个类别。

马氏距离和杠杆通常用于检测离群值，尤其是在线性回归模型的开发中。与其他样本点群具有更大的Mahalanobis距离的点被认为具有更高的杠杆作用，因为它对回归方程的斜率或系数影响更大。马氏距离还用于确定多元离群值。回归技术可用于通过两个或多个可变得分的组合来确定样本总体中的特定情况是否是异常值。即使对于正态分布，点也可以是多变量离群值，即使它不是任何变量的单变量离群值（如沿线 $x_1=x_2$ 集中的概率密度），使得马氏距离比单独检查尺寸更为灵敏。

6.汉明距离(Hamming Distance)

定义

在信息论中，两个等长字符串之间的汉明距离（Hamming distance）是两个字符串对应位置的不同字符的个数。换句话说，它测量将一个字符串转换为另一个字符串所需的最小替换数，或可能将一个字符串转换为另一个字符串的最小错误数。在一般的上下文中，汉明距离是用于测量两个序列之间的编辑距离的几个字符串指标之一。

汉明重量是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数：对于二进制字符串来说，就是1的个数，所以11101的汉明重量是4。

示例

下列字符串的汉明距离为：

"karolin" and "kathrin" is 3.
"karolin" and "kerstin" is 3.
1011101 and 1001001 is 2.
2173896 and 2233796 is 3.

特性

对于固定的长度n，汉明距离是该长度字符向量空间上的度量，很显然它满足非负、唯一及对称性，并且可以很容易地通过完全归纳法证明它满足三角不等式。

两个字a与b之间的汉明距离也可以看作是特定运算−的a−b的汉明重量。

对于二进制字符串a与b来说，它等于a 异或b以后所得二进制字符串中“1”的个数。另外二进制字符串的汉明距离也等于n维超正方体两个顶点之间的曼哈顿距离，其中n是两个字串的长度。

7.巴塔恰里雅距离(Bhattacharyya distance)

在统计中，巴氏距离衡量两个概率分布的相似性。它与Bhattacharyya系数密切相关，后者是两个统计样本或总体之间重叠量的度量。

该系数可用于确定所考虑的两个样本的相对接近度。它用于度量分类的类的可分离性，并且被认为比马哈拉诺比斯距离更可靠，因为当两个类的标准偏差相同时，马哈拉诺比斯距离是巴氏距离的特例。因此，当两个类别的均值相似但标准差不同时，马氏距离将趋于零，而巴氏距离则根据标准差之间的差异而增长。

定义

对于同一域 $X$ 上的概率分布 $p$ 和 $q$ ，巴氏距离定义为:

$D_B(p,q)=-\ln{(BC(p,q))}$

当 $p$ 、 $q$ 为离散概率分布时，Bhattacharyya系数为 $BC(p,q)=\sum_{x\in X}{\sqrt{p(x)q(x)}}$ 。

当 $p$ 、 $q$ 为连续概率分布时，Bhattacharyya系数为 $BC(p,q)=\int{\sqrt{p(x)q(x)}dx}$

在两种情况中， $0\le{BC}\le1$ 并且 $0\le{D_B}\le{\infty}$ 。 $D_B$ 不服从三角形不等式，但是由 $\sqrt{1-BC(p,q)}$ 给出的Hellinger距离服从三角形不等式。

用最简单的公式表示，可以通过提取两个单独的分布或类的均值和方差来计算正态分布下两个类之间的Bhattacharyya距离：

$D_B(p,q)=\frac{1}{4} \ln{\Bigg(\frac{1}{4}\Bigg(\frac{\sigma_p^2}{\sigma_q^2}+\frac{\sigma_q^2}{\sigma_p^2}+2\Bigg)\Bigg)}+\frac{1}{4}\Bigg(\frac{(\mu_p-\mu_q)^2}{\sigma_p^2+\sigma_q^2}\Bigg)$

其中： $D_B(p,q)$ 是 $p$ 和 $q$ 分布之间的Bhattacharyya距离， $\sigma_p^2$ 是分布 $p$ 的方差， $\mu_p$ 是分布 $p$ 的均值， $p,q$ 是两个不同的分布。

Fisher线性判别分析中使用的Mahalanobis距离是Bhattacharyya距离的特例。

8.引用

Metric geometry
Distance

最后编辑于：2020.03.19 11:15:11

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 211,884评论 6赞 492
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,347评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 157,435评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,509评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,611评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,837评论 1赞 290
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,987评论 3赞 408
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,730评论 0赞 267
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,194评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,525评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,664评论 1赞 340
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,334评论 4赞 330
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,944评论 3赞 313
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,764评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,997评论 1赞 266
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,389评论 2赞 360
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,554评论 2赞 349