常用相似性(距离)度量方法概述

(131) 2024-04-18 10:01:01

1 使用背景

在数据分析和数据挖掘的过程中,我们经常需要知道个体间差异的大小,进而评价个体的相似性和类别。

最常见的是数据分析中的相关性分析,数据挖掘中的分类和聚类算法,如K最近邻(KNN)和K均值(K-Means)、图计算等等。

在做很多研究问题

2 距离度量

距离度量(Distance)用于衡量个体在空间上存在的距离,距离越远说明个体间的差异越大。

2.1. 曼哈顿距离(Manhattan Distance)

   在曼哈顿要从一个十字路口开车到另外一个十字路口,实际驾驶距离就是这个“曼哈顿距离”。而这也是曼哈顿距离名称的来源, 曼哈顿距离也称为城市街区距离(City Block distance)。

(1)二维平面两点a(x1,y1)与b(x2,y2)间的曼哈顿距离
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第1张
(2)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的曼哈顿距离常用相似性(距离)度量方法概述 (https://mushiming.com/)  第2张
2.2. 欧氏距离(Euclidean Distance)

   欧氏距离是最易于理解的一种距离计算方法,源自欧氏空间中两点间的距离公式,衡量的是多维空间中各个点之间的绝对距离。

(1)二维平面上两点a(x1,y1)与b(x2,y2)间的欧氏距离:
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第3张
(2)三维空间两点a(x1,y1,z1)与b(x2,y2,z2)间的欧氏距离:
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第4张
(3)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的欧氏距离:
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第5张
  也可以用表示成向量运算的形式:
  常用相似性(距离)度量方法概述 (https://mushiming.com/)  第6张
因为计算是基于各维度特征的绝对数值,所以欧氏度量需要保证各维度指标在相同的刻度级别,比如对身高(cm)和体重(kg)两个单位不同的指标使用欧式距离可能使结果失效。

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

   国际象棋中国王走一步能够移动到相邻的8个方格中的任意一个,那么国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步?自己走走试试。 你会发现最少步数总是max( | x2-x1 | , | y2-y1 | ) 步 。

  有一种类似的一种距离度量方法叫切比雪夫距离。

(1)二维平面两点a(x1,y1)与b(x2,y2)间的切比雪夫距离
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第7张
(2)两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的切比雪夫距离
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第8张
  这个公式的另一种等价形式是
  常用相似性(距离)度量方法概述 (https://mushiming.com/)  第9张
扩展到多维空间,其实切比雪夫距离就是当p趋向于无穷大时的闵氏距离

2.4. 闵可夫斯基距离(Minkowski Distance)

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

也是欧氏距离的推广,是对多个距离度量公式的概括性的表述。

(1) 闵氏距离的定义

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

常用相似性(距离)度量方法概述 (https://mushiming.com/)  第10张
其中p是一个变参数。

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

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

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

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

(2) 闵氏距离的缺点

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

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

   简单说来,闵氏距离的缺点主要有两个:(1)将各个分量的量纲(scale),也就是“单位”当作相同的看待了。(2)没有考虑各个分量的分布(期望,方差等)可能是不同的。所以使用前需要考虑是否进行标准化 (非归一化)

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

标准化欧氏距离的定义

标准化欧氏距离是针对简单欧氏距离的缺点而作的一种改进方案。标准欧氏距离的思路:既然数据各维分量的分布不一样,好吧!那我先将各个分量都“标准 化”到均值、方差相等吧。均值和方差标准化到多少呢?假设样本集X的均值(mean)为m,标准差(standard deviation)为s,标准化变量的数学期望为0,方差为1。那么X的标准化过程(standardization)用公式描述就是:
  常用相似性(距离)度量方法概述 (https://mushiming.com/)  第11张
  标准化后的值 = ( 标准化前的值 - 分量的均值 ) / 分量的标准差

经过简单的推导就可以得到两个n维向量a(x11,x12,…,x1n)与 b(x21,x22,…,x2n)间的标准化欧氏距离的公式:
 常用相似性(距离)度量方法概述 (https://mushiming.com/)  第12张
  如果将方差的倒数看成是一个权重,这个公式可以看成是一种加权欧氏距离(Weighted Euclidean distance)。

2.6. 马氏距离(Mahalanobis Distance)

既然欧几里得距离无法忽略指标度量的差异,所以在使用欧氏距离之前需要对底层指标进行数据的标准化,而基于各指标维度进行标准化后再使用欧氏距离就衍生出来另外一个距离度量——马哈拉诺比斯距离(Mahalanobis Distance),简称马氏距离。与标准化欧氏距离不同的是它认为各个维度之间不是独立分布的,所以马氏距离考虑到各种特性之间的联系。。

(1)马氏距离定义
有M个样本向量X1~Xm,协方差矩阵记为S,均值记为向量μ,则其中样本向量X到u的马氏距离表示为:
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第13张
而其中向量Xi与Xj之间的马氏距离定义为:常用相似性(距离)度量方法概述 (https://mushiming.com/)  第14张
(2) 若协方差矩阵是单位矩阵(各个样本向量之间独立同分布,各个维度上的方差均为1),则公式就成了:
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第15张
 也就是欧氏距离了
 若协方差矩阵是对角矩阵(各个维度上的方差不一定为1),公式变成了标准化欧氏距离。即先对各维度上的距离标准化(除以方差)再计算欧氏距离

(3) 马氏距离的优缺点:

优点:马氏距离不受量纲的影响,两点之间的马氏距离与原始数据的测量单位无关;由标准化数据和中心化数据(即原始数据与均值之差)计算出的两点之间的马氏距离相同。马氏距离还可以排除变量之间的相关性的干扰。缺点:马氏距离的缺点夸大了变化微小的变量的作用。

(4) 注意事项

马氏距离的计算是建立在总体样本的基础上的,这一点可以从上述协方差矩阵的解释中得出,也就是说,如果拿同样的两个样本,放入两个不同的总体中,最后计算得出的两个样本间的马氏距离通常是不相同的,除非这两个总体的协方差矩阵碰巧相同;

在计算马氏距离过程中,要求总体样本数大于样本的维数;否则得到的总体样本协方差矩阵逆矩阵不存在,在此情况下,用欧式距离计算即可;Σ= D1 * D1’ (D1为m*n矩阵,m>n, m为特征维数,n为样本数) rank(Σ)<=n 故 Σ 不可逆。

还有一种情况,满足了条件总体样本数大于样本的维数,但是协方差矩阵的逆矩阵仍然不存在,比如三个样本点(3,4)、(5, 6)和(7,8),这种情况是因为这三个样本在其所处的二维空间平面内共线。这种情况下,也采用欧式距离计算。比如:均值向量为[5, 6], D1=[-2 0 2;-2 0 2], Σ显然不可逆

在实际应用中“总体样本数大于样本的维数”这个条件是很容易满足的,而所有样本点出现3)中所描述的情况是很少出现的,所以在绝大多数情况下,马氏距离是能够顺利计算的,但是马氏距离的计算是不稳定的,不稳定的来源是协方差矩阵,这也是马氏距离与欧式距离的最大差异之处。

最典型的就是根据距离作判别问题,即假设有n个总体,计算某个样品X归属于哪一类的问题。此时虽然样品X离某个总体的欧氏距离最近,但是未必归属它,比如该总体的方差很小,说明需要非常近才能归为该类。对于这种情况,马氏距离比欧氏距离更适合作判别。

2.7. 海林格距离 ( Hellinger Distance ) 和 巴氏距离(Bhattacharyya Distance)

(1) 海林格距离的定义

在概率论和统计理论中,Hellinger距离被用来度量两个概率分布的相似度。它是f散度的一种(f散度——度量两个概率分布相似度的指标)。Hellinger距离被定义成Hellinger积分的形式,这种形式由Ernst Hellinger在1909年引进。

对于两个离散概率分布 P=(p1,p2,…,pn)和 Q=(q1,q2,…,qn),它们的Hellinger距离可以定义如下:
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第16张

上式可以被看作两个离散概率分布平方根向量的欧式距离,如下所示:
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第17张
或者
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第18张

注意:

上公中系数2的平方根之一经常被省略,此时海林格距离的范围是0 ~ 2的平方根

海林格距离和巴氏系数BC(P, Q)的关系:

(2) 巴氏距离的定义

在统计中,Bhattacharyya距离测量两个离散或连续概率分布的相似性。它与衡量两个统计样品或种群之间的重叠量的Bhattacharyya系数密切相关。Bhattacharyya距离和Bhattacharyya系数以20世纪30年代曾在印度统计研究所工作的一个统计学家A. Bhattacharya命名。同时,Bhattacharyya系数可以被用来确定两个样本被认为相对接近的,它是用来测量中的类分类的可分离性。

在同一定义域X中,概率分布p和q的巴氏距离定义如下:其中(2)离散概率分布和(3)连续概率分布
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第19张

BC是巴氏系数(Bhattacharyya coefficient,因此,求得巴氏系数之后,就可以求得巴氏距离和Hellinger距离。

2.8. 汉明距离(Hamming distance)

(1) 汉明距离的定义

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

   应用:信息编码(为了增强容错性,应使得编码间的最小汉明距离尽可能大)、SimHash最后的计算结果

(2) 汉明重量: 它是一种特殊的汉明距离。指一个字符串与一个等长的“零”字符串 的汉明距离,即一个字符串中非零的字符个数
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第20张
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第21张

2.9. 编辑距离(Edit Distance/ Levenshtein Distance)

编辑距离/ 莱文斯坦距离的定义

  在信息论、语言学和计算机科学领域,Levenshtein Distance 是用来度量两个序列相似程度的指标。通俗地来讲,编辑距离指的是在两个单词之间,由其中一个单词w1

转换为另一个单词w2所需要的最少单字符编辑操作次数,操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。一般来说,编辑距离越小,两个串的相似度越大。俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念。编辑距离越小的两个字符串越相似,当编辑距离为0时,两字符串相等。

例如将kitten一字转成sitting,编辑距离是3:

sitten (k→s)

sittin (e→i)

sitting (→g)

3. 相似度度量

相似度度量(Similarity),即计算个体间的相似程度,与距离度量相反,相似度度量的值越小,说明个体间相似度越小,差异越大。

3.1. 余弦相似度/ 夹角余弦(Cosine Similarity)

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

假设两用户同时对两件商品评分,向量分别为(3,3)和(5,5),这两位用户对两件商品的喜好其实是一样的,余弦距离此时为1,欧式距离给出的解显然没有余弦值直观。

(1)在二维空间中向量A(x1,y1)与向量B(x2,y2)的夹角余弦公式:
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第22张

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

   类似的,对于两个n维样本点a(x11,x12,…,x1n)和b(x21,x22,…,x2n),可以使用类似于夹角余弦的概念来衡量它们间的相似程度。

常用相似性(距离)度量方法概述 (https://mushiming.com/)  第23张
即:
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第24张

   夹角余弦取值范围为[-1,1]。夹角余弦越大表示两个向量的夹角越小,夹角余弦越小表示两向量的夹角越大。当两个向量的方向重合时夹角余弦取最大值1,当两个向量的方向完全相反夹角余弦取最小值-1。

(3) 借助三维坐标系来看下欧氏距离和余弦相似度的区别:
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第25张

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

(4) 优点和缺点

优点:余弦距离根据向量方向来判断向量相似度,与向量各个维度的相对大小有关,不受各个维度直接数值影响。某种程度上,归一化后的欧氏距离和余弦相似性表征能力相同。

缺点:对数值大小不够敏感

(5) 适用范围

计算结果对用户数据绝对值不敏感,例如在描述用户的兴趣、喜好、或用于情感分析时。

用户数据中的评分值其实是用户主观的评分结果,换言之,每个用户的评价标准是不一致的,有一些对于“好的”界定标准更为苛刻,而另一些则对于“好”、“不好”的界定则更为宽容。这种情况下,用余弦相似度来计算用户之间的相似度或差异,可以弱化度量标准不统一这一因素。

3.2. 杰卡德相似系数(Jaccard similarity coefficient)

(1) 杰卡德相似系数

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

常用相似性(距离)度量方法概述 (https://mushiming.com/)  第26张
杰卡德相似系数是衡量两个集合的相似度一种指标。

(2) 杰卡德距离

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

常用相似性(距离)度量方法概述 (https://mushiming.com/)  第27张
杰卡德距离用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。

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

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

样本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的杰卡德距离表示为:
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第28张

3.3. Tanimoto 系数(Tanimoto Coefficient)/ (广义Jaccard相似系数)

常用相似性(距离)度量方法概述 (https://mushiming.com/)  第29张

原理:又名广义Jaccard系数,是对Jaccard系数的扩展,元素的取值可以是实数。又叫作谷本系数

范围:[0,1],完全重叠时为1,无重叠项时为0,越接近1说明越相似。

说明:处理无打分的偏好数据,也多用于计算文档数据的相似度。分母是大于等于 cos similarity的分母,但仅A,B长度一样时才相等。这就意味着,Tonimoto系数考虑了两个向量的长度差异,长度差异越大相似性越小。

关系:如果我们的x,y都是二值向量,那么Tanimoto系数就等同Jaccard距离。

应用场景:比较文本相似度,用于文本查重与去重;计算对象间距离,用于数据聚类等。

3.4. 相关系数 ( Correlation coefficient )或皮尔逊相关系数(Pearson Correlation Coefficient ) 与相关距离(Correlation distance)

(1) 相关系数的定义
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第30张

常用相似性(距离)度量方法概述 (https://mushiming.com/)  第31张
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第32张

(其中,E为数学期望或均值,D为方差,D开根号为标准差,E{ [X-E(X)] [Y-E(Y)]}称为随机变量X与Y的协方差,记为Cov(X,Y),即Cov(X,Y) = E{ [X-E(X)] [Y-E(Y)]},而两个变量之间的协方差和标准差的商则称为随机变量X与Y的相关系数,记为)

相关系数是衡量随机变量X与Y相关程度的一种方法,相关系数的取值范围是[-1,1]。相关系数的绝对值越大,则表明X与Y相关度越高。当X与Y线性相关时,相关系数取值为1(正线性相关)或-1(负线性相关)。

具体的,如果有两个变量:X、Y,最终计算出的相关系数的含义可以有如下理解:

当相关系数为0时,X和Y两变量无关系。

当X的值增大(减小),Y值增大(减小),两个变量为正相关,相关系数在0.00与1.00之间。

当X的值增大(减小),Y值减小(增大),两个变量为负相关,相关系数在-1.00与0.00之间。

说明:

不考虑重叠的数量;

如果只有一项重叠,无法计算相似性(计算过程被除数有n-1);

如果重叠的值都相等,也无法计算相似性(标准差为0,做除数)。

该相似度并不是最好的选择,也不是最坏的选择,只是因为其容易理解,在早期研究中经常被提起。使用Pearson线性相关系数必须假设数据是成对地从正态分布中取得的,并且数据至少在逻辑范畴内必须是等间距的数据。

皮尔逊相关系数是余弦相似度在维度值缺失情况下的一种改进

余弦相似度的问题是: 其计算严格要求"两个向量必须所有维度上都有数值", 比如:v1 = (1, 2, 4),v2=(3, -1, null),那么这两个向量由于v2中第三个维度有null, 无法进行计算.

然而, 实际我们做数据挖掘的过程中, 向量在某个维度的值常常是缺失的, 比如v2=(3, -1, null), v2数据采集或者保存中缺少一个维度的信息, 只有两个维度. 那么, 我们一个很朴素的想法就是, 我们在这个地方填充一个值, 不就满足了"两个向量必须所有维度上都有数值"的严格要求了吗? 填充值的时候, 我们一般这个向量已有数据的平均值, 所以v2填充后变成v2=(3, -1, 1), 接下来我们就可以计算cos<v1, v2>了.

而皮尔逊相关系数的思路是, 我把这些null的维度都填上0, 然后让所有其他维度减去这个向量各维度的平均值, 这样的操作叫作中心化. 中心化之后所有维度的平均值就是0了, 也满足进行余弦计算的要求,然后再进行我们的余弦计算得到结果. 这样先中心化再余弦计得到的相关系数叫作皮尔逊相关系数.

通常情况下通过以下取值范围判断变量的相关强度:

相关系数

相关程度

0.8-1.0

极强相关

0.6-0.8

强相关

0.4-0.6

中等程度相关

0.2-0.4

弱相关

0.0-0.2

极弱相关或无相关

(2) 相关距离的定义
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第33张

3.5. 调整余弦相似度(Adjusted Cosine Similarity)

常用相似性(距离)度量方法概述 (https://mushiming.com/)  第34张

在余弦相似度的介绍中说到:余弦相似度更多的是从方向上区分差异,而对绝对的数值不敏感。因此没法衡量每个维数值的差异,会导致这样一个情况:比如用户对内容评分,5分制,X和Y两个用户对两个内容的评分分别为(1,2)和(4,5),使用余弦相似度得出的结果是0.98,两者极为相似,但从评分上看X似乎不喜欢这两个内容,而Y比较喜欢,余弦相似度对数值的不敏感导致了结果的误差,需要修正这种不合理性,就出现了调整余弦相似度,即所有维度上的数值都减去一个均值,比如X和Y的评分均值都是3,那么调整后为(-2,-1)和(1,2),再用余弦相似度计算,得到-0.8,相似度为负值并且差异不小,但显然更加符合现实。

计算方法和皮尔逊方法类似,只是去中心化的方式不一样:

皮尔森区中心化的方式,减去的均值是 item的均值。

修正的余弦,减去的是这个user 的评分均值。

3.6. 信息熵(Information Entropy) 和条件熵(Conditional entropy)

(1) 信息熵是衡量分布的混乱程度或分散程度的一种度量。分布越分散(或者说分布越平均),信息熵就越大。分布越有序(或者说分布越集中),信息熵就越小。

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

常用相似性(距离)度量方法概述 (https://mushiming.com/)  第35张
参数的含义:

n:样本集X的分类数

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

   信息熵越大表明样本集S分类越分散,信息熵越小则表明样本集X分类越集中。。当S中n个分类出现的概率一样大时(都是1/n),信息熵取最大值log2(n)。当X只有一个分类时,信息熵取最小值0

(2) 条件熵 𝐻(𝑌|𝑋)H(Y|X) 表示在已知随机变量 𝑋的条件下随机变量 𝑌 的不确定性。条件熵 𝐻(𝑌|𝑋)H(Y|X) 定义为 𝑋 给定条件下 𝑌 的条件概率分布的熵对 𝑋 的数学期望:常用相似性(距离)度量方法概述 (https://mushiming.com/)  第36张

条件熵 𝐻(𝑌|𝑋)H(Y|X) 相当于联合熵 𝐻(𝑋,𝑌)H(X,Y) 减去单独的熵 𝐻(𝑋)H(X),即

𝐻(𝑌|𝑋)=𝐻(𝑋,𝑌)−𝐻(𝑋)H(Y|X)=H(X,Y)−H(X) ,证明如下:
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第37张

3.7. 相对熵(relative entropy)/KL散度Kullback-Leibler divergence和交叉熵 (Kullback-Leibler divergence)

(1) 相对熵/KL散度:又叫交叉熵,用来衡量两个取值为正数的函数(概率分布)的相似性,当两个随机分布相同时,它们的相对熵为零,当两个随机分布的差别增大时,它们的相对熵也会增大。所以相对熵可以用于比较两个分布的相似度。

设 p(x)、q(x) 是 离散随机变量 𝑋中取值的两个概率分布,则 p 对 q的相对熵是:常用相似性(距离)度量方法概述 (https://mushiming.com/)  第38张

性质:

1、如果 𝑝(𝑥)p(x) 和 𝑞(𝑥)q(x) 两个分布相同,那么相对熵等于0

2、𝐷𝐾𝐿(𝑝||𝑞)≠𝐷𝐾𝐿(𝑞||𝑝)DKL(p||q)≠DKL(q||p) ,相对熵具有不对称性。大家可以举个简单例子算一下。

3、𝐷𝐾𝐿(𝑝||𝑞)≥0DKL(p||q)≥0

总结:相对熵可以用来衡量两个概率分布之间的差异,上面公式的意义就是求 p 与 q 之间的对数差在 p 上的期望值。

(2) 交叉熵
常用相似性(距离)度量方法概述 (https://mushiming.com/)  第39张

https://www.cnblogs.com/kyrieng/p/8694705.html

(3) 总结

信息熵是衡量随机变量分布的混乱程度,是随机分布各事件发生的信息量的期望值,随机变量的取值个数越多,状态数也就越多,信息熵就越大,混乱程度就越大。当随机分布为均匀分布时,熵最大;信息熵推广到多维领域,则可得到联合信息熵;条件熵表示的是在 𝑋X 给定条件下,𝑌Y 的条件概率分布的熵对 𝑋X的期望。

相对熵可以用来衡量两个概率分布之间的差异。

交叉熵可以来衡量在给定的真实分布下,使用非真实分布所指定的策略消除系统的不确定性所需要付出的努力的大小。

信息熵是传输一个随机变量状态值所需的比特位下界(最短平均编码长度)。

相对熵是指用 q 来表示分布 p 额外需要的编码长度。

交叉熵是指用分布 q 来表示本来表示分布 p 的平均编码长度。

3.8. 对数似然相似度 (LogLikelihoodSimilarity)

反映的是用户之间喜欢物品的相关性,处理无打分的偏好数据,比Tanimoto系数的计算方法更为直观

假设有商品全集I={a,b,c,d,e,f},其中A用户偏好商品{a,b,c},B用户偏好商品{b,d},那么有如下矩阵:常用相似性(距离)度量方法概述 (https://mushiming.com/)  第40张

k11k11表示用户A和用户B的共同偏好的商品数量,显然只有商品b,因此值为1

k12k12表示用户A的特有偏好,即商品{a,c},因此值为2

k21k21表示用户B的特有偏好,即商品d,因此值为1

k22k22表示用户A、B的共同非偏好,有商品{e,f},值为2

行熵: rowEntropy = entropy(k11, k12) + entropy(k21, k22)列熵: columnEntropy = entropy(k11, k21) + entropy(k12, k22)矩阵熵: matrixEntropy = entropy(k11, k12, k21, k22)

用户间相似度: 2 * (matrixEntropy - rowEntropy - columnEntropy)

3.9. 互信息/ 信息增益 (Mutual Information)

互信息/信息增益:信息论中两个随机变量的相关性程度 常用相似性(距离)度量方法概述 (https://mushiming.com/)  第41张

3.10. 词对相似度 - 点间相似度PMI (Pointwise Mutual Information)

PMI(Pointwise Mutual Information),不是指经济上的那个PMI,而是点互信息,作用是衡量两个随机变量的相关性。可以用于情感分析中的情感分数计算,计算公式如下:常用相似性(距离)度量方法概述 (https://mushiming.com/)  第42张

基本思想是统计两个词语在文本中同时出现的概率,概率越大,其相关性就越紧密,关联度越高。

3.11. 信息检索 - 词频-逆文档频率(TF-IDF)

在网页查询(Query)中相关性以词频(TF)与逆文档频率(IDF)来度量查询词(key)和网页(page)的相关性;

网页中出现key越多,该page与查询结果越相关,可以使用TF值来量化

每个词的权重越高,也即一个词的信息量越大;比如“原子能”就比“应用”的预测能力强,可以使用IDF值来量化,这里的IDF就是一个特定条件下关键词的概率分布的交叉熵。 常用相似性(距离)度量方法概述 (https://mushiming.com/)  第43张

4. 如何选择?

如果数据存在“分数膨胀“问题( 有的人打分分布正常,有的人就比较极端),就使用皮尔逊相关系数

如果数据比较密集,变量之间基本都存在共有值,且这些距离数据都是非常重要的,那就使用欧几里得/ 曼哈顿距离/ 海林格距离。(空缺值处理:用0代替空缺值的方法可能会造成较大误差,“平均值”填充效果好于0值填充)

如果数据是稀疏的,就使用余弦相似度

调整余弦相似度和余弦相似度,皮尔逊相关系数在推荐系统中应用比较多;在基于项目的推荐中,已有论文证明,调整余弦相似度性能要优于后两者

5. 参考文献

https://www.cnblogs.com/soyo/p/6893551.html

http://blog.sina.com.cn/s/blog_62b83291010127bf.html

https://blog.csdn.net/weixin_43486780/article/details/104313350

https://blog.csdn.net/Kevin_cc98/article/details/73742037?utm_source=blogxgwz0

https://www.jianshu.com/p/7e3dbab7023c

https://www.cnblogs.com/arachis/p/Similarity.html

https://zhuanlan.zhihu.com/p/46626607

https://www.tuiedu.org/74.html

https://blog.csdn.net/lby503274708/article/details/88996795

https://blog.csdn.net/u014374284/article/details/49823557

https://en.wikipedia.org/wiki/Hellinger_distance

https://en.wikipedia.org/wiki/Bhattacharyya_distance

https://www.cnblogs.com/kyrieng/p/8694705.html
https://cloud.tencent.com/developer/article/1668762 比较清晰

THE END

发表回复