机器学习中不同的距离定义汇总（三：集合的相似度）

本文主要参考了此博客和文末列出的参考内容

杰卡德距离（Jaccard Distance）和杰卡德相似系数（Jaccard Similarity Coefficient）

杰卡德相似系数

两个集合A和B交集元素的个数在A、B并集中所占的比例，称为这两个集合的杰卡德系数，用符号 J(A,B) 表示。杰卡德相似系数是衡量两个集合相似度的一种指标（余弦距离也可以用来衡量两个集合的相似度）。

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

杰卡德距离

与杰卡德相似系数相反的概念是杰卡德距离（Jaccard Distance），可以用如下公式来表示：

\[ \mathrm{J}_{\delta}=1-\mathrm{J}(\mathrm{A}, \mathrm{B})=\frac{|\mathrm{A} \cup \mathrm{B}|-|\mathrm{A} \cap \mathrm{B}|}{|\mathrm{A} \cup \mathrm{B}|} \]

杰卡德距离用两个两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。

jaccard相似度的缺点是值适用于二元数据的集合。

应用

假设样本A和样本B是两个n维向量，而且所有维度的取值都是0或1。例如，A（0,1,1,0）和B（1,0,1,1）。我们将样本看成一个集合，1表示集合包含该元素，0表示集合不包含该元素。

p：样本A与B都是1的维度的个数

q：样本A是1而B是0的维度的个数

r：样本A是0而B是1的维度的个数

s：样本A与B都是0的维度的个数

那么样本A与B的杰卡德相似系数可以表示为：

\[ \mathrm{J} = \frac{p}{p+q+r} \]

此处分母之所以不加s的原因在于：

对于杰卡德相似系数或杰卡德距离来说，它处理的都是非对称二元变量。非对称的意思是指状态的两个输出不是同等重要的，例如，疾病检查的阳性和阴性结果。

按照惯例，我们将比较重要的输出结果，通常也是出现几率较小的结果编码为1（例如HIV阳性），而将另一种结果编码为0（例如HIV阴性）。给定两个非对称二元变量，两个都取1的情况（正匹配）认为比两个都取0的情况（负匹配）更有意义。负匹配的数量s认为是不重要的，因此在计算时忽略。

Jaccard的应用很广，最常见的应用就是求两个文档的文本相似度，通过一定的办法(比如shinging)对文档进行分词，构成词语的集合，再计算Jaccard相似度即可。当然，用途还有很多，不过大多需要结合其他的技术。比如：

python实现：

def JaccardDistance(x, y):
    import numpy as np

    x=np.asarray(x, np.int32)
    y=np.asarray(y, np.int32)

    return np.double(np.bitwise_and((x!=y), np.bitwise_or(x!=0, y!=0)).sum())/np.double(np.bitwise_or(x!=0, y!=0).sum())

Ochiia系数（Ochiia Coefficient）

Ochiia系数（Ochiia Coefficient）指的是两个集合的交集大小与两个集合大小的几何平均值的壁纸，它是余弦相似性的一种形式：

\[ K(A, B)=\frac{|A \cap B|}{\sqrt{|A| \times|B|}} \]

共词矩阵到相似矩阵：用Ochiia系数

Dice系数（Dice Coefficient）

Dice系数（Dice Coefficient）用于度量两个集合的相似性，因为可以把字符串理解为一种集合，因此Dice系数也会用于度量字符串的相似性：

\[ \operatorname{Dice}(A, B)=\frac{2|A \cap B|}{|A|+|B|} \]

其中，分子是A与B的交集数量的两倍，分母为A和B的长度之和，所以他的范围也在0到1之间。从公式看，Dice系数和杰卡德相似系数非常的类似。杰卡德相似系数是在分子和分母上都减去了\(|A \cap B|\)

豪斯多夫距离（Hausdorff Distance）

设X和Y是度量空间M的两个紧子集。那么豪斯多夫距离dH(X,Y)是最小的数r使得X的闭r—邻域包含Y，Y的闭r—邻域也包含X。换句话说，若d(x, y)表M中的距离，那么

\[ d_{\mathrm{H}}(X, Y)=\max \left\{\sup _{x \in X} \inf _{y \in Y} d(x, y), \sup _{y \in Y} \inf _{x \in X} d(x, y)\right\} \]

这距离函数令M的所有紧子集组成的集成为度量空间，且记为F(M)。F(M)的拓扑只是依赖于M的拓扑。若M是紧的，则F(M)也是。

豪斯多夫空间也可以照样定义在M的闭非紧子集上，但距离可能是无限大，F(M)的拓扑不只依赖于M的拓扑，也依赖于M的特有度量。非闭子集间的豪斯多夫距离可以定义为它们的闭包的豪斯多夫距离。这给予M的所有子集组成的集一个伪度量。（两个有相同闭包的子集的豪斯多夫距离是零）。

在欧几里得几何常用一个类似概念，称为在等距同构下的豪斯多夫距离。设X 和Y是欧几里得空间中两个紧的图形，则DH(X,Y)是dH(I(X),Y)取所有欧几里得空间的保距变换I的最小值。这距离量度X和Y离等距差多少。

豪斯多夫距离（Hausdorff Distance）是在度量空间中任意两个集合之间定义的一种距离。给定欧氏空间中的两点集\(A=\{a_1,a_2,\dots,a_n\}\)和\(B=\{b_1,b_2,\dots,b_n\}\)，则豪斯多夫距离为：

\[ H(A,B)=\max(h(A,B), h(B,A)) \]

其中，\(h(A, B)=\max _{a \in A} \min _{b \in B} \| a-b \|\)，H(A,B)称为称为双向豪斯多夫距离，h ( A , B ) h(A, B)h(A,B)称为从点集A AA到点集B BB的单向豪斯多夫距离。相应地，h ( B , A ) h(B, A)h(B,A)称为从点集B BB到点集A AA的单向豪斯多夫距离。

参考