文本匹配相似度计算---多种距离算法 ，多种相似度计算算法，一看就懂_相似度匹配算法

常见的距离算法和相似度（相关系数）计算方法

1.常见的距离算法

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

Matlab计算距离主要使用pdist函数。若X是一个M×N的矩阵，则pdist(X)将X矩阵M行的每一行作为一个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
1

1.2马哈拉诺比斯距离（Mahalanobis Distance）

马哈拉诺比斯距离是由印度统计学家马哈拉诺比斯(英语)提出的，表示数据的协方差距离。它是一种有效的计算两个未知样本集的相似度的方法。与欧氏距离不同的是它考虑到各种特性之间的联系（例如：一条关于身高的信息会带来一条关于体重的信息，因为两者是有关联的）并且是尺度无关的（scale-invariant），即独立于测量尺度。
对于一个均值为协方差矩阵为 的多变量向量其马氏距离为

马哈拉诺比斯距离也可以定义为两个服从同一分布并且其协方差矩阵为 Σ 的随机变量X 与 Y的差异程度：

如果协方差矩阵为单位矩阵，马哈拉诺比斯距离就简化为欧氏距离；如果协方差矩阵为对角阵，其也可称为正规化的欧氏距离。

1.3曼哈顿距离（Manhattan Distance）

曼哈顿距离也叫出租车距离，用来标明两个点在标准坐标系上的绝对轴距总和。

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

(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
1

1.4切比雪夫距离（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)间的切比雪夫距离

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

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

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

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

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

D = pdist(X, ‘chebychev’)

结果

D =

 1     2     2
1

1.5闵可夫斯基距离（Minkowski Distance）

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

(1) 闵氏距离的定义

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

其中p是一个变参数。

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

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

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

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

(2)闵氏距离的缺点

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

举个例子：二维样本(身高,体重)，其中身高范围是150_{190，体重范围是50}60，有三个样 本：a(180,50)，b(190,50)，c(180,60)。那么a与b之间的闵氏距离（无论是曼哈顿距离、欧氏距离或切比雪夫距离）等于a与c之 间的闵氏距离，但是身高的10cm真的等价于体重的10kg么？因此用闵氏距离来衡量这些样本间的相似度很有问题。

   简单说来，闵氏距离的缺点主要有两个：(1)将各个分量的量纲(scale)，也就是“单位”当作相同的看待了。(2)没有考虑各个分量的分布（期望，方差等)可能是不同的。
1

(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
1

1.6汉明距离（Hamming distance）

(1)汉明距离的定义

   两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。例如字符串“1111”与“1001”之间的汉明距离为2。

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

(2)Matlab计算汉明距离

Matlab中2个向量之间的汉明距离的定义为2个向量不同的分量所占的百分比。

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

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

D = PDIST(X, ‘hamming’)

结果：

D =

0.5000    0.5000    1.0000
1

1.7 马氏距离(Mahalanobis Distance)

（1）马氏距离定义

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

而其中向量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
1

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

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

标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案。标准欧氏距离的思路：既然数据各维分量的分布不一样，好吧！那我先将各个分量都“标准 化”到均值、方差相等吧。均值和方差标准化到多少呢？这里先复习点统计学知识吧，假设样本集X的均值(mean)为m，标准差(standard deviation)为s，那么X的“标准化变量”表示为：

而且标准化变量的数学期望为0，方差为1。因此样本集的标准化过程(standardization)用公式描述就是：

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

经过简单的推导就可以得到两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的标准化欧氏距离的公式：

　　如果将方差的倒数看成是一个权重，这个公式可以看成是一种加权欧氏距离(Weighted Euclidean distance)。

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

例子：计算向量(0,0)、(1,0)、(0,2)两两间的标准化欧氏距离 (假设两个分量的标准差分别为0.5和1)

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

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

结果：

D =

2.0000    2.0000    2.8284
1

2.常见的相似度（系数）算法

2.1余弦相似度（Cosine Similarity）以及调整余弦相似度（Adjusted Cosine Similarity）

几何中夹角余弦可用来衡量两个向量方向的差异，机器学习中借用这一概念来衡量样本向量之间的差异。

(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,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
1

2.2皮尔森相关系数（Pearson Correlation Coefficient）

即相关分析中的相关系数r，分别对X和Y基于自身总体标准化后计算空间向量的余弦夹角。公式如下：
　

2.3Jaccard相似系数（Jaccard Coefficient）

(1) 杰卡德相似系数

   两个集合A和B的交集元素在A，B的并集中所占的比例，称为两个集合的杰卡德相似系数，用符号J(A,B)表示。
1

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

(2) 杰卡德距离

   与杰卡德相似系数相反的概念是杰卡德距离(Jaccard distance)。杰卡德距离可用如下公式表示：
1

　　杰卡德距离用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。

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

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

样本A与样本B是两个n维向量，而且所有维度的取值都是0或1。例如：A(0111)和B(1011)。我们将样本看成是一个集合，1表示集合包含该元素，0表示集合不包含该元素。

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函数定义的杰卡德距离跟我这里的定义有一些差别，Matlab中将其定义为不同的维度的个数占“非全零维度”的比例。

例子：计算(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

2.4Tanimoto系数（广义Jaccard相似系数）

Jaccard相关系数用来衡量两个集合的相关性，数值越大，相似度就越高。相对于Jaccard系数，Jaccard距离是用来衡量两个样本集合的差异性的。

Jaccard相关系数：

Jaccard距离：

如果A，B集合中元素的取值为二值数（0,或者1，0代表此元素不在这个集合中，1代表此元素在这个集合中）那么Jaccard相关系数和Jaccard距离也可以这样求：

M11代表A,B集合中相同位置同为1的个数

M01 代表A集合中相同位置元素为0，而B集合为1的个数

M10代表A集合中相同位置元素为1，而B集合为0的个数

M00代表A,B集合中相同位置同为0的个数

因为在大多情况下 ，0的个数会大大多于1的个数，就会显得很稀疏，如果只考虑M11，则有：

s=M11/(M00+M10+M01+M11) 称为Jaccard距离

而Tanimoto系数又称为广义的Jaccard相关系数

A,B代表两个样本向量

2.5对数似然相似度/对数似然相似率

我以一个实际的例子来介绍一下其中的计算过程：假设有商品全集I=｛a,b,c,d,e,f｝，其中A用户偏好商品{a,b,c}，B用户偏好商品{b,d}，那么有如下矩阵：

• k11表示用户A和用户B的共同偏好的商品数量，显然只有商品b，因此值为1
• k12表示用户A的特有偏好，即商品{a,c}，因此值为2
  k21表示用户B的特有偏好，即商品d，因此值为1
  k22表示用户A、B的共同非偏好，有商品{e,f}，值为2

此外我们还定义以下变量N=k11+k12+k21+k22，即总商品数量。

计算步骤如下：

1. 计算行熵


2.计算列熵

3.计算矩阵熵

注意：以上熵的计算均没有加负号，后面会讲到原因

4.计算相似度

如何来解释这个相似度的计算方式呢？我们先来看看行熵、列熵和矩阵熵分别代表什么含义：行熵以用户A的偏好和非偏好来划分商品空间，很明显它是一个条件熵，我个人认为相对合理的解释是对于一个商品，在给定它是否属于A偏好的条件下，预测商品属于k11、k12、k21、k22四个空间中哪一个空间的不确定度；同理，列熵则代表给定商品是否属于B偏好的条件下，预测商品属于k11、k12、k21、k22四个空间中哪一个空间的不确定度；矩阵熵则表示在没有任何条件下，预测商品属于四个空间中哪一个空间的不确定度。我们以下图来看：

在给定A偏好与否的条件，预测商品属于哪一个空间的不确定度为S1+S2；在给定B偏好与否的条件下，不确定度为S2+S3；在不给定任何条件下，预测商品属于哪一个空间的不确定度为S1+S2+S3。我的理解这个S2表示的就是给定A、B偏好条件下的公共的不确定度，其表达的就是如果A喜欢某个商品，对B也具有协同效应；如果B喜欢某个商品，对A也具有协同效应，这种公共不确定度或者说是关联其实反映的就是A用户与B用户的相似程度。由于前面计算熵的时候没有加上负号，步骤四中正好得到一个(−S2)，就变成正数了，至于为什么乘上2及1N去哪里了我也不清楚，但这只是一种幅度变换，不影响相对关系。

当然参考论文Accurate methods for the statistics of surprise and coincidence，我们还可以从相关性的角度去解释这个对数似然比相似度。我们假设A偏好空间和A非偏好空间中概率分布满足二项分布，并进行如下假设：

• 假设用户B的喜好与用户1独立无关L(H1)

形成A偏好空间这种分布的概率就为

形成A非偏好空间这种分布的概率为

形成第一幅图中矩阵块分布的概率即为上面两个概率的乘积

• 假设用户B的喜好与用户1相关L(H2)
  在A偏好空间，用户B喜欢一个商品的概率为
  
  形成A偏好空间这种分布的概率就为
  
  在A非偏好空间，用户B喜欢一个商品的概率为
  
  形成A非偏好空间这种分布的概率就为
  
  形成第一幅图中矩阵块分布的概率即为上面两个概率的乘积
  
  用户A、B的相似度就为
  
  公式中 −2log和卡方检验渐近有关，上述假设是按照用户A来划分空间，按用户B来划分空间也可以得到相同的结论，最终计算出来的结果与采用上面行熵、列熵、矩阵熵计算出来的结果一致，表明对数似然比相似度其实反映的就是用户之间喜欢物品的相关性。

2.6互信息/信息增益，相对熵/KL散度

互信息

两个随机变量X,Y的互信息，定义为：X,Y的联合分布P(X,Y)与乘积分布P(X)P(Y)的相对熵：
　　　　
怎么理解呢？也就是用乘积分布P(X)P(Y)与联合分布的交叉熵，减去联合分布的信息熵，就是互信息，还不好理解，就可以看如下图示：

相当于一种不严谨的说法就是： ( X + Y ) − X ⋃ Y = X ⋂ Y (X+Y)-X\bigcup Y=X\bigcap Y (X+Y)−X⋃Y=X⋂Y
或许另一种等价的定义好理解：
I(X;Y)=H(X)−H(X∣Y)

到这里相信大家已经看出来了，上面这个公式表示的就是，在Y已知的条件下，X的信息量减少的多少。也就是决策树中的信息增益
其实两种定义是等价的：

相对熵就是KL散度，用来度量两个分布之间的距离。

由交叉熵可知，用估计的概率分布所需的编码长度，比真实分布的编码长，但是长多少呢？这个就需要另一个度量，相对熵，也称KL散度。

相对熵：用交叉熵减去真实分布的信息熵，表示用估计分布计算的平均编码长度比最短平均编码长度长多少。因此有：

交叉熵=信息熵+相对熵

由于对数函数是凸函数，则有：

因此，相对熵始终是大于等于0的。从上面的描述中也可以看得出，相对熵其实可以理解成两种分布的距离。

2.7信息检索–词频-逆文档频率（TF-IDF）

我们再介绍另外一种应用更为常见和广泛的词袋模型表示方式——TFIDF表示方法。之所以陆续的会出现不同的向量化表示形式，其最终目的都只有一个，即尽可能准确的对原始文本进行表示。

1 TF-IDF

TF-IDF为词频-逆文档频率（term frequence - inverse document frequence） 的简称。首先需要明白的是TF-IDF实际上是TF与IDF两者的乘积。之所以出现TF-IDF的原因在于，通常来说在一个样本中一次词出现的频率越高，其重要性应该对应越高，即考虑到词频对文本向量的影响；但是如果仅仅只是考虑到这一个因素则同样会带来一个新的弊端，即有的词不只是在某个样本中出现的频率高，其实它在整个数据集中的出现频率都很高，而这样的词往往也是没有意义的。因此，TF-IDF的做法是通过词的逆文档频率来加以修正调整。

1.1 计算步骤

考虑到每个样本有长短之分，我们对"词频"进行一个标准化处理：

逆文档频率

可以发现，如果一个词越常见，那么分母就越大，逆文档频率就越小越接近0。分母之所以要加1，是为了避免分母为0（即所有文档都不包含该词）的平滑处理。log表示对得到的值取对数（此处为自然对数）。

然后将计算得到的TF乘以IDF便得到了一个词的TF-IDF权重值。接着，对于数据集中的每个词都进行计算对应的TF-IDF值，最后将所有的值组合成一个矩阵。

注：如果这个词没有出现在词表中，那么其对应的TF-IDF则为0

3.距离算法与相似度算法的选择（对比）

3.1 欧式距离和余弦相似度

欧氏距离是最常见的距离度量，而余弦相似度则是最常见的相似度度量，很多的距离度量和相似度度量都是基于这两者的变形和衍生，所以下面重点比较下两者在衡量个体差异时实现方式和应用环境上的区别。

借助三维坐标系来看下欧氏距离和余弦相似度的区别：

从图上可以看出距离度量衡量的是空间各点间的绝对距离，跟各个点所在的位置坐标（即个体特征维度的数值）直接相关；而余弦相似度衡量的是空间向 量的夹角，更加的是体现在方向上的差异，而不是位置。如果保持A点的位置不变，B点朝原方向远离坐标轴原点，那么这个时候余弦相似度cosθ是保持不变 的，因为夹角不变，而A、B两点的距离显然在发生改变，这就是欧氏距离和余弦相似度的不同之处。

根据欧氏距离和余弦相似度各自的计算方式和衡量特征，分别适用于不同的数据分析模型：欧氏距离能够体现个体数值特征的绝对差异，所以更多的用于 需要从维度的数值大小中体现差异的分析，如使用用户行为指标分析用户价值的相似度或差异；而余弦相似度更多的是从方向上区分差异，而对绝对的数值不敏感， 更多的用于使用用户对内容评分来区分用户兴趣的相似度和差异，同时修正了用户间可能存在的度量标准不统一的问题（因为余弦相似度对绝对数值不敏感）。