距离和相似度度量方法

imelee 2018-02-03

展开全文

http://blog.csdn.net/pipisorry/article/details/45651315

在机器学习和数据挖掘中，我们经常需要知道个体间差异的大小，进而评价个体的相似性和类别。最常见的是数据分析中的相关分析，数据挖掘中的分类和聚类算法，如 K 最近邻（KNN）和 K 均值（K-Means）等等。

不同距离度量的应用场景

根据数据特性的不同，可以采用不同的度量方法。which one to use depends on what type of data we have and what our notion of similar is.

各种“距离”的应用场景简单概括为，空间：欧氏距离，路径：曼哈顿距离，国际象棋国王：切比雪夫距离，以上三种的统一形式:闵可夫斯基距离，加权：标准化欧氏距离，排除量纲和依存：马氏距离，向量差距：夹角余弦，编码差别：汉明距离，集合近似度：杰卡德类似系数与距离，相关：相关系数与相关距离。

距离度量公理Axioms of Distance Measures

一般而言，定义一个距离函数 d(x,y), 需要满足下面几个准则：(即距离度量需要满足的性质)

1) d(x,y) = 0 iff x = y // 到自己的距离为0
2) d(x,y) >= 0 // 距离非负
3) d(x,y) = d(y,x) // 对称性: 如果 A 到 B 距离是 a，那么 B 到 A 的距离也应该是 a
4) d(x,k)+ d(k,y) >= d(x,y) // 三角形法则triangle inequality: (两边之和大于第三边)

Note: iff = if and only if

基础知识：熵与互信息

[熵与互信息 ]

文本相似度量方法一览

此处的“文本”一词涵盖以下两个对象:

字符串/序列
包含较多文本内容的文档

相关的度量方法可以分为两大类，各类下面再有一些具体的分类，比较常用的方法如见下图

Note: lz这里LCS也可以认为就是编辑距离吧。

总的来说，文本相似度量方法可以分为两大类:

String Based，即基于待比较的文本本身中的信息，该类方法评估的是”词法“上的相似性，或说朴素的相似性
Corpus Based，即基于一个较大的文本集合中的信息，该类方法评估的是“语义”上的相似性

[文本相似度量方法(1): 概览]

皮皮blog

欧氏距离度量

欧拉距离，来自于欧式几何，在数学上也可以成为范数。

范数Norm

Lr范数就是x,y每个维度差距上取r次方加和后再开r次方根。Lr norm: what you get by taking the rth power of the differences, summing and taking the rth root.

给定向量x=（x1，x2，...xn）

L1范数：向量各个元素绝对值之和，Manhattan distance。

$= /sum_{i=1}^n /left| x_i - y_i /right|$

L2范数：向量各个元素的平方求和然后求平方根，也叫欧式范数、欧氏距离。

$= /left( /sum_{i=1}^n /left| x_i - y_i /right|^2 /right)^{1/2}$

Lp范数：向量各个元素绝对值的p次方求和然后求1/p次方。

$= /left( /sum_{i=1}^n /left| x_i - y_i /right|^p /right)^{1/p}$

L∞范数：向量各个元素求绝对值，最大那个元素的绝对值。也就是x，y在任意维度上差距最大的那个值。

$= /lim_{p /to /infty} /left( /sum_{i=1}^n /left| x_i - y_i /right|^p /right)^{1/p}$ = /max /left(|x_1 - y_1|, |x_2 - y_2|, /ldots, |x_n - y_n| /right).

小示例

Euclidean distance Vs. Non-Euclidean distance 欧氏距离对比非欧氏距离

dense: 给定两个点，它们的均值也是这个空间的一个点。And there is no reasonable notion of the average of points in the space.欧氏距离可以计算average，但是非欧氏距离却不一定。

皮皮blog

非欧氏距离度量

Jaccard Similarity

一般用于两个一元unary向量(buy or not, click or not)相似性的度量，或者用于集合sets相似性形式定义。

Note: Jaccard distance = 1 - Jaccard similarity

J(A,B) = {{|A /cap B|}/over{|A /cup B|}}.

分子是集合交集，分母是集合并集。即两个集合间的Jaccard similarity就是它们交集的大小除以它们并集的大小。

Jaccard相似度没有考虑评分的大小。

Dice's Coefficient

$s = /frac{2 | X /cap Y |}{| X | + | Y |}$

Dice 系数和 Jaccard 相似性起初被用于生态学上，作为一种判断物种间相似性的方法。在生态学上，要比较两个物种间相似程度时，通常会对该物种的特性进行采样，最后得到各自的特性集合，而 Dice 系数和 Jaccard 相似性都是通过比较两者之间的共有特性占比来度量相似性的，因此这两种方法都不是很关心每个 "Term" 的具体量，只是关心有没有某个 "Term"。

Cosine余弦相似度/向量内积

适合高维度向量vectors的相似度计算。

1. 两个向量间的余弦值可以很容易地通过使用欧几里得点积和量级公式推导 $\mathbf{a}\cdot\mathbf{b}=\left\|\mathbf{a}\right\|\left\|\mathbf{b}\right\|\cos\theta$

鉴于两个向量的属性， A 和B的余弦相似性θ用一个点积形式来表示其大小，如下所示：

$\text{similarity} = \cos(\theta) = {A \cdot B \over \|A\| \|B\|} = \frac{ \sum\limits_{i=1}^{n}{A_i \times B_i} }{ \sqrt{\sum\limits_{i=1}^{n}{(A_i)^2}} \times \sqrt{\sum\limits_{i=1}^{n}{(B_i)^2}} }$

也就是说两个向量的cosin距离就是这两个向量之间的夹角。

Note: if you project P1 onto P2,the length of the projection is the dot product, divided by the length of P2.Then the cosine of the angle between them is the ratio of adjacent(the dot product divided by P2) over hypotenuse(斜边, the length of P1).

产生的相似性范围从-1到1：-1意味着两个向量指向的方向正好截然相反，1表示它们的指向是完全相同的，0通常表示它们之间是独立的，而在这之间的值则表示中度的相似性或相异性。

对于文本匹配，属性向量A 和B 通常是文档中的词频向量。余弦相似性，可以被看作是一个规范比较文件长度的方法。在信息检索的情况下，由于一个词的频率（TF-IDF权）不能为负数，所以这两个文档的余弦相似性范围从0到1。并且，两个词的频率向量之间的角度不能大于90°。

[余弦相似性]

2. 向量内积是线性代数里最为常见的计算，实际上它还是一种有效并且直观的相似性测量手段。向量内积的定义如下：

直观的解释是：如果 x 高的地方 y 也比较高， x 低的地方 y 也比较低，那么整体的内积是偏大的，也就是说 x 和 y 是相似的。举个例子，在一段长的序列信号 A 中寻找哪一段与短序列信号 a 最匹配，只需要将 a 从 A 信号开头逐个向后平移，每次平移做一次内积，内积最大的相似度最大。信号处理中 DFT 和 DCT 也是基于这种内积运算计算出不同频域内的信号组分（DFT 和 DCT 是正交标准基，也可以看做投影）。向量和信号都是离散值，如果是连续的函数值，比如求区间[-1, 1] 两个函数之间的相似度，同样也可以得到（系数）组分，这种方法可以应用于多项式逼近连续函数，也可以用到连续函数逼近离散样本点（最小二乘问题，OLS coefficients）中，扯得有点远了- -!。

向量内积的结果是没有界限的，一种解决办法是除以长度之后再求内积，这就是应用十分广泛的余弦相似度（Cosine similarity）：

余弦相似度与向量的幅值无关，只与向量的方向相关，在文档相似度（TF-IDF）和图片相似性（histogram）计算上都有它的身影。

cosine similarity的一个扩展是

Tonimoto系数

$T(A,B) = {A /cdot B /over /|A/|^2 +/|B/|^2 - A /cdot B}.$

其实也没什么大不了。T（A,B）的分母是大于等于 cos similarity的分母，但且仅仅但 A,B长度一样是才相等。这就意味着，Tonimoto系数考虑了两个向量的长度差异，长度差异越大相似性约小。

另外需要注意一点的是，余弦相似度受到向量的平移影响，上式如果将 x 平移到 x+1, 余弦值就会改变。怎样才能实现平移不变性？

皮尔逊相关系数（Pearson correlation）

{也叫Centered Cosine，有时候也直接叫相关系数}

{数值型数据的相关性分析Correlation Analysis (Numerical Data)，从下面这个公式看出，它其实就是将数据归一化（数据减去其对应均值）后进行cosine相似度计算，所以叫centered cosine}

另一种表示方式

皮尔逊相关系数具有平移不变性和尺度不变性，计算出了两个向量（维度）的相关性。不过，一般我们在谈论相关系数的时候，将 x 与 y 对应位置的两个数值看作一个样本点，皮尔逊系数用来表示这些样本点分布的相关性。

皮尔逊相关系数的适用范围

当两个变量的标准差都不为零时，相关系数才有定义，皮尔逊相关系数适用于：

两个变量之间是线性关系，都是连续数据。
两个变量的总体是正态分布，或接近正态的单峰分布。
两个变量的观测值是成对的，每对观测值之间相互独立。

如何理解皮尔逊相关系数

rubyist：皮尔逊相关系数理解有两个角度

其一, 按照高中数学水平来理解, 它很简单, 可以看做将两组数据首先做Z分数处理之后, 然后两组数据的乘积和除以样本数，Z分数一般代表正态分布中, 数据偏离中心点的距离.等于变量减掉平均数再除以标准差.(就是高考的标准分类似的处理)

样本标准差则等于变量减掉平均数的平方和，再除以样本数，最后再开方，也就是说，方差开方即为标准差，样本标准差计算公式为：

所以, 根据这个最朴素的理解,我们可以将公式依次精简为:

其二, 按照大学的线性数学水平来理解, 它比较复杂一点,可以看做是两组数据的向量夹角的余弦。下面是关于此皮尔逊系数的几何学的解释，先来看一幅图，如下所示：

回归直线： y=gx(x) [红色] 和 x=gy(y) [蓝色]

如上图，对于没有中心化的数据, 相关系数与两条可能的回归线y=gx(x) 和 x=gy(y) 夹角的余弦值一致。
对于没有中心化的数据 (也就是说, 数据移动一个样本平均值以使其均值为0), 相关系数也可以被视作由两个随机变量向量夹角的余弦值（见下方）。
举个例子，例如，有5个国家的国民生产总值分别为 10, 20, 30, 50 和 80 亿美元。假设这5个国家 (顺序相同) 的贫困百分比分别为 11%, 12%, 13%, 15%, and 18% 。令 x 和 y 分别为包含上述5个数据的向量: x = (1, 2, 3, 5, 8) 和 y = (0.11, 0.12, 0.13, 0.15, 0.18)。
利用通常的方法计算两个向量之间的夹角 (参见数量积), 未中心化的相关系数是:

我们发现以上的数据特意选定为完全相关: y = 0.10 + 0.01 x。于是，皮尔逊相关系数应该等于1。将数据中心化 (通过E(x) = 3.8移动 x 和通过 E(y) = 0.138 移动 y ) 得到 x = (−2.8, −1.8, −0.8, 1.2, 4.2) 和 y = (−0.028, −0.018, −0.008, 0.012, 0.042), 从中
(4)皮尔逊相关的约束条件
从以上解释, 也可以理解皮尔逊相关的约束条件:
1 两个变量间有线性关系
2 变量是连续变量
3 变量均符合正态分布,且二元分布也符合正态分布
4 两变量独立
在实践统计中,一般只输出两个系数,一个是相关系数,也就是计算出来的相关系数大小,在-1到1之间;另一个是独立样本检验系数,用来检验样本一致性。

Note: lz文本很短，关键词很少的时候，余弦距离就很难计算出准确的相似度。这时候可以使用主题模型。

皮皮blog

汉明距离-分类数据点间的距离

汉明距离（Hamming distance）是指，两个等长字符串(一般适用于bit vectors)s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。

举个维基百科上的例子：

还可以用简单的匹配系数来表示两点之间的相似度——匹配字符数/总字符数。

在一些情况下，某些特定的值相等并不能代表什么。举个例子，用 1 表示用户看过该电影，用 0 表示用户没有看过，那么用户看电影的的信息就可用 0,1 表示成一个序列。考虑到电影基数非常庞大，用户看过的电影只占其中非常小的一部分，如果两个用户都没有看过某一部电影（两个都是 0），并不能说明两者相似。反而言之，如果两个用户都看过某一部电影（序列中都是 1），则说明用户有很大的相似度。在这个例子中，序列中等于 1 所占的权重应该远远大于 0 的权重，这就引出下面要说的杰卡德相似系数（Jaccard similarity）。

在上面的例子中，用 M11 表示两个用户都看过的电影数目，M10 表示用户 A 看过，用户 B 没看过的电影数目，M01 表示用户 A 没看过，用户 B 看过的电影数目，M00 表示两个用户都没有看过的电影数目。Jaccard 相似性系数可以表示为：

Jaccard similarity 还可以用集合的公式来表达，这里就不多说了。

如果分类数值点是用树形结构来表示的，它们的相似性可以用相同路径的长度来表示，比如，“/product/spot/ballgame/basketball” 离“product/spot/ballgame/soccer/shoes” 的距离小于到 "/product/luxury/handbags" 的距离，以为前者相同父节点路径更长。

编辑距离Edit distance-序列之间的距离

[编辑距离Edit distance]

皮皮blog

kl散度/相对熵/kl距离

1. 相对熵（relative entropy）又称为KL散度（Kullback–Leibler divergence，简称KLD），信息散度（information divergence），信息增益（information gain）。

KL散度是两个概率分布P和Q差别的非对称性的度量（designed to measure the difference between probability distributions）。 KL散度是用来度量使用基于Q的编码来编码来自P的样本平均所需的额外的位元数。典型情况下，P表示数据的真实分布，Q表示数据的理论分布，模型分布，或P的近似分布。

定义

对于离散随机变量，其概率分布P 和Q的KL散度可按下式定义为

$D_{\mathrm{KL}}(P\|Q) = \sum_i P(i) \ln \frac{P(i)}{Q(i)}. \!$

即按概率P求得的P和Q的对数差的平均值。KL散度仅当概率P和Q各自总和均为1，且对于任何i皆满足 Q(i)>0 及 P(i)>0 时，才有定义。式中出现 $0 \ln 0$ 的情况，其值按0处理。

特性

1. 相对熵的值为非负数

$D_{\mathrm{KL}}(P\|Q) \geq 0, \,$

由吉布斯不等式（en:Gibbs' inequality）可知，当且仅当P = Q时DKL(P||Q)为0

2. 尽管从直觉上KL散度是个度量或距离函数, 但是它实际上并不是一个真正的度量或距离。因为KL散度不具有对称性：从分布P到Q的距离（或度量）通常并不等于从Q到P的距离（或度量）。

$D_{\mathrm{KL}}(P\|Q) \neq D_{\mathrm{KL}}(Q\|P)$

L散度是不对称的，当然，如果希望把它变对称，

Ds(p1, p2) = [D(p1, p2) + D(p2, p1)] / 2

[KL散度]

[相对熵]

2. 概率分布之间的距离

实际上两个概率分布之间的距离是可以测量的。在统计学里面经常需要测量两组样本分布之间的距离，进而判断出它们是否出自同一个 population，常见的方法有卡方检验（Chi-Square）和 KL 散度（ KL-Divergence），下面说一说 KL 散度吧。

先了解一下前面的基础知识[信息熵-信息熵的来源]，而KL 散度又叫相对熵（relative entropy）。了解机器学习的童鞋应该都知道，在 Softmax 回归（或者 Logistic 回归），最后的输出节点上的值表示这个样本分到该类的概率，这就是一个概率分布。对于一个带有标签的样本，我们期望的概率分布是：分到标签类的概率是 1，其他类概率是 0。但是理想很丰满，现实很骨感，我们不可能得到完美的概率输出，能做的就是尽量减小总样本的 KL 散度之和（目标函数）。这就是 Softmax 回归或者 Logistic 回归中 Cost function 的优化过程啦。（PS：因为概率和为 1，一般的 logistic 二分类的图只画了一个输出节点，隐藏了另外一个）

[KL散度(Kullback-Leibler_divergence)]

kl散度的python+scipy实现

{计算topic_word分布矩阵所有topic_word分布两两之间的相似度-kl散度}

# 方法1（pdist只能计算对称kl散度）
topic_similar_mat = spatial.distance.pdist(tw_dist_ndaray,
                                           metric=lambda P, Q: ((sum(kl_div(P, Q)) + sum(kl_div(Q, P))) / 2))

def kl(P, Q):
    '''
    计算两个ndarray的kl散度
    KL散度仅当概率P和Q各自总和均为1，且对于任何i皆满足Q(i)>0及P(i)>0时，才有定义
    '''
    return sum(P * log(P / Q)) if (P > 0).all() and (Q > 0).all() else None
    # return sum(where((P > 0).all() and (Q > 0).all(), P * log(P / Q), None), axis=0)

#方法2（对称kl散度，自定义kl函数）
topic_similar_mat = spatial.distance.pdist(tw_dist_ndaray,
                                               metric=lambda P, Q: ((kl(P, Q) + kl(Q, P)) / 2))

Note: kl散度可以通过scipy包的stats.entropy计算[Scipy教程 - 统计函数库scipy.stats ]

# 方法3（非对称kl散度）
topic_similar_mat = zeros([len(tw_dist_ndaray), len(tw_dist_ndaray)])
for i_id, i in enumerate(tw_dist_ndaray):
    for j_id, j in enumerate(tw_dist_ndaray):
        if i_id != j_id:
            topic_similar_mat[i_id, j_id] = stats.entropy(tw_dist_ndaray[i_id], tw_dist_ndaray[j_id])

            topic_similar_mat[i_id, j_id] = sum(kl_div(tw_dist_ndaray[i_id], tw_dist_ndaray[j_id]))

Note：

1. 计算出的结果自己和自己的kl散度为0，为了排序计算与别人的相似度应该将对角线中的元素改为max

topic_similar_mat = spatial.distance.squareform(topic_similar_mat)
max_dist = topic_similar_mat.max()
for i in range(len(topic_similar_mat)):
    topic_similar_mat[i, i] = max_dist+1
print(topic_similar_mat)

2. 非对称kl散度不是对称的，而用pdist计算出的topic_similar_mat一定是对称的，因为pdist只计算上三角，所以使用pdist必须要用对称的kl散度

[Computation of Kullback-Leibler (KL) distance between text-documents using numpy]

[http://docs./doc/scipy-dev/reference/generated/scipy.stats.entropy.html]

闵可夫斯基距离

闵可夫斯基距离（Minkowski distance）是衡量数值点之间距离的一种非常常见的方法，假设数值点 P 和 Q 坐标如下：

那么，闵可夫斯基距离定义为：

该距离最常用的 p 是 2 和 1, 前者是欧几里得距离（Euclidean distance），后者是曼哈顿距离（Manhattan distance）。假设在曼哈顿街区乘坐出租车从 P 点到 Q 点，白色表示高楼大厦，灰色表示街道：

绿色的斜线表示欧几里得距离，在现实中是不可能的。其他三条折线表示了曼哈顿距离，这三条折线的长度是相等的。

当 p 趋近于无穷大时，闵可夫斯基距离转化成切比雪夫距离（Chebyshev distance）：

我们知道平面上到原点欧几里得距离（p = 2）为 1 的点所组成的形状是一个圆，当 p 取其他数值的时候呢？

注意，当 p < 1 时，闵可夫斯基距离不再符合三角形法则，举个例子：当 p < 1, (0,0) 到 (1,1) 的距离等于 (1+1)^{1/p} > 2, 而 (0,1) 到这两个点的距离都是 1。

闵可夫斯基距离比较直观，但是它与数据的分布无关，具有一定的局限性，如果 x 方向的幅值远远大于 y 方向的值，这个距离公式就会过度放大 x 维度的作用。所以，在计算距离之前，我们可能还需要对数据进行 z-transform 处理，即减去均值，除以标准差：

: 该维度上的均值
: 该维度上的标准差

可以看到，上述处理开始体现数据的统计特性了。这种方法在假设数据各个维度不相关的情况下利用数据分布的特性计算出不同的距离。如果维度相互之间数据相关（例如：身高较高的信息很有可能会带来体重较重的信息，因为两者是有关联的），这时候就要用到马氏距离（Mahalanobis distance）了。

马氏距离

马氏距离实际上是利用 Cholesky transformation 来消除不同维度之间的相关性和尺度不同的性质。马氏距离的变换和 PCA 分解的白化处理颇有异曲同工之妙，不同之处在于：就二维来看，PCA 是将数据主成分旋转到 x 轴（正交矩阵的酉变换），再在尺度上缩放（对角矩阵），实现尺度相同。而马氏距离的 L逆矩阵是一个下三角，先在 x 和 y 方向进行缩放，再在 y 方向进行错切（想象矩形变平行四边形），总体来说是一个没有旋转的仿射变换。

考虑下面这张图，椭圆表示等高线，从欧几里得的距离来算，绿黑距离大于红黑距离，但是从马氏距离，结果恰好相反：

假设样本点（列向量）之间的协方差对称矩阵是，通过 Cholesky Decomposition（实际上是对称矩阵 LU 分解的一种特殊形式，可参考博客）可以转化为下三角矩阵和上三角矩阵的乘积：。消除不同维度之间的相关性和尺度不同，只需要对样本点 x 做如下处理：。处理之后的欧几里得距离就是原样本的马氏距离（为了书写方便，这里求马氏距离的平方）：

Note: 这个也正是多维高斯分布的指数项的二次型，即高斯对于x的依赖的二次型表达。当

为单位矩阵时，马氏距离就变成了欧氏距离。

下图蓝色表示原样本点的分布，两颗红星坐标分别是（3, 3），（2, -2）:

由于 x， y 方向的尺度不同，不能单纯用欧几里得的方法测量它们到原点的距离。并且，由于 x 和 y 是相关的（大致可以看出斜向右上），也不能简单地在 x 和 y 方向上分别减去均值，除以标准差。最恰当的方法是对原始数据进行 Cholesky 变换，即求马氏距离（可以看到，右边的红星离原点较近）：

将上面两个图的绘制代码和求马氏距离的代码贴在这里，以备以后查阅：

[python] view plain copy

print?

import numpy as np
import pylab as pl
import scipy.spatial.distance as dist
def plotSamples(x, y, z=None):
stars = np.matrix([[3., -2., 0.], [3., 2., 0.]])
if z is not None:
x, y = z * np.matrix([x, y])
stars = z * stars
pl.scatter(x, y, s=10) # 画 gaussian 随机点
pl.scatter(np.array(stars[0]), np.array(stars[1]), s=200, marker='*', color='r') # 画三个指定点
pl.axhline(linewidth=2, color='g') # 画 x 轴
pl.axvline(linewidth=2, color='g') # 画 y 轴
pl.axis('equal')
pl.axis([-5, 5, -5, 5])
pl.show()
# 产生高斯分布的随机点
mean = [0, 0] # 平均值
cov = [[2, 1], [1, 2]] # 协方差
x, y = np.random.multivariate_normal(mean, cov, 1000).T
plotSamples(x, y)
covMat = np.matrix(np.cov(x, y)) # 求 x 与 y 的协方差矩阵
Z = np.linalg.cholesky(covMat).I # 仿射矩阵
plotSamples(x, y, Z)
# 求马氏距离
print '\n到原点的马氏距离分别是：'
print dist.mahalanobis([0,0], [3,3], covMat.I), dist.mahalanobis([0,0], [-2,2], covMat.I)
# 求变换后的欧几里得距离
dots = (Z * np.matrix([[3, -2, 0], [3, 2, 0]])).T
print '\n变换后到原点的欧几里得距离分别是：'
print dist.minkowski([0, 0], np.array(dots[0]), 2), dist.minkowski([0, 0], np.array(dots[1]), 2)

皮皮blog

其它距离度量方法

卡方检验[概率论：假设检验-t检验、卡方检验和AD-Fuller test ]

mutual information

Spearman's rank coefficient

Earth Mover's Distance

SimRank 相似：SimRank 迭代算法

SimRank来自图论，说两个变量相似，因为他们链接了同一个或相似的节点。

[漫谈：机器学习中距离和相似性度量方法]

大规模相似度计算方法

[大规模数据相似度计算时，解决数据倾斜的问题的思路之一（分块思想）]

皮皮blog

非欧氏距离及其满足公理性质的证明

Jaccard Dist

Note: Proof中使用反证法：两个都不成立，即都相等时，minhash(x)=minhash(y)了。

Cosine Dist余弦距离

Note: vectors here are really directions, not magnitudes.So two vectors with the same direction and different magnitudes are really the same vector.Even to vector and its negation, the reverse of the vector,ought to be thought of as the same vector.