常用的相似度计算方法

不同样本间相似度计算也可以认为是样本间距离的计算,本文主要总结几种常见的距离计算方法

闵可夫斯基距离(Minkowski)

\[\begin{align*} distance(X, Y) = (\sum_{i=1}^{m}|x_{i} - y_{i}|^{p})^{\frac{1}{p}} \\\\ where\ X = (x_{1}, ..., x_{m}), Y = (y_{1}, ..., y_{m}) \tag{1} \end{align*}\]

特别的当

  • \(p = 1\) 时称为曼哈顿距离
  • \(p = 2\) 时称为 欧式距离
  • \(p \rightarrow \infty\) 时称为切比雪夫距离

曼哈顿距离

\[distance(X, Y) = \sum_{i=1}^{m}|x_{i} - y_{i}| \tag{2}\]

曼哈顿距离又称街区距离,从起点到终点只能往东南西北四个方向走,不能斜着走

欧式距离

\[distance(X, Y) = (\sum_{i=1}^{m}|x_{i} - y_{i}|^{2})^{\frac{1}{2}} \tag{3}\]

曼哈顿距离 vs 欧式距离

其中红线代表曼哈顿距离,绿色代表欧氏距离,也就是直线距离,而蓝色和黄色代表等价的曼哈顿距离

余弦相似度 (cosine similarity)

\[\begin{align*} cos(\theta) &= \frac{\underset{a}{\rightarrow} \cdot \underset{b}{\rightarrow}}{\left \| \underset{a}{\rightarrow} \right \| \left \| \underset{b}{\rightarrow} \right \|} \\ &= \frac{\sum_{i=1}^{m} x_{i} y_{i}}{\sqrt{\sum_{i=1}^{m} x_{i}^{2}} \sqrt{\sum_{i=1}^{m} y_{i}^{2}}} \\ & where \underset{a}{\rightarrow} = (x_{1}, x_{1}, ..., x_{n}),\ \underset{b}{\rightarrow} = (y_{2}, y_{2}, ..., y_{n}) \end{align*} \tag{4}\]

由于文档常用VSM形式表示,可以把文档当作高维向量,因此文档之间的相似度一般可以用余弦相似度计算

欧式距离 vs 余弦相似度

皮尔逊相关系数

\[\begin{align*} \rho_{XY} & = \frac{cov(X, Y)}{\sigma_{X} \sigma_{Y}} \\ & = \frac{E[(X-E_{x})(Y-E_{Y})]}{\sigma_{X} \sigma_{Y}} \\ & = \frac{\sum_{i=1}^{m} (X_{i} - \mu_{X}) (Y_{i} - \mu_{Y})}{\sqrt{\sum_{i=1}^{m} (X_{i} - \mu_{X})^{2}} \sqrt{\sum_{i=1}^{m} (Y_{i} - \mu_{Y})^{2}}} \end{align*} \tag{5}\]

其中 \(cov(X, Y)\)\(X\)\(Y\) 的协方差, \(\sigma_{X}\)\(X\) 的标准差, \(\sigma_{Y}\)\(Y\) 的标准差

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

皮尔逊相关系数 vs 余弦相似度

对比一下 \((4)\) 式和 \((5)\) 可以发现,其实相关系数和余弦相似度的关系是平移关系,也可以认为余弦相似度是相关系数去均值化的结果

杰卡德相似系数 (Jaccard)

\[J(A, B) = \frac{|A\cap B|}{|A \cup B|} \tag{6}\]

两个集合A和B的交集元素在A,B的并集中所占的比例,称为两个集合的杰卡德相似系数, 杰卡德系数一般用于度量两个集合的相似度

相对熵 / KL距离

\[D_{KL}(p||q) = \sum_{x} p(x) log \frac{p(x)}{q(x)} \tag{7}\]

计算的是两个分布之间的距离,特别要注意KL距离是非对称的,也就是说 \(p\)\(q\) 互换位置得到的结果是不一致的,一般来说当 \(p\) \(q\) 是同分布时才能得到一样的结果

Refrence

[1] http://www.ehcoo.com/ManhattanDistance.html

[2] https://www.cnblogs.com/heaad/archive/2011/03/08/1977733.html

sean lee wechat
欢迎关注我的公众号!
感谢支持!