Distance Classification

Distance

欧氏距离(Euclidean Distance)

闵可夫斯基距离（Minkowski distance）

曼哈顿距离(Manhattan distance)

切比雪夫距离 ( Chebyshev distance )

标准化欧氏距离(Standardized Euclidean distance )

马氏距离(Mahalanobis Distance)

汉明距离(Hamming distance)

余弦相似度（Cosine Similarity）

杰卡德相似系数(Jaccardsimilarity coefficient)

Reference

Distance

由于最近在做故障诊断相关研究，不断学习各种算法，发现在很多算法里面都用到了Distance来定义各种变量之间的关系，确定之间的相关类指标。且在运用算法做分类时需要估不同样本之间的相似性度量(Similarity Measurement，SM)，这时通常采用的方法就是计算样本间的“距离”(Distance)。在下面一 一道来！

这可太有意思了，不经让我去寻找，究竟有多少种Distance可以运用在不同的算法里面呢？在不同算法里的计算方式是否有所不同？在计算效率上哪种Distance更优？哪种Distance在算法中运行速度更快，效果更好呢？什么Distance能够使得你的分类或聚类效果更加优秀呢？…

针对太多了疑问和不解，那么现在开始做做Distance的相关解读吧！

首先，了解一下距离计算（聚类分析）

对于函数Dist( ; )，倘若它是一个“距离度量”（distance measure），则需要满足一些基本性质：

欧氏距离(Euclidean Distance)

相信欧氏距离(EuclideanDistance)是很多人都知道且用到的一个距离计算方法，且简单高效。

在我们做聚类分析中常用的基于欧几里得距离的相似矩阵作为一种可行的方法。

欧几里得

简而言之，就是欧式空间中，两点之间的距离公式。

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

欧几里得度量（euclidean metric）（也称欧氏距离）是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。在二维和三维空间中的欧氏距离就是两点之间的实际距离。

—来源于网络

• 原理公式

下面简述下计算公式：

• 二维空间的公式

其中，

简单的说，就是求其二维平面上两点之间的模长。—>本人心得

• 三维空间的公式

和二维空间一样，只不过多加了一个坐标系的值

再简单的说，同理就是求其三维平面上两点之间的模长。—>本人心得

• n维空间的公式

将每个维度的求其模长。 及其不标准描述，别说我说的

拓展内容：

所谓欧氏距离变换，是指对于一张二值图像（在此我们假定白色为前景色，黑色为背景色），将前景中的像素的值转化为该点到达最近的背景点的距离。

欧氏距离变换在数字图像处理中的应用范围很广泛，尤其对于图像的骨架提取，是一个很好的参照。

三角关系

最简单的公式：

应用层面

欧氏距离看作信号的相似程度。 距离越近就越相似，就越容易相互干扰，误码率就越高。

最近看了一篇 Paper，大佬级别的，引用率很高。讲的是关于欧几里得距离（欧氏距离）作为主成分分析（PCA）的相似性度量。理论性很强，本人菜鸡一个，目前读的有些老火，上传了网盘，论文可在这里下载【提取码：fvj2】。

《Euclidean Distance as a Similarity Metric for Principal Component Analysis》–KIMBERLY L. ELMORE

cite：[1] Elmore K L , Richman M B . Euclidean Distance as a Similarity Metric for Principal Component Analysis[J]. Monthly Weather Review, 2010, 129(3):540-549.

闵可夫斯基距离（Minkowski distance）

闵氏距离不是一种距离，而是一组距离的定义。是欧氏空间中的一种测度，被看做是欧氏距离的一种推广，欧氏距离是闵可夫斯基距离的一种特殊情况。

闵氏空间指狭义相对论中由一个时间维和三个空间维组成的时空，为俄裔德国数学家闵可夫斯基(H.Minkowski,1864-1909)最先表述。他的平坦空间（即假设没有重力，曲率为零的空间）的概念以及表示为特殊距离量的几何学是与狭义相对论的要求相一致的。闵可夫斯基空间不同于牛顿力学的平坦空间。

闵可夫斯基

一个小故事：

阿尔伯特·爱因斯坦在瑞士苏黎世联邦科技大学(Eidgen?ssische Technische Hochschule, ETH; Swiss Federal Institute of Technology)时期的数学老师赫尔曼·闵可夫斯基在爱因斯坦提出狭义相对论之后，于1907年将爱因斯坦与亨德里克·洛仑兹的理论结果重新表述成(3+1)维的时空，其中光速在各个惯性参考系皆为定值，这样的时空即以其为名，称为闵可夫斯基时空，或称闵可夫斯基空间。

原理公式

官方原理：

闵氏距离有时也指时空间隔，关于时空间隔的内容可跳转看词条解释。

设n维空间中有两点坐标x, y，v为常数，闵式距离定义为

（1）闵氏距离与特征参数的量纲有关，有不同量纲的特征参数的闵氏距离常常是无意义的。

（2）闵氏距离没有考虑特征参数间的相关性，而马哈拉诺比斯距离解决了这个问题。

特殊情况

当v = 2

上面说到欧氏距离是闵可夫斯基距离的一种特殊情况，那么当 v = 2的时候，闵可夫斯基距离即为欧氏距离，欧氏距离中各特征参数是等权的：

当v = 1

可得到绝对值距离，也叫曼哈顿距离（Manhattan distance）、出租汽车距离或街区距离（city block distance）。在二维空间中可以看出，这种距离是计算两点之间的直角边距离，相当于城市中出租汽车沿城市街道拐直角前进而不能走两点连接间的最短距离。绝对值距离的特点是各特征参数以等权参与进来，所以也称等混合距离。

当v → ∞

得到切比雪夫距离，下面再做介绍。

应用层面

我们常常将属性划分为“连续属性”（continuous attribute）和“离散属性”（categorical attribute），前者在定义域上有无穷多个可能的取值，后者在定义域上式有限个取值。然而，在讨论距离计算的时候，属性上是否定义“序”关系更为重要。例如，定义域在{1，2，3}的离散属性和连续属性的性质更为接近一些，能直接在属性值上计算距离：“1”和“2”比较接近、与“3”比较远，这样的属性称为“有序属性”（ordinal attribute）；而定义为{火车、飞机、船}这样的离散属性则不能直接在属性值上计算距离，称为“无序属性”（non-ordinal attribute）。在这里，闵可夫斯基距离可用于有序距离，

连续属性亦成为“数值属性”（numerical attribute）

离散属性亦成为“列名属性”（nominal attribute）

简单总结：闵可夫斯基距离在面对离散数据集的时候则不适用，而对于有序数列数据集可用。

—来自菜鸡解释，不对可忽略。

曼哈顿距离(Manhattan distance)

由上可知，在闵可夫斯基距离中，当v = 1 时，可得到绝对值距离，也叫曼哈顿距离（Manhattan distance）、出租汽车距离或街区距离（city block distance）。

同样也是由上面那位图片上的大佬创建的，这里就不放Photo了

出租车几何或曼哈顿距离（Manhattan Distance）是由十九世纪的赫尔曼·闵可夫斯基所创词汇 ，是种使用在几何度量空间的几何学用语，用以标明两个点在标准坐标系上的绝对轴距总和。

原理公式

官方解释很好理解（附上了）

曼哈顿距离

上图中红线代表曼哈顿距离，绿色代表欧氏距离，也就是直线距离，而蓝色和黄色代表等价的曼哈顿距离。曼哈顿距离——两点在南北方向上的距离加上在东西方向上的距离，即

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

菜鸡理解：曼哈顿距离在处理大规模运算的时候，将一些需要用到浮点运算的地方（欧氏距离运算）换成加减运算，在处理器较强的现在，（不懂算法提速的我），或许还会提高运算速度(虽然没有试过，大胆假设一波，再去补补Paper)。在二维三维平面上本来走直线的，现在通过走曲折的“直线”减小计算难度，但增加了计算过程，最终的结果是使得运算速度提速了！！！很神奇

煮个栗子吧

现在请出灵魂画师

此时的曼哈顿距离

应用层面

关于曼哈顿距离的应用，搜罗了大部分Paper，发现都是在计算机领域的应用较多，比如提高改进GPU运算性能、算法层面的性能提升、CV等等…太多了

这里有几篇引用率且水平较高的Paper可读一读。

本菜在不断摸索当中

[1] Chang D J , Desoky A H , Ming O , et al. Compute Pairwise Manhattan Distance and Pearson Correlation Coefficient of Data Points with GPU[C]// 10th ACIS International Conference on Software Engineering, Artificial Intelligences, Networking and Parallel/Distributed Computing, SNPD 2009, in conjunction with 3rd International Workshop on e-Activity, IWEA 2009, 1st International Workshop on Enterprise Architecture Challenges and Responses, WEACR 2009, Catholic University of Daegu, Daegu, Korea, 27-29 May 2009. IEEE, 2009.

[2] Mattausch H J , Omori N , Fukae S , et al. Fully-parallel pattern-matching engine with dynamic adaptability to Hamming or Manhattan distance[C]// VLSI Circuits Digest of Technical Papers, 2002. Symposium on. IEEE, 2002.

[3] Oike Y , Ikeda M , Asada K . A high-speed and low-voltage associative co-processor with exact Hamming/Manhattan-distance estimation using word-parallel and hierarchical search architecture[J]. IEEE Journal of Solid-State Circuits, 2004, 39(8):1383-1387.

深入了解后再细挖（待更新）。

切比雪夫距离 ( Chebyshev distance )

在数学中，切比雪夫距离（Chebyshev distance）或是L ∞ L_∞L

∞

度量，是向量空间中的一种度量，二个点之间的距离定义是其各坐标数值差绝对值的最大值。以数学的观点来看，切比雪夫距离是由一致范数（uniform norm）（或称为上确界范数）所衍生的度量，也是超凸度量（injective metric space）的一种。(—来自网络)

切比雪夫

最形象的一个比如应该当属“国际象棋”，相信有大部分人像本弱鸡一样不会下国际象棋，下面直接讲原理。

原理公式

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

一维空间中，所有的Lp度量都是一样的------------（即为二坐标差的绝对值）。

假设平面中存在两个点分别为

那么它们之间的切比雪夫距离为

也即是，求其两点之间横纵坐标x ， y对应差的绝对值，在选出最大的一个作为它们之间的切比雪夫距离。

炒个栗子吧

此时又得拿出灵魂画师的水准

此时，

在网路上学习的过程中找到一个狠好的解释：曼哈顿距离和切比雪夫距离相互转换。

（图片来自网络）

因此平面的切比雪夫距离可以视为平面曼哈顿距离旋转再放大后的结果。

• 应用层面

关于切比雪夫距离，在聚类上有所用到，在图象识别领域，改进的切比雪夫相似性度量来替代聚类分析中现有的度量（如欧几里得和标准切比雪夫），通过改进的算法应用到医学的图像识别上，效果很好。所提出的措施产生最小的目标函数值，并在迭代次数最少时收敛。这里推荐一篇Paper.

Mousa A , Yusof Y . An improved Chebyshev distance metric for clustering medical images[C]// American Institute of Physics Conference Series. AIP Publishing LLC, 2015:040020.

标准化欧氏距离(Standardized Euclidean distance )

标准欧氏距离的定义:

标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案。

本菜理解：针对多维变量，将输入样本X XX进行标准化的欧式距离计算操作。

原理公式

首先，将各个分量都“标准化”到均值、方差相等。

应用层面

在机器学习中，聚类用的标准化欧氏距离比较多，在面对求解长方形区域聚类的时候，普通的距离无法满足相似性度量，这是就得采用标准化欧氏距离来度量。

这里推荐一本书。

Chikodili N B , MD Abdulmalik, Abisoye O A , et al. Outlier Detection in Multivariate Time Series Data Using a Fusion of K-Medoid, Standardized Euclidean Distance and Z-Score[M]. 2021.

马氏距离(Mahalanobis Distance)

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

生来清贫，没有头像，只留下一本书

马氏距离(Mahalanobis

Distance)是度量学习中一种常用的距离指标，同欧氏距离、曼哈顿距离、汉明距离等一样被用作评定数据之间的相似度指标。但却可以应对高维线性分布的数据中各维度间非独立同分布的问题。(来自知乎大佬)

原理公式

什么是马氏距离？

简单来说就是，作为一种距离的度量，可以看作是欧氏距离的一种修正，修正了欧式距离中各个维度尺度不一致且相关的问题。

单个数据点的马氏距离

数据点x , y之间的马氏距离

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

应用层面

马氏距离实际意义:

那么马氏距离就能能干什么？它比欧氏距离好在哪里？再炒几个栗子

欧式距离近就一定相似？

先举个比较常用的例子，身高和体重，这两个变量拥有不同的单位标准，也就是有不同的scale。比如身高用毫米计算，而体重用千克计算，显然差10mm的身高与差10kg的体重是完全不同的。但在普通的欧氏距离中，这将会算作相同的差距。

归一化后欧氏距离近就一定相似？

当然我们可以先做归一化来消除这种维度间scale不同的问题，但是样本分布也会影响分类

举个一维的栗子，现在有两个类别，统一单位，第一个类别均值为0，方差为0.1，第二个类别均值为5，方差为5。那么一个值为2的点属于第一类的概率大还是第二类的概率大？距离上说应该是第一类，但是直觉上显然是第二类，因为第一类不太可能到达2这个位置。

所以，在一个方差较小的维度下很小的差别就有可能成为离群点。就像下图一样，A与B相对于原点的距离是相同的。但是由于样本总体沿着横轴分布，所以B点更有可能是这个样本中的点，而A则更有可能是离群点。

算上维度的方差就够了？

还有一个问题——如果维度间不独立同分布，样本点一定与欧氏距离近的样本点同类的概率更大吗？

可以看到样本基本服从f(x) = x的线性分布，A与B相对于原点的距离依旧相等，显然A更像是一个离群点

即使数据已经经过了标准化，也不会改变AB与原点间距离大小的相互关系。所以要本质上解决这个问题，就要针对主成分分析（PCA）中的主成分来进行标准化。

马氏距离的几何意义

上面搞懂了，马氏距离就好理解了，只需要将变量按照主成分进行旋转，让维度间相互独立，然后进行标准化，让维度同分布就OK了。

由主成分分析可知，由于主成分就是特征向量方向，每个方向的方差就是对应的特征值，所以只需要按照特征向量的方向旋转，然后缩放特征值倍就可以了，可以得到以下的结果：

离群点就被成功分离，这时候的欧式距离就是马氏距离。（很妙啊！）

马氏距离的问题

1.协方差矩阵必须满秩

里面有求逆矩阵的过程，不满秩不行，要求数据要有原维度个特征值，如果没有可以考虑先进行PCA，这种情况下PCA不会损失信息

2.不能处理非线性流形(manifold)上的问题

只对线性空间有效，如果要处理流形，只能在局部定义，可以用来建立KNN图

不能处理非线性流形(manifold)上的问题

只对线性空间有效，如果要处理流形，只能在局部定义，可以用来建立KNN图

汉明距离(Hamming distance)

理查德·卫斯里·汉明

原理

在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如：

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

2143896 与 2233796 之间的汉明距离是 3

“toned” 与 “roses” 之间的汉明距离是 3

可视化的煮个栗子吧

汉明距离多用于编码等信息论方面的计算，对于为什么上面的汉明距离结果为此，简单来看，拿出我灵魂画手工笔

这样来看是不是更好理解一点呢。只需要从字符串中寻找出不同的项，不同项的数量就为之间的汉明距离。

这里写了一个小的求汉明距离的Python封装代码（直接调用即可）：

def HammingDistance(x, y):
    """返回等长序列之间的汉明距离"""
    if len(x) != len(y):
        raise ValueError("对于长度不等的序列未定义")
    return sum(t1 != t2 for t1, t2 in zip(x, y))

最小汉明距离

例如：(00)与(01)的距离是1，(110)和(101)的距离是2。在一个码组集合中，任意两个编码之间汉明距离的最小值称为这个码组的最小汉明距离。最小汉明距离越大，码组越具有抗干扰能力。

应用层面

汉明距离更多的用于信号处理，表明一个信号变成另一个信号需要的最小操作（替换位），实际中就是比较两个比特串有多少个位不一样，简洁的操作时就是两个比特串进行异或之后包含1的个数。汉明距在图像处理领域也有这广泛的应用，是比较二进制图像非常有效的手段。计算一个数字的比特位包含1的个数有个小技巧：value &= value - 1这个运算的结果就是把value最后一个1去掉，循环进行运算直到value等于0（所有的1都被去掉）就可以知道vaule拥有多少个1了。其在包括信息论、编码理论、密码学等领域都有应用。但是，如果要比较两个不同长度的字符串，不仅要进行替换，而且要进行插入与删除的运算，在这种场合下，通常使用更加复杂的编辑距离等算法。（源自百科）

在信号处理方面，本菜就不班门弄斧了

据说，在机器学习领域中，汉明距离也常常被用于作为一种距离的度量方式。在LSH算法汉明距离也有重要的应用。具体还有待研究（待进一步深挖后 更新）

余弦相似度（Cosine Similarity）

为什么在这里会提到余弦？等等，这不是在学几何三角！

虽然几何中夹角余弦可用来衡量两个向量方向的差异，但是我们在机器学习中借用这一概念来可以衡量样本向量之间的差异，从此进行相似性度量。

原理公式

来自网络

或许可以理解为：求空间中两点的余弦值，值越大表示两个向量的夹角越小，值越小表示两向量的夹角越大。从上图中可以看出，夹角越小代表两个向量点越相似，夹角越大代表两个向量的相似度越小。

当两个向量的方向重合时夹角余弦取最大值1，当两个向量的方向完全相反夹角余弦取最小值-1。

欧氏距离和余弦相似度的区别

从上图可以看出距离度量衡量的是空间各点间的绝对距离，跟各个点所在的位置坐标（即个体特征维度的数值）直接相关；而余弦相似度衡量的是空间向量的夹角，更加的是体现在方向上的差异，而不是位置。如果保持A点的位置不变，B点朝原方向远离坐标轴原点，那么这个时候余弦相似度cosθ是保持不变的，因为夹角不变，而A、B两点的距离显然在发生改变，这就是欧氏距离和余弦相似度的不同之处。

应用层面

余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。相比距离度量，余弦相似度更加注重两个向量在方向上的差异，而非距离或长度上。(见此大佬转载更好的解释)

关于对余弦相似度的应用，有以下见解：

正如上所述，相比欧氏距离，余弦相似度计算更加注重的是在方向范围上的应用，对绝对数值是相当的不够敏感，在机器学习中，做聚类或分类的时候，针对多维不同特征，在数值上的联系是相当重要的，故本菜自认为可应用性不大。在对多层维度进行分析体现不同特征之间的差异时，欧式距离或标准化欧氏距离会更占优势。

余弦在方向上区分不同特征的差异占优势，可对一些用于使用用户对内容评分来区分用户兴趣的相似度和差异，同时修正了用户间可能存在的度量标准不统一的问题。（这条我抄的别说了）

吴军. 数学之美 系列 12 -余弦定理和新闻的分类.(一个比较好的栗子)

http://www.google.com.hk/ggblog/googlechinablog/2006/07/12_4010.html

杰卡德相似系数(Jaccardsimilarity coefficient)

Jaccard index , 又称为Jaccard相似系数（Jaccard similarity coefficient）用于比较有限样本集之间的相似性与差异性。Jaccard系数值越大，样本相似度越高。

原理公式

官方定义：

给定两个集合A,B，Jaccard 系数定义为A与B交集的大小与A与B并集的大小的比值，定义如下：

当集合A，B都为空时，J(A,B)定义为1。

与Jaccard 系数相关的指标叫做Jaccard 距离，用于描述集合之间的不相似度。Jaccard 距离越大，样本相似度越低。公式定义如下：

其中对参差（symmetric difference）:

• 应用层面

非对称二元属性的相似性

在数据挖掘领域，常常需要比较两个具有布尔值属性的对象之间的距离，Jaccard距离就是常用的一种方法。

给定两个比较对象A，B。

A，B 均有n个二元属性，即每个属性取值为{0，1}。

定义如下4个统计量：

其中，

Jaccard 系数：

Jaccard距离：

主要应用场景：

1.比较文本相似度，用于文本查重与去重；

2.计算对象间距离，用于数据聚类等。

Python有相应的库包scipy.spatial.distance ，包含有杰卡德距离计算，可直接调用

# scipy距离公式
from numpy import *
import scipy.spatial.distance as dist  

matV = mat([[1,1,0,1,0,1,0,0,1], [0,1,1,0,0,0,1,1,1]])
print ("dist.jaccard:", dist.pdist(matV,'jaccard'))

项目相似性度量是协同过滤系统的核心。 相关研究中，基于物品协同过滤系统的相似性度量方法普遍使用余弦相似性。 然而，在许多实际应用中,评价数据稀疏度过高，物品之间通过余弦相似度计算会产生误导性结果。 将杰卡德相似性度量应用到基于物品的协同过滤系统中，并建立起相应的评价分析方法。 与传统相似性度量方法相比，杰卡德方法完善了余弦相似性只考虑用户评分而忽略了其他信息量的弊端，特别适合于应用到稀疏度过高的数据。（引用自百科）