相似性和距离算法种类汇总
评价个体的相似性和类别时,衡量个体差异的方法主要有【距离】和【相似度】两种:
假设我们要比较X个体和Y个体间的差异,它们都包含了N个维的特征, X=(x1, x2, x3, … xn) Y=(y1, y2, y3, … yn) 下面来看看主要可以用哪些方法来衡量两者的差异。
一、距离度量(6种)
1.欧几里得距离(Euclidean Distance)以及欧式距离的标准化(Standardized Euclidean distance) 2.明可夫斯基距离(Minkowski Distance) 3.曼哈顿距离(Manhattan Distance) 4.切比雪夫距离(Chebyshev Distance) 5.马哈拉诺比斯距离(Mahalanobis Distance) 6.海明距离(Hamming distance)
距离度量(Distance)用于衡量个体在空间上存在的距离,距离越远说明个体间的差异越大。
1、欧几里得距离(Euclidean Distance)
欧氏距离是最常见的距离度量,衡量的是多维空间中各个点之间的绝对距离。公式如下:
ps:因为计算是基于各维度特征的绝对数值,所以欧氏度量需要保证各维度指标在相同的刻度级别,比如对身高(cm)和体重(kg)两个单位不同的指标使用欧式距离可能使结果失效。
欧式距离的标准化(Standardized Euclidean distance)
标准欧氏距离的思路:现将各个维度的数据进行标准化:标准化后的值 = ( 标准化前的值 - 分量的均值 ) /分量的标准差,然后计算欧式距离:
2、明可夫斯基距离(Minkowski Distance)
明氏距离是欧氏距离的推广,是对多个距离度量公式的概括性的表述。公式如下:
当p==1,“明可夫斯基距离”变成“曼哈顿距离” 当p==2,“明可夫斯基距离”变成“欧几里得距离” 当p==∞,“明可夫斯基距离”变成“切比雪夫距离”
3、曼哈顿距离(Manhattan Distance)
曼哈顿距离来源于城市区块距离,是将多个维度上的距离进行求和后的结果,如下:
4、切比雪夫距离(Chebyshev Distance)
切比雪夫距离起源于国际象棋中国王的走法,我们知道国际象棋国王每次只能往周围的8格中走一步,那么如果要从棋盘中A格(x1, y1)走到B格(x2, y2)最少需要走几步?扩展到多维空间,其实切比雪夫距离就是当p趋向于无穷大时的明氏距离:
5、马哈拉诺比斯距离(Mahalanobis Distance)
既然欧几里得距离无法忽略指标度量的差异,所以在使用欧氏距离之前需要对底层指标进行数据的标准化,而基于各指标维度进行标准化后再使用欧氏距离就衍生出来另外一个距离度量——马哈拉诺比斯距离(Mahalanobis Distance),简称马氏距离。
6、海明距离(Hamming distance)
定义:在信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。 场景:在海量物品的相似度计算中可用simHash对物品压缩成字符串,然后使用海明距离计算物品间的距离
二、相似度度量(9种)
相似度度量(Similarity),即计算个体间的相似程度,与距离度量相反,相似度度量的值越小,说明个体间相似度越小,差异越大
1、余弦相似度(Cosine Similarity) 2、调整余弦相似度(Adjusted Cosine Similarity) 3、皮尔森相关系数(Pearson Correlation Coefficient) 4、Jaccard相似系数(Jaccard Coefficient) 5、Tanimoto系数(广义Jaccard相似系数) 6、对数似然相似率 7、互信息/信息增益,相对熵/KL散度 8、信息检索–词频-逆文档频率(TF-IDF) 9、词对相似度–点间互信息
1、余弦相似度(Cosine Similarity)
余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。相比距离度量,余弦相似度更加注重两个向量在方向上的差异,而非距离或长度上。公式如下:
2、调整余弦相似度(Adjusted Cosine Similarity)
虽然余弦相似度对个体间存在的偏见可以进行一定的修正,但是因为只能分辨个体在维之间的差异,没法衡量每个维数值的差异,会导致这样一个情况:
比如用户对内容评分,5分制,X和Y两个用户对两个内容的评分分别为(1,2)和(4,5),使用余弦相似度得出的结果是0.98,两者极为相似,但从评 分上看X似乎不喜欢这2个内容,而Y比较喜欢,余弦相似度对数值的不敏感导致了结果的误差;
需要修正这种不合理性,就出现了调整余弦相似度,即所有维度上的数值都减去一个均值,比如X和Y的评分均值都是3,那么调整后为(-2,-1)和(1,2),再用余弦相似度计算,得到-0.8,相似度为负值并且差异不小,但显然更加符合现实。
3、皮尔森相关系数(Pearson Correlation Coefficient)
即相关分析中的相关系数r,分别对X和Y基于自身总体标准化后计算空间向量的余弦夹角。公式如下:
定义:两个变量之间的皮尔逊相关系数定义为两个变量之间的协方差和标准差的商
4、Jaccard相似系数(Jaccard Coefficient)
Jaccard系数主要用于计算符号度量或布尔值度量的个体间的相似度,因为个体的特征属性都是由符号度量或者布尔值标识,因此无法衡量差异具体值的大小,只能获得“是否相同”这个结果,所以Jaccard系数只关心个体间共同具有的特征是否一致这个问题。如果比较X与Y的Jaccard相似系 数,只比较xn和yn中相同的个数,公式如下:
5、Tanimoto系数(广义Jaccard相似系数)
定义:广义Jaccard相似度,元素的取值可以是实数。又叫作谷本系数 关系:如果我们的x,y都是二值向量,那么Tanimoto系数就等同Jaccard距离。
6、对数似然相似率
7、互信息/信息增益,相对熵/KL散度
8、信息检索–词频-逆文档频率(TF-IDF)
9、词对相似度–点间互信息
三、距离度量与相似度度量的区别
欧氏距离是最常见的距离度量,而余弦相似度则是最常见的相似度度量,很多的距离度量和相似度度量都是基于这两者的变形和衍生,所以下面重点比较下两者在衡量个体差异时实现方式和应用环境上的区别。 借助三维坐标系来看下欧氏距离和余弦相似度的区别:
从图上可以看出距离度量衡量的是空间各点间的绝对距离,跟各个点所在的位置坐标(即个体特征维度的数值)直接相关;而余弦相似度衡量的是空间向 量的夹角,更加的是体现在方向上的差异,而不是位置。如果保持A点的位置不变,B点朝原方向远离坐标轴原点,那么这个时候余弦相似度cosθ是保持不变 的,因为夹角不变,而A、B两点的距离显然在发生改变,这就是欧氏距离和余弦相似度的不同之处。
适用场景
根据欧氏距离和余弦相似度各自的计算方式和衡量特征,分别适用于不同的数据分析模型:
欧氏距离能够体现个体数值特征的绝对差异,所以更多的用于需要从维度的数值大小中体现差异的分析,如使用用户行为指标分析用户价值的相似度或差异;
而余弦相似度更多的是从方向上区分差异,而对绝对的数值不敏感, 更多的用于使用用户对内容评分来区分用户兴趣的相似度和差异,同时修正了用户间可能存在的度量标准不统一的问题(因为余弦相似度对绝对数值不敏感)。
推荐阅读
-
Python 神经求解器解耦算法和瓦瑟斯坦距离量化评估-🎯 要点
-
几种相似性/距离(雅卡距离和余弦距离)及其 matlab 实现
-
文本相似性计算 - MinHash 和 LSH 算法
-
雅卡德距离和环算法的 Python 实现说明
-
相似性和距离算法种类汇总
-
知识图谱推理算法综述(上):基于距离和图传播的模型
-
[算法设计] 各种距离算法汇总
-
NeurIPS 2022 | 最强斗地主AI!网易互娱AI Lab提出基于完美信息蒸馏的方法-完美信息蒸馏(PTIE) 在斗地主游戏中,非完美信息的引入主要是由于三位玩家均不能看到别人的手牌,对于任意一位玩家而言,仅可知道其余两位玩家当前手牌的并集,而难于精准判断每位玩家当前手牌。完美信息蒸馏的思路是针对这种非完美问题,构建一个第三方角色,该角色可以看到三位玩家的手牌,该角色在不告知每位玩家完美信息的情况下通过信息蒸馏的方式引导玩家打出当前情况下合理的出牌。 以强化学习常用的 Actor-Critic 算法为例,PTIE 在 Actor-Critic 算法的应用中可以利用 Critic 的 Value 输出作为蒸馏手段来提升 Actor 的表现。具体而言即在训练中 Critic 的输入为完美信息(包含所有玩家的手牌信息),Actor 的输入为非完美信息(仅包含自己手牌信息),此种情况下 Critic 给予的 Value 值包含了完美信息,可以更好地帮助 Actor 学习到更好的策略。 从更新公式上来看,正常的 Actor-Critic 算法 Actor 更新的方式如下: 在 PTIE 模式下,对于每个非完美信息状态 h,我们可以在 Critic 中构建对应的完美信息状态 D(h),并用 Critic 的输出来更新 Actor 的策略梯度,从而达到完美信息蒸馏的效果。 PTIE 框架的整体结构如下图所示: 无论是训练还是执行过程中智能体都不会直接使用完美信息,在训练中通过蒸馏将完美信息用于提升策略,从而帮助智能体达到一个更高的强度。 PTIE 的另一种蒸馏方式是将完美信息奖励引入到奖励值函数的训练中,PerfectDou 提出了基于阵营设计的完美信息奖励 node reward,以引导智能体学习到斗地主游戏中的合作策略,其定义如下: 如上所示,完美信息部分 代表 t 时刻地主手牌最少几步可以出完,在斗地主游戏中可以近似理解为是距游戏获胜的距离, 代表 t 时刻地主阵营和农民阵营距游戏获胜的距离之差, 为调节系数。通过此种奖励设计,在训练时既可以一定程度地引入各玩家的手牌信息(出完的步数需要知道具体手牌才能计算),同时也鼓励农民以阵营的角度做出决策,提升农民的合作性。 特征构建: PerfectDou 针对牌类游戏的特点主要构建了两部分特征:牌局状态特征和动作特征。其中牌局状态特征主要包括当前玩家手牌牌型特征、当前玩家打出的卡牌牌型特征、玩家角色、玩家手牌数目等常用特征,动作特征主要用于刻画当前状态下玩家的所有可能出牌,包括了每种出牌动作的牌型特征、动作的卡牌数目、是否为最大动作等特征。 牌型特征为 12 * 15 的矩阵,如下图所示: 该矩阵前 4 行代表对应每种卡牌的张数,5-12 行代表该种卡牌的种类和对应位置。 网络结构和动作空间设计 针对斗地主游戏出牌组合数较多的问题,PerfectDou 基于 RLCard 的工作上对动作空间进行了简化,对占比最大的两个出牌牌型:飞机带翅膀和四带二进行了动作压缩,将整体动作空间由 27472 种缩减到 621 种。 PerfectDou 策略网络结构如下图所示: 策略网络结构同样分为两部分:状态特征部分和动作特征部分。 在状态特征部分,LSTM 网络用于提取玩家的历史行为特征,当前牌局状态特征和提取后的行为特征会再通过多层的 MLP 网络输出当前的状态信息 embedding。 在动作特征部分,每个可行动作同样会经过多层 MLP 网络进行编码,编码后的动作特征会与其对应的状态信息 embedding 经过一层 MLP 网络计算两者间的相似度,并经由 softmax 函数输出对应的动作概率。 实验结果
-
大数据量和海量数据处理算法汇总_MySQL
-
子空间相似性和距离主角的测量方法