相似度计算——欧氏距离,曼哈顿距离,闵可夫斯基距离,汉明距离,夹角余弦

模式识别、机器学习、数据挖掘当中的各种距离总结

在进行分类分析时，我们经常需要评估不同样本间的相似程度（Similarity）。选择如何计算数据间差异具有决定性的影响（Impact），因为这直接关系到分类结果的准确性（Accuracy）。

本文目录：

1.欧氏距离

2.曼哈顿距离

3. 切比雪夫距离

4. 闵可夫斯基距离

5.标准化欧氏距离

6.马氏距离

7.夹角余弦（余弦相似度）

8.汉明距离

9.杰卡德距离& 杰卡德相似系数

10.相关系数& 相关距离

11.信息熵

1. 欧氏距离(EuclideanDistance)

欧氏距离是最简单易懂的距离计算方法之一，在欧几里得空间中定义了两个点之间的距离公式

(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)Matlab计算欧氏距离

Matlab主要基于pdist函数来计算出距离。其中X为一个M×N维的矩阵，则pdist(X)将每行视为一个N维向量，并进而计算这M个向量之间的两两间距。

例子：计算向量(0,0)、(1,0)、(0,2)两两间的欧式距离

X= [0 0 ; 1 0 ; 0 2]

D= pdist(X,’euclidean’)

结果：

D=

1.0000 2.0000 2.2361

2. 曼哈顿距离(ManhattanDistance)

根据你的要求，在此提供改写后的文本

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

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

(3)Matlab计算曼哈顿距离

例子：计算向量(0,0)、(1,0)、(0,2)两两间的曼哈顿距离

X= [0 0 ; 1 0 ; 0 2]

D= pdist(X, ‘cityblock’)

结果：

D=

1 2 3

3. 切比雪夫距离 ( Chebyshev Distance )

你玩过国际象棋吗？国王每一步能走到相邻的8个方格中的任何一个。想知道从格子(x_1, y_1)到(x_2, y_2)最短需要多少步吗？试着自己算一下吧。实际上，无论怎么走，最少步数总是等于这两点坐标差值的最大值。这种方法在数学上被称为切比雪夫距离。

(1)二维平面两点a(x1,y1)与b(x2,y2)间的切比雪夫距离

(2)两个n维向量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的切比雪夫距离

这个公式的另一种等价形式是

看不出两个公式是等价的？提示一下：试试用放缩法和夹逼法则来证明。

(3)Matlab计算切比雪夫距离

例子：计算向量(0,0)、(1,0)、(0,2)两两间的切比雪夫距离

X= [0 0 ; 1 0 ; 0 2]

D= pdist(X, ‘chebychev’)

结果：

D=

1 2 2

4. 闵可夫斯基距离(MinkowskiDistance)

闵氏距离不是一种距离，而是一组距离的定义。

(1)闵氏距离的定义

两个n维变量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的闵可夫斯基距离定义为：

其中p是一个变参数。

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

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

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

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

(2)闵氏距离的缺点

闵氏距离，包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点。

举例来说，在一个二维空间中考虑身高和体重这两个变量。其中身高维度的取值范围为15米到2米之间（即约15厘米到2厘米），而体重要么取值在4.9千克到6千克之间（即约4.9kg到6kg）。具体的数据点包括a点（2米、4.9千克），b点（2米、4.9千克），以及c点（2米、6千克）。由此可见，在采用不同参数下的闵氏距离计算时（比如曼哈顿距离、欧几里得距离或切比雪夫距离），我们发现a点与b点之间的相似性度量结果等于其与c点之间的相似性度量结果。但这里出现了一个疑问：身高中每增加十分之一个单位（如十厘米），在实际生活中的感知价值是否等同于体重要每增加十分之一个单位所带来的价值呢？因此从这个角度而言使用闵氏距离作为相似性度量可能无法准确反映实际应用场景中的价值差异。

简而言之，在分析现有方法时发现闵氏距离存在两个主要缺点：(1)在处理不同维度的数据时，默认将它们视为相同度量单位可能会带来问题。(2)未能充分考虑各维度的数据分布特征（如期望值和方差等）可能存在差异。

(3)Matlab计算闵氏距离

例子：计算向量(0,0)、(1,0)、(0,2)两两间的闵氏距离（以变参数为2的欧氏距离为例）

X= [0 0 ; 1 0 ; 0 2]

D= pdist(X,’minkowski’,2)

结果：

D=

1.0000 2.0000 2.2361

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

(1)标准欧氏距离的定义

标准化欧氏距离是基于简单欧氏距离的不足而提出的一种优化策略。标准欧氏距离的核心思路是考虑到数据在各个维度上的分布不一致。首先将各个维度的数据进行归一化处理。假设样本集X的均值为m，请问如何确定归一化的目标均值和方差？计算样本集X的标准差s。最终得到归一化后的变量Z_i = (x_i - m) / s。通过这种方法处理后就能得到具有相同均值和方差的新变量集合Z

其均值为零且方差为一；即通过以下公式对数据进行标准化处理后可表示为：

标准化后的值 = ( 标准化前的值 － 分量的均值 ) /分量的标准差

通过较为简洁的推导过程即可获得两个n维向量a(x_{11},x_{12},…,x_{1n})与b(x_{21},x_{22},…,x_{2n})之间的标准化欧氏距离计算公式

如果将方差的倒数值视作一种权重，则该公式可视为一种加权欧氏距离(WeightedEuclidean distance)

(2)Matlab计算标准化欧氏距离

涉及向量间的标准化欧氏距离计算（假设各分量的标准差分别为0.5和1）

X= [0 0 ; 1 0 ; 0 2]

D= pdist(X, ‘seuclidean’,[0.5,1])

结果：

D=

2.0000 2.0000 2.8284

6. 马氏距离(MahalanobisDistance)

（1）马氏距离定义

假设有M个样本向量X₁至Xₘ，其协方差矩阵记为S，则样本均值向量记作μ。根据此设定，则样本向量X至中心点u的马氏距离计算式为

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

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

也就是欧氏距离了。

若协方差矩阵是对角矩阵，公式变成了标准化欧氏距离。

(2)马氏距离的优缺点：量纲无关，排除变量之间的相关性的干扰。

(3)Matlab计算(1 2)，( 1 3)，( 2 2)，( 3 1)两两之间的马氏距离

X = [1 2; 1 3; 2 2; 3 1]

Y = pdist(X,’mahalanobis’)

结果：

Y=

2.3452 2.0000 2.3452 1.2247 2.4495 1.2247

7. 夹角余弦(Cosine)（余弦相似度）

有没有搞错？又不是学几何？怎么突然扯到夹角余弦上来了？各位看官请不要过于紧张。几何中夹角余弦可用来衡量两个向量方向的差异，在机器学习领域中则常用这一概念来衡量样本向量之间的差异。

(1)在二维空间中向量A(x1,y1)与向量B(x2,y2)的夹角余弦公式：

(2)两个n维样本点a(x11,x12,…,x1n)和b(x21,x22,…,x2n)的夹角余弦

类似的，在计算两个n维空间中的样本点a(x₁₁,x₁₂,…,x₁ₙ)和b(x₂₁,x₂₂,…,x₂ₙ)之间相似性时，我们可以采用类似于计算向量间夹角余弦的方法

即：

夹角余弦属于区间[-1,1]。当夹角余弦数值越大时意味着两向量之间的夹角较小，在数值较小时则表示两向量间的角度较大。当两向量方向一致时其夹角余弦达到最大值1而在完全相反的方向上则达到最小值-1。

夹角余弦的具体应用可以参阅参考文献[1]。

(3)Matlab计算夹角余弦

例子：计算(1,0)、( 1,1.732)、(-1,0)两两间的夹角余弦

X= [1 0 ; 1 1.732 ; -1 0]

D= 1- pdist(X, ‘cosine’) % Matlab中的pdist(X,’cosine’)得到的是1减夹角余弦的值

结果：

D=

0.5000 -1.0000 -0.5000

8. 汉明距离(Hammingdistance)

(1)汉明距离的定义

两个等长字符串s₁与s₂之间的汉明距离被称为转换成另一个所需最少替换次数。例如，在这两个特定字符串之间计算汉明距离时，“1111”与“1001”之间有两次替换操作。

应用：信息编码（为了增强容错性，应使得编码间的最小汉明距离尽可能大）。

(2)Matlab计算汉明距离

在Matlab环境中，两个向量之间的汉明距离被定义为其不同分量的比例。

例子：计算向量(0,0)、(1,0)、(0,2)两两间的汉明距离

X = [0 0 ; 1 0 ; 0 2];

D = PDIST(X, ‘hamming’)

结果：

D=

0.5000 0.5000 1.0000

9. 杰卡德相似系数(Jaccardsimilarity coefficient)

(1) 杰卡德相似系数

两个集合A与B的共同元素在其联合集中所占的比例被定义为它们之间的杰卡德相似系数，并以符号J(A,B)表示

杰卡德相似系数是衡量两个集合的相似度一种指标。

(2) 杰卡德距离

与杰卡德相似系数相对的概念是杰卡德距离（Jaccard distance）。其计算方式如下：J(A,B)=|A∩B|/|A∪B|。

杰卡德距离基于两个集合中的不同元素数量与总元素数量的比例关系来用于衡量两个集合之间的差异性。

(3)杰卡德相似系数与杰卡德距离的应用

可将杰卡德相似系数用在衡量样本的相似度上。

样本A和样本B被视为两个n维向量，在其定义域内每个维度的取值仅限于二元状态（即只有两种可能）。例如：A=(0, 1, 1, 1) 和 B=(1, 0, 1, 2)，其中每个数值代表对应维度的状态变量取值情况。我们通常将一个样本视为一个集合，在这种情况下每一个元素的存在与否分别由二进制位来标识：即当某一位为"真"时（以数值"2"为例），则表示对应的属性存在；反之则不存在。

p：样本A与B都是1的维度的个数

q：样本A是1，样本B是0的维度的个数

r：样本A是0，样本B是1的维度的个数

s：样本A与B都是0的维度的个数

那么样本A与B的杰卡德相似系数可以表示为：

这里p+q+r可理解为A与B的并集的元素个数，而p是A与B的交集的元素个数。

而样本A与B的杰卡德距离表示为：

(4)Matlab计算杰卡德距离

相对于我所采用的方法而言，在Matlab中pdist函数所定义的杰卡德距离存在一定的差异性；具体而言，在计算过程中其衡量标准被设定为不同维度上的非零元素数量占总非零维度总数的比例。

例子：计算(1,1,0)、(1,-1,0)、(-1,1,0)两两之间的杰卡德距离

X= [1 1 0; 1 -1 0; -1 1 0]

D= pdist( X , ‘jaccard’)

结果

D=

0.5000 0.5000 1.0000

10. 相关系数( Correlation coefficient )与相关距离(Correlation distance)

(1)相关系数的定义

相关系数是一种度量随机变量X与Y之间关联程度的指标；其取值范围被限定在-1到1之间；当该数值离零越远时，则表示X与Y之间的关联程度越高；特别地，在线性关系下该数值将分别取得1（正线性关系）或-1（负线性关系）。

(2)相关距离的定义

(3)Matlab计算(1, 2 ,3 ,4 )与( 3 ,8 ,7 ,6 )之间的相关系数与相关距离

X = [1 2 3 4 ; 3 8 7 6]

C = corrcoef( X’ ) %将返回相关系数矩阵

D = pdist( X , ‘correlation’)

结果：

C=

1.0000 0.4781

0.4781 1.0000

D=

0.5219

其中0.4781就是相关系数，0.5219是相关距离。

11. 信息熵(Information Entropy)

信息熵并不是一种衡量标准。疑惑为什么会被放到这篇文章中？目前还不清楚原因。哦~

信息熵是用来表征数据分布混乱程度或分散程度的重要指标。当数据呈现高度集中状态时（即数据趋于平均），其值会增大；反之，在数据呈现高度有序状态时（即数据趋于集中），其值会减小。

计算给定的样本集X的信息熵的公式：

参数的含义：

n：样本集X的分类数

pi：X中第i类元素出现的概率

样本集S的分类越分散往往意味着其信息熵较大，在各类别出现概率均等（均为1/n）的情况下，则其对应的信息熵达到最大值log2(n)；反之，在所有样本都归属同一类别时（即类别分布退化为一个Dirac delta函数），所对应的条件熵则降至最小可能水平零。