全面归纳距离和相似度计算方法

2023-04-11 16:23:02JavaScript014

全面归纳距离和相似度计算方法,第1张

距离(distance，差异程度)、相似度(similarity，相似程度)方法可以看作是以某种的距离函数计算元素间的距离，这些方法作为机器学习的基础概念，广泛应用于如：Kmeans聚类、协同过滤推荐算法、相似度算法、MSE损失函数等等。本文对常用的距离计算方法进行归纳以及解析，分为以下几类展开：

对于点x=(x1,x2...xn) 与点y=(y1,y2...yn) , 闵氏距离可以用下式表示：

闵氏距离是对多个距离度量公式的概括性的表述，p=1退化为曼哈顿距离；p=2退化为欧氏距离；切比雪夫距离是闵氏距离取极限的形式。

曼哈顿距离公式：

欧几里得距离公式：

如下图蓝线的距离即是曼哈顿距离（想象你在曼哈顿要从一个十字路口开车到另外一个十字路口实际驾驶距离就是这个“曼哈顿距离”，此即曼哈顿距离名称的来源，也称为城市街区距离），红线为欧几里得距离：

切比雪夫距离起源于国际象棋中国王的走法，国际象棋中国王每次只能往周围的8格中走一步，那么如果要从棋盘中A格(x1,y1)走到B格(x2,y2)最少需要走几步？你会发现最少步数总是max(|x2-x1|,|y2-y1|)步。有一种类似的一种距离度量方法叫切比雪夫距离。

切比雪夫距离就是当p趋向于无穷大时的闵氏距离：

距离函数并不一定是距离度量，当距离函数要作为距离度量，需要满足：

由此可见，闵氏距离可以作为距离度量，而大部分的相似度并不能作为距离度量。

闵氏距离也是Lp范数（如p==2为常用L2范数正则化）的一般化定义。

下图给出了一个Lp球（ ||X||p = 1 ）的形状随着P的减少的可视化图：

距离度量随着空间的维度d的不断增加，计算量复杂也逐增，另外在高维空间下，在维度越高的情况下，任意样本之间的距离越趋于相等（样本间最大与最小欧氏距离之间的相对差距就趋近于0），也就是维度灾难的问题，如下式结论：

对于维度灾难的问题，常用的有PCA方法进行降维计算。

假设各样本有年龄，工资两个变量，计算欧氏距离（p=2）的时候，(年龄1-年龄2)² 的值要远小于(工资1-工资2)² ，这意味着在不使用特征缩放的情况下，距离会被工资变量（大的数值）主导, 特别当p越大，单一维度的差值对整体的影响就越大。因此，我们需要使用特征缩放来将全部的数值统一到一个量级上来解决此问题。基本的解决方法可以对数据进行“标准化”和“归一化”。

另外可以使用马氏距离（协方差距离），与欧式距离不同其考虑到各种特性之间的联系是（量纲）尺度无关 (Scale Invariant) 的，可以排除变量之间的相关性的干扰，缺点是夸大了变化微小的变量的作用。马氏距离定义为：

马氏距离原理是使用矩阵对两两向量进行投影后，再通过常规的欧几里得距离度量两对象间的距离。当协方差矩阵为单位矩阵，马氏距离就简化为欧氏距离；如果协方差矩阵为对角阵，其也可称为正规化的欧氏距离。

根据向量x,y的点积公式：

我们可以利用向量间夹角的cos值作为向量相似度[1]：

余弦相似度的取值范围为：-1~1，1 表示两者完全正相关，-1 表示两者完全负相关，0 表示两者之间独立。余弦相似度与向量的长度无关，只与向量的方向有关，但余弦相似度会受到向量平移的影响（上式如果将 x 平移到 x+1, 余弦值就会改变）。

另外，归一化后计算欧氏距离，等价于余弦值：两个向量x,y, 夹角为A，欧氏距离D=(x-y)^2 = x 2+y 2-2|x||y|cosA = 2-2cosA

协方差是衡量多维数据集中，变量之间相关性的统计量。如下公式X，Y的协方差即是，X减去其均值乘以 Y减去其均值，所得每一组数值的期望（平均值）。

如果两个变量之间的协方差为正值，则这两个变量之间存在正相关，若为负值，则为负相关。

皮尔逊相关系数数值范围也是[-1，1]。皮尔逊相关系数可看作是在余弦相似度或协方差基础上做了优化（变量的协方差除以标准差）。它消除每个分量标准不同（分数膨胀）的影响，具有平移不变性和尺度不变性。

卡方检验X2，主要是比较两个分类变量的关联性、独立性分析。如下公式，A代表实际频数；E代表期望频数：

Levenshtein 距离是编辑距离 (Editor Distance) 的一种，指两个字串之间，由一个转成另一个所需的最少编辑操作次数。允许的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

像hallo与hello两个字符串编辑距离就是1，我们通过替换”a“ 为 ”e“，就可以完成转换。

汉明距离为两个等长字符串对应位置的不同字符的个数，也就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如：1011101 与 1001001 之间的汉明距离是 2，“toned” 与 “roses” 之间的汉明距离是 3

另外的，对于字符串距离来说，不同字符所占的份量是不一样的。比如”我乐了“ 与【“我怒了”，”我乐了啊” 】的Levenshtein 距离都是1，但其实两者差异还是很大的，因为像“啊”这种语气词的重要性明显不如“乐”，考虑字符（特征）权重的相似度方法有：TF-IDF、BM25、WMD算法。

Jaccard 取值范围为0~1，0 表示两个集合没有重合，1 表示两个集合完全重合。

但Dice不满足距离函数的三角不等式，不是一个合适的距离度量。

基础地介绍下信息熵，用来衡量一个随机变量的不确定性程度。对于一个随机变量 X，其概率分布为：

互信息用于衡量两个变量之间的关联程度，衡量了知道这两个变量其中一个，对另一个不确定度减少的程度。公式为：

如下图，条件熵表示已知随机变量X的情况下，随机变量Y的信息熵，因此互信息实际上也代表了已知随机变量X的情况下，随机变量Y的(信息熵)不确定性的减少程度。

JS 散度解决了 KL 散度不对称的问题，定义为：

群体稳定性指标（Population Stability Index，PSI），可以看做是解决KL散度非对称性的一个对称性度量指标，用于度量分布之间的差异（常用于风控领域的评估模型预测的稳定性）。

psi与JS散度的形式是非常类似的，如下公式：

PSI的含义等同P与Q，Q与P之间的KL散度之和。

DTW 距离用于衡量两个序列之间的相似性，适用于不同长度、不同节奏的时间序列。DTW采用了动态规划DP（dynamic programming）的方法来进行时间规整的计算，通过自动warping扭曲时间序列（即在时间轴上进行局部的缩放），使得两个序列的形态尽可能的一致，得到最大可能的相似度。(具体可参考[5])

图结构间的相似度计算，有图同构、最大共同子图、图编辑距离、Graph Kernel 、图嵌入计算距离等方法（具体可参考[4][6]）。

度量学习的对象通常是样本特征向量的距离，度量学习的关键在于如何有效的度量样本间的距离，目的是通过训练和学习，减小或限制同类样本之间的距离，同时增大不同类别样本之间的距离，简单归类如下[2]：

最后，附上常用的距离和相似度度量方法[3]：

编辑距离（Minimum Edit Distance，MED），由俄罗斯科学家 Vladimir Levenshtein 在1965年提出，也因此而得名 Levenshtein Distance。

在信息论、语言学和计算机科学领域，Levenshtein Distance 是用来度量两个序列相似程度的指标。通俗地来讲，编辑距离指的是在两个单词之间，由其中一个单词转换为另一个单词所需要的最少 单字符编辑操作 次数。

在这里定义的单字符编辑操作有且仅有三种：

譬如，"kitten" 和 "sitting" 这两个单词，由 "kitten" 转换为 "sitting" 需要的最少单字符编辑操作有：

1.kitten → sitten (substitution of "s" for "k")

2.sitten → sittin (substitution of "i" for "e")

3.sittin → sitting (insertion of "g" at the end)

因此，"kitten" 和 "sitting" 这两个单词之间的编辑距离为 3 。

我们将两个字符串的 Levenshtein Distance 表示为，其中和分别对应的长度。那么，在这里两个字符串的 Levenshtein Distance，即可用如下的数学语言描述：