一些距离表示和相似度量

本文主要是介绍一些距离表示和相似度量，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

信号或者多维空间里，常常需要用一些距离或者相关度量来衡量两个点或向量的距离和相似度。下面列举一些常用于不同的模型和空间的距离。

1. 欧氏距离（euclidean distance）

最通常采用的距离定义，指在m维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。在二维和三维空间中的欧氏距离就是两点之间的实际距离（直线距离）。在m维空间中，欧式距离的计算如下：

2. 马氏距离(Mahalanobis distance)

马氏距离表示数据的协方差距离。它是一种有效的计算两个未知样本集的相似度的方法。与欧氏距离不同的是它考虑到各种特性之间的联系（例如：一条关于身高的信息会带来一条关于体重的信息，因为两者是有关联的）并且是尺度无关的(scale-invariant)，即独立于测量尺度。

有M个样本向量X1~Xm，协方差矩阵记为S，均值记为向量μ，则其中样本向量X到μ的马氏距离表示为：

而其中向量Xi与Xj之间的马氏距离定义为：

若协方差矩阵是单位矩阵（各个样本向量之间独立同分布）,则公式就成了：

也就是欧氏距离了。

3. Bhattacharyya距离

在统计学中，Bhattacharyya距离（以下称巴氏距离）测量的是两个离散或连续概率分布的相似性。计算方式和Bhattacharyya系数关系很密切。两种计算方式都以A. Bhattacharyya名字命名，Bhattacharyya是一位30年代在印度统计研究所工作的统计学家。巴氏系数可用来对两组样本的相关性进行测量。这一方法常用来作分类器算法

数学定义

-离散概率分布

　　对于在X数域上的两个离散概率分布p和q，巴氏距离定义为:

其中

被称作Bhattacharyya系数（巴氏系数，Bhattacharyya Coefficien）

　　 $0 \le BC \le 1$ 且 $0 \le D_B \le \infty$

对于连续概率分布

　　在连续函数中，Bhattacharyya系数如下定义：

$0 \le BC \le 1$ 且 $0 \le D_B \le \infty$

两种情形中，巴氏距离DB均不满足三角不等式

例如在正态分布下，p(x)和q(x)的巴氏距离为；

$D_{B}(p,q) = \frac{1}{4} \ln \left ( \frac{1}{4}\left( \frac{\sigma_{p}^{2}}{\sigma_{q}^{2}}+\frac{\sigma_{q}^{2}}{\sigma_{p}^{2}}+2\right ) \right ) +\frac{1}{4} \left ( \frac{(\mu_{p}-\mu_{q})^{2}}{\sigma_{p}^{2}+\sigma_{q}^{2}}\right )$

其中，σ和μ分别表示相应的均值和方差。

Bhattacharyya系数

巴氏系数是对两个统计样本的重叠量的近似计算。巴氏系数可用来对两组样本的相关性进行测量。

计算巴氏系数涉及到对该两个样本的重叠部分进行基本形式的积分。两个样本值的积分被分成指定数目的部分。而每一个样本的每一个部分的成员数被用于下式中：

4.Hellinger 距离

在概率论和统计理论中，Hellinger距离被用来度量两个概率分布的相似度。它是f散度的一种（f散度——度量两个概率分布相似度的指标）。为了从度量理论的角度定义Hellinger距离，我们假设P和Q是两个概率测度，并且它们对于第三个概率测度λ来说是绝对连续的，则P和Q的Hellinger距离的平方被定义如下：

$H^2(P,Q) = \frac{1}{2}\displaystyle \int \left(\sqrt{\frac{dP}{d\lambda}} - \sqrt{\frac{dQ}{d\lambda}}\right)^2 d\lambda.$

这里的dP/ dλ 和 dQ/ dλ分别是P和Q的Radon–Nikodym微分。这里的定义是与λ无关的，因此当我们用另外一个概率测度替换λ时，只要P和Q关于它绝对连续，那么上式就不变。为了简单起见，我们通常把上式改写为：

$H^2(P,Q) = \frac{1}{2}\int \left(\sqrt{dP} - \sqrt{dQ}\right)^2.$

Hellinger距离满足如下性质：

$0\le H(P,Q) \le 1.$

离散概率分布

对于两个离散概率分布 P=(p1,p2,...,pn)和 Q=（q1,q2,...,qn)，它们的Hellinger距离可以定义如下：

$H(P, Q) = \frac{1}{\sqrt{2}} \; \sqrt{\sum_{i=1}^{k} (\sqrt{p_i} - \sqrt{q_i})^2},$

上式可以被看作两个离散概率分布平方根向量的欧式距离，如下所示：

$H(P, Q) = \frac{1}{\sqrt{2}} \; \|\sqrt{P} - \sqrt{Q} \|_2 .$

两个正态分布P 和 Q的Hellinger距离的平方可以被定义为：

$H^2(P, Q) = 1 - \sqrt{\frac{2\sigma_1\sigma_2}{\sigma_1^2+\sigma_2^2}} \, e^{-\frac{1}{4}\frac{(\mu_1-\mu_2)^2}{\sigma_1^2+\sigma_2^2}} .$

两个指数分布P 和 Q的Hellinger距离的平方可被定义为：

$H^2(P, Q) = 1 - \frac{2 \sqrt{\alpha \beta}}{\alpha + \beta}.$

两个威利分布P 和 Q（此处k是一个形状参数，α和β是尺度系数）的Hellinger距离的平方可被定义为：

$H^2(P, Q) = 1 - \frac{2 (\alpha \beta)^{k/2}}{\alpha^{k} + \beta^{k}}.$

对于两个具有参数α和β的泊松分布 P 和 Q，它们的Hellinger距离可被定义为：

$H^2(P,Q) = 1-e^{-\frac{1}{2}(\sqrt{\alpha} - \sqrt{\beta})^2}.$

5.明氏距离 (或译成闵可夫斯基距离 MinkowskiDistance)

又叫做明可夫斯基距离,是欧氏空间中的一种测度，被看做是欧氏距离的一种推广，对于n维空间的两个点x，y的明氏距离的定义式：

当p=1时，就是曼哈顿距离

当p=2时，就是欧氏距离

当p→∞时，就是切比雪夫距离

根据变参数的不同，闵氏距离可以表示一类的距离。

6.汉明距离

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

1011101与1001001之间的汉明距离是2。
2143896与2233796之间的汉明距离是3。
"toned"与"roses"之间的汉明距离是3。

用3个二进制位来表示立方体顶点的编码，那个任意两个顶点（二进制序列）的汉明距离就是边长。如下图所示，从000到111要走3步，汉明距离就是3。

用4个二进制表示的超立方体的编码也类似，只是多了一位，距离计算也是位变化数量。

7. 曼哈顿距离(ManhattanDistance)

从名字就可以猜出这种距离的计算方法了。想象你在曼哈顿要从一个十字路口开车到另外一个十字路口，驾驶距离是两点间的直线距离吗？显然不是，除非你能穿越大楼。实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源，曼哈顿距离也称为城市街区距离(CityBlock distance)。

(1)二维平面两点a(x1,y1)与b(x2,y2)间的曼哈顿距离

(2)两个n维向量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的曼哈顿距离

8.余弦距离(Cosine Distance)

从名字就可以知道计算什么了，就是两个向量的余弦，对于n维空间的两个向量a和b，其余弦距离；

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

二个点之间的距离定义为其各座标数值差的最大值，以(x₁,y₁)和(x₂,y₂)二点为例，其切比雪夫距离为max(|x₂-x₁|,|y₂-y₁|)。切比雪夫距离得名自俄罗斯数学家切比雪夫。若将国际象棋棋盘放在二维直角座标系中，格子的边长定义为1，座标的x轴及y轴和棋盘方格平行，原点恰落在某一格的中心点，则王从一个位置走到其他位置需要的步数恰为二个位置的切比雪夫距离，因此切比雪夫距离也称为棋盘距离。例如位置F6和位置E2的切比雪夫距离为4。任何一个不在棋盘边缘的位置，和周围八个位置的切比雪夫距离都是1。

若二个向量或二个点p 、and q，其座标分别为 $p_i$ 及 $q_i$ ，则两者之间的切比雪夫距离定义如下：

D_{\rm Chebyshev}(p,q) := \max_i(|p_i - q_i|).\

这也等于以下L_p度量的极值：

\lim_{k \to \infty} \bigg( \sum_{i=1}^n \left| p_i - q_i \right|^k \bigg)^{1/k},

因此切比雪夫距离也称为L_∞度量。

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

在平面几何中，若二点p及q的直角坐标系坐标为 $(x_1,y_1)$ 及 $(x_2,y_2)$ ，则切比雪夫距离为

D_{\rm Chess} = \max \left ( \left | x_2 - x_1 \right | , \left | y_2 - y_1 \right | \right ) .

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

10. 杰卡德距离(Jaccard Distance)

杰卡德距离是用来衡量两个集合差异性的一种指标，它是杰卡德相似系数的补集，被定义为1减去Jaccard相似系数。而杰卡德相似系数(Jaccard similarity coefficient)，也称杰卡德指数(Jaccard Index)，是用来衡量两个集合相似度的一种指标。

Jaccard相似指数用来度量两个集合之间的相似性，它被定义为两个集合交集的元素个数除以并集的元素个数。

Jaccard距离用来度量两个集合之间的差异性，它是Jaccard的相似系数的补集，被定义为1减去Jaccard相似系数。

1) 若A、B两个集合都为空，则

;

2) ; 给定两个n维二元向量A、B，A、B的每一维都只能是0或者1，利用Jaccard相似系数来计算二者的相似性：

1）M 00 代表向量A与向量B都是0的维度个数；

2）M 01 代表向量A是0而向量B是1的维度个数；

3）M 10 代表向量A是1而向量B是0的维度个数；

M 11

代表向量A和向量B都是1的维度个数。

n维向量的每一维都会落入这4类中的某一类，因此：

则Jaccard相似系数为

Jaccard距离为

11. 信息熵(Information Entropy)

熵用于度量一个热力学系统的无序程度。在信息论里面，熵是对不确定性的测量。但是在信息世界，熵越高，则能传输越多的信息，熵越低，则意味着传输的信息越少。英语文本数据流的熵比较低，因为英语很容易读懂，也就是说很容易被预测。即便我们不知道下一段英语文字是什么内容，但是我们能很容易地预测，比如，字母e总是比字母z多，或者qu字母组合的可能性总是超过q与任何其它字母的组合。如果未经压缩，一段英文文本的每个字母需要8个比特来编码，但是实际上英文文本的熵大概只有4.7比特。

熵的计算

如果有一枚理想的硬币，其出现正面和反面的机会相等，则抛硬币事件的熵等于其能够达到的最大值。我们无法知道下一个硬币抛掷的结果是什么，因此每一次抛硬币都是不可预测的。因此，使用一枚正常硬币进行若干次抛掷，这个事件的熵是一比特，因为结果不外乎两个——正面或者反面，可以表示为0, 1编码，而且两个结果彼此之间相互独立。若进行n次独立实验，则熵为n，因为可以用长度为n的比特流表示。但是如果一枚硬币的两面完全相同，那个这个系列抛硬币事件的熵等于零，因为结果能被准确预测。现实世界里，我们收集到的数据的熵介于上面两种情况之间。

另一个稍微复杂的例子是假设一个随机变量X，取三种可能值 $\begin{smallmatrix} x_1, x_2, x_3 \end{smallmatrix}$ ，概率分别为 $\begin{smallmatrix} \frac{1}{2}, \frac{1}{4}, \frac{1}{4} \end{smallmatrix}$ ，那么编码平均比特长度是： $\begin{smallmatrix} \frac{1}{2} \times 1 + \frac{1}{4} \times 2 + \frac{1}{4} \times 2 = \frac{3}{2} \end{smallmatrix}$ 。其熵为3/2。因此熵实际是对随机变量的比特量和顺次发生概率相乘再总和的数学期望。