18种和“距离(distance)”、“相似度(similarity)”相关的量的小结
在计算机人工智能领域，距离(distance)、相似度(similarity)是经常出现的基本概念，它们在自然语言处理、计算机视觉等子领域有重要的应用，而这些概念又大多源于数学领域的度量(metric)、测度(measure)等概念。这里拮取其中18种做下小结备忘，也借此机会熟悉markdown的数学公式语法。
·
在计算机人工智能领域，距离(distance)、相似度(similarity)是经常出现的基本概念，它们在自然语言处理、计算机视觉等子领域有重要的应用，而这些概念又大多源于数学领域的度量(metric)、测度(measure)等概念。
这里拮取其中18种做下小结备忘，也借机熟悉markdown的数学公式语法。
| 英文名 | 中文名 | 算式 | 说明 |
|---|---|---|---|
| Euclidean Distance | 欧式距离 |
d=∑i=1n(xi−yi)2−−−−−−−−−−√
<script type="math/tex; mode=display" id="MathJax-Element-43">d=\sqrt{\sum_{i=1}^n(x_i-y_i)^2}</script> |
以古希腊数学家欧几里得命名的距离；也就是我们直观的两点之间直线最短的直线距离 |
| Manhattan Distance | 曼哈顿距离 |
d=∑i=1n|xi−yi|
<script type="math/tex; mode=display" id="MathJax-Element-44">d=\sum_{i=1}^n|x_i-y_i|</script> |
是由十九世纪的赫尔曼·闵可夫斯基所创词汇；是种使用在几何度量空间的几何学用语，用以标明两个点在标准坐标系上的绝对轴距总和；也就是和象棋中的“車”一样横平竖直的走过的距离；曼哈顿距离是超凸度量 |
| Minkowski Distance | 闵氏距离 |
d=∑i=1n(xi−yi)p−−−−−−−−−−√p
<script type="math/tex; mode=display" id="MathJax-Element-45">d=\sqrt[p]{\sum_{i=1}^n(x_i-y_i)^p}</script> |
以俄罗斯数学家闵可夫斯基命名的距离；是欧式距离的推广，p=2时等价于欧氏距离，和p-范数等值 |
| Hamming Distance | 海明距离 | 逐个字符(或逐位)对比，统计不一样的位数的个数总和 | 所得值越小，参与对比的两个元素约相似；下面是从wikipedia借的4bit的海明距离示意图 |
| Jaccard Coefficient | 杰卡德距离 |
J(A,B)=|A⋂B||A⋃B|
<script type="math/tex; mode=display" id="MathJax-Element-46">J(A,B)={|A \bigcap B|\over |A \bigcup B|}</script> |
越大越相似；分子是A和B的交集大小，分母是A和B的并集大小 |
| Ochiai Coefficient | ? |
K=n(A⋂B)n(A)×n(B)−−−−−−−−−−√
<script type="math/tex; mode=display" id="MathJax-Element-47">K={n(A \bigcap B)\over \sqrt{n(A) \times n(B)}}</script> |
|
| Pearson Correlation | 皮尔森相关系数 |
r=∑ni=1(Xi−x¯)(yi−y¯)∑ni=1(Xi−x¯)2−−−−−−−−−−−−√∑ni=1(yi−y¯)2−−−−−−−−−−−√
<script type="math/tex; mode=display" id="MathJax-Element-48">r={\sum_{i=1}^n(X_i-\overline x)(y_i-\overline y) \over \sqrt{\sum_{i=1}^n (X_i-\overline x)^2} \sqrt{\sum_{i=1}^n (y_i-\overline y)^2}}</script> |
分子是两个集合的交集大小，分母是两个集合大小的几何平均值。是余弦相似性的一种形式 |
| Cosine Similarity | 余弦相似度 |
S=x⋅y|x||y|
<script type="math/tex; mode=display" id="MathJax-Element-49">S={x \cdot y \over |x| |y|}</script> |
|
| Mahalanobis Distance | 马氏距离 |
d=(x⃗ −y⃗ )TS−1(x⃗ −y⃗ )−−−−−−−−−−−−−−−−√
<script type="math/tex; mode=display" id="MathJax-Element-50">d=\sqrt{(\vec x-\vec y)^TS^{-1}(\vec x-\vec y)}</script> 其中S是x和y的协方差矩阵 |
印度统计学家马哈拉诺比斯(P. C. Mahalanobis)提出的，表示数据的协方差距离。它是一种有效的计算两个未知样本集的相似度的方法；若协方差矩阵是对角阵(diagonal)，则该距离退化为欧式距离 |
| Kullback-Leibler Divergence | K-L散度 |
D(P||Q)=∑i=1nP(i)logP(i)Q(i)
<script type="math/tex; mode=display" id="MathJax-Element-51">D(P||Q)=\sum_{i=1}^nP(i)log{P(i) \over Q(i)}</script> |
即相对熵；是衡量两个分布(P、Q)之间的距离；越小越相似 |
| PMI(Pointwise Mutual Information) | 点对互信息 |
pmi=logp(x,y)p(x)p(y)=logp(y|x)p(y)
<script type="math/tex; mode=display" id="MathJax-Element-52">pmi=log{p(x,y) \over p(x)p(y)}=log{p(y|x) \over p(y)}</script> |
利用co-occurance来衡量x和y的相似度；越大越相关；可以看做局部点的互信息(mutual information) |
| NGD(Normalized Google Distance) | ? |
NGD(x,y)=max{logf(x),logf(y)}−logf(x,y)logM−min{logf(x),logf(y)}
<script type="math/tex; mode=display" id="MathJax-Element-53">NGD(x,y)={max\{log f(x), log f(y)\}-log f(x,y) \over logM-min\{log f(x), log f(y)\}}</script> |
这是google用来衡量两个不同的关键字(keyword)的检索结果之间的相关程度；其中f(x)代表包含了关键字x的页面数量，f(x,y)代表同时包含了关键字x和关键字y的页面的数量，M代表google所搜索的总页数；若两个关键字总是成对出现在页面上，那么NGD值为0，相反的，如果两个关键字在所有页面上都没有同时出现过，那么NGD值为无穷；该量是从normalized compression distance (Cilibrasi & Vitanyi 2003)衍生而来的 |
| Levenshtein Distance(Edit Distance) | Levenshtein距离(编辑距离) | f(n)=
⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪max(i,j)min⎧⎩⎨⎪⎪leva,b(i−1,j)+1leva,b(i,j−1)+1leva,b(i−1,j−1)+1(ai≠bj)if min(i,j)=0,otherwise.
<script type="math/tex; mode=display" id="MathJax-Element-54">\begin{cases}max(i,j) & \text{if min(i,j)=0}, \\ min{\begin{cases} lev_{a,b}(i-1,j)+1 \\ lev_{a,b}(i,j-1)+1 \\ lev_{a,b}(i-1,j-1)+1_{(a_i \neq b_j)} \end{cases}} & \text{otherwise.}\end{cases}</script> |
是指两个字串之间，由一个转成另一个所需的最少编辑操作次数；俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念；编辑距离越小的两个字符串越相似，当编辑距离为0时，两字符串相等 |
| Jaro-Winkler Distance | ? |
⎧⎩⎨⎪⎪⎪⎪013(m|s1|+m|s2|+m−tm)if m=0otherwise
<script type="math/tex; mode=display" id="MathJax-Element-55">\left\{ \begin{array}{l l} 0 & \text{if }m = 0\\ \frac{1}{3}\left(\frac{m}{|s_1|} + \frac{m}{|s_2|} + \frac{m-t}{m}\right) & \text{otherwise} \end{array} \right.</script> |
|
| Lee Distance | 李氏距离 |
d=∑i=1n|xi−yi|
<script type="math/tex; mode=display" id="MathJax-Element-56">d=\sum_{i=1}^n|x_i-y_i|</script> |
在编码理论(coding theory)中两个字符串间距离的一种度量方法 |
| Hellinger Distance | ? |
H2(P,Q)=12√∫(dPdλ−−−√−dQdλ−−−√)2dλ−−−−−−−−−−−−−−−−−−√
<script type="math/tex; mode=display" id="MathJax-Element-57">H^2(P,Q)={1 \over \sqrt{2}}\sqrt{\int(\sqrt{{dP \over d\lambda}}-\sqrt{dQ \over d\lambda})^2d\lambda}</script>当dP/dλ、dQ/dλ<script type="math/tex" id="MathJax-Element-58">dP/d\lambda、dQ/d\lambda</script>为概率密度函数时，进一步有 H2(P,Q)=1−∫f(x)g(x)−−−−−−−√dx−−−−−−−−−−−−−−−√<script type="math/tex" id="MathJax-Element-59">H^2(P,Q)=\sqrt{1-\int{\sqrt{f(x)g(x)}dx}}</script> |
注意在作为概率意义的计算时需在测度空间进行；通常被用来度量两个概率分布的相似度，它是f散度的一种；由Ernst Helligner在1909年引进 |
| Canberra Distance | 坎贝拉距离 |
d(p⃗ ,q⃗ )=∑i=1n|pi−qi||pi|+|qi|
<script type="math/tex; mode=display" id="MathJax-Element-60">d(\vec p,\vec q)=\sum_{i=1}^n{\frac{|p_i-q_i|}{|p_i|+|q_i|}}</script>where
p⃗ =(p1,p2,⋯,pn)
<script type="math/tex; mode=display" id="MathJax-Element-61">\vec p=(p_1,p_2,\cdots,p_n)</script> and
q⃗ =(q1,q2,⋯,qn)
<script type="math/tex; mode=display" id="MathJax-Element-62">\vec q=(q_1,q_2,\cdots,q_n)</script> |
|
| Chebyshev Distance | 切比雪夫距离 |
DChebyshev(p,q)=maxi(|pi−qi|)=limk→∞(∑i=1n|pi−qi|k)1/k
<script type="math/tex; mode=display" id="MathJax-Element-63">D_{Chebyshev}(p,q)=\max_{i}(|p_i-q_i|)=\lim_{k \to \infty}(\sum_{i=1}^n|p_i-q_i|^k)^{1/k}</script> |
切比雪夫距离是由一致范数(uniform norm)(或称为上确界范数)所衍生的度量，也是超凸度量 |
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
31
0- 0
已为社区贡献1条内容
所有评论(0)