[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<1$时，闵可夫斯基距离不再满足直递性。如当$p < 1$， $(0,0)$ 到$ (1,1)$ 的距离等于 $(1+1)^{1/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)<d(a,c)$。

def Cos(x,y):
    tmp = np.vstack([x,y])
	return pdist(tmp,'cosine')

def CosSim(x,y):
    dot_product = x.dot(y.T)
    norms = np.linalg.norm(x) * np.linalg.norm(y)
    return dot_product/norms

汉明距离(Hamming Distance)

定义：对于两个等长字符串s1与s2，将其中一个变为另外一个所需要做的最小替换次数称为汉明距离。

汉明重量：是字符串相对于同样长度的零字符串的汉明距离，也就是说，它是字符串中非零的元素个数。对于二进制字符串来说，就是 1 的个数，所以 1111 的汉明重量是 4。因此，向量空间中的元素a和b之间的汉明距离等于它们汉明重量的差。

def Ham(x,y):
    tmp = np.vstack([x,y])
	return pdist(tmp,'hamming')

编辑距离

背景：汉明距离适用相同长度字符串的比较，而且只有替换操作，对于不同长度的字符串，不仅要进行替换，而且要进行插入与删除的运算，对于这种情况，引入更加复杂的编辑距离。

定义：编辑距离是指两个字串之间，由一个转成另一个所需的最少编辑操作次数，编辑操作包括将一个字符替换成另一个字符、插入一个字符、删除一个字符三种类型。

杰卡德距离(Jaccard Distance)

杰卡德相似系数：两个集合A和B的交集元素在A和B的并集中所占的比例，称为两个集合的杰卡德相似系数。 $\mathrm{J}(\mathrm{A}, \mathrm{B})=\frac{|A \cap B|}{|A \cup B|}$ 定义：与杰卡德相似系数相反，用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。 $d(x,y)=1-J(x,y)=\frac{|x\cup y|-|x\cap y|}{x \cup y}$

def Jac(x,y):
    tmp = np.vstack([x,y])
	return pdist(tmp,'jaccard')

信息熵(Information Entropy)

背景：信息熵描述的是整个系统内部样本之间的一个距离，或者称之为系统内样本分布的集中程度/一致程度、分散程度、混乱程度/不一致程度。系统内样本分布越分散/分布越平均，信息熵就越大。分布越有序/分布越集中，信息熵就越小。

定义： $\text { Entropy }(\mathrm{X})=\sum_{i=1}^{n}-p_{i} \log _{2} p_{i}$ 其中，$n$为样本集$X$的分类数，$p_i$为$X$中第 $i $类元素出现的概率。

DTW 距离（Dynamic Time Warp）

定义：DTW 距离是序列信号在时间或者速度上不匹配的时候一种衡量相似度的方法。

def dtw(sa,sb):
    MAX_COST = 1<<32
    #初始化一个len(sb) 行(i)，len(sa)列(j)的二维矩阵
    len_sa = len(sa)
    len_sb = len(sb)
    # BUG:这样是错误的(浅拷贝): dtw_array = [[MAX_COST]*len(sa)]*len(sb)
    dtw_array = [[MAX_COST for i in range(len_sa)] for j in range(len_sb)]
    dtw_array[0][0] = distance(sa[0],sb[0])
    for i in xrange(0, len_sb):
        for j in xrange(0, len_sa):
            if i+j==0:
                continue
            nb = []
            if i > 0: nb.append(dtw_array[i-1][j])
            if j > 0: nb.append(dtw_array[i][j-1])
            if i > 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]

Tmylla

不同距离度量总结：欧式、马氏、编辑距离、信息熵等11种方法

距离

欧氏距离(Euclidean Distance)

标准欧氏距离

曼哈顿距离(Manhattan Distance)

切比雪夫距离(Chebyshev distance)

闵可夫斯基距离(Minkowski Distance)

马氏距离(Mahalanobis distance)

余弦距离(Cosine Distance)

汉明距离(Hamming Distance)

编辑距离

杰卡德距离(Jaccard Distance)

相关距离(Correlation distance)

信息熵(Information Entropy)

DTW 距离（Dynamic Time Warp）

卡方检验（Chi-Square）

KL 散度（ KL-Divergence）

互信息（mutual information）

斯皮尔曼等级相关（Spearman Rank Correlation）

EMD距离(Earth Mover’s Distance)

参考

Search

欢迎关注我的微信公众号

Table of Contents