不同距离度量总结：欧式、马氏、编辑距离、信息熵等11种方法 |
您所在的位置：网站首页 › 欧式距离的定义 › 不同距离度量总结：欧式、马氏、编辑距离、信息熵等11种方法 |
不同距离度量总结：欧式、马氏、编辑距离、信息熵等11种方法
|
[TOC] 距离设$X$是任一非空集，对$X$中任意两点$x,y$有一实数$d(x,y)$与之对应且满足： 非负性、同一性：$d(x,y)\ge0$，且$d(x,y)=0$当且仅当$x=y$； 对称性：$d(x,y)=d(y,x)$； 直递性（三角不等式）：$d(x,y)\le d(x,z)+d(z,y)$。称$d(x,y)$为$X$中的一个距离，定义了距离$d$的集$X$称为一个距离空间，记为$(X,d)$，在不引起混乱的情形下简记为$X$。 欧氏距离(Euclidean Distance)定义：欧几里得空间中两点间“普通”距离（即直线距离），数学中多数人最熟悉的距离。 \[d(x, y)=\sqrt{\sum_{k=1}^{n}\left(x_{k}-y_{k}\right)^{2}}\] import numpy as np def Euc(x,y): # Euclidean Distance return np.sqrt(np.sum(np.square(x-y))) 标准欧氏距离定义：将变量各维度数据在该维度上进行标准化（$x_k=(x_k-m_k)/s_k$，其中$m_k,s_k$分别为k维上的均值和标准差），然后计算欧氏距离。 \[d(x, y)=\sqrt{\sum_{k=1}^{n}\left(\frac{x_{k}-y_{k}}{s_{k}}\right)^{2}}\] from scipy.spatial.distance import pdist def sEuc(x,y): tmp = np.vstack([x,y]) return pdist(X,'seuclidean') 曼哈顿距离(Manhattan Distance)背景：顾名思义，在曼哈顿街区要从一个十字路口开车到另一个十字路口，驾驶距离显然不是两点间的直线距离。这个实际驾驶距离就是“曼哈顿距离”。曼哈顿距离也称为“城市街区距离”(City Block distance)。 定义：在欧几里德空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和。 \[d(x, y)=\sum_{k=1}^{n}\left|x_{k}-y_{k}\right|\] def Man(x,y): return np.sum(np.abs(x,y))
图中灰色表示街道，绿色的斜线表示欧几里得距离，其他三条折线表示了曼哈顿距离，这三条折线的长度是相等的。 切比雪夫距离(Chebyshev distance)背景：国际象棋中，国王可以直行、横行、斜行，所以国王走一步可以移动到相邻8个方格中的任意一个。国王从一个格子走到另一个格子最少需要的步数就叫切比雪夫距离。
定义：切比雪夫距离是向量空间中的一种度量，两个点之间的距离定义是其各坐标数值差绝对值的最大值。 \[d(x, y)=\max \left(\left|x_{1}-y_{1}\right|, \cdots,\left|x_{n}-y_{n}\right|\right)\] def Che(x,y): return np.max(np.abs(x,y)) 闵可夫斯基距离(Minkowski Distance)定义：闵氏距离不是一种距离，而是一组距离的定义，是对多个距离度量公式的概括性的表述。 $d(x,y)=\left(\sum_{i=1}^{n}\left x_{i}-y_{i}\right ^{p}\right)^{1 / p}$其中，当$p=1$时，曼哈顿距离；当$p=2$时，欧氏距离；当$p\to\infty$，切比雪夫距离。 注意，当$p 2$，而$ (0,1)$ 到这两个点的距离都是 1。 缺点： 与数据的分布无关，当不同维量级不同时，几乎忽略小量级的影响。如$x=(1,10000),y=(2,20000)$，这时闵氏距离会过度放大1维（从0维计数）方向的作用。为此，在计算距离前需要对不同维数做归一化处理，见标准化欧氏距离； 只考虑数值，忽略各分量的量纲(scale)。如$x=(180cm,50kg),y=(190cm,50kg),z=(180cm,60kg)$，根据闵氏距离，有$d(x,y)=d(x,z)$，但我们期望的不会是10cm等效于10kg。为此，引入马氏距离。 def Min(x,y,z): tmp = np.vstack([x,y]) return pdist(tmp, 'minkowski', p=z) 马氏距离(Mahalanobis distance)
背景：在上图中，黄色背景表示样本分布。左侧图中，A、B两点距中心的欧式距离相等，但A的马氏距离（考虑样本分布，或将样本分布想象为等高线）大于B；在右侧图，A、B两点距中心的马式距离相等，但A的欧氏距离（考虑样本分布）显然小于B。 定义：马氏距离考虑到各种特性之间的联系，并且是尺度无关的，表示两个服从同一分布、协方差矩阵为S的随机变量之间的差异程度。 \[\mathrm{d}\left(x, y\right)=\sqrt{\left(x-y\right)^{T} S^{-1}\left(x-y\right)}\]协方差矩阵： \(S=\left[\begin{array}{ccc} \sigma\left(x_{1}, x_{1}\right) & \cdots & \sigma\left(x_{1}, x_{d}\right) \\ \vdots & \ddots & \vdots \\ \sigma\left(x_{d}, x_{1}\right) & \cdots & \sigma\left(x_{d}, x_{d}\right) \end{array}\right] \in \mathbb{R}^{d \times d}\) 其中，$d$表示向量维数，对角线元素为方差，非对角线元素为协方差。 \(\sigma\left(x_{i}, x_{i}\right)=\frac{1}{n-1} \sum_{m=1}^{n}\left(x_{i m}-\bar{x}_{i}\right)^{2}, i=0，1,2, \ldots, d-1\) \[\sigma\left(x_{i}, x_{j}\right)=\frac{1}{n-1} \sum_{m=1}^{n}\left(x_{i m}-\bar{x}_{i}\right)\left(x_{j m}-\bar{x}_{j}\right)\]其中，$x_{im}$表示随机变量第$i$维中的第$m$个观测样本，$n$表示样本量。 特点： 它不受量纲的影响，两点之间的马氏距离与原始数据的测量单位无关； 由标准化数据和中心化数据(即原始数据与均值之差）计算出的二点之间的马氏距离相同; 可以排除变量之间的相关性的干扰； 要求总体样本数大于样本的维数，否则得到的总体样本协方差矩阵逆矩阵不存在。 def Mah(x,y): tmp = np.vstack([x,y]).T return pdist(tmp,'mahalanobis') 余弦距离(Cosine Distance)余弦相似度：余弦相似度，又称为余弦相似性，是通过计算两个向量的夹角余弦值来评估他们的相似度。 \(\cos (x,y)=\frac{x\cdot y}{|x||y|}=\frac{\sum_{k=1}^{n} x_{k} y_{k}}{\sqrt{\sum_{k=1}^{n} x_{k}^{2}} \sqrt{\sum_{k=1}^{n} y_{k}^{2}}}\) 定义：余弦距离就是用1减去余弦相似度，$d(x,y)=1-CosSim(x,y)$，余弦距离的取值范围为[0,2]。 注意，余弦距离不严格满足三角不等式，如$a(0,1),b(1,1),c(1,0)$，$d(a,b)=1-\frac{\sqrt{2}} {2}$,$d(b,c)=1-\frac{\sqrt{2}} {2}$,$d(a,c)=1$，$d(a,b)+d(b,c) 0 and j > 0: nb.append(dtw_array[i-1][j-1]) min_route = min(nb) cost = distance(sa[j],sb[i]) dtw_array[i][j] = cost + min_route return dtw_array[len_sb-1][len_sa-1] 卡方检验（Chi-Square） KL 散度（ KL-Divergence） 互信息（mutual information） 斯皮尔曼等级相关（Spearman Rank Correlation） EMD距离(Earth Mover’s Distance) 总之，一般情况下，相似度越大越好，距离越小越好。 参考漫谈：机器学习中距离和相似性度量方法 机器学习——几种距离度量方法比较 |
【本文地址】
今日新闻 |
推荐新闻 |