0

距离度量(similarity measure)汇总

距离度量的定义

假定有一些点组成的集合,我们称这个集合为空间。该空间下的距离测度(similarity measure)是一个函数d(x, y),以空间中的两个点作为参数,输出是一个实数值。该函数必须满足下列准则:

  1. d(x, y)≥0(距离非负);
  2. d(x, y)=0当且仅当x=y(只有点到自身的距离为0,其他距离均大于0);
  3. d(x, y) = d(y, x)(距离具有对称性);
  4. d(x, y) ≤ d(x, z) + d(z, y)(三角不等式)。

欧式距离

在n维欧氏空间中,每个点是一个n维实数向量。该空间中的传统距离测度,即我们常说的L2范式(L2-norm)定义如下:

d([{x_1},{x_2},...,{x_n}],[{y_1},{y_2},...,{y_n}]) = \sqrt {\sum\limits_{i = 1}^n {{{({x_i} - {y_i})}^2}} }

欧氏空间下还有一些其他的距离测度方法。对于任意常数如, Lr范式的定义如下:

d([{x_1},{x_2},...,{x_n}],[{y_1},{y_2},...,{y_n}]) = {\left( {\sum\limits_{i = 1}^n {{{\left| {{x_i} - {y_i}} \right|}^r}} } \right)^{1/r}}

当r=2是,就是刚才提到的L2范式距离。另一个常用的距离测度是L1范式距离或者称为曼哈顿距离。即两个点的距离是每维距离的绝对值之和。之所以称为“曼哈顿距离”,是因为这里在两个点之间行进时必须要沿着网格线前进,就如同沿着城市(如曼哈顿)的街道行进一样。

另一个有趣的距离测度是L范式,也就是当r趋向于无穷大时Lr范式的极限值。当r增大时,只有那个具有最大距离的维度才真正起作用,因此,正式来讲,L范式定义为在所有维度i下{\left| {{x_i} - {y_i}} \right|}中的最大值。

Jaccard距离

集合的Jaccard距离可以定义为d(x, y) = 1 - SIM(x, y),也就是说,Jaccard距离等于1减去x、y的交集与并集的比率。

余弦距离

在有维度的空间下余弦距离(cosine distance)才有意义,这些空间包括欧氏空间及离散欧氏空间,而后者包括坐标只采用整数值或布尔值(0或1)来表示的空间。在上述空间下,点可以代表方向。因此,两个点的余弦距离实际上是点所代表的向量之间的夹角。不管空间有多少维,该夹角的范围是0~180度。

首先计算夹角的余弦,然后应用反余弦函数将结果转化为0~180度之间的角度,从而最终得到余弦距离。给定向量x和y,其夹角余弦等于它们的内积x·y除以两个向量的L2范式(即它们到原点的欧氏距离)乘积。记得向量的内积为[{x_1},{x_2},...,{x_n}] \cdot [{y_1},{y_2},...,{y_n}]) = \sum\limits_{i = 1}^n {{x_i}{y_i}}

例如:两个向量分别为x=[1, 2, -1]及y=[2, 1, 1],则内积x·y = 1×2 + 2×1 + (-1)×1 = 3。两个向量的L2范式均为\sqrt 6 ,比如x的L2范式为\sqrt {{1^2}{\rm{ + }}{2^2}{\rm{ + ( - 1}}{{\rm{)}}^2}} = \sqrt 6 。因此,x和y的夹角余弦为3/(\sqrt 6 \cdot \sqrt 6 ) = 1/2,而余弦值为1/2的角大小为60度。因此,x和y的余弦距离为60度。

编辑距离

编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串字符串x=x1x2...xn及y=y1y2...ym之间,由一个转成另一个所需的最少编辑操作次数。编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。

例如:两个字符串x=abcde和y=acfdeg的编辑距离为3。为将x转换为y,需要进行如下操作:

  1. 删除字符b;
  2. 在字符c之后插入字符f;
  3. 在字符e之后插入字符g。

可以验证,不存在少于3步的插入/删除操作序列可能把x转换为y。因此,x和y的编辑距离d(x, y) = 3。

另一种定义和计算编辑距离d(x, y)的方法基于x和y的最长公共子序列(LCS)的计算。编辑距离等于x与y的长度之和减去它们的LCS长度的两倍。

例如:字符串x = abcde 和y = acfdeg存在一个唯一的LCS,即acde。注意x的长度为5,y的长度为6,LCS的长度为4。因此它们的编辑距离为5+6-2×4 = 3。

海明距离

给定一个向量空间,海明距离(Hamming distance)定义为两个向量中不同分量的个数。

例如:向量10101和11110的海明距离是3.很明显,这两个向量的第2、4、5位元素不同,而其他元素均相同。

Feixiang

发表评论

电子邮件地址不会被公开。 必填项已用*标注