距离度量方法
发布网友
发布时间：2022-04-23 21:45
共2个回答
懂视网
时间：2022-04-18 10:15
转自：http://www.cnblogs.com/denny402/p/7027954.html
https://www.cnblogs.com/denny402/p/7028832.html
1. 欧氏距离(Euclidean Distance)
欧氏距离是最易于理解的一种距离计算方法，源自欧氏空间中两点间的距离公式。
(1)二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离：
(2)三维空间两点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离：
(3)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的欧氏距离：
(4)也可以用表示成向量运算的形式：
python中的实现：
方法一：
import numpy as np x=np.random.random(10) y=np.random.random(10)#方法一：根据公式求解d1=np.sqrt(np.sum(np.square(x-y)))#方法二：根据scipy库求解from scipy.spatial.distance import pdistX=np.vstack([x,y]) d2=pdist(X)
2. 曼哈顿距离(Manhattan Distance)
从名字就可以猜出这种距离的计算方法了。想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源， 曼哈顿距离也称为城市街区距离(City Block distance)。
(1)二维平面两点a(x1,y1)与b(x2,y2)间的曼哈顿距离
(2)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的曼哈顿距离
python中的实现 ：
import numpy as np x=np.random.random(10) y=np.random.random(10)#方法一：根据公式求解d1=np.sum(np.abs(x-y))#方法二：根据scipy库求解from scipy.spatial.distance import pdistX=np.vstack([x,y]) d2=pdist(X,'cityblock')
3. 切比雪夫距离 ( Chebyshev Distance )
国际象棋玩过么？国王走一步能够移动到相邻的8个方格中的任意一个。那么国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步？自己走走试试。你会发现最少步数总是max( | x2-x1 | , | y2-y1 | ) 步 。有一种类似的一种距离度量方法叫切比雪夫距离。
(1)二维平面两点a(x1,y1)与b(x2,y2)间的切比雪夫距离
(2)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的切比雪夫距离
这个公式的另一种等价形式是
看不出两个公式是等价的？提示一下：试试用放缩法和夹逼法则来证明。
在python中的实现：
import numpy as np x=np.random.random(10) y=np.random.random(10)#方法一：根据公式求解d1=np.max(np.abs(x-y))#方法二：根据scipy库求解from scipy.spatial.distance import pdistX=np.vstack([x,y]) d2=pdist(X,'chebyshev')
4. 闵可夫斯基距离(Minkowski Distance)
闵氏距离不是一种距离，而是一组距离的定义。
(1) 闵氏距离的定义
两个n维变量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的闵可夫斯基距离定义为：
也可写成
其中p是一个变参数。
当p=1时，就是曼哈顿距离
当p=2时，就是欧氏距离
当p→∞时，就是切比雪夫距离
根据变参数的不同，闵氏距离可以表示一类的距离。
(2)闵氏距离的缺点
闵氏距离，包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点。
举个例子：二维样本(身高,体重)，其中身高范围是150~190，体重范围是50~60，有三个样本：a(180,50)，b(190,50)，c(180,60)。那么a与b之间的闵氏距离（无论是曼哈顿距离、欧氏距离或切比雪夫距离）等于a与c之间的闵氏距离，但是身高的10cm真的等价于体重的10kg么？因此用闵氏距离来衡量这些样本间的相似度很有问题。
简单说来，闵氏距离的缺点主要有两个：(1)将各个分量的量纲(scale)，也就是“单位”当作相同的看待了。(2)没有考虑各个分量的分布（期望，方差等)可能是不同的。
python中的实现：
import numpy as np x=np.random.random(10) y=np.random.random(10)#方法一：根据公式求解,p=2d1=np.sqrt(np.sum(np.square(x-y)))#方法二：根据scipy库求解from scipy.spatial.distance import pdistX=np.vstack([x,y]) d2=pdist(X,'minkowski',p=2)
5. 标准化欧氏距离 (Standardized Euclidean distance )
(1)标准欧氏距离的定义
标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案。标准欧氏距离的思路：既然数据各维分量的分布不一样，好吧！那我先将各个分量都“标准化”到均值、方差相等吧。均值和方差标准化到多少呢？这里先复习点统计学知识吧，假设样本集X的均值(mean)为m，标准差(standard deviation)为s，那么X的“标准化变量”表示为：
标准化后的值 = ( 标准化前的值 － 分量的均值 ) /分量的标准差
经过简单的推导就可以得到两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的标准化欧氏距离的公式：
如果将方差的倒数看成是一个权重，这个公式可以看成是一种加权欧氏距离(Weighted Euclidean distance)。
python中的实现：
import numpy as np x=np.random.random(10) y=np.random.random(10) X=np.vstack([x,y])#方法一：根据公式求解sk=np.var(X,axis=0,ddof=1) d1=np.sqrt(((x - y) ** 2 /sk).sum())#方法二：根据scipy库求解from scipy.spatial.distance import pdistd2=pdist(X,'seuclidean')
6. 马氏距离(Mahalanobis Distance)
（1）马氏距离定义
有M个样本向量X1~Xm，协方差矩阵记为S，均值记为向量μ，则其中样本向量X到u的马氏距离表示为：
而其中向量Xi与Xj之间的马氏距离定义为：
若协方差矩阵是单位矩阵（各个样本向量之间独立同分布）,则公式就成了：
也就是欧氏距离了。
若协方差矩阵是对角矩阵，公式变成了标准化欧氏距离。
python 中的实现：
import numpy as np x=np.random.random(10) y=np.random.random(10)#马氏距离要求样本数要大于维数，否则无法求协方差矩阵#此处进行转置，表示10个样本，每个样本2维X=np.vstack([x,y]) XT=X.T#方法一：根据公式求解S=np.cov(X) #两个维度之间协方差矩阵SI = np.linalg.inv(S) #协方差矩阵的逆矩阵#马氏距离计算两个样本之间的距离，此处共有10个样本，两两组合，共有45个距离。n=XT.shape[0] d1=[]for i in range(0,n): for j in range(i+1,n): delta=XT[i]-XT[j] d=np.sqrt(np.dot(np.dot(delta,SI),delta.T)) d1.append(d) #方法二：根据scipy库求解from scipy.spatial.distance import pdist d2=pdist(XT,'mahalanobis')
马氏优缺点：
1）马氏距离的计算是建立在总体样本的基础上的，这一点可以从上述协方差矩阵的解释中可以得出，也就是说，如果拿同样的两个样本，放入两个不同的总体中，最后计算得出的两个样本间的马氏距离通常是不相同的，除非这两个总体的协方差矩阵碰巧相同；
2）在计算马氏距离过程中，要求总体样本数大于样本的维数，否则得到的总体样本协方差矩阵逆矩阵不存在，这种情况下，用欧式距离计算即可。
3）还有一种情况，满足了条件总体样本数大于样本的维数，但是协方差矩阵的逆矩阵仍然不存在，比如三个样本点（3，4），（5，6）和（7，8），这种情况是因为这三个样本在其所处的二维空间平面内共线。这种情况下，也采用欧式距离计算。
4）在实际应用中“总体样本数大于样本的维数”这个条件是很容易满足的，而所有样本点出现3）中所描述的情况是很少出现的，所以在绝大多数情况下，马氏距离是可以顺利计算的，但是马氏距离的计算是不稳定的，不稳定的来源是协方差矩阵，这也是马氏距离与欧式距离的最大差异之处。
优点：它不受量纲的影响，两点之间的马氏距离与原始数据的测量单位无关；由标准化数据和中心化数据(即原始数据与均值之差）计算出的二点之间的马氏距离相同。马氏距离还可以排除变量之间的相关性的干扰。缺点：它的缺点是夸大了变化微小的变量的作用。
7. 夹角余弦(Cosine)
也可以叫余弦相似度。 几何中夹角余弦可用来衡量两个向量方向的差异，机器学习中借用这一概念来衡量样本向量之间的差异。
(1)在二维空间中向量A(x1,y1)与向量B(x2,y2)的夹角余弦公式：
(2) 两个n维样本点a(x11,x12,…,x1n)和b(x21,x22,…,x2n)的夹角余弦
类似的，对于两个n维样本点a(x11,x12,…,x1n)和b(x21,x22,…,x2n)，可以使用类似于夹角余弦的概念来衡量它们间的相似程度。
即：
余弦取值范围为[-1,1]。求得两个向量的夹角，并得出夹角对应的余弦值，此余弦值就可以用来表征这两个向量的相似性。夹角越小，趋近于0度，余弦值越接近于1，它们的方向更加吻合，则越相似。当两个向量的方向完全相反夹角余弦取最小值-1。当余弦值为0时，两向量正交，夹角为90度。因此可以看出，余弦相似度与向量的幅值无关，只与向量的方向相关。
import numpy as np x=np.random.random(10) y=np.random.random(10)#方法一：根据公式求解d1=np.dot(x,y)/(np.linalg.norm(x)*np.linalg.norm(y))#方法二：根据scipy库求解from scipy.spatial.distance import pdist X=np.vstack([x,y]) d2=1-pdist(X,'cosine')
两个向量完全相等时，余弦值为1，如下的代码计算出来的d=1。
d=1-pdist([x,x],'cosine')
8. 皮尔逊相关系数（Pearson correlation）
(1) 皮尔逊相关系数的定义
前面提到的余弦相似度只与向量方向有关，但它会受到向量的平移影响，在夹角余弦公式中如果将 x 平移到 x+1, 余弦值就会改变。怎样才能实现平移不变性？这就要用到皮尔逊相关系数（Pearson correlation），有时候也直接叫相关系数。
如果将夹角余弦公式写成：
表示向量x和向量y之间的夹角余弦，则皮尔逊相关系数则可表示为：
皮尔逊相关系数具有平移不变性和尺度不变性，计算出了两个向量（维度）的相关性。
在python中的实现：
import numpy as np x=np.random.random(10) y=np.random.random(10)#方法一：根据公式求解x_=x-np.mean(x) y_=y-np.mean(y) d1=np.dot(x_,y_)/(np.linalg.norm(x_)*np.linalg.norm(y_))#方法二：根据numpy库求解X=np.vstack([x,y]) d2=np.corrcoef(X)[0][1]
相关系数是衡量随机变量X与Y相关程度的一种方法，相关系数的取值范围是[-1,1]。相关系数的绝对值越大，则表明X与Y相关度越高。当X与Y线性相关时，相关系数取值为1（正线性相关）或-1（负线性相关）。
9. 汉明距离(Hamming distance)
(1)汉明距离的定义
两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。例如字符串“1111”与“1001”之间的汉明距离为2。
应用：信息编码（为了增强容错性，应使得编码间的最小汉明距离尽可能大）。
在python中的实现：
import numpy as npfrom scipy.spatial.distance import pdist x=np.random.random(10)>0.5y=np.random.random(10)>0.5x=np.asarray(x,np.int32) y=np.asarray(y,np.int32)#方法一：根据公式求解d1=np.mean(x!=y)#方法二：根据scipy库求解X=np.vstack([x,y]) d2=pdist(X,'hamming')
10. 杰卡德相似系数(Jaccard similarity coefficient)
(1) 杰卡德相似系数
两个集合A和B的交集元素在A，B的并集中所占的比例，称为两个集合的杰卡德相似系数，用符号J(A,B)表示。
杰卡德相似系数是衡量两个集合的相似度一种指标。
(2) 杰卡德距离
与杰卡德相似系数相反的概念是杰卡德距离(Jaccard distance)。杰卡德距离可用如下公式表示：
杰卡德距离用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。
(3) 杰卡德相似系数与杰卡德距离的应用
可将杰卡德相似系数用在衡量样本的相似度上。
样本A与样本B是两个n维向量，而且所有维度的取值都是0或1。例如：A(0111)和B(1011)。我们将样本看成是一个集合，1表示集合包含该元素，0表示集合不包含该元素。
在python中的实现：
import numpy as npfrom scipy.spatial.distance import pdist x=np.random.random(10)>0.5y=np.random.random(10)>0.5x=np.asarray(x,np.int32) y=np.asarray(y,np.int32)#方法一：根据公式求解up=np.double(np.bitwise_and((x != y),np.bitwise_or(x != 0, y != 0)).sum()) down=np.double(np.bitwise_or(x != 0, y != 0).sum()) d1=(up/down) #方法二：根据scipy库求解X=np.vstack([x,y]) d2=pdist(X,'jaccard')
11. 布雷柯蒂斯距离(Bray Curtis Distance)
Bray Curtis距离主要用于生态学和环境科学，计算坐标之间的距离。该距离取值在[0,1]之间。它也可以用来计算样本之间的差异。
样本数据：
计算：
在python中的实现：
import numpy as npfrom scipy.spatial.distance import pdist x=np.array([11,0,7,8,0]) y=np.array([24,37,5,18,1])#方法一：根据公式求解up=np.sum(np.abs(y-x)) down=np.sum(x)+np.sum(y) d1=(up/down) #方法二：根据scipy库求解X=np.vstack([x,y]) d2=pdist(X,'braycurtis')
相关推荐：
python实现简单的图片文字识别脚本
python实现kMeans算法的详解
热心网友
时间：2022-04-18 07:23
1.曼哈顿距离(Manhattan Distance)
定义：在欧几里德空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。
想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾 驶距离就是这个“曼哈顿距离”,也称为城市街区距离(City Block distance)。
2.欧式距离(Euclidean Distance)
定义：欧几里得距离或欧几里得度量是欧几里得空间中两点间“普通”（即直线）距离。
欧式距离是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）
图中红线代表曼哈顿距离，绿色代表欧式距离，也就是直线距离，而蓝色和*代表等价的曼哈顿距离。
3.切比雪夫距离(Chebyshev distance)
定义：切比雪夫距离是向量空间中的一种度量，二个点之间的距离定义是其各坐标数值差绝对值的最大值。
4.闵可夫斯基距离(Minkowski Distance)
其中p是一个变参数。
当 p = 1 时，就是曼哈顿距离
当 p = 2 时，就是欧氏距离
当 p → ∞ 时，就是切比雪夫距离
闵可夫斯基距离比较直观，但是它与数据的分布无关，具有一定的局限性，如果 x 方向的幅值远远大于 y 方向的值，这个距离公式就
会过度放大 x 维度的作用。所以，在计算距离之前，我们可能还需要对数据进行 z-transform 处理，即减去均值，除以标准差（即 标准化欧式
距离）。
这种方法在假设数据各个维度不相关的情况下利用数据分布的特性计算出不同的距离。如果维度相互之间数据相关（例如：身高较高的
信息很有可能会带来体重较重的信息，因为两者是有关联的），这时候就要用到马氏距离（Mahalanobis distance）了。
5. 标准化欧式距离(Standardized Euclidean distance)
思路：既然数据各维分量的分布不一样，那先将各个分量都“标准化”到均值、方差相等。假设样本集 X 的均值(mean)为 m ，标准差(standard deviation)为 s ， X 的“标准化变量”表示为：
则标准化后的欧式距离公式为：
如果将方差的倒数看成一个权重，也可称之为加权欧氏距离(Weighted Euclidean distance)
6.马氏距离(Mahalanobis distance)
马氏距离表示数据的协方差距离，是一种有效的计算两个未知样本集的相似度的方法。其计算是建立在总体样本的基础上的。即，它考虑到各种特性之间的联系，是尺度无关的（独立于测量尺度）。
一原始*样本数据 Xnm ( m 维，n 个样本 X=(X1, X2,...,Xn))：
对于一个样本的总体均值为μX=(μX1,μX2,...,μXm)，其协方差为Σ，的多变量矢量X=(X1, X2,...,Xn)T，其到样本中心 u 的马氏距离为：
而马氏距离也可以定义两个服从同一分布并且其协方差矩阵为Σ的两个随机变量的差异程度：
如果协方差矩阵为单位矩阵，马氏距离就简化为欧氏距离。
而马氏距离如何不受到量纲的影响呢？
1. 下图为二元数据的散点图：
将坐标拿掉以后，如下图：
2. 根据数据本身的提示信息来引入新的坐标轴。 坐标的原点在这些点的*（根据点的平均值算得）。第一个坐标轴（下图中蓝色的线）沿着数据点的“脊椎”，并向两端延伸，定义为使得数据方差最大的方向。第二个坐标轴（下图红色的线）会与第一个坐标轴垂直并向两端延伸。
3. 然后，我们需要一个比例尺度。用数据沿着每一个坐标轴的标准差来定义一个单位长度。要记住68-95-99.7法则：大约2/3的点需要在离原点一个单位长度的范围内；大约95%的点需要在离原点两个单位的长度范围内。
4.让我们重新沿着正确的方向画图——从左到右，从下到上（相当于旋转一下数据）。同时，并让每个轴方向上的单位长度相同，这样横坐标上一个单位的长度就与纵坐标上的单位长度相同。
假设数据分布是一个二维的正椭圆，x 轴 y 轴均值都为0，x轴的方差为1000，y轴的方差为1，考虑两个点 (1, 0) ， (0, 1) 到原点的距离，如果计算的是欧氏距离那么两者相等，但是仔细想一下，因为x轴的方差大，所以 (0, 1) 应该是更接近中心的点，也就是正态分布标准差的 (68, 95, 99.7) 原则。这时候需要对 x , y 轴进行缩放，对应的操作就是在协方差矩阵的对角上加上归一化的操作，使得方差变为1。 假设数据分布是一个二维的椭圆，但是不是正的，比如椭圆最长的那条线是45°的，因为矩阵的对角只是对坐标轴的归一化，如果不把椭圆旋转回来，这种归一化是没有意义的，所以矩阵上的其他元素（非对角）派上用场了。如果椭圆不是正的，说明变量之间是有相关性的（x 大 y 也大，或者负相关），加上协方差非对角元素的意义就是做旋转。
马氏距离，欧式距离，标准化欧式距离小结：
1. 欧式距离
2. 标准化欧式距离：能够体现各个特性在变差大小上的不同，同时，距离与各个特性所用单位无关
3. 马氏距离 ： 各种特性之间的联系（如身高与体重）
马氏距离的计算是建立在总体样本的基础上的，如果拿同样的两个样本，放入两个不同的总体中，最后计算得出的两个样本间的马氏距离通常是不相同的，除非这两个总体的协方差矩阵碰巧相同。
在计算马氏距离过程中，要求总体样本数大于样本的维数，否则得到的总体样本协方差矩阵逆矩阵不存在，这种情况下，用欧氏距离计算即可。
满足了条件总体样本数大于样本的维数，但是协方差矩阵的逆矩阵仍然不存在，如三个样本在其所处的二维空间平面内共线。这种情况下，也采用欧氏距离计算。
7.余弦相似度(Cosine Similarity)
余弦相似度更多的是从方向上区分差异，而对绝对的数值不敏感。因此没法衡量每个维数值的差异，会导致这样一个情况：比如用户对内容评分，5分制，X 和 Y 两个用户对两个内容的评分分别为(1,2)和(4,5)，使用余弦相似度得出的结果是0.98，两者极为相似，但从评分上看 X 似乎不喜欢这2个内容，而 Y 比较喜欢，余弦相似度对数值的不敏感导致了结果的误差，需要修正这种不合理性，就出现了调整余弦相似度，即所有维度上的数值都减去一个均值，比如 X 和 Y 的评分均值都是3，那么调整后为(-2,-1)和(1,2)，再用余弦相似度计算，得到-0.8，相似度为负值并且差异不小，但显然更加符合现实。
8.汉明距离(Hamming Distance)
两个等长字符串 s1 与 s2 的汉明距离为：将其中一个变为另外一个所需要作的最小字符替换次数。
9.杰卡德距离(Jaccard Distance)
杰卡德距离(Jaccard Distance) 是用来衡量两个集合差异性的一种指标，它是杰卡德相似系数的补集，被定义为1减去Jaccard相似系数。而杰卡德相似系数(Jaccard similarity coefficient)，也称杰卡德指数(Jaccard Index)，是用来衡量两个集合相似度的一种指标。
10.皮尔逊系数(Pearson Correlation Coefficient)
在统计学中，皮尔逊相关系数，又称皮尔逊积矩相关系数（Pearson proct-moment correlation coefficient，简称 PPMCC或PCCs），是用于度量两个变量X和Y之间的相关（线性相关），其值介于-1与1之间。
皮尔逊距离度量的是两个变量X和Y，它可以根据皮尔逊系数定义成 我们可以发现，皮尔逊系数落在 ，而皮尔逊距离落在 。
